T E L KO M NI K A ,  V o l. 1 4 ,  N o. 3 S ept em ber   20 1 6 ,  pp.   10 77 ~ 108 2   I S S N :  1 693 - 6 930 ac c r edi t ed  A   b D IK T I,  D e c r e e  N o 58/ D I K T I / K ep/ 2013   D O I :   10. 12928/ T E LK O M N I K A . v 1 4 i 3 . 3590      10 77       R ec ei v ed   A p r il   2 ,  2 01 6 ;  R e v i s ed  J une   1 2 ,  20 1 6 ;  A c c e pt ed  J u ne  2 9 ,  201 6   H y b r id   Hier ar ch ical Co lli sio n  D et ect i o n   Base d   o n  Da t Reu se       Ji an ca i  H u ,   K e j i n g  H e * ,   X i a o b i n  L i n ,  F u n a n  L i n   S c hoo l  of  C om p ut er  S c i e nc e  a nd E ng i neer i ng ,  S out h C hi na  U ni v er s i t y  of  T ec hno l ogy ,     G uangz hou 5106 41,   G u angd o ng,   C hi na   * C or r es po ndi ng a ut hor ,  e - m a i l k j h e@ s c ut . e du. c n       A b st r act   T i m pr ov t he  ef f i c i e nc y   of   c ol l i s i on  d et e c t i o bet w een  r i gi bo di e s   i c o m p le x  s c en es ,   t his   paper  pr o po s es  a m et h od ba s ed on hy br i d b ound i ng  v ol um e  hi er ar c hi e s  f or  c ol l i s i on det ec t i on.  I n or der  t o   i m pr ov t he  s i m ul at i on  pe r f or m anc e,   t h m et hod  i s   ba s e on  w ei gh t ed  or i ent ed  bo und i n box   a nd  m ak e s   dens e s am pl i ng on t h e c on v e x  h ul l s  of  t he ge om et r i c  m od el s .  T h e hi er ar c h i c a l  boun di n g v ol um e t r ee  i s   c om pos ed o f  m any  l a y er s .  T h e upp er m os t   l ay er  ad opt s  a  c ubi c  bou ndi ng b ox ,  w hi l e l ow e r  l ay er s   em pl o y   w ei ght e d or i e nt ed b ound i ng b ox .  I n t he m ea nt i m e,  t he d at a  of  w ei ght e d or i en t ed bo und i n g box  i s  r eus e d   f or  t r i a ngl e i nt er s ec t i on  c h ec k .  W e t e s t  t he m et h od  us i ng t w o  s c e ne s .  T h e f i r s t   s c ene  c on t ai ns  t w o B udd h a   m odel s  w i t h  t ot al l y   361, 690  t r i angl e  f a c et s .   T he  s ec o nd  s c e ne i s   c om po s ed  of  20 0 m ode l s  w i t h t ot al l y  115 ,   200 t r i ang l e f ac e t s .   T he  ex p er i m ent s  v er i f y  t h e ef f ec t i v e nes s   of  t he  pr op os e d m et ho d.     Ke y w o rd s c ol l i s i on d et e c t i o n,  hi er ar c h i c a l   s t r uc t ur e ,  dat a   r e us e     C o p y r i g h t   ©   20 16 U n i ver si t a s A h mad  D ah l an .  A l l  r i g h t s r eser ved .       1 .  I n tr o d u c ti o n   C ol l i s i on  d et ec t i on i s  w i d el y   us ed i c om put er  g am es ,  v i r t ual  s ur g er y ,   p h y s i c a l   s i m ul at i on,  r o bot i c s  and s o on [ 1,  2 ] .  I t  p l a y s  a n ex t r em el y   i m por t ant  r ol e i n t h es e f i el ds .  T he  pur pos es  of  c ol l i s i o n det ec t i on  ar e t o d et ec t   w h et h er  t h e c ol l i s i o n be t w ee n obj ec t s   oc c ur s  or  not ,   and  t o k no w   w he n a nd   w he r e t he  c ol l i s i on  oc c ur s .   W i t h  t he  ad v a nc of  v i r t ual  r ea l i t y  t ec hno l o g y   i n r ec ent   y e ar s ,  t he d i f f i c ul t i es  of  t he s c ene s i m ul at i o n al s o i nc r eas es .  I n t he s a m e t i m e,  dat a   s t r uc t ur es  and al gor i t hm s   abou t  c ol l i s i o n de t ec t i on h av bec om m or e and m o r e c o m pl ex  i dea l i n w i t s uc l ar ge  d at s et s ,   es pec i a l l y   f or   r eal - t i m c al c ul at i on .   R es ear c o t he  c o l l i s i o n   det ec t i on m et hod has  l o n g hi s t or y ,   and m an y  r es e ar c her s  hav e r es ear c h ed  deep l y   and p ut   f or w ar d a  s er i es  of  ef f i c i ent  al gor i t hm s  bas ed on bou ndi ng box .  B o un di n g box  t i ght l y  c ont a i ns   t he obj ec t  b ut   w i t h s i m pl e geom et r i c  c har ac t er i s t i c s ,  t o appr ox i m at el y  d es c r i be t he  obj ec t .   B ef or e c ond uc t i n g t h e c ol l i s i on  det ec t i o n am ong r eal   o bj ec t s ,  t he i nt er s ec t i on of  b ound i n g box es   i s  c hec k ed f i r s t l y .  I f  t he  i nt e r s ec t i on h app ens ,  a  f ur t her   c ol l i s i on  det ec t i o i s  nee de d.   T her ar s om c o m m on  t y p es   of   boun di ng  box es   s u c as   A x i s - A l i gne B ou nd i ng  B ox   ( AA BB)   [ 3 ] ,   O r i ent ed  B ou n di n B ox   ( O B B )   [ 4 ],  K - D O Ps   [ 5 ] ,   a nd  S ph er es   [ 6 ].  D i ff e r e n t y p e s   o boun di ng b ox es  ha v di f f er ent  f oc us ,  f or  ex a m pl e t h e s i m pl i c i t y   an d t i ght n es s .  T he s i m pl i c i t y   and  t i g ht n es s   of   boun di ng  box   ar of t en  c o nt r ad i c t or y .   R ec en t l y ,   m os t   r es ear c he s   m ai nl y   f oc us   on i m pr ov i n t he  ef f i c i enc y   and  ac c ur ac y  of  c ol l i s i o det ec t i on  a l g or i t hm s .   F i gue i r edo  [ 7 ]   us es   t he o v er l ap pi ng m ul t i - ax i s  boun di ng  box ,   w hi c h c a n f i l t er  d i s j oi nt  obj ec t s  f as t  an d i m pr ov t he   ef f i c i enc y   of  c ol l i s i on de t ec t i on.   Mac i e l  [ 8 ]   em pl o y s  t he  s pher e f or  f as t   c ol l i s i on d et ec t i on  am ong   obj ec t s .   Lai   [ 9 ]   us es   s pher and  c y l i n der   t r epr es e n t   obj ec t s   f or   qui c k   nav i g at i o i t he  s c ene,   w hi c i s   f as t  but   not   ac c ur at e nou gh.   C ha ng  [ 10 ]   c o m bi nes   t he  s ph er w i t h O B B   t i m pr ov t he s pee d of  c ol l i s i on d et e c t i on,  b ut  bec a us e of  t he l i m i t at i ons  of  t he s pher e,  t h e ac c ur ac y   of   det ec t i on  i s  no t  en oug h.   S i n gl e t y pe  of  bou ndi ng  b ox  has  s om e def i c i enc i es  and  ac c ur ac y   pr obl em s   i n r ea l - t i m e c ol l i s i on  det ec t i o n [ 11 ] ,  t h er ef or e m or e and  m or e r es ea r c her s  pr opos m an y  a l gor i t hm s  c o m bi ni ng t he  ad v an t ag es  of  di f f er ent  bou ndi ng b ox es .   A m ong t hem ,   B ou nd i ng  V ol um H i er ar c hi es   ( B V H )   [ 12 - 14 ]   i s   one  of   t he  m os t   w i de l y   us e d,   w hi c c an  w or k   i c o m pl ex  en v i r onm ent s .  A r bab i  [ 15 ]  us es  c y l i ndr i c al  a nd r ad i a l  s pac e  s egm ent at i on m et hod  t per f or m   c ol l i s i on  det ec t i o f or   j oi nt   c on nec t i on.   T hi s   m et hod  has   b et t er   pr ec i s i on   w i t l i m i t ed  us age  i n  c ol l i s i on  det ec t i o n of  bou nd ar y  m ov em ent .  I n r ec e nt   y ear s ,  m an y  r e s ear c her s  us e   har d w ar e a c c el er at i o n t s peed u p t he c o l l i s i o n det ec t i on  w i t t he h el p of  be t t er  c om put er   Evaluation Warning : The document was created with Spire.PDF for Python.
                             I SSN :  1 6 9 3 - 6 930   T E L KO M NI K A     V o l.   1 4 ,  N o 3 S ept em ber   201 6   :   10 77     1 082   1078   per f or m anc [ 16 - 18 ].  X i e   [ 19 ]   c om bi nes   hi er ar c hi c a l   boun di ng  s ph er w i t G P U   ac c el er at i on  t s i m ul at e c ol l i s i on  de t ec t i o n am ong r i gi d b od i es  f or   r hi no pl as t y .   S hen  [ 2 0]   ado pt s   t he  m i x ed   boun di ng  v o l um e hi er ar c h y   t r ee  t o d et ec t  t he  pot e nt i al  c ol l i s i on o bj ec t  s et s  qu i c k l y ,  an d t h en  us es  t he s t r eam i ng pat t er n al gor i t hm   f or  ac c ur at e c ol l i s i o n det ec t i o n.  B ut  t hes e appr oac h es   hav e n ot  t ak en t h e a dv ant a ges  of  di f f er ent  t y p es  of  bo und i n g box es .   I n t h i s  p ap er ,   w e  pr o pos e  an  i m pr ov ed  h y br i hi er ar c hi c al  c ol l i s i on  det ec t i o m et hod  bas ed o n da t a r eus e .   W c om bi ne t he s i m pl i c i t y   of  i m pr ov e d A A B B   and t he t i gh t nes s  of  O B B  t bui l d h y br i B V H  s t r uc t ur e f or  obj ec t s .  O ur  i m pr ov ed h y br i d hi er ar c hi c a l  s t r u c t ur e has  t w l a y er s .  T he upper m os t  l a y er  us es  opt i m i z ed c ubi c  b ound i n g box ,  w hi c h i s  eas y  t o r ot at e a nd  t r ans f or m .  B y  t h i s   w a y ,  t h e obj ec t s  ar e not  i nt er s ec t ed i n t he s c ene c an b e ex c l ude d qu i c k l y .   T he  l o w er   l a y er s   us t he   O B B ,   w h i c has   bet t er   t i g ht n es s   and   c an   be   us ed   f or   f ur t her   c ol l i s i on  det ec t i on f or  t hos e i nt er s e c t ed  obj ec t s  f ound i n t he  u pper  l a y er .  T he m et hod c a n i m pr ov e t he  ef f i c i enc y   an d ac c ur ac y  of   c ol l i s i on  det ec t i o n b y  t ak i ng  t he a dv ant ages  of  t he  h y br i d h i er ar c h i c al   boun di ng s t r uc t ur es .  I n t h m eant i m e,  w e i nt r od uc e  a new  a l g or i t hm  f or  t r i angl e i nt er s ec t i on  c hec k  b y  r eus i n g t h e O B B  dat a   [ 21 ] ,   w h i c h c an ef f ec t i v e l y  r educ e t he c al c u l at i on an d f ur t her   i m pr ov e t he  ef f i c i enc y .   T hi s  paper  i s  or g an i z ed as   f ol l o w s .  F o l l o w i ng t h e i nt r o duc t i o n i n   S ec .  1,   S ec .  2 pr es ent s   t he  i m pr ov ed  h y br i hi er ar c hi c al   c o l l i s i on  d et ec t i on  m et hod  bas e on  da t r eus e.   I S ec .   3,   t he  m et hod i s  ap pl i ed  t o  t he  c o l l i s i on  de t ec t i on  of  t w o m odel s  a nd m ul t i p l e  m odel s  r es pec t i v e l y .   W e   al s o c om par e t h per f or m anc e of  our  m et hod  w i t h  ot h er  ap pr oac hes .  F i n al l y ,  s o m e c onc l us i ons   and  di s c us s i ons  ar e m ade i n S ec .   4.       2.  R e sea r ch  M et h o d   T he c ol l i s i on d et ec t i on am ong  A A B B   i s  s i m pl e and f as t ,  w hi c h c a n be ac c om pl i s he w i t h i n s i x  t es t s .   W hen t he  obj ec t   m ov es ,   A A B B   has   t be   r ebu i l t .   A  g i v en  obj ec t s   O B B   i s  t he  s m al l es t  c ub oi d  t h at  c on t ai ns  t he  obj ec t .  C om par ed t o  A A B B ,  O B B   has  b et t er  t i g ht nes s ,  b ut  t he   i nt er s ec t i on c h ec k  i s   m or e ex pens i v e.   T he  m os t   us ed  m et hod  t det er m i ne  w h et h er   t w o   c on v ex   h ul l s   ar e   i n t er s ec t ed   or   not   i s   t o us e t he  s ep ar at i ng ax i s  t es t  [ 22 ] .  T he num ber  of   s epar at i ng ax i s  d epe nds  o n t he t y p e of   boun di ng b ox .  F or  ex am pl e,  A A B B   has  3 ( x y z )  t y pi c a l  s epar at i n g ax es .  O B B  has  1 5 t y p i c a l   s epar at i ng  ax es ,  s o  t h i nt er s ec t i o n c hec k  of  t w O B B s  c ou l d  t ak e up  t o  1 5 c om par i s on  oper at i o ns ,  60  ad di t i o oper at i o ns ,  81  m ul t i p l i c at i on o per at i o ns ,  an d 2 abs ol ut v a l u oper at i o ns  [ 23 ].   T r adi t i on al   h y br i B V H   j us t   s i m pl y   us es   t w d i f f er ent   boun di ng  b o x es   t enc l os e   ev er y   obj ec t  f or  bet t er  c om pac t nes s  and f as t  ex c l udi ng d i s j oi nt  obj ec t s  [ 24 ] .   W hen t he obj ec t s  ar c l os but   not   c ol l i de,   t he y   c an  be  s ep ar at ed  s i m pl y   b ec aus of   boun di ng  b ox s   t i ght nes s ,   t hus   t he  p er f or m anc of   h y br i B V H   i s   be t t er   t h an  t ha t   of   s i ngl b oun di n b ox .   H o w e v er ,   w hen  t w o   obj ec t s  ar i nt er s ec t ed,  t h e i nt er s ec t i on  of  bou nd i ng  box  s t r uc t ur es  i s   goi ng  t o b e c hec k ed  m ul t i pl y   t i m es ,   w h i c br i ng s   r edund ant   c a l c ul at i ons .   T hus   i t   is   un abl t f ul f i l l   t he   r equi r em ent s   of  r eal - t im e  c o llis io n de t e c t i on.  T hi s  paper  pr o v i d es  an ef f i c i ent  h y br i d hi er ar c hi c al  c ol l i s i on   det ec t i on m et hod bas ed o n  dat a r eus e.   W e  i nt egr at e t he c ubi c  bou nd i ng b ox  and  w ei g ht e d O B B   t o f or m  a h y br i d  hi er ar c hi c a l  s t r uc t ur i t he  pr et r e at m ent  p has e.  T hen  w e  i nt r odu c e t he  t r i a ngl e   i nt er s ec t i on  c hec k   al gor i t h m  b y  r eus i ng  t h e O B B   dat a,   w hi c c an  ef f ec t i v e l y  r e duc t h e   c al c ul a t i o n t i m e and i m pr ov e t he  per f or m anc e of  c ol l i s i on d et ec t i on.     2 .1 F r o m   A A B B  to  C u b i c   B o u n d i n g  B o x   T o r educ e t he m e m or y  c o ns um pt i on an d t o s p eed  u p t he  c a l c ul at i on,  w us e c ubi c   boun di ng  box ,   w hi c i s  a s pec i a l  k i nd of  A A B B .  T he c ubi c  b ou ndi ng  box  h as  t he   s a m e hal f - w i dt ex t ent  ( or  r adi us   r )  i n t hr ee ax es ,  and t he c ent er - r ad i us  r epr es ent at i on i s  ad opt e d.  W e   s uppos e   t hat   t he  m odel   i s   c om pos ed  of   N   t r i an gl es ,   and  i o i p i q   ar t he  v er t ex es   of   t r i a ng l i ,   and  t he c en t er   po i n t  of  c ubi c  b o und i ng  box  i s :     1 1 () 3 = = ++  N ii i i C op q N   .                                                                  ( 1)     T he hal f - w i dt h  ex t en t  or  r ad i us  i s :   Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NI K A     I S S N :  1 693 - 6 930       H y br i d H i er ar c hi c a l  C ol l i s i o n D et ec t i o n B as ed  on D at a   R eus e ( J ia n c a i H u )   1079   ( ) ( ) m a x m a x ( ,) , ( ,) , ( ,) =   i ii i r di s t o C di s t p C di s t q C   ,                                     ( 2)     W h er di s t ( , )  i s  t he f unc t i o n t o c al c ul at e t h di s t a nc e b et w ee n t w o po i nt s .   S i nc e t he c ubi c   boun di ng b ox  has  t he s a m r adi us  i n t hr ee ax es ,   t her ef or e,  t he  obj ec t  c an  m ov e or  r ot at w i t h out   c h ang i ng  t he  r adi us .   T hi s   m et hod  n ot   on l y   r educ es   t he   s t or ag us age,   but   al s ac c el er at es  t he  bou ndi ng  b ox  upda t i n g.  T he i nt er s ec t i on c hec k  of  c ubi c  bound i n g  box  i s  s i m pl er   t han  s pher e s .   S up pos e  t h at  ( x y z )  i s  t he  c ent er  p oi n t  of  c ubi c   bou nd i ng  box ,  t hen  t he   m i ni m u m   c oor di nat ( xr , yr , zr )   an t he  m ax i m u m   c oor di nat e   ( + xr , + y r , + zr )   c an  be   got t e n q ui c k l y .  I t  c a n ac h i e v i nt er s ec t i on  c hec k  w i t hi n  s i x  t es t s .   I n or der  t i m pr ov e t he ef f i c i enc y ,  t he s p at i al  a nd t em por al  c or r el at i on i s  i nt r od uc e d.   W e   us e t hr ee l i s t s  t o s av e t he pr oj ec t i v e c oor di nat es  of  obj ec t s  i n t hr ee  ( x y z )   a x es   r es pec t i v el y .   W hen t he obj ec t s  s t at e c han ges ,   t h m et ho d upd at es   t h e t hr ee  l i s t s   and  qu i c k l y   f i nds   t he  bou nd i ng  box   pa i r s   t hat   i nt er s ec t   i t he  pr oj ec t i on ,   and  p ut s   t hos p ai r s   i nt g l ob al   di c t i onar y .  I t   w i l l  get  obj ec t   pai r s  o ut  f r om  t he gl ob al  d i c t i onar y   w hen f ur t h er  i n t er s ec t i on  c hec k  i s   r equi r e d.   A   t r av er s al   a l gor i t hm   i s   us ed  f or   det ec t i n t h c ol l i s i o ns   bet w een  s i bl i ng   s ubt r ees .   W e   bui l a ne w  l i s t  f or  eac obj ec t  t o r ec or t he  ne i g hbor s  t hos e  c ol l i d w i t h t he o bj ec t .   W e   dedu pl i c at e t h e l i s t  t o ex c l ude r ed und ant  c ol l i s i ons .   W h en t w o obj ec t s  c ol l i d e,   t he obj ec t   w i t l ar ger  I D  num ber   w i l l   be s t or ed  i n t he  l i s t   of  t he o bj ec t   w i t h s m al l er  I D  n um ber .  I f  t he l i s t  i s   em pt y ,  t h er e w as  no c ol l i s i on w i t h t he obj ec t .  A c c or d i n g t o t he ab ov e ana l y s i s ,  our   m et hod t ak es   adv ant ages  of  t he s pat i al   and t em por al  c or r el at i on o f  obj ec t s   m ov e m ent ,  and  m a k e s  i t  not   nec es s ar y   t o t r a v er s e f r o m   t he t r ee r oot ,  a v o i d i n g us el es s  c al c ul at i on,  s o s pee ds  up t he c ol l i s i on  det ec t i on pr oc es s .     2 . 2 W e i g h te d  O r i e n te d  B o u n d i n g  B o x   T r adi t i on al  m et hod f or  c om put i ng  t he  c ent er  p oi n t  of  O B B  i s  t get   t he  m ean pos i t i on  of   al l   v er t ex es .   B ut   i pr ac t i c e ,   t he  s i z es   of   t he  t r i ang l es   t hat   c ons t i t ut t he  obj ec t   ar non un i f or m ,   s o us i ng t he  t r ad i t i on al  m et hod  w i l l  m a k e t he c al c ul a t ed  c ent er  p oi nt  t e nd t o c r o w ded t r i an gl f ac et s .  T hi s   paper  pr op os e s   w e i g ht ed  or i ent e b oun di ng b ox .   W m a k dens s am pl i ng  f or   t he p oi nt s  of  c on v ex  h ul l  s u r f ac es  i n or der  t o r ed uc e t h e i m pac t  of  c r ow d ed  t r i an gl e f ac et s .  I n t he   i - t h t r i a ngu l a r  f ac et  of  c on v e x  hul l ,  t h e c ent er  po i nt  i s :     3 ++ =  i ii i o pq c ,                                                                       ( 3)     A nd  t he s ur f ac e ar e a i s :     ( )( ) 2 × =  i i ii i o p oq S .                                                              ( 4)     T he t ot al   ar ea  of  t he c on v e x  hul l  i s :     1 = = n i i WS .                                                                            ( 5)     T he c ent er  of  t he  bou ndi ng  box  i s :     1 1 ( ) = = n i i i C Sc n .                                                                    ( 6)     Let   j   and  k   be t he c om ponen t  of  ( x y z ) ,  and  ac c or di n g t o  t he a bo v e a na l y s i s ,   t he   c ov ar i anc , jk C ov   is :   ( ) , ,, , , , , , , 1 9 12 = = + + + n i j k i j ik i j ik i j ik i j ik j k i S C ov c c o o p p q q C C W .                      ( 7)   Evaluation Warning : The document was created with Spire.PDF for Python.
                             I SSN :  1 6 9 3 - 6 930   T E L KO M NI K A     V o l.   1 4 ,  N o 3 S ept em ber   201 6   :   10 77     1 082   1080   2 . 3 H y b r i d  H i e r a r c h i c a l  B o u n d i n g  V o l u m e  T r e e   I t h i s   pap er ,   w c r eat h y br i b oun di ng  b ox   t r ee  f or   obj ec t s   i t h v i r t u al   e nv i r o nm ent .   T he t r ee i s  c o m pos ed of  s e v er a l  l a y er s .  T he upper m os t  l a y er  us es  t he c ub i c  bou n di n g box  ( S ec .   2. 1) ,  an d t he l o w er  l a y er s  u s e w e i g ht ed O B B  ( S ec .  2. 2 )  w i t h bet t er  t i g ht n es s .  T hi s  al gor i t hm  not   onl y   c a ex c l ude   n on i nt er s ec t i ng   o bj ec t s   i n   c om pl ex   s c enes   qu i c k l y ,   b ut   al s o   c an  do  ac c ur at c ol l i s i on   de t ec t i on.   I t   has   b et t er  r ea l - t im e   det ec t i o ef f i c i enc y  a nd  t i g ht nes s .   E v e n i n   t he   w or s t   c as e,  t her i s  on l y  on e i nt er s ec t i on c h ec k   f or  ev er y   boun di ng b ox  i eac l a y er ,   w hi c h  f ul l y   r ef l ec t s  t he ad v a nt a ges  of  t he h y br i d b oun di ng b ox  s t r uc t ur e.   C om par ed w i t h R A P I D  a l g or i t hm   [ 4] ,  w h i c h i s  a w i de l y - us ed bo und i n g v o l um e hi er ar c h y   t r ee i m pl em ent at i on b as ed  on O B B ,  t he  i m pr ov ed h y br i B V H  has  s e v er a l  a dv ant ages :     1.   R educ t he  am ount  of  m em or y  us ag e.   B ec a us e c ubi c  b ou ndi ng  box  r eq ui r e s  4  f l oat s ,   an d O B B  o nl y   nee d s  15  f l oat s ,   t he  am ount  of  m e m o r y  t hat   us ed  t o s t or e  t he  bou nd i ng   box es  ar e r e duc ed.     2.   S i m pl i nt er s ec t i on   c hec k .   I t h i s   a l gor i t hm ,   t he  r o ot   n ode  us es   c ub i c   b o und i n b ox   i ns t ea of  O B B .   T he  i nt er s ec t i on  c h ec k s   a m ong  c ubi c   bound i ng  box es  nee f ew er  c al c ul a t i on  oper at i o ns  and  ar e s i m pl er .     3.   R educ e c o l l i s i o n det ec t i o t i m e.  I n r eal - t i m e det ec t i on  pr oc es s ,  t he c ubi c  b oun di ng  box   do es   not   ne ed  upd at es ,   and   c an  qui c k l y   ex c l ud m o s t   noni nt er s ec t i ng  obj ec t s ,   t hus   s a v l ot   of  unnec es s ar y   i n t er s ec t  c hec k i ng t i m e.     2 . 4 . T r ia n g le   I n te r s e c ti o n   C h eck b R e u s i n g  th e  O B B   D at a   I f  t w o bou nd i ng b ox es  ar e i nt er s ec t i ng,   i t  does n t   m ean t hat  t he t w o obj ec t s  r eal l y   c ol l i de,  s o a  f ur t her  i nt er s ec t i on  c hec k  i s  r equi r ed.   W e us e t h e i nt er v al  i nt er s ec t i on  al gor i t hm  [ 25 t o c hec k  w he t her  t r i an gl e f ac et s  i nt er s ec t  or   not .  T he d et ai l  of  t h i s  al gor i t hm  i s  as  f ol l o w :   1.   C al c u l at p l a ne  eq uat i ons   of   t w t r i an gl es   r es pec t i v el y .   I f   al l   v er t i c es   of   one  t r i angl r es i de  i n t he s am e s i de  of  anot h er  t r i a ngl e,  t he t w o t r i a ngl es  do  not   i nt er s ec t .     2.   I f   t hes t w pl an es   i nt er s e c t ,   f i gur out   t he  i nt er s ec t i ng  l i ne  L   of   t w p l a nes .   T hen  es t abl i s h a  c oor d i nat e s y s t em  w hi c has  an  ax i s  p ar al l el i n g t L   3.   C al c u l at e  t he  pr oj ec t i on  i nt er v a l s  of  t he t w o t r i ang l es   i n t he  c oor di nat e s y s t em .     4.   I f  t hes e t w i nt er v a l s  o v er l a p,  t h e t w o  t r i a ngl es  i nt er s e c t.    I n or der   t i m pr ov e t h e e f f i c i enc y   of  t he a bo v al g or i t hm ,  t he O B B - bas e d t r i ang l e   i nt er s ec t i on  c hec k   m et hod  [ 21 ]   i s   a dop t ed.   I t r ad i t i on al   t r i ang l i nt er s ec t i on  c he c k ,   c oor di nat t r ans f or m at i on i s   nec es s a r y ,   w h i c h m eans  t hat  o ne b oun di ng b ox  or  t r i a ngl e m us t  be   r epr es ent e d i n a not her  on e’ s  c oor di n at e s y s t em .   I n our  m et hod,  eac h  l e af  no de i n t h e h y br i B V H  i s  a  r e c t angl e,   w hi c h c o nt a i ns  o nl y   o ne  t r i ang l e.   A t   l eaf   nod es ,   w r epr es ent   eac t r i an gl us i ng  t h c oor d i n at s y s t em   of   i t s   bou nd i ng   box .  B y   r eus i n g t he c o or d i nat e s y s t em  i nf or m at i on,   i t  i s  e as y   t o c a l c ul at t he   poi nt - to - pl a ne   di s t anc e .  I n t hi s   w a y ,  t h e r edun dant  c a l c ul a t i o ns  i n t r i ang l e i nt er s ec t i on c hec k   ar e r educ ed.   T her eb y  t h e ef f i c i enc y   of  c ol l i s i on  det ec t i o n i s   i nc r eas e d.       3 .  E xp er i m en t s   a n d   R esu l t s   T o t es t  t he per f or m anc of  t he i m pr ov ed m et hod,   i t  i s  c om par ed w i t h R A P I D .  T he   al g or i t hm  I  i s   bas e d o n t he  i m pr ov em ent  S ec .   2. 1  t o  2. 3.   A nd  i m pr ov ed  a l gor i t hm  I I  t ak es  al l  t he   i m pr ov em ent s  i nt o ac c ou nt .   T hi s   al gor i t hm   i s   i m pl e m ent ed  us i ng  O p enG gr ap hi c s   l i br ar y   an i s   r u on   m ac hi n w i t h I nt el  C or e2 D uo T 57 50 pr oc es s or ,  2 G B  D D R 2 667M H z  m e m or y  and N V I D I A  G eF or c 8400 M G S  gr aph i c s  c ar d.   W e  t es t  t he  m et hod us i n g t w o s c enes .  T he  f i r s t   s c ene ( F i g ur e   1 c ont ai ns  t w o B ud dhas ,  ea c h of  w hi c h has   180, 845 t r i ang ul ar  f ac et s  and  m ov es  i n a s pec i f i c   t r aj ec t or y .  T he s ec on d s c ene ( F i g ur e   1)   i nc l udes   200  m odel s  w i t h t ot a l l y  1 15, 200  t r i an gl e  f ac et s .   T he  ex per i m ent al   r es ul t s   a r s ho w i F i g ur e   2.   T he  ex per i m ent s   s how   t hat   w h en  t he   num ber  of   i nt er s ec t ed  t r i an gl e gr o w s ,   t h c ol l i s i on d et ec t i on  t i m f or   al l   m et hods  i nc r eas es .  I bot h  t he  t w o - m odel  s c ene   and  t he  m ul t i - m odel  s c ene,  our   i m pr ov ed  h y b r i d  h i er ar c hi c al  c o l l i s i on  det ec t i on m et hod  per f or m s  bet t er  t han  R A P I D .   W h en t h e num ber  of  m odel s  i s  s m al l ,  t he  di f f er enc e bet w een  a l gor i t hm  I  and R A P I D  i s  s l i g ht .  B ut   w h en t her ar a l ot   of   m odel s ,  t h adv ant age  of   i m pr ov ed  A l g or i t hm   I   gr adual l y   app ear s .   T hi s   i s   bec aus t he  i nt er s e c t i on   c hec k   of   i m pr ov ed c ubi c  bou nd i ng  box  i s  f as t er  t han O B B .  A nd t her e i s  no ne ed t o u p dat w h en t he  Evaluation Warning : The document was created with Spire.PDF for Python.
T E L KO M NI K A     I S S N :  1 693 - 6 930       H y br i d H i er ar c hi c a l  C ol l i s i o n D et ec t i o n B as ed  on D at a   R eus e ( J ia n c a i H u )   1081   obj ec t s  s t at e c han ges .  R e us i ng  t he  O B B  d at a f or  t r i ang l i nt er s ec t i on  c hec k  and i nt r od uc i n s pat i o - t em por al  c or r el a t i o c an r educ e r ed und ant  c al c ul at i o n a nd  ha v e s i gn i f i c ant  c ont r i b ut i on t per f or m anc e i m pr ov em ent .             F i gur 1.  T he s c enes  of  B u ddhas  ( l ef t )  and t eap ot s  ( r i g ht ) .               F i gur 2 .  T he ex p er i m ent al   r es ul t s  of  B u ddh as  ( l ef t )  an d t ea pot s  ( r i g ht ) .       4 .  C o n c l u s i o n   T hi s  paper   has   pr es en t ed   a n   i m pr ov ed  h y br i d h i er ar c hi c al  c ol l i s i on  det ec t i o n m et hod  t hat   t ak es   t he  adv ant ages   of   i m pr ov ed  c ubi c   bo und i n box ,   w ei ght e O B B ,   h y br i hi er ar c hi c a l   boun di ng  v o l um t r ee,   an da t r e us i n g.   T he  m et hod   i m pr ov e s   t h ef f i c i enc y   of   c ol l i s i on   det ec t i on.  C om par ed   w i t h  t r adi t i on al  c o l l i s i o n de t ec t i on  al g or i t hm s ,  t he ex per i m ent al  r es ul t s   hav s ho w n   t h at   t hi s   m et hod  has   bet t er   per f or m anc i bot t w o - m odel   s c ene  a nd  m ul t i - m odel   s c ene.       A c k n o w l e d g e m e n ts   T hi s   w or k   w as   s uppor t ed  b y   t he  N a t i o na l   N at ur a l   S c i e nc F ound at i on  of   C hi n ( N S F C )   ( N o.   61 272 200 ,   1 080 501 9) ,   t he  P r o gr am   f or   E x c el l e nt   Y o ung  T eac her s   i H i g her   E d uc at i on  of   G uang don g,  C hi n a ( N o.   Y q2 013 012) ,   t he  F un dam ent a l  R es e ar c h F un ds  f or  t he C ent r a l   U ni v er s i t i es  ( D 215 344 0) ,  t he  S p ec i a l   S u ppor t   P r ogr a m   of   G uangdo ng  P r o v i nc e,  and  t he  P ear l   R i v er  S c i enc &  T ec hno l og y   S t ar  P r oj ec t .       R ef er en ces   [1   J i m enez   P ,  T hom as   F ,  T o rra s   C .  C ol l i s i on det ec t i on:  a s ur v ey .   C om put er s  and G r aphi c s .   2 001 ;   25( 2 ) :   269 - 2 85 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                             I SSN :  1 6 9 3 - 6 930   T E L KO M NI K A     V o l.   1 4 ,  N o 3 S ept em ber   201 6   :   10 77     1 082   1082   [2   S uai N M ,   B ade  A ,   M oham a D .   H y br i C ol l i s i o C ul l i ng   by   B oundi ng  V o l u m es   M ani pul at i on  i n   M as s i v R i gi B ody   S i m ul at i o n.   T E LK O M N I K A   I ndones i an  J our n al   o f   E l e c t r i c al   E ng i neer i ng .   2 01 3;   11( 6) :  3115 - 312 2.   [3   Ca i   PP ,  I ndhu m at hi   C ,  Ca i   YY ,  Z heng   JM ,  G ong   Y , L i m   T S ,   W on g   P C ol l i s i on d et ec t i o n us i n g ax i s   al i g ned boun di n box es .   S i m ul at i on s ,  S er i ou s  G am es   and  T h ei r  A pp l i c at i ons .   20 14 :   1 - 14 .   [4   G ot t s c hal l k  S ,   Li n M C ,  M anoc ha D .   O BBT re e ,   A  hi er ar c hi c al  s t r u c t ur e  f or  r a pi i nt er f er e nc e det e c t i on .   P r oc ee di n gs  of  t h e 23r A n n ual  C onf er en c e on C o m put er  G r aphi c s  and I n t er a c t i v e T ec hni que s .   1996 :  171 - 180.   [5   K l os ow s k i   JT ,  He l d   M M i tc h e l l   J SB ,  So w i z ra l   H , Zi k a n   K E f f i c ie n t  c ol l is io n   det e c t i on us i ng  boundi n g   v ol um hi er ar c h i es   of   k - do ps .   I E E E  T r an s ac t i on s  o n V i s ua l i z at i on an d C om put er  G r a phi c s .   199 8 ;   4 (1 ):  2 1 - 37 .   [6   P al m er   IJ ,   G r im s da l e   RL .   C o l l i s i on  d et ec t i o f or   an i m at i o us i n s p her e - tr e e s C om put er   G r aphi c s   F or um .   199 5 ;   1 4( 2) :  105 - 11 6 .   [7   F i gue i r ed o   M ,  F eenand o   T A n ef f i c i e nt  p ar al l el   c ol l i s i o det e c t i o n al gor i t hm  f or  v i r t u al   pr ot ot y p e   env i r onm ent s .   P r o c ee di ng s   of   t he  10 t I nt er nat i on al   C on f er e nc o P ar a l l e l   and   D i s t r i but e S y s t em s .   2004 :   249 - 256 .   [8   M ac i el   A ,   B o u lie   R ,   T hal m a nn   D .   E f f i c i ent   c o l l i s i o d et e c t i o w i t hi def or m i ng  s pher i c al   s l i di n g   c ont ac t .   I EEE T ra n s a c t i o n s  o n  Vi s u al i z at i on and C om pu t er  G r aphi c s .   200 7 ;   1 3( 3) :  518 - 52 9 .   [9   Lai   KC ,   K an g   SC .   C o l l i s i on  det e c t i o s t r at eg i e s   f or   v i r t ua l   c o ns t r uc t i on  s i m ul at i o n.   A ut om at i on i n   C ons t r u c t i on .   2009 ;   18( 6) :  7 24 - 736 .   [1 0   C hang   JW ,  W ang   WP ,  Ki m   MS .  E f f i c i e nt  c o l l i s i o n det ec t i on us i ng a d ual  O B B - s pher e  bound i n g   v ol um e hi er ar c hy .   C om pu t er  A i ded D e s i gn .   2 010 ;   42( 1) :  50 - 57 .   [1 1   C hr i s t er   E .  R e al - t i m e c ol l i s i on det e c t i o n.   M or gan  K auf m a nn P ubl i s her s   I n c .   2005 .   [1 2   B ade   A ,  Pi n g   CS ,  T anal ol   SH .  C ol l i s i on d et e c t i o f or  c l ot h s i m ul at i on u s i n g bou ndi ng s ph er e   hi er ar c hy .   J ur na l  T e k no l ogi .   2 014 ;   7 5 (2 ):  1 - 5 .   [1 3   S c hw es i ng er   U ,  S i egw ar t   R ,  F ur gal e   P F as t  c ol l i s i on  det ec t i on t hr oug h b ound i ng  v o l um hi er ar c hi e s   i n w or k s p ac e - t i m s pa c f or   s am pl i ng - bas ed m ot i on  pl a nner s P r oc e ed i ng s   of   t he  2 015  I E E E   I nt er na t i o nal  C o nf er e nc e on R obot i c s  and  A ut o m at i on ( I C R A ) .   2015 :   63 - 68 .   [1 4   W u   HY ,  Sh u   Z M , L i u   YG .  S t u dy  bas e d o n hy br i d bo und i ng   v ol um e  hi er ar c hy  f or   c ol l i s i on   det e c t i o n i t he v i r t ua l  m ani pul at or .   A ppl i e d M ec hani c s  a nd M at er i al s .   201 3 ;   4 54 :  74 - 77 .   [1 5   A r babi   E ,  B o u lic   R ,  T hal m an n   D .  F as t  c o l l i s i o n det e c t i on  m et ho ds  f or  j o i nt  s ur f a c es .   J our n al  o f   B i om ec ha ni c s .   200 9 ;   42( 2) :  9 1 - 99 .   [1 6   G u o   AB ,  W an g   Q Z L i   XL R es ear c on  c o l l i s i o det e c t i on a l gor i t hm  o f  t a nk i v i r t ual  bat t l ef i el d P r oc ee di n gs  o f  I nt er nat i on al  C onf er e nc e  on A ut o m at i on .   20 15 :   194 4 - 19 49 .   [1 7   Du   P ,  Z hao   JY ,  Pa n   WB ,  W ang   YG .  G P U  ac c el er at e d  r eal - t im e   c o ll is i on  h a nd l in g i n  v i r t u al  d i sa ss e mb l y .   J o ur na l  of  C om put er  S c i en c and T ec hnol ogy .   2015 ;   30( 3) :  51 1 - 518 .   [1 8   T ang   M ,   M anoc ha   D ,  To n g   RF .  M CCD:  m u l t i - c or e c ol l i s i o det ec t i on   bet w een def or m a bl e m od el s   us i n g f r o nt - ba s ed  de c om po s i t i on.   G r aph i c al  M odel s .   201 0 ;   7 2 (2 ):  7 - 23 .   [1 9   Xi e   K ,   Y ang   J ,   Z hu   YM .   F as t   c ol l i s i on  d et e c t i o ba s ed   on  no s a ug m ent at i o v i r t ua l   s ur ger y .   C om put er  M et hods   and P r ogr am s   i n B i om edi c i n e .   2 007 ;   88( 1) :  1 - 7 .   [2 0   S hen X L,   W u  Q ,  C hen g Y W .  H y br i d C ol l i s i on D et ec t i o n A l gor i t h m  ba s ed o n I m ag e S pac e.   T E LK O M N I K A  I ndone s i a n J ou r nal  o f  E l e c t r i c al  E ngi neer i ng .  2013;  11( 1 2) :   7 159 - 7 165.   [2 1   C hang   JW , K i m   MS . E ffi c i e n t tr i a n g l e - t r i angl e i nt er s e c t i on  t es t  f or  O B B - bas e d c ol l i s i on  det ec t i on .   C om put er s  and  G r a phi c s .   200 9 ;   33( 3 ) :  23 5 - 2 40 .   [2 2   S puy   R.   A dv anc e d G am e D es i gn w i t h F l a s h .  A pr es s .   2010 :   22 4 - 236 .   [2 3   Ma n   RR ,   Z hou   DS ,   Z han g   Q .   A i m pr ov ed   c ol l i s i on  det e c t i on  a l gor i t hm   ba s ed   on   O B B .   C om put er   M odel l i ng a nd N ew  T ec h nol og i es .   201 4 ;   18( 1) :  7 1 - 79 .   [2 4   H ahn   JK .  R eal i s t i c   ani m at i on  o f  r i gi d bo di e s .   C om put er  G r ap hi c s .   1 988 ;   22( 4) :  299 - 308 .   [2 5   M ol l er   T . A  fa s t tr i a n g l e - t r i ang l e i nt er s e c t i on t e s t .   J o ur nal  of   G r aphi c s  T o ol s .   1 997 ;   2( 2) :  25 - 30 .           Evaluation Warning : The document was created with Spire.PDF for Python.