Problème de gestion d'un octree

**MaxPayne** · 31/03/2005, 09h13

Pour l'affichage de mon sol, j'ai essayé d'implémenter un Octree, voici le code, pour l'instant je n'ai fait que le constructer et le destructeur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**********************************************************************************************************
 * Constructeur par defaut
 **********************************************************************************************************/
Octree::Octree(Point3D p, GLfloat size) : d_p(p), d_size(size) {
 /* Si on est trop grand pour contenir des faces alors, on cree des octree fils */
 if(d_size > d_min_size){
  /* On reserve la place memoire */
  d_fils.reserve(8);
 
  /* Les 4 du haut */
  d_fils.push_back(Octree(Point3D(d_p.d_x, d_p.d_y, d_p.d_z), (d_size / 2)));
  d_fils.push_back(Octree(Point3D(d_p.d_x, d_p.d_y, d_p.d_z - (d_size / 2)), (d_size / 2)));
  d_fils.push_back(Octree(Point3D(d_p.d_x + (d_size / 2), d_p.d_y, d_p.d_z), (d_size / 2)));
  d_fils.push_back(Octree(Point3D(d_p.d_x + (d_size / 2), d_p.d_y, d_p.d_z - (d_size / 2)), (d_size / 2)));
 
  /* Les 4 du bas */
  d_fils.push_back(Octree(Point3D(d_p.d_x, d_p.d_y - (d_size / 2), d_p.d_z), (d_size / 2)));
  d_fils.push_back(Octree(Point3D(d_p.d_x, d_p.d_y - (d_size / 2), d_p.d_z - (d_size / 2)), (d_size / 2)));
  d_fils.push_back(Octree(Point3D(d_p.d_x + (d_size / 2), d_p.d_y - (d_size / 2), d_p.d_z), (d_size / 2)));
  d_fils.push_back(Octree(Point3D(d_p.d_x + (d_size / 2), d_p.d_y - (d_size / 2), d_p.d_z - (d_size / 2)), (d_size / 2)));
 }else{
  /* Sinon cet octree est assez petit pour contenir des faces, alors on reserve de la place pour le vecteur de faces */
  d_faces.reserve(0);
 } 
}
 
 
/**********************************************************************************************************
 * Destructeur par defaut
 **********************************************************************************************************/
Octree::~Octree() {
 /* Si on etait assez petit pour avoir des faces, il faut les effacer */
 if(d_size <= d_min_size){
  d_faces.clear();
 }else{
  /* Sinon on a cree des octree fils, il faut les effacer aussi */
  d_fils.clear();
 }
}

Comme vous pouvez le voir, si l'octree est inférieur à une taille minimale qui est 2.0, alors on reserve de la place pour les futures faces qu'on va lui affecter. S'il est plus grand que 2, on crée 8 octree fils, plus petit de moitié, et on les met dans un vecteur.

Le gros problème, c'est que quand l'octree de base fait 200 de taille, ca prend un temps fou pour que l'octree complet se crée, ca prend 15 Mo de mémoire!!! et lorsque je supprime le monde courant, il reste 1 Mo en mémoire, que je n'arrive pas à effacer.

Est ce quelqu'un qui connait bien le C++, pourrait me dire d'où vient ce problème de mémoire, comment faire pour que ça se crée le plus rapidement possible et que la mémoire se libère complêtement?

Dans Point3D, il n'y a que les coordonnées x,y,z et u,v pour les textures, rien d'autres...

**Ti-R** · 31/03/2005, 15h34

Plusieurs point à optimiser

Précalcul:
(d_size / 2) est appelé un certain nombre de fois, si tu le place dans une variable, cela va aider

Construction par copie:
Quand tu définis Point3D, il construit un objet local, qu'il passe à Octree, Octree recopie cet objet local dans la fonction, puis le recopie une nouvelle fois dans d_p....

Ensuite quand Octree est construit, il est lui même recopié dans d_fils...

Donc si tu utilises des pointeurs avec un peu de mémoire dynamique, cela devrait vraiment aller plus vite.

Voila pour un début

**MaxPayne** · 01/04/2005, 10h26

Merci... lol j'ai programmé comme un bourrin sans réfléchir... en plus ca appelle le Destructeur d'Octree et de Point3D à chaque fois en plus de toutes les recopie, normal que ca rame...

Ca devient ça? (je vais virer le point3D, je stocke juste les 3 coordonnées):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Octree* huhu = new Octree(d_p.d_x, d_p.d_y, d_p.d_z, size)
d_fils.push_back(*huhu);
delete huhu;

j'ai juste encore une question, 15 mo de mémoire c pas un peu abusé, si je monte la taille minimale à 4.0 au lieu de 2.0, j'aurais normalement 8 fois moins de place prise, mais est ce que cela sera efficace? En plus si je décide de faire un monde plus grand que 200.0, et que je prenne 400.0 comme taille de l'octree père (ce qui est le cas dans la plupart des jeux car on ne change pas de map toutes les minutes), et bien ca va faire 8 fois plus de mémoire prise...

Quelle est la taille de vos octree en général et de leur taille minimale? je compte faire du frustum culling sur le cube que décrit les dimensions de l'octree (pour ne pas avoir à faire du frustum culling sur chacune des faces, c la logique de base de l'octree en fait)...

**Ti-R** · 01/04/2005, 11h51

Au lieu de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Octree* huhu = new Octree(d_p.d_x, d_p.d_y, d_p.d_z, size) 
d_fils.push_back(*huhu); 
delete huhu;

je serais + pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Octree* huhu = new Octree(d_p.d_x, d_p.d_y, d_p.d_z, size) 
d_fils.push_back(huhu); 
 
//Et bien plus loin à la fin
delete huhu;
// enfin delete de la list d_fils :)

Car dans ton code tu fais encore une copie d'objet...

**MaxPayne** · 01/04/2005, 16h41

Record battu 3 s!!!

voilà le code pour ceux que ça intéresse :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**********************************************************************************************************
 * Constructeur par defaut
 **********************************************************************************************************/
Octree::Octree(GLfloat x, GLfloat y, GLfloat z, GLfloat size) : d_x(x), d_y(y), d_z(z), d_size(size) {
	/* Si on est trop grand pour contenir des faces alors, on cree des octree fils */
	if(d_size > d_min_size){
		GLfloat middle = (d_size / 2);
 
		/* On reserve la place memoire */
		d_fils.reserve(8);
 
		/* Les 4 du haut */
		d_fils.push_back(new Octree(d_x, d_y, d_z, middle));
		d_fils.push_back(new Octree(d_x, d_y, d_z - middle, middle));
		d_fils.push_back(new Octree(d_x + middle, d_y, d_z, middle));
		d_fils.push_back(new Octree(d_x + middle, d_y, d_z - middle, middle));
 
		/* Les 4 du bas */
		d_fils.push_back(new Octree(d_x, d_y - middle, d_z, middle));
		d_fils.push_back(new Octree(d_x, d_y - middle, d_z - middle, middle));
		d_fils.push_back(new Octree(d_x + middle, d_y - middle, d_z, middle));
		d_fils.push_back(new Octree(d_x + middle, d_y - middle, d_z - middle, middle));
	}else{
		/* Sinon cet octree est assez petit pour contenir des faces, alors on reserve de la place pour le vecteur de faces */
 
	} 
}
 
 
/**********************************************************************************************************
 * Destructeur par defaut
 **********************************************************************************************************/
Octree::~Octree() {
	/* Si on etait assez petit pour avoir des faces, il faut les effacer */
	if(d_size <= d_min_size){
 
	}else{
		for(vector<Octree*>::iterator it = d_fils.begin(); it != d_fils.end(); ++it){
			delete (*it);
		}
 
		/* Sinon on a cree des octree fils, il faut les effacer aussi */
		d_fils.clear();
	}
}

Par contre, pour un octree de depart de 400.0 en taille, et de 2.0 au minimum, ça prend 130 mo de mémoire!!!???, je crois que je vais revoir à la baisse la dimension de l'octree ou a la hausse la taille minimale.

J'ai une autre question quand je charge une première fois mon monde et que je reviens à l'écran d'accueil, y a 10 Mo de mémoire qui reste, et quand je refais l'opération (accueil->monde->accueil), la mémoire est intacte. Il n'y a que la première fois que je perds 10 mi, je captes pas trop là??? C'est déjà arriver à quelqu'un??

**Ti-R** · 01/04/2005, 19h13

Tu peux ensuite optimiser la taille si tu veux

**MaxPayne** · 05/04/2005, 13h15

Ca y est je pense avoir fini, voici les resultats obtenus :

Avec un sol composé de 45000 faces, le moteur 3D, affiche cela à la vitesse de 200 fps, car il n'a plus qu'à afficher 5000 faces, tout le reste ayant été supprimer par frustum culling, les faces appartenant à un octree entièrement dans le frustum ne sont pas testées et sont affichées directement (sans test de frustum). Pour les octrees partiellement dans le frustum, les faces sont testées. De plus, les faces éloignées de nous, de plus de 50.0, ne sont également pas affichée, cela donne donc, un résultat relativement satisfaisant, sachant qu'avant j'étais à 40 fps. et que les tests de collisions avec le sol faisait chuter ce nombre, maintenant ce n'est plus le cas. Je conseille donc à tous l'utilisation d'octree et de frustum culling qui est relativement simple à mettre en oeuvre, et qui est très efficace.

Ce post a surtout pour but de connaître vos résultat pour pouvoir les comparer et savoir si ce que j'ai fait tiens la route ou pas... Donc si vous pouviez essayer de me donner les performances de vos moteurs 3D, ce serait sympa, merci...

Note : j'ai un portable pentium4 2ghz et une carte graphique Geforce 5200.

**Laurent Gomila** · 05/04/2005, 13h32

Pour les octrees partiellement dans le frustum, les faces sont testées. De plus, les faces éloignées de nous, de plus de 50.0, ne sont également pas affichée

A mon avis c'est une perte de temps, le test des faces est en général à éviter pour le frustum culling. Tu vas utiliser beaucoup trop de CPU pour ne virer que quelques centaines de polygones, ce qui restera une broutille pour ton GPU. Rendre entièrement les blocs d'octree partiellement visibles reste la meilleure tactique.

**MaxPayne** · 05/04/2005, 16h18

J'ai essayé, et mon moteur 3D est plus performant lorsque je fais du frustum culling sur les quelques faces qui appartiennent à un octree partiellement dans le frustum.

Je pense que le test de frustum sur ces faces, sont relativement bien optimisé, et prennent moins de temps que les tests qu'exécutent OpenGl, pour savoir si les vertex appartiennent ou non à notre frustum.

Je ne sais pas si mon explication tient la route, mais en tout cas, ca marche mieux chez moi, quand je fais du frustum culling sur les faces.

**bafman** · 06/04/2005, 10h17

et bien ce n'est pas normal

les test effectué sur le GPU sont *nettement* plus rapides que ceux effectué sur le CPU car ils sont branché en dure (en Hardware)...

si c'est plus rapide chez toi ca peut venir d'une surcharge du GPU a ce moment, mais il faut aussi penser que certains ont des cartes graphique plus parformantes que la tienne et qu'eux ne seront plus limité par le GPU mais par le CPU...

Problème de gestion d'un octree

OpenGL

Discussions similaires

Partager

Partager