Háromszög koordináták meghatározása paraméterekkel
2016-05-10T10:57:03+02:00
2016-05-20T15:13:21+02:00
2022-08-10T04:00:32+02:00
atkabacsi
Sziasztok!

Egy 3D konverter írása közben a következő problémám akadt.
Adott a 3D térben 3 pont erre kell egy háromszöget illeszteni.
Először meg kell határoznom az illeszkedő háromszög 2D síkbeli alakját.
Ez talán még menne, de a nehezebb rész most jön.
Ezt a háromszöget az egyik tetszőleges pontjával az egyik térbeli ponthoz illesztve x,y,z elforgatási szögekkel kellene ráilleszteni a másik két pontra. A forgatási szögek az illesztett pontból értendőek.
Vagyis pl egy kocka sarkát lecsapva kéne egy háromszöggel befoltozi úgy hogy egy kivágott háromszöget rá kell forgatnom egy pontjára.
Kérdés hogy hogy tudom kiszámolni a háromszög 2D koordinátáit és a szükséges forgatási szögeket.
Van ötlet?
Mutasd a teljes hozzászólást!
Csak, hogy jól értem-e: 

Adott a térben A(xa,ya,za), B(xb,yb,zb) és C(xc,yc,zc) pontok amelyek egy háromszöget definiálnak valamint további három pont: P(xp,yp,zp), Q(xq,yq,zq) és R(xr,yr,zr).

A feladat az, hogy meghatározzuk azt a T transzformációs mátrixot amely ABC ponthármast a PQR ponthármasba viszi át? 

Ha jól értem és ez a feladat, akkor amit keresel az a Kabsch-algoritmus (Kabsch algorithm - Wikipedia, the free encyclopedia) Van hozzá annyi implementáció mint égen a csillag. Nem csak háromszögre, hanem N elemű ponthalmazra működik.

A Kabsch csak eltolási és forgatási mátrixot számol, átméretezést nem, tehát ha nem csak mozgatni és forgatni kell, hanem valamelyik tengely(ek)en méretezni is, akkor kicsit bővíteni kell a módszert. Írás itt: Finding translation and scale on two sets of points to get least square error in their distance?
Mutasd a teljes hozzászólást!

  • én nem egészen értem: 

    Ezt a háromszöget az egyik tetszőleges pontjával az egyik térbeli ponthoz illesztve x,y,z elforgatási szögekkel kellene ráilleszteni a másik két pontra. A forgatási szögek az illesztett pontból értendőek.

    ezek szerint a háromszög egyik csúcsát eltolod egy adott pontba, és azon pont körül (lokálisan) forgatnál? vagy a háromszög tetszőleges belső pontjáról van szó?

    szerintem az ilyen feladatoknál az szokott lenni az egyik "kulcs", hogy koordináta transzformációt végzel,  azaz pld. azt a pontot tekinted az origónak, amihez képest illesztenél, és ahhoz képest számolsz,

    szerkesztés: a "fél" kérdésedhez: google search: plane equation from triangle
    Mutasd a teljes hozzászólást!
  • Igen te jobban megfogalmaztad, pontosan ez lenne a feladat.
    "A  háromszög egyik csúcsát eltolod egy adott pontba, és azon pont körül (lokálisan) forgatnál?"
    Igen az lenne az origó csak azt nem tudom hogy forgassam egyszerre három felé hogy a végén illeszkedjen minden pontja. Forgatni transzformációval menne csak itt már adottak a pontok visszafelé kéne megtudni a mik voltak a forgatási szögek.
    Mutasd a teljes hozzászólást!
  • Azt hiszem fel kell venni egy-egy segédpontot a forgatáshoz ami a két távolabbi pont közötti szakaszokat felezi és az azok közötti szöget kell kiszámolni az origón keresztül. Legalábbis csináltam egy modellt hozzá abból így látom :)
    Mutasd a teljes hozzászólást!
  • Szia!
    Nem tudom pontosan értelmeztem-e amit leírtál de...
    Ha 3D valamit transzformálsz le egy síkra, pl adott pontból kiinduló a síkra merőleges vetítő egyenesekkel az torzulni fog, szóval egyszerű, három tengely menti forgatással nem fogod visszakapni az eredeti objektumot, a háromszög oldalai torzulni fognak. Itt érdemes elgondolkodni valami térbeli transzformációs eljáráson (Helmert-féle térbeli transzformáció nem egy ördögtől származó gondolat, annyira nem bonyolult).

    De a másik. Egy síkot ugyebár 3 pont határoz meg egyértelműen (ha csak pontok vannak). Adott-e az alapsíkod amire le kell vetítened 2D-re? Ha nem, mi lenne ha a háromszöghöz igazítanád ezt a síkot és nem kell forgatnod, vagy ez nem játszik?
    Mutasd a teljes hozzászólást!
  • Csak, hogy jól értem-e: 

    Adott a térben A(xa,ya,za), B(xb,yb,zb) és C(xc,yc,zc) pontok amelyek egy háromszöget definiálnak valamint további három pont: P(xp,yp,zp), Q(xq,yq,zq) és R(xr,yr,zr).

    A feladat az, hogy meghatározzuk azt a T transzformációs mátrixot amely ABC ponthármast a PQR ponthármasba viszi át? 

    Ha jól értem és ez a feladat, akkor amit keresel az a Kabsch-algoritmus (Kabsch algorithm - Wikipedia, the free encyclopedia) Van hozzá annyi implementáció mint égen a csillag. Nem csak háromszögre, hanem N elemű ponthalmazra működik.

    A Kabsch csak eltolási és forgatási mátrixot számol, átméretezést nem, tehát ha nem csak mozgatni és forgatni kell, hanem valamelyik tengely(ek)en méretezni is, akkor kicsit bővíteni kell a módszert. Írás itt: Finding translation and scale on two sets of points to get least square error in their distance?
    Mutasd a teljes hozzászólást!
  • Egy 3D konverter írása közben a következő problémám akadt.

    Lehet, hogy egyszerűbb lenne, ha leírnád, mit konvertálsz mivé (és nem azt, hogy hogyan próbálod).

    Nem egyértelmű, hogy ténylegesen szögekre (mondjuk Euler szögekre) van szükséged, vagy csak egy transzformációra. Ha az egyik irányba megvan egy transzformáció (akár lépések sorozataként), akkor össze tudod szedni egy darab transzformációs mátrixba, és azt invertálva -mindenféle értelmezés nélkül- megkapod az inverz transzformációt. Utána ez vagy elég, vagy tényleg dekomponálgatható forgatásokra, eltolásra, stb.
    Mutasd a teljes hozzászólást!
  • A transzformációs mátrixot a szoftver képzi le, méretezni nem kell csak forgatni.

    A feladat pontosan az lenne hogy van az ABC háromszög ami a síkon fekszik (za,zb,zc értékei=0) és az A pontja az origóban van.
    A másik PQR háromszög az megegyezik az ABC-vel csak el van forgatva a P origóban  lévő pontja körül a 3 tengely mentén.

    Ezekre az elforgatási szögekre volna szükségem mert a program sajnos ebben formában kéri az adatokat. Én viszont csak a kiinduló és az  elforgatás eredményeként kapott koordinátákat tudom megkapni.

    A mellékelt képen pl egy (-10,45,10) fokos elforgatás eredménye látható.
    Tehát a megoldás csak szögekben kapva lenne megfelelő.
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Én az ilyesmit lábbalhajtós módszerrel szoktam:
    - a háromszög és a sík normálvektorát egy irányba hozó forgatást határoznám meg (pl. a skaláris szorzatuk kiadja a közbezárt szög koszinuszát, illetve a vektoriális szorzatuk kiadja, hogy mi mentén kéne annyit forgatni)
    - és mivel ekkorra a két háromszög már egy síkban van, tetszőleges oldalpár irányvektora által bezárt szöggel kell a normálvektor körül forgatni.

    Mivel ezek a forgatások elvarázsolt tengelyek mentén történnek (a két normálvektor által meghatározott sík normálvektora körül, illetve a kiinduló háromszög normálvektora körül), ezért a gyakorlatban ezek mátrixok lennének (ilyeneket - mármint tetszőleges irányvektor körüli forgatás mátrixát - lehet készen találni), amiket össze lehet szorozni, majd az eredményt Euler szögekre bontani.
    Kicsit macerásabb az egylépéses varázslatnál, előnye talán annyi lehet, hogy viszonylag szemléletes, illetve mivel irányvektorokkal dolgozik, az se zavarja, ha a háromszögek mégsem olyan nagyon egybevágóak. Persze ezt a hibaminimalizálós megközelítés is tudja.
    Mutasd a teljes hozzászólást!
  • Kezdem talánl érteni, akkor három lépésben lehet eljutni a célig. Minden forgatásnál az irányvektorokból egyeztetése adja meg a szöget aztán transzformálni a pontokat aztán újra a másik tengely szerint. Reméltem hogy erre van valakinél egy komplett függvény. :)
    A forgatást Cross producttal szoktam kiszámolni , a mátrixokkal gondolom gyorsabb de ez most nem annyira lényeges.
    Igazából a kinduló koordinátáim sincsenek meg, azt is az elforgatottból kell síkra alakítani.

    A dolog lényege egyébként hogy  háromszögekből felépített poligonokat be tudjak építeni egy olyan progiba amibe erre nincs lehetőség a szerkesztőjéből, ott csak téglatestek, henger vannak.
    (A képen a fa csak így lenne beleépíthető pl)

    Az oldallapok mentén esetleg nem lehet megoldani a forgatásokat, akkor talán nem kellenének irányvektorok?
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Hat a forgatasi matrix pont ezt adna. Minden tengelyen az elforgatas szoget. Az eltolasi meg 0 lenne.
    Mutasd a teljes hozzászólást!
  • Az ideális lenne de még nem értem hogy kéne feltölteni. Tanulmáyozom.
    Mutasd a teljes hozzászólást!
  • galicae/kabsch

    van benne Java kod meg teszt.
    Mutasd a teljes hozzászólást!
  • Nem csak ennyi a feladat?

    y = A * x

    ahol A a 4x4-es transzformációs mátrix x az eredeti koordináták, y az új koordináták.
    A = y * pseudoinverz(x)
    Matlab példa kód:
    transzformáció, ami a
    (0 0 0) -> (0 0 0)
    (1 1 0) -> (1 0 1)
    (0 1 0) -> (0 0 1)

    A = [0 0 0 1; 1 0 1 1; 0 0 1 1]' * pinv([0 0 0 1; 1 1 0 1; 0 1 0 1]')
    Az eredmény:

    A = 1.0000 0.0000 0 -0.0000 0 0 0 0 0 1.0000 0 -0.0000 -0.0000 -0.0000 0 1.0000 A = [ O(3x3) T(3x1); 0(1x3) 1]
    Látható, hogy a transzformáció Orientációs része:
    1 0 0
    0 0 0
    0 1 0
    Átgondolva pont azt csinálja, amit szeretnénk. Transzláció pedig nincs, mert [0 0 0 1] az utolsó oszlop.

    Ellenőrzés A*x kiadja a várt eredményt..
    Pseudo inverz számítása SVD segítségével (numerikus dolgok miatt ezzel érdemes számolni), nagyon sok könyvtárban le van implementálva.
    Remélem segítettem :)
    Mutasd a teljes hozzászólást!
  • Kezdem talán érteni

    Az jó, mert én nem.

    A forgatást Cross producttal szoktam kiszámolni

    Természetesen jó az, csak én ezt a tulajdonságát mindig elfelejtem, a skaláris-szorzat=koszinusz hamarabb beugrik. A forgatás tengelyének a meghatározásához ettől még kell a keresztszorzat.

    Igazából a kinduló koordinátáim sincsenek meg, azt is az elforgatottból kell síkra alakítani.

    Na, ez az a rész, amit nem értek. Két nemlétező, de egybevágó háromszög között kéne transzformációt létesíteni? Akkor az egyiket én nagyon egyszerűre igyekeznék választani, A(0,0,0) B(c,0,0) C(x,y,0) - szóval az A pont az origó, a c oldal az x tengely pozitív irányába esik, és a C pont ugyan bármi lehet, de az is a z=0 síkban van. x,y számítható az a és b oldalak hosszából.
    Mutasd a teljes hozzászólást!
  • Na, ez az a rész, amit nem értek. Két nemlétező, de egybevágó háromszög között kéne transzformációt létesíteni?

    Lehet kicsit nyakatekert a dolog. Az elforgatott háromszög a valós , hogy hogyan forgattam az teljesen mindegy csak a síkon kell neki feküdni, tehát több megoldás is lehet. Az biztos hogy célszerű egyszerűt definiálni. Persze lényegesen egyszerűbb lenne a feladat ha a program tudna fogadni vertex adatokat direktbe, de sajnos nem... :( Mindenképpen egy síkban lévő háromszöget vár amit beforgat. Sajnos ilyen háromszöget nem választhatok amit írtál mert egyformának kell lenniük.

    Köszönöm mindenkinek a hozzászólását, már eddig is sokat segítettetek!
    Kabsch algorithmus látszik a legmegfelelőbbnek a problémára.Tulajdonképpen nekem az a mátrix kell ami a síkra leforgatja a háromszöget (bármilyen helyzetebe csak maradjon egy pontjuk közös). Erre csak most jöttem rá hogy fordítva egyszerűbb lesz....
    Mutasd a teljes hozzászólást!
  • Izé, ha csak annyi a feladat, hogy a célháromszöghöz egy olyan háromszöget találj, ami egy bizonyos síkban van/párhuzamos vele, de azon belül már mindegy, hogy hol, akkor a normálvektorok összeforgatása a keresztszorzatos megközelítéseddel ezt pont tudta volna.
    Nyilván a Kabsch-os varázslás is kihozza majd, csak a geometriai tartalma mindössze ennyi.
    Mutasd a teljes hozzászólást!
  • Igazad van teljesen, a Kabsch szerintem is túlzás ehhez a feladathoz, de univerzális megoldás hasonló problámákra. Ezt még nem ismertem de érdekes és korrekt megoldás ezért is fogadtam el.
    Viszont a te megoldásod is jó és valószínű hogy végülis ezt fogom megcsinálni hozzá. Ez közelebb áll az én gondolatmenetemhez is és az ezelőtti válaszod világított rá hogy elbonyolítottam a dolgot.
    Szóval neked is járna pont de csak egyet tudtam elfogadni. Legközelebb jövök neked. Köszi!
    Mutasd a teljes hozzászólást!
  • Őszintén szólva a Kabsch algoritmus lényegét nem sukerült megértenem, de sikerült megoldani a problémámat.
    Mint kiderült elég 2 tengely mentén a forgatás és az y koordinátái a háromszögnek 0-hoz kell minél közelebb kerülni. Próbáltam számításokkal meghatároznioptimális szögeket, de ez csak a 0,90 szögekre sikerült.
    Más szögek esetén a nullába tolom az egyik pontját.
    Aztán két ciklusba egymásba téve az Y, Z tengelyek mentén nagy lépésközökkel végigpörgetem a háromszöget és ahol legjobban illeszkedi elmentem a paramétereket.
    Az eredményt aztán folymatosan csökkenő lépésközökkel rekruzivan folyamatosan lehet finomítani és végül visszatolni az eredeti helyére.
    Elég jó így is a sebesség pár másodperc alatt lepörget vagy 5000 háromszöget.
    A Kabsch algoritmus ennél gyorsabb lenne?
    Íme az eredmény:

    Ha jól gondolom végülis eze egy kétismeretlenes egyenletrendszer létezhet ennek megoldóképlete?
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • A Kabsch algoritmus transzformációs mátrixokat állít elő, azt utána még dekomponálni kell, ha forgatási szögekre van szükséged.
    Amúgy lényegesen gyorsabb lenne, persze: fix számú lépésben számol, nem pedig próbálgat. Ez a normálvektoros izére is igaz.
    Az algoritmus (és megannyi más optimalizáló algoritmusé is) alapgondolata: készít egy hibafüggvényt, és azt minimalizálja. Tipikus hibafüggvény a távolság: ha van akárhány kiinduló-pontod, ugyanannyi cél-pontod, és egy ismeretlen elemekből álló transzformációs mátrixod, akkor a kiinduló pontokat "transzformálhatod" a mátrix-szal, és az eredmény pontok távolságait a kívánt cél-pontoktól összeadhatod: ez egy másodfokú (Pitagorasz-tétellel vett távolságot feltételezve) függvény lesz, benne millió helyen az ismeretlen mátrix elemeivel. Na ennek a függvénynek keressük a minimumát, ami legjobb esetben akár 0 is lehet (amikor nincs távolság a transzformált és a cél pontok között, tökéletes lett a transzformáció). Persze ezt leírni azért könnyebb, mint megcsinálni, de az alap többnyire ez.
    A Kabsch algoritmus olyasmiket tesz hozzá, hogy pl. a mátrix egy forgatás és egy eltolás egymásutánja legyen: ekkor lehet tudni, hogy a mátrix irányvektoros része egymásra merőleges egységvektorokból áll majd, ami a számítást egyszerűsíti.
    Mutasd a teljes hozzászólást!
  • Köszi a leírást, akkor jó uton járok!
    Tulajdonképpen én is így csináltam. Egy hibafüggvény ellenőrzi a forgatás után az illesztés pontosságát. Lehet fix is a lépésszám csak azért rekruzív hogy minél pontosabb legyen, minden következő pásztázást már csak egy sokkal kissebb szeletben nézek, de ha már elég jó az eredmény kiugrik belőle természetesen. Azért majd megpróbálom felírni az egynletét. Valahogy az az érésem hogy hátha iterációk nélkül is ki lehet számolni a szögeket.

    Keresgélés közben olvastam hogy ez még gyorsabb mint a Kabsch algoritmus.
    Theobald Lab: QCP Method

    Szerencsére a koverziónak nem kell valósídőben menni ezért nem gond ha várni kell pár másodpercet egy teljes objektum átalakítására. Ha nagyon gyorsnak kéne lennie akkor valószínűleg csinálnék egy lookup táblát neki.
    Mutasd a teljes hozzászólást!
Címkék
abcd