[Bf-blender-cvs] [b91643c7113] master: Add Constrained Delaunay Triangulation routine to Blenlib.
Howard Trickey
noreply at git.blender.org
Sat Aug 10 15:27:56 CEST 2019
Commit: b91643c7113554f8cc2c50b9a988b5104bd6821f
Author: Howard Trickey
Date: Sat Aug 10 08:24:20 2019 -0500
Branches: master
https://developer.blender.org/rBb91643c7113554f8cc2c50b9a988b5104bd6821f
Add Constrained Delaunay Triangulation routine to Blenlib.
See Design task T68277, and patch D5423.
This commit includes edits by @ideasman42 to patch in
branch temp-D5423-update, plus responses to his comments.
===================================================================
A source/blender/blenlib/BLI_delaunay_2d.h
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/delaunay_2d.c
A tests/gtests/blenlib/BLI_delaunay_2d_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
new file mode 100644
index 00000000000..fe81de5fc5e
--- /dev/null
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -0,0 +1,199 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __BLI_DELAUNAY_2D_H__
+#define __BLI_DELAUNAY_2D_H__
+
+/** \file
+ * \ingroup bli
+ */
+
+/**
+ * Interface for Constrained Delaunay Triangulation (CDT) in 2D.
+ *
+ * The input is a set of vertices, edges between those vertices,
+ * and faces using those vertices.
+ * Those inputs are called "constraints". The output must contain
+ * those constraints, or at least edges, points, and vertices that
+ * may be pieced together to form the constraints. Part of the
+ * work of doing the CDT is to detect intersections and mergers
+ * among the input elements, so these routines are also useful
+ * for doing 2D intersection.
+ *
+ * The output is a triangulation of the plane that includes the
+ * constraints in the above sense, and also satisfies the
+ * "Delaunay condition" as modified to take into account that
+ * the constraints must be there: for every non-constrained edge
+ * in the output, there is a circle through the endpoints that
+ * does not contain any of the vertices directly connected to
+ * those endpoints. What this means in practice is that as
+ * much as possible the triangles look "nice" -- not too long
+ * and skinny.
+ *
+ * Optionally, the output can be a subset of the triangulation
+ * (but still containing all of the constraints), to get the
+ * effect of 2D intersection.
+ *
+ * The underlying method is incremental, but we need to know
+ * beforehand a bounding box for all of the constraints.
+ * This code can be extended in the future to allow for
+ * deletion of constraints, if there is a use in Blender
+ * for dynamically maintaining a triangulation.
+ */
+
+/**
+ * Input to Constrained Delaunay Triangulation.
+ * There are verts_len vertices, whose coordinates
+ * are given by vert_coords. For the rest of the input,
+ * vertices are referred to by indices into that array.
+ * Edges and Faces are optional. If provided, they will
+ * appear in the output triangulation ("constraints").
+ * One can provide faces and not edges -- the edges
+ * implied by the faces will be inferred.
+ *
+ * The edges are given by pairs of vertex indices.
+ * The faces are given in a triple `(faces, faces_start_table, faces_len_table)`
+ * to represent a list-of-lists as follows:
+ * the vertex indices for a counterclockwise traversal of
+ * face number `i` starts at `faces_start_table[i]` and has `faces_len_table[i]`
+ * elements.
+ *
+ * The edges implied by the faces are automatically added
+ * and need not be put in the edges array, which is intended
+ * as a way to specify edges that are not part of any face.
+ *
+ * Some notes about some special cases and how they are handled:
+ * - Input faces can have any number of vertices greater than 2. Depending
+ * on the output option, ngons may be triangulated or they may remain
+ * as ngons.
+ * - Input faces may have repeated vertices. Output faces will not,
+ * except when the CDT_CONSTRAINTS output option is used.
+ * - Input faces may have edges that self-intersect, but currently the labeling
+ * of which output faces have which input faces may not be done correctly,
+ * since the labeling relies on the inside being on the left of edges
+ * as one traverses the face. Output faces will not self-intersect.
+ * - Input edges, including those implied by the input faces, may have
+ * zero-length or near-zero-length edges (nearness as determined by epsilon),
+ * but those edges will not be in the output.
+ * - Input edges (including face edges) can overlap or nearly overlap each other.
+ * The output edges will not overlap, but instead be divided into as many
+ * edges as necessary to represent each overlap regime.
+ * - Input vertices may be coincide with, or nearly coincide with (as determined
+ * by epsilon) other input vertices. Only one representative will survive
+ * in the output. If an input vertex is within epsilon of an edge (including
+ * an added triangulation edge), it will be snapped to that edge, so the
+ * output coordinates may not exactly match the input coordinates in all cases.
+ * - Wire edges (those not part of faces) and isolated vertices are allowed in
+ * the input. If they are inside faces, they will be incorporated into the
+ * triangulation of those faces.
+ *
+ * Epsilon is used for "is it near enough" distance calculations.
+ * If zero is supplied for epsilon, an internal value of 1e-8 used
+ * instead, since this code will not work correctly if it is not allowed
+ * to merge "too near" vertices.
+ */
+typedef struct CDT_input {
+ int verts_len;
+ int edges_len;
+ int faces_len;
+ float (*vert_coords)[2];
+ int (*edges)[2];
+ int *faces;
+ int *faces_start_table;
+ int *faces_len_table;
+ float epsilon;
+} CDT_input;
+
+/**
+ * A representation of the triangulation for output.
+ * See #CDT_input for the representation of the output
+ * vertices, edges, and faces, all represented in
+ * a similar way to the input.
+ *
+ * The output may have merged some input vertices together,
+ * if they were closer than some epsilon distance.
+ * The output edges may be overlapping sub-segments of some
+ * input edges; or they may be new edges for the triangulation.
+ * The output faces may be pieces of some input faces, or they
+ * may be new.
+ *
+ * In the same way that faces lists-of-lists were represented by
+ * a run-together array and a "start" and "len" extra array,
+ * similar triples are used to represent the output to input
+ * mapping of vertices, edges, and faces.
+ *
+ * Those triples are:
+ * - verts_orig, verts_orig_start_table, verts_orig_len_table
+ * - edges_orig, edges_orig_start_table, edges_orig_len_table
+ * - faces_orig, faces_orig_start_table, faces_orig_len_table
+ *
+ * For edges, the edges_orig triple can also say which original face
+ * edge is part of a given output edge. If an index in edges_orig
+ * is greater than the input's edges_len, then subtract input's edges_len
+ * from it to some number i: then the face edge that starts from the
+ * input vertex at input's faces[i] is the corresponding face edge.
+ * for convenience, face_edge_offset in the result will be the input's
+ * edges_len, so that this conversion can be easily done by the caller.
+ */
+typedef struct CDT_result {
+ int verts_len;
+ int edges_len;
+ int faces_len;
+ int face_edge_offset;
+ float (*vert_coords)[2];
+ int (*edges)[2];
+ int *faces;
+ int *faces_start_table;
+ int *faces_len_table;
+ int *verts_orig;
+ int *verts_orig_start_table;
+ int *verts_orig_len_table;
+ int *edges_orig;
+ int *edges_orig_start_table;
+ int *edges_orig_len_table;
+ int *faces_orig;
+ int *faces_orig_start_table;
+ int *faces_orig_len_table;
+} CDT_result;
+
+/** What triangles and edges of CDT are desired when getting output? */
+typedef enum CDT_output_type {
+ /** All triangles, outer boundary is convex hull. */
+ CDT_FULL,
+ /** All triangles fully enclosed by constraint edges or faces. */
+ CDT_INSIDE,
+ /** Only point, edge, and face constraints, and their intersections. */
+ CDT_CONSTRAINTS,
+ /**
+ * Like CDT_CONSTRAINTS, but keep enough
+ * edges so that any output faces that came from input faces can be made as valid
+ * #BMesh faces in Blender: that is,
+ * no vertex appears more than once and no isolated holes in faces.
+ */
+ CDT_CONSTRAINTS_VALID_BMESH
+} CDT_output_type;
+
+/**
+ * API interface to CDT.
+ * This returns a pointer to an allocated CDT_result.
+ * When the caller is finished with it, the caller
+ * should use #BLI_delaunay_2d_cdt_free() to free it.
+ */
+CDT_result *BLI_delaunay_2d_cdt_calc(const CDT_input *input, const CDT_output_type output_type);
+
+void BLI_delaunay_2d_cdt_free(CDT_result *result);
+
+#endif /* __BLI_DELAUNAY_2D_H__ */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 0ec6e7ee4fc..7f6e9d49b17 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -63,6 +63,7 @@ set(SRC
intern/buffer.c
intern/callbacks.c
intern/convexhull_2d.c
+ intern/delaunay_2d.c
intern/dynlib.c
intern/easing.c
intern/edgehash.c
@@ -150,6 +151,7 @@ set(SRC
BLI_compiler_typecheck.h
BLI_console.h
BLI_convexhull_2d.h
+ BLI_delaunay_2d.h
BLI_dial_2d.h
BLI_dlrbTree.h
BLI_dynlib.h
diff --git a/source/blender/blenlib/intern/delaunay_2d.c b/source/blender/blenlib/intern/delaunay_2d.c
new file mode 100644
index 00000000000..f87ca20af84
--- /dev/null
+++ b/source/blender/blenlib/intern/delaunay_2d.c
@@ -0,0 +1,2899 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-13
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list