Publications

The most effective and popular tools for obtaining feature aligned quad meshes from triangular input meshes are based on cross field guided parametrization. These methods are incarnations of a conceptual three-step pipeline: (1) cross field computation, (2) field-guided surface parametrization, (3) quad mesh extraction. While in most meshing scenarios the user prescribes a desired target quad size or edge length, this information is typically taken into account from step 2 onwards only, but not in the cross field computation step. This turns into a problem in the presence of small scale geometric or topological features or noise in the input mesh: closely placed singularities are induced in the cross field, which are not properly reproducible by vertices in a quad mesh with the prescribed edge length, causing severe distortions or even failure of the meshing algorithm. We reformulate the construction of cross fields as well as field-guided parametrizations in a scale-aware manner which effectively suppresses densely spaced features and noise of geometric as well as topological kind. Dominant large-scale features are adequately preserved in the output by relying on the unaltered input mesh as the computational domain.

We introduce Dual Strip Weaving, a novel concept for the interactive design of quad layouts, i.e. partitionings of freeform surfaces into quadrilateral patch networks. In contrast to established tools for the design of quad layouts or subdivision base meshes, which are often based on creating individual vertices, edges, and quads, our method takes a more global perspective, operating on a higher level of abstraction: the atomic operation of our method is the creation of an entire cyclic strip, delineating a large number of quad patches at once. The global consistency-preserving nature of this approach reduces demands on the user’s expertise by requiring less advance planning. Efficiency is achieved using a novel method at the heart of our system, which automatically proposes geometrically and topologically suitable strips to the user. Based on this we provide interaction tools to influence the design process to any desired degree and visual guides to support the user in this task.

Recent improvements in image-based localization have produced powerful methods that scale up to the massive 3D models emerging from modern Structure-from-Motion techniques. However, these approaches are too resource intensive to run in real-time, let alone to be implemented on mobile devices. In this paper, we propose to combine the scalability of such a global localization system running on a server with the speed and precision of a local pose tracker on a mobile device. Our approach is both scalable and drift-free by design and eliminates the need for loop closure. We propose two strategies to combine the information provided by local tracking and global localization. We evaluate our system on a large-scale dataset of the historic inner city of Aachen where it achieves interactive framerates at a localization error of less than 50cm while using less than 5MB of memory on the mobile device.

In rigid body simulation, one must distinguish between contacts (so-called unilateral constraints) and articulations (bilateral constraints). For contacts and friction, iterative solution methods have proven most useful for interactive applications, often in combination with Shock-Propagation in cases with strong interactions between contacts (such as stacks), prioritizing performance and plausibility over accuracy. For articulation constraints, direct solution methods are preferred, because one can rely on a factorization with linear time complexity for tree-like systems, even in ill-conditioned cases caused by large mass-ratios or high complexity. Despite recent advances, combining the advantages of direct and iterative solution methods wrt. performance has proven difficult and the intricacy of articulations in interactive applications is often limited by the convergence speed of the iterative solution method in the presence of closed kinematic loops (i.e. auxiliary constraints) and contacts. We identify common performance bottlenecks in the dynamic simulation of unilateral and bilateral constraints and are able to present a simulation method, that scales well in the number of constraints even in ill-conditioned cases with frictional contacts, collisions and closed loops in the kinematic graph. For cases where many joints are connected to a single body, we propose a technique to increase the sparsity of the positive definite linear system. A solution to these bottlenecks is presented in this paper to make the simulation of a wider range of mechanisms possible in real-time without extensive parameter tuning.

Quad layouting, i.e. the partitioning of a surface into a coarse network of quadrilateral patches, is a fundamental step in application scenarios ranging from animation and simulation to reverse engineering and meshing. This process involves determining the layout's combinatorial structure as well as its geometric embedding in the surface. We present a novel quad layout algorithm that focuses on the embedding optimization, thereby complementing recent methods focusing on the structure optimization aspect. It takes as input a description of the target layout structure and computes a complete embedding in form of a parameterization globally optimized for isometry and, in particular, principal direction alignment. Besides being suited for fully automatic workflows, our method can also incorporate user constraints and support the tedious but common procedure of manual layouting.

We present an algorithm that approximates 2-manifold surfaces with Zometool models while preserving their topology. Zometool is a~popular hands-on mathematical modeling system used in teaching, research and for recreational model assemblies at home. This construction system relies on a single node type with a small, fixed set of directions and only 9 different edge types in its basic form. While being naturally well suited for modeling symmetries, various polytopes or visualizing molecular structures, the inherent discreteness of the system poses difficult constraints on any algorithmic approach to support the modeling of freeform shapes. We contribute a set of local, topology preserving Zome mesh modification operators enabling the efficient exploration of the space of 2-manifold Zome models around a given input shape. Starting from a rough initial approximation, the operators are iteratively selected within a stochastic framework guided by an energy functional measuring the quality of the approximation. We demonstrate our approach on a number of designs and also describe parameters which are used to explore different complexities and enable coarse approximations.

We present a new method to interactively compute and visualize fiber bundles extracted from a diffusion magnetic resonance image. It uses Dijkstra's shortest path algorithm to find globally optimal pathways from a given seed to all other voxels. Our distance function enables Dijkstra to generalize to larger voxel neighborhoods, resulting in fewer quantization artifacts of the orientations, while the shortest paths are still efficiently computable. Our volumetric fiber representation enables the usage of volume rendering techniques. Therefore no complicated pruning or analysis of the resulting fiber tree is needed in order to visualize important fibers. In fact, this can efficiently be done by changing a transfer function. Our application is highly interactive, allowing the user to focus completely on the exploration of the data.

An ever broader availability of freeform designs together with an increasing demand for product customization has lead to a rising interest in efficient physical realization of such designs, the trend toward personal fabrication. Not only large-scale architectural applications are (becoming increasingly) popular but also different consumer-level rapid-prototyping applications, including toy and 3D puzzle creation. In this work we present a method for do-it-yourself reproduction of freeform designs without the typical limitation of state-of-the-art approaches requiring manufacturing custom parts using semi-professional laser cutters or 3d printers. Our idea is based on a popular mathematical modeling system (Zometool) commonly used for modeling higher dimensional polyhedra and symmetric structures such as molecules and crystal lattices. The proposed method extends the scope of Zometool modeling to freeform, disk-topology surfaces. While being an efficient construction system on the one hand (consisting only of a single node type and 9 different edge types), this inherent discreteness of the Zometool system, on the other hand gives rise to a hard approximation problem. We base our method on a marching front approach, where elements are not added in a greedy sense, but rather whole regions on the front are filled optimally, using a set of problem specific heuristics to keep complexity under control.

The efficient, computer aided or automatic generation of quad layouts, i.e. the partitioning of an object’s surface into simple networks of conforming quadrilateral patches, is a task that – despite its importance and utility in Computer Graphics and Geometric Modeling – received relatively low attention in the past. As a consequence, this task is most often performed manually by well-trained experts in practice, where quad layouts are of particular interest for surface representation and parameterization tasks. Deeper analysis reveals the inherent complexity of this problem, which might be one of the underlying reasons for this situation. In this thesis we investigate the structure of the problem and the commonly relevant quality criteria. Based on this we develop novel efficient solution strategies and algorithms for the generation of high quality quad layouts. In particular, we present a fully automatic as well as an interactive pipeline for this task. Both are based on splitting the hard problem into sub-problems with a simpler structure each. For each sub-problem we design efficient, custom-tailored optimization algorithms motivated by the geometric nature of these problems. In this process we pay attention to compatibility, such that these algorithms can be applied in sequence, forming the stages of efficient quad layouting pipelines.