[Bf-blender-cvs] [f05b937b558] temp-D5423-update: Initial D5423 (by @howardt)
Campbell Barton
noreply at git.blender.org
Fri Aug 9 09:13:09 CEST 2019
Commit: f05b937b558fb412db3f656459605e91815403de
Author: Campbell Barton
Date: Fri Aug 9 05:59:14 2019 +1000
Branches: temp-D5423-update
https://developer.blender.org/rBf05b937b558fb412db3f656459605e91815403de
Initial D5423 (by @howardt)
===================================================================
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..4ec52b41cf9
--- /dev/null
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -0,0 +1,170 @@
+/*
+ * 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 contraints, 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 dynmically maintaining a triangulation.
+ */
+
+/*
+ * Input to Constrained Delaunay Triangulation.
+ * There are num_vertex vertices, whose coordinates
+ * are given by vert_coords. For the rest of tne 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, face_start, face_len)
+ * to represent a list-of-lists as follows:
+ * the vertex indices for a counterclockwise traversal of
+ * face number i starts at face_start[i] and has face_len[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.
+ *
+ * epsilon is used for "is it near enough" distance calculations.
+ */
+typedef struct CDT_input {
+ int num_verts;
+ int num_edges;
+ int num_faces;
+ float (*vert_coords)[2];
+ int (*edges)[2];
+ int *faces;
+ int *face_start;
+ int *face_len;
+ 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:
+ * vert_orig, vert_orig_start, vert_orig_len
+ * edge_eorig, edge_orig_start, edge_orig_len
+ * face_orig, face_orig_start, face_orig_len
+ *
+ * For edges, the edge_orig triple can also say which original face
+ * edge is part of a given output edge. If an index in edge_orig
+ * is greater than the input's num_edges, then subtract input's num_edges
+ * 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
+ * num_edges, so that this conversion can be easily done by the caller.
+ */
+typedef struct CDT_result {
+ int num_verts;
+ int num_edges;
+ int num_faces;
+ int face_edge_offset;
+ float (*vert_coords)[2];
+ int (*edges)[2];
+ int *faces;
+ int *face_start;
+ int *face_len;
+ int *vert_orig;
+ int *vert_orig_start;
+ int *vert_orig_len;
+ int *edge_orig;
+ int *edge_orig_start;
+ int *edge_orig_len;
+ int *face_orig;
+ int *face_orig_start;
+ int *face_orig_len;
+} CDT_result;
+
+/*
+ * What triangles and edges of CDT are desired when getting output?
+ *
+ * CDT_FULL - all triangles, outer boundary is convex hull
+ * CDT_INSIDE - all triangles fully enclosed by constraint edges or faces
+ * CDT_CONSTRAINTS - only point, edge, and face constraints, and their intersections
+ * CDT_CONSTRAINTS_VALID_BMESH - 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.
+ */
+typedef enum CDT_output_type {
+ CDT_FULL,
+ CDT_INSIDE,
+ CDT_CONSTRAINTS,
+ 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_constrained_delaunay_free() to free it.
+ */
+CDT_result *BLI_constrained_delaunay(const CDT_input *input, const CDT_output_type output_type);
+
+void BLI_constrained_delaunay_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..f5bd7857d00
--- /dev/null
+++ b/source/blender/blenlib/intern/delaunay_2d.c
@@ -0,0 +1,2740 @@
+/*
+ * 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.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * Dynamic Constrained Delaunay Triangulation.
+ * See paper by Marcelo Kallmann, Hanspeter Bieri, and Daniel Thalmann
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_array.h"
+#include "BLI_bitmap.h"
+#include "BLI_linklist.h"
+#include "BLI_math.h"
+#include "BLI_memarena.h"
+#include "BLI_mempool.h"
+#include "BLI_rand.h"
+
+#include "BLI_delaunay_2d.h"
+
+/* uncomment this define to get helpful debugging functions etc. defined */
+#define DEBUG_CDT
+
+struct CDTVert;
+struct CDTEdge;
+struct CDTFace;
+
+typedef struct SymEdge {
+ struct SymEdge *next; /* in face, doing CCW traversal of face */
+ struct SymEdge *rot; /* CCW around vert */
+ struct CDTVert *vert; /* Vert at origin */
+ struct CDTEdge *edge; /* undirected edge this is for */
+ struct CDTFace *face; /* face on left side */
+} SymEdge;
+
+typedef struct CDTVert {
+ double co[2]; /* coordinates */
+ SymEdge *symedge; /* some edge attached to it */
+ LinkNode *input_ids; /* list of corresponding vertex input ids */
+ int index; /* index into array that cdt keeps */
+} CDTVert;
+
+typedef struct CDTEdge {
+ LinkNode *input_ids; /* list of input edge ids that this is part of */
+ SymEdge symedges[2]; /* the directed edges for this edge */
+} CDTEdge;
+
+typedef struct CDTFace {
+ double centroid[2]; /* avearge of vertex coords */
+ SymEdge *symedge; /* a symedge in face; only used during output */
+ LinkNode *input_ids; /* list of input face ids that this is part of */
+ int visit_index; /* which visit epoch has this been seen */
+ bool deleted; /* marks this face no longer used */
+} CDTFace;
+
+typedef struct CDT_state {
+ LinkNode *edges;
+ LinkNode *faces;
+ CDTFace *outer_face;
+ CDTVert **vert_array;
+ int vert_array_len;
+ int vert_array_allocated;
+ double minx;
+ double miny;
+ double maxx;
+ double maxy;
+ double margin;
+ int visit_count;
+ int face_edge_o
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list