Dynamic Wall Mesh Creation with Delaunay Triangulation in unity3d
We recently required a way to generate wall mesh data at real-time for our project The Office Block. In this application users can build and manage their office in a 3D interactive environment, making office management system, resource and staff management easy and fun.
Figure – 1 shows The Office Block application management system.
The problem we faced while drawing the office structure was the need to selectively remove parts of the mesh surface based on the placement of windows and doors. Our motivation for implementing the solution was to develop a functionality to create removable segments in a polygon, so we can integrate it in our application. As users in this application can draw the office in real-time, we needed a fast and optimized triangulation processing
This is the final implementation of the Delaunay in the Office Block application.
Figure – 2 shows different windows and door making up a perfect triangulation. The triangulation is suitable for fast real-time meshing.
So, how did we do it?
The Ideal Case
The ideal case is to develop an optimized algorithm so if a polygon is added inside a bigger polygon i.e. a window or a door is added inside a wall, it should update the mesh with as few as possible number of triangles.
Figure – 3 shows a simple plane with two triangles making a quad. A wall is simply an object with 6 flat sides i.e. a cube.
Figure – 4 shows that an object is introduced inside our previous mesh. The object can be a window, door or a hollow polygon.
Our first approach was a simple one, to 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 triangulate all these divisions and remove the triangles contained within the object
Figure – 5 shows a simple implementation using horizontal and vertical divisions
This solution works, however, there are a number of vertices and triangles here that serve no purpose, and they are just junk data. The number of wasted vertices and triangles increases as the number of windows or doors increases.
Figure – 6 shows extra vertices and triangles when more objects are introduced.
Things get even worse when the window or door edges don’t line up.
Figure – 7 shows mesh when the window or door edges don’t line up. The above example uses 64 vertices and 80 triangles.
In order to develop a workable solution, we need to remove extra triangulation and develop an optimized algorithm.
Figure – 8 shows a reduced mesh with only necessary vertices and triangles. Here we see that only 16 vertices and 20 triangles are needed. So, what we really need is a way to calculate this kind of triangulation dynamically.
Solution – 2
Delaunay triangulation is a go-to solution for efficiently calculating triangulation of an unordered list of vertices. 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).
Figure – 9 shows a Delaunay triangulation in the plane with circumcircles and their centers represented as red dots.
Figure – 11 shows with the circumcircle solution, it’s just a matter of connecting the vertices of each circumcircle.
Implementation in unity3d
There are several algorithms to compute Delaunay triangulation; we settled on the Sweep-line algorithm used in open source implementation Poly2Tri by Mason Green and Thomas Åhlén, based on the research paper Sweep-line algorithm for constrained Delaunay triangulation by V. Domiter and B. Zalik. This solution is solved in O (n log(n)) time using the Sweep-line technique. We ported the open source Poly2Tri in unity3d.
Figure – 12 shows a simple mesh with 4 vertices.
Figure – 13 shows the implementation of Delaunay with a wall, door, and a window.
This is an unconstrained Delaunay triangulation, meaning the triangles are created based solely on a circumcircle solution.
The Delaunay triangulation maximizes the minimum angle of all the angles of the triangles in the triangulation.
Figure – 14 shows two adjacent polygons using unconstrained Delaunay approach.
For the constrained set of points, a generalized algorithm of Delaunay Triangulation is Constrained Delaunay Triangulation that forces certain edges to be added in triangulation. Constraints can be defined to make a Constrained Delaunay Triangulation to match any given triangulation. So, we added constrained vertices that created edges between set of constrained points.
Figure – 15 shows vertices of a wall, door, and a window are added in constrained set of points (Vertices 0 to 3 for the wall) (Vertices 4 to 7 for the door) (Vertices 8 to 11 for the window).
Our algorithm 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, vertices crossing other polygon vertices and making a new custom shape.
Figure – 16 show multiple boundary cases with modified triangulation. Label – 1(a) and 1(b) represents a standard case when two polygons are adjacent, 2 represent a case when two polygons are adjacent and intersect boundaries, 3 and 4 represent cases when a polygon intersects with boundaries, 5 represent a case when a polygon is stretched and intersects both ceiling and floor.
Figure – 17 shows a custom shape is created when two triangles are close to each other.
We created double side plane and process Delaunay triangulation on each of one offsetting by half of width and adding a roof mesh make it able to visualize in three dimension space.
Figure – 18 shows in making both sides of walls and a mesh for the roof.
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.
Figure – 19 shows Possible Edge Types
Figure – 20 shows close up of wall edge intersection, showing the watertight join at the point of intersection.
With our vertices and triangles ready all that were 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.
Figure – 21 shows Final implementation test scene.
The solution has proved to be fast, reliable and robust.
The Office Block
After handling all possible cases, we used this implementation in The Office Block application.