published_or_final_version / abstract / toc / Statistics / Doctoral / Doctor of Philosophy

Thesis (Ph. D.)--University of Hong Kong, 1997. / Includes bibliographical references (leaf 195-203).

Cette thèse traite du problème de la tessellation volumétrique à partir des formes en trois dimensions, c’est-à-dire, étant donné une forme tridimensionnelle qui est habituellement représentée par sa surface au bord, comment subdiviser l’intérieur de la surface en formes plus petites, appelées cellules, de manière optimale selon plusieurs critères concernant l’exactitude, l’uniformité et la régularité. Nous considérons la tessellation de Voronoi centroidale qui est une approche efficace pour construire des tessellations volumétriques uniformes et régulières.Une tessellation de Voronoi centroidale (CVT) d’une forme peut être considérée comme une subdivision optimale avec les cellules dont les centres de masse, appelés centroides, sont répartis de manière optimale l’intérieur de la forme. CVTs ont été largement utilisés dans la vision par ordinateur et l’infographie en raison de leurs propriétés d’uniformité et de régularité qui sont indépendantes des variations de la forme. Cependant, les problèmes tels que comment évaluer la régularité d’une CVT et comment construire une CVT à partir des formes de types différents restent un défi.Nous proposons, comme contribution de cette thèse, que des critères de régularité basés sur des moments de second ordre normalisés des cellules. Ces critères de régularité permettent d’évaluer les tessellations volumétriques, et surtout, de comparer la régularité des différents CVTs sans l’hypothèse que leur forme et leur nombre de sites devraient être les mêmes. Nous proposons également une approche hiérarchique basée sur un schéma de subdivision qui préserve la régularité des cellules et l’optimalité locale des CVTs. Les résultats expérimentaux montrent que notre approche construit de manière plus efficace des CVTs plus régulières que les méthodes de l’état de l’art selon les critères de régularité.Une autre contribution est un nouvel algorithme de CVT pour les formes implicites et une comparaison approfondie entre l’algorithme Marching Cubes (MC), le raffinement de Delaunay et notre algorithme. L’idée clé de notre algorithme est l’utilisation des enveloppes convexes et l’amélioration locale pour construire des cellules au bord précises. Nous présentons une comparaison des trois algorithmes avec des critères différents, y compris la précision, la régularité et la complexité sur un grand nombre de données variantes. Les résultats montrent que MC est le plus rapide et que le notre construit les tessellations volumétriques les plus précises et les plus régulières.Nous explorons aussi les applications comme, par exemple, un framework d’animation des formes basées sur CVTs qui génère des animations plausibles avec une réelle dynamique. Le code source de l’ensemble des travaux de cette thèse est disponible en ligne dans le but de la recherche future. / This thesis addresses the problem of volumetric tessellations from three-dimensional shapes, i.e., given a three-dimensional shape that is usually represented by its boundary surface, how to optimally subdivide the interior of the surface into smaller shapes, called cells, according to several criteria concerning accuracy, uniformity and regularity. We consider centroidal Voronoi tessellation that is an effective approach for building uniform and regular volumetric tessellations.A centroidal Voronoi tessellation (CVT) of a shape can be viewed as an optimal subdivision with the cells whose centers of mass, called centroids, are optimally distributed inside the shape. CVTs have been widely used in computer vision and graphics because of their properties of uniformity and regularity that are immune to shape variations. However, the problems such as how to evaluate the regularity of a CVT and how to build a CVT from different types of shapes remain a challenge.One contribution of this thesis is that we propose regularity criteria based on the normalized second order moments of the cells. These regularity criteria allow evaluating volumetric tessellations and specially comparing the regularity of different CVTs without the assumption that their shape and number of sites should be the same. Meanwhile, we propose a hierarchical approach based on a subdivision scheme that preserves cell regularity and the local optimality of CVTs. Experimental results show that our approach performs more efficiently and builds more regular CVTs according to the regularity criteria than state-of-the-art methods.Another contribution is a novel CVT algorithm for implicit shapes and an extensive comparison of Marching Cubes, Delaunay refinement and our algorithm. The key of our algorithm is using convex hulls and the local improvement to build accurate boundary cells. We present a comparison of these three algorithms with different criteria including accuracy, regularity and complexity on a large number of variant data. The results show that Marching Cubes is the fastest one and our algorithm build more accurate and regular volumetric tessellations than the others.We also explore the applications such as a shape animation framework based on CVTs that generates plausible animations with real dynamics. And the source code of the whole work of this thesis is available online for the purpose of further research.

Orientadores: Anamaria Gomide, Célia Picinin de Mello / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T15:07:47Z (GMT). No. of bitstreams: 1 Oliveira_JoseFranciscoMota_M.pdf: 3677730 bytes, checksum: 129632445eb36d832a0edf0b95144ac7 (MD5) Previous issue date: 2015 / Resumo: Neste trabalho realizamos um estudo sistemático de algumas pavimentações no plano com polígonos regulares congruentes e não congruentes, propiciando subsídios para o professor que tenha interesse em desenvolvê-lo em sala de aula. Algumas atividades foram sugeridas para serem realizadas inicialmente de forma lúdica e posteriormente objetivando a formalização de alguns conceitos teóricos / Abstract: This work was based on an axiomatic study of some tessellation in the plane with both congruent regular polygons and non-congruent ones providing it for the teachers that are interested in developing it during their classroom. Some activities were suggested to be inicially carried out as an entertaining way and afterwards having as priority the formalization of some theoretical concepts / Mestrado / Matemática em Rede Nacional / Mestre em Matemática em Rede Nacional

The solution for the edge-isoperimetric problem (EIP) of the square tessellation of plane is investigated and solved. Summaries of the stabilization theory and previous research dealing with the EIP are stated. These techniques enable us to solve the EIP of the cubical tessellation.

In this thesis, we will present examples of Voronoi diagrams that are not tessellations. Moreover, we will find sufficient conditions on subspaces of E2, S2 and the Poincaré disk and the sets of sites that guarantee that the Voronoi diagrams are pre-triangulations. We will also study g-spaces, which are metric spaces with ‘extendable’ geodesics joining any 2 points and give properties for a set of sites in a g-space that again guarantees that the Voronoi diagram is a pre-triangulation.

In this thesis, we will present examples of Voronoi diagrams that are not tessellations. Moreover, we will find sufficient conditions on subspaces of E2, S2 and the Poincaré disk and the sets of sites that guarantee that the Voronoi diagrams are pre-triangulations. We will also study g-spaces, which are metric spaces with ‘extendable’ geodesics joining any 2 points and give properties for a set of sites in a g-space that again guarantees that the Voronoi diagram is a pre-triangulation.

In this thesis, we will present examples of Voronoi diagrams that are not tessellations. Moreover, we will find sufficient conditions on subspaces of E2, S2 and the Poincaré disk and the sets of sites that guarantee that the Voronoi diagrams are pre-triangulations. We will also study g-spaces, which are metric spaces with ‘extendable’ geodesics joining any 2 points and give properties for a set of sites in a g-space that again guarantees that the Voronoi diagram is a pre-triangulation.

In this thesis, we will present examples of Voronoi diagrams that are not tessellations. Moreover, we will find sufficient conditions on subspaces of E2, S2 and the Poincaré disk and the sets of sites that guarantee that the Voronoi diagrams are pre-triangulations. We will also study g-spaces, which are metric spaces with ‘extendable’ geodesics joining any 2 points and give properties for a set of sites in a g-space that again guarantees that the Voronoi diagram is a pre-triangulation.

Applying engineering principles to tessellation origami-based designs enables the control of certain design properties, such as flexibility, bending stiffness, mechanical advantage, shape conformance, and deployment motion. The ability to control these and other properties will enable augmented design capabilities in environments which currently limit the design to specific materials, including space, medicine, harsh environments, and scaled environments (such as MEMS applications). Other applications will be able to achieve more complex motions or better satisfy design and performance requirements.This research demonstrates augmented design capabilities of origami tessellations in engineering design in rigid-foldable and non-rigid-foldable applications. First, a method to determine Poisson's ratio and mechanical advantage for deployable, rigid-foldable tessellations is presented. The results enable the selection and tailoring of patterns based on deployment motion of specific patterns.Secondly, a model that predicts the deployment stability of the non-rigid-foldable triangulated cylinder is presented. This model defines the geometry needed to obtain a maximum deployed height, always return to a closed position, or remain in either the open or closed configurations. The Stability Transition Ratio is the ratio of the inner to outer diameter that marks the point between monostable and bistable behavior in a triangulated cylinder and is dependent only on the number of sides.Lastly, this work presents methods to reduce sag in adult diapers by increasing shape conformance, promoting wicking capabilities, and improving the structure through the implementation of origami tessellations. Several basic fold patterns were evaluated and the results reported. Reducing sag increases comfort and decreases leaking.