Entfernung verdeckter Linien: Das Unsichtbare enthüllen: Geheimnisse des Computer Vision

Von Fouad Sabry

Was ist die Entfernung versteckter Linien?

Feste Objekte werden im Bereich der dreidimensionalen Computergrafik typischerweise als Polyeder modelliert. Innerhalb eines Polyeders ist eine Fläche ein planares Polygon, das von geraden Liniensegmenten umgeben ist, die als Kanten bezeichnet werden. Beim Versuch, gekrümmte Oberflächen zu imitieren, wird typischerweise ein Polygonnetz verwendet. Computerprogramme, die zur Erstellung von Strichzeichnungen undurchsichtiger Objekte verwendet werden, müssen in der Lage sein, festzustellen, ob Kanten oder Kantenabschnitte durch das Objekt selbst oder durch andere Objekte verdeckt werden. Dadurch können die Kanten während des Rendervorgangs beschnitten werden. Die betreffende Schwierigkeit wird als Hidden-Line-Entfernung bezeichnet.

Wie Sie davon profitieren

(I) Einblicke und Validierungen zu den folgenden Themen:

Kapitel 1: Entfernung verdeckter Linien

Kapitel 2: Painter-Algorithmus

Kapitel 3: Computergeometrie

Kapitel 4: Strahlenwurf

Kapitel 5: Bestimmung verdeckter Oberflächen

Kapitel 6: Punktort

Kapitel 7: Euklidischer minimaler Spannbaum

Kapitel 8: Kunstgalerieproblem

Kapitel 9: High-Dynamic-Range-Rendering

Kapitel 10: Gerades Skelett

(II) Beantwortung der häufigsten öffentlichen Fragen zur Entfernung verdeckter Linien .

(III) Beispiele aus der Praxis für die Verwendung der Entfernung verdeckter Linien in vielen Bereichen.

Für wen dieses Buch gedacht ist

Profis, Studenten und Doktoranden, Enthusiasten, Bastler und diejenigen, die über Grundkenntnisse oder Informationen für jede Art von Hidden Line Removal hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 5. Mai 2024

Buchvorschau

Kapitel 1: Entfernen verdeckter Linien

In der 3D-Computergrafik werden Polyeder typischerweise verwendet, um feste Dinge zu modellieren. Eine Fläche eines Polyeders ist ein planares Polygon, das von Kanten begrenzt wird, bei denen es sich um gerade Liniensegmente handelt. In der Regel wird ein Polygonnetz verwendet, um gekrümmte Oberflächen darzustellen. Um Kanten während des Renderns beschneiden zu können, müssen Computerprogramme für Strichzeichnungen von undurchsichtigen Objekten in der Lage sein, zu bestimmen, welche Kanten oder Teile von Kanten durch ein Element oder andere Objekte verdeckt werden. Dieses Problem wird als Hidden-Line-Entfernung bezeichnet.

Roberts entwickelte die erste bekannte Lösung für das Problem der versteckten Leitungen. Ivan E. Sutherland hob 1966 zehn ungelöste Probleme in der Computergrafik hervor.

Im computergestützten Design können Modelle beispielsweise Tausende oder Millionen von Kanten haben. Daher ist es wichtig, eine Methode der Rechenkomplexität zu verwenden, die den Ressourcenbedarf (z. B. Zeit und Speicher) in Abhängigkeit von der Problemgröße ausdrückt. Besonders entscheidend sind zeitliche Einschränkungen für interaktive Systeme.

Die Problemgrößen für das Entfernen verdeckter Linien sind die Anzahl n der Kanten des Modells und die Anzahl v der sichtbaren Segmente der Kanten.

An den Kreuzungsstellen der Bilder der Kanten kann sich die Sichtbarkeit verschieben.

Sei k die Gesamtzahl der Stellen, an denen sich die Bilder der Kanten schneiden.

Sowohl k = Θ(n2) als  auch v = Θ(n2) im schlimmsten Fall, typischerweise aber v k.

Vor 1984 schlugen die von Ottmann und Widmayer und Wood veröffentlichten Hidden-Line-Algorithmen O((n + k) log2 n)-Time Hidden-Line-Algorithmen vor.

Dann verbesserte Nurmi die Laufzeit auf O((n + k) log n).

Diese Algorithmen benötigen Θ(n2 log2 n), bzw. Θ(n2 log n) Zeit, die im schlimmsten Fall, wenn k dennoch kleiner als quadratisch ist, kann in Wirklichkeit schneller sein.

Jeder Hidden-Line-Algorithmus muss im schlimmsten Fall die Vereinigung von Θ(n) verdeckten Intervallen auf n Kanten bestimmen.

Da Ω(n log n) eine untere Schranke für die Bestimmung der Vereinigung von n Intervallen ist, scheint es, dass das Beste, was man hoffen kann, die Θ(n2 log n) Worst-Case-Zeit ist.

Der log-n-Faktor wurde jedoch von Devai eliminiert, da die Methoden von Devai und McKenna Meilensteine in Sichtbarkeitsalgorithmen sind, indem sie eine theoretische Barriere von O(n2 log n) zu O(n2) für die Verarbeitung einer Szene von n Kanten durchbrechen.

Die andere offene Frage, die Devai aufgeworfen hat, ob es einen O(n log n + v)-Zeit-Hidden-Line-Algorithmus gibt, wobei v, wie bereits erwähnt, die Anzahl der sichtbaren Segmente ist, blieb zum Zeitpunkt des Schreibens unbeantwortet.

Im Jahr 1988 schlug Devai einen parallelen O(log-n)-Zeitalgorithmus vor, der n2-Prozessoren für das Hidden-Line-Problem unter dem Concurrent Read, Model of computing using exclusive write (CREW) parallel random-access machine (PRAM) verwendet.

Da das Produkt aus der Prozessorzahl und der Laufzeit asymptotisch größer als Θ(n2) ist, ist die sequentielle Komplikation des Problems, Der Algorithmus ist ineffizient, beweist jedoch, dass das Hidden-Line-Problem zur NC-Schwierigkeitsklasse gehört, d.h. Es kann mit einer polynomialen Anzahl von Prozessoren in polylogarithmischer Zeit gelöst werden.

Hidden-Surface-Algorithmen können verwendet werden, um verdeckte Linien zu eliminieren, aber nicht umgekehrt.

Reif und Sen schlugen einen O(log⁴ n)-Zeitalgorithmus für das Problem der verborgenen Oberfläche vor, der O((n + v)/log n) CREW PRAM-Prozessoren für ein eingeschränktes Modell polyedrischer Terrains verwendet, wobei v die Menge der Ausgabe ist.

Im Jahr 2011 veröffentlichte Devai einen O(log n)-Zeit-Hidden-Surface-Algorithmus und einen einfacheren, ebenfalls O(log n)-Zeit-Hidden-Line-Algorithmus.

Der Algorithmus für verdeckte Oberflächen, der n2/log n CREW PRAM-Prozessoren verwendet, ist in Bezug auf die Effizienz am besten.

Der Hidden-Line-Algorithmus verwendet exklusive n2-Lese- und EREW-PRAM-Prozessoren (exklusives Schreiben).

EREW ist der PRAM-Typ, der echten Maschinen am ähnlichsten ist.

Der Hidden-Line-Algorithmus funktioniert O(n2 log n), Was ist die Obergrenze für die effektivsten sequentiellen Algorithmen?.

Cook, Dwork und Reischuk gaben eine untere Grenze von Ω(log n) an, um das Maximum von n ganzen Zahlen zu finden, die unendlich viele Prozessoren eines beliebigen PRAM ohne gleichzeitige Schreibvorgänge zulassen.

{Ende Kapitel 1}

Kapitel 2: Painter's Algorithmus

Der Painter-Algorithmus (auch Tiefensortieralgorithmus und Prioritätsfüllung) ist ein Algorithmus zur Bestimmung sichtbarer Oberflächen in 3D-Computergrafiken, der auf Polygon-für-Polygon-Basis arbeitet und nicht Pixel für Pixel, reihenweise oder auf Region-für-Region-Basis unter Verwendung zusätzlicher Techniken zum Entfernen verdeckter Oberflächen.

Im Jahr 1972, als alle drei bei CADCentre angestellt waren, präsentierten Martin Newell, Richard Newell und Tom Sancha erstmals den Maleralgorithmus als grundlegende Lösung für das Problem der Bestimmung verdeckter Oberflächen.

Der Painter's Algorithm funktioniert konzeptionell wie folgt:

Sortieren Sie jedes Polygon nach Tiefe

Platzieren Sie jedes Polygon vom entferntesten bis zum nächsten.

Sortieren von Polygonen nach Tiefe

Für jedes Polygon p:

Für jedes Pixel , das P abdeckt:

P.Color auf Pixel malen

Die Zeitkomplexität des Maleralgorithmus hängt stark vom Sortiermechanismus ab, der zur Anordnung der Polygone verwendet wird. Geht man von der effizientesten Sortiertechnik aus, so ist die Worst-Case-Komplexität des Maleransatzes O(n log n + m*n), wobei n die Anzahl der Polygone und m die Anzahl der zu füllenden Pixel ist.

Die Worst-Case-Raumkomplexität des Painter-Algorithmus ist O(n+m), wobei n die Anzahl der Polygone und m die Anzahl der zu füllenden Pixel ist.