Complex Polygon Triangulation

Coding Python Support
1

http://i.imgur.com/5bHn56Q.png?1
5bHn56Q.png?1794×480

Problem
Creating meshes from complex polygons.

Question
Does Blender provide an API/Helper for this task?

Context
I’m working on an import addon to handle loading maps from DOOM wad files. Maps are broken down into polygons called sectors. Most sectors are simple polygons which are trivially created from a list of vertices and Blender will generally do the right thing. Some sectors have holes in them which makes things considerably more tricky.

It seems that folks working with GIS data run into similar issues. I’ve implementing a solution based on an answer found on Blender StackExchange[1]. The general approach is to convert a set of edges into a 2D curve and then covert it back to a mesh. This works fine from the console, but fails during import.

I figure since Blender does this for boolean operations and tessellating 2D curves, it must exist somewhere under the hood and I’m hoping there are hooks for it somewhere. Otherwise I’ll look into writing a custom polygon clipper/splitter.

Help/guidance is greatly appreciated.

Notes
May 1st, 2016
It looks like constrained Delaunay triangulation[2] is likely the best way to proceed.

May 2nd, 2016
Looking further into it, triangulation isn’t as important as ending up with convex polygons. Looking at how existing DOOM editors do it[3], in particular SLADE 3.

Also was referred to a paper on triangulation by ear clipping that supports holes[4].

References

2

This is the method we used for Natural Selection 2. It allows for holes in polygons.

3

That resource is very useful, thank you!

4

I have a Blender addon that does triangulation based on ear clipping and constrained Delaunay triangulation. It handles holes. You are welcome to study and /or copy it. You can find it in the blender-addons-contrib repository, in the io_vector directory.