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

3ds max self intersect maxscript
Self intersections have been detected

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.

Finding self-intersections on objects with open edges is now possible
Finding self-intersections on objects with open edges is now possible


7 comments

yuriki

Hi!
I tried your script and with torus it works fine.
But when I use my own mesh I always have error:
— Runtime error: Selection index out of range: 11755

I tried to use as lowpoly object as possible but error continue happened.

Tell me please, why this happened?

Klaas Nienhuis

Could you post a link to that object here and the edited scriptfile?

Robert Seidel

Dear Klaas,

would it be possible to implement the “Find self intersections” script as a SimpleMod in max? Looks highly useful…

Kind regards, Robert

Klaas Nienhuis

Hi Robert, probably yes. Though with larger objects the check takes a few moments. I suppose it could work similarly to the stl-check modifier where you can switch the check off if you want.

Preeth

Hey Klass. This is a beautiful script. I guess as Yuriki pointed out it gives error at times. Try it on a tea pot. You will get that runtime error. I guess this is because the function does not work on a open mesh.

Try deleting one face from that torus and then run that script

Klaas Nienhuis

Hi Preeth, you’re right. I’ve edited the script to function on meshes with open edges. It should work. Could you try it out?

Oleksandr

Hi, Klaas, can you please say me what I’m doing wrong? I’m selecting object, run script, my object disappears and teapot creating, what I’m doing wrong?

Leave a Reply

* Will not be published