Blender V5.3
mesh_sample.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
8
10#include "BKE_bvhutils.hh"
11#include "BKE_mesh.hh"
12#include "BKE_mesh_sample.hh"
13
14#include "BLI_array_utils.hh"
15#include "BLI_math_geom_c.hh"
16#include "BLI_rand.hh"
17
19
20template<typename T>
21BLI_NOINLINE static void sample_point_attribute(const Span<int> corner_verts,
22 const Span<int3> corner_tris,
23 const Span<int> tri_indices,
24 const Span<float3> bary_coords,
25 const VArray<T> &src,
26 const IndexMask &mask,
27 const MutableSpan<T> dst)
28{
29 mask.foreach_index(
30 [&](const int i) {
31 const int3 &tri = corner_tris[tri_indices[i]];
32 dst[i] = attribute_math::mix3(bary_coords[i],
33 src[corner_verts[tri[0]]],
34 src[corner_verts[tri[1]]],
35 src[corner_verts[tri[2]]]);
36 },
38}
39
40void sample_point_normals(const Span<int> corner_verts,
41 const Span<int3> corner_tris,
42 const Span<int> tri_indices,
43 const Span<float3> bary_coords,
44 const Span<float3> src,
45 const IndexMask mask,
46 const MutableSpan<float3> dst)
47{
48 mask.foreach_index(
49 [&](const int i) {
50 const int3 &tri = corner_tris[tri_indices[i]];
51 const float3 value = attribute_math::mix3(bary_coords[i],
52 src[corner_verts[tri[0]]],
53 src[corner_verts[tri[1]]],
54 src[corner_verts[tri[2]]]);
55 dst[i] = math::normalize(value);
56 },
58}
59
60void sample_point_attribute(const Span<int> corner_verts,
61 const Span<int3> corner_tris,
62 const Span<int> tri_indices,
63 const Span<float3> bary_coords,
64 const GVArray &src,
65 const IndexMask &mask,
66 const GMutableSpan dst)
67{
68 BLI_assert(src.type() == dst.type());
69
70 const CPPType &type = src.type();
71 attribute_math::to_static_type(type, [&]<typename T>() {
72 if constexpr (!std::is_same_v<T, std::string>) {
73 sample_point_attribute<T>(corner_verts,
74 corner_tris,
75 tri_indices,
76 bary_coords,
77 src.typed<T>(),
78 mask,
79 dst.typed<T>());
80 }
81 });
82}
83
84template<typename T>
85BLI_NOINLINE static void sample_corner_attribute(const Span<int3> corner_tris,
86 const Span<int> tri_indices,
87 const Span<float3> bary_coords,
88 const VArray<T> &src,
89 const IndexMask &mask,
90 const MutableSpan<T> dst)
91{
92 mask.foreach_index(
93 [&](const int i) {
94 const int3 &tri = corner_tris[tri_indices[i]];
95 dst[i] = sample_corner_attribute_with_bary_coords(bary_coords[i], tri, src);
96 },
98}
99
100void sample_corner_normals(const Span<int3> corner_tris,
101 const Span<int> tri_indices,
102 const Span<float3> bary_coords,
103 const Span<float3> src,
104 const IndexMask &mask,
105 const MutableSpan<float3> dst)
106{
107 mask.foreach_index(
108 [&](const int i) {
109 const int3 &tri = corner_tris[tri_indices[i]];
110 const float3 value = sample_corner_attribute_with_bary_coords(bary_coords[i], tri, src);
111 dst[i] = math::normalize(value);
112 },
114}
115
116void sample_corner_attribute(const Span<int3> corner_tris,
117 const Span<int> tri_indices,
118 const Span<float3> bary_coords,
119 const GVArray &src,
120 const IndexMask &mask,
121 const GMutableSpan dst)
122{
123 BLI_assert(src.type() == dst.type());
124
125 const CPPType &type = src.type();
126 attribute_math::to_static_type(type, [&]<typename T>() {
128 corner_tris, tri_indices, bary_coords, src.typed<T>(), mask, dst.typed<T>());
129 });
130}
131
132template<typename T>
133void sample_face_attribute(const Span<int> tri_faces,
134 const Span<int> tri_indices,
135 const VArray<T> &src,
136 const IndexMask &mask,
137 const MutableSpan<T> dst)
138{
139 mask.foreach_index(
140 [&](const int i) {
141 const int tri_index = tri_indices[i];
142 const int face_index = tri_faces[tri_index];
143 dst[i] = src[face_index];
144 },
146}
147
148void sample_face_attribute(const Span<int> corner_tri_faces,
149 const Span<int> tri_indices,
150 const GVArray &src,
151 const IndexMask &mask,
152 const GMutableSpan dst)
153{
154 BLI_assert(src.type() == dst.type());
155
156 const CPPType &type = src.type();
157 attribute_math::to_static_type(type, [&]<typename T>() {
158 sample_face_attribute<T>(corner_tri_faces, tri_indices, src.typed<T>(), mask, dst.typed<T>());
159 });
160}
161
162template<bool check_indices = false>
163static void sample_nearest_corner(const Span<float3> vert_positions,
164 const Span<int> corner_verts,
165 const Span<int3> corner_tris,
166 const Span<int> tri_indices,
167 const Span<float3> sample_positions,
168 const IndexMask &mask,
169 MutableSpan<int> nearest_corner)
170{
171 mask.foreach_index([&](const int i) {
172 if constexpr (check_indices) {
173 if (tri_indices[i] == -1) {
174 nearest_corner[i] = -1;
175 return;
176 }
177 }
178 const int3 &tri = corner_tris[tri_indices[i]];
179 const std::array<float, 3> distances{
180 math::distance_squared(sample_positions[i], vert_positions[corner_verts[tri[0]]]),
181 math::distance_squared(sample_positions[i], vert_positions[corner_verts[tri[1]]]),
182 math::distance_squared(sample_positions[i], vert_positions[corner_verts[tri[2]]]),
183 };
184 const int index = std::min_element(distances.begin(), distances.end()) - distances.begin();
185 nearest_corner[i] = tri[index];
186 });
187}
188
190 const Mesh &mesh,
191 const Span<int> tris_to_sample,
192 const float3 &sample_pos,
193 const float sample_radius,
194 const float approximate_density,
195 Vector<float3> &r_bary_coords,
196 Vector<int> &r_tri_indices,
197 Vector<float3> &r_positions)
198{
199 const Span<float3> positions = mesh.vert_positions();
200 const Span<int> corner_verts = mesh.corner_verts();
201 const Span<int3> corner_tris = mesh.corner_tris();
202
203 const float sample_radius_sq = pow2f(sample_radius);
204 const float sample_plane_area = M_PI * sample_radius_sq;
205 /* Used for switching between two triangle sampling strategies. */
206 const float area_threshold = sample_plane_area;
207
208 const int old_num = r_bary_coords.size();
209
210 for (const int tri_index : tris_to_sample) {
211 const int3 &tri = corner_tris[tri_index];
212
213 const float3 &v0 = positions[corner_verts[tri[0]]];
214 const float3 &v1 = positions[corner_verts[tri[1]]];
215 const float3 &v2 = positions[corner_verts[tri[2]]];
216
217 const float corner_tri_area = area_tri_v3(v0, v1, v2);
218
219 if (corner_tri_area < area_threshold) {
220 /* The triangle is small compared to the sample radius. Sample by generating random
221 * barycentric coordinates. */
222 const int amount = rng.round_probabilistic(approximate_density * corner_tri_area);
223 for ([[maybe_unused]] const int i : IndexRange(amount)) {
225 const float3 point_pos = attribute_math::mix3(bary_coord, v0, v1, v2);
226 const float dist_to_sample_sq = math::distance_squared(point_pos, sample_pos);
227 if (dist_to_sample_sq > sample_radius_sq) {
228 continue;
229 }
230
231 r_bary_coords.append(bary_coord);
232 r_tri_indices.append(tri_index);
233 r_positions.append(point_pos);
234 }
235 }
236 else {
237 /* The triangle is large compared to the sample radius. Sample by generating random points
238 * on the triangle plane within the sample radius. */
239 float3 normal;
240 normal_tri_v3(normal, v0, v1, v2);
241
242 float3 sample_pos_proj = sample_pos;
243 project_v3_plane(sample_pos_proj, normal, v0);
244
245 const float proj_distance_sq = math::distance_squared(sample_pos_proj, sample_pos);
246 const float sample_radius_factor_sq = 1.0f -
247 std::min(1.0f, proj_distance_sq / sample_radius_sq);
248 const float radius_proj_sq = sample_radius_sq * sample_radius_factor_sq;
249 const float radius_proj = std::sqrt(radius_proj_sq);
250 const float circle_area = M_PI * radius_proj_sq;
251
252 const int amount = rng.round_probabilistic(approximate_density * circle_area);
253
254 const float3 axis_1 = math::normalize(v1 - v0) * radius_proj;
255 const float3 axis_2 = math::normalize(math::cross(axis_1, math::cross(axis_1, v2 - v0))) *
256 radius_proj;
257
258 for ([[maybe_unused]] const int i : IndexRange(amount)) {
259 const float r = std::sqrt(rng.get_float());
260 const float angle = rng.get_float() * 2.0f * M_PI;
261 const float x = r * std::cos(angle);
262 const float y = r * std::sin(angle);
263 const float3 point_pos = sample_pos_proj + axis_1 * x + axis_2 * y;
264 if (!isect_point_tri_prism_v3(point_pos, v0, v1, v2)) {
265 /* Sampled point is not in the triangle. */
266 continue;
267 }
268
270 interp_weights_tri_v3(bary_coord, v0, v1, v2, point_pos);
271
272 r_bary_coords.append(bary_coord);
273 r_tri_indices.append(tri_index);
274 r_positions.append(point_pos);
275 }
276 }
277 }
278 return r_bary_coords.size() - old_num;
279}
280
283 const Mesh &mesh,
284 const bke::bvh::Tree &mesh_bvhtree,
285 const float2 &sample_pos_re,
286 const float sample_radius_re,
287 const FunctionRef<void(const float2 &pos_re, float3 &r_start, float3 &r_end)>
288 region_position_to_ray,
289 const bool front_face_only,
290 const int tries_num,
291 const int max_points,
292 Vector<float3> &r_bary_coords,
293 Vector<int> &r_tri_indices,
294 Vector<float3> &r_positions)
295{
296 const Span<float3> positions = mesh.vert_positions();
297 const Span<int> corner_verts = mesh.corner_verts();
298 const Span<int3> corner_tris = mesh.corner_tris();
299
300 int point_count = 0;
301 for ([[maybe_unused]] const int _ : IndexRange(tries_num)) {
302 if (point_count == max_points) {
303 break;
304 }
305
306 const float r = sample_radius_re * std::sqrt(rng.get_float());
307 const float angle = rng.get_float() * 2.0f * M_PI;
308 float3 ray_start, ray_end;
309 const float2 pos_re = sample_pos_re + r * float2(std::cos(angle), std::sin(angle));
310 region_position_to_ray(pos_re, ray_start, ray_end);
311 const float3 ray_direction = math::normalize(ray_end - ray_start);
312
313 const bke::bvh::Ray ray(ray_start, ray_direction);
314 const std::optional<bke::bvh::RayHit> ray_hit = mesh_bvhtree.ray_intersect(ray);
315 if (!ray_hit) {
316 continue;
317 }
318
319 if (front_face_only) {
320 const float3 normal = math::normalize(ray_hit->normal);
321 if (math::dot(ray_direction, normal) >= 0.0f) {
322 continue;
323 }
324 }
325
326 const int tri_index = ray_hit->index;
327 const float3 pos = ray_hit->position(ray);
328
329 const float3 bary_coords = compute_bary_coord_in_triangle(
330 positions, corner_verts, corner_tris[tri_index], pos);
331
332 r_positions.append(pos);
333 r_bary_coords.append(bary_coords);
334 r_tri_indices.append(tri_index);
335 point_count++;
336 }
337 return point_count;
338}
339
341 const Span<int> corner_verts,
342 const int3 &tri,
343 const float3 &position)
344{
345 const float3 &v0 = vert_positions[corner_verts[tri[0]]];
346 const float3 &v1 = vert_positions[corner_verts[tri[1]]];
347 const float3 &v2 = vert_positions[corner_verts[tri[2]]];
348 float3 bary_coords;
349 interp_weights_tri_v3(bary_coords, v0, v1, v2, position);
350 return bary_coords;
351}
352
354 : source_(std::move(geometry))
355{
356 source_.ensure_owns_direct_data();
357 static const mf::Signature signature = []() {
358 mf::Signature signature;
359 mf::SignatureBuilder builder{"Nearest Weight from Position", signature};
360 builder.single_input<float3>("Position");
361 builder.single_input<int>("Triangle Index");
362 builder.single_output<int>("Nearest Corner");
363 return signature;
364 }();
365 this->set_signature(&signature);
366 const Mesh &mesh = *source_.get_mesh();
367 vert_positions_ = mesh.vert_positions();
368 corner_verts_ = mesh.corner_verts();
369 corner_tris_ = mesh.corner_tris();
370}
371
373 mf::Params params,
374 mf::Context /*context*/) const
375{
376 const VArraySpan<float3> sample_positions = params.readonly_single_input<float3>(0, "Position");
377 const VArraySpan<int> triangle_indices = params.readonly_single_input<int>(1, "Triangle Index");
378 MutableSpan<int> nearest_corner = params.uninitialized_single_output<int>(2, "Nearest Corner");
379 sample_nearest_corner<true>(vert_positions_,
380 corner_verts_,
381 corner_tris_,
382 triangle_indices,
383 sample_positions,
384 mask,
385 nearest_corner);
386}
387
389{
390 static constexpr int8_t id = 0;
391 hash.add(&id);
392 hash.add(source_.get_mesh());
393}
394
396 : source_(std::move(geometry)), src_field_(std::move(src_field))
397{
398 source_.ensure_owns_direct_data();
399 mf::SignatureBuilder builder{"Sample Barycentric Triangles", signature_};
400 builder.single_input<int>("Triangle Index");
401 builder.single_input<float3>("Barycentric Weight");
402 builder.single_output("Value", src_field_.cpp_type());
403 this->set_signature(&signature_);
404}
405
407 mf::Params params,
408 mf::Context /*context*/) const
409{
410 const VArraySpan<int> triangle_indices = params.readonly_single_input<int>(0, "Triangle Index");
411 const VArraySpan<float3> bary_weights = params.readonly_single_input<float3>(
412 1, "Barycentric Weight");
413 GMutableSpan dst = params.uninitialized_single_output(2, "Value");
414 IndexMaskMemory memory;
415 const IndexMask valid_mask = array_utils::indices_non_negative(mask, triangle_indices, memory);
416 switch (src_domain_) {
418 sample_point_attribute(corner_verts_,
419 corner_tris_,
420 triangle_indices,
421 bary_weights,
422 *source_data_,
423 valid_mask,
424 dst);
425 break;
426 case AttrDomain::Face:
427 sample_face_attribute(tri_faces_, triangle_indices, *source_data_, valid_mask, dst);
428 break;
431 corner_tris_, triangle_indices, bary_weights, *source_data_, valid_mask, dst);
432 break;
433 default:
435 break;
436 }
437 dst.type().value_initialize_indices(dst.data(), valid_mask.complement(mask, memory));
438}
439
441{
442 static constexpr int8_t id = 0;
443 hash.add(&id);
444 hash.add(source_.get_mesh());
445 fn::FieldHashDeep field_hash;
446 hash.add(field_hash.ensure(src_field_));
447}
448
450{
451 mutex_.ensure([&]() {
452 const auto &component = *source_.get_component<bke::MeshComponent>();
453 const Mesh &mesh = *component.get();
454 corner_verts_ = mesh.corner_verts();
455 corner_tris_ = mesh.corner_tris();
456 src_domain_ =
457 bke::try_detect_native_field_domain(component, src_field_).value_or(AttrDomain::Corner);
458 if (src_domain_ == AttrDomain::Edge) {
459 /* To maintain legacy behavior and avoid making decisions here about barycentric mixing of
460 * edge attributes, just use the domain interpolation to read the attribute on the face
461 * corner domain. */
462 src_domain_ = AttrDomain::Corner;
463 }
464 else if (src_domain_ == AttrDomain::Face) {
465 tri_faces_ = mesh.corner_tri_faces();
466 }
467 source_context_.emplace(MeshFieldContext(mesh, src_domain_));
468 const int domain_size = mesh.attributes().domain_size(src_domain_);
469 source_evaluator_ = std::make_unique<fn::FieldEvaluator>(*source_context_, domain_size);
470 source_evaluator_->add(src_field_);
471 source_evaluator_->evaluate();
472 source_data_ = &source_evaluator_->get_evaluated(0);
473 });
474}
475
476} // namespace blender::bke::mesh_surface_sample
#define M_PI
#define BLI_assert_unreachable()
#define BLI_NOINLINE
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
const CPPType & type() const
MutableSpan< T > typed() const
constexpr IndexRange()=default
int round_probabilistic(float x)
Definition rand.cc:306
int64_t size() const
void append(const T &value)
MeshFieldContext(const Mesh &mesh, AttrDomain domain)
std::optional< RayHit > ray_intersect(const Ray &ray) const
Definition bvh.cc:439
void call(const IndexMask &mask, mf::Params params, mf::Context context) const override
void hash_unique(UniqueHashBytes &hash) const override
BaryWeightSampleFn(GeometrySet geometry, fn::GField src_field)
void hash_unique(UniqueHashBytes &hash) const override
void call(const IndexMask &mask, mf::Params params, mf::Context context) const override
void set_signature(const Signature *signature)
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
#define position
#define bary_coord
#define T
IndexMask indices_non_negative(const IndexMask &universe, Span< int > values, LinearAllocator<> &memory)
T mix3(const float3 &weights, const T &v0, const T &v1, const T &v2)
void to_static_type(const CPPType &cpp_type, Fn &&fn)
int sample_surface_points_spherical(RandomNumberGenerator &rng, const Mesh &mesh, Span< int > tris_to_sample, const float3 &sample_pos, float sample_radius, float approximate_density, Vector< float3 > &r_bary_coords, Vector< int > &r_tri_indices, Vector< float3 > &r_positions)
int sample_surface_points_projected(RandomNumberGenerator &rng, const Mesh &mesh, const bke::bvh::Tree &mesh_bvhtree, const float2 &sample_pos_re, float sample_radius_re, FunctionRef< void(const float2 &pos_re, float3 &r_start, float3 &r_end)> region_position_to_ray, bool front_face_only, int tries_num, int max_points, Vector< float3 > &r_bary_coords, Vector< int > &r_tri_indices, Vector< float3 > &r_positions)
void sample_corner_normals(Span< int3 > corner_tris, Span< int > tri_indices, Span< float3 > bary_coords, Span< float3 > src, const IndexMask &mask, MutableSpan< float3 > dst)
static void sample_nearest_corner(const Span< float3 > vert_positions, const Span< int > corner_verts, const Span< int3 > corner_tris, const Span< int > tri_indices, const Span< float3 > sample_positions, const IndexMask &mask, MutableSpan< int > nearest_corner)
void sample_point_attribute(Span< int > corner_verts, Span< int3 > corner_tris, Span< int > tri_indices, Span< float3 > bary_coords, const GVArray &src, const IndexMask &mask, GMutableSpan dst)
float3 compute_bary_coord_in_triangle(Span< float3 > vert_positions, Span< int > corner_verts, const int3 &corner_tri, const float3 &position)
void sample_corner_attribute(Span< int3 > corner_tris, Span< int > tri_indices, Span< float3 > bary_coords, const GVArray &src, const IndexMask &mask, GMutableSpan dst)
void sample_face_attribute(Span< int > corner_tri_faces, Span< int > tri_indices, const GVArray &src, const IndexMask &mask, GMutableSpan dst)
T sample_corner_attribute_with_bary_coords(const float3 &bary_weights, const int3 &corner_tri, const Span< T > corner_attribute)
void sample_point_normals(Span< int > corner_verts, Span< int3 > corner_tris, Span< int > tri_indices, Span< float3 > bary_coords, Span< float3 > src, IndexMask mask, MutableSpan< float3 > dst)
std::optional< AttrDomain > try_detect_native_field_domain(const GeometryComponent &component, const fn::GField &field)
constexpr ParallelGrainSize grain_size(int grain_size)
T dot(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
AxisSigned cross(const AxisSigned a, const AxisSigned b)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void project_v3_plane(float out[3], const float plane_no[3], const float plane_co[3])
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
MINLINE float pow2f(float x)
VecBase< float, 2 > float2
VecBase< int32_t, 3 > int3
void interp_weights_tri_v3(float w[3], const float v1[3], const float v2[3], const float v3[3], const float co[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:104
bool isect_point_tri_prism_v3(const float p[3], const float v1[3], const float v2[3], const float v3[3])
VecBase< float, 3 > float3
signed char int8_t
Definition BKE_text.h:76
#define hash
Definition noise_c.cc:156
UniqueHash ensure(const GFieldRef &field)
Definition field.cc:113