SGP03: Eurographics Symposium on Geometry Processing
Permanent URI for this collection
Geometry Compression of Normal Meshes Using Rate-Distortion Algorithms
[meta data] [files:
Lavu, Sridhar
;
Choi, Hyeokho
;
Baraniuk, Richard
High-Pass Quantization for Mesh Encoding
[meta data] [files:
Sorkine, Olga
;
Cohen-Or, Daniel
;
Toledo, Sivan
A concise b-rep data structure for stratified subanalytic objects
[meta data] [files:
Gomes, Abel J.P.
Edge-Sharpener: Recovering sharp features in triangulations of non-adaptively re-meshed surfaces
[meta data] [files:
Attene, Marco
;
Falcidieno, Bianca
;
Rossignac, Jarek
;
Spagnuolo, Michela
CLODs: Dual Hierarchies for Multiresolution Collision Detection
[meta data] [files:
Otaduy, Miguel A.
;
Lin, Ming C.
A scalable data structure for three-dimensional non-manifold objects
[meta data] [files:
Floriani, Leila De
;
Hui, Annie
Simple Silhouettes for Complex Surfaces
[meta data] [files:
Kirsanov, D.
;
Sander, P. V.
;
Gortler, S. J.
Efficient Max-Norm Distance Computation and Reliable Voxelization
[meta data] [files:
Varadhan, Gokul
;
Krishnan, Shankar
;
Kim, Young J.
;
Diggavi, Suhas
;
Manocha, Dinesh
Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors
[meta data] [files:
Kazhdan, Michael
;
Funkhouser, Thomas
;
Rusinkiewicz, Szymon
Multi-Chart Geometry Images
[meta data] [files:
Sander, P. V.
;
Wood, Z. J.
;
Gortler, S. J.
;
Snyder, J.
;
Hoppe, H.
A Geometric Database for Gene Expression Data
[meta data] [files:
Ju, Tao
;
Warren, Joe
;
Eichele, Gregor
;
Thaller, Christina
;
Chiu, Wah
;
Carson, James
Estimating Differential Quantities Using Polynomial Fitting of Osculating Jets
[meta data] [files:
Cazals, F.
;
Pouget, M.
Mesh Forging: Editing of 3D-Meshes Using Implicitly Defined Occluders
[meta data] [files:
Bendels, G. H.
;
Klein, R.
Approximating and Intersecting Surfaces from Points
[meta data] [files:
Adamson, Anders
;
Alexa, Marc
3D Reconstruction Using Labeled Image Regions
[meta data] [files:
Ziegler, Remo
;
Matusik, Wojciech
;
Pfister, Hanspeter
;
McMillan, Leonard
Browse
Recent Submissions
Item Provably Good Surface Sampling and Approximation(The Eurographics Association, 2003) Boissonnat, J-D.; Oudot, S.; Leif Kobbelt and Peter Schroeder and Hugues HoppeWe present an algorithm for meshing surfaces that is a simple adaptation of a greedy "farthest point" technique proposed by Chew. Given a surface S, it progressively adds points on S and updates the 3-dimensional Delaunay triangulation of the points. The method is very simple and works in 3d-space without requiring to parameterize the surface. Taking advantage of recent results on the restricted Delaunay triangulation, we prove that the algorithm can generate good samples on S as well as triangulated surfaces that approximate S. More precisely, we show that the restricted Delaunay triangulation Del??S of the points has the same topology type as S, that the Hausdorff distance between Del??S and S can be made arbitrarily small, and that we can bound the aspect ratio of the facets of Del??S. The algorithm has been implemented and we report on experimental results that provide evidence that it is very effective in practice. We present results on implicit surfaces, on CSG models and on polyhedra. Although most of our theoretical results are given for smooth closed surfaces, the method is quite robust in handling smooth surfaces with boundaries, and even non-smooth surfaces.Item Explicit Surface Remeshing(The Eurographics Association, 2003) Surazhsky, Vitaly; Gotsman, Craig; Leif Kobbelt and Peter Schroeder and Hugues HoppeWe 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.Item Domain Decomposition for Multiresolution Analysis(The Eurographics Association, 2003) Boier-Martin, Ioana M.; Leif Kobbelt and Peter Schroeder and Hugues HoppeThis 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.Item 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 HoppeWe 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.Item High-Pass Quantization for Mesh Encoding(The Eurographics Association, 2003) Sorkine, Olga; Cohen-Or, Daniel; Toledo, Sivan; Leif Kobbelt and Peter Schroeder and Hugues HoppeAny quantization introduces errors. An important question is how to suppress their visual effect. In this paper we present a new quantization method for the geometry of 3D meshes, which enables aggressive quantization without significant loss of visual quality. Conventionally, quantization is applied directly to the 3-space coordinates. This form of quantization introduces high-frequency errors into the model. Since high-frequency errors modify the appearance of the surface, they are highly noticeable, and commonly, this form of quantization must be done conservatively to preserve the precision of the coordinates. Our method first multiplies the coordinates by the Laplacian matrix of the mesh and quantizes the transformed coordinates which we call "d-coordinates". We show that the high-frequency quantization errors in the d-coordinates are transformed into low-frequency errors when the quantized d-coordinates are transformed back into standard Cartesian coordinates. These low-frequency errors in the model are much less noticeable than the high-frequency errors. We call our strategy high-pass quantization, to emphasize the fact that it tends to concentrate the quantization error at the low-frequency end of the spectrum. To allow some control over the shape and magnitude of the low-frequency quantization errors, we extend the Laplacian matrix by adding a number of spatial constraints. This enables us to tailor the quantization process to specific visual requirements, and to strongly quantize the d-coordinates.Item 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 HoppeCurrent 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.Item 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 Hoppe3D 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.Item CLODs: Dual Hierarchies for Multiresolution Collision Detection(The Eurographics Association, 2003) Otaduy, Miguel A.; Lin, Ming C.; Leif Kobbelt and Peter Schroeder and Hugues HoppeWe 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.Item A scalable data structure for three-dimensional non-manifold objects(The Eurographics Association, 2003) Floriani, Leila De; Hui, Annie; Leif Kobbelt and Peter Schroeder and Hugues HoppeIn this paper, we address the problem of representing and manipulating non-manifold, mixed-dimensional objects described by three-dimensional simplicial complexes embedded in the 3D Euclidean space. We describe the design and the implementation of a new data structure, that we call the non-manifold indexed data structure with adjacencies (NMIA), which can represent any three-dimensional Euclidean simplicial complex compactly, since it encodes only the vertices and the top simplexes of the complex plus a restricted subset of topological relations among simplexes. The NMIA structure supports efficient traversal algorithms which retrieve topological relations in optimal time, and it scales very well to the manifold case. Here, we sketch traversal algorithms, and we compare the NMIA structure with data structures for manifold and regular 3D simplicial complexes.Item Statistical Point Geometry(The Eurographics Association, 2003) Kalaiah, Aravind; Varshney, Amitabh; Leif Kobbelt and Peter Schroeder and Hugues HoppeWe 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.Item Simple Silhouettes for Complex Surfaces(The Eurographics Association, 2003) Kirsanov, D.; Sander, P. V.; Gortler, S. J.; Leif Kobbelt and Peter Schroeder and Hugues HoppeComplex 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.Item 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 HoppeWe 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.Item Global Conformal Surface Parameterization(The Eurographics Association, 2003) Gu, Xianfeng; Yau, Shing-Tung; Leif Kobbelt and Peter Schroeder and Hugues HoppeWe 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.Item Smooth Geometry Images(The Eurographics Association, 2003) Losasso, F.; Hoppe, H.; Schaefer, S.; Warren, J.; Leif Kobbelt and Peter Schroeder and Hugues HoppePrevious 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.Item 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 HoppeOne 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.Item Multi-Chart Geometry Images(The Eurographics Association, 2003) Sander, P. V.; Wood, Z. J.; Gortler, S. J.; Snyder, J.; Hoppe, H.; Leif Kobbelt and Peter Schroeder and Hugues HoppeWe introduce multi-chart geometry images, a new representation for arbitrary surfaces. It is created by resampling a surface onto a regular 2D grid. Whereas the original scheme of Gu et al. maps the entire surface onto a single square, we use an atlas construction to map the surface piecewise onto charts of arbitrary shape. We demonstrate that this added flexibility reduces parametrization distortion and thus provides greater geometric fidelity, particularly for shapes with long extremities, high genus, or disconnected components. Traditional atlas constructions suffer from discontinuous reconstruction across chart boundaries, which in our context create unacceptable surface cracks. Our solution is a novel zippering algorithm that creates a watertight surface. In addition, we present a new atlas chartification scheme based on clustering optimization.Item 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 HoppeAs 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.Item Estimating Differential Quantities Using Polynomial Fitting of Osculating Jets(The Eurographics Association, 2003) Cazals, F.; Pouget, M.; Leif Kobbelt and Peter Schroeder and Hugues HoppeThis 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.Item Stellar Subdivision Grammars(The Eurographics Association, 2003) Velho, Luiz; Leif Kobbelt and Peter Schroeder and Hugues HoppeIn 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.Item Filling Holes in Meshes(The Eurographics Association, 2003) Liepa, Peter; Leif Kobbelt and Peter Schroeder and Hugues HoppeWe 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.Item 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 HoppeIn 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.Item Approximating and Intersecting Surfaces from Points(The Eurographics Association, 2003) Adamson, Anders; Alexa, Marc; Leif Kobbelt and Peter Schroeder and Hugues HoppePoint 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.Item Approximate Implicitization Via Curve Fitting(The Eurographics Association, 2003) Wurm, E.; Jüttler, B.; Leif Kobbelt and Peter Schroeder and Hugues HoppeWe 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 successfullyItem A Geometric Convection Approach of 3-D Reconstruction(The Eurographics Association, 2003) Chaine, Raphaëlle; Leif Kobbelt and Peter Schroeder and Hugues HoppeThis paper introduces a fast and efficient algorithm for surface reconstruction. As many algorithms of this kind, it produces a piecewise linear approximation of a surface S from a finite, sufficiently dense, subset of its points. Originally, the starting point of this work does not come from the computational geometry field. It is inspired by an existing numerical scheme of surface convection developed by Zhao, Osher and Fedkiw. We have translated this scheme to make it depend on the geometry of the input data set only, and not on the precision of some grid around the surface. Our algorithm deforms a closed oriented pseudo-surface embedded in the 3D Delaunay triangulation of the sampled points, and the reconstructed surface consists of a set of oriented facets located in this 3D Delaunay triangulation. This paper provides an appropriate data structure to represent a pseudo-surface, together with operations that manage deformations and topological changes. The algorithm can handle surfaces with boundaries, surfaces of high genus and, unlike most of the other existing schemes, it does not involve a global heuristic. Its complexity is that of the 3D Delaunay triangulation of the points. We present some results of the method, which turns out to be efficient even on noisy input data.Item 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 HoppeIn 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.