Netidee Blog Bild
CADMeshConverter – Reduktionsalgorithmen (03/2019)
Anforderungsanalyse (27.03.2019)
Förderjahr 2018 / Project Call #13 / ProjektID: 3511 / Projekt: CADMeshConverter

Evaluierung

Es wurden fünf unterschiedliche CAD Modelle mit denselben Algorithmen und denselben Parametern (Zielgrößen relativ zur Ausgangsgröße) reduziert. Die reduzierten Modelle wurden sowohl optisch als auch rechnerisch auf ihre Qualität hin evaluiert.

Optische Kontrolle

Die Modelle wurden optisch auf diverse Fehler wie etwa Spitzenbildung oder entstandene Löcher überprüft. Dadurch konnten in einem ersten Schritt grobe Abweichungen nach der Konvertierung zwischen Original und konvertiertem Modell festgestellt werden.

Spitzenbildung
Spitzen

 

Rechnerische Kontrolle

Hausdorff Distanz visualisiert.
Hausdorff Distanz visualisiert. Rot = niedrige HD, Blau = hohe HD*

Bei der rechnerischen Evaluierung wurde die Hausdorff Distanz aller Punkte des reduzierten Modells zum Orginalmodell berechnet. Für jede durchgeführte Reduktion wurden folgende Werte berücksichtigt:

  • Der Durchschnitt aller Hausdorff Distanzen pro Modell
  • Die maximale Hausdorf Distanz: Die größte Distanz eines Punkts des reduzierten Modells zum Originalmodell.

Der Durchschnitt der Distanzen gibt an, wie ähnlich sich die beiden Modelle prinzipiell sind. Die maximale Hausdorff Distanz kann, sofern der Wert im Vergleich zum Durchschnitt sehr hoch ist, auf Fehler wie Spikes oder generell auf eine gröbere Abweichung hinweisen.

Die Hausdorff Distanz ermöglich zwar eine Beurteilung der Reduktionsqualität anhand numerischer Werte, da sie jedoch nur für (maximal) alle Punkte des reduzierten Modells berechnet werden kann, gibt sie keinen Hinweis auf eventuell vorhandene optische Probleme (Löcher, etc.).

Original links, Hidden Removal mit Löchern
Links Original, Rechts ein mit Hidden Removal reduziertes Model mit dadurch entstandenen Löchern. Rechts: Hausdorff Distanz = 0,000*

Ein ideales Beispiel für dieses Problem ist beispielsweise die Reduktion über Hidden Removal. Diese Reduktionsart hat im Normalfall nur eine sehr kleine Hausdorff Distanz, es können jedoch sehr leicht Löcher im Modell entstehen.

Da der CADMeshConverter möglichst gute Ergebnisse für unterschiedlichste CAD Modelle liefern soll, wurden für jeden Algorithmus die Durchschnittswerte von allen damit durchgeführten Reduktionen berechnet und verwendet.

Algorithmen

Quadric Edge Collapse Decimation

Dieser Algorithmus basiert auf der Durchführung von Kantenkontraktionen.

Kantenkontraktion
Kantenkontraktion. Author: Claudio Rocchini, Lizenz: CC BY 2.5, Quelle: Wikipedia

 

Bei einer solchen Kontraktion wird eine Kante des zu reduzierenden Meshes entfernt, und die beiden übrigbleibenden Knoten werden zusammengelegt.

Nach der Festlegung der gewünschten Zielgröße wird für jede mögliche Kontraktion berechnet, wie groß die Auswirkung der Kontraktion auf das Erscheinungsbild des Meshes wäre (Fehlerquadrik). Schließlich werden, bis zum Erreichen der Zielgröße, die Kontraktionen mit den kleinsten Fehlerquadriken durchgeführt.

Verwendbarkeit

In der Evaluierung hat sich gezeigt, dass eine Reduktion um 80% in der Regel problemlos möglich ist. Auch eine weitere Reduktion ist mit Abstrichen bei der Qualität möglich. Bei manchen Modellen waren sogar Reduktionen bis 98% brauchbar.

links: Original, rechts: 50% Reduziert
v.l.n.r: Original, 50% Reduziert*

 

Hidden Removal

Ein CAD Modell umfasst meistens nicht nur die äußere Erscheinung, sondern auch die innere Konstruktion, also wie etwas aufgebaut ist. Diese Information ist jedoch sehr oft für MR Anwendungen nicht notwendig. In solchen Fällen bietet es sich an, dass „Innenleben“ eines Modells zu entfernen.

Meshlab verfügt über keinen dedizierten Algorithmus für Hidden Removal, es ist jedoch trotzdem möglich diese Funktion anzuwenden.

Dafür wird zuerst die Umgebungsverdeckung für das Modell berechnet. Anschließend werden die Punkte mit der höchsten Verdeckung ausgewählt und entfernt.

Das Problem bei dieser Vorgehensweise ist jedoch, dass die Grenzwerte für die Auswahl der Punkte manuell für jedes Modell festzulegen sind. Bei einer ungeeigneten Festlegung des Grenzwerts, kann es dazu kommen, dass auch sichtbare Bereiche des Modells entfernt werden.

Probleme bei Hidden Removal
links: Umgebungsverdeckung, rechts: Problematische Bereiche in Rot*

 

Verwendbarkeit

Die Evaluierung hat gezeigt, dass die Qualität von Hidden Removal sehr stark vom Ausgangsmodell und vom Anwendungszweck abhängig ist. Einige Modelle waren nach der Anwendung dieser Funktion unbrauchbar, andere wiederum konnten bis zu 99% ohne, von „außen“ erkennbaren Qualitätsverlust, reduziert werden. Aufgrund der instabilen Ergebnisse, ist es geplant, diese Funktion nicht vom CADMeshConverter zu unterstützen.

 

Clustering Decimation

Dieser Algorithmus basiert auf einer Methode namens „Vertex Clustering“. Bei dieser Methode, wird der Bereich rund um ein Modell (meist begrenzt durch dessen Bounding Box) in Cluster eingeteilt.

Boundingbox
Boundingbox*

Für jeden dieser Cluster wird ein repräsentativer Vertex ausgewählt. Falls in einer Zelle mehrere Vertices vorkommen, werden alle auf die Position des repräsentativen umgelegt.

Durch diese Art der Reduzierung kann ein Mesh fehlerhaft werden, da eine Oberfläche in einen Punkt kollabieren kann.

Verwendbarkeit

Die Evaluierung hat ergeben, dass diese Art der Reduzierung meist nur für Modelle brauchbar ist, welche eher im Hintergrund einer 3D Szene verwendet werden.

Original vs Clustering Decimation
links: Originalmodell, rechts: Reduziert mit Clustering Decimation*

Fazit

Ergebnisdiagramm der Evaluierung
Niedriger ist besser

Die rechnerische Evaluierung in Kombination mit der optischen Kontrolle hat ergeben, dass die Reduktion mittels Quadric Edge Collapse Algorithmus die besten Resultate geliefert hat.

Die Reduktion über Hidden Removal bringt nicht nur einige Probleme mit sich, sondern es ist auch die erreichbare Reduktion in einem sehr großen Maß vom jeweiligen Modell abhängig.

Die Clustering Decimation kann nicht nur bei der Qualität, sondern auch bei der Performance nicht mit dem Quadric Edge Collapse Algorithmus mithalten.

 

* Das verwendete Modell ist der Affenkopf "Suzanne" von Blender. 

 

CAPTCHA
Diese Frage dient der Überprüfung, ob Sie ein menschlicher Besucher sind und um automatisierten SPAM zu verhindern.