Radial View Based Culling for Continuous Self-Collision Detection of Skeletal Models


Sai-Keung Wong,   Wen-Chieh Lin,    Chun-Hung Hung,     Yi-Jheng Huang,     Shing-Yeu Lii


National Chiao Tung University, Taiwan, ROC













Figure 1: The major procedures of our method: (a) Input of a deforming mesh with a skeleton; (b) Clustering triangles based on the skeleton; (c) A radial view test from an observer primitive (an enlarged view of the dashed region in (b)); (d) Culling results. Potentially colliding triangles are colored as red; (e) Our method works better for observer points lying inside the mesh, but it can tolerate some observer points lying outside the mesh. Negatively oriented triangles are colored as blue. [Please click to enlarge the images]



We present a novel radial-view-based culling method for continuous self-collision detection (CSCD) of skeletal models. Our method targets closed triangular meshes used to represent the surface of a model. It can be easily integrated with bounding volume hierarchies (BVHs) and used as the first stage for culling non-colliding triangle pairs. A mesh is decomposed into clusters with respect to a set of observer primitives (i.e., observer points and line segments) on the skeleton of the mesh so that each cluster is associated with an observer primitive. One BVH is then built for each cluster. At the runtime stage, a radial view test is performed from the observer primitive of each cluster to check its collision state. Every pair of clusters is also checked for collisions. We evaluated our method on various models and compared its performance with prior methods. Experimental results show that our method reduces the number of the bounding volume overlapping tests and the number of potentially colliding triangle pairs, thereby improving the overall process of CSCD.





  author    = {Sai-Keung Wong and  Wen-Chieh Lin and  Chun-Hung Hung and  Yi-Jheng Huang and Shing-Yeu Lii},

  title         = {Radial view based culling for continuous self-collision detection of skeletal models},

  journal   = {ACM Transactions on Graphics (ACM SIGGRAPH)},

  volume  = {32},

  number  = {4},

  page = {114},

  year      = {2013}



BibTex File


Movies: RVBC Method [ 51 MB] , Robustness Tests [ 43 MB]


Data (Rope, Urchin and Box) and Binary (Windows Only).


Source Code:

Methods based on Heaviside and Bernstein (source code) for computing the sign of cubic polynomials.


Last update: 21st August, 2013