I'm developing a game in Unity, and have hit a snag with a step I wasn't expecting given the amount of research done on the topic.

I'm in need of a block of code or a library that performs the following steps: takes a convex polygon, all with (integer, even) edge lengths, and splits the area into quads, with as many quads in contact with the edges as their individual lengths.

Example of a polygon with set edge lengths of 2, 4, 4, 4 and 4, split into quads Example of a polygon with set edge lengths of 2, 4, 4, 8 and 8, split into quads

The approaches to this are either the algorithm stated in "Paving: A new approach to automated quadrilateral mesh generation" (T. Blacker, M. Stephenson, 1991), or the various papers and presentations that iterate from it, including the Blossom-Quad algorithm and others that require an initial Delaunay triangulation. These algorithms also cover concave geometry or polygons with interior holes, but for my purposes, this isn't required.

However, every implementation I've found of these are locked into standalone applications and/or with licenses that make them incompatible for immediate inclusion in a closed-source real-time gaming environment.

Before I commit to rewriting all of the original paper in C# (and learning the M.Sc level mathematics I'll need as a prerequisite), I thought I'd check that I'm not reinventing the wheel.

All I'm in need of is just the implementation of this process that'll be either compatible with Unity either because it's written entirely in C#/JavaScript or part of a .dll file that can be included as part of a Unity distributable.

If another implementation of just this procedure is available in another conventional programming language, I'll also accept that provided it's immediately suitable for inclusion after translation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.