Quelltext der Seite Hüllkörper

{{Weiterleitungshinweis|Bounding Box|Für deren zweidimensionalen Fall siehe ''[[Minimal umgebendes Rechteck]]''.}}
[[Datei:BoundingBox.jpg|mini|Ein dreidimensionaler Körper und der entsprechende quaderförmige Hüllkörper (weiße dünne Linien)|alternativtext=]]

Ein '''Hüllkörper''' ({{EnS|bounding volume}}) ist in der [[Algorithmische Geometrie|algorithmischen Geometrie]] ein einfacher [[Körper (Geometrie)|geometrischer Körper]], der ein komplexes dreidimensionales Objekt oder einen komplexen Körper umschließt.

== Anwendungen und Varianten ==
Hüllkörper werden vor allem zur Beschleunigung von Algorithmen der algorithmischen Geometrie oder Computergrafik, etwa beim [[Raytracing]], verwendet. Sie werden oft auch hierarchisch strukturiert (Bounding Volumes umschließen andere Bounding Volumes), um die Effizienz zusätzlich zu steigern. In Computerspielen finden sie als [[Hitbox]] Anwendung, um die [[Kollisionserkennung (algorithmische Geometrie)|Kollisionserkennung]] zu vereinfachen.

Folgende Hüllkörper sind 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 (Geometrie)|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<ref>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}} ({{Webarchiv|url=http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf |wayback=20100629131637 |text=online, 1.3 MB; PDF }})</ref>. 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 <math>O(k)</math> durchführen.<ref>G. Zachmann: [https://cgvr.informatik.uni-bremen.de/papers/vrais98/vrais98.pdf ''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</ref>

== 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 ==
<references />

{{SORTIERUNG:Hullkorper}}
[[Kategorie:Algorithmische Geometrie]]