Progressive transmission and multi-resolution collision detection of polygonal meshes in virtual environments

Abstract

Virtual reality applications such as computer games form a large portion of the computing industry. The increasing expectations for immersive and interactive entertainment require fast graphics rendering with a lot of details and high-fidelity physics simulation. Interference and collision detection between general polygonal models, including all those tasks in the simulated motion of solids which cannot penetrate one another, has been widely explored. The most recent works have been focused on increasing the number of collision queries per second to an interactive rate, assuming that the computing resources such as memory, CPU capacity, and network bandwidth are sufficient all the time. However, the performance of a collision detection algorithm may vary in real environments where the available computing resources are not sufficient or are dynamic at runtime. Such an unstable performance directly affects the interactive rate of many applications, which is not acceptable. This drawback has been noticed extensively by practitioners. Little research work has been introduced to systematically solve this problem. One way out of this problem is to use a technique to dynamically adjust the cost of the collision detection (CD) task according to the measurements of available resources. In this dissertation, a solution to the problem is proposed. The problem is analyzed under three different physical environments: single low end computer, clustered multiple-machine setting, and distributed environment. An extensive comparative study of several methods is done in the context of polygonal models. A new approach, "multi-resolution collision detection", is proposed. It performs time-critical and exact interference detection on continuous level of detail (LOD) representations of arbitrary triangle meshes undergoing rigid body motion. The goal of this work is to extend the bounding volume hierarchy (BVH) based collision detection approach from static to dynamic in order to adapt the cost of collision detection to the available resource in either centralized or distributed environments. Several adaptive mesh refinement criteria based on viewing distance, application context, and movement velocity are proposed. Global and local mesh refinement algorithms and a BVH CD algorithm are introduced. They are computationally simple and achieve reliable real-time performance. The complexity of the proposed algorithms is analyzed and proved. Measurements are taken to compare with the analytical results and strong agreements are achieved. The major application areas considered are distributed virtual environments (DVEs) and interactive haptic applications.