4 Der implementierte Algorithmus
4.1 Generierung eines Höhenfelds
Da die Maschenweite bei dem oben beschriebenen Verfahren zur regulären Triangulierung
einheitlich gewählt ist, entsteht dadurch der grundlegende Nachteil, dass in allen Bereichen des
Gitters gleich viele Dreiecke sind, auch dort, wo sie nicht vonnöten sind.
Einen Vorteil des Verfahrens, den man sich aber zunutze machen kann, besteht darin, dass man
durch dieses Verfahren sehr leicht ein geordnetes Höhenfeld erhält, indem man nacheinander die
Höhenwerte der Vertices des Gitters in einem Array abspeichert.
In einem solchen Höhenfeld werden nur Höhenwerte gespeichert, das heißt, die zweidimensionalen
Positionen der Werte ergeben sich implizit. Deshalb eignet sich beispielsweise ein dynamisches
float-Array zur Speicherung dieses Felds, welches im Vergleich zur Speicherung aller drei
Raumkoordinaten nur etwa ein Drittel des Speicherbedarfs benötigt. Die einzigen noch
notwendigen Parameter sind, der fest gewählte Abstand der Punkte und die Dimensionen (Länge
und Breite) des Felds.
4.1.1 Erfassen der Höhenwerte
Um an einer beliebigen Position innerhalb des Höhenfelds, auch zwischen den Gitterpunkten,
Zugriff auf die Höhenwerte zu erhalten, ist es notwendig, den jeweils nächstgelegenen Höhenwert
des Gitters zu erfassen. Man könnte an dieser Stelle auch mehrere Nachbarpunkte einbeziehen und
zwischen ihnen interpolieren, was exaktere Resultate liefern würde. Aufgrund des erhöhten
Rechenaufwands wurde zunächst aber darauf verzichtet.
Für die Erfassung des nächstgelegenen Höhenwerts werden die 3D-Raumkoordinaten des Punktes
in einen Index des Höhenfelds umgerechnet.
14
Abbildung 10: Ausgangsdatensatz - Punktwolke
eines Arkadenbogens in Kompass-Farben,
gewonnen durch 3D-Laserscans.
Abbildung 11: Gewonnenes Höhenfeld aus dem
Datensatz, bei einer Maschenweite (=Gitter-
punktabstand) von 4 cm.