[Bf-blender-cvs] [fc8f9e42042] bevelv2: Refactored vertex data structures.
Howard Trickey
noreply at git.blender.org
Mon Oct 24 19:38:30 CEST 2022
Commit: fc8f9e420426570dcb3e026ecbe8145cd0fae5ca
Author: Howard Trickey
Date: Mon Oct 24 19:25:22 2022 +0200
Branches: bevelv2
https://developer.blender.org/rBfc8f9e420426570dcb3e026ecbe8145cd0fae5ca
Refactored vertex data structures.
===================================================================
M source/blender/nodes/geometry/nodes/node_geo_bevel_mesh.cc
===================================================================
diff --git a/source/blender/nodes/geometry/nodes/node_geo_bevel_mesh.cc b/source/blender/nodes/geometry/nodes/node_geo_bevel_mesh.cc
index ab6b24515e6..9f0a54ea9c3 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_bevel_mesh.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_bevel_mesh.cc
@@ -9,6 +9,8 @@
#include "BKE_mesh_runtime.h"
#include "BLI_array.hh"
+#include "BLI_hash.hh"
+#include "BLI_map.hh"
#include "BLI_math_vec_types.hh"
#include "BLI_math_vector.hh"
#include "BLI_mesh_inset.hh"
@@ -245,1246 +247,1286 @@ float3 MeshTopology::edge_dir_from_vert_normalized(int e, int v) const
return math::normalize(edge_dir_from_vert(e, v));
}
-/** A Vertex Cap consists of a vertex in a mesh and an CCW ordering of
- * alternating edges and faces around it, as viewed from the face's
- * normal side. Some faces may be missing (i.e., gaps).
- * (If there are other edges and faces attached to the vertex that
- * don't fit into this pattern, they need to go into other Vertex Caps
- * or ignored, for the sake of beveling.)
+/** Canon
+ * CanonVertPair is a pair of vertex indices in canonical order (first index <= second index).
+ * This is suitable for a key to look up edges by.
*/
-class VertexCap {
- Array<int> edges_;
- Array<int> faces_; // face_[i] is between edges i and i+1
-
+class CanonVertPair {
public:
- /* The vertex (as index into a mesh) that the cap is around. */
- int vert;
+ int v1;
+ int v2;
- VertexCap() : vert(-1)
+ CanonVertPair(int a, int b)
{
+ if (a < b) {
+ v1 = a;
+ v2 = b;
+ }
+ else {
+ v1 = b;
+ v2 = a;
+ }
}
- VertexCap(int vert, Span<int> edges, Span<int> faces) : edges_(edges), faces_(faces), vert(vert)
+
+ uint64_t hash() const
{
+ return get_default_hash_2(v1, v2);
}
- /* Initialize for vertex v, given a mesh topo. */
- void init_from_topo(const int vert, const MeshTopology &topo);
+ friend bool operator==(const CanonVertPair a, const CanonVertPair b);
+};
- /* The number of edges around the cap. */
- int size() const
- {
- return edges_.size();
- }
+bool operator==(const CanonVertPair a, const CanonVertPair b){
+ return a.v1 == b.v1 && a.v2 == b.v2;
+}
- /* Edges in CCW order (viewed from top) around the cap. */
- Span<int> edges() const
- {
- return edges_.as_span();
- }
+/** IndexAlloc allocates sequential integers, starting from a given start value. */
+class IndexAlloc {
+ int start_;
+ int first_free_;
- /* Faces in CCW order (viewed from top) around the cap. -1 means a gap. */
- Span<int> faces() const
+ public:
+ IndexAlloc(int start) : start_(start), first_free_(start)
{
- return faces_.as_span();
}
- /* The ith edge. */
- int edge(int i) const
+ int alloc()
{
- return edges_[i];
+ return first_free_++;
}
- /* The edge after the ith edge (with wraparound). */
- int next_edge(int i) const
+ int start() const
{
- return i < edges_.size() - 1 ? edges_[i + 1] : edges_[0];
+ return start_;
}
- /* The edge before the ith edge (with wraparound). */
- int prev_edge(int i) const
+ int allocated_size() const
{
- return i > 1 ? edges_[i - 1] : edges_.last();
+ return first_free_ - start_;
}
+};
- /* The face returned may be -1, meaning "gap". */
- /* The face betwen edge(i) and next_edge(i). */
- int face(int i) const
+/** MeshDelta represents a delta to a Mesh: additions and deletions
+ * of Mesh elements.
+ * New elements will get index numbers starting at the end of the current
+ * range of the elements in the base mesh, `mesh_`.
+ * There is also a fast method for finding an edge, if any, joining two
+ * vertices (either in the base mesh, or in the added vertices, or mixed).
+ */
+class MeshDelta {
+ const Mesh &mesh_;
+ const MeshTopology &topo_;
+ IndexAlloc vert_alloc_;
+ IndexAlloc edge_alloc_;
+ IndexAlloc poly_alloc_;
+ IndexAlloc loop_alloc_;
+ Set<int> vert_deletes_;
+ Set<int> edge_deletes_;
+ Set<int> poly_deletes_;
+ Set<int> loop_deletes_;
+ Vector<MVert> new_verts_;
+ Vector<MEdge> new_edges_;
+ Vector<MPoly> new_polys_;
+ Vector<MLoop> new_loops_;
+ Vector<int> new_vert_rep_;
+ Vector<int> new_edge_rep_;
+ Vector<int> new_poly_rep_;
+ Vector<int> new_loop_rep_;
+ /* Lookup map for added edges. */
+ Map<CanonVertPair, int> new_edge_map_;
+
+ public:
+ MeshDelta(const Mesh &mesh, const MeshTopology &topo);
+
+ /* In the following, `rep` is the index of the old mesh element to base attributes on. */
+ int new_vert(const float3 &co, int rep);
+ int new_edge(int v1, int v2, int rep);
+ int new_loop(int v, int e, int rep);
+ int new_face(int loopstart, int totloop, int rep);
+ /* A new face from a span of vertex indices and edge indices (-1 means: make a new edge). */
+ int new_face(Span<int> verts, Span<int> edges, int rep);
+ /* Find the edge either in mesh or new_edges_, or make a new one if not there. */
+ int find_or_add_edge(int v1, int v2, int rep);
+
+ void delete_vert(int v)
{
- return faces_[i];
+ vert_deletes_.add(v);
}
- /* The face between edge(i) and prev_edge(i). */
- int prev_face(int i) const
+ void delete_edge(int e)
{
- return i > 1 ? faces_[i - 1] : faces_.last();
+ edge_deletes_.add(e);
}
- /* True if there is a gap between edges i and next_edge(i). */
- bool is_gap(int i) const
+ void delete_face(int f);
+
+ void get_edge_verts(int edge, int *r_v1, int *r_v2)
{
- return face(i) == -1;
+ const MEdge &medge = new_edges_[edge - edge_alloc_.start()];
+ *r_v1 = medge.v1;
+ *r_v2 = medge.v2;
}
+
+ /* Return a new Mesh, the result of applying delta to mesh_. */
+ Mesh *apply_delta_to_mesh(GeometrySet &geometry_set, const MeshComponent &in_component);
+
+ void print(const std::string &label) const;
};
-/** Construct and return the VertexCap for vertex `vert`. */
-void VertexCap::init_from_topo(const int vert, const MeshTopology &topo)
+MeshDelta::MeshDelta(const Mesh &mesh, const MeshTopology &topo)
+ : mesh_(mesh),
+ topo_(topo),
+ vert_alloc_(mesh_.totvert),
+ edge_alloc_(mesh_.totedge),
+ poly_alloc_(mesh_.totpoly),
+ loop_alloc_(mesh_.totloop)
{
- this->vert = vert;
- Span<int> incident_edges = topo.vert_edges(vert);
- const int num_edges = incident_edges.size();
- if (num_edges == 0) {
- return;
- }
+}
- /* First check for the most common case: a complete manifold cap:
- * That is, each edge is incident on exactly two faces and the
- * edge--face--edge--...--face chain forms a single cycle.
- */
- bool all_edges_manifold = true;
- for (const int e : incident_edges) {
- if (!topo.edge_is_manifold(e)) {
- all_edges_manifold = false;
- break;
- }
- }
- if (all_edges_manifold) {
- bool is_manifold_cap = true;
- Array<int> ordered_edges(num_edges, -1);
- Array<int> ordered_faces(num_edges, -1);
- Set<int, 16> used_edges;
- Set<int, 16> used_faces;
+int MeshDelta::new_vert(const float3 &co, int rep)
+{
+ int v = vert_alloc_.alloc();
+ MVert mvert;
+ copy_v3_v3(mvert.co, co);
+ new_verts_.append(mvert);
+ new_vert_rep_.append(rep);
+ return v;
+}
- int next_edge = incident_edges[0];
- for (int slot = 0; slot < num_edges; slot++) {
- /* Invariant: ordered_edges and ordered_faces are filled
- * up to slot-1 with a valid sequence for the cap, and
- * next_edge is a valid continuation edge but we don't
- * yet know if it has already been used.
- */
- ordered_edges[slot] = next_edge;
- used_edges.add_new(next_edge);
- /* Find a face attached to next_edge that is not yet used. */
- int next_face;
- if (slot == 0) {
- next_face = topo.edge_faces(next_edge)[0];
- }
- else {
- const int prev_face = ordered_faces[slot - 1];
- next_face = topo.edge_other_manifold_face(next_edge, prev_face);
- }
- if (used_faces.contains(next_face)) {
- is_manifold_cap = false;
- break;
- }
- ordered_faces[slot] = next_face;
- next_edge = topo.face_other_edge_at_vert(next_face, vert, next_edge);
- if (slot < num_edges - 1 && used_edges.contains(next_edge)) {
- is_manifold_cap = false;
- break;
- }
- }
- is_manifold_cap = is_manifold_cap && next_edge == ordered_edges[0];
- if (is_manifold_cap) {
- /* Check if cap is oriented properly, and fix it if not.
- * A pair of successive edges in ordered_edges should be going CW
- * in the face in between. For now, just check the first pair.
- */
- if (num_edges > 1) {
- if (topo.edge_is_successor_in_face(ordered_edges[0], ordered_edges[1], ordered_faces[0])) {
- /* They are in the wrong orientation, so we need to reverse.
- * To make interleaving of edges and faces work out, reverse only 1..end of edges
- * and reverse all of faces.
- */
- std::reverse(ordered_edges.begin() + 1, ordered_edges.end());
- std::reverse(ordered_faces.begin(), ordered_faces.end());
- }
+int MeshDelta::new_edge(int v1, int v2, int rep)
+{
+ int e = edge_alloc_.alloc();
+ MEdge medge;
+ medge.v1 = v1;
+ medge.v2 = v2;
+ medge.flag = ME_EDGEDRAW;
+ new_edges_.append(medge);
+ new_edge_rep_.append(rep);
+ new_edge_map_.add_new(CanonVertPair(v1, v2), e);
+ return e;
+}
+
+int MeshDelta::find_or_add_edge(int v1, int v2, int rep)
+{
+ /* First see if (v1, v2) is an existing edge in the base mesh. */
+ if (v1 < mesh_.totvert && v2 < mesh_.totvert) {
+ for (int i : topo_.vert_edges(v1)) {
+ const MEdge &e = mesh_.edges()[i];
+ if ((e.v1 == v1 && e.v2 == v2) || (e.v1 == v2 && e.v2 == v1)) {
+ return i;
}
- this->edges_ = ordered_edges;
- this->faces_ = ordered_faces;
- return;
}
}
- std::cout << "to implement: VertexCap for non-manifold edges\n";
+ /* Look inside the new edge map to see if it is there. */
+ int e = new_edge_map_.lookup_default(CanonVertPair(v1, v2), -1);
+ if (e != -1) {
+ return e;
+ }
+ return new_edge(v1, v2, rep);
}
-static std::ostream &operator<<(std::ostream &os, const VertexCap &cap)
+int MeshDelta::new_loop(int v, int
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list