[Bf-blender-cvs] [6dfe4cbc6b8] master: Polyfill Beautify: half-edge optimization
Campbell Barton
noreply at git.blender.org
Sun Oct 22 16:37:54 CEST 2017
Commit: 6dfe4cbc6b8717223c631e80af6c7552576966e1
Author: Campbell Barton
Date: Mon Oct 23 01:15:26 2017 +1100
Branches: master
https://developer.blender.org/rB6dfe4cbc6b8717223c631e80af6c7552576966e1
Polyfill Beautify: half-edge optimization
Was using an edge hash for triangle -> edge lookups,
updating triangle indices for each edge-rotation.
Replace this with half-edge which can rotate edges much more simply,
writing triangles back once the solution has been calculated.
Gives ~33% speedup in own tests.
===================================================================
M source/blender/blenlib/BLI_polyfill2d_beautify.h
M source/blender/blenlib/intern/polyfill2d_beautify.c
M source/blender/bmesh/intern/bmesh_polygon.c
M source/blender/bmesh/intern/bmesh_polygon.h
M source/blender/bmesh/operators/bmo_connect_concave.c
M source/blender/bmesh/tools/bmesh_decimate_collapse.c
M source/blender/bmesh/tools/bmesh_triangulate.c
M tests/gtests/blenlib/BLI_polyfill2d_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_polyfill2d_beautify.h b/source/blender/blenlib/BLI_polyfill2d_beautify.h
index 29a900200bb..278771e9611 100644
--- a/source/blender/blenlib/BLI_polyfill2d_beautify.h
+++ b/source/blender/blenlib/BLI_polyfill2d_beautify.h
@@ -21,7 +21,6 @@
#ifndef __BLI_POLYFILL2D_BEAUTIFY_H__
#define __BLI_POLYFILL2D_BEAUTIFY_H__
-struct EdgeHash;
struct Heap;
struct MemArena;
@@ -31,7 +30,7 @@ void BLI_polyfill_beautify(
unsigned int (*tris)[3],
/* structs for reuse */
- struct MemArena *arena, struct Heap *eheap, struct EdgeHash *eh);
+ struct MemArena *arena, struct Heap *eheap);
float BLI_polyfill_beautify_quad_rotate_calc_ex(
const float v1[2], const float v2[2], const float v3[2], const float v4[2],
diff --git a/source/blender/blenlib/intern/polyfill2d_beautify.c b/source/blender/blenlib/intern/polyfill2d_beautify.c
index 5f6fb8e6cd4..f2a1c194eb1 100644
--- a/source/blender/blenlib/intern/polyfill2d_beautify.c
+++ b/source/blender/blenlib/intern/polyfill2d_beautify.c
@@ -42,77 +42,56 @@
#include "BLI_math.h"
#include "BLI_memarena.h"
-#include "BLI_edgehash.h"
#include "BLI_heap.h"
#include "BLI_polyfill2d_beautify.h" /* own include */
#include "BLI_strict_flags.h"
-struct PolyEdge {
- /** ordered vert indices (smaller first) */
- unsigned int verts[2];
- /** ordered face indices (depends on winding compared to the edge verts)
- * - (verts[0], verts[1]) == faces[0]
- * - (verts[1], verts[0]) == faces[1]
- */
- unsigned int faces[2];
- /**
- * The face-index which isn't used by either of the edges verts [0 - 2].
- * could be calculated each time, but cleaner to store for reuse.
- */
- unsigned int faces_other_v[2];
+/* Used to find matching edges. */
+struct OrderEdge {
+ uint verts[2];
+ uint e_half;
};
+/* Half edge used for rotating in-place. */
+struct HalfEdge {
+ uint v;
+ uint e_next;
+ uint e_radial;
+ uint base_index;
+};
-#ifndef NDEBUG
-/**
- * Only to check for error-cases.
- */
-static void polyfill_validate_tri(unsigned int (*tris)[3], unsigned int tri_index, EdgeHash *ehash)
+static int oedge_cmp(const void *a1, const void *a2)
{
- const unsigned int *tri = tris[tri_index];
- int j_curr;
-
- BLI_assert(!ELEM(tri[0], tri[1], tri[2]) &&
- !ELEM(tri[1], tri[0], tri[2]) &&
- !ELEM(tri[2], tri[0], tri[1]));
-
- for (j_curr = 0; j_curr < 3; j_curr++) {
- struct PolyEdge *e;
- unsigned int e_v1 = tri[(j_curr ) ];
- unsigned int e_v2 = tri[(j_curr + 1) % 3];
- e = BLI_edgehash_lookup(ehash, e_v1, e_v2);
- if (e) {
- if (e->faces[0] == tri_index) {
- BLI_assert(e->verts[0] == e_v1);
- BLI_assert(e->verts[1] == e_v2);
- }
- else if (e->faces[1] == tri_index) {
- BLI_assert(e->verts[0] == e_v2);
- BLI_assert(e->verts[1] == e_v1);
- }
- else {
- BLI_assert(0);
- }
+ const struct OrderEdge *x1 = a1, *x2 = a2;
+ if (x1->verts[0] > x2->verts[0]) {
+ return 1;
+ }
+ else if (x1->verts[0] < x2->verts[0]) {
+ return -1;
+ }
- BLI_assert(e->faces[0] != e->faces[1]);
- BLI_assert(ELEM(e_v1, UNPACK3(tri)));
- BLI_assert(ELEM(e_v2, UNPACK3(tri)));
- BLI_assert(ELEM(e_v1, UNPACK2(e->verts)));
- BLI_assert(ELEM(e_v2, UNPACK2(e->verts)));
- BLI_assert(e_v1 != tris[e->faces[0]][e->faces_other_v[0]]);
- BLI_assert(e_v1 != tris[e->faces[1]][e->faces_other_v[1]]);
- BLI_assert(e_v2 != tris[e->faces[0]][e->faces_other_v[0]]);
- BLI_assert(e_v2 != tris[e->faces[1]][e->faces_other_v[1]]);
-
- BLI_assert(ELEM(tri_index, UNPACK2(e->faces)));
- }
+ if (x1->verts[1] > x2->verts[1]) {
+ return 1;
+ }
+ else if (x1->verts[1] < x2->verts[1]) {
+ return -1;
+ }
+
+ /* only for pradictability */
+ if (x1->e_half > x2->e_half) {
+ return 1;
}
+ else if (x1->e_half < x2->e_half) {
+ return -1;
+ }
+ /* Should never get here, no two edges should be the same. */
+ BLI_assert(false);
+ return 0;
}
-#endif
-BLI_INLINE bool is_boundary_edge(unsigned int i_a, unsigned int i_b, const unsigned int coord_last)
+BLI_INLINE bool is_boundary_edge(uint i_a, uint i_b, const uint coord_last)
{
BLI_assert(i_a < i_b);
return ((i_a + 1 == i_b) || UNLIKELY((i_a == 0) && (i_b == coord_last)));
@@ -215,27 +194,31 @@ float BLI_polyfill_beautify_quad_rotate_calc_ex(
static float polyedge_rotate_beauty_calc(
const float (*coords)[2],
- const unsigned int (*tris)[3],
- const struct PolyEdge *e)
+ const struct HalfEdge *edges,
+ const struct HalfEdge *e_a)
{
+ const struct HalfEdge *e_b = &edges[e_a->e_radial];
+
+ const struct HalfEdge *e_a_other = &edges[edges[e_a->e_next].e_next];
+ const struct HalfEdge *e_b_other = &edges[edges[e_b->e_next].e_next];
+
const float *v1, *v2, *v3, *v4;
- v1 = coords[tris[e->faces[0]][e->faces_other_v[0]]];
- v3 = coords[tris[e->faces[1]][e->faces_other_v[1]]];
- v2 = coords[e->verts[0]];
- v4 = coords[e->verts[1]];
+ v1 = coords[e_a_other->v];
+ v2 = coords[e_a->v];
+ v3 = coords[e_b_other->v];
+ v4 = coords[e_b->v];
return BLI_polyfill_beautify_quad_rotate_calc(v1, v2, v3, v4);
}
static void polyedge_beauty_cost_update_single(
const float (*coords)[2],
- const unsigned int (*tris)[3],
- const struct PolyEdge *edges,
- struct PolyEdge *e,
+ const struct HalfEdge *edges,
+ struct HalfEdge *e,
Heap *eheap, HeapNode **eheap_table)
{
- const unsigned int i = (unsigned int)(e - edges);
+ const uint i = e->base_index;
if (eheap_table[i]) {
BLI_heap_remove(eheap, eheap_table[i]);
@@ -244,7 +227,7 @@ static void polyedge_beauty_cost_update_single(
{
/* recalculate edge */
- const float cost = polyedge_rotate_beauty_calc(coords, tris, e);
+ const float cost = polyedge_rotate_beauty_calc(coords, edges, e);
/* We can get cases where both choices generate very small negative costs, which leads to infinite loop.
* Anyway, costs above that are not worth recomputing, maybe we could even optimize it to a smaller limit?
* Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully?
@@ -260,39 +243,22 @@ static void polyedge_beauty_cost_update_single(
static void polyedge_beauty_cost_update(
const float (*coords)[2],
- const unsigned int (*tris)[3],
- const struct PolyEdge *edges,
- struct PolyEdge *e,
- Heap *eheap, HeapNode **eheap_table,
- EdgeHash *ehash)
+ struct HalfEdge *edges,
+ struct HalfEdge *e,
+ Heap *eheap, HeapNode **eheap_table)
{
- const unsigned int *tri_0 = tris[e->faces[0]];
- const unsigned int *tri_1 = tris[e->faces[1]];
- unsigned int i;
-
- struct PolyEdge *e_arr[4] = {
- BLI_edgehash_lookup(ehash,
- tri_0[(e->faces_other_v[0] ) % 3],
- tri_0[(e->faces_other_v[0] + 1) % 3]),
- BLI_edgehash_lookup(ehash,
- tri_0[(e->faces_other_v[0] + 2) % 3],
- tri_0[(e->faces_other_v[0] ) % 3]),
- BLI_edgehash_lookup(ehash,
- tri_1[(e->faces_other_v[1] ) % 3],
- tri_1[(e->faces_other_v[1] + 1) % 3]),
- BLI_edgehash_lookup(ehash,
- tri_1[(e->faces_other_v[1] + 2) % 3],
- tri_1[(e->faces_other_v[1] ) % 3]),
- };
-
-
- for (i = 0; i < 4; i++) {
- if (e_arr[i]) {
- BLI_assert(!(ELEM(e_arr[i]->faces[0], UNPACK2(e->faces)) &&
- ELEM(e_arr[i]->faces[1], UNPACK2(e->faces))));
+ struct HalfEdge *e_arr[4];
+ e_arr[0] = &edges[e->e_next];
+ e_arr[1] = &edges[e_arr[0]->e_next];
+
+ e = &edges[e->e_radial];
+ e_arr[2] = &edges[e->e_next];
+ e_arr[3] = &edges[e_arr[2]->e_next];
+ for (uint i = 0; i < 4; i++) {
+ if (e_arr[i] && e_arr[i]->base_index != UINT_MAX) {
polyedge_beauty_cost_update_single(
- coords, tris, edges,
+ coords, edges,
e_arr[i],
eheap, eheap_table);
}
@@ -300,91 +266,49 @@ static void polyedge_beauty_cost_update(
}
static void polyedge_rotate(
- unsigned int (*tris)[3],
- struct PolyEdge *e,
- EdgeHash *ehash)
+ struct HalfEdge *edges,
+ struct HalfEdge *e)
{
- unsigned int e_v1_new = tris[e->faces[0]][e->faces_other_v[0]];
- unsigned int e_v2_new = tris[e->faces[1]][e->faces_other_v[1]];
-
-#ifndef NDEBUG
- polyfill_validate_tri(tris, e->faces[0], ehash);
- polyfill_validate_tri(tris, e->faces[1], ehash);
-#endif
-
- BLI_assert(e_v1_new != e_v2_new);
- BLI_assert(!ELEM(e_v2_new, UNPACK3(tris[e->faces[0]])));
- BLI_assert(!ELEM(e_v1_new, UNPACK3(tris[e->faces[1]])));
-
- tris[e->faces[0]][(e->faces_other_v[0] + 1) % 3] = e_v2_new;
- tris[e->faces[1]][(e->faces_other_v[1] + 1) % 3] = e_v1_new;
-
- e->faces_other_v[0] = (e->faces_other_v[0] + 2) % 3;
- e->faces_other_v[1] = (e->faces_other_v[1] + 2) % 3;
-
- BLI_assert((tris[e->faces[0]][e->faces_other_v[0]] != e_v1_new) &&
- (tris[e->faces[0]][e->faces_other_v[0]] != e_v2_new));
- BLI_assert((tris[e->faces[1]][e->faces_other_v[1]] != e_v1_new) &&
- (tris[e->faces[1]][e->faces_other_v[1]] != e_v2_new));
-
- BLI_edgehash_remove(ehash, e->verts[0], e->verts[1], NULL);
- BLI_edgehash_insert(ehash, e_v1_new, e_v2_new, e);
-
- if (e_v1_new < e_v2_new) {
- e->verts[0] = e_v1_new;
- e->verts[1] = e_v2_new;
- }
- else {
- /* maintain winding info */
- e->verts[0] = e_v2_new;
- e->verts[1] = e_v1_new;
-
- SWAP(unsigned int, e->faces[0], e->faces[1]);
- SWAP(unsigned int, e->faces_other_v[0], e->faces_other_v[1]);
- }
-
- /* update adjacent data */
- {
- unsigned int e_side = 0;
-
- for (e_side = 0; e_side < 2; e_side++) {
- /* 't_other' which we need to swap out is always the same edge-order */
- const unsigned int t_other = (((e->faces_other_v[e_side]) + 2)) % 3;
- unsigned int t_index = e->faces[e_side];
- unsigned int t_index_other = e->faces[!e_side];
- unsigned int *tri = tris[t_index];
-
- struct PolyEdge *e_other;
- unsigned int e_v1 = tri[(t_other ) ];
- unsigned int e_v2 = tri[(t_other + 1) % 3];
-
- e_other = BLI_edgehash_lookup(ehash, e_v1, e_v2);
- if (e_other) {
- BLI_assert(t_index != e_other->faces[0] && t_index != e_other->faces[1]);
- if (t_index_other == e_other->faces[0]) {
- e_other->faces[0] = t_index;
- e_other->f
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list