[Closed] Find self intersections

unfortunately there is no built-in mxs function that returns average (or render) normal of a vertex. getNormal returns the normal of the first face that uses this vertex. so it can’t be used in general case to “push” the mesh.

Than you Denis, good to know. By the way, this also leaks memory

(
 	m1 = heapfree
 	n = 0
 	for k=1 to 10000 do n += 1
 	format "memory:%
" (m1 - heapfree)
 )

 From the Help:

“getNormal <mesh> <vert_index_integer>
Returns the normal at the indexed vertex’s position as a point3. The normal is based on the faces that use the vertex and the smoothing groups assigned to those faces.”

 I've tried this, and the result is that it intersects with every face. That's why I'm using the slightly offset mesh to test against.

with the “+=” operation the max creates every time new instance of point3 value and doesn’t free memory for old one. it’s a known source of the memory leak. there is a trick how avoid this leaking:
This tip made this part of the code about 7 times more memory efficient!

start = timestamp()
mem = heapfree
local theOffsetMultiplier = 0.001 –the offset for the copied mesh
local theCopiedMesh = copy theMesh
extrudeFace theCopiedMesh #{1…theCopiedMesh.numfaces} theOffsetMultiplier 0 dir:#independent
format “offset mesh:% ms mem:%
” (timestamp() – start) (mem-heapfree)
This is a good suggestion as well. I was so proud of myself finally getting into the normals and figuring out the solution. But this method seems to do the same, and a lot quicker.
Thanks for the help guys! Here’s the updated code

function fn_getFaceSelfIntersection theMesh gridsize = if isKindOf theMesh editable_mesh then
    (	
    	/*<FUNCTION>
    	Description:
    		Detects self-intersecting faces on a mesh
    		Calculating self intersection is tricky. It doesn't work if you intersect rays from the edges with its own faces.
    		Every ray is a hit in that case
    		A hack is to offset a copy of the mesh ever so slightly and intersect the original with the copy. Inspired by the
    		3d printing toolbox from blender
    		Other references:
    			 http://forums.cgsociety.org/showthread.php?f=98&t=1090782&highlight=intersect 
    			 http://forums.cgsociety.org/showthread.php?f=98&t=838041&highlight=intersection 	
    	Arguments:
    		<mesh object> theMesh: the object we're checking self-intersections on
    		<integer> gridSize: the size of the grid for the intersection algorithm
    	Return:
    		intersecting faces are painted in the viewport and selected in the mesh
    	</FUNCTION>*/
    	
    	--set up the intersect grid
    	start = timestamp()
    	mem = heapfree
    	local cgrid = RayMeshGridIntersect()
    	cgrid.initialize gridsize
    	cgrid.addNode theMesh
    	cgrid.buildGrid()
    	local intersectsegfn = cgrid.intersectSegment
    	format "setup grid:% ms mem:%
" (timestamp() - start) (mem-heapfree)
     
    	--create a copy of the mesh and offset it ever so slightly
    	--Suggestion by polytools3d  http://forums.cgsociety.org/showpost.php?p=7622514&postcount=4 
    	--works very fast
    	start = timestamp()
    	mem = heapfree	
    	local theOffsetMultiplier = 0.001 --the offset for the copied mesh
    	local theCopiedMesh = copy theMesh
    	setFaceSelection theCopiedMesh #{1..theCopiedMesh.numfaces}
	extrudeFace theCopiedMesh #{1..theCopiedMesh.numfaces} theOffsetMultiplier 100
	--if there were open edges, this line deletes the extra created faces
	meshop.deleteFaces theCopiedMesh (#{1..theCopiedMesh.numfaces} - (getFaceSelection theCopiedMesh)) 

    	format "offset mesh:% ms mem:%
" (timestamp() - start) (mem-heapfree)
    	
    	--perform the intersection between the original mesh and the copy
    	start = timestamp()
    	mem = heapfree	
    	local theMeshfaces = #{}
    	local numfaces = theCopiedMesh.numfaces
    	for i = 1 to numfaces do
    	(
    		local fverts = getface theCopiedMesh i
    		local a = getVert theCopiedMesh fverts.x
    		local b = getVert theCopiedMesh fverts.y
    		local c = getVert theCopiedMesh fverts.z
    		if intersectsegfn a b true > 0 then theMeshfaces[i] = true
    		if intersectsegfn b c true > 0 then theMeshfaces[i] = true
    		if intersectsegfn c a true > 0 then theMeshfaces[i] = true
    	)
     
    	delete theCopiedMesh --delete the copy. We don't need it
    	
    	--color the object to indicate the self-intersecting faces
    	meshop.setFaceColor theMesh 0 theMeshfaces (color 255 0 0)	
    	theMesh.vertexColorType = #color
    	theMesh.shadeVertexColors = 1
    	theMesh.showVertexColors = true	
    	theMesh.selectedfaces = theMeshfaces
    	
    	cgrid.free()
    	format "intersect mesh:% ms mem:%
" (timestamp() - start) (mem-heapfree)
    )else format "% is not an editable mesh, please convert it first.
" theMesh.name
    
    
    (
    	delete objects
    	local theObject = Torus_Knot Base_Curve:0 Segments:120 sides:36 radius:50 radius2:20 p:1 q:2 Eccentricity:1 Twist:0 Lumps:2 Lump_Height:1.8 Lump_Offset:123
    -- 	local theObject = box()
    	converttomesh theObject
    	local start = timestamp()
    	local mem = heapfree
    	fn_getFaceSelfIntersection theObject 25
    	format "total:% ms mem:%
" (timestamp() - start) (mem-heapfree)
    )

Well, I guess that’s how Max is… You love it, then you hate it, then you love it again, and so on…

True, I’ve edited my previous post. About intersecting twice for most edges. I’m not sure about a solution for this. Any ideas?

 For every shared edge, the order of its vertices is reversed, so if you have a face with vertices [1,2,3], then an adjacent face could have vertices [2,1,8]. So we have edge (1,2), (2,3) and (3,1) for face A and (2,1), (1,8) and (8,2) for face B.

If we already checked the edge with vertices (1,2), there is no need to check vertices (2,1), as they are the same edge (actually they are different but share the same vertices). This was supposed to be obvious, but I didn’t realize it until Denis brought it to the table in another Thread. This is what “fverts.x<fverts.y” does. This is not the case for the open edges, so we need to get them first and treat them separately.
 
 Given a triangle face N, its edges are N*3-2, N*3-1, N*3. So for face 1 we have edge 1, edge 2, edge 3, for face 20 we have edge 58, edge 59, and edge 60. This is what [i*3-2] does. Usually, but not always, the third shared edge is a hidden edge.
 
 Once the check passed, we get the edges for each of the 2 vertices, and the ones they shared are the edges that use the same vertices (edgesA*edgesB).
 
 Now we have 2 edges that belong to 2 different faces (A, B) but share their vertices so if A is intersecting another face C, so must be B.

if fverts.x < fverts.y or meshOpenEdges[i*3-2] do (
     	if intersectsegfn a b true > 0 do (
     		local edgesA = cGetEdgesUsingVert theCopiedMesh fverts.x
     		local edgesB = cGetEdgesUsingVert theCopiedMesh fverts.y
     		local faces = cGetFacesUsingEdge theCopiedMesh (edgesA*edgesB)
     		join theMeshfaces faces
     		for f in faces do deleteItem meshFaces f
     	)
     )