search

danfis / libccd

Library for collision detection between two convex shapes
Other
478 stars 108 forks source link

ccdVec3PointTriDist2() divides by zero. #51

Closed stolk closed 5 years ago

stolk commented 5 years ago

In freak occurrences, ccdVec3PointTriDist2() can divide by zero.

If you collide often enough, at some point wv will equal rr as it was caught in the wild in my debugger, below:

Program received signal SIGFPE, Arithmetic exception.
─── Assembly ───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
0x000055555560cf39 ccdVec3PointTriDist2+1589 movss  -0x7f0(%rbp),%xmm2
0x000055555560cf41 ccdVec3PointTriDist2+1597 mulss  -0x7f0(%rbp),%xmm2
0x000055555560cf49 ccdVec3PointTriDist2+1605 subss  %xmm2,%xmm1
0x000055555560cf4d ccdVec3PointTriDist2+1609 divss  %xmm1,%xmm0
0x000055555560cf51 ccdVec3PointTriDist2+1613 movss  %xmm0,-0x7ec(%rbp)
0x000055555560cf59 ccdVec3PointTriDist2+1621 movss  -0x7ec(%rbp),%xmm1
0x000055555560cf61 ccdVec3PointTriDist2+1629 movss  0x20957(%rip),%xmm0        # 0x55555562d8c0
─── Expressions ────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
─── History ────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
─── Memory ─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
─── Registers ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
   rax 0x00007fffffffbf70     rbx 0x00007fffffffc650     rcx 0x00007fffffffc46c     rdx 0x00007fffffffc448     rsi 0x00007fffffffc424     rdi 0x000055555584bc68     rbp 0x00007fffffffbfc0     rsp 0x00007fffffffb780      r8 0x00007fffffffc500 
    r9 0x00007fffffffc500     r10 0x0000555555866f10     r11 0x0000000000000000     r12 0x0000555555866d50     r13 0x00007fffffffc550     r14 0x00007fffffffc590     r15 0x00007fffffffc650     rip 0x000055555560cf4d  eflags [ PF ZF IF RF ]    
    cs 0x00000033              ss 0x0000002b              ds 0x00000000              es 0x00000000              fs 0x00000000              gs 0x00000000         
─── Source ─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
162     w = ccdVec3Dot(&d2, &d2);
163     p = ccdVec3Dot(&a, &d1);
164     q = ccdVec3Dot(&a, &d2);
165     r = ccdVec3Dot(&d1, &d2);
166 
167     s = (q * r - w * p) / (w * v - r * r);
168     t = (-s * r - q) / w;
169 
170     if ((ccdIsZero(s) || s > CCD_ZERO)
171             && (ccdEq(s, CCD_ONE) || s < CCD_ONE)
172             && (ccdIsZero(t) || t > CCD_ZERO)
─── Stack ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
[0] from 0x000055555560cf4d in ccdVec3PointTriDist2+1609 at /home/bram/src/libccd/src/vec3.c:167
arg P = 0x55555584bc68 <__ccd_vec3_origin>
arg x0 = 0x7fffffffc424
arg B = 0x7fffffffc448
arg C = 0x7fffffffc46c
arg witness = 0x7fffffffc500
[1] from 0x0000555555607a45 in findPenetr+2858 at /home/bram/src/libccd/src/mpr.c:325
arg obj1 = 0x7fffffffc550
arg obj2 = 0x7fffffffc590
arg ccd = 0x7fffffffc4c0
arg portal = 0x7fffffffc400
arg depth = 0x7fffffffc4bc
arg pdir = 0x7fffffffc500
arg pos = 0x7fffffffc50c
[+]
─── Threads ────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
[1] id 8455 name demo_convex from 0x000055555560cf4d in ccdVec3PointTriDist2+1609 at /home/bram/src/libccd/src/vec3.c:167
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
0x000055555560cf4d in ccdVec3PointTriDist2 (P=0x55555584bc68 <__ccd_vec3_origin>, x0=0x7fffffffc424, B=0x7fffffffc448, C=0x7fffffffc46c, witness=0x7fffffffc500) at /home/bram/src/libccd/src/vec3.c:167
167     s = (q * r - w * p) / (w * v - r * r);
>>> where
#0  0x000055555560cf4d in ccdVec3PointTriDist2 (P=0x55555584bc68 <__ccd_vec3_origin>, x0=0x7fffffffc424, B=0x7fffffffc448, C=0x7fffffffc46c, witness=0x7fffffffc500) at /home/bram/src/libccd/src/vec3.c:167
#1  0x0000555555607a45 in findPenetr (obj1=0x7fffffffc550, obj2=0x7fffffffc590, ccd=0x7fffffffc4c0, portal=0x7fffffffc400, depth=0x7fffffffc4bc, pdir=0x7fffffffc500, pos=0x7fffffffc50c) at /home/bram/src/libccd/src/mpr.c:325
#2  0x00005555556033eb in ccdMPRPenetration (obj1=0x7fffffffc550, obj2=0x7fffffffc590, ccd=0x7fffffffc4c0, depth=0x7fffffffc4bc, dir=0x7fffffffc500, pos=0x7fffffffc50c) at /home/bram/src/libccd/src/mpr.c:144
#3  0x000055555559ca8c in ccdCollide (o1=o1@entry=0x555555866d50, o2=o2@entry=0x555555877160, flags=flags@entry=32, contact=contact@entry=0x7fffffffc650, obj1=obj1@entry=0x7fffffffc550, supp1=supp1@entry=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj2=0x7fffffffc590, supp2=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, skip=<optimized out>, cen2=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, cen1=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>) at collision_libccd.cpp:339
#4  0x000055555559d1bb in ccdCollide (skip=<optimized out>, cen2=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, supp2=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj2=0x7fffffffc590, cen1=0x55555559b5d0 <ccdCenter(void const*, ccd_vec3_t*)>, supp1=0x55555559b390 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj1=0x7fffffffc550, contact=0x7fffffffc650, flags=32, o2=0x555555877160, o1=0x555555866d50) at collision_libccd.cpp:319
#5  dCollideConvexConvexCCD (o1=0x555555866d50, o2=0x555555877160, flags=32, contact=0x7fffffffc650, skip=<optimized out>) at collision_libccd.cpp:457
#6  0x000055555555e3a9 in nearCallback (o1=<optimized out>, o2=<optimized out>, data=<optimized out>) at demo_convex.cpp:88
#7  0x0000555555569829 in collideAABBs (callback=<optimized out>, data=0x0, g2=0x555555877160, g1=0x555555866d50) at collision_space_internal.h:77
#8  dxHashSpace::collide (this=0x55555585e9e0, data=0x0, callback=0x55555555e490 <nearCallback(void*, dGeomID, dGeomID)>) at collision_space.cpp:569
#9  0x000055555555de2e in simLoop (pause=<optimized out>) at demo_convex.cpp:230
#10 0x0000555555562a26 in processDrawFrame (frame=0x7fffffffdc00, fn=<optimized out>) at x11.cpp:337
#11 0x00005555555630ab in dsPlatformSimLoop (window_width=window_width@entry=1920, window_height=window_height@entry=1080, fn=fn@entry=0x7fffffffde90, initial_pause=initial_pause@entry=0) at x11.cpp:416
#12 0x000055555556159f in dsSimulationLoop (argc=1, argv=0x7fffffffe038, window_width=1920, window_height=1080, fn=0x7fffffffde90) at drawstuff.cpp:1291
#13 0x000055555555d9b0 in main (argc=1, argv=0x7fffffffe038) at demo_convex.cpp:429
>>> l
162     w = ccdVec3Dot(&d2, &d2);
163     p = ccdVec3Dot(&a, &d1);
164     q = ccdVec3Dot(&a, &d2);
165     r = ccdVec3Dot(&d1, &d2);
166 
167     s = (q * r - w * p) / (w * v - r * r);
168     t = (-s * r - q) / w;
169 
170     if ((ccdIsZero(s) || s > CCD_ZERO)
171             && (ccdEq(s, CCD_ONE) || s < CCD_ONE)
>>> print w
$1 = 1.19620562
>>> print v
$2 = 0.0274525639
>>> print w*v
$3 = 0.0328389108
>>> print r
$4 = 0.181215093
>>> print r*r
$5 = 0.0328389108
>>> print w*v
$6 = 0.0328389108
>>> print r*r
$7 = 0.0328389108
scpeters commented 5 years ago

at some point w*v will equal r*r

I added backticks around the two product terms to fix the text formatting

danfis commented 5 years ago

The question here is why wv equals rr. Can you also print out the input of the function?

stolk commented 5 years ago

I caught another instance.

0x000055555560cf1d in ccdVec3PointTriDist2 (P=0x55555584bc68 <__ccd_vec3_origin>, x0=0x7fffffffc3d4, B=0x7fffffffc3f8, C=0x7fffffffc41c, witness=0x7fffffffc4b0) at /home/bram/src/libccd/src/vec3.c:167
167     s = (q * r - w * p) / (w * v - r * r);
>>> where
#0  0x000055555560cf1d in ccdVec3PointTriDist2 (P=0x55555584bc68 <__ccd_vec3_origin>, x0=0x7fffffffc3d4, B=0x7fffffffc3f8, C=0x7fffffffc41c, witness=0x7fffffffc4b0) at /home/bram/src/libccd/src/vec3.c:167
#1  0x0000555555607a15 in findPenetr (obj1=0x7fffffffc500, obj2=0x7fffffffc540, ccd=0x7fffffffc470, portal=0x7fffffffc3b0, depth=0x7fffffffc46c, pdir=0x7fffffffc4b0, pos=0x7fffffffc4bc) at /home/bram/src/libccd/src/mpr.c:325
#2  0x00005555556033bb in ccdMPRPenetration (obj1=0x7fffffffc500, obj2=0x7fffffffc540, ccd=0x7fffffffc470, depth=0x7fffffffc46c, dir=0x7fffffffc4b0, pos=0x7fffffffc4bc) at /home/bram/src/libccd/src/mpr.c:144
#3  0x000055555559ca5c in ccdCollide (o1=o1@entry=0x555555862170, o2=o2@entry=0x5555558691b0, flags=flags@entry=32, contact=contact@entry=0x7fffffffc600, obj1=obj1@entry=0x7fffffffc500, supp1=supp1@entry=0x55555559b360 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj2=0x7fffffffc540, supp2=0x55555559b360 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, skip=<optimized out>, cen2=0x55555559b5a0 <ccdCenter(void const*, ccd_vec3_t*)>, cen1=0x55555559b5a0 <ccdCenter(void const*, ccd_vec3_t*)>) at collision_libccd.cpp:339
#4  0x000055555559d18b in ccdCollide (skip=<optimized out>, cen2=0x55555559b5a0 <ccdCenter(void const*, ccd_vec3_t*)>, supp2=0x55555559b360 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj2=0x7fffffffc540, cen1=0x55555559b5a0 <ccdCenter(void const*, ccd_vec3_t*)>, supp1=0x55555559b360 <ccdSupportConvex(void const*, ccd_vec3_t const*, ccd_vec3_t*)>, obj1=0x7fffffffc500, contact=0x7fffffffc600, flags=32, o2=0x5555558691b0, o1=0x555555862170) at collision_libccd.cpp:319
#5  dCollideConvexConvexCCD (o1=0x555555862170, o2=0x5555558691b0, flags=32, contact=0x7fffffffc600, skip=<optimized out>) at collision_libccd.cpp:457
#6  0x000055555555e379 in nearCallback (o1=<optimized out>, o2=<optimized out>, data=<optimized out>) at demo_convex.cpp:88
#7  0x00005555555697f9 in collideAABBs (callback=<optimized out>, data=0x0, g2=0x5555558691b0, g1=0x555555862170) at collision_space_internal.h:77
#8  dxHashSpace::collide (this=0x55555585e9e0, data=0x0, callback=0x55555555e460 <nearCallback(void*, dGeomID, dGeomID)>) at collision_space.cpp:569
#9  0x000055555555de1e in simLoop (pause=<optimized out>) at demo_convex.cpp:230
#10 0x00005555555629f6 in processDrawFrame (frame=0x7fffffffdbb0, fn=<optimized out>) at x11.cpp:337
#11 0x000055555556307b in dsPlatformSimLoop (window_width=window_width@entry=1920, window_height=window_height@entry=1080, fn=fn@entry=0x7fffffffde40, initial_pause=initial_pause@entry=0) at x11.cpp:416
#12 0x000055555556156f in dsSimulationLoop (argc=1, argv=0x7fffffffdfe8, window_width=1920, window_height=1080, fn=0x7fffffffde40) at drawstuff.cpp:1291
#13 0x000055555555d9b0 in main (argc=1, argv=0x7fffffffdfe8) at demo_convex.cpp:431
>>> l
162     w = ccdVec3Dot(&d2, &d2);
163     p = ccdVec3Dot(&a, &d1);
164     q = ccdVec3Dot(&a, &d2);
165     r = ccdVec3Dot(&d1, &d2);
166 
167     s = (q * r - w * p) / (w * v - r * r);
168     t = (-s * r - q) / w;
169 
170     if ((ccdIsZero(s) || s > CCD_ZERO)
171             && (ccdEq(s, CCD_ONE) || s < CCD_ONE)
>>> print r*r
$1 = 0.142042294
>>> print w*v
$2 = 0.142042294
>>> print r
$3 = 0.376884997
>>> print w
$4 = 0.737652779
>>> print v
$5 = 0.192559838
>>> print P
$6 = (const ccd_vec3_t *) 0x55555584bc68 <__ccd_vec3_origin>
>>> print *P
$7 = {
  v = {[0] = 0, [1] = 0, [2] = 0}
}
>>> print *x0
$8 = {
  v = {[0] = -0.36715889, [1] = 0.288464308, [2] = 0.000100158155}
}
>>> print B
$9 = (const ccd_vec3_t *) 0x7fffffffc3f8
>>> print* B
$10 = {
  v = {[0] = -0.0222680569, [1] = 0.0171524286, [2] = -2.88337469e-06}
}
>>> print *witness
$11 = {
  v = {[0] = 1.85003703e+13, [1] = 3.0611365e-41, [2] = 1.49615028e+13}
}
>>> print d1
$12 = {
  v = {[0] = 0.344890833, [1] = -0.271311879, [2] = -0.00010304153}
}
>>> print d2
$13 = {
  v = {[0] = 0.675082207, [1] = -0.530958414, [2] = -6.17951155e-05}
}
>>> print a
$14 = {
  v = {[0] = -0.36715889, [1] = 0.288464308, [2] = 0.000100158155}
}