Fórum: Egy kis koordináta geometria

Szeretnél hozzászólni? Jelentkezz be.

2007-03-20 21:18:13

Hello, tehát ha te a fizikai résszel foglalkozol, akkor ütközés megelőzési technikát használnál? 1ékébnt nekem 2 háromszög metszés pontja/síkja/szakasza érdekelne, ami ezekből természtesen simán kijön, csak azt szeretném kérdezni, hogy erre van a másik módszer?

Ha nem vagyok tul tolakodo megkérdezhetem h mien egyetemre jársz/jártál (mondjuk gondolom nagyrészt külön tanultad ezt), mert ez nekem is nagyon szimpi lenne:P

Előzmény: [13] 2501, 2006-02-10 05:41:17

[17] 2501	2006-04-21 11:43:44
A teszt soran kapott petmutalt belso szorzatok (p₀, p₁, p₂) a metszespont normalizalatlan baricentrikus koordinatai. Tehat a metszespont helye $\vec{M}~=~rp_0\vec{V_0}~+~rp_1\vec{V_1}~+~rp_2\vec{V_2}$ , ahol $r~=~\frac{1}{p_0+p_1+p_2}$ , $\vec{V_0},~\vec{V_1},~\vec{V_2}$ pedig a haromszog csucsainak helyei. Az angol nyelvu cikkbol, melyre [2] masodik linkje mutat. :)
Előzmény: [16] Dávid15b, 2006-04-20 15:57:16

[16] Dávid15b

2006-04-20 15:57:16

A háromszög-egyeneses-metszéspontos probléma megoldódott. Most már az érdekelne, hogy annak a bizonyos metszéspont helyét hogyan határozhatom meg, mert egy 3D-s proggiban a falra akarok rajzolni, miközben a kamerát mozgatni is lehet, és nem tudtam, hogy kell azt meghatározni.

Remélem tud valaki segíteni...

[15] Dávid15b	2006-02-21 10:06:29
A 7-esnél a linket valami címsornak néztem, és nem néztem meg. Most letöltöm, hazaviszem, és értelmezem. Majd szólok ha gáz van.
Előzmény: [14] 2501, 2006-02-10 07:21:02

[14] 2501	2006-02-10 07:21:02
A ToU-val kezdodo sor vege hibas, $\vec{T_0} \cdot \vec{U_1} ~+~ \vec{T_1} \cdot \vec{U_0}$ -ra javitando.
Előzmény: [13] 2501, 2006-02-10 05:41:17

[13] 2501

2006-02-10 05:41:17

A [2]-ban illetve [7]-ben irtakbol mar ossze lehet hozni a kert teszteket, nem ertem, hogy mi nem megy. Sebaj, nezzuk...

Egy iranyitott egyenes leirhato egy rendezett pontparral: $\overline E = \left( E_0,~E_1 \right)$ . Plücker-koordinataja egy rendezett vektorpar $\bf P = \big\{ \vec{P_0},~\vec{P_1} \big\}$ , amely a pontok helyvektoraival kifejezve: $\bf P = \big\{ \vec{E_1}-\vec{E_0},~\vec{E_1}\times\vec{E_0} \big\}$

Definialjuk a permutalt belso szorzatot ket Plücker-koordinata kozott:

$\bf T \circ \bf U ~=~ \big\{ \vec{T_0},~\vec{T_1} \big\} \circ \big\{ \vec{U_0},~\vec{U_1} \big\} ~=~ \big\{ \vec{T_0} \cdot \vec{U_1},~\vec{T_1} \cdot \vec{U_0} \big\}$

Adott ket egyenes, $\overline A$ es $\overline B$ , Plücker-koordinataik rendre A es B. Ha A o B nulla, akkor az egyenesek metszik egymast vagy parhuzamosak; ha negativ, akkor oramutato jarasaval megegyezoen; ha pozitiv, akkor oramutato jarasaval ellentetesen ternek ki.

Adott egy n>2 oldalu sokszog, csucsai $V_i~\left(0\le i<n \right)$ , iranyitott oldalegyenesei $\overline E_i = \left(V_i,~V_{(i+1)~mod~n}\right)$ , illetve egy szakasz $\left( P_0,~P_1 \right)$ . Kiszamoljuk a szakasz egyenesenek, illetve a sokszog oldalegyeneseinek Plücker-koordinatait, rendre S illetve P_i. A szakasz egyenese akkor metszi a sokszoget, hogyha az S o P_i permutalt belso szorzatok kozott nincs ket ellenkezo elojelu. Mivel arra vagy kivancsi, hogy a szakasz metszi-e a sokszoget, meg azt is meg kell nezni, hogy a szakasz vegpontjai nem esnek-e a sokszog sikjanak ugyanazon oldalara. (Akkor esnek ugyanazon oldalara, hogyha a sik egy pontjahoz viszonyitott helyvektoraik es a sik normalvektoranak skalaris szorzatai nem ellenkezo elojeluek.)

Ezzel a takarasi teszt meg is van. A sokszog adott ponthoz legkozelebbi pontjanak meghatarozasahoz is lehet a fent leirtakat hasznalni. A pontbol merolegest allitasz a sokszog sikjara (ez konnyen megy, ha megvan a sik normalvektora), es megnezed, hogy metszi-e a sokszoget. Ha igen, akkor egyszeruen kiszamolod a metszespontot a sikkal (ez megint konnyu, ha megvan a normalvektora). Ha nem metszi, akkor meg megnezed, hogy melyik oldalegyeneshez van a legkozelebb, es kiszamolod a legkozelebbi pontot azon az egyenesen. Ezt mar lusta vagyok leirni. :)

Egyebkent en nem utkozes-helyrehozasi, hanem utkozes-megelozesi szimulacioval probalkoznek, de te tudod... A sokszogeket meg szerintem egyenesen rossz haromszogekre osztani, mivel konvex sokszogekre kivaloan mukodnek a tesztek. Mar csak emiatt is erdemes elkuloniteni a grafikai meg a fizikai kodnak "szolo" geometriat.

Előzmény: [12] Dávid15b, 2006-02-09 10:23:30

[12] Dávid15b

2006-02-09 10:23:30

Tehát a falon való átmenést, és a láthatósági tesztet, hogy két űrhajó látja-e egymást, nem takarja el őket egymástól fal, csak forgatással tudtam megoldani. Tehát visszatérve az eredeti problémára, a falon való átmenést meg úgy lehet megakadályozni, hogy a falakat háromszögekre osztjuk, és meghatározzuk a legközelebbi fal legközelebbi pontját, ha túl közel van hozzá, akkor abból a pontból eltaszítjuk az objektumot. Ezeket a teszteket nagyon gyorsan kell elvégezni, és a problémát, úgy látszik nem lehet megkerülni. A másik a láthatósági teszt, amit már alább is írtam már párszor. Először legyen meg a gyors tesztelési módszer, utána kezdek foglalkozni azzal, hogy hogyan szűröm ki a szükségtelen háromszögeket. Tehát az az elv kéne, hogy a fentieket (meg az alábbiakat), hogyan lehet megcsinálni anélkül, hogy feleslegesen forgatgatni kéne. Végül is a legnagyobb akcióban is csak 18-ra megy le az FPS ráta. Míg akinek oda adtam, annak az volt a baja, hogy nála lement 5-re... Probálkozni lehet azzal, hogy a kontroll eljárást ritkábban futtatjuk le, és stb. De ez a AI-t tönkre teszi, tehát... Meg kell oldani azokat a problémákat forgatás nélkül. Én az egész neten nem találtam róla semmit, mert nincs rá a suliban időm.

[11] 2501

2006-02-07 23:44:20

David Baraff (fizikai szimulacioval kapcsolatos) jegyzetet nem muszaj elolvasnod, csak referenciakent irtam, hogy a kvaternios megoldast nem a kisujjambol szoptam. :) Az orientacio tarolasara a kvaternio jobb (kompaktabb $\to$ robusztusabb es gyorsabb), pontok tomeges transzformalasahoz (megjelenitesnel) viszont a matrix a nyero (tehat megjelenites elott erdemes kiszamolni a transzformacios matrixot a kvaterniobol).

A BSP csak akkor mukodik, hogyha nincsenek metszo sokszogek (falak). Tehat a BSP-fa kiszamitasa elott a metszo sokszogeket fel kell darabolni.

Előzmény: [10] Dávid15b, 2006-02-07 10:09:23

[10] Dávid15b	2006-02-07 10:09:23
Még most töltöttem le a Baraffot, még nem régtam magamat át rajta, de megnézem. A számítógép számára a kavaterniós, vagy a mátrixos formula a gyorsabb? Mert a modelleket megjelenítés előtt be kell forgatni a megfelelő orientációra, és a megjelenítés minden esetben helyes, még nem láttam, hogy az űrhajóm deformálódott volna. A BSP működik akkor is, ha a falak össze-vissza állnak? Netán talán keresztezik egymást?
Előzmény: [6] 2501, 2006-01-27 00:51:58

[9] Dávid15b	2006-02-07 10:02:40
Átrégtam magamat a BSP-n. Hát jó ötlet, de csak később fogom használni, mert még kicsi a pálya. De a pályát több részben is le lehet játszani, pl. Ha átlépünk a pálya más részére, akkor a pálya többi részét egyszerűen nem jeleníti meg, mint a QUAKE II-ben. A többit még csak most nézem meg.

[8] Dávid15b	2006-02-02 11:13:55
Nem mazsoláztam végig teljesen, amit irtál, mert csak az iskolámból tudok írni, ezért a válasz lehet, hogy sokat fog késni.

[7] 2501

2006-01-27 01:29:43

Haromszog-egyenes metszespont

Ezzel (meg egy kis fejtoressel) a haromszog-gomb metszestesztet is meg lehet oldani.

Előzmény: [4] Dávid15b, 2006-01-26 11:09:12

[6] 2501

2006-01-27 00:51:58

A forgatast latom mar megoldottad, leirom azert a kvaternios alternativat. Egy merev test orientaciojat egy egysegkvaternioval celszeru leirni, mivel a forgatasi matrix redundansabb, es numerikus hibak miatt konnyen degeneralodik [Baraff]. (A kvaternio numerikus hibak kovetkezteben legfeljebb 1-tol kulonbozo hosszusaguva valik, ez normalizalassal orvosolhato.)

Legyen az orientaciot reprezentalo kvaternio neve k! Hogyan kell megvaltoztatnunk k-t, ha a testet el akarjuk forgatni egy tengely korul $\alpha$ szoggel? Kiszamoljuk a forgatasnak megfelelo kvaterniot (legyen a neve r), majd balrol (a kvaternio szorzas nem kommutativ) beszorozzuk vele k-t (k'=rk).

$r_w=\cos\left(\frac{\alpha}{2}\right),\quad r_x=n_x\sin\left(\frac{\alpha}{2}\right),\quad r_y=n_y\sin\left(\frac{\alpha}{2}\right),\quad r_z=n_z\sin\left(\frac{\alpha}{2}\right)$

ahol $\vec n$ a tengelyre illeszkedo egysegvektor.

Kvaterniok szorzata komponensekkel kifejezve:

(ab)_w = a_wb_w - a_xb_x - a_yb_y - a_zb_z, (ab)_x = a_wb_x + a_xb_w + a_yb_z - a_zb_y

(ab)_y = a_wb_y - a_xb_z + a_yb_w + a_zb_x, (ab)_z = a_wb_z + a_xb_y - a_yb_x + a_zb_w

Amikor tomegesen kell pontokat transzformalni, akkor erdemes az orientaciot reprezentalo kvaterniot "kibontani" egy forgatasi matrixba. (Esetedben egyenesen muszaj; az OpenGL matrixokkal "taplalkozik".) Ezt nem irom le, mert kicsit hosszu lenne. :) Itt (14)-nel kezdodik.

Előzmény: [4] Dávid15b, 2006-01-26 11:09:12

[5] 2501

2006-01-26 23:26:43

A haromszog-gomb illetve haromszog-sugar metszestesztek termeszetesen megoldhatoak forgatas nelkul, de ez onmagaban nem eleg. Ha osszetett palyakat tervezel, akkor mindenkeppen hasznalnod kell valamilyen hierarchikus terfelosztason alapulo adatstrukturat (igy linearisrol logaritmikusra csokken a tesztek futasideje). Pl.: BSP (Binary Space Partitioning), octree, kd-tree. Ezek hasznalataval gyorsan kiszurhetoek azok a haromszogek, amelyeket a gomb/sugar biztosan nem metsz, es utana csak a nehany "gyanusitottra" kell futtatni a tenyleges tesztet. (Ezekkel egyebkent a kirajzolas is gyorsithato, ha tenyleg nagy palyarol van szo. Kis palya eseten alighanem hatekonyabb a videokartya memoriajaban tartani egy masolatot az egeszrol.)

BSP eseten az un. PVS (Potentially Visible Sets) is tarolhato a felosztas eredmenyekent letrejovo konvex darabokhoz (ezek a BSP-fa levelei). Ez nagyon hasznos, amikor azt kell eldonteni, hogy egy hajo lat-e egy masikat. BSP-rol csak ket magyar iromanyt talaltam, sajnos eleg vekonykak: 1 2.

Előzmény: [3] Dávid15b, 2006-01-26 11:01:18

[4] Dávid15b

2006-01-26 11:09:12

Az 1. az objektumoknak a világtérben való forgatásához kell, saját tengelyek körül.

A 2. probléma, a hajóknak a falon való áthaladásának megakadályozásához kell: Az ill. falat háromszögekre osztom, és az összes háromszögre elvégzem, az alábbiakat, ha a háromszögön lévő legközelebbi pont közelebb van egy adott távolságnál, akkor a hajót eloljuk a ponttól arra a távolságra.

A 3. probléma az AI-hoz kell: csak akkor kezdjen az ellenséges hajó darálni a lézerágyújával, ha látja a célpontot, és ne a falat lövöldözze.

Magyar link a problémával kapcsolatban egyáltalán nem volt? Tudok angolul, de mégis jobb, ha anyanyelvemen szól az írás, úgy könnyebben megértem.

[3] Dávid15b	2006-01-26 11:01:18
3D-s játékot írok, és már mind a 3 problémát megoldottam, az elsőt a Rodrigues képlettel, míg a másik kettőt a háromszög megfelelő síkba forgatásával, olyan 3D-s játék lesz ez, mint annak idején a Descent, azonban a sok forgatás rengeteg sinus-t, és cosinust jelent. Megoldható-e a probléma úgy, hogy ne kelljen a háromszöget fordítgatni, hisz, ha pl. 150 hajó van, és 1000 fal, az 150000 számítást jelent ciklusonként, és ez jelentősen belassítaná a játékot, egy ciklusnak 1/20 sec alatt kéne lefutnia, hogy ne szaggasson be a játék, vagy legalább is ne lehessen ezt észrevenni. Most 5 hajó, és 40 fal van de máris szaggat, ez még jóformán semmi pálya. Ami a képszintézist illenti, azt elvégzi helyettem az OpenGL. A linkeket még nem néztem meg, mikor ezt írtam.
Előzmény: [2] 2501, 2006-01-25 04:52:05

[2] 2501

2006-01-25 04:52:05

1. Kvaterniokat hasznalnek. Szolj ha nem tudsz angolul, leforditom!

2. Ez nem biztosan jo, de most annak tunik. :) Meghatarozod a pont meroleges vetuletet a haromszog sikjan, legyen P. Ha P a haromszogon belulre esik, akkor megvan a keresett pont, kulonben meghatarozod P meroleges vetuletet az oldalegyeneseken, es kivalasztod kozuluk a P-hez legkozelebbit.

3. Ekvivalens azzal a kerdessel, hogy a pontokat osszekoto szakasz metszi-e a haromszoget. Eloszor megnezed, hogy a pontok a haromszog sikjanak kulonbozo oldalara esnek-e. Ha igen, akkor az a kerdes, hogy a rajuk illeszkedo egyenes metszi-e a haromszoget. (Ez jol jon a 2-es problemahoz is.) Plücker-koordinatakat hasznalo megoldas.

3D-s kepszintezishez kell egyebkent? :) Ha nagyon nem menne, akkor szivesen magyarazom "szajbaragosan" is, csak egyreszt nem akarom elvenni a "felfedezes" oromet, masreszt meg nem akarok feleslegesen irni. ;)

Előzmény: [1] Dávid15b, 2006-01-24 10:30:05

[1] Dávid15b

2006-01-24 10:30:05

Érdekelne néhány matematikai probléma megoldása:

Adott egy egyenes, és egy pont 3D-ben, meg egy szög is. Ismert az egyenest meghatározó két pont, és a másik pont koordinátái (X,Y,Z). A pontot elforgatjuk a szögg az adott egyenes, mint tengely körül, hogyan határozhatjuk meg, hogy hol lesz az adott pont az elforgatás után?

Adott egy háromszög, és egy pont 3D-ben. Ismertek a háromszög csúcsainak, és az ill. pontnak a koordinátái (X,Y,Z). Hogyan határozhatjuk meg annak a pontnak a koordinátáit, amelyik a háromszögön a megadott ponthoz a legközelebb van?

Adott egy háromszög, és két pont 3D-ben. Ismertek a háromszög csúcsinak, és a két másik pontnak koordinátái (X,Y,Z). Hogyan dönthetjük el, pusztán a koordináták alapján, hogy eltakarja-e az egyik pont elől a másik pontot a háromszög?

Aki zseninek tartja magát, vagy tudja a választ, szóljon!

Már regisztráltál?
Új vendég vagy?