We recently required a way to dynamically generate wall mesh data for one of our projects. While a wall is little more than a stretchy cube, the problem was made more complex by the need to selectively remove parts of the mesh surface based on the placement of windows and doors.
Our first approach was a simple one - create horizontal divisions on the top and bottom edge of any windows or doors, and vertical divisions on the left and right edge of any windows or doors, then remove the triangles contained within.
Simple implementation using horizontal and vertical divisions.
This works, however there are a number of vertices and triangles here which serve no purpose - they're just junk data. The number of wasted vertices and triangles increases as the number of windows or doors increases.
Many wasted vertices and triangles...
Things get even worse when the window or door edges don't line up.
This is getting very bad...
So, how would a human designer arrange the mesh for a game engine? The above example uses 64 vertices and 80 triangles, but it can obviously be done with a lot less.
A reduced mesh with only necessary vertices and triangles.
Here we see we only need 16 vertices and 20 triangles. So, what we really need is a way to calculate this kind of triangulation dynamically.
Delaunay to the rescue!
Delaunay triangulation is the go-to solution for efficiently calculating triangulation of an unordered list of vertices. Summed up, Delaunay triangulation for a set P of points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). For those of us who aren't mathematicians, diagrams help!
Circumcircle solution for 6 vertices. Each circumcircle envelopes 3 vertices, with no other vertices contained within the circumcircle.
With the circumcircle solution, it's just a matter of connecting the vertices of each circumcircle.
There are several algorithms to compute Delaunay triangulation; we settled on the Sweep-line algorithm implementation used in Poly2Tri implemented by Mason Green and Thomas Åhlén based on the research paper by V. Domiter and B. Zalik. This solution is solved in O(n log(n)) time using the Sweep-line technique. After porting the open source Poly2Tri to Unity, we were off and running!
So, we're done, right? Well, not quite. This is an unconstrained Delaunay triangulation, meaning the triangles are created based solely on a circumcircle solution, however there are cases where this isn't what we want. For example, take the case of 2 windows below.
Two windows in a wall.
Resulting Delaunay triangulation.
There's a problem here - not all window edges are included in the triangulation, meaning when we remove the triangles within the windows bounds (highlighted in blue) we will be left with a hole between the two windows. So, what now?
Constrained Delaunay to the rescue!
Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation. However, in the above case, we need to ensure that some points are always connected with an edge. Constrained Delaunay triangulation forces defined edges to be included in the triangulation. Constraints can be defined to make a Constrained Delaunay triangulation match any given triangulation.
Our algorithm first calculates the necessary vertex / edge pairs for the Constrained Delaunay triangulation and handles vertices over plane edges, vertices crossing plane boundaries and vertices crossing multiple edge boundaries, such as floor-to-ceiling windows.
With our vertices and triangles ready, all that was left was some simple UV generation and adding some thickness to make it visible in 3D space. We then put together a simple test scene displayed below.
Final implementation test scene.
One more required consideration was how to connect the walls together. We came up with 7 possible edges for each side of the wall to ensure a watertight join of the walls in any configuration.
Possible Edge Types
Close up of wall edge intersection, showing the watertight join at the point of intersection.
The solution has proved to be fast, reliable and robust.