Use Blender’s internal triangulation function instead of the triangle lib

[PiOverFour]

Hi, there has been a Delaunay constrained triangulation function in Blender for a few versions, written by Howard Trickey and used in particular for booleans. It is exposed through the Python mathutils.geometry module.

Since the Triangle Python wrapper library is quite unstable, and since its legal status is questionable, it would be useful to use another triangulation function, from Blender if possible. I’ve been trying to do that, but couldn’t get results as good as Triangle’s.

I was stuck at adding triangles inside the curve, because delaunay_2d_cdt() only considers the constraints and doesn’t add geometry itself. So I just added a bunch of random points in there, which results in a pretty bad mesh. This could probably be fixed by relaxing the random vertex positions, or finding a more proper way to add them in the first place.
Also, I couldn’t find a way to have holes, they seem to be included only as point constraints, and not reversed curves like can be specified in Triangle.

I’ll paste my results below, in case anyone wants to explore further.

import bpy
from mathutils import Vector
from mathutils.geometry import (delaunay_2d_cdt,
                                intersect_point_tri_2d,
                                tessellate_polygon)
from pprint import pprint
from random import uniform

mesh = bpy.context.object.data


def get_2d_bounding_box(verts):
    x_cos, y_cos = zip(*verts)
    min_x = min(x_cos)
    max_x = max(x_cos)
    min_y = min(y_cos)
    max_y = max(y_cos)
    return (min_x, max_x, min_y, max_y)


def point_inside_polygons(point, tessellated_polygons):
    for verts, poly in tessellated_polygons:
        for tri in poly:
            if intersect_point_tri_2d(point, verts[tri[0]],
                                             verts[tri[1]],
                                             verts[tri[2]]):
                print("point", point, "inside", verts[tri[0]],
                                             verts[tri[1]],
                                             verts[tri[2]])
                return True
    return False


verts_2d = [v.co.xy for v in mesh.vertices]
edges = [e.vertices[:] for e in mesh.edges]
polygons = [f.vertices[:] for f in mesh.polygons]

INSIDE_VERT_NUM = 500
i = 0
bb = get_2d_bounding_box(verts_2d)


tessellated_polygons = []
for polygon in polygons:
    tessellated_polygons.append([[verts_2d[v] for v in polygon],
        tessellate_polygon([[verts_2d[v] for v in polygon]])])

while i < INSIDE_VERT_NUM:
    vert = uniform(bb[0], bb[1]), uniform(bb[2], bb[3])
    if point_inside_polygons(vert, tessellated_polygons):
        i += 1
        verts_2d.append(vert)

delaunay = delaunay_2d_cdt(verts_2d,
                           edges,
                           polygons, 1, .01)
                
me = bpy.data.meshes.new("out")
me.from_pydata([v.to_3d() for v in delaunay[0]], delaunay[1], delaunay[2])

obj = bpy.data.objects.new("out", me)
bpy.context.collection.objects.link(obj)