[C++] Grafo con alte performance di attraversamento

[giuseppe500]

ciao.
Devo realizzare un semplice grafo in c++ , che sia il piu veloce possibile nell' attraversamento.
Su google c'è molta roba , il difficile è scegliere.
Mi consigliate della documentazione?
grazie.

[Alex'87]

Originariamente inviato da giuseppe500
Devo realizzare un semplice grafo in c++ , che sia il piu veloce possibile nell' attraversamento

Tradotto? :master:

[giuseppe500]

vorrei creare una classe a cui si possano aggiungere oggetti di tipo CNode, tipo il pattern composite.
Ogni CNode potrà avere a sua volta figli e un parent(uno solo)
Sono indeciso se usare il pattern composite o meno per via delle prestazioni , vorrei che la mia classe fosse la piu performante possibile nell attraversamento dei nodi e dei loro figli.
grazie.

[Ed_Bunker]

Penso che tu debba almeno indicare con quale sia l'aspetto che maggiormente e' importante ai fini dell'applicazione (?).
Inserzione di un nodo ?
Ricerca di un nodo ?
Rimozione di un nodo ?

Quali sono i criteri di "ordinamento" tra i nodi (Se ce ne sono) ?
La visita/attraversamento deve seguire l'ordinamento in questione oppure no ?

[giuseppe500]

Originariamente inviato da Ed_Bunker
Penso che tu debba almeno indicare con quale sia l'aspetto che maggiormente e' importante ai fini dell'applicazione (?).
Inserzione di un nodo ?
Ricerca di un nodo ?
Rimozione di un nodo ?

Quali sono i criteri di "ordinamento" tra i nodi (Se ce ne sono) ?
La visita/attraversamento deve seguire l'ordinamento in questione oppure no ?

allora piu' che l'inserzione / rimozione / ricerca il problema maggiore che richiede maggiori performance è l'attraversamento e per ogni attraversamento il calcolo di:
1)Calcolo matrici di conversione ,le matrici di rotazione , translazione locale vengono moltiplicate per le matrici del nodo padre , in modo che se ho gerarchicamente ad es un nodo tavola con sopra il nodo bottiglia quando ruoto/translo la tavola la bottiglia agisce di conseguenza.
2)bounding box gni nodo ha un vertexbuffer da cui calcolarlo.
il momento in cui va calcolato è quando sono stati ciclati tutti i figli del nodo e calcolati i bounding box dei nodi , a questo punto il bounding box del padre sarà l'insieme dei bounding box dei figli, questo per ottimizzare e non dovere calcolare tutti i bounding box da vertex buffer.
Sempre per ottimizzare una volta creato il bounding box puo' essere semplicemente spostato con la posizione del nodo
3)frustum culling:
ho una classe camera che è racchiusa da 6 piani , semplicemente devo calcolare se il nodo è o meno all interno di questi piani per sapere se visualizzarlo e escluderlo dalla visualizzazione.

per adesso puo bastare.