Non-contact Breathing Analysis 3D Scanning and Printing Deformation Object Control Deformable Object Collision Visual Bioinformatics
Animation Computer Graphics Advanced Computer Graphics Game Design Shader and GPU Programming
Deformable Collision Detection and Response

Collision Handling for Free-Form Deformation Embedded Surface
S. Jung, M. Hong, and M. Choi

Abstract: Recently, free-form deformation (FFD)-based simulation has received a lot of attention to achieve real-time animation of complex objects, and many researches have improved the accuracy of modelling complex material property. Previously, a freeform deformation axis aligned bounding box (FFD AABB) was proposed to approximate the FFD-embedded surfaces. Using FFD AABB, an efficient update of bounding box is achieved with balancing between accuracy and computational cost. The authors extended the FFD AABB with a more conservative collision handling method between FFD AABBs to deal with the cases that the nodes on one side of FFD AABB are out-of-plane. In addition, the authors adopted a broad-phase culling algorithm to cope efficiently with both self-collision and inter-collision using parallel spatial hashing.

Paper [PDF]   [Project Page]


Optimization of Collision Handling based on Differential Thresholds of Human Perception
Shaila Abraham and Min-Hyung Choi

Abstract: An efficient collision handling mechanism is essential for most computer animation and to achieve realistic yet efficient animations we need to consider human perception in these animation systems. Current states of art collision handling algorithms do not consider human perception in depth, particularly in differentiating thresholds of various collision parameters. Yet the human perception plays a significant role in the quality of perceived animation when multiple collisions are presented in an animated scene. The responsiveness of the objects at the right time and the right behavior makes the animation system look natural. In this paper we describe an approach, which approximates objects by using an interruptible detection algorithm to proximately test for collisions between different objects. Based on the inputs from the user study made we are able to adjust the various parameters in our collision detection algorithm and were able to get considerable speed up.

Paper [PDF]   [Project Page]

A Fast Culling Scheme for Deformable Object Collision Detection Using Spatial Hashing
S. Jung and M. Choi

Abstract: Fast culling for collision detection is one of the key components in dynamic simulation. While culling for collision detection works well when there is a smaller number of collisions compared to potential collision pairs in a given scene, it can be inefficient when most objects are close to each other and exact collision detection are required. Culling process must be simple and fast with minimal overheads. We describe a fast culling scheme using a nobel spatial hashing method with inner-voxel culling(a culling process among primitives in each voxel). Previously, spatial hashing techniques have been used for culling, and exact collision detections were performed between all primitive pairs in a voxel. But due to hash collisions and the inefficiency of fixed grids, unnecessary exact collision checks are mandated, which substantially hamper the culling that consists of two levels: primitive level and element level based on 26-discrete oriented polytopes and surface normal. In addition, our algorithm is parallelized to utilize multi-core processors. Our method performs both inner-collision and self-collision in a linear runtime on the input primitives. Moreover, our method needs no preprocessing and has no assumption or limitations on topology and accuracy.

Paper [PDF]   [Project Page]

Free-Form Deformation Axis Aligned Bounding Box
S. Jung, M. Hong, and M. Choi

Abstract: We present a new efficient collision-handling technique of free-form deformation (FFD) of an embedded surface. By adapting FFD, modeling deformation has been substantially simplified to make possible interactive rate animation of a deformable object even for a complex embedded mesh. However, the lack of effective collision detection and resolution schemes for an FFD-embedded surface hinders the overall performance and often becomes a bottleneck. Most existing collision handling techniques can be directly applied to an FFD grid for fast computation, but surface approximation error would be apparent and it could cause noticeable visual artifacts. On the other hand, applying collision detection and resolution techniques directly to the embedded surface is extremely expensive and can obliterate the viability of real-time FFD simulation because the embedded surface has a high resolution in most cases. We present a fast collision detection and resolution method for the embedded surface in an FFD-enhanced simulation maintaining the approximation error of the embedded surface. Our techniques for detection and resolution provide an ability to balance speed and quality.

Paper [PDF]   [ Project Page]

Balanced Spatial Subdivision Method for Continuous Collision Detection
S. Jung, M. Choi

Abstract: A new optimization technique is presented for the spatial subdivision of a three-dimensional (3D) geometric model to improve the overall performance of continuous collision detection between deformable objects. Spatial subdivision methods decompose a spatial geometric region into a number of predefined voxels (the storage of 3D finite space, or a ¡®cell¡¯) that helps to achieve close to linear performance in collision detection. An optimal performance can be achieved when the subdivision is evenly dispersed. If there must be any subsequent re-subdivision the overall performance is substantially hampered due to the overwhelming cost of the re-subdivision and its associated overhead. Typically a spatial hashing technique is chosen to map a large number of 3D cells into finite voxels. But previous spatial hashing approaches are unable to maximize spatial subdivision method because they do not provide an optimal solution when there are conflicts between changing dispersion patterns of cells for deformable objects and the cost of re-subdivision. The problem of uneven concentration of cells is especially prominent when a deformable object is squeezed and far-stretched. Our method can balance them in a simple way to maximize the performance of spatial subdivision.

Paper [PDF]   [Project Page]

An Adaptive Collision Detection and Resolution for Deformable Objects Using Spherical Implicit Surface
Sunwha Jung, Min Hong, Min-Hyung Choi

Abstract: A fast collision detection and resolution scheme is one of the key components for interactive simulation of deformable objects. It is particularly challenging to reduce the computational cost in collision detection and to achieve the robust treatment at the same time. Since the shape and topology of a deformable object changes continuously unlike the rigid body, an efficient and effective collision detection and resolution is a major challenge. We present a fast and robust collision detection and resolution scheme for deformable objects using a new enhanced spherical implicit surface hierarchy. The penetration depth and separating distance criteria can be adjusted depending on the application specific error tolerance. Our comparative experiments show that the proposed method performs substantially faster than existing algorithms for deformable object simulation with massive element-level collisions at each iteration step. Our adaptive hierarchical approach enables us to achieve a real-time simulation rate, well suited for interactive applications.

Paper [PDF]   [Project Page]