Blender V5.3
collision.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10
11#include "MEM_guardedalloc.h"
12
13#include "DNA_cloth_types.h"
14#include "DNA_layer_types.h"
16#include "DNA_object_types.h"
17#include "DNA_scene_types.h"
18
19#include "BLI_listbase.hh"
20#include "BLI_math_geom_c.hh"
21#include "BLI_math_vector_c.hh"
22#include "BLI_task_c.hh"
23
24#include "BKE_cloth.hh"
25#include "BKE_collection.hh"
26#include "BKE_modifier.hh"
27
28#include "BKE_collision.h"
29#include "BLI_kdopbvh.hh"
30
31#include "DEG_depsgraph.hh"
34
35namespace blender {
36
37#ifdef WITH_ELTOPO
38# include "eltopo-capi.h"
39#endif
40
50
57
58/* -------------------------------------------------------------------- */
61
63 const float step,
64 const float prevstep,
65 const bool moving_bvh)
66{
67 uint i = 0;
68
69 /* the collider doesn't move this frame */
70 if (collmd->is_static) {
71 for (i = 0; i < collmd->mvert_num; i++) {
72 zero_v3(collmd->current_v[i]);
73 }
74
75 return;
76 }
77
78 for (i = 0; i < collmd->mvert_num; i++) {
79 interp_v3_v3v3(collmd->current_x[i], collmd->x[i], collmd->xnew[i], prevstep);
80 interp_v3_v3v3(collmd->current_xnew[i], collmd->x[i], collmd->xnew[i], step);
81 sub_v3_v3v3(collmd->current_v[i], collmd->current_xnew[i], collmd->current_x[i]);
82 }
83
85 collmd->current_xnew,
86 collmd->current_x,
87 reinterpret_cast<const int3 *>(collmd->vert_tris),
88 collmd->tri_num,
89 moving_bvh);
90}
91
92BVHTree *bvhtree_build_from_mvert(const float (*positions)[3],
93 const int3 *vert_tris,
94 int tri_num,
95 float epsilon)
96{
97 BVHTree *tree = BLI_bvhtree_new(tri_num, epsilon, 4, 26);
98
99 /* fill tree */
100 for (int i = 0; i < tri_num; i++) {
101 float co[3][3];
102
103 copy_v3_v3(co[0], positions[vert_tris[i][0]]);
104 copy_v3_v3(co[1], positions[vert_tris[i][1]]);
105 copy_v3_v3(co[2], positions[vert_tris[i][2]]);
106
107 BLI_bvhtree_insert(tree, i, co[0], 3);
108 }
109
110 /* balance tree */
112
113 return tree;
114}
115
117 const float (*positions)[3],
118 const float (*positions_moving)[3],
119 const int3 *vert_tris,
120 int tri_num,
121 bool moving)
122{
123
124 if ((bvhtree == nullptr) || (positions == nullptr)) {
125 return;
126 }
127
128 if (positions_moving == nullptr) {
129 moving = false;
130 }
131
132 for (int i = 0; i < tri_num; i++) {
133 float co[3][3];
134 bool ret;
135
136 copy_v3_v3(co[0], positions[vert_tris[i][0]]);
137 copy_v3_v3(co[1], positions[vert_tris[i][1]]);
138 copy_v3_v3(co[2], positions[vert_tris[i][2]]);
139
140 /* copy new locations into array */
141 if (moving) {
142 float co_moving[3][3];
143 /* update moving positions */
144 copy_v3_v3(co_moving[0], positions_moving[vert_tris[i][0]]);
145 copy_v3_v3(co_moving[1], positions_moving[vert_tris[i][1]]);
146 copy_v3_v3(co_moving[2], positions_moving[vert_tris[i][2]]);
147
148 ret = BLI_bvhtree_update_node(bvhtree, i, &co[0][0], &co_moving[0][0], 3);
149 }
150 else {
151 ret = BLI_bvhtree_update_node(bvhtree, i, &co[0][0], nullptr, 3);
152 }
153
154 /* check if tree is already full */
155 if (ret == false) {
156 break;
157 }
158 }
159
161}
162
164
166{
167 return (++i < 3) ? i : 0;
168}
169
170static float compute_collision_point_tri_tri(const float a1[3],
171 const float a2[3],
172 const float a3[3],
173 const float b1[3],
174 const float b2[3],
175 const float b3[3],
176 bool culling,
177 bool use_normal,
178 float r_a[3],
179 float r_b[3],
180 float r_vec[3])
181{
182 float a[3][3];
183 float b[3][3];
184 float dist = FLT_MAX;
185 float tmp_co1[3], tmp_co2[3];
186 float isect_a[3], isect_b[3];
187 float tmp, tmp_vec[3];
188 float normal[3], cent[3];
189 bool backside = false;
190
191 copy_v3_v3(a[0], a1);
192 copy_v3_v3(a[1], a2);
193 copy_v3_v3(a[2], a3);
194
195 copy_v3_v3(b[0], b1);
196 copy_v3_v3(b[1], b2);
197 copy_v3_v3(b[2], b3);
198
199 /* Find intersections. */
200 int tri_a_edge_isect_count;
201 const bool is_intersecting = isect_tri_tri_v3_ex(
202 a, b, isect_a, isect_b, &tri_a_edge_isect_count);
203
204 /* Determine collision side. */
205 if (culling) {
206 normal_tri_v3(normal, b[0], b[1], b[2]);
207 mid_v3_v3v3v3(cent, b[0], b[1], b[2]);
208
209 if (!is_intersecting) {
210 for (int i = 0; i < 3; i++) {
211 sub_v3_v3v3(tmp_vec, a[i], cent);
212 if (dot_v3v3(tmp_vec, normal) < 0.0f) {
213 backside = true;
214 break;
215 }
216 }
217 }
218 else if (tri_a_edge_isect_count != 1) {
219 /* It is not Edge intersection. */
220 backside = true;
221 }
222 }
223 else if (use_normal) {
224 normal_tri_v3(normal, b[0], b[1], b[2]);
225 }
226
227 if (tri_a_edge_isect_count == 1) {
228 /* Edge intersection. */
229 copy_v3_v3(r_a, isect_a);
230 copy_v3_v3(r_b, isect_b);
231
232 if (use_normal) {
233 copy_v3_v3(r_vec, normal);
234 }
235 else {
236 sub_v3_v3v3(r_vec, r_b, r_a);
237 }
238
239 return 0.0f;
240 }
241
242 if (backside) {
243 float maxdist = 0.0f;
244 bool found = false;
245
246 /* Point projections. */
247 for (int i = 0; i < 3; i++) {
248 if (isect_ray_tri_v3(a[i], normal, b[0], b[1], b[2], &tmp, nullptr)) {
249 if (tmp > maxdist) {
250 maxdist = tmp;
251 copy_v3_v3(r_a, a[i]);
252 madd_v3_v3v3fl(r_b, a[i], normal, tmp);
253 found = true;
254 }
255 }
256 }
257
258 negate_v3(normal);
259
260 for (int i = 0; i < 3; i++) {
261 if (isect_ray_tri_v3(b[i], normal, a[0], a[1], a[2], &tmp, nullptr)) {
262 if (tmp > maxdist) {
263 maxdist = tmp;
264 madd_v3_v3v3fl(r_a, b[i], normal, tmp);
265 copy_v3_v3(r_b, b[i]);
266 found = true;
267 }
268 }
269 }
270
271 negate_v3(normal);
272
273 /* Edge projections. */
274 for (int i = 0; i < 3; i++) {
275 float dir[3];
276
277 sub_v3_v3v3(tmp_vec, b[next_ind(i)], b[i]);
278 cross_v3_v3v3(dir, tmp_vec, normal);
279
280 for (int j = 0; j < 3; j++) {
281 if (isect_line_plane_v3(tmp_co1, a[j], a[next_ind(j)], b[i], dir) &&
282 point_in_slice_seg(tmp_co1, a[j], a[next_ind(j)]) &&
283 point_in_slice_seg(tmp_co1, b[i], b[next_ind(i)]))
284 {
285 closest_to_line_v3(tmp_co2, tmp_co1, b[i], b[next_ind(i)]);
286 sub_v3_v3v3(tmp_vec, tmp_co1, tmp_co2);
287 tmp = len_v3(tmp_vec);
288
289 if ((tmp > maxdist) && (dot_v3v3(tmp_vec, normal) < 0.0f)) {
290 maxdist = tmp;
291 copy_v3_v3(r_a, tmp_co1);
292 copy_v3_v3(r_b, tmp_co2);
293 found = true;
294 }
295 }
296 }
297 }
298
299 /* If no point is found, will fall back onto regular proximity test below. */
300 if (found) {
301 sub_v3_v3v3(r_vec, r_b, r_a);
302
303 if (use_normal) {
304 if (dot_v3v3(normal, r_vec) >= 0.0f) {
305 copy_v3_v3(r_vec, normal);
306 }
307 else {
308 negate_v3_v3(r_vec, normal);
309 }
310 }
311
312 return 0.0f;
313 }
314 }
315
316 /* Closest point. */
317 for (int i = 0; i < 3; i++) {
318 closest_on_tri_to_point_v3(tmp_co1, a[i], b[0], b[1], b[2]);
319 tmp = len_squared_v3v3(tmp_co1, a[i]);
320
321 if (tmp < dist) {
322 dist = tmp;
323 copy_v3_v3(r_a, a[i]);
324 copy_v3_v3(r_b, tmp_co1);
325 }
326 }
327
328 for (int i = 0; i < 3; i++) {
329 closest_on_tri_to_point_v3(tmp_co1, b[i], a[0], a[1], a[2]);
330 tmp = len_squared_v3v3(tmp_co1, b[i]);
331
332 if (tmp < dist) {
333 dist = tmp;
334 copy_v3_v3(r_a, tmp_co1);
335 copy_v3_v3(r_b, b[i]);
336 }
337 }
338
339 /* Closest edge. */
340 if (!is_intersecting) {
341 for (int i = 0; i < 3; i++) {
342 for (int j = 0; j < 3; j++) {
343 isect_seg_seg_v3(a[i], a[next_ind(i)], b[j], b[next_ind(j)], tmp_co1, tmp_co2);
344 tmp = len_squared_v3v3(tmp_co1, tmp_co2);
345
346 if (tmp < dist) {
347 dist = tmp;
348 copy_v3_v3(r_a, tmp_co1);
349 copy_v3_v3(r_b, tmp_co2);
350 }
351 }
352 }
353 }
354
355 if (!is_intersecting) {
356 sub_v3_v3v3(r_vec, r_a, r_b);
357 dist = sqrtf(dist);
358 }
359 else {
360 sub_v3_v3v3(r_vec, r_b, r_a);
361 dist = 0.0f;
362 }
363
364 if (culling && use_normal) {
365 copy_v3_v3(r_vec, normal);
366 }
367 else if (use_normal) {
368 if (dot_v3v3(normal, r_vec) >= 0.0f) {
369 copy_v3_v3(r_vec, normal);
370 }
371 else {
372 negate_v3_v3(r_vec, normal);
373 }
374 }
375 else if (culling && (dot_v3v3(r_vec, normal) < 0.0f)) {
376 return FLT_MAX;
377 }
378
379 return dist;
380}
381
382static float compute_collision_point_edge_tri(const float a1[3],
383 const float a2[3],
384 const float b1[3],
385 const float b2[3],
386 const float b3[3],
387 bool culling,
388 bool use_normal,
389 float r_a[3],
390 float r_b[3],
391 float r_vec[3])
392{
393 float a[2][3];
394 float b[3][3];
395 float dist = FLT_MAX;
396 float tmp_co1[3], tmp_co2[3];
397 float isect_a[3];
398 bool isect = false;
399 float tmp, tmp_vec[3];
400 float normal[3], cent[3];
401 bool backside = false;
402
403 copy_v3_v3(a[0], a1);
404 copy_v3_v3(a[1], a2);
405
406 copy_v3_v3(b[0], b1);
407 copy_v3_v3(b[1], b2);
408 copy_v3_v3(b[2], b3);
409
410 normal_tri_v3(normal, b[0], b[1], b[2]);
411
412 /* Find intersection. */
413 if (isect_line_segment_tri_v3(a[0], a[1], b[0], b[1], b[2], &tmp, nullptr)) {
414 interp_v3_v3v3(isect_a, a[0], a[1], tmp);
415 isect = true;
416 }
417
418 /* Determine collision side. */
419 if (culling) {
420 if (isect) {
421 backside = true;
422 }
423 else {
424 mid_v3_v3v3v3(cent, b[0], b[1], b[2]);
425
426 for (int i = 0; i < 2; i++) {
427 sub_v3_v3v3(tmp_vec, a[i], cent);
428 if (dot_v3v3(tmp_vec, normal) < 0.0f) {
429 backside = true;
430 break;
431 }
432 }
433 }
434 }
435
436 if (isect) {
437 /* Edge intersection. */
438 copy_v3_v3(r_a, isect_a);
439 copy_v3_v3(r_b, isect_a);
440
441 copy_v3_v3(r_vec, normal);
442
443 return 0.0f;
444 }
445
446 if (backside) {
447 float maxdist = 0.0f;
448 bool found = false;
449
450 /* Point projections. */
451 for (int i = 0; i < 2; i++) {
452 if (isect_ray_tri_v3(a[i], normal, b[0], b[1], b[2], &tmp, nullptr)) {
453 if (tmp > maxdist) {
454 maxdist = tmp;
455 copy_v3_v3(r_a, a[i]);
456 madd_v3_v3v3fl(r_b, a[i], normal, tmp);
457 found = true;
458 }
459 }
460 }
461
462 /* Edge projections. */
463 for (int i = 0; i < 3; i++) {
464 float dir[3];
465
466 sub_v3_v3v3(tmp_vec, b[next_ind(i)], b[i]);
467 cross_v3_v3v3(dir, tmp_vec, normal);
468
469 if (isect_line_plane_v3(tmp_co1, a[0], a[1], b[i], dir) &&
470 point_in_slice_seg(tmp_co1, a[0], a[1]) &&
471 point_in_slice_seg(tmp_co1, b[i], b[next_ind(i)]))
472 {
473 closest_to_line_v3(tmp_co2, tmp_co1, b[i], b[next_ind(i)]);
474 sub_v3_v3v3(tmp_vec, tmp_co1, tmp_co2);
475 tmp = len_v3(tmp_vec);
476
477 if ((tmp > maxdist) && (dot_v3v3(tmp_vec, normal) < 0.0f)) {
478 maxdist = tmp;
479 copy_v3_v3(r_a, tmp_co1);
480 copy_v3_v3(r_b, tmp_co2);
481 found = true;
482 }
483 }
484 }
485
486 /* If no point is found, will fall back onto regular proximity test below. */
487 if (found) {
488 sub_v3_v3v3(r_vec, r_b, r_a);
489
490 if (use_normal) {
491 if (dot_v3v3(normal, r_vec) >= 0.0f) {
492 copy_v3_v3(r_vec, normal);
493 }
494 else {
495 negate_v3_v3(r_vec, normal);
496 }
497 }
498
499 return 0.0f;
500 }
501 }
502
503 /* Closest point. */
504 for (int i = 0; i < 2; i++) {
505 closest_on_tri_to_point_v3(tmp_co1, a[i], b[0], b[1], b[2]);
506 tmp = len_squared_v3v3(tmp_co1, a[i]);
507
508 if (tmp < dist) {
509 dist = tmp;
510 copy_v3_v3(r_a, a[i]);
511 copy_v3_v3(r_b, tmp_co1);
512 }
513 }
514
515 /* Closest edge. */
516 if (!isect) {
517 for (int j = 0; j < 3; j++) {
518 isect_seg_seg_v3(a[0], a[1], b[j], b[next_ind(j)], tmp_co1, tmp_co2);
519 tmp = len_squared_v3v3(tmp_co1, tmp_co2);
520
521 if (tmp < dist) {
522 dist = tmp;
523 copy_v3_v3(r_a, tmp_co1);
524 copy_v3_v3(r_b, tmp_co2);
525 }
526 }
527 }
528
529 if (isect) {
530 sub_v3_v3v3(r_vec, r_b, r_a);
531 dist = 0.0f;
532 }
533 else {
534 sub_v3_v3v3(r_vec, r_a, r_b);
535 dist = sqrtf(dist);
536 }
537
538 if (culling && use_normal) {
539 copy_v3_v3(r_vec, normal);
540 }
541 else if (use_normal) {
542 if (dot_v3v3(normal, r_vec) >= 0.0f) {
543 copy_v3_v3(r_vec, normal);
544 }
545 else {
546 negate_v3_v3(r_vec, normal);
547 }
548 }
549 else if (culling && (dot_v3v3(r_vec, normal) < 0.0f)) {
550 return FLT_MAX;
551 }
552
553 return dist;
554}
555
556/* `w3` is not perfect. */
557static void collision_compute_barycentric(const float pv[3],
558 const float p1[3],
559 const float p2[3],
560 const float p3[3],
561 float *w1,
562 float *w2,
563 float *w3)
564{
565 /* dot_v3v3 */
566#define INPR(v1, v2) ((v1)[0] * (v2)[0] + (v1)[1] * (v2)[1] + (v1)[2] * (v2)[2])
567
568 double tempV1[3], tempV2[3], tempV4[3];
569 double a, b, c, d, e, f;
570
571 sub_v3db_v3fl_v3fl(tempV1, p1, p3);
572 sub_v3db_v3fl_v3fl(tempV2, p2, p3);
573 sub_v3db_v3fl_v3fl(tempV4, pv, p3);
574
575 a = INPR(tempV1, tempV1);
576 b = INPR(tempV1, tempV2);
577 c = INPR(tempV2, tempV2);
578 e = INPR(tempV1, tempV4);
579 f = INPR(tempV2, tempV4);
580
581 d = (a * c - b * b);
582
583 if (fabs(d) < double(ALMOST_ZERO)) {
584 *w1 = *w2 = *w3 = 1.0 / 3.0;
585 return;
586 }
587
588 w1[0] = float((e * c - b * f) / d);
589 w1[0] = std::max<float>(w1[0], 0);
590
591 w2[0] = float((f - b * double(w1[0])) / c);
592 w2[0] = std::max<float>(w2[0], 0);
593
594 w3[0] = 1.0f - w1[0] - w2[0];
595
596#undef INPR
597}
598
599#ifdef __GNUC__
600# pragma GCC diagnostic push
601# pragma GCC diagnostic ignored "-Wdouble-promotion"
602#endif
603
605 const float v1[3],
606 const float v2[3],
607 const float v3[3],
608 const double w1,
609 const double w2,
610 const double w3)
611{
612 zero_v3(to);
613 VECADDMUL(to, v1, w1);
614 VECADDMUL(to, v2, w2);
615 VECADDMUL(to, v3, w3);
616}
617
618static void cloth_collision_impulse_vert(const float clamp_sq,
619 const float impulse[3],
620 ClothVertex *vert)
621{
622 float impulse_len_sq = len_squared_v3(impulse);
623
624 if ((clamp_sq > 0.0f) && (impulse_len_sq > clamp_sq)) {
625 return;
626 }
627
628 if (fabsf(vert->impulse[0]) < fabsf(impulse[0])) {
629 vert->impulse[0] = impulse[0];
630 }
631
632 if (fabsf(vert->impulse[1]) < fabsf(impulse[1])) {
633 vert->impulse[1] = impulse[1];
634 }
635
636 if (fabsf(vert->impulse[2]) < fabsf(impulse[2])) {
637 vert->impulse[2] = impulse[2];
638 }
639
640 vert->impulse_count++;
641}
642
644 CollisionModifierData *collmd,
645 Object *collob,
646 CollPair *collpair,
647 uint collision_count,
648 const float dt)
649{
650 int result = 0;
651 Cloth *cloth = clmd->clothObject;
652 const float clamp_sq = square_f(clmd->coll_parms->clamp * dt);
653 const float time_multiplier = 1.0f / (clmd->sim_parms->dt * clmd->sim_parms->timescale);
654 const float epsilon2 = BLI_bvhtree_get_epsilon(collmd->bvhtree);
655 const float min_distance = (clmd->coll_parms->epsilon + epsilon2) * (8.0f / 9.0f);
656
657 const bool is_hair = (clmd->hairdata != nullptr);
658 for (int i = 0; i < collision_count; i++, collpair++) {
659 float i1[3], i2[3], i3[3];
660 float v1[3], v2[3], relativeVelocity[3];
661 zero_v3(i1);
662 zero_v3(i2);
663 zero_v3(i3);
664
665 /* Only handle static collisions here. */
666 if (collpair->flag & (COLLISION_IN_FUTURE | COLLISION_INACTIVE)) {
667 continue;
668 }
669
670 /* Compute barycentric coordinates and relative "velocity" for both collision points. */
671 float w1 = collpair->aw1, w2 = collpair->aw2, w3 = collpair->aw3;
672 float u1 = collpair->bw1, u2 = collpair->bw2, u3 = collpair->bw3;
673
674 if (is_hair) {
675 interp_v3_v3v3(v1, cloth->verts[collpair->ap1].tv, cloth->verts[collpair->ap2].tv, w2);
676 }
677 else {
679 cloth->verts[collpair->ap1].tv,
680 cloth->verts[collpair->ap2].tv,
681 cloth->verts[collpair->ap3].tv,
682 w1,
683 w2,
684 w3);
685 }
686
688 collmd->current_v[collpair->bp1],
689 collmd->current_v[collpair->bp2],
690 collmd->current_v[collpair->bp3],
691 u1,
692 u2,
693 u3);
694
695 sub_v3_v3v3(relativeVelocity, v2, v1);
696
697 /* Calculate the normal component of the relative velocity
698 * (actually only the magnitude - the direction is stored in 'normal'). */
699 const float magrelVel = dot_v3v3(relativeVelocity, collpair->normal);
700 const float d = min_distance - collpair->distance;
701
702 /* If magrelVel < 0 the edges are approaching each other. */
703 if (magrelVel > 0.0f) {
704 /* Calculate Impulse magnitude to stop all motion in normal direction. */
705 float magtangent = 0, repulse = 0;
706 double impulse = 0.0;
707 float vrel_t_pre[3];
708 float temp[3];
709
710 /* Calculate tangential velocity. */
711 copy_v3_v3(temp, collpair->normal);
712 mul_v3_fl(temp, magrelVel);
713 sub_v3_v3v3(vrel_t_pre, relativeVelocity, temp);
714
715 /* Decrease in magnitude of relative tangential velocity due to coulomb friction
716 * in original formula "magrelVel" should be the
717 * "change of relative velocity in normal direction". */
718 magtangent = min_ff(collob->pd->pdef_cfrict * 0.01f * magrelVel, len_v3(vrel_t_pre));
719
720 /* Apply friction impulse. */
721 if (magtangent > ALMOST_ZERO) {
722 normalize_v3(vrel_t_pre);
723
724 impulse = magtangent / 1.5;
725
726 VECADDMUL(i1, vrel_t_pre, double(w1) * impulse);
727 VECADDMUL(i2, vrel_t_pre, double(w2) * impulse);
728
729 if (!is_hair) {
730 VECADDMUL(i3, vrel_t_pre, double(w3) * impulse);
731 }
732 }
733
734 /* Apply velocity stopping impulse. */
735 impulse = magrelVel / 1.5f;
736
737 VECADDMUL(i1, collpair->normal, double(w1) * impulse);
738 VECADDMUL(i2, collpair->normal, double(w2) * impulse);
739 if (!is_hair) {
740 VECADDMUL(i3, collpair->normal, double(w3) * impulse);
741 }
742
743 if ((magrelVel < 0.1f * d * time_multiplier) && (d > ALMOST_ZERO)) {
744 repulse = std::min(d / time_multiplier, 0.1f * d * time_multiplier - magrelVel);
745
746 /* Stay on the safe side and clamp repulse. */
747 if (impulse > ALMOST_ZERO) {
748 repulse = min_ff(repulse, 5.0f * impulse);
749 }
750
751 repulse = max_ff(impulse, repulse);
752
753 impulse = repulse / 1.5f;
754
755 VECADDMUL(i1, collpair->normal, impulse);
756 VECADDMUL(i2, collpair->normal, impulse);
757 if (!is_hair) {
758 VECADDMUL(i3, collpair->normal, impulse);
759 }
760 }
761
762 result = 1;
763 }
764 else if (d > ALMOST_ZERO) {
765 /* Stay on the safe side and clamp repulse. */
766 float repulse = d / time_multiplier;
767 float impulse = repulse / 4.5f;
768
769 VECADDMUL(i1, collpair->normal, w1 * impulse);
770 VECADDMUL(i2, collpair->normal, w2 * impulse);
771
772 if (!is_hair) {
773 VECADDMUL(i3, collpair->normal, w3 * impulse);
774 }
775
776 result = 1;
777 }
778
779 if (result) {
780 cloth_collision_impulse_vert(clamp_sq, i1, &cloth->verts[collpair->ap1]);
781 cloth_collision_impulse_vert(clamp_sq, i2, &cloth->verts[collpair->ap2]);
782 if (!is_hair) {
783 cloth_collision_impulse_vert(clamp_sq, i3, &cloth->verts[collpair->ap3]);
784 }
785 }
786 }
787
788 return result;
789}
790
792 CollPair *collpair,
793 uint collision_count,
794 const float dt)
795{
796 int result = 0;
797 Cloth *cloth = clmd->clothObject;
798 const float clamp_sq = square_f(clmd->coll_parms->self_clamp * dt);
799 const float time_multiplier = 1.0f / (clmd->sim_parms->dt * clmd->sim_parms->timescale);
800 const float min_distance = (2.0f * clmd->coll_parms->selfepsilon) * (8.0f / 9.0f);
801
802 for (int i = 0; i < collision_count; i++, collpair++) {
803 float ia[3][3] = {{0.0f}};
804 float ib[3][3] = {{0.0f}};
805 float v1[3], v2[3], relativeVelocity[3];
806
807 /* Only handle static collisions here. */
808 if (collpair->flag & (COLLISION_IN_FUTURE | COLLISION_INACTIVE)) {
809 continue;
810 }
811
812 /* Retrieve barycentric coordinates for both collision points. */
813 float w1 = collpair->aw1, w2 = collpair->aw2, w3 = collpair->aw3;
814 float u1 = collpair->bw1, u2 = collpair->bw2, u3 = collpair->bw3;
815
816 /* Calculate relative "velocity". */
818 cloth->verts[collpair->ap1].tv,
819 cloth->verts[collpair->ap2].tv,
820 cloth->verts[collpair->ap3].tv,
821 w1,
822 w2,
823 w3);
824
826 cloth->verts[collpair->bp1].tv,
827 cloth->verts[collpair->bp2].tv,
828 cloth->verts[collpair->bp3].tv,
829 u1,
830 u2,
831 u3);
832
833 sub_v3_v3v3(relativeVelocity, v2, v1);
834
835 /* Calculate the normal component of the relative velocity
836 * (actually only the magnitude - the direction is stored in 'normal'). */
837 const float magrelVel = dot_v3v3(relativeVelocity, collpair->normal);
838 const float d = min_distance - collpair->distance;
839
840 /* TODO: Impulses should be weighed by mass as this is self col,
841 * this has to be done after mass distribution is implemented. */
842
843 /* If magrelVel < 0 the edges are approaching each other. */
844 if (magrelVel > 0.0f) {
845 /* Calculate Impulse magnitude to stop all motion in normal direction. */
846 float magtangent = 0, repulse = 0;
847 double impulse = 0.0;
848 float vrel_t_pre[3];
849 float temp[3];
850
851 /* Calculate tangential velocity. */
852 copy_v3_v3(temp, collpair->normal);
853 mul_v3_fl(temp, magrelVel);
854 sub_v3_v3v3(vrel_t_pre, relativeVelocity, temp);
855
856 /* Decrease in magnitude of relative tangential velocity due to coulomb friction
857 * in original formula "magrelVel" should be the
858 * "change of relative velocity in normal direction". */
859 magtangent = min_ff(clmd->coll_parms->self_friction * 0.01f * magrelVel, len_v3(vrel_t_pre));
860
861 /* Apply friction impulse. */
862 if (magtangent > ALMOST_ZERO) {
863 normalize_v3(vrel_t_pre);
864
865 impulse = magtangent / 1.5;
866
867 VECADDMUL(ia[0], vrel_t_pre, double(w1) * impulse);
868 VECADDMUL(ia[1], vrel_t_pre, double(w2) * impulse);
869 VECADDMUL(ia[2], vrel_t_pre, double(w3) * impulse);
870
871 VECADDMUL(ib[0], vrel_t_pre, double(u1) * -impulse);
872 VECADDMUL(ib[1], vrel_t_pre, double(u2) * -impulse);
873 VECADDMUL(ib[2], vrel_t_pre, double(u3) * -impulse);
874 }
875
876 /* Apply velocity stopping impulse. */
877 impulse = magrelVel / 3.0f;
878
879 VECADDMUL(ia[0], collpair->normal, double(w1) * impulse);
880 VECADDMUL(ia[1], collpair->normal, double(w2) * impulse);
881 VECADDMUL(ia[2], collpair->normal, double(w3) * impulse);
882
883 VECADDMUL(ib[0], collpair->normal, double(u1) * -impulse);
884 VECADDMUL(ib[1], collpair->normal, double(u2) * -impulse);
885 VECADDMUL(ib[2], collpair->normal, double(u3) * -impulse);
886
887 if ((magrelVel < 0.1f * d * time_multiplier) && (d > ALMOST_ZERO)) {
888 repulse = std::min(d / time_multiplier, 0.1f * d * time_multiplier - magrelVel);
889
890 if (impulse > ALMOST_ZERO) {
891 repulse = min_ff(repulse, 5.0 * impulse);
892 }
893
894 repulse = max_ff(impulse, repulse);
895 impulse = repulse / 1.5f;
896
897 VECADDMUL(ia[0], collpair->normal, double(w1) * impulse);
898 VECADDMUL(ia[1], collpair->normal, double(w2) * impulse);
899 VECADDMUL(ia[2], collpair->normal, double(w3) * impulse);
900
901 VECADDMUL(ib[0], collpair->normal, double(u1) * -impulse);
902 VECADDMUL(ib[1], collpair->normal, double(u2) * -impulse);
903 VECADDMUL(ib[2], collpair->normal, double(u3) * -impulse);
904 }
905
906 result = 1;
907 }
908 else if (d > ALMOST_ZERO) {
909 /* Stay on the safe side and clamp repulse. */
910 float repulse = d * 1.0f / time_multiplier;
911 float impulse = repulse / 9.0f;
912
913 VECADDMUL(ia[0], collpair->normal, w1 * impulse);
914 VECADDMUL(ia[1], collpair->normal, w2 * impulse);
915 VECADDMUL(ia[2], collpair->normal, w3 * impulse);
916
917 VECADDMUL(ib[0], collpair->normal, u1 * -impulse);
918 VECADDMUL(ib[1], collpair->normal, u2 * -impulse);
919 VECADDMUL(ib[2], collpair->normal, u3 * -impulse);
920
921 result = 1;
922 }
923
924 if (result) {
925 cloth_collision_impulse_vert(clamp_sq, ia[0], &cloth->verts[collpair->ap1]);
926 cloth_collision_impulse_vert(clamp_sq, ia[1], &cloth->verts[collpair->ap2]);
927 cloth_collision_impulse_vert(clamp_sq, ia[2], &cloth->verts[collpair->ap3]);
928
929 cloth_collision_impulse_vert(clamp_sq, ib[0], &cloth->verts[collpair->bp1]);
930 cloth_collision_impulse_vert(clamp_sq, ib[1], &cloth->verts[collpair->bp2]);
931 cloth_collision_impulse_vert(clamp_sq, ib[2], &cloth->verts[collpair->bp3]);
932 }
933 }
934
935 return result;
936}
937
938#ifdef __GNUC__
939# pragma GCC diagnostic pop
940#endif
941
943 const Cloth *cloth,
944 const int3 vert_tri_a)
945{
946 const ClothVertex *verts = cloth->verts;
947
948 /* Fully pinned triangles don't need collision processing. */
949 const int flags_a = verts[vert_tri_a[0]].flags & verts[vert_tri_a[1]].flags &
950 verts[vert_tri_a[2]].flags;
951
953 return false;
954 }
955
956 return true;
957}
958
959static void cloth_collision(void *__restrict userdata,
960 const int index,
961 const TaskParallelTLS *__restrict /*tls*/)
962{
963 ColDetectData *data = static_cast<ColDetectData *>(userdata);
964
965 ClothModifierData *clmd = data->clmd;
966 CollisionModifierData *collmd = data->collmd;
967 CollPair *collpair = data->collisions;
968 ClothVertex *verts1 = clmd->clothObject->verts;
969 float distance = 0.0f;
970 float epsilon1 = clmd->coll_parms->epsilon;
971 float epsilon2 = BLI_bvhtree_get_epsilon(collmd->bvhtree);
972 float pa[3], pb[3], vect[3];
973
974 const int3 vert_tri_a = clmd->clothObject->vert_tris[data->overlap[index].indexA];
975 const int3 vert_tri_b = collmd->vert_tris[data->overlap[index].indexB];
976
977 /* Compute distance and normal. */
978 distance = compute_collision_point_tri_tri(verts1[vert_tri_a[0]].tx,
979 verts1[vert_tri_a[1]].tx,
980 verts1[vert_tri_a[2]].tx,
981 collmd->current_xnew[vert_tri_b[0]],
982 collmd->current_xnew[vert_tri_b[1]],
983 collmd->current_xnew[vert_tri_b[2]],
984 data->culling,
985 data->use_normal,
986 pa,
987 pb,
988 vect);
989
990 if ((distance <= (epsilon1 + epsilon2 + ALMOST_ZERO)) && (len_squared_v3(vect) > ALMOST_ZERO)) {
991 collpair[index].ap1 = vert_tri_a[0];
992 collpair[index].ap2 = vert_tri_a[1];
993 collpair[index].ap3 = vert_tri_a[2];
994
995 collpair[index].bp1 = vert_tri_b[0];
996 collpair[index].bp2 = vert_tri_b[1];
997 collpair[index].bp3 = vert_tri_b[2];
998
999 copy_v3_v3(collpair[index].pa, pa);
1000 copy_v3_v3(collpair[index].pb, pb);
1001 copy_v3_v3(collpair[index].vector, vect);
1002
1003 normalize_v3_v3(collpair[index].normal, collpair[index].vector);
1004
1005 collpair[index].distance = distance;
1006 collpair[index].flag = 0;
1007
1008 data->collided = true;
1009
1010 /* Compute barycentric coordinates for both collision points. */
1012 verts1[vert_tri_a[0]].tx,
1013 verts1[vert_tri_a[1]].tx,
1014 verts1[vert_tri_a[2]].tx,
1015 &collpair[index].aw1,
1016 &collpair[index].aw2,
1017 &collpair[index].aw3);
1018
1020 collmd->current_xnew[vert_tri_b[0]],
1021 collmd->current_xnew[vert_tri_b[1]],
1022 collmd->current_xnew[vert_tri_b[2]],
1023 &collpair[index].bw1,
1024 &collpair[index].bw2,
1025 &collpair[index].bw3);
1026 }
1027 else {
1028 collpair[index].flag = COLLISION_INACTIVE;
1029 }
1030}
1031
1033 const Cloth *cloth,
1034 const int3 vert_tri_a,
1035 const int3 vert_tri_b)
1036{
1037 const ClothVertex *verts = cloth->verts;
1038
1039 /* Skip when either triangle is excluded. */
1040 const int flags_a = verts[vert_tri_a[0]].flags & verts[vert_tri_a[1]].flags &
1041 verts[vert_tri_a[2]].flags;
1042 const int flags_b = verts[vert_tri_b[0]].flags & verts[vert_tri_b[1]].flags &
1043 verts[vert_tri_b[2]].flags;
1044
1045 if ((flags_a | flags_b) & CLOTH_VERT_FLAG_NOSELFCOLL) {
1046 return false;
1047 }
1048
1049 /* Skip when both triangles are pinned. */
1050 if ((flags_a & flags_b) & CLOTH_VERT_FLAG_PINNED) {
1051 return false;
1052 }
1053
1054 /* Ignore overlap of neighboring triangles and triangles connected by a sewing edge. */
1055 bool sewing_active = (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SEW);
1056
1057 for (uint i = 0; i < 3; i++) {
1058 for (uint j = 0; j < 3; j++) {
1059 if (vert_tri_a[i] == vert_tri_b[j]) {
1060 return false;
1061 }
1062
1063 if (sewing_active) {
1064 if (cloth->sew_edge_graph.contains({vert_tri_a[i], vert_tri_b[j]})) {
1065 return false;
1066 }
1067 }
1068 }
1069 }
1070
1071 return true;
1072}
1073
1074static void cloth_selfcollision(void *__restrict userdata,
1075 const int index,
1076 const TaskParallelTLS *__restrict /*tls*/)
1077{
1078 SelfColDetectData *data = static_cast<SelfColDetectData *>(userdata);
1079
1080 ClothModifierData *clmd = data->clmd;
1081 CollPair *collpair = data->collisions;
1082 ClothVertex *verts1 = clmd->clothObject->verts;
1083 float distance = 0.0f;
1084 float epsilon = clmd->coll_parms->selfepsilon;
1085 float pa[3], pb[3], vect[3];
1086
1087 /* Collision math is currently not symmetric, so ensure a stable order for each pair. */
1088 int indexA = data->overlap[index].indexA, indexB = data->overlap[index].indexB;
1089
1090 if (indexA > indexB) {
1091 std::swap(indexA, indexB);
1092 }
1093
1094 const int3 vert_tri_a = clmd->clothObject->vert_tris[indexA];
1095 const int3 vert_tri_b = clmd->clothObject->vert_tris[indexB];
1096
1097 BLI_assert(cloth_bvh_selfcollision_is_active(clmd, clmd->clothObject, vert_tri_a, vert_tri_b));
1098
1099 /* Compute distance and normal. */
1100 distance = compute_collision_point_tri_tri(verts1[vert_tri_a[0]].tx,
1101 verts1[vert_tri_a[1]].tx,
1102 verts1[vert_tri_a[2]].tx,
1103 verts1[vert_tri_b[0]].tx,
1104 verts1[vert_tri_b[1]].tx,
1105 verts1[vert_tri_b[2]].tx,
1106 false,
1107 false,
1108 pa,
1109 pb,
1110 vect);
1111
1112 if ((distance <= (epsilon * 2.0f + ALMOST_ZERO)) && (len_squared_v3(vect) > ALMOST_ZERO)) {
1113 collpair[index].ap1 = vert_tri_a[0];
1114 collpair[index].ap2 = vert_tri_a[1];
1115 collpair[index].ap3 = vert_tri_a[2];
1116
1117 collpair[index].bp1 = vert_tri_b[0];
1118 collpair[index].bp2 = vert_tri_b[1];
1119 collpair[index].bp3 = vert_tri_b[2];
1120
1121 copy_v3_v3(collpair[index].pa, pa);
1122 copy_v3_v3(collpair[index].pb, pb);
1123 copy_v3_v3(collpair[index].vector, vect);
1124
1125 normalize_v3_v3(collpair[index].normal, collpair[index].vector);
1126
1127 collpair[index].distance = distance;
1128 collpair[index].flag = 0;
1129
1130 data->collided = true;
1131
1132 /* Compute barycentric coordinates for both collision points. */
1134 verts1[vert_tri_a[0]].tx,
1135 verts1[vert_tri_a[1]].tx,
1136 verts1[vert_tri_a[2]].tx,
1137 &collpair[index].aw1,
1138 &collpair[index].aw2,
1139 &collpair[index].aw3);
1140
1142 verts1[vert_tri_b[0]].tx,
1143 verts1[vert_tri_b[1]].tx,
1144 verts1[vert_tri_b[2]].tx,
1145 &collpair[index].bw1,
1146 &collpair[index].bw2,
1147 &collpair[index].bw3);
1148 }
1149 else {
1150 collpair[index].flag = COLLISION_INACTIVE;
1151 }
1152}
1153
1154static void hair_collision(void *__restrict userdata,
1155 const int index,
1156 const TaskParallelTLS *__restrict /*tls*/)
1157{
1158 ColDetectData *data = static_cast<ColDetectData *>(userdata);
1159
1160 ClothModifierData *clmd = data->clmd;
1161 CollisionModifierData *collmd = data->collmd;
1162 CollPair *collpair = data->collisions;
1163 ClothVertex *verts1 = clmd->clothObject->verts;
1164 float distance = 0.0f;
1165 float epsilon1 = clmd->coll_parms->epsilon;
1166 float epsilon2 = BLI_bvhtree_get_epsilon(collmd->bvhtree);
1167 float pa[3], pb[3], vect[3];
1168
1169 /* TODO: This is not efficient. Might be wise to instead build an array before iterating, to
1170 * avoid walking the list every time. */
1171 const int2 &edge_coll = reinterpret_cast<const int2 *>(
1172 clmd->clothObject->edges)[data->overlap[index].indexA];
1173 const int3 tri_coll = collmd->vert_tris[data->overlap[index].indexB];
1174
1175 /* Compute distance and normal. */
1176 distance = compute_collision_point_edge_tri(verts1[edge_coll[0]].tx,
1177 verts1[edge_coll[1]].tx,
1178 collmd->current_x[tri_coll[0]],
1179 collmd->current_x[tri_coll[1]],
1180 collmd->current_x[tri_coll[2]],
1181 data->culling,
1182 data->use_normal,
1183 pa,
1184 pb,
1185 vect);
1186
1187 if ((distance <= (epsilon1 + epsilon2 + ALMOST_ZERO)) && (len_squared_v3(vect) > ALMOST_ZERO)) {
1188 collpair[index].ap1 = edge_coll[0];
1189 collpair[index].ap2 = edge_coll[1];
1190
1191 collpair[index].bp1 = tri_coll[0];
1192 collpair[index].bp2 = tri_coll[1];
1193 collpair[index].bp3 = tri_coll[2];
1194
1195 copy_v3_v3(collpair[index].pa, pa);
1196 copy_v3_v3(collpair[index].pb, pb);
1197 copy_v3_v3(collpair[index].vector, vect);
1198
1199 normalize_v3_v3(collpair[index].normal, collpair[index].vector);
1200
1201 collpair[index].distance = distance;
1202 collpair[index].flag = 0;
1203
1204 data->collided = true;
1205
1206 /* Compute barycentric coordinates for the collision points. */
1207 collpair[index].aw2 = line_point_factor_v3(
1208 pa, verts1[edge_coll[0]].tx, verts1[edge_coll[1]].tx);
1209
1210 collpair[index].aw1 = 1.0f - collpair[index].aw2;
1211
1213 collmd->current_xnew[tri_coll[0]],
1214 collmd->current_xnew[tri_coll[1]],
1215 collmd->current_xnew[tri_coll[2]],
1216 &collpair[index].bw1,
1217 &collpair[index].bw2,
1218 &collpair[index].bw3);
1219 }
1220 else {
1221 collpair[index].flag = COLLISION_INACTIVE;
1222 }
1223}
1224
1225static void add_collision_object(ListBaseT<CollisionRelation> *relations,
1226 Object *ob,
1227 int level,
1228 const ModifierType modifier_type)
1229{
1230 /* only get objects with collision modifier */
1231 ModifierData *cmd = BKE_modifiers_findby_type(ob, modifier_type);
1232
1233 if (cmd) {
1235 relation->ob = ob;
1236 BLI_addtail(relations, relation);
1237 }
1238
1239 /* objects in dupli groups, one level only for now */
1240 /* TODO: this doesn't really work, we are not taking into account the
1241 * dupli transforms and can get objects in the list multiple times. */
1242 if (ob->instance_collection && level == 0) {
1243 Collection *collection = ob->instance_collection;
1244
1245 /* add objects */
1246 FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN (collection, object) {
1247 add_collision_object(relations, object, level + 1, modifier_type);
1248 }
1250 }
1251}
1252
1253ListBaseT<CollisionRelation> *BKE_collision_relations_create(Depsgraph *depsgraph,
1254 Collection *collection,
1255 uint modifier_type)
1256{
1257 const Scene *scene = DEG_get_input_scene(depsgraph);
1258 ViewLayer *view_layer = DEG_get_input_view_layer(depsgraph);
1260 *DEG_get_bmain(depsgraph), scene, view_layer, collection);
1261 const bool for_render = (DEG_get_mode(depsgraph) == DAG_EVAL_RENDER);
1262 const int base_flag = (for_render) ? BASE_ENABLED_RENDER : BASE_ENABLED_VIEWPORT;
1263
1264 ListBaseT<CollisionRelation> *relations = MEM_new_zeroed<ListBaseT<CollisionRelation>>(__func__);
1265
1266 for (; base; base = base->next) {
1267 if (base->flag & base_flag) {
1268 add_collision_object(relations, base->object, 0, ModifierType(modifier_type));
1269 }
1270 }
1271
1272 return relations;
1273}
1274
1275void BKE_collision_relations_free(ListBaseT<CollisionRelation> *relations)
1276{
1277 if (relations) {
1278 relations->free_no_destruct();
1279 MEM_delete(relations);
1280 }
1281}
1282
1284 Object *self,
1285 Collection *collection,
1286 uint *numcollobj,
1287 uint modifier_type)
1288{
1289 ListBaseT<CollisionRelation> *relations = DEG_get_collision_relations(
1290 depsgraph, collection, modifier_type);
1291
1292 if (!relations) {
1293 *numcollobj = 0;
1294 return nullptr;
1295 }
1296
1297 int maxnum = relations->count();
1298 int num = 0;
1299 Object **objects = MEM_new_array_zeroed<Object *>(maxnum, __func__);
1300
1301 for (CollisionRelation &relation : *relations) {
1302 /* Get evaluated object. */
1303 Object *ob = DEG_get_evaluated(depsgraph, relation.ob);
1304
1305 if (modifier_type == eModifierType_Collision && !(ob->pd && ob->pd->deflect)) {
1306 continue;
1307 }
1308
1309 if (ob != self) {
1310 objects[num] = ob;
1311 num++;
1312 }
1313 }
1314
1315 if (num == 0) {
1316 MEM_delete(objects);
1317 objects = nullptr;
1318 }
1319
1320 *numcollobj = num;
1321 return objects;
1322}
1323
1325{
1326 if (objects) {
1327 MEM_delete(objects);
1328 }
1329}
1330
1331ListBaseT<ColliderCache> *BKE_collider_cache_create(Depsgraph *depsgraph,
1332 Object *self,
1333 Collection *collection)
1334{
1335 ListBaseT<CollisionRelation> *relations = DEG_get_collision_relations(
1336 depsgraph, collection, eModifierType_Collision);
1337 ListBaseT<ColliderCache> *cache = nullptr;
1338
1339 if (!relations) {
1340 return nullptr;
1341 }
1342
1343 for (CollisionRelation &relation : *relations) {
1344 /* Get evaluated object. */
1345 Object *ob = DEG_get_evaluated(depsgraph, relation.ob);
1346
1347 if (ob == self) {
1348 continue;
1349 }
1350
1351 CollisionModifierData *cmd = reinterpret_cast<CollisionModifierData *>(
1353 if (cmd && cmd->bvhtree) {
1354 if (cache == nullptr) {
1355 cache = MEM_new_zeroed<ListBaseT<ColliderCache>>(__func__);
1356 }
1357
1359 col->ob = ob;
1360 col->collmd = cmd;
1361 /* make sure collider is properly set up */
1362 collision_move_object(cmd, 1.0, 0.0, true);
1363 BLI_addtail(cache, col);
1364 }
1365 }
1366
1367 return cache;
1368}
1369
1370void BKE_collider_cache_free(ListBaseT<ColliderCache> **colliders)
1371{
1372 if (*colliders) {
1373 BLI_freelistN(*colliders);
1374 MEM_delete(*colliders);
1375 *colliders = nullptr;
1376 }
1377}
1378
1380 CollisionModifierData *collmd,
1381 CollPair **collisions,
1382 int numresult,
1383 BVHTreeOverlap *overlap,
1384 bool culling,
1385 bool use_normal)
1386{
1387 const bool is_hair = (clmd->hairdata != nullptr);
1388 *collisions = MEM_new_array_uninitialized<CollPair>(size_t(numresult), "collision array");
1389
1391 data.clmd = clmd;
1392 data.collmd = collmd;
1393 data.overlap = overlap;
1394 data.collisions = *collisions;
1395 data.culling = culling;
1396 data.use_normal = use_normal;
1397 data.collided = false;
1398
1399 TaskParallelSettings settings;
1401 settings.use_threading = true;
1403 0, numresult, &data, is_hair ? hair_collision : cloth_collision, &settings);
1404
1405 return data.collided;
1406}
1407
1409 CollPair *collisions,
1410 int numresult,
1411 BVHTreeOverlap *overlap)
1412{
1414 data.clmd = clmd;
1415 data.overlap = overlap;
1416 data.collisions = collisions;
1417 data.collided = false;
1418
1419 TaskParallelSettings settings;
1421 settings.use_threading = true;
1422 BLI_task_parallel_range(0, numresult, &data, cloth_selfcollision, &settings);
1423
1424 return data.collided;
1425}
1426
1428 Object **collobjs,
1429 CollPair **collisions,
1430 uint *collision_counts,
1431 const uint numcollobj,
1432 const float dt)
1433{
1434 Cloth *cloth = clmd->clothObject;
1435 int i = 0, j = 0, mvert_num = 0;
1436 ClothVertex *verts = nullptr;
1437 int ret = 0;
1438 int result = 0;
1439
1440 mvert_num = clmd->clothObject->mvert_num;
1441 verts = cloth->verts;
1442
1443 result = 1;
1444
1445 for (j = 0; j < 2; j++) {
1446 result = 0;
1447
1448 for (i = 0; i < numcollobj; i++) {
1449 Object *collob = collobjs[i];
1450 CollisionModifierData *collmd = reinterpret_cast<CollisionModifierData *>(
1452
1453 if (collmd->bvhtree) {
1455 clmd, collmd, collob, collisions[i], collision_counts[i], dt);
1456 }
1457 }
1458
1459 /* Apply impulses in parallel. */
1460 if (result) {
1461 for (i = 0; i < mvert_num; i++) {
1462 /* Calculate "velocities" (just `xnew = xold + v`; no `dt` in `v`). */
1463 if (verts[i].impulse_count) {
1464 add_v3_v3(verts[i].tv, verts[i].impulse);
1465 add_v3_v3(verts[i].dcvel, verts[i].impulse);
1466 zero_v3(verts[i].impulse);
1467 verts[i].impulse_count = 0;
1468
1469 ret++;
1470 }
1471 }
1472 }
1473 else {
1474 break;
1475 }
1476 }
1477 return ret;
1478}
1479
1481 CollPair *collisions,
1482 int collision_count,
1483 const float dt)
1484{
1485 Cloth *cloth = clmd->clothObject;
1486 int i = 0, j = 0, mvert_num = 0;
1487 ClothVertex *verts = nullptr;
1488 int ret = 0;
1489 int result = 0;
1490
1491 mvert_num = clmd->clothObject->mvert_num;
1492 verts = cloth->verts;
1493
1494 for (j = 0; j < 2; j++) {
1495 result = 0;
1496
1497 result += cloth_selfcollision_response_static(clmd, collisions, collision_count, dt);
1498
1499 /* Apply impulses in parallel. */
1500 if (result) {
1501 for (i = 0; i < mvert_num; i++) {
1502 if (verts[i].impulse_count) {
1503 // VECADDMUL ( verts[i].tv, verts[i].impulse, 1.0f / verts[i].impulse_count );
1504 add_v3_v3(verts[i].tv, verts[i].impulse);
1505 add_v3_v3(verts[i].dcvel, verts[i].impulse);
1506 zero_v3(verts[i].impulse);
1507 verts[i].impulse_count = 0;
1508
1509 ret++;
1510 }
1511 }
1512 }
1513
1514 if (!result) {
1515 break;
1516 }
1517 }
1518 return ret;
1519}
1520
1521static bool cloth_bvh_obj_overlap_cb(void *userdata, int index_a, int /*index_b*/, int /*thread*/)
1522{
1523 ClothModifierData *clmd = static_cast<ClothModifierData *>(userdata);
1524 Cloth *clothObject = clmd->clothObject;
1525 const int3 tri_a = clothObject->vert_tris[index_a];
1526
1527 return cloth_bvh_collision_is_active(clmd, clothObject, tri_a);
1528}
1529
1530static bool cloth_bvh_self_overlap_cb(void *userdata, int index_a, int index_b, int /*thread*/)
1531{
1532 /* This shouldn't happen, but just in case. Note that equal combinations
1533 * (eg. (0,1) & (1,0)) would be filtered out by BLI_bvhtree_overlap_self. */
1534 if (index_a != index_b) {
1535 ClothModifierData *clmd = static_cast<ClothModifierData *>(userdata);
1536 Cloth *clothObject = clmd->clothObject;
1537 const int3 tri_a = clothObject->vert_tris[index_a];
1538 const int3 tri_b = clothObject->vert_tris[index_b];
1539
1540 if (cloth_bvh_selfcollision_is_active(clmd, clothObject, tri_a, tri_b)) {
1541 return true;
1542 }
1543 }
1544 return false;
1545}
1546
1548 Depsgraph *depsgraph, Object *ob, ClothModifierData *clmd, float step, float dt)
1549{
1550 Cloth *cloth = clmd->clothObject;
1551 BVHTree *cloth_bvh = cloth->bvhtree;
1552 uint i = 0, mvert_num = 0;
1553 int rounds = 0;
1554 ClothVertex *verts = nullptr;
1555 int ret = 0, ret2 = 0;
1556 Object **collobjs = nullptr;
1557 uint numcollobj = 0;
1558 uint *coll_counts_obj = nullptr;
1559 BVHTreeOverlap **overlap_obj = nullptr;
1560 uint coll_count_self = 0;
1561 BVHTreeOverlap *overlap_self = nullptr;
1562 bool bvh_updated = false;
1563
1564 if ((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_COLLOBJ) || cloth_bvh == nullptr) {
1565 return 0;
1566 }
1567
1568 verts = cloth->verts;
1569 mvert_num = cloth->mvert_num;
1570
1572 bvhtree_update_from_cloth(clmd, false, false);
1573 bvh_updated = true;
1574
1575 /* Enable self collision if this is a hair sim */
1576 const bool is_hair = (clmd->hairdata != nullptr);
1577
1578 collobjs = BKE_collision_objects_create(depsgraph,
1579 is_hair ? nullptr : ob,
1580 clmd->coll_parms->group,
1581 &numcollobj,
1583
1584 if (collobjs) {
1585 coll_counts_obj = MEM_new_array_zeroed<uint>(numcollobj, "CollCounts");
1586 overlap_obj = MEM_new_array_zeroed<BVHTreeOverlap *>(numcollobj, "BVHOverlap");
1587
1588 for (i = 0; i < numcollobj; i++) {
1589 Object *collob = collobjs[i];
1590 CollisionModifierData *collmd = reinterpret_cast<CollisionModifierData *>(
1592
1593 if (!collmd->bvhtree) {
1594 continue;
1595 }
1596
1597 /* Move object to position (step) in time. */
1598 collision_move_object(collmd, step + dt, step, false);
1599
1600 overlap_obj[i] = BLI_bvhtree_overlap(cloth_bvh,
1601 collmd->bvhtree,
1602 &coll_counts_obj[i],
1603 is_hair ? nullptr : cloth_bvh_obj_overlap_cb,
1604 clmd);
1605 }
1606 }
1607 }
1608
1610 if (cloth->bvhselftree != cloth->bvhtree || !bvh_updated) {
1611 bvhtree_update_from_cloth(clmd, false, true);
1612 }
1613
1614 overlap_self = BLI_bvhtree_overlap_self(
1615 cloth->bvhselftree, &coll_count_self, cloth_bvh_self_overlap_cb, clmd);
1616 }
1617
1618 do {
1619 ret2 = 0;
1620
1621 /* Object collisions. */
1622 if ((clmd->coll_parms->flags & CLOTH_COLLSETTINGS_FLAG_ENABLED) && collobjs) {
1623 CollPair **collisions;
1624 bool collided = false;
1625
1626 collisions = MEM_new_array_zeroed<CollPair *>(numcollobj, "CollPair");
1627
1628 for (i = 0; i < numcollobj; i++) {
1629 Object *collob = collobjs[i];
1630 CollisionModifierData *collmd = reinterpret_cast<CollisionModifierData *>(
1632
1633 if (!collmd->bvhtree) {
1634 continue;
1635 }
1636
1637 if (coll_counts_obj[i] && overlap_obj[i]) {
1639 clmd,
1640 collmd,
1641 &collisions[i],
1642 coll_counts_obj[i],
1643 overlap_obj[i],
1644 (collob->pd->flag & PFIELD_CLOTH_USE_CULLING),
1645 (collob->pd->flag & PFIELD_CLOTH_USE_NORMAL)) ||
1646 collided;
1647 }
1648 }
1649
1650 if (collided) {
1652 clmd, collobjs, collisions, coll_counts_obj, numcollobj, dt);
1653 ret2 += ret;
1654 }
1655
1656 for (i = 0; i < numcollobj; i++) {
1657 MEM_SAFE_DELETE(collisions[i]);
1658 }
1659
1660 MEM_delete(collisions);
1661 }
1662
1663 /* Self collisions. */
1665 CollPair *collisions = nullptr;
1666
1667 verts = cloth->verts;
1668 mvert_num = cloth->mvert_num;
1669
1670 if (cloth->bvhselftree) {
1671 if (coll_count_self && overlap_self) {
1672 collisions = MEM_new_array_uninitialized<CollPair>(coll_count_self, "collision array");
1673
1674 if (cloth_bvh_selfcollisions_nearcheck(clmd, collisions, coll_count_self, overlap_self))
1675 {
1676 ret += cloth_bvh_selfcollisions_resolve(clmd, collisions, coll_count_self, dt);
1677 ret2 += ret;
1678 }
1679 }
1680 }
1681
1682 MEM_SAFE_DELETE(collisions);
1683 }
1684
1685 /* Apply all collision resolution. */
1686 if (ret2) {
1687 for (i = 0; i < mvert_num; i++) {
1688 if (clmd->sim_parms->vgroup_mass > 0) {
1689 if (verts[i].flags & CLOTH_VERT_FLAG_PINNED) {
1690 continue;
1691 }
1692 }
1693
1694 add_v3_v3v3(verts[i].tx, verts[i].txold, verts[i].tv);
1695 }
1696 }
1697
1698 rounds++;
1699 } while (ret2 && (clmd->coll_parms->loop_count > rounds));
1700
1701 if (overlap_obj) {
1702 for (i = 0; i < numcollobj; i++) {
1703 MEM_SAFE_DELETE(overlap_obj[i]);
1704 }
1705
1706 MEM_delete(overlap_obj);
1707 }
1708
1709 MEM_SAFE_DELETE(coll_counts_obj);
1710
1711 MEM_SAFE_DELETE(overlap_self);
1712
1714
1715 return std::min(ret, 1);
1716}
1717
1718BLI_INLINE void max_v3_v3v3(float r[3], const float a[3], const float b[3])
1719{
1720 r[0] = max_ff(a[0], b[0]);
1721 r[1] = max_ff(a[1], b[1]);
1722 r[2] = max_ff(a[2], b[2]);
1723}
1724
1726 float vel_new[3],
1727 CollisionModifierData *collmd,
1728 CollPair *collpair)
1729{
1730 float u1, u2, u3;
1731
1732 /* compute barycentric coordinates */
1734 collmd->current_x[collpair->bp1],
1735 collmd->current_x[collpair->bp2],
1736 collmd->current_x[collpair->bp3],
1737 &u1,
1738 &u2,
1739 &u3);
1740
1742 collmd->current_v[collpair->bp1],
1743 collmd->current_v[collpair->bp2],
1744 collmd->current_v[collpair->bp3],
1745 u1,
1746 u2,
1747 u3);
1748 /* XXX assume constant velocity of the collider for now */
1749 copy_v3_v3(vel_old, vel_new);
1750}
1751
1752} // namespace blender
#define DO_INLINE
Definition BKE_cloth.hh:29
#define VECADDMUL(v1, v2, aS)
Definition BKE_cloth.hh:178
#define ALMOST_ZERO
Definition BKE_cloth.hh:36
#define FOREACH_COLLECTION_OBJECT_RECURSIVE_END
#define FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN(_collection, _object)
Object is a sort of wrapper for general info.
Read Blender memory allocation and freeing.
#define BLI_INLINE
#define INPR(v1, v2)
#define FLT_MAX
float distance(float, float) RET
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
ccl_device_inline dual3 fabs(const ccl_private dual3 &a)
Definition math_dual.h:241
BMesh Iterators.
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)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
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])
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
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])
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
static float compute_collision_point_edge_tri(const float a1[3], const float a2[3], const float b1[3], const float b2[3], const float b3[3], bool culling, bool use_normal, float r_a[3], float r_b[3], float r_vec[3])
Definition collision.cc:382
void BKE_collider_cache_free(ListBaseT< ColliderCache > **colliders)
float BLI_bvhtree_get_epsilon(const BVHTree *tree)
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
static void hair_collision(void *__restrict userdata, const int index, const TaskParallelTLS *__restrict)
void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3])
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)
@ BASE_ENABLED_VIEWPORT
static bool cloth_bvh_selfcollision_is_active(const ClothModifierData *clmd, const Cloth *cloth, const int3 vert_tri_a, const int3 vert_tri_b)
void collision_move_object(struct CollisionModifierData *collmd, float step, float prevstep, bool moving_bvh)
Definition collision.cc:62
void BLI_bvhtree_balance(BVHTree *tree)
static void collision_compute_barycentric(const float pv[3], const float p1[3], const float p2[3], const float p3[3], float *w1, float *w2, float *w3)
Definition collision.cc:557
void BLI_task_parallel_range(int start, int stop, void *userdata, TaskParallelRangeFunc func, const TaskParallelSettings *settings)
@ COLLISION_IN_FUTURE
@ COLLISION_INACTIVE
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
static bool cloth_bvh_obj_overlap_cb(void *userdata, int index_a, int, int)
void BKE_collision_relations_free(ListBaseT< CollisionRelation > *relations)
bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
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 collision_get_collider_velocity(float vel_old[3], float vel_new[3], struct CollisionModifierData *collmd, struct CollPair *collpair)
MINLINE void mul_v3_fl(float r[3], float f)
static int cloth_bvh_objcollisions_resolve(ClothModifierData *clmd, Object **collobjs, CollPair **collisions, uint *collision_counts, const uint numcollobj, const float dt)
BLI_INLINE int next_ind(int i)
Definition collision.cc:165
void BLI_bvhtree_update_tree(BVHTree *tree)
static bool cloth_bvh_selfcollisions_nearcheck(ClothModifierData *clmd, CollPair *collisions, int numresult, BVHTreeOverlap *overlap)
ViewLayer * DEG_get_input_view_layer(const Depsgraph *graph)
VecBase< int32_t, 2 > int2
struct BVHTree * bvhtree_build_from_mvert(const float(*positions)[3], const int3 *vert_tris, int tri_num, float epsilon)
Definition collision.cc:92
VecBase< int32_t, 3 > int3
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
void void BLI_freelistN(ListBase *listbase) ATTR_NONNULL(1)
Definition listbase.cc:504
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
ListBaseT< ColliderCache > * BKE_collider_cache_create(struct Depsgraph *depsgraph, struct Object *self, struct Collection *collection)
Main * DEG_get_bmain(const Depsgraph *graph)
BMesh const char void * data
static bool cloth_bvh_objcollisions_nearcheck(ClothModifierData *clmd, CollisionModifierData *collmd, CollPair **collisions, int numresult, BVHTreeOverlap *overlap, bool culling, bool use_normal)
T * DEG_get_evaluated(const Depsgraph *depsgraph, T *id)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
Base * BKE_collection_or_layer_objects(const Main &bmain, const Scene *scene, ViewLayer *view_layer, Collection *collection)
MINLINE void negate_v3(float r[3])
static void cloth_selfcollision(void *__restrict userdata, const int index, const TaskParallelTLS *__restrict)
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
ATTR_WARN_UNUSED_RESULT const size_t num
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
static int cloth_bvh_selfcollisions_resolve(ClothModifierData *clmd, CollPair *collisions, int collision_count, const float dt)
BVHTreeOverlap * BLI_bvhtree_overlap_self(const BVHTree *tree, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
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 zero_v3(float r[3])
eEvaluationMode DEG_get_mode(const Depsgraph *graph)
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
int cloth_bvh_collision(Depsgraph *depsgraph, Object *ob, ClothModifierData *clmd, float step, float dt)
void bvhtree_update_from_cloth(ClothModifierData *clmd, bool moving, bool self)
Definition cloth.cc:123
MINLINE float normalize_v3_v3(float r[3], const float a[3])
MINLINE float normalize_v3(float n[3])
ModifierData * BKE_modifiers_findby_type(const Object *ob, ModifierType type)
MINLINE void add_v3_v3(float r[3], const float a[3])
@ CLOTH_SIMSETTINGS_FLAG_COLLOBJ
@ CLOTH_SIMSETTINGS_FLAG_SEW
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
BLI_INLINE void max_v3_v3v3(float r[3], const float a[3], const float b[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE void sub_v3db_v3fl_v3fl(double r[3], const float a[3], const float b[3])
struct Object ** BKE_collision_objects_create(struct Depsgraph *depsgraph, struct Object *self, struct Collection *collection, unsigned int *numcollobj, unsigned int modifier_type)
ListBaseT< CollisionRelation > * DEG_get_collision_relations(const Depsgraph *depsgraph, Collection *collection, unsigned int modifier_type)
void bvhtree_update_from_mvert(struct BVHTree *bvhtree, const float(*positions)[3], const float(*positions_moving)[3], const int3 *vert_tris, int tri_num, bool moving)
Definition collision.cc:116
MINLINE float max_ff(float a, float b)
float closest_to_line_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
DO_INLINE void collision_interpolateOnTriangle(float to[3], const float v1[3], const float v2[3], const float v3[3], const double w1, const double w2, const double w3)
Definition collision.cc:604
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])
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
Scene * DEG_get_input_scene(const Depsgraph *graph)
ListBaseT< CollisionRelation > * BKE_collision_relations_create(struct Depsgraph *depsgraph, struct Collection *collection, unsigned int modifier_type)
@ CLOTH_VERT_FLAG_NOSELFCOLL
Definition BKE_cloth.hh:41
@ CLOTH_VERT_FLAG_NOOBJCOLL
Definition BKE_cloth.hh:42
@ CLOTH_VERT_FLAG_PINNED
Definition BKE_cloth.hh:40
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
MINLINE float square_f(float a)
static void cloth_collision(void *__restrict userdata, const int index, const TaskParallelTLS *__restrict)
Definition collision.cc:959
static int cloth_collision_response_static(ClothModifierData *clmd, CollisionModifierData *collmd, Object *collob, CollPair *collpair, uint collision_count, const float dt)
Definition collision.cc:643
static void add_collision_object(ListBaseT< CollisionRelation > *relations, Object *ob, int level, const ModifierType modifier_type)
static float compute_collision_point_tri_tri(const float a1[3], const float a2[3], const float a3[3], const float b1[3], const float b2[3], const float b3[3], bool culling, bool use_normal, float r_a[3], float r_b[3], float r_vec[3])
Definition collision.cc:170
@ CLOTH_COLLSETTINGS_FLAG_ENABLED
@ CLOTH_COLLSETTINGS_FLAG_SELF
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BKE_collision_objects_free(struct Object **objects)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
static bool cloth_bvh_self_overlap_cb(void *userdata, int index_a, int index_b, int)
static void cloth_collision_impulse_vert(const float clamp_sq, const float impulse[3], ClothVertex *vert)
Definition collision.cc:618
static int cloth_selfcollision_response_static(ClothModifierData *clmd, CollPair *collpair, uint collision_count, const float dt)
Definition collision.cc:791
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static bool cloth_bvh_collision_is_active(const ClothModifierData *, const Cloth *cloth, const int3 vert_tri_a)
Definition collision.cc:942
#define fabsf
#define sqrtf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct Object * object
struct Base * next
CLOTH_COLLISIONSETTINGS_FLAGS flags
struct Collection * group
struct ClothHairData * hairdata
struct ClothSimSettings * sim_parms
struct ClothCollSettings * coll_parms
CLOTH_SIMSETTINGS_FLAGS flags
unsigned int impulse_count
Definition BKE_cloth.hh:108
unsigned int mvert_num
Definition BKE_cloth.hh:74
const int2 * edges
Definition BKE_cloth.hh:87
ClothVertex * verts
Definition BKE_cloth.hh:71
int3 * vert_tris
Definition BKE_cloth.hh:81
CollisionModifierData * collmd
Definition collision.cc:43
ClothModifierData * clmd
Definition collision.cc:42
BVHTreeOverlap * overlap
Definition collision.cc:44
struct CollisionModifierData * collmd
struct PartDeflect * pd
struct Collection * instance_collection
BVHTreeOverlap * overlap
Definition collision.cc:53
ClothModifierData * clmd
Definition collision.cc:52