259: Physically Based Modeling, Simulation and Animation


Collision Detection, Distance Computation, and Contact Determination

The problem of checking whether two geometric objects overlap or not is called collision detection.
Because of its complexity, collision detection is often the bottleneck in physical simulation systems.  We will also discuss more complex problems such as distance computation (computing distance between two objects), and contact determination or intersection computation ( finding the first contact point of two moving objects).

The followings are some of results in UNC research group. Please look at:

  • Interactive and Exact Collision Detection for Virtual and Simulated Environments
  • Real-Time Collision Detection Mpegs Based on Hierarchical Incremental Computation
  • IMMPACT: Partitioning and Handling Massive Models for Interactive Collision Detection
  • Fast Proximity Queries for Dynamic Simulation, Virtual Prototyping and Path Planning
  • Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware
  • Real-time Motion Planning Based on Generalized Voronoi Diagram Using Graphics Hardware
  • Randomized Path Planning for a Rigid Body Based on Hardware Accelerated Voronoi Sampling

    Architectural Kitchen Simulation
    574KB MPEG
    This shows a hand interacting with hundreds of objects in a kitchen architectural environment. Note we detect the exact contact points (the hand's fingers turning red indicates contact).
    Composite Simulation
    1.1MB MPEG
    This shows a composite mpeg of the previous sections. It goes over the convex polytope distance tracking algorithm (Lin-Canny), multiple moving bodies algorithm, and non-convex collision detection algorithm. All the simulations in this segment were recoreded in real time. 

    Particle Dynamics

    Simulation of objects with no spatial extent. Most of basic concepts and mathematical and numerical techniques (error estimation, ODE, and DAE) of physically based simulation will be illustrated by using particle dynamics.

    Particle System

    Definition of particle system is not very clear. In physically based modeling, it is often an application of particle dynamics.
    MPEG 405KB 
    Duncan Brinsmead, Alias|Wavefront
    MPEG 554KB 
    Alexis Lamouret, iMAGIS

    Rigid Body Dynamics

    Simulation of "hard" objects. This is the core of the course.
    Quick Time 284KB
    Created by WorkingModel(R)
    Quick Time 798KB
    Created by WorkingModel(R)

    Deformable Objects

    Simulation of deformable objects.

    MPEG 1.5MB
    Facial Animation by Finite Element Method
    Bioengineering Research Group, University of Auckland

    Highly Deformable Objects

    Finite Element Analysis of Large Elastic Deformation
    and Volume Preserving Free-Form Deformation.
    Computer Science Department, UNC-CH

    Space Time Constraints

    MPEG 70KB
    Michael Kass, Andrew Witkin

    Haptic Display

    Using a force feedback device, users can touch and feel virtual objects. Computing feedback force in virtual environment is called force display or force rendering. This technology involves far more than physically based simulation.  The designer of a force feedback system must be familiar with mechanical engineering, control theory, and human factor.

    The application of this technology in computer graphics, especially in geometric modeling, has great potential. See an interesting example: UNC-CH's inTouch.

    Gas and Liquid (Computer and Information Science Department, UPENN)

    Various Numerical and Geometric Methods