Find 2D overlapping faces using rasterization

I’m trying to find a faster method of finding UV faces overlaps. I’m thinking I could use OpenGL and the fragment shader in some way to check what faces are drawn on top of each other to get this information, maybe by using the faceId as the color so I can get that information.

I wanted to check if anyone here might have a good approach to use for this. Right now my idea is to do 2 passes, 1st drawing all the UVs with their color being the faceId and then in the second pass check if the color we want to draw for each pixel is the same as the one drawn in the first pass, if it is not we know there is an overlap.

In the end I want to be able to get a list of the faceIds of the overlapping faces back to the CPU to be able to use them for other calculations there. I was wondering if a frame buffer object would allow me to do this, is there any way to get that information back? If not, maybe an SSBO could work?


That would work. If you have a sufficiently recent version of OpenGL, you can use an integer-format texture for the colour buffer and store the ID directly (no need to encode it as a colour). For the second pass, you’d look up the value written in the first pass (use texelFetch with gl_FragCoord.xy as the coordinates) and check whether it’s the same as the current face ID.

That leaves the question of what to do when you get a mismatch. You’ll probably return data by writing into a SSBO. If two faces overlap, they’ll probably do so for multiple fragments and you presumably won’t want to generate a record for each fragment. You could use an array indexed by face ID into which you write the ID of the “other” face. But that only gives you one possible pair for each fragment, so it’s possible that some relationships get missed. More complex structures are possible but then you have to deal with atomic updates, as you’ll have multiple fragment shader invocations running concurrently for the same face ID. Atomic image load/store will probably be useful here.

Ultimately it depends upon how much detail you want, the number of faces, the number of fragments rendered, the number of fragments which are likely to overlap, and the average and maximum number of overlapping faces for any given fragment.

1 Like