[C++]Optimaliseren van triangle mesh constructie

[NC83]

Het probleem waar ik mee zit is dat de constructie van een triangle mesh van 30K vertices en 60K faces in Wavefront OBJ formaat ontzettend lang duurt. Ik heb eerlijk gezegd wat hulp nodig bij de optimalisatie van deze constructie.

C++:

struct OBJVertex
{
    Vector3 m_position;
    Vector3 m_normal;
    Vector3 m_tangent;
    Vector3 m_textureCoordinate;
};

for (int i = 0; i < (int)m_faces.size(); ++i)
{
    OBJFace face = m_faces[i];
    unsigned int layout = face.getLayout();
    for ( unsigned int i = 0; i < face.getSize(); ++i)
    {
        const OBJVNTData* vntData = face.getVNTDataAt(i);
        OBJVertex newVertex;
        newVertex.m_tangent = createTangent(face, i);
        newVertex.m_position = m_vertices[vntData->m_vertexIndex];
        newVertex.m_normal = m_normals[vntData->m_normalIndex];
        newVertex.m_textureCoordinate = m_texCoords[vntData->m_texCoordIndex];
        newVertex.m_tangent.normalize();
        addVertex( newVertex);
    }
}

void OBJLoader::addVertex( OBJVertex vertex )
{
    bool foundInList = false;
    unsigned int returnIndex = 0;
    
    for (int i = 0; i < (int)m_tempVB.size(); ++i)
    {
        if (0 == memcmp(&vertex, &m_tempVB[i], sizeof(OBJVertex)))
        {
            foundInList = true;
            returnIndex = i;
            break;
        }
    }

    if (!foundInList)
    {
        returnIndex = m_tempVB.size();
        m_tempVB.push_back(vertex);
    }

     m_tempIB.push_back(returnIndex);
}

Zoals je uit deze code kunt zien zit het probleem in de addVertex functie, die een optimalisatie doet zodat een vertex buffer geen dubble vertices bevat.
Ik kan natuurlijk gewoon alle data in een vertex buffer duwen en geen mesh optimalistie uitvoeren maar dat levert dan natuulijk weer perfomance degradatie op bij het renderen.

Een oplossing zou natuurlijk zijn om een CRC te berekenen over de vertex en deze bij te houden in een andere array. Natuurlijk moet de functie addVertex ook gebruik gaan maken bij pass by reference ipv pass by value. Al denk ik dat de grootste performance hit in de memcmp zit.

Als ik zoek op vertex chache optimisation of traingle mesh contrstruction kan ik niet echt vinden wat ik nodig heb.
Onder vertex chache optimisation gaat het steeds over GPU based optimisation, dit komt later pas wil eerst het laden van een file binnen in een redelijke marge hebben.
En bij traingle mesh contstruction kom ik artikels tegen die een log in vereisen, acm port en dergelijken.

Heeft iemand een andere idee of een weblink waar ik meer info kan vinden.

[.oisyn]

Het probleem is natuurlijk dat je gewoon lineair over de lijst met al geaccepteerde vertices loopt, dit maakt je algoritme O(n²). Probeer gebruik te maken van een spatial partitioning datastructuur (op basis van de positie van de vertex, die is het meest volatile), zoals een kd-tree, octree of bounding volume tree, zodat je algoritme O(n log n) wordt. Pas als je algoritme goed in elkaar zit wordt het tijd om eventueel te kijken naar micro-optimizations zoals het passen van data met references (wat onder water waarschijnlijk toch al gebeurt omdat je struct zo groot is)

[ Voor 33% gewijzigd door .oisyn op 02-02-2010 11:34 ]

[NC83]

Ik zal er eens naar kijken als ik thuis kom vanavond, dat was idd waar ik naar opzoek was. Ik wist dat deze implementatie niet het snelst was.

[PrisonerOfPain]

.oisyn schreef op dinsdag 02 februari 2010 @ 11:27:
Probeer gebruik te maken van een spatial partitioning datastructuur (op basis van de positie van de vertex, die is het meest volatile), zoals een kd-tree, octree of bounding volume tree, zodat je algoritme O(n log n) wordt.

Het enige wat er gedaan word is kijken of er een duplicate vertex bestaat. Volgens mij moet een std::set het probleem dan al oplossen. Insert daarop is ook O(log n) en geeft meteen je duplicate terug.

Edit: nevermind. Ondanks dat je insert O(log n) is zit je met je bidirectional iterator. Om die naar je index te vertalen ben je weer O(n) verder, tenzij je de index ergens in je OBJVertex stopt.

Overigens is het ook handig om te kijken hoe vaak je uberhaupt met dubbele vertices zit. Als het klein is, kun je overwegen of het waard is om de extra data naar de GPU te sturen.

[ Voor 26% gewijzigd door PrisonerOfPain op 02-02-2010 14:53 ]

[MLM]

toevallig heb ik laatst een soortgelijke constructie gemaakt. ik merkte (net als de TS waarschijnlijk) dat de naieve implementatie best lang kan duren.

zoals .oisyn al aangeeft gaat de beste manier zijn om een slim algoritme in te zetten, maar mocht je lui zijn (zoals mij), dan heb ik drie tips voor je:
1) loop andersom over je bestaande vertices. het komt heel veel vaker voor dat je met "recente" vertices triangles maakt dan met oude
2) limiteer de hoeveelheid vertices die je controleert. in mijn ~400k triangle mesh had ik door slechts de 10k recentste vertices te controleren slechts 5% "teveel" vertices gemaakt
3) doe je conversie offline. maak een vertex en indexbuffer en serialiseer die naar een file. heb je als bijgaand voordeel dat je daarna veel sneller inlaad omdat je geserializeerde data niet hoeft te parsen (tekst->nummer) en waarschijnlijk nog een kleinere filesize heeft

als je 3) toepast kan je 2) eventueel weglaten om de kleinst mogelijke vertexbuffer te maken, aangezien het toch niet meer real-time hoeft

@PrisonerOfPain: unsorted_set met een goeie hash-functie gaat een betere optie zijn, maar dan moet je wel een "recente" STL hebben. ik heb geen idee eigenlijk wat een goeie hash-functie is op een partij floats, maar dat is vast wel ergens te vinden. dan zou je in O(1) een lookup kunnen doen, en wordt het algoritme O(n)

[ Voor 12% gewijzigd door MLM op 02-02-2010 15:06 . Reden: triangle waar vertex hoort te staan :P ]

[.oisyn]

PrisonerOfPain schreef op dinsdag 02 februari 2010 @ 14:44:
[...]


Het enige wat er gedaan word is kijken of er een duplicate vertex bestaat. Volgens mij moet een std::set het probleem dan al oplossen. Insert daarop is ook O(log n) en geeft meteen je duplicate terug.

Als je alleen perfecte matches wil vinden dan kan dat idd ook. Maar normaalgesproken wil je vertices welden op basis van een minimale afstand wegens mogelijke afrondingsfouten. Met een spatial datastructure kun je volume queries doen, dat kan met een (unsorted_)set niet.

Edit: nevermind. Ondanks dat je insert O(log n) is zit je met je bidirectional iterator. Om die naar je index te vertalen ben je weer O(n) verder, tenzij je de index ergens in je OBJVertex stopt.

Dat is simpel op te lossen door ipv een set een map te nemen, met als value de index in de lijst waar je ze opslaat.

MLM schreef op dinsdag 02 februari 2010 @ 14:55:
3) doe je conversie offline. maak een vertex en indexbuffer en serialiseer die naar een file. heb je als bijgaand voordeel dat je daarna veel sneller inlaad omdat je geserializeerde data niet hoeft te parsen (tekst->nummer) en waarschijnlijk nog een kleinere filesize heeft

Het feit dat het offline gebeurt wil nog niet zeggen dat het dan maar langzaam mag zijn . Ik heb op een gegeven moment ook de welder herschreven van een hashtable met slechte hashfunctie naar een spatial structure. Van de gespendeerde tijd in het welden bleef maar iets van 5% over

[ Voor 26% gewijzigd door .oisyn op 02-02-2010 15:09 ]

[NC83]

Achterste voren er doorheen lopen had ik idd zelf ook bedacht nog niet geprobeerd alleen , limiting had ik nog niet aangedacht ik denk dat dat wel goed zal werken voor nu.

Uiteindelijk wil ik natuurlijk wel naar een model toe dat als pre processed alleen ligt mijn focus daarop het moment nog niet.

Die hash had ik ook al aangedacht vandaar mijn CRC opmerking maar denk eerst eens dat ik die limiting ga toepassen en anders om door het array heen loop.

[PrisonerOfPain]

.oisyn schreef op dinsdag 02 februari 2010 @ 15:06:
Als je alleen perfecte matches wil vinden dan kan dat idd ook. Maar normaalgesproken wil je vertices welden op basis van een minimale afstand wegens mogelijke afrondingsfouten. Met een spatial datastructure kun je volume queries doen, dat kan met een (unsorted_)set niet.

Perfecte matches zijn op het moment ook waar naar gezocht word, dus dat zal het probleem niet zijn. Het probleem met matchen op een bepaalde afstand is dat een artist het verschil er ook in heeft kunnen zitten om hard / soft edges te creëren.

[MLM]

ja, welden en hashes gaat niet echt heel goed samen natuurlijk (alhoewel je daar wellicht om heen kan hacken door je vertex-data af te ronden ofzo, heb je wel een kwaliteitsverlies), maar de TS is duidelijk niet aan het welden met een memcmp() dus daar ben ik niet van uit gegaan

maar mijn persoonlijke mening over welden is dat het een artist-probleem is, net als zorgen dat alle normals de goede kant opwijzen en de data triangulated is. tuurlijk, je kan het een en ander doen als je een conversie/import/export/whatever doet, maar het punt blijft dat je artist een beter inzicht heeft in wat de bedoeling is, en kwalitatief betere beslissingen kan nemen dan jouw software.

daarnaast, als je submeshes los van elkaar gaat welden (immers, je wil waarschijnlijk losse vertex/indexbuffers ivm mogelijk materiaal wisselen etc.) kan het zijn dat wat origineel vertices op exact dezelfde positie waren in de input data daarna dat net niet meer zijn en dan heb je dus effectief een (klein) gat in de mesh geoptimized

en over afrondingsfouten, die zouden niet moeten voorkomen in een OBJ file, aangezien de afronding dan altijd even fout gaat bij de import, dus dan matcht het nog altijd perfect (ervanuitgaande dat je OBJ file wel goed is, natuurlijk)

[ Voor 10% gewijzigd door MLM op 02-02-2010 15:25 ]

[.oisyn]

MLM schreef op dinsdag 02 februari 2010 @ 15:20:
maar mijn persoonlijke mening over welden is dat het een artist-probleem is

Te kort door de bocht. Een 3d pakket produceert meestal vertex channel streams met voor iedere face indices per vertex per stream. Oftewel, de vertex positions hebben andere indices dan de texture coordinaten. Rendering hardware wil echter dat alle data per vertex gegroepeerd is, en dus moet je de data uit elkaar trekken en opnieuw bij elkaar voegen.

daarnaast, als je submeshes los van elkaar gaat welden (immers, je wil waarschijnlijk losse vertex/indexbuffers ivm mogelijk materiaal wisselen etc.)

Je hoeft ze niet los van elkaar te welden. Dat niet doen impliceert namelijk niet dat alles per se in dezelfde buffer terecht komt.

en over afrondingsfouten, die zouden niet moeten voorkomen in een OBJ file, aangezien de afronding dan altijd even fout gaat bij de import, dus dan matcht het nog altijd perfect (ervanuitgaande dat je OBJ file wel goed is, natuurlijk)

Ik ken het formaat van OBJ files niet, maar wij gebruikten 3dsmax en nu Maya en voor terrain gooien wij alle individuele objecten bij elkaar, en die individuele objecten hebben individuele transformaties. Hun vertices zijn dus sowieso in hun eigen local space en matchen daarom per definitie niet. Alles transformeren naar een gemeenschappelijke terrain space brengt hoe dan ook afrondingsfouten met zich mee. Juist door ze niet te welden krijg je gaten tussen objecten die prima aan elkaar passen.

[ Voor 4% gewijzigd door .oisyn op 02-02-2010 15:35 ]

[NC83]

PrisonerOfPain schreef op dinsdag 02 februari 2010 @ 14:44:
[...]


Het enige wat er gedaan word is kijken of er een duplicate vertex bestaat. Volgens mij moet een std::set het probleem dan al oplossen. Insert daarop is ook O(log n) en geeft meteen je duplicate terug.

Edit: nevermind. Ondanks dat je insert O(log n) is zit je met je bidirectional iterator. Om die naar je index te vertalen ben je weer O(n) verder, tenzij je de index ergens in je OBJVertex stopt.

Overigens is het ook handig om te kijken hoe vaak je uberhaupt met dubbele vertices zit. Als het klein is, kun je overwegen of het waard is om de extra data naar de GPU te sturen.

Ja ik snap dat het te maken heeft met hoe vaak het gebeurt maar dit is een generieke implemetatie en ik heb geen controle over waar de models gemaakt worden, dus dat kan wel eens rare resultaten opleveren.

[PrisonerOfPain]

.oisyn schreef op dinsdag 02 februari 2010 @ 15:32:
Ik ken het formaat van OBJ files niet, maar wij gebruikten 3dsmax en nu Maya en voor terrain gooien wij alle individuele objecten bij elkaar, en die individuele objecten hebben individuele transformaties. Hun vertices zijn dus sowieso in hun eigen local space en matchen daarom per definitie niet. Alles transformeren naar een gemeenschappelijke terrain space brengt hoe dan ook afrondingsfouten met zich mee.

Alle coordinaten zijn in plain-text, in world / object space (afhankelijk van de door de artist gebruikte origin, meestal object space) met ongeveer 6 decimalen aan precisie. Ergo, het enige dat je met de coordinaten doet is een string-to-float conversion bij het inladen. De transformaties komen pas na deze stap aan bod.

NC83 schreef op dinsdag 02 februari 2010 @ 15:34:
[...]

Ja ik snap dat het te maken heeft met hoe vaak het gebeurt maar dit is een generieke implemetatie en ik heb geen controle over waar de models gemaakt worden, dus dat kan wel eens rare resultaten opleveren.

Het enige wat er eventueel trager van zou worden is het uploaden van de data naar de GPU, het renderen zelf zou dezelfde performance moeten hebben. Je zit immers niet meer triangles te tekenen. Maar goed, dat is eigenlijk alleen een afweging die je kunt maken als je de data beter kent.

[ Voor 26% gewijzigd door PrisonerOfPain op 02-02-2010 15:41 ]

[NC83]

.oisyn schreef op dinsdag 02 februari 2010 @ 15:32:
[...]

Te kort door de bocht. Een 3d pakket produceert meestal vertex channel streams met voor iedere face indices per vertex per stream. Oftewel, de vertex positions hebben andere indices dan de texture coordinaten. Rendering hardware wil echter dat alle data per vertex gegroepeerd is, en dus moet je de data uit elkaar trekken en opnieuw bij elkaar voegen.


[...]

Je hoeft ze niet los van elkaar te welden. Dat niet doen impliceert namelijk niet dat alles per se in dezelfde buffer terecht komt.


[...]

Ik ken het formaat van OBJ files niet, maar wij gebruikten 3dsmax en nu Maya en voor terrain gooien wij alle individuele objecten bij elkaar, en die individuele objecten hebben individuele transformaties. Hun vertices zijn dus sowieso in hun eigen local space en matchen daarom per definitie niet. Alles transformeren naar een gemeenschappelijke terrain space brengt hoe dan ook afrondingsfouten met zich mee. Juist door ze niet te welden krijg je gaten tussen objecten die prima aan elkaar passen.

OBJ formaat is heel erg simpel en makkelijk te zien als je een object uit max of welke andere 3d model programma naar obj exporteert kun je de file in een text editor openen en de structuur zien.
v = vertex data
vn = normal data
vt = texture data, een enkel kanaal
f = face

Alle arrays staan los van elkaar in de file, in verschilende streams zeg maar.

[.oisyn]

PrisonerOfPain schreef op dinsdag 02 februari 2010 @ 15:37:
[...]


Alle coordinaten zijn in plain-text, in world / object space (afhankelijk van de door de artist gebruikte origin, meestal object space) met ongeveer 6 decimalen aan precisie. Ergo, het enige dat je met de coordinaten doet is een string-to-float conversion bij het inladen. De transformaties komen pas na deze stap aan bod.

Maar verschillende transformaties per object in de OBJ, of hebben ze allemaal dezelfde transformatie? Want dat is nou juist het kernpunt. Bij max en maya files hebben individuele objecten hun eigen transformatie.
[.edit: ah met de uitleg van NC83 erbij is het me nu duidelijk]

Het enige wat er eventueel trager van zou worden is het uploaden van de data naar de GPU, het renderen zelf zou dezelfde performance moeten hebben. Je zit immers niet meer triangles te tekenen. Maar goed, dat is eigenlijk alleen een afweging die je kunt maken als je de data beter kent.

Meer unieke vertices betekent ook meer tijd die gespendeerd wordt in de vertex shader.

[ Voor 3% gewijzigd door .oisyn op 02-02-2010 15:49 ]

[MLM]

.oisyn schreef op dinsdag 02 februari 2010 @ 15:32:
[...]

Te kort door de bocht. Een 3d pakket produceert meestal vertex channel streams met voor iedere face indices per vertex per stream. Oftewel, de vertex positions hebben andere indices dan de texture coordinaten. Rendering hardware wil echter dat alle data per vertex gegroepeerd is, en dus moet je de data uit elkaar trekken en opnieuw bij elkaar voegen.


[...]

Je hoeft ze niet los van elkaar te welden. Dat niet doen impliceert namelijk niet dat alles per se in dezelfde buffer terecht komt.


[...]

Ik ken het formaat van OBJ files niet, maar wij gebruikten 3dsmax en nu Maya en voor terrain gooien wij alle individuele objecten bij elkaar, en die individuele objecten hebben individuele transformaties. Hun vertices zijn dus sowieso in hun eigen local space en matchen daarom per definitie niet. Alles transformeren naar een gemeenschappelijke terrain space brengt hoe dan ook afrondingsfouten met zich mee. Juist door ze niet te welden krijg je gaten tussen objecten die prima aan elkaar passen.

ah okay, ik zat in een context te denken waarin je 1 mesh (in dezelfde local space dus) aan het inladen was. natuurlijk zijn dan de posities/normals/texcoords dan nog wel los, maar gezien de data geindexeerd is in de OBJ gaat afronding geen probleem zijn dus kan je nog steeds een memcmp() gebruiken om te kijken of vertices gelijk zijn (immers de data waaraan gerefereerd word is gelijk)

in jouw geval waarin je ook transformaties gaat toepassen heb je waarschijnlijk te maken met vector/matrix multiplications en dan ga je wel mogelijk wat precisie-problemen hebben natuurlijk en dan gaat memcmp() (en hashing) niet meer op als valide methode.

[ Voor 4% gewijzigd door MLM op 02-02-2010 15:55 ]

[NC83]

Psuedo code voor een slimmere manier om dit te doen gebaseerd op een octree:

code:

foreach vertex in vertexArray
  if vertex in dit volume
    if als deze node kindren heeft
      foreach child van node
        herhaal dit script
    else
      if data van de node de vertex bevat (exacte match)
        return opgeslagen index
      else 
        creeer nieuwe index en sla op en geef waarde trg

Ben ik hier op de goede weg of kan het nog sneller?

Btw OBJ vertices zijn altijd in world space in ieder geval als ik vanuit Max naar obj exporteer.

[ Voor 10% gewijzigd door NC83 op 02-02-2010 15:55 ]

[MLM]

NC83 schreef op dinsdag 02 februari 2010 @ 15:52:
Psuedo code voor een slimmere manier om dit te doen gebaseerd op een octree:

code:

foreach vertex in vertexArray
  if vertex in dit volume
    if als deze node kindren heeft
      foreach child van node
        herhaal dit script
    else
      if data van de node de vertex bevat (exacte match)
        return opgeslagen index
      else 
        creeer nieuwe index en sla op en geef waarde trg

Ben ik hier op de goede weg of kan het nog sneller?

Btw OBJ vertices zijn altijd in world space in ieder geval als ik vanuit Max naar obj exporteer.

dat lijkt wel goed. alleen je octree kan ook dynamisch zijn (als in, als ik X aantal items in mijn node heb, dan splits ik mijn node op in 8 subnodes, rond regel 10 in jouw pseudocode) waardoor je een minimalere en effectiever aantal nodes hebt in je octree. dan start je gewoon met 1 node die een space zo groot beschrijft dat in elk geval al je vertices erin vallen (bij voorkeur de bounding box)
maar goed, ik denk dat .oisyn iets meer thuis is in spatial division methodes gezien zijn voorliefde voor culling etc, dus wellicht kan hij het beter toelichten

[ Voor 7% gewijzigd door MLM op 02-02-2010 16:01 ]

[.oisyn]

Idd. Als je octree fixed is is het sowieso zonde om een octree te gebruiken, omdat je dan in O(1) kunt bepalen in welke node hij terecht komt (het is immers een grid) . Wat overigens an sich ook al een aardige methode is - als je gewoon een (bijv) 32x32x32 grid legt over de extents van de OBJ data, dan werkt dat doorgaans met de meeste mesh ook wel aardig. Je krijgt dan alleen belabberde performance als alle vertices zich rond hetzelfde punt concentreren of als je grote extremen hebt, wat over het algemeen niet vaak voorkomt. Maar een dynamische boom schaalt wat dat betreft wel een stuk beter.

Een kd-tree is trouwens iets makkelijker om te implementeren omdat je altijd maar met 1 splitsing werkt per node. Meestal splits je dan in de richting waarin de huidige node het grootst is.

[NC83]

Deze psuedo code is ff snel tussen het werken door geschreven trouwens, ik denk idd dat het een dynamische boom structuur wordt die splits op het moment de vertices in de leaf node over een bepaald aantal heen gaan.

[Verwijderd]

Hier een O(n log n) manier, sneller en heel wat minder complex dan de KD-Tree proposals hier... aangezien de KD-tree alleen een spacial subdivision maakt, en je daardoor nog altijd normals, tangents en textures coords van elkaar moet gaan onderscheiden. Nu zou je natuurlijk een 12 dimensionale KD-tree kunnen implementeren, maar als je dan een extra component toevoegd, moet je dus ook extra dimensies toevoegen, en dat schaalt gewoon niet zo makkelijk. Gebruik gewoon een standaard std::map hiervoor...

De implementatie van je ==, < en > operators maken uiteindelijk niet zo heel veel uit, zolang ze maar niet 'liegen', en je kunt qua performance nog wat verder doorschalen. Door bijvoorbeeld een 'hash' uit te rekenen van je vertex kun je door gebruik te maken van de std::hash_map wat snellere early outs krijgen, en ook door bijvoorbeeld de operators zo te schrijven dat je de float values bekijkt, ipv gewoon binary compares te doen, kun je nog een en ander bereiken.

code:

struct OBJVertex
{
    Vector3 m_position;
    Vector3 m_normal;
    Vector3 m_tangent;
    Vector3 m_textureCoordinate;

    bool operator==(const OBJVertex& other) const
    {
        return memcmp(this, &other, sizeof(OBJVertex))) == 0;
    }

    bool operator<(const OBJVertex& other) const
    {
        return memcmp(this, &other, sizeof(OBJVertex))) < 0;
    }

    bool operator>(const OBJVertex& other) const
    {
        return memcmp(this, &other, sizeof(OBJVertex))) > 0;
    }
};

typedef std::map<OBJVertex, int> VertexMap_t;

for (int i = 0; i < (int)m_faces.size(); ++i)
{
    OBJFace face = m_faces[i];
    unsigned int layout = face.getLayout();
    for ( unsigned int i = 0; i < face.getSize(); ++i)
    {
        const OBJVNTData* vntData = face.getVNTDataAt(i);
        OBJVertex newVertex;
        newVertex.m_tangent = createTangent(face, i);
        newVertex.m_position = m_vertices[vntData->m_vertexIndex];
        newVertex.m_normal = m_normals[vntData->m_normalIndex];
        newVertex.m_textureCoordinate = m_texCoords[vntData->m_texCoordIndex];
        newVertex.m_tangent.normalize();
        addVertex( newVertex);
    }
}

void OBJLoader::addVertex( OBJVertex vertex )
{
    bool foundInList = false;
    unsigned int returnIndex = 0;
    
    VertexMap_t::iterator iter = m_vertexMap.find(vertex);
    if (iter != m_vertexMap.end())
    {
        returnIndex = iter->second;
    } else
    {
        returnIndex = m_tempVB.size();
        m_tempVB.push_back(vertex);
        m_vertexMap.insert(vertex, returnIndex);
    }

    m_tempIB.push_back(returnIndex);
}

Kost wat extra geheugen voor de m_vertexMap, maar dit is wat ik al jaren gebruik...

Tom.

[ Voor 31% gewijzigd door Verwijderd op 07-02-2010 07:31 . Reden: const corrections, en wat betere uitleg. ]

[Killemov]

Verwijderd schreef op zondag 07 februari 2010 @ 07:17:
Hier een O(n log n) manier, sneller en heel wat minder complex dan de KD-Tree proposals hier... aangezien de KD-tree alleen een spacial subdivision maakt, en je daardoor nog altijd normals, tangents en textures coords van elkaar moet gaan onderscheiden. Nu zou je natuurlijk een 12 dimensionale KD-tree kunnen implementeren, maar als je dan een extra component toevoegd, moet je dus ook extra dimensies toevoegen, en dat schaalt gewoon niet zo makkelijk. Gebruik gewoon een standaard std::map hiervoor...

Dat schaalt toch prima? Mits de tree natuurlijk niet hard op 3 is gedimensioneerd.

De implementatie van je ==, < en > operators maken uiteindelijk niet zo heel veel uit, zolang ze maar niet 'liegen', en je kunt qua performance nog wat verder doorschalen. Door bijvoorbeeld een 'hash' uit te rekenen van je vertex kun je door gebruik te maken van de std::hash_map wat snellere early outs krijgen, en ook door bijvoorbeeld de operators zo te schrijven dat je de float values bekijkt, ipv gewoon binary compares te doen, kun je nog een en ander bereiken.

Je zou de comparator van vector3 kunnen gebruiken, mits deze is geimplementeerd natuurlijk.

code:

struct OBJVertex
{
    Vector3 m_position;
    Vector3 m_normal;
    Vector3 m_tangent;
    Vector3 m_textureCoordinate;

    bool operator==(const OBJVertex& other) const
    {
       return m_position == other.m_position || m_normal == other.m_normal || ...
    }
...
};

Iets dat je ook graag zou moeten willen doen is de mesh array optimaliseren voor de vertex-cache. Dit betekent dus tri's sorteren ( en roteren! ) zodanig dat vertices zoveel mogelijk worden hergebruikt. De meeste caches zijn 32 vertices groot en werken FIFO. Ik heb vroeger zoiets voor de Ogre 3D engine geschreven, ahgi kun je het er nog steeds in vinden. (IndexVertexBuffer.cpp oid)

[.oisyn]

Verwijderd schreef op zondag 07 februari 2010 @ 07:17:
Hier een O(n log n) manier, sneller en heel wat minder complex dan de KD-Tree proposals hier...

Heb je de topic überhaupt gelezen? Lijkt me niet, want de map variant was allang voorgesteld, en ook werd gezegd dat als je vertices wilt welden op basis van minimale afstand je een spatial tree moet gebruiken omdat je map geen area queries kan afhandelen.

aangezien de KD-tree alleen een spacial subdivision maakt, en je daardoor nog altijd normals, tangents en textures coords van elkaar moet gaan onderscheiden.

Wat natuurlijk een onzin-argument is, aangezien 3d mesh in de regel niet heel veel vertices heeft waarbij de positie wel hetzelfde is maar overige properties niet. Veruit de meeste verts zijn uniek in hun positie, en voor de gevallen waarbij dat niet zo is heb je in de regel slechts 2 of 3 verts met een gelijke positie maar verschillende andere properties. Voor die paar verts voldoet een lineaire search prima.

[Verwijderd]

.oisyn schreef op zondag 07 februari 2010 @ 16:25:
[...]

Heb je de topic überhaupt gelezen? Lijkt me niet, want de map variant was allang voorgesteld, en ook werd gezegd dat als je vertices wilt welden op basis van minimale afstand je een spatial tree moet gebruiken omdat je map geen area queries kan afhandelen.


[...]

Wat natuurlijk een onzin-argument is, aangezien 3d mesh in de regel niet heel veel vertices heeft waarbij de positie wel hetzelfde is maar overige properties niet. Veruit de meeste verts zijn uniek in hun positie, en voor de gevallen waarbij dat niet zo is heb je in de regel slechts 2 of 3 verts met een gelijke positie maar verschillende andere properties. Voor die paar verts voldoet een lineaire search prima.

Ja, had wel gelezen, en uiteraard het 'set' idee gezien, maar dat werd om een of andere reden aan de kant geschoven als een niet werkbare oplossing...

En 'in de regel niet veel vertices met dezelfde positie', ja dat zal vast, maar daar gaat het dus helemaal niet om... het gaat erom dat het dus WEL voor kan komen, en je dus in iedergeval erop moet controleren. Door de zaak in een spatial tree te duwen, moet je dus alsnog voor elke node in de KD-Tree controleren of het toevallig voorkomt. Ongeacht of dat maar 2 or 3 keer voorkomt, krijg je dus linear search in die nodes, of je moet alsnog een map gaan gebruiken, en daarmee is je algoritme dus niet O(n log n), maar een klein beetje duurder.

Overigens komst zoiets vaker voor dan je denkt. harde edges, hebben altijd gelijke positie maar andere normals. een simpele cube heeft al 8 posities, maar ik zou als ik jou was toch naar 24 vertices importeren, ander zijn al je normals compleet kut. en uiteraard komt zoiets minder snel voor in een object met 60k vertices, maar dat is helemaal niet wat ik hier ter discussie stel.. het komt voor, en dus moet je er rekening mee houden, dit via een KD-tree doen kan, maar voegt een hoop complexiteit toe die nergens voor nodig is.

Daarnaast zei ik helemaal niet dat een KD-tree geen oplossing is... het is duidelijk wel een oplossing, maar mijn argument is dat je dan dus een hoop code schrijft die in de praktijk helemaal niet nodig is, omdat het met een simpele map ook kan, en je daarmee ook O(n log n) bereikt... en ook via de implementatie die ik als voorbeeld gaf kun je super simpel 'welding' toevoegen mocht je dat willen. maar je zei zelf al dat je dat beter aan de artiest over kunt laten.


Anyway, ik begrijp niet zo goed waarom je zo super hard in de 'aanval' schiet? ik geloof niet dat ik echt iets verkeerd gedaan heb ofzo. ik geef een suggestie, leg uit waarom ik denk dat een KD-tree niet de aller slimste oplossing is, en zelfs als het super slim is, ben je een hoop code aan het schrijven voor vrij weinig toegevoegde waarde naar mijn mening... dat moet toch kunnen? of wordt ik verboden '.oisyn' tegen te spreken?

[Verwijderd]

Killemov schreef op zondag 07 februari 2010 @ 14:50:
Iets dat je ook graag zou moeten willen doen is de mesh array optimaliseren voor de vertex-cache. Dit betekent dus tri's sorteren ( en roteren! ) zodanig dat vertices zoveel mogelijk worden hergebruikt. De meeste caches zijn 32 vertices groot en werken FIFO. Ik heb vroeger zoiets voor de Ogre 3D engine geschreven, ahgi kun je het er nog steeds in vinden. (IndexVertexBuffer.cpp oid)

Yup, al zou ik dit ook niet zelf schrijven, maar gewoon de NvTriStrip library van nvidia voor gebruiken.. of als je beschikking hebt over DirectX, simpel de functies die in DirectX aanwezig zijn hiervoor.
- D3DXOptimizeFaces
- D3DXOptimizeVertices

zijn een beetje vage functies in gebruik, maar doen een hoop werk voor je..
en ik ben liever lui dan moe..

[.oisyn]

Verwijderd schreef op zondag 07 februari 2010 @ 18:39:

Ja, had wel gelezen, en uiteraard het 'set' idee gezien, maar dat werd om een of andere reden aan de kant geschoven als een niet werkbare oplossing...

Zoals ik in mijn vorige post al zei, het is niet werkbaar als je wilt welden op basis van een threshold (wat voor het OBJ formaat blijkbaar idd niet hoeft, mea culpa). Als je dat niet wilt is een set/map idd een werkbare oplossing.

Ongeacht of dat maar 2 or 3 keer voorkomt, krijg je dus linear search in die nodes, of je moet alsnog een map gaan gebruiken, en daarmee is je algoritme dus niet O(n log n), maar een klein beetje duurder.

Als je een map gebruikt blijft het weldegelijk O(n log n), maar in de praktijk zal de constante factor hoger liggen dan bij de lineair search als er toch maar een paar verts per leaf node hebt. Maar goed, je blijft de ene methode maar vergelijken met de andere, terwijl zoals al gezegd de usecases gewoon verschillen.

Anyway, ik begrijp niet zo goed waarom je zo super hard in de 'aanval' schiet?

Super hard? Kom op zeg . Als je doelt op mijn opmerking over het niet lezen van de topic, die is imho zeer terecht. Je herhaalt wat al gezegd is maar brengt het als iets nieuws.

Doe Jaap trouwens de groeten

[NC83]

Ik gebruik liever geen D3DX functies als ik ze kan vermijden in mijn eigen mesh classes, in DX specifieke gevallen wordt er vaak wel gebruik van gemaakt.
Ik zal eens naar NvTriStrip kijken.

Ik gebruik trouwens geen KD tree maar gewoon een octree die zichzelf splits naar gelang hoeveel vertices zich in een bepaald deel ervan bevinden. Daar alle nodes die geen leaves zijn in deze tree geen data bevaten (heb het nou eenmaal zo opgezet) wordt de compare van de hele vertex enkel op de leaves uitgevoerd. Daarnaast heeft dit hier voordeel dat je een octree voor meer dingen kan gebruiken, en deze dan dus al geimplementeerd is.

Bedankt voor alle info trouwens.

[Killemov]

Verwijderd schreef op zondag 07 februari 2010 @ 18:57:
[...]
Yup, al zou ik dit ook niet zelf schrijven, maar gewoon de NvTriStrip library van nvidia voor gebruiken.. of als je beschikking hebt over DirectX, simpel de functies die in DirectX aanwezig zijn hiervoor.
- D3DXOptimizeFaces
- D3DXOptimizeVertices

zijn een beetje vage functies in gebruik, maar doen een hoop werk voor je..
en ik ben liever lui dan moe..

Ai, het gaat niet om een TriStrip maar om een TriList, en die heeft weer net wat andere behoeftes als het gaat om optimalisatie. Die DX (<v11) functies hebben wat problemen. Ze houden geen rekening met een variabele cache-size en het is lastig om de geoptimaliseerde buffer weer terug te lezen in normaal geheugen.

NC83 schreef op zondag 07 februari 2010 @ 23:22:
Ik gebruik liever geen D3DX functies als ik ze kan vermijden in mijn eigen mesh classes, in DX specifieke gevallen wordt er vaak wel gebruik van gemaakt.

Amen.

NC83 schreef op zondag 07 februari 2010 @ 23:22:
Ik zal eens naar NvTriStrip kijken.

Het gaat niet om een TriStrip (Elke nieuwe vertex (>3) moet een nieuwe triangle vormen.) maar een (Indexed)TriList (Elke 3 (geindexeerde)vertices vormen een nieuwe triangle).

NC83 schreef op zondag 07 februari 2010 @ 23:22:
Ik gebruik trouwens geen KD tree maar gewoon een octree die zichzelf splits naar gelang hoeveel vertices zich in een bepaald deel ervan bevinden. Daar alle nodes die geen leaves zijn in deze tree geen data bevaten (heb het nou eenmaal zo opgezet) wordt de compare van de hele vertex enkel op de leaves uitgevoerd. Daarnaast heeft dit hier voordeel dat je een octree voor meer dingen kan gebruiken, en deze dan dus al geimplementeerd is.

Is dit dan toch een octree met vaste dimensionering (3)? Ik geloof toch niet dat je een blauwe vertex op een locatie moet matchen met een rode vertex op dezelfde locatie. Levert zo'n octree dan echt winst op of alleen maar meer overhead?

[.oisyn]

Killemov schreef op maandag 08 februari 2010 @ 22:16:
Is dit dan toch een octree met vaste dimensionering (3)? Ik geloof toch niet dat je een blauwe vertex op een locatie moet matchen met een rode vertex op dezelfde locatie.

Dat doe je toch al niet, je hebt per leaf een groepje verts dus daar zul je sowieso in moeten zoeken. En zo heel veel vertices per positie met verschillende andere properties zullen er in de regel niet zijn in manifold mesh.

[Verwijderd]

Killemov schreef op maandag 08 februari 2010 @ 22:16:
[...]

Ai, het gaat niet om een TriStrip maar om een TriList, en die heeft weer net wat andere behoeftes als het gaat om optimalisatie. Die DX (<v11) functies hebben wat problemen. Ze houden geen rekening met een variabele cache-size en het is lastig om de geoptimaliseerde buffer weer terug te lezen in normaal geheugen.

Ik quote even van de website van nvidia:

NVTriStrip is a library for vertex cache aware stripification of geometry.
Features:

* generates strips from arbitrary geometry.
* flexibly optimizes for post TnL vertex caches.
* can stitch together strips using degenerate triangles, or not.
* can output lists instead of strips.
* can optionally throw excessively small strips into a list instead.
* can remap indices to improve spatial locality in your vertex buffers.
* API and OS independent.

met de nadruk op:
* can output lists instead of strips.

[NC83]

Ik kwam net zelf een artikel tegen over NVTriStrip die erop deed wijzen dat deze library erg traag is in de orde van enkele 10 tal seconden. Hier te vinden ik geef hier meteen bij toe dat dit om een erg oude implementatie gaat, dus als iemand me het tegendeel kan geven graag. Deze post bewerde trouwens ook dat NVTriStripper niet goed om kan gaan met groote meshes, vanwege int16 indices, is dat nog steeds zo?

[B0rf]

Wat voor datatype gebruik je voor die m_tempIB ? als dat een 'gewone' stl vector is, dan kost de push_back methode waarschijnlijk ook veel tijd. Probeer deze vector vantevoren een grootte te geven met reserve(), zodat niet bij iedere push_back call een geheugenallocatie plaatsvind

[.oisyn]

B0rf schreef op dinsdag 09 februari 2010 @ 13:33:
zodat niet bij iedere push_back call een geheugenallocatie plaatsvind

Je hebt in totaal log N geheugenallocaties, niet N (en dus ook niet bij elke push_back()). Neemt niet weg dat een goede reserve aan te raden is.

[NC83]

Dat is inderdaad iets dat ook nog moet gebeuren hetzelfde geldt trouwens voor de vertex buffer vector die ook gereserved moet worden van te voren.

[Killemov]

Gebruik je nou een trilist of een indexed trilist?

Maar goed, het optimaliseren kan ipc in-place, de resulterende buffer kan alleen maar kleiner worden . Al is het swappen van volledige vertices (dus niet indexed) misschien niet eens meer de moeite waard.

[NC83]

Er wordt gebruik gemaakt van een index triangle list zoals je al had kunnen zien in de addVertex functie.