Eurographics Symposium on Geometry Processing (2006)Konrad Polthier, Alla Sheffer (Editors)Hierarchical Error-Driven Approximationof Implicit Surface s from Polygonal MeshesTakashi Kanai1Yutaka Ohtake2Kiwamu Kase21The University of Tokyo, Graduate School of Arts and Sciences, Japan2RIKEN, VCAD Modeling Team, JapanAbstractThis paper describes an efficient method for the hierarchical approximation of implicit surfaces from polygonalmeshes. A novel error function between a polygonal mesh and an implicit surface is proposed. This error functionis defined so as to be scale-independent from it s global behavior as well as to be area-sensitive on local regions.An implicit surface tightly-fitted to polygons can be computed by the least-squares fitting method. Furthermore,this function can be represented as the quadric form, which realizes a compact representation of such an errormetric. Our novel algorithm rapidly constructs a SLIM (Sparse Low-degree IMplicit) surface which is a recentlydeveloped non-conforming hierarchical implicit surface representation. Users can quickly obtain a set of implicitsurfaces with arbitrary resolution according to errors from a SLIM surface.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer G r aphics]: Curve, Surface, Soli d andObject Representations, G .1.2 [N umerical Analysis]: Approximation of Surfaces and Contours1. IntroductionPolygonal mesh is nowadays recognized as a de f actostandard geometric representation in the area of ComputerGraphics (CG). A large variety of applications to generateor edit polygonal meshes have been developed. However,these polygonal meshes often contain defects such as gaps,T-junctions, self-intersections, and non-manifold structure.These problems must be handled with care for many pur-poses. Geometrically unfavorable conditions such as bad as-pect ratios also render them unsuitable for other purposessuch as numerical simulations.On the other hand, an implicit surface is a well-knownsurface representation. Geometric details of an object can berepresented using less surface primitives than meshes. Sincethe combination of multiple implicit surfaces can define asolid model stri ctly, issues for meshes described above donot occur. Implicit surfaces are convenient even for geometryprocessing because we do not need to take into considerationthe connectivity of neighbor surfaces.This paper provides a tool for rapidly converting polygo-nal meshes into implicit surfaces. We specifically deal withSLIM (Sparse Low-degree IMplicit) surfaces [OBA05 ]. Ouralgorithm can approximate a SLIM surface which has thehierarchical structure of implicit surfaces. Each node of aSLIM surface contains an error between parts of a polygo-nal mesh and an implicit surface which is calculated in ouralgorithm. It is t hen possible to quickly extract different res-olutions of SLIM nodes according to the error specified bythe user.The technical contributions of our approach include:Surface Fi tting using Polygon-Implicit Error Metrics.We propose a novel error function of an implicit surfacefor polygons. It combines the algebraic distance and thenormal err or distance and is a natural extension of errorfunctions for points. The function is also represented asa quadric form. This provides several advantages, forexample, a compact storage and efficient approximation.Coefficients of an implicit function can be calculatedby the l east-squares fitting method. This requires onlysolving a small linear system.Hierarchical Implicit Surface Approximation. Ourscheme for the approximation to a SLIM surface fr oma polygonal mesh is originated from the mesh simplifi-cation method. The algorithm itself is quite simple, fast,and robust for creating a hierarchical tree structure ofc The Eurographics Association 2006.T. Kanai, Y. Ohtake & K. Kase / Hierarchical Error-Driven Approximation of Implicit SurfacesE < 1.0 × 10−1E < 1.0 × 10−2E < 1.0 × 10−3E < 1.0 × 10−4E < 1.0 × 10−5Figure 1: Error-driven approximation of SLIM surfaces for “bimba” mesh (1.2M polygons). Different specifications of errorthresholds enable us to quickly generate various resolutions of SLIM surfaces. The number of nodes is: 721, 2,258, 7,076,22,317, and 70,273 (from left to right). Color balls shown in the bottom denote a set of supports for the corresponded SLIMsurfaces. Colors are assigned according to the error E which decreases from red to green.implicit surfaces. Since our algorithm computes a set ofimplicit surfaces in the order of increasing errors, it iseasy to build such a hierarchy based on errors. Geometricfeatures such as creases or corners can be preserved inthe process of our algorithm.Partition of Unity Evaluation with Sh arp Features. Topolygonize and visualize implicit surfaces with sharpfeatures, we propose a new Partition of Unity (PU)evaluation method which can exactly estimate creaseedges. This new PU method is valid for the genericrepresentation of SLIM surfaces and is well-fi tted to ourapproximation algorithm.Fig.1 clearly demonstrates the characteristics of our ap-proach. We assign an error value calculated in the approxi-mation process to each node of a SLIM surface. Using the hi-erarchical structure of a SLIM surface, we can then quicklyextract a set of implicit surfaces within an error thresholdspecified by the user. Such the run-time extraction is usefulfor LOD rendering of SLIM surfaces. Also, the idea of suchan error-driven extraction is a natural approach to control fit-ting errors for the use of the applications such as CAD.1.1. Related WorkThe most relevant research to ours can be seen in [SOS04].They have proposed a construction method of implicit sur-faces which approximates or interpolates polygonal meshes.Their method uses Moving Least Squares (MLS) surfacesimposed with additional constraints such as points, nor-mals, or integrals over polygons. The difference betweentheir approach and ours is the algorithm of surface construc-tion. Their algorithm first collects neighbor primitives (e.g.points, polygons) within an error threshold for each primi-tive. For such neighbor primitives, they fit a plane to gener-ate a MLS surface. In contrast, our algorithm is performedhierarchically. A set of implicit surfaces with different r es-olutions can be generated by executing the algorithm onlyonce.Many approaches on implicit surface reconstruction froma set of input points have been proposed. In [SPOK95,CBC∗01, TO02, YT02] the
View Full Document
Unlocking...