Discrete representation of a surface, especially the triangle mesh, is ubiquitous in numerical simulation and computer graphics. Compared with isotropic triangle meshes, anisotropic triangle meshes provide more accurate results in numerical simulation by capturing anisotropic features more faithfully. Furthermore, emerging applications in computer graphics and geometric modeling require reliable differential geometry information estimated on these anisotropic meshes. The first part of this thesis proposes a special type of anisotropic meshes, called shape-preserving meshes, provides guaranteed convergence of discrete differential operators on these meshes and devises an algorithm for generating shape-preserving meshes on free-form surfaces based on the mesh optimization framework with centroidal Voronoi tessellation (CVT). To improve the numerical stability in simulation, we discuss how to reduce the number of obtuse triangles in the mesh. The second part of the thesis discusses the non-uniqueness of anisotropic meshes to represent the same anisotropy defined on a domain, shows that of all anisotropic meshes, there exists one instance minimizing the number of obtuse triangles, and proposes a variational approach to suppressing obtuse triangles in anisotropic meshes by introducing a Minkowski metric in the CVT framework. On a complex shape, its topological information is also highly useful to guide the mesh generation. To extract topology properties, the Morse-Smale complex (MSC) is a classical tool and widely used in computer graphics. However, on a manifold with boundary, its MSC is not well defined. The final part of this thesis generalizes the MSC to manifolds with boundaries. Based on this generalized MSC (GMSC), an operator to merge n GMSCs of manifolds partitioning a large manifold is proposed. The merging operator is used in a divide-and-conquer approach on a massive data set, providing the potential to employ the computational power in a parallel manner. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Computer graphics applications call for various mesh generation techniques to visualize objects, store shape data, perform numerical analyses, etc. Mesh generation is also a fundamental research topic in many other engineering areas related to physical models described by partial differential equations. The reason that meshed surfaces are preferred over spline surfaces in many engineering applications is its flexibility in handling complex objects, while sharp features and boundaries can be represented without trimming, which is highly desired in numerical simulations. In this thesis, we study two methods for generating meshes with sharp features. Sharp features, such as creases and corners, are very common in mechanical objects. Hence effectively handling sharp features is of great importance to this kind of objects. The first method is to generate triangular subdivision surfaces with sharp features. Although there have been various methods to fit subdivision surfaces to different types of shape data, e.g., dense meshes and point clouds, none of these methods can handle sharp features effectively. We present a new exact evaluation scheme for all types of sharp features in Loop subdivision, and integrate the new evaluation scheme into the optimization framework to fit Loop subdivision surfaces to dense meshes. The second method is to generate quadrilateral meshes with varying element sizes which observe the user requirement. This method is inspired by the idea of spectral quadrangulation, but existing spectral quadrangulation methods are limited to closed surfaces due to its lack of proper boundary treatment. We present a new set of boundary conditions, and introduce the Quasi-Eigenfunction to assist the mesh generation process. The proposed boundary treatment is further applied to sharp features to handle mechanical objects. The quasi-eigenfunction based quadrangulation framework is also extended to 3D volumetric domain to generate hexahedral meshes. Experimental results and comparisons with existing methods are presented in each chapter to demonstrate the effectiveness of the proposed methods. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Computer Science / Doctoral / Doctor of Philosophy

This research examines procedural modeling in the eld of computer graphics. Procedural modeling automates the generation of objects by representing models as procedures that provide a description of the process required to create the model. The problem we solve with this research is the creation of a procedural modeling environment that consists of a procedural modeling language and a set of non-interactive modeling tools. A goal of this research is to provide comparisons between 3D manual modeling and procedural modeling, which focus on the modeling strategies, tools and model representations used by each modeling paradigm. A procedural modeling language is presented that has the same facilities and features of existing procedural modeling languages. In addition, features such as caching and a pseudorandom number generator is included, demonstrating the advantages of a procedural modeling paradigm. The non-interactive tools created within the procedural modeling framework are selection, extrusion, subdivision, curve shaping and stitching. In order to demonstrate the usefulness of the procedural modeling framework, human and furniture models are created using this procedural modeling environment. Various techniques are presented to generate these objects, and may be used to create a variety of other models. A detailed discussion of each technique is provided. Six experiments are conducted to test the support of the procedural modeling benets provided by this non- interactive modeling environment. The experiments test, namely parameterisation, re-usability, base-shape independence, model complexity, the generation of reproducible random numbers and caching. We prove that a number of distinct models can be generated from a single procedure through the use parameterisation. Modeling procedures and sub-procedures are re-usable and can be applied to different models. Procedures can be base-shape independent. The level of complexity of a model can be increased by repeatedly applying geometry to the model. The pseudo-random number generator is capable of generating reproducible random numbers. The caching facility reduces the time required to generate a model that uses repetitive geometry.

Applications using image-based illumination analysis are very limited in the current literature of computer graphics. However, there are potentially more applications based on such analysis and estimation. In this thesis, we show two applications in computer graphics that can be directly benefited from using such analysis and estimation: photo colorization and texture synthesis. / Illumination is a very common phenomenon. All the photographs that we casually take with cameras exhibit such phenomenon. Computer graphicists usually simulate the illumination cast on objects based on physical models. While directly rendering such effects has been intensively studied in the field of computer graphics, the inverse estimation of illumination contribution to each pixel in the digital photographs, which we call image-based illumination estimation, still remains a challenging problem. The lack of the underlying geometry as well as the light source and material properties usually makes such inverse estimation ill-posed and a very difficult problem to solve. / In this thesis, we target on such image-based illumination estimation problem. We will review the current state-of-the-art illumination estimation algorithms for solving intrinsic images, and demonstrate their benefits and drawbacks. While this is a fundamental research problem in the field of computer vision, we show that by decomposing the image into its intrinsic components, the reflectance and illumination, many graphical applications can potentially be explored and benefited. In the meantime, we will also introduce a new and novel algorithm to efficiently estimate the intrinsic components based on the statistics of the textured regions. The same algorithm can also be directly applied to non-textured regions in an image. / Texture synthesis is a very fundamental problem in computer graphics. Current texture synthesis method is difficult to automatically take into account the illumination and deformation during the synthesis. By exploring the statistics of the texture, we propose a very efficient algorithm to estimate both the illumination and deformation fields on textures. The color of the illuminant is also taken into account so that the recovered reflectance has consistent color. By decomposing the illumination and deformation fields, we show that many texture-based applications, such as the preparation of texture exemplars from real photographs, the natural replacement of textured regions, the relighting of objects, as well as the manipulation of geometries in natural images can be well achieved, with the success of texture synthesis guided by illumination and deformation. / Traditional example-based colorization of natural images usually suffers from illumination inconsistency. The color transfer from areas such as highlights and shadows may severely harm the colorization result. We propose to consider the illumination problem in colorization and perform colorization in an illumination-free domain. The decomposition of the intrinsic components from multiple example images, as well as the recombination and utilization of these intrinsic components in colorization, form the foundation of the proposed technique. Consistent colorization results are obtained even though the example images are from different lighting conditions and viewing directions. / Liu, Xiaopei. / Adviser: Wong Tien Tsin. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 76-83). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

In this thesis we study the isoperimetric problem on trees and graphs with bounded treewidth. Let G = (V,E) be a finite, simple and undirected graph. For let δ(S,G)= {(u,v) ε E : u ε S and v ε V – S }be the edge boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the edge isoperimetric value of G at I be defined as be(i,G)= mins v;|s|= i | δ(S,G)|. For S V, let φ(S,G) = {u ε V – S : ,such that be the vertex boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the vertex isoperimetric value of G at I be defined as bv(i,G)= The edge isoperimetric peak of G is defined as be(G) =. Similarly the vertex isoperimetric peak of G is defined as bv(G)= .The problem of determining a lower bound for the vertex isoperimetric peak in complete k-ary trees of depth d,Tdkwas recently considered in[32]. In the first part of this thesis we provide lower bounds for the edge and vertex isoperimetric peaks in complete k-ary trees which improve those in[32]. Our results are then generalized to arbitrary (rooted)trees. Let i be an integer where . For each i define the connected edge isoperimetric value and the connected vertex isoperimetric value of G at i as follows: is connected and is connected A meta-Fibonacci sequence is given by the reccurence a(n)= a(x1(n)+ a1′(n-1))+ a(x2(n)+ a2′(n -2)), where xi: Z+ → Z+ , i =1,2, is a linear function of n and ai′(j)= a(j) or ai′(j)= -a(j), for i=1,2. Sequences belonging to this class have been well studied but in general their properties remain intriguing. In the second part of the thesis we show an interesting connection between the problem of determining and certain meta-Fibonacci sequences. In the third part of the thesis we study the problem of determining be and bv algorithmically for certain special classes of graphs. Definition 0.1. A tree decomposition of a graph G = (V,E) is a pair where I is an index set, is a collection of subsets of V and T is a tree whose node set is I such that the following conditions are satisfied: (For mathematical equations pl see the pdf file)