TELKOM NIKA , Vol. 11, No. 6, June 20 13, pp. 3115  ~ 312 2   e-ISSN: 2087 -278X           3115      Re cei v ed  Jan uary 18, 201 3 ;  Revi sed Ma rch 3 0 , 2013;  Acce pted April 16, 2013   Hybrid Collision Culling by Bounding Volumes  Manipulation in Massive Rigid Body Simulation      Norhaid a  Mo hd Suaib *1 , Abdullah Bade 2 , Dz ulkifli Mohamad 3   1,3 F a culty   of Co mputin g, Unive r siti T e knologi   Mala ysi a , 813 1 0  UT M Skudai, Johor, Mala ys i a .  2 School of Scie nce & T e chnol og y, Univ ersiti  Ma la ysi a  Sab a h , Kota Kina bal u, Sabah, Ma la ysi a .  *Corres p o ndi n g  author, e-ma i l : haid a @utm. m y * , a bad e0 8 @ yah oo.com, dzulkifl i@utm. m y       A b st r a ct     Collis io n dete c tion is an i m p o rtant aspect i n  ma ny  real-ti m e si mulati on  envir on me nts.  Due to its  nature of high Com p utation i n volv ed,  collis i on  detection c an c ontribute t o  the bottleneck on t he syst em  involv in g l a rg e  nu mb er of  inter a cting  ob jects.   This p a p e r foc u ses  on fi nd ing  opti ons to  effic i ently c u l l  aw ay   obj ect pa irs th at are  not  like l y to col l i de  in  larg e- scal e  dy na mic r i gi d-b o d y si mu lati ons  invo lvi ng  n-b o dy   obj ects.  T he  ma in  id ea  is to  perfor m  ti me  cr itical c o mp utin g  co ncept by ma ni pul at io n of  pote n tial  b oun din g   volu me tech niq ues.  In or der t o  take a d va nta ge of a  fa st col lisio n test a nd  a more  accurat e  resu lt, a hybr i d   collis io n cull in g appr oac h ba sed on sp her e - or-Dops w a s  used.  Base d on in itial res u lt s, this approa ch   show s a potent ial a dapt ation t o  a massive ri g i d bo dy si mul a tion.      Ke y w ords : col lisio n cul lin g, collis io n detecti on, rigi d bo dy, bou ndi ng vo lu me, b oun dary r epres entati o n      Copy right  ©  2013 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  Colli sion det ection i s  usually an integral  p a rt to many real -time and in teractiv e   appli c ation s .  There are m any appli c ati ons th at re lie s on  colli sion  detectio n  su ch a s  in the f i eld   of virtual reali t y, computer  game s , anim a tion, training , enginee ring  and medi cal  simulatio n .  With   these va st areas of  collisi on dete c tion  appli c atio n s , it is unde rsta ndabl e that collision  dete c tion  research i s   still an  active  research area.   Despit e the advances in techno logy, coll ision  detection  still contri bute s  to the syste m  bottlene cks for mo re th an thirty years [1].  In many re al-time and i n te ractive  appli c ations ,  colli si on dete c tion  is a p r e - requi site for  reali s tic  syste m  re sp on se.   A simpl e  ex ample i s  i n volving a  com p uter g ene rate d bou nci ng  b a ll.    Colli sion  bet wee n  the  bal l and  any  ob stacl e s ne ed  to be  d e tected so that  the  system  can   gene rate a p p rop r iate  re spon se li ke t he directio n  and mo me ntum after i m pact.   Coll ision   detection and collisi on resp onse usually are carried  out successively [2].  The m a in  purpose  of colli sion detection is  to ensure that ther e  will not be any two  obje c ts that o c cupy the  sa me space at t he same ti me .  This i s  eq ui valent to ho w obje c ts b eha ve   in the real  worl d–two o b ject s cann o t  fit into  the sam e  spa c e at exactly  the sa me t i me .    Dep endin g  o n  the level   of accu ra cy  that is   need ed o n  the  a pplication, co llision  dete c tion  pro c e ss  can  either si mply flag interse c tion(s)  bet we en obje c ts, o r  it might produ ce detail ed  repo rt on the  event like time of conta c t, point of  contact and int e rpe netration  depth.  The firs t  type of detection ca n be  carri ed out in  a very sh ort  time but doe s not yield m u ch i n form ation   about the  coll ision.  Ap plication like co mputer  gam e s  that requi re s ap proxim ate but fa st coll ision   detectio n  u s u a lly ado pts t hese type s o f  colli sion  de tection  app ro ach e s.   On  the oth e r han d,   more computation n eeds t o  be  carried  out in  order t o  get  detailed co llisi on i n formation needed  for a mo re  seriou s a ppli c ation a s  in m edical sim u la tor.  The r efo r e there is  ge nerally trade -offs   betwe en sp e ed and a c cu racy in collisi on detectio n .   At the same time, issue s  like real-ti m e  perfo rman ce,  efficiency an d robu stne ss need to be a d d re ssed [1].  Perha p s the  most ad apted  appro a ch in  tr ading  spe e d  and accu ra cy was introdu ced by  Hub bard a s   can  be  se en  in ma ny re search  pap ers co ncerni ng  colli sion  dete c tion.  It works  based on th e idea of time-critical com puting: co lli si on detectio n  and re sp on se for intera ctive   grap hics ap pl ication s  ca n be improve d  by usi ng a two-ph ase pro c ess:  broa d-ph ase a nd na rrow- pha se [3].  Collision  cullin g, which in e s sen c e deal s with quickly removin g  obj ect pairs that  are   Evaluation Warning : The document was created with Spire.PDF for Python.
                               e-ISSN: 2 087-278X   TELKOM NIKA   Vol. 11, No. 6, June 20 13 :  3115 – 3 122   3116 less likely to collide i s  very much rel a ted to  the  broa d-pha se  level, as wi ll be discu ssed  thorou ghly in the next secti on.  Th is will  be the focu s  of this pape r.  The  re st of this p ape r  will  be o r g anize d a s  follows :  related work , partic u larly involving  boun ding  vol u me i n  b r oa d - pha se   collisi on  cullin g  will  be  discu s se d in S e ctio n I I  followe d by   th e   idea of hybri d  collisi on cul ling in Section III.   Experimental layout  will be outlined in Section IV.     Section V de als with the result an d discussion, while  Section VI co nclu de s this p aper.       2. Related Work  As mentio ne d in p r eviou s  sectio n, a   two-pha se  approa ch i s  usu a lly ad opted in   minimizi ng  collision  test s due to  the  nature of  collision  dete c tion that is  comp utationa ll y  intensive.   G enerally, the  broa d- pha se colli sion dete c tion  a c ts  m o re  li ke  a filter that id entifies  only pairs of  objects that  are m o re li kely to co llide.  This  step is responsi ble to cull  away  unrel ated  pai rs i n  the whole  collisi on  detection pr ocess, and  thus  synonymous with  the  t e rm   ‘colli sion  culli ng’.  These identified pai rs are t hen fe d to the narro w-p h a s e colli sion d e tectio n for   further collisi on te sts  (ple ase  refe r to   [4] for a n  el aborate di scussion  on  co llision  dete c tion  approa che s  a nd appli c atio ns).   Different approaches  can  be implem ent ed duri ng col lision culling  pr ocess  such as the  brute fo rce  (all-pai r te st),  swee p an d  prun e  (S aP)  and  hierarchi c al  ha sh tabl e [4].  Meth od  impleme n ted  in this  study i s  ba se d o n  b oundi ng  volu me techniq u e  whi c h i s  ve ry conventio n a l  with the first  approa ch.  Convention a l b oundi ng  volu mes that a r e  comm only used in the bro a d - phase level will be present ed next.    2.1. Conv entional Boundi ng Volumes  Boundin g  vol u me i s  o ne  of the mo st  comm only u s ed b r oa d-p h a s e  colli sion  d e tection  approa ch in   simulatio n s i n volving n-bo dy obje c ts .   Based  on it s  popul arity, we will n e xt ou tline   some of the p opula r  bou ndi ng volume s.  Boundin g  vol u me  algo rith ms  en comp a s ses techniq ues like b o u nding  sphe re , Axis- aligne d boun ding box (AA BB), oriented  boundin g  bo x (OBB) and  discrete o r ien t ation polytop es  ( k - D O P s)  (s ee  F i g u r e  1) .  O r ie n t ed -D ops  (o r- Do ps),  a co mbinatio n of OBB an d k-Do ps wa s  introdu ce d to overcome the  update cost  of k-Dop s  [5] (sh o wn as Fi gure 2 ) .           Figure 1. Con v entional Bou nding Volu me s       Figure 2. Orie nted-Dop s  o r  also  kno w n a s  or- Dop s      2.2. Boundin g  Volumes: Simplicit y   Versus  Accu r a c y   Based   on previous re se a r ch,  th ese  b oundi ng  volu mes had  it s own advanta ges and   disa dvantag e s .  In short,  a simple b o undin g  volu me req u ire s   less co mputa t ion in terms o f   con s tru c tion,  update s  an d tests.  Th erefo r e it  is  expecte d tha t  simulation s or appli c ati ons  utilizing  simpl e  bounding volumes  c an  give higher frame rates but  with the  cost of more fal s e  positive te st outcom e .  A false  po sitive colli si on  occu rre d when  col lision te st ba sed on  bou ndi ng   volume gives a positive result (c olli sion detected) but the actual  object di d not  collide.  This  is  due to la rg e  empty co rne r s cau s ed  by  simple  bou nd ing volume.   On the  other hand, a  mo re   accurate  bou nding  volume  re quires mo re  com putati on a n d  mo re  time, resulting in  le ss fra m e   rates.   Th e p r eviou s  b oun ding volu me s ca n be  r oug hly arrang ed  according  to  simpli city versu s   accuracy a s  in Figure 3.  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       Hybrid  Colli si on Culli ng by  Bounding Vol u m e s Manipulation... (Norhaida Mohd Suaib)  3117       Figure 3. Simplicity versu s   Accu ra cy       2.3. Time-Cri tical Collision Detection  The ide a  of  time-critical  collision  dete c ti on, as int r o duced by  Hu bbard [3], ha s be en  adapte d  by  many researche r s.   Altho ugh it i s   quit e  impo ssible   to incl ude  all  refe ren c e s  i n  this  category, some  of highly   relat ed work  will be  discussed here.   Most  of the approaches use  boun ding vol u me hie r arch y (BVH) in o ne way o r  an other.  One o f  them utilize d  the tree cal l ed  averag e-distri bution tree o r  ADB-tre e  [6] that  is a combinatio n o f  bounding v o lume hie r a r chy  (BVH) with  an estimated  probability of  colli sion  occurrence  to reduce co llisi o n tests.  S phere- tree  was used for time-cri tical  collisi o n detection  by  at least two resear chers;  sphere-tree  on  redu ce d mo d e l for d e form able o b je cts  [7] and  sph e r e-t r ee  with  close s t featu r e map s   (CF M s)  applie d to refinable  collisi o n respon se [8 , 9].   An AABB-tree with  re duced defo r m able mod e l was  also  used for self-colli sion cullin g [10].  An event-based  scheduli ng that adapt ively prioriti zi ng   colli sion te sts and p e rfo r m s  collisi on te sts at  differe nt time interv al wa s int r od uce d  by Com i ng  and Staa dt [ 11, 12],  whil e a BV H  wa s u s e d   with  certificates th at indi cate a b se nce  of se lf- colli sion [10].     2.4. Total Co st Be nchmar king  Total co st  be nchm arkin g   (Equation 1)  for colli sion  d e tection  that  wa s p r op ose d  by [13]   will be used as a basis:     T = Nu x  Cu  + Nv  x  Cv  + Np x  Cp + Co             (1)     Whe r e:   T: total c o s t  func tion for interferenc e  det ec tion,   Nv: numbe r o f  boundin g  volume pai r ove r lap test s  Cv: cost of testing a pai r of boundi ng vol u mes fo r overlap   Np: is the nu mber p r imitive pairs tested  for interferen ce,   Cp: co st of testing a pai r of primitives for interfere n ce,  Nu: numb e r o f  boundin g  volumes u pdate d ,  Cu: co st of averag e bou ndi ng volume up date,  Co: indi cate s co st for one ti me pro c e s sin g , where ne cessary   Ho wever, not  all param ete r s mu st be i n volved;  they depen d on the problem  and the type  of  colli sion invol v ed.      3. H y brid Co llision Cullin g Method  The m a in  pu rpo s e  of colli sion  culling i s  to  red u ce  colli sion te st s by i dentifying a nd  cullin g away unne ce ssary  pairs.  The b a si c colli si o n  detectio n  pro c e ss  whi c h u s ually is  ca rri ed  out in  a t w o-pha se  pro c e s s (bro ad -ph a se  an d n a rrow-pha se ) i n spires a  two - pha se  colli si on  cullin g pro c e s s in ord e r to a c hieve a  simp le, fast and re liable collisio n detectio n .  The culling  p r ocess  will b e  ba sed  on t he bo undi n g   volume ap proach.  Since  there a r e  quite a num b e r of pop ular  boun ding vol u me, a que sti on will ne ed s to be add re ss is the type  o f   boun ding  volumes that i s   suitabl e for th at pu rpo s e.    If there  are  su itable  can d id ates, i s  the r e   any  way that perf o rmance of the  culling process can be i m proved?  There are two main issue s  that need to be co n s id e r ed in the qu estion ab ove.  On the   one h and, a  simple  and fa st colli sio n  te st is n eed ed  but on the  other h and, it a l so n eed s to  be   Si m p le r B V   M o re  ac c u ra t e   BV   Evaluation Warning : The document was created with Spire.PDF for Python.
            TEL K 3118 relia b their  to le a into t fals e    4. E x st ag e one  a the e a se t and  O orien and  e   4.1.  H Duo  C Micr o usin g 4.2.  E suit a b part  w 4.2.1 the  c use d   1346      T 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1     next  e differ obje c capt u         K OM NIKA    V b le .  T he c a n simpl e  repr e a d to false c o he possi bilit y d e t ec tion .    x perimental  For th e  m e ,  we are ta r a not her, like  mpty sp ace  Since m o t  of  simp le  e O BB) whic h  ted  D ops  ( O e ac h  ob je c t   w H ard w a r e U s A ll of the  C P U  E7 400  o soft Windo w g  the sa me h   E xperiment s There ar e b l e  boun din g w as  to expe r   . Part I  Four set s c ommonl y u s to bo un d 1 5 ver t ic es as   T able 1. List   List  of  1  [ h 2  [t o 3   4   5   6   7   8   9   0  1  2  3  4  5  [p e [upper [uppe [low e r R [low e r [le f [rig h [uppe r [upper R [low e r [low e r R [lef t [Rig h Average  e xperim ents ent velo city  c ts .  Figure  u ring th e  av e V ol. 11, No.  6 n didate s  f o r  s e se ntation  a n o lli sion de te c y  of manipul a La y out  m om ent we   a r getin g a  sui in a crowd e is  not too la r o vem ent of  V e xperim ent s  w ar e  most  c r- Dop s ). At  t w as  as sume d s ed   exp e rime nt s @2. 8 0G Hz   w s  XP P r of e ardware co n s   e  m a inly tw o g  volumes t h r iment on th e s  of  experim s e d  b oun din g 5  different  o b listed in T a b of 3D Obje c 3D O b jects  F iles   h ead.tri]   o rso.tri]   e lvis.tr i]   RightL eg.t ri]  rLeft Leg.tri]   R ightLeg.t ri]  r LeftLeg .tri]   f tFoot.tri]   h tFoot.t ri]  r LeftA rm.tri ]   R ightA rm.t ri]  r LeftArm. t ri]   R ightArm.t ri]  t Hand.tri]   h tHand.t ri]    b o u nding v o , all obje c ts  assi gne d  a s 4 sho w s  on e r a ge  co nstr u    6 , June 20 1 3 s imp l e a nd  f n d  t e st s.    H o c tion d ue to   a ting a m o r e a re ex perim e tabl e BV to  e d environ m e r ge ) but co ul d V E inh abitan t w here we t e c ommonly f o t his stage, a  d  to repres e n s  outli ned h e processo r  w e ssio nal S P 3 n figuration a s o  exp e rime n t h at could b e e  perfo rma n c ents were  i n g  volumes  – b je ct s.   Obj e le 1.   c ts Us ed    Total Verte x   542  841  74  706  706  706  706  122  122  1346   1346   1138   1138   589  589  o lum e  const r are ra ndo ml s  in rigid b o d e of  the ex p u c t ion time, t 3  :  3115 – 3 1 f ast collisi o n  o wev e r, it i s   large empty  e  ac cu r a te  b o nting o n   diff e be u s ed  on   e nt. Theref o d  su ppo rt re a t s coul d  not  b e st four  diffe o und in the  singl e boun d n t an avata r . e re w e re  do n w ith 2 GB  R A 3 .  Different  s  will be expl t s involved:  e  used fo r t h c e of the p r o p n volved in t h –  sph e r e ,   A A cts used  a r e Figur e r uc tion time s y trans form e d y motion, s o p erim ents c o here a r e th r e 1 22   t e st  a r e  sp h ty p i c a l  f o r  t h cor n e r s.   T h o undi ng vol u e rent BVs  to many avat a o re, a BV th a a l-time ap pli c b e anticipat e rent types o l iterature, pl d ing volume    n e on a CPU  A M onbo ard,  types of b o ained in the  the first  par t h e hybrid co l p osed hybri d h e firs t part.   A BB, OBB,  k e  based o n   p e  4. Sample  e s  for thes e o e d insid e  a v o  that there  w o nd uc te d  o n e e other  exp          e - h ere and   AA h e s e ‘ s impl e’ h e r efore, it i s u me so that i  be  us ed   o n   a rs and  prob a t fits  an av a c ation is ver y e d mo st of t h f BVs   (sphe us  a n o t he r   t wa s as sig n e ru nnin g  on  a and NVidia  o undin g  vol u nex t  sub- se c t  w a s  de sig n l li sion cullin g d  method.   All four ex p k -Do p s an d  o p o i nt-clo ud,  r   e xper iment  u sph e re s   bj ect s  wil l  b e olume (box)  w ill be collis n  bo undin g   s eri m ents th a - ISSN: 2087 A BB, mainly  d  b o undi ng v o s  d e sirable t o t coul d red u c the avatar.  A ab ly very cl o a tar (me anin y  much pref e h e time, we  d re,  AABB, k t ype of BV  e d  for each  o a n Intel®  C o Ge F o rc e 2 1 u mes were  t c ti o n .   n ed to ide n t i g ,  and the s e p eri m ents in v o r- D o ps tha t r an ging fro m u s i ng  b o un d i e  logged.   F with differe n i o ns am ong  s pheres.   B e a t were c o nd u -278X   d ue  to   o lume  o  loo k   c e the   A t this   o se to   g that  e rred.  d esign   -Do p s  cal l ed  o bjec t,  o re™2   0 with   t e s ted  i fy the   e co nd  v o l ved  t  wer e    74  to    i ng  or the   n t with   th e s e   e sides  u ct e d .   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       Hybrid  Colli si on Culli ng by  Bounding Vol u m e s Manipulation... (Norhaida Mohd Suaib)  3119 The first experiment was  conduc ted to test collisi o n time using different types of  boundi ng  volumes  whil e the se con d  experime n t wa s co ndu ct ed to test the  average  upd ate time.  Results  from the s e  experim ents  were fed i n to the To tal  Co st Ben c h m arking fu nction.  The l a st   experim ent was im pleme n ted to  roug hly sho w  th e ov erall  perfo rm ance ba se d  on fra m es-p e r - se con d  (FPS) count s.    4.2.2. Part  II  The second  part of this t e st deal s  with fu rthe r exp e rime nts on  the pro p o s ed  hybrid   colli sion  culli ng meth od.   As m ention ed e a rlie r, th e hybri d   colli sion  culling i s  a  two - ph a s e   colli sion culli ng  process d e sig ned  to achieve  a simp l e , fast and  re liable  collisi o n dete c tion.   The  scene involve s  a co mbinati on of ran dom ly moving  objects a nd som e  static obj ects insid e  a bo x  (se e  Fig u re  5 a  and  5b for  a sam p le of l oade d obje c t s ).  Simila r to  experim ents  in Part I, obje c ts  are  allo wed  to go throug h othe r obj e c ts  but w ill  simply ch ange  dire ction  on ce they  hit the   boun dary of t he box to e n s ure that n o   obje c t will  wa nder off the b ound arie s.   Once collisi o n is   detecte d, a chang e of col our will visua lly i ndicate collision b e tween two obj e c ts an d relat e d   information will be logged.   While  experi m ents in P a rt  I only involved rel a tively small number of  obje c ts, the p r opo se d met hod will b e  tested ag ain s t conve n tional  techni que s in  a massive ri gid   body simul a tion und erg o in g rigid - bo dy simulation.       Figure 5a. Sample Experim ent usin g 50  Obje ct s wit h o u t  B V     Figure 5b. Sample Experim ent usin g 50  Obje cts with  Boundin g  Sp here       5. Results a nd Analy s is  5.1. Part I  C o ns tr uc tio n  T i me . Con s truction  times  for ea ch  obj ects u s ed  (a s p r eviou s ly  listed in  Table 1 )  wa s  recorded a n d  repeate d  10 0 times. Average con s tru c tion time is sh own in Fig u re  6.        Figure 6. Effects of Sele cting Differe nt Switchi ng un de r Dynami c  Co ndition       Num ber of detected collisions .  Initially,  accumul a ted  numbe r of col lision s  dete c ted wa s  recorded for  100, 200, 30 0 ,  400 and 50 0  frames a s  in dicate d in Ta ble 2 and Fig u re 7.   0 1000 Sphere AABB O BB k ‐ Dops orDops Av e r a g e   c o ns truction   time Evaluation Warning : The document was created with Spire.PDF for Python.
            TEL K 3120 Ta Bou n g Volu Sp h AA O B k- D o or- D     mea s inclu d     sin c e the v a Whe r Re s u belo w             K OM NIKA    V ble 2. Nu m b n din g   mes    10 0  2 h ere  36 7  5 BB 15 9  2 B B  o ps  D op s  82  71  59  9 8 Average   s ure for  per f d ed for i ndic a     Total Co s e  colli sio n   t e s a lues of  Np  a   T = Nu x    r e  T: total c o Nv: num b Cv :  cost   o Nu: num b Cu:  co st   o Co: indi c a   u lts from  ex p w .  Calculati o S A O k - o r V ol. 11, No.  6 ers of Colli si   2 0 0  Frame s   300  5 7 2  872  2 5 5  387  13 4  9 9  8 6  207  165  140    fram es pe r  s f or ma nc e ,  t h a tive purpos Figure  8 s t Be nchm a r s t s  cond uct e a nd  C p   we r e Cu  + Nv  x   C o s t  func tion  f b e r  o f  bound i o f testing a  p b er o f  bound o f averag e  b a t e s co st  f o r  p e r iment s f o o ns  for tot a l  c T a BV  Nv  phere  5239 5 A ABB 5239 5 O BB  5239 5 - Dops 5239 5 r -Do p s 5239 5    6 , June 20 1 3 ons Dete cte   400    50 0 109 1  144 1 497 625 308  230  202  395 316 267 s e c on d (FP S h e fps valu e s es.  Figu re  8 8 . Frames  p e r kin g .    A  mo d e d in  th ese   e e  not in clud e d C v +  C o   f or interfere n i ng  vo lu me   p p ai r of boun d ing volumes  b ou ndi ng vol u one ti me pr o o r  the firs t 5 c os t were b a a ble 3. Nu m b Cv  5  0.00024   5  0.00024   5  0.100106   5  0.000249   5  0.001567   0 100 10 0 3 0 fps Numb e A v 3  :  3115 – 3 1 d  0   F S ).    A lth ough s  for  differe n 8  illustrates t h   e r  second fo r d ified b ench m e xpe r iment s  d  and total c n ce det ectio n p ai r ove r lap  t d i ng vol u me s u pdate d ,  u me up date, o cessing, in  t 00 frame s   a a sed on Eq.   2 b ers of Colli s Values  Nu  104790  0. 0 104790  0.0 104790  0.0 104790  0.0 104790  0.0 T otal   number   of   k ‐ Dops 0 0 0 500 e r   of   frames   t e v er ag e   F 1 22   igure 7. Nu m  fram es  per  n t types of  b h e fps value s r  the firs t  50 0 m a r ki ng fun c d o  not i n vo l os t func tion    n ,  t est s   s  (ov e rl a p )   t his ca se ,  t h e a re summar i 2  mentioned  s i ons Dete ct e Cu C o 0 0012  135.0 49377  90.63 50053  367.6 00124  574.2 00784  369.4 0 2000 100 collisions N Numb e e sted F PS k A O          e -   m ber of collis second (FP S b oundi ng v o s .    0  frames  c tion ba se d  o l ve primitive  only involve : e  const r u c ti o i zed in Tabl above.   e d  Total  Cost  o   783  160.212 781  5277.36 315  10857.7 866  600.328 002  533.635 100 200 300 400 500 N umber   of   fr a e r   of   co k ‐ Dops A ABB O BB - ISSN: 2087 i ons d e tecte S ) is not a d o lume s  us ed o n Eq. 1  wa s t e st s.    The r :     ( o n co st   e  3 and Fi g 6  4  2  8  6  500 a mes llisions Sp h AA OB k ‐ D -278X   d  efinite   wer e   s  us ed   r ef ore,  ( 2)  g ure 9   h ere BB B D ops Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   e-ISSN:  2087 -278X       Hybrid  Colli si on Culli ng by  Bounding Vol u m e s Manipulation... (Norhaida Mohd Suaib)  3121     Figure 9. Total co st based  on first 500 frames      The total  co st benchma r ki ng p r o c e ss  wa s al so  ca rried  out for  1 000 a nd 5 0 0 0  frame s   simulatio n s.   Experime n ts involving 10 00 fram es  g a ve unexp e ct ed result wh ere th e value  of  total cost for k-Dops  skyrock eted above OBB.  Based on the  first 500 fram es t e sted, AABB and  k-Dop s  gave  frame rat e s  way belo w  int e ra ctive fr am e rates  (~60 fps), an d this  might cont rib u te   to the lapse.  These two b oundi ng volu mes are excl uded in the 5 000 frame s  test.  Result s for  the final test (500 0 fram es) are  as exp e c ted; sp he re  gave the lowest co st, follo wed by o r -Do p s  (se e  Figu re 1 0 ).            Figure 10. To tal Cost ba se d on  Shortliste d BV and 5000 F r ame s   Figure 13. Fp s Perfo r man c es for  Differe nt BV Approa ch  for 500 O b jects (first 10 0 frames)    5.2. Part II  Hybrid  Colli si on Culli ng.   Re sults from the experim e n ts in  Part I show that com b ination  of sp here a n d  or-Dop s b oundi ng volu mes  offer th e pote n tial fo r an  optio n t o wa rd s a  bet ter  colli sion  culli ng process.  Hybrid  colli si on culli ng tha t  is a combi n ation of boun ding sphe re  and  Oriente d -Di s crete O r ientati on Polytope s  (Or-Dop s)   wa s imple m ente d  on m u ltiple  *.tri obje c ts a s   outlined in  previous  se ctio n.  Figure  11  sho w s  hybri d  colli sion  cul ling implem e n ted on a  pai r of  collidin g o b je ct – thi s  i s  d one to  pu rpo s ely hig h light  the con c ept.   It wa s the n  tested  agai n s t  conve n tional  boun ding vol u me app ro ach.          Figure 11. Hy brid Collisi on  cullin g–note t he  Pairs  with Sphere a nd o r -Dop s      Figure 12. Hy brid Collisi on  Culling  on 350  Obje cts  0 20000 To t a l C o s t TotalCost 0 200000 S … O … or … To t a l   Cos t   fo r   5000   Fr ames TotalCost 0 20 1 14 27 40 53 66 79 92 FPS Frame   number FPS   perf ormance No   BV Sphere Or ‐ Dops Evaluation Warning : The document was created with Spire.PDF for Python.
                               e-ISSN: 2 087-278X   TELKOM NIKA   Vol. 11, No. 6, June 20 13 :  3115 – 3 122   3122 Initial result based o n  th e frame s  p e r se con d  (fp s ) of 50 0 obj ects  und erg o i ng rigi d  motion i s   sh o w n  as Fig u re   13.  Simul a tion  without  bo undin g  volum e  (th u s no  col lision  dete c tio n   employed) was  i m plem ent ed  as a c ont rol experiment.  If hybrid co llision culling  is employed  on   a particular o b ject of intere st (label ed as ‘1ObjHyb rid’ in the graph ),  the frame rates ca n rea c h  to  nearly the pe rforman c e of the co ntrol ex perim ent,  sim ilar to the perf o rma n ce of sphere bou ndi ng   volume.  Fps perform ance dropped if all objects  em ployed hybrid collision  cull ing, but it stil l  outperfo rm s t he h o mog e n eou s o r -Do p s  im pleme n tation.  An oth e r  app roa c h   wa s al so  tested   whe r e  a t w o-pass te st  wa s e m ploye d  (l abele d  a s  ‘S eq Sp -O rD’  i n  the  graph ).   Th e first te st to  identify pairs  that are li kely  to  collide  ba sed  on   bo un ding sp here  t e sts.   Th ese pairs are   sen t   to   the second pass  where  or-Dops te st s  will be conducted.  It  show s an improved perform a nce if  all obje c ts ne eds to empl o y  the hybrid collision  cullin g method.       6. Conclusio n   Re sults from  the experim e n ts  shows th at the hybrid  colli sion  culli ng metho d  shows the  potential of an option for a better colli sion culli ng t e ch niqu e for massive rigid  body simula tion  comp ared to   the ho mog e n eou s b oun din g  volum e s.    Ho wever a  d e tailed te st li ke th e total  cost  ben chma rkin g test need s to be don e to sy stem aticall y  evaluate this re sult.       Ackn o w l e dg ment   This  re sea r ch is supp ort ed by Unive r siti  Teknolo g i  Malaysia  (UTM) an d Min i stry of  High er E d u c ation (MO H E ) , in  colla bo ration  with  Re sea r ch  M ana gement Ce ntre (RMC),  UTM.  This pa pe r is finan cially sup porte d by Resear ch  University Grant (R UG ) Prog ram, Tier 2  ( r e s e a r c h  gr an t 0 5 J 21 ) .       Referen ces   [1]    Q Avril, V Gouranto n , B Arnal di. Fast Co llis i on C u ll in g i n  Lar ge-Sca l e  Environm ents  Using GPU   Mapp ing F u nction.  Euro gra phi cs Sympos iu m  on Para lle l Graphics a nd Vis u ali z a t i on.  2 012.   [2]    D Harmo n, D  Panozz o , O Sorkin e, D Z o ri n. Interference - a w are  ge ome t ric model in g.  ACM T r ans.   Graph.  201 1; 3 0 : 1-10.   [3]    PM Hub bar d. Col lisi on  Det e ction f o r Int e ractive Gra p h ics Ap plic atio ns.  IEEE Transactions on  Visua l i z a t i on a nd Co mputer  Graphics . 19 95 ; 1: 218-23 0.  [4]    NM Suaib, A Bade, D Moh a mad.  Co llis io n Detectio n: A Survey of  Techni ques a nd App licati o n .   Coll isio n Detec t ion for Rea l -T i m e Grap hics:  Series of T e ch niq ues.  Joh o r; UT M. 2009; 1: 1-18.   [5]    NM Suai b, A Bade, AM Z i n,  T M T  Sembok.  Oriented co n v ex poly h e d ra  for collis io n de tection i n  3 D   computer a n i m ati on.  Proce edi ngs of the 4th Internati o n a l Conf erenc e  on Computer  Graphics and   Interactive T e chni ques i n  Aus t ralasi a and S o utheast Asia K ual a Lump u r, Mala ysi a : ACM ,  2006.   [6]    J Klein, G Zachmann.  T i me-c ritical c o ll isio n  detectio n   usin g  an  aver ag e-c a se  appr oac h . Procee din g s  of the ACM s y mposi u m on Vi rtual rea lit y  s o ftw a r e a nd tech nol og y Osaka,  Japa n: ACM, 2003.   [7]    C Mendoz a, C O'Sullivan.  An Interruptib l e  Algorit hm fo r Collis ion D e tection b e tw een Defor m a b l e   Objects . Intern ation a l W o rksh op on V i rtual  Real it y   an d Ph ysic al Sim u lati on (VRIPHYS' 05). 200 5: 73- 80.   [8]    T Giang, C O'Sulliva n .  Cl osest Feature  Maps for Time- C ritica l Co llisi on H and lin g . International  W o rkshop o n  Virtual R eal it y   and Ph ys ical S i mulati on (VRI PHYS' 05). 200 5: 65-72.   [9]    T   Giang, C O ' Sulliva n . Virtu a l R eal it y  I n te racti on  an d P h y s ical  Simu la tion: Ap pro x im ate col lisi o n   respo n se usi n g  closest feature  maps.  Comput . Graph . 2006;  30: 423- 43 1.  [10]   J Barbic, DL Ja mes. Subspac e self-col lisi on  culli ng. ACM T r ans. Graph. 2 010; 29: 1- 9.  [11]   DS Comin g , OG Staadt. Stride sched uli ng fo r time-critical c o llis io n detecti on VRST : AC M. 2007.   [12]    DS Comi ng, OG Staadt.  Stride Sche du ling for  T i me-Critical C o ll isi on Detecti on.   T he F ourt h   Internatio na l S y mp osi u m o n  3D D a ta P r ocessi ng, Vis ualiz atio n an d   T r ansmissio n  (3DPVT ' 08).  Atlanta, Georg i a, 2008.   [13]   GVD Bergen.  Coll isio n Detec t i on in Interacti v e 3D Envir o n m ents.  Elsevier.  2004.   Evaluation Warning : The document was created with Spire.PDF for Python.