3ds max - Select self-intersecting polys?
admin
We need to fix models that have self-intersections. Some of their triangles intersect with other triangles in the same mesh, which then causes Z-buffer sorting problems in the game engine. The intersecting areas flash on and off when seen from a distance, because the Z precision is low on certain graphics cards.
I'm looking for a way to select intersecting polygons, which I can then fix. I cannot change the vertex count of the mesh, because the meshes are morph targets. I have to use a tool that merely moves the vertices so thay aren't intersecting anymore.
I was thinking that if I could at least select the problem faces, I could apply a Relax modifier to pull them away from one another, or maybe a Push modifier. At last resort, I would go in there and hand-edit them. I just have a bunch of these models to do (4x12 or so) so an automatic solution would be awesome.
It would also be helpful to have a tool that would select long thin triangles, since these cause other problems in-game. I tried the STL Check modifier, but that doesn't select these kinds of problems. Orionflame's PolaX tool does all kinds of other cool selection types, just not self-intersections.
Any insights would be appreciated. BTW, still in max 5.1 if that matters.
I'm looking for a way to select intersecting polygons, which I can then fix. I cannot change the vertex count of the mesh, because the meshes are morph targets. I have to use a tool that merely moves the vertices so thay aren't intersecting anymore.
I was thinking that if I could at least select the problem faces, I could apply a Relax modifier to pull them away from one another, or maybe a Push modifier. At last resort, I would go in there and hand-edit them. I just have a bunch of these models to do (4x12 or so) so an automatic solution would be awesome.
It would also be helpful to have a tool that would select long thin triangles, since these cause other problems in-game. I tried the STL Check modifier, but that doesn't select these kinds of problems. Orionflame's PolaX tool does all kinds of other cool selection types, just not self-intersections.
Any insights would be appreciated. BTW, still in max 5.1 if that matters.
Replies
just wondering if a trivial "test all tris with all tris" algorithm would work, or if someone would need to do some spatial structuring to reduce from O(n^2) complexity
I suppose you would need to select each poly in turn, and find its normal.
Then for every vert, find every vert it is connected to. This will give you the edges.
Then compare the verts at each end of these edges, to see if any are on opposite sides of the normal.
Long thin ones should be a lot easier - for each vert get the lengths of each edge. Take the longest edge = 100%, then see if any lengths fall under a certain threshold - if one of the remaining is close to 100%, and the other close to 10%, you have a long one.
OR if the other two edges lengths add up to around 100% -then you have a short wide triangle.
Just thinking out loud.
and for that you need to check if one vert lies on the opposite side of the tris plane, and then also check if the edges connected to that vert, which are pojected on the tris plane intersect the tris.
sounds like a bug chunk of work hehe
algo:
test all tris a with all others b
-if one of b's verts v lies on the "opposite" (compared to the other verts of b) side
-of tris a's normals
--then
--if one of the edges to that vert v
--intersects tris a (doing via projection into tris a plane)
---then select tris
end
I think it is along the lines of testing if an edge goes through the space occupied by another triangle.
Then select all the triangles concerned... the two triangles shared by that edge, and the intersected triangle.
All could be done in Editable Mesh if Editable Poly was adding a layer of complexity, since it's easy for me to pre-convert the poly meshes to Editable Mesh.
The issue comes about because we have these hilly terrain tile pieces that are made procedurally by using Noise and Push modifiers. This gives us a great rolling, rocky surface, and we can make lots of variations real fast just by altering the Noise seed. But the Push modifier causes these intersections.
We put the variations in a morph-like interactive structure, and let the game randomly choose a combination of the four targets for each terrain tile. So we end up with lots of variation from one model set. But... we have a lot of different sets, for valleys vs. hills vs. trenches vs. etc., each with their own morph set.
Right now, I'm looking at manually editing each target. No fun!
BTW, Orionflame is really neat. The PolaX tool itself is really robust... doesn't do the particulars I need, but does do tons of other algorithmic selection types. Worth a look if you haven't played with it.
http://www.flamefx.com (click on the screenshot to d/l the scripts)
and your right, probably easier to just check all edges with the tris for intersection and then select polys part of that edge. I will give it a try as maxscript, though I suspect it to be very slow
Orionflame does work in v5.1, at least most of the tools do. Some good stuff in there. And free to boot!
Another option is to use soft selections to only affect certain parts of the mesh. The possibilities are (almost) endless.
If you're still looking for a script solution for the intersecting edges, check out the MaxScript section of the Discreet webboard. Someone else is asking the same question.
Funny about the webboard, Yunus is the author of Orionflame. I asked him in email if he could script something. We'll see!
Thanks for your help, much appreciated.
currently only EditableMesh supported, but I will add Poly once I got more time
http://crazybutcher.cube3d.de/code/_3dsmax.html
I always appreciate the lengths people go to help out. Will give this a spin, let you know how it goes.
Don't know how long this is supposed to take. Did I just hang max, or is it just taking a while to process? I imagine the latter, but how long is long? Guess I'll just have to wait it out, or End Process on it.
and yeah it is ungodly slow unfortunately... to make it efficient one would need to introduce some sort of spatial structure like octree, which ends up being a mini full blown collision engine for that function.
there is also another flaw, it just performs tests on edges, so lets say no edge intersects the triangle, but the ones neighboring it, the middle tris will not be marked intersected
just gotta fiddle some bugs, debuggin maxscript aint as comfortable as c in msdev is
tomorrow I think I can release the greatly improved speed version
EDIT: tomorrow already started so time for an update
currently no UI to change octree depth, but depending on the model one could raise the octree depth in the script manually
just search for OCTREEDEPTH variable
hope this is more useable