Blender V5.3
bmo_circularize.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10#include "BLI_kdopbvh.hh"
11#include "BLI_listbase.hh"
12#include "BLI_map.hh"
13#include "BLI_math_geom_c.hh"
14#include "BLI_math_matrix.hh"
15#include "BLI_math_matrix_c.hh"
16#include "BLI_math_vector.hh"
17#include "BLI_span.hh"
18#include "BLI_vector.hh"
19
20#include <numbers>
21#include <optional>
22
23#include "bmesh.hh"
24#include "intern/bmesh_operators_private.hh" /* own include */
25
26namespace blender {
27
31constexpr float MIRROR_LIMIT = 0.001f;
33constexpr float CIRCULARIZE_EPSILON = 1e-6f;
34
37
46
56
66 const char hflag,
67 const bool check_axis[3],
68 bool extract_wire_edges)
69{
71 return false;
72 }
73
74 if (extract_wire_edges ? e->l != nullptr : e->l == nullptr) {
75 return false;
76 }
77
78 int selected_face_count = 0;
79 BMIter fiter;
80 BMFace *f;
81 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
83 selected_face_count++;
84 if (selected_face_count > 1) {
85 break;
86 }
87 }
88 }
89
90 if (selected_face_count > 1) {
91 return false;
92 }
93
94 /* If both vertices of an edge lie close to the same coordinate plane
95 * (X = 0, Y = 0, or Z = 0), the edge lies on a mirror plane and is not
96 * considered a valid boundary edge. */
97 for (int i = 0; i < 3; i++) {
98 if (check_axis[i] && std::abs(e->v1->co[i]) < MIRROR_LIMIT &&
99 std::abs(e->v2->co[i]) < MIRROR_LIMIT)
100 {
101 return false;
102 }
103 }
104
105 return true;
106}
107
110 Vector<VertChain> &r_chains,
111 const char hflag,
112 const bool check_axis[3],
113 bool extract_wire_edges)
114{
115 ListBaseT<BMEdgeLoopStore> eloops = {nullptr};
116 const BMEdgeLoopFind_Params params = {
117 .use_vert_junction = true,
118 };
119
121 bm,
122 &eloops,
123 [&](BMEdge *e) { return is_valid_boundary_edge(e, hflag, check_axis, extract_wire_edges); },
124 &params);
125
126 for (BMEdgeLoopStore &el_store : eloops) {
127 VertChain chain;
128 chain.is_closed = BM_edgeloop_is_closed(&el_store);
129 chain.is_wire = extract_wire_edges;
130 for (LinkData &node : *BM_edgeloop_verts_get(&el_store)) {
131 chain.verts.append(static_cast<BMVert *>(node.data));
132 }
133
134 /* Reject wire edge chains that touch a face region. Wire edges are only circularized if they
135 * are completely isolated. */
136 if (extract_wire_edges) {
137 bool touches_face_region = false;
138 for (BMVert *v : chain.verts) {
139 BMIter eiter;
140 BMEdge *e_other;
141 BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
142 if (BM_elem_flag_test(e_other, hflag) && e_other->l != nullptr) {
143 touches_face_region = true;
144 break;
145 }
146 }
147 if (touches_face_region) {
148 break;
149 }
150 }
151 if (touches_face_region) {
152 continue;
153 }
154 }
155
156 if (chain.verts.size() >= 3) {
157 r_chains.append(std::move(chain));
158 }
159 }
160
161 BM_mesh_edgeloops_free(&eloops);
162}
163
169 float3 &r_center,
170 float3x3 &r_mat)
171{
172 r_center = float3(0.0f);
173 for (BMVert *v : chain) {
174 r_center += float3(v->co);
175 }
176 r_center /= float(chain.size());
177 BMVert *prev = chain.last();
178
179 float3 normal = float3(0.0f);
180 /* Compute a best fit plane normal for the chain using Newell's method. */
181 for (BMVert *curr : chain) {
182 add_newell_cross_v3_v3v3(normal, prev->co, curr->co);
183 prev = curr;
184 }
185
186 if (math::length(normal) < CIRCULARIZE_EPSILON) {
187 return false;
188 }
189
190 normal = math::normalize(normal);
191 r_mat = math::from_up_axis<float3x3>(normal);
192 return true;
193}
194
197 const float3 &center,
198 const float3x3 &mat,
199 Vector<CircleVert> &r_2d_verts)
200{
201 r_2d_verts.reserve(chain.size());
202 for (BMVert *v : chain) {
203 float3 vec = float3(v->co) - center;
204 CircleVert cv{.v = v, .co_2d = {math::dot(vec, mat.x_axis()), math::dot(vec, mat.y_axis())}};
205 r_2d_verts.append(cv);
206 }
207}
208
210 const std::optional<float2> &fixed_center,
211 float2 &r_center,
212 float *r_radius)
213{
214 /* If the center is locked, we skip the solver. The best fit for the fixed center
215 * is simply the average radius. */
216 if (fixed_center.has_value()) {
217 r_center = *fixed_center;
218 float radius = 0.0f;
219 for (const CircleVert &cv : verts) {
220 radius += math::length(cv.co_2d);
221 }
222 radius /= verts.size();
223 *r_radius = radius;
224 return;
225 }
226
227 /* Initial guesses. */
228 float2 initial_center = float2(0.0f);
229 float initial_radius = 1.0f;
230 bool converged = false;
231
232 for (int iter = 0; iter < NON_LINEAR_LEAST_SQUARES_MAX_ITERATIONS; iter++) {
233 float3x3 normal_matrix = float3x3::zero();
234 float3 jacobian_transpose_residual = float3(0.0f);
235
236 for (const CircleVert &cv : verts) {
237 const float2 d_vec = initial_center - cv.co_2d;
238 const float distance = math::length(d_vec);
240 continue;
241 }
242 const float3 j_row = {d_vec / distance, -1.0f};
243 const float residual = initial_radius - distance;
244
245 for (int row = 0; row < 3; row++) {
246 for (int col = 0; col < 3; col++) {
247 normal_matrix[col][row] += j_row[row] * j_row[col];
248 }
249 jacobian_transpose_residual[row] += j_row[row] * residual;
250 }
251 }
252 bool success;
253 float3x3 inverse_normal_matrix = math::invert(normal_matrix, success);
254 if (!success) {
255 break;
256 }
257
258 float3 delta = inverse_normal_matrix * jacobian_transpose_residual;
259
260 initial_center.x += delta.x;
261 initial_center.y += delta.y;
262 initial_radius += delta.z;
263
264 /* Check for convergence to stop iterating if we're close enough to the optimal
265 * solution. */
266 if (std::abs(delta.x) < CIRCULARIZE_EPSILON && std::abs(delta.y) < CIRCULARIZE_EPSILON &&
267 std::abs(delta.z) < CIRCULARIZE_EPSILON)
268 {
269 converged = true;
270 break;
271 }
272 }
273
274 if (!converged) {
275 /* Fallback for the best fit circle in the scenario that the Gauss-Newton solver
276 * fails to converge. */
277 initial_center = float2(0.0f);
278 initial_radius = 0.0f;
279 for (const CircleVert &cv : verts) {
280 initial_radius += math::length(cv.co_2d);
281 }
282 initial_radius /= verts.size();
283 }
284
285 r_center = initial_center;
286 *r_radius = initial_radius;
287}
288
290 const std::optional<float2> &fixed_center,
291 float2 &r_center,
292 float *r_radius)
293{
294 float2 center;
295 if (fixed_center.has_value()) {
296 center = *fixed_center;
297 }
298 else {
299 float total_edge_length = 0.0f;
300 center = float2(0.0f);
301 float2 prev_co = verts.last().co_2d;
302
303 for (const CircleVert &cv : verts) {
304 const float2 &curr_co = cv.co_2d;
305 const float edge_length = math::distance(prev_co, curr_co);
306 center += (prev_co + curr_co) * edge_length;
307 total_edge_length += edge_length;
308 prev_co = curr_co;
309 }
310 if (total_edge_length != 0.0f) {
311 center *= (0.5f / total_edge_length);
312 }
313 }
314
315 float radius_sq = FLT_MAX;
316 for (const CircleVert &cv : verts) {
317 const float dist_sq = math::distance_squared(center, cv.co_2d);
318 radius_sq = std::min(radius_sq, dist_sq);
319 }
320
321 r_center = center;
322 *r_radius = math::sqrt(radius_sq);
323}
324
326 const float2 &center,
327 const float radius,
328 const bool is_regular,
329 const bool is_closed,
330 const float rotation_angle)
331{
332 float step = 0.0f;
333 float start_angle = 0.0f;
334
335 if (is_regular) {
336 float total_angle = 2.0f * std::numbers::pi_v<float>;
337 int divisions = verts.size();
338
339 /* For open chains, we calculate the total angle obtained by traversing
340 * the vertices. Unlike closed chains whose total angle is 2*Pi,
341 * we cannot assume Pi for an open chain because it might span any amount
342 * of the circle. */
343 if (!is_closed && divisions > 1) {
344 total_angle = 0.0f;
345 divisions = verts.size() - 1;
346
347 float2 vec_prev = verts[0].co_2d - center;
348 vec_prev = math::normalize(vec_prev);
349 /* Skip the first vertex because it was used to initialize vec_prev otherwise
350 * we'll end up with a self comparison in the first iteration. */
351 for (const int i : verts.index_range().drop_front(1)) {
352 float2 vec_curr = verts[i].co_2d - center;
353 vec_curr = math::normalize(vec_curr);
354
355 total_angle -= angle_signed_v2v2(vec_prev, vec_curr);
356 vec_prev = vec_curr;
357 }
358 /* In case the angle exceeds a full revolution, clamp it to the max angle. */
359 const float max_angle = 2.0f * std::numbers::pi_v<float>;
360 total_angle = std::clamp(total_angle, -max_angle, max_angle);
361 }
362
363 step = total_angle / divisions;
364 float sum_sin = 0.0f;
365 float sum_cos = 0.0f;
366
367 /* Using only one vertex as the basis for the start angle can skew
368 * the resulting rotation of the circle in an undesirable way.
369 * So instead, we calculate the circular mean of the rotation by measuring
370 * the angular deviation for every vertex and averaging them to find the best
371 * fit alignment.
372 * Note: We accumulate the sine and cosine of the angular deviations to calculate
373 * the circular mean because angles wrap around 360 degrees, and averaging them directly
374 * would give incorrect results. */
375 for (const int i : verts.index_range()) {
376 float2 vec = verts[i].co_2d - center;
377 const float angle_diff = atan2f(vec.y, vec.x) - (step * i);
378 sum_sin += sinf(angle_diff);
379 sum_cos += cosf(angle_diff);
380 }
381 start_angle = atan2f(sum_sin, sum_cos);
382 }
383
384 for (const int i : verts.index_range()) {
385 float angle;
386
387 if (is_regular) {
388 angle = start_angle + step * i - rotation_angle;
389 }
390 else {
391 float2 vec = verts[i].co_2d - center;
392 angle = atan2f(vec.y, vec.x) - rotation_angle;
393 }
394
395 verts[i].target_2d.x = center.x + cosf(angle) * radius;
396 verts[i].target_2d.y = center.y + sinf(angle) * radius;
397 }
398}
399
403
405static void nearest_tri_cb(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
406{
407 const NearestTriUserData *data = static_cast<const NearestTriUserData *>(userdata);
408 const std::array<BMLoop *, 3> &ltri = data->looptris[index];
409
411 closest_on_tri_to_point_v3(closest, co, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co);
412 const float dist_sq = math::distance_squared(float3(co), closest);
413 if (dist_sq < nearest->dist_sq) {
414 nearest->dist_sq = dist_sq;
415 nearest->index = index;
416 copy_v3_v3(nearest->co, closest);
417 }
418}
419
421
422static void project_on_mesh(BVHTree *bvh_tree,
423 NearestTriUserData *bvh_data,
424 BMVert *v,
425 const float3 &center_pos,
426 const float3 &normal,
427 float3 &r_pos,
428 FaceTessellationCache &tess_cache)
429{
430 float3 vec = center_pos - float3(v->co);
431 float length;
433 /* If vertices are too close, normalization can fail. */
434 if (length == 0.0f) {
435 r_pos = center_pos;
436 return;
437 }
438 const float angle = angle_normalized_v3v3(vec, normal);
439 if (std::abs(angle) < CIRCULARIZE_EPSILON ||
440 std::abs(std::numbers::pi_v<float> - angle) < CIRCULARIZE_EPSILON)
441 {
442 r_pos = float3(v->co);
443 return;
444 }
445
446 float3 p2 = center_pos + normal;
447 float best_dist_sq = FLT_MAX;
448 bool found = false;
449
450 auto test_tri_fn = [&](BMVert *v1, BMVert *v2, BMVert *v3) {
451 float lambda;
452 float2 uv;
453 if (isect_line_tri_v3(center_pos, p2, v1->co, v2->co, v3->co, &lambda, uv)) {
454 float3 hit_pos = center_pos + normal * lambda;
455 const float dist_sq = math::distance_squared(center_pos, hit_pos);
456 if (dist_sq < best_dist_sq) {
457 best_dist_sq = dist_sq;
458 r_pos = hit_pos;
459 found = true;
460 }
461 }
462 };
463
464 BMIter fiter;
465 BMFace *f;
466 BM_ITER_ELEM (f, &fiter, v, BM_FACES_OF_VERT) {
467 if (f->len < 3 || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
468 continue;
469 }
470 if (ELEM(f->len, 3, 4)) {
471 BMLoop *l_start = f->l_first;
472 BMVert *v1 = l_start->prev->v;
473 BMVert *v2 = l_start->v;
474 BMVert *v3 = l_start->next->v;
475 test_tri_fn(v1, v2, v3);
476
477 if (f->len == 4) {
478 BMVert *v4 = l_start->next->next->v;
479 test_tri_fn(v1, v3, v4);
480 }
481 }
482 else {
483 const Array<std::array<BMVert *, 3>> &cached = tess_cache.lookup_or_add_cb(f, [&]() {
484 const int tottri = f->len - 2;
488 f, false, loops.data(), reinterpret_cast<uint(*)[3]>(index.data()));
489 Array<std::array<BMVert *, 3>> tris(tottri);
490 for (int i = 0; i < tottri; i++) {
491 tris[i] = {loops[index[i][0]]->v, loops[index[i][1]]->v, loops[index[i][2]]->v};
492 }
493 return tris;
494 });
495 for (const std::array<BMVert *, 3> &tri : cached) {
496 test_tri_fn(tri[0], tri[1], tri[2]);
497 }
498 }
499 }
500
501 if (found) {
502 return;
503 }
504
505 BMIter eiter;
506 BMEdge *e;
507 BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
509 closest_to_line_v3(closest, center_pos, e->v1->co, e->v2->co);
510 const float fac = line_point_factor_v3(closest, e->v1->co, e->v2->co);
511 if (fac > CIRCULARIZE_EPSILON && fac < 1.0f - CIRCULARIZE_EPSILON) {
512 const float dist_sq = math::distance_squared(center_pos, closest);
513 if (dist_sq < best_dist_sq) {
514 best_dist_sq = dist_sq;
515 r_pos = closest;
516 found = true;
517 }
518 }
519 }
520
521 if (found) {
522 return;
523 }
524
525 if (bvh_tree) {
526 BVHTreeNearest nearest;
527 nearest.dist_sq = FLT_MAX;
528 nearest.index = -1;
529 BLI_bvhtree_find_nearest(bvh_tree, center_pos, &nearest, nearest_tri_cb, bvh_data);
530 if (nearest.index != -1) {
531 r_pos = float3(nearest.co);
532 return;
533 }
534 }
535
536 r_pos = center_pos;
537}
538
540{
541 const float factor = BMO_slot_float_get(op->slots_in, "factor");
542 const float custom_radius = BMO_slot_float_get(op->slots_in, "custom_radius");
543 const float angle = BMO_slot_float_get(op->slots_in, "angle");
544 const int fit_method = BMO_slot_int_get(op->slots_in, "fit_method");
545 const float flatten = BMO_slot_float_get(op->slots_in, "flatten");
546 const bool regular = BMO_slot_bool_get(op->slots_in, "regular");
547
548 const bool check_axis[3] = {
549 BMO_slot_bool_get(op->slots_in, "mirror_x"),
550 BMO_slot_bool_get(op->slots_in, "mirror_y"),
551 BMO_slot_bool_get(op->slots_in, "mirror_z"),
552 };
553
554 const bool lock_x = BMO_slot_bool_get(op->slots_in, "lock_x");
555 const bool lock_y = BMO_slot_bool_get(op->slots_in, "lock_y");
556 const bool lock_z = BMO_slot_bool_get(op->slots_in, "lock_z");
557
560 bm, op->slots_in, "geom", BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false);
561
562 Vector<VertChain> chains;
563
564 /* Uses two passes to detect if edges are wire edges or they have face regions.
565 * Wire edges are rejected in the first pass but included in the second pass. */
566 for (const bool extract_wire_edges : {false, true}) {
567 if (!extract_wire_edges && bm->totface == 0) {
568 continue;
569 }
571 bm, chains, BM_ELEM_TAG, check_axis, extract_wire_edges);
572 }
573
574 /* Builds a BVH tree when flatten is disabled. Without this we would have to iterate
575 * over every face in the mesh for every vertex which is too slow.
576 *
577 * Note: There is the possibility of a feedback loop here, with the geometry
578 * being manipulated which is used in the BVH tree. However, in practice this
579 * is an acceptable limitation that is unlikely to cause problems. */
581 BVHTree *bvh_tree = nullptr;
582 NearestTriUserData bvh_data = {};
583 FaceTessellationCache tess_cache;
584
585 if ((flatten < 1.0f) && (bm->totface > 0)) {
586 const int tot_tri = poly_to_tri_count(bm->totface, bm->totloop);
587 looptris.reinitialize(tot_tri);
588 BM_mesh_calc_tessellation(bm, looptris);
589
590 bvh_tree = BLI_bvhtree_new(tot_tri, 0.0f, 8, 8);
591 for (const int i : looptris.index_range()) {
592 const std::array<BMLoop *, 3> &ltri = looptris[i];
593 float3 tri_coords[3] = {
594 float3(ltri[0]->v->co), float3(ltri[1]->v->co), float3(ltri[2]->v->co)};
595 BLI_bvhtree_insert(bvh_tree, i, reinterpret_cast<float *>(tri_coords), 3);
596 }
597 BLI_bvhtree_balance(bvh_tree);
598 bvh_data.looptris = looptris;
599 }
600
601 for (VertChain &chain_data : chains) {
602 Vector<BMVert *> &chain = chain_data.verts;
603 float3 normal_accum = float3(0.0f);
604 for (BMVert *v : chain) {
605 normal_accum += float3(v->no);
606 }
607 float3 center_3d;
608 float3x3 mat;
609 if (!bm_vert_chain_orientation_matrix_calc(chain, center_3d, mat)) {
611 bm, op, BMO_ERROR_CANCEL, "Selection requires at least 3 non-collinear vertices");
612 return;
613 }
614
615 /* Reverse the chain winding if the Newell normal opposes the cumulative vertex normal. */
616 if (math::dot(mat.z_axis(), normal_accum) < 0.0f) {
617 std::reverse(chain.begin(), chain.end());
618 if (!bm_vert_chain_orientation_matrix_calc(chain, center_3d, mat)) {
620 bm, op, BMO_ERROR_CANCEL, "Selection requires at least 3 non-collinear vertices");
621 return;
622 }
623 }
624
625 bool is_mirrored = false;
626 int mirror_axis = -1;
627
628 if (!chain_data.is_closed) {
629 BMVert *v_start = chain.first();
630 BMVert *v_end = chain.last();
631
632 for (int i = 0; i < 3; i++) {
633 if (check_axis[i] && std::abs(v_start->co[i]) < MIRROR_LIMIT &&
634 std::abs(v_end->co[i]) < MIRROR_LIMIT)
635 {
636 is_mirrored = true;
637 mirror_axis = i;
638 }
639 }
640 }
641
642 /* For open chains on a symmetry plane, force the center to the midpoint of the endpoints
643 * to keep the circle aligned with the mirror plane. */
644 if (is_mirrored) {
645 BMVert *v_start = chain.first();
646 BMVert *v_end = chain.last();
647
648 center_3d = math::midpoint(float3(v_start->co), float3(v_end->co));
649 float3 p = math::normalize(float3(v_start->co) - center_3d);
651 mat.x_axis() = p;
652 mat.y_axis() = q;
653 }
654
655 Vector<CircleVert> circle_verts;
656 project_chain_to_2d(chain, center_3d, mat, circle_verts);
657
658 float2 circle_center_2d;
659 float radius;
660
661 std::optional<float2> fixed_center = std::nullopt;
662 if (is_mirrored) {
663 fixed_center = float2(0.0f);
664 }
665
666 if (fit_method == FIT_METHOD_CONTRACT) {
667 calculate_circle_inside_fit(circle_verts, fixed_center, circle_center_2d, &radius);
668 }
669 else {
670 calculate_circle_best_fit(circle_verts, fixed_center, circle_center_2d, &radius);
671 }
672
673 if (custom_radius > 0.0f) {
674 radius = custom_radius;
675 }
676
678 circle_verts, circle_center_2d, radius, regular, chain_data.is_closed, angle);
679
680 for (const CircleVert &cv : circle_verts) {
681 const float3 target_local(cv.target_2d.x, cv.target_2d.y, 0.0f);
682 float3 final_pos = center_3d + mat * target_local;
683
684 /* Projecting the circle onto the mesh only makes sense for edge chains
685 * that have faces attached. */
686 if (flatten < 1.0f && !chain_data.is_wire) {
687 float3 projected_pos;
689 bvh_tree, &bvh_data, cv.v, final_pos, mat.z_axis(), projected_pos, tess_cache);
690 interp_v3_v3v3(final_pos, projected_pos, final_pos, flatten);
691 }
692
693 /* If this vertex is an endpoint of a mirrored chain, force it
694 * exactly to 0.0 on the mirror axis.
695 * There are some cases where a slight floating point drift ends up being
696 * produced which prevents the mirror modifier from merging vertices. */
697 if (is_mirrored) {
698 BLI_assert(mirror_axis != -1);
699 if (cv.v == chain.first() || cv.v == chain.last()) {
700 final_pos[mirror_axis] = 0.0f;
701 }
702 }
703
704 /* If an axis is locked, restore the original coordinate. */
705 if (lock_x || lock_y || lock_z) {
706 const float *orig = cv.v->co;
707 if (lock_x) {
708 final_pos.x = orig[0];
709 }
710 if (lock_y) {
711 final_pos.y = orig[1];
712 }
713 if (lock_z) {
714 final_pos.z = orig[2];
715 }
716 }
717
718 interp_v3_v3v3(cv.v->co, cv.v->co, final_pos, factor);
719 }
720 }
721
722 /* There would be a memory leak if this isn't freed. */
723 if (bvh_tree) {
724 BLI_bvhtree_free(bvh_tree);
725 }
726}
727
728} // namespace blender
#define ELEM(...)
#define BM_DEFAULT_NGON_STACK_SIZE
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
bool closest(btVector3 &v)
const T * data() const
Definition BLI_array.hh:323
Value & lookup_or_add_cb(const Key &key, const CreateValueF &create_value)
Definition BLI_map.hh:620
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr const T & last(const int64_t n=0) const
Definition BLI_span.hh:329
void append(const T &value)
const T & last(const int64_t n=0) const
IndexRange index_range() const
void reserve(const int64_t min_capacity)
void reinitialize(const int64_t new_size)
const T & first() const
constexpr IndexRange drop_front(int64_t n) const
constexpr int64_t size() const
#define FLT_MAX
float distance(float, float) RET
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
float length(VecOp< float, D >) RET
T sqrt(const T &a)
MatT from_up_axis(const VectorT up)
T distance(const T &a, const T &b)
T length(const VecBase< T, Size > &a)
QuaternionBase< T > normalize_and_get_length(const QuaternionBase< T > &q, T &out_length)
T dot(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
CartesianBasis invert(const CartesianBasis &basis)
T midpoint(const T &a, const 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)
BMesh Iterators.
void BM_face_calc_tessellation(const BMFace *f, const bool use_fixed_quad, BMLoop **r_loops, uint(*r_index)[3])
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
ListBaseT< LinkData > * BM_edgeloop_verts_get(BMEdgeLoopStore *el_store)
int BM_mesh_edgeloops_find(BMesh *bm, ListBaseT< BMEdgeLoopStore > *r_eloops, FunctionRef< bool(BMEdge *)> test_fn, const BMEdgeLoopFind_Params *params)
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
static bool is_valid_boundary_edge(BMEdge *e, const char hflag, const bool check_axis[3], bool extract_wire_edges)
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
int BMO_slot_int_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
int BLI_bvhtree_find_nearest(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
void BMO_slot_buffer_hflag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, char hflag, bool do_flush)
BMO_FLAG_BUFFER.
bool isect_line_tri_v3(const float p1[3], const float p2[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
void BM_mesh_edgeloops_free(ListBaseT< BMEdgeLoopStore > *eloops)
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void BLI_bvhtree_free(BVHTree *tree)
@ FIT_METHOD_LEAST_SQUARE
void BLI_bvhtree_balance(BVHTree *tree)
float angle_signed_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static void bm_vert_chain_extract_from_boundary_edges(BMesh *bm, Vector< VertChain > &r_chains, const char hflag, const bool check_axis[3], bool extract_wire_edges)
bool BM_edgeloop_is_closed(BMEdgeLoopStore *el_store)
Map< BMFace *, Array< std::array< BMVert *, 3 > > > FaceTessellationCache
void bmo_circularize_exec(BMesh *bm, BMOperator *op)
VecBase< float, 2 > float2
BMesh const char void * data
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
static void project_on_mesh(BVHTree *bvh_tree, NearestTriUserData *bvh_data, BMVert *v, const float3 &center_pos, const float3 &normal, float3 &r_pos, FaceTessellationCache &tess_cache)
static bool bm_vert_chain_orientation_matrix_calc(Span< BMVert * > chain, float3 &r_center, float3x3 &r_mat)
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
void BM_mesh_calc_tessellation(BMesh *bm, MutableSpan< std::array< BMLoop *, 3 > > looptris)
static void calculate_circle_best_fit(Span< CircleVert > verts, const std::optional< float2 > &fixed_center, float2 &r_center, float *r_radius)
MINLINE int poly_to_tri_count(int poly_count, int corner_count)
MatBase< float, 3, 3 > float3x3
constexpr float CIRCULARIZE_EPSILON
constexpr float MIRROR_LIMIT
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
float closest_to_line_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
constexpr int NON_LINEAR_LEAST_SQUARES_MAX_ITERATIONS
void closest_on_tri_to_point_v3(float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
static void nearest_tri_cb(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
static void project_chain_to_2d(Span< BMVert * > chain, const float3 &center, const float3x3 &mat, Vector< CircleVert > &r_2d_verts)
void BMO_error_raise(BMesh *bm, BMOperator *owner, eBMOpErrorLevel level, const char *msg) ATTR_NONNULL(1
VecBase< float, 3 > float3
static void calculate_circle_inside_fit(Span< CircleVert > verts, const std::optional< float2 > &fixed_center, float2 &r_center, float *r_radius)
@ BMO_ERROR_CANCEL
static void calculate_target_locations(MutableSpan< CircleVert > verts, const float2 &center, const float radius, const bool is_regular, const bool is_closed, const float rotation_angle)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
#define sinf
#define cosf
#define atan2f
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMVert * v
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
Span< std::array< BMLoop *, 3 > > looptris
Vector< BMVert * > verts