[Bf-blender-cvs] [3b2bc5d1463] bevelv2: Added a mesh_inset Blenlib function.
Howard Trickey
noreply at git.blender.org
Thu Sep 8 16:09:05 CEST 2022
Commit: 3b2bc5d1463a10c445fb74e9a7888ef4d59e368c
Author: Howard Trickey
Date: Thu Sep 8 10:04:20 2022 -0400
Branches: bevelv2
https://developer.blender.org/rB3b2bc5d1463a10c445fb74e9a7888ef4d59e368c
Added a mesh_inset Blenlib function.
Based on python code from Henrik Dick, this libray function
calculates a Straight Skeleton, and hence, deals properly
with cases where the advancing inset geometry would overlap
or pass through opposite edges. It still needs work but the
basic tests pass.
This function will be used for edge and face bevels but is
not yet hooked up for that.
===================================================================
A source/blender/blenlib/BLI_mesh_inset.hh
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/mesh_inset.cc
A source/blender/blenlib/tests/BLI_mesh_inset_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_mesh_inset.hh b/source/blender/blenlib/BLI_mesh_inset.hh
new file mode 100644
index 00000000000..cd7dfcb57df
--- /dev/null
+++ b/source/blender/blenlib/BLI_mesh_inset.hh
@@ -0,0 +1,48 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ *
+ * This header file contains a C++ interface to a 3D mesh inset algorithm
+ * which is based on a 2D Straight Skeleton construction.
+ */
+
+#include "BLI_array.hh"
+#include "BLI_math_vec_types.hh"
+#include "BLI_span.hh"
+#include "BLI_vector.hh"
+
+
+namespace blender::meshinset {
+
+class MeshInset_Input {
+public:
+ /** The vertices. Can be a superset of the needed vertices. */
+ Span<float3> vert;
+ /** The faces, each a CCW ordering of vertex indices. */
+ Span<Vector<int>> face;
+ /** The contours to inset; ints are vert indices; contour is on left side of implied edges. */
+ Span<Vector<int>> contour;
+ float inset_amount;
+ bool need_ids;
+};
+
+class MeshInset_Result {
+public:
+ /** The output vertices. A subset (perhaps) of input vertices, plus some new ones. */
+ Array<float3> vert;
+ /** The output faces, each a CCW ordering of the output vertices. */
+ Array<Vector<int>> face;
+ /** The output contours -- where the input contours ended up. */
+ Array<Vector<int>> contour;
+ /** Maps output vertex indices to input vertex indices, -1 if there is none. */
+ Array<int> orig_vert;
+ /** Maps output faces tot input faces that they were part of. */
+ Array<int> orig_face;
+};
+
+MeshInset_Result mesh_inset_calc(const MeshInset_Input &input);
+
+} // namespace blender::meshinset
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index d87c60e6099..fea46237997 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -107,6 +107,7 @@ set(SRC
intern/math_vector_inline.c
intern/memory_utils.c
intern/mesh_boolean.cc
+ intern/mesh_inset.cc
intern/mesh_intersect.cc
intern/noise.c
intern/noise.cc
@@ -275,6 +276,7 @@ set(SRC
BLI_memory_utils.hh
BLI_mempool.h
BLI_mesh_boolean.hh
+ BLI_mesh_inset.hh
BLI_mesh_intersect.hh
BLI_mmap.h
BLI_multi_value_map.hh
@@ -473,6 +475,7 @@ if(WITH_GTESTS)
tests/BLI_memiter_test.cc
tests/BLI_memory_utils_test.cc
tests/BLI_mesh_boolean_test.cc
+ tests/BLI_mesh_inset_test.cc
tests/BLI_mesh_intersect_test.cc
tests/BLI_multi_value_map_test.cc
tests/BLI_path_util_test.cc
diff --git a/source/blender/blenlib/intern/mesh_inset.cc b/source/blender/blenlib/intern/mesh_inset.cc
new file mode 100644
index 00000000000..69bddbb8035
--- /dev/null
+++ b/source/blender/blenlib/intern/mesh_inset.cc
@@ -0,0 +1,3058 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+/** \file
+ * \ingroup bli
+ */
+
+#include <fstream>
+#include <iostream>
+#include <limits>
+#include <queue>
+
+#include "BLI_array.hh"
+#include "BLI_heap.h"
+#include "BLI_map.hh"
+#include "BLI_math_vector.h"
+#include "BLI_math_vector.hh"
+#include "BLI_memarena.h"
+#include "BLI_mesh_inset.hh"
+#include "BLI_polyfill_2d.h"
+#include "BLI_polyfill_2d_beautify.h"
+#include "BLI_set.hh"
+#include "BLI_span.hh"
+#include "BLI_vector.hh"
+
+#include "BLI_mesh_inset.hh"
+
+namespace blender::meshinset {
+
+class Vert;
+class Edge;
+class Triangle;
+
+/** The predecessor index to \a i in a triangle. */
+static inline int pred_index(const int i)
+{
+ return (i + 2) % 3;
+}
+
+/** The successor index to \a i in a triangle. */
+static inline int succ_index(const int i)
+{
+ return (i + 1) % 3;
+}
+
+/** The ith edge of triangle tri. Not shared with the adjacent triangle. */
+class Edge {
+ /* Assume Triangles are allocated on at least 4 byte boundaries.
+ * Then, use the lower two bits of the pointer as the index (0,1,2)
+ * saying which edge of the triangle we refer to.
+ */
+
+ /** A pointer with lower two bits used for index. */
+ Triangle *tri_and_index_;
+
+ public:
+ Edge() : tri_and_index_(nullptr)
+ {
+ }
+ Edge(const Triangle *tri, int tri_edge_index)
+ {
+ static_assert(sizeof(Triangle *) % 4 == 0);
+ uintptr_t tri_x = reinterpret_cast<uintptr_t>(tri);
+ BLI_assert(0 <= tri_edge_index && tri_edge_index < 3);
+ tri_x |= tri_edge_index;
+ tri_and_index_ = reinterpret_cast<Triangle *>(tri_x);
+ }
+
+ /** The triangle containing this edge. */
+ Triangle *tri() const
+ {
+ uintptr_t tri_x = reinterpret_cast<uintptr_t>(tri_and_index_);
+ tri_x &= ~3;
+ return reinterpret_cast<Triangle *>(tri_x);
+ }
+
+ /** Which edge of the triangle is it? 0, 1, or 2? */
+ int tri_edge_index() const
+ {
+ uintptr_t tri_x = reinterpret_cast<uintptr_t>(tri_and_index_);
+ return tri_x & 3;
+ }
+
+ bool is_null() const
+ {
+ return tri_and_index_ == nullptr;
+ }
+
+ /** Return the edge next around this one's triangle. */
+ Edge triangle_succ() const
+ {
+ return Edge(this->tri(), succ_index(this->tri_edge_index()));
+ }
+
+ /** Return the edge before this in this one's triangle. */
+ Edge triangle_pred() const
+ {
+ return Edge(this->tri(), pred_index(this->tri_edge_index()));
+ }
+
+ uint64_t hash() const
+ {
+ /* Like the default hash for pointers but without the right-shift of 4 bits. */
+ uintptr_t ptr = reinterpret_cast<uintptr_t>(this->tri_and_index_);
+ uint64_t hash = static_cast<uint64_t>(ptr);
+ return hash;
+ }
+
+ friend std::ostream &operator<<(std::ostream &os, const Edge e);
+
+ protected:
+ friend bool operator==(const Edge &a, const Edge &b)
+ {
+ return a.tri_and_index_ == b.tri_and_index_;
+ }
+ friend bool operator!=(const Edge &a, const Edge &b)
+ {
+ return a.tri_and_index_ != b.tri_and_index_;
+ }
+};
+
+static Edge null_edge = Edge();
+
+enum VertFlags { VDELETED = 1 };
+
+class Vert {
+ public:
+ float3 co;
+ /** Any Edge leaving this vertesx. */
+ Edge e;
+ int id{0};
+ uint8_t flags{0};
+
+ Vert(const float3 co, const Edge e) : co(co), e(e)
+ {
+ }
+ Vert(const float3 co) : co(co), e(Edge(nullptr, 0))
+ {
+ }
+
+ void mark_deleted()
+ {
+ this->flags |= VDELETED;
+ }
+
+ bool is_deleted() const
+ {
+ return (this->flags & VDELETED) != 0;
+ }
+
+ friend std::ostream &operator<<(std::ostream &os, const Vert &v);
+ friend std::ostream &operator<<(std::ostream &os, const Vert *v);
+};
+
+class Triangle {
+
+ enum TriangleFlags {
+ TDELETED = 1,
+ TNORMAL_VALID = 1 << 1,
+ TREGION = 1 << 2,
+ TSPOKE0 = 1 << 3,
+ TSPOKE1 = 1 << 4,
+ TSPOKE2 = 1 << 5,
+ };
+ Edge neighbor_[3];
+ Vert *vert_[3];
+ float3 normal_;
+ int id_{0};
+ uint8_t flags_{0};
+
+ public:
+ Triangle(Vert *v0, Vert *v1, Vert *v2)
+ {
+ neighbor_[0] = Edge();
+ neighbor_[1] = Edge();
+ neighbor_[2] = Edge();
+ vert_[0] = v0;
+ vert_[1] = v1;
+ vert_[2] = v2;
+ if (v0 != nullptr && v0->e.is_null()) {
+ v0->e = Edge(this, 0);
+ }
+ if (v1 != nullptr && v1->e.is_null()) {
+ v1->e = Edge(this, 1);
+ }
+
+ if (v2 != nullptr && v2->e.is_null()) {
+ v2->e = Edge(this, 2);
+ }
+ };
+
+ /** This triangle's ith vertex. */
+ Vert *vert(int i) const
+ {
+ return vert_[i];
+ }
+
+ /** The neighbor edge corresponding to this triangle's ith edge. */
+ Edge neighbor(int i) const
+ {
+ return neighbor_[i];
+ }
+
+ /** This Triangle's ith edge. */
+ Edge edge(int i) const
+ {
+ return Edge(this, i);
+ }
+
+ /** An id for this triangle. Should have been set using set_id(). */
+ int id() const
+ {
+ return id_;
+ }
+
+ /** Set the id of this triangle (should be done just once). */
+ void set_id(int id)
+ {
+ id_ = id;
+ }
+
+ /** Set the ith vertex of this triangle to \a v .*/
+ void set_vert(int i, Vert *v)
+ {
+ vert_[i] = v;
+ flags_ &= ~TNORMAL_VALID;
+ }
+
+ /** A "ghost" triangle has a nullptr for vert[1]. */
+ bool is_ghost() const
+ {
+ return vert_[1] == nullptr;
+ }
+
+ /** Return the triangle normal. Assumes calculate_normal() has been called. */
+ float3 normal() const
+ {
+ BLI_assert(flags_ & TNORMAL_VALID);
+ return normal_;
+ }
+
+ void calculate_normal();
+
+ void mark_deleted()
+ {
+ flags_ |= TDELETED;
+ }
+
+ bool is_deleted() const
+ {
+ return (flags_ & TDELETED) != 0;
+ }
+
+ /* Our algorithm cares which triangles are "in the region" or not. */
+ void mark_in_region()
+ {
+ flags_ |= TREGION;
+ }
+
+ void clear_in_region()
+ {
+ flags_ &= ~TREGION;
+ }
+
+ bool in_region() const
+ {
+ return (flags_ & TREGION) != 0;
+ }
+
+ /* Our algorithm cares which edges are "spokes".
+ * As a convenience, always mark the spoke of the neibhgor edge too. */
+ void mark_spoke(int pos)
+ {
+ flags_ |= (TSPOKE0 << pos);
+ Edge en = neighbor_[pos];
+ Triangle *tn = en.tri();
+ tn->flags_ |= (TSPOKE0 << en.tri_edge_index());
+ }
+
+ void clear_spoke(int pos)
+ {
+ flags_ &= ~(TSPOKE0 << pos);
+ Edge en = neighbor_[pos];
+ Triangle *tn = en.tri();
+ tn->flags_ &= ~(TSPOKE0 << en.tri_edge_index());
+ }
+
+ bool is_spoke(int pos) const
+ {
+ return (flags_ & (TSPOKE0 << pos)) != 0;
+ }
+
+ friend void set_mutual_neighbors(Triangle *t1, int pos1, Triangle *t2, int pos2);
+ friend void set_mutual_neighbors(Triangle *t1, int pos1, Edge e2);
+
+ friend std::ostream &operator<<(std::ostream &os, const Triangle &tri);
+};
+
+void Triangle::calculate_normal()
+{
+ BLI_assert(!this->is_ghost());
+ 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));
+ flags_ |= TNORMAL_VALID;
+}
+
+/* For use when we may not have calculated tri->normal_ (mostly for debugging). */
+static float3 triangle_normal(const Triangle *tri)
+{
+ if (tri->is_ghost()) {
+ return float3(0.0f, 0.0f, 0.0f);
+ }
+ BLI_assert(!tri->is_ghost());
+ float3 v0v1 = tri->vert(1)->co - tri->vert(0)->co;
+ float3 v0v2 = tri->vert(2)->co - tri->vert(0)->co;
+ return math::normalize(math::cross_high_precision(v0v1, v0v2));
+}
+
+/** Mark triangles \a t1 and \a t2 as neighbors, where \a pos1 and \a pos2
+ * are the positions in
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list