A couple of discoveries:
- It really depends if you want your mesh to be conformal or not. The non-conformal meshes are not "watertight," but are easier to refine into.
- It might not be necessary to refine the initial triangulation. Sometimes, it is enough to refine the derived triangulation obtained by merging the Poly_Triangulation patches using nodal gluing (check out the MeshMerge tool). However, in such a scenario your mesh data structure should preserve back-references to the originating CAD faces. I have this simplistic data structure for that purpose.
- A question of a good mesh data structure that would allow for local refinement is really a key one. Here I wouldn't vote for any external package as, to remain on the cutting edge, you might need to invent something new depending on your app. I'm also close to thinking that you'd better store all mesh edges right away, with the back pointers to mesh elements. It's harder to maintain than just plain vectors of vertices plus triangles, but it really pays off once you're there. I did not follow that path though.
Down the road, I tried a couple of things to tweak BRepMesh to generate somewhat more dense triangulations. What I did was:
- Inserting internal vertices to faces like that (OpenCascade claims to keep internal vertices respected during the meshing process, and, indeed, I see them added to the BRepMesh internal structures; however, this leads to nothing in terms of constraint triangulation; I only saw that the presence of an extra vertex might introduce some degenerated triangles):
const double u = 0.75*(uMin + uMax);
const double v = 0.35*(vMin + vMax);
gp_Pnt P = bas.Value(u, v);
TopoDS_Vertex V = BRepBuilderAPI_MakeVertex(P);
BRep_Builder().UpdateVertex( V, u, v, face, Precision::Confusion() );
- Playing with all parameters of the mesher. Yeah, there's this "minSize" thingy that does not work or works in somewhat obscure ways that it's impossible to rely upon.
- Converting input geometries to splines. Converting your model to splines is the last thing you wanna do, and, thank goodness, it did not work either
The conclusion is that you'd never get any better than this:
All my attempts to refine it with midpoint/midedge splits and edge flipping sort of slightly improved the situation, but not radically, and I am not happy with the results so far. The main problem is all these skinny triangles that are hard to get rid of. Now I'm thinking to try out octree-based layouts for planar faces. Even without merging them nicely across the boundaries with the rest of the model, you might get a good enough grid for some specific applications, like what I'm looking for (face accessibility analysis and thickness analysis).
Another option would be to try global remeshing, like something reported in [Botsch, M., & Kobbelt, L. (2004). A remeshing approach to multiresolution modeling. ACM International Conference Proceeding Series, 71, 185–192. https://doi.org/10.1145/1057432.1057457]
. They use local mesh editing procedures, namely a few cycles (~5) like this:
- Midpoint split all the edges that are longer than 4/3*l (where l is the target edge length).
- Collapse all edges shorter than 4/5*l into their midpoints.
- Flip edges in order to minimize the deviation from valence 6 (or 4 on boundaries).
- Relocate vertices on the surface by tangential smoothing.
Why I think this paper is promising is that it claims to get rid of the degenerated or sliver triangles that kinda sucked me out. For the ray-based algorithms, I'd like to have higher-regularity meshes, and it is appealing to convert the initial triangulation into such. Simply because if you modify your input, you can simplify further processing. Not to mention that the algorithms like that can be reused down the road in a multitude of other algorithms I make living from. On the other hand, edge collapse (the gun to kill slivers) will inevitably distort the original boundary of a CAD face (well, its discretized version), and that does not sound good. Should I restrict it from touching the boundaries?
Btw, here is a nice presentation of various remeshing approaches
. I skimmed it over searching for references, and it was quite instructive.
To confess, mesh refinement looks quite desperate as of now when I spent a week or so working on the basic refinement techniques (triangle subdivision, edge flipping, midedge subdivision) intensively. But I still miss quite a bunch of important ingredients (see the picture above for a gentleman's set of refining operators) and a good strategy for refinement. What I also discovered is that there's not much you can reuse from the Internet. For example, the famous J. R. Shewchuk's Triangle
requires a license for commercial use, and that is something I could not afford for a couple of reasons.