Elengedhetetlen a játékokban, mozi produkciós eszközökben Nélküle kvantum hatás lép fel. Az objektumok áthaladnak a többi objektumon

Bevezetés  Ütközés detektálás  Elengedhetetlen a játékokban, mozi produkciós eszközökben  Nélküle kvantum hatás lép fel 

Az objektumok áthaladnak a többi objektumon

 A valósághű megjelenítés része  Nem tisztán számítógépes grafikai algoritmus  De nagyon fontos  Sok alap építőkocka áll már rendelkezésre  Térbeli adatstruktúrák  Metszés teszt

Technikák  Ray-tracing használata  Nagyon egyszerű  Nem pontos  Nagyon gyors  Néha elegendő  Határoló térfogat hierarchiák  Sokkal bonyolultabb  Lassabb  Pontos eredményt képes adni  Hatékony ütközés detektálás néhány száz objektumra

Általában  Három fő rész  Ütközés detektálás  Ütközés meghatározás  Válasz az üközésre  Az első kettővel foglalkozunk  A harmadik fizikai alapú animációt is magába foglalja  Egyszerű alkalmazásokhoz sugár használata  Határoló térfogat hierarchiák használata két bonyolult

objektum ütközésekor  Mi van akkor ha néhány száz objektumunk van?

Nagyon sok objektumra  Határoló térfogatok ellenőrzése mindegyik

objektumra  Kis méretű halmazra jól alkalmazható  Nem okos  Tfh. n darab mozgó objektumunk van 



 n    2

ellenőrzés

m statikus objektum esetén további mn ellenőrzést kell elvégezni  Ki kell szűrni azokat az objektumokat, melyek ütköznek  Utána lehet más algoritmusokat használni

Ütközés detektálás sugarakkal  Képzeljünk el egy kocsit, amely felfele halad egy lejtőn  Teszteljük az összes kerékhez tartozó háromszöget az út geometriájához 



Bizonyos alkalmazások esetén  Közelíthetünk és még így is jó eredményt kapunk Ötlet  A bonyolult objektumot sugarak halmazával közelítjük

Ütközés detektálás sugarakkal  Mindegyik kerékhez egy sugarat helyezünk el  Számítsuk ki a legközelebbi metszéspontot, t, a sugár

és az út geometriája között  Ha t = 0 

A kocsi az úton van

 Ha t > 0 

A kocsi repül az út felett

 Ha t < 0 

A kocsi mélyszántást csinál az úton

 t értékét használjuk az egyszerű ütközés válaszra

Ütközés detektálás sugarakkal  Egyszerűsített kocsi  De az út nem az  Térbeli adat struktúra az útra nézve  Használjuk a hierarchikus határoló térfogatot vagy BSP fát például  A távolság negatív is lehet a sugár mentén  Pozitív és negatív irányba is keresni kell  A sugár mozgatása visszafele, amíg kívül esik az út geometriájának határoló térfogatán

Másik egyszerűsítés  Néha a 3D-s műveletek 2D-s műveletekké alakíthatóak  Például útvesztő  Egy ember a labirintusban sétál  



Közelíthető egy körrel Ellenőrizzük a kört az útvesztő vonalaival szemben Mozgassuk a falakat a kör sugarával arrébb  A kör középpontjának az ellenőrzése a falakkal

Ütközés detektálás sok objektumra és pontosan

 Nyesés és pontos ütközés  Szimuláció – objektumok mozgása

Összetett objektumok összetett objektumok ellen  Ha pontos eredmény szükséges  Hierarchikus határoló térfogat 

Ha a háromszögek átfedőek  Pontos metszés kiszámítása, ha szükséges

 Hierarchikus határoló térfogat (HHT) felépítésének a

tisztázása

Példa hierarchikus határoló térfogat felépítésére  Felosztható a háromszögek szintjén is Rendezés síkokkal figyelembevéve

vágósík használata

háromszög középpontjait

=

+

Minimális dobozok keresése

…stb.

Pszeudó kód HHT-HHT esetén  Négy eset  Levél-levél csomópont  Belső csomómópont belső  Belső-levél csomópont  Levél-belső csomópont

Megjegyzések a pszeukódra  Befejeződik, ha megtalálja az első ütköző háromszög

pár esetén  Egyszerűen módosítható úgy, hogy folyatatódjon a bejárás és mindegyik párost egy listába rakjuk  Meglehetősen egyszerű forgatást az objektumokra

bevezetni

Kompromisszumok  Határoló térfogat választása  AABB, OBB, k-DOP, gömb  Általában a szűkebb határoló térfogat  lassabb

ellenőrzés

 Kevésbé szűk térfogat a végén több háromszög-

háromszög ellenőrzést ad  Költségfüggvény

Ütközés detektálás sok objektumra  Miért van szükség rá?  Képzeljünk el egy lejtőn leguruló több száz követ  Első szintű ütközés detektálás  A második ellenőrzést kevesebbszer szeretnénk végrehajtani  Tételezzünk fel magas képkocka-képkocka koherenciát 



Azt jelenti, hogy objektum az előző képkockához képest kicsit mozdult el. Elfogadható

Pásztázás és nyesés algoritmus [Ming Lin]  Tfh. az objektumok forgathatók és eltolhatók  Ezután megtalálhatunk egy olyan minimális kockát, amely

mindegyik forgatásra tartalmazza az objektumot  Csináljunk ütközés átfedést háromszor  x, y és z tengelyre

 Csak egy tengelyre vizsgáljuk  Mindegyik kocka egy intervallum erre a tengelyre nézve  si-k és ei-k határozzák meg 

Ahol si < ei ; 0<=i
Pásztázás és nyesés  Az si-k és ei-k értékek növekvő sorrendbe vannak

rendezve egy listában  Járjuk be a listát az elejétől a végéig  Amikor egy s-sel találkozik  Jelöljük meg a listát aktívként egy

active_interval_list listában

 Amikor egy e-vel találkozik  Töröljük a listát az active_interval_list listából  Mindegyik intervallum az active_interval_list

listában átfedő

Pásztázás és nyesés  A rendezés drága O(n*log n)  Kihasználjuk a képkockák koherenciáját  A lista feltehetően nem változik nagyon  Újra rendezés buborék vagy beszúró rendezéssel 

O(n)

Pásztázás és nyesés

Pásztázás és nyesés  Az időbeli koherenciát kihasználva  Mindegyik intervallum párra egy logikai változót definiálunk 

Igaz, ha átfedőek, különben hamis

 Az első rendezés után inicializáljuk őket  Feltesszük, hogy az előző képkockán átfedőek voltak  Ha egy intervallum kezdőpontja helyet cserél a végponttal  A státusza az intervallumnak invertálódik  Ez fordítva is igaz

 A 3 fő tengelyre nézve előállíthatjuk az átfedő

intervallumok listáját  Ha mind a három átfedő, akkor az AABB is átfedő