Hello, T-Junctions have been a pain for me to fix because I’ve only found brute force methods which take ages with a BSP tree containing over 10k nodes. Has anyone worked with this issue before and had a solution?
I don’t have practical experience with constructing BSP trees myself, but I think one solution that may work well is to work with edge lists. So, for each edge of every polygon, have some data to identify the vertices which span the edge, and a list of adjacent polygons this edge is shared with.
During BSP construction, splitting one (convex) polygon also means that up to 2 of its edges are split (if the split does not intersect exactly at one of its vertices). If that happens, search for the adjacent polygons which share those edges, and split those too (which means you insert one more vertex on their edge).
Then you “just” need to add/update edge information for the local and adjacent polygons. The local polygon is split in 2, sharing a new edge with each other. For the adjacent polygons, affected edges are subdivided and replaced by 2 new edges.
I will implement your idea if this other idea I had doesnt work. My idea is to “stretch” split polygons over their plane by a fixed epsilon to fill up the cracks. I was thinking about for each vertex, finding the direction towards the polygon’s centroid and extrapolating backwards on the 3D line created by that direction by a certain epsilon. What do you think of that?
Hm. This may work, but you’ll have to try and tune the epsilon carefully. Depending on your geometry, it may cause distortions or z-fighting issues.
I dont think that Z-fighting will be an issue since it’s a bsp tree and a bsp tree is essentially an advanced painters algorithm