PDF (Thesis)
Contents
1. In the standard case the sum of the angles around any internal vertex is fixed to 27 and the sum of the angles around any boundary vertex is left free However one can also fix boundary angles to control the shape of the parameter domain It is also possible to fix the sum of the angles around some internal vertices to 27 which makes this vertices cone singularities while the rest of the parameterization remains continuous piecewise flat surface In this case V is the number of the 16 vertices for which cone angle is fixed it is also possible to fix the range of the sum 3 F 100010000 T 0 O Eine 3 4 0 0 0 100010 A lt T A O Where Ejn is the number of the internal edges because the previous constraints ensure that O for the boundary edge are within the valid bounds The 0 1 values in all the above matrices correspond to incidence relations described in Figure 3 1 3 2 Energy Minimization After correct O angles are computed non linear energy minimization is performed in order to find valid radii of circumcircles of flattened mesh The final solution is a minimizer of the following functional where the variables x are the logarithms of the radii Energy i i Seci x Y ImLi2 e 7 ImLig e 4 m 0 xi xj Y 2l 0 axr Eint Epary F Gradient ha e 1 J 1 Sect x 21 A AB de T 0 Ox Eim fi e WA cos 9 Epary fi Hessi2. for the infor mation on CON format iv lt singularities file gt Give the path for the input file with cone singularities see below for the information on the format ie lt edges to cut file gt Give the path for the input file list of edges to cut see below for the information on the format oc lt output CON file gt Give the path for the output CON file computed parameterization is stored as new edge lengths no Only cut if cuts are provided and layout mesh no parameterization is computed Input mesh needs to be a piecewise flat surface lt text file with options gt All the options from above can be stored in the text file and then the text file is passed to the program as a single command line argument File Formats OBJ format Standard obj format is used to represent triangle meshes If the mesh does not have texture coordinates the OBJ file is just a list of lines that start with v and are followed by 3 doubles to represent vertex positions and a list of lines that start with f and are followed by three integers to represent vertices of each face v lt x coord gt lt y coord gt lt z coord gt v lt x coord gt lt y coord gt lt z coord gt f lt vert id 1 gt lt vert id 2 gt lt vert id 3 gt f lt vert id 1 gt lt vert id 2 gt lt vert id 3 gt Note vertex ids go from 1 to N where N is the number of vertices in the mesh When texture coordinates are assigned the for
3. such a way that it should not be too difficult to adapt it for a different nonlinear solver Refer to the documentation in the AnglesOptimization CirclePattern and EnergyMinimization classes for more information 2 2 1 Using Other Nonlinear Solvers Currently the black box external library MOSEK is used to perform quadratic programming for finding optimal theta angles and convex unconstrained non linear minimization for finding the radii of the circumcircles of the triangles in the parameterization One could use a different non linear solvers if either one does not have access to MOSEK or a better solver is available This will re quire some changes in the code however as most solvers use a similar interface the changes will be minimal If you do not have a library to do quadratic programming the problem of finding optimal theta angles can be rewritten as convex non linear minimization with linear constraints We found that the results of such a minimization are similar to those of quadratic programming The non linear problem has the following set up let a and aj be alpha angles opposite to the edge e all the amp angles are the variables the angles we are looking for and are the correspondent angles in the original mesh 10 Energy A A A A A 0 j Cj 10 Oi E G y toga log Olji log 7 Oi ji J J j j 4 ei CE int Qij jj TT Oj Oji WEO 4 HU Ji Qi T Oi ei Ebndry 1 ij
4. 3 1 04g T Ay a4 and Opc T 0 This representation for Os is particularly convenient because the condition for existence of solution for circle pattern problem is existence of coherent angle system A coherent angle system is expressed 15 in terms of angles such that they are all positive they sum to 7 inside each triangle and they form Os which are between 0 and 7 So the problem of finding valid and optimal angles can be formulated as finding new amp s which form a coherent angles system satisfy boundary conditions at vertices usually sum to 27 around internal vertices and are as close as possible to original as The natural way to solve the angle optimization problem is to use quadratic programming The vari able of the quadratic program are A i a and there are 3 F variables where F is the number of triangles in the mesh The quadratic objective is A min which is just an identity matrix and variables are subject to the following 4 types of constraints Vi Aj gt Qj 3 1 Where we picked e 107 to ensure that the gt relation is satisfied 3 F 1110000 0 0 TT Nie fy Oi Fi 0001110 00 a TV ief 0 3 2 000000111 T Lie Oi The sum of the current as in each triangle is subtracted from 7 to ensure that As sum to the correct value a similar subtraction is done in the next two matrices 3 F 00100100 1 20 Y izo 06 WA Liv 3 3 000010100 a ANA
5. 4 in 7 The input file is a list of lines lt vert id gt lt min angle gt lt max angle gt Note vertex ids go from 1 to N where N is the number of vertices in the mesh The values for the angles are given as multiples of pi e g 0 5 means 1 57 radians Maximum and minimum values for the cone angle can be and usually are the same Edge Cuts file format This file gives information about cuts provided by the user Format of the file is a list of lines lt vert from id gt lt vert to id gt lt face id gt The information in the file is somewhat redundant but as eventually we want to allow non regular meshes there might be two half edges with the same end points Note vertex ids go from 1 to N where N is the number of vertices in the mesh face ids go from 1 to M where M is the number of faces This cuts can be defined manually for example using the graphical user interface provided in 6 that connects two selected cone singularities with a shortest path Alternatively one of the existing mesh partitioning algorithms such as 5 9 can be adapted to define valid cuts 2 1 3 Limitations on the Input Mesh The input meshes need to be 2 manifold connected regular triangle surfaces stored in either OBJ or CON format Although this method can be used to parameterize some non regular surfaces the current version of the code does not support this If the mesh has holes they need to be filled prior to parameterization When no c
6. Gradient JE G i gt 1 wil 1 A A T A A T ii nn Dj Aj IO Oi Oj TI yj hj for angles opposite to internal edge JE amp 1 1 1 1 d j Qij n ij Qij TT Qij for angles opposite to boundary edge Hessian 0 E a 1 1 A A we A A 00 0 Cj di TT Gj ji 0 E amp 1 Ada 1 j ji for angles opposite to internal edge 0 E a 1 1 Ijk hj rm iis for angles opposite to boundary edge In cases when division by zero occurs infinity some very large number needs to be returned Constraints There are two types of linear constraints for alpha angles e all alpha angles inside a triangle sum to pi e all alpha angles around a vertex sum to the prescribed cone angle of the vertex 11 Figure 2 2 The Hygeia 50K triangles and rabbit 26K triangles models parameterized over the sphere with the parameterization visualized through textures In the case of Hygeia a grid of latti tude longitude lines The rabbit is textured with points in an icosahedral pattern Note the typical area distortion when mapping the head and ear regions to the sphere No less the roundness of the texture dots is well preserved through the mapping 2 2 2 Spherical Parameterization It can be useful sometimes to parameterize closed genus zero mesh onto the sphere The algorithm to do it is e Remove one vertex of the mesh and all incident faces e Use CirclePatterns code to do the paramet
7. Implementation of Circle Pattern Parameterization Thesis by Liliya Kharevych In Partial Fulfillment of the Reguirements for the Degree of Master of Science California Institute of Technology Pasadena California 2005 Submitted June 3 2006 il 2005 Liliya Kharevych All Rights Reserved 111 Acknowledgements This is a joint project with Boris Springborn and Peter Schr der This work was supported in part by NSF DMS 0220905 DMS 0138458 ACI 0219979 DFG Research Center MATHEON Mathe matics for Key Technologies DOE W 7405 ENG 48 B341492 Center for the Mathematics of Information Alias and Pixar Special thanks to Alexander Bobenko Mathieu Desbrun Nathan Litke Ilja Friedel Cici Koenig Matthew Fisher Weiwei Yang Sharif Elcott Manuel Lombardini and Donnie Pinkston iv Abstract Circle Pattern is a novel method for the construction of discrete conformal mappings from surface meshes of arbitrary topology to the plane This approach is based on representing a mesh as arrange ments of circles one for each face with prescribed intersection angles Given these angles the circle radii follow as the unique minimizer of a convex energy The method supports very flexible boundary conditions ranging from free boundaries to control of the boundary shape via prescribed curvatures Closed meshes of genus zero can be parameterized over the sphere To parameterize higher genus meshes we introduc
8. an 9 Seci X _ sin dxidx cosh x x cos O Seci x _ j sin OxjOx Exch cosh x xj cos All the sums are taken over edges not the half edges The variables O are defined for each edge and represent an angle of intersection of two circumcircles of triangles meeting on this edge Since gradient and Hessian of the energy are available and furthermore the Hessian is non negative 17 standard Newton methods will easily find the minimum One can either implement the solver or use any of the existing black box solvers We have tried multiple solvers and found that MOSEK performs the best for this problem 3 3 Layout When no cone singularities are used in the interior of the mesh layout procedure can be performed after the energy minimization If cone singularities are used then edge cuts need to be defined The cuts need to be defined in such a way that when the mesh is cut each patch is a disk with single boundary loop and each cone singularity is at the boundary of at least one patch There are multiple ways to find a planar layout of the mesh when intersection angles and radii of the circumcircles r are known In the current code release we compute edge lengths as le 2r sin Q where for the internal edges 1211 T Q atan2 sin 0 e cos 0 za atan2 1 e cos 0 e sin0 and for the boundary edges T e Notice that Pe is also Y angle formed by two edges opposite to
9. and see full documentation for the implementation of the method visit 6 Chapter 2 User Manual 2 1 Running the Code The code can be used with Windows or UNIX operating systems The only external library used is MOSEK 8 which is free for students This library does numerical optimization in our case quadratic programming and non linear convex minimization If you can download this library for your operating system and link it to the CirclePatterns code you should have no problem running the code on different operating systems We provide a Visual Studio NET project for Windows and sample makefile for UNIX Make sure that the path for the MOSEK library and include files corresponds to those on your computer 2 1 1 Command Line Options After the application is compiled either using Visual Studio or the Makefile it can be called with command line arguments to compute parameterizations of triangle meshes Standard way to call the application is CirclePatterns exe lt INPUT OPTS gt lt OUTPUT OPTS gt OTHER OPTS lt TEXT FILE WITH OPTS gt Where the supported options are e io lt input obj file gt Give the path for the input OBJ file that needs to be parameterized 2 1 2 00 lt output obj file gt Give the path for the output OBJ file computed parameterization is stored in vt coordinates of that file ic lt input CON file gt Give the path for the input CON file that needs to be parameterized see below
10. d circle packing Starting in 1936 with Koebe and followed few decades later by Andreev Thurston 12 Collins and Stephenson 2 and others the conformality of circle packing was proven to converge as circles get finer Unfortunately circle packings yield mappings which depend only on the combinatorics of the original mesh while we are seeking methods which depend on the geometry of the mesh Circle Pattern method was first introdued in 1 and later developed for graphics in 7 The ba sic algorithm consists of three stages In a first step each edge of the input mesh is assigned an angle 0 lt 0 lt a These angles serve to incorporate the original geometry into the circle pattern algorithm Choosing good angles is achieved by solving a quadratic program Section 3 1 Once the angles have been assigned the circle radii are found as the unique minimum of a convex energy Section 3 2 Finally the edge angles together with the found radii are used to lay out the mesh in the parameter domain Section 3 3 The mappings are always locally injective They may fail to be globally injective due to self overlap of the boundary of the parameter domain However this can be avoided since we can prescribe the boundary curvature K if for any sequence of consecutive boundary vertices the sum of Ks is larger or equal 7 then there can be no overlap and the method is guaranteed to produce a global embedding In order to download the actual code
11. e cone singularities at designated vertices The parameter domain is then a piecewise Euclidean surface Cone singularities can also help to reduce the often very large area distortion of global conformal maps to moderate levels Our method involves two optimization problems a quadratic program and the unconstrained minimization of the circle pattern energy The latter is a convex function of logarithmic radius variables with simple explicit expressions for gradient and Hessian In this thesis we demonstrate implementation details and possible extensions to the Circle Pattern method Contents Acknowledgements Abstract 1 Introduction 2 User Manual 2 1 Rumingthelode Aa AI AWA 2 1 1 Command Line Options 21 2 Bile Pormats y e si ow ee Ge RO a UA 2 1 3 Limitations On the Input o o e 2 2 EXtending the Code vicios e EA eh Mg Ged 2 2 1 Using Other Nonlinear Solvers 2 2 2 Spherical Parameterization 2 2 3 UnitDiskParameterization 3 Implementation Details 3 1 Angles Optimization sts sos moa aa a aAa aai da i a Aa Sae ee 3 2 Energy Minimization 3 3 yA St alee hae wd AAA Ae bat Aa 4 Conclusions and Future Work Bibliography iii VO VO 0 A U U yu 11 12 14 14 16 17 18 19 Chapter 1 Introduction A conformal mapping between surfaces i
12. erization into the plane e Apply stereographic projection to the result and add the missing vertex at the north pole e Then in order to get lower area distortion normalization on the sphere can be performed One way to do the normalization is to put the barycenter of all the vertices at the center of the sphere There is a unique Lorentz transformation which achieves this as shown in 11 In order to do this normalization first find x which is a minimum of the following energy 1 are the coordinates of all the vertices on the sphere Energy Minimization over 3 variables y S x E og veV 12 Gradient OS x Wa Y Xi Vi oxi Ea l xx l v x Hessian 9 2S x XiXj viv Ls 1 dxidx E 1 x x 2 lv 1 x x Then compute the Lorentz transformation which moves x to the center of the sphere Now apply this transformation to all the vertices v This can be done by representing x and v in homogenous coordinates with x4 and v 4 being the 4th coordinate The final formula for transformation is 2 2 3 Unit Disk Parameterization For some applications such as morphing parameterizations to the unit disk could be important It can be done in the following way e Remove one vertex at the boundary and faces incident to it e Write out a cone singularities file that fixes the cone angle for all the remaining old bound ary vertices to 7 1 in the file e Use CirclePatterns code to do the
13. mat changes to the following v lt x coord gt lt y coord gt lt z coord gt v lt x coord gt lt y coord gt lt z coord gt vt lt x uv coord gt lt y uv coord gt vt lt x uv coord gt lt y uv coord gt f lt vert id 1 gt lt vert uv id 1 gt lt vert id 2 gt lt vert uv id 2 gt lt vert id 3 gt lt vert uv id 3 gt f lt vert id 1 gt lt vert uv id 1 gt lt vert id 2 gt lt vert uv id 2 gt lt vert id 3 gt lt vert uv id 3 gt CON format In order to represent mesh connectivity with edge length for each edge we changed OBJ format to store that information Note that only edge lengths are known not the position of the vertices The lines in the CON file are as following lt number of vertices gt lt number of faces gt f lt vert id 1 gt lt vert id 2 gt lt vert id 3 gt lt edge length 1 gt lt edge length 2 gt lt edge length 3 gt f lt vert id 1 gt lt vert id 2 gt lt vert id 3 gt lt edge length 1 gt lt edge length 2 gt lt edge length 3 gt Warning This format has some drawbacks only regular meshes can be represented only triangle meshes are parsed easily It might need to be improved later when the method is extended Note vertex ids go from 1 to N where N is the number of vertices in the mesh Cone Singularities file format This file is used to give information about allowed cone singulari 6 ties in the parameterization In order to learn more about cone singularities refer to Section
14. one which needs to have at least one cut from the tip to the boundary of the cone to lay it flat on the table or a rubber torus which needs to have two cuts to stretch the rubber over the table In our case cuts have exactly the same purpose they need to transform higher genus surfaces into the topological disk and allow singularities to be developed into the Euclidian plane So the cuts need to be assigned in such a way that all the cone vertices have at least one cut touching them and after the mesh is cut all the components are topologically equivalent to a disk It is also possible to save the resulting parameterization in the CON format and cut it later when the texture coordinates are needed The other option is to save the mesh in CON format and find texture coordinates only for the parts of the mesh 9 which need to be textured see Figure 2 1 2 2 Extending the Code This code is only an example of how the circle pattern method can be used The code can be used either as a separate application for finding a parameterization of the mesh or as a guideline on how to implement the circle pattern method for parameterizations One can write utility programs that generate cone singularities that minimize area distortion of parameterizations or compute cuts that are optimal for packing parameterized patched in the texture plane or create parameterizations over the sphere or unit disk or other 2D domains etc The code is also structured in
15. one singularities are defined only genus zero meshes with a single boundary can be parameterized see requirements for cone singularities and edge cuts to learn more about parameterization of higer genus meshes Because the resulting parameterizations are Delaunay conformal distortion is minimized if input meshes are also intrinsically Delaunay The simplest way to do this is to perform a se ries of edge flips whenever there are edges that do not satisfy the Delaunay property the sum of two angles opposite to an edge is greater than Pi To lower the error the mesh can be trans formed into an Intrinsic Delaunay Triangulation 4 Section 5 of 6 and given as input in ARI Wa PET ERLIEN xe La Ka L4 Liki li Figure 2 1 Feline model of genus 2 parameterized with cone singularities Rough outline of the parameter domain bottom left helps to compute cone singularities Fleur de Lis texture from the 2D parameter domain top left is used to texure map the feline model right Purple lines on the 3D model correspond to cuts in the parameter domain 8 CON format in a few cases the result of the Intrinsic Delaunay Triangulation algorithm is a non regular mesh the current version of the code needs to be extended to handle those cases Then the result can be output in CON format and all the edges that were flipped can be flipped back to achieve original triangulation In the future we will try to p
16. parameterization e Rotate texture coordinates so that the straight line of the boundary lies on the x axis with the rest of the mesh in the upper half plane e Pick a vertex that you want to be in the center of the final parameterization lets call it c 13 e Doa circle inversion around that vertex r2 x c x dar where x are new coordinates of each vertex x old coordinates and r is the circle radius which is equal to the y coordinate of c Using the concept of fixing the boundary curvatures via cone singularities input parameterizations of different shapes can be done 14 Chapter 3 Implementation Details 3 1 Angles Optimization B Figure 3 1 A cutout of the mesh for demonstration purposes Vertices B and C are boundary all the other vertices are internal Circle Pattern energy is defined in term of given s for each edge For an internal edge e 6 is the intersection angle between the circumcircles of two faces that share this edge If an edge e is bound ary then 0 is defined as an intersection between the circumcircle of a neighboring boundary face and a circle at infinity Lets call internal angles of a mesh angles formed by each two neighboring edges in a triangle as After few trigonometric observations we can express 0 as m Oi Qr where Q and are internal angles of the two neighboring triangles that are opposite to the edge e or m Q if e is boundary For example for Figure
17. rovide additional code to do this Of course non Delaunay meshes can also be parameterized but the angle distortion may be higher in that case Cone Singularities The main requirement for input cone singularities in the file is for the cone angle divided by 7 to be in 0 valence of vertex range which means the actual cone angle is bounded below by O and bounded above by z valence of the vertex or equivalently Gaussian curvature of the singularity vertex is between 2 valence of the vertex and 27 The cone angle at a vertex is defined as the sum of incident angles and the Gaussian curvature at a vertex is 27 minus the cone angle After all the singularities are prescribed the Gauss Bonet Equation Y Ki ys kj 20x 2 1 cone vertices vi boundary vertices v where K is the Gaussian curvature at interior singularities and k is the curvature at the boundary vertices curvature at the boundary is equal to 7 minus the sum of incident angles at the boundary In order to be sure that the equation is satisfied it could be useful to give a range as a value for the cone angle of a singularity Giving a range especially a large range for all singularities usually does not give the best results in terms of area distortion Edge Cuts When the mesh is parameterized with cone singularities it needs to be cut in order to assign texture coordinates for all the vertices The best way to understand why cuts are needed is to imagine a paper c
18. s ACM Transactions on Graphics 2006 To appear MOSEK Constrained quadratic minimization software http www mosek com 2005 Ver sion 3 1142 9 10 11 12 20 SANDER P V WOOD Z J GORTLER S J SNYDER J AND HOPPE H Multi chart geometry images In SGP 03 Proceedings of the 2003 Eurographics ACM SIGGRAPH symposium on Geometry processing Aire la Ville Switzerland Switzerland 2003 Euro graphics Association pp 146 155 SHEFFER A L VY B MOGILNITSKY M AND BOGOMYAKOV A ABF Fast and Robust Angle Based Flattening ACM Trans Graph 24 2 2005 311 330 SPRINGBORN B A unique representation of polyhedral types Math Z 2005 THURSTON W P The finite Riemann mapping theorem Invited talk at the symposium on the occasion of the proof of the Bieberbach conjecture held at Purdue University March 1985 1985
19. s a transformation that preserves local angles Since there is no angle distortion under these mappings they have been widely used in computer graphics for parameterizations Conformal mappings are also important in other areas of engineering and physics because they represent analytic functions This allows many problems to be solved ona simple domain and than the solution is conformally mapped to more complicated domains Usually conformal mappings in the discrete setting are approximated by discretizing Cauchy Riemann and Laplaces equations using finite elements or similar techniques 3 Although these techniques have been proved to work well they either do not give control over the shape of the boundary of the map ping or when the shape of the boundary is fixed angle distortion is created next to the boundary Rather then discretizing the continuous equations this work approaches the problem through the notion of a discrete conformal mapping In order to choose correct measurements for discrete geometry we need to delve deeply into geo metrical concepts of the continuous theory For example another way to think about continuous conformal mappings is that they map infinitesimal circles to infinitesimal circles This definition promotes the idea of using finite circles in the discrete setting The circles are arranged in some kind of specified order and the mapping changes their radii but their arrangement stays the same This approach is calle
20. the edge e however these as are different then the ones computed during angles optimization the sum of opposite Ys is preserved not each individual one Depending on circumstances different layout procedure can be choosen for example numerical accuracy can be improved by using a layout procedure as in 10 18 Chapter 4 Conclusions and Future Work We have presented a new method to parameterize arbitrary topology surface meshes It is based on the mathematical theory of circle patterns In the case of bounded domains the shape of the boundary may be determined by free boundary conditions or by prescribing the curvature of the boundary This provides a high degree of flexibility in controlling the boundary shape ranging from disks and simple polygonal outlines to more complex boundary arrangements Introducing cone singularities we are able to mitigate the usually high area factor in conformal parameterizations Cone singularities are also the key in our approach to dealing with globally continuous parameter izations of arbitrary topology meshes over Euclidean domains with cone singularities We provide the implementation of the method code documentation and some suggestions on how to improve or modify the current implementation There are still a few questions to answer and directions for the interesting projects Some of them are e Where to put cone singularities and what the cone angle value should be to achieve small area distor
21. tion while maintaining small number of singular points e What is the best way to texture map a piecewise flat surface e Application of this parameterization algorithm for remeshing e Finding optimal cuts 19 Bibliography 1 2 a 3 4 5 6 7 8 BOBENKO A I AND SPRINGBORN B A Variational Principles for Circle Patterns and Koebe s Theorem Transactions of the American Mathematical Society 356 2004 659 689 COLLINS C AND STEPHENSON K A Circle Packing Algorithm Computational Geome try Theory and Applications 25 2003 233 256 DESBRUN M MEYER M AND ALLIEZ P Intrinsic Parameterizations of Surface Meshes Computer Graphics Forum Proceedings of Eurographics 2002 21 3 2002 209 218 FISHER M SPRINGBORN B BOBENKO A I AND SCHRODER P An Algorithm for the Construction of Intrinsic Delaunay Triangulations with Applications to Digital Geometry Processing In Discrete Differential Geometry E Grinspun M Desbrun and P Schr der Eds Course Notes ACM SIGGRAPH 2006 JULIUS D KRAEVOY V AND SHEFFER A D charts Quasi developable mesh segmen tation In Computer Graphics Forum Proceedings of Eurographics 2005 Dublin Ireland 2005 vol 24 Eurographics Blackwell pp 581 590 KHAREVYCH L Circle Patterns Code and Documentation 2006 Version 1 0 KHAREVYCH L SPRINGBORN B AND SCHRODER P Discrete Conformal Mappings via Circle Pattern
Download Pdf Manuals
Related Search