blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 747 Projects 19 Wiki Activity

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.
This commit is contained in:
Howard Trickey 2019-08-10 08:24:20 -05:00
parent 553b581f25
commit b91643c711
5 changed files with 3851 additions and 0 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

199
source/blender/blenlib/BLI_delaunay_2d.h Normal file
View File

@ -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__ */

2
source/blender/blenlib/CMakeLists.txt
View File

@ -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

2899
source/blender/blenlib/intern/delaunay_2d.c Normal file
View File

File diff suppressed because it is too large Load Diff

750
tests/gtests/blenlib/BLI_delaunay_2d_test.cc Normal file
View File

@ -0,0 +1,750 @@
/* Apache License, Version 2.0 */
#include "testing/testing.h"
extern "C" {
#include "MEM_guardedalloc.h"
#include "BLI_math.h"
#include "BLI_rand.h"
#include "PIL_time.h"
#include "BLI_delaunay_2d.h"
}
#include <iostream>
#include <fstream>
#include <sstream>
#define DLNY_EPSILON 1e-8
static void fill_input_verts(CDT_input *r_input, float (*vcos)[2], int nverts)
{
r_input->verts_len = nverts;
r_input->edges_len = 0;
r_input->faces_len = 0;
r_input->vert_coords = vcos;
r_input->edges = NULL;
r_input->faces = NULL;
r_input->faces_start_table = NULL;
r_input->faces_len_table = NULL;
r_input->epsilon = 1e-6f;
}
static void add_input_edges(CDT_input *r_input, int (*edges)[2], int nedges)
{
r_input->edges_len = nedges;
r_input->edges = edges;
}
static void add_input_faces(CDT_input *r_input, int *faces, int *faces_start_table, int *faces_len_table, int nfaces)
{
r_input->faces_len = nfaces;
r_input->faces = faces;
r_input->faces_start_table = faces_start_table;
r_input->faces_len_table = faces_len_table;
}
/* which output vert index goes with given input vertex? -1 if not found */
static int get_output_vert_index(const CDT_result *r, int in_index)
{
int i, j;
for (i = 0; i < r->verts_len; i++) {
for (j = 0; j < r->verts_orig_len_table[i]; j++) {
if (r->verts_orig[r->verts_orig_start_table[i] + j] == in_index) {
return i;
}
}
}
return -1;
}
/* which output edge index is for given output vert indices? */
static int get_edge(const CDT_result *r, int out_index_1, int out_index_2)
{
int i;
for (i = 0; i < r->edges_len; i++) {
if ((r->edges[i][0] == out_index_1 && r->edges[i][1] == out_index_2) ||
(r->edges[i][0] == out_index_2 && r->edges[i][1] == out_index_1))
return i;
}
return -1;
}
/* return true if given output edge has given input edge id in its originals list */
static bool out_edge_has_input_id(const CDT_result *r, int out_edge_index, int in_edge_index)
{
if (r->edges_orig == NULL)
return false;
if (out_edge_index < 0 || out_edge_index >= r->edges_len)
return false;
for (int i = 0; i < r->edges_orig_len_table[out_edge_index]; i++) {
if (r->edges_orig[r->edges_orig_start_table[out_edge_index] + i] == in_edge_index)
return true;
}
return false;
}
/* which face is for given output vertex ngon? */
static int get_face(const CDT_result *r, int *out_indices, int nverts)
{
int f, cycle_start, k, fstart;
bool ok;
if (r->faces_len == 0)
return -1;
for (f = 0; f < r->faces_len; f++) {
if (r->faces_len_table[f] != nverts)
continue;
fstart = r->faces_start_table[f];
for (cycle_start = 0; cycle_start < nverts; cycle_start++) {
ok = true;
for (k = 0; ok && k < nverts; k++) {
if (r->faces[fstart + ((cycle_start + k) % nverts)] != out_indices[k]) {
ok = false;
}
}
if (ok) {
return f;
}
}
}
return -1;
}
static int get_face_tri(const CDT_result *r, int out_index_1, int out_index_2, int out_index_3)
{
int tri[3];
tri[0] = out_index_1;
tri[1] = out_index_2;
tri[2] = out_index_3;
return get_face(r, tri, 3);
}
/* return true if given otuput face has given input face id in its originals list */
static bool out_face_has_input_id(const CDT_result *r, int out_face_index, int in_face_index)
{
if (r->faces_orig == NULL)
return false;
if (out_face_index < 0 || out_face_index >= r->faces_len)
return false;
for (int i = 0; i < r->faces_orig_len_table[out_face_index]; i++) {
if (r->faces_orig[r->faces_orig_start_table[out_face_index] + i] == in_face_index)
return true;
}
return false;
}
/* for debugging */
static void dump_result(CDT_result *r)
{
int i, j;
fprintf(stderr, "\nRESULT\n");
fprintf(stderr,
"verts_len=%d edges_len=%d faces_len=%d\n",
r->verts_len,
r->edges_len,
r->faces_len);
fprintf(stderr, "\nvert coords:\n");
for (i = 0; i < r->verts_len; i++)
fprintf(stderr, "%d: (%f,%f)\n", i, r->vert_coords[i][0], r->vert_coords[i][1]);
fprintf(stderr, "vert orig:\n");
for (i = 0; i < r->verts_len; i++) {
fprintf(stderr, "%d:", i);
for (j = 0; j < r->verts_orig_len_table[i]; j++)
fprintf(stderr, " %d", r->verts_orig[r->verts_orig_start_table[i] + j]);
fprintf(stderr, "\n");
}
fprintf(stderr, "\nedges:\n");
for (i = 0; i < r->edges_len; i++)
fprintf(stderr, "%d: (%d,%d)\n", i, r->edges[i][0], r->edges[i][1]);
if (r->edges_orig) {
fprintf(stderr, "edge orig:\n");
for (i = 0; i < r->edges_len; i++) {
fprintf(stderr, "%d:", i);
for (j = 0; j < r->edges_orig_len_table[i]; j++)
fprintf(stderr, " %d", r->edges_orig[r->edges_orig_start_table[i] + j]);
fprintf(stderr, "\n");
}
}
fprintf(stderr, "\nfaces:\n");
for (i = 0; i < r->faces_len; i++) {
fprintf(stderr, "%d: ", i);
for (j = 0; j < r->faces_len_table[i]; j++)
fprintf(stderr, " %d", r->faces[r->faces_start_table[i] + j]);
fprintf(stderr, "\n");
}
if (r->faces_orig) {
fprintf(stderr, "face orig:\n");
for (i = 0; i < r->faces_len; i++) {
fprintf(stderr, "%d:", i);
for (j = 0; j < r->faces_orig_len_table[i]; j++)
fprintf(stderr, " %d", r->faces_orig[r->faces_orig_start_table[i] + j]);
fprintf(stderr, "\n");
}
}
}
TEST(delaunay, Empty)
{
CDT_input in;
CDT_result *out;
fill_input_verts(&in, NULL, 0);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_NE((CDT_result *)NULL, out);
EXPECT_EQ(out->verts_len, 0);
EXPECT_EQ(out->edges_len, 0);
EXPECT_EQ(out->faces_len, 0);
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, OnePt)
{
CDT_input in;
CDT_result *out;
float p[][2] = {{0.0f, 0.0f}};
fill_input_verts(&in, p, 1);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 1);
EXPECT_EQ(out->edges_len, 0);
EXPECT_EQ(out->faces_len, 0);
EXPECT_EQ(out->vert_coords[0][0], 0.0f);
EXPECT_EQ(out->vert_coords[0][1], 0.0f);
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, TwoPt)
{
CDT_input in;
CDT_result *out;
int v0_out, v1_out, e0_out;
float p[][2] = {{0.0f, -0.75f}, {0.0f, 0.75f}};
fill_input_verts(&in, p, 2);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 2);
EXPECT_EQ(out->edges_len, 1);
EXPECT_EQ(out->faces_len, 0);
v0_out = get_output_vert_index(out, 0);
v1_out = get_output_vert_index(out, 1);
EXPECT_NE(v0_out, -1);
EXPECT_NE(v1_out, -1);
EXPECT_NE(v0_out, v1_out);
EXPECT_NEAR(out->vert_coords[v0_out][0], p[0][0], in.epsilon);
EXPECT_NEAR(out->vert_coords[v0_out][1], p[0][1], in.epsilon);
EXPECT_NEAR(out->vert_coords[v1_out][0], p[1][0], in.epsilon);
EXPECT_NEAR(out->vert_coords[v1_out][1], p[1][1], in.epsilon);
e0_out = get_edge(out, v0_out, v1_out);
EXPECT_EQ(e0_out, 0);
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, ThreePt)
{
CDT_input in;
CDT_result *out;
int v0_out, v1_out, v2_out;
int e0_out, e1_out, e2_out;
int f0_out;
float p[][2] = {{-0.1f, -0.75f}, {0.1f, 0.75f}, {0.5f, 0.5f}};
fill_input_verts(&in, p, 3);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 3);
EXPECT_EQ(out->edges_len, 3);
EXPECT_EQ(out->faces_len, 1);
v0_out = get_output_vert_index(out, 0);
v1_out = get_output_vert_index(out, 1);
v2_out = get_output_vert_index(out, 2);
EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1);
EXPECT_TRUE(v0_out != v1_out && v0_out != v2_out && v1_out != v2_out);
e0_out = get_edge(out, v0_out, v1_out);
e1_out = get_edge(out, v1_out, v2_out);
e2_out = get_edge(out, v2_out, v0_out);
EXPECT_TRUE(e0_out != -1 && e1_out != -1 && e2_out != -1);
EXPECT_TRUE(e0_out != e1_out && e0_out != e2_out && e1_out != e2_out);
f0_out = get_face_tri(out, v0_out, v2_out, v1_out);
EXPECT_EQ(f0_out, 0);
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, ThreePtsMerge)
{
CDT_input in;
CDT_result *out;
int v0_out, v1_out, v2_out;
/* equilateral triangle with side 0.1 */
float p[][2] = {{-0.05f, -0.05f}, {0.05f, -0.05f}, {0.0f, 0.03660254f}};
/* First with epsilon such that points are within that distance of each other */
fill_input_verts(&in, p, 3);
in.epsilon = 0.21f;
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 1);
EXPECT_EQ(out->edges_len, 0);
EXPECT_EQ(out->faces_len, 0);
v0_out = get_output_vert_index(out, 0);
v1_out = get_output_vert_index(out, 1);
v2_out = get_output_vert_index(out, 2);
EXPECT_EQ(v0_out, 0);
EXPECT_EQ(v1_out, 0);
EXPECT_EQ(v2_out, 0);
BLI_delaunay_2d_cdt_free(out);
/* Now with epsilon such that points are farther away than that.
* Note that the points won't merge with each other if distance is
* less than .01, but that they may merge with points on the Delaunay
* triangulation lines, so make epsilon even smaller to avoid that for
* this test.
*/
in.epsilon = 0.05f;
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 3);
EXPECT_EQ(out->edges_len, 3);
EXPECT_EQ(out->faces_len, 1);
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, MixedPts)
{
CDT_input in;
CDT_result *out;
float p[][2] = {{0.0f, 0.0f}, {-0.5f, -0.5f}, {-0.4f, -0.25f}, {-0.3f, 0.8}};
int e[][2] = {{0, 1}, {1, 2}, {2, 3}};
int v0_out, v1_out, v2_out, v3_out;
int e0_out, e1_out, e2_out;
fill_input_verts(&in, p, 4);
add_input_edges(&in, e, 3);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 4);
EXPECT_EQ(out->edges_len, 6);
v0_out = get_output_vert_index(out, 0);
v1_out = get_output_vert_index(out, 1);
v2_out = get_output_vert_index(out, 2);
v3_out = get_output_vert_index(out, 3);
EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1);
e0_out = get_edge(out, v0_out, v1_out);
e1_out = get_edge(out, v1_out, v2_out);
e2_out = get_edge(out, v2_out, v3_out);
EXPECT_TRUE(e0_out != -1 && e1_out != -1 && e2_out != -1);
EXPECT_TRUE(out_edge_has_input_id(out, e0_out, 0));
EXPECT_TRUE(out_edge_has_input_id(out, e1_out, 1));
EXPECT_TRUE(out_edge_has_input_id(out, e2_out, 2));
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, CrossSegs)
{
CDT_input in;
CDT_result *out;
float p[][2] = {{-0.5f, 0.0f}, {0.5f, 0.0f}, {-0.4f, -0.5f}, {0.4f, 0.5f}};
int e[][2] = {{0, 1}, {2, 3}};
int v0_out, v1_out, v2_out, v3_out, v_intersect;
int i;
fill_input_verts(&in, p, 4);
add_input_edges(&in, e, 2);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 5);
EXPECT_EQ(out->edges_len, 8);
EXPECT_EQ(out->faces_len, 4);
v0_out = get_output_vert_index(out, 0);
v1_out = get_output_vert_index(out, 1);
v2_out = get_output_vert_index(out, 2);
v3_out = get_output_vert_index(out, 3);
EXPECT_TRUE(v0_out != -1 && v1_out != -1 && v2_out != -1 && v3_out != -1);
v_intersect = -1;
for (i = 0; i < out->verts_len; i++) {
if (i != v0_out && i != v1_out && i != v2_out && i != v3_out) {
EXPECT_EQ(v_intersect, -1);
v_intersect = i;
}
}
EXPECT_NE(v_intersect, -1);
EXPECT_NEAR(out->vert_coords[v_intersect][0], 0.0f, in.epsilon);
EXPECT_NEAR(out->vert_coords[v_intersect][1], 0.0f, in.epsilon);
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, DiamondCross)
{
CDT_input in;
CDT_result *out;
float p[][2] = {{0.0f, 0.0f},
{1.0f, 3.0f},
{2.0f, 0.0f},
{1.0f, -3.0f},
{0.0f, 0.0f},
{1.0f, -3.0f},
{1.0f, 3.0f}};
int e[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {5, 6}};
fill_input_verts(&in, p, 7);
add_input_edges(&in, e, 5);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 4);
EXPECT_EQ(out->edges_len, 5);
EXPECT_EQ(out->faces_len, 2);
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, TwoDiamondsCrossed)
{
CDT_input in;
CDT_result *out;
/* Input has some repetition of vertices, on purpose */
float p[][2] = {{0.0f, 0.0f},
{1.0f, 2.0f},
{2.0f, 0.0f},
{1.0f, -2.0f},
{0.0f, 0.0f},
{3.0f, 0.0f},
{4.0f, 2.0f},
{5.0f, 0.0f},
{4.0f, -2.0f},
{3.0f, 0.0f},
{0.0f, 0.0f},
{5.0f, 0.0f}};
int e[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {10, 11}};
int v_out[12];
int e_out[9], e_cross_1, e_cross_2, e_cross_3;
int i;
fill_input_verts(&in, p, 12);
add_input_edges(&in, e, 9);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 8);
EXPECT_EQ(out->edges_len, 15);
EXPECT_EQ(out->faces_len, 8);
for (i = 0; i < 12; i++) {
v_out[i] = get_output_vert_index(out, i);
EXPECT_NE(v_out[i], -1);
}
EXPECT_EQ(v_out[0], v_out[4]);
EXPECT_EQ(v_out[0], v_out[10]);
EXPECT_EQ(v_out[5], v_out[9]);
EXPECT_EQ(v_out[7], v_out[11]);
for (i = 0; i < 8; i++) {
e_out[i] = get_edge(out, v_out[e[i][0]], v_out[e[i][1]]);
EXPECT_NE(e_out[i], -1);
}
/* there won't be a single edge for the input cross edge, but rather 3 */
EXPECT_EQ(get_edge(out, v_out[10], v_out[11]), -1);
e_cross_1 = get_edge(out, v_out[0], v_out[2]);
e_cross_2 = get_edge(out, v_out[2], v_out[5]);
e_cross_3 = get_edge(out, v_out[5], v_out[7]);
EXPECT_TRUE(e_cross_1 != -1 && e_cross_2 != -1 && e_cross_3 != -1);
EXPECT_TRUE(out_edge_has_input_id(out, e_cross_1, 8));
EXPECT_TRUE(out_edge_has_input_id(out, e_cross_2, 8));
EXPECT_TRUE(out_edge_has_input_id(out, e_cross_3, 8));
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, ManyCross)
{
CDT_input in;
CDT_result *out;
/* Input has some repetition of vertices, on purpose */
float p[][2] = {/* upper: verts 0 to 10 */
{0.0f, 0.0f},
{6.0f, 9.0f},
{15.0f, 18.0f},
{35.0f, 13.0f},
{43.0f, 18.0f},
{57.0f, 12.0f},
{69.0f, 10.0f},
{78.0f, 0.0f},
{91.0f, 0.0f},
{107.0f, 22.0f},
{123.0f, 0.0f},
/* lower part 1: verts 11 to 16 */
{0.0f, 0.0f},
{10.0f, -14.0f},
{35.0f, -8.0f},
{43.0f, -12.0f},
{64.0f, -13.0f},
{78.0f, 0.0f},
/* lower part 2: verts 17 to 20 */
{91.0f, 0.0f},
{102.0f, -9.0f},
{116.0f, -9.0f},
{123.0f, 0.0f},
/* cross 1: verts 21, 22 */
{43.0f, 18.0f},
{43.0f, -12.0f},
/* cross 2: verts 23, 24 */
{107.0f, 22.0f},
{102.0f, -9.0f},
/* cross all: verts 25, 26 */
{0.0f, 0.0f},
{123.0f, 0.0f}};
int e[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7},
{7, 8}, {8, 9}, {9, 10}, {11, 12}, {12, 13}, {13, 14}, {14, 15},
{15, 16}, {17, 18}, {18, 19}, {19, 20}, {21, 22}, {23, 24}, {25, 26}};
fill_input_verts(&in, p, 27);
add_input_edges(&in, e, 21);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 19);
EXPECT_EQ(out->edges_len, 46);
EXPECT_EQ(out->faces_len, 28);
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, TwoFace) {
CDT_input in;
CDT_result *out;
float p[][2] = {{0.0f, 0.0f}, {1.0f, 0.0f}, {0.5f, 1.0f}, {1.1f, 1.0f}, {1.1f, 0.0f}, {1.6f, 1.0f}};
int f[] = {/* 0 */ 0, 1, 2, /* 1 */ 3, 4, 5};
int fstart[] = {0, 3};
int flen[] = {3, 3};
int v_out[6], f0_out, f1_out, e0_out, e1_out, e2_out;
int i;
fill_input_verts(&in, p, 6);
add_input_faces(&in, f, fstart, flen, 2);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 6);
EXPECT_EQ(out->edges_len, 9);
EXPECT_EQ(out->faces_len, 4);
for (i = 0; i < 6; i++) {
v_out[i] = get_output_vert_index(out, i);
EXPECT_NE(v_out[i], -1);
}
f0_out = get_face(out, &v_out[0], 3);
f1_out = get_face(out, &v_out[3], 3);
EXPECT_NE(f0_out, -1);
EXPECT_NE(f1_out, -1);
e0_out = get_edge(out, v_out[0], v_out[1]);
e1_out = get_edge(out, v_out[1], v_out[2]);
e2_out = get_edge(out, v_out[2], v_out[0]);
EXPECT_NE(e0_out, -1);
EXPECT_NE(e1_out, -1);
EXPECT_NE(e2_out, -1);
EXPECT_TRUE(out_edge_has_input_id(out, e0_out, out->face_edge_offset + 0));
EXPECT_TRUE(out_edge_has_input_id(out, e1_out, out->face_edge_offset + 1));
EXPECT_TRUE(out_edge_has_input_id(out, e2_out, out->face_edge_offset + 2));
EXPECT_TRUE(out_face_has_input_id(out, f0_out, 0));
EXPECT_TRUE(out_face_has_input_id(out, f1_out, 1));
BLI_delaunay_2d_cdt_free(out);
}
TEST(delaunay, OverlapFaces) {
CDT_input in;
CDT_result *out;
float p[][2] = {{0.0f, 0.0f}, {1.0f, 0.0f}, {1.0f, 1.0f}, {0.0f, 1.0f},
{0.5f, 0.5f}, {1.5f, 0.5f}, {1.5f, 1.3f}, {0.5f, 1.3f},
{0.1f, 0.1f}, {0.3f, 0.1f}, {0.3f, 0.3f}, {0.1f, 0.3f}};
int f[] = {/* 0 */ 0, 1, 2, 3, /* 1 */ 4, 5, 6, 7, /* 2*/ 8, 9, 10, 11};
int fstart[] = {0, 4, 8};
int flen[] = {4, 4, 4};
int v_out[12], v_int1, v_int2, f0_out, f1_out, f2_out;
int i;
fill_input_verts(&in, p, 12);
add_input_faces(&in, f, fstart, flen, 3);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_EQ(out->verts_len, 14);
EXPECT_EQ(out->edges_len, 33);
EXPECT_EQ(out->faces_len, 20);
for (i = 0; i < 12; i++) {
v_out[i] = get_output_vert_index(out, i);
EXPECT_NE(v_out[i], -1);
}
v_int1 = 12;
v_int2 = 13;
if (fabsf(out->vert_coords[v_int1][0] - 1.0f) > in.epsilon) {
v_int1 = 13;
v_int2 = 12;
}
EXPECT_NEAR(out->vert_coords[v_int1][0], 1.0, in.epsilon);
EXPECT_NEAR(out->vert_coords[v_int1][1], 0.5, in.epsilon);
EXPECT_NEAR(out->vert_coords[v_int2][0], 0.5, in.epsilon);
EXPECT_NEAR(out->vert_coords[v_int2][1], 1.0, in.epsilon);
f0_out = get_face_tri(out, v_out[1], v_int1, v_out[4]);
EXPECT_NE(f0_out, -1);
EXPECT_TRUE(out_face_has_input_id(out, f0_out, 0));
f1_out = get_face_tri(out, v_out[4], v_int1, v_out[2]);
EXPECT_NE(f1_out, -1);
EXPECT_TRUE(out_face_has_input_id(out, f1_out, 0));
EXPECT_TRUE(out_face_has_input_id(out, f1_out, 0));
f2_out = get_face_tri(out, v_out[8], v_out[9], v_out[10]);
EXPECT_NE(f2_out, -1);
EXPECT_TRUE(out_face_has_input_id(out, f2_out, 0));
EXPECT_TRUE(out_face_has_input_id(out, f2_out, 2));
BLI_delaunay_2d_cdt_free(out);
/* Different output types */
out = BLI_delaunay_2d_cdt_calc(&in, CDT_INSIDE);
EXPECT_EQ(out->faces_len, 18);
BLI_delaunay_2d_cdt_free(out);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_CONSTRAINTS);
EXPECT_EQ(out->faces_len, 4);
BLI_delaunay_2d_cdt_free(out);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_CONSTRAINTS_VALID_BMESH);
EXPECT_EQ(out->faces_len, 5);
BLI_delaunay_2d_cdt_free(out);
}
enum {
RANDOM_PTS,
RANDOM_SEGS,
RANDOM_POLY,
};
// #define DO_TIMING
static void rand_delaunay_test(int test_kind, int max_lg_size, int reps_per_size)
{
CDT_input in;
CDT_result *out;
int lg_size, size, rep, i, npts, nedges;
float (*p)[2];
int (*e)[2];
double tstart;
double *times;
RNG *rng;
rng = BLI_rng_new(0);
npts = (1 << max_lg_size);
p = (float (*)[2])MEM_malloc_arrayN(npts, 2 * sizeof(float), "delaunay");
switch (test_kind) {
case RANDOM_PTS:
nedges = 0;
e = NULL;
break;
case RANDOM_SEGS:
case RANDOM_POLY:
/* TODO: use faces for poly case, but need to deal with winding parity issue */
nedges = npts - 1 + (test_kind == RANDOM_POLY);
e = (int (*)[2])MEM_malloc_arrayN(nedges, 2 * sizeof(int), "delaunay");
break;
default:
fprintf(stderr, "unknown random delaunay test kind\n");
return;
}
times = (double *)MEM_malloc_arrayN(max_lg_size + 1, sizeof(double), "delaunay");
for (lg_size = 0; lg_size <= max_lg_size; lg_size++) {
size = 1 << lg_size;
times[lg_size] = 0.0;
if (size == 1 && test_kind != RANDOM_PTS)
continue;
for (rep = 0; rep < reps_per_size; rep++) {
for (i = 0; i < size; i++) {
p[i][0] = (float)BLI_rng_get_double(rng); /* will be in range in [0,1) */
p[i][1] = (float)BLI_rng_get_double(rng);
}
fill_input_verts(&in, p, size);
if (test_kind == RANDOM_SEGS || test_kind == RANDOM_POLY) {
for (i = 0; i < size - 1; i++) {
e[i][0] = i;
e[i][1] = i + 1;
}
if (test_kind == RANDOM_POLY) {
e[size - 1][0] = size - 1;
e[size - 1][1] = 0;
}
add_input_edges(&in, e, size - 1 + (test_kind == RANDOM_POLY));
}
tstart = PIL_check_seconds_timer();
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
EXPECT_NE(out->verts_len, 0);
BLI_delaunay_2d_cdt_free(out);
times[lg_size] += PIL_check_seconds_timer() - tstart;
}
}
# ifdef DO_TIMING
fprintf(stderr, "size,time\n");
for (lg_size = 0; lg_size <= max_lg_size; lg_size++) {
fprintf(stderr, "%d,%f\n", 1 << lg_size, times[lg_size] / reps_per_size);
}
# endif
MEM_freeN(p);
if (e)
MEM_freeN(e);
MEM_freeN(times);
BLI_rng_free(rng);
}
TEST(delaunay, randompts)
{
rand_delaunay_test(RANDOM_PTS, 7, 1);
}
TEST(delaunay, randomsegs)
{
rand_delaunay_test(RANDOM_SEGS, 7, 1);
}
TEST(delaunay, randompoly)
{
rand_delaunay_test(RANDOM_POLY, 7, 1);
}
#if 0
/* For debugging or timing large examples.
* The given file should have one point per line, as a space-separated pair of floats
*/
static void points_from_file_test(const char *filename)
{
std::ifstream f;
std::string line;
struct XY {
float x;
float y;
} xy;
std::vector<XY> pts;
int i, n;
CDT_input in;
CDT_result *out;
double tstart;
float (*p)[2];
f.open(filename);
while (getline(f, line)) {
std::istringstream iss(line);
iss >> xy.x >> xy.y;
pts.push_back(xy);
}
n = (int)pts.size();
fprintf(stderr, "read %d points\n", (int)pts.size());
p = (float (*)[2])MEM_malloc_arrayN(n, 2 * sizeof(float), "delaunay");
for (i = 0; i < n; i++) {
xy = pts[i];
p[i][0] = xy.x;
p[i][1] = xy.y;
}
tstart = PIL_check_seconds_timer();
fill_input_verts(&in, p, n);
out = BLI_delaunay_2d_cdt_calc(&in, CDT_FULL);
fprintf(stderr, "time to triangulate=%f seconds\n", PIL_check_seconds_timer() - tstart);
BLI_delaunay_2d_cdt_free(out);
MEM_freeN(p);
}
# define POINTFILEROOT "/tmp/"
TEST(delaunay, terrain1)
{
points_from_file_test(POINTFILEROOT "points1.txt");
}
TEST(delaunay, terrain2)
{
points_from_file_test(POINTFILEROOT "points2.txt");
}
TEST(delaunay, terrain3)
{
points_from_file_test(POINTFILEROOT "points3.txt");
}
#endif

1
tests/gtests/blenlib/CMakeLists.txt
View File

@ -40,6 +40,7 @@ endif()
BLENDER_TEST(BLI_array_store "bf_blenlib")
BLENDER_TEST(BLI_array_utils "bf_blenlib")
BLENDER_TEST(BLI_delaunay_2d "bf_blenlib")
BLENDER_TEST(BLI_expr_pylike_eval "bf_blenlib")
BLENDER_TEST(BLI_edgehash "bf_blenlib")
BLENDER_TEST(BLI_ghash "bf_blenlib")