If you notice the highlighted edges meet, but not in a way that each tri has exactly 2 shared edges. This is easy to triangulate by hand if I add a small border around it (just imagine the whole door shrinks so it meets the top too; MS paint doesn’t have that feature):
Wondering if anyone knows of an algorithm that can do this automatically with reasonable performance and introduce a minimal number of extra tris? The generated mesh will only be used for casting shadows, so I don’t care about normals or UVs.
It’s definitely not easy. You have to find any vertices which are coplanar and colinear with another triangle’s edge, then split the triangle into two, to incorporate the vertex. For example, the two tall triangles adjacent to your door need to break at the top-of-the-door vertices which touch them.
Once done with all that, you may have coplanar redundant polygons in the space you labeled in yellow, which can be removed.
That said, game design does not require manifold spaces. A little clip-through or redundant polygons are quite normal and it would be counterproductive to make every model perfect at runtime. If you’re worried about z-fighting between walls and a door frame (as you label in green), perhaps you can make the door frame more puffy to fully hide the wall it is covering.
I see what you’re saying. although finding coplanar + colinear polygons in an efficient way seems difficult especially when there’s whole walls of them, so a hash is going to turn into a linear lookup. I need to be able to do this at runtime in a burst job. I’ll noodle with it a bit more, but I can see what you’re saying there.
This is for stencil shadows, which have all sorts of glitches with nonmanifold geometry. As for why stencil shadows, here’s URP shadow maps at 2048x2048 shadow resolution:
That’s not a manifold though. It’s just separate non-manifold geometry that’s floating close together. Manifold geometry requires continuous shared vertices, which that mesh does not have anymore.
Understand there’s a difference between geometry that’s presented to users in a 3D modelling program, and the geometry that game engines / GPUs actually use. Each vertex can only have one set of data, which is why hard edges breaks stuff for stencils as the vertex has to be split so there can be separate normal vectors for the difference faces.
3D modelling programs often have different sets of data for each face connected to a vertex, and that’s just not how GPUs are setup to handle it. So under the hood even those programs are splitting everything up before it gets rendered for the real time viewports.
The easiest solution is to fix the source assets in the tools they were created in to not have t-junctions. It’s “obvious” and “simple” for a human to see where they need to go. Very, very hard for a computer.
These meshes are all generated dynamically in a burst job and could theoretically be changed in-game. Hence why I’m looking for an algorithm to do it :-).
Separate verts sharing location isn’t a problem since my edge-finding algorithm rounds everything to a grid (to avoid floating point errors) and checks for shared edges that way, so it already handles normal/UV seams seamlessly.
If you’re generating the geometry, then you should be able to do this without doing CSG. Have a loop for constructing walls that take into account if the section next to it has a door or not and add the necessary vertices to meet up with the doorway.
Sadly, there’s more than just doors to think about; the hole can be any arbitrary shape (windows, big windows, round windows, archways, French Provencal style patio doors… OK, mostly just windows and doors). Anyways, I will figure it out. I was hoping there was a well-known algorithm for this, but I guess it’s not a particularly common problem to have.
For now, I hacked in doors and small windows. Ultimately, I think I’ll have to solve it upstream. The triangulation right now is very slipshod.
