Computer Graphics Laboratory, ETH Zurich - People > PhD Students > Denis Steinemann

/ ETHZ / Computer Science / CGL / People / PhD Students / Denis Steinemann / Publications

Publications

	Fast Adaptive Shape Matching Deformations
	Denis Steinemann, Miguel A. Otaduy, Markus Gross
	to appear in ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Dublin, July 7-9, 2008

	Abstract:We present a new shape-matching deformation model that allows for efficient handling of topological changes and dynamic adaptive selection of levels of detail. Similar to the recently presented Fast Lattice Shape Matching (FLSM), we compute the position of simulation nodes by convolution of rigid shape matching operators on many overlapping regions, but we rely instead on octree-based hierarchical sampling and an interval-based region definition. Our approach enjoys the efficiency and robustness of shape-matching deformation models, and the same algorithmic simplicity and linear cost as FLSM, but it eliminates its dense sampling requirements. Our method can handle adaptive spatial discretizations, allowing the simulation of more degrees of freedom in arbitrary regions of interest at little additional cost. The method is also versatile, as it can simulate elastic and plastic deformation, it can handle cuts interactively, and it reuses the underlying data structures for efficient handling of (self-)collisions. All this makes it especially useful for interactive applications such as videogames.


	Tight and Efficient Surface Bounds in Meshless Animation
	Denis Steinemann, Miguel A. Otaduy, Markus Gross
	Journal of Computers & Graphics, vol. 32, issue 2, pp. 235-245, April 2008

	Abstract: This paper presents a fast approach for computing tight surface bounds in meshless animation, and its application to collision detection. Given a high-resolution surface animated by a comparatively small number of simulation nodes, we are able to compute tight bounding volumes with a cost linear in the number of simulation nodes. Our approach extends concepts about bounds of convex sets to the meshless deformation setting, and we introduce an efficient algorithm for finding extrema of these convex sets. The extrema can be used for efficiently updating bounding volumes such as AABBs or k-DOPs, as we show in our results. The choice of particular bounding volume may depend on the complexity of the contact configurations, but in all cases we can compute surface bound orders of magnitude faster and/or tighter than with previous methods.


	Efficient Bounds for Point-Based Animations
	Denis Steinemann, Miguel A. Otaduy, Markus Gross
	Proceedings of the IEEE/Eurographics Symposium on Point-Based Graphics (Prague, Czech Republic, September 2-3, 2007), pp. 57-64

	Abstract: We introduce a new and efficient approach for collision detection in point-based animations, based on the fast computation of tight surface bounds. Our approach is able to tightly bound a high-resolution surface with a cost linear in the number of simulation nodes, which is typically small. We extend concepts about bounds of convex sets to the point-based deformation setting, and we introduce an efficient algorithm for finding extrema of these convex sets. We can compute surface bounds orders of magnitude faster and/or tighter than with previous methods.


	Balanced Hierarchies for Collision Detection between Fracturing Objects
	Miguel A. Otaduy, Olivier Chassot, Denis Steinemann, Markus Gross
	Proc. of the IEEE Virtual Reality Conference, pp. 83-90. Charlotte, NC, USA. 2007.

	Abstract: The simulation of fracture leads to collision-intensive situations that call for efficient collision detection algorithms and data structures. Bounding volume hierarchies (BVHs) are a popular approach for accelerating collision detection, but they rarely see application in fracture simulations, due to the dynamic creation and deletion of geometric primitives. We propose the use of balanced trees for storing BVHs, as well as novel algorithms for dynamically restructuring them in the presence of progressive or instantaneous fracture. By paying a small loss of fitting quality compared with complete reconstruction, we achievemore than one order of magnitude speedup in the update of BVHs.


	Fast Arbitrary Splitting of Deforming Objects
	Denis Steinemann, Miguel A. Otaduy, Markus Gross
	Proc. of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, pp. 63-72. Vienna, Austria. September 2 - September 4, 2006.

	Abstract: We present a novel algorithm for efficiently splitting deformable solids along arbitrary piecewise linear crack surfaces in cutting and fracture simulations. We propose the use of a meshless discretization of the deformation field, and a novel visibility graph for fast update of shape functions in meshless discretizations. We decompose the splitting operation into a first step where we synthesize crack surfaces as triangle meshes, and a second step where we use the newly synthesized surfaces to update the visibility graph, and thus the meshless discretization of the deformation field. The separation of the splitting operation into two steps, along with our novel visibility graph, enables high flexibility and control over the splitting trajectories, provides fast dynamic update of the meshless discretization, and facilitates an easy implementation, making our algorithm scalable, versatile, and suitable for a large range of applications, from computer animation to interactive medical simulation.
	More...


	Hybrid Cutting of Deformable Solids
	Denis Steinemann, Matthias Harders, Markus Gross, Gabor Szekely
	Proc. of IEEE VR 2006. Alexandria VA, USA. March 24 - March 29, 2006.

	Abstract: A central training objective of virtual reality based surgical simulation is the removal of pathologic tissue. This necessitates stable, real-time updates of the underlying mesh representation. Within the framework of a hysteroscopy simulator, we have developed a hybrid cutting approach for tetrahedral meshes. It combines the topological update by subdivision with adjustments of the existing topology. Moreover, the mechanical and the visual model are decoupled, thus allowing different resolutions for the underlying mesh representations. With our method, we can closely approximate an arbitrary, user-dened cut surface while avoiding the creation of small or badly shaped elements, thus strongly reducing stability problems in the subsequent deformation computation. The presented approach has been integrated into a virtual reality training system for hysteroscopic interventions. The performance of the algorithm is demonstrated by examples of intra-uterine tumor ablations.
	More...


	A Hybrid Cutting Approach for Hysteroscopy Simulation
	Matthias Harders, Denis Steinemann, Markus Gross, Gabor Szekely
	MICCAI '05. Palm Springs, USA, October 26 - October 29, 2005.

	Abstract: An integral element of every surgical simulator is the ability to interactively cut tissue. A number of approaches have been suggested in the past, the most important being mesh subdivision by introducing new elements and mesh adaptation by adjusting existing topology. In this paper we combine these two methods and optimize them for our training system of hysteroscopic interventions. The basic methodology is introduced in 2D, a first extension to 3D is presented and finally the integration into the simulator described.


	Efficient Animation of Point-Sampled Thin Shells
	Martin Wicke, Denis Steinemann, Markus Gross
	Eurographics '05. Dublin, Ireland, August 29 - September 2, 2005.

	Abstract: We present a novel framework for the efficient simulation and animation of discrete thin shells. Our method takes a point sampled surface as input and performs all necessary computations without intermediate triangulation. We discretize the thin shell functional using so-called fibers. Such fibers are locally embedded parametric curves crisscrossing individual point samples. In combination, they create a dense mesh representing the surface structure and connectivity for the shell computations. In particular, we utilize the fibers to approximate the differential surface operators of the thin shell functional. The polynomials underlying the fiber representation allow for a robust and fast simulation of thin shell behavior. Our method supports both elastic and plastic deformations as well as fracturing and tearing of the material. To compute surfaces with rich surface detail, we designed a multiresolution representation which maps a high-resolution surface onto a fiber network of lower resolution. This makes it possible to animate densely sampled models of very high surface complexity. While being tuned for point sampled objects, the presented framework is versatile and can also take triangle meshes or triangle soups as input.
	More...


	Generation and Fracturing of Thick Shells
	Denis Steinemann
	Central European Seminar On Computer Graphics, Bratislava, Slovakia, May 9-11, 2005.

	Abstract: In this paper we present methods to generate and animate shells with a pre-defined thickness. Given a polygonal surface mesh, a thick shell is constructed by computing a second, extruded polygonal surface. We introduce methods to simulate deformation and fracture of thick shells in realtime. Mass-spring models are used in this context. A novel simulation framework to generate, animate and interact with shells in real-time has been created. The entire pipeline of shell animation may be handled, starting at the generation of shell, continuing on to deformation and fracture and ending with rigid body simulation of fractured shell fragments.
	More...


	Generation and Animation of Shells
	Denis Steinemann
	Diploma Thesis, ETH Zurich. April 2004.

	Abstract: This diploma thesis presents methods to generate and animate shells. A shell is a surface with a pre-defined thickness. In a first part, generation of thick surfaces is discussed. Given a polygonal surface mesh, a second, extruded surface is constructed, producing a shell. In a second part, methods to simulate deformation and fracture of shells in real-time are introduced. Mass-spring-models are used in this context. A novel simulation framework to generate, animate and interact with shells in real-time has been created. The entire pipeline of shell animation may be handled, starting at the generation of shell, continuing on to deformation and fracture and ending with rigid body simulation of fractured shell fragments. The implementation of this framework is discussed is this thesis.

Last Update: October 27th, 2004