ABSTRACT

In this paper, we present a prism-based mesh culling method to improve effectiveness of continuous collision detection which is a major bottleneck in a simulation using polygonal mesh models. A prism is defined based on two matching triangles between a sequence of times in a polygonal model. In order to detect potential colliding set(PCS) of prisms between two polygonal models in a unit time, we apply the visibility test based on the occlusion query to two sets of prisms which are defined from two polygonal models in a unit time. Moreover, we execute the narrow band culling based on SAT(Separating Axis Test) to define potential colliding prism pairs from PCS of prisms extracted as a result of the visibility test. In the SAT, we examine one axis to be perpendicular to a plane which divides a 3D space into two half spaces to include each prism. In the experiments, we applied the proposed culling method to pairs of polygonal models with the different size and compared the number of potential colliding prism pairs with the number of all possible prism pairs of two polygonal models. We also compared effectiveness and performance of the visibility test-based method with those of the SAT-based method as the second narrow band culling. In an experiment using two models to consist of 2916 and 2731 polygons, respectively, we got potential colliding prism pairs with 99 % of culling rate.

KEYWORD

Continuous Collision Detection, Culling, Visibility Test, Separating Axis Test

REFERENCES(17)open

  1. [confproc] Yoo-Joo Choi / 2005 / self-CD Interactive Self-collision Detection for Deformable Body Simulation Using GPUs / AsiaSim : 187 ~ 196

  2. [confproc] Gottschalk, S / 1996 / OBBTree:A hierarchical structure for rapid interference detection / Proc.of SIGGRAPH : 171 ~ 180

  3. [confproc] Redon, S / 2004 / Interactive and continuous collision detection for avatars in virtual environments / Proc. of IEEE Virtual Reality

  4. [jounal] Larsson T / 2006 / A dynamic bounding volume hierarchy for generalized collision detection / Computers and Graphics 30 (3) : 451 ~ 460

  5. [confproc] Min Tang / 2009 / C2A: Controlled Conservative Advancement for Continuous Collision Detection of Polygonal Models / Proc. of International Conference on Robotics and Automation japan 2009

  6. [thesis] Mirtich, B. V / 1996 / Impulse-based Dynamic Simulation of Rigid Body Systems

  7. [jounal] Barequet G / 2001 / Efficiently approximating the minimum-volume bounding box of a point set in three dimensions / J Algorithms 38 : 91 ~ 109

  8. [jounal] Teschner, M / 2005 / Collision detection for deformable objects / Computer Graphics Forum 19 : 61 ~ 81

  9. [confproc] Ehmann S / 2000 / Accelerated proximity queries between convex polyhedra using multi-level Voronoi marching / Proc.of IEEE/RSJ International Conference on Intelligent Robots and Systems : 2101 ~ 2106

  10. [jounal] Ehmann, S / 2001 / Accurate and fast proximity queries between polyhedra using convex surface decomposition / Computer Graphics Forum(In Proc.of Eurographics 2001) 20 (3) : 500 ~ 510

  11. [confproc] Redon, S / 2000 / An algebraic solution to the problem of collision detection for rigid polyhedral objects / Proc.of IEEE Conference on Robotics and Automation

  12. [jounal] Abdel-Malek, K / 2000 / Swept volumes:foundations,perspectives,and applications / International journal of Shape Modeling

  13. [confproc] Schwarzer, F / 2002 / Exact collision checking of robot paths / Workshop on Algorithmic Foundations of Robotics(WAFR)

  14. [jounal] Zhang. X. Y / 2006 / Interactive continuous collision detection for rigid non-convex:polyhedra / The Visual Computer(In Proc.of Pacific Graphics 2006) 22 : 9 ~ 11

  15. [jounal] Zhang. X. Y / 2007 / Continuous collision detection for articulated models using Taylor models and temporal culling / AGM Transactions on Graphics(TOG) 26 (3)

  16. [report] N.K. Govindaraju / 2003 / Fast self-collision culling in general environment using graphics processors

  17. [confproc] Min Tang / 2008 / Interactive Continuous Collision Detection between Deformable Models using Connectivity-Based Culling / ACM Symp.on Solid and Physical Modeling : 25 ~ 36