Hüllkörper

Ein Hüllkörper (englisch bounding volume) i​st in d​er algorithmischen Geometrie e​in einfacher geometrischer Körper, d​er ein komplexes dreidimensionales Objekt o​der einen komplexen Körper umschließt.

Ein dreidimensionaler Körper und der entsprechende quaderförmige Hüllkörper (in weiß)

Anwendungen und Varianten

Hüllkörper werden v​or allem z​ur Beschleunigung v​on Algorithmen d​er algorithmischen Geometrie o​der Computergrafik, e​twa beim Raytracing, verwendet. Sie werden o​ft auch hierarchisch strukturiert (Bounding Volumes umschließen andere Bounding Volumes), u​m die Effizienz zusätzlich z​u steigern.

Folgende Hüllkörper s​ind gebräuchlich:

  • Kugeln (Bounding Spheres). Diese Art von Hüllkörpern ist besonders bei der Kollisionserkennung verbreitet, da sich Kollisionen mit Kugeln sehr leicht berechnen lassen.
  • Quader oder Würfel (Bounding Boxes). Quaderförmige Hüllkörper umschreiben Objekte oft genauer als Kugeln und sind deshalb in einigen Anwendungen wie Raytracing von Vorteil. Über Bounding Volume Hierarchies (BVH) kann das Raytracing beschleunigt werden[1]. Beliebig orientierte Quader werden auch als Oriented Bounding Boxes (OBB), an den Achsen ausgerichtete Quader als Axis-Aligned Bounding Boxes (AABB) bezeichnet. AABBs werden üblicherweise durch zwei Punkte definiert, die die Position der Ecken auf beiden Seiten einer Quaderdiagonalen angeben. Eine zweidimensionale Bounding Box wird als minimal umgebendes Rechteck bezeichnet.
  • k-DOP oder k-Discretely Oriented Polytopes genannt. Im Gegensatz zu OBBs erlauben k-DOP's mehrere Beschränkungsflächen, wodurch sie Objekte besser (enger) einschließen können. Diese Beschränkungsflächen müssen immer paarweise parallel zueinander sein, so dass ein k-DOP auch als Schnittmenge von k Slabs betrachtet werden kann. Der Überlappungstest (Schnitttest) zweier k-DOPs lässt sich in Zeit durchführen.[2]

Siehe auch

Literatur
  • Michael Bender, Manfred Brill: Computergrafik: ein anwendungsorientiertes Lehrbuch, S. 54 f. Hanser, München 2006, ISBN 3-446-40434-1

Fußnoten und Einzelnachweise
  1. Jeffrey Goldsmith, John Salmon: Automatic Creation of Object Hierarchies for Ray Tracing In: Proceedings of IEEE Symposium on Computer Graphics and Applications, Mai 1987, S. 14–20, ISSN 0272-1716 ((online, 1.3 MB; PDF) (Memento des Originals vom 29. Juni 2010 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/graphics.ucsd.edu)
  2. G. Zachmann: Rapid Collision Detection by Dynamically Aligned DOP-Trees. Proc. of IEEE Virtual Reality Annual International Symposium (VRAIS, now IEEE VR), 1998, S. 90–97, doi:10.1109/VRAIS.1998.658428, ISBN 0-8186-8362-7
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.