SGP: Eurographics Symposium on Geometry Processing

Permanent URI for this community

https://diglib.eg.org/handle/10.2312/434

Browse

Now showing 1 - 20 of 378

Approximating and Intersecting Surfaces from Points
(The Eurographics Association, 2003) Adamson, Anders; Alexa, Marc; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
Point sets become an increasingly popular shape representation. Most shape processing and rendering tasks require the approximation of a continuous surface from the point data. We present a surface approximation that is motivated by an efficient iterative ray intersection computation. On each point on a ray, a local normal direction is estimated as the direction of smallest weighted co-variances of the points. The normal direction is used to build a local polynomial approximation to the surface, which is then intersected with the ray. The distance to the polynomials essentially defines a distance field, whose zero-set is computed by repeated ray intersection. Requiring the distance field to be smooth leads to an intuitive and natural sampling criterion, namely, that normals derived from the weighted co-variances are well defined in a tubular neighborhood of the surface. For certain, well-chosen weight functions we can show that well-sampled surfaces lead to smooth distance fields with non-zero gradients and, thus, the surface is a continuously differentiable manifold. We detail spatial data structures and efficient algorithms to compute ray-surface intersections for fast ray casting and ray tracing of the surface.
Domain Decomposition for Multiresolution Analysis
(The Eurographics Association, 2003) Boier-Martin, Ioana M.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
This paper describes a method for converting an arbitrary mesh with irregular connectivity to a semi-regular multiresolution representation. A shape image encoding geometric and differential properties of the input model is computed. Standard image processing operations lead to an initial decomposition of the model that conforms to its salient features. A triangulation step performed on the resulting partition in image space, followed by resampling and multiresolution analysis in object space, complete the procedure. The conversion technique is automatic, takes into account surface properties for deriving a base domain, and is computationally efficient as the bulk of the processing is carried out in image space. Besides domain decomposition, our image-based approach to handling geometry may be used in the context of related applications, including model simplification, remeshing, and wireframe generation.
Efficient Max-Norm Distance Computation and Reliable Voxelization
(The Eurographics Association, 2003) Varadhan, Gokul; Krishnan, Shankar; Kim, Young J.; Diggavi, Suhas; Manocha, Dinesh; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We present techniques to efficiently compute the distance under max-norm between a point and a wide class of geometric primitives. We formulate the distance computation as an optimization problem and use this framework to design efficient algorithms for convex polytopes, algebraic primitives and triangulated models. We extend them to handle large models using bounding volume hierarchies, and use rasterization hardware followed by local refinement for higher-order primitives. We use the max-norm distance computation algorithm to design a reliable voxel-intersection test to determine whether the surface of a primitive intersects a voxel.We use this test to perform reliable voxelization of solids and generate adaptive distance fields that provides a Hausdorff distance guarantee between the boundary of the original primitives and the reconstructed surface.
Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors
(The Eurographics Association, 2003) Kazhdan, Michael; Funkhouser, Thomas; Rusinkiewicz, Szymon; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
One of the challenges in 3D shape matching arises from the fact that in many applications, models should be considered to be the same if they differ by a rotation. Consequently, when comparing two models, a similarity metric implicitly provides the measure of similarity at the optimal alignment. Explicitly solving for the optimal alignment is usually impractical. So, two general methods have been proposed for addressing this issue: (1) Every model is represented using rotation invariant descriptors. (2) Every model is described by a rotation dependent descriptor that is aligned into a canonical coordinate system defined by the model. In this paper, we describe the limitations of canonical alignment and discuss an alternate method, based on spherical harmonics, for obtaining rotation invariant representations. We describe the properties of this tool and show how it can be applied to a number of existing, orientation dependent descriptors to improve their matching performance. The advantages of this tool are two-fold: First, it improves the matching performance of many descriptors. Second, it reduces the dimensionality of the descriptor, providing a more compact representation, which in turn makes comparing two models more efficient.
A Geometric Database for Gene Expression Data
(The Eurographics Association, 2003) Ju, Tao; Warren, Joe; Eichele, Gregor; Thaller, Christina; Chiu, Wah; Carson, James; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
As the logical next step after sequencing the mouse genome, biologists have developed laboratory methods for rapidly determining where each of the 30K genes in the mouse genome is synthesizing protein. Applying these methods to the mouse brain, biologists are currently generating large numbers of 2D cross-sectional images that record the expression pattern for each gene in the mouse genome. In this paper, we describe the structure of a geometric database for the mouse brain that allows biologists to organize and search this gene expression data. The central component of this database is an atlas that explicitly partitions the mouse brain into key anatomical regions. This atlas is represented as a Catmull-Clark subdivision mesh with anatomical regions separated by a network of B-spline crease curves. New gene expression images are added to the database by deforming this atlas onto each image using techniques developed for fitting subdivision surfaces to scatter data. Due to this partitioning of the subdivision mesh, user queries comparing expression data between various genes can be restricted to anatomical regions without difficulty while the multi-resolution structure of the subdivision mesh allows these queries to be processed efficiently.
Estimating Differential Quantities Using Polynomial Fitting of Osculating Jets
(The Eurographics Association, 2003) Cazals, F.; Pouget, M.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
This paper addresses the pointwise estimation of differential properties of a smooth manifold S -a curve in the plane or a surface in 3D- assuming a point cloud sampled over S is provided. The method consists of fitting the local representation of the manifold using a jet, by either interpolating or approximating. A jet is a truncated Taylor expansion, and the incentive for using jets is that they encode all local geometric quantities - such as normal or curvatures. On the way to using jets, the question of estimating differential properties is recasted into the more general framework of multivariate interpolation/approximation, a well-studied problem in numerical analysis. On a theoretical perspective, we prove several convergence results when the samples get denser. For curves and surfaces, these results involve asymptotic estimates with convergence rates depending upon the degree of the jet used. For the particular case of curves, an error bound is also derived. To the best of our knowledge, these results are among the first ones providing accurate estimates for differential quantities of order three and more. On the algorithmic side, we solve the interpolation/approximation problem using Vandermonde systems. Experimental results for surfaces of R3 are reported. These experiments illustrate the asymptotic convergence results, but also the robustness of the methods on general Computer Graphics models.
Global Conformal Surface Parameterization
(The Eurographics Association, 2003) Gu, Xianfeng; Yau, Shing-Tung; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We solve the problem of computing global conformal parameterizations for surfaces with nontrivial topologies. The parameterization is global in the sense that it preserves the conformality everywhere except for a few points, and has no boundary of discontinuity. We analyze the structure of the space of all global conformal parameterizations of a given surface and find all possible solutions by constructing a basis of the underlying linear solution space. This space has a natural structure solely determined by the surface geometry, so our computing result is independent of connectivity, insensitive to resolution, and independent of the algorithms to discover it. Our algorithm is based on the properties of gradient fields of conformal maps, which are closedness, harmonity, conjugacy, duality and symmetry. These properties can be formulated by sparse linear systems, so the method is easy to implement and the entire process is automatic. We also introduce a novel topological modification method to improve the uniformity of the parameterization. Based on the global conformal parameterization of a surface, we can construct a conformal atlas and use it to build conformal geometry images which have very accurate reconstructed normals.
Stellar Subdivision Grammars
(The Eurographics Association, 2003) Velho, Luiz; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
In this paper we develop a new description for subdivision surfaces based on a graph grammar formalism. Subdivision schemes are specified by a context sensitive grammar in which production rules represent topological and geometrical transformations to the surface's control mesh. This methodology can be used for all known subdivision surface schemes. Moreover, it gives an effective representation that allows simple implementation and is suitable for adaptive computations.
A concise b-rep data structure for stratified subanalytic objects
(The Eurographics Association, 2003) Gomes, Abel J.P.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
Current geometric kernels suffer from poor abstraction and design of their data structures. In part, this is due to the lack of a general mathematical framework for geometric modelling and processing. As a result, there is a proliferation of ad hoc solutions, say external data structures, whenever new problems arise in industry, causing serious difficulties in software maintenance. This paper proposes such a framework based on subanalytic geometry and theory of stratifications, as well as a concise data structure for it, called DiX (Data in Xtratus). Basically, this is a non-manifold b-rep (boundary representation) data structure without oriented cells (e.g. half-edges, coedges or so). Thus, it is more concise than the traditional b-rep data structures provided that no oriented cells (e.g. half-edges, half-faces, etc.) are used at all. Nevertheless, all the adjacency and incidence data we need is retrieved by a single operator, called mask operator. Besides, the DiX data structure includes shape descriptors, as generalizations of loops and shells, to support shape reasoning as needed in the design and implementation of shape operators such as, for example, Euler operators.
3D Reconstruction Using Labeled Image Regions
(The Eurographics Association, 2003) Ziegler, Remo; Matusik, Wojciech; Pfister, Hanspeter; McMillan, Leonard; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
In this paper we present a novel algorithm for reconstructing 3D scenes from a set of images. The user defines a set of polygonal regions with corresponding labels in each image using familiar 2D photo-editing tools. Our reconstruction algorithm computes the 3D model with maximum volume that is consistent with the set of regions in the input images. The algorithm is fast, uses only 2D intersection operations, and directly computes a polygonal model. We implemented a user-assisted system for 3D scene reconstruction and show results on scenes that are difficult or impossible to reconstruct with other methods.
Edge-Sharpener: Recovering sharp features in triangulations of non-adaptively re-meshed surfaces
(The Eurographics Association, 2003) Attene, Marco; Falcidieno, Bianca; Rossignac, Jarek; Spagnuolo, Michela; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
3D scanners, iso-surface extraction procedures, and several recent geometric compression schemes sample surfaces of 3D shapes in a regular fashion, without any attempt to align the samples with the sharp edges and corners of the original shape. Consequently, the interpolating triangle meshes chamfer these sharp features and thus exhibit significant errors. The new Edge-Sharpener filter introduced here identifies the chamfer edges and subdivides them and their incident triangles by inserting new vertices and by forcing these vertices to lie on intersections of planes that locally approximate the smooth surfaces that meet at these sharp features. This post-processing significantly reduces the error produced by the initial sampling process. For example, we have observed that the L2 error introduced by the SwingWrapper9 remeshing-based compressor can be reduced down to a fifth by executing Edge-Sharpener after decompression, with no additional information.
Smooth Geometry Images
(The Eurographics Association, 2003) Losasso, F.; Hoppe, H.; Schaefer, S.; Warren, J.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
Previous parametric representations of smooth genus-zero surfaces require a collection of abutting patches (e.g. splines, NURBS, recursively subdivided polygons). We introduce a simple construction for these surfaces using a single uniform bi-cubic B-spline. Due to its tensor-product structure, the spline control points are conveniently stored as a geometry image with simple boundary symmetries. The bicubic surface is evaluated using subdivision, and the regular structure of the geometry image makes this computation ideally suited for graphics hardware. Specifically, we let the fragment shader pipeline perform subdivision by applying a sequence of masks (splitting, averaging, limit, and tangent) uniformly to the geometry image. We then extend this scheme to provide smooth level-of-detail transitions from a subsampled base octahedron all the way to a finely subdivided, smooth model. Finally, we show how the framework easily supports scalar displacement mapping.
Statistical Point Geometry
(The Eurographics Association, 2003) Kalaiah, Aravind; Varshney, Amitabh; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We propose a scheme for modeling point sample geometry with statistical analysis. In our scheme we depart from the current schemes that deterministically represent the attributes of each point sample. We show how the statistical analysis of a densely sampled point model can be used to improve the geometry bandwidth bottleneck and to do randomized rendering without sacrificing visual realism. We first carry out a hierarchical principal component analysis (PCA) of the model. This stage partitions the model into compact local geometries by exploiting local coherence. Our scheme handles vertex coordinates, normals, and color. The input model is reconstructed and rendered using a probability distribution derived from the PCA analysis. We demonstrate the benefits of this approach in all stages of the graphics pipeline: (1) orders of magnitude improvement in the storage and transmission complexity of point geometry, (2) direct rendering from compressed data, and (3) view-dependent randomized rendering.
Filling Holes in Meshes
(The Eurographics Association, 2003) Liepa, Peter; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We describe a method for filling holes in unstructured triangular meshes. The resulting patching meshes interpolate the shape and density of the surrounding mesh. Our methods work with arbitrary holes in oriented connected manifold meshes. The steps in filling a hole include boundary identification, hole triangulation, refinement, and fairing.
CLODs: Dual Hierarchies for Multiresolution Collision Detection
(The Eurographics Association, 2003) Otaduy, Miguel A.; Lin, Ming C.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We present "contact levels of detail" (CLOD), a novel concept for multiresolution collision detection. Given a polyhedral model, our algorithm automatically builds a "dual hierarchy", both a multiresolution representation of the original model and its bounding volume hierarchy for accelerating collision queries.We have proposed various error metrics, including object-space errors, velocity dependent gap, screen-space errors and their combinations. At runtime, our algorithm uses these error metrics to select the appropriate levels of detail independently at each potential contact location. Compared to the existing exact collision detection algorithms, we observe significant performance improvement using CLODs on some benchmarks, with little degradation in the visual rendering of simulations.
Simple Silhouettes for Complex Surfaces
(The Eurographics Association, 2003) Kirsanov, D.; Sander, P. V.; Gortler, S. J.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
Complex meshes tend to have intricate, detailed silhouettes. This paper proposes two algorithms for extracting a simpler, approximate silhouette from a high-resolution model. Our methods preserve the important features of the silhouette by using the silhouette of a coarser, simplified mesh as a guide. Our simple silhouettes have significantly fewer edges than the original silhouette, while still preserving its appearance.
Geometry Compression of Normal Meshes Using Rate-Distortion Algorithms
(The Eurographics Association, 2003) Lavu, Sridhar; Choi, Hyeokho; Baraniuk, Richard; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We propose a new rate-distortion based algorithm for compressing 3D surface geometry represented using triangular normal meshes. We apply the Estimation-Quantization (EQ) algorithm to compress normal mesh wavelet coefficients. The EQ algorithm models the wavelet coefficients as a Gaussian random field with slowly varying standard deviation that depends on the local neighborhood and uses rate-distortion optimal scalar quantizers. We achieve gains of 0.5 to 1 dB with the EQ algorithm compared to the recently proposed zerotree compression for normal meshes.
Explicit Surface Remeshing
(The Eurographics Association, 2003) Surazhsky, Vitaly; Gotsman, Craig; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We present a new remeshing scheme based on the idea of improving mesh quality by a series of local modifications of the mesh geometry and connectivity. Our contribution to the family of local modification techniques is an areabased smoothing technique. Area-based smoothing allows the control of both triangle quality and vertex sampling over the mesh, as a function of some criteria, e.g. the mesh curvature. To perform local modifications of arbitrary genus meshes we use dynamic patch-wise parameterization. The parameterization is constructed and updated onthe- fly as the algorithm progresses with local updates. As a post-processing stage, we introduce a new algorithm to improve the regularity of the mesh connectivity. The algorithm is able to create an unstructured mesh with a very small number of irregular vertices. Our remeshing scheme is robust, runs at interactive speeds and can be applied to arbitrary complex meshes.
Mesh Forging: Editing of 3D-Meshes Using Implicitly Defined Occluders
(The Eurographics Association, 2003) Bendels, G. H.; Klein, R.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
In recent years the ease of use and the flexibility in the editing process shifted into focus in modelling and animation applications. In this spirit we present a 3D mesh editing method that is similar to the simple constrained deformation (scodef) method 9. We extend this method to the so-called mesh forging paradigm by adding an occluder to the editing environment. Our method resembles and was in fact motivated by the forging process where an anvil is used to give the manipulated object the desired shape. While users perform the editing operation by directly manipulating the 3D-mesh, the occluder is defined implicitly. To enable fine detail edits even in sparsely triangulated areas, we propose an adaptive refinement method that also allows the creation of sharp features where desired. The functionality and ease of use of our editing approach is shown by several examples.
Approximate Implicitization Via Curve Fitting
(The Eurographics Association, 2003) Wurm, E.; Jüttler, B.; Leif Kobbelt and Peter Schroeder and Hugues Hoppe
We discuss methods for fitting implicitly defined (e.g. piecewise algebraic) curves to scattered data, which may contain problematic regions, such as edges, cusps or vertices. As the main idea, we construct a bivariate function, whose zero contour approximates a given set of points, and whose gradient field simultaneously approximates an estimated normal field. The coefficients of the implicit representation are found by solving a system of linear equations. In order to allow for problematic input data, we introduce a criterion for detecting points close to possible singularities. Using this criterion we split the data into segments and develop methods for propagating the orientation of the normals globally. Furthermore we present a simple fallback strategy, that can be used when the process of orientation propagation fails. The method has been shown to work successfully

Browse

Browsing SGP: Eurographics Symposium on Geometry Processing by Issue Date

Results Per Page

Sort Options