www.wikidata.de-de.nina.az

Polygonnetz Untereinander mit Kanten verbundene Punkte bilden in der Computergrafik ein das die Gestalt eines Polyeders

Polygonnetz

Untereinander mit Kanten verbundene Punkte bilden in der Computergrafik ein Polygonnetz, das die Gestalt eines Polyeders definiert. Dreiecksnetze und Vierecksnetze sind hier am geläufigsten. Zur Speicherung von Polygonnetzen und Polygonen gibt es eine Reihe bekannter Datenstrukturen. Die bekanntesten Strukturen sind die Knotenliste, Kantenliste, Winged Edge und die doppelt verkettete Kantenliste (doubly connected halfedge list).

Unterschiedliche Drahtgittermodelle, die einfachste Möglichkeit, ein Polygonnetz darzustellen.

Jeder Knoten muss mindestens eine Verbindung zum Restnetz haben, um Mitglied des Netzes zu sein. Daraus folgt, dass jeder Knoten von jedem anderen im Netz erreichbar ist. In der Graphentheorie sind Polygonnetze als ungerichtete Graphen ohne Mehrfachkanten darstellbar.

Eigenschaften von Polygonnetzen Bearbeiten

Das Bild zeigt typische Netzeigenschaften an verschiedenen Polygonnetzen: a) Zeigt ein Polygonnetz ohne besondere Eigenschaften, b) ein strukturiertes Polygonnetz, c) zeigt ein Polygonnetz, das strukturiert und regulär ist, und d) ist strukturiert, regulär und orthogonal.

Folgende Eigenschaften kann ein Netz haben, keine davon ist allerdings für ein Polygonnetz erforderlich:

  • Strukturiertheit: Ein Polygonnetz wird als strukturiert bezeichnet, wenn jeder innere Punkt die gleiche Anzahl anliegender Kanten und Flächen hat.
  • Regularität: Ein Polygonnetz ist regulär, wenn die Kantenlängen in jede Richtung konstant sind. Diese Eigenschaft baut auf der Strukturiertheit auf.
  • Orthogonalität: Ein Polygonnetz wird als orthogonal bezeichnet, wenn die Netzkanten rechte Winkel bilden. Die Orthogonalität baut auf die Eigenschaft der Strukturiertheit und der Regularität auf.

Polygonnetz als Dreiecksnetz Bearbeiten

Das Polygonnetz als Dreiecksnetz ist eine weit verbreitete Form des Polygonnetzes. Es ist vor allem bei Triangulationen und beim Meshing von Bedeutung.

(TIN)

Datenstrukturen Bearbeiten

Einfache Datenstrukturen Bearbeiten

Knotenliste Bearbeiten

Bei der Knotenliste werden die Punkte in einer separaten Punktliste abgelegt. Eine Fläche wird dann als eine Liste von Zeigern auf die Punkte in dieser Liste definiert. Dadurch wird eine Trennung zwischen der Geometrie (den Koordinaten der Knoten) und der Topologie (welche Knoten verbinden welche Kanten, welche Kanten begrenzen welche Flächen) realisiert.

Kantenliste Bearbeiten

Die Nachteile der Knotenliste werden bei der Kantenliste dadurch umgangen, dass alle Kanten in einer separaten Liste gespeichert werden. Facetten werden hier als Zeiger auf die Kantenliste definiert. Neben dem Anfangs- und Endpunkt werden auch die maximal zwei zugehörigen Facetten für jede Kante abgelegt. Die Reihenfolge der Angabe der Eckpunkte für Kanten legt eine Orientierung fest und bestimmt bei Facetten, wo innen und wo außen ist.

Vor- bzw. Nachteile Bearbeiten

Datenstruktur Vorteile Nachteile
Knotenliste
  • Trennung von Geometrie und Topologie
  • minimale Redundanzen (Punkte werden nur einmal abgelegt)
  • Kanten werden mehrmals durchlaufen und ausgegeben
  • Suche nach zu Kanten gehörenden Facetten nicht effizient möglich (nur mit erschöpfender Suche möglich) Für alle Kanten in F1 (jedes Knotenpaar) suchen wir in allen weiteren Facetten, ob sie enthalten ist, wenn nein, dann Randkante
  • Suchen nach Facetten, welche eine Kante bzw. Ecke enthalten, ist ineffizient
Kantenliste
  • Trennung von Geometrie und Topologie
  • Schnelle Bestimmung von Randkanten (Kanten mit nur einem Verweis auf Facette)
  • Suchen nach Facetten, welche eine Kante bzw. Ecke enthalten, ist ineffizient

Generell gilt für Knoten- und Kantenlisten, dass die Suche ausgehend von einer Facette nach untergeordneten Objekten wie Kanten und Knoten sehr effizient durchführbar ist. In umgekehrter Richtung verhält es sich jedoch gegenteilig. So ist z. B. die Suche nach allen Facetten, welche eine bestimmte Ecke enthalten, immer noch nur durch eine erschöpfende Suche möglich.

Komplexere Datenstrukturen Bearbeiten

Winged Edge nach Baumgart Bearbeiten

Eine Datenstruktur, mit deren Hilfe sehr viele Abfragen effizient bearbeitet werden können, ist die Winged-Edge-Darstellung nach Baumgart. Zusätzlich zu den Informationen der Kantenliste werden hier noch Zeiger auf die Kanten abgelegt, die von Anfangs- und Endpunkt der aktuellen Kante abgehen. Aufgrund der Orientierung wird jede Kante einmal positiv (im Uhrzeigersinn) und einmal negativ (gegen den Uhrzeigersinn) durchlaufen.

Mit der Winged-Edge-Datenstruktur ist es möglich, in konstanter Zeit abzufragen, welche Knoten oder Facetten zu einer gegebenen Kante gehören. Hat eine Facette k Kanten, können in linearer Zeit diese Kanten nacheinander abgesucht werden (nur bei polygonalen Netzen ohne Änderung der Durchlaufrichtung eines Polygons). Andere Anfragen, insbesondere solche ausgehend von einer Ecke, die nach den Kanten oder Facetten, in denen diese Ecke enthalten ist, suchen, sind deutlich langsamer.

Doppelt verkettete Kantenliste (Half Edge) Bearbeiten

Die Half-Edge-Datenstruktur ist ein wenig ausgereifter als die Winged-Edge-Liste. Sie erlaubt, die meisten in der folgenden Tabelle aufgeführten Operationen in konstanter Zeit auszuführen, d. h. konstanter Zeit pro gesammelte Information. Wenn man z. B. alle zu einem Eckpunkt benachbarten Kanten herausfinden will, ist die Operation linear bezüglich der Anzahl der benachbarten Kanten aber konstant in der Zeit pro Kante. Half Edge funktioniert nur mit zweidimensionaler Mannigfaltigkeit, d. h. jede Kante ist von genau zwei Facetten (zu jeder Halbkante gibt es eine entgegengesetzte Halbkante) umgeben, d. h. T-Verbindungen, innere Polygone und Brüche sind nicht erlaubt.

Bei der Half-Edge-Struktur werden nicht Kanten, sondern Halbkanten abgelegt. Halbkanten sind gerichtet und zwei zusammengehörende Halbkanten (Paar) bilden eine Kante und zeigen in die entgegengesetzte Richtung.

Eine weitere Datenstruktur ist die Doubly-connected edge list (DCEL).

Laufzeitvergleich Bearbeiten

Folgende Tabelle zeigt einen Vergleich der asymptotischen Laufzeit in Abhängigkeit von den vorhandenen Elementen Knoten, Kanten und Flächen. Es gibt neun mögliche Abfragen auf die Struktur, nämlich „welche Ecke, Kante oder Fläche gehört zu welcher Ecke Kante oder Fläche“. Alle Abfragen bis auf diejenige nach den benachbarten Ecken einer gegebenen Ecke werden in der Tabelle aufgeführt. Der Vergleich zeigt, wie unterschiedlich gut die Datenstrukturen die Anfrageklassen bearbeiten.

Suchanfrage (gegeben → gesucht) Knotenliste Kantenliste Winged Edge Half Edge
Kante → Eckpunkte N/A
Kante → Facetten N/A
Kante → angrenzende Kanten N/A
Eckpunkt → Kanten
Eckpunkt → Facetten
Facette → Kanten
Facette → Eckpunkte
Facette → benachbarte Facette

Hierbei bezeichnet:

  • : Anzahl aller Kanten
  • : Anzahl der Kanten einer Facette
  • : Anzahl der Kanten, welche zu einem Punkt gehören
  • : Anzahl aller Facetten

Erläuterung der Anfrageklassen Bearbeiten

Anfrage Knotenliste Kantenliste Winged Edge Half Edge
Kante → Eckpunkte Nicht möglich (es gibt keine Kanten) direkt über Kanten ablesbar direkt über Eintrag für Kante abzulesen über Halbkante→vert und pair→vert.
Kante → Facetten Nicht möglich (es gibt keine Kanten) direkt aus Kanten ablesbar direkt aus Kante ersichtlich die angrenzenden Flächen über edge→face und edge→pair→face bestimmen.
Kante → angrenzende Kanten Nicht möglich (es gibt keine Kanten) für beide Eckpunkte: „Eckpunkt → Kante“ durchführen siehe Kantenliste siehe Kantenliste
Eckpunkt → Kanten Da es sich um geschlossene Polygone handelt, hat jede Facette (genauso viele Kanten wie Punkte) Kanten, diese müssen zu jeder Fläche bestimmt werden und nachgeschaut werden, ob die gegebene Ecke darin enthalten ist einfach alle Kanten durchlaufen Startkante zum Punkt ermitteln, dann über „Vorgänger rechts“ suchen solange bis keine Kante mehr da ist, dann wieder bei Startkante beginnen und in andere Richtung laufen. über vert→edge erste Kante holen, danach entgegengesetzte Kante holen und links weiterlaufen. Dies so lange machen, bis links keine Nachfolgerkante da ist, dann wieder mit vert→edge anfangen und diesmal so lange nach rechts laufen, bis keine Nachbarkante mehr vorhanden ist.
Eckpunkt → Facetten Einfach für alle Facetten die Kanten durchgehen, und schauen, ob der gesuchte Eckpunkt enthalten ist. „Eckpunkt → Kante“ ausführen und aus diesen Kanten dann direkt die zugehörige Facette lesen. einfach nur die Kanten zum Punkt ermitteln und in konstanter Zeit die dazugehörigen Flächen ermitteln siehe Kantenliste
Facette → Kanten Alle Kanten einer Facette jeweils paarweise bilden direkt aus Facetten ablesbar siehe Half Edge Bei Startkante der Facette beginnen und nach links laufen. Gehört die nachfolgende Kante zur selben Facette, dann in gleicher Laufrichtung weitermachen. Wird das erste Mal kein Nachfolger gefunden, kehrt man die Laufrichtung um. Gehört der Nachfolger zur selben Facette, dann in dieser Laufrichtung weitermachen, ansonsten abbrechen. Die Laufrichtung kann sich mehrmals ändern. Irgendwann kommt man bei der Startkante an. Dann kann man aufhören.
Facette → Eckpunkte Einfach direkt aus Facetten auslesen „Facette → Kanten“ ausführen und in konstanter Zeit die zugehörigen Eckpunkte auslesen siehe Half Edge „Facette → Kanten“ ausführen und aus den Kanten die Punkte herauslesen, doppelte Punkte rausschmeißen.
Facette → benachbarte Facette Alle Kanten der zu überprüfenden Facette ermitteln und für jede Kante schauen, ob die anderen Facetten diese Kante auch enthalten. „Facette → Kanten“ ausführen und dann direkt aus den Kanten die zugehörigen Facetten ablesen „Facette → Kanten“ ausführen und zu jeder Kante die angrenzende Fläche auslesen siehe Winged Edge

Zusammenfassung Bearbeiten

Wie man sieht, sind die Winged-Edge- und die Half-Edge-Struktur von den enthaltenen Informationen nahezu identisch. Sie weisen deshalb auch fast die gleichen Laufzeiten für das Suchen auf. Half Edge ist in den komplexeren Anfragen etwas besser. Hier müssen aufgrund des Zeigers eines Punktes auf eine zugehörige Startkante beim Suchen aller Kanten eines Punktes auch nur diese angefasst werden. Die Knotenliste scheidet von vornherein aus und die Kantenliste ist vom Suchen her genauso gut wie die Winged-Edge-Liste, benötigt jedoch etwas mehr Speicherplatz, da bei Winged Edge zu einer Facette nur eine Startkante abgelegt werden muss.

Siehe auch Bearbeiten

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. ↑ Jens Neumann: Verfahren zur adhoc-Modellierung und -Simulation räumlicher Feder-Masse-Systeme für den Einsatz in VirtualReality-basierten Handhabungssimulationen. Technische Universität Berlin, Fraunhofer IRB Verlag, 2009, ISBN 978-3-8167-7954-4.
  2. Oliver Burgert: (Memento des Originals vom 10. August 2007 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.iccas.de (PDF) Universität Leipzig, 2005.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Untereinander mit Kanten verbundene Punkte bilden in der Computergrafik ein Polygonnetz das die Gestalt eines Polyeders definiert Dreiecksnetze und Vierecksnetze sind hier am gelaufigsten Zur Speicherung von Polygonnetzen und Polygonen gibt es eine Reihe bekannter Datenstrukturen Die bekanntesten Strukturen sind die Knotenliste Kantenliste Winged Edge und die doppelt verkettete Kantenliste doubly connected halfedge list Unterschiedliche Drahtgittermodelle die einfachste Moglichkeit ein Polygonnetz darzustellen Jeder Knoten muss mindestens eine Verbindung zum Restnetz haben um Mitglied des Netzes zu sein Daraus folgt dass jeder Knoten von jedem anderen im Netz erreichbar ist In der Graphentheorie sind Polygonnetze als ungerichtete Graphen ohne Mehrfachkanten darstellbar 1 2 Inhaltsverzeichnis 1 Eigenschaften von Polygonnetzen 2 Polygonnetz als Dreiecksnetz 3 Datenstrukturen 3 1 Einfache Datenstrukturen 3 1 1 Knotenliste 3 1 2 Kantenliste 3 1 3 Vor bzw Nachteile 3 2 Komplexere Datenstrukturen 3 2 1 Winged Edge nach Baumgart 3 2 2 Doppelt verkettete Kantenliste Half Edge 3 3 Laufzeitvergleich 3 3 1 Erlauterung der Anfrageklassen 3 3 2 Zusammenfassung 4 Siehe auch 5 Weblinks 6 EinzelnachweiseEigenschaften von Polygonnetzen Bearbeiten nbsp Das Bild zeigt typische Netzeigenschaften an verschiedenen Polygonnetzen a Zeigt ein Polygonnetz ohne besondere Eigenschaften b ein strukturiertes Polygonnetz c zeigt ein Polygonnetz das strukturiert und regular ist und d ist strukturiert regular und orthogonal Folgende Eigenschaften kann ein Netz haben keine davon ist allerdings fur ein Polygonnetz erforderlich 1 Strukturiertheit Ein Polygonnetz wird als strukturiert bezeichnet wenn jeder innere Punkt die gleiche Anzahl anliegender Kanten und Flachen hat Regularitat Ein Polygonnetz ist regular wenn die Kantenlangen in jede Richtung konstant sind Diese Eigenschaft baut auf der Strukturiertheit auf Orthogonalitat Ein Polygonnetz wird als orthogonal bezeichnet wenn die Netzkanten rechte Winkel bilden Die Orthogonalitat baut auf die Eigenschaft der Strukturiertheit und der Regularitat auf Polygonnetz als Dreiecksnetz BearbeitenDas Polygonnetz als Dreiecksnetz ist eine weit verbreitete Form des Polygonnetzes Es ist vor allem bei Triangulationen und beim Meshing von Bedeutung Siehe auch Unregelmassiges Dreiecksnetz TIN Datenstrukturen BearbeitenEinfache Datenstrukturen Bearbeiten Knotenliste Bearbeiten Bei der Knotenliste werden die Punkte in einer separaten Punktliste abgelegt Eine Flache wird dann als eine Liste von Zeigern auf die Punkte in dieser Liste definiert Dadurch wird eine Trennung zwischen der Geometrie den Koordinaten der Knoten und der Topologie welche Knoten verbinden welche Kanten welche Kanten begrenzen welche Flachen realisiert Kantenliste Bearbeiten Die Nachteile der Knotenliste werden bei der Kantenliste dadurch umgangen dass alle Kanten in einer separaten Liste gespeichert werden Facetten werden hier als Zeiger auf die Kantenliste definiert Neben dem Anfangs und Endpunkt werden auch die maximal zwei zugehorigen Facetten fur jede Kante abgelegt Die Reihenfolge der Angabe der Eckpunkte fur Kanten legt eine Orientierung fest und bestimmt bei Facetten wo innen und wo aussen ist Vor bzw Nachteile Bearbeiten Datenstruktur Vorteile NachteileKnotenliste Trennung von Geometrie und Topologie minimale Redundanzen Punkte werden nur einmal abgelegt Kanten werden mehrmals durchlaufen und ausgegeben Suche nach zu Kanten gehorenden Facetten nicht effizient moglich nur mit erschopfender Suche moglich Fur alle Kanten in F1 jedes Knotenpaar suchen wir in allen weiteren Facetten ob sie enthalten ist wenn nein dann Randkante Suchen nach Facetten welche eine Kante bzw Ecke enthalten ist ineffizientKantenliste Trennung von Geometrie und Topologie Schnelle Bestimmung von Randkanten Kanten mit nur einem Verweis auf Facette Suchen nach Facetten welche eine Kante bzw Ecke enthalten ist ineffizientGenerell gilt fur Knoten und Kantenlisten dass die Suche ausgehend von einer Facette nach untergeordneten Objekten wie Kanten und Knoten sehr effizient durchfuhrbar ist In umgekehrter Richtung verhalt es sich jedoch gegenteilig So ist z B die Suche nach allen Facetten welche eine bestimmte Ecke enthalten immer noch nur durch eine erschopfende Suche moglich Komplexere Datenstrukturen Bearbeiten Winged Edge nach Baumgart Bearbeiten Eine Datenstruktur mit deren Hilfe sehr viele Abfragen effizient bearbeitet werden konnen ist die Winged Edge Darstellung nach Baumgart Zusatzlich zu den Informationen der Kantenliste werden hier noch Zeiger auf die Kanten abgelegt die von Anfangs und Endpunkt der aktuellen Kante abgehen Aufgrund der Orientierung wird jede Kante einmal positiv im Uhrzeigersinn und einmal negativ gegen den Uhrzeigersinn durchlaufen Mit der Winged Edge Datenstruktur ist es moglich in konstanter Zeit abzufragen welche Knoten oder Facetten zu einer gegebenen Kante gehoren Hat eine Facette k Kanten konnen in linearer Zeit diese Kanten nacheinander abgesucht werden nur bei polygonalen Netzen ohne Anderung der Durchlaufrichtung eines Polygons Andere Anfragen insbesondere solche ausgehend von einer Ecke die nach den Kanten oder Facetten in denen diese Ecke enthalten ist suchen sind deutlich langsamer Doppelt verkettete Kantenliste Half Edge Bearbeiten Die Half Edge Datenstruktur ist ein wenig ausgereifter als die Winged Edge Liste Sie erlaubt die meisten in der folgenden Tabelle aufgefuhrten Operationen in konstanter Zeit auszufuhren d h konstanter Zeit pro gesammelte Information Wenn man z B alle zu einem Eckpunkt benachbarten Kanten herausfinden will ist die Operation linear bezuglich der Anzahl der benachbarten Kanten aber konstant in der Zeit pro Kante Half Edge funktioniert nur mit zweidimensionaler Mannigfaltigkeit d h jede Kante ist von genau zwei Facetten zu jeder Halbkante gibt es eine entgegengesetzte Halbkante umgeben d h T Verbindungen innere Polygone und Bruche sind nicht erlaubt Bei der Half Edge Struktur werden nicht Kanten sondern Halbkanten abgelegt Halbkanten sind gerichtet und zwei zusammengehorende Halbkanten Paar bilden eine Kante und zeigen in die entgegengesetzte Richtung Eine weitere Datenstruktur ist die Doubly connected edge list DCEL Laufzeitvergleich Bearbeiten Folgende Tabelle zeigt einen Vergleich der asymptotischen Laufzeit in Abhangigkeit von den vorhandenen Elementen Knoten Kanten und Flachen Es gibt neun mogliche Abfragen auf die Struktur namlich welche Ecke Kante oder Flache gehort zu welcher Ecke Kante oder Flache Alle Abfragen bis auf diejenige nach den benachbarten Ecken einer gegebenen Ecke werden in der Tabelle aufgefuhrt Der Vergleich zeigt wie unterschiedlich gut die Datenstrukturen die Anfrageklassen bearbeiten Suchanfrage gegeben gesucht Knotenliste Kantenliste Winged Edge Half EdgeKante Eckpunkte N A O 1 displaystyle mathcal O 1 nbsp O 1 displaystyle mathcal O 1 nbsp O 1 displaystyle mathcal O 1 nbsp Kante Facetten N A O 1 displaystyle mathcal O 1 nbsp O 1 displaystyle mathcal O 1 nbsp O 1 displaystyle mathcal O 1 nbsp Kante angrenzende Kanten N A O k displaystyle mathcal O k nbsp O k displaystyle mathcal O k nbsp O k v displaystyle mathcal O k v nbsp Eckpunkt Kanten O f k f displaystyle mathcal O f k f nbsp O k displaystyle mathcal O k nbsp O k displaystyle mathcal O k nbsp O k v displaystyle mathcal O k v nbsp Eckpunkt Facetten O f k f displaystyle mathcal O f k f nbsp O k displaystyle mathcal O k nbsp O k displaystyle mathcal O k nbsp O k v displaystyle mathcal O k v nbsp Facette Kanten O k f displaystyle mathcal O k f nbsp O k f displaystyle mathcal O k f nbsp O k f displaystyle mathcal O k f nbsp O k f displaystyle mathcal O k f nbsp Facette Eckpunkte O k f displaystyle mathcal O k f nbsp O k f displaystyle mathcal O k f nbsp O k f displaystyle mathcal O k f nbsp O k f displaystyle mathcal O k f nbsp Facette benachbarte Facette O f k f 2 displaystyle mathcal O f k f 2 nbsp O k f displaystyle mathcal O k f nbsp O k f displaystyle mathcal O k f nbsp O k f displaystyle mathcal O k f nbsp Hierbei bezeichnet k displaystyle k nbsp Anzahl aller Kanten k f displaystyle k f nbsp Anzahl der Kanten einer Facette k v displaystyle k v nbsp Anzahl der Kanten welche zu einem Punkt gehoren f displaystyle f nbsp Anzahl aller FacettenErlauterung der Anfrageklassen Bearbeiten Anfrage Knotenliste Kantenliste Winged Edge Half EdgeKante Eckpunkte Nicht moglich es gibt keine Kanten direkt uber Kanten ablesbar direkt uber Eintrag fur Kante abzulesen uber Halbkante vert und pair vert Kante Facetten Nicht moglich es gibt keine Kanten direkt aus Kanten ablesbar direkt aus Kante ersichtlich die angrenzenden Flachen uber edge face und edge pair face bestimmen Kante angrenzende Kanten Nicht moglich es gibt keine Kanten fur beide Eckpunkte Eckpunkt Kante durchfuhren siehe Kantenliste siehe KantenlisteEckpunkt Kanten Da es sich um geschlossene Polygone handelt hat jede Facette genauso viele Kanten wie Punkte Kanten diese mussen zu jeder Flache bestimmt werden und nachgeschaut werden ob die gegebene Ecke darin enthalten ist einfach alle Kanten durchlaufen Startkante zum Punkt ermitteln dann uber Vorganger rechts suchen solange bis keine Kante mehr da ist dann wieder bei Startkante beginnen und in andere Richtung laufen uber vert edge erste Kante holen danach entgegengesetzte Kante holen und links weiterlaufen Dies so lange machen bis links keine Nachfolgerkante da ist dann wieder mit vert edge anfangen und diesmal so lange nach rechts laufen bis keine Nachbarkante mehr vorhanden ist Eckpunkt Facetten Einfach fur alle Facetten die Kanten durchgehen und schauen ob der gesuchte Eckpunkt enthalten ist Eckpunkt Kante ausfuhren und aus diesen Kanten dann direkt die zugehorige Facette lesen einfach nur die Kanten zum Punkt ermitteln und in konstanter Zeit die dazugehorigen Flachen ermitteln siehe KantenlisteFacette Kanten Alle Kanten einer Facette jeweils paarweise bilden direkt aus Facetten ablesbar siehe Half Edge Bei Startkante der Facette beginnen und nach links laufen Gehort die nachfolgende Kante zur selben Facette dann in gleicher Laufrichtung weitermachen Wird das erste Mal kein Nachfolger gefunden kehrt man die Laufrichtung um Gehort der Nachfolger zur selben Facette dann in dieser Laufrichtung weitermachen ansonsten abbrechen Die Laufrichtung kann sich mehrmals andern Irgendwann kommt man bei der Startkante an Dann kann man aufhoren Facette Eckpunkte Einfach direkt aus Facetten auslesen Facette Kanten ausfuhren und in konstanter Zeit die zugehorigen Eckpunkte auslesen siehe Half Edge Facette Kanten ausfuhren und aus den Kanten die Punkte herauslesen doppelte Punkte rausschmeissen Facette benachbarte Facette Alle Kanten der zu uberprufenden Facette ermitteln und fur jede Kante schauen ob die anderen Facetten diese Kante auch enthalten Facette Kanten ausfuhren und dann direkt aus den Kanten die zugehorigen Facetten ablesen Facette Kanten ausfuhren und zu jeder Kante die angrenzende Flache auslesen siehe Winged EdgeZusammenfassung Bearbeiten Wie man sieht sind die Winged Edge und die Half Edge Struktur von den enthaltenen Informationen nahezu identisch Sie weisen deshalb auch fast die gleichen Laufzeiten fur das Suchen auf Half Edge ist in den komplexeren Anfragen etwas besser Hier mussen aufgrund des Zeigers eines Punktes auf eine zugehorige Startkante beim Suchen aller Kanten eines Punktes auch nur diese angefasst werden Die Knotenliste scheidet von vornherein aus und die Kantenliste ist vom Suchen her genauso gut wie die Winged Edge Liste benotigt jedoch etwas mehr Speicherplatz da bei Winged Edge zu einer Facette nur eine Startkante abgelegt werden muss Siehe auch BearbeitenDrahtgittermodell Meshing Garland Heckbert AlgorithmusWeblinks BearbeitenPolygon Mesh Processing LibraryEinzelnachweise Bearbeiten a b Jens Neumann Verfahren zur adhoc Modellierung und Simulation raumlicher Feder Masse Systeme fur den Einsatz in VirtualReality basierten Handhabungssimulationen Technische Universitat Berlin Fraunhofer IRB Verlag 2009 ISBN 978 3 8167 7954 4 Oliver Burgert Modellbildung II Nodale Netze Medizinische Planungs und Simulationssysteme Memento des Originals vom 10 August 2007 im Internet Archive nbsp Info Der Archivlink wurde automatisch eingesetzt und noch nicht gepruft Bitte prufe Original und Archivlink gemass Anleitung und entferne dann diesen Hinweis 1 2 Vorlage Webachiv IABot www iccas de PDF Universitat Leipzig 2005 Abgerufen von https de wikipedia org w index php title Polygonnetz amp oldid 213570549