Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 28. 02. 2017 07:13

unknow005
Příspěvky: 82
Škola: "Výběrová" Střední
Pozice: Programátor
Reputace:   
 

Funkce na počítání společného průniku dvou QUADů

Dobrý den,

programuji si v OpenGL aplikaci na počítání průniků 3D objektů, které jsou složené z QUADů (spojení 4 bodů v prostoru). Rád bych si proto vytvořil funkci na jejíž vstupu by byly oba QUADy (každý z jednoho objektu) a na výstupu pole průniků (žádný, jeden bod, nebo dva body reprezentující úsečku). Vyjímkou by byly QUADy vzájemně koplanární - u nich nelze spočítat společný průnik.

Na internetu jsem nic podobného neobjevil. Testování přímky a QUADu mám hotové (výstupem je jeden bod), ale to by znamenalo celkem 8 testů při porovnání dvou QUADů, což by bylo při složitějších objektech (stovky až tisíce QUADů) poměrně náročné na výpočetní výkon. 

Mohl bych se prosím zeptat nějakého zkušeného matematika, zda-li by se společný průnik dvou QUADů dal řešit matematicky (například pomocí vzorečků)?

Očekával bych pak vyšší spolehlivost (co se týče zaokrouhlovací chyby) a skokové navýšení rychlosti. Pokud je to vůbec možné...

Děkuji za rady.
SpaM

Offline

 

#2 28. 02. 2017 11:09

unknow005
Příspěvky: 82
Škola: "Výběrová" Střední
Pozice: Programátor
Reputace:   
 

Re: Funkce na počítání společného průniku dvou QUADů

Hledal jsem nějaká řešení a zatím se mi nejvíce zamlouvá toto:

1) natočit všechny body prvního QUADu tak aby ležel na rovině XY (natočení si zapamatovat)
2) natočit všechny body druhého QUADu o zapamatované natočení
3) projít všechny strany druhého QUADu a zjistit místa, kde protíná rovinu XY (vzniknou dva body A a B)
4) najít všechny průniky úsečky AB se stranami prvního QUADu (výsledkem může být 0, 1, nebo 2 průniky)

Pro výdledek 0: úsečka AB může ležet celá uvnitř prvního QUADu (pak se jedná o průnik) a nebo leží mimo (nejedná se o průnik).

Pro výsledek 1: jeden průnik (např. bod C). Pak je průnik buď AC, nebo BC podle toho který z bodů A nebo B leží uvnitř prvního QUADu.

Pro výsledek 2: dva průniky (např. body C a D). Pak je průnik úsečka CD.

5) natočíme výsledný průnik (bod, nebo body) zpětně o zapamatované natočení (reverzní).

Tím by se mělo celkem snadno vypočítat průnik dvou QUADů. Díky 2D zobrazení by vše mělo mít menší nároky na procesor.

Souhlas? :)

Offline

 

#3 01. 03. 2017 13:40

unknow005
Příspěvky: 82
Škola: "Výběrová" Střední
Pozice: Programátor
Reputace:   
 

Re: Funkce na počítání společného průniku dvou QUADů

Tak jsem začal programovat a hned problém v prvním bodě: po vytvoření rotační matice a aplikaci na oba QUADy nedostávám správný výsledek, respektive hodnota osy Z není 0.

Jak počítám rotační matici:

Mám dva QUADY (Q1, Q2 = [0, 1, 2, 3]). Z každého QUADu si zjistím jejich normálový vektor:

Q1_norm = VectorNormalize(VectorCrossProduct(VectorSubtract(Q1[0], Q1[1]), VectorSubtract(Q1[0], Q1[2])))
Q2_norm = VectorNormalize(VectorCrossProduct(VectorSubtract(Q2[0], Q2[1]), VectorSubtract(Q2[0], Q2[2])))

V podstatě se vytvoří normalizovaný cross produkt ze dvou vektorů každého QUADu (jeden vektor je bod 0 - bod 1, a druhý vektor je bod 0 - bod 1).

Následně si vypočítám rotační osu a úhel (v radiánech) podle Q1
 
rot_axis   = VectorNormalize(VectorCrossProduct(Vector(0, 0, 1), Q1_norm))
rot_angle = arccos(VectorDotProduct(Vector(0, 0, 1), Q1_norm))

rot_axis je XYZ vektor - normalizovaný cross produkt vektoru Z a Q1_norm.
rot_angle je úhel v radiánech - acos dot produktu vektoru Z a Q1_norm.

Z rot_axis a rot_angle vytvořím rotační matici M a aplikuji ji na všechny body Q1 a Q2.

Tím bych měl dostat jeden 2D QUAD (Q1) u kterého by měla být hodnota osy Z rovná nule. Což ale nenastává a hodnota Z u bodů je různá.

Nějaký nápad?

Díky!
SpaM

Offline

 

#4 01. 03. 2017 13:52

ViliX
Místo: Praha
Příspěvky: 188
Škola: MFF
Pozice: student
Reputace:   11 
Web
 

Re: Funkce na počítání společného průniku dvou QUADů

Nešlo by jednoduše určit dvě roviny obou QUADů a pak matematicky vypočítat průnik (přímka nebo celá rovina) a to potom zprůnikovat s jedním z QUADů, aby se dostala úsečka nebo celý QUAD?

Offline

 

#5 01. 03. 2017 14:21

unknow005
Příspěvky: 82
Škola: "Výběrová" Střední
Pozice: Programátor
Reputace:   
 

Re: Funkce na počítání společného průniku dvou QUADů

To Vilix: ... mohl by jsi mi prosím napsat příklad?

Díky.
SpaM

Offline

 

#6 01. 03. 2017 14:25

ViliX
Místo: Praha
Příspěvky: 188
Škola: MFF
Pozice: student
Reputace:   11 
Web
 

Re: Funkce na počítání společného průniku dvou QUADů

↑ unknow005:

Myslím že by to tak mohlo jít. Ozvu se ale až tak za dvě hodiny.

Offline

 

#7 01. 03. 2017 15:58

ViliX
Místo: Praha
Příspěvky: 188
Škola: MFF
Pozice: student
Reputace:   11 
Web
 

Re: Funkce na počítání společného průniku dvou QUADů

Ukáži to na trojúhelnících. Pravděpodobně existují i mnohem chytřejší algoritmy nebo způsoby. Toto se dá použít v případě kdy nás zajímá jednoduše průnik dvou trojúhelníků (od čtyřúhelníků se to bude lišit jen v té druhé části).

Mějme tyto body: http://forum.matematika.cz/upload3/img/2017-03/77541_b.PNG
Trojúhelníky ABC, DEF vypadají takto: http://forum.matematika.cz/upload3/img/2017-03/77563_a.PNG

Určíme roviny trojúhelníků za pomocí vektorového součinu:
$\overrightarrow{AB} = (1,1,1), \space \overrightarrow{AC} = (-2,2,3), \space \overrightarrow{AB} \times \overrightarrow{AC} = (1,-5,4)$
$\overrightarrow{ED} = (-7,-4,3), \space \overrightarrow{EF} = (-7.-1.1), \space \overrightarrow{ED} \times \overrightarrow{EF} = (-1,-14,-21)$

Z toho určíme rovnice rovin (dosazením bodu):
$\alpha: x-5y+4z +d =0, 0 + 0 + 0 + d = 0 \Rightarrow d = 0 \Rightarrow \alpha:  x-5y+4z =0$
$\beta: -x-14y-21z +d =0, -5 - 14\cdot4 + 0 + d = 0 \Rightarrow d = 61 \Rightarrow \beta: -x-14y-21z+61 = 0$

Jednu proměnnou určíme za parametr a vyřešíme soustavu:
$z=t$
$-19y-17t+61=0 \Rightarrow y = \frac{61-17t}{19}$
$x = \frac{305-161t}{19}$

Body průsečnice tedy budou:
$P[\frac{305-161t}{19}, \frac{61-17t}{19}, t]$

Přímka prochází (maximálně) čtyřmi stranami trojúhelníků. Určí se následně průsečíky a z toho úsečka.

--
Když si zpětně čtu můj příspěvek tak zjišťuji jak neomalené by to bylo řešení a kolik výjimek by se tam muselo řešit (rovnoběžné roviny, přímka kolmá k průmětnám, apod).. Nejefektivnější bude asi implementace jakéhokoliv algoritmu na průnik trojúhelníků s tím, že si každý čtyřúhelník jednoduše rozdělíš na dva trojúhelníky.

Tady je návod na implementaci 3D průsečíků trojúhelníků. Jedná se však jen o trochu chytřejší zformalizování toho co jsem tady ručně počítal. Určitě existuje i něco rychlejšího co by umělo dělat tyto výpočty v reálném čase pro spoustu objektů.

Offline

 

#8 01. 03. 2017 17:21

unknow005
Příspěvky: 82
Škola: "Výběrová" Střední
Pozice: Programátor
Reputace:   
 

Re: Funkce na počítání společného průniku dvou QUADů

Děkuji za příklad. Trochu mě mate použití parametru "t". Ale řešit průniky dvou QUADů přes trojúhelníky je dobrý nápad.

Zkusím se ještě zde na fóru zeptat na postup vytvoření rotační matice 3D bodů. Způsob řešení přes 2D mi přijde možná trošku složitější, ale možná bych to mohl použít i pro jiné problémy.

Offline

 

#9 02. 03. 2017 00:31

edison
Příspěvky: 267
Reputace:   
 

Re: Funkce na počítání společného průniku dvou QUADů

Také by to mohlo být popsáno v dokumentacích k fyzikálním enginům.

Offline

 

#10 20. 03. 2017 12:46

unknow005
Příspěvky: 82
Škola: "Výběrová" Střední
Pozice: Programátor
Reputace:   
 

Re: Funkce na počítání společného průniku dvou QUADů

Bohužel, zjistit průnik dvou QUADů není tak jednoduché jak se může na první pohled zdát. Počítání selhává na tzv. Epsilon čísle. Funkce je schopná řešit průnik dvou velikostně přibližných QUADů, ale když se berou extrémy (rozměry stran jsou řádově jiné), tak dochází vlivem zaokrouhlování k chybám... :(

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson