# BRepMesh_Incremental Mesh - Algorithm

Hi Forum,

i actually try to do some basic research. In other cad software there are some libraries which are doing the tesselation part. For example cad exchanger has the possibilty to use either Netgen or Mefisto to create the triangle mesh out of the CAD boundary representation.

Does someone know, which algorithm is used by the BRepMesh_IncrementalMesh function? I did only find this information page: https://www.opencascade.com/content/mesh-framework

Would be very happy for some more information!

Does someone know, which algorithm is used by the BRepMesh_IncrementalMesh function?

BRepMesh computes Delaunay's triangulation with the algorithm of Watson, see docs:

Basically, it is incremental algorithm (hence, incremental in it's name), which splits triangles until result triangulation satisfies deflection criteria.
The mesh is suitable for visualization and for many algorithms with controlled precision:

I did only find this information page: https://www.opencascade.com/content/mesh-framework

Mesh Framework (OMF) is dedicated component for working with mesh structures (like Boolean operations, modification, etc.), so it is unrelated to BRepMesh.
There is also Express Mesh component implementing different algorithm (producing more structured mesh with desired element size, and, optionally, quad-only mesh):

has the possibilty to use either Netgen

Netgen is interesting library, but, unfortunately, looks incomplete - it is too slow, unstable (when tested on complex geometry imported from STEP)
and has different control parameters (so that it is difficult comparing it to BRepMesh or replacing it in existing algorithms).

Hi Kirill,

I came across another question about the meshing algorithms. Is it true that every meshed step solid is always a watertight mesh, because the step solid itstelf is watertight? Or do I have to do some postprocessing to be sure that it is watertight?

What be really nice if I can get another answer!

BRepMesh algorithm (and Express Mesh) takes into account closeness of the shell, so that generated triangulation should have no holes in valid case.
Based on this assumption, OCCT 3D Viewer automatically enables back face culling in this case, improving rendering performance and eliminating extra visual artifacts on boundaries.
Otherwise, enabling back-face culling for non-closed triangulation will produce visual artifacts where holes would take place.
You can also read description of my pull request to glTF specification about watertight mesh flag:
https://github.com/KhronosGroup/glTF/pull/922

So, in general, mesh generated by OCCT for valid closed shell can be considered watertight if meshing algorithm succeeded (e.g. there are no face with NULL triangulation).
But apart from this assumption, there is no guarantee that result triangulation is actually watertight - so if this property is critical for your algorithm to provide correct results, it might be better verifying watertightness.

Note that this considers only closeness of mesh for a given solid only - in general case (model consisting of multiple solids, overlapping solids) more sophisticated analysis/processing might be required.

Hi Kirill,

thanks for the reply. For now I did not recover any not watertight mesh, which was calculated by brep incremental mesh. But good to know that it in some cases can happen.

Because I am no expert in working with triangle meshes, can you give me a hint, how to check if a mesh is watertight. I actually know, what watertight means. Do I have to check if every triangle has at least two neighbouring triangles?

Sorry, I have expected that you know better about mesh properties important for your case.
I haven't wrote any watertight triangulation checks before.
Though it does not look like checking each triangle having >=2 neighbours is enough...

.

On each sub shape I did a triangulation using the BRepMesh function.

First of all, it is better calling BRepMesh for all shapes at once rather then calling it for each sub-shape, to ensure that shared parts will be tessellated in consistent way.
Another point is that BRep defines Solid as a set of Faces (TopoDS_Face), not necessarily one face - e.g. simple Box has 6 Faces.
Each Face has its own triangulation (Poly_Triangulation), which might be open - only aggregation of triangulations for all Faces within Solid can be considered as closed mesh.

I found that the code in BRepMesh_Delaun::compute() will repeat do insert the first vertex, It's not necessary, isn't it?

code line 271 in BRepMesh_Delaun::compute() is createTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges );

and in createTrianglesOnNewVertices( theVertexIndexes );

Line 439:  Standard_Integer anIndex = theVertexIndexes.Lower();
Line 440:  Standard_Integer anUpper = theVertexIndexes.Upper();
Line 441:  for( ; anIndex <= anUpper; ++anIndex )

still from the start  vertex to do insert.

Of course, I know this operation has no effect on the results

Hi,

would it be possible to share an example how to triangulate a whole step file, containing several shapes or faces?

Currently I triangulate face after face, but the watertightness, as mentioned above, is important for me, too.

Thanks,
Thomas

Hello Thomas,

In Open CASCADE Technology, the triangulations produced by BRepMesh_IncrementalMesh are stored per-face, in Poly_Triangulation objects.

If the original shape is watertight, the individual triangulations on faces should have same number and positions of nodes along shared edges.

You just need to write an algorithm to take all individual Poly_Triangulation objects from faces and merge them, taking into account the nodes along shared edges.

We shall be glad to help you write this or any other specific algorithm – please, contact us for further information.

Best regards,

Forum supervisor