Add mathutils.geometry.delaunay_2d_cdt() function to Python API.

Provides Python API access to recently added Constrained Delaunay
Triangulation routine.
Reviewed in D5467.

1 files changed, 185 insertions, 0 deletions

diff --git a/source/blender/python/mathutils/mathutils_geometry.c b/source/blender/python/mathutils/mathutils_geometry.c
index 32ce78f702d..a6dded4ee8b 100644
--- a/source/blender/python/mathutils/mathutils_geometry.c
+++ b/source/blender/python/mathutils/mathutils_geometry.c
@@ -29,6 +29,7 @@
 #  include "BLI_blenlib.h"
 #  include "BLI_boxpack_2d.h"
 #  include "BLI_convexhull_2d.h"
+#  include "BLI_delaunay_2d.h"
 #  include "BKE_displist.h"
 #  include "BKE_curve.h"
 #endif
@@ -1507,6 +1508,186 @@ static PyObject *M_Geometry_convex_hull_2d(PyObject *UNUSED(self), PyObject *poi
   return ret;
 }
 
+/* Return a PyObject that is a list of lists, using the flattened list array
+ * to fill values, with start_table and len_table giving the start index
+ * and length of the toplevel_len sublists
+ */
+static PyObject *list_of_lists_from_arrays(int *array,
+                                           int *start_table,
+                                           int *len_table,
+                                           int toplevel_len)
+{
+  PyObject *ret, *sublist;
+  int i, j, sublist_len, sublist_start, val;
+
+  ret = PyList_New(toplevel_len);
+  for (i = 0; i < toplevel_len; i++) {
+    sublist_len = len_table[i];
+    sublist = PyList_New(sublist_len);
+    sublist_start = start_table[i];
+    for (j = 0; j < sublist_len; j++) {
+      val = array[sublist_start + j];
+      PyList_SET_ITEM(sublist, j, PyLong_FromLong(val));
+    }
+    PyList_SET_ITEM(ret, i, sublist);
+  }
+  return ret;
+}
+
+PyDoc_STRVAR(
+    M_Geometry_delaunay_2d_cdt_doc,
+    ".. function:: delaunay_2d_cdt(vert_coords, edges, faces, output_type, epsilon)\n"
+    "\n"
+    "Computes the Constrained Delaunay Triangulation of a set of vertices, "
+    "with edges and faces that must appear in the triangulation. "
+    "Some triangles may be eaten away, or combined with other triangles, "
+    "according to output type. "
+    "The returned verts may be in a different order from input verts, may be moved "
+    "slightly, and may be merged with other nearby verts. "
+    "The three returned orig lists give, for each of verts, edges, and faces, the list of "
+    "input element indices corresponding to the positionally same output element. "
+    "For edges, the orig indices start with the input edges and then continue "
+    "with the edges implied by each of the faces (n of them for an n-gon).\n"
+    "\n"
+    "   :arg vert_coords: Vertex coordinates (2d)\n"
+    "   :type vert_coords: list of :class:`mathutils.Vector`\n"
+    "   :arg edges: Edges, as pairs of indices in `vert_coords`\n"
+    "   :type edges: list of (int, int)\n"
+    "   :arg faces: Faces, each sublist is a face, as indices in `vert_coords` (CCW oriented)\n"
+    "   :type faces: list of list of int\n"
+    "   :arg output_type: What output looks like. 0 => triangles with convex hull. "
+    "1 => triangles inside constraints. "
+    "2 => the input constraints, intersected. "
+    "3 => like 2 but with extra edges to make valid BMesh faces.\n"
+    "   :type output_type: int\\n"
+    "   :arg epsilon: For nearness tests; should not be zero\n"
+    "   :type epsilon: float\n"
+    "   :return: Output tuple, (vert_coords, edges, faces, orig_verts, orig_edges, orig_faces)\n"
+    "   :rtype: (list of `mathutils.Vector`, "
+    "list of (int, int), "
+    "list of list of int, "
+    "list of list of int, "
+    "list of list of int, "
+    "list of list of int)\n"
+    "\n");
+static PyObject *M_Geometry_delaunay_2d_cdt(PyObject *UNUSED(self), PyObject *args)
+{
+  const char *error_prefix = "delaunay_2d_cdt";
+  PyObject *vert_coords, *edges, *faces, *item;
+  int output_type;
+  float epsilon;
+  float(*in_coords)[2] = NULL;
+  int(*in_edges)[2] = NULL;
+  int *in_faces = NULL;
+  int *in_faces_start_table = NULL;
+  int *in_faces_len_table = NULL;
+  Py_ssize_t vert_coords_len, edges_len, faces_len;
+  CDT_input in;
+  CDT_result *res = NULL;
+  PyObject *out_vert_coords = NULL;
+  PyObject *out_edges = NULL;
+  PyObject *out_faces = NULL;
+  PyObject *out_orig_verts = NULL;
+  PyObject *out_orig_edges = NULL;
+  PyObject *out_orig_faces = NULL;
+  PyObject *ret_value = NULL;
+  int i;
+
+  if (!PyArg_ParseTuple(
+          args, "OOOif:delaunay_2d_cdt", &vert_coords, &edges, &faces, &output_type, &epsilon)) {
+    return NULL;
+  }
+
+  vert_coords_len = mathutils_array_parse_alloc_v(
+      (float **)&in_coords, 2, vert_coords, error_prefix);
+  if (vert_coords_len == -1) {
+    return NULL;
+  }
+
+  edges_len = mathutils_array_parse_alloc_vi((int **)&in_edges, 2, edges, error_prefix);
+  if (edges_len == -1) {
+    goto exit_cdt;
+  }
+
+  faces_len = mathutils_array_parse_alloc_viseq(
+      &in_faces, &in_faces_start_table, &in_faces_len_table, faces, error_prefix);
+  if (faces_len == -1) {
+    goto exit_cdt;
+  }
+
+  in.verts_len = (int)vert_coords_len;
+  in.vert_coords = in_coords;
+  in.edges_len = edges_len;
+  in.faces_len = faces_len;
+  in.edges = in_edges;
+  in.faces = in_faces;
+  in.faces_start_table = in_faces_start_table;
+  in.faces_len_table = in_faces_len_table;
+  in.epsilon = epsilon;
+
+  res = BLI_delaunay_2d_cdt_calc(&in, output_type);
+
+  ret_value = PyTuple_New(6);
+
+  out_vert_coords = PyList_New(res->verts_len);
+  for (i = 0; i < res->verts_len; i++) {
+    item = Vector_CreatePyObject(res->vert_coords[i], 2, NULL);
+    if (item == NULL) {
+      Py_DECREF(ret_value);
+      Py_DECREF(out_vert_coords);
+      goto exit_cdt;
+    }
+    PyList_SET_ITEM(out_vert_coords, i, item);
+  }
+  PyTuple_SET_ITEM(ret_value, 0, out_vert_coords);
+
+  out_edges = PyList_New(res->edges_len);
+  for (i = 0; i < res->edges_len; i++) {
+    item = PyTuple_New(2);
+    PyTuple_SET_ITEM(item, 0, PyLong_FromLong((long)res->edges[i][0]));
+    PyTuple_SET_ITEM(item, 1, PyLong_FromLong((long)res->edges[i][1]));
+    PyList_SET_ITEM(out_edges, i, item);
+  }
+  PyTuple_SET_ITEM(ret_value, 1, out_edges);
+
+  out_faces = list_of_lists_from_arrays(
+      res->faces, res->faces_start_table, res->faces_len_table, res->faces_len);
+  PyTuple_SET_ITEM(ret_value, 2, out_faces);
+
+  out_orig_verts = list_of_lists_from_arrays(
+      res->verts_orig, res->verts_orig_start_table, res->verts_orig_len_table, res->verts_len);
+  PyTuple_SET_ITEM(ret_value, 3, out_orig_verts);
+
+  out_orig_edges = list_of_lists_from_arrays(
+      res->edges_orig, res->edges_orig_start_table, res->edges_orig_len_table, res->edges_len);
+  PyTuple_SET_ITEM(ret_value, 4, out_orig_edges);
+
+  out_orig_faces = list_of_lists_from_arrays(
+      res->faces_orig, res->faces_orig_start_table, res->faces_orig_len_table, res->faces_len);
+  PyTuple_SET_ITEM(ret_value, 5, out_orig_faces);
+
+exit_cdt:
+  if (in_coords != NULL) {
+    PyMem_Free(in_coords);
+  }
+  if (in_edges != NULL) {
+    PyMem_Free(in_edges);
+  }
+  if (in_faces != NULL) {
+    PyMem_Free(in_faces);
+  }
+  if (in_faces_start_table != NULL) {
+    PyMem_Free(in_faces_start_table);
+  }
+  if (in_faces_len_table != NULL) {
+    PyMem_Free(in_faces_len_table);
+  }
+  if (res) {
+    BLI_delaunay_2d_cdt_free(res);
+  }
+  return ret_value;
+}
+
 #endif /* MATH_STANDALONE */
 
 static PyMethodDef M_Geometry_methods[] = {
@@ -1593,6 +1774,10 @@ static PyMethodDef M_Geometry_methods[] = {
      (PyCFunction)M_Geometry_convex_hull_2d,
      METH_O,
      M_Geometry_convex_hull_2d_doc},
+    {"delaunay_2d_cdt",
+     (PyCFunction)M_Geometry_delaunay_2d_cdt,
+     METH_VARARGS,
+     M_Geometry_delaunay_2d_cdt_doc},
     {"box_fit_2d", (PyCFunction)M_Geometry_box_fit_2d, METH_O, M_Geometry_box_fit_2d_doc},
     {"box_pack_2d", (PyCFunction)M_Geometry_box_pack_2d, METH_O, M_Geometry_box_pack_2d_doc},
 #endif