max planck institut
informatik
informatik
Coordinator: Stefan Gumhold
Investigators: Matthias Fenchel, Martin Isenburg, Philipp Jenke, and Carsten Stoll
This project started in November 2004 and investigates subjects related to animations of three-dimensional content. A 3D animation represents the geometry of a moving or deformable 3D object such as an agile animal or a liquid in motion. Previously, 3D animations have mostly been synthesized automatically through physically based simulations and procedural modeling or handmade by a skilled designer time-step by time-step.
In recent years significant advances have been made in all kinds of 3D acquisition technology: computer tomography, magnetic resonance imaging, ultrasonic imaging and structured light or multi-stereo based 3D video scanning. This will demand for a wide range of different processing tools for acquired 3D animation in the near future. The work in this project is devoted to the generalization of processing techniques for static geometry to the dynamic case. Theoretical and practical issues are investigated and the basic principles for the efficient representation and processing of 3D animations are developed.
An underlying technical problem of 3D animation processing is the tremendous size of the acquired or calculated raw data. On the other hand forces the inertia inherent to our physical world a large amount of redundancy into dynamic geometry. Therefore is the most elementary processing task the elimination of this redundancy from the representation.
Two further fundamental issues play an important role in 3D animation processing. The first one is the ability of a change in topology, which arises whenever a deformable model splits apart or grows into itself. The geometrical description of the object becomes singular at these critical points in time; a surface representation for example becomes non manifold. This demands for more general data structures with flexible incremental update operations. The second issue concerns changes in the parameterization. The efficiency of most processing algorithms builds on well behaved parameterizations, i.e. mappings to 2D with low distortion or surface tessellations with nicely shaped elements. The surface of a deformable model can drastically shrink or expand over time, such that also a well behaved parameterization must be dynamic.
The project builds on mesh processing work for static models. On the one hand there is the work on mesh compression as described in the section "Optimized Connectivity Compression". On the other hand there are works on streaming mesh compression and processing as described in the next section and on multi-resolution modeling as described in section 0.1.2. Further research directions of work in progress are described in section 0.1.3.
Investigators: Martin Isenburg and Stefan Gumhold
One major bottleneck for 3D animation processing is the huge amount of data that has to be handled. A solution to this is a streaming access to the dynamic geometry. In cooperation with Peter Lindstrom and Jack Snoeyink we developed streaming mesh processing approaches for the static case to facilitate fast compression and simplification of gigantic polygonal meshes.
Standard schemes for compressing polygonal surface meshes or polyhedral volume meshes first construct an explicit representation of the mesh connectivity and then traverse it with some deterministic strategy [TG98,GS98,Ros99]. This implicitly assumes that the compressor is allowed to reorder the mesh elements as it sees it. Hence, current mesh compressors take the entire mesh as input, construct temporary data structures in the size of the mesh, and produce a completely reordered compressed mesh.
 |
In this project we investigate compression schemes that can preserve the original element order of a mesh. They incrementally construct mesh connectivity as mesh elements are input and immediately compresses them. This compression scheme is mainly intended for meshes in streaming formats (see Figure 0.1), which interleave vertices and polygons or polyhedrons and finalize vertices that are no longer used. The availability of such compression schemes enables the compression of gigantic meshes on-the-fly without ever having the entire mesh in memory and without ever having to reload parts of the mesh as required by our earlier approach that is currently the only alternative for large meshes [IG03].
We have previously shown that streaming approaches allow highly IO-efficient compression and simplification [ILGS03]. Currently we investigate how these approaches can be extended to other geometric data, such as tetrahedral volume meshes and point cloud data. While the extension of a streaming format from surface meshes to volume meshes is trivial, the extension of the compression scheme is not. Furthermore, it is currently not clear how to extend the concept of finalization to a streaming point format.
For more efficient compression we will employ a small delay buffer within which the compressor is allowed to locally reorder mesh elements. The memory requirements of the compressor are proportional to the width of the streaming mesh and the size of the delay buffer. Again, for tetrahedral mesh compression this will be similar to the triangle mesh case, while the re-ordering strategies for point compression also depend on which predictive compression technique we use.
Investigator: Stefan Gumhold
Mesh simplification and refinement algorithms allow to build hierarchical representations of irregularly sampled 3D surfaces. These representations can be used in a variety of ways - for example to accelerate rendering in a view-dependent manner. Two complementary goals need to be traded off when building a hierarchical mesh model. On the one hand should the coarse approximations be as accurate as possible with a tight error control. On the other hand should the hierarchy be able the adapt to the application dependent demands on the resolution as locally as possible. Some of the known algorithms allow for tight error control [XESV97,CCMS97,KS99], some optimize for adaptability [Hop97,KL01,Paj01], but no known algorithm does both.
|
|
| (a) | (b) |
In [Gum05] we developed an algorithm with a good trade-off between adaptability and tight error control. For this we worked in the dual domain and used edge-removal operations instead of edge-collapse operations to build the hierarchy, whose basic structure is a forest over the faces. This approach also results in a polygonal - not triangular - mesh hierarchy, which has interesting properties already in the progressive setting as described in [Gum04]. A one-to-one correspondence between faces from a coarse approximation with the faces in the original model allows for a very efficient error control. Figure 0.2 a) illustrates a view-dependent mesh adaptation. In b) the view-frustum is illustrated by the pink pyramid and all polygons outside the view-frustum are rendered in wire frame mode. The resolution is adapted to the distance and surface orientation with respect to the camera.
As this project has only recently started, we also present some preliminary results, which point to future work.
Investigators: Carsten Stoll and Stefan Gumhold
|
3D Animations are 3-manifolds in 4D space-time and therefore it is hard to imagine and visualize the complete structure. One approach is to visualize trajectories of points on the dynamic surface of the 3D animation. For this we have developed efficient rendering approaches for stylized curves. The skeleton of a stylized curve is the trajectory of a surface point. To visualize additional attributes like speed or changes in the local coordinate system additional visual attributes are introduced. For this the curve is blown up to a generalized cylindrical shape. The profile does not have to be circular but can for example be rectangular as well. This allows three further visual attributes: the curve width, the curve color and the orientation of the profile. Figure 0.3 shows an example of stylized curves with a rectangular profile, where all visual attributes are varied.
One important issue for the rendering of stylized curves is the rendering speed. Tessellation of the underlying geometry results in a number of rendering primitives that can hardly be handled even for a small number of stylized curves. We developed rendering algorithms that are based on a combination of splatting and ray casting. Only a small number of primitives are splatted and have to be transmitted to the graphics processing unit. The ray casting is implemented in the fragment shader allowing for very fast performance through the highly parallelized architectures of modern GPUs. In this way the performance is close to the performance of rendering simple curves.
There are a lot of other applications of stylized curves for the visualization of complex molecules, knitted fabrics, vector and tensor fields, etc.
Investigators: Philipp Jenke, Stefan Gumhold
|
|
| (a) | (b) |
In recent years, fluid simulations based on the Navier-Stokes equation have become an important tool to generate 3D animations. 3D scanning techniques became capable of acquiring fluids in motion only recently. This facilitates a comparison between simulation and experiment for the first time. We used an optical 3D scanner acquiring with a rate of 40 depth images per second. The scanner setup and the provided reconstruction software limited us to a quiet simple experimental setup. A fluid of high viscosity was run down a declining planar surface. A resulting scan is sown in Figure 0.4 a), which has a significant amount of noise. In order to reproduce the same fluid dynamics with a state-of-the-art simulation we developed a scheme to adjust the simulation parameters iteratively to the scanned experiment. This adjustment is based on a comparison between the scanned and the simulated fluid. Because of our basic experimental setup we could restrict the comparison to a height field representation of the fluid as shown in Figure 0.4 b). The results do not completely validate the simulation approaches. They rather produce a similar behavior but do not exactly reproduce reality.
Investigators: Matthias Fenchel and Stefan Gumhold
|
The central organ of the human being is the heart. The examination of the heart is particularly difficult as it is always in rapid motion. The latest MRI imaging techniques are just fast enough to allow for a dynamic acquisition of the heart with a low temporal and spatial resolution. This makes the extraction of a surface model very difficult. In this work we develop efficient segmentation techniques for dynamic surface models.
In the analysis phase we extract a probability distribution for the surface boundaries. This stage combines region growing with a voting-based local cluster analysis. In the second step a smooth surface is extracted from the probability model. Here we employ a generalization of MLS surfaces to the 4D space-time in which the dynamic surface lives. Figure 0.5 shows some preliminary result for the segmentation of the left chamber of the heart. Only one time slice of the time series is shown. The resulting surface model can be used for a variety of diagnostics. One can for example easily track the chamber volumes over time.