Sometimes a mesh is self intersecting.
How can I determine the faces that intersect and delete them?
Thank you.
there are various ways to detect those faces in the mesh but it quickly can get very complex. You might try the script linked here and note the other sugestions in the same thread.
c.
@clement I had seen that script, but it is taking a while before it completes.
When I use MeshRepair it instantly tells me it has X intersections. How does Rhino knows this so fast? Is there a function in Rhino to locate these intersections?
@jordy1989, i think this has been requested often but there is nothing i know apart from TestMMX which is not reliable / usable.
I don’t know but would love to have a command to locate these intersections and the places where it reports that face normals differ from vertex normals. Currently I have to use external software to detect these and repair meshes coming from laser scanning.
c.
I have created a command for this a while back, because as far as I know there are no SDK functions to do this.
protected override Result RunCommand(RhinoDoc doc, RunMode mode)
{
ObjRef mRef;
Result res = RhinoGet.GetOneObject("Select mesh", false, ObjectType.Mesh, out mRef);
if (res != Result.Success || null == mRef)
return res;
Mesh mesh = mRef.Mesh();
if (null == mesh)
return Result.Failure;
MeshTopologyEdgeList topEdges = mesh.TopologyEdges;
MeshTopologyVertexList topVertices = mesh.TopologyVertices;
ConcurrentList<Line> intersectingEdges = new ConcurrentList<Line>();
Parallel.For(0, topEdges.Count, ei =>
{
ISet<int> set = new HashSet<int>();
IndexPair ij = topEdges.GetTopologyVertices(ei);
foreach (var x in topVertices.ConnectedFaces(ij.I))
set.Add(x);
foreach (var x in topVertices.ConnectedFaces(ij.J))
set.Add(x);
Line edgeLine = topEdges.EdgeLine(ei);
int[] faces;
Rhino.Geometry.Intersect.Intersection.MeshLine(mesh, edgeLine, out faces);
if (null != faces)
{
ISet<int> faceSet = new HashSet<int>(faces);
faceSet.ExceptWith(set);
if (faceSet.Any())
{
intersectingEdges.Add(edgeLine);
}
}
});
// deselect the mesh
doc.Objects.Select(mRef, false);
RhinoApp.WriteLine("{0} face edges found that intersect mesh faces.", intersectingEdges.Count);
// add the intersecting edges and select them
if (intersectingEdges.Any())
{
IEnumerable<Guid> guids = intersectingEdges.Select(l => doc.Objects.AddLine(l));
doc.Objects.Select(guids);
}
return Result.Success;
1 Like
Why this isn’t integrated into the current release?
@menno could I ask you to convert this as a button for us (normal people not good in programming)?
Ciao!
The same code, but now in Python. You should be able to get this behind a button using the workspace editor.
import Rhino
import rhinoscriptsyntax as rs
import scriptcontext
def MarkSelfIntersectingMeshFaces():
go = Rhino.Input.Custom.GetObject()
go.SetCommandPrompt("Select mesh to mark selfintersections")
go.GeometryFilter = Rhino.DocObjects.ObjectType.Mesh
go.SubObjectSelect = False
go.GroupSelect = False
go.Get()
if go.CommandResult()!=Rhino.Commands.Result.Success:
return Rhino.Commands.Result.Cancel
mesh = go.Object(0).Mesh()
rs.UnselectAllObjects()
topEdges = mesh.TopologyEdges
topVertices = mesh.TopologyVertices
intersectingEdges = []
for ei in xrange(0, topEdges.Count):
ij = topEdges.GetTopologyVertices(ei)
faceIndexSet = set(topVertices.ConnectedFaces(ij.I))
faceIndexSet.update(topVertices.ConnectedFaces(ij.J))
edgeLine = topEdges.EdgeLine(ei)
rc, faces = Rhino.Geometry.Intersect.Intersection.MeshLine(mesh, edgeLine)
if faces is not None:
faceSet = set(faces)
faceSet = faceSet - faceIndexSet
if len(faceSet) > 0:
intersectingEdges.append(edgeLine)
for i in xrange(0, len(intersectingEdges)):
edge = intersectingEdges[i]
rs.AddLine(edge.From, edge.To)
if (__name__=="__main__"):
MarkSelfIntersectingMeshFaces()
3 Likes
That’s great!
THANKS!!!
If you are using the Rhino WIP, you can use MeshFaceList.GetClashingFacePairs.
The Rhino WIP C++ SDK equivalent is ON_Mesh::GetClashingFacePairs.
– Dale
Hi @menno,
I tried to compile this code, but wonder what implementation of ConcurrentList you used. It doesn’t seem to be included in .NET standard libraries.
Doing some googling I found an implementation which inherited from a ThreadSafeList<T>, but also this one seems to be of unknown origin.
Anyway, I used ConcurrentBag instead, which I hope is at least useful since the iterations done upon it is done outside the Parallel.For-loop (to remove any intersected faces, using an extra face indices list for that).
Apart from the above, I was a bit surprised to notice that even though I deleted, say two faces that were found intersected, one of them still remained after removal of the face and compacting the mesh. So I made a breaking loop, max count 10, to iterate until all intersecting edges (& faces) were removed. It’s not very fast though…
// Rolf
Yeah, the concurrent list is something I made myself. I’m surprised about your finding re face removal, can you post an example? Note that I am away from my computer for a while, so don’t expect anything soon 
Edit 2: Fixed the bug (fixed by calling Distinct and OrderDescending on indicies list) in the code far below. :
// #foreach( var faceIndex in isectFaceIndexes )
var tmp_distinctDescending = isectFaceIndexes.Distinct().OrderByDescending(x => x).ToArray<int>();
foreach ( var faceIndex in tmp_distinctDescending )
Edit: Updated code: Added number of extra attempts (Cnt+ laps) to remove self intersections + image:
Absolutely yes.
I only tested the code below briefly, on one single mesh, but any self intersections found are removed.
The component repeats attempts to remove faces up to ten (10) times, but outputs only the first set of found edges & faces, for visualization purposes. After the first round in the function, with removal option set to true, the number of edges & faces decreases until they’re gone (function returns false). Face removal is optional.
Please let me know if you find something nasty in this.
using System;
using System.Collections.Generic;
using System.Threading.Tasks;
using System.Linq;
using Rhino.Geometry;
using Rhino.Geometry.Collections;
using Grasshopper.Kernel;
namespace MennoMesh // :)
{
public class GH_MeshSelfIntersect: GH_Component
{
public GH_MeshSelfIntersect()
: base( "Mesh Self Intersect", "MSelfIsect",
"Test for self intersecting faces and, optionally,\n"
+ "removing them.\n\nProvided by RIL, based on an algorithm by \"Menno\".",
"Menno", "Mesh" )
{
}
int IN_Mesh;
int IN_Remove;
int OUT_Mesh;
int OUT_IntersectingEdges;
int OUT_IntersectingFaces;
int OUT_Cnt;
protected override void RegisterInputParams(GH_Component.GH_InputParamManager pManager)
{
IN_Mesh = pManager.AddMeshParameter( "Mesh", "M", "Input Mesh to be examined", GH_ParamAccess.item );
IN_Remove = pManager.AddBooleanParameter( "Remove Intersecting Edges", "R", "Remove Intersecting edges if any were found. Default is false.", GH_ParamAccess.item, false );
}
protected override void RegisterOutputParams(GH_Component.GH_OutputParamManager pManager)
{
OUT_Mesh = pManager.AddMeshParameter( "Mesh", "M2", "If option = remove, then a mesh copy is output, otherwise the original.", GH_ParamAccess.item );
OUT_IntersectingEdges = pManager.AddLineParameter( "Self intersecting edges", "IE", "All the self intersecting edges being found.", GH_ParamAccess.list );
OUT_IntersectingFaces = pManager.AddMeshFaceParameter( "Self intersected faces", "IF", "All the self intersected face involved.", GH_ParamAccess.list );
OUT_Cnt = pManager.AddIntegerParameter( "Extra attempts", "Cnt+", "Number of *extra* iterations trying to remove self intersecting faces.", GH_ParamAccess.item );
}
IGH_DataAccess m_DA = null;
protected override void SolveInstance(IGH_DataAccess DA)
{
// Provide access to other member methods
m_DA = DA;
Mesh mesh_tmp = null;
if( !m_DA.GetData( IN_Mesh, ref mesh_tmp ) || mesh_tmp == null )
return;
bool m_remove = false;
if( !m_DA.GetData( IN_Remove, ref m_remove ) )
m_remove = false;
// Copy mesh only if about to modify
Mesh m_mesh = null;
if( m_remove )
m_mesh = mesh_tmp.DuplicateMesh();
else
m_mesh = mesh_tmp;
// ---------------------------
// The loop is called only if
// option remove intersections
// ---------------------------
var extraLaps = 0;
if( m_remove )
{
//
// Loop until no more intersections are found, but
// only up to "maxAttemptsCnt" number of times
//
const int maxAttemptsCnt = 10;
for( var r = 0; r < maxAttemptsCnt; r++ )
{
if( !TryFindSelfIntersections( m_mesh, true, r ) )
break;
extraLaps += 1;
}
}
else
TryFindSelfIntersections( m_mesh, false, 0 );
// OUTPUT mesh copy
DA.SetData( OUT_Cnt, extraLaps );
DA.SetData( OUT_Mesh, m_mesh );
}
private bool TryFindSelfIntersections(Mesh m_mesh, bool remove, int lapsCount)
{
var result = false;
// -----------------------------------------
// Locally defined lists due to Parallel.For
// -----------------------------------------
Rhino.Geometry.Collections.MeshTopologyEdgeList topEdges = m_mesh.TopologyEdges;
Rhino.Geometry.Collections.MeshTopologyVertexList topVertices = m_mesh.TopologyVertices;
//System.Collections.Concurrent.ConcurrentList<Line> intersectingEdges = new ConcurrentList<Line>();
var intersectingEdges = new System.Collections.Concurrent.ConcurrentBag<Line>();
var isectFaceIndexes = new System.Collections.Concurrent.ConcurrentBag<int>();
Parallel.For( 0, topEdges.Count, ei =>
{
//
// Collect topology face indices
//
ISet<int> hash_set = new HashSet<int>();
Rhino.IndexPair ij = topEdges.GetTopologyVertices( ei );
foreach( var x in topVertices.ConnectedFaces( ij.I ) )
hash_set.Add( x );
foreach( var x in topVertices.ConnectedFaces( ij.J ) )
hash_set.Add( x );
//
// Test for intersections
//
Line edgeLine = topEdges.EdgeLine( ei );
int[] faces;
Rhino.Geometry.Intersect.Intersection.MeshLine( m_mesh, edgeLine, out faces );
//
// Collect edges and faces for
// output and later removal
//
if( faces != null )
{
//
// Intersections occured. Now remove (intersect) faces from faceSet which
// already exists in the topology ( = hash_set collection).
//
ISet<int> faceSet = new HashSet<int>( faces );
faceSet.ExceptWith( hash_set );
//
// Remaining content is a duplicate - to be removed!
//
if( faceSet.Any() )
{
intersectingEdges.Add( edgeLine );
for( int f = 0; f < faceSet.Count; f++ )
{
var ix = faceSet.ElementAt( f );
isectFaceIndexes.Add( ix );
}
}
}
} );
// End parallel
// ---------------------
// OUTPUT INTERSECTIONS
// ---------------------
// Run this only on first call
if( lapsCount == 0 )
{
if( intersectingEdges.Any() )
{
// EDGES
m_DA.SetDataList( OUT_IntersectingEdges, intersectingEdges );
// FACES
var faceList = new List<MeshFace>();
foreach( var faceIndex in isectFaceIndexes )
{
faceList.Add( m_mesh.Faces[faceIndex] );
}
if( faceList.Count > 0 )
m_DA.SetDataList( OUT_IntersectingFaces, faceList );
}
}
// --------------------
// DELETE INTERSECTIONS
// --------------------
if( remove )
{
//
// Removing duplicates ("distinct") and sorting descending.
// This will remove faces from the end of the list first.
//
// #foreach( var faceIndex in isectFaceIndexes )
var tmp_distinctDescending = isectFaceIndexes.Distinct().OrderByDescending(x => x).ToArray<int>();
foreach ( var faceIndex in tmp_distinctDescending )
{
m_mesh.Faces.RemoveAt( faceIndex );
}
m_mesh.Compact();
}
result = intersectingEdges.Any();
return result;
}
}
// Only Icon and Guid omitted from class
//
// Rolf
Ah, suddenly it struck me while making my coffee. I wonder if the failed attempts to remove all faces at the first attempt simply depends on the ORDER in which the faces are removed.
The following may be a bug to be fixed: If removing face index [0] before [1] in a list, then the second removal actually removes index [2] from the initial list.
So the code above perhaps is removing other than self intersecting faces after the first face was removed … until it finds the remaining self intersecting faces? Hm, gotta debug this carefully (but not for another 24 hours, busy, busy).
In any case, to make sure nothing bad happens on removal, the following can be changed in the code above: The indices in the list isectFaceIndexes first to be sorted before starting to delete the indexed faces, and, traverse in reversed order (from biggest index down to lowert index). Then the potential bug is eliminated.
// Rolf
If you do this in a loop the indeed changing collections works like this. The steps you think about are the only way to go about it: collect indices, sort descending, go over that index list to remove.
There is no bug in the core Rhino code, nor in .NET, regarding that.
1 Like
I agree. And I also really meant that it was me that had introduced the bug in my code by overlooking the index order while removing. Clumpsy me.
// Rolf
1 Like
I am a Python fan so I tried your code to fix my mesh with 613,955 faces. It ran fast, only 18 sec, but did not find the case I was interested in:
I am not sure why it fails for this case.
Regards,
Terry.
Hi Rolf,
I’ve been trying to recreate your MSelfIsect component (I’m very new to this). Unfortunately, I am coming up short. If you are comfortable sharing, I would really appreciate it if you could share your component so I can investigate where I am messing up. Thanks.
Best,
Kevin