[Bf-blender-cvs] [e737fe70617] bevelv2: Fix bugs exposed by using non-zero slope in all tests.
Howard Trickey
noreply at git.blender.org
Wed Dec 7 19:46:49 CET 2022
Commit: e737fe706177d56f2124a66ebb52740ed7904606
Author: Howard Trickey
Date: Wed Dec 7 13:43:57 2022 -0500
Branches: bevelv2
https://developer.blender.org/rBe737fe706177d56f2124a66ebb52740ed7904606
Fix bugs exposed by using non-zero slope in all tests.
Using a non-zero slope in all tests causes some normal calculations
at the end, which in turn exposed a number of places where the trimesh
invariants were not properly maintained. This fixes all the problems
exposed by the current tests (there were several, mostly related
to how to reassign the representative edge for a vertex when
triangles and edges are collapsed.
===================================================================
M source/blender/blenlib/intern/mesh_inset.cc
M source/blender/blenlib/tests/BLI_mesh_inset_test.cc
===================================================================
diff --git a/source/blender/blenlib/intern/mesh_inset.cc b/source/blender/blenlib/intern/mesh_inset.cc
index 3d04a21a1d4..5ea16a49a73 100644
--- a/source/blender/blenlib/intern/mesh_inset.cc
+++ b/source/blender/blenlib/intern/mesh_inset.cc
@@ -164,7 +164,8 @@ class Triangle {
TSPOKE0 = 1 << 3,
TSPOKE1 = 1 << 4,
TSPOKE2 = 1 << 5,
- /* TORIGi means the ith edge is an edge that was in the incoming mesh (before triangulation). */
+ /* TORIGi means the ith edge is an edge that was in the incoming mesh (before triangulation).
+ */
TORIG0 = 1 << 6,
TORIG1 = 1 << 7,
TORIG2 = 1 << 8,
@@ -322,7 +323,7 @@ class Triangle {
void Triangle::calculate_normal()
{
- BLI_assert(!this->is_ghost());
+ BLI_assert(!this->is_ghost() && !this->is_deleted());
float3 v0v1 = vert_[1]->co - vert_[0]->co;
float3 v0v2 = vert_[2]->co - vert_[0]->co;
normal_ = math::normalize(math::cross_high_precision(v0v1, v0v2));
@@ -332,7 +333,7 @@ void Triangle::calculate_normal()
/* For use when we may not have calculated tri->normal_ (mostly for debugging). */
static float3 triangle_normal(const Triangle *tri)
{
- if (tri->is_ghost()) {
+ if (tri->is_ghost() || tri->is_deleted()) {
return float3(0.0f, 0.0f, 0.0f);
}
BLI_assert(!tri->is_ghost());
@@ -443,12 +444,14 @@ static Vector<Triangle *> triangles_of_vert(const Vert *v)
*/
static float3 vertex_normal(const Vert *vert)
{
+ BLI_assert(!vert->is_deleted());
float3 ans{0.0f, 0.0f, 0.0f};
Edge e0 = vert->e;
BLI_assert(!e0.is_null());
Edge ecur = e0;
do {
Triangle *tri = ecur.tri();
+ BLI_assert(!tri->is_deleted());
if (!tri->is_ghost()) {
Edge eprev = ecur.triangle_pred();
float3 din = math::normalize(vert->co - v_src(eprev)->co);
@@ -548,6 +551,14 @@ class TriangleMesh {
*/
Vert *collapse_triangle(Triangle *tri, int pos);
+ /** Delete \a tri, which should have a repeated vertex and therefore is degenerate.
+ * This means merging the two non-degenerate sides, which means properly setting
+ * the neighbor relations across the new single edge.
+ * Also, if any vertex was using an edge in \a tri for its representative, then a
+ * new representaative must be found.
+ */
+ Edge delete_degenerate_triangle(Triangle *tri);
+
Span<Vert *> all_verts() const
{
return verts_.as_span();
@@ -561,6 +572,8 @@ class TriangleMesh {
void calculate_all_tri_normals();
+ void validate();
+
friend std::ostream &operator<<(std::ostream &os, const TriangleMesh &trimesh);
};
@@ -627,6 +640,9 @@ std::ostream &operator<<(std::ostream &os, const Triangle &tri)
os << " o" << i;
}
}
+ if (tri.is_deleted()) {
+ os << " deleted";
+ }
return os;
}
@@ -798,7 +814,7 @@ static void trimesh_draw(const std::string &label, const TriangleMesh &trimesh)
void TriangleMesh::calculate_all_tri_normals()
{
for (Triangle *tri : triangles_) {
- if (!tri->is_ghost()) {
+ if (!tri->is_ghost() && !tri->is_deleted()) {
tri->calculate_normal();
}
}
@@ -913,6 +929,62 @@ Vert *TriangleMesh::split_vert(Vert *v, Edge e1, Edge e2)
return v_new;
}
+/** Find and set a `v->e` that is not part of Triangle `tri`. */
+static void set_rep_excluding(Vert *v, const Triangle *tri)
+{
+ Edge e0 = v->e;
+ Edge ecur = e0;
+ do {
+ /* It is possible that, triangles around v may be deleted as we are in the process of deleting
+ * v. */
+ if (ecur.tri() != tri && !ecur.tri()->is_deleted()) {
+ v->e = ecur;
+ return;
+ }
+ ecur = rot_ccw(ecur);
+ } while (ecur != e0);
+ BLI_assert_unreachable();
+}
+
+/** Delete \a tri, which should have a repeated vertex and therefore is degenerate.
+ * This means merging the two non-degenerate sides, which means properly setting
+ * the neighbor relations across the new single edge.
+ * Also, if any vertex was using an edge in \a tri for its representative, then a
+ * new representaative must be found.
+ * Return one of the edges that represents the merged non-degenerate edges.
+ */
+Edge TriangleMesh::delete_degenerate_triangle(Triangle *tri)
+{
+ /* Find positions of non-degenerate edges. */
+ Vector<int> good_edges;
+ for (int i = 0; i < 3; ++i) {
+ if (tri->vert(i) != tri->vert(succ_index(i))) {
+ good_edges.append(i);
+ }
+ }
+ BLI_assert(good_edges.size() == 2);
+ const int p0 = good_edges[0];
+ const int p1 = good_edges[1];
+ Edge en_0 = tri->neighbor(p0);
+ Edge en_1 = tri->neighbor(p1);
+ if (tri->is_spoke(p0) || tri->is_spoke(p1)) {
+ en_0.tri()->mark_spoke(en_0.tri_edge_index());
+ en_1.tri()->mark_spoke(en_1.tri_edge_index());
+ }
+ BLI_assert(en_0.tri() != en_1.tri());
+ set_mutual_neighbors(en_0.tri(), en_0.tri_edge_index(), en_1.tri(), en_1.tri_edge_index());
+ Vert *v0 = tri->vert(p0);
+ Vert *v1 = tri->vert(p1);
+ if (v0->e.tri() == tri) {
+ set_rep_excluding(v0, tri);
+ }
+ if (v1->e.tri() == tri) {
+ set_rep_excluding(v1, tri);
+ }
+ tri->mark_deleted();
+ return en_0;
+}
+
/* Collapse the edge \a e to the single vertex at its source end.
* This will delete the trriangle that \a e is part of, and also the vertex
* at the destination end of \a e, and will fix the affected neighbor relations.
@@ -963,71 +1035,85 @@ Vert *TriangleMesh::split_vert(Vert *v, Edge e1, Edge e2)
* -/ | \-
* --------------|-------------
*
+ * It is even possible that t0 == t1 or t0 == t2 but not both. If t0 == t1, we the result is:
+ *
+ * - -
+ * -- \- -/ -\
+ * -/ \- -/ -\
+ * -/ t2a \ / t0b -
+ * ------------ |------------
+ * \ | /|
+ * | -\ t2 | t0a /-
+ * | -\ | /-
+ * | -\ e'| /-
+ * | t2b -\ | /-
+ * | -\v0/-
+ * |-------------
+ *
+ * and if t0 == t2 it is like this:
+ *
+ * -
+ * -/ -\
+ * -/ -\
+ * / t1b -
+ * ------------ |------------
+ * \ | /|
+ * -\ t2a | t1 /- |
+ * -\ | /- |
+ * -\ e'| /- |
+ * -\ | /- t1a |
+ * -\v0/- |
+ * --------------
+ * --/ | \--
+ * -/ | \-
+ * --/ t0a | t0b \--
+ * -/ | \-
+ * --------------|-------------
+ *
*/
Edge TriangleMesh::collapse_edge(Edge e)
{
- Triangle *t = e.tri();
- int epos = e.tri_edge_index();
+ Triangle *t_a = e.tri();
Vert *v0 = v_src(e);
Vert *v1 = v_dst(e);
- Edge e_t0 = neighbor_edge(e);
- Edge e_t1 = neighbor_edge(Edge(t, succ_index(epos)));
- Edge e_t2 = neighbor_edge(Edge(t, pred_index(epos)));
- Triangle *t0 = e_t0.tri();
- Triangle *t2 = e_t2.tri();
- Edge e_t0a = neighbor_edge(e_t0.triangle_succ());
- Edge e_t0b = neighbor_edge(e_t0.triangle_pred());
- Triangle *t0a = e_t0a.tri();
- bool t1t2_spoke = e_t1.tri()->is_spoke(e_t1.tri_edge_index()) ||
- e_t2.tri()->is_spoke(e_t2.tri_edge_index());
- bool t0at0b_spoke = e_t0a.tri()->is_spoke(e_t0a.tri_edge_index()) ||
- e_t0b.tri()->is_spoke(e_t0b.tri_edge_index());
-
- /* If v0 has e as representative edge, it will have to get a new one.
- * Similarly if v2 has an edge in t as representative edge, it will have to get a new one.
- * Similarly if the third vertex of t0 (v3) has a representative edge in t0, it needs a new one.
- */
- Vert *v2 = v_src(e.triangle_succ().triangle_succ());
- Vert *v3 = v_src(e_t0.triangle_pred());
- if (v0->e.tri() == t) {
- v0->e = e_t2;
- BLI_assert(v_src(v0->e) == v0);
- }
- if (v2->e.tri() == t) {
- v2->e = rot_ccw(e_t1);
- BLI_assert(v_src(v2->e) == v2);
- }
- if (v3->e.tri() == t0) {
- v3->e = neighbor_edge(e_t0.triangle_succ());
- BLI_assert(v_src(v3->e) == v3);
- }
- /* Change v1 to v0 in affected triangles.
- * If any triangle has v1 as a representative vertex, it needs a new one.
- */
- Edge e_fix = e_t0b;
- Edge e_fix_done = e.triangle_succ();
+ /* Gather triangles around `v1` that will get `v1` changed to `v0`. */
+ Vector<Triangle *> v1_tris;
+ Edge ecur = v1->e;
do {
- BLI_assert(v_src(e_fix) == v1);
- Triangle *tri_fix = e_fix.tri();
- tri_fix->set_vert(e_fix.tri_edge_index(), v0);
- tri_fix->calculate_normal();
- Edge e_fix_next = rot_ccw(e_fix);
- e_fix = e_fix_next;
- } while (e_fix != e_fix_done);
-
- /* Fix up neighbor relations, spokes, and delete things. */
- set_mutual_neighbors(t0a, e_t0a.tri_edge_index(), e_t0b);
- set_mutual_neighbors(t2, e_t2.tri_edge_index(), e_t1);
- if (t1t2_spoke) {
- e_t1.tri()->mark_spoke(e_t1.tri_edge_index());
- }
- if (t0at0b_spoke) {
- e_t0a.tri()->mark_spoke(e_t0a.tri_edge_index());
+ Triangle *t = ecur.tri();
+ BLI_assert(!t->is_ghost() && !t->is_deleted());
+ v1_tris.append(t);
+ ecur = rot_ccw(ecur);
+ } while (ecur != v1->e);
+ /* For each triangle in `v1_tris`, replace `v1` by `v0` then eliminate if now there are two
+ * `v0`s. */
+ Edge e_ans = null_edge;
+ for (Triangle *t : v1_tris) {
+ int v0_count = 0;
+ for (int i = 0; i < 3; ++i) {
+ Vert *v = t->vert(i);
+ if (v == v1) {
+ t->set_vert(i, v0);
+ v0_count++;
+ }
+ else if (v == v0) {
+ v0_count++;
+ }
+ }
+ if (v0_count > 1) {
+ Edge enew = delete_degenerate_triangle(t);
+ if (t == t_a) {
+ e_ans = enew;
+ }
+ }
}
v1->mark_deleted();
- t->mark_deleted();
- t0->mark_deleted();
- return e_t2;
+ BLI_assert(e_ans != null_edge);
+ if (v_src(e_ans) != v0) {
+ e_ans = e_ans.tri()->neighbor(e_ans.tri_edge_index());
+ BLI_assert(v_src(e_ans) == v0);
+ }
+ return e_ans;
}
/** Collapse the triangle \a tri to a single vertex (th
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list