Volume Data Generation from Triangle Meshes Using the Signed Distance Function

This work deals with the creation of volumetric data from triangle meshes. Volumetric data is used to represent the results of CT scans (computed tomography). This representation uses density values at discrete, regular grid points. Volumetric data can also be generated from different sources. The idea behind this work is to create volumetric data with the signed distance function from triangle meshes. From every point on the grid the distance as well as a relation if the point is inside or outside the mesh (the sign) is measured. This process creates a signed distance field (or SDF for short), which is a preprocessing result of the volumetric data. This work evaluates different techniques to create the signed distance field. First of all the distance calculation from a point to a triangle is examined. This distance calculation can be done in two and three dimensions. The more efficient method in two dimensions requires the problem to be translated to 2D-coordinates with a translation and a rotation. This is followed by a case analysis to find the closest feature of the triangle (a vertex, an edge or the face of the triangle). Because the calculation of the euclidean distance is expensive in terms of processing power, optimizations and heuristics for calculating complete SDFs are presented. In particular the so-called distance transforms are discussed, which propagate a quasi-euclidean distance from the zero-surface of the volume data with masks (or templates). Chamfer distance transforms work with masks that contain simple distance values. Vector distance transforms instead use vectors in the mask components to obtain more precise results. The evaluated techniques are compared to each other regarding their quality with respect to the error. Then a program for the creation of volumetric data is presented. This program was created as a result of surveying calculation techniques for SDFs and volumetric data and is the main contribution of this work. The program is able to create volumetric data in user-defined size and precision with different algorithms to choose from (Brute Force, CDTs, VCVDT, EVDT). Diese Arbeit beschäftigt sich mit der Erstellung von Volumendaten aus Dreiecksmodellen. Volumendaten werden z.B. für die Repräsentation von Ergebnissen des CT-Scans (Computertomographie) verwendet, bei der Dichtewerte auf einem diskreten, regulären Gitter einer bestimmten Größe gespeichert werden. Volumendaten können auch aus anderen Quellen generiert werden. Die Idee hinter dieser Arbeit ist es, Volumendaten mit Hilfe einer vorzeichenbehafteten Abstandsfunktion (signed distance function) aus Dreiecksmodellen zu generieren. Von jedem Element des Gitters wird sowohl der kürzeste Abstand zum Modell als auch eine Relation, ob sich das Gitterelement innerhalb oder außerhalb des Modells befindet, gemessen. Dieser Prozess dient der Erstellung eines vorzeichenbehafteten Abstandsfeldes (signed distance field, SDF), welches ein Vorverarbeitungsschritt bei der Erstellung von Volumendaten ist. Die Arbeit untersucht verschiedene Techniken, die zur Erstellung eines SDF verwendet werden können. Zunächst wird die Abstandsberechnung von einem Punkt zu einem Dreieck untersucht. Diese Abstandsberechnung kann entweder im zwei- oder im dreidimensionalen stattfinden. Die effizientere Methode im zweidimensionalen erfordert eine Transformation des Problems (eine Translation und Rotation) in 2D-Koordinaten, anschließend wird das nähste Feature des Dreiecks (Eckpunkt, Kante oder Dreiecksfläche) ermittelt. Da die Berechnung der euklidischen Distanz zeitintensiv ist, werden Optimierungen und Heuristiken zur Berechnung des vollständigen SDF vorgestellt. Insbesondere wird hierbei auf die sogenannten Distance Transforms (DTs) eingegangen, welche mit Hilfe von Masken eine Schätzung der euklidischen Distanz von der Null-Oberfläche propagieren. Die Arbeit geht genauer auf Chamfer DTs und Vector DTs ein. Chamfer DTs arbeiten mit Masken, die einfache Abstandsinformationen beinhalten. Vector DTs hingegen verwenden Vektoren in den Masken, um präzisere Ergebnisse zu erreichen. Die untersuchten Techniken werden gegenüber gestellt und anhand der resultierenden Datensätze bezüglich Qualität (Fehlermessung) verglichen. Anschließend wird ein Programm zur Erstellung von Volumendaten aus Dreiecksmodellen vorgestellt, dass während der Arbeit zur Implementierung der Techniken entstanden ist, und den wesentlichen Beitrag der Arbeit darstellt. Das Programm erlaubt die Erstellung von Volumendaten in benutzerspezifizierter Auflösung und Genauigkeit unter Verwendung verschiedener Algorithmen (Brute Force, CDTs, VCVDT, EVDT)