diff options
| -rw-r--r-- | intern/rigidbody/RBI_hull_api.h | 4 | ||||
| -rw-r--r-- | intern/rigidbody/rb_convex_hull_api.cpp | 32 | ||||
| -rw-r--r-- | release/scripts/startup/nodeitems_builtins.py | 1 | ||||
| -rw-r--r-- | source/blender/blenkernel/BKE_node.h | 1 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/node.cc | 1 | ||||
| -rw-r--r-- | source/blender/nodes/CMakeLists.txt | 18 | ||||
| -rw-r--r-- | source/blender/nodes/NOD_geometry.h | 1 | ||||
| -rw-r--r-- | source/blender/nodes/NOD_static_types.h | 1 | ||||
| -rw-r--r-- | source/blender/nodes/geometry/nodes/node_geo_convex_hull.cc | 321 |
9 files changed, 380 insertions, 0 deletions
diff --git a/intern/rigidbody/RBI_hull_api.h b/intern/rigidbody/RBI_hull_api.h index 9d2dc5034db..3bd216b92cb 100644 --- a/intern/rigidbody/RBI_hull_api.h +++ b/intern/rigidbody/RBI_hull_api.h @@ -31,9 +31,13 @@ typedef struct plConvexHull__ { plConvexHull plConvexHullCompute(float (*coords)[3], int count); void plConvexHullDelete(plConvexHull hull); int plConvexHullNumVertices(plConvexHull hull); +int plConvexHullNumLoops(plConvexHull hull); int plConvexHullNumFaces(plConvexHull hull); void plConvexHullGetVertex(plConvexHull hull, int n, float coords[3], int *original_index); +void plConvexHullGetLoop(plConvexHull hull, int n, int *v_from, int *v_to); +int plConvexHullGetReversedLoopIndex(plConvexHull hull, int n); int plConvexHullGetFaceSize(plConvexHull hull, int n); +void plConvexHullGetFaceLoops(plConvexHull hull, int n, int *loops); void plConvexHullGetFaceVertices(plConvexHull hull, int n, int *vertices); #ifdef __cplusplus diff --git a/intern/rigidbody/rb_convex_hull_api.cpp b/intern/rigidbody/rb_convex_hull_api.cpp index c5893a4c808..03e7580a12b 100644 --- a/intern/rigidbody/rb_convex_hull_api.cpp +++ b/intern/rigidbody/rb_convex_hull_api.cpp @@ -39,6 +39,12 @@ int plConvexHullNumVertices(plConvexHull hull) return computer->vertices.size(); } +int plConvexHullNumLoops(plConvexHull hull) +{ + btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull)); + return computer->edges.size(); +} + int plConvexHullNumFaces(plConvexHull hull) { btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull)); @@ -55,6 +61,19 @@ void plConvexHullGetVertex(plConvexHull hull, int n, float coords[3], int *origi (*original_index) = computer->original_vertex_index[n]; } +void plConvexHullGetLoop(plConvexHull hull, int n, int *v_from, int *v_to) +{ + btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull)); + (*v_from) = computer->edges[n].getSourceVertex(); + (*v_to) = computer->edges[n].getTargetVertex(); +} + +int plConvexHullGetReversedLoopIndex(plConvexHull hull, int n) +{ + btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull)); + return computer->edges[n].getReverseEdge() - &computer->edges[0]; +} + int plConvexHullGetFaceSize(plConvexHull hull, int n) { btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull)); @@ -69,6 +88,19 @@ int plConvexHullGetFaceSize(plConvexHull hull, int n) return count; } +void plConvexHullGetFaceLoops(plConvexHull hull, int n, int *loops) +{ + btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull)); + const btConvexHullComputer::Edge *e_orig, *e; + int count; + + for (e_orig = &computer->edges[computer->faces[n]], e = e_orig, count = 0; + count == 0 || e != e_orig; + e = e->getNextEdgeOfFace(), count++) { + loops[count] = e - &computer->edges[0]; + } +} + void plConvexHullGetFaceVertices(plConvexHull hull, int n, int *vertices) { btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull)); diff --git a/release/scripts/startup/nodeitems_builtins.py b/release/scripts/startup/nodeitems_builtins.py index cf125075b3b..5ff0e13f242 100644 --- a/release/scripts/startup/nodeitems_builtins.py +++ b/release/scripts/startup/nodeitems_builtins.py @@ -508,6 +508,7 @@ geometry_node_categories = [ ]), GeometryNodeCategory("GEO_GEOMETRY", "Geometry", items=[ NodeItem("GeometryNodeBoundBox"), + NodeItem("GeometryNodeConvexHull"), NodeItem("GeometryNodeDeleteGeometry"), NodeItem("GeometryNodeTransform"), NodeItem("GeometryNodeJoinGeometry"), diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h index 16da621a0fa..a67d7116874 100644 --- a/source/blender/blenkernel/BKE_node.h +++ b/source/blender/blenkernel/BKE_node.h @@ -1433,6 +1433,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree, #define GEO_NODE_DELETE_GEOMETRY 1053 #define GEO_NODE_CURVE_LENGTH 1054 #define GEO_NODE_SELECT_BY_MATERIAL 1055 +#define GEO_NODE_CONVEX_HULL 1056 /** \} */ diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc index 10f1f40f390..8d8f7b90d3b 100644 --- a/source/blender/blenkernel/intern/node.cc +++ b/source/blender/blenkernel/intern/node.cc @@ -5050,6 +5050,7 @@ static void registerGeometryNodes() register_node_type_geo_boolean(); register_node_type_geo_bounding_box(); register_node_type_geo_collection_info(); + register_node_type_geo_convex_hull(); register_node_type_geo_curve_length(); register_node_type_geo_curve_to_mesh(); register_node_type_geo_curve_resample(); diff --git a/source/blender/nodes/CMakeLists.txt b/source/blender/nodes/CMakeLists.txt index 7aaf28869de..025ce79ffc5 100644 --- a/source/blender/nodes/CMakeLists.txt +++ b/source/blender/nodes/CMakeLists.txt @@ -162,6 +162,7 @@ set(SRC geometry/nodes/node_geo_bounding_box.cc geometry/nodes/node_geo_collection_info.cc geometry/nodes/node_geo_common.cc + geometry/nodes/node_geo_convex_hull.cc geometry/nodes/node_geo_curve_length.cc geometry/nodes/node_geo_curve_to_mesh.cc geometry/nodes/node_geo_curve_resample.cc @@ -363,6 +364,23 @@ set(LIB bf_intern_sky ) +if(WITH_BULLET) + list(APPEND INC_SYS + ${BULLET_INCLUDE_DIRS} + "../../../intern/rigidbody/" + ) + if(NOT WITH_SYSTEM_BULLET) + list(APPEND LIB + extern_bullet + ) + endif() + + list(APPEND LIB + ${BULLET_LIBRARIES} + ) + add_definitions(-DWITH_BULLET) +endif() + if(WITH_PYTHON) list(APPEND INC ../python diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h index df14fcfe5b4..b7e1b0b657c 100644 --- a/source/blender/nodes/NOD_geometry.h +++ b/source/blender/nodes/NOD_geometry.h @@ -50,6 +50,7 @@ void register_node_type_geo_attribute_remove(void); void register_node_type_geo_boolean(void); void register_node_type_geo_bounding_box(void); void register_node_type_geo_collection_info(void); +void register_node_type_geo_convex_hull(void); void register_node_type_geo_curve_length(void); void register_node_type_geo_curve_to_mesh(void); void register_node_type_geo_curve_resample(void); diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h index bfd99a2bb60..b255c6e5f23 100644 --- a/source/blender/nodes/NOD_static_types.h +++ b/source/blender/nodes/NOD_static_types.h @@ -289,6 +289,7 @@ DefNode(GeometryNode, GEO_NODE_ATTRIBUTE_VECTOR_ROTATE, def_geo_attribute_vector DefNode(GeometryNode, GEO_NODE_BOOLEAN, def_geo_boolean, "BOOLEAN", Boolean, "Boolean", "") DefNode(GeometryNode, GEO_NODE_BOUNDING_BOX, 0, "BOUNDING_BOX", BoundBox, "Bounding Box", "") DefNode(GeometryNode, GEO_NODE_COLLECTION_INFO, def_geo_collection_info, "COLLECTION_INFO", CollectionInfo, "Collection Info", "") +DefNode(GeometryNode, GEO_NODE_CONVEX_HULL, 0, "CONVEX_HULL", ConvexHull, "Convex Hull", "") DefNode(GeometryNode, GEO_NODE_CURVE_LENGTH, 0, "CURVE_LENGTH", CurveLength, "Curve Length", "") DefNode(GeometryNode, GEO_NODE_CURVE_RESAMPLE, def_geo_curve_resample, "CURVE_RESAMPLE", CurveResample, "Resample Curve", "") DefNode(GeometryNode, GEO_NODE_CURVE_TO_MESH, 0, "CURVE_TO_MESH", CurveToMesh, "Curve to Mesh", "") diff --git a/source/blender/nodes/geometry/nodes/node_geo_convex_hull.cc b/source/blender/nodes/geometry/nodes/node_geo_convex_hull.cc new file mode 100644 index 00000000000..b1b17a321b8 --- /dev/null +++ b/source/blender/nodes/geometry/nodes/node_geo_convex_hull.cc @@ -0,0 +1,321 @@ +/* + * 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. + */ + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" +#include "DNA_pointcloud_types.h" + +#include "BKE_material.h" +#include "BKE_mesh.h" +#include "BKE_spline.hh" + +#include "node_geometry_util.hh" + +#ifdef WITH_BULLET +# include "RBI_hull_api.h" +#endif + +static bNodeSocketTemplate geo_node_convex_hull_in[] = { + {SOCK_GEOMETRY, N_("Geometry")}, + {-1, ""}, +}; + +static bNodeSocketTemplate geo_node_convex_hull_out[] = { + {SOCK_GEOMETRY, N_("Convex Hull")}, + {-1, ""}, +}; + +namespace blender::nodes { + +using bke::GeometryInstanceGroup; + +#ifdef WITH_BULLET + +static Mesh *hull_from_bullet(const Mesh *mesh, Span<float3> coords) +{ + plConvexHull hull = plConvexHullCompute((float(*)[3])coords.data(), coords.size()); + + const int num_verts = plConvexHullNumVertices(hull); + const int num_faces = num_verts <= 2 ? 0 : plConvexHullNumFaces(hull); + const int num_loops = num_verts <= 2 ? 0 : plConvexHullNumLoops(hull); + /* Half as many edges as loops, because the mesh is manifold. */ + const int num_edges = num_verts == 2 ? 1 : num_verts < 2 ? 0 : num_loops / 2; + + /* Create Mesh *result with proper capacity. */ + Mesh *result; + if (mesh) { + result = BKE_mesh_new_nomain_from_template( + mesh, num_verts, num_edges, 0, num_loops, num_faces); + } + else { + result = BKE_mesh_new_nomain(num_verts, num_edges, 0, num_loops, num_faces); + BKE_id_material_eval_ensure_default_slot(&result->id); + } + + /* Copy vertices. */ + for (const int i : IndexRange(num_verts)) { + float co[3]; + int original_index; + plConvexHullGetVertex(hull, i, co, &original_index); + + if (original_index >= 0 && original_index < coords.size()) { +# if 0 /* Disabled because it only works for meshes, not predictable enough. */ + /* Copy custom data on vertices, like vertex groups etc. */ + if (mesh && original_index < mesh->totvert) { + CustomData_copy_data(&mesh->vdata, &result->vdata, (int)original_index, (int)i, 1); + } +# endif + /* Copy the position of the original point. */ + copy_v3_v3(result->mvert[i].co, co); + } + else { + BLI_assert(!"Unexpected new vertex in hull output"); + } + } + + /* Copy edges and loops. */ + + /* NOTE: ConvexHull from Bullet uses a half-edge data structure + * for its mesh. To convert that, each half-edge needs to be converted + * to a loop and edges need to be created from that. */ + Array<MLoop> mloop_src(num_loops); + uint edge_index = 0; + for (const int i : IndexRange(num_loops)) { + int v_from; + int v_to; + plConvexHullGetLoop(hull, i, &v_from, &v_to); + + mloop_src[i].v = (uint)v_from; + /* Add edges for ascending order loops only. */ + if (v_from < v_to) { + MEdge &edge = result->medge[edge_index]; + edge.v1 = v_from; + edge.v2 = v_to; + edge.flag = ME_EDGEDRAW | ME_EDGERENDER; + + /* Write edge index into both loops that have it. */ + int reverse_index = plConvexHullGetReversedLoopIndex(hull, i); + mloop_src[i].e = edge_index; + mloop_src[reverse_index].e = edge_index; + edge_index++; + } + } + if (num_edges == 1) { + /* In this case there are no loops. */ + MEdge &edge = result->medge[0]; + edge.v1 = 0; + edge.v2 = 1; + edge.flag |= ME_EDGEDRAW | ME_EDGERENDER | ME_LOOSEEDGE; + edge_index++; + } + BLI_assert(edge_index == num_edges); + + /* Copy faces. */ + Array<int> loops; + int j = 0; + MLoop *loop = result->mloop; + for (const int i : IndexRange(num_faces)) { + const int len = plConvexHullGetFaceSize(hull, i); + + BLI_assert(len > 2); + + /* Get face loop indices. */ + loops.reinitialize(len); + plConvexHullGetFaceLoops(hull, i, loops.data()); + + MPoly &face = result->mpoly[i]; + face.loopstart = j; + face.totloop = len; + for (const int k : IndexRange(len)) { + MLoop &src_loop = mloop_src[loops[k]]; + loop->v = src_loop.v; + loop->e = src_loop.e; + loop++; + } + j += len; + } + + plConvexHullDelete(hull); + + BKE_mesh_calc_normals(result); + return result; +} + +static Mesh *compute_hull(const GeometrySet &geometry_set) +{ + int span_count = 0; + int count = 0; + int total_size = 0; + + Span<float3> positions_span; + + if (geometry_set.has_mesh()) { + count++; + const MeshComponent *component = geometry_set.get_component_for_read<MeshComponent>(); + total_size += component->attribute_domain_size(ATTR_DOMAIN_POINT); + } + + if (geometry_set.has_pointcloud()) { + count++; + span_count++; + const PointCloudComponent *component = + geometry_set.get_component_for_read<PointCloudComponent>(); + GVArray_Typed<float3> varray = component->attribute_get_for_read<float3>( + "position", ATTR_DOMAIN_POINT, {0, 0, 0}); + total_size += varray->size(); + positions_span = varray->get_internal_span(); + } + + if (geometry_set.has_curve()) { + const CurveEval &curve = *geometry_set.get_curve_for_read(); + for (const SplinePtr &spline : curve.splines()) { + positions_span = spline->evaluated_positions(); + total_size += positions_span.size(); + count++; + span_count++; + } + } + + if (count == 0) { + return nullptr; + } + + /* If there is only one positions virtual array and it is already contiguous, avoid copying + * all of the positions and instead pass the span directly to the convex hull function. */ + if (span_count == 1 && count == 1) { + return hull_from_bullet(nullptr, positions_span); + } + + Array<float3> positions(total_size); + int offset = 0; + + if (geometry_set.has_mesh()) { + const MeshComponent *component = geometry_set.get_component_for_read<MeshComponent>(); + GVArray_Typed<float3> varray = component->attribute_get_for_read<float3>( + "position", ATTR_DOMAIN_POINT, {0, 0, 0}); + varray->materialize(positions.as_mutable_span().slice(offset, varray.size())); + offset += varray.size(); + } + + if (geometry_set.has_pointcloud()) { + const PointCloudComponent *component = + geometry_set.get_component_for_read<PointCloudComponent>(); + GVArray_Typed<float3> varray = component->attribute_get_for_read<float3>( + "position", ATTR_DOMAIN_POINT, {0, 0, 0}); + varray->materialize(positions.as_mutable_span().slice(offset, varray.size())); + offset += varray.size(); + } + + if (geometry_set.has_curve()) { + const CurveEval &curve = *geometry_set.get_curve_for_read(); + for (const SplinePtr &spline : curve.splines()) { + Span<float3> array = spline->evaluated_positions(); + positions.as_mutable_span().slice(offset, array.size()).copy_from(array); + offset += array.size(); + } + } + + return hull_from_bullet(geometry_set.get_mesh_for_read(), positions); +} + +static void read_positions(const GeometryComponent &component, + Span<float4x4> transforms, + Vector<float3> *r_coords) +{ + GVArray_Typed<float3> positions = component.attribute_get_for_read<float3>( + "position", ATTR_DOMAIN_POINT, {0, 0, 0}); + + /* NOTE: could use convex hull operation here to + * cut out some vertices, before accumulating, + * but can also be done by the user beforehand. */ + + r_coords->reserve(r_coords->size() + positions.size() * transforms.size()); + for (const float4x4 &transform : transforms) { + for (const int i : positions.index_range()) { + const float3 position = positions[i]; + const float3 transformed_position = transform * position; + r_coords->append(transformed_position); + } + } +} + +static void read_curve_positions(const CurveEval &curve, + Span<float4x4> transforms, + Vector<float3> *r_coords) +{ + const Array<int> offsets = curve.evaluated_point_offsets(); + const int total_size = offsets.last(); + r_coords->reserve(r_coords->size() + total_size * transforms.size()); + for (const SplinePtr &spline : curve.splines()) { + Span<float3> positions = spline->evaluated_positions(); + for (const float4x4 &transform : transforms) { + for (const float3 &position : positions) { + r_coords->append(transform * position); + } + } + } +} + +#endif /* WITH_BULLET */ + +static void geo_node_convex_hull_exec(GeoNodeExecParams params) +{ + GeometrySet geometry_set = params.extract_input<GeometrySet>("Geometry"); + +#ifdef WITH_BULLET + Mesh *mesh = nullptr; + if (geometry_set.has_instances()) { + Vector<GeometryInstanceGroup> set_groups; + bke::geometry_set_gather_instances(geometry_set, set_groups); + + Vector<float3> coords; + + for (const GeometryInstanceGroup &set_group : set_groups) { + const GeometrySet &set = set_group.geometry_set; + Span<float4x4> transforms = set_group.transforms; + + if (set.has_pointcloud()) { + read_positions(*set.get_component_for_read<PointCloudComponent>(), transforms, &coords); + } + if (set.has_mesh()) { + read_positions(*set.get_component_for_read<MeshComponent>(), transforms, &coords); + } + if (set.has_curve()) { + read_curve_positions(*set.get_curve_for_read(), transforms, &coords); + } + } + mesh = hull_from_bullet(nullptr, coords); + } + else { + mesh = compute_hull(geometry_set); + } + params.set_output("Convex Hull", GeometrySet::create_with_mesh(mesh)); +#else + params.set_output("Convex Hull", geometry_set); +#endif /* WITH_BULLET */ +} + +} // namespace blender::nodes + +void register_node_type_geo_convex_hull() +{ + static bNodeType ntype; + + geo_node_type_base(&ntype, GEO_NODE_CONVEX_HULL, "Convex Hull", NODE_CLASS_GEOMETRY, 0); + node_type_socket_templates(&ntype, geo_node_convex_hull_in, geo_node_convex_hull_out); + ntype.geometry_node_execute = blender::nodes::geo_node_convex_hull_exec; + nodeRegisterType(&ntype); +} |