Find self intersections

[denisT]

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)
  )

true. because max creates an instance of integer ;)… but in case a.x += x, the max uses a chuck of pre-allocated memory. sometimes i use this trick to minimize “integer-leak” as well

[denisT]

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.”

try to autosmooth(>90 deg) a cube. and check the normal. that will not be an average value.

[denisT]

true. because max creates an instance of integer ;)… but in case a.x += x, the max uses a chuck of pre-allocated memory. sometimes i use this trick to minimize “integer-leak” as well

sometimes a little leak causes big problem… for example in scripted controllers.

[grabjacket]

the question is -
What is self-intersection? if the self-intersection is the fact that any edge of the mesh intersects with any face, probably it will be easier and faster just cast a ray from every vertex in direction of surrounded edges and check intersection.

 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)
    )

[PolyTools3D]

I am glad the extrudeFace worked for your needs. However, I would not rely on it as a generic approach for every case.

If the mesh has open edges, then extrudeFaces will add faces for every open edge, so you’ll need either to delete the remaining faces or to change to avoid an error:

local numfaces = theCopiedMesh.numfaces
to:
local numfaces = theMesh.numfaces

Also, intersectSegment is checking twice the “same” edge for every not open edge, so there might be some way to improve it.

[PolyTools3D]

try to autosmooth(>90 deg) a cube. and check the normal. that will not be an average value.

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

[grabjacket]

I am glad the extrudeFace worked for your needs. However, I would not rely on it as a generic approach for every case.

If the mesh has open edges, then extrudeFaces will add faces for every open edge, so you’ll need either to delete the remaining faces or to change to avoid an error:

local numfaces = theCopiedMesh.numfaces
to:
local numfaces = theMesh.numfaces

Also, intersectSegment is checking twice the “same” edge for every not open edge, so there might be some way to improve it.

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

[PolyTools3D]

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

Thanks to this tip from DenisT “vtIndex[1] < vtIndex[2]” (from another post) we could:

--perform the intersection between the original mesh and the copy
 start = timestamp()
 mem = heapfree	
 local theMeshfaces = #{}
 local numfaces = theCopiedMesh.numfaces
 
 local cGetEdgesUsingVert = meshop.getEdgesUsingVert
 local cGetFacesUsingEdge = meshop.getFacesUsingEdge
 local meshOpenEdges = meshop.getOpenEdges theCopiedMesh
 
 local meshFaces = #{1..numfaces}
 for i in meshFaces 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 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
 		)
 	)
 	if fverts.y < fverts.z or meshOpenEdges[i*3-1] do (
 		if intersectsegfn b c true > 0 do (
 			local edgesA = cGetEdgesUsingVert theCopiedMesh fverts.y
 			local edgesB = cGetEdgesUsingVert theCopiedMesh fverts.z
 			local faces = cGetFacesUsingEdge theCopiedMesh (edgesA*edgesB)
 			join theMeshfaces faces
 			for f in faces do deleteItem meshFaces f
 		)
 	)
 	if fverts.z < fverts.x or meshOpenEdges[i*3] do (
 		if intersectsegfn c a true > 0 do (
 			local edgesA = cGetEdgesUsingVert theCopiedMesh fverts.z
 			local edgesB = cGetEdgesUsingVert theCopiedMesh fverts.x
 			local faces = cGetFacesUsingEdge theCopiedMesh (edgesA*edgesB)
 			join theMeshfaces faces
 			for f in faces do deleteItem meshFaces f
 		)
 	)
 )		
  delete theCopiedMesh --delete the copy. We don't need it

This runs about 1.5 times faster but uses more memory.
Although it works with the Torus, I have tested it with a default Teapot, and I get different results from your original code and this, so I am not sure which one returns the correct faces. This needs a lot of manual verification to be sure it will work in all cases.
I still have that feeling… It could be at least 2x faster. Perhaps with a different approach?

[grabjacket]

Oh Boy, I think this is a bit out of my league. I need some more practice to get to this level. I don’t really see what’s going on with this code. Could you maybe add some comments to explain it a bit?

 	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
 		 )
 	 )

[PolyTools3D]

Oh Boy, I think this is a bit out of my league. I need some more practice to get to this level. I don’t really see what’s going on with this code. Could you maybe add some comments to explain it a bit?

 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
     	)
     )

[PolyTools3D]

Here is a graphic that may be useful for others. If you find any errors please let me know.

[denisT]

      		for f in faces do deleteItem meshFaces f
      )

it’s probably nothing by speed and memory use but looks clear:

meshFaces -= faces 

[PolyTools3D]

it’s probably nothing by speed and memory use but looks clear:

      meshFaces -= faces 
      

It is a bit slower and uses twice the memory in my case.

for f in faces do deleteItem meshFaces f

setup grid:6 ms mem:624L
offset mesh:4 ms mem:584L
intersect mesh:651 ms mem:53040L
total:664 ms mem:54368L

meshFaces -= faces

setup grid:6 ms mem:624L
offset mesh:4 ms mem:584L
intersect mesh:700 ms mem:98096L
total:713 ms mem:99424L

[PolyTools3D]

For some reason I stopped using -= for bitarrays to reduce the iterations in a loop. Perhaps I was creating the bitarrays to be removed on-the-fly at that time and never cared to look it in depth.

I can’t really see what is wrong with this code, but the results are odd. Is it due to the creation of the bitarray to be removed?

(
 	------------------------------------------------------------------
 	array = #{1..10}
 	for j in array do (print j; array -= #{5..10})
 
 	print "-----"
 	
 	array = #{1..10}
 	for j in array do (print j; for i = 5 to 10 do deleteitem array i)
 	------------------------------------------------------------------
 	
 	last = 50000
 	
 	seed 0
 	st = timestamp()
 	sh = heapfree
 	array = #{1..last}
 	deleted = #{}
 	for j in array do (
 		r = random 1 array.numberset
 		append deleted r
 		deleteitem array r
 	)
 	format "deleted:% time:% memory:% 
" array.numberset (timestamp()-st) (sh-heapfree)
 
 	seed 0
 	st = timestamp()
 	sh = heapfree
 	array = #{1..last}
 	deleted = #{}
 	for j in array do (
 		r = random 1 array.numberset
 		append deleted r
 		array -= #{r}
 	)
 	format "deleted:% time:% memory:% 
" array.numberset (timestamp()-st) (sh-heapfree)
 	
 	seed 0
 	st = timestamp()
 	sh = heapfree
 	array = #{1..last}
 	deleted = #{}
 	for j in array do (
 		r = random 1 array.numberset
 		append deleted r
 		array[r] = false
 	)
 	format "deleted:% time:% memory:% 
" array.numberset (timestamp()-st) (sh-heapfree)
 )

[PolyTools3D]

it’s probably nothing by speed and memory use but looks clear:

  meshFaces -= faces 
  

It looks like the same behavior as with point3 or integers where Max creates a new instance of it.
But in this case it seems the original bitarray is never modified, so items are not actually been removed when using -= in a loop. Could it be?

[denisT]

It looks like the same behavior as with point3 or integers where Max creates a new instance of it.
But in this case it seems the original bitarray is never modified, so items are not actually been removed when using -= in a loop. Could it be?

 i've never used your trick with deleting already processed bits from processing bitarray:
 like: 

     done = #{}
     for f in faces do
     (
     	ff = <grow> f
     	join done ff
     	for b in ff do deleteitem faces f
     )
     

 i usually just check a current bit against already done...
 check this sample (the first is how you do it, the second is how i do):

     (
     	delete objects
     	t = teapot segments:16
     	mesh = snapshotasmesh t
     	
     	 t1 = timestamp()
     	 m1 = heapfree
     	 verts = #{1..mesh.numverts}
     	processed = #{}
     	for v in verts do 
     	(
     		vv = meshop.getvertsusingface mesh (meshop.getfacesusingvert mesh v)
     		append processed v
     		for v in vv do deleteitem verts v
     	)
     	format "#1 processed:% time:% memory:% 
" processed.numberset (timestamp() - t1) (m1 - heapfree)
     
     	 t1 = timestamp()
     	 m1 = heapfree
     	 verts = #{1..mesh.numverts}
     	 done = #{}
     	processed = #{}
     	for v in verts where not done[v] do 
     	(
     		vv = meshop.getvertsusingface mesh (meshop.getfacesusingvert mesh v)
     	        join done vv
     		append processed v
     	)
     	format "#2 processed:% time:% memory:% 
" processed.numberset (timestamp() - t1) (m1 - heapfree)
     )
     

[PolyTools3D]

I would have think than checking against a second array would be less efficient, but it seems it’s not. In fact your approach runs a little bit faster and uses the same memory.

[denisT]

I would have think than checking against a second array would be less efficient, but it seems it’s not. In fact your approach runs a little bit faster and uses the same memory.

if we change a condition it makes the difference bigger:

(
	num = 50000
	
	t1 = timestamp()
	m1 = heapfree
	verts = #{1..num}
	processed = #{}
	for v in verts do 
	(
		seed v
		vv = #{random v num, random v num}
		append processed v
		for v in vv do deleteitem verts v
	)
	format "#1 processed:% time:% memory:% 
" processed.numberset (timestamp() - t1) (m1 - heapfree)

	t1 = timestamp()
	m1 = heapfree
	verts = #{1..num}
	done = #{}
	processed = #{}
	for v in verts where not done[v] do 
	(
		seed v
		vv = #{random v num, random v num}
		join done vv
		append processed v
	)
	format "#2 processed:% time:% memory:% 
" processed.numberset (timestamp() - t1) (m1 - heapfree)
)

[PolyTools3D]

Awe-so-me! I will sure find a place to use this.
I wish that performance boost could be achieved in all cases.

[CGTalk_Moderation]

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.