复制成功
  • 图案背景
  • 纯色背景
  •   |  注册
  • /
  • 批注本地保存成功,开通会员云端永久保存 去开通
  • 网上书库

    上传于:2013-01-03

    粉丝量:691

    上传资料均来自于互联网,若有侵权,立刻通知删除。

    

    Guide to Computational Geometry Processing - Foundations, Algorithms, and Method.

    下载积分:800

    内容提示: Guide to Computational GeometryProcessing Jakob Andreas BærentzenFrançois AntonrJens GravesenrrHenrik AanæsGuide toComputationalGeometryProcessingFoundations, Algorithms, and Methods Jakob Andreas BærentzenDepartment ofInformatics andMathematical ModellingTechnical University of DenmarkKongens Lyngby, DenmarkJens GravesenDepartment ofMathematicsTechnical University of DenmarkKongens Lyngby, DenmarkFrançois AntonDepartment ofInformatics andMathematical ModellingTechnical University of DenmarkKongen...

    亚博足球app下载格式:PDF| 浏览次数:12| 上传日期:2013-01-03 10:05:56| 亚博足球app下载星级:
    Guide to Computational GeometryProcessing Jakob Andreas BærentzenFrançois AntonrJens GravesenrrHenrik AanæsGuide toComputationalGeometryProcessingFoundations, Algorithms, and Methods Jakob Andreas BærentzenDepartment ofInformatics andMathematical ModellingTechnical University of DenmarkKongens Lyngby, DenmarkJens GravesenDepartment ofMathematicsTechnical University of DenmarkKongens Lyngby, DenmarkFrançois AntonDepartment ofInformatics andMathematical ModellingTechnical University of DenmarkKongens Lyngby, DenmarkHenrik AanæsDepartment ofInformatics andMathematical ModellingTechnical University of DenmarkKongens Lyngby, DenmarkISBN 978-1-4471-4074-0DOI 10.1007/978-1-4471-4075-7Springer London Heidelberg New York DordrechtISBN 978-1-4471-4075-7 (eBook)Library of Congress Control Number: 2012940245© Springer-Verlag London 2012This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part ofthe material is concerned, specifically the rights oftranslation, reprinting, reuse ofillustrations, recitation,broadcasting, reproduction on microfilms or in any other physical way, and transmission or informationstorage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodologynow known or hereafter developed. Exempted from this legal reservation are briefexcerpts in connectionwith reviews or scholarly analysis or material supplied specifically for the purpose of being enteredand executed on a computer system, for exclusive use by the purchaser of the work. Duplication ofthis publication or parts thereof is permitted only under the provisions of the Copyright Law of thePublisher’s location, in its current version, and permission foruse must always be obtained from Springer.Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violationsare liable to prosecution under the respective Copyright Law.The use ofgeneral descriptive names, registered names, trademarks, service marks, etc. in this publicationdoes not imply, even in the absence ofa specific statement, that such names are exempt from the relevantprotective laws and regulations and therefore free for general use.While the advice and information in this book are believed to be true and accurate at the date of pub-lication, neither the authors nor the editors nor the publisher can accept any legal responsibility for anyerrors or omissions that may be made. The publisher makes no warranty, express or implied, with respectto the material contained herein.Printed on acid-free paperSpringer is part ofSpringer Science+Business Media (www.springer.com) PrefaceThis book grew out of a conversation between two of the authors. We were dis-cussing the fact that many ofour students needed a set ofcompetencies, which theycould not really learn in any course that we offered at the Technical University ofDenmark. The specific competencies were at the junction of computer vision andcomputer graphics, and they all had something to do with “how to deal with” dis-crete 3D shapes (often simply denoted “geometry”).The tiresome fact was that many of our students at graduate level had to pick upthings like registration ofsurfaces, smoothing ofsurfaces, reconstruction from pointclouds, implicit surface polygonization, etc. on their own. Somehow these topics didnot quite fit in a graphics course or a computer vision course. In fact, just a few yearsbefore our conversation, topics such as these had begun to crystallize out of com-puter graphics and vision forming the field of geometry processing. Consequently,we created a course in computational geometry processing and started writing a setofcourse notes, which have been improved over the course ofa few years, and now,after some additional polishing and editing, form the present book.Of course, the question remains: why was the course an important missing piecein our curriculum, and, by extension, why should anyone bother about this book?The answer is that optical scanning is becoming ubiquitous. In principle, anytechnically minded person can create a laser scanner using just a laser pointer, a webcam, and a computer together with a few other paraphernalia. Such a device wouldnot be at the 20 micron precision which an industrial laser scanner touts these days,but it goes to show that the principles are fairly simple. The result is that a numberof organizations now have easy access to optical acquisition devices. In fact, manyindividuals have too—since the Microsoft Kinect contains a depth sensing camera.Geometry also comes from other sources. For instance, medical CT, MR and 3Dultrasound scanners provide us with huge volumetric images from which we canextract surfaces.However, often we cannot directly use this acquired geometry for its intendedpurpose. Any measurement is fraught with error, so we need to be able to filter thegeometry to reduce noise, and usually acquired geometry is also very verbose andsimplification is called for. Often we need to convert between various representa-tions, or we need to put together several partial models into one big model. In otherwords, raw acquired geometry needs to be processed before it is useful for someenvisioned purpose, and this book is precisely about algorithms for such processingofgeometry as is needed in order to make geometric data useful.v viPrefaceOverview and GoalsGeometry processing can loosely be defined as the field which is concernedwith how geometric objects (points, lines, polygons, polyhedra, smooth curves, orsmooth surfaces) are worked upon by a computer. Thus, we are mostly concernedwith algorithms that work on a (large) set of data. Often, but not necessarily, wehave data that have been acquired by scanning some real object. Dealing with laserscanned data is a good example ofwhat this book is about, but it is by no means theonly example.We could have approached the topic by surveying the literature within the topicscovered by the book. That would have led to a bookgiving an overview ofthe topics,and it would have allowed us to cover more methods than we actually do. Instead,since we believe that we have a relatively broad practical experience in the areas,we have chosen to focus on methods we actually use, cf. Chap. 1. Therefore, withvery few exceptions, the methods covered in this book have been implemented byone or more of the authors. This strategy has allowed us to put emphasis on whatwe believe to be the core tools of the subject, allowing the reader to gain a deeperunderstanding of these, and, hopefully, made the text more accessible. We believethat our strategy makes this book very suitable for teaching, because students areable to implement much of the material in this book without needing to consultother texts.We had a few other concerns too. One is that we had no desire to write a bookwhich was tied to a specific programming library or even a specific programminglanguage, since that tends to make some of the information in a book less general.On the other hand, in our geometry processing course, we use C++ for the exer-cises in conjunction with a library called GEL1which contains many algorithmsand functions for geometry processing. In this book, we rarely mention GEL exceptin the exercises, where we sometimes make a note that some particular problem canbe solved in a particular way using the GEL library.In many ways this is a practical book, but we aim to show the connections tothe mathematical underpinnings: Most of the methods rely on theory which it isour desire to explain in as much detail as it takes for a graduate student to not onlyimplement a given method but also to understand the ideas behind it, its limitationsand its advantages.Organization and FeaturesA problem confronting any author is how to delimit the subject. In this book, wecover a range of topics that almost anyone intending to do work in geometry pro-cessing will need to be familiar with. However, we choose not to go into concrete1C++ library developed by some ofthe authors ofthis book and freely available. URL provided atthe end ofthis preface. Prefaceviiapplications ofgeometry processing. For instance, we do not discuss animation, de-formation, 3D printing of prototypes, or topics pertaining to (computer graphics)rendering of geometric data. In the following, we give a brief overview of the con-tents ofthe book.Chapter 1 contains a briefoverview oftechniques for acquisition of3D geometryand applications of3D geometry.Chapters 2–4 are about mathematical theory which is used throughout the restof the book. Specifically, these chapters cover vector spaces, metric space, affinespaces, differential geometry, and finite difference methods for computing deriva-tives and solving differential equations. For many readers these chapters will not benecessary on a first reading, but they may serve as useful points of reference whensomething in a later chapter is hard to understand.Chapters 5–7 are about geometry representations. Specifically, these chapterscover polygonal meshes, splines, and subdivision surfaces.Chapter 8 is about computing curvature from polygonal meshes. This is some-thing often needed either for analysis or for the processing algorithms described inlater chapters.Chapters 9–11 describe algorithms for mesh smoothing, mesh parametrization,and mesh optimization and simplification—operations very often needed in order tobe able to use acquired geometry for the intended purpose.Chapters 12–13 cover point location databases and convex hulls of point sets.Point databases (in particular kD trees) are essential to many geometry processingalgorithms, for instance registration. Convex hulls are also needed in numerous con-texts such as collision detection.Chapters 14–18 are about a variety of topics that pertain to the reconstructionof triangle meshes from point clouds: Delaunay triangulation, registration of pointclouds (or meshes), surface reconstruction using scattered data interpolation (withradial basis functions), volumetric methods for surface reconstruction and the levelset method, and finally isosurface extraction. Together, these chapters should pro-vide a fairly complete overview of the algorithms needed to go from a raw set ofscanned points to a final mesh. For further processing ofthe mesh, the algorithms inChaps. 9–11 are likely to be useful.Target AudienceThe intended reader of this book is a professional or a graduate student who isfamiliar with (and able to apply) the main results of linear algebra, calculus, anddifferential equations. It is an advantage to be familiar with a number of more ad-vanced subjects, especially differential geometry, vectorspaces, and finite differencemethods for partial differential equations. However, since many graduate studentstend to need a brush up on these topics, the initial chapters cover the mathematicalpreliminaries just mentioned.The ability to program in a standard imperative programming language such asC++, C, C#, Java or similar will be a distinct advantage if the reader intends to putthe material in this book to actual use. Provided the reader is familiar with such a viiiPrefaceprogramming language, he or she should be able to implement many ofthe methodspresented in this book. The implementation will, however, be much easierifalibraryofbasic data structures and algorithms for dealing with linear algebra and geometricdata is available.Supplemental ResourcesAt the web page ofthis book, http://www.springer.com/978-1-4471-4074-0, we pro-vide three types of supplementary material.1. Data for exercises. This comprises point sets and polygonal meshes suitable forsolving some ofthe exercise problems which are listed at the end ofeach chapter.2. The GEL library. GEL is an abbreviation for Geometry and Linear algebra Li-brary’—a collection of C++ classes and functions distributed as source code.GEL is useful for geometry processing and visualization tasks in particular andmost ofthe algorithms in this book have been implemented on top of GEL.3. Example C++ programs. Readers interested in implementing the material in thisbook using GEL will probably find it very convenient to use our example pro-grams. These programs build on GEL and should make it easy and convenientto get started. The example programs are fairly generic, but for all programmingone of the examples should serve as a convenient starting point.Notes to the InstructorAs mentioned above, the first three chapters in this bookare considered to be prereq-uisite material, and would typically not be part of a course syllabus. For instance,we expect students who follow our geometry processing course to have passed acourse in differential geometry, but experience has taught us that not all come withthe prerequisites. Therefore, we have provided the four initial chapters to give thestudents a chance to catch up on some ofthe basics.In general, it might be a good idea to consider the grouping of chapters given inthe overview above as the “atomic units”. We do have references from one chapterto another, but the chapters can be read independently. The exception is that Chap. 5introduces many notions pertaining to polygonal meshes without which it is hardto understand many of the later chapters, so we recommend that this chapter is notskipped in a course based on this book.GEL is just one library amongst many others, but it is the one we used in theexercises from the aforementioned course. Since we strongly desire that the bookshould not be too closely tied to GEL and that it should be possible to use this bookwith other packages, no reference is made to GEL in the main description of eachexercise, but in some of the exercises you will find paragraphs headed by[GEL Users]These paragraphs contain notes on material that can be used by GEL users. PrefaceixAcknowledgementsA number of 3D models and images have been provided by courtesy of people ororganizations outside the circle of authors.• The Stanford bunny, provided courtesy ofThe Stanford Computer Graphics Lab-oratory, has been used in Chaps. 9, 11, 16, and 17. In most places Greg Turk’sreconstruction (Turk and Levoy, Computer Graphics Proceedings, pp. 311–318,1994) has been used, but in Chap. 17, the geometry ofthe bunny is reconstructedfrom the original range scans.• The 3D scans of the Egea bust and the Venus statue both used in Chap. 11 areprovided by the AIM@SHAPE Shape Repository.• Stine Bærentzen provided the terrain data model used in Chaps. 9 and 11.• Rasmus Reinhold Paulsen provided the 3D model of his own head (generatedfrom a structured light scan), which was used in Chap. 11.• In Fig. 10.3 we have used two pictures taken from Wikipedia. The Mercator pro-jection by Peter Mercator, http://en.wikipedia.org/wiki/File:MercNormSph.pngand Lambert azimuthal equal-area projection by Strebe, http://en.wikipedia.org/wiki/File:Lambert_azimuthal_equal-area_projection_SW.jpg.• In Fig. 12.4, we have used the 3D tree picture taken from Wikipedia, http://en.wikipedia.org/wiki/File:3dtree.png.• In Fig. 12.10, we have used the octree picture taken from Wikipedia, http://fr.wikipedia.org/wiki/Fichier:Octreend.png.• In Fig. 12.11, we have used the r-tree picture taken from Wikipedia, http://en.wikipedia.org/wiki/File:R-tree.svg.• In Fig. 12.12, we have used the 3D r-tree picture taken from Wikipedia, http://en.wikipedia.org/wiki/File:RTree-Visualization-3D.svg.We would like to acknowledge our students, who, through their feedback, havehelped us improve the course and the material which grew into this book. We wouldalso like to thank the company 3Shape. Every year, we have taken our class to3Shape for a brief visit to show them applications of the things they learn. That hasbeen very helpful in motivating the course and, thereby, also the material in thisbook.Research and university teaching is becoming more and more of a team sport,and as such we would also like to thank our colleagues at the Technical Univer-sity of Denmark for their help and support in the many projects where we gainedexperience that has been distilled into this book.Last but not least, we would like to thank our families for their help and support.Jakob Andreas BærentzenJens GravesenFrançois AntonHenrik AanæsKongens Lyngby, Denmark Contents1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1From Optical Scanning to 3D Model . . . . . . . . . . . . . . . .1.2Medical Reverse Engineering . . . . . . . . . . . . . . . . . . . .1.3Computer Aided Design . . . . . . . . . . . . . . . . . . . . . . .1.4Geographical Information Systems . . . . . . . . . . . . . . . . .1.5Summary and Advice . . . . . . . . . . . . . . . . . . . . . . . .References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1257899Part IMathematical Preliminaries2Vector Spaces, Affine Spaces, and Metric Spaces2.1Vector Spaces and Linear Algebra . . . . . . . . . . . . . . . . . .2.1.1Subspaces, Bases, and Dimension . . . . . . . . . . . . . .2.1.2Linear Maps, Matrices, and Determinants . . . . . . . . . .2.1.3Euclidean Vector Spaces and Symmetric Maps . . . . . . .2.1.4Eigenvalues, Eigenvectors, and Diagonalization . . . . . .2.1.5Singular Value Decomposition2.2Affine Spaces. . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.1Affine and Convex Combinations . . . . . . . . . . . . . .2.2.2Affine Maps . . . . . . . . . . . . . . . . . . . . . . . . .2.2.3Convex Sets . . . . . . . . . . . . . . . . . . . . . . . . .2.3Metric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .1313151824283032343637384243. . . . . . . . . . . . . . .3Differential Geometry . . . . . . . . . . . . . . . . . . . . . . . . . .3.1First Fundamental Form, Normal, and Area . . . . . . . . . . . . .3.2Mapping of Surfaces and the Differential . . . . . . . . . . . . . .3.3Second Fundamental Form, the Gauß Map and the Weingarten Map3.4Smoothness of a Surface . . . . . . . . . . . . . . . . . . . . . . .3.5Normal and Geodesic Curvature . . . . . . . . . . . . . . . . . . .3.6Principal Curvatures and Direction . . . . . . . . . . . . . . . . .3.7The Gaußian and Mean Curvature . . . . . . . . . . . . . . . . . .3.8The Gauß–Bonnet Theorem . . . . . . . . . . . . . . . . . . . . .3.9Differential Operators on Surfaces45454648495051525455. . . . . . . . . . . . . . . . .xi xiiContents3.10 Implicitly Defined Surfaces . . . . . . . . . . . . . . . . . . . . .3.10.1 The Signed Distance Function . . . . . . . . . . . . . . . .3.10.2 An Arbitrary Function . . . . . . . . . . . . . . . . . . . .3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57586062634Finite Difference Methods for Partial Differential Equations . . . . .4.1Discrete Differential Operators . . . . . . . . . . . . . . . . . . .4.2Explicit and Implicit Methods . . . . . . . . . . . . . . . . . . . .4.3Boundary Conditions. . . . . . . . . . . . . . . . . . . . . . . .4.4Hyperbolic, Parabolic, and Elliptic Differential Equations . . . . .4.4.1Parabolic Differential Equations . . . . . . . . . . . . . . .4.4.2Hyperbolic Differential Equations . . . . . . . . . . . . . .4.4.3Elliptic Differential Equations . . . . . . . . . . . . . . . .4.5Consistency, Stability, and Convergence4.62D and 3D problems and Irregular Grids . . . . . . . . . . . . . .4.7Linear Interpolation . . . . . . . . . . . . . . . . . . . . . . . . .4.8Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65666871737374757577777979. . . . . . . . . . . . . .Part IIComputational Geometry Processing5Polygonal Meshes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.1Primitives for Shape Representation . . . . . . . . . . . . . . . . .5.2Basics of Polygonal and Triangle Meshes . . . . . . . . . . . . . .5.3Sources and Scourges ofPolygonal Models . . . . . . . . . . . . .5.4Polygonal Mesh Manipulation . . . . . . . . . . . . . . . . . . . .5.5Polygonal Mesh Representations . . . . . . . . . . . . . . . . . .5.6The Half Edge Data Structure . . . . . . . . . . . . . . . . . . . .5.6.1The Quad-edge Data Structure5.7Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83838486878991939696. . . . . . . . . . . . . . .6Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.1Parametrization. . . . . . . . . . . . . . . . . . . . . . . . . . .6.2Basis Functions and Control Points . . . . . . . . . . . . . . . . . 1006.3Knots and Spline Spaces on the Line . . . . . . . . . . . . . . . . 1006.4B-Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1026.4.1Knot Insertion and de Boor’s Algorithm6.4.2Differentiation . . . . . . . . . . . . . . . . . . . . . . . . 1046.5NURBS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1056.6Tensor Product Spline Surfaces . . . . . . . . . . . . . . . . . . . 1076.7Spline Curves and Surfaces in Practice . . . . . . . . . . . . . . . 1086.7.1Representation of Conics and Quadrics . . . . . . . . . . . 1096.7.2Interpolation and Approximation . . . . . . . . . . . . . . 1136.7.3Tessellation and Trimming of Parametric Surfaces . . . . . 1159999. . . . . . . . . . 104 Contentsxiii6.8References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1157Subdivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1197.1Subdivision Curves. . . . . . . . . . . . . . . . . . . . . . . . . 1207.1.1Eigenanalysis. . . . . . . . . . . . . . . . . . . . . . . . 1247.2Subdivision Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . 1267.2.1The Characteristic Map . . . . . . . . . . . . . . . . . . . 1287.3Subdivision Surfaces in Practice . . . . . . . . . . . . . . . . . . . 1307.3.1Subdivision Schemes. . . . . . . . . . . . . . . . . . . . 1327.3.2The Role of Extraordinary Vertices . . . . . . . . . . . . . 1377.3.3Boundaries and Sharp Edges7.3.4Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . 1397.4Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141. . . . . . . . . . . . . . . . 1388Curvature in Triangle Meshes . . . . . . . . . . . . . . . . . . . . . . 1438.1Estimating the Surface Normal . . . . . . . . . . . . . . . . . . . 1448.2Estimating the Mean Curvature Normal . . . . . . . . . . . . . . . 1468.3Estimating Gaußian Curvature using Angle Defects8.4Curvature Estimation based on Dihedral Angles . . . . . . . . . . 1508.5Fitting a Smooth Surface. . . . . . . . . . . . . . . . . . . . . . 1528.6Estimating Principal Curvatures and Directions . . . . . . . . . . . 1548.7Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1558.8Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158. . . . . . . . 1489Mesh Smoothing and Variational Subdivision . . . . . . . . . . . . . 1599.1Signal Processing . . . . . . . . . . . . . . . . . . . . . . . . . . 1609.2Laplacian and Taubin Smoothing . . . . . . . . . . . . . . . . . . 1619.3Mean Curvature Flow . . . . . . . . . . . . . . . . . . . . . . . . 1649.4Spectral Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . 1659.5Feature-Preserving Smoothing . . . . . . . . . . . . . . . . . . . . 1679.6Variational Subdivision . . . . . . . . . . . . . . . . . . . . . . . 1689.6.1Energy Functionals. . . . . . . . . . . . . . . . . . . . . 1699.6.2Minimizing the Energies . . . . . . . . . . . . . . . . . . . 1709.6.3Implementation . . . . . . . . . . . . . . . . . . . . . . . 1729.7Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173AppendixA Laplace Operator for a Triangle Mesh . . . . . . . . . . . 174References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17610Parametrization of Meshes . . . . . . . . . . . . . . . . . . . . . . . . 17910.1 Properties of Parametrizations . . . . . . . . . . . . . . . . . . . . 18110.1.1 Goals of Triangle Mesh Parametrization10.2 Convex Combination Mappings . . . . . . . . . . . . . . . . . . . 183. . . . . . . . . . 182 xivContents10.3 Mean Value Coordinates . . . . . . . . . . . . . . . . . . . . . . . 18410.4 Harmonic Mappings . . . . . . . . . . . . . . . . . . . . . . . . . 18610.5 Least Squares Conformal Mappings . . . . . . . . . . . . . . . . . 18610.5.1 Natural Boundary Conditions . . . . . . . . . . . . . . . . 18710.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19011Simplifying and Optimizing Triangle Meshes . . . . . . . . . . . . . 19111.1 Simplification of Triangle Meshes . . . . . . . . . . . . . . . . . . 19211.1.1 Simplification by Edge Collapses . . . . . . . . . . . . . . 19411.1.2 Quadric Error Metrics . . . . . . . . . . . . . . . . . . . . 19511.1.3 Some Implementation Details . . . . . . . . . . . . . . . . 19811.2 Triangle Mesh Optimization by Edge Flips . . . . . . . . . . . . . 19911.2.1 Energy Functions Based on the Dihedral Angles . . . . . . 20111.2.2 Avoiding Degenerate Triangles . . . . . . . . . . . . . . . 20311.2.3 Simulated Annealing. . . . . . . . . . . . . . . . . . . . 20411.3 Remeshing by Local Operations . . . . . . . . . . . . . . . . . . . 20711.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21011.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21012Spatial Data Indexing and Point Location . . . . . . . . . . . . . . . 21312.1 Databases, Spatial Data Handling and Spatial Data Models12.1.1 Databases. . . . . . . . . . . . . . . . . . . . . . . . . . 21412.1.2 Spatial Data Handling . . . . . . . . . . . . . . . . . . . . 21412.1.3 Spatial Data Models . . . . . . . . . . . . . . . . . . . . . 21512.2 Space-Driven Spatial Access Methods12.2.1 The kD Tree . . . . . . . . . . . . . . . . . . . . . . . . . 21712.2.2 The Binary Space Partitioning Tree . . . . . . . . . . . . . 21912.2.3 Quadtrees. . . . . . . . . . . . . . . . . . . . . . . . . . 21912.2.4 Octrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22112.3 Object-Driven Spatial Access Methods . . . . . . . . . . . . . . . 22112.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22312.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224. . . . 213. . . . . . . . . . . . . . . 21613Convex Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22713.1 Convexity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22713.2 Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22813.3 Convex Hull Algorithms in 2D. . . . . . . . . . . . . . . . . . . 23013.3.1 Graham’s Scan Algorithm . . . . . . . . . . . . . . . . . . 23113.3.2 Incremental (Semi-dynamic) Algorithm . . . . . . . . . . . 23313.3.3 Divide and Conquer Algorithm . . . . . . . . . . . . . . . 23513.4 3D Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23613.4.1 Incremental Algorithm . . . . . . . . . . . . . . . . . . . . 23713.4.2 Divide and Conquer Algorithm . . . . . . . . . . . . . . . 237 Contentsxv13.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23913.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23914Triangle Mesh Generation: Delaunay Triangulation14.1 Notation and Basic 2D Concepts14.2 Delaunay Triangulation . . . . . . . . . . . . . . . . . . . . . . . 24214.2.1 Refining a Triangulation by Flips . . . . . . . . . . . . . . 24614.2.2 Points not in General Position . . . . . . . . . . . . . . . . 24814.2.3 Properties of a Delaunay Triangulation . . . . . . . . . . . 24914.3 Delaunay Triangulation Algorithms . . . . . . . . . . . . . . . . . 25014.3.1 Geometric Primitives. . . . . . . . . . . . . . . . . . . . 25114.3.2 The Flip Algorithm . . . . . . . . . . . . . . . . . . . . . 25314.3.3 The Divide and Conquer Algorithm14.4 Stability Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25514.5 Other Subjects in Triangulation . . . . . . . . . . . . . . . . . . . 25714.5.1 Mesh Refinement . . . . . . . . . . . . . . . . . . . . . . 25714.5.2 Constrained Delaunay Triangulation . . . . . . . . . . . . 25714.6 Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . 25814.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260. . . . . . . . . 241. . . . . . . . . . . . . . . . . . 241. . . . . . . . . . . . 255153D Surface Registration via Iterative Closest Point (ICP) . . . . . . . 26315.1 Surface Registration Outline . . . . . . . . . . . . . . . . . . . . . 26315.2 The ICP Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . 26515.2.1 Implementation Issues . . . . . . . . . . . . . . . . . . . . 26715.2.2 Aligning Two 3D Point Sets . . . . . . . . . . . . . . . . . 26815.2.3 Degenerate Problems. . . . . . . . . . . . . . . . . . . . 27015.3 ICP with Partly Overlapping Surfaces . . . . . . . . . . . . . . . . 27015.4 Further Extensions of the ICP Algorithm . . . . . . . . . . . . . . 27215.4.1 Closest Point not a Vertex . . . . . . . . . . . . . . . . . . 27215.4.2 Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . 27215.5 Merging Aligned Surfaces . . . . . . . . . . . . . . . . . . . . . . 27415.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27416Surface Reconstruction using Radial Basis Functions . . . . . . . . . 27716.1 Interpolation of Scattered Data . . . . . . . . . . . . . . . . . . . 27816.2 Radial Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . 27916.2.1 Regularization . . . . . . . . . . . . . . . . . . . . . . . . 28116.3 Surface Reconstruction. . . . . . . . . . . . . . . . . . . . . . . 28216.4 Implicit Surface Reconstruction . . . . . . . . . . . . . . . . . . . 28216.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28516.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 xviContents17Volumetric Methods for Surface Reconstruction and Manipulation . 28717.1 Reconstructing Surfaces by Diffusion . . . . . . . . . . . . . . . . 28817.1.1 Computing Point Normals . . . . . . . . . . . . . . . . . . 29317.2 Poisson Reconstruction . . . . . . . . . . . . . . . . . . . . . . . 29717.3 The Level Set Method . . . . . . . . . . . . . . . . . . . . . . . . 29817.3.1 Discrete Implementation . . . . . . . . . . . . . . . . . . . 30017.3.2 Maintaining a Distance Field . . . . . . . . . . . . . . . . 30117.3.3 Curvature Flow in 2D . . . . . . . . . . . . . . . . . . . . 30217.3.4 3D Examples . . . . . . . . . . . . . . . . . . . . . . . . . 30317.4 Converting Triangle Meshes to Distance Fields . . . . . . . . . . . 30417.4.1 Alternative Methods . . . . . . . . . . . . . . . . . . . . . 30617.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30718Isosurface Polygonization . . . . . . . . . . . . . . . . . . . . . . . . 30918.1 Cell Based Isosurface Polygonization . . . . . . . . . . . . . . . . 30918.2 Marching Cubes and Variations . . . . . . . . . . . . . . . . . . . 31118.2.1 Ambiguity Resolution . . . . . . . . . . . . . . . . . . . . 31218.3 Dual Contouring . . . . . . . . . . . . . . . . . . . . . . . . . . . 31418.3.1 Placing Vertices . . . . . . . . . . . . . . . . . . . . . . . 31618.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31818.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319References . . . . . . . . . . . . . . . . ....

    关注我们

  • 新浪微博
  • 关注微信公众号

  • 打印亚博足球app下载
  • 复制文本
  • 下载Guide to Computational Geometry Processing - Foundations, Algorithms, and Methods.XDF
  • 您选择了以下内容