Blender V5.3
node_geo_convex_hull.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
6
7#include "BKE_curves.hh"
9#include "BKE_instances.hh"
10#include "BKE_material.hh"
11#include "BKE_mesh.hh"
12
15#include "GEO_randomize.hh"
16
17#include "node_geometry_util.hh"
18
19#ifdef WITH_BULLET
20# include "RBI_hull_api.h"
21#endif
22
24
26{
27 b.add_input<decl::Geometry>("Geometry"_ustr).description("Points to compute the convex hull of");
28 b.add_output<decl::Geometry>("Convex Hull"_ustr).propagate_all_geometry();
29}
30
31#ifdef WITH_BULLET
32
33static Mesh *hull_from_bullet(const Mesh *mesh, Span<float3> coords)
34{
35 plConvexHull hull = plConvexHullCompute((float (*)[3])coords.data(), coords.size());
36
37 const int verts_num = plConvexHullNumVertices(hull);
38 const int faces_num = verts_num <= 2 ? 0 : plConvexHullNumFaces(hull);
39 const int loops_num = verts_num <= 2 ? 0 : plConvexHullNumLoops(hull);
40 /* Half as many edges as loops, because the mesh is manifold. */
41 const int edges_num = verts_num == 2 ? 1 : verts_num < 2 ? 0 : loops_num / 2;
42
43 /* Create Mesh *result with proper capacity. */
44 Mesh *result;
45 if (mesh) {
46 result = BKE_mesh_new_nomain_from_template(mesh, verts_num, edges_num, faces_num, loops_num);
47 }
48 else {
49 result = BKE_mesh_new_nomain(verts_num, edges_num, faces_num, loops_num);
51 }
53
54 /* Copy vertices. */
55 MutableSpan<float3> dst_positions = result->vert_positions_for_write();
56 for (const int i : IndexRange(verts_num)) {
57 float3 dummy_co;
58 int original_index;
59 plConvexHullGetVertex(hull, i, dummy_co, &original_index);
60 if (!coords.index_range().contains(original_index)) [[unlikely]] {
62 dst_positions[i] = float3(0);
63 continue;
64 }
65 dst_positions[i] = coords[original_index];
66 }
67
68 /* Copy edges and loops. */
69
70 /* NOTE: ConvexHull from Bullet uses a half-edge data structure
71 * for its mesh. To convert that, each half-edge needs to be converted
72 * to a loop and edges need to be created from that. */
73 Array<int> corner_verts(loops_num);
74 Array<int> corner_edges(loops_num);
75 uint edge_index = 0;
76 MutableSpan<int2> edges = result->edges_for_write();
77
78 for (const int i : IndexRange(loops_num)) {
79 int v_from;
80 int v_to;
81 plConvexHullGetLoop(hull, i, &v_from, &v_to);
82
83 corner_verts[i] = v_from;
84 /* Add edges for ascending order loops only. */
85 if (v_from < v_to) {
86 edges[edge_index] = int2(v_from, v_to);
87
88 /* Write edge index into both loops that have it. */
89 int reverse_index = plConvexHullGetReversedLoopIndex(hull, i);
90 corner_edges[i] = edge_index;
91 corner_edges[reverse_index] = edge_index;
92 edge_index++;
93 }
94 }
95 if (edges_num == 1) {
96 /* In this case there are no loops. */
97 edges[0] = int2(0, 1);
98 edge_index++;
99 }
100 BLI_assert(edge_index == edges_num);
101
102 /* Copy faces. */
103 Array<int> loops;
104 int j = 0;
105 MutableSpan<int> face_offsets = result->face_offsets_for_write();
106 MutableSpan<int> mesh_corner_verts = result->corner_verts_for_write();
107 MutableSpan<int> mesh_corner_edges = result->corner_edges_for_write();
108 int dst_corner = 0;
109
110 for (const int i : IndexRange(faces_num)) {
111 const int len = plConvexHullGetFaceSize(hull, i);
112
113 BLI_assert(len > 2);
114
115 /* Get face loop indices. */
116 loops.reinitialize(len);
117 plConvexHullGetFaceLoops(hull, i, loops.data());
118
119 face_offsets[i] = j;
120 for (const int k : IndexRange(len)) {
121 mesh_corner_verts[dst_corner] = corner_verts[loops[k]];
122 mesh_corner_edges[dst_corner] = corner_edges[loops[k]];
123 dst_corner++;
124 }
125 j += len;
126 }
127
128 plConvexHullDelete(hull);
129 return result;
130}
131
132static Mesh *compute_hull(const GeometrySet &geometry_set)
133{
134 int span_count = 0;
135 int count = 0;
136 int total_num = 0;
137
138 Span<float3> positions_span;
139
140 if (const Mesh *mesh = geometry_set.get_mesh()) {
141 count++;
142 if (const VArray positions = *mesh->attributes().lookup<float3>("position")) {
143 if (positions.is_span()) {
144 span_count++;
145 positions_span = positions.get_internal_span();
146 }
147 total_num += positions.size();
148 }
149 }
150
151 if (const PointCloud *points = geometry_set.get_pointcloud()) {
152 count++;
153 if (const VArray positions = *points->attributes().lookup<float3>("position")) {
154 if (positions.is_span()) {
155 span_count++;
156 positions_span = positions.get_internal_span();
157 }
158 total_num += positions.size();
159 }
160 }
161
162 if (const Curves *curves_id = geometry_set.get_curves()) {
163 count++;
164 span_count++;
165 const bke::CurvesGeometry &curves = curves_id->geometry.wrap();
166 positions_span = curves.evaluated_positions();
167 total_num += positions_span.size();
168 }
169
170 if (count == 0) {
171 return nullptr;
172 }
173
174 /* If there is only one positions virtual array and it is already contiguous, avoid copying
175 * all of the positions and instead pass the span directly to the convex hull function. */
176 if (span_count == 1 && count == 1) {
177 return hull_from_bullet(geometry_set.get_mesh(), positions_span);
178 }
179
180 Array<float3> positions(total_num);
181 int offset = 0;
182
183 if (const Mesh *mesh = geometry_set.get_mesh()) {
184 if (const VArray varray = *mesh->attributes().lookup<float3>("position")) {
185 varray.materialize(positions.as_mutable_span().slice(offset, varray.size()));
186 offset += varray.size();
187 }
188 }
189
190 if (const PointCloud *points = geometry_set.get_pointcloud()) {
191 if (const VArray varray = *points->attributes().lookup<float3>("position")) {
192 varray.materialize(positions.as_mutable_span().slice(offset, varray.size()));
193 offset += varray.size();
194 }
195 }
196
197 if (const Curves *curves_id = geometry_set.get_curves()) {
198 const bke::CurvesGeometry &curves = curves_id->geometry.wrap();
199 Span<float3> array = curves.evaluated_positions();
200 positions.as_mutable_span().slice(offset, array.size()).copy_from(array);
201 offset += array.size();
202 }
203
204 return hull_from_bullet(geometry_set.get_mesh(), positions);
205}
206
207static void convex_hull_grease_pencil(GeometrySet &geometry_set)
208{
209 using namespace blender::bke::greasepencil;
210
211 const GreasePencil &grease_pencil = *geometry_set.get_grease_pencil();
212 Array<Mesh *> mesh_by_layer(grease_pencil.layers().size(), nullptr);
213
214 for (const int layer_index : grease_pencil.layers().index_range()) {
215 const Drawing *drawing = grease_pencil.get_eval_drawing(grease_pencil.layer(layer_index));
216 if (drawing == nullptr) {
217 continue;
218 }
219 const bke::CurvesGeometry &curves = drawing->strokes();
220 const Span<float3> positions_span = curves.evaluated_positions();
221 if (positions_span.is_empty()) {
222 continue;
223 }
224 mesh_by_layer[layer_index] = hull_from_bullet(nullptr, positions_span);
225 }
226
227 if (mesh_by_layer.is_empty()) {
228 return;
229 }
230
231 auto instances = std::make_unique<bke::Instances>(mesh_by_layer.size());
232 MutableSpan<int> handles = instances->reference_handles_for_write();
233 instances->transforms_for_write().fill(float4x4::identity());
234 for (const int i : mesh_by_layer.index_range()) {
235 Mesh *mesh = mesh_by_layer[i];
236 if (!mesh) {
237 /* Add an empty reference so the number of layers and instances match.
238 * This makes it easy to reconstruct the layers afterwards and keep their attributes.
239 * Although in this particular case we don't propagate the attributes. */
240 handles[i] = instances->add_reference(bke::InstanceReference());
241 continue;
242 }
243 GeometrySet temp_set = GeometrySet::from_mesh(mesh);
244 handles[i] = instances->add_reference(bke::InstanceReference{temp_set});
245 }
246 auto &dst_component = geometry_set.get_component_for_write<InstancesComponent>();
247 GeometrySet new_instances = geometry::join_geometries(
248 {GeometrySet::from_instances(dst_component.release()),
249 GeometrySet::from_instances(std::move(instances))},
250 {});
251 dst_component.replace(new_instances.get_component_for_write<InstancesComponent>().release());
252 geometry_set.replace_grease_pencil(nullptr);
253}
254
255#endif /* WITH_BULLET */
256
258{
259 GeometrySet geometry_set = params.extract_input<GeometrySet>("Geometry"_ustr);
260
261#ifdef WITH_BULLET
262
263 geometry::foreach_real_geometry(geometry_set, [&](GeometrySet &geometry_set) {
264 Mesh *mesh = compute_hull(geometry_set);
265 if (mesh) {
267 }
268 geometry_set.replace_mesh(mesh);
269 if (geometry_set.has_grease_pencil()) {
270 convex_hull_grease_pencil(geometry_set);
271 }
275 });
276
277 params.set_output("Convex Hull"_ustr, std::move(geometry_set));
278#else
280 TIP_("Disabled, Blender was compiled without Bullet"));
282#endif /* WITH_BULLET */
283}
284
285static void node_register()
286{
287 static bke::bNodeType ntype;
288 geo_node_type_base(&ntype, "GeometryNodeConvexHull"_ustr, GEO_NODE_CONVEX_HULL);
289 ntype.ui_name = "Convex Hull";
290 ntype.ui_description =
291 "Create a mesh that encloses all points in the input geometry with the smallest number of "
292 "points";
293 ntype.enum_name_legacy = "CONVEX_HULL";
295 ntype.declare = node_declare;
298}
300
301} // namespace blender::nodes::node_geo_convex_hull_cc
Low-level operations for curves.
Low-level operations for grease pencil.
General operations, lookup, etc. for materials.
#define NODE_CLASS_GEOMETRY
Definition BKE_node.hh:492
#define GEO_NODE_CONVEX_HULL
#define TIP_(msgid)
#define NOD_REGISTER_NODE(REGISTER_FUNC)
struct plConvexHull__ * plConvexHull
#define BLI_assert_unreachable()
#define BLI_assert(a)
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr bool is_empty() const
Definition BLI_span.hh:264
constexpr IndexRange()=default
constexpr bool contains(int64_t value) const
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
Span< float3 > evaluated_positions() const
const bke::CurvesGeometry & strokes() const
void error_message_add(const NodeWarningType type, StringRef message) const
T extract_input(const UString identifier)
void set_output(const UString identifier, T &&value)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
void node_register_type(bNodeType &ntype)
Definition node.cc:2920
void mesh_smooth_set(Mesh &mesh, bool use_smooth, bool keep_sharp_edges=false)
bke::GeometrySet join_geometries(Span< bke::GeometrySet > geometries, const bke::AttributeFilter &attribute_filter, const std::optional< Span< bke::GeometryComponent::Type > > &component_types_to_join=std::nullopt, bool allow_merging_instance_references=true)
void foreach_real_geometry(bke::GeometrySet &geometry, FunctionRef< void(bke::GeometrySet &geometry_set)> fn)
void debug_randomize_mesh_order(Mesh *mesh)
Definition randomize.cc:305
static void node_declare(NodeDeclarationBuilder &b)
static void node_geo_exec(GeoNodeExecParams params)
unsigned int uint
Definition BKE_text.h:55
VecBase< int32_t, 2 > int2
Mesh * BKE_mesh_new_nomain(int verts_num, int edges_num, int faces_num, int corners_num)
void BKE_id_material_eval_ensure_default_slot(ID *id)
Mesh * BKE_mesh_new_nomain_from_template(const Mesh *me_src, int verts_num, int edges_num, int faces_num, int corners_num)
VecBase< float, 3 > float3
void geo_node_type_base(bke::bNodeType *ntype, UString idname, const std::optional< int16_t > legacy_type)
int plConvexHullGetFaceSize(plConvexHull hull, int n)
int plConvexHullNumLoops(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 plConvexHullNumVertices(plConvexHull hull)
int plConvexHullGetReversedLoopIndex(plConvexHull hull, int n)
plConvexHull plConvexHullCompute(float(*coords)[3], int count)
void plConvexHullDelete(plConvexHull hull)
void plConvexHullGetFaceLoops(plConvexHull hull, int n, int *loops)
int plConvexHullNumFaces(plConvexHull hull)
void keep_only(Span< GeometryComponent::Type > component_types)
void replace_mesh(Mesh *mesh, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
void replace_grease_pencil(GreasePencil *grease_pencil, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
Defines a node type.
Definition BKE_node.hh:265
std::string ui_description
Definition BKE_node.hh:271
NodeGeometryExecFunction geometry_node_execute
Definition BKE_node.hh:385
const char * enum_name_legacy
Definition BKE_node.hh:274
NodeDeclareFunction declare
Definition BKE_node.hh:393
static GeometrySet from_mesh(Mesh *mesh, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
static GeometrySet from_instances(std::unique_ptr< Instances > instances)