**New here?**Learn about Bountify and follow @bountify to get notified of new bounties! Follow @bountify 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.

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.