diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2019-08-10 16:24:20 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2019-08-10 16:24:20 +0300 |
commit | b91643c7113554f8cc2c50b9a988b5104bd6821f (patch) | |
tree | e4a72d502d1fb5fd48c1eff431a0428dcceb5e72 /source/blender/blenlib/BLI_delaunay_2d.h | |
parent | 553b581f25c1782c4231816965cd3f6ce58a449a (diff) |
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.
Diffstat (limited to 'source/blender/blenlib/BLI_delaunay_2d.h')
-rw-r--r-- | source/blender/blenlib/BLI_delaunay_2d.h | 199 |
1 files changed, 199 insertions, 0 deletions
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__ */ |