Research

Physical Simulation

Generative Deformation: Procedural Perforation for Elastic Structures
Authors: Shane Transue, Min-Hyung Choi

Description: Procedural generation of elastic structures pro- vides the fundamental basis for controlling and designing 3D printed deformable object behaviors. The automation through generative algorithms provides flexibility in how design and functionality can be seamlessly integrated into a cohesive pro- cess that generates 3D prints with variable elasticity. Generative deformation introduces an automated method for perforating existing volumetric structures, promoting simulated deforma- tions, and integrating stress analysis into a cohesive pipeline model that can be used with existing consumer-level 3D printers with elastic material capabilities. In this work, we present a consolidated implementation of the design, simulate, refine, and 3D print procedure based on the automated generation of heterogeneous lattice structures. We utilize Finite Element Analysis (FEA) metrics to generate perforated deformation models that adhere to deformation behaviors created within our design environment. We present the core algorithms, automated pipeline, and 3D print deformations of various objects. Quantitative results illustrate how the heterogeneous geometric structure can influence elastic material behaviors towards design objectives. Our method provides an automated open-source tool for quickly prototyping elastic 3D prints.
Download Links: [ PDF ] [ YouTube ]
Interactive Control of Deformable-object Animations through Control Metaphor Pattern Adherence
Members: S. Transue, M. Choi

Description: In this paper we present an adaptive and intuitive methodology for controlling the localized deformations of physically simulated objects using an intuitive pattern-based control interface. To maximize the interactive component presented in this approach we consolidate existing feedback mechanisms in deformable-body control techniques to provide intuitive editing metaphors for stretching, bending, twisting, and compressing simulated objects. The resulting movements created by these control metaphors are validated using imposed behavior evaluation and the effectiveness of this approach is demonstrated through interactively generated compound movements that introduce complex local deformations of objects in existing physical animations.
Download Links: [ PDF ] [ YouTube ]
Controllable simulation of deformable objects using the heuristic optimal control method
Members: Hongjun Jeon, Min-Hyung Choi

Description: Physically-based simulation techniques have been widely used in computer graphics because it creates highly realistic animation. However, due to the limitation of passive simulation and simplified modeling methods, it is very difficult to control the behavior of deformable objects directly. Ability to control the behavior of deformable objects is a very important feature for an effective simulation. In this paper, we present a novel interactive method and interface techniques for controlling the behavior of physically-based simulation of deformable objects. In our approach, an animator can select any part of the deformable structure and drag it to the desired location then our system automatically generates the motion path using the heuristic optimal method. Animators can focus on the final pose of the controlled object, without worrying about how to achieve the goal pose. Based on the displacement distance and the previous trajectory of the intended node, the optimal path generator computes the required control parameters that steer the intended node to the desired goal position while preserving the style of the original motion and minimizing the energy to achieve the goal pose. The goal oriented control scheme enables users to interactively control and redirect the motion of deformable objects and guarantees that the edited motion is physically conforming.
Download Links: [ PDF ] [ YouTube ]
Deformable Object Behavior Reconstruction Derived through Simultaneous Geometric and Material Property Estimation
Members: S. Transue, M. Choi

Description: We present a methodology of accurately reconstructing the deformation and surface characteristics of a scanned 3D model recorded in real-time within a Finite Element Model (FEM) simulation. Based on a sequence of generated surface deformations defining a reference animation, we illustrate the ability to accurately replicate the deformation behavior of an object composed of an unknown homogeneous elastic material. We then formulate the procedural generation of the internal geometric structure and material parameterization required to achieve the recorded deformation behavior as a non-linear optimization problem. In this formulation the geometric distribution (quality) and density of tetrahedral components are simultaneously optimized with the elastic material parameters (Young's Modulus and Possion's ratio) of a procedurally generated FEM model to provide the optimal deformation behavior with respect to the recorded surface.
Download Links: [ PDF ] [ YouTube ]
Collision Handling for Free-Form Deformation Embedded Surface

Authors: S. Jung, M. Hong, M. Choi

Description: 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.
Download Links: [ PDF ]
Optimization of Collision Handling based on Differential Thresholds of Human Perception

Authors: Shaila Abraham, Min-Hyung Choi

Description: 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.
Download Links: [ PDF ]
A Fast Culling Scheme for Deformable Object Collision Detection Using Spatial Hashing

Authors: S. Jung, M. Choi

Description: 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.
Download Links: [ PDF ]
Free-Form Deformation Axis Aligned Bounding Box

Authors: S. Jung, M. Hong, M. Choi

Description: 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.
Download Links: [ PDF ]
Balanced Spatial Subdivision Method for Continuous Collision Detection

Authors: S. Jung, M. Choi

Description: 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.
Download Links: [ PDF ]
Enhanced Second-Order Implicit Constraint Enforcement for Dynamic Simulation

Authors: M. Hong, S. Welch, S. Jung, M. Choi, D. Park

Description: This paper proposes a second-order implicit constraint enforcement method which yields enhanced controllability compared to a first-order implicit constraints enforcement method. Although the proposed method requires solving a linear system twice, it yields superior accuracy from the constraints error perspective and guarantees the precise and natural movement of objects, in contrast to the first-order method. Thus, the proposed method is the most suitable for exact prediction simulations. This paper describes the numerical formulation of second-order implicit constraints enforcement. To prove its superiority, the proposed method is compared with the firstorder method using a simple two-link simulation. In this paper, there is a reasonable discussion about the comparison of constraints error and the analysis of dynamic behavior using kinetic energy and potential energy.
Download Links: [ PDF ]
Interactive Motion Control of Deformable Objects Using Localized Optimal Control

Authors: Hongjun Jeon, Min-Hyung Choi

Description: In this paper we present a novel interactive method and interface techniques for controlling the behavior of physically-based simulation of deformable objects. The goal of our research is to provide users an ability to control the motion which appears physically correct, preserves the moving pattern of the original motion, and satisfies goals for a deformable object. In our approach, a user can select any part of the deformable structure, called control points, and can define target poses by moving control points. A user also can define target poses then our system automatically generates the motion path to achieve the target pose. With this technique patient specific organ simulation can be achieved by using a stream of image data. A series of sectional images can be the target poses. The optimal path generator computes the required control parameters that steer the intended node to the desired goal position while preserving the moving pattern of the original motion. It guarantees that the edited motion is physically conforming and natural.
Download Links: [ PDF ]
Physics-Based Deformable Object Simulation in Ubiquitous Computing Environments

Authors: Sunhwa Jung, Hongjun Jeon, Min-Hyung Choi

Description: Ubiquity is a trend and vision of modern computer science. Planting physics-based deformable object simulation, which provides realism to animation and medical simulation, into ubiquitous computing environments will make a step forward to envisioned realism in the ubiquity of computation. The essential components of embedding physics-based deformable simulation to ubiquitous computational environments are adaptive simulation paradigm and data driven simulation techniques. In this paper we examine the feasibility of physics-based deformable object simulation in ubiquitous computing environments and present the possible applications of ubiquitous deformable object simulation.
Download Links: [ PDF ]
Implicit Constraint Enforcement for Rigid Body Dynamic Simulation

Authors: Min Hong, Samuel Welch, John Trapp, Min-Hyung Choi

Description: The paper presents a simple, robust, and effective constraint enforcement scheme for rigid body dynamic simulation. The constraint enforcement scheme treats the constraint equations implicitly providing stability as well as accuracy in constrained dynamic problems. The method does not require ad-hoc problem dependent parameters. We describe the formulation of implicit constraint enforcement for both holonomic and non-holonomic cases in rigid body simulation. A first order version of the method is compared to a first order version of the well-known Baumgarte stabilization.
Download Links: [ PDF ]
An Adaptive Collision Detection and Resolution for Deformable Objects Using Spherical Implicit Surface

Authors: Sunwha Jung, Min Hong, Min-Hyung Choi

Description: 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.
Download Links: [ PDF ]