Hüllkörper

{{#if: Bounding Box

 | Vorlage:Hinweisbaustein
 | {{#ifeq: 0 | 0 | }}}}

Datei:BoundingBox.jpg

Ein dreidimensionaler Körper und der entsprechende quaderförmige Hüllkörper (weiße dünne Linien)

Ein Hüllkörper ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}) ist in der algorithmischen Geometrie ein einfacher 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 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 (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, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0272-1716|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0272-1716}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}} (<templatestyles src="Webarchiv/styles.css" />{{#if:20100629131637

      | {{#ifeq: 20100629131637 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: online, 1.3 MB; PDF | {{#invoke:WLink|getEscapedTitle|online, 1.3 MB; PDF}} | {{#invoke:Webarchiv|getdomain|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20100629131637}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: online, 1.3 MB; PDF | {{#invoke:WLink|getEscapedTitle|online, 1.3 MB; PDF}} | {{#invoke:Webarchiv|getdomain|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20100629131637}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: online, 1.3 MB; PDF | {{#invoke:WLink|getEscapedTitle|online, 1.3 MB; PDF}} | {{#invoke:Webarchiv|getdomain|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: online, 1.3 MB; PDF | {{#invoke:WLink|getEscapedTitle|online, 1.3 MB; PDF}} | {{#invoke:Webarchiv|getdomain|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: online, 1.3 MB; PDF | {{#invoke:WLink|getEscapedTitle|online, 1.3 MB; PDF}} | {{#invoke:Webarchiv|getdomain|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: online, 1.3 MB; PDF | {{#invoke:WLink|getEscapedTitle|online, 1.3 MB; PDF}} | {{#invoke:Webarchiv|getdomain|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20100629131637|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: online, 1.3 MB; PDF
    | {{#if: {{#invoke:WLink|isBracketedLink|online, 1.3 MB; PDF}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://graphics.ucsd.edu/courses/cse168_s06/ucsd/automatic_bbox.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }})</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: Rapid Collision Detection by Dynamically Aligned DOP-Trees. Proc. of IEEE Virtual Reality Annual International Symposium (VRAIS, now IEEE VR), 1998, S. 90–97, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}, 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