Interactive Visualization and Collision Detection using Dynamic Simplification and Cache-Coherent Layouts

Ph.D. Thesis on

Interactive Visualization and Collision Detection using Dynamic Simplification and Cache-Coherent Layouts

Sung-eui Yoon
Univ. of North Carolina at Chapel Hill

Pdf file (218 pages)
Talk slide


Recent advances in model acquisition, computer-aided design, and simulation technologies have resulted in massive databases of complex geometric models consisting of more than tens or hundreds of millions of triangles. In spite of the rapid progress in the performance of CPUs and graphics processing units (GPUs), it may not be possible to visualize or perform collision detection between massive models at interactive rates on commodity hardware. In this thesis, we present dynamic simplification and cache-coherent layout algorithms for interactive visualization and collision detection between large models, in order to bridge the gap between the performance of commodity hardware and high model complexity.

Firstly, we present a novel dynamic simplification algorithm that efficiently handles massive models for view-dependent rendering while alleviating discontinuity problems such as visual poppings that arise when switching between different levels of detail (LODs). We describe an out-of-core construction algorithm for hierarchical simplification of massive models that cannot fit into main memory. We also apply dynamic simplification to collision detection and introduce a new conservative distance metric to perform fast and conservative collision detection between massive models. Our approach is conservative in that it may overestimate the set of colliding primitives, but never misses any collisions.

Secondly, we present novel cache-oblivious layout algorithms for polygonal meshes and hierarchies to minimize the expected number of cache misses for a wide variety of applications. Our layout algorithms only assume that runtime applications have random, but cache-coherent access patterns. However, we do not require any knowledge of cache parameters such as block and cache sizes. We demonstrate benefits of our layout algorithm on three different applications including view-dependent rendering, collision detection, and isosurface extraction.

We have implemented our algorithms on a desktop PC and are able to achieve significant improvements over previous approaches and obtain interactive performance (more than 10 frames per second) on view-dependent rendering and collision detection between massive and complex models.

Related publictions:

  • Cache-Efficient Layouts of Bounding Volume Hierarchies
    Sung-Eui Yoon and Dinesh Manocha
    Computer Graphics Forum (Eurographics), volume 25, issue 3, 2006
  • Cache-Oblivious Mesh Layouts
    Sung-Eui Yoon, Peter Lindstrom, Valerio Pascucci, and Dinesh Manocha
    ACM Transaction on Graphics (ACM SIGGRAPH), 2005
  • Fast Collision Detection between Massive Models using Dynamic Simplification
    Sung-Eui Yoon, Brian Salomon, Ming Lin, and Dinesh Manocha
    ACM SIGGRAPH/Eurographics Symposium on Geometry Processing 2004, Nice, France.
  • Quick-VDR: Interactive View-Dependent Rendering of Massive Models
    Sung-Eui Yoon, Brian Salomon, Russell Gayle and Dinesh Manocha
    IEEE Transaction on Visualization and Computer Graphics 05 (and IEEE Visualization 04)
  • Interactive View-dependent rendering with Conservative Occlusion Culling in Complex Environments
    Sung-Eui Yoon, Brian Salomon and Dinesh Manocha
    IEEE Visualization 2003, Seattle, USA