Fixing Geometric Errors on Polygonal Models: A Survey
---
paper_title: Interpolation and Approximation of Surfaces from Three-Dimensional Scattered Data Points

paper_content:

There is a wide range of applications for which surface interpolation or approximation from scattered data points in space is important. Dependent on the field of application and the related properties of the data, many algorithms were developed in the past. This contribution gives a survey of existing algorithms, and identifies basic methods common to independently developed solutions. We distinguish surface construction based on spatial subdivision, distance functions, warping, and incremental surface growing. The systematic analysis of existing approaches leads to several interesting open questions for further research.
---
paper_title: Amodal volume completion: 3D visual completion

paper_content:

This work considers the common problem of completing partially visible artifacts within a 3D scene. Human vision abilities to complete such artifacts are well studied within the realms of perceptual psychology. However, the psychological explanations for completion have received only limited application in the domain of 3D computer vision. Here, we examine prior work in this area of computer vision with reference to psychological accounts of completion and identify remaining challenges for future work.
---
paper_title: Stitching and Filling: Creating Conformal Faceted Geometry

paper_content:

Consistent and accurate representation of geometry is required by a number of applications such as mesh generation, rapid prototyping, manufacturing, and computer graphics. Unfortunately, faceted Computer Aided Design (CAD) models received by downstream applications have many issues that pose problems for their successful usability. Automatic or semi-automatic tools are needed to process the geometry to make it suitable for these downstream applications. An algorithm is presented to detect commonly found geometrical and topological issues in the faceted geometry and process them with minimum user interaction. The present algorithm is based on the iterative vertex pair contraction and expansion operations called stitching and filling respectively. The combination of generality, accuracy, and efficiency of this algorithm seems to be a significant improvement over existing techniques. Results are presented showing the effectiveness of the algorithm to process two- and three-dimensional configurations.
---
paper_title: Context-based surface completion

paper_content:

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.
---
paper_title: Filling holes in meshes using a mechanical model to simulate the curvature variation minimization

paper_content:

The presence of holes in a triangle mesh is classically ascribed to the deficiencies of the point cloud acquired from a physical object to be reverse engineered. This lack of information results from both the scanning process and the object complexity. The consequences are simply not acceptable in many application domains (e.g. visualization, finite element analysis or STL prototyping). This paper addresses the way these holes can be filled in while minimizing the curvature variation between the surrounding and inserted meshes. The curvature variation is simulated by the variation between external forces applied to the nodes of a linear mechanical model coupled to the meshes. The functional to be minimized is quadratic and a set of geometric constraints can be added to further shape the inserted mesh. In addition, a complete cleaning toolbox is proposed to remove degenerated and badly oriented triangles resulting from the scanning process.
---
paper_title: Dual domain extrapolation

paper_content:

Shape optimization and surface fairing for polygon meshes have been active research areas for the last few years. Existing approaches either require the border of the surface to be fixed, or are only applicable to closed surfaces. In this paper, we propose a new approach, that computes natural boundaries. This makes it possible not only to smooth an existing geometry, but also to extrapolate its shape beyond the existing border. Our approach is based on a global parameterization of the surface and on a minimization of the squared curvatures, discretized on the edges of the surface. The so-constructed surface is an approximation of a minimal energy surface (MES). Using a global parameterization makes it possible to completely decouple the outer fairness (surface smoothness) from the inner fairness (mesh quality). In addition, the parameter space provides the user with a new means of controlling the shape of the surface. When used as a geometry filter, our approach computes a smoothed mesh that is discrete conformal to the original one. This allows smoothing textured meshes without introducing distortions.
---
paper_title: Filling Gaps in the Boundary of a Polyhedron

paper_content:

Abstract In this paper we present an algorithm for detecting and repairing defects in the boundary of a polyhedron. These defects, usually caused by problems in CAD software, consist of small gaps bounded by edges that are incident to only one polyhedron face. The algorithm uses a partial curve matching technique for matching parts of the defects, and an optimal triangulation of 3-D polygons for resolving the unmatched parts. It is also shown that finding a consistent set of partial curve matches with maximum score, a subproblem which is related to our repairing process, is NP-hard. Experimental results on several polyhedra are presented.
---
paper_title: Progressive Gap Closing for Mesh Repairing

paper_content:

Modern 3D acquisition and modeling tools generate high-quality, detailed geometric models. However, in order to cope with the associated complexity, several mesh decimation methods have been developed in the recent years. On the other hand, a common problem of geometric modeling tools is the generation of consistent three-dimensional meshes. Most of these programs output meshes containing degenerate faces, T-vertices, narrow gaps and cracks. Applying well-established decimation methods to such meshes results in severe artifacts due to lack of consistent connectivity information. The industrial relevance of this problem is emphasized by the fact that as an output of most of the commercial CAD/CAM and other modeling tools, the user usually gets consistent meshes only for separate polygonal patches as opposed to the whole mesh.
---
paper_title: Surface simplification using quadric error metrics

paper_content:

Many applications in computer graphics require complex, highly detailed models. However, the level of detail actually necessary may vary considerably. To control processing time, it is often desirable to use approximations in place of excessively detailed models. We have developed a surface simplification algorithm which can rapidly produce high quality approximations of polygonal models. The algorithm uses iterative contractions of vertex pairs to simplify models and maintains surface error approximations using quadric matrices. By contracting arbitrary vertex pairs (not just edges), our algorithm is able to join unconnected regions of models. This can facilitate much better approximations, both visually and with respect to geometric error. In order to allow topological joining, our system also supports non-manifold surface models. CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—surface and object representations
---
paper_title: Template-Based Mesh Completion

paper_content:

Meshes generated by range scanners and other acquisition tools are often incomplete and typically contain multiple connected components with irregular boundaries and complex holes. This paper introduces a robust algorithm for completion of such meshes using a mapping between the incomplete mesh and a template model. The mapping is computed using a novel framework for bijective parameterization of meshes with gaps and holes. We employ this mapping to correctly glue together the components of the input mesh and to close the holes. The template is used to fill in the topological and geometric information missing in the input. The completed models are guaranteed to have the same topology as the template. Furthermore, if no appropriate template exists or if only topologically correct completion is required a standard canonical shape can be used as a template. As part of our completion method we propose a boundary-mapping technique useful for mesh editing operations such as merging, blending, and detail transfer. We demonstrate that by using this technique we can automatically perform complex editing operations that previously required a large amount of user interaction.
---
paper_title: A multistep approach to restoration of locally undersampled meshes

paper_content:

The paper deals with the problem of remeshing and fairing of undersampled areas (called "holes") in triangular meshes. In this work, we are particularly interested in meshes constructed with geological data but the method can however be applied to any kind of data. With such input data, the point density is often drastically lesser in some regions than in others: this leads to what we call "holes". Once these holes identified, they are filled using a multistep approach. We iteratively: insert vertices in the hole in order to progressively converge towards the density of its neighbourhood, then deform this patch mesh (by minimizing a discrete thin-plate energy) in order to restore the local curvature and guarantee the smoothness of the hole boundary. The main goal of our method is to control both time and space complexity in order to handle huge models while producing quality meshes.
---
paper_title: Filling Gaps in the Boundary of a Polyhedron

paper_content:

Abstract In this paper we present an algorithm for detecting and repairing defects in the boundary of a polyhedron. These defects, usually caused by problems in CAD software, consist of small gaps bounded by edges that are incident to only one polyhedron face. The algorithm uses a partial curve matching technique for matching parts of the defects, and an optimal triangulation of 3-D polygons for resolving the unmatched parts. It is also shown that finding a consistent set of partial curve matches with maximum score, a subproblem which is related to our repairing process, is NP-hard. Experimental results on several polyhedra are presented.
---
paper_title: An Approach to Blend Surfaces

paper_content:

In this paper, we present an application of a space mapping technique for surface reconstruction (more precisely: reconstruction of missing parts of a real geometric object represented by volume data). Using a space mapping technique, the surface of a given model, in particular tooth shape is fitted by a shape transformation to extrapolate the remaining surface of a patient’s tooth with occurring damage such as a “drill hole.” The genetic algorithm minimizes the error of the approximation by optimizing a set of control points that determine the coefficients for spline functions, which in turn define a space transformation. The fitness function to be minimized consists of two components. First one is the error between the blended surface of an object and the surface of the object to be blended in some predefined points. The second is a component that is responsible for the bending energy being minimized.
---
paper_title: Repairing incomplete measured data with a deformable model under constraints of feature shapes

paper_content:

Measured data of a product can be incomplete because of the inaccessibility or invisibility of some portions of the product surface for measure tools in reverse engineering. Usually, the missed surface areas include some key form features of the product, which represent important design components. However, flat surfaces are often used to mend the incomplete form features in current reverse engineering systems. In this paper, an incomplete data repair method is presented using a deformable model under the constraints of given feature forms. The method ensures the accuracy of identifying the missed local areas by choosing a set of proper rules of mesh construction according to the density distribution of measured data, and fills them with an energy-based, deformable local mesh that is adaptively-formed using an iteration of the procedure of mesh subdivision, constraint satisfaction and finite element equation solving.
---
paper_title: Discovering structural regularity in 3D geometry

paper_content:

We introduce a computational framework for discovering regular or repeated geometric structures in 3D shapes. We describe and classify possible regular structures and present an effective algorithm for detecting such repeated geometric patterns in point- or meshbased models. Our method assumes no prior knowledge of the geometry or spatial location of the individual elements that define the pattern. Structure discovery is made possible by a careful analysis of pairwise similarity transformations that reveals prominent lattice structures in a suitable model of transformation space. We introduce an optimization method for detecting such uniform grids specifically designed to deal with outliers and missing elements. This yields a robust algorithm that successfully discovers complex regular structures amidst clutter, noise, and missing geometry. The accuracy of the extracted generating transformations is further improved using a novel simultaneous registration method in the spatial domain. We demonstrate the effectiveness of our algorithm on a variety of examples and show applications to compression, model repair, and geometry synthesis.
---
paper_title: A Hole-Filling Algorithm Using Non-Uniform Rational B-Splines

paper_content:

A three-dimensional (3D) geometric model obtained from a 3D device or other approaches is not necessarily watertight due to the presence of geometric deficiencies. These inadequacies must be repaired to create a valid surface mesh on the model as a pre-process of computational engineering analyses. This procedure has been a tedious and labor-intensive step, as there are many kinds of deficiencies that can make the geometry to be nonwatertight, such as gaps and holes. It is still challenging to repair discrete surface models based on available geometric information. The focus of this paper is to develop a new automated method for patching holes on the surface models in order to achieve watertightness. It describes a numerical algorithm utilizing Non-Uniform Rational B-Splines (NURBS) surfaces to generate smooth triangulated surface patches for topologically simple holes on discrete surface models. The Delaunay criterion for point insertion and edge swapping is used in this algorithm to improve the outcome. Surface patches are generated based on existing points surrounding the holes without altering them. The watertight geometry produced can be used in a wide range of engineering applications in the field of computational engineering simulation studies.
---
paper_title: Inference of segmented color and texture description by tensor voting

paper_content:

A robust synthesis method is proposed to automatically infer missing color and texture information from a damaged 2D image by ND tensor voting (N > 3). The same approach is generalized to range and 3D data in the presence of occlusion, missing data and noise. Our method translates texture information into an adaptive ND tensor, followed by a voting process that infers noniteratively the optimal color values in the ND texture space. A two-step method is proposed. First, we perform segmentation based on insufficient geometry, color, and texture information in the input, and extrapolate partitioning boundaries by either 2D or 3D tensor voting to generate a complete segmentation for the input. Missing colors are synthesized using ND tensor voting in each segment. Different feature scales in the input are automatically adapted by our tensor scale analysis. Results on a variety of difficult inputs demonstrate the effectiveness of our tensor voting approach.
---
paper_title: A statistical method for robust 3D surface reconstruction from sparse data

paper_content:

General information about a class of objects, such as human faces or teeth, can help to solve the otherwise ill-posed problem of reconstructing a complete surface from sparse 3D feature points or 2D projections of points. We present a technique that uses a vector space representation of shape (3D morphable model) to infer missing vertex coordinates. Regularization derived from a statistical approach makes the system stable and robust with respect to noise by computing the optimal tradeoff between fitting quality and plausibility. We present a direct, noniterative algorithm to calculate this optimum efficiently, and a method for simultaneously compensating unknown rigid transformations. The system is applied and evaluated in two different fields: (1) reconstruction of 3D faces at unknown orientations from 2D feature points at interactive rates, and (2) restoration of missing surface regions of teeth for CAD-CAM production of dental inlays and other medical applications.
---
paper_title: A Sharpness-Dependent Filter for Recovering Sharp Features in Repaired 3D Mesh Models

paper_content:

This paper presents a sharpness-based method for hole-filling that can repair a 3D model such that its shape conforms to that of the original model. The method involves two processes: interpolation-based hole-filling, which produces an initial repaired model, and postprocessing, which adjusts the shape of the initial repaired model to conform to that of the original model. In the interpolation-based hole-filling process, a surface interpolation algorithm based on the radial basis function creates a smooth implicit surface that fills the hole. Then, a regularized marching tetrahedral algorithm is used to triangulate the implicit surface. Finally, a stitching and regulating strategy is applied to the surface patch and its neighboring boundary polygon meshes to produce an initial repaired mesh model, which is a regular mesh model suitable for postprocessing. During postprocessing, a sharpness-dependent filtering algorithm is applied to the initial repaired model. This is an iterative procedure whereby each iteration step adjusts the face normal associated with each meshed polygon to recover the sharp features hidden in the repaired model. The experiment results demonstrate that the method is effective in repairing incomplete 3D mesh models.
---
paper_title: Filling holes in meshes

paper_content:

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.
---
paper_title: Context-based surface completion

paper_content:

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.
---
paper_title: Automatic Hole-Filling of Triangular Meshes Using Local Radial Basis Function

paper_content:

Creating models of real objects is a complex task for which the use of traditional modeling techniques has proven to be difficult. To solve some of these problems, laser rangefinders are frequently used to sample an object?s surface from several viewpoints resulting in a set of range images that are registered and integrated into a final triangulated model. In practice, due to surface reflectance properties, occlusions and accessibility limitations, certain areas of the object?s surface are usually not sampled, leaving holes which create undesirable artifacts in the integrated model. In this paper, we present a novel algorithm for the automatic hole?filling of triangulated models. The algorithm starts by locating hole boundary regions. A hole consists of a closed path of edges of boundary triangles that have at least an edge, which is not shared with any other triangle. The edge of the hole is then fitted with a b-spline where the average variation of the torsion of the b-spline approximation is calculated. Using a simple threshold of the average variation of the torsion along the edge, one can automatically classify real holes from man-made holes. Following this classification process, we then use an automated version of a radial basis function interpolator to fill the inside of the hole using neighboring edges. Excellent experimental results are presented.
---
paper_title: Image Guided Geometry Inference

paper_content:

We introduce a new method for filling holes in geometry obtained from 3D range scanners. Our method makes use of 2D images of the areas where geometric data is missing. The 2D images guide the filling using the relationship between the images and geometry learned from the existing 3D scanned data. Our method builds on existing techniques for using scanned geometry and for estimating shape from shaded images. Rather than creating plausibly filled holes, we attempt to approximate the missing geometry. We present results for scanned data from both triangulation and time-of-flight scanners for various types of materials. To quantitatively validate our proposed method, we also compare the filled areas with ground-truth data.
---
paper_title: Filling holes in meshes using a mechanical model to simulate the curvature variation minimization

paper_content:

The presence of holes in a triangle mesh is classically ascribed to the deficiencies of the point cloud acquired from a physical object to be reverse engineered. This lack of information results from both the scanning process and the object complexity. The consequences are simply not acceptable in many application domains (e.g. visualization, finite element analysis or STL prototyping). This paper addresses the way these holes can be filled in while minimizing the curvature variation between the surrounding and inserted meshes. The curvature variation is simulated by the variation between external forces applied to the nodes of a linear mechanical model coupled to the meshes. The functional to be minimized is quadratic and a set of geometric constraints can be added to further shape the inserted mesh. In addition, a complete cleaning toolbox is proposed to remove degenerated and badly oriented triangles resulting from the scanning process.
---
paper_title: Dual domain extrapolation

paper_content:

Shape optimization and surface fairing for polygon meshes have been active research areas for the last few years. Existing approaches either require the border of the surface to be fixed, or are only applicable to closed surfaces. In this paper, we propose a new approach, that computes natural boundaries. This makes it possible not only to smooth an existing geometry, but also to extrapolate its shape beyond the existing border. Our approach is based on a global parameterization of the surface and on a minimization of the squared curvatures, discretized on the edges of the surface. The so-constructed surface is an approximation of a minimal energy surface (MES). Using a global parameterization makes it possible to completely decouple the outer fairness (surface smoothness) from the inner fairness (mesh quality). In addition, the parameter space provides the user with a new means of controlling the shape of the surface. When used as a geometry filter, our approach computes a smoothed mesh that is discrete conformal to the original one. This allows smoothing textured meshes without introducing distortions.
---
paper_title: A finite element method for surface restoration with smooth boundary conditions

paper_content:

In surface restoration usually a damaged region of a surface has to be replaced by a surface patch which restores the region in a suitable way. In particular one aims for C1-continuity at the patch boundary. The Willmore energy is considered to measure fairness and to allow appropriate boundary conditions to ensure continuity of the normal field. The corresponding L2-gradient flow as the actual restoration process leads to a system of fourth order partial differential equations, which can also be written as a system of two coupled second order equations. As it is well known, fourth order problems require an implicit time discretization. Here a semi-implicit approach is presented which allows large time steps. For the discretization of the boundary condition, two different numerical methods are introduced. Finally, we show applications to different surface restoration problems.
---
paper_title: A robust hole-filling algorithm for triangular mesh

paper_content:

This paper presents a novel hole-filling algorithm that can fill arbitrary holes in triangular mesh models. First, the advancing front mesh technique is used to cover the hole with newly created triangles. Next, the desirable normals of the new triangles are approximated using our desirable normal computing schemes. Finally, the three coordinates of every new vertex are re-positioned by solving the Poisson equation based on the desirable normals and the boundary vertices of the hole. Many experimental results and error evaluations are given to show the robustness and efficiency of the algorithm.
---
paper_title: Cutting and Stitching: Converting Sets of Polygons to Manifold Surfaces

paper_content:

Many real-world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, and smoothing. We present an algorithm that removes singularities from nonmanifold sets of polygons to create manifold (optionally oriented) polygonal surfaces. We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching operation, we maintain the surface as a manifold while joining boundary edges. We present two different edge stitching strategies, called pinching and snapping. Our algorithm manipulates the surface topology and ignores physical coordinates. Except for the optional stitching, the algorithm has a linear complexity and requires no floating point operations. In addition to introducing new algorithms, we expose the complexity (and pitfalls) associated with stitching. Finally, several real-world examples are studied.
---
paper_title: Making radiosity usable: automatic preprocessing and meshing techniques for the generation of accurate radiosity solutions

paper_content:

Generating accurate radiosity solutions of real world environments is user-intensive and requires significant knowledge of the method. As a result, few end-users such as architects and designers use it. The output of most commercial modeling packages must be substantially "cleaned up" to satisfy the geometrical and topological criteria imposed by radiosity solution algorithms. Furthermore, the mesh used as the basis of the radiosity computation must meet several additional requirements for the solution to be accurate.A set of geometrical and topological requirements is formalized that when satisfied yields an accurate radiosity solution. A series of algorithms is introduced that automatically processes raw model databases to meet these requirements. Thus, the end-user can concentrate on the design rather than on the details of the radiosity solution process. These algorithms are generally independent of the radiosity solution technique used, and thus apply to all mesh based radiosity methods.
---
paper_title: RSVP: A Geometric Toolkit for Controlled Repair of Solid Models

paper_content:

The paper presents a system and the associated algorithms for repairing the boundary representation of CAD models. Two types of errors are considered: topological errors, i.e., aggregate errors, like zero volume parts, duplicate or missing parts, inconsistent surface orientation, etc., and geometric errors, i.e., numerical imprecision errors, like cracks or overlaps of geometry. The output of our system describes a set of clean and consistent two-manifolds (possibly with boundaries) with derived adjacencies. Such solid representation enables the application of a variety of rendering and analysis algorithms, e.g., finite element analysis, radiosity computation, model simplification, and solid free form fabrication. The algorithms described were originally designed to correct errors in polygonal B-Reps. We also present an extension for spline surfaces. Central to our system is a procedure for inferring local adjacencies of edges. The geometric representation of topologically adjacent edges are merged to evolve a set of two-manifolds. Aggregate errors are discovered during the merging step. Unfortunately, there are many ambiguous situations where errors admit more than one valid solution. Our system proposes an object repairing process based on a set of user tunable heuristics. The system also allows the user to override the algorithm's decisions in a repair visualization step. In essence, this visualization step presents an organized and intuitive way for the user to explore the space of valid solutions and to select the correct one.
---
paper_title: Removing zero-volume parts from CAD models for layered manufacturing

paper_content:

CAD models for automated manufacturing should describe solids as mathematically regularized sets. The technique presented clears STL files of zero-volume parts that violate the definition of a regularized set. >
---
paper_title: The Marching Intersections algorithm for merging range images

paper_content:

A new algorithm for the integration of partially overlapping range images into a triangular mesh is presented. The algorithm consists of three main steps: it locates the intersections between the range surfaces and a reference grid chosen by the user, then merges all nearly coincident and redundant intersections according to a proximity criterion, and, finally, reconstructs the merged surface(s) from the filtered intersection set. Compared with previous methods, which adopt a volumetric approach, our algorithm shows lower computational costs and improves the accuracy of the surfaces produced. It takes into account the quality of the input measurements and is able to patch small holes corresponding to the parts of the 3D scanned object that were not observed by the acquisition device. The algorithm has been tested on several datasets of range maps; graphical and numeric results are reported.
---
paper_title: Zippered polygon meshes from range images

paper_content:

Range imaging offers an inexpensive and accurate means for digitizing the shape of three-dimensional objects. Because most objects self occlude, no single range image suffices to describe the entire object. We present a method for combining a collection of range images into a single polygonal mesh that completely describes an object to the extent that it is visible from the outside. The steps in our method are: 1) align the meshes with each other using a modified iterated closest-point algorithm, 2) zipper together adjacent meshes to form a continuous surface that correctly captures the topology of the object, and 3) compute local weighted averages of surface positions on all meshes to form a consensus surface geometry. Our system differs from previous approaches in that it is incremental; scans are acquired and combined one at a time. This approach allows us to acquire and combine large numbers of scans with minimal storage overhead. Our largest models contain up to 360,000 triangles. All the steps needed to digitize an object that requires up to 10 range scans can be performed using our system with five minutes of user interaction and a few hours of compute time. We show two models created using our method with range data from a commercial rangefinder that employs laser stripe technology.
---
paper_title: Dual contouring of hermite data

paper_content:

This paper describes a new method for contouring a signed grid whose edges are tagged by Hermite data (i.e; exact intersection points and normals). This method avoids the need to explicitly identify and process "features" as required in previous Hermite contouring methods. Using a new, numerically stable representation for quadratic error functions, we develop an octree-based method for simplifying contours produced by this method. We next extend our contouring method to these simpli£ed octrees. This new method imposes no constraints on the octree (such as being a restricted octree) and requires no "crack patching". We conclude with a simple test for preserving the topology of the contour during simplification.
---
paper_title: Efficient representation and extraction of 2-manifold isosurfaces using kd-trees

paper_content:

In this paper, we propose the utilization of a kd-tree based hierarchy as an implicit object representation. Compared to an octree, the kd-tree based hierarchy is superior in terms of adaptation to the object surface. In consequence, we obtain considerably more compact implicit representations especially in case of thin object structures. We describe a new isosurface extraction algorithm for this kind of implicit representation. In contrast to related algorithms for octrees, it generates 2-manifold meshes even for kd-trees with cells containing multiple surface components. The algorithm retains all the good properties of the dual contouring approach [10] like feature preservation, computational efficiency, etc. In addition, we present a simplification framework for the surfaces represented by the kd-tree based on quadric error metrics. We adapt this framework to quantify the influence of topological changes, thereby allowing controlled topological simplification of the object. The advantages of the new algorithm are demonstrated by several examples.
---
paper_title: 3D distance fields: a survey of techniques and applications

paper_content:

A distance field is a representation where, at each point within the field, we know the distance from that point to the closest point on any object within the domain. In addition to distance, other properties may be derived from the distance field, such as the direction to the surface, and when the distance field is signed, we may also determine if the point is internal or external to objects within the domain. The distance field has been found to be a useful construction within the areas of computer vision, physics, and computer graphics. This paper serves as an exposition of methods for the production of distance fields, and a review of alternative representations and applications of distance fields. In the course of this paper, we present various methods from all three of the above areas, and we answer pertinent questions such as How accurate are these methods compared to each other? How simple are they to implement?, and What is the complexity and runtime of such methods?.
---
paper_title: Using distance maps for accurate surface representation in sampled volumes

paper_content:

High quality rendering and physics based modeling in volume graphics have been limited because intensity based volumetric data do not represent surfaces well. High spatial frequencies due to abrupt intensity changes at object surfaces result in jagged or terraced surfaces in rendered images. The use of a distance-to-closest-surface function to encode object surfaces is proposed. This function varies smoothly across surfaces and hence can be accurately reconstructed from sampled data. The zero value iso surface of the distance map yields the object surface and the derivative of the distance map yields the surface normal. Examples of rendered images are presented along with a new method for calculating distance maps from sampled binary data.
---
paper_title: Topology-reducing surface simplification using a discrete solid representation

paper_content:

This paper presents a new approach for generating coarse-level approximations of topologically complex models. Dramatic topology reduction is achieved by converting a 3D model to and from a volumetric representation. Our approach produces valid, error-bounded models and supports the creation of approximations that do not interpenetrate the original model, either being completely contained in the input solid or bounding it. Several simple to implement versions of our approach are presented and discussed. We show that these methods perform significantly better than other surface-based approaches when simplifying topologically-rich models such as scene parts and complex mechanical assemblies.
---
paper_title: Filling holes in complex surfaces using volumetric diffusion

paper_content:

We address the problem of building watertight 3D models from surfaces that contain holes - for example, sets of range scans that observe most but not all of a surface. We specifically address situations in which the holes are too geometrically and topologically complex to fill using triangulation algorithms. Our solution begins by constructing a signed distance function, the zero set of which defines the surface. Initially, this function is defined only in the vicinity of observed surfaces. We then apply a diffusion process to extend this function through the volume until its zero set bridges whatever holes may be present. If additional information is available, such as known-empty regions of space inferred from the lines of sight to a 3D scanner, it can be incorporated into the diffusion process. Our algorithm is simple to implement, is guaranteed to produce manifold non-interpenetrating surfaces, and is efficient to run on large datasets because computation is limited to areas near holes.
---
paper_title: Filling the signed distance field by fitting local quadrics

paper_content:

We propose a method of filling unmeasured regions of shape models integrated from multiple measurements of surface shapes. We use the signed distance field (SDF) as shape representation that contains information of the surface normal along with the signed distance at the closest point on the surface from the sampling point. We solve this problem by iteratively fitting quadratic function to generate smoothly connected SDF. We analyzed the relationship between the quadratic coefficients and the surface curvature, and by using the coefficients, we evenly propagated the SDF so that it satisfies the constraints of the field. The proposed method was tested on synthetic data and real data that was generated by integrating multiple range images.
---
paper_title: Robust repair of polygonal models

paper_content:

We present a robust method for repairing arbitrary polygon models. The method is guaranteed to produce a closed surface that partitions the space into disjoint internal and external volumes. Given any model represented as a polygon soup, we construct an inside/outside volume using an octree grid, and reconstruct the surface by contouring. Our novel algorithm can efficiently process large models containing millions of polygons and is capable of reproducing sharp features in the original geometry.
---
paper_title: Automatic restoration of polygon models

paper_content:

We present a fully automatic technique which converts an inconsistent input mesh into an output mesh that is guaranteed to be a clean and consistent mesh representing the closed manifold surface of a solid object. The algorithm removes all typical mesh artifacts such as degenerate triangles, incompatible face orientation, non-manifold vertices and edges, overlapping and penetrating polygons, internal redundant geometry, as well as gaps and holes up to a user-defined maximum size ρ. Moreover, the output mesh always stays within a prescribed tolerance e to the input mesh. Due to the effective use of a hierarchical octree data structure, the algorithm achieves high voxel resolution (up to 40963 on a 2GB PC) and processing times of just a few minutes for moderately complex objects. We demonstrate our technique on various architectural CAD models to show its robustness and reliability.
---
paper_title: Robust Reconstruction of Watertight 3D Models from Non-uniformly Sampled Point Clouds Without Normal Information

paper_content:

We present a new volumetric method for reconstructing watertight triangle meshes from arbitrary, unoriented point clouds. While previous techniques usually reconstruct surfaces as the zero level-set of a signed distance function, our method uses an unsigned distance function and hence does not require any information about the local surface orientation. Our algorithm estimates local surface confidence values within a dilated crust around the input samples. The surface which maximizes the global confidence is then extracted by computing the minimum cut of a weighted spatial graph structure. We present an algorithm, which efficiently converts this cut into a closed, manifold triangle mesh with a minimal number of vertices. The use of an unsigned distance function avoids the topological noise artifacts caused by misalignment of 3D scans, which are common to most volumetric reconstruction techniques. Due to a hierarchical approach our method efficiently produces solid models of low genus even for noisy and highly irregular data containing large holes, without loosing fine details in densely sampled regions. We show several examples for different application settings such as model generation from raw laser-scanned data, image-based 3D reconstruction, and mesh repair.
---
paper_title: Robust tetrahedral meshing of triangle soups

paper_content:

We propose a novel approach to generate coarse tetrahedral meshes which can be used in interactive simulation frameworks. The proposed algorithm processes unconstrained, i. e. unorientable and non-manifold triangle soups. Since the volume bounded by an unconstrained surface is not defined, we tetrahedralize the pseudo volume of the surface, namely the space that is intuitively occupied by the surface. Using our approach, we can generate coarse tetrahedral meshes from damaged surfaces and even triangle soups without any connectivity. Various examples underline the robustness of our approach. The usability of the resulting meshes is illustrated in the context of interactive deformable modeling.
---
paper_title: Simplification and Repair of Polygonal Models Using Volumetric Techniques

paper_content:

Two important tools for manipulating polygonal models are simplification and repair and we present voxel-based methods for performing both of these tasks. We describe a method for converting polygonal models to a volumetric representation in a way that handles models with holes, double walls, and intersecting parts. This allows us to perform polygon model repair simply by converting a model to and from the volumetric domain. We also describe a new topology-altering simplification method that is based on 3D morphological operators. Visually unimportant features such as tubes and holes may be eliminated from a model by the open and close morphological operators. Our simplification approach accepts polygonal models as input, scan converts these to create a volumetric description, performs topology modification, and then converts the results back to polygons. We then apply a topology-preserving polygon simplification technique to produce a final model. Our simplification method produces results that are everywhere manifold.
---
paper_title: Robust repair of polygonal models

paper_content:

We present a robust method for repairing arbitrary polygon models. The method is guaranteed to produce a closed surface that partitions the space into disjoint internal and external volumes. Given any model represented as a polygon soup, we construct an inside/outside volume using an octree grid, and reconstruct the surface by contouring. Our novel algorithm can efficiently process large models containing millions of polygons and is capable of reproducing sharp features in the original geometry.
---
paper_title: Improved space carving method for merging and interpolating multiple range images using information of light sources of active stereo

paper_content:

To merge multiple range data obtained by range scanners, filling holes caused by unmeasured regions, the space carving method is a simple and effective method. However, this method often fails if the number of the input range images is small, because unseen voxels that are not carved out remains in the volume area. In this paper, we propose an improved algorithm of the space carving method that produces stable results. In the proposed method, a discriminant function defined on volume space is used to estimate whether each voxel is inside or outside the objects. Also, in particular case that the range images are obtained by active stereo method, the information of the positions of the light sources can be used to improve the accuracy of the results.
---
paper_title: Taking consensus of signed distance field for complementing unobservable surface

paper_content:

When we use range finders to observe the shape of an object, many occluded areas may occur. These become holes and gaps in the model and make it undesirable to utilize the model for various applications. We propose a novel method to fill holes and gaps and complement such an incomplete model. We use a signed distance field (SDF) as an intermediate representation, which stores Euclidean signed distances from a voxel to the nearest point of the mesh model. Since the signs of a SDF become unstable around holes or gaps, we take a consensus of the signed distances of neighbor voxels by estimating the consistency of the SDF. Once we make the SDF consistent, we can efficiently fill holes and gaps.
---
paper_title: Filling holes in complex surfaces using volumetric diffusion

paper_content:

We address the problem of building watertight 3D models from surfaces that contain holes - for example, sets of range scans that observe most but not all of a surface. We specifically address situations in which the holes are too geometrically and topologically complex to fill using triangulation algorithms. Our solution begins by constructing a signed distance function, the zero set of which defines the surface. Initially, this function is defined only in the vicinity of observed surfaces. We then apply a diffusion process to extend this function through the volume until its zero set bridges whatever holes may be present. If additional information is available, such as known-empty regions of space inferred from the lines of sight to a 3D scanner, it can be incorporated into the diffusion process. Our algorithm is simple to implement, is guaranteed to produce manifold non-interpenetrating surfaces, and is efficient to run on large datasets because computation is limited to areas near holes.
---
paper_title: Hole Filling of a 3D Model by Flipping Signs of a Signed Distance Field in Adaptive Resolution

paper_content:

When we use range finders to observe the shape of an object, many occluded areas may occur. These become holes and gaps in the model and make it undesirable for various applications. We propose a novel method to fill holes and gaps to complete this incomplete model. As an intermediate representation, we use a signed distance field (SDF), which stores euclidean signed distances from a voxel to the nearest point of the mesh model. By using an SDF, we can obtain interpolating surfaces for holes and gaps. The proposed method generates an interpolating surface that becomes smoothly continuous with real surfaces by minimizing the area of the interpolating surface. Since the isosurface of an SDF can be identified as being a real or interpolating surface from the magnitude of signed distances, our method computes the area of an interpolating surface in the neighborhood of a voxel both before and after flipping the sign of the signed distance of the voxel. If the area is reduced by flipping the sign, then our method changes the sign for the voxel. Therefore, we minimize the area of the interpolating surface by iterating this computation until convergence. Unlike methods based on partial differential equations (PDEs), our method does not require any boundary condition and the initial state that we use is automatically obtained by computing the distance to the closest point of the real surface. Moreover, because our method can be applied to an SDF of adaptive resolution, our method efficiently interpolates large holes and gaps of high curvature. We tested the proposed method with both synthesized and real objects and evaluated the interpolating surfaces.
---
paper_title: A volumetric method for building complex models from range images

paper_content:

A number of techniques have been developed for reconstructing surfaces by integrating groups of aligned range images. A desirable set of properties for such algorithms includes: incremental updating, representation of directional uncertainty, the ability to fill gaps in the reconstruction, and robustness in the presence of outliers. Prior algorithms possess subsets of these properties. In this paper, we present a volumetric method for integrating range images that possesses all of these properties. Our volumetric representation consists of a cumulative weighted signed distance function. Working with one range image at a time, we first scan-convert it to a distance function, then combine this with the data already acquired using a simple additive scheme. To achieve space efficiency, we employ a run-length encoding of the volume. To achieve time efficiency, we resample the range image to align with the voxel grid and traverse the range and voxel scanlines synchronously. We generate the final manifold by extracting an isosurface from the volumetric grid. We show that under certain assumptions, this isosurface is optimal in the least squares sense. To fill gaps in the model, we tessellate over the boundaries between regions seen to be empty and regions never observed. Using this method, we are able to integrate a large number of range images (as many as 70) yielding seamless, high-detail models of up to 2.6 million triangles.
---
paper_title: Poisson Surface Reconstruction

paper_content:

We show that surface reconstruction from oriented points can be cast as a spatial Poisson problem. This Poisson formulation considers all the points at once, without resorting to heuristic spatial partitioning or blending, and is therefore highly resilient to data noise. Unlike radial basis function schemes, our Poisson approach allows a hierarchy of locally supported basis functions, and therefore the solution reduces to a well conditioned sparse linear system. We describe a spatially adaptive multiscale algorithm whose time and space complexities are proportional to the size of the reconstructed model. Experimenting with publicly available scan data, we demonstrate reconstruction of surfaces with greater detail than previously achievable.
---
paper_title: Interpolating and approximating implicit surfaces from polygon soup

paper_content:

This paper describes a method for building interpolating or approximating implicit surfaces from polygonal data. The user can choose to generate a surface that exactly interpolates the polygons, or a surface that approximates the input by smoothing away features smaller than some user-specified size. The implicit functions are represented using a moving least-squares formulation with constraints integrated over the polygons. The paper also presents an improved method for enforcing normal constraints and an iterative procedure for ensuring that the implicit surface tightly encloses the input vertices.
---
paper_title: Reconstruction and representation of 3D objects with radial basis functions

paper_content:

We use polyharmonic Radial Basis Functions (RBFs) to reconstruct smooth, manifold surfaces from point-cloud data and to repair incomplete meshes. An object's surface is defined implicitly as the zero set of an RBF fitted to the given surface data. Fast methods for fitting and evaluating RBFs allow us to model large data sets, consisting of millions of surface points, by a single RBF — previously an impossible task. A greedy algorithm in the fitting process reduces the number of RBF centers required to represent a surface and results in significant compression and further computational advantages. The energy-minimisation characterisation of polyharmonic splines result in a “smoothest” interpolant. This scale-independent characterisation is well-suited to reconstructing surfaces from non-uniformly sampled data. Holes are smoothly filled and surfaces smoothly extrapolated. We use a non-interpolating approximation when the data is noisy. The functional representation is in effect a solid model, which means that gradients and surface normals can be determined analytically. This helps generate uniform meshes and we show that the RBF representation has advantages for mesh simplification and remeshing applications. Results are presented for real-world rangefinder data.
---
paper_title: Robust tetrahedral meshing of triangle soups

paper_content:

We propose a novel approach to generate coarse tetrahedral meshes which can be used in interactive simulation frameworks. The proposed algorithm processes unconstrained, i. e. unorientable and non-manifold triangle soups. Since the volume bounded by an unconstrained surface is not defined, we tetrahedralize the pseudo volume of the surface, namely the space that is intuitively occupied by the surface. Using our approach, we can generate coarse tetrahedral meshes from damaged surfaces and even triangle soups without any connectivity. Various examples underline the robustness of our approach. The usability of the resulting meshes is illustrated in the context of interactive deformable modeling.
---
paper_title: Filling the signed distance field by fitting local quadrics

paper_content:

We propose a method of filling unmeasured regions of shape models integrated from multiple measurements of surface shapes. We use the signed distance field (SDF) as shape representation that contains information of the surface normal along with the signed distance at the closest point on the surface from the sampling point. We solve this problem by iteratively fitting quadratic function to generate smoothly connected SDF. We analyzed the relationship between the quadratic coefficients and the surface curvature, and by using the coefficients, we evenly propagated the SDF so that it satisfies the constraints of the field. The proposed method was tested on synthetic data and real data that was generated by integrating multiple range images.
---
paper_title: Filling Holes in Complex Surfaces using Oriented Voxel Diffusion

paper_content:

Range scanning devices often yield imperfect surface sampling for real-world models with complex features. These holes in the surface are commonly filled with smooth patches conforming to the boundaries. We introduce an oriented voxel diffusion method to fill holes in complex surfaces. First, an initial field of oriented distance is measured according to the existing surface. The implicit surface of the oriented distance field coincides with the existing surface. Second, the oriented distance field diffuses inward the hole until the implicit surface converges. Particularly, the orientation information in the distance field is used to control the diffusion direction accurately. Therefore this method is able to restore the sharp features.
---
paper_title: Simplification and Repair of Polygonal Models Using Volumetric Techniques

paper_content:

Two important tools for manipulating polygonal models are simplification and repair and we present voxel-based methods for performing both of these tasks. We describe a method for converting polygonal models to a volumetric representation in a way that handles models with holes, double walls, and intersecting parts. This allows us to perform polygon model repair simply by converting a model to and from the volumetric domain. We also describe a new topology-altering simplification method that is based on 3D morphological operators. Visually unimportant features such as tubes and holes may be eliminated from a model by the open and close morphological operators. Our simplification approach accepts polygonal models as input, scan converts these to create a volumetric description, performs topology modification, and then converts the results back to polygons. We then apply a topology-preserving polygon simplification technique to produce a final model. Our simplification method produces results that are everywhere manifold.
---
paper_title: Inpainting surface holes

paper_content:

An algorithm for filling-in surface holes is introduced in this paper. The basic idea is to represent the surface of interest in implicit form, and fill-in the holes with a system of geometric partial differential equations derived from image inpainting algorithms. The framework and examples with synthetic and real data are presented.
---
paper_title: Automatic restoration of polygon models

paper_content:

We present a fully automatic technique which converts an inconsistent input mesh into an output mesh that is guaranteed to be a clean and consistent mesh representing the closed manifold surface of a solid object. The algorithm removes all typical mesh artifacts such as degenerate triangles, incompatible face orientation, non-manifold vertices and edges, overlapping and penetrating polygons, internal redundant geometry, as well as gaps and holes up to a user-defined maximum size ρ. Moreover, the output mesh always stays within a prescribed tolerance e to the input mesh. Due to the effective use of a hierarchical octree data structure, the algorithm achieves high voxel resolution (up to 40963 on a 2GB PC) and processing times of just a few minutes for moderately complex objects. We demonstrate our technique on various architectural CAD models to show its robustness and reliability.
---
paper_title: Dual contouring of hermite data

paper_content:

This paper describes a new method for contouring a signed grid whose edges are tagged by Hermite data (i.e; exact intersection points and normals). This method avoids the need to explicitly identify and process "features" as required in previous Hermite contouring methods. Using a new, numerically stable representation for quadratic error functions, we develop an octree-based method for simplifying contours produced by this method. We next extend our contouring method to these simpli£ed octrees. This new method imposes no constraints on the octree (such as being a restricted octree) and requires no "crack patching". We conclude with a simple test for preserving the topology of the contour during simplification.
---
paper_title: Efficient representation and extraction of 2-manifold isosurfaces using kd-trees

paper_content:

In this paper, we propose the utilization of a kd-tree based hierarchy as an implicit object representation. Compared to an octree, the kd-tree based hierarchy is superior in terms of adaptation to the object surface. In consequence, we obtain considerably more compact implicit representations especially in case of thin object structures. We describe a new isosurface extraction algorithm for this kind of implicit representation. In contrast to related algorithms for octrees, it generates 2-manifold meshes even for kd-trees with cells containing multiple surface components. The algorithm retains all the good properties of the dual contouring approach [10] like feature preservation, computational efficiency, etc. In addition, we present a simplification framework for the surfaces represented by the kd-tree based on quadric error metrics. We adapt this framework to quantify the influence of topological changes, thereby allowing controlled topological simplification of the object. The advantages of the new algorithm are demonstrated by several examples.
---
paper_title: Feature sensitive surface extraction from volume data

paper_content:

The representation of geometric objects based on volumetric data structures has advantages in many geometry processing applications that require, e.g., fast surface interrogation or boolean operations such as intersection and union. However, surface based algorithms like shape optimization (fairing) or freeform modeling often need a topological manifold representation where neighborhood information within the surface is explicitly available. Consequently, it is necessary to find effective conversion algorithms to generate explicit surface descriptions for the geometry which is implicitly defined by a volumetric data set. Since volume data is usually sampled on a regular grid with a given step width, we often observe severe alias artifacts at sharp features on the extracted surfaces. In this paper we present a new technique for surface extraction that performs feature sensitive sampling and thus reduces these alias effects while keeping the simple algorithmic structure of the standard Marching Cubes algorithm. We demonstrate the effectiveness of the new technique with a number of application examples ranging from CSG modeling and simulation to surface reconstruction and remeshing of polygonal models.
---
paper_title: Solid representation and operation using extended octrees

paper_content:

Solid modelers must be based on reliable and fast algorithms for Boolean operations. The octree model, as well as several generalizations (polytrees, integrated polytrees, extended octrees), is specially well suited for these algorithms and can be used either as a primary or as a secondary model in solid modeling systems. This paper is concerned with a precise definition of the extended octree model that allows the representation of nonmanifold objects with planar faces and, consequently, is closed under Boolean operations on polyhedrons. Boolean nodes and nearly vertex nodes are introduced, and the model is discussed in comparison with related representations. A fast algorithm for the direct generation of the extended octree from the geometry of the base polygon in extrusion solids is presented, and its complexity is studied. Boolean operation algorithms are introduced.
---
paper_title: Robust repair of polygonal models

paper_content:

We present a robust method for repairing arbitrary polygon models. The method is guaranteed to produce a closed surface that partitions the space into disjoint internal and external volumes. Given any model represented as a polygon soup, we construct an inside/outside volume using an octree grid, and reconstruct the surface by contouring. Our novel algorithm can efficiently process large models containing millions of polygons and is capable of reproducing sharp features in the original geometry.
---
paper_title: Editing the topology of 3D models by sketching

paper_content:

We present a method for modifying the topology of a 3D model with user control. The heart of our method is a guided topology editing algorithm. Given a source model and a user-provided target shape, the algorithm modifies the source so that the resulting model is topologically consistent with the target. Our algorithm permits removing or adding various topological features (e.g., handles, cavities and islands) in a common framework and ensures that each topological change is made by minimal modification to the source model. To create the target shape, we have also designed a convenient 2D sketching interface for drawing 3D line skeletons. As demonstrated in a suite of examples, the use of sketching allows more accurate removal of topological artifacts than previous methods, and enables creative designs with specific topological goals.
---
paper_title: Consistent solid and boundary representations from arbitrary polygonal data

paper_content:

Consistent repreaentations of the boundary and interior of thredimensional solid objects are required by applications ramging from interactive visualization to finite element analysis. However, most commonly available models of solid objects contain errors and inconsistencies. We describe an algorithm that automatically constructs consistent representations of the solid objects modeled by an arbitrary set of polygons. The key feature of our algorithm is that it first partitions space into a set of polyhedral regions and then determines which regions are solid based on region adjacency relationships. Fromthe solid polyhedral regions, we are able to output umsistent boundary and solid representations in a variety of iile formats. Unlike previous approaches, our solid-based approach is effective even when the input polygons intersect, overlap, are wrongly-oriented, have T-junctions, or are unconnected.
---
paper_title: Efficient representation and extraction of 2-manifold isosurfaces using kd-trees

paper_content:

In this paper, we propose the utilization of a kd-tree based hierarchy as an implicit object representation. Compared to an octree, the kd-tree based hierarchy is superior in terms of adaptation to the object surface. In consequence, we obtain considerably more compact implicit representations especially in case of thin object structures. We describe a new isosurface extraction algorithm for this kind of implicit representation. In contrast to related algorithms for octrees, it generates 2-manifold meshes even for kd-trees with cells containing multiple surface components. The algorithm retains all the good properties of the dual contouring approach [10] like feature preservation, computational efficiency, etc. In addition, we present a simplification framework for the surfaces represented by the kd-tree based on quadric error metrics. We adapt this framework to quantify the influence of topological changes, thereby allowing controlled topological simplification of the object. The advantages of the new algorithm are demonstrated by several examples.
---
paper_title: Solid representation and operation using extended octrees

paper_content:

Solid modelers must be based on reliable and fast algorithms for Boolean operations. The octree model, as well as several generalizations (polytrees, integrated polytrees, extended octrees), is specially well suited for these algorithms and can be used either as a primary or as a secondary model in solid modeling systems. This paper is concerned with a precise definition of the extended octree model that allows the representation of nonmanifold objects with planar faces and, consequently, is closed under Boolean operations on polyhedrons. Boolean nodes and nearly vertex nodes are introduced, and the model is discussed in comparison with related representations. A fast algorithm for the direct generation of the extended octree from the geometry of the base polygon in extrusion solids is presented, and its complexity is studied. Boolean operation algorithms are introduced.
---
paper_title: Interactive topology-aware surface reconstruction

paper_content:

The reconstruction of a complete watertight model from scan data is still a difficult process. In particular, since scanned data is often incomplete, the reconstruction of the expected shape is an ill-posed problem. Techniques that reconstruct poorly-sampled areas without any user intervention fail in many cases to faithfully reconstruct the topology of the model. The method that we introduce in this paper is topology-aware: it uses minimal user input to make correct decisions at regions where the topology of the model cannot be automatically induced with a reasonable degree of confidence. We first construct a continuous function over a three-dimensional domain. This function is constructed by minimizing a penalty function combining the data points, user constraints, and a regularization term. The optimization problem is formulated in a mesh-independent manner, and mapped onto a specific mesh using the finite-element method. The zero level-set of this function is a first approximation of the reconstructed surface. At complex under-sampled regions, the constraints might be insufficient. Hence, we analyze the local topological stability of the zero level-set to detect weak regions of the surface. These regions are suggested to the user for adding local inside/outside constraints by merely scribbling over a 2D tablet. Each new user constraint modifies the minimization problem, which is solved incrementally. The process is repeated, converging to a topology-stable reconstruction. Reconstructions of models acquired by a structured-light scanner with a small number of scribbles demonstrate the effectiveness of the method.
---
paper_title: Context-based surface completion

paper_content:

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.
---
paper_title: Removing excess topology from isosurfaces

paper_content:

Many high-resolution surfaces are created through isosurface extraction from volumetric representations, obtained by 3D photography, CT, or MRI. Noise inherent in the acquisition process can lead to geometrical and topological errors. Reducing geometrical errors during reconstruction is well studied. However, isosurfaces often contain many topological errors in the form of tiny handles. These nearly invisible artifacts hinder subsequent operations like mesh simplification, remeshing, and parametrization. In this article we present a practical method for removing handles in an isosurface. Our algorithm makes an axis-aligned sweep through the volume to locate handles, compute their sizes, and selectively remove them. The algorithm is designed to facilitate out-of-core execution. It finds the handles by incrementally constructing and analyzing a Reeb graph. The size of a handle is measured by a short nonseparating cycle. Handles are removed robustly by modifying the volume rather than attempting "mesh surgery." Finally, the volumetric modifications are spatially localized to preserve geometrical detail. We demonstrate topology simplification on several complex models, and show its benefits for subsequent surface processing.
---
paper_title: Robust repair of polygonal models

paper_content:

We present a robust method for repairing arbitrary polygon models. The method is guaranteed to produce a closed surface that partitions the space into disjoint internal and external volumes. Given any model represented as a polygon soup, we construct an inside/outside volume using an octree grid, and reconstruct the surface by contouring. Our novel algorithm can efficiently process large models containing millions of polygons and is capable of reproducing sharp features in the original geometry.
---

Title: Fixing Geometric Errors on Polygonal Models: A Survey

Section 1: Introduction
Description 1: Introduce the prevalence of polygonal models in various domains, their creation methods, and the importance of geometric and topological correctness.

Section 2: Geometric Errors
Description 2: Describe the types of geometric errors found in polygonal models, such as gaps, holes, non-manifold elements, and self-intersections.

Section 3: Overview
Description 3: Provide an overview of the paper, introducing the categorization of methods into mesh-based and volume-based approaches, and referencing related literature.

Section 4: Mesh-Based Approaches
Description 4: Discuss methods that directly identify and fix errors on polygonal surfaces by performing modifications such as adding or removing vertices and altering polygon connectivity.

Section 5: Gaps and Holes
Description 5: Explain the techniques for filling gaps and holes, including boundary detection, stitching, triangulation, and example-based methods.

Section 6: Non-Manifold Edges
Description 6: Describe approaches for handling non-manifold edges that often represent redundant geometry or internal membranes.

Section 7: Geometric Intersections
Description 7: Outline the challenges and strategies in detecting and resolving geometric intersections.

Section 8: Volume-Based Approaches
Description 8: Detail methods that convert the model into a volumetric grid to determine inside and outside regions and then reconstruct a polygonal boundary.

Section 9: Comparison and Discussion
Description 9: Summarize and compare mesh-based and volume-based methods, and discuss potential research directions for improving model repair techniques.