Publications

[Complete list of all entries in BibTex format]

Stable 6-DOF Haptic Rendering with Inner Sphere Trees

Rene Weller, Gabriel Zachmann

Based on our new geometric data structure, the inner sphere trees, we present a fast and stable uniform algorithm for proximity and penetration volume queries between watertight objects at haptic rates. Moreover, we present a multi-threaded version of the penetration volume computation for time-critical haptic rendering that is based on separation lists and the novel notion of expected overlapping volumes. Finally, we show how to use the penetration volume to compute continuous contact forces and torques that enable a stable rendering of 6-DOF penalty-based distributed contacts.

Published:

Proceedings of International Design Engineering Technical Conferences & Computers and Information in Engineering Conference (IDETC/CIE), San Diego, USA, 30 August - 02 September 2009. Virtual Environments and Systems - 2009 Best Paper Award. [BibTex]

Files:

     IDETC/CIE Presentation (ppt, 15MB)
     Simulation Video wmv, mov
     Interaction Video wmv, mov
     Bones Video wmv, mov
     758 Video wmv, mov
     Pin in Hole Benchmark Video wmv, mov

Links:

Project Homepage

Visual Computing for Medical Diagnosis and Treatment

Jan Klein, Ola Friman, Markus Hadwiger, Bernhard Preim, Felix Ritter, Anna Vilanova, Gabriel Zachmann, Dirk Bartz

Diagnostic algorithms and efficient visualization techniques are of major importance for pre-operative decisions, intra-operative imaging and image-guided surgery. Complex diagnostic decisions are characterized by a high information flow and fast decisions, requiring efficient and intuitive presentation of complex medical data and precision in the visualization. For intra-operative medical treatment, the pre-operative visualization results of the diagnostic systems have to be transferred to the patient on the operation room table. Via augmented reality, additional information of the hidden regions can be displayed virtually. This state-of-the-art report summarizes visual computing algorithms for medical diagnosis and treatment. After starting with direct volume rendering and tagged volume rendering as general techniques for visualizing anatomical structures, we go into more detail by focusing on the visualization of tissue and vessel structures. Afterwards, algorithms and techniques that are used for medical treatment in the context of image-guided surgery, intra-operative imaging and augmented reality, are discussed and reviewed.

Published:

Computers & Graphics, Vol. 33, Issue 4, August 2009, pp. 554 -- 565. [BibTex]

Files:

Preliminary version of the paper (pdf),

A Unified Approach for Physically-Based Simulations and Haptic Rendering

Rene Weller, Gabriel Zachmann

Since the visual feedback and effects of today’s games have become extremely mature, it will be more and more important for games to provide realistic feedback to other senses, such as our haptic sense. On the hardware side, this has become possible in recent years by the advent of first inexpensive haptic devices on the consumer market, such as the Falcon from Novint. Research on force-feedback devices and algorithms has been done over 10 years, and has only fairly recently been introduced to games. However, while there is a large body of research on how to render forces given a collision and its contact information, the computation of the latter for massive models is still a challenge. First of all, this is due to the much higher effort to compute contact information. Second, this is due to the update rates that are necessary for haptic rendering, which need to be much higher than for visual rendering, i.e., 250–1000 Hz. And third, defining the contact information such that continuous contact forces can be derived is not always obvious. Therefore, one of the major challenges in haptic rendering for games is the computation of continuous forces at haptic rates. A solution to this challenge can also be utilized to do physically-based simulation of rigid bodies, which has become increasingly popular in games over the past few years. In this paper, we take advantage of the fact that in rendering haptic forces, as well as in most real-time applications that involve physically-based simulation, an absolutely correct determination of the forces acting on the virtual objects is not necessary.

Published:

ACM SIGGRAPH Video Game Proceedings , New Orleans, USA, August 2009. [BibTex]

Files:

     Siggraph Paper (pdf, 4MB)
     Siggraph Presentation (ppt, 25MB)
     Simulation Video wmv, mov
     Interaction Video wmv, mov
     Armadillo Video wmv, mov
     Screwdriver Video wmv, mov
     Bozzle Video wmv, mov

Links:

Project Homepage

Inner Sphere Trees for Proximity and Penetration Queries

Rene Weller, Gabriel Zachmann

We present a novel geometric data structure for approximate collision detection at haptic rates between rigid objects. Our data structure, which we call inner sphere trees, supports different kinds of queries, namely, proximity queries and a new method for interpenetration computation, the penetration volume, which is related to the water displacement of the overlapping region and, thus, corresponds to a physically motivated force. The main idea is to bound objects from the inside with a set of non-overlapping spheres. Based on such sphere packings, a “inner bounding volume hierarchy” can be constructed. In order to do so, we propose to use an AI clustering algorithm, which we extend and adapt here. The results show performance at haptic rates both for proximity and penetration volume queries for models consisting of hundreds of thousands of polygons.

Published:

2009 Robotics: Science and Systems Conference (RSS), Seattle, USA, 28 June - 01 July 2009. [BibTex]

Files:

     RSS paper (pdf, 6MB),
     RSS poster (pdf, 2MB)
     Technical Report (pdf, 6MB), [BibTex]

Links:

Project Homepage

Modeling Transformation Paths of Multiphase Materials: The Triple Point of Zirconia

Patrick W. Dondl, Kai Hormann, and Johannes Zimmer

We propose a general method for modelling transformation paths of multi-phase materials such that elastic moduli can be fitted exactly. The energy landscape obtained in this way is global and automatically enjoys the correct symmetries. the method is applied to the triple point of zirconia, where tetragonal, orthorhombic (ortho-I), and monoclinic phases meet. An explicit and relatively simple expression yields a phenomenological model in the two-dimensional space spanned by a set of order parameters. We also show how to extend this energy to the apparently first fully three-dimensional model with an exact fit of all given elastic moduli.

Published

Physical Review B, Volume 79, Number 10, pages 104114, March 2009. [BibTeX]

Files:

Paper (pdf, 1MB)

A Hybrid GPU Rendering Pipeline for Alias-Free Hard Shadows

Stefan Hertel, Kai Hormann, and Rüdiger Westermann

We present a new GPU pipeline for rendering per-pixel exact shadows that are cast by point lights and parallel lights. Our approach is hybrid in that it uses kD-tree accelerated ray-tracing to determine shadow-ray intersections, and rasterization to effectively reduce both the number of shadow rays to be traversed and the number of sub-spaces to be considered along each of these rays. To achieve this we introduce conservative shadow maps, which store for each possible shadow ray a conservative estimate of the first intersection of this ray with the scene. A novel approach to build such a map is presented, which uses rasterization to compute for every shadow-map pixel the triangles intersecting this pixel. By exploiting the rasterization capacities of recent GPUs in combination with accurate ray-triangle intersection tests, we are able to efficiently compute alias-free shadows in high-resolution and spatially extended scenes where classical shadow mapping techniques have severe difficulties.

Published

Eurographics 2009 Areas Papers, pages 59–66, München, Germany, March 2009. [BibTeX]

Files:

Paper (pdf, 7.5MB)

Four-Point Curve Subdivision Based on Iterated Chordal and Centripetal Parameterizations

Nira Dyn, Michael S. Floater, and Kai Hormann

Dubuc's interpolatory four-point scheme inserts a new point by fitting a cubic polynomial to neighbouring points over uniformly spaced parameter values. In this paper we replace uniform parameter values by chordal and centripetal ones. Since we update the parameterization at each refinement level, both schemes are non-linear. Because of this data-dependent parameterization, the schemes are only invariant under solid body and isotropic scaling transformations, but not under general affine transformations. We prove convergence of the two schemes and bound the distance between the limit curve and the initial control polygon. Numerical examples indicate that the limit curves are smooth and that the centripetal one is tighter, as suggested by the distance bounds. Similar to cubic spline interpolation, the use of centripetal parameter values for highly non-uniform initial data yields better results than the use of uniform or chordal ones.

Published

Computer Aided Geometric Design, Volume 26, Number 3, pages 279–286, March 2009. [BibTeX]

Files:

Paper (pdf, 1MB)

Continuous Edge Gradient-Based Template Matching for Articulated Objects

Gabriel Zachmann, Daniel Mohr

In this paper, we propose a novel edge gradient based template matching method for object detection. In contrast to other methods, ours does not perform any binarization or discretization during the online matching. This is facilitated by a new continuous edge gradient similarity measure. Its main components are a novel edge gradient operator, which is applied to query and template images, and the formulation as a convolution, which can be computed very efficiently in Fourier space.

Published

International Conference on Computer Vision Theory and Applications (VISAPP), Lisbon, Portugal, 05-09 February 2009. [BibTex]

Files:

     Paper (pdf, 780KB)
     Slides (pdf, 2.5MB)
     Technical Report
     Video 1 (divx, 656KB), Video 2 (divx, 763KB), Video 3 (divx, 317KB)

Links:

Project Homepage

Mesh Parameterization: Theory and Practice

Kai Hormann, Konrad Polthier, and Alla Sheffer

Mesh parameterization is a powerful geometry processing tool with numerous computer graphics applications, from texture mapping to animation transfer. This course outlines its mathematical foundations, describes recent methods for parameterizing meshes over various domains, discusses emerging tools like global parameterization and inter-surface mapping, and demonstrates a variety of parameterization applications.

Published

SIGGRAPH Asia 2008 Course Notes, Volume 11, pages 1–87, Singapore, December 2008. [BibTeX]

Files:

Paper (pdf, 6.4MB)

Links:

Course Homepage

Polynomial Reproduction by Symmetric Subdivision Schemes

Nira Dyn, Kai Hormann, Malcolm A. Sabin, and Zuowei Shen

We first present necessary and sufficient conditions for a linear, binary, uniform, and stationary subdivision scheme to have polynomial reproduction of degree d and thus approximation order d+1. Our conditions are partly algebraic and easy to check by considering the symbol of a subdivision scheme, but also relate to the parameterization of the scheme. After discussing some special properties that hold for symmetric schemes, we then use our conditions to derive the maximum degree of polynomial reproduction for two families of symmetric schemes, the family of pseudo-splines and a new family of dual pseudo-splines.

Published

Journal of Approximation Theory, Volume 155, Number 1, pages 28–42, November 2008. [BibTeX]

Files:

Paper (pdf, 0.5MB)

Thinning Mesh Animations

Tim Winkler, Jens Drieseberg, Alexander Hasenfuß, Barbara Hammer, and Kai Hormann

Three-dimensional animation sequences are often represented by a discrete set of compatible triangle meshes. In order to create the illusion of a smooth motion, a sequence usually consists of a large number of frames. We propose a pre-processing algorithm that considerably reduces the number of frames required to describe the whole animation. Our method is based on Batch Neural Gas, a new clustering and classification approach that can be used to automatically find the most relevant frames from the sequence. The meshes from the original sequence can then be expressed as linear combinations of these few key-frames with small approximation error. The key-frames can finally be compressed with any state-of-the-art compression scheme. Overall, this leads to improved compression rates as the number of key-frames is significantly smaller than the number of original frames and the storage overhead for the reconstruction weights is marginal.

Published

Vision, Modeling, and Visualization, pages 149–158, Konstanz, Germany, October 2008. [BibTeX]

Files:

Paper (pdf, 0.7MB)

Efficient Evaluation of Interpolating Cubic Polynomials

Kai Hormann

This short note discusses the efficient evaluation of interpolating cubic polynomials with a focus on the evaluation at the midpoint between the interior interpolation points.

Published

Technical Report, IfI-08-04, Department of Informatics, Clausthal University of Technology, August 2008. [BibTeX]

Files:

Paper (pdf, 0.3MB)

Maximum Entropy Coordinates for Arbitrary Polytopes

Kai Hormann and N. Sukumar

Barycentric coordinates can be used to express any point inside a triangle as a unique convex combination of the triangle's vertices, and they provide a convenient way to linearly interpolate data that is given at the vertices of a triangle. In recent years, the ideas of barycentric coordinates and barycentric interpolation have been extended to arbitrary polygons in the plane and general polytopes in higher dimensions, which in turn has led to novel solutions in applications like mesh parameterization, image warping, and mesh deformation. In this paper we introduce a new generalization of barycentric coordinates that stems from the maximum entropy principle. The coordinates are guaranteed to be positive inside any planar polygon, can be evaluated efficiently by solving a convex optimization problem with Newton's method, and experimental evidence indicates that they are smooth inside the domain. Moreover, the construction of these coordinates can be extended to arbitrary polyhedra and higher-dimensional polytopes.

Published

Computer Graphics Forum, Volume 27, Number 5, pages 1513–1520, July 2008. [BibTeX]

Files:

Paper (pdf, 3.3MB)

Interactive Rendering of Dynamic Geometry

Federico Ponchio and Kai Hormann

Fluid simulations typically produce complex three-dimensional iso-surfaces whose geometry and topology change over time. The standard way of representing such dynamic geometry is by a set of iso-surfaces that are extracted individually at certain time steps. An alternative strategy is to represent the whole sequence as a four-dimensional tetrahedral mesh. The iso-surface at a specific time step can then be computed by intersecting the tetrahedral mesh with a three-dimensional hyperplane. This not only allows to animate the surface continuously over time without having to worry about the topological changes, but also enables simplification algorithms to exploit temporal coherence. We show how to interactively render such four-dimensional tetrahedral meshes by improving previous GPU-accelerated techniques and building an out-of-core multi-resolution structure based on quadric error simplification. As a second application we apply our framework to time-varying surfaces that result from morphing one triangle mesh into another.

Published

IEEE Transactions on Visualization and Computer Graphics, Volume 14, Number 4, pages 914–925, July/August 2008. [BibTeX]

Files:

Paper (pdf, 7.7MB)

Mesh Massage: A Versatile Mesh Optimization Framework

Tim Winkler, Kai Hormann and Craig Gotsman

We present a general framework for post-processing and optimizing surface meshes with respect to various target criteria. On the one hand, the framework allows us to control the shapes of the mesh triangles by applying simple averaging operations, on the other we can control the Hausdorff distance to some reference geometry by minimizing a quadratic energy. Due to the simplicity of this setup, the framework is efficient and easy to implement. Yet it constitutes an effective and versatile tool with a variety of possible applications. In particular, we use it to reduce the texture distortion in animated mesh sequences, to improve the results of cross-parameterizations, and to minimize the distance between meshes and their remeshes.

Published

The Visual Computer, Volume 24, Number 7–9, pages 775–785, July 2008. [BibTeX]

Files:

Paper (pdf, 11.6MB)

A Family of Subdivision Schemes with Cubic Precision

Kai Hormann and Malcolm A. Sabin

The 4-point subdivision scheme is well known as an interpolating subdivision scheme, but it has recently come to our notice that it is but the first scheme in a family all of whose members have the property that if all the control points lie equally spaced along the same cubic polynomial, the limit curve is exactly that polynomial. Other members of the family have higher smoothness. This paper introduces the family and determines how the support, the hölder regularity, the precision set, the degree of polynomials spanned by the limit curves, and the artifact behaviour vary with the parameter that identifies the members of the family.

Published

Computer Aided Geometric Design, Volume 25, Number 1, pages 41–52, January 2008. [BibTeX]

Files:

Paper (pdf, 0.5MB)

Segmentation of Distinct Homogeneous Color Regions in Images

Gabriel Zachmann, Daniel Mohr

In this paper, we present a novel algorithm to detect homogeneous color regions in images with application to skin segmentation.

Published

The 12th International Conference on Computer Analysis of Images and Patterns (CAIP), Vienna, Austria, 27-29 August 2007. [BibTex]

Files:

     Paper (pdf, 1.6MB)
     Slides (pdf, 6.2MB)
     Video (divx, 2.2MB)
     Video (mov, 3.5MB)

Links:

Project Homepage

Mesh Parameterization: Theory and Practice

Kai Hormann, Bruno Lévy, and Alla Sheffer

Mesh parameterization is a powerful geometry processing tool with numerous computer graphics applications, from texture mapping to animation transfer. This course outlines its mathematical foundations, describes recent methods for parameterizing meshes over various domains, discusses emerging tools like global parameterization and inter-surface mapping, and demonstrates a variety of parameterization applications.

Published

SIGGRAPH 2007 Course Notes, Volume 2, pages 1–122, San Diego, CA, August 2007. [BibTeX]

Files:

Paper (pdf, 6.3MB)

Links:

Course Homepage

Barycentric Rational Interpolation with no Poles and High Rates of Approximation

Michael S. Floater and Kai Hormann

In this paper we propose and study a family of barycentric rational interpolants that have no poles and arbitrarily high approximation orders, regardless of the distribution of the points. They can be regarded as the linear combination of local polynomial interpolants with certain rational blending functions that form a partition of unity.

Published

Numerische Mathematik, Volume 107, Number 2, pages 315–331, August 2007. [BibTeX]

Files:

Paper (pdf, 0.4MB)
Slides (pdf, 1.0MB)

On Landau Theory and Symmetric Energy Landscapes for Phase Transitions

Kai Hormann and Johannes Zimmer

The aim of this presentation is the development of a general approach for modelling the global complex energy landscapes of phase transitions. Explicit energy functions are derived for the cubic-to-tetragonal phase transition, where data is fitted for InTl and the cubic-to-monoclinic transition in CuZnAl. The resulting energies are defined globally, in a piecewise manner. We use splines that are twice continuously differentiable to ensure sufficient smoothness. The modular (piecewise) technique advocated here allows for modelling elastic moduli, energy barriers and other characteristics independently of each other.

Published

Journal of the Mechanics and Physics of Solids, Volume 55, Number 7, pages 1385–1409, July 2007. [BibTeX]

Files:

Paper (pdf, 1.1MB)

IEEE VR2007 Workshop on "Trends and Issues in Tracking for Virtual Environments"

Gabriel Zachmann (ed.)

The goal of this half-day workshop is to bring together researchers and industry working in the area of tracking and to talk about making tracking actually work. To that end, the workshop is to provide a broad picture of what is the current state of the art, what are the various technologies available, and what are issues for further research and development

Published

February 2007, Shaker Verlag, Aachen, Germany, ISBN 978-3-8322-5967-9 [BibTeX]

Files:

     Home page of the Workshop
     Buy a copy of the the workshop proceedings online (hard-copy for 25€; electronic version for 3€) from the publisher
     You can also ask me at zach in.tu-clausthal.de -- I've still got some copies for sale, left over from the conference ;-)

A Benchmarking Suite for Static Collision Detection Algorithms

Sven Trenkel, René Weller, Gabriel Zachmann

In this paper, we present a benchmarking suite that allows a systematic comparison of pairwise static collision detection algorithms for rigid objects. The pdf-file contains a slightly extended version of the original published paper.

Published

International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), Plzen, Czech Republic, January 29 - February 1, 2007. [BibTex]

Files:

     Paper (pdf, 1.0MB)
     Slides (pdf, 5.4MB)
     Video of configuration generation (avi, 16.6MB)

For further information please visit our project homepage.

Kinetic Separation Lists for Continuous Collision Detection of Deformable Objects

Gabriel Zachmann, René Weller

In this paper, we present a new acceleration scheme for continuous inter- and intra-collision detection of deformable objects. The pdf-file contains a slightly extended version of the original published paper (Section 6.2).

Published

Third Workshop in Virtual Reality Interactions and Physical Simulation (Vriphys), Madrid, Spain, 6/7 November 2006. [BibTex]

Files:

Paper (pdf, 0.7MB)
Slides (pdf, 4.9MB)

Mean Value Coordinates for Arbitrary Planar Polygons

Kai Hormann and Michael S. Floater

Barycentric coordinates for triangles are commonly used in computer graphics, geometric modelling, and other computational sciences for various purposes, because they provide a convenient way to linearly interpolate data that is given at the corners of a triangle. In this paper we show that Mean Value Coordinates extend this concept to arbitrary planar polygons without self-intersections. Besides many other important properties, these coordinate functions are smooth and allow for an efficient and robust implementation. They are particularly useful for interpolating data that is given at the vertices of the polygons and we present several examples of their application to common problems in computer graphics and geometric modelling.

Published

ACM Transactions on Graphics, Volume 25, Number 4, pages 1424–1441, October 2006. [BibTeX]

Files:

Paper (pdf, 6.6MB)
Slides (pdf, 6.7MB)

Kinetic Bounding Volume Hierarchies for Deformable Objects

Gabriel Zachmann, René Weller

In this paper, we present novel algorithms for updating bounding volume hierarchies of objects undergoing arbitrary deformations.

Published

ACM Int'l Conf. on Virtual Reality Continuum and Its Applications (VRCIA), Hong Kong, China, 14-17 June 2006. [BibTex]

Files:

     Paper (pdf, 1MB)
     Slides (pdf, 6.0 MB)
     Technical Report (pdf, 1.2MB)

A Model for the Expected Running Time of Collision Detection using AABB Trees

René Weller, Jan Klein, Gabriel Zachmann

In this paper, we propose a model to estimate the expected running time of hierarchical collision detection that utilizes AABB trees, which are a frequently used type of bounding volume (BV).

Published

12th Eurographics Symposium on Virtual Environments (EGVE), Lisbon, Portugal, 8-10 May 2006. [BibTex]

Files:

     Paper, on-screen version (pdf, 1.6 MB)
     Paper, print version (pdf, 1.6 MB)
     Slides (pdf, 2.5 MB)

Book: Geometric Data Structures for Computer Graphics

Elmar Langetepe, Gabriel Zachmann, AK Peters, 2006

Links

Buy from the publisher or from Amazon

BibTex

GPU-ABiSort: Optimal Parallel Sorting on Stream Architectures

Alexander Greß, Gabriel Zachmann

In this paper, we present a novel approach for parallel sorting on stream processing architectures.

Published

Proc. 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Rhodes Island, Greece, 25-29 April 2006. [BibTex]

Files:

Paper (pdf, 0.3MB)
Technical Report (pdf, 1.3MB)

Space-Efficient FPGA-Accelerated Collision Detection for Virtual Prototyping

Andreas Raabe, Stefan Hochgürtel, Gabriel Zachmann, Joachim K. Anlauf

In this paper, we present a space-efficient, FPGA-optimized architecture to detect collisions among virtual objects, as well as simulation results for collision queries using this architecture.

Published

Design Automation and Test in Europe (DATE), Munich, Germany, 6-10 March 2006. [BibTex]

Files:

Paper (pdf, 0.3MB)
Slides (pdf, 0.8MB)

A General Construction of Barycentric Coordinates over Convex Polygons

Michael S. Floater, Kai Hormann, and Geza Kós

Barycentric coordinates are unique for triangles, but there are many possible generalizations to arbitrary convex polygons. In this paper we derive sharp upper and lower bounds and use them to show that all barycentric coordinates are identical at the boundary of the polygon. We then present a general approach for constructing such coordinates and use it to show that the wachspress, mean value, and discrete harmonic coordinates all belong to a unifying one-parameter family. But the only members of this family that are positive are the wachspress and mean value coordinates. However, our general approach does allow us to construct several new sets of barycentric coordinates.

Published

Advances in Computational Mathematics, Volume 24, Number 1–4, pages 311–331, January 2006. [BibTeX]

Files:

Paper (pdf, 1.4MB)

Hardware-Accelerated Collision Detection using Bounded-Error Fixed-Point Arithmetic

Andreas Raabe, Stefan Hochgürtel, Gabriel Zachmann, Joachim K. Anlauf

In this paper, we present a novel approach for highly space-efficient hardware-accelerated collision detection.

Published

The 14-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG), Plzen, Czech Republic, 30 January - 3 February 2006. [BibTex]

Files:

Paper (pdf, 0.4MB)
Slides (pdf, 0.6MB)

A C² Four-Point Subdivision Scheme with Fourth Order Accuracy and its Extensions

Nira Dyn, Michael S. Floater, and Kai Hormann

We present a new four-point subdivision scheme that generates C² curves. It reproduces cubic polynomials, has a basic limit function with support [-4,3], and is close to being interpolatory.

Published

Mathematical Methods for Curves and Surfaces, pages 145–156, Nashboro Press, 2005. [BibTeX]

Files:

Paper (pdf, 0.6MB)
Slides (ppt, 1.2MB)

Surface Parameterization: a Tutorial and Survey

Michael S. Floater and Kai Hormann

This paper provides a tutorial and survey of methods for parameterizing surfaces with a view to applications in geometric modelling and computer graphics. We gather various concepts from differential geometry which are relevant to surface mapping and use them to understand the strengths and weaknesses of the many methods for parameterizing piecewise linear surfaces and their relationship to one another.

Published

Advances in Multiresolution for Geometric Modelling, pages 157–186, Springer, 2005. [BibTeX]

Files:

Paper (pdf, 0.6MB)

Patent on Collision Detection

Gabriel Zachmann, US Patent and Trademark Office, May 2005, [BibTex]

Links:

first page
US Patent

The Expected Running Time of Hierarchical Collision Detection

Jan Klein, Gabriel Zachmann

We propose a theoretical approach to analyze the average-case running time of hierarchical collision detection that utilizes bounding volume hierarchies.

Published

SIGGRAPH 2005, Poster, Los Angeles, CA, USA, August 2005. [BibTex]

Files:

     Poster (pdf, 1.8MB)
     One-Page Summary. (pdf, 1.6 MB)
     Supplemental Material (pdf, 1.4 MB)
     Slides (pdf, 0.6 MB)

Collision Detection for Deformable Objects

M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnenat-Thalmann, W. Strasser, P. Volino

This paper focusses on collision detection for deformable objects and summarizes recent research in the area of deformable collision detection. Various approaches based on bounding volume hierarchies, distance fields, and spatial partitioning are discussed. Further, image-space techniques and stochastic methods are considered. Applications in cloth modeling and surgical simulation are presented.

Published

Computer Graphics forum, March 2005, Volume 24 [BibTex]

Files:

     Paper (gzipped postscript, 2.8MB)
     Paper (pdf, 10MB)
     Slides (pdf, 0.5MB)

Interpolation Search for Point Cloud Intersection

Jan Klein, Gabriel Zachmann

We present a novel algorithm to compute intersections of two point clouds.

Published

Proc. of WSCG 2005, Plzen, Czech Republic, 31 January - 7 February 2005. [BibTex]

Files:

     Paper (pdf print-version, 2.4MB)
     Paper (pdf onscreen-version, 2.4MB)
     Slides (pdf, 4.1MB)

A Quadrilateral Rendering Primitive

Kai Hormann and Marco Tarini

We propose a new method that processes a potentially non-planar quadrilateral directly without any splitting and interpolates attributes smoothly inside the quadrilateral. This interpolation is based on a recent generalization of barycentric coordinates that we adapted to handle perspective correction and situations in which a quadrilateral is partially behind the point of view. Our method is designed to be implemented in hardware as a new rasterizer.

Published

Graphics Hardware 2004, pages 7–14, Grenoble, France, August 2005. [BibTeX]

Files:

Paper (pdf, 2.9MB)
Slides (ppt, 3.2MB)

PolyCube-Maps

Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani

Standard texture mapping of real-world meshes suffers from the presence of seams that need to be introduced in order to avoid excessive distortions and to make the topology of the mesh compatible to the one of the texture domain. In contrast, cube maps provide a mechanism that could be used for seamless texture mapping with low distortion, but only if the object roughly resembles a cube. We extend this concept to arbitrary meshes by using as texture domain the surface of a polycube whose shape is similar to that of the given mesh. our approach leads to a seamless texture mapping method that is simple enough to be implemented in currently available graphics hardware.

Published

ACM Transactions on Graphics, Volume 23, Number 3, pages 853–860, August 2004. Proceedings of ACM SIGGRAPH. [BibTeX]

Files:

     Paper (pdf, 6.8MB)
     Slides (ppt, 10.0MB)
     Video (avi, 26.8MB)

Shader Maker

Markus Kramer, Rene Weller, Gabriel Zachmann

Actually, this is not a regular publication, but a software release.

Shader Maker is a simple, cross-platform GLSL editor. It works on Windows, Linux, and Mac OS X.

It provides the basics of a shader editor, such that students can get started with writing their own shaders as quickly as possible. This includes: syntax highlighting in the GLSL editors; geometry shader editor (as well as vertex and fragment shader editors, of course); interactive editing of the uniform variables; light source parameters; pre-defined simple shapes (e.g., torus et al.) and a simple OBJ loader; and a few more.

Prerequisite:

Qt 4.3 or higher

Files:

     source code
     Mac OS X executable (intel) (Mac OS 10.4 and higher)
     Mac OS X executable (ppc) (Mac OS 10.4 and higher)
     Windows executable (Includes Qt-Dlls)