View Full Version : 3ds max - Select self-intersecting polys?
03-09-2005, 11:27 AM
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.
03-09-2005, 11:34 AM
hm how many tris do those objects have ?
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
03-09-2005, 11:37 AM
1944 polygons / 3776 triangles.
03-09-2005, 11:44 AM
Hmm...an intesting one. It may be possible, let's see if we can break it down a little.
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.
03-09-2005, 12:08 PM
the tris however can intersect any others ? not just the ones around a poly, which makes it harder, cause you basically need a "test every tris with every other" then
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
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
--if one of the edges to that vert v
--intersects tris a (doing via projection into tris a plane)
---then select tris
03-09-2005, 05:31 PM
Yeah that last bit sounds interesting.
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)
03-10-2005, 04:12 AM
it said max6,7 so never tried it
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
03-10-2005, 07:18 AM
Yeah I figured something like this might be slow. I really appreciate your help! (btw, I'm hoping sometime we can actually get that internship going. It's just too busy right now unfortunately. We have a new artist that just started, and that always takes extra time, helping someone new get up to speed. On top of the usual time demands...)
Orionflame does work in v5.1, at least most of the tools do. Some good stuff in there. And free to boot!
03-10-2005, 08:35 AM
In the future, you might want to try using a displace modifier. Since it only pushes the polys up or down, you never get intersecting triangles. And it's easy enough to change the look using the controls on the modifier along with settings in your procedural noise texture.
03-10-2005, 09:14 AM
Thanks, Displace is better. Fortunately we're at the exploratory stage. Doesn't give the same "chunky" look though, have to add a little Push to it. I think hand-editing will still need to be done, per-target, just less of it if Displace gives the look we want.
03-10-2005, 09:31 AM
Playing around the map will give you the most variety in looks. Try using noise, smoke, splat, etc., along with mix maps using gradients in the mixer slot. And also try changing the color curves in the procedural maps to get sharper, or fuzzier edges between the black and white values. Of course, this won't have as much of a visible affect in a lower poly mesh, I don't know how dense the meshes are that you're working with.
Another option is to use soft selections to only affect certain parts of the mesh. The possibilities are (almost) endless. /images/graemlins/smile.gif
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.
03-10-2005, 09:43 AM
It's about 4000 tris, so the map type doesn't have a lot of weight. I am using Soft Selections right now to ignore certain areas, so they remain static during the morph, but the overlaps would need their own custom selections, and then that'll be different per-target. Sounds kind of fiddly. Hmmm.
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.
03-10-2005, 03:10 PM
ah I hope it aint too late for me now, but I did a script
currently only EditableMesh supported, but I will add Poly once I got more time
03-10-2005, 03:17 PM
Hey man, it's never too late! If it solves the problem, I'm all over it.
I always appreciate the lengths people go to help out. Will give this a spin, let you know how it goes.
03-10-2005, 03:23 PM
Holy moly, no progress bar? no UI? Sorry, I know beggars can't be choosers.
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.
03-10-2005, 03:45 PM
okay added the progress bar
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
03-11-2005, 02:53 AM
I will spend a little time in optimizing it a bit to improve efficiency
03-11-2005, 12:32 PM
Well, wouldn't ya know it, I've been pulled off this and on to something else... we still need to solve this, just not right away. If that helps any...
03-11-2005, 04:33 PM
good I just put in several hours to add an octree optimization to it, which greatly enhances speed.
just gotta fiddle some bugs, debuggin maxscript aint as comfortable as c in msdev is /images/graemlins/wink.gif
tomorrow I think I can release the greatly improved speed version
EDIT: tomorrow already started so time for an update /images/graemlins/wink.gif
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
vBulletin® v3.8.4, Copyright ©2000-2013, Jelsoft Enterprises Ltd.