Algoritam za indexe tacaka trouglova

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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 ); } }



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 , 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;     } ...

• 1Ovo se svidja korisniku: morando
  
  Registruj se da bi pohvalio/la poruku!

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

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.

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.
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:

• 1Ovo se svidja korisniku: morando
  
  Registruj se da bi pohvalio/la poruku!

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.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.

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.

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; }

• 1Ovo se svidja korisniku: morando
  
  Registruj se da bi pohvalio/la poruku!

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/

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

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.

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".
Ako imas neku ideju ili linkove bio bih ti zahvalan.