Algoritam za indexe tacaka trouglova

Algoritam za indexe tacaka trouglova

offline
  • Pridružio: 19 Maj 2011
  • Poruke: 297

Recimo da imam tacke koje opisuju jedan konveksan poligon, treba da generisem indexe tacaka trouglova koje ispadaju od tog poligona da bih posle mogao da ih iscrtam.
Nesto sam ja probao ali vizuelno kad pogledam dobijam pogresan rezlutat, mislim da negde gresim:

std::vector<WORD> vTriIndices; std::vector<D3DXVECTOR3> vPoints; ... for(...) { std::vector<D3DXVECTOR3> vPolygon; ... assert( vPolygon.size() >= 3 ); vPoints.insert(vPoints.end(), vPolygon.begin(), vPolygon.end()); // append vertices // make "triangle fan" of convex polygon for(std::size_t k = 0; k < vPolygon.size() - 2; ++k) {     WORD inx0 = 0;     if(!vTriIndices.empty())     {         inx0 = vPoints.size() - 1;     }     WORD inx1 = inx0 + k + 1;     WORD inx2 = inx0 + k + 2;     vTriIndices.push_back( inx0 );     vTriIndices.push_back( inx1 );     vTriIndices.push_back( inx2 ); } }

Confused

EDIT:
Treba da se stavi append-ovanje ispod petlje zbog prvog indexa, ali opet nije to to.

... //vPoints.insert(vPoints.end(), vPolygon.begin(), vPolygon.end()); // append vertices // make "triangle fan" of convex polygon for(std::size_t k = 0; k < vPolygon.size() - 2; ++k) {     WORD inx0 = 0;     if(!vTriIndices.empty())     {         inx0 = vPoints.size() - 1;     }     WORD inx1 = inx0 + k + 1;     WORD inx2 = inx0 + k + 2;     vTriIndices.push_back( inx0 );     vTriIndices.push_back( inx1 );     vTriIndices.push_back( inx2 ); } vPoints.insert(vPoints.end(), vPolygon.begin(), vPolygon.end()); // append vertices }

EDIT: Jos jedna ispravka Mr. Green , ali jos nije u redu.
... // make "triangle fan" of convex polygon for(std::size_t k = 0; k < vPolygon.size() - 2; ++k) {     WORD inx0 = 0;    // if(!vTriIndices.empty())     if(!vPoints.empty())     {         inx0 = vPoints.size() - 1;     } ...



Registruj se da bi učestvovao u diskusiji. Registrovanim korisnicima se NE prikazuju reklame unutar poruka.
offline
  • Srđan Tot
  • Am I evil? I am man, yes I am.
  • Pridružio: 12 Jul 2005
  • Poruke: 2483
  • Gde živiš: Ljubljana

Znam da nije odgovor koji si želeo, ali zašto ne koristiš triangle fan? U tom slučaju ti indeksi nisu ni potrebni.



offline
  • Pridružio: 19 Maj 2011
  • Poruke: 297

Napisano: 10 Apr 2013 18:58

Zato sto je mesh sastavljen od vise takvih poligona pa ne moze sa fan-om iz jedne tacke da se "vrti", bili bi spageti od trouglova. Mr. Green

EDIT:
Da objasnim malo detaljnije zasta ovo koristim pa ce moza biti lakse da mi neko pomogne.

Hocu da crtam decal-e (bullet holes, blood splater...). Imam listu trouglova koji su zahvaceni AABB-om (axis aligned bounding box), tako da su neke njihove tacke van AABB-a.
Da bih izbegao fillrate problem (zamisli da ispalis 30-40 metaka na ogroman poligon od zida recimo) a posto su decal-i mali uglavnom trebalo bi da klipujem ove trouglove sa plane-ovima sacinjeni od AABB-a.
Evo pseudo ukratko:

vector< Tri > vTri; // lista trouglova zahvacenih AABB-om vector< WORD > vTriIndices; // lista indexa vector< D3DXVECTOR3 > vPoints; // lista klipovanih tacaka for each triangle in vTri {         for each of 6 AABB planes     {         ClipTriAgainstPlane( inputTri, plane[i], vPolygon ); // klipuj i stavi rezlutat u vPolygon     }     ... // moj kod (koji ne radi) odozgo     vPoints.append( vPolygon ); }

EDIT2:
Evo malo slicica gde se vidi problem, mada sam veoma blizu resenja. Mr. Green
Iskljucio sam alfa blendovanje da bi se videli trouglovi (crno). Crvene linije su ne-klipovani trouglovi.







Dopuna: 11 Apr 2013 14:40

Mislim da znam u cemu je problem.
Funkcija koja klipuje trouglove, odnosno tacke u izlaznom vektoru nisu u "pravilnom" redosledu da bih mogao samo tako da napravim triangle-fan. Mislim da bih morao prvo da ih sortiram. To se valjda zove TSP (traveling salesman problem), da krenem od jedne (prve recimo) i idem do sledece najblize tacke. E sad da li neko zna kako ide ovaj algoritam sa elementima u vektoru?

Ovako bi trebalo da bude:


A verovatno svaki put izlazi zbrckan redosled:

offline
  • Srđan Tot
  • Am I evil? I am man, yes I am.
  • Pridružio: 12 Jul 2005
  • Poruke: 2483
  • Gde živiš: Ljubljana

Ako ti je samo to problem, najlakši način je da nađeš približan centar objekta i da ređaš tačke u odnosu na ugao između vertikalne linije koja prolazi kroz centar i one koja prolazi kroz centar i datu tačku na poligonu.

offline
  • Pridružio: 19 Maj 2011
  • Poruke: 297

Napisano: 11 Apr 2013 16:29

Centar mogu da dobije izracunavajuci AABB od datih tacaka, AABB half-extent dodje kao radijus i onda samo:
adjacent = length( center - vertex[i] ) hypotenuse = length( center - vertex[i + n] ) cos( a ) = adjacent / hypotenuse

Jel tako?

Posle cu imati i drugi problem, ne znam kako da ga sortiram da dodje CCW ( counterclockwise) da mi ne bi bilo flip-ovano.

Dopuna: 11 Apr 2013 18:28

Joooj, majko moja. Mr. Green

Opet negde gresim sa logikom. Probao sam da sastavim algo prema tvojoj ideji ali mi ne radi kako treba, imam i dalje "supu" od trouglova. Mr. Green

Vidis li negde gresku?

typedef std::vector<D3DXVECTOR3>::iterator v_pt_iter; D3DXVECTOR3 getPtsCenter(std::vector<D3DXVECTOR3>& v) {    D3DXVECTOR3 outCenter(0.0f, 0.0f, 0.0f);    float maxF = std::numeric_limits<float>::max();    float minF = std::numeric_limits<float>::min();    D3DXVECTOR3 minPt(maxF, maxF, maxF);    D3DXVECTOR3 maxPt(minF, minF, minF);    for(std::size_t i = 0; i < v.size(); ++i)    {       // min       if(minPt.x > v[i].x)       {          minPt.x = v[i].x;       }       if(minPt.y > v[i].y)       {          minPt.y = v[i].y;       }       if(minPt.z > v[i].z)       {          minPt.z = v[i].z;       }       // max       if(maxPt.x < v[i].x)       {          maxPt.x = v[i].x;       }       if(maxPt.y < v[i].y)       {          maxPt.y = v[i].y;       }       if(maxPt.z < v[i].z)       {          maxPt.z = v[i].z;       }    }    outCenter = (maxPt + minPt) * 0.5f;    return outCenter; } v_pt_iter findSmallestAngle(const D3DXVECTOR3& center, const D3DXVECTOR3& currPt, v_pt_iter begIt, v_pt_iter endIt) {    v_pt_iter outIt = endIt;    float cosA = std::numeric_limits<float>::max();    float adjacent = D3DXVec3Length(&(center - currPt));    for(; begIt != endIt; ++begIt)    {       float hypotenuse = D3DXVec3Length(&(center - *begIt));       float currCosA = adjacent / hypotenuse;       if(cosA > currCosA)       {          cosA = currCosA;          outIt = begIt;       }    }    return outIt; } std::vector<D3DXVECTOR3> getSortedPtList(std::vector<D3DXVECTOR3>& v) {    std::vector<D3DXVECTOR3> vOut(v.size());    vOut.push_back(v.front());    std::swap(v.front(), v.back());    v.pop_back();    D3DXVECTOR3 center = getPtsCenter(v);    while(!v.empty())    {       auto smCosAIt = findSmallestAngle(center, vOut.back(), v.begin(), v.end());       vOut.push_back(*smCosAIt);       std::size_t pos = std::distance(v.begin(), smCosAIt);       std::swap(v[pos], v.back());       v.pop_back();    }        return vOut; }

offline
  • Srđan Tot
  • Am I evil? I am man, yes I am.
  • Pridružio: 12 Jul 2005
  • Poruke: 2483
  • Gde živiš: Ljubljana

Nažalost, nemam sad vremena da proverim šta nije u redu, ali mogu da ti dam sajt na kojem je sve lepo objašnjeno: http://www.shiffman.net/2011/12/23/night-4-sorting-the-vertices-of-a-polygon/

offline
  • Pridružio: 19 Maj 2011
  • Poruke: 297

Napisano: 11 Apr 2013 20:24

Algo je slican ovom mom, samo sto ne znam kako bih implementirao heading2D() funkciju u 3D varijanti da bih mogao da probam. Da li je uopste moguce? Ja za sad ne vidim kako da izvedem.

Dopuna: 12 Apr 2013 22:19

Mislim da sam resio. Smile

Kontaktirao sam autora funkcije za klipovanje trouglova sa plane-ovima koju sam koristio i rekao je da redosled tacka ostaje "normalan", tako da ne moram da sortiram nista. A greska je bila u mom algoritmu za indexe triangle fan-a:

for(std::size_t k = 0; k < vTri.size() - 2; ++k)             {                WORD inx0 = 0;                WORD inx1, inx2;                if(!vTriPoints.empty())                {                   inx0 = vTriPoints.size();// - 1; // <- OVDE JE BILA GRESKA                }                inx1 = inx0 + k + 1;                inx2 = inx1 + 1;                vTriIndx.push_back( inx0 );                vTriIndx.push_back( inx1 );                vTriIndx.push_back( inx2 );             }             vTriPoints.insert(vTriPoints.end(), vTri.begin(), vTri.end());







Sad mogu da predjem na sledeci problem, a to je kalkulacija korektnih texture kordinata posto mi je sad nekako razvuceno gde je ugao veliki izmedju susednih trouglova. Ovo je sa algoritmom koji koristim iz jedne knjige, trenutno ne mogu da nadjem bolji, a nisam neki "math wizard". Sad
Ako imas neku ideju ili linkove bio bih ti zahvalan. Ziveli

Ko je trenutno na forumu
 

Ukupno su 571 korisnika na forumu :: 2 registrovanih, 1 sakriven i 568 gosta   ::   [ Administrator ] [ Supermoderator ] [ Moderator ] :: Detaljnije

Najviše korisnika na forumu ikad bilo je 3466 - dana 01 Jun 2021 17:07

Korisnici koji su trenutno na forumu:
Korisnici trenutno na forumu: blue, kayvan6079