Mezní objem - Bounding volume

3D model s ohraničovacím rámečkem nakresleným přerušovanými čarami.

V počítačové grafice a výpočetní geometrii je ohraničujícím svazkem pro sadu objektů uzavřený svazek, který zcela obsahuje spojení objektů v sadě. Ohraničující svazky se používají ke zlepšení efektivity geometrických operací pomocí jednoduchých svazků, které obsahují složitější objekty. Za normálních okolností mají jednodušší svazky jednodušší způsoby testování překrývání .

Ohraničující svazek pro sadu objektů je také ohraničující svazek pro jeden objekt skládající se z jejich sjednocení a naopak. Proto je možné omezit popis na případ jediného objektu, o kterém se předpokládá, že je neprázdný a ohraničený (konečný).

Použití

Hraniční svazky se nejčastěji používají k urychlení určitých druhů testů.

V trasování paprsků se ohraničující svazky používají v testech průniku paprsků a v mnoha vykreslovacích algoritmech se používají k prohlížení testů komprese . Pokud paprsek nebo zorné pole neprotínají ohraničující svazek, nemohou protínat objekt obsažený v něm, což umožňuje triviální odmítnutí . Podobně, pokud komolý komůrk obsahuje celistvost objemového objemu, může být obsah bez dalších testů triviálně přijat . Tyto testy průniku vytvářejí seznam objektů, které musí být 'zobrazeny' (vykresleny; rastrovány ).

Při detekci kolizí , když se dva ohraničující svazky neprotínají, se obsažené objekty nemohou srazit.

Testování proti ohraničujícímu svazku je obvykle mnohem rychlejší než testování proti samotnému objektu z důvodu jednodušší geometrie vázaného svazku. Je to proto, že „objekt“ se obvykle skládá z polygonů nebo datových struktur, které jsou redukovány na polygonální aproximace. V obou případech je výpočetně nehospodárné testovat každý polygon proti objemu pohledu, pokud objekt není viditelný. (Objekty na obrazovce musí být na obrazovku „připnuty“, bez ohledu na to, zda jsou jejich povrchy skutečně viditelné.)

Chcete-li získat ohraničující svazky složitých objektů, běžným způsobem je rozbít objekty / scénu pomocí grafu scény nebo konkrétněji hierarchie svazků objemů , jako jsou např . Stromy OBB . Základní myšlenkou je uspořádat scénu ve stromové struktuře, kde kořen zahrnuje celou scénu a každý list obsahuje menší podčást.

Běžné typy

Volba typu ohraničujícího svazku pro danou aplikaci je dána řadou faktorů: výpočetní náklady na výpočet ohraničujícího svazku pro objekt, náklady na jeho aktualizaci v aplikacích, ve kterých se objekty mohou pohybovat nebo měnit tvar nebo velikost , náklady na určení křižovatek a požadovaná přesnost testu křižovatky. Přesnost testu průniku souvisí s množstvím prostoru v ohraničujícím svazku, který není spojen s ohraničeným objektem, který se nazývá prázdný prostor . Sofistikované ohraničující svazky obecně umožňují méně prázdného prostoru, ale jsou výpočetně nákladnější. Je běžné používat několik typů ve spojení, například levný pro rychlý, ale hrubý test ve spojení s přesnějším, ale také dražším typem.

Všechny zde zpracované typy poskytují konvexní ohraničující objemy. Pokud je o ohraničeném objektu známo, že je konvexní, nejedná se o omezení. Pokud jsou vyžadovány nekonvexní ohraničující svazky, je třeba je reprezentovat jako spojení řady konvexních ohraničujících svazků. Testy křižovatky se bohužel stávají rychle dražšími, protože ohraničující rámečky se stávají sofistikovanějšími.

Ohraničující box je kvádru , nebo v 2-D a obdélník , obsahující objekt. V dynamické simulaci jsou ohraničující rámečky upřednostňovány před jinými tvary ohraničujícího objemu, jako jsou ohraničující koule nebo válce pro objekty, které mají zhruba tvar kvádru, když musí být průnikový test docela přesný. Výhoda je zřejmá například u předmětů, které spočívají na jiných, jako je například auto odpočívající na zemi: ohraničující koule by ukázala, že by se auto mohlo protínat se zemí, což by pak bylo nutné odmítnout nákladnějším testem skutečného modelu automobilu; ohraničující rámeček okamžitě ukazuje, že se auto neprotíná s vozovkou, což šetří nákladnější test.

V mnoha aplikacích je ohraničující rámeček zarovnán s osami souřadnicového systému a je pak znám jako ohraničovací rámeček zarovnaný na osu ( AABB ). Aby se odlišil obecný případ od AABB, libovolné ohraničující pole se někdy nazývá orientovaný ohraničující rámeček ( OBB ) nebo OOBB, když se použije místní souřadný systém existujícího objektu . AABB je mnohem jednodušší testovat průnik než OBB, ale mají tu nevýhodu, že když se model otáčí, nelze s ním jednoduše otáčet, ale je třeba jej přepočítat.

Ohraničení kapsle je zametl koule (tedy objem, že koule se, jak se pohybuje podél úsečky přímé) obsahující objekt. Kapsle mohou být reprezentovány poloměrem tažené koule a segmentem, přes který je koule tažena). Má vlastnosti podobné válci, ale je jednodušší, protože je průnikový test jednodušší. Kapsle a další objekt se protínají, pokud je vzdálenost mezi definujícím segmentem kapsle a některým znakem druhého objektu menší než poloměr kapsle. Například dvě kapsle se protínají, pokud je vzdálenost mezi segmenty kapslí menší než součet jejich poloměrů. To platí pro libovolně rotované kapsle, a proto jsou v praxi přitažlivější než válce.

Ohraničující válec je válec obsahující objekt. Ve většině aplikací je osa válce zarovnána se svislým směrem scény. Válce jsou vhodné pro 3D objekty, které se mohou otáčet pouze kolem svislé osy, ale ne kolem ostatních os, a jinak jsou omezeny pohybem pouze pomocí posunu. Dva válce zarovnané se svislou osou se protínají, když se současně protínají jejich projekce na svislé ose - což jsou dva úsečné úseky - a také jejich projekce na vodorovné rovině - dva kruhové disky. Oba lze snadno otestovat. Ve videohrách se ohraničující válce často používají jako ohraničující svazky pro lidi stojící vzpřímeně.

Ohraničující elipsoid je elipsoid obsahující objekt. Elipsoidy obvykle poskytují těsnější tvar než koule. Průsečíky s elipsoidy se provádějí změnou měřítka druhého objektu podél hlavních os elipsoidu o částku rovnající se multiplikativní inverzi poloměrů elipsoidu, čímž se zmenší problém protnutí zmenšeného objektu s jednotkovou koulí . Je třeba dbát na to, aby se předešlo problémům, pokud aplikované škálování způsobí zkosení . Zkosení může v určitých případech znemožnit použití elipsoidů, například kolize mezi dvěma libovolnými elipsoidy.

Ohraničující koule je koule obsahující objekt. Ve 2D grafice se jedná o kruh . Ohraničující koule jsou reprezentovány středem a poloměrem. Velmi rychle testují vzájemnou kolizi: dvě koule se protínají, když vzdálenost mezi jejich středy nepřesahuje součet jejich poloměrů. Díky tomu jsou ohraničující koule vhodné pro objekty, které se mohou pohybovat v libovolném počtu dimenzí.

Ohraničující deska je svazek, který projektů v míře, na ose, a lze je považovat za deska ohraničena mezi dvěma rovinami. Ohraničující rámeček je průsečík ortogonálně orientovaných ohraničujících desek. K urychlení paprskového sledování byly použity ohraničující desky

Ohraničující trojúhelník ve 2-D, je velmi užitečné, aby zrychlení test oříznutí nebo viditelnost B-spline křivky. Viz „Circle a B-spline ořezové algoritmy“ v rámci předmětu ořezové (počítačová grafika), kde je uveden příklad použití.

Konvexní obal je nejmenší konvexní objem obsahující objekt. Pokud je objekt spojením konečné množiny bodů, jeho konvexní trup je mnohostěn.

Diskrétní orientovaný mnohostěn ( DOP ) zobecňuje ohraničení. K-DOP je booleovský průsečík rozsahů podél k směrů. Tak, k -DOP je logický průnik k- ohraničující desek a je konvexní mnohostěn obsahující objekt (v 2-D a mnohoúhelníku , v 3-D a polyhedron ). 2-D obdélník je speciální případ 2-DOP a 3-D box je speciální případ 3-DOP. Obecně platí, že osy DOP nemusí být ortogonální a může existovat více os než rozměrů prostoru. Například trojrozměrný rámeček, který je zkosený na všech hranách a rozích, lze zkonstruovat jako 13-DOP. Skutečný počet ploch může být menší než 2krát k, pokud se některé plochy zvrhnou, zmenší na hranu nebo vrchol.

Minimální ohraničující obdélník nebo MBR - nejméně AABB ve 2-D - je často používán v popisu geografických (nebo „geografických“) datových položek, které slouží jako zjednodušené proxy pro prostorového rozsahu datové sady (viz geoprostorovou metadata ) pro účely vyhledávání dat (včetně případných prostorových dotazů) a zobrazení. Je také základní součástí metody prostorového indexování metodou R-stromu .

Základní kontroly křižovatky

U některých typů ohraničujícího objemu (OBB a konvexní mnohostěny) je účinnou kontrolou věta o oddělovací ose . Myšlenka zde je, že pokud existuje osa, kterou se objekty nepřekrývají, pak se objekty neprotínají. Kontrolované osy jsou obvykle osy základních os pro objemy (jednotkové osy v případě AABB nebo 3 základní osy z každé OBB v případě OBB). Často následuje také kontrola křížových produktů předchozích os (jedna osa od každého objektu).

V případě AABB se z těchto testů stane jednoduchá sada testů překrytí, pokud jde o jednotkové osy. Pro AABB definovanou M, N proti jedné definované O, P se neprotínají, pokud (M _x > P _x ) nebo (O _x > N _x ) nebo (M _y > P _y ) nebo (O _y > N _y ) nebo (M _z > P _z ) nebo (O _z > N _z ).

AABB lze také promítnout podél osy, například pokud má okraje délky L a je vystředěn na C a je promítán podél osy N:, a nebo , a kde m a n jsou minimální a maximální rozsahy .
${\ displaystyle r = 0,5L_ {x} | N_ {x} | + 0,5L_ {y} | N_ {y} | + 0,5L_ {z} | N_ {z} | \,}$ ${\ displaystyle b = C * N \,}$ ${\ displaystyle b = C_ {x} N_ {x} + C_ {y} N_ {y} + C_ {z} N_ {z} \,}$ ${\ displaystyle m = br, n = b + r \,}$

OBB je v tomto ohledu podobný, ale je o něco složitější. Pro OBB s L a C, jak je uvedeno výše, a s I, J a K jako základními osami OBB, pak:
${\ displaystyle r = 0,5L_ {x} | N * I | + 0,5L_ {y} | N * J | + 0,5L_ {z} | N * K | \,}$

${\ displaystyle m = C * Nr {\ mbox {a}} n = C * N + r \,}$

Pro rozsahy m, na a o, p lze říci, že se neprotínají, pokud m> p nebo o> n. Takže promítnutím rozsahů 2 OBB podél os I, J a K každého OBB a kontrolou neprotínání je možné detekovat neprotínání. Dodatečnou kontrolou podél křížových součinů těchto os (I ₀ × I ₁ , I ₀ × J ₁ , ...) si lze být jistější, že průnik je nemožný.

Tento koncept určování neprotínajícího se průřezu pomocí osy se vztahuje také na konvexní mnohostěny, avšak místo základních os se používají normály každé polyhedrální plochy a rozsahy jsou založeny na minimálních a maximálních bodových produktech každého vrcholu proti osám. Tento popis předpokládá, že se kontroly provádějí ve světovém prostoru.

Průsečík dvou k -DOP lze vypočítat velmi podobně jako AABB: pro každou orientaci stačí zkontrolovat dva odpovídající intervaly dvou DOP. Stejně jako je DOP zobecněním AABB, je test průniku zevšeobecněním testu překrytí AABB. Složitost testu překrytí dvou DOP je v $O (k)$ . To však předpokládá, že oba DOP jsou uvedeny s ohledem na stejnou sadu orientací. Pokud se jeden z nich otočí, již to není pravda. V takovém případě jedním relativně snadným způsobem, jak zkontrolovat průnik dvou DOP, je uzavřít otočený jeden, druhým, nejmenším uzavírajícím DOP, který je orientován vzhledem k orientacím prvního DOP . Postup je o něco složitější, ale nakonec se rovná i maticovému vektorovému násobení složitosti $O ($ $k$ $)$ . ${\ displaystyle D ^ {1}, D ^ {2}}$ ${\ displaystyle D ^ {2}}$ ${\ displaystyle {\ tilde {D}} ^ {2}}$ ${\ displaystyle D ^ {1}}$

Viz také

Reference

externí odkazy

Ilustrace několika DOP pro stejný model, z epicgames.com

Languages

In other projects