La requête étant un peu floue, je vais m'en tenir à des généralités.
Il est assez facile de tasser les noeuds - feuille ou interne - d'un tel kD-tree en 8 octets, et si on est attentif celà se fait sans pénalité d'accès.
Code :
- struct node_t {
- struct {
- uint32_t axis : 3; // extraction rapide de l'axe avec un et logique
- uint32_t offset : 32-3-1; // pas besoin de decaler pour calculer l'adresse
- uint32_t leaf : 1; // test simple (signe)
- };
- union {
- float split;
- uint32_t count;
- };
- };
|
L'usage de "déplacement" résoud plusieurs problèmes épineux (64bits etc...) et ce sans surcoût au parcours si on est sioux.
Généralement on a interêt à au moins allouer les noeuds par paire, c.a.d. que gauche & droite sont tjs contigus; celà amène des simplifications quand on traverse (notament pour le calcul d'adresse), une meilleur coherence etc...
Après, et selon les usages, il est possible de descendre à 4 octets, de placer les noeuds de façon à optimiser la cachabilité et autres finasseries. Les variations sont sans fins
Tjs est-il que sous cette forme on peut directement mmapper l'arbre ou le reloger (ce qui permet de "streamer" à la création + mmap derriere).
EDIT: j'ai oublié de préciser que celà supose un alignement idoine.
Message édité par tbp le 10-10-2006 à 09:37:47