Quadrangulating a polygon in Unity C#
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

I require an implementation of a constrained quadmesh paving algorithm in C# that utilises no external dependencies other than what can be included as part of the answer, for a commercial solution to be included in a Unity3D project.

The required implementation takes a polygon with (integer, even) edge values, and splits the area of it into quadrilaterals, with as many quads in contact with the original edges as their assigned value (so an edge with weight 4 should have 4 quads in contact with it). The quads generated should be a similar area, with no interior angle of any quad being greater than 150 degrees, either before or after the new points generated undergo Laplacian smoothing. Solutions that leave triangles are not permitted.

A pentagon with edge lengths 4, 4, 4, 4 and 2 split into quadrilaterals
A pentagon with edge lengths 8, 8, 4, 4 and 2 split into quadrilaterals

The algorithm I expect to see would be the Advanced Front Quad Mesh Algorithm in C# which is detailed in the paper "Paving: A new approach to automated quadrilateral mesh generation" (T. Blacker, M. Stephenson, 1991) and refinements upon this method exist as well. Methods that start with constrained Delauney triangulation and apply an algorithm such as the Blossom-Quad algorithm are also accepted.

These algorithmic solutions cover concave polygons and ones with inner holes that I've not factored into the example illustrations above. While I personally only need to solve the interiors of polygons defined by voronoi cels and don't expect to need concave or complex polygons, an implementation that covers this situation will be appreciated (and appropriately tipped).

If possible, quads that share meshes and vertices should share references to those objects as well if those helper objects exist, so that implementations of them in the game can be used for easier pathfinding later.

The solution needs to have no dependencies that would restrict it from operating inside Unity 3D in polynomial time (so, for instance, nothing that requires an external program or importing of libraries that would be platform, environment or runtime specific outside of Unity3D). Ideally, commented and annotated in a way that would allow for easy translation into other languages.

Which kind of object would the implementation receive as input? And what should be the result? I mean, is the input a set of points in clockwise order and the side weights, for example?
gabrielsimoes 4 years ago
Indeed, an ordered list of points (in clockwise or anticlockwise, I'm not fussy) and the side weights following the same order would be the expected input. If you've located a solution for the general problem that includes concave and complex solutions, I imagine given standard boolean calculations, anticlockwise for addition and clockwise for subtraction would be the expected form
KaynSD 4 years ago
As for result, either a two dimensional list or array, forming effectively a list of the quads generated
KaynSD 4 years ago

Crowdsource coding tasks.

0 Solutions