Begrenzungsvolumen: Erforschung der räumlichen Darstellung in Computer Vision

Von Fouad Sabry

Was ist ein Begrenzungsvolumen

In der Computergrafik und der Computergeometrie ist ein Begrenzungsvolumen für eine Menge von Objekten ein geschlossener Bereich, der die Vereinigung der Objekte in der vollständig enthält Satz. Begrenzungsvolumina werden verwendet, um die Effizienz geometrischer Operationen zu verbessern, beispielsweise durch die Verwendung einfacher Regionen und einfachere Möglichkeiten zum Testen auf Überlappung.

Ihr Nutzen

(I) Erkenntnisse und Validierungen zu den folgenden Themen:

Kapitel 1: Grenzvolumen

Kapitel 2: Kugel

Kapitel 3: Ellipsoid

Kapitel 4: Kollisionserkennung

Kapitel 5: Kegel

Kapitel 6: Zylinder

Kapitel 7: Konvexes Polytop

Kapitel 8: Hierarchie des Begrenzungsvolumens

Kapitel 9: Minimaler Begrenzungsrahmen

Kapitel 10: Geometrisches Trennzeichen

(II) Beantwortung der häufigsten öffentlichen Fragen zum Begrenzungsvolumen .

(III) Beispiele aus der Praxis für die Verwendung von Bounding Volume in vielen Bereichen.

Für wen dieses Buch gedacht ist

Fachleute, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über Grundkenntnisse oder Informationen für jede Art von Begrenzungsvolumen hinausgehen möchten.

 

 

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

Buchvorschau

Kapitel 1: Begrenzungsvolumen

In der Computergrafik und der Computergeometrie ist ein Begrenzungsvolumen für eine Menge von Objekten ein geschlossenes Volumen, das ihre Vereinigung vollständig umschließt. Begrenzte Volumina werden verwendet, um kompliziertere Objekte zu halten, und begrenzte Volumina werden verwendet, um die Effizienz geometrischer Prozesse zu erhöhen. In der Regel verfügen einfachere Volumes über einfachere Methoden zur Erkennung von Überlappungen.

Ein umgebendes Volumen für eine Sammlung von Elementen ist auch ein umgebendes Volumen für das Objekt, das durch ihre Vereinigung gebildet wird, und umgekehrt. Daher kann die Beschreibung auf ein einzelnes Objekt beschränkt werden, von dem angenommen wird, dass es nicht leer und begrenzt (endlich) ist.

Am häufigsten werden begrenzende Volumina verwendet, um bestimmte Arten von Tests zu beschleunigen.

Beim Raytracing werden Begrenzungsvolumina für Ray-Intersection-Tests verwendet, und in vielen Rendering-Techniken werden sie für Frustum-Tests verwendet. Wenn der Strahl oder der Betrachtungsstumpf das umgebende Volumen nicht schneidet, ist es ihm unmöglich, das darin eingeschlossene Element zu schneiden, was eine triviale Ablehnung ermöglicht. Ebenso, wenn das Frustum die Gesamtheit des gebundenen Volumens enthält, kann der Inhalt ohne zusätzliche Prüfung angenommen werden. Diese Schnittpunkttests generieren eine Liste von darstellbaren Objekten (gerendert; gerastert).

Wenn sich zwei umgebende Volumina in der Kollisionserkennung nicht überschneiden, können die eingeschlossenen Objekte nicht kollidieren.

Aufgrund der vereinfachten Geometrie eines umgebenden Volumens ist das Testen mit diesem Volumen oft viel schneller als das Testen mit dem Element selbst. Das liegt daran, dass ein Objekt oft aus Polygonen oder Datenstrukturen aufgebaut ist, die mit Hilfe von Polygonen approximiert werden. Wenn ein Objekt nicht sichtbar ist, ist es rechnerisch ineffizient, jedes Polygon anhand des Ansichtsvolumens zu testen. (Objekte auf dem Bildschirm müssen unabhängig davon, ob ihre Oberflächen sichtbar sind oder nicht, auf den Bildschirm zugeschnitten werden.)

Um die umgebenden Volumina komplexer Objekte zu erfassen, ist es üblich, ein Szenendiagramm oder eine Bounding-Volume-Hierarchie, wie z. B. OBB-Bäume, zu verwenden, um die Objekte/Szene zu zerlegen. Die Grundidee besteht darin, eine Szene in einer baumartigen Struktur zu organisieren, wobei die Wurzel die gesamte Szene und jedes Blatt eine Komponente darstellt.

Eine visuelle Hülle ist ein Grenzvolumen, das aus den Silhouetten eines Objekts in Computer-Stereo-Vision rekonstruiert wird.

Der Rechenaufwand für die Berechnung eines Begrenzungsvolumens für ein Objekt, die Kosten für die Aktualisierung in Anwendungen, in denen die Objekte verschoben oder ihre Form oder Größe ändern können, die Kosten für die Bestimmung von Schnittpunkten und die gewünschte Genauigkeit des Schnittpunkttests beeinflussen die Auswahl des Typs des Begrenzungsvolumens für eine bestimmte Anwendung. Die Genauigkeit des Schnittpunkttests ist proportional zur Größe des Hohlraums innerhalb des umgebenden Volumens, der nicht mit dem umgebenden Objekt verknüpft ist. Im Allgemeinen ermöglichen ausgeklügelte Begrenzungsvolumina weniger freie Fläche, verursachen aber mehr Verarbeitungskosten. Es ist üblich, mehrere Typen gleichzeitig einzusetzen, z. B. einen billigen für einen schnellen, aber ungenauen Test neben einem genaueren, aber auch teureren.

Alle hier besprochenen Typen haben konvexe Randvolumina. Wenn bekannt ist, dass das abhängige Element konvex ist, handelt es sich nicht um eine Einschränkung. Wenn nicht-konvexe Begrenzungsvolumina benötigt werden, können sie als Vereinigung vieler konvexer Begrenzungsvolumina dargestellt werden. Leider werden Schnittpunktprüfungen mit zunehmender Komplexität der Begrenzungsrahmen immer teurer.

Der Begrenzungsrahmen des Objekts ist ein Quader oder, in zwei Dimensionen, ein Rechteck. In der dynamischen Simulation werden Begrenzungsrahmen gegenüber alternativen Arten von Begrenzungsvolumen, wie z. B. Begrenzungskugeln oder Zylindern, für annähernd quaderförmige Objekte bevorzugt, wenn die Genauigkeit des Schnittversuchs von entscheidender Bedeutung ist. Bei Gegenständen, die auf anderen ruhen, wie z. B. einem auf dem Boden liegenden Auto, liegt der Nutzen auf der Hand. Eine Begrenzungskugel würde darauf hindeuten, dass sich das Auto mit dem Boden überschneiden könnte, was einen teureren Test des tatsächlichen Modells des Autos erfordern würde, um ihn abzulehnen. Ein Begrenzungsrahmen würde jedoch sofort anzeigen, dass sich das Auto nicht mit dem Boden kreuzt, wodurch der teurere Test entfällt.

In einer Reihe von Anwendungen wird der Begrenzungsrahmen an den Achsen des Koordinatensystems ausgerichtet, wobei er als achsenausgerichteter Begrenzungsrahmen (AABB) bezeichnet wird. Um die allgemeine Situation von einem AABB zu unterscheiden, wird ein beliebiger Begrenzungsrahmen manchmal als orientierter Begrenzungsrahmen (OBB) oder OOBB bezeichnet, wenn das lokale Koordinatensystem eines vorhandenen Objekts verwendet wird. AABBs sind leichter für Schnittpunkte zu verifizieren als OBBs, aber wenn das Modell gedreht wird, müssen sie neu berechnet werden und können nicht einfach mit dem Modell gedreht werden.

Eine Begrenzungskapsel ist eine gepfeilte Kugel (das Volumen, das eine Kugel einnimmt, wenn sie sich entlang eines geraden Liniensegments bewegt), die das Objekt umschließt. Der Radius der Sweeping-Kugel und der Abschnitt, über den die Kugel gesweept wird, können zur Symbolisierung von Kapseln verwendet werden. Er hat die gleichen Eigenschaften wie ein Zylinder, ist aber leichter zu manipulieren, da der Kreuzungstest weniger kompliziert ist. Eine Kapsel und ein anderes Objekt schneiden sich, wenn der Abstand zwischen dem definierenden Segment der Kapsel und einem Merkmal des anderen Objekts kleiner als der Radius der Kapsel ist. Zwei Kapseln schneiden sich beispielsweise, wenn der Abstand zwischen ihren Segmenten kleiner ist als die Summe ihrer Radien. Dies gilt für beliebig rotierende Kapseln, was sie in der Praxis attraktiver macht als Zylinder.

Ein umschreibender Zylinder ist ein Zylinder, der das Element enthält. Die Achse des Zylinders wird in den meisten Anwendungen oft an der vertikalen Richtung der Szene ausgerichtet. Zylinder eignen sich für dreidimensionale Objekte, die sich nur um eine vertikale Achse, nicht aber um andere Achsen drehen können und ansonsten ausschließlich auf translatorische Bewegung beschränkt sind. Zwei an der vertikalen Achse ausgerichtete Zylinder kollidieren, wenn sich ihre Projektionen auf der vertikalen Achse – zwei Liniensegmente – und ihre Projektionen auf der horizontalen Ebene – zwei kreisförmige Scheiben – gleichzeitig schneiden. Jede ist einfach zu testen. In Videospielen werden Begrenzungszylinder häufig als Begrenzungsvolumen für aufrechte Personen verwendet.

Das umgebende Ellipsoid eines Objekts ist die Ellipse, die das Objekt enthält. In der Regel erzeugen Ellipsoide engere Passungen als Kugeln. Schnittpunkte mit Ellipsoiden werden erreicht, indem das andere Objekt entlang der Primärachsen des Ellipsoids um einen Faktor skaliert wird, der dem multiplikativen Kehrwert der Radien des Ellipsoids entspricht, wodurch das Problem vereinfacht wird, das skalierte Element mit einer Einheitskugel zu kreuzen. Wenn die angewandte Skalierung zu einer Verzerrung führt, muss darauf geachtet werden, Komplikationen zu vermeiden. Eine Verzerrung kann die Verwendung von Ellipsoiden unter bestimmten Umständen undurchführbar machen, z. B. wenn zwei beliebige Ellipsoide kollidieren.

Eine Begrenzungskugel ist eine Kugel, in der das Objekt enthalten ist. In zweidimensionalen Grafiken ist dies ein Kreis. Der Mittelpunkt und der Radius einer sphärischen Begrenzung stellen sie dar. Zwei Kugeln kollidieren, wenn der Abstand zwischen ihren Mittelpunkten kleiner ist als die Summe ihrer Radien. Dies ist ein sehr schneller Kollisionstest. Dadurch eignen sich