Writing an experimental BSP system. The idea here is that it works on a tree of hexahedra; artbitary (but convex) six sided shapes divided using edge loops.. I've hit a bit of a snag, though when trying to get that data converted into triangles.



Ideally, this is what I'm after. The black square is the left face of a big solid, the grey square is the right face of an airspace which touches it. I wish to get the matching area. Note that these ARE planar.

My method (which is implemented, but has problems, later on) is to make a list of the triangles on the matching face in the solid; in this case, it's two that make up the big black square. Then, I determine how many vertices of each triangle are within our airspace's face. I do this by finding the perpendicular to each border that faces the other side of the face. These appear to be valid, so I'm sure this isn't the cause of the problem. Then, I dot product the normal between the midpoint of each border and the vertices of the triangles. Count the in and out vertices and take one of four actions:

All in - go to next triangle
1 out - split into two triangles using edges of triangle and plane of normal to determine new vertices
2 out - move the out-of-bounds vertices back in bounds by using edge-plane-of-normal intersection like 1 out
3 out - delete triangle

It works really well with nice tidy, ordinary geometry, but it doesn't take much turbulence in the geometry before the thresholds on the dot product give out and I have unclipped geometry bleeding everywhere and geometry being clipped when it shouldn't be.

There's got to be a better solution. Right? I have my airspace's quad, and their solid's quad, I know they're planar and I want the touching area as triangles.

Thanks for reading this mini-essay.