[Bf-blender-cvs] [f0f45ee] master: Polyfill2d: replace array with linklist, faster resizing
Campbell Barton
noreply at git.blender.org
Sat Jun 14 00:33:26 CEST 2014
Commit: f0f45eea2e1c83138ba2cf01b363c67f7f6dcb59
Author: Campbell Barton
Date: Sat May 31 22:25:39 2014 +1000
https://developer.blender.org/rBf0f45eea2e1c83138ba2cf01b363c67f7f6dcb59
Polyfill2d: replace array with linklist, faster resizing
approx 4.0x speedup
===================================================================
M source/blender/blenlib/BLI_polyfill2d.h
M source/blender/blenlib/intern/polyfill2d.c
===================================================================
diff --git a/source/blender/blenlib/BLI_polyfill2d.h b/source/blender/blenlib/BLI_polyfill2d.h
index d434e1b..bdc9c10 100644
--- a/source/blender/blenlib/BLI_polyfill2d.h
+++ b/source/blender/blenlib/BLI_polyfill2d.h
@@ -23,14 +23,6 @@
struct MemArena;
-void BLI_polyfill_calc_ex(
- const float (*coords)[2],
- const unsigned int count,
- unsigned int (*r_tris)[3],
-
- /* avoid allocating each time */
- unsigned int *r_indices, signed char *r_coords_sign);
-
void BLI_polyfill_calc_arena(
const float (*coords)[2],
const unsigned int coords_tot,
diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c
index fbe3c31..fe96023 100644
--- a/source/blender/blenlib/intern/polyfill2d.c
+++ b/source/blender/blenlib/intern/polyfill2d.c
@@ -69,11 +69,10 @@ enum {
};
typedef struct PolyFill {
- unsigned int *indices; /* vertex aligned */
+ struct PolyIndex *indices; /* vertex aligned */
const float (*coords)[2];
unsigned int coords_tot;
- eSign *coords_sign;
#ifdef USE_CONVEX_SKIP
unsigned int coords_tot_concave;
#endif
@@ -84,19 +83,24 @@ typedef struct PolyFill {
} PolyFill;
-/* based on libgdx 2013-11-28, apache 2.0 licensed */
+/* circular linklist */
+typedef struct PolyIndex {
+ struct PolyIndex *next, *prev;
+ unsigned int index;
+ eSign sign;
+} PolyIndex;
+
-static eSign pf_coord_sign_calc(PolyFill *pf, unsigned int index);
-static unsigned int pf_index_prev(const PolyFill *pf, const unsigned int index);
-static unsigned int pf_index_next(const PolyFill *pf, unsigned index);
+/* based on libgdx 2013-11-28, apache 2.0 licensed */
+static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi);
#ifdef USE_CLIP_EVEN
-static unsigned int pf_ear_tip_find(PolyFill *pf, const unsigned int index_offset);
+static PolyIndex *pf_ear_tip_find(PolyFill *pf, PolyIndex *pi_ear_init);
#else
-static unsigned int pf_ear_tip_find(PolyFill *pf);
+static PolyIndex *pf_ear_tip_find(PolyFill *pf);
#endif
-static bool pf_ear_tip_check(PolyFill *pf, const unsigned int index_ear_tip);
-static void pf_ear_tip_cut(PolyFill *pf, unsigned int index_ear_tip);
+static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip);
+static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip);
BLI_INLINE eSign signum_i(float a)
@@ -133,118 +137,126 @@ static unsigned int *pf_tri_add(PolyFill *pf)
return pf->tris[pf->tris_tot++];
}
-static void pf_coord_remove(PolyFill *pf, const unsigned int index)
+static void pf_coord_remove(PolyFill *pf, PolyIndex *pi)
{
- ARRAY_DELETE(pf->indices, index, 1, pf->coords_tot);
- ARRAY_DELETE(pf->coords_sign, index, 1, pf->coords_tot);
+ pi->next->prev = pi->prev;
+ pi->prev->next = pi->next;
+
+ if (UNLIKELY(pf->indices == pi)) {
+ pf->indices = pi->next;
+ }
+#ifdef DEBUG
+ pi->index = (unsigned int)-1;
+ pi->next = pi->prev = NULL;
+#endif
+
pf->coords_tot -= 1;
}
static void pf_triangulate(PolyFill *pf)
{
/* localize */
- eSign *coords_sign = pf->coords_sign;
+ PolyIndex *pi_ear;
- unsigned int index_ear_tip = 0;
+ PolyIndex *pi_ear_init = pf->indices;
while (pf->coords_tot > 3) {
- unsigned int i_prev, i_next;
-
-#ifdef USE_CONVEX_SKIP
+ PolyIndex *pi_prev, *pi_next;
eSign sign_orig_prev, sign_orig_next;
-#endif
-
#ifdef USE_CLIP_EVEN
- index_ear_tip = pf_ear_tip_find(pf, index_ear_tip);
+ pi_ear = pf_ear_tip_find(pf, pi_ear_init);
#else
- index_ear_tip = pf_ear_tip_find(pf);
+ pi_ear = pf_ear_tip_find(pf);
#endif
#ifdef USE_CONVEX_SKIP
- if (coords_sign[index_ear_tip] != CONVEX) {
+ if (pi_ear->sign != CONVEX) {
pf->coords_tot_concave -= 1;
}
#endif
- pf_ear_tip_cut(pf, index_ear_tip);
+ pi_prev = pi_ear->prev;
+ pi_next = pi_ear->next;
+
+ pf_ear_tip_cut(pf, pi_ear);
/* The type of the two vertices adjacent to the clipped vertex may have changed. */
- i_prev = pf_index_prev(pf, index_ear_tip);
- i_next = (index_ear_tip == pf->coords_tot) ? 0 : index_ear_tip;
+ sign_orig_prev = pi_prev->sign;
+ sign_orig_next = pi_next->sign;
+ /* check if any verts became convex the (else if)
+ * case is highly unlikely but may happen with degenerate polygons */
+ if (sign_orig_prev != CONVEX) {
+ pf_coord_sign_calc(pf, pi_prev);
#ifdef USE_CONVEX_SKIP
- sign_orig_prev = coords_sign[i_prev];
- sign_orig_next = coords_sign[i_next];
+ if (pi_prev->sign == CONVEX) {
+ pf->coords_tot_concave -= 1;
+ }
#endif
-
- coords_sign[i_prev] = pf_coord_sign_calc(pf, i_prev);
- coords_sign[i_next] = pf_coord_sign_calc(pf, i_next);
-
+ }
+ if (sign_orig_next != CONVEX) {
+ pf_coord_sign_calc(pf, pi_next);
#ifdef USE_CONVEX_SKIP
- /* check if any verts became convex the (else if)
- * case is highly unlikely but may happen with degenerate polygons */
- if ((sign_orig_prev != CONVEX) && (coords_sign[i_prev] == CONVEX)) pf->coords_tot_concave -= 1;
- else if (UNLIKELY((sign_orig_prev == CONVEX) && (coords_sign[i_prev] != CONVEX))) pf->coords_tot_concave += 1;
-
- if ((sign_orig_next != CONVEX) && (coords_sign[i_next] == CONVEX)) pf->coords_tot_concave -= 1;
- else if (UNLIKELY((sign_orig_next == CONVEX) && (coords_sign[i_next] != CONVEX))) pf->coords_tot_concave += 1;
+ if (pi_next->sign == CONVEX) {
+ pf->coords_tot_concave -= 1;
+ }
#endif
+ }
#ifdef USE_CLIP_EVEN
- index_ear_tip = i_prev;
+ pi_ear_init = pi_next->next;
#endif
}
if (pf->coords_tot == 3) {
unsigned int *tri = pf_tri_add(pf);
- tri[0] = pf->indices[0];
- tri[1] = pf->indices[1];
- tri[2] = pf->indices[2];
+ pi_ear = pf->indices;
+ tri[0] = pi_ear->index; pi_ear = pi_ear->next;
+ tri[1] = pi_ear->index; pi_ear = pi_ear->next;
+ tri[2] = pi_ear->index;
}
}
/**
* \return CONCAVE, TANGENTIAL or CONVEX
*/
-static eSign pf_coord_sign_calc(PolyFill *pf, unsigned int index)
+static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi)
{
/* localize */
- unsigned int *indices = pf->indices;
const float (*coords)[2] = pf->coords;
- return span_tri_v2_sign(
- coords[indices[pf_index_prev(pf, index)]],
- coords[indices[index]],
- coords[indices[pf_index_next(pf, index)]]);
+ pi->sign = span_tri_v2_sign(
+ coords[pi->prev->index],
+ coords[pi->index],
+ coords[pi->next->index]);
}
#ifdef USE_CLIP_EVEN
-static unsigned int pf_ear_tip_find(PolyFill *pf, const unsigned int index_offset)
+static PolyIndex *pf_ear_tip_find(PolyFill *pf, PolyIndex *pi_ear_init)
#else
-static unsigned int pf_ear_tip_find(PolyFill *pf)
+static PolyIndex *pf_ear_tip_find(PolyFill *pf)
#endif
{
/* localize */
- const eSign *coords_sign = pf->coords_sign;
const unsigned int coords_tot = pf->coords_tot;
+ PolyIndex *pi_ear;
unsigned int i;
+#ifdef USE_CLIP_EVEN
+ pi_ear = pi_ear_init;
+#else
+ pi_ear = pf->indices;
+#endif
i = coords_tot;
while (i--) {
-#ifdef USE_CLIP_EVEN
- unsigned int j = (i + index_offset) % coords_tot;
- if (pf_ear_tip_check(pf, j)) {
- return j;
+ if (pf_ear_tip_check(pf, pi_ear)) {
+ return pi_ear;
}
-#else
- if (pf_ear_tip_check(pf, i)) {
- return i;
- }
-#endif
+ pi_ear = pi_ear->next;
}
/* Desperate mode: if no vertex is an ear tip, we are dealing with a degenerate polygon (e.g. nearly collinear).
@@ -256,32 +268,29 @@ static unsigned int pf_ear_tip_find(PolyFill *pf)
* Return a convex or tangential vertex if one exists.
*/
- i = coords_tot;
- while (i--) {
#ifdef USE_CLIP_EVEN
- unsigned int j = (i + index_offset) % coords_tot;
- if (coords_sign[j] != CONCAVE) {
- return j;
- }
+ pi_ear = pi_ear_init;
#else
- if (coords_sign[i] != CONCAVE) {
- return i;
- }
+ pi_ear = pf->indices;
#endif
+
+ i = coords_tot;
+ while (i--) {
+ if (pi_ear->sign != CONCAVE) {
+ return pi_ear;
+ }
+ pi_ear = pi_ear->next;
}
/* If all vertices are concave, just return the last one. */
- return coords_tot - 1;
+ return pi_ear;
}
-static bool pf_ear_tip_check(PolyFill *pf, const unsigned int index_ear_tip)
+static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip)
{
/* localize */
- const unsigned int *indices = pf->indices;
+ PolyIndex *pi_curr;
const float (*coords)[2] = pf->coords;
- const eSign *coords_sign = pf->coords_sign;
-
- unsigned int i_prev, i_curr, i_next;
const float *v1, *v2, *v3;
@@ -298,7 +307,7 @@ static bool pf_ear_tip_check(PolyFill *pf, const unsigned int index_ear_tip)
unsigned int coords_tot_concave_test = 0;
unsigned int i = pf->coords_tot;
while (i--) {
- if (coords_sign[i] != CONVEX) {
+ if (pf->indices[i].sign != CONVEX) {
coords_tot_concave_test += 1;
}
}
@@ -312,25 +321,22 @@ static bool pf_ear_tip_check(PolyFill *pf, const unsigned int index_ear_tip)
}
#endif
- if (UNLIKELY(coords_sign[index_ear_tip] == CONCAVE)) {
+ if (UNLIKELY(pi_ear_tip->sign == CONCAVE)) {
return false;
}
- i_prev = pf_index_prev(pf, index_ear_tip);
- i_next = pf_index_next(pf, index_ear_tip);
-
- v1 = coords[indices[i_prev]];
- v2 = coords[indices[index_ear_tip]];
- v3 = coords[indices[i_next]];
+ v1 = coords[pi_ear_tip->prev->index];
+ v2 = coords[pi_ear_tip->index];
+ v3 = coords[pi_ear_tip->next->index];
/* Check if any point is inside the triangle formed by previous, current and next vertices.
* Only consider vertices that are not part of this triangle, or else we'll always find one inside. */
- for (i_curr = pf_index_next(pf, i_next); i_curr != i_prev; i_curr = pf_index_next(pf, i_curr)) {
+ for (pi_curr = pi_ear_tip->next->next; pi_curr != pi_ear_tip->prev; pi_curr = pi_curr->next) {
/* Concave vertices can obviously be inside the candidate ear, but so can tangential vertices
* if they coincide with one of the triangle's vertices. */
- if (coords_sign[i_curr] != CONVEX) {
- const float *v = coords[indices[i_curr]];
+ if (pi_curr->sign != CONVEX) {
+ const float *v = coords[pi_curr->index];
/* Because the polygon has clockwise winding order,
* the area sign will be positive if the point is strictly inside.
* It will be 0 on the edge, which we want to include as well. */
@@ -355,25 +361
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list