Geometry processing has witnessed tremendous development in the last few decades. Starting from acquiring 3D data of real life objects, people have developed practical methods for polishing the raw data usually in the format of point clouds, reconstructing surfaces from the point clouds, cleaning up the surfaces by denoising or fairing, texturing the object surfaces by parametrization to 2D domain, deforming the objects realistically and in real time, and many other advanced tasks. Along with the notable methods is the sophistication of knowledge for working with discrete geometric data, in particular points, triangles, quadrangles and polygons for object representation, with a large body summarized and principled in the field known as discrete differential geometry. Meanwhile, geometric modeling has come to a new era: unlike the previous industrial practice of spline-based modeling where people tune control points to search for aesthetic shapes, now people want novel ways of interaction. For example, find unknown shapes that are usually characterized to have variational and physical properties of interest. Also user-friendly modeling methods like sketching have gained remarkable attention and advances. We note that many of these surface modeling problems could be regarded as asking for surfaces with special differential geometric properties. To be specific, people find surfaces of minimal area for modeling soap films that are balanced under surface tension; surfaces that if fabricated could stand firmly and are therefore important in real life architectural structures, are described by having homogeneous relative mean curvatures; even for surfaces filling up sketched 3D curves, the significant property of a good filling surface is that the curves follow principal curvature directions of the surface. This thesis presents our results in developing effective algorithms for modeling the above mentioned surfaces, by adapting knowledge and techniques in geometry processing, especially from computational and discrete differential geometry. In particular, we extend surface remeshing techniques to model high quality Constant Mean Curvature (CMC) surfaces that are models of soap films and bubbles, use power diagrams and the dual regular triangulations to parametrize and process self-supporting surfaces, and apply direction field modeling and discrete curvature adaptation to surfacing sketch curve networks. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

In this thesis it is demonstrated that the structure of rectilinear polygons can be exploited to solve a variety of geometric problems efficiently. These problems include: (1) recognizing polygonal properties, such as star-shapedness, monotonicity, and edge-visibility, (2) removing hidden lines, (3) constructing the rectilinear convex hull, (4) decomposing rectilinear polygons into simpler components, and (5) placing guards in rectilinear polygons. / A new tool for computational geometry is introduced which extracts information about the winding properties of rectilinear polygons. Employing this tool as a preprocessing step, efficient and conceptually clear algorithms for the above problems have been designed.

No description available.

No description available.

No description available.

Qin, Guiming. / "August 2010." / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (p. 72-74). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.5 / Chapter 1.1 --- B splines and B-splines surfaces --- p.5 / Chapter 1. 2 --- Box spline --- p.6 / Chapter 1. 3 --- Biorthogonal subdivision wavelets based on the lifting scheme --- p.7 / Chapter 1.4 --- Geometrically-constrained subdivision wavelets --- p.9 / Chapter 1.5 --- Contributions --- p.9 / Chapter 2 --- Explicit symbol formulae for B-splines --- p.11 / Chapter 2. 1 --- Explicit formula for a general recursion scheme --- p.11 / Chapter 2. 2 --- Explicit formulae for de Boor algorithms of B-spline curves and their derivatives --- p.14 / Chapter 2.2.1 --- Explicit computation of de Boor Algorithm for Computing B-Spline Curves --- p.14 / Chapter 2.2.2 --- Explicit computation of Derivatives of B-Spline Curves --- p.15 / Chapter 2. 3 --- Explicit power-basis matrix fomula for non-uniform B-spline curves --- p.17 / Chapter 3 --- Biorthogonal subdivision wavelets with geometric constraints --- p.23 / Chapter 3. 1 --- Primal subdivision and dual subdivision --- p.23 / Chapter 3. 2 --- Biorthogonal Loop-subdivision-based wavelets with geometric constraints for triangular meshes --- p.24 / Chapter 3.2.1 --- Loop subdivision surfaces and exact evaluation --- p.24 / Chapter 3.2.2 --- Lifting-based Loop subdivision wavelets --- p.24 / Chapter 3.2.3 --- Biorthogonal Loop-subdivision wavelets with geometric constraints --- p.26 / Chapter 3. 3 --- Biorthogonal subdivision wavelets with geometric constraints for quadrilateral meshes --- p.35 / Chapter 3.3.1 --- Catmull-Clark subdivision and Doo-Sabin subdivision surfaces --- p.35 / Chapter 3.3.1.1 --- Catmull-Clark subdivision --- p.36 / Chapter 3.3.1.2 --- Doo-Sabin subdivision --- p.37 / Chapter 3.3.2 --- Biorthogonal subdivision wavelets with geometric constraints for quadrilateral meshes --- p.38 / Chapter 3.3.2.1 --- Biorthogonal Doo-Sabin subdivision wavelets with geometric constraints --- p.38 / Chapter 3.3.2.2 --- Biorthogonal Catmull-Clark subdivision wavelets with geometric constraints --- p.44 / Chapter 4 --- Experiments and results --- p.49 / Chapter 5 --- Conclusions and future work --- p.60 / Appendix A --- p.62 / Appendix B --- p.67 / Appendix C --- p.69 / Appendix D --- p.71 / References --- p.72

published_or_final_version / abstract / toc / Computer Science and Information Systems / Master / Master of Philosophy

In this thesis it is shown that several pattern recognition problems can be solved efficiently by exploiting the geometrical structure of the problems. The problems considered are in the area of clustering and classification. These problems are: (i) computing the diameter of a finite planar set, (ii) computing the maximum and minimum distance between two finite planar sets of points, (iii) testing for point inclusion in a convex polyhedron in d-dimensional space, and (iv) exact and inexact reference set thinning for the nearest neighbor decision rule. / Algorithms to solve the above problems are presented and analyzed for worst-case and average-case situations. These algorithms are implemented and experimentally compared with the existing algorithms. / In solving the above problems, a geometrical construct, known as the Voronoi diagram is used extensively. However, there exists no practical algorithm to construct the Voronoi diagram in d dimensional spaces when d > 2. In this thesis an efficient algorithm to construct the Voronoi diagram in d-space is presented.

Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

No description available.