Abstract We present a framework for learning compactly supported basis functions that define tangent continuous surfaces based on coarse irregular triangle meshes. The basis functions are represented as MLPs. Smoothness of the basis functions is achieved by using the values of Loop basis functions as the parameterization of the surface. Post‐multiplying the value of the MLP with the Loop basis yields smooth compact support. We show that this approach works similar or better than Neural Subdivision in terms of recreating given geometry, while the runtime scales better with surface resolution and can be evaluated at arbitrary resolution.

Abstract Implicit surface representations have regained popularity because of their use in machine learning. A common component in optimization is regularization, penalizing the deviation of the surface from its original shape. The popular as‐rigid‐as‐possible (A rap ) energy strikes a good compromise between realistic deformation behavior and efficient computation, at least for piecewise linear meshes. We develop an approach for computing the A rap energy of a deformation function based on point sampling of the surface. The implicit representation is exploited to provide differentials in each sample. The evaluation is efficient and exact in each sample (up to numerical precision). We demonstrate the general applicability of the method to neural shape processing in several applications and contrast its properties with alternatives from the literature.

Abstract The well‐established As‐Rigid‐As‐Possible (ARAP) energy has various forms. For surface deformation, commonly used energies contain an implicit bending penalty. We present a natural, continuous generalization that incorporates multiple ARAP versions with an implicit, user‐controllable bending penalty. We discretize an intuitive variant of the energy and demonstrate that it is independent of mesh resolution and produces comparable results to those of competing methods that include an explicit bending penalty term. We validate our method and demonstrate that, despite its computational overhead, it converges among the fastest of all ARAP variants.

Abstract Signed distance fields are often represented by discrete samples (e.g., on a grid). Recovering the contour implicitly represented by the distance samples requires an approximation algorithm. Several recent approaches have shown that exploiting the information carried in each distance sample by explicitly constructing a surface point gives better results than classical contouring algorithms. We explore the idea of generating surface points by simply approximating the gradient of the signed distance function from a tesselation of the sample locations. The distance value together with gradient yields a potential surface point. To avoid problems resulting from bad approximation, surface points are removed if they are too close to any of the distance samples. Using the regular triangulation as tesselation facilitates this filtering. The resulting approximation algorithm is conceptually simple, easy to implement, and significantly faster than existing alternatives, yielding reconstructions that are on par.

Abstract Unsigned distance fields (UDF) are a versatile, implicit representation of geometry. They can represent surfaces that are not bounding a solid or contain points or curves that are not manifold, for example several sheets meeting along a common curve. Contouring the implicit representation, i.e. turning it into an explicit one, requires finding the zero level set. This is challenging because of the lacking sign information. We present an adaptive re‐sampling approach based on regular triangulations that allows efficiently querying the UDF function at the most important locations. Using a dual contouring approach, information on the topology of the reconstructed surface patches is available during refinement, enabling to increase the resolution in the more critical non‐manifold regions.

Abstract The convex hull is a central concept in computational geometry, geometry processing, and generally for summarizing sampled data. Its descriptive power suffers significantly in the presence of noise. The k‐hull, also known as the k‐depth contour in statistics, is the intersection of all half‐spaces that contain all but k data points, i.e. it is a convex hull ignoring k points in any direction. While it is well established theoretically, the lack of a robust and efficient algorithm, especially for the 3D case, limits applications. We combine ideas of an intuitive algorithm for the 2D case with gift wrapping and improve efficiency using established spatial data structures. The clear concept also facilitates a generalization to weighted data, allowing us to ignore points whose weights sum up to at most a given tolerance. For the case of unweighted data with unknown noise characteristics, we determine a simple heuristic for estimating k to adjust to outliers in the data. We demonstrate the effectiveness of the algorithm on the examples of computing convex hulls for data with noise and for visibility determination via convex hulls.

Abstract The As‐Rigid‐As‐Possible (ARAP) energy [SA07] has become a versatile ingredient in various geometry processing and machine learning methods. The classic method for its minimization is a block coordinate descent, alternating between local rotation estimation and a global linear solve, which converges slowly for large problem instances. We develop and evaluate a multi‐level scheme targeted specifically at the optimization of the ARAP energy on large meshes. The main points of our approach are (1) a mesh hierarchy that provides the necessary control over topology while being fast, (2) methods for upsampling the rotations from coarser to finer levels of the hierarchy, and (3) using direct solvers for the linear system. The resulting optimization, remarkably, yields smaller energy while typically being faster on a large number of test cases. The hierarchical approach generalizes to related energies and compares favorably to acceleration schemes such as ADMM, which, in turn, also profit from the hierarchical approach.

We investigate the construction of visually smooth spline surfaces that interpolate the vertices of triangulations by blending local patches. Each triangle star carries a locally interpolating surface patch. The patches are only required to interpolate the vertex, whereas in previous methods the patches are often defined per edge, imposing multiple constraints on local approximations. We adopt simple rational blend functions for the triangular domains, that are constructed so that they retain the interpolation and tangent behavior on the patch boundaries. Decoupling local approximation from blending facilitates the exploration of visually pleasing constructions, while controlling the complexity.

Abstract Contouring an implicit function typically considers function values in the vicinity of the desired level set, only. In a recent string of works, Sellán at al. have demonstrated that signed distance values contain useful information also if they are further away from the surface. This can be exploited to increase the resolution and amount of detail in surface reconstruction from signed distance values. We argue that the right tool for this analysis is a regular triangulation of the distance samples, with the weights chosen based on the distance values. The resulting triangulation is better suited for reconstructing the surface than a standard Delaunay triangulation of the samples. Moreover, the dual power diagram encodes the envelope enclosing the surface, consisting of spherical caps. We discuss how this information can be exploited for reconstructing the surface. In particular, the approach based on regular triangulations lends itself well to refining the sample set. Refining the sample set based on the power diagram outperforms other reconstruction methods relative to the sample count.

Abstract Many common approaches for reconstructing surfaces from point clouds leverage normal information to fit an implicit function to the points. Normals typically play two roles: the direction provides a planar approximation to the surface and the sign distinguishes inside from outside. When the sign is missing, reconstructing a surface with globally consistent sidedness is challenging. In this work, we investigate the idea of squaring the Poisson Surface Reconstruction, replacing the normals with their outer products, making the approach agnostic to the signs of the input/estimated normals. Squaring results in a quartic optimization problem, for which we develop an iterative and hierarchical solver, based on setting the cubic partial derivatives to zero. We show that this technique significantly outperforms standard L‐BFGS solver and demonstrate reconstruction of surfaces from unoriented noisy input in linear time.

Abstract Tutte’s embedding theorem states that every 3-connected graph without a $$K_5$$ K 5 - or $$K_{3,3}$$ K 3 , 3 -minor (i.e., a planar graph) is embedded in the plane if the outer face is in convex position and the interior vertices are convex combinations of their neighbors. We show that this result extends to simply connected tetrahedral meshes in a natural way: for the tetrahedral mesh to be embedded if the outer polyhedron is in convex position and the interior vertices are convex combination of their neighbors it is sufficient (but not necessary) that the graph of the tetrahedral mesh contains no $$K_6$$ K 6 and no $$K_{3,3,1}$$ K 3 , 3 , 1 , and all triangles incident on three boundary vertices are boundary triangles.

We show how the problem of creating a triangulation in d -dimensional space that conforms to constraints given as sub-simplices can be turned into the problem of computing the lower hull of a sum of wedge functions. This sum can be interpreted as a Weighted Delaunay Triangulations, necessarily containing the constraints as unions of its elements. Intersections of wedges lead to Steiner points. As the number of such intersections is polynomial in the number of wedges, and the number of wedges per element is typically 1 (at most d ), this proves that the complexity of the output is polynomial. Moreover, we show that the majority of wedge intersections is unnecessary for a conforming triangulation and further heuristically reduce the number of Steiner points. Using appropriate data structures, the function can be evaluated in quasi-linear time, leading to an output-sensitive algorithm.

Differentiable rendering has become a key ingredient in solving challenging inverse problems in computer graphics and vision. Existing systems can simulate and differentiate the spatial propagation of light. We exploit the duality of light transport simulations and geometric acoustics to apply differential rendering techniques to established acoustic simulation methods. The resulting system is capable of simulating sound according to the geometrical acoustics model and computing derivatives of the output energy spectrograms with respect to arbitrary parameters of the scene, including materials, emitters, microphones, and scene geometry. Contrary to current differentiable transient rendering, we can handle arbitrary simulation depths and achieve constant memory and linear execution times by presenting a temporal extension of Path Replay Backpropagation [Vicini et al. 2021]. We verify our model against established simulation software, and demonstrate the capabilities of optimization with gradients at examples of inverse acoustics and optimizing room parameters. This opens up a new field of research for acoustic optimization that could be as impactful for the acoustic community as differentiable rendering was for the graphics community.

All rendering methods aim at striking a balance between realism and efficiency. This is particularly relevant for differentiable rendering, where the additional aspect of differentiablity w.r.t. scene parameters causes increased computational complexity while, on the other hand, in the common application of inverse rendering, the diverse effects of real image formation must be faithfully reproduced. An important effect in rendering is the attenuation of light as it travels through different media (visibility, shadows, transmittance, transparency). This can be modeled as an integral over non-negative functions and has been successfully approximated in forward rendering by so-called moments. We show that moment-based approximations are differentiable in the parameters defining the moments, and that this leads to efficient and practical methods for inverse rendering. In particular, we demonstrate the method at the examples of shadow mapping and visibility in volume rendering, leading to approximations that are similar in efficiency to existing ad-hoc techniques while being significantly more accurate.

Affine subspaces of Euclidean spaces are also referred to as flats. A standard task in computer vision, or more generally in engineering and applied sciences, is fitting a flat to a set of points, which is commonly solved using the PCA. We generalize this technique to enable fitting a flat to a set of other flats, possibly of varying dimensions, based on representing the flats as squared distance fields. Compared to previous approaches such as Riemannian centers of mass in the manifold of affine Grassmannians, our approach is conceptually much simpler and computationally more efficient, yet offers desirable properties such as respecting symmetries and being equivariant to rigid transformations, leading to more intuitive and useful results in practice. We demonstrate these claims in a number of synthetic experiments and a multi-view reconstruction task of line-like objects.

Abstract A parameterization of a triangle mesh is a realization in the plane so that all triangles have positive signed area. Triangle mesh parameterizations are commonly computed by minimizing a distortion energy, measuring the distortions of the triangles as they are mapped into the parameter domain. It is assumed that the triangulation is fixed and the triangles are mapped affinely. We consider a more general setup and additionally optimize among the intrinsic triangulations of the piecewise linear input geometry. This means the distortion energy is computed for the same geometry, yet the space of possible parameterizations is enlarged. For minimizing the distortion energy, we suggest alternating between varying the parameter locations of the vertices and intrinsic flipping. We show that this process improves the mapping for different distortion energies at moderate additional cost. We also find intrinsic triangulations that are better starting points for the optimization of positions, offering a compromise between the full optimization approach and exploiting the additional freedom of intrinsic triangulations.

Abstract Discrete Laplacians are the basis for various tasks in geometry processing. While the most desirable properties of the discretization invariably lead to the so‐called cotangent Laplacian fortrianglemeshes, applying the same principles topolygonLaplacians leaves degrees of freedom in their construction. From linear finite elements it is well‐known how the shape of triangles affects both the error and the operator's condition. We notice that shape quality can be encapsulated as the trace of the Laplacian and suggest that trace minimization is a helpful tool to improve numerical behavior. We apply this observation to the polygon Laplacian constructed from a virtual triangulation [BHKB20] to derive optimal parameters per polygon. Moreover, we devise a smoothing approach for the vertices of a polygon mesh to minimize the trace. We analyze the properties of the optimized discrete operators and show their superiority over generic parameter selection in theory and through various experiments.

We show how shadows can be efficiently generated in differentiable rendering of triangle meshes. Our central observation is that pre-filtered shadow mapping, a technique for approximating shadows based on rendering from the perspective of a light, can be combined with existing differentiable rasterizers to yield differentiable visibility information. We demonstrate at several inverse graphics problems that differentiable shadow maps are orders of magnitude faster than differentiable light transport simulation with similar accuracy - while differentiable rasterization without shadows often fails to converge.

The Laplace-Beltrami operator is one of the essential tools in geometric processing. It allows us to solve numerous partial differential equations on discrete surface and volume meshes, which is a fundamental building block in many computer graphics applications. Discrete Laplacians are typically limited to standard elements like triangles or quadrilaterals, which severely constrains the tessellation of the mesh. But in recent years, several approaches were able to generalize the Laplace Beltrami and its closely related gradient and divergence operators to more general meshes. This allows artists and engineers to work with a wider range of elements which are sometimes required and beneficial in their field. This course, which extends the state-of-the-art report by Bunge and Botsch [2023], discusses the different constructions of these three ubiquitous differential operators on arbitrary polygons and polyhedra and analyzes their individual advantages and properties in common computer graphics applications.

Abstract As‐rigid‐as‐possible (ARAP) surface modelling is widely used for interactive deformation of triangle meshes. We show that ARAP can be interpreted as minimizing a discretization of an elastic energy based on non‐conforming elements defined over dual orthogonal cells of the mesh. Using the intrinsic Voronoi cells rather than an orthogonal dual of the extrinsic mesh guarantees that the energy is non‐negative over each cell. We represent the intrinsic Delaunay edges extrinsically as polylines over the mesh, encoded in barycentric coordinates relative to the mesh vertices. This modification of the original ARAP energy, which we term iARAP , remedies problems stemming from non‐Delaunay edges in the original approach. Unlike the spokes‐and‐rims version of the ARAP approach it is less susceptible to the triangulation of the surface. We provide examples of deformations generated with iARAP and contrast them with other versions of ARAP. We also discuss the properties of the Laplace‐Beltrami operator implicitly introduced with the new discretization.

Abstract Screened Poisson Surface Reconstruction creates 2D surfaces from sets of oriented points in 3D (and can be extended to co‐dimension one surfaces in arbitrary dimensions). In this work we generalize the technique to manifolds of co‐dimension larger than one. The reconstruction problem consists of finding a vector‐valued function whose zero set approximates the input points. We argue that the right extension of screened Poisson Surface Reconstruction is based on exterior products: the orientation of the point samples is encoded as the exterior product of the local normal frame. The goal is to find a set of scalar functions such that the exterior product of their gradients matches the exterior products prescribed by the input points. We show that this setup reduces to the standard formulation for co‐dimension 1, and leads to more challenging multi‐quadratic optimization problems in higher co‐dimension. We explicitly treat the case of co‐dimension 2, i.e., curves in 3D and 2D surfaces in 4D. We show that the resulting bi‐quadratic problem can be relaxed to a set of quadratic problems in two variables and that the solution can be made effective and efficient by leveraging a hierarchical approach.

K-surfaces are an interactive modeling technique for Bézier-spline surfaces. Inspired by k -curves by [Yan et al. 2017], each patch provides a single control point that is being interpolated at a local extremum of Gaussian curvature. The challenge is to solve the inverse problem of finding the center control point of a Bézier patch given the boundary control points and the handle. Unlike the situation in 2D, bi-quadratic Bézier patches may exhibit none, one, or several extrema, and finding them is non-trivial. We solve the difficult inverse problem, including the possible selection among several extrema, by learning the desired function from samples, generated by computing Gaussian curvature of random patches. This approximation provides a stable solution to the ill-defined inverse problem and is much more efficient than direct numerical optimization, facilitating the interactive modeling framework. The local solution is used in an iterative optimization incorporating continuity constraints across patches. We demonstrate that the surface varies smoothly with the handle location and that the resulting modeling system provides local and generally intuitive control. The idea of learning the inverse mapping from handles to patches may be applicable to other parametric surfaces.

We provide a set of tools for generating planar embeddings of triangulated topological spheres. The algorithms make use of Schnyder labelings and realizers. A new representation of the realizer based on dual trees leads to a simple linear time algorithm mapping from weights per triangle to barycentric coordinates and, more importantly, also in the reverse direction. The algorithms can be implemented so that all coefficients involved are 1 or -1. This enables integer computation, making all computations exact. Being a Schnyder realizer, mapping from positive triangle weights guarantees that the barycentric coordinates form an embedding. The reverse direction enables an algorithm for fixing flipped triangles in planar realizations, by mapping from coordinates to weights and adjusting the weights (without forcing them to be positive). In a range of experiments, we demonstrate that all algorithms are orders of magnitude faster than existing robust approaches.

We propose an efficient method for differentiable rendering of parametric surfaces and curves, which enables their use in inverse graphics problems. Our central observation is that a representative triangle mesh can be extracted from a continuous parametric object in a differentiable and efficient way. We derive differentiable meshing operators for surfaces and curves that provide varying levels of approximation granularity. With triangle mesh approximations, we can readily leverage existing machinery for differentiable mesh rendering to handle parametric geometry. Naively combining differentiable tessellation with inverse graphics settings lacks robustness and is prone to reaching undesirable local minima. To this end, we draw a connection between our setting and the optimization of triangle meshes in inverse graphics and present a set of optimization techniques, including regularizations and coarse-to-fine schemes. We show the viability and efficiency of our method in a set of image-based computer-aided design applications.

Super-Fibonacci spirals are an extension of Fibonacci spirals, enabling fast generation of an arbitrary but fixed number of 3D orientations. The algorithm is simple and fast. A comprehensive evaluation comparing to other meth-ods shows that the generated sets of orientations have low discrepancy, minimal spurious components in the power spectrum, and almost identical Voronoi volumes. This makes them useful for a variety of applications, in partic-ular Monte Carlo sampling.

Abstract Extending the ARAP energy with a term that depends on the face normal, energy minimization becomes an effective stylization tool for shapes represented as meshes. Our approach generalizes the possibilities of Cubic Stylization: the set of preferred normals can be chosen arbitrarily from the Gauss sphere, including semi‐discrete sets to model preference for cylinder‐ or cone‐like shapes. The optimization is designed to retain, similar to ARAP, the constant linear system in the global optimization. This leads to convergence behavior that enables interactive control over the parameters of the optimization. We provide various examples demonstrating the simplicity and versatility of the approach.

Abstract Across computer graphics, vision, robotics and simulation, many applications rely on determining the 3D rotation that aligns two objects or sets of points. The standard solution is to use singular value decomposition (SVD), where the optimal rotation is recovered as the product of the singular vectors. Faster computation of only the rotation is possible using suitable parameterizations of the rotations and iterative optimization. We propose such a method based on the Cayley transformations. The resulting optimization problem allows better local quadratic approximation compared to the Taylor approximation of the exponential map. This results in both faster convergence as well as more stable approximation compared to other iterative approaches. It also maps well to AVX vectorization. We compare our implementation with a wide range of alternatives on real and synthetic data. The results demonstrate up to two orders of magnitude of speedup compared to a straightforward SVD implementation and a 1.5‐6 times speedup over popular optimized code.

Abstract Discrete Laplacians for triangle meshes are a fundamental tool in geometry processing. The so‐called cotan Laplacian is widely used since it preserves several important properties of its smooth counterpart. It can be derived from different principles: either considering the piecewise linear nature of the primal elements or associating values to the dual vertices. Both approaches lead to the same operator in the two‐dimensional setting. In contrast, for tetrahedral meshes, only the primal construction is reminiscent of the cotan weights, involving dihedral angles. We provide explicit formulas for the lesser‐known dual construction. In both cases, the weights can be computed by adding the contributions of individual tetrahedra to an edge. The resulting two different discrete Laplacians for tetrahedral meshes only retain some of the properties of their two‐dimensional counterpart. In particular, while both constructions have linear precision, only the primal construction is positive semi‐definite and only the dual construction generates positive weights and provides a maximum principle for Delaunay meshes. We perform a range of numerical experiments that highlight the benefits and limitations of the two constructions for different problems and meshes.

Given a set of points together with a set of simplices we show how to compute weights associated with the points such that the weighted Delaunay triangulation of the point set contains the simplices, if possible. For a given triangulated surface, this process provides a tetrahedral mesh conforming to the triangulation, i.e. solves the problem of meshing the triangulated surface without inserting additional vertices. The restriction to weighted Delaunay triangulations ensures that the orthogonal dual mesh is embedded, facilitating common geometry processing tasks. We show that the existence of a single simplex in a weighted Delaunay triangulation for given vertices amounts to a set of linear inequalities, one for each vertex. This means that the number of inequalities for a given triangle mesh is quadratic in the number of mesh elements, making the naive approach impractical. We devise an algorithm that incrementally selects a small subset of inequalities, repeatedly updating the weights, until the weighted Delaunay triangulation contains all constrained simplices or the problem becomes infeasible. Applying this algorithm to a range of triangle meshes commonly used graphics demonstrates that many of them admit a conforming weighted Delaunay triangulation, in contrast to conforming or constrained Delaunay that require additional vertices to split the input primitives.

In this paper, we establish the underlying foundations of mechanisms that are composed of cell structures---known as metamaterial mechanisms. Such metamaterial mechanisms were previously shown to implement complete mechanisms in the cell structure of a 3D printed material, without the need for assembly. However, their design is highly challenging. A mechanism consists of many cells that are interconnected and impose constraints on each other. This leads to unobvious and non-linear behavior of the mechanism, which impedes user design. In this work, we investigate the underlying topological constraints of such cell structures and their influence on the resulting mechanism. Based on these findings, we contribute a computational design tool that automatically creates a metamaterial mechanism from user-defined motion paths. This tool is only feasible because our novel abstract representation of the global constraints highly reduces the search space of possible cell arrangements.

Humans involuntarily move their eyes when retrieving an image from memory. This motion is often similar to actually observing the image. We suggest to exploit this behavior as a new modality in human computer interaction, using the motion of the eyes as a descriptor of the image. Interaction requires the user's eyes to be tracked but no voluntary physical activity. We perform a controlled experiment and develop matching techniques using machine learning to investigate if images can be discriminated based on the gaze patterns recorded while users merely think about image. Our results indicate that image retrieval is possible with an accuracy significantly above chance. We also show that this result generalizes to images not used during training of the classifier and extends to uncontrolled settings in a realistic scenario.

We introduce ABC-Dataset, a collection of one million Computer-Aided Design (CAD) models for research of geometric deep learning methods and applications. Each model is a collection of explicitly parametrized curves and surfaces, providing ground truth for differential quantities, patch segmentation, geometric feature detection, and shape reconstruction. Sampling the parametric descriptions of surfaces and curves allows generating data in different formats and resolutions, enabling fair comparisons for a wide range of geometric learning algorithms. As a use case for our dataset, we perform a large-scale benchmark for estimation of surface normals, comparing existing data driven methods and evaluating their performance against both the ground truth and traditional normal estimation methods.

Abstract Many applications in geometry processing require the computation of local parameterizations on a surface mesh at interactive rates. A popular approach is to compute local exponential maps, i.e. parameterizations that preserve distance and angle to the origin of the map. We extend the computation of geodesic distance by heat diffusion to also determine angular information for the geodesic curves. This approach has two important benefits compared to fast approximate as well as exact forward tracing of the distance function: First, it allows generating smoother maps, avoiding discontinuities. Second, exploiting the factorization of the global Laplace–Beltrami operator of the mesh and using recent localized solution techniques, the computation is more efficient even compared to fast approximate solutions based on Dijkstra's algorithm.

Head-mounted displays cause discomfort. This is commonly attributed to conflicting depth cues, most prominently between vergence, which is consistent with object depth, and accommodation, which is adjusted to the near eye displays. It is possible to adjust the camera parameters, specifically interocular distance and vergence angles, for rendering the virtual environment to minimize this conflict. This requires dynamic adjustment of the parameters based on object depth. In an experiment based on a visual search task, we evaluate how dynamic adjustment affects visual comfort compared to fixed camera parameters. We collect objective as well as subjective data. Results show that dynamic adjustment decreases common objective measures of visual comfort such as pupil diameter and blink rate by a statistically significant margin. The subjective evaluation of categories such as fatigue or eye irritation shows a similar trend but was inconclusive. This suggests that rendering with fixed camera parameters is the better choice for head-mounted displays, at least in scenarios similar to the ones used here.

We introduce the notion of harmonic triangulations: a harmonic triangulation simultaneously minimizes the Dirichlet energy of all piecewise linear functions. By a famous result of Rippa, Delaunay triangulations are the harmonic triangulations of planar point sets. We prove by explicit counterexample that in 3D a harmonic triangulation does not exist in general. However, we show that bistellar flips are harmonic: if they decrease Dirichlet energy for one set of function values, they do so for all. This observation gives rise to the notion of locally harmonic triangulations. We demonstrate that locally harmonic triangulations can be efficiently computed, and efficiently reduce sliver tetrahedra. The notion of harmonic triangulation also gives rise to a scalar measure of the quality of a triangulation, which can be used to prioritize flips and optimize the position of vertices. Tetrahedral meshes generated by optimizing this function generally show better quality than Delaunay-based optimization techniques.

Most additive manufacturing processes fabricate objects by stacking planar layers of solidified material. As a result, produced parts exhibit a so-called staircase effect, which results from sampling slanted surfaces with parallel planes. Using thinner slices reduces this effect, but it always remains visible where layers almost align with the input surfaces. In this research we exploit the ability of some additive manufacturing processes to deposit material slightly out of plane to dramatically reduce these artifacts. We focus in particular on the widespread Fused Filament Fabrication (FFF) technology, since most printers in this category can deposit along slightly curved paths, under deposition slope and thickness constraints. Our algorithm curves the layers, making them either follow the natural slope of the input surface or on the contrary, make them intersect the surfaces at a steeper angle thereby improving the sampling quality. Rather than directly computing curved layers, our algorithm optimizes for a deformation of the model which is then sliced with a standard planar approach. We demonstrate that this approach enables us to encode all fabrication constraints, including the guarantee of generating collision-free toolpaths, in a convex optimization that can be solved using a QP solver. We produce a variety of models and compare print quality between curved deposition and planar slicing.

We present OptiSpace, a system for the automated placement of perspectively corrected projection mapping content. We analyze the geometry of physical surfaces and the viewing behavior of users over time using depth cameras. Our system measures user view behavior and simulates a virtual projection mapping scene users would see if content were placed in a particular way. OptiSpace evaluates the simulated scene according to perceptual criteria, including visibility and visual quality of virtual content. Finally, based on these evaluations, it optimizes content placement, using a two-phase procedure involving adaptive sampling and the covariance matrix adaptation algorithm. With our proposed architecture, projection mapping applications are developed without any knowledge of the physical layouts of the target environments. Applications can be deployed in different uncontrolled environments, such as living rooms and office spaces.

A common operation in geometry processing is solving symmetric and positive semi-definite systems on a subset of a mesh, with conditions for the vertices at the boundary of the region. This is commonly done by setting up the linear system for the sub-mesh, factorizing the system (potentially applying preordering to improve sparseness of the factors), and then solving by back-substitution. This approach suffers from a comparably high setup cost for each local operation. We propose to reuse factorizations defined on the full mesh to solve linear problems on sub-meshes. We show how an update on sparse matrices can be performed in a particularly efficient way to obtain the factorization of the operator on a sun-mesh significantly outperforming general factor updates and complete refactorization. We analyze the resulting speedup for a variety of situations and demonstrate that our method outperforms factorization of a new matrix by a factor of up to 10 while never being slower in our experiments.

We provide the first large dataset of human fixations on physical 3D objects presented in varying viewing conditions and made of different materials. Our experimental setup is carefully designed to allow for accurate calibration and measurement. We estimate a mapping from the pair of pupil positions to 3D coordinates in space and register the presented shape with the eye tracking setup. By modeling the fixated positions on 3D shapes as a probability distribution, we analysis the similarities among different conditions. The resulting data indicates that salient features depend on the viewing direction. Stable features across different viewing directions seem to be connected to semantically meaningful parts. We also show that it is possible to estimate the gaze density maps from view dependent data. The dataset provides the necessary ground truth data for computational models of human perception in 3D.

We present an approach to alter the perceived appearance of physical objects by controlling their surrounding space. Many real-world objects cannot easily be equipped with displays or actuators in order to change their shape. While common approaches such as projection mapping enable changing the appearance of objects without modifying them, certain surface properties (e.g. highly reflective or transparent surfaces) can make employing these techniques difficult. In this work, we present a conceptual design exploration on how the appearance of an object can be changed by solely altering the space around it, rather than the object itself. In a proof-of-concept implementation, we place objects onto a tabletop display and track them together with users to display perspective-corrected 3D graphics for augmentation. This enables controlling properties such as the perceived size, color, or shape of objects. We characterize the design space of our approach and demonstrate potential applications. For example, we change the contour of a wallet to notify users when their bank account is debited. We envision our approach to gain in importance with increasing ubiquity of display surfaces.

We present HeatSpace, a system that records and empirically analyzes user behavior in a space and automatically suggests positions and sizes for new displays. The system uses depth cameras to capture 3D geometry and users' perspectives over time. To derive possible display placements, it calculates volumetric heatmaps describing geometric persistence and planarity of structures inside the space. It evaluates visibility of display poses by calculating a volumetric heatmap describing occlusions, position within users' field of view, and viewing angle. Optimal display size is calculated through a heatmap of average viewing distance. Based on the heatmaps and user constraints we sample the space of valid display placements and jointly optimize their positions. This can be useful when installing displays in multi-display environments such as meeting rooms, offices, and train stations.

We define Voronoi cells and centroids based on heat diffusion. These heat cells and heat centroids coincide with the common definitions in Euclidean spaces. On curved surfaces they compare favorably with definitions based on geodesics: they are smooth and can be computed in a stable way with a single linear solve. We analyze the numerics of this approach and can show that diffusion diagrams converge quadratically against the smooth case under mesh refinement, which is better than other common discretization of distance measures in curved spaces. By factorizing the system matrix in a preprocess, computing Voronoi diagrams or centroids amounts to just back-substitution. We show how to localize this operation so that the complexity is linear in the size of the cells and not the underlying mesh. We provide several example applications that show how to benefit from this approach.

Abstract Polygon meshes with 3‐valent vertices often occur as the frame of free‐form surfaces in architecture, in which rigid beams are connected in rigid joints. For modelling such meshes, it is desirable to measure the deformation of the joints' shapes. We show that it is natural to represent joint shapes as points in hyperbolic 3‐space. This endows the space of joint shapes with a geometric structure that facilitates computation. We use this structure to optimize meshes towards different constraints, and we believe that it will be useful for other applications as well.

Slicing is the procedure necessary to prepare a shape for layered manufacturing. There are degrees of freedom in this process, such as the starting point of the slicing sequence and the thickness of each slice. The choice of these parameters influences the manufacturing process and its result: The number of slices significantly affects the time needed for manufacturing, while their thickness affects the error. Assuming a discrete setting, we measure the error as the number of voxels that are incorrectly assigned due to slicing. We provide an algorithm that generates, for a given set of available slice heights and a shape, a slicing that is provably optimal. By optimal, we mean that the algorithm generates sequences with minimal error for any possible number of slices. The algorithm is fast and flexible, that is, it can accommodate a user driven importance modulation of the error function and allows the interactive exploration of the desired quality/time tradeoff. We demonstrate the practical importance of our optimization on several three-dimensional-printed results.

Computing solutions to linear systems is a fundamental building block of many geometry processing algorithms. In many cases the Cholesky factorization of the system matrix is computed to subsequently solve the system, possibly for many right-hand sides, using forward and back substitution. We demonstrate how to exploit sparsity in both the right-hand side and the set of desired solution values to obtain significant speedups. The method is easy to implement and potentially useful in any scenarios where linear problems have to be solved locally. We show that this technique is useful for geometry processing operations, in particular we consider the solution of diffusion problems. All problems profit significantly from sparse computations in terms of runtime, which we demonstrate by providing timings for a set of numerical experiments.

We propose combining shape-changing interfaces and spatial augmented reality for extending the space of appearances and interactions of actuated interfaces. While shape-changing interfaces can dynamically alter the physical appearance of objects, the integration of spatial augmented reality additionally allows for dynamically changing objects' optical appearance with high detail. This way, devices can render currently challenging features such as high frequency texture or fast motion. We frame this combination in the context of computer graphics with analogies to established techniques for increasing the realism of 3D objects such as bump mapping. This extensible framework helps us identify challenges of the two techniques and benefits of their combination. We utilize our prototype shape-changing device enriched with spatial augmented reality through projection mapping to demonstrate the concept. We present a novel mechanical distance-fields algorithm for real-time fitting of mechanically constrained shape-changing devices to arbitrary 3D graphics. Furthermore, we present a technique for increasing effective screen real estate for spatial augmented reality through view-dependent shape change.

We present physical interfaces that change their appearance through controlled transparency. These transparency-controlled physical interfaces are well suited for applications where communication through optical appearance is sufficient, such as ambient display scenarios. They transition between perceived shapes within milliseconds, require no mechanically moving parts and consume little energy. We build 3D physical interfaces with individually controllable parts by laser cutting and folding a single sheet of transparency-controlled material. Electrical connections are engraved in the surface, eliminating the need for wiring individual parts. We consider our work as complementary to current shape-changing interfaces. While our proposed interfaces do not exhibit dynamic tangible qualities, they have unique benefits such as the ability to create apparent holes or nesting of objects. We explore the benefits of transparency-controlled physical interfaces by characterizing their design space and showcase four physical prototypes: two activity indicators, a playful avatar, and a lamp shade with dynamic appearance.

Light field displays allow viewers to see view-dependent 3D content as if looking through a window; however, existing work on light field display interaction is limited. Yet, they have the potential to parallel 2D pen and touch screen systems, which present a joint input and display surface for natural interaction. We propose a 4D display and interaction space using a dual-purpose lenslet array, which combines light field display and light field pen sensing, and allows us to estimate the 3D position and 2D orientation of the pen. This method is simple, fast (150Hz), with position accuracy of 2-3mm and precision of 0.2-0.6mm from 0-350mm away from the lenslet array, and orientation accuracy of 2 degrees and precision of 0.2-0.3 degrees within a 45 degree field of view. Further, we 3D print the lenslet array with embedded baffles to reduce out-of-bounds cross-talk, and use an optical relay to allow interaction behind the focal plane. We demonstrate our joint display/sensing system with interactive light field painting.

Abstract A discrete Laplace‐Beltrami operator is called perfect if it possesses all the important properties of its smooth counterpart. It is known which triangle meshes admit perfect Laplace operators and how to fix any other mesh by changing the combinatorics. We extend the characterization of meshes that admit perfect Laplacians to general polygon meshes. More importantly, we provide an algorithm that computes a perfect Laplace operator for any polygon mesh without changing the combinatorics, although, possibly changing the embedding. We evaluate this algorithm and demonstrate it at applications.

Abstract We consider the problem of manufacturing free‐form geometry with classical manufacturing techniques, such as mold casting or 3‐axis milling. We determine a set of constraints that are necessary for manufacturability and then decompose and, if necessary, deform the shape to satisfy the constraints per segment. We show that many objects can be generated from a small number of (mold‐)pieces if slight deformations are acceptable. We provide examples of actual molds and the resulting manufactured objects.

Abstract Within this paper, we present a novel, straightforward progressive encoding scheme for general triangle soups, which is particularly well‐suited for mobile and Web‐based environments due to its minimal requirements on the client's hardware and software. Our rapid encoding method uses a hierarchy of quantization to effectively reorder the original primitive data into several nested levels of detail. The resulting stateless buffer can progressively be transferred as‐is to the GPU, where clustering is efficiently performed in parallel during rendering. We combine our approach with a crack‐free mesh partitioning scheme to obtain a straightforward method for fast streaming and basic view‐dependent LOD control.

Abstract ShadowPixare white surfaces that display several prescribed images formed by the self‐shadowing of the surface when lit from certain directions. The effect is surprising and not commonly seen in the real world. We present algorithms for constructingShadowPixthat allow up to four images to be embedded in a single surface. ShadowPixcan produce a variety of unusual effects depending on the embedded images: moving the light can animate or relight the object in the image, or three colored lights may be used to produce a single colored image. ShadowPixare easy to manufacture using a 3D printer and we present photographs, videos, and renderings demonstrating these effects.

Abstract We introduce an algorithm and representation for fabricating 3D shape abstractions using mutually intersecting planar cut‐outs. The planes have prefabricated slits at their intersections and are assembled by sliding them together. Often such abstractions are used as a sculptural art form or in architecture and are colloquially called ‘cardboard sculptures’. Based on an analysis of construction rules, we propose an extended binary space partitioning tree as an efficient representation of such cardboard models which allows us to quickly evaluate the feasibility of newly added planar elements. The complexity of insertion order quickly increases with the number of planar elements and manual analysis becomes intractable. We provide tools for generating cardboard sculptures with guaranteed constructibility. In combination with a simple optimization and sampling strategy for new elements, planar shape abstraction models can be designed by iteratively adding elements. As an output, we obtain a fabrication plan that can be printed or sent to a laser cutter. We demonstrate the complete process by designing and fabricating cardboard models of various well‐known 3D shapes.

Humans have used sketching to depict our visual world since prehistoric times. Even today, sketching is possibly the only rendering technique readily available to all humans. This paper is the first large scale exploration of human sketches. We analyze the distribution of non-expert sketches of everyday objects such as 'teapot' or 'car'. We ask humans to sketch objects of a given category and gather 20,000 unique sketches evenly distributed over 250 object categories. With this dataset we perform a perceptual study and find that humans can correctly identify the object category of a sketch 73% of the time. We compare human performance against computational recognition methods. We develop a bag-of-features sketch representation and use multi-class support vector machines, trained on our sketch dataset, to classify sketches. The resulting recognition method is able to identify unknown sketches with 56% accuracy (chance is 0.4%). Based on the computational model, we demonstrate an interactive sketch recognition system. We release the complete crowd-sourced dataset of sketches to the community.

We develop a system for 3D object retrieval based on sketched feature lines as input. For objective evaluation, we collect a large number of query sketches from human users that are related to an existing data base of objects. The sketches turn out to be generally quite abstract with large local and global deviations from the original shape. Based on this observation, we decide to use a bag-of-features approach over computer generated line drawings of the objects. We develop a targeted feature transform based on Gabor filters for this system. We can show objectively that this transform is better suited than other approaches from the literature developed for similar tasks. Moreover, we demonstrate how to optimize the parameters of our, as well as other approaches, based on the gathered sketches. In the resulting comparison, our approach is significantly better than any other system described so far.

Abstract This work deals with the problem of automatically choosing the correct exposure (or integration) time for time‐of‐flight depth image capturing. We apply methods known from high dynamic range imaging to combine depth images taken with differing integration times in order to produce high quality depth maps. We evaluate the quality of these depth maps by comparing the performance in reconstruction of planar textured patches and in the 3D reconstruction of an indoor scene. Our solution is fast enough to capture the images at interactive frame rates and also flexible to deal with any amount of exposures.

While the theory and applications of discrete Laplacians on triangulated surfaces are well developed, far less is known about the general polygonal case. We present here a principled approach for constructing geometric discrete Laplacians on surfaces with arbitrary polygonal faces, encompassing non-planar and non-convex polygons. Our construction is guided by closely mimicking structural properties of the smooth Laplace--Beltrami operator. Among other features, our construction leads to an extension of the widely employed cotan formula from triangles to polygons. Besides carefully laying out theoretical aspects, we demonstrate the versatility of our approach for a variety of geometry processing applications, embarking on situations that would have been more difficult to achieve based on geometric Laplacians for simplicial meshes or purely combinatorial Laplacians for general meshes.

We introduce a benchmark for evaluating the performance of large-scale sketch-based image retrieval systems. The necessary data are acquired in a controlled user study where subjects rate how well given sketch/image pairs match. We suggest how to use the data for evaluating the performance of sketch-based image retrieval systems. The benchmark data as well as the large image database are made publicly available for further studies of this type. Furthermore, we develop new descriptors based on the bag-of-features approach and use the benchmark to demonstrate that they significantly outperform other descriptors in the literature.

Abstract In the style of binary shading, shape and illumination are depicted using two colours, typically black and white, which form coherent lines and regions in the image. We formulate the problem of assigning colours in the rendered image as an energy minimization, computed using graph cut on the image grid. The terms of this energy come from two sources: appearance (shading) and geometry (depth and curvature). Our contributions are in the use of geometric information in determining colours, and how this information is incorporated into a graph cut approach. This optimization yields boundaries between black and white regions that tend towards being shorter and to run along geometric features like creases. We show a range of results, and demonstrate that this approach produces more coherent images than simpler approaches that make local decisions when assigning colours, or that do not use geometry.

Abstract Interpolating vertex positions among triangle meshes with identical vertex‐edge graphs is a fundamental part of many geometric modelling systems. Linear vertex interpolation is robust but fails to preserve local shape. Most recent approaches identify local affine transformations for parts of the mesh, model desired interpolations of the affine transformations, and then optimize vertex positions to conform with the desired transformations. However, the local interpolation of the rotational part is non‐trivial for more than two input configurations and ambiguous if the meshes are deformed significantly. We propose a solution to the vertex interpolation problem that starts from interpolating the local metric (edge lengths) and mean curvature (dihedral angles) and makes consistent choices of local affine transformations using shape matching applied to successively larger parts of the mesh. The local interpolation can be applied to any number of input vertex configurations and due to the hierarchical scheme for generating consolidated vertex positions, the approach is fast and can be applied to very large meshes.

We describe how to create relief surfaces whose diffuse reflection approximates given images under known directional illumination. This allows using any surface with a significant diffuse reflection component as an image display. We propose a discrete model for the area in the relief surface that corresponds to a pixel in the desired image. This model introduces the necessary degrees of freedom to overcome theoretical limitations in shape from shading and practical requirements such as stability of the image under changes in viewing condition and limited overall variation in depth. The discrete surface is determined using an iterative least squares optimization. We show several resulting relief surfaces conveying one image for varying lighting directions as well as two images for two specific lighting directions.

A central problem in computer graphics is finding optimal sampling conditions for a given surface representation. We propose a new method to solve this problem based on spectral analysis of manifolds which results in faithful reconstructions and high quality isotropic samplings, is efficient, out-of-core, feature sensitive, intuitive to control and simple to implement. We approach the problem in a novel way by utilizing results from spectral analysis, kernel methods, and matrix perturbation theory. Change in a manifold due to a single point is quantified by a local measure that limits the change in the Laplace-Beltrami spectrum of the manifold. Hence, we do not need to explicitly compute the spectrum or any global quantity, which makes our algorithms very efficient. Although our main focus is on sampling surfaces, the analysis and algorithms are general and can be applied for simplifying and resampling point clouds lying near a manifold of arbitrary dimension.

In this paper we present an algorithm for watertight meshing of closed, sketched curves. The sketch is resampled as a piecewise linear (PWL) curve and placed onto a triangular grid. A small boundary (seed) that describes a closed path along grid points is placed inside the sketch and grown until it resembles the sketch. Vertices of the evolved grid boundary are projected onto the stroke to establish a bijective, ordered mapping. Finally, valences along the boundary are optimized while retaining the previously established mapping. The resulting mesh patch can be duplicated, stitched and inflated to generate a new shape, or used to fill a hole in an existing shape. We have implemented our algorithm in FiberMesh, an interactive sketch based interface for designing freeform surfaces, where it is used for the all mesh generation processes. The triangulation generated with our algorithm improves the quality of the model by reducing the number of irregular vertices, while running at real time rates.

Point set surfaces define a (typically) manifold surface from a set of scattered points. The definition involves weighted centroids and a gradient field. The data points are interpolated if singular weight functions are used to define the centroids. While this way of deriving an interpolatory scheme appears natural, we show that it has two deficiencies: Convexity of the input is not preserved and the extension to Hermite data is numerically unstable. We present a generalization of the standard scheme that we call Hermite point set surface . It allows interpolating, given normal constraints in a stable way. It also yields an intuitive parameter for shape control and preserves convexity in most situations. The analysis of derivatives also leads to a more natural way to define normals, in case they are not supplied with the point data. We conclude by comparing to similar surface definitions.

The idea of Phong Shading is applied to subdivision surfaces: normals are associated with vertices and the same construction is used for both locations and normals. This creates vertex positions and normals. The vertex normals are smoother than the normals of the subdivision surface and using vertex normals for shading attenuates the well known visual artifacts of many subdivision schemes. We demonstrate how to apply subdivision to normals and how blend and combine different normals for achieving a variety of effects.

Modern 3D engines used in real-time applications provide shading that hides the lack of higher order continuity inside the shapes using modulated normals, textures, and tone-mapping -- artifacts remain only on interior contours and silhouettes if the surface geometry is not smooth. The basic idea in this paper is to apply a purely local refinement strategy that inflates the geometry enough to avoid these artifacts. Our technique is a geometric version of Phong normal interpolation, not applied on normals but on the vertex positions. We call this strategy Phong Tessellation.

This paper presents a system for designing freeform surfaces with a collection of 3D curves. The user first creates a rough 3D model by using a sketching interface. Unlike previous sketching systems, the user-drawn strokes stay on the model surface and serve as handles for controlling the geometry. The user can add, remove, and deform these control curves easily, as if working with a 2D line drawing. The curves can have arbitrary topology; they need not be connected to each other. For a given set of curves, the system automatically constructs a smooth surface embedding by applying functional optimization. Our system provides real-time algorithms for both control curve deformation and the subsequent surface optimization. We show that one can create sophisticated models using this system, which have not yet been seen in previous sketching or functional optimization systems.

We discuss a shape representation based on a set of disconnected (planar) polygons. The polygons are computed by creating a BSP that contains approximately linear surface patches in each cell. This is achieved by employing two heuristics for finding appropriate split planes in each cell. Leaf nodes in the BSP tree represent either polygonal surface approximations or empty (clip) cells rather than split planes. We show that the resulting set of disconnected primitives typically leads to a better two-sided Hausdorff error for a given number of primitives than meshes. The BSP cells can be coded with few bits and, consequently, the tree is a compact shape representation. The special properties of BSPs are very useful in applications that need to perform spatial queries on the primitives, such as for occlusion and view frustum culling, and proximity or collision tests

Abstract Point Set Surfaces define smooth surfaces from regular samples based on weighted averaging of the points. Because weighting is done based on a spatial scale parameter, point set surfaces apply basically only to regular samples. We suggest to attach individual weight functions to each sample rather than to the location in space. This extends Point Set Surfaces to irregular settings, including anisotropic sampling adjusting to the principal curvatures of the surface. In particular, we describe how to represent surfaces with ellipsoidal weight functions per sample. Details of deriving such a representation from typical inputs and computing points on the surface are discussed.

A piecewise smooth surface, possibly with boundaries, sharp edges, corners, or other features is defined by a set of samples. The basic idea is to model surface patches, curve segments and points explicitly, and then to glue them together based on explicit connectivity information. The geometry is defined as the set of stationary points of a projection operator, which is generalized to allow modeling curves with samples, and extended to account for the connectivity information. Additional tangent constraints can be used to model shapes with continuous tangents across edges and corners.

We present a sampling strategy and rendering framework for intersectable models, whose surface is implicitly defined by a black box intersection test that provides the location and normal of the closest intersection of a ray with the surface. To speed up image generation despite potentially slow intersection tests, our method exploits spatial coherence by adjusting the sampling resolution in image space to the surface variation in object space. The result is a set of small, view-dependent bilinear surface approximations, which are rendered as quads using conventional graphics hardware. The advantage of this temporary rendering representation is two-fold: First, rendering is performed on the GPU, leaving CPU time for ray intersection computation. As the number of primitives is typically small, complex per vertex or per fragment programs can be used to achieve a variety of rendering effects. Second, bilinear surface approximations are derived from the geometry and can be reused in other views. Here, graphics hardware is exploited to determine the subset of image space in need of re-sampling. We demonstrate our system by ray casting an implicit surface defined from point samples, for which current ray-surface intersection computations are usually too slow to generate images at interactive rates.

In this paper we present a method for the intuitive editing of surface meshes by means of view-dependent sketching. In most existing shape deformation work, editing is carried out by selecting and moving a handle , usually a set of vertices. Our system lets the user easily determine the handle, either by silhouette selection and cropping, or by sketching directly onto the surface. Subsequently, an edit is carried out by sketching a new, view-dependent handle position or by indirectly influencing differential properties along the sketch. Combined, these editing and handle metaphors greatly simplify otherwise complex shape modeling tasks.

Bounding volumes are crucial for culling in interactive graphics applications. For dynamic shapes, computing a bounding volume for each frame could be very expensive. We analyze the situation for a particular class of dynamic geometry, namely, shapes resulting from the linear interpolation of several base shapes. The space of weights for the linear combination can be decomposed into cells so that in each cell a particular vertex is maximal (resp. minimal) in a given direction. This cell decomposition of the weight space allows deriving bounding volumes from the weight vectors rather than the generated geometry. We present algorithms to generate the cell decomposition, to map from weights to cells, and to efficiently compute the necessary data structures. This approach to computing bounding volumes for dynamic shapes proves to be beneficial if the geometry representation is large compared to the number of base shapes.

Patch-based texture synthesis has proven to produce high quality textures faster than pixel-based approaches. Previous algorithms differ in how the regions of overlap between neighboring patches are treated. We present an approach that produces higher quality overlap regions than simple blending of patches or computing good boundaries, however, that is faster than resynthesizing invalid pixels using a classical per-pixel synthesis algorithm: we use a k-nearest neighbor (knn) data structure, obtained from the input texture in a precomputation step. Results from our implementation show that the algorithm produces high-quality textures, where the time complexity of the synthesis stage is linear in the number of resynthesized pixels and, therefore, scales well with the size of the input texture

We present an approach to surface approximation from points that allows reconstructing surfaces with boundaries, including globally nonorientable surfaces. The surface is defined implicitly using directions of weighted covariances and weighted averages of the points. Specifically, a point belongs to the surface, if its direction to the weighted average has no component into the direction of smallest covariance. For bounded surfaces, we require in addition that any point on the surface is close to the weighted average of the input points. We compare this definition to alternatives and discuss the details and parameter choices. Points on the surface can be determined by intersection computations. We show that the computation is local and, therefore, no globally consistent orientation of normals is needed. Continuity of the surfaces is not affected by the particular choice of local orientation. We demonstrate our approach by rendering several bounded (and nonorientable) surfaces using ray casting.

Sampling complex, real-world geometry with range scanning devices almost always yields imperfect surface samplings. These "holes" in the surface are commonly filled with a smooth patch that conforms with the boundary. We introduce a context-based method: the characteristics of the given surface are analyzed, and the hole is iteratively filled by copying patches from valid regions of the given surface. In particular, the method needs to determine best matching patches, and then, fit imported patches by aligning them with the surrounding surface. The completion process works top down, where details refine intermediate coarser approximations. To align an imported patch with the existing surface, we apply a rigid transformation followed by an iterative closest point procedure with non-rigid transformations. The surface is essentially treated as a point set, and local implicit approximations aid in measuring the similarity between two point set patches. We demonstrate the method at several point-sampled surfaces, where the holes either result from imperfect sampling during range scanning or manual removal.

Point set surfaces (PSS) are a smooth manifold surface approximation from a set of sample points. The surface definition is based on a projection operation that constructs local polynomial approximations and respects a minimum feature size. We present techniques for ray tracing PSSs. For the computation of ray-surface intersection the properties of the projection operation are exploited. The surface is enclosed by a union of minimum feature size spheres. A ray is intersected with the spheres first and inside the spheres with local polynomial approximations. Our results show that 2-3 projections are sufficient to accurately intersect a ray with the surface.

Progressive point set surfaces (PPSS) are a multilevel point-based surface representation. They combine the usability of multilevel scalar displacement maps (e.g., compression, filtering, geometric modeling) with the generality of point-based surface representations (i.e., no fixed homology group or continuity class). The multiscale nature of PPSS fosters the idea of point-based modeling. The basic building block for the construction of PPSS is a projection operator, which maps points in the proximity of the shape onto local polynomial surface approximations. The projection operator allows the computing of displacements from smoother to more detailed levels. Based on the properties of the projection operator we derive an algorithm to construct a base point set. Starting from this base point set, a refinement rule using the projection operator constructs a PPSS from any given manifold surface.

We present a new shape representation, the multi-level partition of unity implicit surface, that allows us to construct surface models from very large sets of points. There are three key ingredients to our approach: 1) piecewise quadratic functions that capture the local shape of the surface, 2) weighting functions (the partitions of unity) that blend together these local shape functions, and 3) an octree subdivision method that adapts to variations in the complexity of the local shape.Our approach gives us considerable flexibility in the choice of local shape functions, and in particular we can accurately represent sharp features such as edges and corners by selecting appropriate shape functions. An error-controlled subdivision leads to an adaptive approximation whose time and memory consumption depends on the required accuracy. Due to the separation of local approximation and local blending, the representation is not global and can be created and evaluated rapidly. Because our surfaces are described using implicit functions, operations such as shape blending, offsets, deformations and CSG are simple to perform.

We advocate the use of point sets to represent shapes. We provide a definition of a smooth manifold surface from a set of points close to the original surface. The definition is based on local maps from differential geometry, which are approximated by the method of moving least squares (MLS). The computation of points on the surface is local, which results in an out-of-core technique that can handle any point set. We show that the approximation error is bounded and present tools to increase or decrease the density of the points, thus allowing an adjustment of the spacing among the points to control the error. To display the point set surface, we introduce a novel point rendering technique. The idea is to evaluate the local maps according to the image resolution. This results in high quality shading effects and smooth silhouettes at interactive frame rates.

This work investigates smoothing, fairing, or, more generally, filtering of mesh geometry. The approach transfers the ideas of optimal (Wiener) filtering to the setting of meshes. It extends fairing approaches that use only first order neighborhoods and allows to assume arbitrary local spectral properties of the mesh geometry. The definition of the local autocorrelation allows the design of filters for smoothing as well as for special effects in shape modeling.

Meshes have become a widespread and popular representation of models in computer graphics. Morphing techniques aim at transforming a given source shape into a target shape. Morphing techniques have various applications ranging from special effects in television and movies to medical imaging and scientific visualization. Not surprisingly, morphing techniques for meshes have received a lot of interest lately. This work sums up recent developments in the area of mesh morphing. It presents a consistent framework to classify and compare various techniques approaching the same underlying problems from different angles.

Geometric transformations are most commonly represented as square matrices in computer graphics. Following simple geometric arguments we derive a natural and geometrically meaningful definition of scalar multiples and a commutative addition of transformations based on the matrix representation, given that the matrices have no negative real eigenvalues. Together, these operations allow the linear combination of transformations. This provides the ability to create weighted combination of transformations, interpolate between transformations, and to construct or use arbitrary transformations in a structure similar to a basis of a vector space. These basic techniques are useful for synthesis and analysis of motions or animations. Animations through a set of key transformations are generated using standard techniques such as subdivision curves. For analysis and progressive compression a PCA can be applied to sequences of transformations. We describe an implementation of the techniques that enables an easy-to-use and transparent way of dealing with geometric transformations in graphics software. We compare and relate our approach to other techniques such as matrix decomposition and quaternion interpolation.

Mesh morphing techniques are capable of producing a sequence of meshes, gradually changing from a source to a target shape. However, current techniques do not allow to describe the local behavior of the morph. A solution to this problem is presented. The main idea is to describe mesh geometry in a differential way, thus, insertion of local features from one shape into another does not suffer from difference in absolute coordinates. Besides interesting possibilities for animation the technique proves to be a powerful modeling tool.

We advocate the use of point sets to represent shapes. We provide a definition of a smooth manifold surface from a set of points close to the original surface. The definition is based on local maps from differential geometry, which are approximated by the method of moving least squares (MLS). We present tools to increase or decrease the density of the points, thus, allowing an adjustment of the spacing among the points to control the fidelity of the representation. To display the point set surface, we introduce a novel point rendering technique. The idea is to evaluate the local maps according to the image resolution. This results in high quality shading effects and smooth silhouettes at interactive frame rates.

We present an object-space morphing technique that blends the interiors of given two- or three-dimensional shapes rather than their boundaries. The morph is rigid in the sense that local volumes are least-distorting as they vary from their source to target configurations. Given a boundary vertex correspondence, the source and target shapes are decomposed into isomorphic simplicial complexes. For the simplicial complexes, we find a closed-form expression allocating the paths of both boundary and interior vertices from source to target locations as a function of time. Key points are the identification of the optimal simplex morphing and the appropriate definition of an error functional whose minimization defines the paths of the vertices. Each pair of corresponding simplices defines an affine transformation, which is factored into a rotation and a stretching transformation. These local transformations are naturally interpolated over time and serve as the basis for composing a global coherent least-distorting transformation.

In this paper, we present a representation for three‐dimensional geometric animation sequences. Different from standard key‐frame techniques, this approach is based on the determination of principal animation components and decouples the animation from the underlying geometry. The new representation supports progressive animation compression with spatial, as well as temporal, level‐of‐detail and high compression ratios. The distinction of animation and geometry allows for mapping animations onto other objects.

The paper presents a technique for merging two genus 0 polyhedra. Merging establishes correspondences between vertices of the models as a first step in a 3D morphing process. The technique allows for the specification of scattered features to be aligned. This is accomplished by performing the following three steps: First, initial embeddings of the polyhedra on unit spheres are computed. Second, the embeddings are deformed such that user defined features (vertices) coincide on the spheres. Third, an overlay of the subdivisions is computed and the aligned vertices are fused in the merged model.