Nigolian, Valentin Zénon (2024). Robust Tetrahedral Maps — The Shrink-and-Expand Framework. (Thesis). Universität Bern, Bern

Preview

Text 24nigolian_v.pdf - Thesis Available under License Creative Commons: Attribution-Share Alike (CC-BY-SA 4.0). Download (106MB) | Preview

Abstract

Digital geometry is an essential aspect of numerous modern technical practices, including numerical simulation, medical visualization or computer-aided design (CAD). Meshes, digital discretizations of shapes and objects, are often at the core of these practices, leveraging the power of modern computational machinery to approximate reality. A ubiquitous problem related to meshes is to transform or map these meshes into different shapes and objects. While this has been studied for decades, yielding powerful and robust solutions for surface meshes, reaching the same level of robustness for volumetric meshes remains an open problem. As it happens, among the numerous and various research directions leading to meaningful results for surfaces, all of them lose their theoretical guarantees when translated to the volumetric setting. Specifically, one property that is essential to most map-related applications is that of bijectivity, the ability to make one-to-one relations between objects or spaces, through these maps. This lack of guarantees can ultimately lead to considerable human manual effort from users of map-related techniques, particularly for numerical simulations through the so-called finite element method (FEM). In this thesis, we thus focus on developing methods where bijectivity is paramount, pushing forward the capabilities of volumetric maps, specifically tetrahedral maps. We discuss the main obstacles on the road to robustness, and how they impact related state-of-the-art methods. In a venture to take a first step towards our goal, we take inspiration from a 2D method called “progressive embeddings” and put great effort into making it compatible to the 3D realm. This results in the main contribution of this thesis, the Shrink-and-Expand framework, whose key feature is robustness, through a novel approach relying on a sequence of operations that generate maps in a step-by-step manner. These steps, called expansions, consist in finding sets of tetrahedra whose map image positions can be computed, in a way that guarantees not to invalidate the image positions of previously expanded tetrahedra. As a result, these expansions guarantee to monotonically reach closer to a complete bijective map. Whether or not such a map can ultimately be generated depends on a set of concrete choices for the modular components of Shrink-and-Expand, including how to pick elements for expansion. The second contribution of this thesis is thus the design and implementation of two different sets of modulars components, i.e. realizations of Shrink-and-Expand (SaE). The first realization verifies the practical feasibility of SaE. It provides a working example that experimentally proved to be better than the state of the art in terms of its ability to generate bijective maps, particularly for difficult cases. However, its shortcomings include a limited applicability to real-world situations due to its overall suboptimal runtime performance, as well as lacking theoretical guarantees of success for all inputs. The second realization, however, introduces a simplified way of picking tetrahedra for expansion, yielding provable guarantees of success for a class of inputs fitting the vast majority of meshes. It is also shown to generate better results than the state of the art, even surpassing the performance of the first realization, to a point where it becomes of actual practical use for end-users. The overall contribution of this thesis is hence to push the boundaries of the state of art regarding tetrahedral bijective maps, opening the door to a whole new range of techniques, with robustness at their core.

Item Type:	Thesis
Dissertation Type:	Cumulative
Date of Defense:	18 November 2024
Subjects:	000 Computer science, knowledge & systems 500 Science > 510 Mathematics 600 Technology > 620 Engineering
Institute / Center:	08 Faculty of Science > Institute of Computer Science (INF)
Depositing User:	Sarah Stalder
Date Deposited:	28 Jan 2025 14:53
Last Modified:	28 Jan 2025 14:53
URI:	https://boristheses.unibe.ch/id/eprint/5771

Actions (login required)

View Item