[Bf-blender-cvs] [a5c3de2] master: Fix T42630: Triangulate returns invalid face-map
Campbell Barton
noreply at git.blender.org
Tue Dec 9 13:16:50 CET 2014
Commit: a5c3de2e49ca348479b1f5915db9f7460422d07a
Author: Campbell Barton
Date: Mon Dec 8 16:57:39 2014 +0100
Branches: master
https://developer.blender.org/rBa5c3de2e49ca348479b1f5915db9f7460422d07a
Fix T42630: Triangulate returns invalid face-map
Triangulate with beautify caused a bug when there were existing edges
could make the bmesh-operator return an invalid face-map.
Now the beauty is calculated on the 2d-tri's resulting from polyfill,
its simpler and faster.
===================================================================
A source/blender/blenlib/BLI_polyfill2d_beautify.h
M source/blender/blenlib/CMakeLists.txt
A 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/tools/bmesh_triangulate.c
===================================================================
diff --git a/source/blender/blenlib/BLI_polyfill2d_beautify.h b/source/blender/blenlib/BLI_polyfill2d_beautify.h
new file mode 100644
index 0000000..c3bb29a
--- /dev/null
+++ b/source/blender/blenlib/BLI_polyfill2d_beautify.h
@@ -0,0 +1,39 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BLI_POLYFILL2D_BEAUTIFY_H__
+#define __BLI_POLYFILL2D_BEAUTIFY_H__
+
+struct EdgeHash;
+struct Heap;
+struct MemArena;
+
+void BLI_polyfill_beautify(
+ const float (*coords)[2],
+ const unsigned int coords_tot,
+ unsigned int (*tris)[3],
+
+ /* structs for reuse */
+ struct MemArena *arena, struct Heap *eheap, struct EdgeHash *eh);
+
+/* avoid realloc's when creating new structures for polyfill ngons */
+#define BLI_POLYFILL_ALLOC_NGON_RESERVE 64
+
+#endif /* __BLI_POLYFILL2D_BEAUTIFY_H__ */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 7dfcc2a..c8f0e1b 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -85,6 +85,7 @@ set(SRC
intern/noise.c
intern/path_util.c
intern/polyfill2d.c
+ intern/polyfill2d_beautify.c
intern/quadric.c
intern/rand.c
intern/rct.c
@@ -161,6 +162,7 @@ set(SRC
BLI_noise.h
BLI_path_util.h
BLI_polyfill2d.h
+ BLI_polyfill2d_beautify.h
BLI_quadric.h
BLI_rand.h
BLI_rect.h
diff --git a/source/blender/blenlib/intern/polyfill2d_beautify.c b/source/blender/blenlib/intern/polyfill2d_beautify.c
new file mode 100644
index 0000000..5bbdbeb
--- /dev/null
+++ b/source/blender/blenlib/intern/polyfill2d_beautify.c
@@ -0,0 +1,498 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/blenlib/intern/polyfill2d_beautify.c
+ * \ingroup bli
+ *
+ * This function is to improve the tessellation resulting from polyfill2d,
+ * creating optimal topology.
+ *
+ * The functionality here matches #BM_mesh_beautify_fill,
+ * but its far simpler to perform this operation in 2d,
+ * on a simple polygon representation where we _know_:
+ *
+ * - The polygon is primitive with no holes with a continuous boundary.
+ * - Tris have consistent winding.
+ * - 2d (saves some hassles projecting face pairs on an axis for every edge-rotation)
+ * also saves us having to store all previous edge-states (see #EdRotState in bmesh_beautify.c)
+ *
+ * \note
+ *
+ * No globals - keep threadsafe.
+ */
+
+#include "BLI_utildefines.h"
+#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];
+};
+
+
+#ifndef NDEBUG
+/**
+ * Only to check for error-cases.
+ */
+static void polyfill_validate_tri(unsigned int (*tris)[3], unsigned int tri_index, EdgeHash *ehash)
+{
+ 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);
+ }
+
+ 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)));
+ }
+ }
+}
+#endif
+
+BLI_INLINE bool is_boundary_edge(unsigned int i_a, unsigned int i_b, const unsigned int coord_last)
+{
+ BLI_assert(i_a < i_b);
+ return ((i_a + 1 == i_b) || UNLIKELY((i_a == 0) && (i_b == coord_last)));
+}
+/**
+ * Assuming we have 2 triangles sharing an edge (2 - 4),
+ * check if the edge running from (1 - 3) gives better results
+ * (negative number, lager == better).
+ */
+static float quad_v2_rotate_beauty_calc(
+ const float v1[2], const float v2[2], const float v3[2], const float v4[2])
+{
+ /* not a loop (only to be able to break out) */
+ do {
+ bool is_zero_a, is_zero_b;
+
+ const float area_2x_234 = cross_tri_v2(v2, v3, v4);
+ const float area_2x_241 = cross_tri_v2(v2, v4, v1);
+
+ const float area_2x_123 = cross_tri_v2(v1, v2, v3);
+ const float area_2x_134 = cross_tri_v2(v1, v3, v4);
+
+ {
+ BLI_assert((ELEM(v1, v2, v3, v4) == false) &&
+ (ELEM(v2, v1, v3, v4) == false) &&
+ (ELEM(v3, v1, v2, v4) == false) &&
+ (ELEM(v4, v1, v2, v3) == false));
+
+ is_zero_a = (fabsf(area_2x_234) <= FLT_EPSILON);
+ is_zero_b = (fabsf(area_2x_241) <= FLT_EPSILON);
+
+ if (is_zero_a && is_zero_b) {
+ break;
+ }
+ }
+
+ if (is_zero_a == false && is_zero_b == false) {
+ /* both tri's are valid, check we make a concave quad */
+ if (!is_quad_convex_v2(v1, v2, v3, v4)) {
+ break;
+ }
+ }
+ else {
+ /* one of the tri's was degenerate, chech we're not rotating
+ * into a different degenerate shape or flipping the face */
+ if ((fabsf(area_2x_123) <= FLT_EPSILON) || (fabsf(area_2x_134) <= FLT_EPSILON)) {
+ /* one of the new rotations is degenerate */
+ break;
+ }
+
+ if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) {
+ /* rotation would cause flipping */
+ break;
+ }
+ }
+
+ {
+ /* testing rule: the area divided by the perimeter,
+ * check if (1-3) beats the existing (2-4) edge rotation */
+ float area_a, area_b;
+ float prim_a, prim_b;
+ float fac_24, fac_13;
+
+ float len_12, len_23, len_34, len_41, len_24, len_13;
+
+#define AREA_FROM_CROSS(f) (fabsf(f) / 2.0f)
+
+ /* edges around the quad */
+ len_12 = len_v2v2(v1, v2);
+ len_23 = len_v2v2(v2, v3);
+ len_34 = len_v2v2(v3, v4);
+ len_41 = len_v2v2(v4, v1);
+ /* edges crossing the quad interior */
+ len_13 = len_v2v2(v1, v3);
+ len_24 = len_v2v2(v2, v4);
+
+ /* edge (2-4), current state */
+ area_a = AREA_FROM_CROSS(area_2x_234);
+ area_b = AREA_FROM_CROSS(area_2x_241);
+ prim_a = len_23 + len_34 + len_24;
+ prim_b = len_24 + len_41 + len_12;
+ fac_24 = (area_a / prim_a) + (area_b / prim_b);
+
+ /* edge (1-3), new state */
+ area_a = AREA_FROM_CROSS(area_2x_123);
+ area_b = AREA_FROM_CROSS(area_2x_134);
+ prim_a = len_12 + len_23 + len_13;
+ prim_b = len_34 + len_41 + len_13;
+ fac_13 = (area_a / prim_a) + (area_b / prim_b);
+
+#undef AREA_FROM_CROSS
+
+ /* negative number if (1-3) is an improved state */
+ return fac_24 - fac_13;
+ }
+ } while (false);
+
+ return FLT_MAX;
+}
+
+static float polyedge_rotate_beauty_calc(
+ const float (*coords)[2],
+ const unsigned int (*tris)[3],
+ const struct PolyEdge *e)
+{
+ 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]];
+
+ return quad_v2_rotate_beauty_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,
+ Heap *eheap, HeapNode **eheap_table)
+{
+ const unsigned int i = (unsigned int)(e - edges);
+
+ if (eheap_table[i]) {
+ BLI_heap_remove(eheap, eheap_table[i]);
+ eheap_table[i] = NULL;
+ }
+
+ {
+ /* recalculate edge */
+ const float cost = polyedge_rotate_beauty_calc(coords, tris, e);
+ if (cost < 0.0f) {
+ eheap_table[i] = BLI_heap_insert(eheap, cost, e);
+ }
+ else {
+ eheap_table[i] = NULL;
+ }
+ }
+}
+
+static void polyedge_beauty_cost_update(
+ const float (*coords)[2],
+ const unsigned int (
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list