PDA

View Full Version : Detect overlaping polygons?

billy
07-06-2003, 11:55 PM
Hello,

I have a set of polygons in 3d space. Some may be overlapping. This produces z fighting effect. The question is: How do I identify these overlapping polygons automatically and delete them? I have tried triangle-triangle intersection algorithms and it does not work for these cases.
I was thinking about getting z component from OpenGL of each polygon and comparing them. Does anyone have an idea?

Billy.

john
07-07-2003, 02:06 AM
are you talking about static geometry, or trying to do this for every frame?

in the static geometry case, I'd probably suggest computing the plane coefficients for the triangles and test for similarity... but htat could get quite problematic because a plane has an infinite set of valid coefficients. You could do a preliminary sweep by removing planes with greatly dissimilar normals and then check to see if two planes are coplanar by plugging in verticies of OTHER triangles into a given plane's equation. Using histograms to planes into buckets to reduce an O(N*N) problem *may* make that tractable:

for each triangle, T
compute P <- the plane through T
place {T,P} into its appropriate bucket
end for

for each bucket, B
for each plane P in B
for each OTHER plane P' in B (ie. P!=P')
if crossProduct(v, P')==0 forall v E T of {T,P'}
P==P' ; do triangle intersection test
end if
end for
end for
end for

you still need to compute the triangle intersection test when you've ascertained that two triangles are coplanar, but thats ok because its a 2D problem.

This algorithm would suck in the renderloop, though...

cheers,
John

billy
07-07-2003, 02:35 AM
Checking if they are co-planar is not sufficient. After determining co-planicity I would need to reduce 3d to 2d and then check for segment-triangle intersections to see if they overlap. Right?

Billy.

john
07-07-2003, 03:25 AM
yes, thats correct. that's what I meant by the "extra caveat" inside that inner for loop (and what I meant by the comment after the for loop).