Blender V5.3
math_geom.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10
11#include "BLI_array.hh"
12#include "BLI_math_base.hh"
13#include "BLI_math_base_c.hh"
14#include "BLI_math_geom_c.hh"
15
16#include "BLI_math_bits.hh"
17#include "BLI_math_matrix_c.hh"
19#include "BLI_math_vector_c.hh"
20#include "BLI_utildefines.hh"
21
22#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
23
24namespace blender {
25
26/* -------------------------------------------------------------------- */
29
30void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
31{
32 float n1[3], n2[3];
33
34 n1[0] = v1[0] - v2[0];
35 n2[0] = v2[0] - v3[0];
36 n1[1] = v1[1] - v2[1];
37 n2[1] = v2[1] - v3[1];
38 n1[2] = v1[2] - v2[2];
39 n2[2] = v2[2] - v3[2];
40 n[0] = n1[1] * n2[2] - n1[2] * n2[1];
41 n[1] = n1[2] * n2[0] - n1[0] * n2[2];
42 n[2] = n1[0] * n2[1] - n1[1] * n2[0];
43}
44
45float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
46{
47 float n1[3], n2[3];
48
49 n1[0] = v1[0] - v2[0];
50 n2[0] = v2[0] - v3[0];
51 n1[1] = v1[1] - v2[1];
52 n2[1] = v2[1] - v3[1];
53 n1[2] = v1[2] - v2[2];
54 n2[2] = v2[2] - v3[2];
55 n[0] = n1[1] * n2[2] - n1[2] * n2[1];
56 n[1] = n1[2] * n2[0] - n1[0] * n2[2];
57 n[2] = n1[0] * n2[1] - n1[1] * n2[0];
58
59 return normalize_v3(n);
60}
61
63 float n[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
64{
65 /* real cross! */
66 float n1[3], n2[3];
67
68 n1[0] = v1[0] - v3[0];
69 n1[1] = v1[1] - v3[1];
70 n1[2] = v1[2] - v3[2];
71
72 n2[0] = v2[0] - v4[0];
73 n2[1] = v2[1] - v4[1];
74 n2[2] = v2[2] - v4[2];
75
76 n[0] = n1[1] * n2[2] - n1[2] * n2[1];
77 n[1] = n1[2] * n2[0] - n1[0] * n2[2];
78 n[2] = n1[0] * n2[1] - n1[1] * n2[0];
79
80 return normalize_v3(n);
81}
82
83float normal_poly_v3(float n[3], const float verts[][3], uint nr)
84{
85 cross_poly_v3(n, verts, nr);
86 return normalize_v3(n);
87}
88
89float area_quad_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
90{
91 const float verts[4][3] = {{UNPACK3(v1)}, {UNPACK3(v2)}, {UNPACK3(v3)}, {UNPACK3(v4)}};
92 return area_poly_v3(verts, 4);
93}
94
95float area_squared_quad_v3(const float v1[3],
96 const float v2[3],
97 const float v3[3],
98 const float v4[3])
99{
100 const float verts[4][3] = {{UNPACK3(v1)}, {UNPACK3(v2)}, {UNPACK3(v3)}, {UNPACK3(v4)}};
101 return area_squared_poly_v3(verts, 4);
102}
103
104float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
105{
106 float n[3];
107 cross_tri_v3(n, v1, v2, v3);
108 return len_v3(n) * 0.5f;
109}
110
111float area_squared_tri_v3(const float v1[3], const float v2[3], const float v3[3])
112{
113 float n[3];
114 cross_tri_v3(n, v1, v2, v3);
115 mul_v3_fl(n, 0.5f);
116 return len_squared_v3(n);
117}
118
119float area_tri_signed_v3(const float v1[3],
120 const float v2[3],
121 const float v3[3],
122 const float normal[3])
123{
124 float area, n[3];
125
126 cross_tri_v3(n, v1, v2, v3);
127 area = len_v3(n) * 0.5f;
128
129 /* negate area for flipped triangles */
130 if (dot_v3v3(n, normal) < 0.0f) {
131 area = -area;
132 }
133
134 return area;
135}
136
137float area_poly_v3(const float verts[][3], uint nr)
138{
139 float n[3];
140 cross_poly_v3(n, verts, nr);
141 return len_v3(n) * 0.5f;
142}
143
144float area_squared_poly_v3(const float verts[][3], uint nr)
145{
146 float n[3];
147
148 cross_poly_v3(n, verts, nr);
149 mul_v3_fl(n, 0.5f);
150 return len_squared_v3(n);
151}
152
153float cross_poly_v2(const float verts[][2], uint nr)
154{
155 uint a;
156 float cross;
157 const float *co_curr, *co_prev;
158
159 /* The Trapezium Area Rule */
160 co_prev = verts[nr - 1];
161 co_curr = verts[0];
162 cross = 0.0f;
163 for (a = 0; a < nr; a++) {
164 cross += (co_prev[0] - co_curr[0]) * (co_curr[1] + co_prev[1]);
165 co_prev = co_curr;
166 co_curr += 2;
167 }
168
169 return cross;
170}
171
172void cross_poly_v3(float n[3], const float verts[][3], uint nr)
173{
174 const float *v_prev = verts[nr - 1];
175 const float *v_curr = verts[0];
176 uint i;
177
178 zero_v3(n);
179
180 /* Newell's Method */
181 for (i = 0; i < nr; v_prev = v_curr, v_curr = verts[++i]) {
182 add_newell_cross_v3_v3v3(n, v_prev, v_curr);
183 }
184}
185
186float area_poly_v2(const float verts[][2], uint nr)
187{
188 return fabsf(0.5f * cross_poly_v2(verts, nr));
189}
190
191float area_poly_signed_v2(const float verts[][2], uint nr)
192{
193 return (0.5f * cross_poly_v2(verts, nr));
194}
195
196float area_squared_poly_v2(const float verts[][2], uint nr)
197{
198 float area = area_poly_signed_v2(verts, nr);
199 return area * area;
200}
201
202float cotangent_tri_weight_v3(const float v1[3], const float v2[3], const float v3[3])
203{
204 float a[3], b[3], c[3], c_len;
205
206 sub_v3_v3v3(a, v2, v1);
207 sub_v3_v3v3(b, v3, v1);
208 cross_v3_v3v3(c, a, b);
209
210 c_len = len_v3(c);
211
212 if (c_len > FLT_EPSILON) {
213 return dot_v3v3(a, b) / c_len;
214 }
215
216 return 0.0f;
217}
218
220
221/* -------------------------------------------------------------------- */
224
225void plane_from_point_normal_v3(float r_plane[4], const float plane_co[3], const float plane_no[3])
226{
227 copy_v3_v3(r_plane, plane_no);
228 r_plane[3] = -dot_v3v3(r_plane, plane_co);
229}
230
231void plane_to_point_vector_v3(const float plane[4], float r_plane_co[3], float r_plane_no[3])
232{
233 mul_v3_v3fl(r_plane_co, plane, (-plane[3] / len_squared_v3(plane)));
234 copy_v3_v3(r_plane_no, plane);
235}
236
237void plane_to_point_vector_v3_normalized(const float plane[4],
238 float r_plane_co[3],
239 float r_plane_no[3])
240{
241 const float length = normalize_v3_v3(r_plane_no, plane);
242 mul_v3_v3fl(r_plane_co, r_plane_no, (-plane[3] / length));
243}
244
246
247/* -------------------------------------------------------------------- */
250
251float volume_tetrahedron_v3(const float v1[3],
252 const float v2[3],
253 const float v3[3],
254 const float v4[3])
255{
256 float m[3][3];
257 sub_v3_v3v3(m[0], v1, v2);
258 sub_v3_v3v3(m[1], v2, v3);
259 sub_v3_v3v3(m[2], v3, v4);
260 return fabsf(determinant_m3_array(m)) / 6.0f;
261}
262
263float volume_tetrahedron_signed_v3(const float v1[3],
264 const float v2[3],
265 const float v3[3],
266 const float v4[3])
267{
268 float m[3][3];
269 sub_v3_v3v3(m[0], v1, v2);
270 sub_v3_v3v3(m[1], v2, v3);
271 sub_v3_v3v3(m[2], v3, v4);
272 return determinant_m3_array(m) / 6.0f;
273}
274
275float volume_tri_tetrahedron_signed_v3_6x(const float v1[3], const float v2[3], const float v3[3])
276{
277 float v_cross[3];
278 cross_v3_v3v3(v_cross, v1, v2);
279 float tetra_volume = dot_v3v3(v_cross, v3);
280 return tetra_volume;
281}
282
283float volume_tri_tetrahedron_signed_v3(const float v1[3], const float v2[3], const float v3[3])
284{
285 return volume_tri_tetrahedron_signed_v3_6x(v1, v2, v3) / 6.0f;
286}
287
289
290/* -------------------------------------------------------------------- */
293
294float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2])
295{
296 float closest[2];
297
298 closest_to_line_v2(closest, p, l1, l2);
299
300 return len_squared_v2v2(closest, p);
301}
302float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2])
303{
304 return sqrtf(dist_squared_to_line_v2(p, l1, l2));
305}
306
307float dist_squared_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2])
308{
309 float closest[2];
310
312
313 return len_squared_v2v2(closest, p);
314}
315
316float dist_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2])
317{
318 return sqrtf(dist_squared_to_line_segment_v2(p, l1, l2));
319}
320
321float closest_seg_seg_v2(float r_closest_a[2],
322 float r_closest_b[2],
323 float *r_lambda_a,
324 float *r_lambda_b,
325 const float a1[2],
326 const float a2[2],
327 const float b1[2],
328 const float b2[2])
329{
330 if (isect_seg_seg_v2_simple(a1, a2, b1, b2)) {
331 float intersection[2];
332 isect_line_line_v2_point(a1, a2, b1, b2, intersection);
333 copy_v2_v2(r_closest_a, intersection);
334 copy_v2_v2(r_closest_b, intersection);
335 float tmp[2];
336 *r_lambda_a = closest_to_line_v2(tmp, intersection, a1, a2);
337 *r_lambda_b = closest_to_line_v2(tmp, intersection, b1, b2);
338 const float min_dist_sq = len_squared_v2v2(r_closest_a, r_closest_b);
339 return min_dist_sq;
340 }
341
342 float p1[2], p2[2], p3[2], p4[2];
343 const float lambda1 = closest_to_line_segment_v2(p1, a1, b1, b2);
344 const float lambda2 = closest_to_line_segment_v2(p2, a2, b1, b2);
345 const float lambda3 = closest_to_line_segment_v2(p3, b1, a1, a2);
346 const float lambda4 = closest_to_line_segment_v2(p4, b2, a1, a2);
347 const float dist_sq1 = len_squared_v2v2(p1, a1);
348 const float dist_sq2 = len_squared_v2v2(p2, a2);
349 const float dist_sq3 = len_squared_v2v2(p3, b1);
350 const float dist_sq4 = len_squared_v2v2(p4, b2);
351
352 const float min_dist_sq = std::min({dist_sq1, dist_sq2, dist_sq3, dist_sq4});
353 if (min_dist_sq == dist_sq1) {
354 copy_v2_v2(r_closest_a, a1);
355 copy_v2_v2(r_closest_b, p1);
356 *r_lambda_a = 0.0f;
357 *r_lambda_b = lambda1;
358 }
359 else if (min_dist_sq == dist_sq2) {
360 copy_v2_v2(r_closest_a, a2);
361 copy_v2_v2(r_closest_b, p2);
362 *r_lambda_a = 1.0f;
363 *r_lambda_b = lambda2;
364 }
365 else if (min_dist_sq == dist_sq3) {
366 copy_v2_v2(r_closest_a, p3);
367 copy_v2_v2(r_closest_b, b1);
368 *r_lambda_a = lambda3;
369 *r_lambda_b = 0.0f;
370 }
371 else {
372 BLI_assert(min_dist_sq == dist_sq4);
373 copy_v2_v2(r_closest_a, p4);
374 copy_v2_v2(r_closest_b, b2);
375 *r_lambda_a = lambda4;
376 *r_lambda_b = 1.0f;
377 }
378 return min_dist_sq;
379}
380
381float closest_to_line_segment_v2(float r_close[2],
382 const float p[2],
383 const float l1[2],
384 const float l2[2])
385{
386 float lambda, cp[2];
387
388 lambda = closest_to_line_v2(cp, p, l1, l2);
389
390 /* flip checks for !finite case (when segment is a point) */
391 if (lambda <= 0.0f) {
392 copy_v2_v2(r_close, l1);
393 return 0.0f;
394 }
395 if (lambda >= 1.0f) {
396 copy_v2_v2(r_close, l2);
397 return 1.0f;
398 }
399 copy_v2_v2(r_close, cp);
400 return lambda;
401}
402
403float closest_to_line_segment_v3(float r_close[3],
404 const float p[3],
405 const float l1[3],
406 const float l2[3])
407{
408 float lambda, cp[3];
409
410 lambda = closest_to_line_v3(cp, p, l1, l2);
411
412 /* flip checks for !finite case (when segment is a point) */
413 if (lambda <= 0.0f) {
414 copy_v3_v3(r_close, l1);
415 return 0.0f;
416 }
417 if (lambda >= 1.0f) {
418 copy_v3_v3(r_close, l2);
419 return 1.0f;
420 }
421 copy_v3_v3(r_close, cp);
422 return lambda;
423}
424
425float closest_ray_to_segment_v3(const float ray_origin[3],
426 const float ray_direction[3],
427 const float v0[3],
428 const float v1[3],
429 float r_close[3])
430{
431 float lambda;
432 if (!isect_ray_line_v3(ray_origin, ray_direction, v0, v1, &lambda)) {
433 copy_v3_v3(r_close, v0);
434 return 0.0f;
435 }
436
437 if (lambda <= 0.0f) {
438 copy_v3_v3(r_close, v0);
439 return 0.0f;
440 }
441
442 if (lambda >= 1.0f) {
443 copy_v3_v3(r_close, v1);
444 return 1.0f;
445 }
446
447 interp_v3_v3v3(r_close, v0, v1, lambda);
448 return lambda;
449}
450
451void closest_to_plane_v3(float r_close[3], const float plane[4], const float pt[3])
452{
453 const float len_sq = len_squared_v3(plane);
454 const float side = plane_point_side_v3(plane, pt);
455 madd_v3_v3v3fl(r_close, pt, plane, -side / len_sq);
456}
457
458void closest_to_plane_normalized_v3(float r_close[3], const float plane[4], const float pt[3])
459{
460 const float side = plane_point_side_v3(plane, pt);
461 BLI_ASSERT_UNIT_V3(plane);
462 madd_v3_v3v3fl(r_close, pt, plane, -side);
463}
464
465void closest_to_plane3_v3(float r_close[3], const float plane[3], const float pt[3])
466{
467 const float len_sq = len_squared_v3(plane);
468 const float side = dot_v3v3(plane, pt);
469 madd_v3_v3v3fl(r_close, pt, plane, -side / len_sq);
470}
471
472void closest_to_plane3_normalized_v3(float r_close[3], const float plane[3], const float pt[3])
473{
474 const float side = dot_v3v3(plane, pt);
475 BLI_ASSERT_UNIT_V3(plane);
476 madd_v3_v3v3fl(r_close, pt, plane, -side);
477}
478
479float dist_signed_squared_to_plane_v3(const float p[3], const float plane[4])
480{
481 const float len_sq = len_squared_v3(plane);
482 const float side = plane_point_side_v3(plane, p);
483 const float fac = side / len_sq;
484 return copysignf(len_sq * (fac * fac), side);
485}
486float dist_squared_to_plane_v3(const float p[3], const float plane[4])
487{
488 const float len_sq = len_squared_v3(plane);
489 const float side = plane_point_side_v3(plane, p);
490 const float fac = side / len_sq;
491 /* only difference to code above - no 'copysignf' */
492 return len_sq * (fac * fac);
493}
494
495float dist_signed_squared_to_plane3_v3(const float p[3], const float plane[3])
496{
497 const float len_sq = len_squared_v3(plane);
498 const float side = dot_v3v3(plane, p); /* only difference with 'plane[4]' version */
499 const float fac = side / len_sq;
500 return copysignf(len_sq * (fac * fac), side);
501}
502float dist_squared_to_plane3_v3(const float p[3], const float plane[3])
503{
504 const float len_sq = len_squared_v3(plane);
505 const float side = dot_v3v3(plane, p); /* only difference with 'plane[4]' version */
506 const float fac = side / len_sq;
507 /* only difference to code above - no 'copysignf' */
508 return len_sq * (fac * fac);
509}
510
511float dist_signed_to_plane_v3(const float p[3], const float plane[4])
512{
513 const float len_sq = len_squared_v3(plane);
514 const float side = plane_point_side_v3(plane, p);
515 const float fac = side / len_sq;
516 return sqrtf(len_sq) * fac;
517}
518float dist_to_plane_v3(const float p[3], const float plane[4])
519{
520 return fabsf(dist_signed_to_plane_v3(p, plane));
521}
522
523float dist_signed_to_plane3_v3(const float p[3], const float plane[3])
524{
525 const float len_sq = len_squared_v3(plane);
526 const float side = dot_v3v3(plane, p); /* only difference with 'plane[4]' version */
527 const float fac = side / len_sq;
528 return sqrtf(len_sq) * fac;
529}
530float dist_to_plane3_v3(const float p[3], const float plane[3])
531{
532 return fabsf(dist_signed_to_plane3_v3(p, plane));
533}
534
535float dist_squared_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3])
536{
537 float closest[3];
538
540
541 return len_squared_v3v3(closest, p);
542}
543
544float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3])
545{
546 return sqrtf(dist_squared_to_line_segment_v3(p, l1, l2));
547}
548
549float dist_squared_to_line_v3(const float p[3], const float l1[3], const float l2[3])
550{
551 float closest[3];
552
553 closest_to_line_v3(closest, p, l1, l2);
554
555 return len_squared_v3v3(closest, p);
556}
557float dist_to_line_v3(const float p[3], const float l1[3], const float l2[3])
558{
559 return sqrtf(dist_squared_to_line_v3(p, l1, l2));
560}
561
563 const float v1[3],
564 const float v2[3],
565 const float v3[3],
566 const float axis_ref[3])
567{
568 float dir_a[3], dir_b[3];
569 float plane_a[3], plane_b[3];
570 float dist_a, dist_b;
571 float axis[3];
572 float s_p_v2[3];
573 bool flip = false;
574
575 sub_v3_v3v3(dir_a, v1, v2);
576 sub_v3_v3v3(dir_b, v3, v2);
577
578 cross_v3_v3v3(axis, dir_a, dir_b);
579
580 if (len_squared_v3(axis) < FLT_EPSILON) {
581 copy_v3_v3(axis, axis_ref);
582 }
583 else if (dot_v3v3(axis, axis_ref) < 0.0f) {
584 /* concave */
585 flip = true;
586 negate_v3(axis);
587 }
588
589 cross_v3_v3v3(plane_a, dir_a, axis);
590 cross_v3_v3v3(plane_b, axis, dir_b);
591
592#if 0
593 plane_from_point_normal_v3(plane_a, v2, plane_a);
594 plane_from_point_normal_v3(plane_b, v2, plane_b);
595
596 dist_a = dist_signed_squared_to_plane_v3(p, plane_a);
597 dist_b = dist_signed_squared_to_plane_v3(p, plane_b);
598#else
599 /* calculate without the planes 4th component to avoid float precision issues */
600 sub_v3_v3v3(s_p_v2, p, v2);
601
602 dist_a = dist_signed_squared_to_plane3_v3(s_p_v2, plane_a);
603 dist_b = dist_signed_squared_to_plane3_v3(s_p_v2, plane_b);
604#endif
605
606 if (flip) {
607 return min_ff(dist_a, dist_b);
608 }
609
610 return max_ff(dist_a, dist_b);
611}
612
613float dist_squared_to_ray_v3_normalized(const float ray_origin[3],
614 const float ray_direction[3],
615 const float co[3])
616{
617 float origin_to_co[3];
618 sub_v3_v3v3(origin_to_co, co, ray_origin);
619
620 float origin_to_proj[3];
621 project_v3_v3v3_normalized(origin_to_proj, origin_to_co, ray_direction);
622
623 float co_projected_on_ray[3];
624 add_v3_v3v3(co_projected_on_ray, ray_origin, origin_to_proj);
625
626 return len_squared_v3v3(co, co_projected_on_ray);
627}
628
629float dist_squared_ray_to_seg_v3(const float ray_origin[3],
630 const float ray_direction[3],
631 const float v0[3],
632 const float v1[3],
633 float r_point[3],
634 float *r_depth)
635{
636 float lambda, depth;
637 if (isect_ray_line_v3(ray_origin, ray_direction, v0, v1, &lambda)) {
638 if (lambda <= 0.0f) {
639 copy_v3_v3(r_point, v0);
640 }
641 else if (lambda >= 1.0f) {
642 copy_v3_v3(r_point, v1);
643 }
644 else {
645 interp_v3_v3v3(r_point, v0, v1, lambda);
646 }
647 }
648 else {
649 /* Has no nearest point because two lines are parallel, only distance squared. */
650 /* Calculate the distance to the point v0 then. */
651 copy_v3_v3(r_point, v0);
652 }
653
654 float dvec[3];
655 sub_v3_v3v3(dvec, r_point, ray_origin);
656 depth = dot_v3v3(dvec, ray_direction);
657
658 if (r_depth) {
659 *r_depth = depth;
660 }
661
662 return len_squared_v3(dvec) - square_f(depth);
663}
664
665void aabb_get_near_far_from_plane(const float plane_no[3],
666 const float bbmin[3],
667 const float bbmax[3],
668 float bb_near[3],
669 float bb_afar[3])
670{
671 if (plane_no[0] < 0.0f) {
672 bb_near[0] = bbmax[0];
673 bb_afar[0] = bbmin[0];
674 }
675 else {
676 bb_near[0] = bbmin[0];
677 bb_afar[0] = bbmax[0];
678 }
679 if (plane_no[1] < 0.0f) {
680 bb_near[1] = bbmax[1];
681 bb_afar[1] = bbmin[1];
682 }
683 else {
684 bb_near[1] = bbmin[1];
685 bb_afar[1] = bbmax[1];
686 }
687 if (plane_no[2] < 0.0f) {
688 bb_near[2] = bbmax[2];
689 bb_afar[2] = bbmin[2];
690 }
691 else {
692 bb_near[2] = bbmin[2];
693 bb_afar[2] = bbmax[2];
694 }
695}
696
698
699/* -------------------------------------------------------------------- */
702
704 const float ray_direction[3])
705{
706 DistRayAABB_Precalc nearest_precalc{};
707 copy_v3_v3(nearest_precalc.ray_origin, ray_origin);
708 copy_v3_v3(nearest_precalc.ray_direction, ray_direction);
709
710 for (int i = 0; i < 3; i++) {
711 nearest_precalc.ray_inv_dir[i] = (nearest_precalc.ray_direction[i] != 0.0f) ?
712 (1.0f / nearest_precalc.ray_direction[i]) :
713 FLT_MAX;
714 }
715 return nearest_precalc;
716}
717
719 const float bb_min[3],
720 const float bb_max[3],
721 float r_point[3],
722 float *r_depth)
723{
724 // bool r_axis_closest[3];
725 float local_bvmin[3], local_bvmax[3];
726 aabb_get_near_far_from_plane(data->ray_direction, bb_min, bb_max, local_bvmin, local_bvmax);
727
728 /* Distance along the ray where the ray crosses the near-plane (tmin) and far-plane (tmax) of the
729 * AABB on each axis. */
730 const float tmin[3] = {
731 (local_bvmin[0] - data->ray_origin[0]) * data->ray_inv_dir[0],
732 (local_bvmin[1] - data->ray_origin[1]) * data->ray_inv_dir[1],
733 (local_bvmin[2] - data->ray_origin[2]) * data->ray_inv_dir[2],
734 };
735 const float tmax[3] = {
736 (local_bvmax[0] - data->ray_origin[0]) * data->ray_inv_dir[0],
737 (local_bvmax[1] - data->ray_origin[1]) * data->ray_inv_dir[1],
738 (local_bvmax[2] - data->ray_origin[2]) * data->ray_inv_dir[2],
739 };
740 /* `va` and `vb` are the coordinates of the AABB edge closest to the ray */
741 float va[3], vb[3];
742 /* `rtmin` and `rtmax` are the minimum and maximum distances of the ray hits on the AABB */
743 float rtmin, rtmax;
744 int main_axis;
745
746 /* Find the first far plane that the ray exits. */
747 if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) {
748 rtmax = tmax[0];
749 va[0] = vb[0] = local_bvmax[0];
750 main_axis = 3;
751 // r_axis_closest[0] = neasrest_precalc->ray_direction[0] < 0.0f;
752 }
753 else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) {
754 rtmax = tmax[1];
755 va[1] = vb[1] = local_bvmax[1];
756 main_axis = 2;
757 // r_axis_closest[1] = neasrest_precalc->ray_direction[1] < 0.0f;
758 }
759 else {
760 rtmax = tmax[2];
761 va[2] = vb[2] = local_bvmax[2];
762 main_axis = 1;
763 // r_axis_closest[2] = neasrest_precalc->ray_direction[2] < 0.0f;
764 }
765
766 /* Find the last near plane that the ray enters. */
767 if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) {
768 rtmin = tmin[0];
769 va[0] = vb[0] = local_bvmin[0];
770 main_axis -= 3;
771 // r_axis_closest[0] = neasrest_precalc->ray_direction[0] >= 0.0f;
772 }
773 else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) {
774 rtmin = tmin[1];
775 va[1] = vb[1] = local_bvmin[1];
776 main_axis -= 1;
777 // r_axis_closest[1] = neasrest_precalc->ray_direction[1] >= 0.0f;
778 }
779 else {
780 rtmin = tmin[2];
781 va[2] = vb[2] = local_bvmin[2];
782 main_axis -= 2;
783 // r_axis_closest[2] = neasrest_precalc->ray_direction[2] >= 0.0f;
784 }
785 if (main_axis < 0) {
786 main_axis += 3;
787 }
788
789 /* If rtmin <= rtmax, the ray intersects the AABB. Otherwise, there is no moment where the ray
790 * has entered through all three near planes but has not exited from any far plane, meaning the
791 * ray does not intersect the AABB. */
792 if (rtmin <= rtmax) {
793 float dvec[3];
794 copy_v3_v3(r_point, local_bvmax);
795 sub_v3_v3v3(dvec, local_bvmax, data->ray_origin);
796 *r_depth = dot_v3v3(dvec, data->ray_direction);
797 return 0.0f;
798 }
799
800 /* The main_axis is the intersection of the first far plane and the last near plane, which must
801 * be the third axis that is orthogonal to the normals of both planes. */
802 if (data->ray_direction[main_axis] >= 0.0f) {
803 va[main_axis] = local_bvmin[main_axis];
804 vb[main_axis] = local_bvmax[main_axis];
805 }
806 else {
807 va[main_axis] = local_bvmax[main_axis];
808 vb[main_axis] = local_bvmin[main_axis];
809 }
810
812 data->ray_origin, data->ray_direction, va, vb, r_point, r_depth);
813}
814
815float dist_squared_ray_to_aabb_v3_simple(const float ray_origin[3],
816 const float ray_direction[3],
817 const float bb_min[3],
818 const float bb_max[3],
819 float r_point[3],
820 float *r_depth)
821{
822 const DistRayAABB_Precalc data = dist_squared_ray_to_aabb_v3_precalc(ray_origin, ray_direction);
823 return dist_squared_ray_to_aabb_v3(&data, bb_min, bb_max, r_point, r_depth);
824}
825
827
828/* -------------------------------------------------------------------- */
831
833 const float projmat[4][4],
834 const float winsize[2],
835 const float mval[2])
836{
837 float win_half[2], relative_mval[2], px[4], py[4];
838
839 mul_v2_v2fl(win_half, winsize, 0.5f);
840 sub_v2_v2v2(precalc->mval, mval, win_half);
841
842 relative_mval[0] = precalc->mval[0] / win_half[0];
843 relative_mval[1] = precalc->mval[1] / win_half[1];
844
845 copy_m4_m4(precalc->pmat, projmat);
846 for (int i = 0; i < 4; i++) {
847 px[i] = precalc->pmat[i][0] - precalc->pmat[i][3] * relative_mval[0];
848 py[i] = precalc->pmat[i][1] - precalc->pmat[i][3] * relative_mval[1];
849
850 precalc->pmat[i][0] *= win_half[0];
851 precalc->pmat[i][1] *= win_half[1];
852 }
853#if 0
854 float projmat_trans[4][4];
855 transpose_m4_m4(projmat_trans, projmat);
857 projmat_trans[0], projmat_trans[1], projmat_trans[3], precalc->ray_origin))
858 {
859 /* Orthographic projection. */
860 isect_plane_plane_v3(px, py, precalc->ray_origin, precalc->ray_direction);
861 }
862 else {
863 /* Perspective projection. */
864 cross_v3_v3v3(precalc->ray_direction, py, px);
865 // normalize_v3(precalc->ray_direction);
866 }
867#else
868 if (!isect_plane_plane_v3(px, py, precalc->ray_origin, precalc->ray_direction)) {
869 /* Matrix with weird co-planar planes. Undetermined origin. */
870 zero_v3(precalc->ray_origin);
871 precalc->ray_direction[0] = precalc->pmat[0][3];
872 precalc->ray_direction[1] = precalc->pmat[1][3];
873 precalc->ray_direction[2] = precalc->pmat[2][3];
874 }
875#endif
876
877 for (int i = 0; i < 3; i++) {
878 precalc->ray_inv_dir[i] = (precalc->ray_direction[i] != 0.0f) ?
879 (1.0f / precalc->ray_direction[i]) :
880 FLT_MAX;
881 }
882}
883
885 const float bbmin[3],
886 const float bbmax[3],
887 bool r_axis_closest[3])
888{
889 float local_bvmin[3], local_bvmax[3];
890 aabb_get_near_far_from_plane(data->ray_direction, bbmin, bbmax, local_bvmin, local_bvmax);
891
892 const float tmin[3] = {
893 (local_bvmin[0] - data->ray_origin[0]) * data->ray_inv_dir[0],
894 (local_bvmin[1] - data->ray_origin[1]) * data->ray_inv_dir[1],
895 (local_bvmin[2] - data->ray_origin[2]) * data->ray_inv_dir[2],
896 };
897 const float tmax[3] = {
898 (local_bvmax[0] - data->ray_origin[0]) * data->ray_inv_dir[0],
899 (local_bvmax[1] - data->ray_origin[1]) * data->ray_inv_dir[1],
900 (local_bvmax[2] - data->ray_origin[2]) * data->ray_inv_dir[2],
901 };
902 /* `va` and `vb` are the coordinates of the AABB edge closest to the ray */
903 float va[3], vb[3];
904 /* `rtmin` and `rtmax` are the minimum and maximum distances of the ray hits on the AABB */
905 float rtmin, rtmax;
906 int main_axis;
907
908 r_axis_closest[0] = false;
909 r_axis_closest[1] = false;
910 r_axis_closest[2] = false;
911
912 if ((tmax[0] <= tmax[1]) && (tmax[0] <= tmax[2])) {
913 rtmax = tmax[0];
914 va[0] = vb[0] = local_bvmax[0];
915 main_axis = 3;
916 r_axis_closest[0] = data->ray_direction[0] < 0.0f;
917 }
918 else if ((tmax[1] <= tmax[0]) && (tmax[1] <= tmax[2])) {
919 rtmax = tmax[1];
920 va[1] = vb[1] = local_bvmax[1];
921 main_axis = 2;
922 r_axis_closest[1] = data->ray_direction[1] < 0.0f;
923 }
924 else {
925 rtmax = tmax[2];
926 va[2] = vb[2] = local_bvmax[2];
927 main_axis = 1;
928 r_axis_closest[2] = data->ray_direction[2] < 0.0f;
929 }
930
931 if ((tmin[0] >= tmin[1]) && (tmin[0] >= tmin[2])) {
932 rtmin = tmin[0];
933 va[0] = vb[0] = local_bvmin[0];
934 main_axis -= 3;
935 r_axis_closest[0] = data->ray_direction[0] >= 0.0f;
936 }
937 else if ((tmin[1] >= tmin[0]) && (tmin[1] >= tmin[2])) {
938 rtmin = tmin[1];
939 va[1] = vb[1] = local_bvmin[1];
940 main_axis -= 1;
941 r_axis_closest[1] = data->ray_direction[1] >= 0.0f;
942 }
943 else {
944 rtmin = tmin[2];
945 va[2] = vb[2] = local_bvmin[2];
946 main_axis -= 2;
947 r_axis_closest[2] = data->ray_direction[2] >= 0.0f;
948 }
949 if (main_axis < 0) {
950 main_axis += 3;
951 }
952
953 /* if rtmin <= rtmax, ray intersect `AABB` */
954 if (rtmin <= rtmax) {
955 return 0;
956 }
957
958 if (data->ray_direction[main_axis] >= 0.0f) {
959 va[main_axis] = local_bvmin[main_axis];
960 vb[main_axis] = local_bvmax[main_axis];
961 }
962 else {
963 va[main_axis] = local_bvmax[main_axis];
964 vb[main_axis] = local_bvmin[main_axis];
965 }
966 float scale = fabsf(local_bvmax[main_axis] - local_bvmin[main_axis]);
967
968 float va2d[2] = {
969 (dot_m4_v3_row_x(data->pmat, va) + data->pmat[3][0]),
970 (dot_m4_v3_row_y(data->pmat, va) + data->pmat[3][1]),
971 };
972 float vb2d[2] = {
973 (va2d[0] + data->pmat[main_axis][0] * scale),
974 (va2d[1] + data->pmat[main_axis][1] * scale),
975 };
976
977 float w_a = mul_project_m4_v3_zfac(data->pmat, va);
978 if (w_a != 1.0f) {
979 /* Perspective Projection. */
980 float w_b = w_a + data->pmat[main_axis][3] * scale;
981 va2d[0] /= w_a;
982 va2d[1] /= w_a;
983 vb2d[0] /= w_b;
984 vb2d[1] /= w_b;
985 }
986
987 float dvec[2], edge[2], lambda, rdist_sq;
988 sub_v2_v2v2(dvec, data->mval, va2d);
989 sub_v2_v2v2(edge, vb2d, va2d);
990 lambda = dot_v2v2(dvec, edge);
991 if (lambda != 0.0f) {
992 lambda /= len_squared_v2(edge);
993 if (lambda <= 0.0f) {
994 rdist_sq = len_squared_v2v2(data->mval, va2d);
995 r_axis_closest[main_axis] = true;
996 }
997 else if (lambda >= 1.0f) {
998 rdist_sq = len_squared_v2v2(data->mval, vb2d);
999 r_axis_closest[main_axis] = false;
1000 }
1001 else {
1002 madd_v2_v2fl(va2d, edge, lambda);
1003 rdist_sq = len_squared_v2v2(data->mval, va2d);
1004 r_axis_closest[main_axis] = lambda < 0.5f;
1005 }
1006 }
1007 else {
1008 rdist_sq = len_squared_v2v2(data->mval, va2d);
1009 }
1010
1011 return rdist_sq;
1012}
1013
1014float dist_squared_to_projected_aabb_simple(const float projmat[4][4],
1015 const float winsize[2],
1016 const float mval[2],
1017 const float bbmin[3],
1018 const float bbmax[3])
1019{
1021 dist_squared_to_projected_aabb_precalc(&data, projmat, winsize, mval);
1022
1023 bool dummy[3] = {true, true, true};
1024 return dist_squared_to_projected_aabb(&data, bbmin, bbmax, dummy);
1025}
1026
1028
1029/* -------------------------------------------------------------------- */
1032
1033float dist_seg_seg_v2(const float a1[3], const float a2[3], const float b1[3], const float b2[3])
1034{
1035 if (isect_seg_seg_v2_simple(a1, a2, b1, b2)) {
1036 return 0.0f;
1037 }
1038 const float d1 = dist_squared_to_line_segment_v2(a1, b1, b2);
1039 const float d2 = dist_squared_to_line_segment_v2(a2, b1, b2);
1040 const float d3 = dist_squared_to_line_segment_v2(b1, a1, a2);
1041 const float d4 = dist_squared_to_line_segment_v2(b2, a1, a2);
1042 return sqrtf(std::min({d1, d2, d3, d4}));
1043}
1044
1046 float r_bary[3],
1047 const float p[3],
1048 const float v1[3],
1049 const float v2[3],
1050 const float v3[3])
1051{
1052 /* Adapted from "Real-Time Collision Detection" by Christer Ericson,
1053 * published by Morgan Kaufmann Publishers, copyright 2005 Elsevier Inc. */
1054
1055 float ab[3], ac[3], ap[3], d1, d2;
1056 float bp[3], d3, d4, vc, cp[3], d5, d6, vb, va;
1057 float denom, v, w;
1058
1059 /* Check if P in vertex region outside A */
1060 sub_v3_v3v3(ab, v2, v1);
1061 sub_v3_v3v3(ac, v3, v1);
1062 sub_v3_v3v3(ap, p, v1);
1063 d1 = dot_v3v3(ab, ap);
1064 d2 = dot_v3v3(ac, ap);
1065 if (d1 <= 0.0f && d2 <= 0.0f) {
1066 r_bary[0] = 1.0f;
1067 r_bary[1] = 0.0f;
1068 r_bary[2] = 0.0f;
1069 copy_v3_v3(r, v1);
1070 return;
1071 }
1072
1073 /* Check if P in vertex region outside B */
1074 sub_v3_v3v3(bp, p, v2);
1075 d3 = dot_v3v3(ab, bp);
1076 d4 = dot_v3v3(ac, bp);
1077 if (d3 >= 0.0f && d4 <= d3) {
1078 r_bary[0] = 0.0f;
1079 r_bary[1] = 1.0f;
1080 r_bary[2] = 0.0f;
1081 copy_v3_v3(r, v2);
1082 return;
1083 }
1084 /* Check if P in edge region of AB, if so return projection of P onto AB */
1085 vc = d1 * d4 - d3 * d2;
1086 if (vc <= 0.0f && d1 >= 0.0f && d3 <= 0.0f) {
1087 const float ab_squared = d1 - d3;
1088 if (ab_squared == 0.0f) {
1089 r_bary[0] = 1.0f;
1090 r_bary[1] = 0.0f;
1091 r_bary[2] = 0.0f;
1092 copy_v3_v3(r, v1);
1093 }
1094 else {
1095 v = d1 / ab_squared;
1096 r_bary[0] = 1.0f - v;
1097 r_bary[1] = v;
1098 r_bary[2] = 0.0f;
1099 madd_v3_v3v3fl(r, v1, ab, v);
1100 }
1101 return;
1102 }
1103 /* Check if P in vertex region outside C */
1104 sub_v3_v3v3(cp, p, v3);
1105 d5 = dot_v3v3(ab, cp);
1106 d6 = dot_v3v3(ac, cp);
1107 if (d6 >= 0.0f && d5 <= d6) {
1108 r_bary[0] = 0.0f;
1109 r_bary[1] = 0.0f;
1110 r_bary[2] = 1.0f;
1111 copy_v3_v3(r, v3);
1112 return;
1113 }
1114 /* Check if P in edge region of AC, if so return projection of P onto AC */
1115 vb = d5 * d2 - d1 * d6;
1116 if (vb <= 0.0f && d2 >= 0.0f && d6 <= 0.0f) {
1117 const float ac_squared = d2 - d6;
1118 if (ac_squared == 0.0f) {
1119 r_bary[0] = 1.0f;
1120 r_bary[1] = 0.0f;
1121 r_bary[2] = 0.0f;
1122 copy_v3_v3(r, v1);
1123 }
1124 else {
1125 w = d2 / ac_squared;
1126 r_bary[0] = 1.0f - w;
1127 r_bary[1] = 0.0f;
1128 r_bary[2] = w;
1129 madd_v3_v3v3fl(r, v1, ac, w);
1130 }
1131 return;
1132 }
1133 /* Check if P in edge region of BC, if so return projection of P onto BC */
1134 va = d3 * d6 - d5 * d4;
1135 if (va <= 0.0f && (d4 - d3) >= 0.0f && (d5 - d6) >= 0.0f) {
1136 const float bc_squared = (d4 - d3) + (d5 - d6);
1137 if (bc_squared == 0.0f) {
1138 r_bary[0] = 0.0f;
1139 r_bary[1] = 1.0f;
1140 r_bary[2] = 0.0f;
1141 copy_v3_v3(r, v2);
1142 }
1143 else {
1144 w = (d4 - d3) / bc_squared;
1145 r_bary[0] = 0.0f;
1146 r_bary[1] = 1.0f - w;
1147 r_bary[2] = w;
1148
1149 sub_v3_v3v3(r, v3, v2);
1150 mul_v3_fl(r, w);
1151 add_v3_v3(r, v2);
1152 }
1153 return;
1154 }
1155
1156 /* P inside face region. Compute Q through its barycentric coordinates (u,v,w) */
1157 denom = 1.0f / (va + vb + vc);
1158 v = vb * denom;
1159 w = vc * denom;
1160
1161 r_bary[1] = v;
1162 r_bary[2] = w;
1163 r_bary[0] = 1.0f - v - w;
1164
1165 /* = u*a + v*b + w*c, u = va * denom = 1.0f - v - w */
1166 /* ac * w */
1167 mul_v3_fl(ac, w);
1168 /* a + ab * v */
1169 madd_v3_v3v3fl(r, v1, ab, v);
1170 /* a + ab * v + ac * w */
1171 add_v3_v3(r, ac);
1172}
1173
1175 float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
1176{
1177 float bary_dummy[3];
1178 closest_on_tri_to_point_v3(r, bary_dummy, p, v1, v2, v3);
1179}
1180
1182
1183/* -------------------------------------------------------------------- */
1186
1187int isect_seg_seg_v2_int(const int v1[2], const int v2[2], const int v3[2], const int v4[2])
1188{
1189 float div, lambda, mu;
1190
1191 div = float((v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]));
1192 if (div == 0.0f) {
1194 }
1195
1196 lambda = float((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
1197
1198 mu = float((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
1199
1200 if (lambda >= 0.0f && lambda <= 1.0f && mu >= 0.0f && mu <= 1.0f) {
1201 if (lambda == 0.0f || lambda == 1.0f || mu == 0.0f || mu == 1.0f) {
1202 return ISECT_LINE_LINE_EXACT;
1203 }
1204 return ISECT_LINE_LINE_CROSS;
1205 }
1206 return ISECT_LINE_LINE_NONE;
1207}
1208
1210 const float v0[2], const float v1[2], const float v2[2], const float v3[2], float r_vi[2])
1211{
1212 float s10[2], s32[2];
1213 float div;
1214
1215 sub_v2_v2v2(s10, v1, v0);
1216 sub_v2_v2v2(s32, v3, v2);
1217
1218 div = cross_v2v2(s10, s32);
1219 if (div != 0.0f) {
1220 const float u = cross_v2v2(v1, v0);
1221 const float v = cross_v2v2(v3, v2);
1222
1223 r_vi[0] = ((s32[0] * u) - (s10[0] * v)) / div;
1224 r_vi[1] = ((s32[1] * u) - (s10[1] * v)) / div;
1225
1226 return ISECT_LINE_LINE_CROSS;
1227 }
1228
1230}
1231
1232int isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
1233{
1234 float div, lambda, mu;
1235
1236 div = (v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]);
1237 if (div == 0.0f) {
1239 }
1240
1241 lambda = (float(v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
1242
1243 mu = (float(v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
1244
1245 if (lambda >= 0.0f && lambda <= 1.0f && mu >= 0.0f && mu <= 1.0f) {
1246 if (lambda == 0.0f || lambda == 1.0f || mu == 0.0f || mu == 1.0f) {
1247 return ISECT_LINE_LINE_EXACT;
1248 }
1249 return ISECT_LINE_LINE_CROSS;
1250 }
1251 return ISECT_LINE_LINE_NONE;
1252}
1253
1254void isect_seg_seg_v3(const float a0[3],
1255 const float a1[3],
1256 const float b0[3],
1257 const float b1[3],
1258 float r_a[3],
1259 float r_b[3])
1260{
1261 float fac_a, fac_b;
1262 float a_dir[3], b_dir[3], a0b0[3], crs_ab[3];
1263 sub_v3_v3v3(a_dir, a1, a0);
1264 sub_v3_v3v3(b_dir, b1, b0);
1265 sub_v3_v3v3(a0b0, b0, a0);
1266 cross_v3_v3v3(crs_ab, b_dir, a_dir);
1267 const float nlen = len_squared_v3(crs_ab);
1268
1269 if (nlen == 0.0f) {
1270 /* Parallel Lines */
1271 /* In this case return any point that
1272 * is between the closest segments. */
1273 float a0b1[3], a1b0[3], len_a, len_b, fac1, fac2;
1274 sub_v3_v3v3(a0b1, b1, a0);
1275 sub_v3_v3v3(a1b0, b0, a1);
1276 len_a = len_squared_v3(a_dir);
1277 len_b = len_squared_v3(b_dir);
1278
1279 if (len_a) {
1280 fac1 = dot_v3v3(a0b0, a_dir);
1281 fac2 = dot_v3v3(a0b1, a_dir);
1282 CLAMP(fac1, 0.0f, len_a);
1283 CLAMP(fac2, 0.0f, len_a);
1284 fac_a = (fac1 + fac2) / (2 * len_a);
1285 }
1286 else {
1287 fac_a = 0.0f;
1288 }
1289
1290 if (len_b) {
1291 fac1 = -dot_v3v3(a0b0, b_dir);
1292 fac2 = -dot_v3v3(a1b0, b_dir);
1293 CLAMP(fac1, 0.0f, len_b);
1294 CLAMP(fac2, 0.0f, len_b);
1295 fac_b = (fac1 + fac2) / (2 * len_b);
1296 }
1297 else {
1298 fac_b = 0.0f;
1299 }
1300 }
1301 else {
1302 float c[3], cray[3];
1303 sub_v3_v3v3(c, crs_ab, a0b0);
1304
1305 cross_v3_v3v3(cray, c, b_dir);
1306 fac_a = dot_v3v3(cray, crs_ab) / nlen;
1307
1308 cross_v3_v3v3(cray, c, a_dir);
1309 fac_b = dot_v3v3(cray, crs_ab) / nlen;
1310
1311 CLAMP(fac_a, 0.0f, 1.0f);
1312 CLAMP(fac_b, 0.0f, 1.0f);
1313 }
1314
1315 madd_v3_v3v3fl(r_a, a0, a_dir, fac_a);
1316 madd_v3_v3v3fl(r_b, b0, b_dir, fac_b);
1317}
1318
1319int isect_seg_seg_v2_point_ex(const float v0[2],
1320 const float v1[2],
1321 const float v2[2],
1322 const float v3[2],
1323 const float endpoint_bias,
1324 float r_vi[2])
1325{
1326 float s10[2], s32[2], s30[2], d;
1327 const float eps = 1e-6f;
1328 const float endpoint_min = -endpoint_bias;
1329 const float endpoint_max = endpoint_bias + 1.0f;
1330
1331 sub_v2_v2v2(s10, v1, v0);
1332 sub_v2_v2v2(s32, v3, v2);
1333 sub_v2_v2v2(s30, v3, v0);
1334
1335 d = cross_v2v2(s10, s32);
1336
1337 if (d != 0) {
1338 float u, v;
1339
1340 u = cross_v2v2(s30, s32) / d;
1341 v = cross_v2v2(s10, s30) / d;
1342
1343 if ((u >= endpoint_min && u <= endpoint_max) && (v >= endpoint_min && v <= endpoint_max)) {
1344 /* intersection */
1345 float vi_test[2];
1346 float s_vi_v2[2];
1347
1348 madd_v2_v2v2fl(vi_test, v0, s10, u);
1349
1350 /* When 'd' approaches zero, float precision lets non-overlapping co-linear segments
1351 * detect as an intersection. So re-calculate 'v' to ensure the point overlaps both.
1352 * see #45123 */
1353
1354 /* inline since we have most vars already */
1355#if 0
1356 v = line_point_factor_v2(ix_test, v2, v3);
1357#else
1358 sub_v2_v2v2(s_vi_v2, vi_test, v2);
1359 v = (dot_v2v2(s32, s_vi_v2) / dot_v2v2(s32, s32));
1360#endif
1361 if (v >= endpoint_min && v <= endpoint_max) {
1362 copy_v2_v2(r_vi, vi_test);
1363 return 1;
1364 }
1365 }
1366
1367 /* out of segment intersection */
1368 return -1;
1369 }
1370
1371 if ((cross_v2v2(s10, s30) == 0.0f) && (cross_v2v2(s32, s30) == 0.0f)) {
1372 /* equal lines */
1373 float s20[2];
1374 float u_a, u_b;
1375
1376 if (equals_v2v2(v0, v1)) {
1377 if (len_squared_v2v2(v2, v3) > square_f(eps)) {
1378 /* use non-point segment as basis */
1379 std::swap(v0, v2);
1380 std::swap(v1, v3);
1381
1382 sub_v2_v2v2(s10, v1, v0);
1383 sub_v2_v2v2(s30, v3, v0);
1384 }
1385 else { /* both of segments are points */
1386 if (equals_v2v2(v0, v2)) { /* points are equal */
1387 copy_v2_v2(r_vi, v0);
1388 return 1;
1389 }
1390
1391 /* two different points */
1392 return -1;
1393 }
1394 }
1395
1396 sub_v2_v2v2(s20, v2, v0);
1397
1398 u_a = dot_v2v2(s20, s10) / dot_v2v2(s10, s10);
1399 u_b = dot_v2v2(s30, s10) / dot_v2v2(s10, s10);
1400
1401 if (u_a > u_b) {
1402 std::swap(u_a, u_b);
1403 }
1404
1405 if (u_a > endpoint_max || u_b < endpoint_min) {
1406 /* non-overlapping segments */
1407 return -1;
1408 }
1409 if (max_ff(0.0f, u_a) == min_ff(1.0f, u_b)) {
1410 /* one common point: can return result */
1411 madd_v2_v2v2fl(r_vi, v0, s10, max_ff(0, u_a));
1412 return 1;
1413 }
1414 }
1415
1416 /* lines are collinear */
1417 return -1;
1418}
1419
1421 const float v0[2], const float v1[2], const float v2[2], const float v3[2], float r_vi[2])
1422{
1423 const float endpoint_bias = 1e-6f;
1424 return isect_seg_seg_v2_point_ex(v0, v1, v2, v3, endpoint_bias, r_vi);
1425}
1426
1427bool isect_seg_seg_v2_simple(const float v1[2],
1428 const float v2[2],
1429 const float v3[2],
1430 const float v4[2])
1431{
1432#define CCW(A, B, C) ((C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0]))
1433
1434 return CCW(v1, v3, v4) != CCW(v2, v3, v4) && CCW(v1, v2, v3) != CCW(v1, v2, v4);
1435
1436#undef CCW
1437}
1438
1439int isect_seg_seg_v2_lambda_mu_db(const double v1[2],
1440 const double v2[2],
1441 const double v3[2],
1442 const double v4[2],
1443 double *r_lambda,
1444 double *r_mu)
1445{
1446 double div, lambda, mu;
1447
1448 div = (v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]);
1449 if (fabs(div) < DBL_EPSILON) {
1451 }
1452
1453 lambda = ((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
1454
1455 mu = ((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
1456
1457 if (r_lambda) {
1458 *r_lambda = lambda;
1459 }
1460 if (r_mu) {
1461 *r_mu = mu;
1462 }
1463
1464 if (lambda >= 0.0 && lambda <= 1.0 && mu >= 0.0 && mu <= 1.0) {
1465 if (lambda == 0.0 || lambda == 1.0 || mu == 0.0 || mu == 1.0) {
1466 return ISECT_LINE_LINE_EXACT;
1467 }
1468 return ISECT_LINE_LINE_CROSS;
1469 }
1470 return ISECT_LINE_LINE_NONE;
1471}
1472
1473int isect_line_sphere_v3(const float l1[3],
1474 const float l2[3],
1475 const float sp[3],
1476 const float r,
1477 float r_p1[3],
1478 float r_p2[3])
1479{
1480 /* Adapted for use in blender by Campbell Barton, 2011.
1481 *
1482 * http://www.iebele.nl
1483 * `Atelier Iebele Abel <atelier@iebele.nl>` - 2001.
1484 *
1485 * sphere_line_intersection function adapted from:
1486 * http://astronomy.swin.edu.au/pbourke/geometry/sphereline
1487 * `Paul Bourke <pbourke@swin.edu.au>`. */
1488
1489 const float ldir[3] = {
1490 l2[0] - l1[0],
1491 l2[1] - l1[1],
1492 l2[2] - l1[2],
1493 };
1494
1495 const float a = len_squared_v3(ldir);
1496
1497 const float b = 2.0f * (ldir[0] * (l1[0] - sp[0]) + ldir[1] * (l1[1] - sp[1]) +
1498 ldir[2] * (l1[2] - sp[2]));
1499
1500 const float c = len_squared_v3(sp) + len_squared_v3(l1) - (2.0f * dot_v3v3(sp, l1)) - (r * r);
1501
1502 const float i = b * b - 4.0f * a * c;
1503
1504 float mu;
1505
1506 if (i < 0.0f) {
1507 /* no intersections */
1508 return 0;
1509 }
1510 if (i == 0.0f) {
1511 /* one intersection */
1512 mu = -b / (2.0f * a);
1513 madd_v3_v3v3fl(r_p1, l1, ldir, mu);
1514 return 1;
1515 }
1516 if (i > 0.0f) {
1517 const float i_sqrt = sqrtf(i); /* avoid calc twice */
1518
1519 /* first intersection */
1520 mu = (-b + i_sqrt) / (2.0f * a);
1521 madd_v3_v3v3fl(r_p1, l1, ldir, mu);
1522
1523 /* second intersection */
1524 mu = (-b - i_sqrt) / (2.0f * a);
1525 madd_v3_v3v3fl(r_p2, l1, ldir, mu);
1526 return 2;
1527 }
1528
1529 /* math domain error - nan */
1530 return -1;
1531}
1532
1533int isect_line_sphere_v2(const float l1[2],
1534 const float l2[2],
1535 const float sp[2],
1536 const float r,
1537 float r_p1[2],
1538 float r_p2[2])
1539{
1540 /* Keep in sync with #isect_line_sphere_v3. */
1541
1542 const float ldir[2] = {l2[0] - l1[0], l2[1] - l1[1]};
1543
1544 const float a = dot_v2v2(ldir, ldir);
1545
1546 const float b = 2.0f * (ldir[0] * (l1[0] - sp[0]) + ldir[1] * (l1[1] - sp[1]));
1547
1548 const float c = dot_v2v2(sp, sp) + dot_v2v2(l1, l1) - (2.0f * dot_v2v2(sp, l1)) - (r * r);
1549
1550 const float i = b * b - 4.0f * a * c;
1551
1552 float mu;
1553
1554 if (i < 0.0f) {
1555 /* no intersections */
1556 return 0;
1557 }
1558 if (i == 0.0f) {
1559 /* one intersection */
1560 mu = -b / (2.0f * a);
1561 madd_v2_v2v2fl(r_p1, l1, ldir, mu);
1562 return 1;
1563 }
1564 if (i > 0.0f) {
1565 const float i_sqrt = sqrtf(i); /* avoid calc twice */
1566
1567 /* first intersection */
1568 mu = (-b + i_sqrt) / (2.0f * a);
1569 madd_v2_v2v2fl(r_p1, l1, ldir, mu);
1570
1571 /* second intersection */
1572 mu = (-b - i_sqrt) / (2.0f * a);
1573 madd_v2_v2v2fl(r_p2, l1, ldir, mu);
1574 return 2;
1575 }
1576
1577 /* math domain error - nan */
1578 return -1;
1579}
1580
1581bool isect_point_poly_v2(const float pt[2], const float verts[][2], const uint nr)
1582{
1583 /* Keep in sync with #isect_point_poly_v2_int. */
1584
1585 uint i, j;
1586 bool isect = false;
1587 for (i = 0, j = nr - 1; i < nr; j = i++) {
1588 if (((verts[i][1] > pt[1]) != (verts[j][1] > pt[1])) &&
1589 (pt[0] <
1590 (verts[j][0] - verts[i][0]) * (pt[1] - verts[i][1]) / (verts[j][1] - verts[i][1]) +
1591 verts[i][0]))
1592 {
1593 isect = !isect;
1594 }
1595 }
1596 return isect;
1597}
1598bool isect_point_poly_v2_int(const int pt[2], const int verts[][2], const uint nr)
1599{
1600 /* Keep in sync with #isect_point_poly_v2. */
1601
1602 uint i, j;
1603 bool isect = false;
1604 for (i = 0, j = nr - 1; i < nr; j = i++) {
1605 if (((verts[i][1] > pt[1]) != (verts[j][1] > pt[1])) &&
1606 (pt[0] <
1607 (verts[j][0] - verts[i][0]) * (pt[1] - verts[i][1]) / (verts[j][1] - verts[i][1]) +
1608 verts[i][0]))
1609 {
1610 isect = !isect;
1611 }
1612 }
1613 return isect;
1614}
1615
1616/* point in tri */
1617
1618bool isect_point_tri_v2_cw(const float pt[2],
1619 const float v1[2],
1620 const float v2[2],
1621 const float v3[2])
1622{
1623 if (line_point_side_v2(v1, v2, pt) >= 0.0f) {
1624 if (line_point_side_v2(v2, v3, pt) >= 0.0f) {
1625 if (line_point_side_v2(v3, v1, pt) >= 0.0f) {
1626 return true;
1627 }
1628 }
1629 }
1630
1631 return false;
1632}
1633
1634int isect_point_tri_v2(const float pt[2], const float v1[2], const float v2[2], const float v3[2])
1635{
1636 float side12 = line_point_side_v2(v1, v2, pt);
1637 float side23 = line_point_side_v2(v2, v3, pt);
1638 float side31 = line_point_side_v2(v3, v1, pt);
1639 if (side12 >= 0.0f && side23 >= 0.0f && side31 >= 0.0f) {
1640 return 1;
1641 }
1642 if (side12 <= 0.0f && side23 <= 0.0f && side31 <= 0.0f) {
1643 return -1;
1644 }
1645
1646 return 0;
1647}
1648
1650 const float p[2], const float v1[2], const float v2[2], const float v3[2], const float v4[2])
1651{
1652 float side12 = line_point_side_v2(v1, v2, p);
1653 float side23 = line_point_side_v2(v2, v3, p);
1654 float side34 = line_point_side_v2(v3, v4, p);
1655 float side41 = line_point_side_v2(v4, v1, p);
1656 if (side12 >= 0.0f && side23 >= 0.0f && side34 >= 0.0f && side41 >= 0.0f) {
1657 return 1;
1658 }
1659 if (side12 <= 0.0f && side23 <= 0.0f && side34 <= 0.0f && side41 <= 0.0f) {
1660 return -1;
1661 }
1662 return 0;
1663}
1664
1665bool isect_line_segment_tri_v3(const float p1[3],
1666 const float p2[3],
1667 const float v0[3],
1668 const float v1[3],
1669 const float v2[3],
1670 float *r_lambda,
1671 float r_uv[2])
1672{
1673
1674 float p[3], s[3], d[3], e1[3], e2[3], q[3];
1675 float a, f, u, v;
1676
1677 sub_v3_v3v3(e1, v1, v0);
1678 sub_v3_v3v3(e2, v2, v0);
1679 sub_v3_v3v3(d, p2, p1);
1680
1681 cross_v3_v3v3(p, d, e2);
1682 a = dot_v3v3(e1, p);
1683 if (a == 0.0f) {
1684 return false;
1685 }
1686 f = 1.0f / a;
1687
1688 sub_v3_v3v3(s, p1, v0);
1689
1690 u = f * dot_v3v3(s, p);
1691 if ((u < 0.0f) || (u > 1.0f)) {
1692 return false;
1693 }
1694
1695 cross_v3_v3v3(q, s, e1);
1696
1697 v = f * dot_v3v3(d, q);
1698 if ((v < 0.0f) || ((u + v) > 1.0f)) {
1699 return false;
1700 }
1701
1702 *r_lambda = f * dot_v3v3(e2, q);
1703 if ((*r_lambda < 0.0f) || (*r_lambda > 1.0f)) {
1704 return false;
1705 }
1706
1707 if (r_uv) {
1708 r_uv[0] = u;
1709 r_uv[1] = v;
1710 }
1711
1712 return true;
1713}
1714
1715bool isect_line_tri_v3(const float p1[3],
1716 const float p2[3],
1717 const float v0[3],
1718 const float v1[3],
1719 const float v2[3],
1720 float *r_lambda,
1721 float r_uv[2])
1722{
1723 float p[3], s[3], d[3], e1[3], e2[3], q[3];
1724 float a, f, u, v;
1725
1726 sub_v3_v3v3(e1, v1, v0);
1727 sub_v3_v3v3(e2, v2, v0);
1728 sub_v3_v3v3(d, p2, p1);
1729
1730 cross_v3_v3v3(p, d, e2);
1731 a = dot_v3v3(e1, p);
1732 if (a == 0.0f) {
1733 return false;
1734 }
1735 f = 1.0f / a;
1736
1737 sub_v3_v3v3(s, p1, v0);
1738
1739 u = f * dot_v3v3(s, p);
1740 if ((u < 0.0f) || (u > 1.0f)) {
1741 return false;
1742 }
1743
1744 cross_v3_v3v3(q, s, e1);
1745
1746 v = f * dot_v3v3(d, q);
1747 if ((v < 0.0f) || ((u + v) > 1.0f)) {
1748 return false;
1749 }
1750
1751 *r_lambda = f * dot_v3v3(e2, q);
1752
1753 if (r_uv) {
1754 r_uv[0] = u;
1755 r_uv[1] = v;
1756 }
1757
1758 return true;
1759}
1760
1762 const float p2[3],
1763 const float v0[3],
1764 const float v1[3],
1765 const float v2[3],
1766 float *r_lambda,
1767 float r_uv[2],
1768 const float epsilon)
1769{
1770
1771 float p[3], s[3], d[3], e1[3], e2[3], q[3];
1772 float a, f, u, v;
1773
1774 sub_v3_v3v3(e1, v1, v0);
1775 sub_v3_v3v3(e2, v2, v0);
1776 sub_v3_v3v3(d, p2, p1);
1777
1778 cross_v3_v3v3(p, d, e2);
1779 a = dot_v3v3(e1, p);
1780 if (a == 0.0f) {
1781 return false;
1782 }
1783 f = 1.0f / a;
1784
1785 sub_v3_v3v3(s, p1, v0);
1786
1787 u = f * dot_v3v3(s, p);
1788 if ((u < -epsilon) || (u > 1.0f + epsilon)) {
1789 return false;
1790 }
1791
1792 cross_v3_v3v3(q, s, e1);
1793
1794 v = f * dot_v3v3(d, q);
1795 if ((v < -epsilon) || ((u + v) > 1.0f + epsilon)) {
1796 return false;
1797 }
1798
1799 *r_lambda = f * dot_v3v3(e2, q);
1800 if ((*r_lambda < 0.0f) || (*r_lambda > 1.0f)) {
1801 return false;
1802 }
1803
1804 if (r_uv) {
1805 r_uv[0] = u;
1806 r_uv[1] = v;
1807 }
1808
1809 return true;
1810}
1811
1812bool isect_ray_tri_v3(const float ray_origin[3],
1813 const float ray_direction[3],
1814 const float v0[3],
1815 const float v1[3],
1816 const float v2[3],
1817 float *r_lambda,
1818 float r_uv[2])
1819{
1820 /* NOTE(@ideasman42): these values were 0.000001 in 2.4x but for projection snapping on
1821 * a human head `(1BU == 1m)`, subdivision-surface level 2, this gave many errors. */
1822 const float epsilon = 0.00000001f;
1823 float p[3], s[3], e1[3], e2[3], q[3];
1824 float a, f, u, v;
1825
1826 sub_v3_v3v3(e1, v1, v0);
1827 sub_v3_v3v3(e2, v2, v0);
1828
1829 cross_v3_v3v3(p, ray_direction, e2);
1830 a = dot_v3v3(e1, p);
1831 if ((a > -epsilon) && (a < epsilon)) {
1832 return false;
1833 }
1834 f = 1.0f / a;
1835
1836 sub_v3_v3v3(s, ray_origin, v0);
1837
1838 u = f * dot_v3v3(s, p);
1839 if ((u < 0.0f) || (u > 1.0f)) {
1840 return false;
1841 }
1842
1843 cross_v3_v3v3(q, s, e1);
1844
1845 v = f * dot_v3v3(ray_direction, q);
1846 if ((v < 0.0f) || ((u + v) > 1.0f)) {
1847 return false;
1848 }
1849
1850 *r_lambda = f * dot_v3v3(e2, q);
1851 if (*r_lambda < 0.0f) {
1852 return false;
1853 }
1854
1855 if (r_uv) {
1856 r_uv[0] = u;
1857 r_uv[1] = v;
1858 }
1859
1860 return true;
1861}
1862
1863bool isect_ray_plane_v3_factor(const float ray_origin[3],
1864 const float ray_direction[3],
1865 const float plane_co[3],
1866 const float plane_no[3],
1867 float *r_lambda)
1868{
1869 float h[3];
1870 float dot = dot_v3v3(plane_no, ray_direction);
1871 if (dot == 0.0f) {
1872 return false;
1873 }
1874 sub_v3_v3v3(h, ray_origin, plane_co);
1875 *r_lambda = -dot_v3v3(plane_no, h) / dot;
1876 return true;
1877}
1878
1879bool isect_ray_plane_v3(const float ray_origin[3],
1880 const float ray_direction[3],
1881 const float plane[4],
1882 float *r_lambda,
1883 const bool clip)
1884{
1885 float plane_co[3], plane_no[3];
1886 plane_to_point_vector_v3(plane, plane_co, plane_no);
1887 if (!isect_ray_plane_v3_factor(ray_origin, ray_direction, plane_co, plane_no, r_lambda)) {
1888 return false;
1889 }
1890 if (clip && (*r_lambda < 0.0f)) {
1891 return false;
1892 }
1893 return true;
1894}
1895
1896bool isect_ray_tri_epsilon_v3(const float ray_origin[3],
1897 const float ray_direction[3],
1898 const float v0[3],
1899 const float v1[3],
1900 const float v2[3],
1901 float *r_lambda,
1902 float r_uv[2],
1903 const float epsilon)
1904{
1905 float p[3], s[3], e1[3], e2[3], q[3];
1906 float a, f, u, v;
1907
1908 sub_v3_v3v3(e1, v1, v0);
1909 sub_v3_v3v3(e2, v2, v0);
1910
1911 cross_v3_v3v3(p, ray_direction, e2);
1912 a = dot_v3v3(e1, p);
1913 if (a == 0.0f) {
1914 return false;
1915 }
1916 f = 1.0f / a;
1917
1918 sub_v3_v3v3(s, ray_origin, v0);
1919
1920 u = f * dot_v3v3(s, p);
1921 if ((u < -epsilon) || (u > 1.0f + epsilon)) {
1922 return false;
1923 }
1924
1925 cross_v3_v3v3(q, s, e1);
1926
1927 v = f * dot_v3v3(ray_direction, q);
1928 if ((v < -epsilon) || ((u + v) > 1.0f + epsilon)) {
1929 return false;
1930 }
1931
1932 *r_lambda = f * dot_v3v3(e2, q);
1933 if (*r_lambda < 0.0f) {
1934 return false;
1935 }
1936
1937 if (r_uv) {
1938 r_uv[0] = u;
1939 r_uv[1] = v;
1940 }
1941
1942 return true;
1943}
1944
1946 const float ray_direction[3])
1947{
1948 float inv_dir_z;
1949
1950 /* Calculate dimension where the ray direction is maximal. */
1951 int kz = axis_dominant_v3_single(ray_direction);
1952 int kx = (kz != 2) ? (kz + 1) : 0;
1953 int ky = (kx != 2) ? (kx + 1) : 0;
1954
1955 /* Swap kx and ky dimensions to preserve winding direction of triangles. */
1956 if (ray_direction[kz] < 0.0f) {
1957 std::swap(kx, ky);
1958 }
1959
1960 /* Calculate the shear constants. */
1961 inv_dir_z = 1.0f / ray_direction[kz];
1962 isect_precalc->sx = ray_direction[kx] * inv_dir_z;
1963 isect_precalc->sy = ray_direction[ky] * inv_dir_z;
1964 isect_precalc->sz = inv_dir_z;
1965
1966 /* Store the dimensions. */
1967 isect_precalc->kx = kx;
1968 isect_precalc->ky = ky;
1969 isect_precalc->kz = kz;
1970}
1971
1972bool isect_ray_tri_watertight_v3(const float ray_origin[3],
1973 const IsectRayPrecalc *isect_precalc,
1974 const float v0[3],
1975 const float v1[3],
1976 const float v2[3],
1977 float *r_lambda,
1978 float r_uv[2])
1979{
1980 const int kx = isect_precalc->kx;
1981 const int ky = isect_precalc->ky;
1982 const int kz = isect_precalc->kz;
1983 const float sx = isect_precalc->sx;
1984 const float sy = isect_precalc->sy;
1985 const float sz = isect_precalc->sz;
1986
1987 /* Calculate vertices relative to ray origin. */
1988 const float a[3] = {v0[0] - ray_origin[0], v0[1] - ray_origin[1], v0[2] - ray_origin[2]};
1989 const float b[3] = {v1[0] - ray_origin[0], v1[1] - ray_origin[1], v1[2] - ray_origin[2]};
1990 const float c[3] = {v2[0] - ray_origin[0], v2[1] - ray_origin[1], v2[2] - ray_origin[2]};
1991
1992 const float a_kx = a[kx], a_ky = a[ky], a_kz = a[kz];
1993 const float b_kx = b[kx], b_ky = b[ky], b_kz = b[kz];
1994 const float c_kx = c[kx], c_ky = c[ky], c_kz = c[kz];
1995
1996 /* Perform shear and scale of vertices. */
1997 const float ax = a_kx - sx * a_kz;
1998 const float ay = a_ky - sy * a_kz;
1999 const float bx = b_kx - sx * b_kz;
2000 const float by = b_ky - sy * b_kz;
2001 const float cx = c_kx - sx * c_kz;
2002 const float cy = c_ky - sy * c_kz;
2003
2004 /* Calculate scaled barycentric coordinates. */
2005 const float u = cx * by - cy * bx;
2006 const float v = ax * cy - ay * cx;
2007 const float w = bx * ay - by * ax;
2008 float det;
2009
2010 if ((u < 0.0f || v < 0.0f || w < 0.0f) && (u > 0.0f || v > 0.0f || w > 0.0f)) {
2011 return false;
2012 }
2013
2014 /* Calculate determinant. */
2015 det = u + v + w;
2016 if (det == 0.0f || !isfinite(det)) [[unlikely]] {
2017 return false;
2018 }
2019
2020 /* Calculate scaled z-coordinates of vertices and use them to calculate
2021 * the hit distance.
2022 */
2023 const int sign_det = (float_as_int(det) & int(0x80000000));
2024 const float t = (u * a_kz + v * b_kz + w * c_kz) * sz;
2025 const float sign_t = xor_fl(t, sign_det);
2026 if ((sign_t < 0.0f)
2027 /* Differ from Cycles, don't read r_lambda's original value
2028 * otherwise we won't match any of the other intersect functions here...
2029 * which would be confusing. */
2030#if 0
2031 || (sign_T > *r_lambda * xor_signmask(det, sign_mask))
2032#endif
2033 )
2034 {
2035 return false;
2036 }
2037
2038 /* Normalize u, v and t. */
2039 const float inv_det = 1.0f / det;
2040 if (r_uv) {
2041 r_uv[0] = u * inv_det;
2042 r_uv[1] = v * inv_det;
2043 }
2044 *r_lambda = t * inv_det;
2045 return true;
2046}
2047
2048bool isect_ray_tri_watertight_v3_simple(const float ray_origin[3],
2049 const float ray_direction[3],
2050 const float v0[3],
2051 const float v1[3],
2052 const float v2[3],
2053 float *r_lambda,
2054 float r_uv[2])
2055{
2056 IsectRayPrecalc isect_precalc;
2057 isect_ray_tri_watertight_v3_precalc(&isect_precalc, ray_direction);
2058 return isect_ray_tri_watertight_v3(ray_origin, &isect_precalc, v0, v1, v2, r_lambda, r_uv);
2059}
2060
2061#if 0 /* UNUSED */
2066bool isect_ray_tri_threshold_v3(const float ray_origin[3],
2067 const float ray_direction[3],
2068 const float v0[3],
2069 const float v1[3],
2070 const float v2[3],
2071 float *r_lambda,
2072 float r_uv[2],
2073 const float threshold)
2074{
2075 const float epsilon = 0.00000001f;
2076 float p[3], s[3], e1[3], e2[3], q[3];
2077 float a, f, u, v;
2078 float du, dv;
2079
2080 sub_v3_v3v3(e1, v1, v0);
2081 sub_v3_v3v3(e2, v2, v0);
2082
2083 cross_v3_v3v3(p, ray_direction, e2);
2084 a = dot_v3v3(e1, p);
2085 if ((a > -epsilon) && (a < epsilon)) {
2086 return false;
2087 }
2088 f = 1.0f / a;
2089
2090 sub_v3_v3v3(s, ray_origin, v0);
2091
2092 cross_v3_v3v3(q, s, e1);
2093 *r_lambda = f * dot_v3v3(e2, q);
2094 if (*r_lambda < 0.0f) {
2095 return false;
2096 }
2097
2098 u = f * dot_v3v3(s, p);
2099 v = f * dot_v3v3(ray_direction, q);
2100
2101 if (u > 0 && v > 0 && u + v > 1) {
2102 float t = (u + v - 1) / 2;
2103 du = u - t;
2104 dv = v - t;
2105 }
2106 else {
2107 if (u < 0) {
2108 du = u;
2109 }
2110 else if (u > 1) {
2111 du = u - 1;
2112 }
2113 else {
2114 du = 0.0f;
2115 }
2116
2117 if (v < 0) {
2118 dv = v;
2119 }
2120 else if (v > 1) {
2121 dv = v - 1;
2122 }
2123 else {
2124 dv = 0.0f;
2125 }
2126 }
2127
2128 mul_v3_fl(e1, du);
2129 mul_v3_fl(e2, dv);
2130
2131 if (len_squared_v3(e1) + len_squared_v3(e2) > threshold * threshold) {
2132 return false;
2133 }
2134
2135 if (r_uv) {
2136 r_uv[0] = u;
2137 r_uv[1] = v;
2138 }
2139
2140 return true;
2141}
2142#endif
2143
2144bool isect_ray_seg_v2(const float ray_origin[2],
2145 const float ray_direction[2],
2146 const float v0[2],
2147 const float v1[2],
2148 float *r_lambda,
2149 float *r_u)
2150{
2151 float v0_local[2], v1_local[2];
2152 sub_v2_v2v2(v0_local, v0, ray_origin);
2153 sub_v2_v2v2(v1_local, v1, ray_origin);
2154
2155 float s10[2];
2156 float det;
2157
2158 sub_v2_v2v2(s10, v1_local, v0_local);
2159
2160 det = cross_v2v2(ray_direction, s10);
2161 if (det != 0.0f) {
2162 const float v = cross_v2v2(v0_local, v1_local);
2163 const float p[2] = {(ray_direction[0] * v) / det, (ray_direction[1] * v) / det};
2164
2165 const float t = (dot_v2v2(p, ray_direction) / dot_v2v2(ray_direction, ray_direction));
2166 if ((t >= 0.0f) == 0) {
2167 return false;
2168 }
2169
2170 float h[2];
2171 sub_v2_v2v2(h, v1_local, p);
2172 const float u = (dot_v2v2(s10, h) / dot_v2v2(s10, s10));
2173 if ((u >= 0.0f && u <= 1.0f) == 0) {
2174 return false;
2175 }
2176
2177 if (r_lambda) {
2178 *r_lambda = t;
2179 }
2180 if (r_u) {
2181 *r_u = u;
2182 }
2183
2184 return true;
2185 }
2186
2187 return false;
2188}
2189
2190bool isect_ray_line_v3(const float ray_origin[3],
2191 const float ray_direction[3],
2192 const float v0[3],
2193 const float v1[3],
2194 float *r_lambda)
2195{
2196 float a[3], t[3], n[3];
2197 sub_v3_v3v3(a, v1, v0);
2198 sub_v3_v3v3(t, v0, ray_origin);
2199 cross_v3_v3v3(n, a, ray_direction);
2200 const float nlen = len_squared_v3(n);
2201
2202 if (nlen == 0.0f) {
2203 /* The lines are parallel. */
2204 return false;
2205 }
2206
2207 /* The following lines use a math trick to do the same thing as:
2208 * <pre>
2209 * const float numerator = dot_v3v3(t, ray_direction) * dot_v3v3(a, ray_direction) -
2210 * dot_v3v3(t, a) * len_squared_v3(ray_direction);
2211 *
2212 * *r_lambda = numerator / nlen;
2213 * </pre> */
2214
2215 float c[3], cray[3];
2216 sub_v3_v3v3(c, n, t);
2217 cross_v3_v3v3(cray, c, ray_direction);
2218
2219 *r_lambda = dot_v3v3(cray, n) / nlen;
2220
2221 return true;
2222}
2223
2224bool isect_point_planes_v3(const float (*planes)[4], int totplane, const float p[3])
2225{
2226 int i;
2227
2228 for (i = 0; i < totplane; i++) {
2229 if (plane_point_side_v3(planes[i], p) > 0.0f) {
2230 return false;
2231 }
2232 }
2233
2234 return true;
2235}
2236
2237bool isect_point_planes_v3_negated(const float (*planes)[4], const int totplane, const float p[3])
2238{
2239 for (int i = 0; i < totplane; i++) {
2240 if (plane_point_side_v3(planes[i], p) <= 0.0f) {
2241 return false;
2242 }
2243 }
2244
2245 return true;
2246}
2247
2248bool isect_line_plane_v3(float r_isect_co[3],
2249 const float l1[3],
2250 const float l2[3],
2251 const float plane_co[3],
2252 const float plane_no[3])
2253{
2254 float u[3], h[3];
2255 float dot;
2256
2257 sub_v3_v3v3(u, l2, l1);
2258 sub_v3_v3v3(h, l1, plane_co);
2259 dot = dot_v3v3(plane_no, u);
2260
2261 if (fabsf(dot) > FLT_EPSILON) {
2262 float lambda = -dot_v3v3(plane_no, h) / dot;
2263 madd_v3_v3v3fl(r_isect_co, l1, u, lambda);
2264 return true;
2265 }
2266
2267 /* The segment is parallel to plane */
2268 return false;
2269}
2270
2271bool isect_plane_plane_plane_v3(const float plane_a[4],
2272 const float plane_b[4],
2273 const float plane_c[4],
2274 float r_isect_co[3])
2275{
2276 float det;
2277
2278 det = determinant_m3(UNPACK3(plane_a), UNPACK3(plane_b), UNPACK3(plane_c));
2279
2280 if (det != 0.0f) {
2281 float tmp[3];
2282
2283 /* (plane_b.xyz.cross(plane_c.xyz) * -plane_a[3] +
2284 * plane_c.xyz.cross(plane_a.xyz) * -plane_b[3] +
2285 * plane_a.xyz.cross(plane_b.xyz) * -plane_c[3]) / det; */
2286
2287 cross_v3_v3v3(tmp, plane_c, plane_b);
2288 mul_v3_v3fl(r_isect_co, tmp, plane_a[3]);
2289
2290 cross_v3_v3v3(tmp, plane_a, plane_c);
2291 madd_v3_v3fl(r_isect_co, tmp, plane_b[3]);
2292
2293 cross_v3_v3v3(tmp, plane_b, plane_a);
2294 madd_v3_v3fl(r_isect_co, tmp, plane_c[3]);
2295
2296 mul_v3_fl(r_isect_co, 1.0f / det);
2297
2298 return true;
2299 }
2300
2301 return false;
2302}
2303
2304bool isect_plane_plane_v3(const float plane_a[4],
2305 const float plane_b[4],
2306 float r_isect_co[3],
2307 float r_isect_no[3])
2308{
2309 float det, plane_c[3];
2310
2311 /* direction is simply the cross product */
2312 cross_v3_v3v3(plane_c, plane_a, plane_b);
2313
2314 /* in this case we don't need to use 'determinant_m3' */
2315 det = len_squared_v3(plane_c);
2316
2317 if (det != 0.0f) {
2318 float tmp[3];
2319
2320 /* (plane_b.xyz.cross(plane_c.xyz) * -plane_a[3] +
2321 * plane_c.xyz.cross(plane_a.xyz) * -plane_b[3]) / det; */
2322 cross_v3_v3v3(tmp, plane_c, plane_b);
2323 mul_v3_v3fl(r_isect_co, tmp, plane_a[3]);
2324
2325 cross_v3_v3v3(tmp, plane_a, plane_c);
2326 madd_v3_v3fl(r_isect_co, tmp, plane_b[3]);
2327
2328 mul_v3_fl(r_isect_co, 1.0f / det);
2329
2330 copy_v3_v3(r_isect_no, plane_c);
2331
2332 return true;
2333 }
2334
2335 return false;
2336}
2337
2339 const float planes[][4],
2340 const int planes_len,
2341 const float eps_coplanar,
2342 const float eps_isect,
2343 void (*callback_fn)(const float co[3], int i, int j, int k, void *user_data),
2344 void *user_data)
2345{
2346 bool found = false;
2347
2348 float n1n2[3], n2n3[3], n3n1[3];
2349
2350 for (int i = 0; i < planes_len; i++) {
2351 const float *n1 = planes[i];
2352 for (int j = i + 1; j < planes_len; j++) {
2353 const float *n2 = planes[j];
2354 cross_v3_v3v3(n1n2, n1, n2);
2355 if (len_squared_v3(n1n2) <= eps_coplanar) {
2356 continue;
2357 }
2358 for (int k = j + 1; k < planes_len; k++) {
2359 const float *n3 = planes[k];
2360 cross_v3_v3v3(n2n3, n2, n3);
2361 if (len_squared_v3(n2n3) <= eps_coplanar) {
2362 continue;
2363 }
2364
2365 cross_v3_v3v3(n3n1, n3, n1);
2366 if (len_squared_v3(n3n1) <= eps_coplanar) {
2367 continue;
2368 }
2369 const float quotient = -dot_v3v3(n1, n2n3);
2370 if (fabsf(quotient) < eps_coplanar) {
2371 continue;
2372 }
2373 const float co_test[3] = {
2374 ((n2n3[0] * n1[3]) + (n3n1[0] * n2[3]) + (n1n2[0] * n3[3])) / quotient,
2375 ((n2n3[1] * n1[3]) + (n3n1[1] * n2[3]) + (n1n2[1] * n3[3])) / quotient,
2376 ((n2n3[2] * n1[3]) + (n3n1[2] * n2[3]) + (n1n2[2] * n3[3])) / quotient,
2377 };
2378 int i_test;
2379 for (i_test = 0; i_test < planes_len; i_test++) {
2380 const float *np_test = planes[i_test];
2381 if ((dot_v3v3(np_test, co_test) + np_test[3]) > eps_isect) {
2382 /* For low epsilon values the point could intersect its own plane. */
2383 if (!ELEM(i_test, i, j, k)) {
2384 break;
2385 }
2386 }
2387 }
2388
2389 if (i_test == planes_len) { /* ok */
2390 callback_fn(co_test, i, j, k, user_data);
2391 found = true;
2392 }
2393 }
2394 }
2395 }
2396
2397 return found;
2398}
2399
2400bool isect_tri_tri_v3_ex(const float tri_a[3][3],
2401 const float tri_b[3][3],
2402 float r_i1[3],
2403 float r_i2[3],
2404 int *r_tri_a_edge_isect_count)
2405{
2406 struct {
2407 /* Factor that indicates the position of the intersection point on the line
2408 * that intersects the planes of the triangles. */
2409 float min, max;
2410 /* Intersection point location. */
2411 float loc[2][3];
2412 } range[2];
2413
2414 float side[2][3];
2415 double ba[3], bc[3], plane_a[4], plane_b[4];
2416 *r_tri_a_edge_isect_count = 0;
2417
2418 sub_v3db_v3fl_v3fl(ba, tri_a[0], tri_a[1]);
2419 sub_v3db_v3fl_v3fl(bc, tri_a[2], tri_a[1]);
2420 cross_v3_v3v3_db(plane_a, ba, bc);
2421 plane_a[3] = -dot_v3db_v3fl(plane_a, tri_a[1]);
2422 side[1][0] = float(dot_v3db_v3fl(plane_a, tri_b[0]) + plane_a[3]);
2423 side[1][1] = float(dot_v3db_v3fl(plane_a, tri_b[1]) + plane_a[3]);
2424 side[1][2] = float(dot_v3db_v3fl(plane_a, tri_b[2]) + plane_a[3]);
2425
2426 if (!side[1][0] && !side[1][1] && !side[1][2]) {
2427 /* Coplanar case is not supported. */
2428 return false;
2429 }
2430
2431 if ((side[1][0] && side[1][1] && side[1][2]) && (side[1][0] < 0.0f) == (side[1][1] < 0.0f) &&
2432 (side[1][0] < 0.0f) == (side[1][2] < 0.0f))
2433 {
2434 /* All vertices of the 2nd triangle are positioned on the same side to the
2435 * plane defined by the 1st triangle. */
2436 return false;
2437 }
2438
2439 sub_v3db_v3fl_v3fl(ba, tri_b[0], tri_b[1]);
2440 sub_v3db_v3fl_v3fl(bc, tri_b[2], tri_b[1]);
2441 cross_v3_v3v3_db(plane_b, ba, bc);
2442 plane_b[3] = -dot_v3db_v3fl(plane_b, tri_b[1]);
2443 side[0][0] = float(dot_v3db_v3fl(plane_b, tri_a[0]) + plane_b[3]);
2444 side[0][1] = float(dot_v3db_v3fl(plane_b, tri_a[1]) + plane_b[3]);
2445 side[0][2] = float(dot_v3db_v3fl(plane_b, tri_a[2]) + plane_b[3]);
2446
2447 if ((side[0][0] && side[0][1] && side[0][2]) && (side[0][0] < 0.0f) == (side[0][1] < 0.0f) &&
2448 (side[0][0] < 0.0f) == (side[0][2] < 0.0f))
2449 {
2450 /* All vertices of the 1st triangle are positioned on the same side to the
2451 * plane defined by the 2nd triangle. */
2452 return false;
2453 }
2454
2455 /* Direction of the line that intersects the planes of the triangles. */
2456 double isect_dir[3];
2457 cross_v3_v3v3_db(isect_dir, plane_a, plane_b);
2458 for (int i = 0; i < 2; i++) {
2459 const float (*tri)[3] = i == 0 ? tri_a : tri_b;
2460 /* Rearrange the triangle so that the vertex that is alone on one side
2461 * of the plane is located at index 1. */
2462 int tri_i[3];
2463 if ((side[i][0] && side[i][1]) && (side[i][0] < 0.0f) == (side[i][1] < 0.0f)) {
2464 tri_i[0] = 1;
2465 tri_i[1] = 2;
2466 tri_i[2] = 0;
2467 }
2468 else if ((side[i][1] && side[i][2]) && (side[i][1] < 0.0f) == (side[i][2] < 0.0f)) {
2469 tri_i[0] = 2;
2470 tri_i[1] = 0;
2471 tri_i[2] = 1;
2472 }
2473 else {
2474 tri_i[0] = 0;
2475 tri_i[1] = 1;
2476 tri_i[2] = 2;
2477 }
2478
2479 double dot_b = dot_v3db_v3fl(isect_dir, tri[tri_i[1]]);
2480 float sidec = side[i][tri_i[1]];
2481 if (sidec) {
2482 double dot_a = dot_v3db_v3fl(isect_dir, tri[tri_i[0]]);
2483 double dot_c = dot_v3db_v3fl(isect_dir, tri[tri_i[2]]);
2484 float fac0 = sidec / (sidec - side[i][tri_i[0]]);
2485 float fac1 = sidec / (sidec - side[i][tri_i[2]]);
2486 double offset0 = fac0 * (dot_a - dot_b);
2487 double offset1 = fac1 * (dot_c - dot_b);
2488 if (offset0 > offset1) {
2489 /* Sort min max. */
2490 std::swap(offset0, offset1);
2491 std::swap(fac0, fac1);
2492 std::swap(tri_i[0], tri_i[2]);
2493 }
2494
2495 range[i].min = float(dot_b + offset0);
2496 range[i].max = float(dot_b + offset1);
2497 interp_v3_v3v3(range[i].loc[0], tri[tri_i[1]], tri[tri_i[0]], fac0);
2498 interp_v3_v3v3(range[i].loc[1], tri[tri_i[1]], tri[tri_i[2]], fac1);
2499 }
2500 else {
2501 range[i].min = range[i].max = float(dot_b);
2502 copy_v3_v3(range[i].loc[0], tri[tri_i[1]]);
2503 copy_v3_v3(range[i].loc[1], tri[tri_i[1]]);
2504 }
2505 }
2506
2507 if ((range[0].max > range[1].min) && (range[0].min < range[1].max)) {
2508 /* The triangles intersect because they overlap on the intersection line.
2509 * Now identify the two points of intersection that are in the middle to get the actual
2510 * intersection between the triangles. (B--C from A--B--C--D) */
2511 if (range[0].min >= range[1].min) {
2512 copy_v3_v3(r_i1, range[0].loc[0]);
2513 if (range[0].max <= range[1].max) {
2514 copy_v3_v3(r_i2, range[0].loc[1]);
2515 *r_tri_a_edge_isect_count = 2;
2516 }
2517 else {
2518 copy_v3_v3(r_i2, range[1].loc[1]);
2519 *r_tri_a_edge_isect_count = 1;
2520 }
2521 }
2522 else {
2523 if (range[0].max <= range[1].max) {
2524 copy_v3_v3(r_i1, range[0].loc[1]);
2525 copy_v3_v3(r_i2, range[1].loc[0]);
2526 *r_tri_a_edge_isect_count = 1;
2527 }
2528 else {
2529 copy_v3_v3(r_i1, range[1].loc[0]);
2530 copy_v3_v3(r_i2, range[1].loc[1]);
2531 }
2532 }
2533 return true;
2534 }
2535
2536 return false;
2537}
2538
2539bool isect_tri_tri_v3(const float t_a0[3],
2540 const float t_a1[3],
2541 const float t_a2[3],
2542 const float t_b0[3],
2543 const float t_b1[3],
2544 const float t_b2[3],
2545 float r_i1[3],
2546 float r_i2[3])
2547{
2548 float tri_a[3][3], tri_b[3][3];
2549 int dummy;
2550 copy_v3_v3(tri_a[0], t_a0);
2551 copy_v3_v3(tri_a[1], t_a1);
2552 copy_v3_v3(tri_a[2], t_a2);
2553 copy_v3_v3(tri_b[0], t_b0);
2554 copy_v3_v3(tri_b[1], t_b1);
2555 copy_v3_v3(tri_b[2], t_b2);
2556 return isect_tri_tri_v3_ex(tri_a, tri_b, r_i1, r_i2, &dummy);
2557}
2558
2560
2561/* -------------------------------------------------------------------- */
2569
2570static bool isect_tri_tri_v2_impl_vert(const float t_a0[2],
2571 const float t_a1[2],
2572 const float t_a2[2],
2573 const float t_b0[2],
2574 const float t_b1[2],
2575 const float t_b2[2])
2576{
2577 if (line_point_side_v2(t_b2, t_b0, t_a1) >= 0.0f) {
2578 if (line_point_side_v2(t_b2, t_b1, t_a1) <= 0.0f) {
2579 if (line_point_side_v2(t_a0, t_b0, t_a1) > 0.0f) {
2580 if (line_point_side_v2(t_a0, t_b1, t_a1) <= 0.0f) {
2581 return true;
2582 }
2583
2584 return false;
2585 }
2586
2587 if (line_point_side_v2(t_a0, t_b0, t_a2) >= 0.0f) {
2588 if (line_point_side_v2(t_a1, t_a2, t_b0) >= 0.0f) {
2589 return true;
2590 }
2591
2592 return false;
2593 }
2594
2595 return false;
2596 }
2597 if (line_point_side_v2(t_a0, t_b1, t_a1) <= 0.0f) {
2598 if (line_point_side_v2(t_b2, t_b1, t_a2) <= 0.0f) {
2599 if (line_point_side_v2(t_a1, t_a2, t_b1) >= 0.0f) {
2600 return true;
2601 }
2602
2603 return false;
2604 }
2605
2606 return false;
2607 }
2608
2609 return false;
2610 }
2611 if (line_point_side_v2(t_b2, t_b0, t_a2) >= 0.0f) {
2612 if (line_point_side_v2(t_a1, t_a2, t_b2) >= 0.0f) {
2613 if (line_point_side_v2(t_a0, t_b0, t_a2) >= 0.0f) {
2614 return true;
2615 }
2616
2617 return false;
2618 }
2619 if (line_point_side_v2(t_a1, t_a2, t_b1) >= 0.0f) {
2620 if (line_point_side_v2(t_b2, t_a2, t_b1) >= 0.0f) {
2621 return true;
2622 }
2623
2624 return false;
2625 }
2626
2627 return false;
2628 }
2629
2630 return false;
2631}
2632
2633static bool isect_tri_tri_v2_impl_edge(const float t_a0[2],
2634 const float t_a1[2],
2635 const float t_a2[2],
2636 const float t_b0[2],
2637 const float t_b1[2],
2638 const float t_b2[2])
2639{
2640 UNUSED_VARS(t_b1);
2641
2642 if (line_point_side_v2(t_b2, t_b0, t_a1) >= 0.0f) {
2643 if (line_point_side_v2(t_a0, t_b0, t_a1) >= 0.0f) {
2644 if (line_point_side_v2(t_a0, t_a1, t_b2) >= 0.0f) {
2645 return true;
2646 }
2647
2648 return false;
2649 }
2650
2651 if (line_point_side_v2(t_a1, t_a2, t_b0) >= 0.0f) {
2652 if (line_point_side_v2(t_a2, t_a0, t_b0) >= 0.0f) {
2653 return true;
2654 }
2655
2656 return false;
2657 }
2658
2659 return false;
2660 }
2661
2662 if (line_point_side_v2(t_b2, t_b0, t_a2) >= 0.0f) {
2663 if (line_point_side_v2(t_a0, t_b0, t_a2) >= 0.0f) {
2664 if (line_point_side_v2(t_a0, t_a2, t_b2) >= 0.0f) {
2665 return true;
2666 }
2667
2668 if (line_point_side_v2(t_a1, t_a2, t_b2) >= 0.0f) {
2669 return true;
2670 }
2671
2672 return false;
2673 }
2674
2675 return false;
2676 }
2677
2678 return false;
2679}
2680
2681static int isect_tri_tri_impl_ccw_v2(const float t_a0[2],
2682 const float t_a1[2],
2683 const float t_a2[2],
2684 const float t_b0[2],
2685 const float t_b1[2],
2686 const float t_b2[2])
2687{
2688 if (line_point_side_v2(t_b0, t_b1, t_a0) >= 0.0f) {
2689 if (line_point_side_v2(t_b1, t_b2, t_a0) >= 0.0f) {
2690 if (line_point_side_v2(t_b2, t_b0, t_a0) >= 0.0f) {
2691 return 1;
2692 }
2693
2694 return isect_tri_tri_v2_impl_edge(t_a0, t_a1, t_a2, t_b0, t_b1, t_b2);
2695 }
2696
2697 if (line_point_side_v2(t_b2, t_b0, t_a0) >= 0.0f) {
2698 return isect_tri_tri_v2_impl_edge(t_a0, t_a1, t_a2, t_b2, t_b0, t_b1);
2699 }
2700
2701 return isect_tri_tri_v2_impl_vert(t_a0, t_a1, t_a2, t_b0, t_b1, t_b2);
2702 }
2703
2704 if (line_point_side_v2(t_b1, t_b2, t_a0) >= 0.0f) {
2705 if (line_point_side_v2(t_b2, t_b0, t_a0) >= 0.0f) {
2706 return isect_tri_tri_v2_impl_edge(t_a0, t_a1, t_a2, t_b1, t_b2, t_b0);
2707 }
2708
2709 return isect_tri_tri_v2_impl_vert(t_a0, t_a1, t_a2, t_b1, t_b2, t_b0);
2710 }
2711
2712 return isect_tri_tri_v2_impl_vert(t_a0, t_a1, t_a2, t_b2, t_b0, t_b1);
2713}
2714
2715bool isect_tri_tri_v2(const float t_a0[2],
2716 const float t_a1[2],
2717 const float t_a2[2],
2718 const float t_b0[2],
2719 const float t_b1[2],
2720 const float t_b2[2])
2721{
2722 if (line_point_side_v2(t_a0, t_a1, t_a2) < 0.0f) {
2723 if (line_point_side_v2(t_b0, t_b1, t_b2) < 0.0f) {
2724 return isect_tri_tri_impl_ccw_v2(t_a0, t_a2, t_a1, t_b0, t_b2, t_b1);
2725 }
2726
2727 return isect_tri_tri_impl_ccw_v2(t_a0, t_a2, t_a1, t_b0, t_b1, t_b2);
2728 }
2729
2730 if (line_point_side_v2(t_b0, t_b1, t_b2) < 0.0f) {
2731 return isect_tri_tri_impl_ccw_v2(t_a0, t_a1, t_a2, t_b0, t_b2, t_b1);
2732 }
2733
2734 return isect_tri_tri_impl_ccw_v2(t_a0, t_a1, t_a2, t_b0, t_b1, t_b2);
2735}
2736
2738
2739/* -------------------------------------------------------------------- */
2742
2743/* Adapted from the paper by Kasper Fauerby */
2744
2745/* "Improved Collision detection and Response" */
2746static bool getLowestRoot(
2747 const float a, const float b, const float c, const float maxR, float *root)
2748{
2749 /* Check if a solution exists */
2750 const float determinant = b * b - 4.0f * a * c;
2751
2752 /* If determinant is negative it means no solutions. */
2753 if (determinant >= 0.0f) {
2754 /* calculate the two roots: (if determinant == 0 then
2755 * x1==x2 but lets disregard that slight optimization) */
2756 const float sqrtD = sqrtf(determinant);
2757 float r1 = (-b - sqrtD) / (2.0f * a);
2758 float r2 = (-b + sqrtD) / (2.0f * a);
2759
2760 /* Sort so x1 <= x2 */
2761 if (r1 > r2) {
2762 std::swap(r1, r2);
2763 }
2764
2765 /* Get lowest root: */
2766 if (r1 > 0.0f && r1 < maxR) {
2767 *root = r1;
2768 return true;
2769 }
2770
2771 /* It is possible that we want x2 - this can happen */
2772 /* if x1 < 0 */
2773 if (r2 > 0.0f && r2 < maxR) {
2774 *root = r2;
2775 return true;
2776 }
2777 }
2778 /* No (valid) solutions */
2779 return false;
2780}
2781
2782int isect_aabb_planes_v3(const float (*planes)[4],
2783 const int totplane,
2784 const float bbmin[3],
2785 const float bbmax[3])
2786{
2788
2789 float bb_near[3], bb_far[3];
2790 for (int i = 0; i < totplane; i++) {
2791 aabb_get_near_far_from_plane(planes[i], bbmin, bbmax, bb_near, bb_far);
2792
2793 if (plane_point_side_v3(planes[i], bb_far) < 0.0f) {
2795 }
2796 if ((ret != ISECT_AABB_PLANE_CROSS_ANY) && (plane_point_side_v3(planes[i], bb_near) < 0.0f)) {
2798 }
2799 }
2800
2801 return ret;
2802}
2803
2804bool isect_sweeping_sphere_tri_v3(const float p1[3],
2805 const float p2[3],
2806 const float radius,
2807 const float v0[3],
2808 const float v1[3],
2809 const float v2[3],
2810 float *r_lambda,
2811 float ipoint[3])
2812{
2813 float e1[3], e2[3], e3[3], point[3], vel[3], /*dist[3],*/ nor[3], temp[3], bv[3];
2814 float a, b, c, d, e, x, y, z, radius2 = radius * radius;
2815 float elen2, edotv, edotbv, nordotv;
2816 float newLambda;
2817 bool found_by_sweep = false;
2818
2819 sub_v3_v3v3(e1, v1, v0);
2820 sub_v3_v3v3(e2, v2, v0);
2821 sub_v3_v3v3(vel, p2, p1);
2822
2823 /*---test plane of tri---*/
2824 cross_v3_v3v3(nor, e1, e2);
2825 normalize_v3(nor);
2826
2827 /* flip normal */
2828 if (dot_v3v3(nor, vel) > 0.0f) {
2829 negate_v3(nor);
2830 }
2831
2832 a = dot_v3v3(p1, nor) - dot_v3v3(v0, nor);
2833 nordotv = dot_v3v3(nor, vel);
2834
2835 if (fabsf(nordotv) < 0.000001f) {
2836 if (fabsf(a) >= radius) {
2837 return false;
2838 }
2839 }
2840 else {
2841 float t0 = (-a + radius) / nordotv;
2842 float t1 = (-a - radius) / nordotv;
2843
2844 if (t0 > t1) {
2845 std::swap(t0, t1);
2846 }
2847
2848 if (t0 > 1.0f || t1 < 0.0f) {
2849 return false;
2850 }
2851
2852 /* clamp to [0, 1] */
2853 CLAMP(t0, 0.0f, 1.0f);
2854 // CLAMP(t1, 0.0f, 1.0f); /* UNUSED. */
2855
2856 /*---test inside of tri---*/
2857 /* plane intersection point */
2858
2859 point[0] = p1[0] + vel[0] * t0 - nor[0] * radius;
2860 point[1] = p1[1] + vel[1] * t0 - nor[1] * radius;
2861 point[2] = p1[2] + vel[2] * t0 - nor[2] * radius;
2862
2863 /* is the point in the tri? */
2864 a = dot_v3v3(e1, e1);
2865 b = dot_v3v3(e1, e2);
2866 c = dot_v3v3(e2, e2);
2867
2868 sub_v3_v3v3(temp, point, v0);
2869 d = dot_v3v3(temp, e1);
2870 e = dot_v3v3(temp, e2);
2871
2872 x = d * c - e * b;
2873 y = e * a - d * b;
2874 z = x + y - (a * c - b * b);
2875
2876 if (z <= 0.0f && (x >= 0.0f && y >= 0.0f)) {
2877 // ((uint32_t(z) & ~(uint32_t(x) | uint32_t(y))) & 0x80000000)
2878 *r_lambda = t0;
2879 copy_v3_v3(ipoint, point);
2880 return true;
2881 }
2882 }
2883
2884 *r_lambda = 1.0f;
2885
2886 /*---test points---*/
2887 a = dot_v3v3(vel, vel);
2888
2889 /*v0*/
2890 sub_v3_v3v3(temp, p1, v0);
2891 b = 2.0f * dot_v3v3(vel, temp);
2892 c = dot_v3v3(temp, temp) - radius2;
2893
2894 if (getLowestRoot(a, b, c, *r_lambda, r_lambda)) {
2895 copy_v3_v3(ipoint, v0);
2896 found_by_sweep = true;
2897 }
2898
2899 /*v1*/
2900 sub_v3_v3v3(temp, p1, v1);
2901 b = 2.0f * dot_v3v3(vel, temp);
2902 c = dot_v3v3(temp, temp) - radius2;
2903
2904 if (getLowestRoot(a, b, c, *r_lambda, r_lambda)) {
2905 copy_v3_v3(ipoint, v1);
2906 found_by_sweep = true;
2907 }
2908
2909 /*v2*/
2910 sub_v3_v3v3(temp, p1, v2);
2911 b = 2.0f * dot_v3v3(vel, temp);
2912 c = dot_v3v3(temp, temp) - radius2;
2913
2914 if (getLowestRoot(a, b, c, *r_lambda, r_lambda)) {
2915 copy_v3_v3(ipoint, v2);
2916 found_by_sweep = true;
2917 }
2918
2919 /*---test edges---*/
2920 sub_v3_v3v3(e3, v2, v1); /* wasn't yet calculated */
2921
2922 /* `e1` */
2923 sub_v3_v3v3(bv, v0, p1);
2924
2925 elen2 = dot_v3v3(e1, e1);
2926 edotv = dot_v3v3(e1, vel);
2927 edotbv = dot_v3v3(e1, bv);
2928
2929 a = elen2 * -dot_v3v3(vel, vel) + edotv * edotv;
2930 b = 2.0f * (elen2 * dot_v3v3(vel, bv) - edotv * edotbv);
2931 c = elen2 * (radius2 - dot_v3v3(bv, bv)) + edotbv * edotbv;
2932
2933 if (getLowestRoot(a, b, c, *r_lambda, &newLambda)) {
2934 e = (edotv * newLambda - edotbv) / elen2;
2935
2936 if (e >= 0.0f && e <= 1.0f) {
2937 *r_lambda = newLambda;
2938 copy_v3_v3(ipoint, e1);
2939 mul_v3_fl(ipoint, e);
2940 add_v3_v3(ipoint, v0);
2941 found_by_sweep = true;
2942 }
2943 }
2944
2945 /* `e2` */
2946 /* `bv` is same. */
2947 elen2 = dot_v3v3(e2, e2);
2948 edotv = dot_v3v3(e2, vel);
2949 edotbv = dot_v3v3(e2, bv);
2950
2951 a = elen2 * -dot_v3v3(vel, vel) + edotv * edotv;
2952 b = 2.0f * (elen2 * dot_v3v3(vel, bv) - edotv * edotbv);
2953 c = elen2 * (radius2 - dot_v3v3(bv, bv)) + edotbv * edotbv;
2954
2955 if (getLowestRoot(a, b, c, *r_lambda, &newLambda)) {
2956 e = (edotv * newLambda - edotbv) / elen2;
2957
2958 if (e >= 0.0f && e <= 1.0f) {
2959 *r_lambda = newLambda;
2960 copy_v3_v3(ipoint, e2);
2961 mul_v3_fl(ipoint, e);
2962 add_v3_v3(ipoint, v0);
2963 found_by_sweep = true;
2964 }
2965 }
2966
2967 /* `e3` */
2968 // sub_v3_v3v3(bv, v0, p1); /* UNUSED */
2969 // elen2 = dot_v3v3(e1, e1); /* UNUSED */
2970 // edotv = dot_v3v3(e1, vel); /* UNUSED */
2971 // edotbv = dot_v3v3(e1, bv); /* UNUSED */
2972
2973 sub_v3_v3v3(bv, v1, p1);
2974 elen2 = dot_v3v3(e3, e3);
2975 edotv = dot_v3v3(e3, vel);
2976 edotbv = dot_v3v3(e3, bv);
2977
2978 a = elen2 * -dot_v3v3(vel, vel) + edotv * edotv;
2979 b = 2.0f * (elen2 * dot_v3v3(vel, bv) - edotv * edotbv);
2980 c = elen2 * (radius2 - dot_v3v3(bv, bv)) + edotbv * edotbv;
2981
2982 if (getLowestRoot(a, b, c, *r_lambda, &newLambda)) {
2983 e = (edotv * newLambda - edotbv) / elen2;
2984
2985 if (e >= 0.0f && e <= 1.0f) {
2986 *r_lambda = newLambda;
2987 copy_v3_v3(ipoint, e3);
2988 mul_v3_fl(ipoint, e);
2989 add_v3_v3(ipoint, v1);
2990 found_by_sweep = true;
2991 }
2992 }
2993
2994 return found_by_sweep;
2995}
2996
2998 const float p1[3],
2999 const float p2[3],
3000 const float v0[3],
3001 const float v1[3],
3002 const float v2[3],
3003 float *r_lambda)
3004{
3005 const float epsilon = 0.000001f;
3006 float p[3], e1[3], e2[3];
3007 float u, v, f;
3008 int a0 = axis, a1 = (axis + 1) % 3, a2 = (axis + 2) % 3;
3009
3010 sub_v3_v3v3(e1, v1, v0);
3011 sub_v3_v3v3(e2, v2, v0);
3012 sub_v3_v3v3(p, v0, p1);
3013
3014 f = (e2[a1] * e1[a2] - e2[a2] * e1[a1]);
3015 if ((f > -epsilon) && (f < epsilon)) {
3016 return false;
3017 }
3018
3019 v = (p[a2] * e1[a1] - p[a1] * e1[a2]) / f;
3020 if ((v < 0.0f) || (v > 1.0f)) {
3021 return false;
3022 }
3023
3024 f = e1[a1];
3025 if ((f > -epsilon) && (f < epsilon)) {
3026 f = e1[a2];
3027 if ((f > -epsilon) && (f < epsilon)) {
3028 return false;
3029 }
3030 u = (-p[a2] - v * e2[a2]) / f;
3031 }
3032 else {
3033 u = (-p[a1] - v * e2[a1]) / f;
3034 }
3035
3036 if ((u < 0.0f) || ((u + v) > 1.0f)) {
3037 return false;
3038 }
3039
3040 *r_lambda = (p[a0] + u * e1[a0] + v * e2[a0]) / (p2[a0] - p1[a0]);
3041
3042 if ((*r_lambda < 0.0f) || (*r_lambda > 1.0f)) {
3043 return false;
3044 }
3045
3046 return true;
3047}
3048
3049int isect_line_line_epsilon_v3(const float v1[3],
3050 const float v2[3],
3051 const float v3[3],
3052 const float v4[3],
3053 float r_i1[3],
3054 float r_i2[3],
3055 const float epsilon)
3056{
3057 float a[3], b[3], c[3], ab[3], cb[3];
3058 float d, div;
3059
3060 sub_v3_v3v3(c, v3, v1);
3061 sub_v3_v3v3(a, v2, v1);
3062 sub_v3_v3v3(b, v4, v3);
3063
3064 cross_v3_v3v3(ab, a, b);
3065 d = dot_v3v3(c, ab);
3066 div = dot_v3v3(ab, ab);
3067
3068 /* important not to use an epsilon here, see: #45919 */
3069 /* test zero length line */
3070 if (div == 0.0f) [[unlikely]] {
3071 return 0;
3072 }
3073 /* test if the two lines are coplanar */
3074 if (fabsf(d) <= epsilon) [[unlikely]] {
3075 cross_v3_v3v3(cb, c, b);
3076
3077 mul_v3_fl(a, dot_v3v3(cb, ab) / div);
3078 add_v3_v3v3(r_i1, v1, a);
3079 copy_v3_v3(r_i2, r_i1);
3080
3081 return 1; /* one intersection only */
3082 }
3083 /* if not */
3084
3085 float n[3], t[3];
3086 float v3t[3], v4t[3];
3087 sub_v3_v3v3(t, v1, v3);
3088
3089 /* offset between both plane where the lines lies */
3090 cross_v3_v3v3(n, a, b);
3091 project_v3_v3v3(t, t, n);
3092
3093 /* for the first line, offset the second line until it is coplanar */
3094 add_v3_v3v3(v3t, v3, t);
3095 add_v3_v3v3(v4t, v4, t);
3096
3097 sub_v3_v3v3(c, v3t, v1);
3098 sub_v3_v3v3(a, v2, v1);
3099 sub_v3_v3v3(b, v4t, v3t);
3100
3101 cross_v3_v3v3(ab, a, b);
3102 cross_v3_v3v3(cb, c, b);
3103
3104 mul_v3_fl(a, dot_v3v3(cb, ab) / dot_v3v3(ab, ab));
3105 add_v3_v3v3(r_i1, v1, a);
3106
3107 /* for the second line, just subtract the offset from the first intersection point */
3108 sub_v3_v3v3(r_i2, r_i1, t);
3109
3110 return 2; /* two nearest points */
3111}
3112
3113int isect_line_line_v3(const float v1[3],
3114 const float v2[3],
3115 const float v3[3],
3116 const float v4[3],
3117 float r_i1[3],
3118 float r_i2[3])
3119{
3120 const float epsilon = 0.000001f;
3121 return isect_line_line_epsilon_v3(v1, v2, v3, v4, r_i1, r_i2, epsilon);
3122}
3123
3124bool isect_line_line_strict_v3(const float v1[3],
3125 const float v2[3],
3126 const float v3[3],
3127 const float v4[3],
3128 float vi[3],
3129 float *r_lambda)
3130{
3131 const float epsilon = 0.000001f;
3132 float a[3], b[3], c[3], ab[3], cb[3], ca[3];
3133 float d, div;
3134
3135 sub_v3_v3v3(c, v3, v1);
3136 sub_v3_v3v3(a, v2, v1);
3137 sub_v3_v3v3(b, v4, v3);
3138
3139 cross_v3_v3v3(ab, a, b);
3140 d = dot_v3v3(c, ab);
3141 div = dot_v3v3(ab, ab);
3142
3143 /* important not to use an epsilon here, see: #45919 */
3144 /* test zero length line */
3145 if (div == 0.0f) [[unlikely]] {
3146 return false;
3147 }
3148 /* test if the two lines are coplanar */
3149 if (fabsf(d) < epsilon) [[unlikely]] {
3150 return false;
3151 }
3152
3153 float f1, f2;
3154 cross_v3_v3v3(cb, c, b);
3155 cross_v3_v3v3(ca, c, a);
3156
3157 f1 = dot_v3v3(cb, ab) / div;
3158 f2 = dot_v3v3(ca, ab) / div;
3159
3160 if (f1 >= 0 && f1 <= 1 && f2 >= 0 && f2 <= 1) {
3161 mul_v3_fl(a, f1);
3162 add_v3_v3v3(vi, v1, a);
3163
3164 if (r_lambda) {
3165 *r_lambda = f1;
3166 }
3167
3168 return true; /* intersection found */
3169 }
3170
3171 return false;
3172}
3173
3174bool isect_ray_ray_epsilon_v3(const float ray_origin_a[3],
3175 const float ray_direction_a[3],
3176 const float ray_origin_b[3],
3177 const float ray_direction_b[3],
3178 const float epsilon,
3179 float *r_lambda_a,
3180 float *r_lambda_b)
3181{
3182 BLI_assert(r_lambda_a || r_lambda_b);
3183 float n[3];
3184 cross_v3_v3v3(n, ray_direction_b, ray_direction_a);
3185 const float nlen = len_squared_v3(n);
3186
3187 /* `nlen` is the square of the area formed by the two vectors. */
3188 if (nlen < epsilon) [[unlikely]] {
3189 /* The lines are parallel. */
3190 return false;
3191 }
3192
3193 float t[3], c[3], cray[3];
3194 sub_v3_v3v3(t, ray_origin_b, ray_origin_a);
3195 sub_v3_v3v3(c, n, t);
3196
3197 if (r_lambda_a != nullptr) {
3198 cross_v3_v3v3(cray, c, ray_direction_b);
3199 *r_lambda_a = dot_v3v3(cray, n) / nlen;
3200 }
3201
3202 if (r_lambda_b != nullptr) {
3203 cross_v3_v3v3(cray, c, ray_direction_a);
3204 *r_lambda_b = dot_v3v3(cray, n) / nlen;
3205 }
3206
3207 return true;
3208}
3209
3210bool isect_ray_ray_v3(const float ray_origin_a[3],
3211 const float ray_direction_a[3],
3212 const float ray_origin_b[3],
3213 const float ray_direction_b[3],
3214 float *r_lambda_a,
3215 float *r_lambda_b)
3216{
3217 return isect_ray_ray_epsilon_v3(ray_origin_a,
3218 ray_direction_a,
3219 ray_origin_b,
3220 ray_direction_b,
3221 FLT_MIN,
3222 r_lambda_a,
3223 r_lambda_b);
3224}
3225
3226bool isect_aabb_aabb_v3(const float min1[3],
3227 const float max1[3],
3228 const float min2[3],
3229 const float max2[3])
3230{
3231 return (min1[0] < max2[0] && min1[1] < max2[1] && min1[2] < max2[2] && min2[0] < max1[0] &&
3232 min2[1] < max1[1] && min2[2] < max1[2]);
3233}
3234
3236 const float ray_origin[3],
3237 const float ray_direction[3])
3238{
3239 copy_v3_v3(data->ray_origin, ray_origin);
3240
3241 data->ray_inv_dir[0] = 1.0f / ray_direction[0];
3242 data->ray_inv_dir[1] = 1.0f / ray_direction[1];
3243 data->ray_inv_dir[2] = 1.0f / ray_direction[2];
3244
3245 data->sign[0] = data->ray_inv_dir[0] < 0.0f;
3246 data->sign[1] = data->ray_inv_dir[1] < 0.0f;
3247 data->sign[2] = data->ray_inv_dir[2] < 0.0f;
3248}
3249
3251 const float bb_min[3],
3252 const float bb_max[3],
3253 float *r_tmin)
3254{
3255 /* Adapted from http://www.gamedev.net/community/forums/topic.asp?topic_id=459973 */
3256
3257 float bbox[2][3];
3258
3259 copy_v3_v3(bbox[0], bb_min);
3260 copy_v3_v3(bbox[1], bb_max);
3261
3262 float tmin = (bbox[data->sign[0]][0] - data->ray_origin[0]) * data->ray_inv_dir[0];
3263 float tmax = (bbox[1 - data->sign[0]][0] - data->ray_origin[0]) * data->ray_inv_dir[0];
3264
3265 const float tymin = (bbox[data->sign[1]][1] - data->ray_origin[1]) * data->ray_inv_dir[1];
3266 const float tymax = (bbox[1 - data->sign[1]][1] - data->ray_origin[1]) * data->ray_inv_dir[1];
3267
3268 if ((tmin > tymax) || (tymin > tmax)) {
3269 return false;
3270 }
3271
3272 tmin = std::max(tymin, tmin);
3273 tmax = std::min(tymax, tmax);
3274
3275 const float tzmin = (bbox[data->sign[2]][2] - data->ray_origin[2]) * data->ray_inv_dir[2];
3276 const float tzmax = (bbox[1 - data->sign[2]][2] - data->ray_origin[2]) * data->ray_inv_dir[2];
3277
3278 if ((tmin > tzmax) || (tzmin > tmax)) {
3279 return false;
3280 }
3281
3282 tmin = std::max(tzmin, tmin);
3283
3284 /* NOTE(jwilkins): tmax does not need to be updated since we don't use it
3285 * keeping this here for future reference. */
3286 // if (tzmax < tmax) tmax = tzmax;
3287
3288 if (r_tmin) {
3289 (*r_tmin) = tmin;
3290 }
3291
3292 return true;
3293}
3294
3295bool isect_ray_aabb_v3_simple(const float orig[3],
3296 const float dir[3],
3297 const float bb_min[3],
3298 const float bb_max[3],
3299 float *tmin,
3300 float *tmax)
3301{
3302 double t[6];
3303 float hit_dist[2];
3304 const double invdirx = (dir[0] > 1e-35f || dir[0] < -1e-35f) ? 1.0 / double(dir[0]) : DBL_MAX;
3305 const double invdiry = (dir[1] > 1e-35f || dir[1] < -1e-35f) ? 1.0 / double(dir[1]) : DBL_MAX;
3306 const double invdirz = (dir[2] > 1e-35f || dir[2] < -1e-35f) ? 1.0 / double(dir[2]) : DBL_MAX;
3307 t[0] = double(bb_min[0] - orig[0]) * invdirx;
3308 t[1] = double(bb_max[0] - orig[0]) * invdirx;
3309 t[2] = double(bb_min[1] - orig[1]) * invdiry;
3310 t[3] = double(bb_max[1] - orig[1]) * invdiry;
3311 t[4] = double(bb_min[2] - orig[2]) * invdirz;
3312 t[5] = double(bb_max[2] - orig[2]) * invdirz;
3313 hit_dist[0] = float(fmax(fmax(fmin(t[0], t[1]), fmin(t[2], t[3])), fmin(t[4], t[5])));
3314 hit_dist[1] = float(fmin(fmin(fmax(t[0], t[1]), fmax(t[2], t[3])), fmax(t[4], t[5])));
3315 if ((hit_dist[1] < 0.0f) || (hit_dist[0] > hit_dist[1])) {
3316 return false;
3317 }
3318
3319 if (tmin) {
3320 *tmin = hit_dist[0];
3321 }
3322 if (tmax) {
3323 *tmax = hit_dist[1];
3324 }
3325 return true;
3326}
3327
3328float closest_to_ray_v3(float r_close[3],
3329 const float p[3],
3330 const float ray_orig[3],
3331 const float ray_dir[3])
3332{
3333 float h[3], lambda;
3334
3335 if (is_zero_v3(ray_dir)) [[unlikely]] {
3336 lambda = 0.0f;
3337 copy_v3_v3(r_close, ray_orig);
3338 return lambda;
3339 }
3340
3341 sub_v3_v3v3(h, p, ray_orig);
3342 lambda = dot_v3v3(ray_dir, h) / dot_v3v3(ray_dir, ray_dir);
3343 madd_v3_v3v3fl(r_close, ray_orig, ray_dir, lambda);
3344 return lambda;
3345}
3346
3347float closest_to_line_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
3348{
3349 float u[3];
3350 sub_v3_v3v3(u, l2, l1);
3351 return closest_to_ray_v3(r_close, p, l1, u);
3352}
3353
3354float closest_to_line_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2])
3355{
3356 float h[2], u[2], lambda, denom;
3357 sub_v2_v2v2(u, l2, l1);
3358 sub_v2_v2v2(h, p, l1);
3359 denom = dot_v2v2(u, u);
3360 if (denom == 0.0f) {
3361 r_close[0] = l1[0];
3362 r_close[1] = l1[1];
3363 return 0.0f;
3364 }
3365 lambda = dot_v2v2(u, h) / denom;
3366 r_close[0] = l1[0] + u[0] * lambda;
3367 r_close[1] = l1[1] + u[1] * lambda;
3368 return lambda;
3369}
3370
3371double closest_to_line_v2_db(double r_close[2],
3372 const double p[2],
3373 const double l1[2],
3374 const double l2[2])
3375{
3376 double h[2], u[2], lambda, denom;
3377 sub_v2_v2v2_db(u, l2, l1);
3378 sub_v2_v2v2_db(h, p, l1);
3379 denom = dot_v2v2_db(u, u);
3380 if (denom == 0.0) {
3381 r_close[0] = l1[0];
3382 r_close[1] = l1[1];
3383 return 0.0;
3384 }
3385 lambda = dot_v2v2_db(u, h) / denom;
3386 r_close[0] = l1[0] + u[0] * lambda;
3387 r_close[1] = l1[1] + u[1] * lambda;
3388 return lambda;
3389}
3390
3391float ray_point_factor_v3_ex(const float p[3],
3392 const float ray_origin[3],
3393 const float ray_direction[3],
3394 const float epsilon,
3395 const float fallback)
3396{
3397 float p_relative[3];
3398 sub_v3_v3v3(p_relative, p, ray_origin);
3399 const float dot = len_squared_v3(ray_direction);
3400 return (dot > epsilon) ? (dot_v3v3(ray_direction, p_relative) / dot) : fallback;
3401}
3402
3403float ray_point_factor_v3(const float p[3],
3404 const float ray_origin[3],
3405 const float ray_direction[3])
3406{
3407 return ray_point_factor_v3_ex(p, ray_origin, ray_direction, 0.0f, 0.0f);
3408}
3409
3410float line_point_factor_v3_ex(const float p[3],
3411 const float l1[3],
3412 const float l2[3],
3413 const float epsilon,
3414 const float fallback)
3415{
3416 float h[3], u[3];
3417 float dot;
3418 sub_v3_v3v3(u, l2, l1);
3419 sub_v3_v3v3(h, p, l1);
3420
3421 /* better check for zero */
3422 dot = len_squared_v3(u);
3423 return (dot > epsilon) ? (dot_v3v3(u, h) / dot) : fallback;
3424}
3425float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
3426{
3427 return line_point_factor_v3_ex(p, l1, l2, 0.0f, 0.0f);
3428}
3429
3430float line_point_factor_v2_ex(const float p[2],
3431 const float l1[2],
3432 const float l2[2],
3433 const float epsilon,
3434 const float fallback)
3435{
3436 float h[2], u[2];
3437 float dot;
3438 sub_v2_v2v2(u, l2, l1);
3439 sub_v2_v2v2(h, p, l1);
3440 /* better check for zero */
3441 dot = len_squared_v2(u);
3442 return (dot > epsilon) ? (dot_v2v2(u, h) / dot) : fallback;
3443}
3444
3445float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2])
3446{
3447 return line_point_factor_v2_ex(p, l1, l2, 0.0f, 0.0f);
3448}
3449
3450float line_plane_factor_v3(const float plane_co[3],
3451 const float plane_no[3],
3452 const float l1[3],
3453 const float l2[3])
3454{
3455 float u[3], h[3];
3456 float dot;
3457 sub_v3_v3v3(u, l2, l1);
3458 sub_v3_v3v3(h, l1, plane_co);
3459 dot = dot_v3v3(plane_no, u);
3460 return (dot != 0.0f) ? -dot_v3v3(plane_no, h) / dot : 0.0f;
3461}
3462
3463void limit_dist_v3(float v1[3], float v2[3], const float dist)
3464{
3465 const float dist_old = len_v3v3(v1, v2);
3466
3467 if (dist_old > dist) {
3468 float v1_old[3];
3469 float v2_old[3];
3470 float fac = (dist / dist_old) * 0.5f;
3471
3472 copy_v3_v3(v1_old, v1);
3473 copy_v3_v3(v2_old, v2);
3474
3475 interp_v3_v3v3(v1, v1_old, v2_old, 0.5f - fac);
3476 interp_v3_v3v3(v2, v1_old, v2_old, 0.5f + fac);
3477 }
3478}
3479
3481 const int x1, const int y1, const int x2, const int y2, const int a, const int b)
3482{
3483 float v1[2], v2[2], v3[2], p[2];
3484
3485 v1[0] = float(x1);
3486 v1[1] = float(y1);
3487
3488 v2[0] = float(x1);
3489 v2[1] = float(y2);
3490
3491 v3[0] = float(x2);
3492 v3[1] = float(y1);
3493
3494 p[0] = float(a);
3495 p[1] = float(b);
3496
3497 return isect_point_tri_v2(p, v1, v2, v3);
3498}
3499
3500static bool point_in_slice(const float p[3],
3501 const float v1[3],
3502 const float l1[3],
3503 const float l2[3])
3504{
3505 /* What is a slice?
3506 * Some math:
3507 * a line including (l1, l2) and a point not on the line
3508 * define a subset of R3 delimited by planes parallel to the line and orthogonal
3509 * to the (point --> line) distance vector, one plane on the line one on the point,
3510 * the room inside usually is rather small compared to R3 though still infinite
3511 * useful for restricting (speeding up) searches
3512 * e.g. all points of triangular prism are within the intersection of 3 "slices"
3513 * Another trivial case is a cube, but see a "spat" which is a deformed cube
3514 * with paired parallel planes needs only 3 slices too. */
3515 float h, rp[3], cp[3], q[3];
3516
3517 closest_to_line_v3(cp, v1, l1, l2);
3518 sub_v3_v3v3(q, cp, v1);
3519 const float q_squared = dot_v3v3(q, q);
3520 if (math::is_zero(q_squared)) {
3521 return false;
3522 }
3523
3524 sub_v3_v3v3(rp, p, v1);
3525 h = dot_v3v3(q, rp) / q_squared;
3526 return (h >= 0.0f && h <= 1.0f);
3527}
3528
3529/* Adult sister defining the slice planes by the origin and the normal.
3530 * NOTE: |normal| may not be 1 but defining the thickness of the slice. */
3531static bool point_in_slice_as(const float p[3], const float origin[3], const float normal[3])
3532{
3533 float h, rp[3];
3534 sub_v3_v3v3(rp, p, origin);
3535 h = dot_v3v3(normal, rp) / dot_v3v3(normal, normal);
3536 if (h < 0.0f || h > 1.0f) {
3537 return false;
3538 }
3539 return true;
3540}
3541
3542bool point_in_slice_seg(float p[3], float l1[3], float l2[3])
3543{
3544 float normal[3];
3545
3546 sub_v3_v3v3(normal, l2, l1);
3547
3548 return point_in_slice_as(p, l1, normal);
3549}
3550
3551bool isect_point_tri_prism_v3(const float p[3],
3552 const float v1[3],
3553 const float v2[3],
3554 const float v3[3])
3555{
3556 if (!point_in_slice(p, v1, v2, v3)) {
3557 return false;
3558 }
3559 if (!point_in_slice(p, v2, v3, v1)) {
3560 return false;
3561 }
3562 if (!point_in_slice(p, v3, v1, v2)) {
3563 return false;
3564 }
3565 return true;
3566}
3567
3569 const float p[3], const float v1[3], const float v2[3], const float v3[3], float r_isect_co[3])
3570{
3571 if (isect_point_tri_prism_v3(p, v1, v2, v3)) {
3572 float plane[4];
3573 float no[3];
3574
3575 /* Could use normal_tri_v3, but doesn't have to be unit-length */
3576 cross_tri_v3(no, v1, v2, v3);
3577 BLI_assert(len_squared_v3(no) != 0.0f);
3578
3579 plane_from_point_normal_v3(plane, v1, no);
3580 closest_to_plane_v3(r_isect_co, plane, p);
3581
3582 return true;
3583 }
3584
3585 return false;
3586}
3587
3589 const float p1[3], const float p2[3], const float plane[4], float r_p1[3], float r_p2[3])
3590{
3591 float dp[3], div;
3592
3593 sub_v3_v3v3(dp, p2, p1);
3594 div = dot_v3v3(dp, plane);
3595
3596 if (div == 0.0f) {
3597 /* parallel */
3598 return true;
3599 }
3600
3601 float t = -plane_point_side_v3(plane, p1);
3602
3603 if (div > 0.0f) {
3604 /* behind plane, completely clipped */
3605 if (t >= div) {
3606 return false;
3607 }
3608 if (t > 0.0f) {
3609 const float p1_copy[3] = {UNPACK3(p1)};
3610 copy_v3_v3(r_p2, p2);
3611 madd_v3_v3v3fl(r_p1, p1_copy, dp, t / div);
3612 return true;
3613 }
3614 }
3615 else {
3616 /* behind plane, completely clipped */
3617 if (t >= 0.0f) {
3618 return false;
3619 }
3620 if (t > div) {
3621 const float p1_copy[3] = {UNPACK3(p1)};
3622 copy_v3_v3(r_p1, p1);
3623 madd_v3_v3v3fl(r_p2, p1_copy, dp, t / div);
3624 return true;
3625 }
3626 }
3627
3628 /* In case input/output values match (above also). */
3629 const float p1_copy[3] = {UNPACK3(p1)};
3630 copy_v3_v3(r_p2, p2);
3631 copy_v3_v3(r_p1, p1_copy);
3632 return true;
3633}
3634
3635bool clip_segment_v3_plane_n(const float p1[3],
3636 const float p2[3],
3637 const float plane_array[][4],
3638 const int plane_num,
3639 float r_p1[3],
3640 float r_p2[3])
3641{
3642 /* intersect from both directions */
3643 float p1_fac = 0.0f, p2_fac = 1.0f;
3644
3645 float dp[3];
3646 sub_v3_v3v3(dp, p2, p1);
3647
3648 for (int i = 0; i < plane_num; i++) {
3649 const float *plane = plane_array[i];
3650 const float div = dot_v3v3(dp, plane);
3651
3652 if (div != 0.0f) {
3653 float t = -plane_point_side_v3(plane, p1);
3654 if (div > 0.0f) {
3655 /* clip p1 lower bounds */
3656 if (t >= div) {
3657 return false;
3658 }
3659 if (t > 0.0f) {
3660 t /= div;
3661 if (t > p1_fac) {
3662 p1_fac = t;
3663 if (p1_fac > p2_fac) {
3664 return false;
3665 }
3666 }
3667 }
3668 }
3669 else if (div < 0.0f) {
3670 /* clip p2 upper bounds */
3671 if (t >= 0.0f) {
3672 return false;
3673 }
3674 if (t > div) {
3675 t /= div;
3676 if (t < p2_fac) {
3677 p2_fac = t;
3678 if (p1_fac > p2_fac) {
3679 return false;
3680 }
3681 }
3682 }
3683 }
3684 }
3685 }
3686
3687 /* In case input/output values match. */
3688 const float p1_copy[3] = {UNPACK3(p1)};
3689
3690 madd_v3_v3v3fl(r_p1, p1_copy, dp, p1_fac);
3691 madd_v3_v3v3fl(r_p2, p1_copy, dp, p2_fac);
3692
3693 return true;
3694}
3695
3697
3698/* -------------------------------------------------------------------- */
3701
3702void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
3703{
3704 BLI_ASSERT_UNIT_V3(normal);
3705
3706 copy_v3_v3(r_mat[2], normal);
3707 ortho_basis_v3v3_v3(r_mat[0], r_mat[1], r_mat[2]);
3708
3709 BLI_ASSERT_UNIT_V3(r_mat[0]);
3710 BLI_ASSERT_UNIT_V3(r_mat[1]);
3711
3712 transpose_m3(r_mat);
3713
3714 BLI_assert(!is_negative_m3(r_mat));
3715 BLI_assert((fabsf(dot_m3_v3_row_z(r_mat, normal) - 1.0f) < BLI_ASSERT_UNIT_EPSILON) ||
3716 is_zero_v3(normal));
3717}
3718
3719void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
3720{
3721 BLI_ASSERT_UNIT_V3(normal);
3722
3723 negate_v3_v3(r_mat[2], normal);
3724 ortho_basis_v3v3_v3(r_mat[0], r_mat[1], r_mat[2]);
3725
3726 BLI_ASSERT_UNIT_V3(r_mat[0]);
3727 BLI_ASSERT_UNIT_V3(r_mat[1]);
3728
3729 transpose_m3(r_mat);
3730
3731 BLI_assert(!is_negative_m3(r_mat));
3732 BLI_assert((dot_m3_v3_row_z(r_mat, normal) < BLI_ASSERT_UNIT_EPSILON) || is_zero_v3(normal));
3733}
3734
3736
3737/* -------------------------------------------------------------------- */
3740
3741static float tri_signed_area(
3742 const float v1[3], const float v2[3], const float v3[3], const int i, const int j)
3743{
3744 return 0.5f * ((v1[i] - v2[i]) * (v2[j] - v3[j]) + (v1[j] - v2[j]) * (v3[i] - v2[i]));
3745}
3746
3750static bool barycentric_weights(const float v1[3],
3751 const float v2[3],
3752 const float v3[3],
3753 const float co[3],
3754 const float n[3],
3755 float w[3])
3756{
3757 float wtot;
3758 int i, j;
3759
3760 axis_dominant_v3(&i, &j, n);
3761
3762 w[0] = tri_signed_area(v2, v3, co, i, j);
3763 w[1] = tri_signed_area(v3, v1, co, i, j);
3764 w[2] = tri_signed_area(v1, v2, co, i, j);
3765
3766 wtot = w[0] + w[1] + w[2];
3767
3768#ifndef NDEBUG /* Avoid floating point exception when debugging. */
3769 if (wtot != 0.0f)
3770#endif
3771 {
3772 mul_v3_fl(w, 1.0f / wtot);
3773 if (is_finite_v3(w)) {
3774 return true;
3775 }
3776 }
3777 /* Zero area triangle. */
3778 copy_v3_fl(w, 1.0f / 3.0f);
3779 return false;
3780}
3781
3783 float w[3], const float v1[3], const float v2[3], const float v3[3], const float co[3])
3784{
3785 float n[3];
3786
3787 normal_tri_v3(n, v1, v2, v3);
3788 barycentric_weights(v1, v2, v3, co, n, w);
3789}
3790
3792 const float v1[3],
3793 const float v2[3],
3794 const float v3[3],
3795 const float v4[3],
3796 const float co[3])
3797{
3798 float w2[3];
3799
3800 zero_v4(w);
3801
3802 /* first check for exact match */
3803 if (equals_v3v3(co, v1)) {
3804 w[0] = 1.0f;
3805 }
3806 else if (equals_v3v3(co, v2)) {
3807 w[1] = 1.0f;
3808 }
3809 else if (equals_v3v3(co, v3)) {
3810 w[2] = 1.0f;
3811 }
3812 else if (equals_v3v3(co, v4)) {
3813 w[3] = 1.0f;
3814 }
3815 else {
3816 /* otherwise compute barycentric interpolation weights */
3817 float n1[3], n2[3], n[3];
3818 bool ok;
3819
3820 sub_v3_v3v3(n1, v1, v3);
3821 sub_v3_v3v3(n2, v2, v4);
3822 cross_v3_v3v3(n, n1, n2);
3823
3824 ok = barycentric_weights(v1, v2, v4, co, n, w);
3825 std::swap(w[2], w[3]);
3826
3827 if (!ok || (w[0] < 0.0f)) {
3828 /* if w[1] is negative, co is on the other side of the v1-v3 edge,
3829 * so we interpolate using the other triangle */
3830 ok = barycentric_weights(v2, v3, v4, co, n, w2);
3831
3832 if (ok) {
3833 w[0] = 0.0f;
3834 w[1] = w2[0];
3835 w[2] = w2[1];
3836 w[3] = w2[2];
3837 }
3838 }
3839 }
3840}
3841
3843{
3844 if (IN_RANGE(w[0], 0.0f, 1.0f) && IN_RANGE(w[1], 0.0f, 1.0f) && IN_RANGE(w[2], 0.0f, 1.0f)) {
3845 return 1;
3846 }
3847 if (IN_RANGE_INCL(w[0], 0.0f, 1.0f) && IN_RANGE_INCL(w[1], 0.0f, 1.0f) &&
3848 IN_RANGE_INCL(w[2], 0.0f, 1.0f))
3849 {
3850 return 2;
3851 }
3852
3853 return 0;
3854}
3855
3857 const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
3858{
3859 const float x = co[0], y = co[1];
3860 const float x1 = v1[0], y1 = v1[1];
3861 const float x2 = v2[0], y2 = v2[1];
3862 const float x3 = v3[0], y3 = v3[1];
3863 const float det = (y2 - y3) * (x1 - x3) + (x3 - x2) * (y1 - y3);
3864
3865#ifndef NDEBUG /* Avoid floating point exception when debugging. */
3866 if (det != 0.0f)
3867#endif
3868 {
3869 w[0] = ((y2 - y3) * (x - x3) + (x3 - x2) * (y - y3)) / det;
3870 w[1] = ((y3 - y1) * (x - x3) + (x1 - x3) * (y - y3)) / det;
3871 w[2] = 1.0f - w[0] - w[1];
3872 if (is_finite_v3(w)) {
3873 return true;
3874 }
3875 }
3876
3877 return false;
3878}
3879
3881 const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
3882{
3883 float wtot;
3884
3885 w[0] = cross_tri_v2(v2, v3, co);
3886 w[1] = cross_tri_v2(v3, v1, co);
3887 w[2] = cross_tri_v2(v1, v2, co);
3888 wtot = w[0] + w[1] + w[2];
3889
3890#ifndef NDEBUG /* Avoid floating point exception when debugging. */
3891 if (wtot != 0.0f)
3892#endif
3893 {
3894 mul_v3_fl(w, 1.0f / wtot);
3895 if (is_finite_v3(w)) {
3896 return;
3897 }
3898 }
3899 /* Dummy values for zero area face. */
3900 copy_v3_fl(w, 1.0f / 3.0f);
3901}
3902
3904 const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
3905{
3906 float wtot;
3907
3908 w[0] = max_ff(cross_tri_v2(v2, v3, co), 0.0f);
3909 w[1] = max_ff(cross_tri_v2(v3, v1, co), 0.0f);
3910 w[2] = max_ff(cross_tri_v2(v1, v2, co), 0.0f);
3911 wtot = w[0] + w[1] + w[2];
3912
3913#ifndef NDEBUG /* Avoid floating point exception when debugging. */
3914 if (wtot != 0.0f)
3915#endif
3916 {
3917 mul_v3_fl(w, 1.0f / wtot);
3918 if (is_finite_v3(w)) {
3919 return;
3920 }
3921 }
3922 /* Dummy values for zero area face. */
3923 copy_v3_fl(w, 1.0f / 3.0f);
3924}
3925
3927 const float v1[4], const float v2[4], const float v3[4], const float co[2], float w[3])
3928{
3929 float wtot;
3930
3931 w[0] = cross_tri_v2(v2, v3, co) / v1[3];
3932 w[1] = cross_tri_v2(v3, v1, co) / v2[3];
3933 w[2] = cross_tri_v2(v1, v2, co) / v3[3];
3934 wtot = w[0] + w[1] + w[2];
3935
3936#ifndef NDEBUG /* Avoid floating point exception when debugging. */
3937 if (wtot != 0.0f)
3938#endif
3939 {
3940 mul_v3_fl(w, 1.0f / wtot);
3941 if (is_finite_v3(w)) {
3942 return;
3943 }
3944 }
3945 /* Dummy values for zero area face. */
3946 copy_v3_fl(w, 1.0f / 3.0f);
3947}
3948
3949void barycentric_weights_v2_quad(const float v1[2],
3950 const float v2[2],
3951 const float v3[2],
3952 const float v4[2],
3953 const float co[2],
3954 float w[4])
3955{
3956 const float dirs[4][2] = {
3957 {v1[0] - co[0], v1[1] - co[1]},
3958 {v2[0] - co[0], v2[1] - co[1]},
3959 {v3[0] - co[0], v3[1] - co[1]},
3960 {v4[0] - co[0], v4[1] - co[1]},
3961 };
3962
3963 const float lens[4] = {
3964 len_v2(dirs[0]),
3965 len_v2(dirs[1]),
3966 len_v2(dirs[2]),
3967 len_v2(dirs[3]),
3968 };
3969
3970 /* avoid divide by zero */
3971 if (lens[0] < FLT_EPSILON) [[unlikely]] {
3972 w[0] = 1.0f;
3973 w[1] = w[2] = w[3] = 0.0f;
3974 }
3975 else if (lens[1] < FLT_EPSILON) [[unlikely]] {
3976 w[1] = 1.0f;
3977 w[0] = w[2] = w[3] = 0.0f;
3978 }
3979 else if (lens[2] < FLT_EPSILON) [[unlikely]] {
3980 w[2] = 1.0f;
3981 w[0] = w[1] = w[3] = 0.0f;
3982 }
3983 else if (lens[3] < FLT_EPSILON) [[unlikely]] {
3984 w[3] = 1.0f;
3985 w[0] = w[1] = w[2] = 0.0f;
3986 }
3987 else {
3988
3989 const float areas[4] = {
3990 cross_v2v2(dirs[0], dirs[1]),
3991 cross_v2v2(dirs[1], dirs[2]),
3992 cross_v2v2(dirs[2], dirs[3]),
3993 cross_v2v2(dirs[3], dirs[0]),
3994 };
3995 const float dots[4] = {
3996 dot_v2v2(dirs[0], dirs[1]),
3997 dot_v2v2(dirs[1], dirs[2]),
3998 dot_v2v2(dirs[2], dirs[3]),
3999 dot_v2v2(dirs[3], dirs[0]),
4000 };
4001 const float lens_prod[4] = {
4002 lens[0] * lens[1],
4003 lens[1] * lens[2],
4004 lens[2] * lens[3],
4005 lens[3] * lens[0],
4006 };
4007
4008 /* Handle cases where point lies exactly on the edge. */
4009 for (int i = 0; i < 4; i++) {
4010 const float area = areas[i];
4011 /* Collinear with edge i-j and between the endpoints. */
4012 if (fabsf(area) < 1.0e-12f * lens_prod[i] && dots[i] <= 0.0f) {
4013 const int j = (i + 1) & 3;
4014 const float sum = lens[i] + lens[j];
4015 w[0] = w[1] = w[2] = w[3] = 0.0f;
4016 w[i] = lens[j] / sum;
4017 w[j] = lens[i] / sum;
4018 return;
4019 }
4020 }
4021
4022 /* NOTE(@ideasman42): fabsf() here is not needed for convex quads
4023 * (and not used in #interp_weights_poly_v2).
4024 * But in the case of concave/bow-tie quads for the mask rasterizer it
4025 * gives unreliable results without adding `absf()`. If this becomes an issue for more general
4026 * usage we could have this optional or use a different function. */
4027#define MEAN_VALUE_HALF_TAN_V2(i1) \
4028 (areas[i1] != 0.0f ? fabsf((lens_prod[i1] - dots[i1]) / areas[i1]) : 0.0f)
4029 const float t[4] = {
4034 };
4035#undef MEAN_VALUE_HALF_TAN_V2
4036
4037 w[0] = (t[3] + t[0]) / lens[0];
4038 w[1] = (t[0] + t[1]) / lens[1];
4039 w[2] = (t[1] + t[2]) / lens[2];
4040 w[3] = (t[2] + t[3]) / lens[3];
4041
4042 float wtot = w[0] + w[1] + w[2] + w[3];
4043
4044#ifndef NDEBUG /* Avoid floating point exception when debugging. */
4045 if (wtot != 0.0f)
4046#endif
4047 {
4048 mul_v4_fl(w, 1.0f / wtot);
4049 if (is_finite_v4(w)) {
4050 return;
4051 }
4052 }
4053 /* Dummy values for zero area face. */
4054 copy_v4_fl(w, 1.0f / 4.0f);
4055 }
4056}
4057
4058void transform_point_by_tri_v3(float pt_tar[3],
4059 float const pt_src[3],
4060 const float tri_tar_p1[3],
4061 const float tri_tar_p2[3],
4062 const float tri_tar_p3[3],
4063 const float tri_src_p1[3],
4064 const float tri_src_p2[3],
4065 const float tri_src_p3[3])
4066{
4067 /* this works by moving the source triangle so its normal is pointing on the Z
4068 * axis where its barycentric weights can be calculated in 2D and its Z offset can
4069 * be re-applied. The weights are applied directly to the targets 3D points and the
4070 * z-depth is used to scale the targets normal as an offset.
4071 * This saves transforming the target into its Z-Up orientation and back
4072 * (which could also work) */
4073 float no_tar[3], no_src[3];
4074 float mat_src[3][3];
4075 float pt_src_xy[3];
4076 float tri_xy_src[3][3];
4077 float w_src[3];
4078 float area_tar, area_src;
4079 float z_ofs_src;
4080
4081 normal_tri_v3(no_tar, tri_tar_p1, tri_tar_p2, tri_tar_p3);
4082 normal_tri_v3(no_src, tri_src_p1, tri_src_p2, tri_src_p3);
4083
4084 axis_dominant_v3_to_m3(mat_src, no_src);
4085
4086 /* make the source tri xy space */
4087 mul_v3_m3v3(pt_src_xy, mat_src, pt_src);
4088 mul_v3_m3v3(tri_xy_src[0], mat_src, tri_src_p1);
4089 mul_v3_m3v3(tri_xy_src[1], mat_src, tri_src_p2);
4090 mul_v3_m3v3(tri_xy_src[2], mat_src, tri_src_p3);
4091
4092 barycentric_weights_v2(tri_xy_src[0], tri_xy_src[1], tri_xy_src[2], pt_src_xy, w_src);
4093 interp_v3_v3v3v3(pt_tar, tri_tar_p1, tri_tar_p2, tri_tar_p3, w_src);
4094
4095 area_tar = sqrtf(area_tri_v3(tri_tar_p1, tri_tar_p2, tri_tar_p3));
4096 area_src = sqrtf(area_tri_v2(tri_xy_src[0], tri_xy_src[1], tri_xy_src[2]));
4097
4098 z_ofs_src = pt_src_xy[2] - tri_xy_src[0][2];
4099 madd_v3_v3v3fl(pt_tar, pt_tar, no_tar, (z_ofs_src / area_src) * area_tar);
4100}
4101
4102void transform_point_by_seg_v3(float p_dst[3],
4103 const float p_src[3],
4104 const float l_dst_p1[3],
4105 const float l_dst_p2[3],
4106 const float l_src_p1[3],
4107 const float l_src_p2[3])
4108{
4109 float t = line_point_factor_v3(p_src, l_src_p1, l_src_p2);
4110 interp_v3_v3v3(p_dst, l_dst_p1, l_dst_p2, t);
4111}
4112
4113int interp_sparse_array(float *array, const int list_size, const float skipval)
4114{
4115 int found_invalid = 0;
4116 int found_valid = 0;
4117 int i;
4118
4119 for (i = 0; i < list_size; i++) {
4120 if (array[i] == skipval) {
4121 found_invalid = 1;
4122 }
4123 else {
4124 found_valid = 1;
4125 }
4126 }
4127
4128 if (found_valid == 0) {
4129 return -1;
4130 }
4131 if (found_invalid == 0) {
4132 return 0;
4133 }
4134
4135 /* found invalid depths, interpolate */
4136 float valid_last = skipval;
4137 int valid_ofs = 0;
4138
4139 Array<float> array_up(list_size);
4140 Array<float> array_down(list_size);
4141
4142 Array<int> ofs_tot_up(list_size);
4143 Array<int> ofs_tot_down(list_size);
4144
4145 for (i = 0; i < list_size; i++) {
4146 if (array[i] == skipval) {
4147 array_up[i] = valid_last;
4148 ofs_tot_up[i] = ++valid_ofs;
4149 }
4150 else {
4151 valid_last = array[i];
4152 valid_ofs = 0;
4153 }
4154 }
4155
4156 valid_last = skipval;
4157 valid_ofs = 0;
4158
4159 for (i = list_size - 1; i >= 0; i--) {
4160 if (array[i] == skipval) {
4161 array_down[i] = valid_last;
4162 ofs_tot_down[i] = ++valid_ofs;
4163 }
4164 else {
4165 valid_last = array[i];
4166 valid_ofs = 0;
4167 }
4168 }
4169
4170 /* now blend */
4171 for (i = 0; i < list_size; i++) {
4172 if (array[i] == skipval) {
4173 if (array_up[i] != skipval && array_down[i] != skipval) {
4174 array[i] = ((array_up[i] * float(ofs_tot_down[i])) +
4175 (array_down[i] * float(ofs_tot_up[i]))) /
4176 float(ofs_tot_down[i] + ofs_tot_up[i]);
4177 }
4178 else if (array_up[i] != skipval) {
4179 array[i] = array_up[i];
4180 }
4181 else if (array_down[i] != skipval) {
4182 array[i] = array_down[i];
4183 }
4184 }
4185 }
4186
4187 return 1;
4188}
4189
4191
4192/* -------------------------------------------------------------------- */
4195
4196#define IS_POINT_IX (1 << 0)
4197#define IS_SEGMENT_IX (1 << 1)
4198
4199#define DIR_V3_SET(d_len, va, vb) \
4200 { \
4201 sub_v3_v3v3((d_len)->dir, va, vb); \
4202 (d_len)->len = len_v3((d_len)->dir); \
4203 } \
4204 (void)0
4205
4206#define DIR_V2_SET(d_len, va, vb) \
4207 { \
4208 sub_v2db_v2fl_v2fl((d_len)->dir, va, vb); \
4209 (d_len)->len = len_v2_db((d_len)->dir); \
4210 } \
4211 (void)0
4212
4214 float dir[3], len;
4215};
4216
4218 double dir[2], len;
4219};
4220
4221/* Mean value weights - smooth interpolation weights for polygons with
4222 * more than 3 vertices */
4223static float mean_value_half_tan_v3(const Float3_Len *d_curr, const Float3_Len *d_next)
4224{
4225 float cross[3];
4226 cross_v3_v3v3(cross, d_curr->dir, d_next->dir);
4227 const float area = len_v3(cross);
4228 /* Compare against zero since 'FLT_EPSILON' can be too large, see: #73348. */
4229 if (area != 0.0f) [[likely]] {
4230 const float dot = dot_v3v3(d_curr->dir, d_next->dir);
4231 const float len = d_curr->len * d_next->len;
4232 const float result = (len - dot) / area;
4233 if (isfinite(result)) {
4234 return result;
4235 }
4236 }
4237 return 0.0f;
4238}
4239
4249static double mean_value_half_tan_v2_db(const Double2_Len *d_curr, const Double2_Len *d_next)
4250{
4251 /* Different from the 3d version but still correct. */
4252 const double area = cross_v2v2_db(d_curr->dir, d_next->dir);
4253 /* Compare against zero since 'FLT_EPSILON' can be too large, see: #73348. */
4254 if (area != 0.0) [[likely]] {
4255 const double dot = dot_v2v2_db(d_curr->dir, d_next->dir);
4256 const double len = d_curr->len * d_next->len;
4257 const double result = (len - dot) / area;
4258 if (isfinite(result)) {
4259 return result;
4260 }
4261 }
4262 return 0.0;
4263}
4264
4265void interp_weights_poly_v3(float *w, float v[][3], const int n, const float co[3])
4266{
4267 /* Before starting to calculate the weight, we need to figure out the floating point precision we
4268 * can expect from the supplied data. */
4269 float max_value = 0;
4270
4271 for (int i = 0; i < n; i++) {
4272 max_value = max_ff(max_value, fabsf(v[i][0] - co[0]));
4273 max_value = max_ff(max_value, fabsf(v[i][1] - co[1]));
4274 max_value = max_ff(max_value, fabsf(v[i][2] - co[2]));
4275 }
4276
4277 /* These to values we derived by empirically testing different values that works for the test
4278 * files in D7772. */
4279 const float eps = 16.0f * FLT_EPSILON * max_value;
4280 const float eps_sq = eps * eps;
4281 const float *v_curr, *v_next;
4282 float ht_prev, ht; /* half tangents */
4283 float totweight = 0.0f;
4284 int i_curr, i_next;
4285 char ix_flag = 0;
4286 Float3_Len d_curr, d_next;
4287
4288 /* loop over 'i_next' */
4289 i_curr = n - 1;
4290 i_next = 0;
4291
4292 v_curr = v[i_curr];
4293 v_next = v[i_next];
4294
4295 DIR_V3_SET(&d_curr, v_curr - 3 /* v[n - 2] */, co);
4296 DIR_V3_SET(&d_next, v_curr /* v[n - 1] */, co);
4297 ht_prev = mean_value_half_tan_v3(&d_curr, &d_next);
4298
4299 while (i_next < n) {
4300 /* Mark Mayer et al algorithm that is used here does not operate well if vertex is close
4301 * to borders of face.
4302 * In that case, do simple linear interpolation between the two edge vertices */
4303
4304 /* 'd_next.len' is in fact 'd_curr.len', just avoid copy to begin with */
4305 if (d_next.len < eps) [[unlikely]] {
4306 ix_flag = IS_POINT_IX;
4307 break;
4308 }
4309 if (dist_squared_to_line_segment_v3(co, v_curr, v_next) < eps_sq) [[unlikely]] {
4310 ix_flag = IS_SEGMENT_IX;
4311 break;
4312 }
4313
4314 d_curr = d_next;
4315 DIR_V3_SET(&d_next, v_next, co);
4316 ht = mean_value_half_tan_v3(&d_curr, &d_next);
4317 w[i_curr] = (ht_prev + ht) / d_curr.len;
4318 totweight += w[i_curr];
4319
4320 /* step */
4321 i_curr = i_next++;
4322 v_curr = v_next;
4323 v_next = v[i_next];
4324
4325 ht_prev = ht;
4326 }
4327
4328 if (ix_flag) {
4329 memset(w, 0, sizeof(*w) * size_t(n));
4330
4331 if (ix_flag & IS_POINT_IX) {
4332 w[i_curr] = 1.0f;
4333 }
4334 else {
4335 float fac = line_point_factor_v3(co, v_curr, v_next);
4336 CLAMP(fac, 0.0f, 1.0f);
4337 w[i_curr] = 1.0f - fac;
4338 w[i_next] = fac;
4339 }
4340 }
4341 else {
4342 if (totweight != 0.0f) {
4343 for (i_curr = 0; i_curr < n; i_curr++) {
4344 w[i_curr] /= totweight;
4345 }
4346 }
4347 }
4348}
4349
4350void interp_weights_poly_v2(float *w, float v[][2], const int n, const float co[2])
4351{
4352 /* Before starting to calculate the weight, we need to figure out the floating point precision we
4353 * can expect from the supplied data. */
4354 float max_value = 0;
4355
4356 for (int i = 0; i < n; i++) {
4357 max_value = max_ff(max_value, fabsf(v[i][0] - co[0]));
4358 max_value = max_ff(max_value, fabsf(v[i][1] - co[1]));
4359 }
4360
4361 /* These to values we derived by empirically testing different values that works for the test
4362 * files in D7772. */
4363 const float eps = 16.0f * FLT_EPSILON * max_value;
4364 const float eps_sq = eps * eps;
4365
4366 const float *v_curr, *v_next;
4367 double ht_prev, ht; /* half tangents */
4368 float totweight = 0.0f;
4369 int i_curr, i_next;
4370 char ix_flag = 0;
4371 Double2_Len d_curr, d_next;
4372
4373 /* loop over 'i_next' */
4374 i_curr = n - 1;
4375 i_next = 0;
4376
4377 v_curr = v[i_curr];
4378 v_next = v[i_next];
4379
4380 DIR_V2_SET(&d_curr, v_curr - 2 /* v[n - 2] */, co);
4381 DIR_V2_SET(&d_next, v_curr /* v[n - 1] */, co);
4382 ht_prev = mean_value_half_tan_v2_db(&d_curr, &d_next);
4383
4384 while (i_next < n) {
4385 /* Mark Mayer et al algorithm that is used here does not operate well if vertex is close
4386 * to borders of face. In that case,
4387 * do simple linear interpolation between the two edge vertices */
4388
4389 /* 'd_next.len' is in fact 'd_curr.len', just avoid copy to begin with */
4390 if (d_next.len < eps) [[unlikely]] {
4391 ix_flag = IS_POINT_IX;
4392 break;
4393 }
4394 if (dist_squared_to_line_segment_v2(co, v_curr, v_next) < eps_sq) [[unlikely]] {
4395 ix_flag = IS_SEGMENT_IX;
4396 break;
4397 }
4398
4399 d_curr = d_next;
4400 DIR_V2_SET(&d_next, v_next, co);
4401 ht = mean_value_half_tan_v2_db(&d_curr, &d_next);
4402 w[i_curr] = (d_curr.len == 0.0) ? 0.0f : float((ht_prev + ht) / d_curr.len);
4403 totweight += w[i_curr];
4404
4405 /* step */
4406 i_curr = i_next++;
4407 v_curr = v_next;
4408 v_next = v[i_next];
4409
4410 ht_prev = ht;
4411 }
4412
4413 if (ix_flag) {
4414 memset(w, 0, sizeof(*w) * size_t(n));
4415
4416 if (ix_flag & IS_POINT_IX) {
4417 w[i_curr] = 1.0f;
4418 }
4419 else {
4420 float fac = line_point_factor_v2(co, v_curr, v_next);
4421 CLAMP(fac, 0.0f, 1.0f);
4422 w[i_curr] = 1.0f - fac;
4423 w[i_next] = fac;
4424 }
4425 }
4426 else {
4427 if (totweight != 0.0f) {
4428 for (i_curr = 0; i_curr < n; i_curr++) {
4429 w[i_curr] /= totweight;
4430 }
4431 }
4432 }
4433}
4434
4435#undef IS_POINT_IX
4436#undef IS_SEGMENT_IX
4437
4438#undef DIR_V3_SET
4439#undef DIR_V2_SET
4440
4442
4443/* -------------------------------------------------------------------- */
4446
4447void interp_cubic_v3(float x[3],
4448 float v[3],
4449 const float x1[3],
4450 const float v1[3],
4451 const float x2[3],
4452 const float v2[3],
4453 const float t)
4454{
4455 float a[3], b[3];
4456 const float t2 = t * t;
4457 const float t3 = t2 * t;
4458
4459 /* cubic interpolation */
4460 a[0] = v1[0] + v2[0] + 2 * (x1[0] - x2[0]);
4461 a[1] = v1[1] + v2[1] + 2 * (x1[1] - x2[1]);
4462 a[2] = v1[2] + v2[2] + 2 * (x1[2] - x2[2]);
4463
4464 b[0] = -2 * v1[0] - v2[0] - 3 * (x1[0] - x2[0]);
4465 b[1] = -2 * v1[1] - v2[1] - 3 * (x1[1] - x2[1]);
4466 b[2] = -2 * v1[2] - v2[2] - 3 * (x1[2] - x2[2]);
4467
4468 x[0] = a[0] * t3 + b[0] * t2 + v1[0] * t + x1[0];
4469 x[1] = a[1] * t3 + b[1] * t2 + v1[1] * t + x1[1];
4470 x[2] = a[2] * t3 + b[2] * t2 + v1[2] * t + x1[2];
4471
4472 v[0] = 3 * a[0] * t2 + 2 * b[0] * t + v1[0];
4473 v[1] = 3 * a[1] * t2 + 2 * b[1] * t + v1[1];
4474 v[2] = 3 * a[2] * t2 + 2 * b[2] * t + v1[2];
4475}
4476
4477/* unfortunately internal calculations have to be done at double precision
4478 * to achieve correct/stable results. */
4479
4480#define IS_ZERO(x) ((x > (-DBL_EPSILON) && x < DBL_EPSILON) ? 1 : 0)
4481
4483 float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2])
4484{
4485 /* find UV such that
4486 * t = u * t0 + v * t1 + (1 - u - v) * t2
4487 * u * (t0 - t2) + v * (t1 - t2) = t - t2 */
4488 const double a = st0[0] - st2[0], b = st1[0] - st2[0];
4489 const double c = st0[1] - st2[1], d = st1[1] - st2[1];
4490 const double det = a * d - c * b;
4491
4492 /* det should never be zero since the determinant is the signed ST area of the triangle. */
4493 if (IS_ZERO(det) == 0) {
4494 const double x[2] = {st[0] - st2[0], st[1] - st2[1]};
4495
4496 r_uv[0] = float((d * x[0] - b * x[1]) / det);
4497 r_uv[1] = float(((-c) * x[0] + a * x[1]) / det);
4498 }
4499 else {
4500 zero_v2(r_uv);
4501 }
4502}
4503
4505 float r_uv[2], const float st[3], const float st0[3], const float st1[3], const float st2[3])
4506{
4507 float v0[3], v1[3], v2[3];
4508 double d00, d01, d11, d20, d21, det;
4509
4510 sub_v3_v3v3(v0, st1, st0);
4511 sub_v3_v3v3(v1, st2, st0);
4512 sub_v3_v3v3(v2, st, st0);
4513
4514 d00 = dot_v3v3(v0, v0);
4515 d01 = dot_v3v3(v0, v1);
4516 d11 = dot_v3v3(v1, v1);
4517 d20 = dot_v3v3(v2, v0);
4518 d21 = dot_v3v3(v2, v1);
4519
4520 det = d00 * d11 - d01 * d01;
4521
4522 /* det should never be zero since the determinant is the signed ST area of the triangle. */
4523 if (IS_ZERO(det) == 0) {
4524 float w;
4525
4526 w = float((d00 * d21 - d01 * d20) / det);
4527 r_uv[1] = float((d11 * d20 - d01 * d21) / det);
4528 r_uv[0] = 1.0f - r_uv[1] - w;
4529 }
4530 else {
4531 zero_v2(r_uv);
4532 }
4533}
4534
4535void resolve_quad_uv_v2(float r_uv[2],
4536 const float st[2],
4537 const float st0[2],
4538 const float st1[2],
4539 const float st2[2],
4540 const float st3[2])
4541{
4542 resolve_quad_uv_v2_deriv(r_uv, nullptr, st, st0, st1, st2, st3);
4543}
4544
4545void resolve_quad_uv_v2_deriv(float r_uv[2],
4546 float r_deriv[2][2],
4547 const float st[2],
4548 const float st0[2],
4549 const float st1[2],
4550 const float st2[2],
4551 const float st3[2])
4552{
4553 const double signed_area = (st0[0] * st1[1] - st0[1] * st1[0]) +
4554 (st1[0] * st2[1] - st1[1] * st2[0]) +
4555 (st2[0] * st3[1] - st2[1] * st3[0]) +
4556 (st3[0] * st0[1] - st3[1] * st0[0]);
4557
4558 /* X is 2D cross product (determinant)
4559 * A = (p0 - p) X (p0 - p3) */
4560 const double a = (st0[0] - st[0]) * (st0[1] - st3[1]) - (st0[1] - st[1]) * (st0[0] - st3[0]);
4561
4562 /* B = ( (p0 - p) X (p1 - p2) + (p1 - p) X (p0 - p3) ) / 2 */
4563 const double b =
4564 0.5 * double(((st0[0] - st[0]) * (st1[1] - st2[1]) - (st0[1] - st[1]) * (st1[0] - st2[0])) +
4565 ((st1[0] - st[0]) * (st0[1] - st3[1]) - (st1[1] - st[1]) * (st0[0] - st3[0])));
4566
4567 /* C = (p1-p) X (p1-p2) */
4568 const double fC = (st1[0] - st[0]) * (st1[1] - st2[1]) - (st1[1] - st[1]) * (st1[0] - st2[0]);
4569 double denom = a - 2 * b + fC;
4570
4571 /* clear outputs */
4572 zero_v2(r_uv);
4573
4574 if (IS_ZERO(denom) != 0) {
4575 const double fDen = a - fC;
4576 if (IS_ZERO(fDen) == 0) {
4577 r_uv[0] = float(a / fDen);
4578 }
4579 }
4580 else {
4581 const double desc_sq = b * b - a * fC;
4582 const double desc = sqrt(desc_sq < 0.0 ? 0.0 : desc_sq);
4583 const double s = signed_area > 0 ? (-1.0) : 1.0;
4584
4585 r_uv[0] = float(((a - b) + s * desc) / denom);
4586 }
4587
4588 /* find UV such that
4589 * fST = (1-u)(1-v) * ST0 + u * (1-v) * ST1 + u * v * ST2 + (1-u) * v * ST3 */
4590 {
4591 const double denom_s = (1 - r_uv[0]) * (st0[0] - st3[0]) + r_uv[0] * (st1[0] - st2[0]);
4592 const double denom_t = (1 - r_uv[0]) * (st0[1] - st3[1]) + r_uv[0] * (st1[1] - st2[1]);
4593 int i = 0;
4594 denom = denom_s;
4595
4596 if (fabs(denom_s) < fabs(denom_t)) {
4597 i = 1;
4598 denom = denom_t;
4599 }
4600
4601 if (IS_ZERO(denom) == 0) {
4602 r_uv[1] = float(double((1.0f - r_uv[0]) * (st0[i] - st[i]) + r_uv[0] * (st1[i] - st[i])) /
4603 denom);
4604 }
4605 }
4606
4607 if (r_deriv) {
4608 float tmp1[2], tmp2[2], s[2], t[2];
4609
4610 /* clear outputs */
4611 zero_v2(r_deriv[0]);
4612 zero_v2(r_deriv[1]);
4613
4614 sub_v2_v2v2(tmp1, st1, st0);
4615 sub_v2_v2v2(tmp2, st2, st3);
4616 interp_v2_v2v2(s, tmp1, tmp2, r_uv[1]);
4617 sub_v2_v2v2(tmp1, st3, st0);
4618 sub_v2_v2v2(tmp2, st2, st1);
4619 interp_v2_v2v2(t, tmp1, tmp2, r_uv[0]);
4620
4621 denom = t[0] * s[1] - t[1] * s[0];
4622
4623 if (!IS_ZERO(denom)) {
4624 double inv_denom = 1.0 / denom;
4625 r_deriv[0][0] = float(double(-t[1]) * inv_denom);
4626 r_deriv[0][1] = float(double(t[0]) * inv_denom);
4627 r_deriv[1][0] = float(double(s[1]) * inv_denom);
4628 r_deriv[1][1] = float(double(-s[0]) * inv_denom);
4629 }
4630 }
4631}
4632
4633float resolve_quad_u_v2(const float st[2],
4634 const float st0[2],
4635 const float st1[2],
4636 const float st2[2],
4637 const float st3[2])
4638{
4639 const double signed_area = (st0[0] * st1[1] - st0[1] * st1[0]) +
4640 (st1[0] * st2[1] - st1[1] * st2[0]) +
4641 (st2[0] * st3[1] - st2[1] * st3[0]) +
4642 (st3[0] * st0[1] - st3[1] * st0[0]);
4643
4644 /* X is 2D cross product (determinant)
4645 * A = (p0 - p) X (p0 - p3) */
4646 const double a = (st0[0] - st[0]) * (st0[1] - st3[1]) - (st0[1] - st[1]) * (st0[0] - st3[0]);
4647
4648 /* B = ( (p0 - p) X (p1 - p2) + (p1 - p) X (p0 - p3) ) / 2 */
4649 const double b =
4650 0.5 * double(((st0[0] - st[0]) * (st1[1] - st2[1]) - (st0[1] - st[1]) * (st1[0] - st2[0])) +
4651 ((st1[0] - st[0]) * (st0[1] - st3[1]) - (st1[1] - st[1]) * (st0[0] - st3[0])));
4652
4653 /* C = (p1-p) X (p1-p2) */
4654 const double fC = (st1[0] - st[0]) * (st1[1] - st2[1]) - (st1[1] - st[1]) * (st1[0] - st2[0]);
4655 double denom = a - 2 * b + fC;
4656
4657 if (IS_ZERO(denom) != 0) {
4658 const double fDen = a - fC;
4659 if (IS_ZERO(fDen) == 0) {
4660 return float(a / fDen);
4661 }
4662
4663 return 0.0f;
4664 }
4665
4666 const double desc_sq = b * b - a * fC;
4667 const double desc = sqrt(desc_sq < 0.0 ? 0.0 : desc_sq);
4668 const double s = signed_area > 0 ? (-1.0) : 1.0;
4669
4670 return float(((a - b) + s * desc) / denom);
4671}
4672
4673#undef IS_ZERO
4674
4675void interp_bilinear_quad_v3(float data[4][3], float u, float v, float res[3])
4676{
4677 float vec[3];
4678
4679 copy_v3_v3(res, data[0]);
4680 mul_v3_fl(res, (1 - u) * (1 - v));
4681 copy_v3_v3(vec, data[1]);
4682 mul_v3_fl(vec, u * (1 - v));
4683 add_v3_v3(res, vec);
4684 copy_v3_v3(vec, data[2]);
4685 mul_v3_fl(vec, u * v);
4686 add_v3_v3(res, vec);
4687 copy_v3_v3(vec, data[3]);
4688 mul_v3_fl(vec, (1 - u) * v);
4689 add_v3_v3(res, vec);
4690}
4691
4692void interp_barycentric_tri_v3(float data[3][3], float u, float v, float res[3])
4693{
4694 float vec[3];
4695
4696 copy_v3_v3(res, data[0]);
4697 mul_v3_fl(res, u);
4698 copy_v3_v3(vec, data[1]);
4699 mul_v3_fl(vec, v);
4700 add_v3_v3(res, vec);
4701 copy_v3_v3(vec, data[2]);
4702 mul_v3_fl(vec, 1.0f - u - v);
4703 add_v3_v3(res, vec);
4704}
4705
4707
4708/* -------------------------------------------------------------------- */
4711
4712void orthographic_m4(float mat[4][4],
4713 const float left,
4714 const float right,
4715 const float bottom,
4716 const float top,
4717 const float nearClip,
4718 const float farClip)
4719{
4720 float Xdelta, Ydelta, Zdelta;
4721
4722 Xdelta = right - left;
4723 Ydelta = top - bottom;
4724 Zdelta = farClip - nearClip;
4725 if (Xdelta == 0.0f || Ydelta == 0.0f || Zdelta == 0.0f) {
4726 return;
4727 }
4728 unit_m4(mat);
4729 mat[0][0] = 2.0f / Xdelta;
4730 mat[3][0] = -(right + left) / Xdelta;
4731 mat[1][1] = 2.0f / Ydelta;
4732 mat[3][1] = -(top + bottom) / Ydelta;
4733 mat[2][2] = -2.0f / Zdelta; /* NOTE: negate Z. */
4734 mat[3][2] = -(farClip + nearClip) / Zdelta;
4735}
4736
4737void perspective_m4(float mat[4][4],
4738 const float left,
4739 const float right,
4740 const float bottom,
4741 const float top,
4742 const float nearClip,
4743 const float farClip)
4744{
4745 const float Xdelta = right - left;
4746 const float Ydelta = top - bottom;
4747 const float Zdelta = farClip - nearClip;
4748
4749 if (Xdelta == 0.0f || Ydelta == 0.0f || Zdelta == 0.0f) {
4750 return;
4751 }
4752 mat[0][0] = nearClip * 2.0f / Xdelta;
4753 mat[1][1] = nearClip * 2.0f / Ydelta;
4754 mat[2][0] = (right + left) / Xdelta; /* NOTE: negate Z. */
4755 mat[2][1] = (top + bottom) / Ydelta;
4756 mat[2][2] = -(farClip + nearClip) / Zdelta;
4757 mat[2][3] = -1.0f;
4758 mat[3][2] = (-2.0f * nearClip * farClip) / Zdelta;
4759 mat[0][1] = mat[0][2] = mat[0][3] = mat[1][0] = mat[1][2] = mat[1][3] = mat[3][0] = mat[3][1] =
4760 mat[3][3] = 0.0f;
4761}
4762
4763void perspective_m4_fov(float mat[4][4],
4764 const float angle_left,
4765 const float angle_right,
4766 const float angle_up,
4767 const float angle_down,
4768 const float nearClip,
4769 const float farClip)
4770{
4771 const float tan_angle_left = tanf(angle_left);
4772 const float tan_angle_right = tanf(angle_right);
4773 const float tan_angle_bottom = tanf(angle_up);
4774 const float tan_angle_top = tanf(angle_down);
4775
4777 mat, tan_angle_left, tan_angle_right, tan_angle_top, tan_angle_bottom, nearClip, farClip);
4778 mat[0][0] /= nearClip;
4779 mat[1][1] /= nearClip;
4780}
4781
4782void window_translate_m4(float winmat[4][4], float perspmat[4][4], const float x, const float y)
4783{
4784 if (winmat[2][3] == -1.0f) {
4785 /* in the case of a win-matrix, this means perspective always */
4786 float v1[3];
4787 float v2[3];
4788 float len1, len2;
4789
4790 v1[0] = perspmat[0][0];
4791 v1[1] = perspmat[1][0];
4792 v1[2] = perspmat[2][0];
4793
4794 v2[0] = perspmat[0][1];
4795 v2[1] = perspmat[1][1];
4796 v2[2] = perspmat[2][1];
4797
4798 len1 = (1.0f / len_v3(v1));
4799 len2 = (1.0f / len_v3(v2));
4800
4801 winmat[2][0] -= len1 * winmat[0][0] * x;
4802 winmat[2][1] -= len2 * winmat[1][1] * y;
4803 }
4804 else {
4805 winmat[3][0] += x;
4806 winmat[3][1] += y;
4807 }
4808}
4809
4810void planes_from_projmat(const float mat[4][4],
4811 float left[4],
4812 float right[4],
4813 float bottom[4],
4814 float top[4],
4815 float near[4],
4816 float far[4])
4817{
4818 /* References:
4819 *
4820 * https://fgiesen.wordpress.com/2012/08/31/frustum-planes-from-the-projection-matrix/
4821 * http://www8.cs.umu.se/kurser/5DV051/HT12/lab/plane_extraction.pdf
4822 */
4823
4824 int i;
4825
4826 if (left) {
4827 for (i = 4; i--;) {
4828 left[i] = mat[i][3] + mat[i][0];
4829 }
4830 }
4831
4832 if (right) {
4833 for (i = 4; i--;) {
4834 right[i] = mat[i][3] - mat[i][0];
4835 }
4836 }
4837
4838 if (bottom) {
4839 for (i = 4; i--;) {
4840 bottom[i] = mat[i][3] + mat[i][1];
4841 }
4842 }
4843
4844 if (top) {
4845 for (i = 4; i--;) {
4846 top[i] = mat[i][3] - mat[i][1];
4847 }
4848 }
4849
4850 if (near) {
4851 for (i = 4; i--;) {
4852 near[i] = mat[i][3] + mat[i][2];
4853 }
4854 }
4855
4856 if (far) {
4857 for (i = 4; i--;) {
4858 far[i] = mat[i][3] - mat[i][2];
4859 }
4860 }
4861}
4862
4863void projmat_dimensions(const float winmat[4][4],
4864 float *r_left,
4865 float *r_right,
4866 float *r_bottom,
4867 float *r_top,
4868 float *r_near,
4869 float *r_far)
4870{
4871 const bool is_persp = winmat[3][3] == 0.0f;
4872 if (is_persp) {
4873 const float near = winmat[3][2] / (winmat[2][2] - 1.0f);
4874 *r_left = near * ((winmat[2][0] - 1.0f) / winmat[0][0]);
4875 *r_right = near * ((winmat[2][0] + 1.0f) / winmat[0][0]);
4876 *r_bottom = near * ((winmat[2][1] - 1.0f) / winmat[1][1]);
4877 *r_top = near * ((winmat[2][1] + 1.0f) / winmat[1][1]);
4878 *r_near = near;
4879 if (winmat[2][2] == -1.0f) {
4880 /* Case of infinite projection matrix. Assume large clip end. */
4881 *r_far = near + 1e9f;
4882 }
4883 else {
4884 *r_far = winmat[3][2] / (winmat[2][2] + 1.0f);
4885 }
4886 }
4887 else {
4888 *r_left = (-winmat[3][0] - 1.0f) / winmat[0][0];
4889 *r_right = (-winmat[3][0] + 1.0f) / winmat[0][0];
4890 *r_bottom = (-winmat[3][1] - 1.0f) / winmat[1][1];
4891 *r_top = (-winmat[3][1] + 1.0f) / winmat[1][1];
4892 *r_near = (winmat[3][2] + 1.0f) / winmat[2][2];
4893 *r_far = (winmat[3][2] - 1.0f) / winmat[2][2];
4894 }
4895}
4896
4897void projmat_dimensions_db(const float winmat_fl[4][4],
4898 double *r_left,
4899 double *r_right,
4900 double *r_bottom,
4901 double *r_top,
4902 double *r_near,
4903 double *r_far)
4904{
4905 double winmat[4][4];
4906 copy_m4d_m4(winmat, winmat_fl);
4907
4908 const bool is_persp = winmat[3][3] == 0.0f;
4909 if (is_persp) {
4910 const double near = winmat[3][2] / (winmat[2][2] - 1.0);
4911 *r_left = near * ((winmat[2][0] - 1.0) / winmat[0][0]);
4912 *r_right = near * ((winmat[2][0] + 1.0) / winmat[0][0]);
4913 *r_bottom = near * ((winmat[2][1] - 1.0) / winmat[1][1]);
4914 *r_top = near * ((winmat[2][1] + 1.0) / winmat[1][1]);
4915 *r_near = near;
4916 *r_far = winmat[3][2] / (winmat[2][2] + 1.0);
4917 }
4918 else {
4919 *r_left = (-winmat[3][0] - 1.0) / winmat[0][0];
4920 *r_right = (-winmat[3][0] + 1.0) / winmat[0][0];
4921 *r_bottom = (-winmat[3][1] - 1.0) / winmat[1][1];
4922 *r_top = (-winmat[3][1] + 1.0) / winmat[1][1];
4923 *r_near = (winmat[3][2] + 1.0) / winmat[2][2];
4924 *r_far = (winmat[3][2] - 1.0) / winmat[2][2];
4925 }
4926}
4927
4928void projmat_from_subregion(const float projmat[4][4],
4929 const int win_size[2],
4930 const int x_min,
4931 const int x_max,
4932 const int y_min,
4933 const int y_max,
4934 float r_projmat[4][4])
4935{
4936 float rect_width = float(x_max - x_min);
4937 float rect_height = float(y_max - y_min);
4938
4939 float x_sca = float(win_size[0]) / rect_width;
4940 float y_sca = float(win_size[1]) / rect_height;
4941
4942 float x_fac = float((x_min + x_max) - win_size[0]) / rect_width;
4943 float y_fac = float((y_min + y_max) - win_size[1]) / rect_height;
4944
4945 copy_m4_m4(r_projmat, projmat);
4946 r_projmat[0][0] *= x_sca;
4947 r_projmat[1][1] *= y_sca;
4948
4949 if (projmat[3][3] == 0.0f) {
4950 r_projmat[2][0] = r_projmat[2][0] * x_sca + x_fac;
4951 r_projmat[2][1] = r_projmat[2][1] * y_sca + y_fac;
4952 }
4953 else {
4954 r_projmat[3][0] = r_projmat[3][0] * x_sca - x_fac;
4955 r_projmat[3][1] = r_projmat[3][1] * y_sca - y_fac;
4956 }
4957}
4958
4959static void i_multmatrix(const float icand[4][4], float mat[4][4])
4960{
4961 int row, col;
4962 float temp[4][4];
4963
4964 for (row = 0; row < 4; row++) {
4965 for (col = 0; col < 4; col++) {
4966 temp[row][col] = (icand[row][0] * mat[0][col] + icand[row][1] * mat[1][col] +
4967 icand[row][2] * mat[2][col] + icand[row][3] * mat[3][col]);
4968 }
4969 }
4970 copy_m4_m4(mat, temp);
4971}
4972
4973void polarview_m4(float mat[4][4], float dist, float azimuth, float incidence, float twist)
4974{
4975 unit_m4(mat);
4976
4977 translate_m4(mat, 0.0, 0.0, -dist);
4978 rotate_m4(mat, 'Z', -twist);
4979 rotate_m4(mat, 'X', -incidence);
4980 rotate_m4(mat, 'Z', -azimuth);
4981}
4982
4984 float mat[4][4], float vx, float vy, float vz, float px, float py, float pz, float twist)
4985{
4986 float sine, cosine, hyp, hyp1, dx, dy, dz;
4987 float mat1[4][4];
4988
4989 unit_m4(mat1);
4990
4991 axis_angle_to_mat4_single(mat, 'Z', -twist);
4992
4993 dx = px - vx;
4994 dy = py - vy;
4995 dz = pz - vz;
4996 hyp = dx * dx + dz * dz; /* hyp squared */
4997 hyp1 = sqrtf(dy * dy + hyp);
4998 hyp = sqrtf(hyp); /* the real hyp */
4999
5000 if (hyp1 != 0.0f) { /* rotate X */
5001 sine = -dy / hyp1;
5002 cosine = hyp / hyp1;
5003 }
5004 else {
5005 sine = 0.0f;
5006 cosine = 1.0f;
5007 }
5008 mat1[1][1] = cosine;
5009 mat1[1][2] = sine;
5010 mat1[2][1] = -sine;
5011 mat1[2][2] = cosine;
5012
5013 i_multmatrix(mat1, mat);
5014
5015 /* Be careful here to reinitialize those modified by the last. */
5016 mat1[1][1] = mat1[2][2] = 1.0f;
5017 mat1[1][2] = mat1[2][1] = 0.0f;
5018
5019 /* paragraph */
5020 if (hyp != 0.0f) { /* rotate Y */
5021 sine = dx / hyp;
5022 cosine = -dz / hyp;
5023 }
5024 else {
5025 sine = 0.0f;
5026 cosine = 1.0f;
5027 }
5028 mat1[0][0] = cosine;
5029 mat1[0][2] = -sine;
5030 mat1[2][0] = sine;
5031 mat1[2][2] = cosine;
5032
5033 i_multmatrix(mat1, mat);
5034 translate_m4(mat, -vx, -vy, -vz); /* translate viewpoint to origin */
5035}
5036
5037int box_clip_bounds_m4(float boundbox[2][3], const float bounds[4], float winmat[4][4])
5038{
5039 float mat[4][4], vec[4];
5040 int a, fl, flag = -1;
5041
5042 copy_m4_m4(mat, winmat);
5043
5044 for (a = 0; a < 8; a++) {
5045 vec[0] = (a & 1) ? boundbox[0][0] : boundbox[1][0];
5046 vec[1] = (a & 2) ? boundbox[0][1] : boundbox[1][1];
5047 vec[2] = (a & 4) ? boundbox[0][2] : boundbox[1][2];
5048 vec[3] = 1.0;
5049 mul_m4_v4(mat, vec);
5050
5051 fl = 0;
5052 if (bounds) {
5053 if (vec[0] > bounds[1] * vec[3]) {
5054 fl |= 1;
5055 }
5056 if (vec[0] < bounds[0] * vec[3]) {
5057 fl |= 2;
5058 }
5059 if (vec[1] > bounds[3] * vec[3]) {
5060 fl |= 4;
5061 }
5062 if (vec[1] < bounds[2] * vec[3]) {
5063 fl |= 8;
5064 }
5065 }
5066 else {
5067 if (vec[0] < -vec[3]) {
5068 fl |= 1;
5069 }
5070 if (vec[0] > vec[3]) {
5071 fl |= 2;
5072 }
5073 if (vec[1] < -vec[3]) {
5074 fl |= 4;
5075 }
5076 if (vec[1] > vec[3]) {
5077 fl |= 8;
5078 }
5079 }
5080 if (vec[2] < -vec[3]) {
5081 fl |= 16;
5082 }
5083 if (vec[2] > vec[3]) {
5084 fl |= 32;
5085 }
5086
5087 flag &= fl;
5088 if (flag == 0) {
5089 return 0;
5090 }
5091 }
5092
5093 return flag;
5094}
5095
5096void box_minmax_bounds_m4(float min[3], float max[3], float boundbox[2][3], float mat[4][4])
5097{
5098 float mn[3], mx[3], vec[3];
5099 int a;
5100
5101 copy_v3_v3(mn, min);
5102 copy_v3_v3(mx, max);
5103
5104 for (a = 0; a < 8; a++) {
5105 vec[0] = (a & 1) ? boundbox[0][0] : boundbox[1][0];
5106 vec[1] = (a & 2) ? boundbox[0][1] : boundbox[1][1];
5107 vec[2] = (a & 4) ? boundbox[0][2] : boundbox[1][2];
5108
5109 mul_m4_v3(mat, vec);
5110 minmax_v3v3_v3(mn, mx, vec);
5111 }
5112
5113 copy_v3_v3(min, mn);
5114 copy_v3_v3(max, mx);
5115}
5116
5118
5119/* -------------------------------------------------------------------- */
5122
5123static float snap_coordinate(float u)
5124{
5125 /* Adjust a coordinate value `u` to obtain a value inside the (closed) unit interval.
5126 * i.e. 0.0 <= snap_coordinate(u) <= 1.0.
5127 * Due to round-off errors, it is possible that the value of `u` may be close to the boundary of
5128 * the unit interval, but not exactly on it. In order to handle these cases, `snap_coordinate`
5129 * checks whether `u` is within `epsilon` of the boundary, and if so, it snaps the return value
5130 * to the boundary. */
5131 if (u < 0.0f) {
5132 u += 1.0f; /* Get back into the unit interval. */
5133 }
5134 BLI_assert(!(0.0f > u));
5135 BLI_assert(!(1.0f < u));
5136 const float epsilon = 0.25f / 65536.0f; /* i.e. Quarter of a texel on a 65536 x 65536 texture. */
5137 if (u < epsilon) {
5138 return 0.0f; /* `u` is close to 0, just return 0. */
5139 }
5140 if (1.0f - epsilon < u) {
5141 return 1.0f; /* `u` is close to 1, just return 1. */
5142 }
5143 return u;
5144}
5145
5146bool map_to_tube(float *r_u, float *r_v, const float x, const float y, const float z)
5147{
5148 bool regular = true;
5149 if (x * x + y * y < 1e-6f * 1e-6f) {
5150 regular = false; /* We're too close to the cylinder's axis. */
5151 *r_u = 0.5f;
5152 }
5153 else {
5154 /* The "Regular" case, just compute the coordinate. */
5155 *r_u = snap_coordinate(atan2f(x, -y) / float(2.0f * M_PI));
5156 }
5157 *r_v = (z + 1.0f) / 2.0f;
5158 return regular;
5159}
5160
5161bool map_to_sphere(float *r_u, float *r_v, const float x, const float y, const float z)
5162{
5163 bool regular = true;
5164 const float epsilon = 0.25f / 65536.0f; /* i.e. Quarter of a texel on a 65536 x 65536 texture. */
5165 const float len_xy = sqrtf(x * x + y * y);
5166 if (len_xy <= fabsf(z) * epsilon) {
5167 regular = false; /* We're on the line that runs through the north and south poles. */
5168 *r_u = 0.5f;
5169 }
5170 else {
5171 /* The "Regular" case, just compute the coordinate. */
5172 *r_u = snap_coordinate(atan2f(x, -y) / float(2.0f * M_PI));
5173 }
5174 *r_v = snap_coordinate(atan2f(len_xy, -z) / float(M_PI));
5175 return regular;
5176}
5177
5178void map_to_plane_v2_v3v3(float r_co[2], const float co[3], const float no[3])
5179{
5180 const float target[3] = {0.0f, 0.0f, 1.0f};
5181 float axis[3];
5182
5183 cross_v3_v3v3(axis, no, target);
5184 normalize_v3(axis);
5185
5186 map_to_plane_axis_angle_v2_v3v3fl(r_co, co, axis, angle_normalized_v3v3(no, target));
5187}
5188
5190 const float co[3],
5191 const float axis[3],
5192 const float angle)
5193{
5194 float tmp[3];
5195
5196 rotate_normalized_v3_v3v3fl(tmp, co, axis, angle);
5197
5198 copy_v2_v2(r_co, tmp);
5199}
5200
5202
5203/* -------------------------------------------------------------------- */
5206
5208 float n2[3],
5209 float n3[3],
5210 const float f_no[3],
5211 const float co1[3],
5212 const float co2[3],
5213 const float co3[3])
5214{
5215 float vdiffs[3][3];
5216 const int nverts = 3;
5217
5218 /* compute normalized edge vectors */
5219 sub_v3_v3v3(vdiffs[0], co2, co1);
5220 sub_v3_v3v3(vdiffs[1], co3, co2);
5221 sub_v3_v3v3(vdiffs[2], co1, co3);
5222
5223 normalize_v3(vdiffs[0]);
5224 normalize_v3(vdiffs[1]);
5225 normalize_v3(vdiffs[2]);
5226
5227 /* accumulate angle weighted face normal */
5228 {
5229 float *vn[] = {n1, n2, n3};
5230 const float *prev_edge = vdiffs[nverts - 1];
5231 int i;
5232
5233 for (i = 0; i < nverts; i++) {
5234 const float *cur_edge = vdiffs[i];
5235 const float fac = math::safe_acos_approx(-dot_v3v3(cur_edge, prev_edge));
5236
5237 /* accumulate */
5238 madd_v3_v3fl(vn[i], f_no, fac);
5239 prev_edge = cur_edge;
5240 }
5241 }
5242}
5243
5245 float n2[3],
5246 float n3[3],
5247 float n4[3],
5248 const float f_no[3],
5249 const float co1[3],
5250 const float co2[3],
5251 const float co3[3],
5252 const float co4[3])
5253{
5254 float vdiffs[4][3];
5255 const int nverts = (n4 != nullptr && co4 != nullptr) ? 4 : 3;
5256
5257 /* compute normalized edge vectors */
5258 sub_v3_v3v3(vdiffs[0], co2, co1);
5259 sub_v3_v3v3(vdiffs[1], co3, co2);
5260
5261 if (nverts == 3) {
5262 sub_v3_v3v3(vdiffs[2], co1, co3);
5263 }
5264 else {
5265 sub_v3_v3v3(vdiffs[2], co4, co3);
5266 sub_v3_v3v3(vdiffs[3], co1, co4);
5267 normalize_v3(vdiffs[3]);
5268 }
5269
5270 normalize_v3(vdiffs[0]);
5271 normalize_v3(vdiffs[1]);
5272 normalize_v3(vdiffs[2]);
5273
5274 /* accumulate angle weighted face normal */
5275 {
5276 float *vn[] = {n1, n2, n3, n4};
5277 const float *prev_edge = vdiffs[nverts - 1];
5278 int i;
5279
5280 for (i = 0; i < nverts; i++) {
5281 const float *cur_edge = vdiffs[i];
5282 const float fac = math::safe_acos_approx(-dot_v3v3(cur_edge, prev_edge));
5283
5284 /* accumulate */
5285 madd_v3_v3fl(vn[i], f_no, fac);
5286 prev_edge = cur_edge;
5287 }
5288 }
5289}
5290
5292 const float polyno[3],
5293 const float **vertcos,
5294 float vdiffs[][3],
5295 const int nverts)
5296{
5297 int i;
5298
5299 /* calculate normalized edge directions for each edge in the poly */
5300 for (i = 0; i < nverts; i++) {
5301 sub_v3_v3v3(vdiffs[i], vertcos[(i + 1) % nverts], vertcos[i]);
5302 normalize_v3(vdiffs[i]);
5303 }
5304
5305 /* accumulate angle weighted face normal */
5306 {
5307 const float *prev_edge = vdiffs[nverts - 1];
5308
5309 for (i = 0; i < nverts; i++) {
5310 const float *cur_edge = vdiffs[i];
5311
5312 /* calculate angle between the two poly edges incident on
5313 * this vertex */
5314 const float fac = math::safe_acos_approx(-dot_v3v3(cur_edge, prev_edge));
5315
5316 /* accumulate */
5317 madd_v3_v3fl(vertnos[i], polyno, fac);
5318 prev_edge = cur_edge;
5319 }
5320 }
5321}
5322
5324
5325/* -------------------------------------------------------------------- */
5328
5329void tangent_from_uv_v3(const float uv1[2],
5330 const float uv2[2],
5331 const float uv3[2],
5332 const float co1[3],
5333 const float co2[3],
5334 const float co3[3],
5335 const float n[3],
5336 float r_tang[3])
5337{
5338 const float s1 = uv2[0] - uv1[0];
5339 const float s2 = uv3[0] - uv1[0];
5340 const float t1 = uv2[1] - uv1[1];
5341 const float t2 = uv3[1] - uv1[1];
5342 float det = (s1 * t2 - s2 * t1);
5343
5344 /* otherwise 'r_tang' becomes nan */
5345 if (det != 0.0f) {
5346 float tangv[3], ct[3], e1[3], e2[3];
5347
5348 det = 1.0f / det;
5349
5350 /* normals in render are inversed... */
5351 sub_v3_v3v3(e1, co1, co2);
5352 sub_v3_v3v3(e2, co1, co3);
5353 r_tang[0] = (t2 * e1[0] - t1 * e2[0]) * det;
5354 r_tang[1] = (t2 * e1[1] - t1 * e2[1]) * det;
5355 r_tang[2] = (t2 * e1[2] - t1 * e2[2]) * det;
5356 tangv[0] = (s1 * e2[0] - s2 * e1[0]) * det;
5357 tangv[1] = (s1 * e2[1] - s2 * e1[1]) * det;
5358 tangv[2] = (s1 * e2[2] - s2 * e1[2]) * det;
5359 cross_v3_v3v3(ct, r_tang, tangv);
5360
5361 /* check flip */
5362 if (dot_v3v3(ct, n) < 0.0f) {
5363 negate_v3(r_tang);
5364 }
5365 }
5366 else {
5367 zero_v3(r_tang);
5368 }
5369}
5370
5372
5373/* -------------------------------------------------------------------- */
5376
5377/* vector clouds */
5378
5379void vcloud_estimate_transform_v3(const int list_size,
5380 const float (*pos)[3],
5381 const float *weight,
5382 const float (*rpos)[3],
5383 const float *rweight,
5384 float lloc[3],
5385 float rloc[3],
5386 float lrot[3][3],
5387 float lscale[3][3])
5388{
5389 float accu_com[3] = {0.0f, 0.0f, 0.0f}, accu_rcom[3] = {0.0f, 0.0f, 0.0f};
5390 float accu_weight = 0.0f, accu_rweight = 0.0f;
5391 const float eps = 1e-6f;
5392
5393 int a;
5394 /* first set up a nice default response */
5395 if (lloc) {
5396 zero_v3(lloc);
5397 }
5398 if (rloc) {
5399 zero_v3(rloc);
5400 }
5401 if (lrot) {
5402 unit_m3(lrot);
5403 }
5404 if (lscale) {
5405 unit_m3(lscale);
5406 }
5407 /* do com for both clouds */
5408 if (pos && rpos && (list_size > 0)) { /* paranoia check */
5409 /* do com for both clouds */
5410 for (a = 0; a < list_size; a++) {
5411 if (weight) {
5412 float v[3];
5413 copy_v3_v3(v, pos[a]);
5414 mul_v3_fl(v, weight[a]);
5415 add_v3_v3(accu_com, v);
5416 accu_weight += weight[a];
5417 }
5418 else {
5419 add_v3_v3(accu_com, pos[a]);
5420 }
5421
5422 if (rweight) {
5423 float v[3];
5424 copy_v3_v3(v, rpos[a]);
5425 mul_v3_fl(v, rweight[a]);
5426 add_v3_v3(accu_rcom, v);
5427 accu_rweight += rweight[a];
5428 }
5429 else {
5430 add_v3_v3(accu_rcom, rpos[a]);
5431 }
5432 }
5433 if (!weight || !rweight) {
5434 accu_weight = accu_rweight = float(list_size);
5435 }
5436
5437 mul_v3_fl(accu_com, 1.0f / accu_weight);
5438 mul_v3_fl(accu_rcom, 1.0f / accu_rweight);
5439 if (lloc) {
5440 copy_v3_v3(lloc, accu_com);
5441 }
5442 if (rloc) {
5443 copy_v3_v3(rloc, accu_rcom);
5444 }
5445 if (lrot || lscale) { /* caller does not want rot nor scale, strange but legal */
5446 /* so now do some reverse engineering and see if we can
5447 * split rotation from scale -> Polar-decompose. */
5448 /* build 'projection' matrix */
5449 float m[3][3], mr[3][3], q[3][3], qi[3][3];
5450 float va[3], vb[3], stunt[3];
5451 float odet, ndet;
5452 int i = 0, imax = 15;
5453 zero_m3(m);
5454 zero_m3(mr);
5455
5456 /* build 'projection' matrix */
5457 for (a = 0; a < list_size; a++) {
5458 sub_v3_v3v3(va, rpos[a], accu_rcom);
5459 // mul_v3_fl(va, bp->mass); /* Mass needs re-normalization here? */
5460 sub_v3_v3v3(vb, pos[a], accu_com);
5461 // mul_v3_fl(va, rp->mass);
5462 m[0][0] += va[0] * vb[0];
5463 m[0][1] += va[0] * vb[1];
5464 m[0][2] += va[0] * vb[2];
5465
5466 m[1][0] += va[1] * vb[0];
5467 m[1][1] += va[1] * vb[1];
5468 m[1][2] += va[1] * vb[2];
5469
5470 m[2][0] += va[2] * vb[0];
5471 m[2][1] += va[2] * vb[1];
5472 m[2][2] += va[2] * vb[2];
5473
5474 /* building the reference matrix on the fly
5475 * needed to scale properly later */
5476
5477 mr[0][0] += va[0] * va[0];
5478 mr[0][1] += va[0] * va[1];
5479 mr[0][2] += va[0] * va[2];
5480
5481 mr[1][0] += va[1] * va[0];
5482 mr[1][1] += va[1] * va[1];
5483 mr[1][2] += va[1] * va[2];
5484
5485 mr[2][0] += va[2] * va[0];
5486 mr[2][1] += va[2] * va[1];
5487 mr[2][2] += va[2] * va[2];
5488 }
5489 copy_m3_m3(q, m);
5490 stunt[0] = q[0][0];
5491 stunt[1] = q[1][1];
5492 stunt[2] = q[2][2];
5493 /* Re-normalizing for numeric stability. */
5494 mul_m3_fl(q, 1.0f / len_v3(stunt));
5495
5496 /* This is pretty much Polar-decompose 'inline' the algorithm based on Higham's thesis
5497 * without the far case ... but seems to work here pretty neat. */
5498 odet = 0.0f;
5499 ndet = determinant_m3_array(q);
5500 while ((odet - ndet) * (odet - ndet) > eps && i < imax) {
5501 invert_m3_m3(qi, q);
5502 transpose_m3(qi);
5503 add_m3_m3m3(q, q, qi);
5504 mul_m3_fl(q, 0.5f);
5505 odet = ndet;
5506 ndet = determinant_m3_array(q);
5507 i++;
5508 }
5509
5510 if (i) {
5511 float scale[3][3];
5512 float irot[3][3];
5513 if (lrot) {
5514 copy_m3_m3(lrot, q);
5515 }
5516 invert_m3_m3(irot, q);
5517 invert_m3_m3(qi, mr);
5518 mul_m3_m3m3(q, m, qi);
5519 mul_m3_m3m3(scale, irot, q);
5520 if (lscale) {
5521 copy_m3_m3(lscale, scale);
5522 }
5523 }
5524 }
5525 }
5526}
5527
5528bool is_edge_convex_v3(const float v1[3],
5529 const float v2[3],
5530 const float f1_no[3],
5531 const float f2_no[3])
5532{
5533 if (!equals_v3v3(f1_no, f2_no)) {
5534 float cross[3];
5535 float l_dir[3];
5536 cross_v3_v3v3(cross, f1_no, f2_no);
5537 /* we assume contiguous normals, otherwise the result isn't meaningful */
5538 sub_v3_v3v3(l_dir, v2, v1);
5539 return (dot_v3v3(l_dir, cross) > 0.0f);
5540 }
5541 return false;
5542}
5543
5544bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
5545{
5554
5555 /* non-unit length normal, used as a projection plane */
5556 float plane[3];
5557
5558 {
5559 float v13[3], v24[3];
5560
5561 sub_v3_v3v3(v13, v1, v3);
5562 sub_v3_v3v3(v24, v2, v4);
5563
5564 cross_v3_v3v3(plane, v13, v24);
5565
5566 /* Ignore planes that are small or (near) zero area,
5567 * scale the threshold down as the length of the cross product is also squared.
5568 * With this value quads with edges smaller than 1e-05 may be detected as too small. */
5569 const float eps_sq = square_f(1e-8f);
5570 if (len_squared_v3(plane) < eps_sq) {
5571 return false;
5572 }
5573 }
5574
5575 const float *quad_coords[4] = {v1, v2, v3, v4};
5576 float quad_proj[4][3];
5577
5578 for (int i = 0; i < 4; i++) {
5579 project_plane_v3_v3v3(quad_proj[i], quad_coords[i], plane);
5580 }
5581
5582 float quad_dirs[4][3];
5583 for (int i = 0, j = 3; i < 4; j = i++) {
5584 sub_v3_v3v3(quad_dirs[i], quad_proj[i], quad_proj[j]);
5585 }
5586
5587 float test_dir[3];
5588
5589#define CROSS_SIGN(dir_a, dir_b) \
5590 ((void)cross_v3_v3v3(test_dir, dir_a, dir_b), (dot_v3v3(plane, test_dir) > 0.0f))
5591
5592 return (CROSS_SIGN(quad_dirs[0], quad_dirs[1]) && CROSS_SIGN(quad_dirs[1], quad_dirs[2]) &&
5593 CROSS_SIGN(quad_dirs[2], quad_dirs[3]) && CROSS_SIGN(quad_dirs[3], quad_dirs[0]));
5594
5595#undef CROSS_SIGN
5596}
5597
5598bool is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
5599{
5600 /* Line-tests, the 2 diagonals have to intersect to be convex. */
5601 return (isect_seg_seg_v2(v1, v3, v2, v4) > 0);
5602}
5603
5604bool is_poly_convex_v2(const float verts[][2], uint nr)
5605{
5606 uint sign_flag = 0;
5607 uint a;
5608 const float *co_curr, *co_prev;
5609 float dir_curr[2], dir_prev[2];
5610
5611 co_prev = verts[nr - 1];
5612 co_curr = verts[0];
5613
5614 sub_v2_v2v2(dir_prev, verts[nr - 2], co_prev);
5615
5616 for (a = 0; a < nr; a++) {
5617 float cross;
5618
5619 sub_v2_v2v2(dir_curr, co_prev, co_curr);
5620
5621 cross = cross_v2v2(dir_prev, dir_curr);
5622
5623 if (cross < 0.0f) {
5624 sign_flag |= 1;
5625 }
5626 else if (cross > 0.0f) {
5627 sign_flag |= 2;
5628 }
5629
5630 if (sign_flag == (1 | 2)) {
5631 return false;
5632 }
5633
5634 copy_v2_v2(dir_prev, dir_curr);
5635
5636 co_prev = co_curr;
5637 co_curr += 2;
5638 }
5639
5640 return true;
5641}
5642
5643int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
5644{
5645 float d_12[3], d_23[3], d_34[3], d_41[3];
5646 float cross_a[3], cross_b[3];
5647 int ret = 0;
5648
5649 sub_v3_v3v3(d_12, v1, v2);
5650 sub_v3_v3v3(d_23, v2, v3);
5651 sub_v3_v3v3(d_34, v3, v4);
5652 sub_v3_v3v3(d_41, v4, v1);
5653
5654 cross_v3_v3v3(cross_a, d_12, d_23);
5655 cross_v3_v3v3(cross_b, d_34, d_41);
5656 ret |= ((dot_v3v3(cross_a, cross_b) < 0.0f) << 0);
5657
5658 cross_v3_v3v3(cross_a, d_23, d_34);
5659 cross_v3_v3v3(cross_b, d_41, d_12);
5660 ret |= ((dot_v3v3(cross_a, cross_b) < 0.0f) << 1);
5661
5662 return ret;
5663}
5664
5666 const float v2[3],
5667 const float v3[3],
5668 const float v4[3])
5669{
5670 /* NOTE: if the faces normal has been calculated it's possible to simplify the following checks,
5671 * however this means the solution may be different depending on the existence of normals
5672 * causing tessellation to be "unstable" depending on the existence of normals, see #106469. */
5673 float d_12[3], d_13[3], d_14[3];
5674 float cross_a[3], cross_b[3];
5675 sub_v3_v3v3(d_12, v2, v1);
5676 sub_v3_v3v3(d_13, v3, v1);
5677 sub_v3_v3v3(d_14, v4, v1);
5678 cross_v3_v3v3(cross_a, d_12, d_13);
5679 cross_v3_v3v3(cross_b, d_14, d_13);
5680 return dot_v3v3(cross_a, cross_b) > 0.0f;
5681}
5682
5683float cubic_tangent_factor_circle_v3(const float tan_l[3], const float tan_r[3])
5684{
5685 BLI_ASSERT_UNIT_V3(tan_l);
5686 BLI_ASSERT_UNIT_V3(tan_r);
5687
5688 /* -7f causes instability/glitches with Bendy Bones + Custom Refs. */
5689 const float eps = 1e-5f;
5690
5691 const float tan_dot = dot_v3v3(tan_l, tan_r);
5692 if (tan_dot > 1.0f - eps) {
5693 /* no angle difference (use fallback, length won't make any difference) */
5694 return (1.0f / 3.0f) * 0.75f;
5695 }
5696 if (tan_dot < -1.0f + eps) {
5697 /* Parallel tangents (half-circle). */
5698 return (1.0f / 2.0f);
5699 }
5700
5701 /* non-aligned tangents, calculate handle length */
5702 const float angle = acosf(tan_dot) / 2.0f;
5703
5704 /* could also use 'angle_sin = len_vnvn(tan_l, tan_r, dims) / 2.0' */
5705 const float angle_sin = sinf(angle);
5706 const float angle_cos = cosf(angle);
5707 return ((1.0f - angle_cos) / (angle_sin * 2.0f)) / angle_sin;
5708}
5709
5711 const float v0[3], const float v1[3], const float v2[3], const float dist1, const float dist2)
5712{
5713 /* Vectors along triangle edges. */
5714 float v10[3], v12[3];
5715 sub_v3_v3v3(v10, v0, v1);
5716 sub_v3_v3v3(v12, v2, v1);
5717
5718 if (dist1 != 0.0f && dist2 != 0.0f) {
5719 /* Local coordinate system in the triangle plane. */
5720 float u[3], v[3], n[3];
5721 const float d12 = normalize_v3_v3(u, v12);
5722
5723 if (d12 * d12 > 0.0f) {
5724 cross_v3_v3v3(n, v12, v10);
5725 normalize_v3(n);
5726 cross_v3_v3v3(v, n, u);
5727
5728 /* v0 in local coordinates */
5729 const float v0_[2] = {dot_v3v3(v10, u), fabsf(dot_v3v3(v10, v))};
5730
5731 /* Compute virtual source point in local coordinates, that we estimate the geodesic
5732 * distance is being computed from. See figure 9 in the paper for the derivation. */
5733 const float a = 0.5f * (1.0f + (dist1 * dist1 - dist2 * dist2) / (d12 * d12));
5734 const float hh = dist1 * dist1 - a * a * d12 * d12;
5735
5736 if (hh > 0.0f) {
5737 const float h = sqrtf(hh);
5738 const float S_[2] = {a * d12, -h};
5739
5740 /* Only valid if the line between the source point and v0 crosses
5741 * the edge between v1 and v2. */
5742 const float x_intercept = S_[0] + h * (v0_[0] - S_[0]) / (v0_[1] + h);
5743 if (x_intercept >= 0.0f && x_intercept <= d12) {
5744 const float dist0 = len_v2v2(S_, v0_);
5745
5746 /* Reject the distance when v0 is closer to the virtual source point than both
5747 * v1 and v2. This is a heuristic to detect when v1 and v2 did not originate from
5748 * the same source, and the virtual source point is bogus. */
5749 if (dist0 >= std::min(dist1, dist2)) {
5750 return dist0;
5751 }
5752 }
5753 }
5754 }
5755 }
5756
5757 /* Fall back to Dijkstra approximation in trivial case, or if no valid source
5758 * point found that connects to v0 across the triangle. */
5759 return min_ff(dist1 + len_v3(v10), dist2 + len_v3v3(v0, v2));
5760}
5761
5763
5764} // namespace blender
#define BLI_ASSERT_UNIT_EPSILON
#define BLI_ASSERT_UNIT_V3(v)
#define M_PI
#define ISECT_AABB_PLANE_IN_FRONT_ALL
#define ISECT_LINE_LINE_NONE
#define ISECT_AABB_PLANE_CROSS_ANY
#define ISECT_AABB_PLANE_BEHIND_ANY
#define ISECT_LINE_LINE_COLINEAR
#define ISECT_LINE_LINE_EXACT
#define ISECT_LINE_LINE_CROSS
#define CLAMP(a, b, c)
#define UNUSED_VARS(...)
#define IN_RANGE(a, b, c)
#define UNPACK3(a)
#define ELEM(...)
#define IN_RANGE_INCL(a, b, c)
btScalar max
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
Definition btQuadWord.h:117
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
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)
#define acosf(x)
#define copysignf(x, y)
#define FLT_MAX
#define FLT_MIN
#define FLT_EPSILON
b[1] b &&[1] b &&[1] b &&[1] b &&[1] b[3] b &&[1] b[3] float determinant(MatBase< C, R >) RET
float dot(VecOp< float, D >, VecOp< float, D >) RET
VecBase< float, 3 > cross(VecOp< float, 3 >, VecOp< float, 3 >) RET
float length(VecOp< float, D >) RET
float3x3 scale(float3x3 mat, float2 scale)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
Definition math_dual.h:241
#define IS_ZERO(x)
#define MEAN_VALUE_HALF_TAN_V2(i1)
#define IS_POINT_IX
#define DIR_V3_SET(d_len, va, vb)
#define CCW(A, B, C)
#define DIR_V2_SET(d_len, va, vb)
#define IS_SEGMENT_IX
#define CROSS_SIGN(dir_a, dir_b)
float safe_acos_approx(float x)
bool is_zero(const T &a)
BMesh Iterators.
float area_quad_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition math_geom.cc:89
bool isect_ray_plane_v3_factor(const float ray_origin[3], const float ray_direction[3], const float plane_co[3], const float plane_no[3], float *r_lambda)
void resolve_quad_uv_v2(float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2], const float st3[2])
MINLINE float min_ff(float a, float b)
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
float dist_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2])
Definition math_geom.cc:316
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
float area_squared_quad_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition math_geom.cc:95
void closest_to_plane_v3(float r_close[3], const float plane[4], const float pt[3])
Definition math_geom.cc:451
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
bool isect_plane_plane_plane_v3(const float plane_a[4], const float plane_b[4], const float plane_c[4], float r_isect_co[3]) ATTR_WARN_UNUSED_RESULT
bool isect_point_tri_v3(const float p[3], const float v1[3], const float v2[3], const float v3[3], float r_isect_co[3])
bool point_in_slice_seg(float p[3], float l1[3], float l2[3])
MINLINE void negate_v3_v3(float r[3], const float a[3])
bool isect_plane_plane_v3(const float plane_a[4], const float plane_b[4], float r_isect_co[3], float r_isect_no[3]) ATTR_WARN_UNUSED_RESULT
double closest_to_line_v2_db(double r_close[2], const double p[2], const double l1[2], const double l2[2])
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
MINLINE float dot_m3_v3_row_z(const float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT
static int isect_tri_tri_impl_ccw_v2(const float t_a0[2], const float t_a1[2], const float t_a2[2], const float t_b0[2], const float t_b1[2], const float t_b2[2])
int isect_line_line_epsilon_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float r_i1[3], float r_i2[3], float epsilon)
int isect_line_sphere_v3(const float l1[3], const float l2[3], const float sp[3], float r, float r_p1[3], float r_p2[3])
float closest_to_ray_v3(float r_close[3], const float p[3], const float ray_orig[3], const float ray_dir[3])
void interp_cubic_v3(float x[3], float v[3], const float x1[3], const float v1[3], const float x2[3], const float v2[3], float t)
MINLINE bool is_finite_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
void rotate_normalized_v3_v3v3fl(float out[3], const float p[3], const float axis[3], float angle)
MINLINE void sub_v2_v2v2_db(double r[2], const double a[2], const double b[2])
bool isect_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], float radius, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float ipoint[3])
float line_point_factor_v3_ex(const float p[3], const float l1[3], const float l2[3], float epsilon, float fallback)
bool map_to_tube(float *r_u, float *r_v, float x, float y, float z)
bool isect_ray_aabb_v3(const struct IsectRayAABB_Precalc *data, const float bb_min[3], const float bb_max[3], float *r_tmin)
bool isect_ray_seg_v2(const float ray_origin[2], const float ray_direction[2], const float v0[2], const float v1[2], float *r_lambda, float *r_u)
void isect_seg_seg_v3(const float a0[3], const float a1[3], const float b0[3], const float b1[3], float r_a[3], float r_b[3])
bool isect_tri_tri_v3(const float t_a0[3], const float t_a1[3], const float t_a2[3], const float t_b0[3], const float t_b1[3], const float t_b2[3], float r_i1[3], float r_i2[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
int interp_sparse_array(float *array, int list_size, float skipval)
void interp_weights_quad_v3(float w[4], const float v1[3], const float v2[3], const float v3[3], const float v4[3], const float co[3])
static bool barycentric_weights(const float v1[3], const float v2[3], const float v3[3], const float co[3], const float n[3], float w[3])
void minmax_v3v3_v3(float min[3], float max[3], const float vec[3])
static bool point_in_slice(const float p[3], const float v1[3], const float l1[3], const float l2[3])
void projmat_dimensions(const float winmat[4][4], float *r_left, float *r_right, float *r_bottom, float *r_top, float *r_near, float *r_far)
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
bool isect_ray_tri_watertight_v3(const float ray_origin[3], const struct IsectRayPrecalc *isect_precalc, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
void copy_m3_m3(float m1[3][3], const float m2[3][3])
int isect_aabb_planes_v3(const float(*planes)[4], int totplane, const float bbmin[3], const float bbmax[3])
void cross_poly_v3(float n[3], const float verts[][3], unsigned int nr)
Definition math_geom.cc:172
float dist_signed_squared_to_plane_v3(const float p[3], const float plane[4])
Definition math_geom.cc:479
bool isect_ray_plane_v3(const float ray_origin[3], const float ray_direction[3], const float plane[4], float *r_lambda, bool clip)
void projmat_from_subregion(const float projmat[4][4], const int win_size[2], int x_min, int x_max, int y_min, int y_max, float r_projmat[4][4])
int isect_point_tri_v2_int(int x1, int y1, int x2, int y2, int a, int b)
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])
bool isect_point_poly_v2_int(const int pt[2], const int verts[][2], unsigned int nr)
MINLINE float cross_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
bool isect_tri_tri_v3_ex(const float tri_a[3][3], const float tri_b[3][3], float r_i1[3], float r_i2[3], int *r_tri_a_edge_isect_count)
bool invert_m3_m3(float inverse[3][3], const float mat[3][3])
int isect_line_sphere_v2(const float l1[2], const float l2[2], const float sp[2], float r, float r_p1[2], float r_p2[2])
MINLINE void copy_v2_v2(float r[2], const float a[2])
float dist_signed_to_plane_v3(const float p[3], const float plane[4])
Definition math_geom.cc:511
void project_v3_v3v3_normalized(float out[3], const float p[3], const float v_proj[3])
void perspective_m4_fov(float mat[4][4], float angle_left, float angle_right, float angle_up, float angle_down, float nearClip, float farClip)
bool isect_ray_line_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], float *r_lambda)
float dist_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3])
Definition math_geom.cc:544
float cross_poly_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:153
MINLINE float mul_project_m4_v3_zfac(const float mat[4][4], const float co[3]) ATTR_WARN_UNUSED_RESULT
float normal_poly_v3(float n[3], const float verts[][3], unsigned int nr)
Definition math_geom.cc:83
void planes_from_projmat(const float mat[4][4], float left[4], float right[4], float bottom[4], float top[4], float near[4], float far[4])
int isect_seg_seg_v2_point_ex(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float endpoint_bias, float r_vi[2])
static double mean_value_half_tan_v2_db(const Double2_Len *d_curr, const Double2_Len *d_next)
float dist_squared_to_projected_aabb_simple(const float projmat[4][4], const float winsize[2], const float mval[2], const float bbmin[3], const float bbmax[3])
int isect_seg_seg_v2_int(const int v1[2], const int v2[2], const int v3[2], const int v4[2])
struct DistRayAABB_Precalc dist_squared_ray_to_aabb_v3_precalc(const float ray_origin[3], const float ray_direction[3])
Definition math_geom.cc:703
void barycentric_weights_v2_persp(const float v1[4], const float v2[4], const float v3[4], const float co[2], float w[3])
int isect_seg_seg_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float r_vi[2])
void transform_point_by_tri_v3(float pt_tar[3], float const pt_src[3], const float tri_tar_p1[3], const float tri_tar_p2[3], const float tri_tar_p3[3], const float tri_src_p1[3], const float tri_src_p2[3], const float tri_src_p3[3])
void window_translate_m4(float winmat[4][4], float perspmat[4][4], float x, float y)
bool isect_ray_tri_threshold_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], float threshold)
float closest_to_line_segment_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
Definition math_geom.cc:403
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
MINLINE void copy_v4_fl(float r[4], float f)
void resolve_quad_uv_v2_deriv(float r_uv[2], float r_deriv[2][2], const float st[2], const float st0[2], const float st1[2], const float st2[2], const float st3[2])
bool isect_axial_line_segment_tri_v3(int axis, const float p1[3], const float p2[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda)
float area_tri_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float normal[3])
Definition math_geom.cc:119
void translate_m4(float mat[4][4], float Tx, float Ty, float Tz)
int isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
bool isect_line_line_strict_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float vi[3], float *r_lambda)
ATTR_WARN_UNUSED_RESULT const BMVert * v
void projmat_dimensions_db(const float winmat_fl[4][4], double *r_left, double *r_right, double *r_bottom, double *r_top, double *r_near, double *r_far)
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
int isect_point_tri_v2(const float pt[2], const float v1[2], const float v2[2], const float v3[2])
bool map_to_sphere(float *r_u, float *r_v, float x, float y, float z)
void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:30
bool is_quad_flip_v3_first_third_fast(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
bool isect_ray_aabb_v3_simple(const float orig[3], const float dir[3], const float bb_min[3], const float bb_max[3], float *tmin, float *tmax)
float ray_point_factor_v3(const float p[3], const float ray_origin[3], const float ray_direction[3])
bool isect_planes_v3_fn(const float planes[][4], int planes_len, float eps_coplanar, float eps_isect, void(*callback_fn)(const float co[3], int i, int j, int k, void *user_data), void *user_data)
static bool isect_tri_tri_v2_impl_vert(const float t_a0[2], const float t_a1[2], const float t_a2[2], const float t_b0[2], const float t_b1[2], const float t_b2[2])
void plane_to_point_vector_v3_normalized(const float plane[4], float r_plane_co[3], float r_plane_no[3])
Definition math_geom.cc:237
void limit_dist_v3(float v1[3], float v2[3], float dist)
float ray_point_factor_v3_ex(const float p[3], const float ray_origin[3], const float ray_direction[3], float epsilon, float fallback)
void closest_to_plane_normalized_v3(float r_close[3], const float plane[4], const float pt[3])
Definition math_geom.cc:458
MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2])
float determinant_m3_array(const float m[3][3])
void plane_from_point_normal_v3(float r_plane[4], const float plane_co[3], const float plane_no[3])
Definition math_geom.cc:225
void closest_to_plane3_normalized_v3(float r_close[3], const float plane[3], const float pt[3])
Definition math_geom.cc:472
bool isect_line_segment_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 perspective_m4(float mat[4][4], float left, float right, float bottom, float top, float nearClip, float farClip)
void dist_squared_to_projected_aabb_precalc(struct DistProjectedAABBPrecalc *precalc, const float projmat[4][4], const float winsize[2], const float mval[2])
Definition math_geom.cc:832
float line_point_factor_v2_ex(const float p[2], const float l1[2], const float l2[2], float epsilon, float fallback)
MINLINE void mul_v3_fl(float r[3], float f)
float dist_to_line_v3(const float p[3], const float l1[3], const float l2[3])
Definition math_geom.cc:557
float dist_squared_to_line_v3(const float p[3], const float l1[3], const float l2[3])
Definition math_geom.cc:549
bool isect_ray_ray_epsilon_v3(const float ray_origin_a[3], const float ray_direction_a[3], const float ray_origin_b[3], const float ray_direction_b[3], float epsilon, float *r_lambda_a, float *r_lambda_b)
float dist_squared_to_line_segment_v2(const float p[2], const float l1[2], const float l2[2])
Definition math_geom.cc:307
void project_v3_v3v3(float out[3], const float p[3], const float v_proj[3])
void barycentric_weights_v2_clamped(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
void orthographic_m4(float mat[4][4], float left, float right, float bottom, float top, float nearClip, float farClip)
MINLINE void zero_v4(float r[4])
void plane_to_point_vector_v3(const float plane[4], float r_plane_co[3], float r_plane_no[3])
Definition math_geom.cc:231
void mul_m4_v3(const float M[4][4], float r[3])
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
MINLINE bool equals_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
void vcloud_estimate_transform_v3(int list_size, const float(*pos)[3], const float *weight, const float(*rpos)[3], const float *rweight, float lloc[3], float rloc[3], float lrot[3][3], float lscale[3][3])
float area_poly_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:186
float volume_tetrahedron_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition math_geom.cc:251
static float tri_signed_area(const float v1[3], const float v2[3], const float v3[3], const int i, const int j)
MINLINE float dot_m4_v3_row_x(const float M[4][4], const float a[3]) ATTR_WARN_UNUSED_RESULT
void transform_point_by_seg_v3(float p_dst[3], const float p_src[3], const float l_dst_p1[3], const float l_dst_p2[3], const float l_src_p1[3], const float l_src_p2[3])
void transpose_m3(float R[3][3])
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void resolve_tri_uv_v2(float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2])
static float snap_coordinate(float u)
MINLINE float area_tri_v2(const float v1[2], const float v2[2], const float v3[2])
static float mean_value_half_tan_v3(const Float3_Len *d_curr, const Float3_Len *d_next)
BMesh const char void * data
bool isect_ray_tri_watertight_v3_simple(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2])
float normal_quad_v3(float n[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition math_geom.cc:62
float dist_to_line_v2(const float p[2], const float l1[2], const float l2[2])
Definition math_geom.cc:302
MINLINE int axis_dominant_v3_single(const float vec[3])
void interp_weights_tri_v3(float w[3], const float v1[3], const float v2[3], const float v3[3], const float co[3])
bool barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
void barycentric_weights_v2_quad(const float v1[2], const float v2[2], const float v3[2], const float v4[2], const float co[2], float w[4])
bool isect_point_poly_v2(const float pt[2], const float verts[][2], unsigned int nr)
MINLINE void cross_v3_v3v3_db(double r[3], const double a[3], const double b[3])
float closest_seg_seg_v2(float r_closest_a[2], float r_closest_b[2], float *r_lambda_a, float *r_lambda_b, const float a1[2], const float a2[2], const float b1[2], const float b2[2])
Definition math_geom.cc:321
void aabb_get_near_far_from_plane(const float plane_no[3], const float bbmin[3], const float bbmax[3], float bb_near[3], float bb_afar[3])
Definition math_geom.cc:665
sqrt(x)+1/max(0
MINLINE void negate_v3(float r[3])
MINLINE float plane_point_side_v3(const float plane[4], const float co[3])
void accumulate_vertex_normals_poly_v3(float **vertnos, const float polyno[3], const float **vertcos, float vdiffs[][3], int nverts)
void unit_m4(float m[4][4])
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
int box_clip_bounds_m4(float boundbox[2][3], const float bounds[4], float winmat[4][4])
float dist_squared_to_plane3_v3(const float p[3], const float plane[3])
Definition math_geom.cc:502
void isect_ray_tri_watertight_v3_precalc(struct IsectRayPrecalc *isect_precalc, const float ray_direction[3])
void resolve_tri_uv_v3(float r_uv[2], const float st[3], const float st0[3], const float st1[3], const float st2[3])
int isect_point_quad_v2(const float p[2], const float v1[2], const float v2[2], const float v3[2], const float v4[2])
float dist_squared_to_line_segment_v3(const float p[3], const float l1[3], const float l2[3])
Definition math_geom.cc:535
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
static void i_multmatrix(const float icand[4][4], float mat[4][4])
void interp_weights_poly_v3(float w[], float v[][3], int n, const float co[3])
int isect_seg_seg_v2_lambda_mu_db(const double v1[2], const double v2[2], const double v3[2], const double v4[2], double *r_lambda, double *r_mu)
float dist_seg_seg_v2(const float a1[3], const float a2[3], const float b1[3], const float b2[3])
float resolve_quad_u_v2(const float st[2], const float st0[2], const float st1[2], const float st2[2], const float st3[2])
bool isect_ray_tri_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
MINLINE void mul_v2_v2fl(float r[2], const float a[2], float f)
MINLINE void zero_v3(float r[3])
void mul_m4_v4(const float mat[4][4], float r[4])
static bool isect_tri_tri_v2_impl_edge(const float t_a0[2], const float t_a1[2], const float t_a2[2], const float t_b0[2], const float t_b1[2], const float t_b2[2])
MINLINE float dot_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
void interp_weights_poly_v2(float w[], float v[][2], int n, const float co[2])
bool isect_ray_ray_v3(const float ray_origin_a[3], const float ray_direction_a[3], const float ray_origin_b[3], const float ray_direction_b[3], float *r_lambda_a, float *r_lambda_b)
bool isect_seg_seg_v2_simple(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
bool isect_line_plane_v3(float r_isect_co[3], const float l1[3], const float l2[3], const float plane_co[3], const float plane_no[3]) ATTR_WARN_UNUSED_RESULT
MINLINE double cross_v2v2_db(const double a[2], const double b[2]) ATTR_WARN_UNUSED_RESULT
void project_plane_v3_v3v3(float out[3], const float p[3], const float v_plane[3])
void copy_m4d_m4(double m1[4][4], const float m2[4][4])
MINLINE float normalize_v3_v3(float r[3], const float a[3])
MINLINE void mul_v3_v3fl(float r[3], const float a[3], float f)
void transpose_m4_m4(float R[4][4], const float M[4][4])
bool isect_point_tri_v2_cw(const float pt[2], const float v1[2], const float v2[2], const float v3[2])
MINLINE float normalize_v3(float n[3])
MINLINE float len_squared_v2(const float v[2]) ATTR_WARN_UNUSED_RESULT
MINLINE void add_v3_v3(float r[3], const float a[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
float cotangent_tri_weight_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:202
void mul_m3_fl(float R[3][3], float f)
float dist_to_plane_v3(const float p[3], const float plane[4])
Definition math_geom.cc:518
void box_minmax_bounds_m4(float min[3], float max[3], float boundbox[2][3], float mat[4][4])
bool is_poly_convex_v2(const float verts[][2], unsigned int nr)
float area_squared_poly_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:196
void axis_angle_to_mat4_single(float R[4][4], char axis, float angle)
int barycentric_inside_triangle_v2(const float w[3])
bool isect_line_segment_tri_epsilon_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], float epsilon)
float closest_ray_to_segment_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], float r_close[3])
Definition math_geom.cc:425
float dist_squared_to_plane_v3(const float p[3], const float plane[4])
Definition math_geom.cc:486
void accumulate_vertex_normals_tri_v3(float n1[3], float n2[3], float n3[3], const float f_no[3], const float co1[3], const float co2[3], const float co3[3])
void rotate_m4(float mat[4][4], char axis, float angle)
MINLINE float dot_m4_v3_row_y(const float M[4][4], const float a[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void madd_v2_v2fl(float r[2], const float a[2], float f)
void unit_m3(float m[3][3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE void copy_v3_fl(float r[3], float f)
void polarview_m4(float mat[4][4], float dist, float azimuth, float incidence, float twist)
MINLINE void sub_v3db_v3fl_v3fl(double r[3], const float a[3], const float b[3])
static bool point_in_slice_as(const float p[3], const float origin[3], const float normal[3])
float dist_squared_to_ray_v3_normalized(const float ray_origin[3], const float ray_direction[3], const float co[3])
Definition math_geom.cc:613
void interp_v2_v2v2(float r[2], const float a[2], const float b[2], float t)
void interp_bilinear_quad_v3(float data[4][3], float u, float v, float res[3])
void lookat_m4(float mat[4][4], float vx, float vy, float vz, float px, float py, float pz, float twist)
MINLINE float max_ff(float a, float b)
bool is_quad_convex_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE float len_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
float dist_to_plane3_v3(const float p[3], const float plane[3])
Definition math_geom.cc:530
float dist_signed_to_plane3_v3(const float p[3], const float plane[3])
Definition math_geom.cc:523
MINLINE void axis_dominant_v3(int *r_axis_a, int *r_axis_b, const float axis[3])
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:104
float closest_to_line_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
bool isect_point_planes_v3_negated(const float(*planes)[4], int totplane, const float p[3])
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])
bool clip_segment_v3_plane(const float p1[3], const float p2[3], const float plane[4], float r_p1[3], float r_p2[3])
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE double dot_v2v2_db(const double a[2], const double b[2]) ATTR_WARN_UNUSED_RESULT
bool isect_point_planes_v3(const float(*planes)[4], int totplane, const float p[3])
float geodesic_distance_propagate_across_triangle(const float v0[3], const float v1[3], const float v2[3], float dist1, float dist2)
float dist_squared_ray_to_aabb_v3_simple(const float ray_origin[3], const float ray_direction[3], const float bb_min[3], const float bb_max[3], float r_point[3], float *r_depth)
Definition math_geom.cc:815
float closest_to_line_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2])
float area_squared_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:111
void interp_barycentric_tri_v3(float data[3][3], float u, float v, float res[3])
void map_to_plane_v2_v3v3(float r_co[2], const float co[3], const float no[3])
MINLINE float square_f(float a)
bool isect_tri_tri_v2(const float t_a0[2], const float t_a1[2], const float t_a2[2], const float t_b0[2], const float t_b1[2], const float t_b2[2])
MINLINE bool is_finite_v4(const float v[4]) ATTR_WARN_UNUSED_RESULT
MINLINE float line_point_side_v2(const float l1[2], const float l2[2], const float pt[2]) ATTR_WARN_UNUSED_RESULT
MINLINE float xor_fl(float x, int y)
void zero_m3(float m[3][3])
void accumulate_vertex_normals_v3(float n1[3], float n2[3], float n3[3], float n4[3], const float f_no[3], const float co1[3], const float co2[3], const float co3[3], const float co4[3])
float area_squared_poly_v3(const float verts[][3], unsigned int nr)
Definition math_geom.cc:144
bool is_edge_convex_v3(const float v1[3], const float v2[3], const float f1_no[3], const float f2_no[3])
bool isect_point_tri_prism_v3(const float p[3], const float v1[3], const float v2[3], const float v3[3])
float dist_squared_ray_to_seg_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], float r_point[3], float *r_depth)
Definition math_geom.cc:629
bool isect_ray_tri_epsilon_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], float epsilon)
float volume_tri_tetrahedron_signed_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:283
void mul_m3_m3m3(float R[3][3], const float A[3][3], const float B[3][3])
void copy_m4_m4(float m1[4][4], const float m2[4][4])
int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
MINLINE float len_v2(const float v[2]) ATTR_WARN_UNUSED_RESULT
MINLINE void mul_v4_fl(float r[4], float f)
float dist_squared_to_projected_aabb(struct DistProjectedAABBPrecalc *data, const float bbmin[3], const float bbmax[3], bool r_axis_closest[3])
Definition math_geom.cc:884
void interp_v3_v3v3v3(float p[3], const float v1[3], const float v2[3], const float v3[3], const float w[3])
float line_plane_factor_v3(const float plane_co[3], const float plane_no[3], const float l1[3], const float l2[3])
void ortho_basis_v3v3_v3(float r_n1[3], float r_n2[3], const float n[3])
float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2])
Definition math_geom.cc:294
static bool getLowestRoot(const float a, const float b, const float c, const float maxR, float *root)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
float area_poly_v3(const float verts[][3], unsigned int nr)
Definition math_geom.cc:137
float volume_tri_tetrahedron_signed_v3_6x(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:275
float dist_signed_squared_to_plane3_v3(const float p[3], const float plane[3])
Definition math_geom.cc:495
MINLINE float len_squared_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
bool clip_segment_v3_plane_n(const float p1[3], const float p2[3], const float plane_array[][4], int plane_num, float r_p1[3], float r_p2[3])
void mul_v3_m3v3(float r[3], const float M[3][3], const float a[3])
bool is_negative_m3(const float mat[3][3])
void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
float closest_to_line_segment_v2(float r_close[2], const float p[2], const float l1[2], const float l2[2])
Definition math_geom.cc:381
float cubic_tangent_factor_circle_v3(const float tan_l[3], const float tan_r[3])
bool isect_aabb_aabb_v3(const float min1[3], const float max1[3], const float min2[3], const float max2[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
bool is_quad_convex_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
void map_to_plane_axis_angle_v2_v3v3fl(float r_co[2], const float co[3], const float axis[3], float angle)
MINLINE double dot_v3db_v3fl(const double a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void zero_v2(float r[2])
void isect_ray_aabb_v3_precalc(struct IsectRayAABB_Precalc *data, const float ray_origin[3], const float ray_direction[3])
float dist_signed_squared_to_corner_v3v3v3(const float p[3], const float v1[3], const float v2[3], const float v3[3], const float axis_ref[3])
Definition math_geom.cc:562
float volume_tetrahedron_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition math_geom.cc:263
float determinant_m3(float a1, float a2, float a3, float b1, float b2, float b3, float c1, float c2, float c3)
float dist_squared_ray_to_aabb_v3(const struct DistRayAABB_Precalc *data, const float bb_min[3], const float bb_max[3], float r_point[3], float *r_depth)
MINLINE bool is_zero_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
int isect_line_line_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float r_vi[2])
void closest_to_plane3_v3(float r_close[3], const float plane[3], const float pt[3])
Definition math_geom.cc:465
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
MINLINE int float_as_int(float f)
float area_poly_signed_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:191
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
int isect_line_line_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float r_i1[3], float r_i2[3])
void add_m3_m3m3(float R[3][3], const float A[3][3], const float B[3][3])
MINLINE void madd_v2_v2v2fl(float r[2], const float a[2], const float b[2], float f)
void tangent_from_uv_v3(const float uv1[2], const float uv2[2], const float uv3[2], const float co1[3], const float co2[3], const float co3[3], const float n[3], float r_tang[3])
const btScalar eps
Definition poly34.cpp:11
#define fabsf
#define sqrtf
#define sinf
#define tanf
#define cosf
#define atan2f
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define min(a, b)
Definition sort.cc:38