Játékgeometria. * Hat lecke játékfejlesztőknek oktatási segédanyag, mely a

Játékgeometria * Hat lecke játékfejleszt˝oknek oktatási segédanyag, mely a

Társadalmi Megújulás Operatív Program Határon átnyúló együttmuködés ˝ a szakképzés és a feln˝ottképzés területén c. pályázati felhívás keretében megvalósított Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

2013

TA R TA L O M J E G Y Z É K

Bevezetés

4

1. vektorok és mátrixok 6 1.1. Vektorok 6 1.2. Mátrixok 9 1.3. Lineáris leképezések 12 1.4. Lineáris egyenletrendszer megoldása

14

2. alakzatok megadása 16 2.1. Pont 16 2.2. Egyenes, félegyenes, szakasz paraméterezése 17 2.3. Egyenes és sík egyenlete 18 2.4. Dobozok 21 2.5. Sík és háromszög paraméteres el˝oállítása 23 3. geometriai algoritmusok 26 3.1. Pont lokalizációja 26 3.2. Véges sok síkbeli pont konvex burkának keresése

29

4. alakzatok metszése 33 4.1. Síkok metszése 33 4.2. Egyenes és sík kölcsönös helyzete és kapcsolódó problémák 4.3. Doboz-egyenes metszés 37 5. lineáris transzformációk 39 5.1. Egyenestartó transzformációk mátrix alakja 5.2. Tükrözés 42 5.3. Pont körüli forgatás síkban 45 5.4. Egyenes körüli elforgatás a térben 45 5.5. Vetítés és a szelekció probléma 46

39

6. távolságok kiszámítása és ütközések detektálása 6.1. Pont és sík távolsága 51 6.2. Pont és egyenes távolsága 52 6.3. Két egyenes távolsága 53 6.4. Doboz és sík távolsága 53 6.5. Gömb távolsága doboztól 55 6.6. Doboz távolsága doboztól 56 6.7. Mozgó gömbök ütközése 59

2

34

51

Játékgeometria 3 Irodalomjegyzék Jelmagyarázat Tárgymutató

61 63 63

Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

BEVEZETÉS

A matematika a játékprogramozó legfontosabb fejleszt˝o eszközei közé tartozik. Ha a játékfejleszt˝onek nincsenek bizonyos matematikai területeken biztos ismeretei, akkor napokat vesztegethet el olyan problémák programozásával, amelyek megoldása megfelel˝o matematikai tudással olyan egyszeru, ˝ mint az 1 × 1. Ez a jegyzetet játékfejleszt˝oknek készül, nem matematikusoknak. Két véglet között szeretném megtalálni a megfelel˝o középutat: a legszigorúbb absztrakt matematikai felépítés és a „plug-and-play” típusú receptgyujtemény ˝ között. Ha csak plug-and-play recepteket ismerünk, és nem látunk a recept mögé, aligha tudunk új problémát önállóan hatékonyan megoldani, vagy akár csak a receptet saját problémánkra hatékonyan adaptálni. Milyen matematikai ismeret szükséges a játékfejleszt˝onek? Ennek pontos meghatározása nyilván lehetetlen, jelen jegyzet anyagát pedig er˝os terjedelmi korlátok is befolyásolják. Legel˝oször is az szükséges, hogy biztos fogalmi alapunk legyen vektorokról és mátrixokról. Az olvasó nyilván tanult már lineáris algebrát, az 1. fejezetben leírt anyagot próbáltam a játékfejleszt˝o programozó szemüvegén keresztül megfogalmazni, az anyagba már itt is belesz˝ove néhány gyakorlati problémát. Sokszor magam is rádöbbenek, hogy a matematikusok és a programozók a lineáris algebrát mennyivel másképpen látják. A kedvenc olvasmányom a „programozók szemével” a [GVL13] klasszikus, amely mint ajánlott olvasmány is szerepel a javaslataim között. Másodjára a geometriai algoritmusokat (geometriai programozást) emelem ki. A geometriai programozás az a terület, amely a geometriai problémák számítógépi kezelésével foglalkozik. Tipikus problémája pl. az, hogy adott pontról döntsük el, hogy egy alakzathoz tartozik-e vagy sem, vagy két téglatest a térben diszjunkt-e vagy sem. A jegyzet f˝o profilja a geometriai programozás elemeibe betekintést adni, így tárgyaljuk a következ˝oeket: • alakzatok reprezentálása és metszete (2. és 4. fejezet) • tartalmazás vizsgálata (3. fejezet.) • ütközés vizsgálata (6. fejezet) • konvex burok keresés (3. fejezet.). A geometriai programozás nem csak a problémák megoldásainak algoritmusaival, hanem az algoritmusok vizsgálatával és adatstruktúrák elemzésével is foglalkozik, ebben a jegyzetben ezt nem tekintjük célnak. Az ajánlott olvasnivaló: [PS85, Sza03], de bátorítom az olvasót arra is, hogy a geometriai

4

Játékgeometria 5 algoritmusok keres˝o szóval indítson keresést, s különböz˝o akadémiai, egyetemi oldalakon kiváló magyar nyelvu˝ olvasnivalókat is találunk egyes részproblémákról. A lineáris transzformációk (ezen belül a geometriai transzformációk és a vetítések) ismerete gyakorlatilag a számítógépi geometria minden területén el˝ojön, így a játékprogramozásban is. Az 5. fejezet fedi le ezt a témát. Az irodalom szinte kimeríthetetlen, én egy régi klasszikushoz, [RA90]-hez ragaszkodom. Végezetül néhány olyan terület, amely fontos a játékfejleszt˝onek, de itt nem érintjük. Elemi algebra, trigonometria és kalkulus. A szükséges algebrai és trigonometriai ismeretek ritkán haladják meg az (emelt) középiskolás szintet, talán csak a komplex számokkal és a kvaterniókkal való bánás jelenthet újat. A kalkulus (lényegében: differenciál és integrálszámítás elemei, kitekintéssel a differenciálegyenletekre) minden matematika alkalmazónak alapvet˝o bevezet˝o kurzusa. Szeretnék ehhez egy olyan jegyzetet ajánlani, amely megközelítésében a programozóknak minden bizonnyal tetszeni fog: [Bla11]. Majdnem mindig, amikor különböz˝o matematikai problémákat (pl. egyenletek megoldása, differenciálegyenletek megoldása, differenciálás, stb.) számítógéppel kezelünk, numerikus módszereket alkalmazunk. Ezek ismerete a játékfejlesztésben is fontos lehet. A jegyzetben ezzel a fejezettel nem foglalkozunk, a [PTVF07] könyvben az olvasó kiváló összefoglalót kap a témából. A szabad formájú görbék és felületek modellezésének ismerete minden kétséget kizáróan a játékprogramozó eszköztárába tartozik. Ebben a jegyzetben err˝ol nem lesz szó, a [Kov11] jegyzetben ezt a témát bevezet˝o szinten feldolgoztam, ott további hivatkozásokat is találunk. Az alakzatok mozgását sokszor fizikai elvek alapján írjuk le, így a fizika és ezen belül a szimulációk elmélete és gyakorlata is kiemelt terület, amelyhez szorosan kapcsolódik a statisztika is. A jegyzet megírásához használtam még a fentieken kívül a [Tre04] könyvet. [Fol96] ebben a témában is megkerülhetetlen. Az interneten elérhet˝o források közül jó kiindulópont az Essential Math for Game Programmers oldal. Ezzel a címmel konferenciákat tartanak, honlapot muködtetnek ˝ (link), ahonnan hasznos anyagokat érünk el ingyenesen. A jegyzet ábráinak egy részét (a „2D” ábrákat) GeoGebra-val készítettem, tikz exporttal (link). Más ábrák (ezek a „3D” ábrák) az Asymptote programmal készültek (link). A pszeudokódok olvasásához felhívom a figyelmet arra, hogy az összetartozó programrészek behúzással vannak jelölve, tehát end utasítást nem használok. Végezetül hálásan megköszönöm a lektornak az értékes észrevételeit, amelyek lényegesen javították a tananyag érthet˝oségét.


1 V E K T O R O K É S M ÁT R I X O K

Ebben a részben a kés˝obbi alkalmazások igényeinek megfelel˝oen röviden áttekintjük a vektorokról és mátrixokról tanultakat, els˝osorban a jelölések egyértelmusítése, ˝ no meg az „újrakezd˝ok” kedvéért. 1.1

vektorok

Vektor alatt egy programozó egydimenziós tömböt ért, ebben a jegyzetben mi ugyanebben az értelemben használjuk a vektor szót, csak geometriai elnevezést alkalmazunk. n dimenziós vektorként ebben a jegyzetben a valós rendezett szám n-eseket említjük, azaz Rn elemeit. Ugyanakkor R2 geometriai szempontból a sík egy modellje, R3 pedig a tér egy modellje, tehát Rn elemeit lehet pontoknak és vektoroknak egyaránt nevezni. Ezért jelölésben sem teszünk mindig különbséget pontok és vektorok között, de ha hangsúlyozottan pontra gondolunk, akkor nagy betukkel ˝ (X ∈ Rn ), míg n ha vektorra, akkor kis betukkel ˝ (x ∈ R ) jelöljük az elemeket. A vektorokat tipográfiailag nem fogom aláhúzással jelölni, vagy félkövérrel szedni. (Ha programot írunk akkor sem használjuk ezeket a megkülönböztetéseket.) A programozó valószínuleg ˝ az x vektor i-edik komponensére az x (i ) vagy x [i ] jelölést szereti, mi megtartjuk a matematikusok által gyakrabban használt xi jelölést. Ebben a tananyagban a vektor els˝o komponensét 0 indexszel jelölöm, ahogy a nagyon sok programozási nyelvben ez szokásos. Tehát, ha x ∈ Rn , akkor x = ( x0 , . . . , xn−1 ). Jól ismert, hogy Rn -ben tudunk összeadni, a muveletet ˝ komponensenként elvégezve, s erre az összeadásra Rn kommutatív csoport, ami azt jelenti, hogy a struktúra ugyanolyan tulajdonságokkal rendelkezik, mint a valós számok összeadás struktúrája. A csoport zéruselemét 0-val jelölöm, ha hangsúlyozottan vektorra gondolok, míg O-val, ha pontra. Ez utóbbit origónak is szokás mondani. Ebben a fejezetben a ponttól bonyolultabb geometriai struktúráról nem is lesz szó, a 2. részben ezt a hiányt pótoljuk. Az összeadás segítségével egy geometriai transzformációt értelmezhetünk. Legyem v ∈ Rn rögzített vektor. A Tv : Rn → Rn , X 7→ Tv ( X ) = X + v leképezés Rn eltolása.

6

Játékgeometria 7 X 0 = C + λ( X − C ) X

C

1. ábra. Középpontos nyújtás Rn elemeit számokkal is lehet szorozni (ez a szám-vektor szorzás), a szorzást komponensenként elvégezve. Ennek az R × Rn → Rn leképezésnek egyszeru˝ tulajdonságai: α · ( x + y) = α · x + α · y (α + β) · x = α · x + β · x (αβ) · x = α( β · x ) 1 · x = x, ahol x, y tetsz˝oleges vektorok, α, β pedig tetsz˝oleges valós számok. Az összeadás és a szám-vektor szorzás segítségével a középpontos nyújtást értelmezhetjük. Legyen C ∈ Rn rögzített pont, λ 6= 0 rögzített valós szám. A h(C, λ) : Rn → Rn , X 7→ C + λ( X − C )

(1.1)

transzformáció a C középpontú λ arányú középpontos nyújtás (ld. 1. ábra). Az el˝obbiek mellett Rn -t az teszi hasznossá a számítógépi alkalmazások számára, hogy van benne egy ún. skaláris szorzás, melyet a vektorok megfelel˝o komponensei szorzatának összegével értelmezünk. Matematikailag n −1

x•y =

∑ xi yi .

(1.2)

i =0

Itt x = ( x0 , x1 , . . . , xn−1 ) ∈ Rn , y = (y0 , y1 , . . . , yn−1 ) ∈ Rn . A skaláris szorzás jelét tipográfiailag jól megkülönböztetem a számok szorzásától, vagy a szám-vektor szorzástól. A programozó számára a skaláris szorzás az alábbi algoritmust jelenti: A skaláris szorzás egyik alkalmazása, hogy segítségével kiszámíthatjuk egy vektor hosszát: √ k x k = x • x, x ∈ Rn , (1.3)


Játékgeometria 8 Algoritmus 1.1 Skaláris szorzás Input: x, y Output: x • y d←0 for i = 0 to n − 1 do d ← d + xi yi vagy két pont távolságát: d( P, Q) = k P − Qk =

q

( Q − P) • ( Q − P), P, Q ∈ Rn .

Az (1.3) képletben a jobb oldalon gyökvonás van, amelyet a különböz˝o algoritmusokban igyekszünk elkerülni, ezért ha csak lehet, az

k x k2 = x • x összefüggést használjuk. Két (nem zéró) vektor szöge cos ^( x, y) =

x•y , k x k · kyk

alapján értelmezhet˝o ahol a szög a [0, π ] intervallumban van. Ebben az intervallumban a cos függvény invertálható, így a szög egyértelmuen ˝ definiált.1 Három dimenzióban van még egy vektor muvelet, ˝ amelynek többször gyakorlati hasznát vesszük még, ez a vektoriális szorzás. Az a, b ∈ R3 vektorok a × b-vel jelölt vektoriális szorzata egy olyan a-ra és b-re is mer˝oleges vektor, melynek hosszára fennáll, hogy

k a × b k2 = k a k2 · k b k2 − ( a • b )2 .

(1.4)

(1.4)-b˝ol látjuk, hogy a × b zérusvektor, ha a és b párhuzamosak. Ha a és b nem párhuzamosak, akkor (1.4) és a mer˝olegességi feltétel még nem határozza meg a × b-t egyértelmuen, ˝ hiszen adott hosszúságú, adott síkra mer˝oleges vektor (a sík most az a és b által kifeszített sík) kett˝o is van, a vektor a sík mindkéz oldala felé mutathat. Megkötjük tehát, hogy ( a, b, a × b jobbrendszert alkosson, azaz olyan sorrendben kövessék egymást a vektorok, mint a jobb kéz hüvelyk, mutató és középs˝o ujja, ha a középs˝o ujjat a tenyérre mer˝olegesn tartjuk, a másik két ujjat pedig a tenyér síkjában. Ha a = ( a0 , a1 , a2 ) és b = (b0 , b1 , b2 ), akkor a × b = ( a1 b2 − a2 b1 , a2 b0 − a0 b2 , a0 b1 − a1 b0 ). 1 A figyelmes olvasó elgondolkodhat azon, hogy a jobb oldalon miért szerepel egészen biztosan 0 és 1 közötti szám. Ez a Cauchy-Schwarz egyenl˝otlenség közvetlen következménye:

k x k2 · k y k2 ≥ ( x • y )2 .


Játékgeometria 9

2. ábra. Vektoriális szorzás (1.4)-nek van egy fontos geometriai tartalma: k a × bk megegyezik az a és b által kifeszített paralelogramma területével. (Ld. 2. ábra) 1.2

mátrixok

A vektorokat nem csak egy dimenziós tömbben, hanem összetettebb adattípusban, két dimenziós tömbben is fel lehet írni. Ha egy m · n dimenziós vektor komponenseit m sorba és n oszlopba rendezzük el, akkor egy m × n típusú mátrixot kapunk. Jelölésben az összes m × n típusú mátrixok halmazára az Rm×n jelölést alkalmazom:   a00 ··· a0,(n−1)   .. .. A ∈ Rm×n ⇐⇒ A = ( aij ) =   . . a(m−1),0 · · · a(m−1),(n−1) A jelölés kifejezi azt, hogy az m × n típusú mátrix mint m · n dimenziós vektor tárolható, ahol a vektorban a mátrix elemeit soronként írjuk be. Pl. az a b c d mátrix tárolása történhet a ( a, b, c, d) vektorral. Ha a példa alapján gondolkodunk, akkor rögtön megértjük, hogy miért nem teszünk különbséget az x ∈ Rn vektor, az x ∈ Rn×1 oszlopvektor, vagy R1×n sorvektor között. Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 10 Azonos típusú mátrixok összeadását és egy mátrix skalárral való szorzását komponensenként végezzük el. (Ekkor a mátrixot lényegében vektornak tekintjük.) Speciális mátrix muvelet ˝ a transzponálás, amely egy Rm×n → n × m R leképezés: C = At ⇐⇒ cij = a ji A négyzetes mátrixok transzponálása az alábbi (optimalizált) algoritmussal elvégezhet˝o: Algoritmus 1.2 Transzponálás Input: ( a(i, j)) Output: ( a(i, j))t for i = 0 to n − 2 do for k = i + 1 to n − 1 do swap a(i, k) with a(k, i ) A mátrixok szorzása: r −1

C = AB ⇐⇒ cij =

∑ aik bkj ,

k =0

ahol A ∈ Rm× p , B ∈ R p×n , C ∈ Rm×n . A C mátrix i-edik sorának j-edik eleme megegyezik A i-edik sorának és B j-edik oszlopának skaláris szorzatával. Speciálisan, legyen A ∈ Rm×n , x ∈ Rn = Rn×1 , y ∈ Rm . A sorait jelölje A0 , . . . , Am−1 . Az 1.3. algoritmus adja meg az Ax + y (y = 0 esetén speciálisan Ax) kiszámítását. Algoritmus 1.3 Mátrix-vektor szorzás Input: A = ( A0 , . . . , Am−1 ), x, y Output: y ← Ax + y for i = 0 to m − 1 do yi ← Ai • x + yi A mátrix-mátrix szorzás mindig visszavezethet˝o mátrix-vektor szorzásra, így az el˝obbi algoritmust megfelel˝o ciklusban alkalmazva a mátrix-mátrix szorzást is megkapjuk. A négyzetes mátrix determinánsának általános fogalmát és a kiszámításának különböz˝o algoritmusait nem tekintjük át, mert csak 2 × 2, illetve 3 × 3 típusú mátrixok determinánsára lesz szükségünk, s ezeket egyszeruen ˝ megadhatjuk. a b a b = ad − bc, det = c d c d a00 a01 a02 a10 a11 a12 = a00 a11 a12 − a01 a10 a12 + a02 a10 a11 . a21 a22 a20 a22 a20 a21 a20 a21 a22 Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 11

3. ábra. A körüljárási irány eldöntése A 3 × 3 típusú mátrixok determinánsának egyik geometriai alkalmazása a vektorok vegyes szorzata. Ha a, b, c ∈ R3 vektorok, akkor

| a, b, c| = ( a × b) • c. Kiszámítása

a0 | a, b, c| = b0 c0

a1 b1 c1

(1.5)

a2 b2 . c2

Geometriailag | a, b, c| az a, b, c által kifeszített paralelepipedon el˝ojeles térfogata, ahol az el˝ojel aszerint pozitív, vagy negatív, hogy ( a, b, c) jobbrendszert, vagy balrendszert alkot. Egysíkú vektorok esetén a vegyes szorzat értéke nulla. Bár a konstrukció térbeli, mégis egy síkbeli probléma megoldására ad egyszeru˝ segédeszközt a vegyes szorzat. A kérdés, hogy az adott ABC háromszög (A, B, C ∈ R2 ) csúcsai az óramutató járásával megegyez˝o (negatív), vagy ellentétes (pozitív) körüljárást eredményeznek-e. Az ABC háromszög el˝ojeles területe legyen t. t > 0, ha ABC pozitív körüljárási irányú, t < 0 ellentétes esetben. Az ABC háromszög az xy síkban van, toljuk el a z = 1 síkba (ld. 3. ábra). Az új csúcsok: a = ( a0 , a1 , 1), b = (b0 , b1 , 1), c = (c0 , c1 , 1).

( a, b, c) pontosan akkor jobbrendszer, ha az ABC háromszög pozitív körüljárású. Az (Oabc) tetraéder el˝ojeles térfogata 31 t, és ez a térfogat az ( a, b, c) által kifeszített paralelepipedon térfogatának hatoda. Így 2t = | a, b, c| és


Játékgeometria 12

| a, b, c| > 0 esetén az ABC háromszög felírva a 1 0 t = b0 2 c0

pozitív körbejárású. Determinánssal a1 1 (1.6) b1 1 . c1 1

Rögzített n-re az n × n típusú nem zéró determinánsú mátrixok algebrai értelemben csoportot alkotnak: két ilyen mátrix szorzata szintén nem zéró determinánsú mátrix lesz, a szorzás asszociatív, van egységelem (az egységmátrix) és minden elemnek van inverze. Az n × n típusú, I-vel jelölt egységmatrix elemeire: ( 1 ha i = j aij = 0 ha i 6= j. Az A négyzetes mátrix inverze az a A−1 -el jelölt, A-val azonos típusú mátrix, melyre AA−1 = A−1 A = I. Lineáris algebrai tanulmányainkból tudjuk, hogy egy négyzetes mátrix akkor és csakis akkor invertálható, ha determinánsa nem zérus. Az n × n típusú invertálható mátrixok csoportját (melyet Rn általános lineáris csoportjának is nevezünk) GL(n) jelöli: GL(n) = { A ∈ Rn×n | det A 6= 0}. A mátrix aritmetika témaköréb˝ol utoljára mátrixok inverzének meghatározásával foglalkozunk. Ismét csak a 2 × 2, illetve 3 × 3 típusú mátrixokkal foglalkozunk. Behelyettesítéssel egyszeruen ˝ ellen˝orizhet˝o, hogy

a c

b d

−1

=

1 ad − bc

d −c

−b a b , ∈ GL(2). a c d

A jobb oldalon a tört nevez˝ojében pontosan az invertálandó mátrix determinánsa van, amir˝ol feltettük, hogy nem zéró. A 3 × 3-as esetben legyen A = ( aij ), det A 6= 0. A −1

1.3

 a a − a12 a21 1  11 22 = a12 a20 − a00 a22 det A a10 a21 − a11 a20

a02 a21 − a01 a22 a00 a22 − a02 a20 a01 a20 − a00 a21

 a01 a12 − a02 a11 a02 a10 − a00 a12  . a00 a11 − a01 a10

lineáris leképezések

A mátrix-vektor szorzás (vektort szorzunk balról mátrixszal) a vektoroknak mindig lineáris transzformációját adja. Ez alatt azt értjük, hogy ha A ∈ Rm×n , x ∈ Rn , akkor L A : Rn → Rm , x 7→ L A ( x ) = Ax


Játékgeometria 13

x

k x k cos α · w α

w

4. ábra. Mer˝oleges vetítés, kwk = 1 lineáris leképezés, azaz A( x + y) = Ax + Ay A(αx ) = αAx teljesül minden x, y ∈ Rn vektorra és α ∈ R skalárra. A továbbiakban három fontos példát adunk lineáris leképezésre. Legyen 0 6= w ∈ Rn , és tekintsük a következ˝o leképezést: Rn → Rn , x 7→ pw ( x ) = ( x • w) · w. Ha w egységvektor, akkor pw ( x ) megadja az x vektor w irányú mer˝oleges vetületét (ld. 4. ábra). (x • w el˝ojele aszerint pozitív, vagy negatív, hogy a vetület w irányába mutat, vagy azzal ellentétes.) Mivel a leképezés lineáris, biztosan megadható egy n × n típusú mátrixszal történ˝o balszorzással. Valóban, könnyu˝ elleno˝ rizni, hogy pw ( x ) = wwt · x. (1.7) Ha a térben vagyunk, és w = ( a, b, c), akkor a wwt mátrix     2 a ab ac a b ( a, b, c) = ba b2 bc . c ca cb c2 Mivel az eddigiekben feltételeztük, hogy w egységvektor, az eredményül kapott vetítési mátrix f˝oátlójában a mátrix elemek összege 1. (Emellett a mátrix szimmetrikus is!) Nem okoz különösebb nehézséget a vetítési mátrix felírása akkor sem, ha w nem egységvektor. Ekkor el˝oször w-t normálni kell, és az így kapott Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 14 w/kwk vektorra kell az el˝oz˝o formulákat alkalmazni. Célszeru, ˝ ha a normálást (a kellemetlen gyökvonás miatt) nem is végezzük el, hanem w/kwk-t beírjuk (1.7)-be, így az x 0 vetületre azt kapjuk, hogy x0 =

1 wwt · x, k w k2

tehát a vetítési mátrix általánosan wwt 1 wwt = t . 2 ww kwk

(1.8)

Ne felejtsük el, hogy (1.8)-ban w oszlopvektor. A második példa az el˝oz˝o példán alapul. Az Rn → Rn , x 7→ x − pw ( x ) = x − ( x • w) · w

(1.9)

leképezés geometriai tartalma világos: ha w egységvektor, akkor x − ( x • w) · w megadja az x vektor w irányára mer˝oleges komponensét. Ugyanezt mátrix szorzással (1.7) alapján könnyen felírhatjuk: x 7→ ( I − wwt ) x,

(1.10)

ahol a képletben I az n × n típusú egységmátrix. Az utolsó példánk csak a térben érvényes. Legyen w = ( a, b, c) ∈ R3 . Az Rn → Rn , x 7→ w × x leképezés szintén lineáris leképezés, azaz egy 3 × 3 típusú mátrixszal történ˝o balszorzással megadható. Valóban, egyszeru˝ számítással ellen˝orizhetjük, hogy    0 −c b x1 w×x =  c (1.11) 0 − a   x2  . −b a 0 x3 1.4

lineáris egyenletrendszer megoldása

Ha A ∈ Rn×n egy négyzetes mátrix, b ∈ Rn vektor, akkor az Ax = p egy lineáris egyenletrendszer az ismeretlen x ∈ Rn vektorra. Gyakran lesz szükségünk egy ilyen egyenletrendszer megoldására, ha n = 2. Legyen A = a b , p = ( p0 , p1 ). Ha det A 6= 0, akkor a megoldást az ún. Cramerc d szabállyal kapjuk: p0 b a p0 p1 d c p1 p0 d − bp1 ap − p0 c = = 1 x0 = , x1 = . a b ad − bc ad − bc a b c d c d Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 15 3 egyenletre és három ismeretlenre a Cramer-szabály hasonlóan alkalmazható. Az A ∈ GL(3) mátrix oszlopai legyenek ( A0 , A1 , A2 ), B ∈ R3 , az ismeretlenek X = ( x0 , x1 , x2 ). A lineáris egyenletrendszert tömören az

( A0 , A1 , A2 ) X = B alakban írhatjuk. Mivel A invertálható, ezért ez az egyenletrendszer egyértelmuen ˝ megoldható, és a megoldás: x0 =

| B, A1 , A2 | | A0 , B, A2 | | A0 , A1 , B | , x = , x = . | A0 , A1 , A2 | 1 | A0 , A1 , A2 | 0 | A0 , A1 , A2 |

Mindhárom nevez˝oben az A mátrix determinánsa szerepel.


2 A L A K Z AT O K M E G A D Á S A

A számítógépi grafikában a bonyolultabb alakzatokat gyakran célszeru˝ egyszeru, ˝ elemi alakzatokra bontani, illetve azokkal modellezni. Az 5. ábrán a gömböt háromszögekkel modelleztük, ez segített a láthatóság és árnyékolás problémájának megoldásához. Ebben a fejezetben a pontok, az egyeneses és szakaszok, a síkok és háromszöglemezek, a félsíkok, sávok és dobozok, továbbá a konvex sokszöglemezek megadásával és ezek metszéseivel foglalkozunk. (Sáv alatt a síkban párhuzamos határegyenesu˝ félsíkok metszetét értjük, ha a metszet nem üres, a térben pedig párhuzamos határsíkú félterek metszetét, ha a metszet nem üres. Doboz alatt a síkon téglalapot, a térben téglatestet értünk.) Nagyon gyakran formálisan nincs különbség a síkbeli és a térbeli eset között. Az egyenes paraméteres el˝oállítása a síkban pontosan ugyanazzal a képlettel történik (ld. (2.3)), mint térben, csak a képletben szerepl˝o vektorok az els˝o esetben R2 elemei (rendezett számpárok), a másik esetben R3 elemei (rendezett számhármasok). A fontosabb analógiákat soroltuk fel az 1. táblázatban. 2.1

pont

A legegyszerubb ˝ 2D/3D alakzat a pont, melyet két/három derékszögu˝ koordinátájával adhatunk meg: P ∈ Rn (n = 2 vagy 3).

sík

tér

egyenes paraméterezése egyenes egyenlete félsík egyenlete téglalap

egyenes paraméterezése sík egyenlete féltér egyenlete téglatest

1. táblázat. Fontosabb sík – tér analógiák

16

Játékgeometria 17

5. ábra. A gömböt háromszög lemezekre bontottuk A pont megadásának másik módja, amikor homogén koordinátákat használunk. A P = ( x, y) pont homogén koordinátái [ x1 , x2 , x3 ], ha x=

x1 x2 , y= . x3 x3

(2.1)

Figyeljünk a jelölésre, a homogén koordináták esetén szögletes zárójelet használunk, innen tudjuk megkülönböztetni egy térbeli pont Descarteskoordinátáit a síkbeli pont homogén koordinátáitól. Észrevehetjük, hogy egy pont homogén koordinátái nem egyértelmuek, ˝ ha [ x1 , x2 , x3 ] egy pont homogén koordinátái, akkor az ezzel arányos [λx1 , λx2 , λx3 ] (λ 6= 0) is ugyanazt a pontot határozza meg, mert ha [ x1 , x2 , x3 ]-ra teljesül (2.1), akkor [λx1 , λx2 , λx3 ]-ra is nyilvánvalóan teljesül. Az ( x, y) pont „legegyszerubb” ˝ homogén koordinátái [ x, y, 1]. A definícióban szerepl˝o osztás miatt x3 6= 0. A számolásokban mégis megengedjük az x3 = 0 lehet˝oséget is. Err˝ol tudni kell, hogy az ilyen [ x1 , x2 , 0] hármas nem pontot jelöl, hanem a (− x2 , x1 ) síkbeli irányt. Mivel az irány meghatározásához nem zéró vektor szükséges, ezért x1 és x2 egyszerre nem lehet zéró. A térben a P = ( x, y, z) pont homogén koordinátái [ x1 , x2 , x3 , x4 ], ha x=

x1 x2 x3 , y= , z= . x4 x4 x4

(2.2)

Az arányosságról elmondottak itt is ugyanúgy érvényesek, mint síkban. 2.2

egyenes, félegyenes, szakasz paraméterezése

Egy egyenest vagy egy szakaszt geometriailag két pont határoz meg. Ha megadunk két pontot, akkor ezek egyértelmuen ˝ meghatározzák a rájuk illeszked˝o egyenest, vagy azt a szakaszt, amelynek határpontjai éppen az Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 18 adott pontok. Legyenek P0 , P1 ∈ Rn a pontok (P0 6= P1 ) ekkor a rájuk illeszked˝o egyenes pontjai (és csakis azok) el˝oállíthatók az alábbi formában X = tP1 + (1 − t) P0 ,

t ∈ R.

(2.3)

A (2.3) képletet úgy kell értelmezni, hogy ha t helyére bármilyen valós számot beírunk, akkor a P0 P1 egyenes egy pontját kapjuk, illetve az egyenes minden pontjához találunk ilyen számot. A (2.3)-t könnyen tudjuk értelmezni, ha átalakítjuk: X = tP1 + (1 − t) P0 = P0 + t( P1 − P0 ),

t ∈ R,

azaz a P0 -ra illeszked˝o P1 − P0 irányvektorú egyenesr˝ol van szó. A (2.3) képletet a P0 P1 egyenes paraméteres el˝oállításának nevezzük. Ha (2.3)-ben t ∈ [0, 1], akkor a P0 P1 szakasz pontjait (és csakis azokat) kapjuk meg: X = tP1 + (1 − t) P0 , t ∈ [0, 1]. (2.4) t = 0 adja a szakasz P0 határpontját, míg t = 1 a P1 határpontot. A 0 < t < 1 számok a szakasz bels˝o pontjai. Ha (2.3)-ben t ∈ [0, ∞), akkor a P0 P1 félegyenes pontjait (és csakis azokat) kapjuk meg. 2.3

egyenes és sík egyenlete

Az egyenes (2.3) paraméteres el˝oállítása mellett a síkban az egyenes egyenletét is gyakran használjuk. Ehhez az egyenest egy P0 ∈ R2 pontjával és az egyenesre mer˝oleges (nem zéró) u ∈ R2 vektorral, az egyenes ún. normálvektorával adjuk meg. Vegyük szemügyre a 6. ábrát! Az X pont akkor és csakis akkor illeszkedik a P0 ponton áthaladó u normálvektorú egyenesre, ha α = π/2, vagy X = P0 , azaz, ha

( X − P0 ) • u = 0.

(2.5)

Csak arra kell gondolni, hogy

( X − P0 ) • u = k X − P0 k · kuk · cos α,

(α ∈ [0, π ]),

(2.6)

továbbá a [0, π ] intervallumban a cos függvény π/2 nél zérus. A (2.5) képletet a P0 ponton áthaladó u normálvektorú egyenes egyenletének nevezzük. A tömör vektoros formában felírt (2.5) egyenletben azonnal ráismerünk a középiskolában tanult formára. Ha P0 = ( x0 , y0 ) és u = ( A, B), valamint a „futó” pont X = ( x, y), akkor X − P0 = ( x − x0 , y − y0 ) és a skaláris szorzást elvégezve az alábbi ismer˝os egyenletet kapjuk: A( x − x0 ) + B(y − y0 ) = 0 ⇐⇒ Ax + By = Ax0 + By0 .


(2.7)

Játékgeometria 19

X

u α P0

6. ábra. Az egyenes egyenlet Hogyan tárolhatunk a programunkban egy síkbeli egyenest? Ha a paraméteres el˝oállításra gondolunk, akkor négy adat kell hozzá, vagy az egyenes két pontjának két-két Descartes-koordinátája, vagy egy pont és egy irányvektor, azaz ismét négy adat. Ha az egyenes (2.7) egyenletére gondolunk, akkor láthatjuk, hogy elegend˝o egy rendezett számhármas is, az egyenletben szerepl˝o három szám: A, B és C = −( Ax0 + By0 ). Az [ A, B, C ] hármas „homogén módon” viselkedik, azaz [λA, λB, λC ]-vel felírt λAx + λBy + λC = 0 nyilvánvalóan ugyanannak az egyenesnek az egyenlete, mint amit az [ A, B, C ] hármas meghatároz. Éppen ezért az [ A, B, C ] hármast az Ax + By + C = 0 egyenes homogén koordinátáinak nevezik. Mivel ( A, B) az egyenes normálvektora, így A és B egyszerre nem zéró. Az [ A, B, C ] homogén koordinátákkal rendelkez˝o egyenes egy irányvektora (− B, A), így iránya [− B, A, 0]. Homogén koordinátákat használva az alapvet˝o síkbeli illeszkedési és metszési feladatok egyszeruen ˝ megoldhatók. Ezek összefoglalásához állapodjunk meg abban, hogy ha X ∈ R2 egy pont, akkor ennek egy homogén koordináta hármasát x ∈ R3 jelöli (azaz ugynannál a pontnál ugyanaz a betu, ˝ csak nagy betu˝ – kis betu˝ változatban.) illeszkedés A P pont akkor és csakis akkor illeszkedik az u homogén koordinátákkal rendelkez˝o egyenesre, ha p • u = 0.


Játékgeometria 20

7. ábra. Sík normálvektora összekötés. A P, Q pontokra illeszked˝o egyenes homogén koordinátái p × q. metszés. Ha u és v két egyenes homogén koordinátái, akkor metszéspontjuk homogén koordinátái u × v. Ha a két egyenes párhuzamos lenne, akkor u × v nem pont, hanem irány, a két egyenes közös iránya. párhuzamos húzás. A P pontra illeszked˝o, u homogén koordinátákkal rendelkez˝o egyenes homogén koordinátái p × (−u2 , u1 , 0), azaz P-t összekötjük az egyenes irányával. A részleteket a gyakorlati feladatok megoldásával látjuk. A (2.5) egyenletnek van egy másik szépsége: változatlan formában érvényes térben is, pontosabban, ha P0 ∈ R3 tetsz˝oleges pont és u ∈ R3 nem zéró vektor, akkor (2.5) megadja a P0 pontra illeszked˝o, u normálvektorú sík egyenletét. (Egy sík normálvektorán a síkra mer˝oleges nem zéró vektort értjük. Ld. a 7. ábrát!) Ha P0 = ( x0 , y0 , z0 ) és u = ( A, B, C ), akkor az el˝obbiekhez hasonló módon a sík egyenlete: A( x − x0 ) + B(y − y0 ) + C (z − z0 ) = 0.


Játékgeometria 21 C D H IG F B A

8. ábra. Doboz el˝oállítása sávok metszeteként Most térjünk vissza a (2.6) egyenlethez! Ha α hegyesszög, azaz cos α > 0, az azt jelenti, hogy X az egyenes (vagy sík) ugyanazon oldalára1 esik, mint P0 + u. Így az egyenes (sík) u iránya által meghatározott oldala (beleértve az egyenest/síkot is) { X ∈ Rn | ( X − P0 ) • u ≥ 0}, (2.8) míg az ellentétes oldal

{ X ∈ Rn | ( X − P0 ) • u ≤ 0}. 2.4

(2.9)

dobozok

A (2.8) és (2.9) formulák megértése után elérkeztünk a számítógépi alkalmazások egyik legfontosabb alakzatához, a dobozhoz. Doboz alatt a síkban téglalapot, a térben téglatestet értünk. A téglalapot mint egymásra mer˝oleges irányú sávok metszetét fogjuk fel (8. ábra). Hogyan adhatunk meg egy sávot? A sáv középpárhuzamosán vegyünk fel egy tetsz˝oleges pontot, melyet jelöljön C. C-b˝ol a sáv egyik határegyeneséhez mutató mer˝oleges vektor legyen u. (9. ábra.) A (C, u) pár

1 Egy síkbeli egyenes a síkot két félsíkra, a sík a teret két féltérre bontja. Ezeket a (zárt) félsíkokat/féltereket neveztük az egyenes/sík oldalainak.


Játékgeometria 22

u

C

9. ábra. Sáv el˝oállítása a sávot meghatározza. Az két határegyenes egy-egy pontja így C ± u, míg mindkét egyenes normálvektora u. A két határegyenes egyenlete tehát

( X − (C ± u)) • u = 0 ⇐⇒ ( X − C ) • u = ±kuk2 . A sáv maga az ( X − C ) • u ≤ kuk2 félsík és a ( X − C ) • u ≥ −kuk2 félsík metszete, azaz azon X pontok halmaza, melyekre

−kuk2 ≤ ( X − C ) • u ≤ kuk2

(2.10)

teljesül. A téglalapot ezek után megadhatjuk C középpontjával és a fél oldalvektorokkal, azaz a középpontból két szomszédos oldalhoz mer˝olegesen mutató egymásra mer˝oleges ( a, b) vektorpárral. A téglalap csúcsait a C±a±b vektorok adják, ahol a + és − el˝ojelek minden lehetséges (ismétléses) variációjára szükség van. A téglalap (lemez) pontjai (és csakis azok) pedig eleget tesznek az alábbi relációknak:

−k ak2 ≤( X − C ) • a ≤ k ak2 −kbk2 ≤( X − C ) • b ≤ kbk2 .

(2.11)

Térben minden analóg, a téglatestet a C középpontjával és az egymásra páronként mer˝oleges fél élvektorokkal adjuk meg. Legyenek ezek ( a, b, c). Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 23 Így téglatest csúcsai C ± a ± b ± c, a tömör téglatest pontjai (beleértve a határoló lapokat is) és csakis azok eleget tesznek a

−k ak2 ≤( X − C ) • a ≤ k ak2 −kbk2 ≤( X − C ) • b ≤ kbk2

(2.12)

−kck2 ≤( X − C ) • c ≤ kck2 relációknak. A kés˝obbieken azt is megtanuljuk, hogyan kell eldönteni, hogy egy X0 pontból X1 irányban kil˝ott lézersugár eltalál-e egy (C, a, b, c) dobozt. 2.5

˝ sík és háromszög paraméteres el oállítása

Ha megadunk három nem egy egyenesre illeszked˝o pontot, akkor ezek egyértelmuen ˝ meghatározzák azt a síkot, amely mindhárom pontra illeszkedik, illetve azt a háromszög lemezt, amelynek csúcsai az adott pontok. A sík a P0 pontra illeszkedik, és a P1 − P0 , P2 − P0 vektorok feszítik ki, azaz ezen vektorok lineáris kombináció adják meg a síkban reprezentálható vektorokat (és csakis azokat). Így a sík pontjaira X = P0 + s( P1 − P0 ) + t( P2 − P0 ),

s, t ∈ R.

(2.13)

Ha a (2.13)-ben s, t ∈ [0, 1], akkor a P0 P1 P2 háromszög lemez pontjait (és csakis azokat) kapjuk. Rendezzük át a (2.13) el˝oállítás jobb oldalát! X = (1 − s − t) P0 + sP1 + tP2

(2.14)

Ha ( P0 , P1 , P2 ) nem kollineáris rendezett ponthármas, akkor (2.14) alapján megállapíthatjuk, hogy van olyan (α, β, γ) rendezett számhármas, hogy X = αP0 + βP1 + γP2 , α + β + γ = 1.

(α, β, γ)-t X normált baricentrikus koordinátáinak nevezzük ( P0 , P1 , P2 )-ra vonatkozóan. Ha síkban vagyunk (Pi ∈ R2 ), akkor az el˝oz˝o egyenletrendszert megolghatjuk pl. a következ˝o módon. A problémát tömören felírva (homogén koordinátákkal):   α X P0 P1 P2   X= . β = 1 1 1 1 γ Cramer-szabállyal megoldva (ld. 15. oldalt) X P1 P2 P0 X P2 P0 P1 X 1 1 1 1 1 1 1 1 1 , β = , γ = . α= P0 P1 P2 P0 P1 P2 P0 P1 P2 1 1 1 1 1 1 1 1 1 Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 24

P2

t1

t0 X

t2 P0

P1

10. ábra. Baricentrikus koordináták: ha a P0 P1 P2 háromszög el˝ojeles területe t, akkor α = t0 /t, β = t1 /t, γ = t2 /t és X = αP0 + βP1 + γP2 . (1.6)-ból tudjuk, hogy a fenti megoldásban a számlálókban és a nevez˝okben szerepl˝o determinánsoknak egyszeru˝ geometriai jelentése van: megegyeznek a megfelel˝o háromszög el˝ojeles területének kétszeresével: az X pontot a háromszög csúcsaival összekötve három (esetleg elfajuló) háromszöget kapunk. A részháromszög és az eredeti háromszög területének aránya adja a megfelel˝o normált baricentrikus koordinátákat (ld. 10. ábra). A (2.13) és (2.3) formulák hasonlítanak abban, hogy a szám együtthatók összege 1. A szakasz és a sík el˝oállítása esetében ráadásul a szám együtthatók mind nem negatívak. Vektorok olyan lineáris kombinációját, melyben az együtthatók összege 1 és az együtthatók nem negatívak, konvex (lineáris) kombinációnak nevezzük. Úgy is fogalmazhatunk, hogy a szakasz a határpontjai összes konvex kombinációinak halmaza, míg a háromszög lemez a csúcsai összes konvex kombinációinak halmaza. Általánosan, ha P0 , P1 , . . . , Pn egy pontsorozat, akkor a pontok összes konvex kombinációi ( ) X=

n

n

i =0

i =0

∑ αi Pi , | αi ≥ 0, ∑ αi = 1,

a P0 , P1 , . . . , Pn pontrendszer konvex burkát adják. (Egy alakzat konvex burka az a legszukebb ˝ konvex halmaz, amely az adott halmazt tartalmazza.) Véges sok síkbeli pont konvex burka (zárt) sokszöglemez, (elfajuló esetben, azaz egy egyenesre illeszked˝o pontok esetén szakasz) melynek csúcsai (szakasz esetén határpontjai) az adott pontok közül kerülnek ki. Ez utóbbi pontokat nevezik extremális pontoknak. Térben véges sok pont konvex burka konvex poiédertest (elfajuló esetben egy síkra illeszked˝o pontok esetén konvex sokszöglemez, kollineáris pontok esetén szakasz), melynek csúcsai Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 25 (szakasz esetén határpontjai) az adott pontrendszerb˝ol kerülnek ki, s melyeket ismét extremális pontoknak nevezünk. A 2.5. fejezet két problémát vet fel. 1. A pont lokalizációjának problémája: adott pontról eldönteni, hogy adott háromszöglemezben van-e 2. A konvex burok keresés problémáját: adott pontrendszer extremális pontjainak megkeresése. Mindkét kérdés egy mára önállóvá vált tudományág, melyet magyarul geometriai algoritmusok néven szokták meghatározni,2 fontos problémája. A következ˝o fejezetben foglalkozunk a megoldásukkal.

2 Angolul: Computational Geometry


3 GEOMETRIAI ALGORITMUSOK

3.1

pont lokalizációja

Hogyan tudjuk eldönteni, hogy egy pont benne van-e egy háromszöglemezben vagy sem? Ennek a fontos problémának a megoldására több megoldást is adunk. El˝oször egy direkt algoritmust adunk, amelyben kiszámítjuk a háromszög síkjában fekv˝o pont normált baricentrikus koordinátáit a háromszöglemezre vonatkozóan, s a koordinátákból eldöntjük a tartalmazási kérdést. Ezt az eljárást nagyon könnyu˝ lesz a térre átvinni. Legyen adva az X0 X1 X2 háromszög és a síkjában egy D pont. Mivel D a háromszög síkjában van, biztosan vannak olyan s, t együtthatók, hogy D = (1 − t − s) X0 + sX1 + tX2 . Rendezve D − X0 = s ( X1 − X0 ) + t ( X2 − X0 ) .

(3.1)

(3.1) egy lineáris egyenletrendszer. Az ismeretlenek s és t, az egyenletek száma annyi, amennyi koordinátája van a vektoroknak. A további képletek egyszerusítése ˝ kedvéért vezessük be a következ˝o jelöléseket: D − X0 = w, X1 − X0 = u, X2 − X0 = v. Tehát az egyenletrendszer w = su + tv.

(3.2)

Síkban két egyenlet és két ismeretlen van, a megoldást rögtön kapjuk Cramer-szabállyal: w0 v 0 u 0 w0 w1 v 1 u 1 w1 , t = , s= u0 v0 u0 v0 u1 v1 u1 v1 ahol w = (w0 , w1 ), u = (u0 , u1 ), v = (v0 , v1 ). Mindkét tört nevez˝oje ugyanannyi (csak egyszer kell kiszámolni). Ez a közös nevez˝o bizonyosan nem nulla, mert X1 − X0 és X2 − X0 nem párhuzamosak.

26

Játékgeometria 27

P

D

11. ábra. A horizontális egyenes D el˝ott lép be a sokszögbe. Csúcson is átmegy és ez a csúcs a számolásba kétszeresen számít. Az összes keresztezések száma az ábrán páratlan, tehát D a sokszög belsejében van. Térben (3.2) megoldásához szorozzuk az egyenletet skalárisan u-val és v-vel: w • u = s(u • u) + t(v • u) w • v = s ( u • v ) + t ( v • v ). Innen a megoldás (s, t)-re szintén a Cramer-szabály alapján: w • u v • u u • u w • u w • v v • v u • v w • v , t = . s= u • u v • u u • u v • u u • v v • v u • v v • v D akkor és csakis akkor az X0 X1 X2 zárt háromszöglemez pontja, ha 0 ≤ s ≤ 1 és 0 ≤ t ≤ 1. A második algoritmus csak síkban muködik, ˝ viszont nem csak háromszöglemezre, hanem tetsz˝oleges egyszeru˝ sokszöglemezre. (Emlékeztet˝oül: az egyszeru˝ sokszög oldalai egymást nem metszik, minden csúcsban két oldal találkozik. Az egyszeru˝ sokszög a sík (sokszögvonaltól különböz˝o) pontjait két osztályba sorolja, a sokszög külsejébe és belsejébe.) Azt teszteljük, hogy a sík egy D pontját tartalmazza-e a sokszög belseje. Gyakorlatiasabb nyelven megfogalmazva. Egy síkbeli egyszeru˝ sokszöget megadunk csúcsaival: P0 , P1 , . . . , Pn−1 . A felhasználó egérrel kattint a képerny˝on. El kell dönteni, hogy a kattintás helye benne van a sokszög belsejében, vagy nincs. Húzzunk a D ponton keresztül egy ` horizontális, azaz az x tengellyel párhuzamos egyenest (11. ábra). El˝oször tegyük fel, hogy az egyenes nem megy át csúcson. Induljunk a sokszögön kívülr˝ol a mínusz végtelen irányától a plusz végtelen irányába, s akkor álljunk meg, ha elértük a pontot. Amikor a sokszög valamelyik oldalát el˝oször keresztezzük, akkor beléptünk Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 28 a sokszög belsejébe. A következ˝o keresztezésnél kilépünk. Számoljuk a keresztezéseket! Ha a pontba érve a keresztezések száma páratlan, akkor úgy értünk D-hez, hogy utoljára beléptünk a sokszög belsejébe, tehát a sokszöglemez tartalmazza D-t. Ha a keresztezések száma páros (beleértve 0-t), akkor D kívül van a sokszöglemezen. (Úgy értünk D-hez, hogy közben utóljára kiléptünk a sokszög belsejéb˝ol, vagy egyáltalán be sem léptünk.) Ha a horizontális egyenes csúcsot tartalmaz, akkor képzeljük el, hogy gondolatban az egyenest D körül elforgatjuk az óramutató járásával ellentétesen épp annyira, hogy az egyenes már ne menjen át a csúcson, de új csúcsot se érjen el. A csúcs annyiszorosan számít, ahány metszéspont keletkezik az elforgatás után. (Ez a szám kett˝o, egy vagy nulla lehet. A 11. ábrán két metszéspont keletkezett az elforgatás után, vázoljuk a többi lehetséges esetet is!) Azt a következtetést vonhatjuk le, hogy egy oldalszakasz figyelmen kívül hagyandó a keresztezések számlálásánál, ha mindkét csúcs rajta van `-n, vagy ha a metszés a kisebb ordinátájú1 határpontnál történt. Az algoritmus elvégzéséhez szükséges számítás mindössze annyi, hogy egy horizontális egyenes és egy szakasz metszéspontját ki tudjuk számolni. Legyen D második koordinátája d, Pi = ( xi , yi ). A Pi Pi+1 szakaszt tekintjük. (Az utolsó szakasz Pi+1 P0 , ezért a csúcsokat a

( P0 , . . . , Pn−1 , P0 = Pn ) szerkezetben érdemes megadni.) Ha yi = yi+1 , akkor a szakasszal nem kell foglalkozni. Egyébként a szakasz paraméteres el˝oállításából a metszési probléma: Xi + t( Xi+1 − Xi ) = D + s · (1, 0).

(0, 1)-el skalárisan szorozva: yi + t(yi+1 − yi ) = d, ahonnan t=

d − yi . y i +1 − y i

Ha 0 ≤ t ≤ 1, akkor a horizontális egyenes metszi a szakaszt, és az Mi metszéspont abszcisszája2

( Mi ) 1 = x i +

d − yi ( x − x i ), y i +1 − y i i +1

míg ordinátája (természetesen)

( Mi ) 2 = y i +

d − yi (y − yi ) = d. y i +1 − y i i +1

Ha ( Mi )1 < d és ( Mi )2 > min{yi , yi+1 }, akkor a metszéspontot számláljuk. 1 ordináta = második koordinta 2 abszcissza = els˝o koordináta


Játékgeometria 29 Algoritmus 3.1 Sokszöglemez bel˝o pontjára kattintottunk-e? Input: ( P0 , . . . , Pn−1 , P0 = Pn ), D L←0 for i = 0 to n − 1 do if yi+1 6= yi and ( Mi )1 < d and ( Mi )2 > min{yi , yi+1 } then L ← L+1 if L páros then D nem bels˝o pont else D bels˝o pont

3.2

véges sok síkbeli pont konvex burkának keresése

A konvex burok keresése a geometriai számítások egyik központi problémája, több algoritmus ismert rá. Egy konkrét alkalmazást említek: a szabadformájú görbék modellezésénél használt több görbetípusra is igaz az ún. konvex burokban maradás problémája, azaz a görbe a kontrollpontok konvex burkában halad. (Részletesebben lásd például a [Kov11] jegyzet 3. és 4. fejezetét.) Így ha ismerjük a kontrollpontok konvex burkát, akkor a metszési és láthatósági feladatokat el˝oször a konvex burokra ellen˝orizzük. Ha a kontrollpontok konvex burka nem látható, akkor a görbe sem látszik. Ha két görbe kontrollpontjaiknak konvex burka nem metsz˝o, akkor a görbék sem metsz˝ok. Sok algoritmus használja az alábbi fontos észrevételt. Ha P0 = ( x0 , y0 ), P1 = ( x1 , y1 ) és P2 = ( x2 , y2 ) síkbeli pontok, akkor a P0 P1 P2 (esetleg elfajuló) háromszög el˝ojeles területe (ld. (1.6)) x y0 1 1 0 t( P0 P1 P2 ) = x1 y1 1 . (3.3) 2 x2 y2 1 Ha a három pont kollineáris, akkor a determináns értéke 0. Egyébként az el˝ojel úgy értend˝o, hogy ha P0 P1 P2 balra kanyarodik P1 -nél, akkor a determináns pozitív el˝ojelu, ˝ ha jobbra kanyarodik, akkor negatív el˝ojelu. ˝ A konvex burok keres˝o algoritmusoknk alapvet˝oen két problémát kell megoldaniuk: 1. kiválasztani az extremális pontokat, 2. ezeket megfelel˝o sorrendbe rendezni. A következ˝okben ismertetett konvex burok keres˝o algoritmus a Jarvisalgoritmus. Azon az észrevételen múlik, hogy a megadott ponthalmazból kiválasztott két pont összeköt˝o szakasza akkor és csakis akkor a konvex


Játékgeometria 30

12. ábra. Pontrendszerek extremális pontjai (pirossal) burok oldalszakasza, ha az összes többi pont a szakaszon, vagy a pontokat összeköt˝o egyenes ugyanazon oldalán van. n pont (n2 ) egyenest határoz meg. Minden egyeneshez (legrosszabb esetben) n − 2 pont elhelyezkedését kell megvizsgálni. Vegyük észre, hogy ha találtunk egy extremális pontot, akkor a konvex burok hozzá tartozó (egyik) oldalának másik végpontja is extremális pont, tehát extremális pontból kiindulva mindig találunk egy következ˝o extremális pontot. (Ez az észrevétel az extremális pontok sorrendjének problémáját meg is oldja.) A legkisebb abszcisszájú pont (vagy azok egyike) biztosan extremális pont. Ha több legkisebb abszcisszájú pont van, akkor közülük a legkisebb ordinátájú biztosan extremális pont. A 12. ábrán szemléltettem, hogy milyen problémák vet˝odnek fel, amelyekre a konvex burok keres˝o algoritmusnak figyelnie kell: kollineáris pontok esetén két másik adott pont között lev˝o pont nem lehet extremális pont (bal oldali ábra); el˝ofordul, hogy az adott ponthalmaz egy egyenesre illeszked˝o pontrendszer. Kétfajta tesztet alkalmazunk. Mindkét tesz elválasztásról szól, az els˝o egy dimenzióban, a második két dimenzióban. Az egy dimenziós teszt a „között van” teszt. Ha t( P0 P1 X ) = 0, azt kell eldönteni, hogy X a P0 P1 szakaszon van vagy sem, vagyis X a P0 , P1 pontok között van, vagy sem. A párhuzamos vetítés a „között van” relációt megtartja. Így csak az abszcisszákat (vagy ordinátákat) kell vizsgálni. Legyen P0 = ( x0 , y0 ), P1 = ( x1 , y1 ), X = ( x, y). x0 6= x1 esetén X pontosan akkor nincs P0 és P1 között, ha x < min{ x0 , x1 } vagy x > max{ x0 , x1 }. Ha x0 = x1 , akkor ordinátákra végezzük el ugyanezt a tesztet. A második teszt a (két dimenziós) elválasztás teszt. Azt kell tesztelnünk, hogy vannak-e az adott pontok között olyanok, amelyeket két kiválasztott pont, P0 P1 elválaszt. Ezt megtehetjük úgy, hogy csak a P0 P1 -gyel nem kollineáris pontokat vizsgáljuk, kiszámítjuk ebb˝ol a halmazból egy X0 pontra t( P0 P1 X0 ) el˝ojelét, majd az összes többi X pontra teszteljük t( P0 P1 X ) el˝ojelét. Ha minden el˝ojel megegyezik t( P0 P1 X0 ) el˝ojelével, akkor minden pont P0 P1 azonos oldalán van. Legyen a kiválasztott két pont Pi és Pj (i 6= j), az el˝obbiek szerint feltehet˝o, hogy Pi extremális pont. Az vizsgáljuk, hogy Pi Pj a konvex burok oldalAz oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 31 szakasza-e (i 6= j). (Röviden úgy fogom használni, hogy „jó” szakasz.) Ha igen, akkor Pj extremális pont. Legyen S a Pi -vel és Pj -vel kollineáris pontok halmaza (beleértve Pi -t és Pj -t is), míg T a Pi -vel és Pj -vel nem kollineáris pontok halmaza. 1. El˝oször az S halmaz pontjaira ellen˝orizzük, hogy belül vannak-e a Pi Pj szakaszon. for X ∈ S do if ¬ Pi − X − Pj then Pj nem extremális pont 2. Ha Pj -t nem zártuk az els˝o lépésben m. for k = 1 to m − 1 do if sgn t( Pi Pj Tk ) 6= sgn t( Pi Pj T0 ) then Pi Pj nem jó szakasz és Pj -t kizárjuk

ki,

legyen

|T |

=

3. Ha Pj -t nem zártuk ki a második lépésben sem, akkor Pj extremális pont. (Ha Pi Pj nem jó szakasz, attól még Pj lehet extremális pont.) Példaként a korábban már szerepelt „öt pöttyös” alakzaton illusztrálom az algoritmust. A pontokat el˝oször az abszcisszák szerint növekv˝o sorrendbe rendeztem, ahol azonos abszcisszák vannak, ott az ordináták szerint is rendeztem. P1

P5

P3

P0

P2

P4

A legkisebb abszcisszájú pontok között a legkisebb ordinátájú pont extremális pont lesz. P1

P5

P3

P0

P2

P4

P0 P1 jó szakasz, s így P1 extremális pont, mert a P0 P1 egyenesen nincs további pont a pontrendszerb˝ol, és P0 P1 nem választ el pontokat az adott pontrendszerb˝ol. P1 P2 nem jó szakasz, mert a P0 és P3 pontokat elválasztja. A P3 pontot azért kell kizárni, mert elválasztja P4 -et és P1 -et. P1 P4 sem jó szakasz, mert Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 32 P1

P5 P1

P3

P0

P2

P5 P1

P3

P4 P0

P2

P5

P3

P4 P0

P2

P4

elválasztja a P0 és P5 pontokat. Végül P1 P5 megfelel˝o szakasz, és P5 extremális pont. P1

P5

P3

P0

P2

P4

P5 mellé már csak a P2 P3 , P4 pontok közül kell társat találni. P2 és P3 könnyen kiesnek, mert P2 megbukik a két dimenziós elválasztás teszten, P3 már az egy dimenziós elválasztás teszten (a „között van” teszten). P4 megfelel˝o. P4 -b˝ol kiidulva csak a P2 és P3 pont jöhet szóba, de P2 -t a „között van” teszt miatt, P3 -t a két dimenziós elválasztás tesz miatt kell kizárni: valamennyi extremális pontot megtaláltuk.


4 A L A K Z AT O K M E T S Z É S E

4.1

síkok metszése

Ha két sík normálvektora nem párhuzamos, akkor a két sík metszésvonala egyenes. Hogyan tudjuk meghatározni két sík metszésvonalát? Legynek a síkok normálvektorai w1 és w2 , a síkok egyenletei tehát w1 • X = d 1

(4.1)

w2 • X = d 2 . (4.1)-ben három ismeretlen és két egyenlet van. Ha v = w1 × w2 6= 0, akkor az egyenletrendszernek van megoldása, s a megoldások halmaza egy egyenes, a két sík metszésvonala, melynek irányvektora v. Egy pontot kell még találnunk a megoldás halmazban. Az irányvektor valamelyik koordinátája (mondjuk az i-edik) biztosan nem nulla. X-ben az i-edik koordinátát 0-nak helyettesítve (4.1)-ben már csak két ismeretlen lesz, és az egyenletrendszert egyértelmuen ˝ meg tudjuk oldani. (4.1) megoldásaként kapjuk a metszésvonal pontjának hiányzó két koordinátáját. Három sík kölcsönös helyzetét vizsgálva, a síkok normálvektorait jelölje w1 , w2 , w3 ; a síkok egyenletei w1 • X = d 1

(4.2)

w2 • X = d 2 w3 • X = d 3 . Legyen W = (w1 , w2 , w3 )t (azaz W i-edik sora wi ), D = (d1 , d2 , d3 )t ∈ R3×1 . A (4.2) lineáris egyenletrendszer mátrix alakja WX = D. Az egyenletrendszer megoldható, ha rang W = rang(W, D ). A megoldható esetben a megoldástér dimenziója (3 − rang W ), azaz lehet pont, egyenes, vagy sík. A megoldást általánosan a Gauss-eliminációval tudjuk kezelni. Ha rang W = 3, azaz a három normálvektor nem egy síkban reprezentálható, akkor X = W −1 D. Jóllehet a Gauss-elimináció az inverz meghatározására is alkalmazható, célszeru˝ direkt megoldást adni a problémára, hogy az egymást követ˝o eliminációs lépések következtében fellép˝o numerikus hibaterjedést elkerüljük. W

33

Játékgeometria 34 inverzét a kifejtési tétel alapján, a „szorzótársak módszerével” képezve, a megoldást a következ˝oképpen adhatjuk meg: W −1 D =

4.2

d 1 ( w2 × w3 ) − d 2 ( w3 × w1 ) + d 3 ( w1 × w2 ) . det(w1 , w2 , w3 )

egyenes és sík kölcsönös helyzete és kapcsolódó problémák

Legyen a sík egyenlete w • X = d, az egyenes paraméteres el˝oállítása X = X0 + tv. Ha v • w 6= 0, akkor az egyenes metszi a síkot. Valamely t ∈ R értékre X = X0 + tv kielégíti a sík egyenletét:

( X0 + tv) • w = d, ahonnan t kifejezhet˝o: t=

d − w • X0 , w•v

azaz a metszéspont X = X0 +

d − w • X0 v. w•v

(4.3)

Háromszöglemez és szakasz metszése Az eddig ismertetett problémák közül a „legvalószerubb”: ˝ a síkok, egyenesek „végtelen” alakzatok, s mint ilyenek absztrakciók. Els˝o módszerként a síkot egyenletével kezeljük. A háromszög csúcsai legyenek P0 , P1 , P2 , a szakasz határpontjai X0 , X1 . A háromszöglemez síkjának egyenletét P0 P1 P2 ismeretében fel tudjuk írni: w • X = d, ahol w = ( P1 − P0 ) × ( P2 − P0 ). A feladatot három lépésben oldjuk meg 1. eldöntjük, hogy a szakasz metszi-e a háromszög lemez síkját 2. ha az el˝oz˝o lépésben a válasz igen akkor meghatározzuk a sík és a szakasz metszéspontját 3. eldöntjük, hogy a metszéspont a háromszöglemezen belül esik-e. (V.ö.3.1. fejezet: A pont lokalizációja.) Képezzük az F : R3 → R, X 7→ F ( X ) = w • X − d függvényt. F a sík pontjaira 0 értéket vesz fel, egyébként a sík egyik oldalán pozitív, a másik oldalán negatív. Az adott szakasz csak akkor metszheti a háromszög lemezt, ha F ( X0 ) és F ( X1 ) el˝ojele különbözik.


Játékgeometria 35 A továbbiakban tegyük fel tehát, hogy sgn F ( X0 ) sgn F ( X1 ) = −1. Az el˝oz˝oekben ismertetett módszer szerint (ld. a (4.3) formulát) megkeressük a sík és a szakasz metszéspontját. A 3. lépésben most egy újabb módszert alkalmazunk. Megvizsgáljuk a háromszög síkjában a háromszög minden oldalára, hogy az X metszéspont ugyanazon oldalon van-e, mint a háromszög harmadik (a szóban forgó oldalra nem illeszked˝o) csúcsa. Ha a kiválasztott oldal a Pi Pj oldal és a harmadik csúcs Pk , akkor ( Pi − Pj ) × ( X − Pj ) = 0 esetén X a Pi Pj egyenesen van. Egyébként ( Pi − Pj ) × ( Pk − Pj ) és ( Pi − Pj ) × ( X − Pj ) is a háromszög síkjára mer˝oleges vektor, tehát egyirányúk vagy ellentétes irányúak. Egyirányúság esetén van X a jó oldalon, ekkor a vizsgálatot folytatjuk a következ˝o oldallal (ha még nem vizsgáltuk meg mindhárom oldalt), míg ha a két vektor ellentétes irányú, akkor a metszéspont biztosan nem a háromszög lemezre esik. A két vektor azonos irányát a skaláris szorzatuk dönti:

( Pi − Pj ) × ( Pk − Pj ) • ( Pi − Pj ) × ( X − Pj ) ( > 0 akkor X „jó” oldalon van < 0 akkor X „rossz” oldalon van. Sugár metszése háromszöggel Az X0 X1 egyenes (félegyenes, szakasz) metszetét vizsgáljuk a P0 P1 P2 háromszöglemezzel. Elegend˝o az eljárást egyenesre megadni, félegyenesre, szakaszra könnyen módosítható. A megoldáshoz az egyenes és a háromszöglemez paraméteres el˝oállítását használjuk. A kérdés, hogy vannak-e olyan t ∈ R, u, v ∈ [0, 1] paraméterek, hogy

(1 − t) X0 + tX1 = (1 − u − v) P0 + uP1 + vP2 .

(4.4)

Ha a probléma az X0 X1 félegyenesr˝ol szól, akkor t ∈ [0, ∞), míg ha az X0 X1 szakaszról, akkor t ∈ [0, 1]. (4.4)-et rendezve: t ( X1 − X0 ) +u ( P0 − P1 ) +v ( P0 − P2 ) = P0 − X0 . | {z } | {z } | {z } | {z } a

b

c

d

A jobb áttekinthet˝oség kedvéért vezessük be az el˝obbiekben már jelölt elnevezéseket: ta + ub + cv = d. (4.5) (4.5) egy lineáris egyenletrendszer a t, u, v ismeretlenekre. a, b, c, d ∈ R2 vagy ∈ R3 vektorok, annyi egyenletünk van, ahány dimenzióban vagyunk. Kiegészíthetjük a vektorokat a 0 utolsó koordinátával, így mindig három dimenzióban vagyunk, a továbbiakban ezt tesszük. A lineáris egyenletrendszert természetesen általánosan meg tudjuk oldani Gauss-eliminációval.


Játékgeometria 36 Az egymásba ágyazott eliminációs lépések azonban növelik a numerikus hibákat, így (4.5)-öt explicit módon fogjuk megoldani. b és c nem párhuzamos vektorok, így vektoriális szorzatuk nem zéró. Emellett b × c mer˝oleges b-re is és c-re is. Így (4.5)-öt skalárisan szorozva b × c-vel t( a • (b × c)) = d • (b × c).

(4.6)

Két esetet különböztetünk meg. 1. eset: a • (b × c) 6= 0. Ekkor t-t (4.6)-ból kifejezhetjük: t=

d • (b × c) . a • (b × c)

(4.5)-ben máris csak két ismeretlen van: ub + vc = d − ta . | {z }

(4.7)

e

(4.7)-et skalárisan szorozva b-vel és c-vel:

(b • b)u + (c • b)v = e • b (b • c)u + (c • c)v = e • c, majd a Cramer-szabállyal megoldva: e • b c • b b • b e • c c • c b • c , v = u= b • b c • b b • b b • c c • c b • c

e • b e • c . c • b c • c

Ha u, v ∈ [0, 1], akkor az egyenes metszi a háromszöglemezt. Ha emellett t ≥ 0, akkor a metszéspont rajta van az X0 X1 félegyenesen, ha t ∈ [0, 1], akkor az X0 X1 szakaszon is. 2. eset: a • (b × c) = 0. A két-dimenziós síkbeli problémánál mindig ez a helyzet, a térben akkor fordul el˝o ez az eset, ha a pontok mind egy síkban vannak. Ekkor (4.4)-nek végtelen sok megoldása van: minden t-re a bal oldali pont a közös síkban van, ezért u és v is meghatározható hozzá. (4.4) helyett az X0 X1 egyenes és a háromszög oldal szakaszainak metszését kell vizsgálni. Mivel a két-dimenziós problémánál is kiegészítettük a pontokat harmadik koordinátával, vektoriális szorzással mindig el tudjuk dönteni, hogy az egyenes párhuzamos-e valamelyik oldallal. Pl.

( X1 − X0 )k P0 − P1 ⇐⇒ ( X1 − X0 ) × ( P0 − P1 ) = 0. Csak azokat az oldal szakaszokat kell vizsgálni, amelyek nem párhuzamosak az egyenessel. Legyen pl. a P0 P1 szakasz ilyen. Az X1 X0 és P1 P0 egyenesek metszéspontjának megkeresése a

(1 − t) X0 + tX1 = (1 − u) P0 + uP1 Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

(4.8)

Játékgeometria 37 lineáris egyenletrendszer megoldását jelenti t-re és u-ra. Rendezve t ( X1 − X0 ) +u ( P0 − P1 ) = P0 − X0 . | {z } | {z } | {z } a

d

b

a-val és b-vel skalárisan szorozva mindkét oldalt:

( a • a)t + (b • a)u = d • a ( a • b)t + (b • b)u = d • b. Cramer-szabállyal megoldva: d • a d • b t= a • a a • b

a • a b • a a • b b•b u= a • a b • a a • b b•b

d • a d • b . b • a b • b

X0 X1 akkor és csakis akkor metszi a P0 P1 szakaszt, ha u ∈ [0, 1], a metszéspont pedig M = (1 − u) P0 + uP1 . Ehhez t-t nem is kell meghatározni, de ha az is fomtos, hogy a metszéspontról megállapítsuk, hogy az X0 X1 félegyenesen vagy szakaszon van, akkor t értékét is meg kell vizsgálni. M akkor és csakis akkor van az X0 kezd˝opontú X1 -et tartalmazó félegyenesn, ha t ≥ 0, illetve akkor és csakis akkor van a P0 P1 szakaszon, ha t ∈ [0, 1]. A fentebb ismertetett módszer egyenes és konvex sokszöglemez metszési problémájára is alkalmazható. Ha a sokszöglemez és az egyenes nem egy síkban vannak, akkor a konvex sokszöglemezt egy csúcsból induló átlóival háromszöglemezekre lehet bontani, ezekre a háromszögekre kell a metszési feladatot megoldani az el˝oz˝oek szerint (1. eset). Ha az egyenes és a sokszöglemez egysíkúak, akkor az egyenes és az oldalszakaszok metszési problémáját vizsgáljuk a 2. eset szerint. 4.3

doboz-egyenes metszés

A síkbeli problémát tekintsünk: egy egyenes metsz-e egy téglalapot? Ezt a problémát sokféle hatékony módon meg lehet oldani, amire a kés˝obbiekben még látunk módszert (pl. az effektív sugár módszerét az 53. oldalon). Az alábbiakban leírt módszer a térbeli problémára is általánosítható, s˝ot a téglatestt˝ol általánosabban tetsz˝oleges paralelepipedonra is muködik. ˝ Az X0 X1 egyenest paraméterezve adjuk meg: X = X0 + t ( X1 − X0 ) . Ha az el˝obbi parametrizált el˝oállítást az X mozgó pont mozgását leíró egyenletnek fogjuk fel, ahol t az id˝o, akkor a kérdés az, hogy van-e olyan id˝opont, hogy X mindkét sávon belül van. Ha X1 − X0 nem párhuzamos Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 38 C B A

t2

t1 X1

X0

13. ábra. Sugár és sáv keresztezése: az X0 -ból induló X1 − X0 sebességgelD mozgó pont t1 id˝opontban lép be a sávba és t2 id˝opontban lép ki. a téglalap oldalaival, akkor a mozgó pont mindkét sávba belép és mindkét sávból kilép. Ha az [ a1 , a2 ] id˝ointervallumot tölti az egyik sávban, a [b1 , b2 ] intervallumot a másik sávban. A kérdés, hogy a két intervallum kölcsönös helyzete milyen. A két intervallum diszjunkt, ha egyik intervallum teljesen a másik valamelyik oldalán van, azaz a2 < b1 vagy b2 < a1 . Tagadással kapjuk, hogy van olyan id˝opont, hogy X mindkét sávban benne van, ha a2 ≥ b1 és b2 ≥ a1 .


5 LINEÁRIS TRANSZFORMÁCIÓK

Geometriai transzformáción a sík vagy a tér kölcsönösen egyértelmu˝ leképezését értjük a síkra vagy térre. Vagyis • a leképezés értelmezési tartománya a sík vagy a tér • a leképezés céltere megegyezik az értelmezési tartománnyal • különböz˝o pontoknak különböz˝o a képe • minden pont valamely pontnak a képe. 5.1

egyenestartó transzformációk mátrix alakja

Ezek közül a transzformációk közül is ebben a tananyagban csak az egyenestartókkal foglalkozunk, vagyis egy egyenesre illeszked˝o pontok képei is egy egyenesre illeszkednek, illetve egy egyenesre illeszked˝o pontok o˝ sképei is egy egyenesre illeszkednek. Más szóval az egyenestartó transzformációkat affin transzformációknak is nevezik. Az affin transzformációkat az olvasó feltehet˝oen már ismeri (pl. a [Kov11] vagy [Sza10] jegyzetekb˝ol.) Az affin transzformációk mindig mátrix muveletek ˝ segítségével írhatók le: F : Rn → Rn akkor és csakis akkor affin, ha van olyan A ∈ GL(n) mátrix és b ∈ Rn vektor, hogy F ( X ) = AX + b. (5.1) Röviden úgy is írhatjuk, hogy F = ( A, b), és mivel ( A, b) ∈ Rn×(n+ I ) , F-re mint mátrixra is tekinthetünk. A sík affin transzformációjánál ( A, b) ∈ R2×3 , a térben ( A, b) ∈ R3×4 . Az A mátrix a transzformáció lineáris része, b pedig az eltoló vektora. (F ( X ) = X + b a b-vektorral történ˝o eltolás – innen a név.) Az (5.1) képlet elég egyszeru, ˝ a transzformációk szorzása (egymás után való elvégzése) viszont némi körültekintést igényel. Ha F = ( A, b), G = (C, d) két affin transzformáció, akkor

( G ◦ F )( X ) = C ( AX + b) + d = (CA) X + (Cb + d),

(5.2)

(C, d) ◦ ( A, b) = (CA, Cb + d).

(5.3)

azaz

39

Játékgeometria 40 Ebb˝ol az észrevételb˝ol az inverz transzformációra is következtethetünk:

( A, b)−1 = ( A−1 , − A−1 b),

(5.4)

ugyanis

( A, b) ◦ ( A−1 , − A−1 b) = ( AA−1 , − A( A−1 b) + b) = ( I, 0) ( A−1 , − A−1 b) ◦ ( A, b) = ( A−1 A, A−1 b − A−1 b) = ( I, 0). Az (5.2) és (5.4) formulák ugyan nem bonyolultak, a lineáris résszel való számolás kézenfekv˝onek is tunik, ˝ az eltoló vektorokkal való számolás viszont külön figyelmet (és külön algoritmust) igényel. Az egész számítást egyetlen mátrixszorzásra lehet egyszerusíteni, ˝ ha homogén koordinátákkal számolunk. (A homogén koordinátákra vonatkozóan ld. a 2.1. fejezetet.) ( A, b) helyett térjünk át a A b ∈ GL(n + 1) (5.5) 0 1 mátrixra. (5.5)-ben a mátrixot tömb alakban írtuk fel, ahol nem minden az, aminek látszik, mert 0 ∈ Rn . Pl. a síkban, ha n = 2, b = (b1 , b2 ) és A = ( aij ), akkor   a11 a12 b1 A b =  a21 a22 b2  . 0 1 0 0 1 A tömb alakú mátrixok alkalmazásában az a jó, hogy az egyébként nem mátrix szorzással elvégezhet˝o leképezések (mint pl. (5.1)) mátrixok szorzására redukálhatók, pl. (5.1) esetében A b X AX + b = . (5.6) 0 1 1 1 (5.6)-ban a jobb oldali mátrixot a mátrixszorzás formális szabálya szerint (sor – oszlop kompozíció) kaptuk meg. Ennek az egyszerusítésnek ˝ azonban ára van, az X pont helyett a pont ( X, 1)-el számoltunk , azaz a pont homogén koordinátáival. Hasonlóan, az eredmény ( AX + b, 1), azaz a képpont homogén koordinátái. Az igazi nyeremény azonban a transzformációk szorzásánál jelentkezik. (5.2) helyett mátrixszorzással számolhatunk: C d A b CA Cb + d = , (5.7) 0 1 0 1 0 1 következésképpen

A 0

b 1

−1

=

A −1 0

− A −1 b . 1

A lényeg az, hogy megértsük, hogy a transzformációnak van lineáris része és eltoló vektora. A programunkban aztán minden a transzformáció lineáris Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 41 részének és eltoló vektorának elhelyezését˝ol függ. Ha az ( A, b) ∈ Rn×(n+1) elrendezést választjuk, akkor a transzformációt a síkban 2 × 3 típusú, a térben 3 × 4 típusú mátrixszal adjuk meg, nem kell homogén koordinátákkal számolni, de a transzformációk szorzása komplikált ((5.3) szerint). Ha az A b elrendezést választjuk, akkor a transzformációk szorzása mátrix0 1 szorzás, viszont homogén koordinátákkal kell számolni, 3 × 3 típusú, illetve 4 × 4 típusú mátrixokkal. (Ezt a felírást nevezzük lineáris reprezentációnak.) A szerz˝o mindkett˝ore látott már komoly példát. Ha valamilyen grafikus könyvtárat használunk, akkor annak a szabályát kell követni. Pl. az OpenGL könyvtár a „homogén koordinátás” módszert alkalmazza, a PostScript nyelv a R2×3 = R6 típusú reprezentációt (csak síkban)1 . Ha mindent magunk írunk, akkor választani kell. A továbbiakban csak a lényegre, a lineáris részre koncentrálunk. Az eltolást szorzással mindig be lehet építeni: A b I b A 0 = vagy ( A, b) = ( I, b) ◦ ( A, I ). 0 1 0 1 0 1 Az el˝obbi sorban I a megfelel˝o típusú egységmátrix. Példaként el˝oször a skálázást mutatjuk be térben. (Síkban értelem szeruen ˝ módosítható a példa.) A transzformáció lineáris része 

sx A = 0 0

0 sy 0

 0 0  , s x , sy , sz 6= 0, sz

eltoló vektora pedig 0 vektor. A transzformáció hatását könnyen megértjük, ha az (1, 0, 0), (0, 1, 0), (0, 0, 1) vektorokra alkalmazzuk. A képek rendre (ld. 14. ábrát) (s x , 0, 0), (sy , 0, 0), (0, 0, sz ). A skálázás inverze szintén skálázás, a lineáris rész f˝oátlójában (1/s x , 1/sy , 1/sz ) áll. Második példánk legyen a középpontos nyújtás (ld. (1.1)). A C centrumú λ arányú nyújtás lineáris része (1.1) alapján λI, eltoló vektora pedig C − λC. Azaz a transzformáció mátrix reprezentációja: λI C − λC . 0 1 Az inverz transzformáció lineáris része

1 λ I,

eltoló vektora

1 1 − I (C − λC ) = − C + C, λ λ 1 Ok, PostScriptben általában nem írunk játékprogramot.


Játékgeometria 42

14. ábra. Skálázás. A piros kocka oldalai egységnyi hosszúak. A kék téglatest oldalai a skálafaktoroknak megfelel˝oen s x , sy , sz . azaz mátrix reprezentációja 1 λ

I 0

λC − C . 1

További példákat találunk a feladatok között. 5.2

tükrözés

Tükrözzünk az ( X − P) • w = 0 egyenletu˝ egyenesre vagy síkra! (Ld. a 15. ábrát!) (w ∈ Rn = Rn×1 nem zéró vektor az egyenes/sík normálvektora, P illeszkedik az egyenesre/síkra.) Ez a transzformáció nem más, mint az X 7→ X − 2

( X − P) • w X•w P•w w = X−2 w+2 w k w k2 k w k2 k w k2

leképezés. Ennek a transzformációnak az eltoló vektora a 2

P•w w ∈ Rn k w k2

vektor, míg lineáris része az X 7→ X − 2

X•w w k w k2


Játékgeometria 43

X

(( X − P)•w) w k w k2

w P

X0

15. ábra. Tükrözés egyenesre leképezés, amely X 7→ Hw X mátrix szorzással is megadható (Hw ∈ Rn×n ). Hw lineáris algebrai módszerekkel azonnal kiszámítható: Hw = I − 2

w · wt ∈ Rn×n , w•w

(5.8)

ahol I az n × n típusú egységmátrix. (Az ilyen módon megadott mátrixot Householder-mátrixnak nevezzük.) Példaként kiszámítjuk az egyenesre vonatkozó síkbeli tükrözés lineáris reprezentációját. (5.8) második tagjának számlálója w = ( A, B) esetén: 2 A A AB , ( A, B) = B BA B2 míg a nevez˝o A2 + B2 . Így a mátrix: 2

Hw =

1 − 2 A2A+ B2

−2 A2AB + B2

−2 A2AB + B2

1 − 2 A2B+ B2

2

!

=

B2 − A2 A2 + B2 −2AB A2 + B2

−2AB A2 + B2 A2 − B2 A2 + B2

Ha P = ( x0 , y0 ), akkor az eltoló vektor

2( x0 A2 + y0 AB) 2( x0 AB + y0 B2 ) , A2 + B2 A2 + B2


.

! .

Játékgeometria 44 Így a transzformáció lineáris reprezentációja  2 B2 − A2  A2 + B2  −2AB  A2 + B2

−2AB A2 + B2 A2 − B2 A2 + B2

0



2( x0 A +y0 AB) A2 + B2  2( x0 AB+y0 B2 )  .  A2 + B2

0

1

Mivel w-nek csak az iránya lényeges, A 6= 0 esetén át szokás térni a w-vel párhuzamos (1, B/A) = (1, D )) vektorra, ekkor a mátrix elemek egyszeru˝ södnek, például a Housholder-mátrix alakja ! 2 H(1,D) =

D −1 D 2 +1 −2D D 2 +1

−2D D 2 +1 1− D 2 D 2 +1

.

Alkalmazásként vizsgáljunk egy gyakran el˝oforduló problémát. Olyan mozgást (irányítástartó egybevágóságot) kell konstruálni, amely egy dobozt (téglalapot vagy téglatestet) „irányba állít”, azaz a transzformált doboz oldalirányai a koordinátatengelyek irányai legyenek. Kezdjük a síkbeli esettel. A téglalap nem párhuzamos oldalvektorai legyenek a, és b továbbá ( a, b) pozitív irányítású legyen, azaz det( a, b) > 0. Legyen i = (1, 0, ), j = (0, 1). Ha i a (i és a párhuzamosak és egyirányúak), akkor készen vagyunk. Egyébként legyen w = a − k aki. Ekkor w•a w= w•w k a k2 − a1 k a k = a−2 ( a − k a ki ) = k ak2 − 2a1 k ak + k ak2

a0 = a − 2

= a − ( a − k aki ) = k aki. Mivel a tükrözés a mer˝olegességet megtartja b0 mer˝oleges lesz i-re, ugyanakkor a tükrözés az irányítást megváltoztatja, ezért b0 ↑↓ j, vagyis még tükrözni kell az x tengelyre. (Ez a tükrözés a0 -t már nem változtatja.) Emlékeztet˝oül, az x tengelyre vonatkozó tükrözés mátrixa 1 0 . 0 −1 Térben a téglatest oldalvektorai legyenek a, b és c, továbbá ( a, b, c) pozitív irányítású. Az els˝o lépés a síkbeli esethez analóg, ha i a, akkor készen vagyunk, egyébként w = a − k aki. Ekkor a0 = k aki, b képe b0 . Tudjuk, hogy a0 ⊥ b0 (ezzel együtt i ⊥ b0 ), mert a és b is mer˝olegesek voltak. Ha b0 j, akkor tükröznünk kell még az xy síkra. (Ez a tükrözés a0 -t és b0 -t nem változtatja, a harmadik oldalt a pozitív orientációnak megfelel˝oen állítja be.) Egyébként legyen w = b0 − kbk j. Hw · b0 = kbk j. Könnyen látható, hogy Hw · a0 = a0 , hiszen i a tükrözés síkjában van:

(b0 − kbk j • i = b0 • i = 0, Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 45 i ⊥ b0 miatt. Ha a két lépésben együttvéve csak egy tükrözésünk volt, akkor még a harmadik irány beállítása miatt tükrözzünk az xy síkra. Ennek mátrixa   1 0 0 0 1 0 . 0 0 −1 5.3

pont körüli forgatás síkban

Geometriailag a forgatást a síkban annak középpontja és szöge határozza meg. Ha az origó körül forgatunk, akkor a transzformáció lineáris (azaz eltoló vektora zérus vektor). α szögu˝ elforgatás2 esetén az X = ( x, y) pont képe 0 cos α − sin α x x = . (5.9) y sin α cos α y0 | {z } rot α

Ha egy C centrum körül forgatunk α szöggel, akkor a transzformáció lineáris része az (5.9)-ben szerepl˝o forgatási mátrix, eltoló része pedig C − rot α · C: X 7→ rot α · X + (C − rot α · C ) (5.10) Például, ha a C = ( x0 , y0 ) pont körül forgatunk, az eltoló vektor x0 cos α − sin α x0 x0 (1 − cos α) + y0 sin α − = . y0 sin α cos α y0 y0 (1 − cos α) − x0 sin α 5.4

egyenes körüli elforgatás a térben

A források gazdagsága a probléma kiemelt fontosságára utal. Terjedelmes receptek találhatók különböz˝o könyvekben és az interneten, a cél most az, hogy egy könnyen használható módszert adjunk. El˝oször olyan tengely körül forgassunk, mely áthalad az origón. Az egyszeruség ˝ kedvéért a tengely irányvektora legyen egységvektor, s jelöljük ezt az egységvektort w-vel. A számításokban w = ( a, b, c). A forgatás szöge α ∈ R. Ez a két adat még nem határozza meg egyértelmuen ˝ a forgatást, állapodjunk meg abban, hogy a forgatást mindig a jobbkéz-szabálynak megfelel˝oen értjük, azaz a tengely irányával szembe nézve a forgatás az óramutató járásával ellentétes. Az elforgatást ekkor az R3 → R3 , X 7→ cos α( X − w • X · w) + w • x · w + sin α(w × X )

2 A forgatás iránya α el˝ojelének megfelel˝oen értend˝o.


(5.11)

Játékgeometria 46 összefüggés adja meg. Ha összevetjük (5.11)-et összefüggést (1.7)-tel, (1.9)cel és (1.11)-gyel, akkor a forgatás felírható X 7→ RX aklakban az R = cos α(1 − wwt ) + wwt + sin αW =

= cos α · 1 + sin αW + (1 − cos α)wwt mátrixszal, ahol 

0 W= c −b

 −c b 0 −a . a 0

Mivel w egységvektor, azaz a2 + b2 + c2 = 1, közvetlen számolás mutatja, hogy W 2 + I = wwt , így R = I + sin αW + (1 − cos α)W 2 .

(5.12)

Ez elég egyszeru, ˝ igaz? Csak kicsit bonyolultabb a helyzet, ha a forgástengely nem megy át az origón. A tengely egy pontja legyen P0 . A „TFT” (tolforgat-tol) szabályt kell alkalmazni: 1. olyan eltolást alkalmazunk, hogy P0 az origóba kerüljön: X 7→ X − P0 2. forgatunk az (5.12) mátrixszal történ˝o balszorzással 3. az els˝o eltolás inverzét alkalmazzuk. Vagyis X 7→ R( X − P0 ) + P0 = RX + ( P0 − RP0 ).

(5.13)

A transzformáció lineáris része R, eltoló vektora X0 − RX0 . (Önmagában (5.13) és (5.10) teljesen analóg formulák.) 5.5

vetítés és a szelekció probléma

Ebben a fejezetben térbeli problémát tárgyalunk, ha a játékunk nem 3D-s, akkor átugorhatjuk. Már végrehajtottuk az összes R3 → R3 transzformációt, most a térbeli pontokat le kell vetítenünk a képerny˝ore, vagy a képerny˝on nyitott ablakra. Nagyon fontos, hogy el˝oször egy absztrakt (vagy másképpen normalizált) képerny˝ore vetítünk, ahol a koordináták csak a [−1, 1] intervallumban vannak. (Ha három pixel × három pixeles képerny˝onk van, akkor vége is ,.) Ezután skálázunk a képerny˝o, vagy a megnyitott ablak geometriájának megfelel˝oen. Ha a megnyitott ablak mérete (pixelben) w × h, az origó a bal fels˝o sarokban van, a pozitív irányok pedig jobbra és lefele vannak, akkor az absztrakt képerny˝or˝ol az ablakba a w ( x + 1) 2 h y 0 = ( y + 1) 2

x0 =


(5.14)

Játékgeometria 47 transzformációval térünk át. Centrális vetítés Ebben a munkában csak centrális vetítésekkel foglalkozunk. Általánosan a C ∈ R3 centrumból vetítünk a w normálvektorú, X0 ponton átmen˝o ( X − X0 ) • w = 0 egyenletu˝ síkra. A P pont vetületét jelölje P0 , azaz valamely t ∈ R-re P0 = C + t( P − C ) kielégíti a sík egyenletét:

(C + t( P − C ) − X0 ) • w = 0.

(5.15)

Az (5.15) egyenletb˝ol t kifejezhet˝o: t=

( X0 − C ) • w , (P − C) • w

így visszahelyettesítve megkapjuk P0 -t: P0 = C +

( X0 − C ) • w ( P − C ). (P − C) • w

(5.16)

C, X0 és w választásától függ˝oen különböz˝o speciális vetítéseket írhatunk fel. A következ˝o példa egy gyakran alkalmazott vetítés típust ad meg. Vetítsünk az origóból a z = −n (n > 0) síkra. Azaz az origóból vetítünk a (0, 0, 1) normálvektorú, (0, 0, −n) ponton áthaladó síkra. (n a near– közeli szóra utal, ennek logikáját a kés˝obbiekben majd látni fogjuk.) Az (5.16) egyenletbe behelyettesítve n P0 = − P, z vagy részletesen: nx z ny 0 y =− z

x0 = −

z0 = −n = −

(5.17) (5.18) nz . z

(5.19)

Mivel a vetítés alakja közös nevez˝oju˝ lineáris törtfüggvény, kézenfekv˝o áttérni homogén koordinátákra: x10 = nx x20 = ny x30 = nz x40 = −z,


Játékgeometria 48 és x 0 = x10 /x40 , y0 = x20 /x40 . A vetítés mátrix alakban tehát    0  x n 0 0 0 x1  x 0   0 n 0 0  y     2 =   x 0   0 0 n 0  z  3

x40

0

0

−1 0

1

Most bevezetjük az ún. normalizált vetítést. A vetítési transzformációról el˝oírjuk, hogy a képsík conv{(l, b), (l, t), (r, t), (r, b)} téglalapja a [−1, 1] × [−1, 1] négyzetbe transzformálódjon egyenestartó (affin) transzformációval. (l, r, t, b > 0, a betuk ˝ a left – bal, right – jobb, top – fenn, bottom – lenn szavakra utalnak.) Egyszeruen ˝ látható, hogy ehhez (a képsík Descartes-koordinátarendszerében) az r+l x − r−l r−l y t+b y0 = 2 − t−b t−b

x0 = 2

transzformációt kell végrehajtani. Az els˝o koordinátára beírva a vetítéskor kapott értéket az (5.17) formulából: x0 = 2

nx −z

r−l

−

2 n x+ r+l = r −l r−l −z

r +l r −l z

.

Hasonlóan a második koordinátára: y0 = 2

nx −z

t−b

−

2 n y+ t+b = t−b t−b −z

Homogén koordinátákkal mátrix alakban  0   2n r +l 0 x1 r −l r −l 2n t+b  x0   0 2  = t−b t−b  x0   0 0 n 3 x40 0 0 −1

t+b t−b z

.

  0 x y 0  . 0  z  1 0

A vetületi pont koordinátáit x 0 = x10 /x40 , y0 = x20 /x40 adja. z0 = x30 /x40 eredménye minden pontra −n. Mivel x30 -t a vetületi pont koordinátái kiszámításánál nem használjuk, a vetítési mátrix harmadik sorát úgy módosítjuk, hogy az ábrázolásnál nem használt z0 = x30 /x40 koordináta kódolja az eredeti pont térbeli harmadik koordinátáját. z0 nem függhet x-t˝ol és y-tól, így a mátrix alakja  2n  r +l 0 0 r −l r −l 2n t+b  0 0  . t−b t−b  0 0 A B 0 0 −1 0 Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 49 Bennünket most csak x30 és x40 érdekel: x30 = Az + B x40 = −z, azaz

B . z Itt is normalizáljunk, a térbeli [−n, − f ] koordináták képe [−1, 1] legyen. ( f > 0, jelentése far – távoli. A normalizálás tehát most azt jelenti, hogy a közeli és távoli síkok közötti pontok vetületének harmadik koordinátája −1 és 1 közé essen.) Tehát z = −n-re z0 = −1; z = − f -re z0 = 1. Így az alábbi egyenletrendszert kapjuk: z0 = − A −

f = −A f + B

−n = − An + B. Az egyenletrendszert megoldva, f +n 2fn , B= . n− f n− f

A= A vetítési mátrix tehát 

2n r −l

0 2n t−b

 0  V=  0 0

0 0

r +l r −l t+b t−b f +n n− f

−1

 0 0   2fn  .  n− f

(5.20)

0

A normalizált képerny˝on tehát az ( x, y, z) ∈ R3 térbeli pont vetületének koordinátáit az alábbi séma szerint kapjuk: t

t

( x, y, z) 7→ V ( x, y, z, 1) = ( x1 , x2 , x3 , x4 ) 7→

x1 x2 x3 , , x4 x4 x4

t .

A normalizált képerny˝on

x1 x2 , x4 x4

egy pont (amit az ( x, y, z) pont színével kivilágítunk), az x3 /x4 koordinátát a képerny˝o az ún. z-tárban o˝ rzi. Az (5.20) mátrix pontosan az OpenGL centrális vetítéshez használt mátrixa. A szelekció probléma A képerny˝on egy 3D jelenet van. Egér kattintással szeretnénk az egyik objektumot kijelölni, lényegében a vetítést szeretnénk invertálni. Ha z-tárat Az oktatási segédanyag a „Mobil alkalmazásfejlesztés az informatikai tudás innovatív alkalmazásával” címu, ˝ TÁMOP-2.2.4-11/1-2012-0055 kódszámú projekt keretében valósult meg.

Játékgeometria 50 nem alkalmazunk, akkor a vetítés nem invertálható, a vetítés centrumát a képerny˝on kijelölt ponttal összekötve a térbeli pont irányát kaphatjuk csak meg. z-tár alkalmazása esetén azonban a vetítés invertálható lesz, az (5.20) mátrix invertálhatósága miatt. Az egyszeruség ˝ kedvéért csak a normalizált képerny˝ovel (pontosabban z-tárral ellátott normalizált képerny˝ovel) dolgozunk, a valóságban el˝oször az (5.14) leképezést is invertálni kell. (5.20) inverzének meghatározásához a mátrix szorzás elvégzésével elleno˝ rizhet˝o, hogy ha a megfelel˝o mátrix elemek nem nullák, akkor   −1  1 a13  0 0 a11 0 a13 0 a11 a11 0 a23  1  0 a22 a23 0  0 a a22    = 22  ,  0 0 a33 a34  0 0 0 −1 a33 1 0 0 −1 0 0 0 a a 34

34

így 

2n r −l

 0  V −1 =   0 0

0 2n t−b

0 0

r +l r −l t+b t−b f +n n− f

−1

 −1  r − l 0 2n  0 0    = 0 2fn    n− f 0 0

0 t−b 2n

0 0

0 0 0 n− f 2fn

r +l 2n t+b 2n



  . −1   f +n 2fn

A képerny˝on a ( X, Y, Z ) vetületi pont kijelölésével megkapjuk a térbeli o˝ s pontot homogén koordinátákkal V −1 ( X, Y, Z, 1)t = ( x1 , x2 , x3 , x4 ), ahonnan

P=

x1 x2 x3 , , , x4 x4 x4

a keresett pont. Ezután még azt is el kell dönteni, hogy a pont melyik alakzathoz tartozik. A gömbök tesztelése egyszeru, ˝ P akkor és csakis akkor az M középpontú, r sugarú gömb pontja, ha k M − Pk2 = r2 . (Az ilyen tesztet természetesen mindig egy hibát megengedve kell elvégezni. Azt is megfigyelhetjük, hogy szokásos módon nem a távolságot, hanem a négyzetét teszteljük a gyökvonást elkerülend˝o.) A pont és doboz helyzetének eldöntését is ismerjük, ld. a 2.4. szakaszt.


6 TÁV O L S Á G O K K I S Z Á M Í TÁ S A É S Ü T K Ö Z É S E K D E T E K TÁ L Á S A

„Nagy csattanások, brutális ütközések” – sokan ezért szeretik a játékprogramokat. Az ütközések detektálásának alapja a távolságok számítása. A távolságok meghatározásának alapja, hogy • meg tudjuk határozni két pont távolságát • meg tudjuk határozni egy vektor adott irányra vonatkozó mer˝oleges vetületének hosszát. Mindkét kérdéssel foglalkoztunk az 1. fejezetben. 6.1

pont és sík távolsága

Legyen ( X − X0 ) • n = 0 egy sík egyenlete, tehát a sík az X0 pontra illeszkedik és normálvektora n. Határozzuk meg egy tesz˝oleges P pontnak a távolságát ett˝ol a síktól! A keresett érték nem más, mint a P − X0 vektor n irányára vonatkozó vetületének hossza: d=

|( P − X0 ) • n| . knk

(6.1)

Érdemes megjegyezni, hogy (6.1) számlálójában az abszolút értéket elhagyva tesztelni tudjuk, hogy két pontot a sík elválaszt-e. Tegyük fel, hogy a pontok nincsenek a síkon. sgn( P − X0 ) • n = sgn( Q − X0 ) • n =⇒ P-t és Q-t S nem választja el sgn( P − X0 ) • n 6= sgn( Q − X0 ) • n =⇒ P-t és Q-t S elválasztja.

Gömb és sík kölcsönös helyzete A játékunkban egy labda (billiárdgolyó) mozog, a mozgás folyamán tesztelnünk kell, hogy elér-e a labda egy falat? Azt kell meghatározni, hogy

51

Játékgeometria 52 egy középpontjával és sugarával adott gömb és egy sík távolsága mennyi. A probléma egyszeruen ˝ visszavezethet˝o a középpont és a sík távolságára. Jelölje a gömb középpontját C, sugarát R, a síkot S! d(C, S) a középpont és a sík távolsága. Tehát a keresett távolság ( d(C, S) − R, ha d(C, S) − R > 0 (6.2) d= 0, ha d(C, S) − R ≤ 0. 6.2

pont és egyenes távolsága

A pontból az egyenesre bocsátott mer˝oleges szakasz hosszát kell kiszámítani. A módszer négyzetgyök vonást is használ, így ha csak távolságok összehasonlítása a cél, akkor a távolságok helyett elegend˝o a négyzeteiket összehasonlítani, elkerülve a „drága” gyökvonást. Legyen az adott pont P ∈ R3 , az egyenes pedig X0 X1 (16. Ábra). A P − X0

X1 P0

X0 P

16. ábra. Pont és egyenes távolsága vektor egyenesre vonatkozó mer˝oleges vetületének hossza

( P − X0 ) • ( X1 − X0 ) , k X1 − X0 k így Pitagorasz tételéb˝ol a távolság négyzete d 2 = k P − X0 k 2 −

(( P − X0 ) • ( X1 − X0 ))2 . k X1 − X0 k 2


(6.3)

Játékgeometria 53 (6.3)-ból egyszeru˝ átalakítással más formában is megadhatjuk az eredményt: d2 =

6.3

k( X1 − X0 ) × ( P − X0 )k2 . k X1 − X0 k 2

két egyenes távolsága

Legyen az egyik egyenes X0 X1 , míg a másik egyenes Y0 Y1 . Távolságuk nem más, mint annak a szakasznak a hossza, amely mindkét egyenesre mer˝oleges. Ha az egyenesek párhuzamosak, akkor ez a szakasz nem egyértelmu, ˝ és ekkor az egyik egyenesen felvett tetsz˝oleges pontnak a másik egyenest˝ol mért távolságát kell meghatározni. Egyébként a mindkét egyenesre mer˝oleges szakasz egyértelmu. ˝ Ha történetesen az egyenesek metszik egymást, akkor az el˝obbi szakasz „elfajuló”, azaz egyetlen pontból áll. Foglalkozzunk a nem párhuzamos egyenesek kérdésével. Mindkét egyenesre mer˝oleges vektort n = ( X1 − X0 ) × (Y1 − Y0 ) ad. Erre az irányra kell az Y0 − X0 vektort mer˝olegesen vetíteni. Így d=

6.4

|(Y0 − X0 ) • n| . knk

(6.4)

doboz és sík távolsága

Ha a doboz minden csúcsa a sík egyik oldalán van (de nem a síkon), akkor a csúcsok távolságainak minimuma adja a doboz és a sík távolságát. Ha a doboznak vannak a síkon csúcsai, vagy a sík csúcsokat választ el, akkor a távolság 0. Ha a sík egyenlete ( X − X0 ) • n = 0 és n egységvektor, akkor a P pont el˝ojeles távolsága a síktól ( P − X0 ) • n. Tehát el˝oször mindegyik csúcsra kiszámítjuk a csúcs el˝ojeles távolságát a síktól. Ha a nyolc szám között van zérus, vagy két ellentétes el˝ojelu, ˝ akkor a keresett távolság 0. Ellenkez˝o esetben d = min{|( Pi − X0 ) • n| | i = 0, . . . 7}, ahol P0 , . . . , P7 jelöli a csúcsokat. Második módszerként megismerünk egy nagyon fontos koncepciót használó, kevesebb skaláris szorzás elvégzésével járó eljárást. El˝oször vizsgáljunk síkbeli dobozt, azaz téglalapot, illetve téglalap és egyenes kölcsönös helyzetét! A 17. ábrán a téglalap középpontja C, a fél oldalvektorok u és v (azaz a téglalap csúcsai C ± u ± v); míg az egyenest S jelöli. A cél, hogy (6.5)-höz hasonló, egyszeru˝ eljárást kapjunk. Ehhez egy nagyon fontos koncepciót kell megismernünk, a doboz effektív sugarát. Az effektív sugár mindig egy


Játékgeometria 54

v

v

u

C0

C

re

n

S

P

17. ábra. Doboz effektív sugara irányra vonatkozik. Ha az irányt az n egységvektor adja meg, és a doboz fél-odalvektorai u és v, akkor a doboz effektív sugara r e = | u • n | + | v • n |. A 17. ábrán láthatjuk, hogy az effektív sugár kétszerese megadja a téglalapnak egy n irányú egyenesre vonatkozó árnyékának hosszát, ha a vetítés n-re mer˝oleges irányú. (Az ábrán a vetítés irányát jelzik a szaggatott vonalak. Mivel az ábrán n az S egyenes egy normálvektora, a vetítési irány párhuzamos S-el.) Ezek után a téglalap és az S távolsága megállapítható a C középpontú, re sugarú körlemez és S távolságából. (Az ábrán az n irányú egyenes akár át is mehet C-n, s akkor C = C 0 .) Azaz ( d(C, S) − re , ha d(C, S) − re > 0 d= (6.5) 0, ha d(C, S) − re ≤ 0. Az el˝obbieket nagyon könnyu˝ kiterjeszteni térbe. Ha egy téglatest fél élvektorai u, v és w; n pedig egy egységvektor, akkor a téglatest effektív sugara n irányára vonatkozóan r e = | u • n | + | v • n | + | w • n |.


(6.6)

Játékgeometria 55 Ha a téglatest középpontja C (azaz a csúcsok C ± u ± v ± w), az S sík normál egységvektora pedig n, akkor a téglatest és a sík távolsága egyenl˝o a C középpontú, re sugarú gömb és S távolságával, ahol re a (6.6)-tal van adva. 6.5

gömb távolsága doboztól

Doboz alatt síkban téglalapot, térbe téglatestet értünk, ez lehet egy bonyolultabb formát körülölel˝o doboz is. El˝oször egy egyszeru˝ egy-dimenziós problémát tanulmányozunk: mennyi a számegyenes u ∈ R pontjának távolsága a [− a, a] intervallumtól (a > 0)? Egyszeru˝ megfontolás mutatja, hogy a távolság d1 (u, [− a, a]) = max{0, u − a, −u − a}. Ugyanis u > a esetben u − a > 0, −u − a < 0, tehát max{0, u − a, −u − a} = u − a, ami valóban megegyezik a pont és az intervallum távolságával. − a ≤ u ≤ a esetén a távolság természetesen nulla, és valóban, u − a < 0, −u − a < 0 miatt ez megegyezik max{0, u − a, −u − a} = 0 értékével. Hasonlóan, u < − a esetén 0, u − a, −u − a közül csak −u − a pozitív, és ez a pozitív érték valóban megegyezik a pont és az intervallum távolságával. Két-dimenzióban hasonlóan adhatunk választ arra a kérdésre, hogy mennyi egy u = (u1 , u1 ) ∈ R2 pont távolsága a T0 = [− a, a] × [−b, b] téglalaptól: d2 (u, T ) = d21 (u1 , [− a, a]) + d21 (u2 , [−b, b]) =

= max 2 {0, u1 − a, −u1 − a} + max 2 {0, u2 − b, −u2 − b}. A probléma általában ett˝ol bonyolultabb, mert a téglalap nem feltétlenül az el˝obbi „szabályos” pozícióban van. (Ti. a középpont az el˝obbiekben az origó, a téglalap oldalai a koordináta-tengelyekkel párhuzamosak.) Valójában az általános esetet nagyon könnyu˝ visszavezetni erre az egyszeru˝ esetre. Ha az el˝obbi T0 téglalappal egybevágó T téglalap a T0 -ból az ( A, v) mozgással származik, akkor az ( A, v)−1 inverz mozgás T-t T0 -ba, u-t egy u0 = ( A, v)−1 u pontba viszi, azaz u0 és T0 helyzetét kell vizsgálni az el˝obbi módon. Ezt az „irányba állító” mozgást a 44. oldalon tanultuk. Ezek után könnyen általánosítható, hogy a térbeli problémánál a B = [− a, a] × [−b, −b] × [−c, c] „szabályos elhelyezkedésu” ˝ doboz és az u = (u1 , u2 , u3 ) pont távolsága d2 (u, B) = d21 (u1 , [− a, a]) + d21 (u2 , [−b, b]) + d21 (u3 , [−c, c]). A B doboz és az u középpontú r sugarú gömb ütközik, ha d(u, B) = r.


Játékgeometria szeparáló 56 egyenes

18. ábra. Két nem átfed˝o téglalap szeparáló egyenese 6.6

doboz távolsága doboztól

A doboz-doboz ütközés detektálását inkább az elkerülés detektálására lehet visszavezetni. Térben két doboz nem átfed˝o, ha síkkal szeparálni lehet azokat, azaz tudunk olyan síkot állítani, amelynek az egyik doboz az egyik oldalán, a mások doboz a másik oldalán van. Síkban két téglalap nem átfed˝o, ha egyenesekkel szeparálhatók. Ha van szeparáló sík (egyenes), akkor a dobozok síkra (egyenesre) mer˝oleges egyenesre vonatkozó mer˝oleges vetületei nem átfed˝o szakaszok, ld. 18. ábra. A szeparáló síkra (egyenesre) mer˝oleges egyenest nevezzük a továbbiakban szeparáló tengelynek. Három kérdést kell megválaszolnunk a továbbiakban: 1. Hogyan határozzuk meg egy doboz vetületét egy egyenesre? 2. A számegyenesen két intervallum átfedését hogyan állapítjuk meg? 3. Hogyan választjuk ki azokat az irányokat, amelyekre vetítve az elkerülést megállapíthatjuk. Hogyan határozzuk meg egy doboz vetületét egy egyenesre? Ha az adott egyenes az X0 X1 egyenes, akkor a P pont mer˝oleges vetülete P 0 = X0 +

( P − X0 ) • ( X1 − X0 ) ( X1 − X0 ) . k X1 − X0 k 2


Játékgeometria 57 Az egyenest most koordinátázzuk olyan módon, hogy a zérus pont X0 legyen (másképpen fogalmazva, feltehetjük, hogy az egyenes átmegy az origón), az egység-pont pedig X1 . P0 koordinátája a számegyenesen megmutatja, hogy ( P0 − X0 ) = P0 hányszorosa ( X1 − X0 ) = X1 -nek, azaz P vetületének koordinátája P • X1 . k X1 k 2 Mivel k X1 k2 minden P-re ugyanaz a pozitív szám, és csak a koordináták közötti kisebb-nagyobb reláció megállapítására van szükség, elegend˝o az el˝obbi kifejezés számlálóját használni koordinátaként: P • X1 . Ha a doboz mindegyik csúcsát vetítjük az egyenesre, akkor a legkisebb és a legnagyobb koordináták adják a vetületi intervallum határait. A számegyenesen két intervallum átfedését hogyan állapítjuk meg? Egy I1 = [ amin , amax ] és I2 = [bmin , bmax ] akkor és csakis akkor nem átfed˝o, ha I2 az I1 -t˝ol jobbra van, vagy balra van: amax < bmin vagy bmax < amin Hogyan választjuk ki azokat az irányokat, amelyekre vetítve az elkerülést megállapíthatjuk. A legegyszerubb ˝ teszt, ha a dobozoknak a koordináta-tengelyekre vonatkozó mer˝oleges vetületeinek átfedését vizsgáljuk. Egy adott irányban, mondjuk az x-tengely irányában egy doboz mer˝oleges vetületét úgy határozzuk meg, hogy vesszük a csúcsok els˝o koordinátáinak minimumát és maximumát, ez a két érték határozza meg a vetületi intervallumot. (Tulajdonképpen a problémát olyan keretez˝o dobozok átfedésének vizsgálatára vezettük vissza, melynek élei a koordináta-tengelyek irányába esnek. Az ilyen keretez˝o dobozt Bounding Boxnak nevezik. Általánosan, a Bounding Box úgy tartalmazza az alakzatot, hogy a doboz élei a koordináta-tengelyekkel párhuzamosak.) Ha a Bounding Boxok nem átfed˝oek, akkor a két eredeti alakzat sem átfed˝o, de fordítva már nem igaz: a Bounding Boxok lehetnek átfed˝oek úgy, hogy az alakzatok nem átfed˝oek. (Ismer˝os? A játékban úgy látszik, hogy elkerültük az ütközést, de a program mégis robbanást produkál. Ez azért lehet, mert a program az alakzattól általában b˝ovebb keretez˝o dobozok ütközését figyelte.) Ha precízebb ütközés detektálást akarunk, a keretez˝o dobozok ütközését akkor is célszeru˝ el˝ozetes tesztként elvégezni, annak gyorsasága miatt. A síkban be lehet látni, hogy ha két téglalap nem átfed˝o, akkor van olyan szeparáló egyenes, mely az egyik téglalap valamelyik oldalával párhuza-


Játékgeometria 58

19. ábra. Az élirányok tesztelése nem elegend˝o mos. Így elegend˝o a dobozok mer˝oleges vetületét olyan egyenesekre képezni, amelyek iránya megegyezik a dobozok oldalainak irányával, tehát összesen négy egyenesre vonatkozóan vizsgáljuk a mer˝oleges vetületek átfedését. Ha az oldalirányokra vonatkozó vetületi intervallumok nem átfed˝oek, akkor a téglalapok biztosan nem átfed˝oek. Az analóg térbeli tétel az lenne, hogy elegend˝o a dobozok éleinek irányát, tehát hat irányt vizsgálni, azonban ez az állítás már nem igaz. (Ld. 19. ábra!) Sokkal több irányra, összesen tizenöt irányra van szükség. A térben a dobozok három-három éle legyen ( a1 , b1 , c1 ) és ( a2 , b2 , c2 ). Be lehet látni, hogy a vizsgálandó irányok a1 , b1 , c1 , a2 , b2 , c2 , a1 × a2 , a1 × b2 , a1 × c2 , b1 × a2 , b1 × b2 , b1 × c2 , c1 × a2 , c1 × b2 , c1 × c2 . Ha az el˝oforduló vektoriális szorzatok valamelyike zérus, azaz a dobozok egy-egy éle párhuzamos, akkor a vektoriális szorzat nem határoz meg irányt. Ha az élirányokra, valamint a (nem párhuzamos) élpárokra mer˝oleges irányokra vonatkozó vetületi intervallumok nem átfed˝oek, akkor a dobozok biztosan nem átfed˝oek.


Játékgeometria 59

6.7

mozgó gömbök ütközése

Most az ütközési problémába bevezetjük az id˝ot, mint paramétert. Ha egyegy pont egyenesek mentén mozog, az egyenesek lehetnek ugyan metsz˝ok, de a mozgó pontok elkerülhetik egymást, mert az ütközéshez egyszerre kell a metszésponthoz érni. A mozgó gömbök ütközésének feladatát vizsgáljuk egy egyszeru˝ esetben. Ez a probléma geometriailag könnyen kezelhet˝o, mert az ütközési pont a középpontokat összeköt˝o szakaszon jön létre, így csak a középpontok távolságát kell figyelni. Síkban kör-kör, térben gömb-gömb ütközése minden szempontból analóg probléma. Itt a térbeli esetet írjuk le, minden nehézség nélkül lehet alkalmazni a síkban is. A gömbök középpontjainak mozgását a térben írják le az u : I1 → R3 , t 7→ u(t) és v : I1 → R3 , t 7→ v(t) vektor értéku˝ leképezések. A t paraméter az id˝ot jelenti, I1 és I2 a szóba jöv˝o id˝o intervallumot. Tehát egy t id˝opontban a gömbök középpontjai a térben u(t) és v(t). A gömbök sugarai legyenek r és R. A gömbök középpontjainak távolsága az id˝o függvényében q d(t) = ku(t) − v(t)k = (u(t) − v(t)) • (u(t) − v(t)). Ha van olyan id˝opont, hogy d(t) = R + r, akkor a gömbök ütköznek, egyébként elkerülik egymást. A négyzetgyök vonást elkerülve, az

(u(t) − v(t)) • (u(t) − v(t)) = ( R + r )2 egyenletet kell megoldani, az egyenlet megoldása szolgáltatja az ütközés id˝opontját. A problémát általában csak numerikusan lehet kezelni, emellett a t értékére ésszeru˝ feltételeket szabhatunk, pl. negatív id˝o nem jöhet szóba. Több (pozitív) megoldás közül a legkisebb megoldás adja az ütközés id˝opontját: ha a gömbök egyszer már ütköztek, akkor a további ütközésnek nincs jelent˝osége. Megjegyezzük, hogy ha mozgások pályáját eleve valamilyen fizikai elv alapján számoljuk, pl. egy differenciálegyenlet numerikus megoldásával, akkor u(t) és v(t) értékét valamilyen t0 , t0 + ∆t, . . . , t0 + N∆t


Játékgeometria 60 id˝opontokban ismerjük, és ekkor az ütközést minden id˝opontban tesztelni lehet. Az ütközés feltétele, hogy

ku(t + k∆t) − v(t + ∆t)k2 ≤ ( R + r )2 , és ütközés esetén a mozgás számítását már nem kell tovább folytatni. Mindig fontos lehet egy probléma megoldásánál, ha a numerikus megoldás helyett zárt formulát tudunk az eredményre adni, ez növeli a számítás pontosságát. (A numerikus megoldások egymásba ágyazott lépései a korábbi lépések numerikus hibáit tovább ronthatják.) A legegyszerubb ˝ problémát tanulmányozzuk: egyenesvonalú egyenletes mozgást végz˝o gömbök ütközését. Legyenek a pályák u ( t ) = X0 + t ( X1 − X0 ) v(t) = Y0 + t(Y1 − Y0 ), tehát t = 0 id˝opontban a gömbök középpontjai az X0 , illetve Y0 helyen vannak, a t = 1 id˝opontban a megfelel˝o helyek X1 és Y1 . Ésszeru˝ feltételezés, hogy k X0 − Y0 k > R + r. Vezessük be az a = X0 − Y0 és b = ( X1 − Y1 ) − a új ismeretleneket. Ekkor d2 = ( a + bt) • ( a + bt) =

(6.7)

2

= (b • b)t + 2( a • b)t + a • a. Ha b = 0, akkor a probléma lényegesen leegyszerusödik. ˝ Geometriailag ekkor a mozgások pályái párhuzamosak, vagy egybe is eshetnek, mert az egyenesek irányvektorai párhuzamosak, továbbá a mozgások azonos sebességuek: ˝ b = 0 ⇐⇒ X1 − Y1 = X0 − Y0 ⇐⇒ X1 − X0 = Y1 − Y0 . A testek távolsága állandó lesz, d = k ak > R + r, így nem fognak ütközni. A b 6= 0 esetet vizsgáljuk. El˝oször végezzünk el egy egyszeru˝ tesztet. A távolságnégyzet minimuma ott lehet, ahol a d2 függvény t-szerinti deriváltja 0. 0 d2 = 2tb • b + 2a • b, 0

azaz d2 = 0, ha t=−

a•b . b•b

Visszahelyettesítve (6.7)-be: d2min = a • a −

( a • b )2 . b•b


(6.8)

Játékgeometria 61 Tehát az ütközés biztosan nem jön létre, ha a•a−

( a • b )2 > ( R + r )2 . b•b

Ha lesz ütközés, akkor az ütközés id˝opontját a d2 = ( R + r )2 egyenlet megoldása adja. Másodfokú egyenletet kell megoldanunk: p − a • b ± ( a • b )2 − b • b ( a • a − ( R + r )2 ) t= . (6.9) b•b Negatív t érték nem jöhet szóba (ez azt jelentené, hogy a mozgás kezdete el˝ott ütköznének a testek), két pozitív érték esetén a korábbi id˝opontot kell figyelembe venni.


IRODALOMJEGYZÉK

[Bla11]

István Blahota. Kalkulus és Maxima. TÁMOP-4.1.2-08/1/A, 2011.

[Fol96]

J.D. Foley. Computer Graphics: Principles and Practice, Second Edition in C. Addison-Wesley Systems Programming Series. AddisonWesley Pub, 1996.

[GVL13] Gene H. Golub and Charles F. Van Loan. Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, fourth edition, 2013. [Kov11]

Zoltán Kovács. Számítógépi geometria. Informatika Tananyag Tárház, 2011. us.nyf.hu/˜kovacsz.

[PS85]

Franco P. Preparata and Michael Ian Shamos. Computational geometry. Texts and Monographs in Computer Science. SpringerVerlag, New York, 1985. An introduction.

Kelet-Magyarországi Online elérhet˝o: ze-

[PTVF07] William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical recipes. Cambridge University Press, Cambridge, third edition, 2007. The art of scientific computing. [RA90]

David Rogers and J. Alan Adams. Mathematical Elements for Computer Graphics. McGraw-Hill, second edition, 1990.

[Sza03]

László Szabó. Kombinatorikus geometria és geometriai algoritmusok. Polygon könyvtár. Polygon, 2003.

[Sza10]

József Szabó. A számítógépi grafika elemei. Debreceni Egyetemi Kiadó, 2010.

[Tre04]

Christopher Tremblay. Mathematics for Game Developers. Thomson Course Technology/Premier Press, 2004.

62

J E L M A G YA R Á Z AT

Az el˝ofordulás sorrendjében: • Rn – a valós rendezett szám n-esek tere • u • v – az u és v vektorok skaláris szorzata • kuk – az u vektor hossza • u × v – az u és v vektorok vektoriális szorzata • Rm×n – a valós elemu˝ m × n típusú mátrixok halmaza • At – az A mátrix transzponáltja • det A vagy | A| – az A négyzetes mátrix determinánsa • GL(n) az n × n típusú nem zéró determinánsú mátrixok csoportja • L A – az A mátrixszal történ˝o balszorzás, mint lineáris transzformáció

63

TÁ R G Y M U TAT Ó

z-tár, 48 általános lineáris csoport, 11

pont, 15 sík paraméteres el˝oállítása, 22 sáv, 20 skaláris szorzás, 6 szám-vektor szorzás, 6 szakasz paraméteres el˝oállítása, 17 szelekció, 49

affin transzformáció, 38 baricentrikus koordináta, 22 centrális vetítés, 46 Cramer-szabály, 13 doboz, 20

tükrözés, 41

egyenes és sík metszéspontja, 33 egyenes egyenlete síkban, 17 egyenes paraméteres el˝oállítása, 17 extremális pont, 23, 29

vegyes szorzás, 10 vektor, 5 vektor hossza, 6 vektoriális szorzás, 7 vektorok szöge, 7

félegyenes paraméteres el˝oállítása, 17 forgatás, 44 háromszög lemez, 22 homogén koordináták, 16 Householder-mátrix, 42 inverz, 39 Jarvis-algoritmus, 28 közös pontra illeszked˝o három sík, 33 konvex burok, 23, 28 lineáris egyenletrendszer, 13 lineáris leképezés, 11 lineáris reprezentáció, 43 mátrix, 8 mer˝oleges vetület, 12

64

Játékgeometria. * Hat lecke játékfejlesztőknek oktatási segédanyag, mely a

Recommend Documents