Detect overlaping polygons?

OpenGL OpenGL: Advanced Coding
1

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?

Thanks in advance,

Billy.

2

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

3

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.

4

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).