voila mon pb jai un terrain 3D constitue de 100 000 000 de points dans un fichier texte dont la syntaxe est la suivante
x1;y1;z1;x2;y2;z2 .....
 
comment faire pour que je puisse l'afficher a lecran pour me balader dedans + mofidier mon terrain en temps reel  
 
car stoquer 100 000 000 de points dans un tableau ca nous donne 300 000 000 de int (je bosse pas avec des float) a stoquer quand meme ce qui est impossible
 
la meilleur idee sue jai eut pour linstant est de couper l'enorme fichier de + de 100Mo en pleins de sous fichier (chaque fichier = une zone de 1 000 sur 1 000) et les charger quand j'en ait besoin ..  
au pire jaurrais 4 zones dans mon axe de vue soit 1 000 000 de points stoques au maximum  
 
existe t'il un autre moyen plus simple ou plus intelligent de faire cela ??

fo faire plutot un truc genre table de hachage
 

lecture par blocs...
tu gardes tout dans ton fichier mais tu ne lis que ce qui doit être affiché.

 
  une table de hash de 400Mo  

 
en gros comme mon idee de decouper le gros fichier en pleins de sous fichier  
 
mais non pas faire des miliers de petit fichier mais une sorte de table d'index en memoire pour aller choper les zones souhaite a grand coup de lseek  dans le gros fichier de +100Mo  
 
 

Ouais, c'est l'idée. Ca ira evidement moins vite que de tout monter en mémoire, mais c'est plus propre. Sinon si tu es sous unix, tu peux voir du coté de mmap()

mmap n'est pas scencer maper ton fichier a lecran donc indirectement le loader en memoire ?

en fait j'en sais rien, je m'en suis jamais servi de ce truc, mais j'ose esperer que c'est assez bien foutu pour paginer automatiquement... D'ailleurs c'est visiblement le cas, cf http://campuscgi.princeton.edu/man?mmap

Globalement, ce que tu cherches (si je comprends bien), c'est exactement ce que sait faire un index géographique : étant donné un ensemble (petit ou gigantesque) d'informations localisées dans le plan ou l'espace (voire plus de dimensions), c'est-à-dire chacune étant associée à des coordonnées, on veut pouvoir trouver quels sont les informations qui se trouvent en un point donné ou dans un rectangle/parallélépipède donné.
 
L'algorithme dit du "QuadTree" fonctionne très bien pour des données ponctuelles (i.e. surface/volume nul(le)), dès lors que tu connais les bornes du plan/de l'espace à indexer (i.e. les coordonnées min et max possibles).
 
Le principe est le suivant (je le décris pour la 2D pour faire plus simple, mais l'algorithme est facilement adaptable à n'importe quel nombre de dimensions à partir de 2) :
 

• Etape 1 : soit la région "R0" qui contient toutes tes données

• Etape 2 : tu découpes cette région en 2 parties égales selon chaque dimension ; donc, en 2D, en 4 (en 3D, tu découperais en 8). Appelons ces 4 régions R1, R2, R3 et R4.

• Etape 3 : si tu as encore trop de données dans chaque région, tu découpes chacune encore en 2 suivant chaque dimension, pour obtenir, en 2D, les régions R11, R12, R13, R14, R21, R22, R23, R24, R31, R32, R33, R34, R41, R42, R43 et R44. Et tu recommences le découpage jusqu'à ce que chacune des régions obtenues contienne un nombre raisonnable de données (i.e. pas trop grand ; à toi de décider combien). Cette liste d'informations de taille raisonnable constitue un fichier sur disque.

• Dernière étape, la recherche : quelles sont les données dans ce rectangle/parallélépipède (typiquement celui que tu veux visualiser). A partir des coordonnées de la région à rechercher et des coordonnées min et max possibles, il est assez facile de trouver le numéro de la région ou des régions qui la contien(nen)t, donc le nom du ou des fichiers qui contien(nen)t les informations de cette/ces région(s)-là. Les données que tu recherches sont dedans.

Le nom de "QuadTree" vient du fait que l'on construit par cet algorithme une structure en arbre, dont la racine est R0, et dont les noeuds fils d'un noeud/région Rn sont les 4 sous-régions Rn1, Rn2, Rn3 et Rn4 ("Quad" parce que découpage en 4, pour la 2D).

(truc idiot a deux francs : si tes points sont disposé de facon reguliere tu n'a besoin que de la hauteur)
 
ensuite si j'etais toi je me debarasserais du fichier texte pour un fichier binaire.....
 
pour le reste y'a effectivement le quadtree, ou plus simple , une bete grille. tu decoupe ton terrain en petit secteur (genre 33x33) et tu ne charge que ceux se trouvant pres de toi.  
 
le pb du decoupage en secteur sera l'introduction possible de point redondant en memoire (un point peut appartenir jusqu'a 4 secteurs...) et il te faudra donc prendre ca en compte lorsque tu ajouteras les possibilité d'editions

koulip31 a écrit a écrit :     une table de hash de 400Mo

 
subdiviser ton ensemble en petits secteurs ca revient a hacher, donc ce n'est pas si débile que ca.
 
ceci dit, il manque des données a ton probleme:
si c'est une topologie quelconque, dans ce cas il manque les infos de connectivité des points (comment faire des triangles à partir de tes points). En general pour des terrains on utilise des heightmaps (on ne conserve que la hauteur que l'on echantillonne sur une grille reguliere) ce qui diminue le cout de stockage considerablement et on n'a pas a stocker les infos de connectivité, elle est implicite.
 
Va voir sur le site suivant, il a pas mal bossé sur des problemes similaires au tien:
http://research.microsoft.com/~hoppe/
 
LeGreg