Mesh has --- pairs of faces that intersect each other

I’m getting following error when I’m using the attached script here.
GUC_RD50_quad.3dm (419.4 KB)

script_error

Can you help me with this?

Getting the following error when I use the attached script.
GUC_RD50_quad.3dm (419.4 KB)

Any idea why this is happening?

In Rhino 7 there is a new command useful for this purpose: MeshSelfIntersect.

@gianpaolo_savio, @stevebaer,

On my large mesh with 100M faces, I have run
(1) pairs = meshGeo.Faces.GetClashingFacePairs(-1) in 219 sec in a Python script
(2) ON_SimpleArray<ON_2dex> pairs; mesh->GetClashingFacePairs(-1, pairs); in 300 sec in a C++ script
(3) MeshSelfIntersect in 360 sec from the Rhino Command line. This is what you suggested.
Are these different performances to be expected? The Python method which uses a RhinoCommon function is the fastest which surprized me. Is there a still faster method, something that runs in 10 sec or so? I noticed that not much parallelism was used in any of these function so significant speedup may be possible.

When looking for non-manifold edges in this mesh, I tried Rhino’s
manifoldMesh = meshGeo.ExtractNonManifoldEdges(False)
but this took 64 sec to run. I wrote my own version with the edges sorted into bins by their centers so I could run the checks in parallel. This found the same edges in 6 sec. Thus I am looking for a way to find self-intersecting faces in a similar time so that I can keep my mesh import tool quick.

Regards,
Terry.

2 Likes

I am close to finishing my C++ code to find intersecting faces. For my 100M faces mesh test case, it runs in 15 sec or about 10x faster than any of the Rhino tools I have tried. This is a big help went in comes to handling large meshes efficiently. It uses a combination of (1) binning faces by XY location with 2-way parallel operations (2) a large number of bins, 1M for the 100M faces mesh, in order to reduce the overhead of n^2 checks = 5x10^16 by a million fold down to 5x10^10 (3) Parallel checking for face intersections using the Moeller-Trumbore ray-triangle intersection algorithm after (4) pre-filtering the faces by the distance from each other vs the sum of the radius of their enclosing spheres. For quad faces, the quad is handled as 2-triangles which could be accommodated in the ray intersection algorithm with less than 50% overhead.

The code is focused on meshes like terraines which have large X & Y variations and smaller Z variations. For meshes with more equal XYZ variations it may be necessary to replace the 2D bins with a 3D tree but this will cost performance and may only be necessary in a few cases. If only 2 of the 3 dimensions have large variations, the mesh can be oriented to put the lesser variation in the Z direction and this code should work well. I could add that as an automatic step if requested.

My first stab at this ran over 1000 sec for the 100M faces test case. Way slower than Rhino. It took many iterations to get this down to 15 sec but the voyage was exciting and the destination amazing.

At some point I will put all the code on Github so others can benefit possibly.

Regards,
Terry.

2 Likes