1 /*
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2011-2014, Willow Garage, Inc.
5 * Copyright (c) 2014-2016, Open Source Robotics Foundation
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * * Redistributions in binary form must reproduce the above
15 * copyright notice, this list of conditions and the following
16 * disclaimer in the documentation and/or other materials provided
17 * with the distribution.
18 * * Neither the name of Open Source Robotics Foundation nor the names of its
19 * contributors may be used to endorse or promote products derived
20 * from this software without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 /** \author Jia Pan */
37
38
39 #include "fcl/traversal/traversal_node_bvhs.h"
40
41 namespace fcl
42 {
43
44 namespace details
45 {
46 template<typename BV>
meshCollisionOrientedNodeLeafTesting(int b1,int b2,const BVHModel<BV> * model1,const BVHModel<BV> * model2,Vec3f * vertices1,Vec3f * vertices2,Triangle * tri_indices1,Triangle * tri_indices2,const Matrix3f & R,const Vec3f & T,const Transform3f & tf1,const Transform3f & tf2,bool enable_statistics,FCL_REAL cost_density,int & num_leaf_tests,const CollisionRequest & request,CollisionResult & result)47 static inline void meshCollisionOrientedNodeLeafTesting(int b1, int b2,
48 const BVHModel<BV>* model1, const BVHModel<BV>* model2,
49 Vec3f* vertices1, Vec3f* vertices2,
50 Triangle* tri_indices1, Triangle* tri_indices2,
51 const Matrix3f& R, const Vec3f& T,
52 const Transform3f& tf1, const Transform3f& tf2,
53 bool enable_statistics,
54 FCL_REAL cost_density,
55 int& num_leaf_tests,
56 const CollisionRequest& request,
57 CollisionResult& result)
58 {
59 if(enable_statistics) num_leaf_tests++;
60
61 const BVNode<BV>& node1 = model1->getBV(b1);
62 const BVNode<BV>& node2 = model2->getBV(b2);
63
64 int primitive_id1 = node1.primitiveId();
65 int primitive_id2 = node2.primitiveId();
66
67 const Triangle& tri_id1 = tri_indices1[primitive_id1];
68 const Triangle& tri_id2 = tri_indices2[primitive_id2];
69
70 const Vec3f& p1 = vertices1[tri_id1[0]];
71 const Vec3f& p2 = vertices1[tri_id1[1]];
72 const Vec3f& p3 = vertices1[tri_id1[2]];
73 const Vec3f& q1 = vertices2[tri_id2[0]];
74 const Vec3f& q2 = vertices2[tri_id2[1]];
75 const Vec3f& q3 = vertices2[tri_id2[2]];
76
77 if(model1->isOccupied() && model2->isOccupied())
78 {
79 bool is_intersect = false;
80
81 if(!request.enable_contact) // only interested in collision or not
82 {
83 if(Intersect::intersect_Triangle(p1, p2, p3, q1, q2, q3, R, T))
84 {
85 is_intersect = true;
86 if(result.numContacts() < request.num_max_contacts)
87 result.addContact(Contact(model1, model2, primitive_id1, primitive_id2));
88 }
89 }
90 else // need compute the contact information
91 {
92 FCL_REAL penetration;
93 Vec3f normal;
94 unsigned int n_contacts;
95 Vec3f contacts[2];
96
97 if(Intersect::intersect_Triangle(p1, p2, p3, q1, q2, q3,
98 R, T,
99 contacts,
100 &n_contacts,
101 &penetration,
102 &normal))
103 {
104 is_intersect = true;
105
106 if(request.num_max_contacts < result.numContacts() + n_contacts)
107 n_contacts = (request.num_max_contacts > result.numContacts()) ? (request.num_max_contacts - result.numContacts()) : 0;
108
109 for(unsigned int i = 0; i < n_contacts; ++i)
110 {
111 result.addContact(Contact(model1, model2, primitive_id1, primitive_id2, tf1.transform(contacts[i]), tf1.getQuatRotation().transform(normal), penetration));
112 }
113 }
114 }
115
116 if(is_intersect && request.enable_cost)
117 {
118 AABB overlap_part;
119 AABB(tf1.transform(p1), tf1.transform(p2), tf1.transform(p3)).overlap(AABB(tf2.transform(q1), tf2.transform(q2), tf2.transform(q3)), overlap_part);
120 result.addCostSource(CostSource(overlap_part, cost_density), request.num_max_cost_sources);
121 }
122 }
123 else if((!model1->isFree() && !model2->isFree()) && request.enable_cost)
124 {
125 if(Intersect::intersect_Triangle(p1, p2, p3, q1, q2, q3, R, T))
126 {
127 AABB overlap_part;
128 AABB(tf1.transform(p1), tf1.transform(p2), tf1.transform(p3)).overlap(AABB(tf2.transform(q1), tf2.transform(q2), tf2.transform(q3)), overlap_part);
129 result.addCostSource(CostSource(overlap_part, cost_density), request.num_max_cost_sources);
130 }
131 }
132 }
133
134
135
136
137 template<typename BV>
meshDistanceOrientedNodeLeafTesting(int b1,int b2,const BVHModel<BV> * model1,const BVHModel<BV> * model2,Vec3f * vertices1,Vec3f * vertices2,Triangle * tri_indices1,Triangle * tri_indices2,const Matrix3f & R,const Vec3f & T,bool enable_statistics,int & num_leaf_tests,const DistanceRequest & request,DistanceResult & result)138 static inline void meshDistanceOrientedNodeLeafTesting(int b1, int b2,
139 const BVHModel<BV>* model1, const BVHModel<BV>* model2,
140 Vec3f* vertices1, Vec3f* vertices2,
141 Triangle* tri_indices1, Triangle* tri_indices2,
142 const Matrix3f& R, const Vec3f& T,
143 bool enable_statistics,
144 int& num_leaf_tests,
145 const DistanceRequest& request,
146 DistanceResult& result)
147 {
148 if(enable_statistics) num_leaf_tests++;
149
150 const BVNode<BV>& node1 = model1->getBV(b1);
151 const BVNode<BV>& node2 = model2->getBV(b2);
152
153 int primitive_id1 = node1.primitiveId();
154 int primitive_id2 = node2.primitiveId();
155
156 const Triangle& tri_id1 = tri_indices1[primitive_id1];
157 const Triangle& tri_id2 = tri_indices2[primitive_id2];
158
159 const Vec3f& t11 = vertices1[tri_id1[0]];
160 const Vec3f& t12 = vertices1[tri_id1[1]];
161 const Vec3f& t13 = vertices1[tri_id1[2]];
162
163 const Vec3f& t21 = vertices2[tri_id2[0]];
164 const Vec3f& t22 = vertices2[tri_id2[1]];
165 const Vec3f& t23 = vertices2[tri_id2[2]];
166
167 // nearest point pair
168 Vec3f P1, P2;
169
170 FCL_REAL d = TriangleDistance::triDistance(t11, t12, t13, t21, t22, t23,
171 R, T,
172 P1, P2);
173
174 if(request.enable_nearest_points)
175 result.update(d, model1, model2, primitive_id1, primitive_id2, P1, P2);
176 else
177 result.update(d, model1, model2, primitive_id1, primitive_id2);
178 }
179
180 }
181
MeshCollisionTraversalNodeOBB()182 MeshCollisionTraversalNodeOBB::MeshCollisionTraversalNodeOBB() : MeshCollisionTraversalNode<OBB>()
183 {
184 R.setIdentity();
185 }
186
BVTesting(int b1,int b2) const187 bool MeshCollisionTraversalNodeOBB::BVTesting(int b1, int b2) const
188 {
189 if(enable_statistics) num_bv_tests++;
190 return !overlap(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv);
191 }
192
leafTesting(int b1,int b2) const193 void MeshCollisionTraversalNodeOBB::leafTesting(int b1, int b2) const
194 {
195 details::meshCollisionOrientedNodeLeafTesting(b1, b2, model1, model2, vertices1, vertices2,
196 tri_indices1, tri_indices2,
197 R, T,
198 tf1, tf2,
199 enable_statistics, cost_density,
200 num_leaf_tests,
201 request, *result);
202 }
203
204
BVTesting(int b1,int b2,const Matrix3f & Rc,const Vec3f & Tc) const205 bool MeshCollisionTraversalNodeOBB::BVTesting(int b1, int b2, const Matrix3f& Rc, const Vec3f& Tc) const
206 {
207 if(enable_statistics) num_bv_tests++;
208 return obbDisjoint(Rc, Tc, model1->getBV(b1).bv.extent, model2->getBV(b2).bv.extent);
209 }
210
leafTesting(int b1,int b2,const Matrix3f & Rc,const Vec3f & Tc) const211 void MeshCollisionTraversalNodeOBB::leafTesting(int b1, int b2, const Matrix3f& Rc, const Vec3f& Tc) const
212 {
213 details::meshCollisionOrientedNodeLeafTesting(b1, b2, model1, model2, vertices1, vertices2,
214 tri_indices1, tri_indices2,
215 R, T,
216 tf1, tf2,
217 enable_statistics, cost_density,
218 num_leaf_tests,
219 request, *result);
220 }
221
222
223
MeshCollisionTraversalNodeRSS()224 MeshCollisionTraversalNodeRSS::MeshCollisionTraversalNodeRSS() : MeshCollisionTraversalNode<RSS>()
225 {
226 R.setIdentity();
227 }
228
BVTesting(int b1,int b2) const229 bool MeshCollisionTraversalNodeRSS::BVTesting(int b1, int b2) const
230 {
231 if(enable_statistics) num_bv_tests++;
232 return !overlap(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv);
233 }
234
leafTesting(int b1,int b2) const235 void MeshCollisionTraversalNodeRSS::leafTesting(int b1, int b2) const
236 {
237 details::meshCollisionOrientedNodeLeafTesting(b1, b2, model1, model2, vertices1, vertices2,
238 tri_indices1, tri_indices2,
239 R, T,
240 tf1, tf2,
241 enable_statistics, cost_density,
242 num_leaf_tests,
243 request, *result);
244 }
245
246
247
248
MeshCollisionTraversalNodekIOS()249 MeshCollisionTraversalNodekIOS::MeshCollisionTraversalNodekIOS() : MeshCollisionTraversalNode<kIOS>()
250 {
251 R.setIdentity();
252 }
253
BVTesting(int b1,int b2) const254 bool MeshCollisionTraversalNodekIOS::BVTesting(int b1, int b2) const
255 {
256 if(enable_statistics) num_bv_tests++;
257 return !overlap(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv);
258 }
259
leafTesting(int b1,int b2) const260 void MeshCollisionTraversalNodekIOS::leafTesting(int b1, int b2) const
261 {
262 details::meshCollisionOrientedNodeLeafTesting(b1, b2, model1, model2, vertices1, vertices2,
263 tri_indices1, tri_indices2,
264 R, T,
265 tf1, tf2,
266 enable_statistics, cost_density,
267 num_leaf_tests,
268 request, *result);
269 }
270
271
272
MeshCollisionTraversalNodeOBBRSS()273 MeshCollisionTraversalNodeOBBRSS::MeshCollisionTraversalNodeOBBRSS() : MeshCollisionTraversalNode<OBBRSS>()
274 {
275 R.setIdentity();
276 }
277
BVTesting(int b1,int b2) const278 bool MeshCollisionTraversalNodeOBBRSS::BVTesting(int b1, int b2) const
279 {
280 if(enable_statistics) num_bv_tests++;
281 return !overlap(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv);
282 }
283
leafTesting(int b1,int b2) const284 void MeshCollisionTraversalNodeOBBRSS::leafTesting(int b1, int b2) const
285 {
286 details::meshCollisionOrientedNodeLeafTesting(b1, b2, model1, model2, vertices1, vertices2,
287 tri_indices1, tri_indices2,
288 R, T,
289 tf1, tf2,
290 enable_statistics, cost_density,
291 num_leaf_tests,
292 request,*result);
293 }
294
295
296 namespace details
297 {
298
299 template<typename BV>
distancePreprocessOrientedNode(const BVHModel<BV> * model1,const BVHModel<BV> * model2,const Vec3f * vertices1,Vec3f * vertices2,Triangle * tri_indices1,Triangle * tri_indices2,int init_tri_id1,int init_tri_id2,const Matrix3f & R,const Vec3f & T,const DistanceRequest & request,DistanceResult & result)300 static inline void distancePreprocessOrientedNode(const BVHModel<BV>* model1, const BVHModel<BV>* model2,
301 const Vec3f* vertices1, Vec3f* vertices2,
302 Triangle* tri_indices1, Triangle* tri_indices2,
303 int init_tri_id1, int init_tri_id2,
304 const Matrix3f& R, const Vec3f& T,
305 const DistanceRequest& request,
306 DistanceResult& result)
307 {
308 const Triangle& init_tri1 = tri_indices1[init_tri_id1];
309 const Triangle& init_tri2 = tri_indices2[init_tri_id2];
310
311 Vec3f init_tri1_points[3];
312 Vec3f init_tri2_points[3];
313
314 init_tri1_points[0] = vertices1[init_tri1[0]];
315 init_tri1_points[1] = vertices1[init_tri1[1]];
316 init_tri1_points[2] = vertices1[init_tri1[2]];
317
318 init_tri2_points[0] = vertices2[init_tri2[0]];
319 init_tri2_points[1] = vertices2[init_tri2[1]];
320 init_tri2_points[2] = vertices2[init_tri2[2]];
321
322 Vec3f p1, p2;
323 FCL_REAL distance = TriangleDistance::triDistance(init_tri1_points[0], init_tri1_points[1], init_tri1_points[2],
324 init_tri2_points[0], init_tri2_points[1], init_tri2_points[2],
325 R, T, p1, p2);
326
327 if(request.enable_nearest_points)
328 result.update(distance, model1, model2, init_tri_id1, init_tri_id2, p1, p2);
329 else
330 result.update(distance, model1, model2, init_tri_id1, init_tri_id2);
331 }
332
333 template<typename BV>
distancePostprocessOrientedNode(const BVHModel<BV> * model1,const BVHModel<BV> * model2,const Transform3f & tf1,const DistanceRequest & request,DistanceResult & result)334 static inline void distancePostprocessOrientedNode(const BVHModel<BV>* model1, const BVHModel<BV>* model2,
335 const Transform3f& tf1, const DistanceRequest& request, DistanceResult& result)
336 {
337 /// the points obtained by triDistance are not in world space: both are in object1's local coordinate system, so we need to convert them into the world space.
338 if(request.enable_nearest_points && (result.o1 == model1) && (result.o2 == model2))
339 {
340 result.nearest_points[0] = tf1.transform(result.nearest_points[0]);
341 result.nearest_points[1] = tf1.transform(result.nearest_points[1]);
342 }
343 }
344
345 }
346
MeshDistanceTraversalNodeRSS()347 MeshDistanceTraversalNodeRSS::MeshDistanceTraversalNodeRSS() : MeshDistanceTraversalNode<RSS>()
348 {
349 R.setIdentity();
350 }
351
preprocess()352 void MeshDistanceTraversalNodeRSS::preprocess()
353 {
354 details::distancePreprocessOrientedNode(model1, model2, vertices1, vertices2, tri_indices1, tri_indices2, 0, 0, R, T, request, *result);
355 }
356
postprocess()357 void MeshDistanceTraversalNodeRSS::postprocess()
358 {
359 details::distancePostprocessOrientedNode(model1, model2, tf1, request, *result);
360 }
361
BVTesting(int b1,int b2) const362 FCL_REAL MeshDistanceTraversalNodeRSS::BVTesting(int b1, int b2) const
363 {
364 if(enable_statistics) num_bv_tests++;
365 return distance(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv);
366 }
367
leafTesting(int b1,int b2) const368 void MeshDistanceTraversalNodeRSS::leafTesting(int b1, int b2) const
369 {
370 details::meshDistanceOrientedNodeLeafTesting(b1, b2, model1, model2, vertices1, vertices2, tri_indices1, tri_indices2,
371 R, T, enable_statistics, num_leaf_tests,
372 request, *result);
373 }
374
MeshDistanceTraversalNodekIOS()375 MeshDistanceTraversalNodekIOS::MeshDistanceTraversalNodekIOS() : MeshDistanceTraversalNode<kIOS>()
376 {
377 R.setIdentity();
378 }
379
preprocess()380 void MeshDistanceTraversalNodekIOS::preprocess()
381 {
382 details::distancePreprocessOrientedNode(model1, model2, vertices1, vertices2, tri_indices1, tri_indices2, 0, 0, R, T, request, *result);
383 }
384
postprocess()385 void MeshDistanceTraversalNodekIOS::postprocess()
386 {
387 details::distancePostprocessOrientedNode(model1, model2, tf1, request, *result);
388 }
389
BVTesting(int b1,int b2) const390 FCL_REAL MeshDistanceTraversalNodekIOS::BVTesting(int b1, int b2) const
391 {
392 if(enable_statistics) num_bv_tests++;
393 return distance(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv);
394 }
395
leafTesting(int b1,int b2) const396 void MeshDistanceTraversalNodekIOS::leafTesting(int b1, int b2) const
397 {
398 details::meshDistanceOrientedNodeLeafTesting(b1, b2, model1, model2, vertices1, vertices2, tri_indices1, tri_indices2,
399 R, T, enable_statistics, num_leaf_tests,
400 request, *result);
401 }
402
MeshDistanceTraversalNodeOBBRSS()403 MeshDistanceTraversalNodeOBBRSS::MeshDistanceTraversalNodeOBBRSS() : MeshDistanceTraversalNode<OBBRSS>()
404 {
405 R.setIdentity();
406 }
407
preprocess()408 void MeshDistanceTraversalNodeOBBRSS::preprocess()
409 {
410 details::distancePreprocessOrientedNode(model1, model2, vertices1, vertices2, tri_indices1, tri_indices2, 0, 0, R, T, request, *result);
411 }
412
postprocess()413 void MeshDistanceTraversalNodeOBBRSS::postprocess()
414 {
415 details::distancePostprocessOrientedNode(model1, model2, tf1, request, *result);
416 }
417
BVTesting(int b1,int b2) const418 FCL_REAL MeshDistanceTraversalNodeOBBRSS::BVTesting(int b1, int b2) const
419 {
420 if(enable_statistics) num_bv_tests++;
421 return distance(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv);
422 }
423
leafTesting(int b1,int b2) const424 void MeshDistanceTraversalNodeOBBRSS::leafTesting(int b1, int b2) const
425 {
426 details::meshDistanceOrientedNodeLeafTesting(b1, b2, model1, model2, vertices1, vertices2, tri_indices1, tri_indices2,
427 R, T, enable_statistics, num_leaf_tests,
428 request, *result);
429 }
430
431
432
433
434
435
436 namespace details
437 {
438
439 template<typename BV>
meshConservativeAdvancementOrientedNodeCanStop(FCL_REAL c,FCL_REAL min_distance,FCL_REAL abs_err,FCL_REAL rel_err,FCL_REAL w,const BVHModel<BV> * model1,const BVHModel<BV> * model2,const MotionBase * motion1,const MotionBase * motion2,std::vector<ConservativeAdvancementStackData> & stack,FCL_REAL & delta_t)440 bool meshConservativeAdvancementOrientedNodeCanStop(FCL_REAL c,
441 FCL_REAL min_distance,
442 FCL_REAL abs_err, FCL_REAL rel_err, FCL_REAL w,
443 const BVHModel<BV>* model1, const BVHModel<BV>* model2,
444 const MotionBase* motion1, const MotionBase* motion2,
445 std::vector<ConservativeAdvancementStackData>& stack,
446 FCL_REAL& delta_t)
447 {
448 if((c >= w * (min_distance - abs_err)) && (c * (1 + rel_err) >= w * min_distance))
449 {
450 const ConservativeAdvancementStackData& data = stack.back();
451 FCL_REAL d = data.d;
452 Vec3f n;
453 int c1, c2;
454
455 if(d > c)
456 {
457 const ConservativeAdvancementStackData& data2 = stack[stack.size() - 2];
458 d = data2.d;
459 n = data2.P2 - data2.P1; n.normalize();
460 c1 = data2.c1;
461 c2 = data2.c2;
462 stack[stack.size() - 2] = stack[stack.size() - 1];
463 }
464 else
465 {
466 n = data.P2 - data.P1; n.normalize();
467 c1 = data.c1;
468 c2 = data.c2;
469 }
470
471 assert(c == d);
472
473 // n is in local frame of c1, so we need to turn n into the global frame
474 Vec3f n_transformed =
475 getBVAxis(model1->getBV(c1).bv, 0) * n[0] +
476 getBVAxis(model1->getBV(c1).bv, 1) * n[2] +
477 getBVAxis(model1->getBV(c1).bv, 2) * n[2];
478 Quaternion3f R0;
479 motion1->getCurrentRotation(R0);
480 n_transformed = R0.transform(n_transformed);
481 n_transformed.normalize();
482
483 TBVMotionBoundVisitor<BV> mb_visitor1(model1->getBV(c1).bv, n_transformed), mb_visitor2(model2->getBV(c2).bv, -n_transformed);
484 FCL_REAL bound1 = motion1->computeMotionBound(mb_visitor1);
485 FCL_REAL bound2 = motion2->computeMotionBound(mb_visitor2);
486
487 FCL_REAL bound = bound1 + bound2;
488
489 FCL_REAL cur_delta_t;
490 if(bound <= c) cur_delta_t = 1;
491 else cur_delta_t = c / bound;
492
493 if(cur_delta_t < delta_t)
494 delta_t = cur_delta_t;
495
496 stack.pop_back();
497
498 return true;
499 }
500 else
501 {
502 const ConservativeAdvancementStackData& data = stack.back();
503 FCL_REAL d = data.d;
504
505 if(d > c)
506 stack[stack.size() - 2] = stack[stack.size() - 1];
507
508 stack.pop_back();
509
510 return false;
511 }
512 }
513
514 template<typename BV>
meshConservativeAdvancementOrientedNodeLeafTesting(int b1,int b2,const BVHModel<BV> * model1,const BVHModel<BV> * model2,const Triangle * tri_indices1,const Triangle * tri_indices2,const Vec3f * vertices1,const Vec3f * vertices2,const Matrix3f & R,const Vec3f & T,const MotionBase * motion1,const MotionBase * motion2,bool enable_statistics,FCL_REAL & min_distance,Vec3f & p1,Vec3f & p2,int & last_tri_id1,int & last_tri_id2,FCL_REAL & delta_t,int & num_leaf_tests)515 void meshConservativeAdvancementOrientedNodeLeafTesting(int b1, int b2,
516 const BVHModel<BV>* model1, const BVHModel<BV>* model2,
517 const Triangle* tri_indices1, const Triangle* tri_indices2,
518 const Vec3f* vertices1, const Vec3f* vertices2,
519 const Matrix3f& R, const Vec3f& T,
520 const MotionBase* motion1, const MotionBase* motion2,
521 bool enable_statistics,
522 FCL_REAL& min_distance,
523 Vec3f& p1, Vec3f& p2,
524 int& last_tri_id1, int& last_tri_id2,
525 FCL_REAL& delta_t,
526 int& num_leaf_tests)
527 {
528 if(enable_statistics) num_leaf_tests++;
529
530 const BVNode<BV>& node1 = model1->getBV(b1);
531 const BVNode<BV>& node2 = model2->getBV(b2);
532
533 int primitive_id1 = node1.primitiveId();
534 int primitive_id2 = node2.primitiveId();
535
536 const Triangle& tri_id1 = tri_indices1[primitive_id1];
537 const Triangle& tri_id2 = tri_indices2[primitive_id2];
538
539 const Vec3f& t11 = vertices1[tri_id1[0]];
540 const Vec3f& t12 = vertices1[tri_id1[1]];
541 const Vec3f& t13 = vertices1[tri_id1[2]];
542
543 const Vec3f& t21 = vertices2[tri_id2[0]];
544 const Vec3f& t22 = vertices2[tri_id2[1]];
545 const Vec3f& t23 = vertices2[tri_id2[2]];
546
547 // nearest point pair
548 Vec3f P1, P2;
549
550 FCL_REAL d = TriangleDistance::triDistance(t11, t12, t13, t21, t22, t23,
551 R, T,
552 P1, P2);
553
554 if(d < min_distance)
555 {
556 min_distance = d;
557
558 p1 = P1;
559 p2 = P2;
560
561 last_tri_id1 = primitive_id1;
562 last_tri_id2 = primitive_id2;
563 }
564
565
566 /// n is the local frame of object 1, pointing from object 1 to object2
567 Vec3f n = P2 - P1;
568 /// turn n into the global frame, pointing from object 1 to object 2
569 Quaternion3f R0;
570 motion1->getCurrentRotation(R0);
571 Vec3f n_transformed = R0.transform(n);
572 n_transformed.normalize(); // normalized here
573
574 TriangleMotionBoundVisitor mb_visitor1(t11, t12, t13, n_transformed), mb_visitor2(t21, t22, t23, -n_transformed);
575 FCL_REAL bound1 = motion1->computeMotionBound(mb_visitor1);
576 FCL_REAL bound2 = motion2->computeMotionBound(mb_visitor2);
577
578 FCL_REAL bound = bound1 + bound2;
579
580 FCL_REAL cur_delta_t;
581 if(bound <= d) cur_delta_t = 1;
582 else cur_delta_t = d / bound;
583
584 if(cur_delta_t < delta_t)
585 delta_t = cur_delta_t;
586 }
587
588 }
589
590
MeshConservativeAdvancementTraversalNodeRSS(FCL_REAL w_)591 MeshConservativeAdvancementTraversalNodeRSS::MeshConservativeAdvancementTraversalNodeRSS(FCL_REAL w_)
592 : MeshConservativeAdvancementTraversalNode<RSS>(w_)
593 {
594 R.setIdentity();
595 }
596
BVTesting(int b1,int b2) const597 FCL_REAL MeshConservativeAdvancementTraversalNodeRSS::BVTesting(int b1, int b2) const
598 {
599 if(enable_statistics) num_bv_tests++;
600 Vec3f P1, P2;
601 FCL_REAL d = distance(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv, &P1, &P2);
602
603 stack.push_back(ConservativeAdvancementStackData(P1, P2, b1, b2, d));
604
605 return d;
606 }
607
608
leafTesting(int b1,int b2) const609 void MeshConservativeAdvancementTraversalNodeRSS::leafTesting(int b1, int b2) const
610 {
611 details::meshConservativeAdvancementOrientedNodeLeafTesting(b1, b2,
612 model1, model2,
613 tri_indices1, tri_indices2,
614 vertices1, vertices2,
615 R, T,
616 motion1, motion2,
617 enable_statistics,
618 min_distance,
619 closest_p1, closest_p2,
620 last_tri_id1, last_tri_id2,
621 delta_t,
622 num_leaf_tests);
623 }
624
canStop(FCL_REAL c) const625 bool MeshConservativeAdvancementTraversalNodeRSS::canStop(FCL_REAL c) const
626 {
627 return details::meshConservativeAdvancementOrientedNodeCanStop(c,
628 min_distance,
629 abs_err, rel_err, w,
630 model1, model2,
631 motion1, motion2,
632 stack,
633 delta_t);
634 }
635
636
637
638
MeshConservativeAdvancementTraversalNodeOBBRSS(FCL_REAL w_)639 MeshConservativeAdvancementTraversalNodeOBBRSS::MeshConservativeAdvancementTraversalNodeOBBRSS(FCL_REAL w_)
640 : MeshConservativeAdvancementTraversalNode<OBBRSS>(w_)
641 {
642 R.setIdentity();
643 }
644
BVTesting(int b1,int b2) const645 FCL_REAL MeshConservativeAdvancementTraversalNodeOBBRSS::BVTesting(int b1, int b2) const
646 {
647 if(enable_statistics) num_bv_tests++;
648 Vec3f P1, P2;
649 FCL_REAL d = distance(R, T, model1->getBV(b1).bv, model2->getBV(b2).bv, &P1, &P2);
650
651 stack.push_back(ConservativeAdvancementStackData(P1, P2, b1, b2, d));
652
653 return d;
654 }
655
656
leafTesting(int b1,int b2) const657 void MeshConservativeAdvancementTraversalNodeOBBRSS::leafTesting(int b1, int b2) const
658 {
659 details::meshConservativeAdvancementOrientedNodeLeafTesting(b1, b2,
660 model1, model2,
661 tri_indices1, tri_indices2,
662 vertices1, vertices2,
663 R, T,
664 motion1, motion2,
665 enable_statistics,
666 min_distance,
667 closest_p1, closest_p2,
668 last_tri_id1, last_tri_id2,
669 delta_t,
670 num_leaf_tests);
671 }
672
canStop(FCL_REAL c) const673 bool MeshConservativeAdvancementTraversalNodeOBBRSS::canStop(FCL_REAL c) const
674 {
675 return details::meshConservativeAdvancementOrientedNodeCanStop(c,
676 min_distance,
677 abs_err, rel_err, w,
678 model1, model2,
679 motion1, motion2,
680 stack,
681 delta_t);
682 }
683
684
685
686
687
688 }
689