Find self intersections in objects

Finding intersections between objects in maxscript can be really handy if you want to get rid of pieces of a mesh or optimize your models. You can use intersections also as a guide where to put special effects, like debris or explosions. I haven’t found a good method to do the same for self intersections though.

Download the script here

Development

I took some inspiration from a module in blender (3D printing toolkit) and a few methods on cgTalk here and here. The trick here is to intersect the object with a slightly modified copy of itself. the intersections are calculated by shooting rays from all face-edges and see if it hits something. If you shoot a ray from a face-edge and test if it hits itself it will always return “yes, I did!”. This is totally useless. If you shoot a ray to a slightly offset version of the model, you get what you want. It feels kind of hacky, but it gives good enough results for me.

After posting it on cgTalk, DenisT and PolyTools3D gave great suggestions to make it more efficient. Thanks guys!

The demo script will generate a self-intersecting torus knot and perform the test. It will paint the self intersecting faces red and selects them. There are plenty of comments in the 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:%n" (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
    extrudeFace theCopiedMesh #{1..theCopiedMesh.numfaces} theOffsetMultiplier 0
    format "offset mesh:% ms mem:%n" (timestamp() - start) (mem-heapfree)
    
    --perform the intersection between the original mesh and the copy
    start = timestamp()
    mem = heapfree    
    local theMeshfaces = #{}
    local numfaces = theMesh.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:%n" (timestamp() - start) (mem-heapfree)
)else format "% is not an editable mesh, please convert it first.n" 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
    converttomesh theObject
    local start = timestamp()
    local mem = heapfree
    fn_getFaceSelfIntersection theObject 25
    format "total:% ms mem:%n" (timestamp() - start) (mem-heapfree)
)

A minor edit now also allows the script to be run on meshes with open edges.