From 9bb2afb55e50f9353cfc76cf2d8df7521b0b5feb Mon Sep 17 00:00:00 2001 From: Howard Trickey Date: Sat, 2 Jul 2022 10:09:18 -0400 Subject: Start of Bevel V2, as being worked on with task T98674. This is the start of a geometry node to do edge, vertex, and face bevels. It doesn't yet do anything but analyze the "Vertex cap" around selected vertices for vertex bevel. --- source/blender/nodes/NOD_geometry.h | 1 + source/blender/nodes/NOD_static_types.h | 1 + source/blender/nodes/geometry/CMakeLists.txt | 1 + .../nodes/geometry/nodes/node_geo_bevel_mesh.cc | 461 +++++++++++++++++++++ 4 files changed, 464 insertions(+) create mode 100644 source/blender/nodes/geometry/nodes/node_geo_bevel_mesh.cc (limited to 'source/blender/nodes') diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h index 8f15add33fd..7e813aef85e 100644 --- a/source/blender/nodes/NOD_geometry.h +++ b/source/blender/nodes/NOD_geometry.h @@ -20,6 +20,7 @@ void register_node_type_geo_attribute_capture(void); void register_node_type_geo_attribute_domain_size(void); void register_node_type_geo_attribute_separate_xyz(void); void register_node_type_geo_attribute_statistic(void); +void register_node_type_geo_bevel_mesh(void); void register_node_type_geo_boolean(void); void register_node_type_geo_bounding_box(void); void register_node_type_geo_collection_info(void); diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h index 609791ad091..da324c98a26 100644 --- a/source/blender/nodes/NOD_static_types.h +++ b/source/blender/nodes/NOD_static_types.h @@ -281,6 +281,7 @@ DefNode(FunctionNode, FN_NODE_VALUE_TO_STRING, 0, "VALUE_TO_STRING", ValueToStri DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_DOMAIN_SIZE, def_geo_attribute_domain_size, "ATTRIBUTE_DOMAIN_SIZE", AttributeDomainSize, "Domain Size", "") DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_STATISTIC, def_geo_attribute_statistic, "ATTRIBUTE_STATISTIC", AttributeStatistic, "Attribute Statistic", "") +DefNode(GeometryNode, GEO_NODE_BEVEL_MESH, def_geo_bevel_mesh, "BEVEL_MESH", BevelMesh, "Bevel Mesh", "") DefNode(GeometryNode, GEO_NODE_BOUNDING_BOX, 0, "BOUNDING_BOX", BoundBox, "Bounding Box", "") DefNode(GeometryNode, GEO_NODE_CAPTURE_ATTRIBUTE, def_geo_attribute_capture, "CAPTURE_ATTRIBUTE", CaptureAttribute, "Capture Attribute", "") DefNode(GeometryNode, GEO_NODE_COLLECTION_INFO, def_geo_collection_info, "COLLECTION_INFO", CollectionInfo, "Collection Info", "") diff --git a/source/blender/nodes/geometry/CMakeLists.txt b/source/blender/nodes/geometry/CMakeLists.txt index 950124f75d0..1f83b375a84 100644 --- a/source/blender/nodes/geometry/CMakeLists.txt +++ b/source/blender/nodes/geometry/CMakeLists.txt @@ -29,6 +29,7 @@ set(SRC nodes/node_geo_attribute_capture.cc nodes/node_geo_attribute_domain_size.cc nodes/node_geo_attribute_statistic.cc + nodes/node_geo_bevel_mesh.cc nodes/node_geo_boolean.cc nodes/node_geo_bounding_box.cc nodes/node_geo_collection_info.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 new file mode 100644 index 00000000000..f14535a3c65 --- /dev/null +++ b/source/blender/nodes/geometry/nodes/node_geo_bevel_mesh.cc @@ -0,0 +1,461 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "BKE_mesh.h" +#include "BKE_mesh_mapping.h" +#include "BKE_mesh_runtime.h" + +#include "BLI_array.hh" +#include "BLI_set.hh" +#include "BLI_sort.hh" +#include "BLI_task.hh" +#include "BLI_timeit.hh" +#include "BLI_vector.hh" + +#include "UI_interface.h" +#include "UI_resources.h" + +#include "node_geometry_util.hh" + +#include + +namespace blender::nodes::node_geo_bevel_mesh_cc { + +NODE_STORAGE_FUNCS(NodeGeometryBevelMesh) + +static void node_declare(NodeDeclarationBuilder &b) +{ + b.add_input("Mesh").supported_type(GEO_COMPONENT_TYPE_MESH); + b.add_input(N_("Selection")).default_value(true).supports_field().hide_value(); + b.add_input(N_("Amount")).default_value(1.0f).supports_field(); + b.add_output("Mesh"); +} + +static void node_layout(uiLayout *layout, bContext *UNUSED(C), PointerRNA *ptr) +{ + uiLayoutSetPropSep(layout, true); + uiLayoutSetPropDecorate(layout, false); + uiItemR(layout, ptr, "mode", 0, "", ICON_NONE); +} + +static void node_init(bNodeTree *UNUSED(tree), bNode *node) +{ + NodeGeometryBevelMesh *data = MEM_cnew(__func__); + data->mode = GEO_NODE_BEVEL_MESH_EDGES; + node->storage = data; +} + +static void node_update(bNodeTree *UNUSED(ntree), bNode *UNUSED(node)) +{ +} + +/* While Mesh uses the term 'poly' for polygon, most of Blender uses the term 'face', + * so we'll go with 'face' in this code except in the final to/from mesh routines. + */ +class MeshTopology { + MeshElemMap *vert_edge_map_; + int *vert_edge_map_mem_; + MeshElemMap *edge_poly_map_; + int *edge_poly_map_mem_; + const Mesh &mesh_; + + public: + MeshTopology(const Mesh &mesh); + ~MeshTopology(); + + /* Edges adjacent to vertex v. */ + Span vert_edges(int v) const + { + const MeshElemMap &m = vert_edge_map_[v]; + return Span{m.indices, m.count}; + } + + /* Faces adjacent to edge e. */ + Span edge_faces(int e) const + { + const MeshElemMap &m = edge_poly_map_[e]; + return Span{m.indices, m.count}; + } + + /* Does edge e have exactly two adjacent faces? */ + bool edge_is_manifold(int e) const + { + return edge_poly_map_[e].count == 2; + } + + /* What is the other manifold face (i.e., not f) attached to edge e? + * Edge e must be manifold and f must be one of the incident faces. */ + int edge_other_manifold_face(int e, int f) const; + + /* What is the other edge of f (i.e., not e) attached to vertex v. + * Face f must contain e, and e must have v as one of its vertices. */ + int face_other_edge_at_vert(int f, int v, int e) const; + + /* Is edge e1 the successor of e0 when going around face f? */ + bool edge_is_successor_in_face(int e0, int e1, int f) const; + + int num_verts() const + { + return mesh_.totvert; + } + int num_edges() const + { + return mesh_.totedge; + } + int num_faces() const + { + return mesh_.totpoly; + } +}; + +MeshTopology::MeshTopology(const Mesh &mesh) : mesh_(mesh) +{ + timeit::ScopedTimer t("MeshTopology construction"); + BKE_mesh_vert_edge_map_create( + &vert_edge_map_, &vert_edge_map_mem_, mesh.medge, mesh.totvert, mesh.totedge); + BKE_mesh_edge_poly_map_create(&edge_poly_map_, + &edge_poly_map_mem_, + mesh.medge, + mesh.totedge, + mesh.mpoly, + mesh.totpoly, + mesh.mloop, + mesh.totloop); +} + +MeshTopology::~MeshTopology() +{ + MEM_freeN(vert_edge_map_); + MEM_freeN(vert_edge_map_mem_); + MEM_freeN(edge_poly_map_); + MEM_freeN(edge_poly_map_mem_); +} + +int MeshTopology::edge_other_manifold_face(int e, int f) const +{ + const MeshElemMap &m = edge_poly_map_[e]; + BLI_assert(m.count == 2); + if (m.indices[0] == f) { + return m.indices[1]; + } + BLI_assert(m.indices[1] == f); + return m.indices[0]; +} + +int MeshTopology::face_other_edge_at_vert(int f, int v, int e) const +{ + const MPoly &mpoly = mesh_.mpoly[f]; + const int loopstart = mpoly.loopstart; + const int loopend = mpoly.loopstart + mpoly.totloop - 1; + for (int l = loopstart; l <= loopend; l++) { + const MLoop &mloop = mesh_.mloop[l]; + if (mloop.e == e) { + if (mloop.v == v) { + /* The other edge with vertex v is the preceding (incoming) edge. */ + MLoop &mloop_prev = l == loopstart ? mesh_.mloop[loopend] : mesh_.mloop[l - 1]; + return mloop_prev.e; + } + else { + /* The other edge with vertex v is the next (outgoing) edge, which should have vertex v. */ + MLoop &mloop_next = l == loopend ? mesh_.mloop[loopstart] : mesh_.mloop[l + 1]; + BLI_assert(mloop_next.v == v); + return mloop_next.e; + } + } + } + /* If didn't return in the loop, then there is no edge e with vertex v in face f. */ + BLI_assert_unreachable(); + return -1; +} + +bool MeshTopology::edge_is_successor_in_face(const int e0, const int e1, const int f) const +{ + const MPoly &mpoly = mesh_.mpoly[f]; + const int loopstart = mpoly.loopstart; + const int loopend = mpoly.loopstart + mpoly.totloop - 1; + for (int l = loopstart; l <= loopend; l++) { + const MLoop &mloop = mesh_.mloop[l]; + if (mloop.e == e0) { + const MLoop &mloop_next = l == loopend ? mesh_.mloop[loopstart] : mesh_.mloop[l + 1]; + return mloop_next.e == e1; + } + } + return false; +} + +/* 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.) + */ +class VertexCap { + Array edges_; + Array faces_; // face_[i] is between edges i and i+1 + + public: + /* The vertex (as index into a mesh) that the cap is around. */ + int vert; + + VertexCap() : vert(-1) + { + } + VertexCap(int vert, Span edges, Span faces) : edges_(edges), faces_(faces), vert(vert) + { + } + + /* The number of edges around the cap. */ + int size() const + { + return edges_.size(); + } + + /* Edges in CCW order (viewed from top) around the cap. */ + Span edges() const + { + return edges_.as_span(); + } + + /* Faces in CCW order (viewed from top) around the cap. -1 means a gap. */ + Span faces() const + { + return faces_.as_span(); + } + + /* The ith edge. */ + int edge(int i) const + { + return edges_[i]; + } + /* The edge after the ith edge (with wraparound). */ + int next_edge(int i) const + { + return i < edges_.size() - 1 ? edges_[i + 1] : edges_[0]; + } + /* The edge before the ith edge (with wraparound). */ + int prev_edge(int i) const + { + return i > 1 ? edges_[i - 1] : edges_.last(); + } + + /* The face returned may be -1, meaning "gap". */ + /* The face betwen edge(i) and next_edge(i). */ + int face(int i) const + { + return faces_[i]; + } + /* The face between edge(i) and prev_edge(i). */ + int prev_face(int i) const + { + return i > 1 ? faces_[i - 1] : faces_.last(); + } + /* True if there is a gap between edges i and next_edge(i). */ + bool is_gap(int i) const + { + return face(i) == -1; + } + + /* Debug printing on std::cout. */ + void print() const; +}; + +class BevelData { + Array bevel_vert_caps_; + + public: + MeshTopology topo; + + BevelData(const Mesh &mesh) : topo(mesh) + { + } + ~BevelData() + { + } + + void init_caps_from_vertex_selection(const IndexMask selection); +}; + +/* Construct and return the VertexCap for vertex vert. */ +static VertexCap construct_cap(const int vert, const MeshTopology &topo) +{ + Span incident_edges = topo.vert_edges(vert); + const int num_edges = incident_edges.size(); + if (num_edges == 0) { + return VertexCap(vert, Span(), Span()); + } + + /* 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 ordered_edges(num_edges, -1); + Array ordered_faces(num_edges, -1); + Set used_edges; + Set used_faces; + + 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()); + } + } + return VertexCap(vert, ordered_edges.as_span(), ordered_faces.as_span()); + } + } + std::cout << "to implement: VertexCap for non-manifold edges\n"; + BLI_assert(false); + return VertexCap(); +} + +void VertexCap::print() const +{ + std::cout << "cap at v" << vert << ": "; + for (const int i : edges_.index_range()) { + std::cout << "e" << edges_[i] << " "; + if (faces_[i] == -1) { + std::cout << " "; + } + else { + std::cout << "f" << faces_[i] << " "; + } + } + std::cout << "\n"; +} + +void BevelData::init_caps_from_vertex_selection(const IndexMask selection) +{ + bevel_vert_caps_.reinitialize(selection.size()); + threading::parallel_for(selection.index_range(), 1024, [&](const IndexRange range) { + for (const int i : range) { + bevel_vert_caps_[i] = construct_cap(selection[i], topo); + } + }); +} + +static void bevel_mesh_vertices(MeshComponent &component, + const Field &selection_field, + const Field &amount_field) +{ + Mesh &mesh = *component.get_for_write(); + int orig_vert_size = mesh.totvert; + GeometryComponentFieldContext context(component, ATTR_DOMAIN_POINT); + FieldEvaluator evaluator{context, orig_vert_size}; + evaluator.set_selection(selection_field); + evaluator.add(amount_field); + evaluator.evaluate(); + VArray amounts = evaluator.get_evaluated(0); + const IndexMask selection = evaluator.get_evaluated_selection_as_mask(); + + BevelData bdata(mesh); + bdata.init_caps_from_vertex_selection(selection); +} + +static void bevel_mesh_edges(MeshComponent &UNUSED(component), + const Field &UNUSED(selection_field), + const Field &UNUSED(amount_field)) +{ +} + +static void bevel_mesh_faces(MeshComponent &UNUSED(component), + const Field &UNUSED(selection_field), + const Field &UNUSED(amount_field)) +{ +} + +static void node_geo_exec(GeoNodeExecParams params) +{ + GeometrySet geometry_set = params.extract_input("Mesh"); + Field selection_field = params.extract_input>("Selection"); + Field amount_field = params.extract_input>("Amount"); + const NodeGeometryBevelMesh &storage = node_storage(params.node()); + GeometryNodeBevelMeshMode mode = static_cast(storage.mode); + + geometry_set.modify_geometry_sets([&](GeometrySet &geometry_set) { + if (geometry_set.has_mesh()) { + MeshComponent &component = geometry_set.get_component_for_write(); + switch (mode) { + case GEO_NODE_BEVEL_MESH_VERTICES: + bevel_mesh_vertices(component, selection_field, amount_field); + break; + case GEO_NODE_BEVEL_MESH_EDGES: + bevel_mesh_edges(component, selection_field, amount_field); + break; + case GEO_NODE_BEVEL_MESH_FACES: + bevel_mesh_faces(component, selection_field, amount_field); + break; + } + BLI_assert(BKE_mesh_is_valid(component.get_for_write())); + } + }); + + params.set_output("Mesh", std::move(geometry_set)); +} + +} // namespace blender::nodes::node_geo_bevel_mesh_cc + +void register_node_type_geo_bevel_mesh() +{ + namespace file_ns = blender::nodes::node_geo_bevel_mesh_cc; + + static bNodeType ntype; + geo_node_type_base(&ntype, GEO_NODE_BEVEL_MESH, "Bevel Mesh", NODE_CLASS_GEOMETRY); + ntype.declare = file_ns::node_declare; + node_type_init(&ntype, file_ns::node_init); + node_type_update(&ntype, file_ns::node_update); + ntype.geometry_node_execute = file_ns::node_geo_exec; + node_type_storage( + &ntype, "NodeGeometryBevelMesh", node_free_standard_storage, node_copy_standard_storage); + ntype.draw_buttons = file_ns::node_layout; + nodeRegisterType(&ntype); +} -- cgit v1.2.3