HTML

Az élet kódjai

Csináld maga. Senki nem csinálja meg helyetted.

Friss topikok

  • sdani: @Travis.CG: Nohát, nem is tudtam, hogy ilyen van... bár ahogy elnézem ezek a komponensek fizetősek... (2018.11.01. 10:14) Rossz beidegződések a bionformatikában
  • Csenge Tarnói: Ez érdekes. Most csinálok egy meta-analízist, életemben először, úgyhogy az én tudásom is felszíne... (2018.10.01. 21:39) Ez már nekem sok
  • robertherczeg: Nekem a kedvenc az volt, hogy: "Inkább eleve Mann-Whitney és/vagy Wilcoxon tesztet használjunk, m... (2018.09.04. 07:47) Ezért utálom a Wilcoxon-tesztet
  • Travis.CG: ÉÉÉÉÉs megjelent! (2018.08.24. 23:31) Nehéz szülés 2
  • Szedlák Ádám: Hogy én mennyire köszönöm ezt a posztot, arra nincs szó. A kódoljon mindenki / legyen mindenki olc... (2018.06.25. 03:37) Legyen mindenki programozó

Készölődés Revision 2012-re (II. rész)

2012.03.18. 17:09 Travis.CG

Trianguláció

A demóban több két dimenziós poligon lesz látható. Mivel szeretnénk rá textúrákat rakni OpenGL alatt, kénytelenek vagyunk felbontani őket háromszögekre. Minden sokszöget fel lehet bontani háromszögekre a matematikusok szerint, de a sokszög bonyuloltságától függően több algoritmust használhatunk. Mit jelent ez a gyakorlatban? A sokszöget alkotó csúcspontokat megadhatjuk véletlenszerűen, vagy szisztematikusan. A sokszög élei metszhetik egymást, tartalmazhatnak lyukakat, sőt a lyukak újabb lyukakat.

Egyszerűsíteni akartuk a munkánkat, ezért kikötöttük, hogy a sokszög nem tartalmazhat lyukakat, és a csúcsok sorrendje az óramutató járásával megegyező irányban írja le az alakzatot. A kikötések után az "ear clipping" (magyarul nem tudom, hogyan lehetne frappánsan lefordítani) algoritmusra esett a választás, amely kellően egyszerű ahhoz, hogy implementálni lehessen.

Az algoritmus leírása

Egy háromnál több csúcsot tartalmazó sokszög három egymás után következő csúcspontját összekötve háromszöget kapunk. Ez a háromszög lehet "száj" vagy "fül" attól függően, hogy a háromszög alapja a sokszögen belül vagy kívül található (1. ábra).

 

 

 

 

Az ábrán az A csúcs egy száj, míg a B egy fül. A fül eltávolításával egy egyszerűbb sokszöget kapunk. Addig ismételgetjük a fülek eltávolítását, amíg egy háromszög nem marad.

Egy háromszögről úgy döntjük el, hogy fül-e, hogy megvizsgáljuk a körüljárási irányukat. Erre van érdekes módon a háromszög területének kiszámításával kapunk választ.:

T = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)

A fenti összefüggés ugyanis más előjelű eredményt ad a körüljárás irányától függően.

Egy lépés viszont még visszavan. Az ábrán látható sokszög elég egyszerű, de találkozhatunk olyan elvetemült esettel is, ahol egy másik csúcs a vizsgálandó háromszög területén belül található. Ilyen esetben nem szabad eltávolítani a csúcsot.

A kérdés eldöntésére a háromszög összes szomszédos csúcsával és a vizsgálandó ponttal alkotunk egy-egy háromszöget, és megvizsgáljuk ezen háromszöget körüljárását. Ha az összes körüljárási irány azonos, a pont az eredeti háromszögen belül található (2. ábra).

Ha megvizsgáljuk az AEB és az AFB háromszögeket, láthatjuk, hogy más a körüljárási irányuk. Az algoritmus tesztelésére készítettem egy C#-os programot, ahova idővel további triangulációs algoritmusokat is be fogok építeni.

Algoritmus a GitHub-on.

Források:

http://softsurfer.com/Archive/algorithm_0101/algorithm_0101.htm#Modern%20Triangles
http://www.gamedev.net/topic/295943-is-this-a-better-point-in-triangle-test-2d/
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html

Szólj hozzá!

Címkék: demoscene

A bejegyzés trackback címe:

https://cybernetic.blog.hu/api/trackback/id/tr294324126

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.