[C++] Boomstructuur simpel aflopen

[Verwijderd]

Afgesplitst vanuit De Devschuur Coffee Corner - Iteratie 4

Leuke puzzels, die datastructuren.

Ik heb een octree implementatie. Lekker simpel, node klasse, vectortje van items, 8 pointers naar de volgende node.

C++:

class Node {
    AABB bounding;
    std::vector< Item* > items;
    std::array< std::unique_ptr< Node >, 8 > children;
}

C++11 FTW.

Maar het verhaal is niet zo efficiënt. Worst-case duurt het traversen van de tree voor frustum culling 3ms. Dus ik maak er een platte array van in plaats van pointers en optimalisatie X en Y. Maar nu is de interface van mijn tree totaal aan gort. Hoe traverse ik een boomstructuur als ik de gebruiker geen kennis wil geven van de structuur zelf? Een simpel for ( Node* child : node->children ) is er niet meer bij...

[ Voor 6% gewijzigd door Creepy op 01-10-2013 10:26 ]

[.oisyn]

En wat is er precies mis met node->children() ?

---

Vaag. Win 2012 server VM ingericht, instellingen goed gezet enzo, image gemaakt, tweede VM opgezet vanaf image. Resultaat: tweede server popt wel op in Network, eerste niet. (kan er verder wel naartoe browsen door handmatig de naam in de adresbalk te tikken)

[ Voor 70% gewijzigd door .oisyn op 30-09-2013 23:49 ]

[Verwijderd]

Mijn node is een betekenisloos object net niets meer dan een pointertje naar een object en een een boolean. Ik denk dat ik zo'n 200 a 300 regels aan iterators verder ben voordat iets als node->children() werkt zoals het zou moeten.

Alhoewel de oplossing waar ik nu aan werk ook niet echt netjes is... Ik schrijf eerst iets wat werkt, eventueel refractor ik het later nog als het op meer dan 1 punt gebruikt gaat worden (want ik betwijfel of dat gaat gebeuren).

[ Voor 33% gewijzigd door Verwijderd op 30-09-2013 23:29 ]

[ThomasG]

Verwijderd schreef op maandag 30 september 2013 @ 23:22:
Mijn node is een betekenisloos object net niets meer dan een pointertje naar een object en een een boolean. Ik denk dat ik zo'n 200 a 300 regels aan iterators verder ben voordat iets als node->children() werkt zoals het zou moeten.

Hoe heb je het precies geïmplementeerd? Ik kan zo een pauper-oplossing bedenken waar het met een simpele recursieve N*9+X kan worden opgelost, maar dan zit de performance issue bij het inserten.

[PrisonerOfPain]

Verwijderd schreef op maandag 30 september 2013 @ 22:42:
Maar het verhaal is niet zo efficiënt. Worst-case duurt het traversen van de tree voor frustum culling 3ms. Dus ik maak er een platte array van in plaats van pointers en optimalisatie X en Y. Maar nu is de interface van mijn tree totaal aan gort. Hoe traverse ik een boomstructuur als ik de gebruiker geen kennis wil geven van de structuur zelf? Een simpel for ( Node* child : node->children ) is er niet meer bij...

Lekker je loop omgooien .

C++:

template<typename T>
void walkNodes(Node *n, T lambda)
{
   if(!n) return;
   lambda(n);
   walkNodes(n->n0);
   walkNodes(n->n1);
   walkNodes(n->n2);
   walkNodes(n->n3);
   walkNodes(n->n4);
   walkNodes(n->n5);
   walkNodes(n->n6);
   walkNodes(n->n7);
   walkNodes(n->n8);
}

[Verwijderd]

ThomasG schreef op maandag 30 september 2013 @ 23:29:
[...]
Hoe heb je het precies geïmplementeerd? Ik kan zo een pauper-oplossing bedenken waar het met een simpele recursieve N*9+X kan worden opgelost, maar dan zit de performance issue bij het inserten.

Ik heb hem zoals een in-place binare heap geimplementeerd. Dit minimaliseert volgens mij de ergste performance hit (pointer chasing). Aan het begin alloceert hij een array met genoeg ruimte voor alle nodes ( ~16MB ). Een node is dan:

C++:

    struct Node {
        Node(): item( 0 ), hasChildren( false ) {}
        Item* item; // max. 1 item.
        bool hasChildren;
    };

Als je de index weet van deze node weet je ook zijn children ( index * 8 + 1 t/m index * 8 + 9. Aldus Wikipedia: Binary heap ). Het probleem is dat je ook x/y/z/halfwidth informatie nodig hebt voor de frustum culling. Deze is makkelijk te berekenen tijdens het traversen van de tree.

Maar die informatie moet ook naar buiten beschikbaar zijn. Dat kost wat moeite om 'volgens het boekje' te implementeren.

PrisonerOfPain schreef op maandag 30 september 2013 @ 23:51:
[...]


Lekker je loop omgooien .

C++:

template<typename T>
void walkNodes(Node *n, T lambda)
{
   if(!n) return;
   lambda(n);
   walkNodes(n->n0);
   walkNodes(n->n1);
   walkNodes(n->n2);
   walkNodes(n->n3);
   walkNodes(n->n4);
   walkNodes(n->n5);
   walkNodes(n->n6);
   walkNodes(n->n7);
   walkNodes(n->n8);
}

Als dat op 1 plek moet is het niet erg. Maar als die klasse op 20 plekken wordt gebruikt zou ik het jammer vinden als iemand op voorhand niet de moeite heeft genomen er een iterator voor te schrijven.

[ Voor 22% gewijzigd door Verwijderd op 01-10-2013 00:01 ]

[PrisonerOfPain]

Verwijderd schreef op maandag 30 september 2013 @ 23:56:
[...]

Ik heb hem zoals een in-place binare heap geimplementeerd. Dit minimaliseert volgens mij de ergste performance hit (pointer chasing). Aan het begin alloceert hij een array met genoeg ruimte voor alle nodes ( ~16MB ). Een node is dan:

Kun je je octree niet linear opslaan met een space filling curve - dan zou je van idx naar xyz en xyz naar idx kunnen. En dan hoef je meteen ook geen pointers meer op te slaan.

[ Voor 5% gewijzigd door PrisonerOfPain op 01-10-2013 00:16 ]

[PrisonerOfPain]

Holy crap dat is een prachtig idee Ik denk dat ik daar binnenkort maar eens een implementatie van uit ga tikken.

[Verwijderd]

Ik sla geen pointers naar de datastructuur op, alleen pointers naar het item wat in de structuur zit opgeslagen.

Die space filling curve ken ik nog niet. Ik ken, en misbruik op grote schaal, wel de cantor pairing function en afgeleiden. Kan je met een space filling curve in O( 1 ) van een index naar x/y/z/width komen? Op de lineaire opslag manier kan dat volgens mij alleen proportioneel aan de diepte van de boom.

Ik zie niet hoe je dat voor je ziet met die space filling curve..

[ Voor 7% gewijzigd door Verwijderd op 01-10-2013 00:31 ]

[PrisonerOfPain]

Verwijderd schreef op dinsdag 01 oktober 2013 @ 00:28:
Ik sla geen pointers naar de datastructuur op, alleen pointers naar het item wat in de structuur zit opgeslagen.

Je hebt je std::array<> daar toch nog zitten? Die kan dan weg

Kan je met een space filling curve in O( 1 ) van een index naar x/y/z/width komen?

Wikipedia: Hilbert curve zie de xy2d functie (en d2xy). Die zijn constant voor de width (pow-of-two) van je grid.

[ Voor 6% gewijzigd door PrisonerOfPain op 01-10-2013 00:32 ]

[Verwijderd]

PrisonerOfPain schreef op dinsdag 01 oktober 2013 @ 00:32:
[...]

Je hebt je std::array<> daar toch nog zitten? Die kan dan weg

Dat is de oude implementatie. De nieuwe gebruikt een hele lange std::vector van

C++:

    struct Node {
        Node(): item( 0 ), hasChildren( false ) {}
        Item* item; // max. 1 item.
        bool hasChildren;
    };

Als ik in O(1) van index naar x/y/z kan zou dat veel complexiteit schelen.

PrisonerOfPain schreef op dinsdag 01 oktober 2013 @ 00:32:


Wikipedia: Hilbert curve zie de xy2d functie (en d2xy). Die zijn constant voor de width (pow-of-two) van je grid.

Someone beat you to it: http://blog.notdot.net/20...dtrees-and-Hilbert-Curves

[ Voor 29% gewijzigd door Verwijderd op 01-10-2013 00:38 ]

[PrisonerOfPain]

Kortom, klinkt als een goed idee

[Verwijderd]

xy2d en 2dxy zijn O( n ) aan de diepte van de boom. Daar heb je dus -in mijn situatie- niet zoveel aan. Behalve als je denkt dat een struct van 12 bytes een ergere performance kill is dan het berekenen van de hilbert curve.

Cantor pairing is O( 1 ). Maar het converteren van 2d naar 1d is significant minder expensieve dan andersom. (sqrt enzo). Die mapping functies gebruik ik onder andere voor mijn perlin noise: hij mapt 2D naar 1D, en 'on demand' 1D noise genereren is een stuk minder complex dan 2D noise.

[ Voor 3% gewijzigd door Verwijderd op 01-10-2013 01:01 ]

[PrisonerOfPain]

Verwijderd schreef op dinsdag 01 oktober 2013 @ 00:59:
xy2d en 2dxy zijn O( n ) aan de diepte van de boom. Daar heb je dus -in mijn situatie- niet zoveel aan. Behalve als je denkt dat een struct van 12 bytes een ergere performance kill is dan het berekenen van de hilbert curve.

Dan pak je een morton curve - dat is sowieso O(1) omdat dat een simpele bit-interleave is.

[.oisyn]

Verwijderd schreef op maandag 30 september 2013 @ 23:22:
Mijn node is een betekenisloos object net niets meer dan een pointertje naar een object en een een boolean. Ik denk dat ik zo'n 200 a 300 regels aan iterators verder ben voordat iets als node->children() werkt zoals het zou moeten.

Dan doe je tree->children(node).

[Verwijderd]

Ik heb nu tree->child( node, childno ) ...

Die returnt een node, waarmee ik vervolgens tree->getItem( node ) kan doen.

[ Voor 49% gewijzigd door Verwijderd op 01-10-2013 01:20 ]

[.oisyn]

Maar wat winnen al die filling curves je? 't Nadeel van al die structuren is dat ze niet sparse kunnen zijn.

Ik gebruik zoiets in onze renderer:

C++:

struct node
{
    // ...
    bool leaf;
    node * nextSibling;
};

Waarbij het eerste kind (if any) simpelweg op node+1 staat, en het tweede kind direct na alle descendents van het eerste kind, en dat is tevens waar nextSibling naar wijst. Enzovoorts voor de rest van de kinderen. De kinderen zijn dus effectief een gelinkte lijst.

Als je een depth-first search doet, wat nogal typisch is, loop je alle nodes simpelweg van voor naar achter af. Sterker nog, die search kun je met een simpel loopje implementeren*. Een subtree skippen doe je door simpelweg de nextSibling pointer te volgen. Ook een voordeel van deze structuur is dat elke subboom op zichzelf ook compleet contiguous is. Handig voor dingen als streaming content, het opdelen over meerdere threads, etc.


* Vereist wel dat nextSibling van de laatste child naar de volgende sibling van de parent wijst.

C++:

template<class T>
void depth_first_search(node * n, node * end, T visitor)
{
    while(n < end)
    {
        if (visitor(n))
            n++;
        else
            n = n->nextSibling;
    }
}

nextSibling kan ook simpelweg een distance vanaf de huidige node zijn, handig voor serialization

[ Voor 9% gewijzigd door .oisyn op 01-10-2013 01:55 ]

[Verwijderd]

Dat de datstructuur niet sparse is vind ik voor deze applicatie niet erg. Het memory verbruik valt mee ( max ~16MB ) en de octree dient enkel voor de chunk visibility.

Ik bedacht me verder nog iets. Mijn link ziet er zo uit:

code:

    struct Link {
        Link() : chunk( 0 ), hasChildren( false ) {}
        Chunk* chunk;
        bool hasChildren;
    };

Maar msvc voegt padding toe dus de structuur is 16 bytes op een x64 platform. Ik kan dus 3 shorts en en byte erbij opslaan zonder enige memory overhead. De coordinaten passen in die 3 shorts (die optimalisatie heb ik immers ook in de shader gedaan) en die extra byte kan ik gebruiken voor een macht van 2. Zonder dat de datastructuur groter wordt. Daar had ik eerder aan moeten denken .

---

challange successfull: frustum + occlusion culling was 2.7ms, nu 2.0ms. Ik kan nog wat winnen door het een en ander te inlinen, dat doet de compiler erg slecht. Verder is de frustum cuiling zelf ( niet het traversen van de graph ) nog niet met SSE/AVX geoptimaliseerd.

[ Voor 15% gewijzigd door Verwijderd op 01-10-2013 03:13 ]

[Zoijar]

PrisonerOfPain schreef op dinsdag 01 oktober 2013 @ 01:09:
Dan pak je een morton curve - dat is sowieso O(1) omdat dat een simpele bit-interleave is.

Ik heb in het verleden ook altijd morton gebruikt.

Volgens mij nog met dank aan jullie:

C++:

inline static quint32 interleave(quint32 x, quint32 y) {
    static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
    static const unsigned int S[] = {1, 2, 4, 8};

    x = (x | (x << S[3])) & B[3];
    x = (x | (x << S[2])) & B[2];
    x = (x | (x << S[1])) & B[1];
    x = (x | (x << S[0])) & B[0];

    y = (y | (y << S[3])) & B[3];
    y = (y | (y << S[2])) & B[2];
    y = (y | (y << S[1])) & B[1];
    y = (y | (y << S[0])) & B[0];

    return x | (y << 1);
}

inline static void deinterleave(quint32 z, quint16* x, quint16* y) {
    static const unsigned int B[] = {0x33333333, 0X0F0F0F0F, 0X00FF00FF, 0X0000FFFF};
    static const unsigned int S[] = {1, 2, 4, 8};

    quint32 w = z >> 1;

    z &= 0x55555555;
    z = (z ^ (z >> S[0])) & B[0];
    z = (z ^ (z >> S[1])) & B[1];
    z = (z ^ (z >> S[2])) & B[2];
    z = (z ^ (z >> S[3])) & B[3];

    w &= 0x55555555;
    w = (w ^ (w >> S[0])) & B[0];
    w = (w ^ (w >> S[1])) & B[1];
    w = (w ^ (w >> S[2])) & B[2];
    w = (w ^ (w >> S[3])) & B[3];

    *x = z;
    *y = w;
}

inline static void deinterleave2(quint32 z, quint16 *x, quint16 *y) {
    z = ((z & 0x0000aaaa) << 15) | (z & 0xaaaa5555) | ((z & 0x55550000) >> 15);
    z = ((z & 0x00aa00aa) <<  7) | (z & 0xaa55aa55) | ((z & 0x55005500) >>  7);
    z = ((z & 0x0a0a0a0a) <<  3) | (z & 0xa5a5a5a5) | ((z & 0x50505050) >>  3);
    z = ((z & 0x22222222) <<  1) | (z & 0x99999999) | ((z & 0x44444444) >>  1);
    *x = z;
    *y = z>>16;
}

[PrisonerOfPain]

Verwijderd schreef op dinsdag 01 oktober 2013 @ 02:03:

Maar msvc voegt padding toe dus de structuur is 16 bytes op een x64 platform. Ik kan dus 3 shorts en en byte erbij opslaan zonder enige memory overhead.

Als je minder geheugen wilt gebruiken kun je ook die boolean in je alignment prutten.

C++:

class link
{
     link *get_link() const { (link*)(data & ~1); }
     bool is_leaf() const { data & 1 == 1; }

     void set_leaf(bool l) { data = (data & ~1) | l; }

     uintptr_t data;
};

[PrisonerOfPain]

.oisyn schreef op dinsdag 01 oktober 2013 @ 01:48:
Maar wat winnen al die filling curves je? 't Nadeel van al die structuren is dat ze niet sparse kunnen zijn.

En zodra je ze wel sparse opslaat is je traversal ineens super kut.

[Verwijderd]

In de structuur die .oisyn heeft laten zien kun je theoretisch een sparse tree maken die wel contiguous in memory staat. Maar dat vereist een O(n) memcpy bij inserts/delete. Op zich niet heel spannend als je slechts een item per zoveel frames insert/delete. Modify doe ik niet.

Je doet daarbij wel de O( log(n) ) insert/delete te niet.

[ Voor 11% gewijzigd door Verwijderd op 01-10-2013 12:47 ]

[Soultaker]

Trouwens, voor de goede orde: de binaire heap waar je het over hebt is noch binair, noch een heap.

[.oisyn]

PrisonerOfPain schreef op dinsdag 01 oktober 2013 @ 10:54:
[...]


En zodra je ze wel sparse opslaat is je traversal ineens super kut.

nonsens, zoals ik al liet zien.

@darkstone: onze trees zijn offline gecookt en worden in de runtime niet aangepast.

[ Voor 15% gewijzigd door .oisyn op 01-10-2013 14:40 ]

[PrisonerOfPain]

.oisyn schreef op dinsdag 01 oktober 2013 @ 14:39:
[...]

nonsens, zoals ik al liet zien.

Sparse met behulp van de space filling cuve

[.oisyn]

Oh zo