commit 546781be3649e910386af97d6434857c5aab3bed
parent 53b6f69f94e6031bbfc0521dec1d58424a06ac1f
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Mon, 16 Jan 2012 15:35:32 +0100
Correction de la fuite mémoire du LOD.
Diffstat:
8 files changed, 90 insertions(+), 191 deletions(-)
diff --git a/all_includes.hh b/all_includes.hh
@@ -10,7 +10,8 @@ class Chose;
#include <cstdlib>
#include <cmath>
#include <vector>
-#include <map>
+//#include <map>
+#include <set>
#include <SDL/SDL.h>
#include <GL/glew.h>
diff --git a/heap.cpp b/heap.cpp
@@ -1,42 +1,16 @@
-Heap::Heap()
- : buckets(new HeapNode*[1]), lastAllocatedBucket(-1),
- bucketArraySize(1), lastNode(-1) {
+#include "all_includes.hh"
+
+Heap::Heap() {
}
-void Heap::init(int _id, int _factor) { this->id = _id; this->factor = (float)_factor; }
+void Heap::init(int _factor) { factor = (float)_factor; }
void Heap::insert(float key, Chose* value) {
- ++lastNode;
- if (getBucket(lastNode) > lastAllocatedBucket) {
- allocateBucket();
- }
- buckets[getBucket(lastNode)][getIndex(lastNode)].key = key;
- buckets[getBucket(lastNode)][getIndex(lastNode)].value = value;
- siftUp(lastNode);
+ bst.insert(HeapNode(key * factor, value));
}
-void Heap::remove(Chose* value) {
- int node = value->lod.heaps[id];
-
- if (node == lastNode) { // On a supprimé le dernier noeud.
- --lastNode;
- // + 1 pour garder au moins un bucket "en cache".
- if (getBucket(lastNode) + 1 < lastAllocatedBucket)
- freeBucket();
- return;
- }
-
- buckets[getBucket(node)][getIndex(node)] = \
- buckets[getBucket(lastNode)][getIndex(lastNode)];
-
- --lastNode;
-
- // + 1 pour garder au moins un bucket "en cache".
- if (getBucket(lastNode) + 1 < lastAllocatedBucket) {
- freeBucket();
- }
-
- siftDown(node);
+void Heap::remove(float key, Chose* value) {
+ bst.erase(HeapNode(key * factor, value));
}
bool Heap::lessThan(float a, float b) {
@@ -44,95 +18,11 @@ bool Heap::lessThan(float a, float b) {
}
Chose* Heap::popIfLessThan(float key) {
- if (lastNode >= 0 && buckets[0][0].key * factor < key * factor) {
- Chose* ret = buckets[0][0].value;
- remove(ret);
+ std::set<HeapNode>::iterator min = bst.begin();
+ if (min != bst.end() && min->key < key * factor) {
+ Chose* ret = min->value;
+ bst.erase(min);
return ret;
}
return NULL;
}
-
-void Heap::siftUp(int node) {
- HeapNode* n;
- HeapNode* np;
- while (true) {
- n = &(buckets[getBucket(node)][getIndex(node)]);
- if (node <= 0)
- break;
- int p = parent(node);
- np = &(buckets[getBucket(p)][getIndex(p)]);
- if (n->key * factor >= np->key * factor) //!!!!!
- break;
- HeapNode temp = *n;
- *n = *np;
- *np = temp;
- // mettre à jour le champ lod.heaps[id] de l'ancien parent qu'on
- // vient de descendre.
- n->value->lod.heaps[id] = node;
- node = p;
- }
- // après les break; qui sortent de la boucle, on a déjà actualisé
- // le pointeur `n` vers buckets[getBucket(node)][getIndex(node)].
- n->value->lod.heaps[id] = node;
-}
-
-void Heap::siftDown(int node) {
- HeapNode* n;
- HeapNode* nlc;
- HeapNode* nrc;
- while (true) {
- n = &(buckets[getBucket(node)][getIndex(node)]);
- int lc = leftchild(node);
- int rc = rightchild(node);
- nlc = &(buckets[getBucket(lc)][getIndex(lc)]);
- nrc = &(buckets[getBucket(rc)][getIndex(rc)]);
- // exchLeft et exchRight peuvent être tout deux true. Dans ce
- // cas, c'est exchRight qui gagne.
- bool exchLeft = (lc <= lastNode) && (n->key * factor > nlc->key * factor);
- bool exchRight = (rc <= lastNode) && (n->key * factor > nrc->key * factor);
- exchRight = exchRight && (nlc->key * factor > nrc->key * factor);
- if ((!exchLeft) && (!exchRight))
- break;
- HeapNode temp = *n;
- if (exchRight) {
- *n = *nrc;
- *nrc = temp;
- } else {
- *n = *nlc;
- *nlc = temp;
- }
- // mettre à jour le champ lod.heaps[id] de l'ancien fils qu'on
- // vient de remonter.
- n->value->lod.heaps[id] = node;
- node = (exchRight ? rc : lc);
- }
- // après les break; qui sortent de la boucle, on a déjà actualisé
- // le pointeur `n` vers buckets[getBucket(node)][getIndex(node)].
- n->value->lod.heaps[id] = node;
-}
-
-void Heap::allocateBucket() {
- ++lastAllocatedBucket;
- if (lastAllocatedBucket >= bucketArraySize) {
- HeapNode** old = buckets;
- buckets = new HeapNode*[bucketArraySize*2];
- for (int i = 0; i < lastAllocatedBucket; i++)
- buckets[i] = old[i];
- delete[] old;
- bucketArraySize *= 2;
- }
- buckets[lastAllocatedBucket] = new HeapNode[bucketSize];
-}
-
-void Heap::freeBucket() {
- delete[] buckets[lastAllocatedBucket];
- --lastAllocatedBucket;
- if (lastAllocatedBucket * 4 < bucketArraySize && bucketArraySize > 1) {
- HeapNode** old = buckets;
- buckets = new HeapNode*[bucketArraySize/2];
- for (int i = 0; i <= lastAllocatedBucket; i++)
- buckets[i] = old[i];
- delete[] old;
- bucketArraySize /= 2;
- }
-}
diff --git a/heap.hh b/heap.hh
@@ -1,42 +1,29 @@
#ifndef _HEAP_HH_
#define _HEAP_HH_
-struct HeapNode {
+#include "all_includes.hh"
+
+class HeapNode {
+public:
+ HeapNode(float _key, Chose* _value) : key(_key), value(_value) {};
float key;
Chose* value;
+ friend bool operator< (const HeapNode &a, const HeapNode &b) {
+ return (a.key < b.key || (a.key == b.key && a.value < b.value));
+ }
};
class Heap {
private:
- int id;
- static const int log2BucketSize = 9; // 2^9 = 512
- static const int bucketSize = (1 << log2BucketSize);
- HeapNode** buckets;
- int lastAllocatedBucket;
- int bucketArraySize;
- int lastNode;
-private:
- inline int getBucket(int node) {
- return (node >> log2BucketSize);
- }
- inline int getIndex(int node) {
- return (node & (bucketSize - 1));
- }
- void allocateBucket(); // Allocate into lastAllocatedBucket+1
- void freeBucket(); // free lastAllocatedBucket
- void siftUp(int node);
- void siftDown(int node);
- inline int parent(int node) { return (node - 1)/2; }
- inline int leftchild(int node) { return node * 2 + 1; }
- inline int rightchild(int node) { return node * 2 + 2; }
-public:
+ std::set<HeapNode> bst;
float factor; // -1.f ou +1.f
+public:
Heap();
void insert(float key, Chose* value);
- void remove(Chose* value);
+ void remove(float key, Chose* value);
Chose* popIfLessThan(float key);
bool lessThan(float a, float b); // Renvoie true ssi a < b dans l'ordre du tas.
- void init(int id, int factor); // factor = -1 pour tas Min, 1 pour tas max
+ void init(int factor); // factor = -1 pour tas Min, 1 pour tas max
};
#endif
diff --git a/lod.cpp b/lod.cpp
@@ -2,9 +2,9 @@
Lod::Lod(Vertex _camera, Chose* root) {
for (int i = 0; i < 6; i++) {
- merge[i].init(i, (i & 1) ? 1 : -1);
- splitIn[i].init(6+i, (i & 1) ? 1 : -1);
- splitOut[i].init(12+i, (i & 1) ? -1 : 1);
+ merge[i].init((i & 1) ? 1 : -1);
+ splitIn[i].init((i & 1) ? 1 : -1);
+ splitOut[i].init((i & 1) ? -1 : 1);
}
this->camera[0] = _camera.x;
this->camera[1] = _camera.y;
@@ -24,7 +24,7 @@ void Lod::setCamera(Vertex newCamera) {
while((c = merge[i].popIfLessThan(camera[i>>1]))) {
for(int j = 0; j < 6; j++) {
if(i == j) continue;
- merge[j].remove(c);
+ merge[j].remove(c->lod.mergeBox[j], c);
}
doMerge(c);
}
@@ -36,7 +36,7 @@ void Lod::setCamera(Vertex newCamera) {
if(c->lod.inCounter == 5) {
for(int j = 0; j < 6; j++) {
if(i == j) continue;
- splitIn[j].remove(c);
+ splitIn[j].remove(c->lod.splitBox[j], c);
}
doSplit(c);
}
@@ -58,7 +58,6 @@ void Lod::setCamera(Vertex newCamera) {
}
void Lod::doSplit(Chose* c) {
- // TODO
if (c->split()) {
std::vector<Chose*>::iterator it;
for (it = c->children.begin(); it != c->children.end(); ++it) {
@@ -78,10 +77,23 @@ void Lod::doSplit(Chose* c) {
}
void Lod::doMerge(Chose* c) {
- c->merge();
+ doSubMerge(c);
addSplitCube(c);
}
+void Lod::doSubMerge(Chose* c) {
+ std::vector<Chose*>::iterator it;
+ for (it = c->children.begin(); it != c->children.end(); ++it) {
+ for(int j = 0; j < 6; j++) {
+ merge[j].remove((*it)->lod.mergeBox[j], (*it));
+ splitIn[j].remove((*it)->lod.splitBox[j], (*it));
+ splitOut[j].remove((*it)->lod.splitBox[j], (*it));
+ }
+ doSubMerge(*it);
+ }
+ c->merge();
+}
+
void Lod::addMergeCube(Chose* chose) {
// Innutile de détecter si l'on est déjà sortis de la mergeBox :
// comme elle est plus grosse que la splitBox, on est forcément
@@ -90,20 +102,20 @@ void Lod::addMergeCube(Chose* chose) {
merge[i].insert(chose->lod.mergeBox[i], chose);
}
-void Lod::addSplitCube(Chose* chose) {
- chose->lod.inCounter = 0;
+void Lod::addSplitCube(Chose* c) {
+ c->lod.inCounter = 0;
for(int i = 0; i < 6; i++) {
- if(splitOut[i].lessThan(chose->lod.splitBox[i], camera[i>>1])) {
- chose->lod.inCounter++;
- splitIn[i].insert(chose->lod.splitBox[i], chose);
+ if(splitOut[i].lessThan(c->lod.splitBox[i], camera[i>>1])) {
+ c->lod.inCounter++;
+ splitIn[i].insert(c->lod.splitBox[i], c);
} else {
- splitOut[i].insert(chose->lod.splitBox[i], chose);
+ splitOut[i].insert(c->lod.splitBox[i], c);
}
}
// TODO : plutôt que d'ajouter puis enlever, précalculer puis enlever si nécessaire.
- if (chose->lod.inCounter == 6) {
+ if (c->lod.inCounter == 6) {
for(int i = 0; i < 6; i++)
- splitIn[i].remove(chose);
- doSplit(chose);
+ splitIn[i].remove(c->lod.splitBox[i], c);
+ doSplit(c);
}
}
diff --git a/lod.hh b/lod.hh
@@ -14,6 +14,7 @@ private :
private:
void doSplit(Chose* c);
void doMerge(Chose* c);
+ void doSubMerge(Chose* c);
public :
Lod(Vertex camera, Chose* root);
void addMergeCube(Chose* chose);
@@ -22,7 +23,6 @@ public :
};
struct LodNode {
- int heaps[18];
float aabb[6];
float splitBox[6];
float mergeBox[6];
diff --git a/rules/chose.cpp b/rules/chose.cpp
@@ -3,11 +3,18 @@
Chose::Chose() : seed(initialSeed), children() {
}
-// TODO : Le destructeur est-il vraiment nécessaire ?
-// TODO : Vu que children et triangles contiennent des pointeurs, le .clear() risque de ne pas les désallouer !
+
+void Chose::clearChildren() {
+ std::vector<Chose*>::iterator it;
+ for (it = children.begin(); it != children.end(); it++)
+ // TODO : d'abbord virer *it des arbres de LOD !
+ delete *it;
+ children.clear();
+}
+
Chose::~Chose() {
- children.clear();
- triangles.clear();
+ clearChildren();
+ triangles.clear();
}
void Chose::addChild(Chose* c) {
@@ -15,9 +22,9 @@ void Chose::addChild(Chose* c) {
}
bool Chose::merge() {
- children.clear();
+ clearChildren();
// triangles.clear();
- return true;
+ return true;
}
void Chose::addGPUTriangle(Vertex left, Vertex top, Vertex right, unsigned int rgb) {
@@ -29,8 +36,8 @@ void Chose::addGPUTriangle(Triangle t, unsigned int rgb) {
}
void Chose::addGPUQuad(Vertex ne, Vertex se, Vertex sw, Vertex nw, unsigned int rgb) {
- this->addGPUTriangle(nw, ne, se, rgb);
- this->addGPUTriangle(se, sw, nw, rgb);
+ this->addGPUTriangle(nw, ne, se, rgb);
+ this->addGPUTriangle(se, sw, nw, rgb);
}
void Chose::addGPUQuad(Quad q, unsigned int rgb) {
@@ -38,15 +45,15 @@ void Chose::addGPUQuad(Quad q, unsigned int rgb) {
}
void Chose::addGPUOcto(Vertex ne, Vertex se, Vertex sw, Vertex nw,
- Vertex neh, Vertex seh, Vertex swh, Vertex nwh, unsigned int rgb) {
+ Vertex neh, Vertex seh, Vertex swh, Vertex nwh, unsigned int rgb) {
addGPUOcto(Quad(ne,se,sw,nw), Quad(neh,seh,swh,nwh), rgb);
}
void Chose::addGPUOcto(Quad q, Quad qh, unsigned int rgb) {
- this->addGPUQuad(q[SE], q[NE], q[NW], q[SW], rgb);
- this->addGPUQuad(qh[NE], qh[SE], qh[SW], qh[NW], rgb);
- for (int i = 0; i < 4; i++)
- this->addGPUQuad(q[NE+i], q[SE+i], qh[SE+i], qh[NE+i], rgb);
+ this->addGPUQuad(q[SE], q[NE], q[NW], q[SW], rgb);
+ this->addGPUQuad(qh[NE], qh[SE], qh[SW], qh[NW], rgb);
+ for (int i = 0; i < 4; i++)
+ this->addGPUQuad(q[NE+i], q[SE+i], qh[SE+i], qh[NE+i], rgb);
}
void Chose::display() {
@@ -144,15 +151,15 @@ void Chose::updateAABB() {
// DEBUG
void Chose::drawAABB() {
addGPUOcto(
- Vertex(lod.splitBox[0], lod.splitBox[2], lod.splitBox[4]),
- Vertex(lod.splitBox[1], lod.splitBox[2], lod.splitBox[4]),
- Vertex(lod.splitBox[1], lod.splitBox[3], lod.splitBox[4]),
- Vertex(lod.splitBox[0], lod.splitBox[3], lod.splitBox[4]),
- Vertex(lod.splitBox[0], lod.splitBox[2], lod.splitBox[5]),
- Vertex(lod.splitBox[1], lod.splitBox[2], lod.splitBox[5]),
- Vertex(lod.splitBox[1], lod.splitBox[3], lod.splitBox[5]),
- Vertex(lod.splitBox[0], lod.splitBox[3], lod.splitBox[5]),
- hash2(seed, 42) & 0xffffff
+ Vertex(lod.splitBox[0], lod.splitBox[2], lod.splitBox[4]),
+ Vertex(lod.splitBox[1], lod.splitBox[2], lod.splitBox[4]),
+ Vertex(lod.splitBox[1], lod.splitBox[3], lod.splitBox[4]),
+ Vertex(lod.splitBox[0], lod.splitBox[3], lod.splitBox[4]),
+ Vertex(lod.splitBox[0], lod.splitBox[2], lod.splitBox[5]),
+ Vertex(lod.splitBox[1], lod.splitBox[2], lod.splitBox[5]),
+ Vertex(lod.splitBox[1], lod.splitBox[3], lod.splitBox[5]),
+ Vertex(lod.splitBox[0], lod.splitBox[3], lod.splitBox[5]),
+ hash2(seed, 42) & 0xffffff
);
}
diff --git a/rules/chose.hh b/rules/chose.hh
@@ -5,14 +5,14 @@
// RectangleRoutes est un quadrilatère de routes avec des angles aux coins égaux à 90°.
class Chose {
- public :
+public :
static unsigned int initialSeed;
unsigned int seed;
std::vector<Chose*> children;
std::vector<GPUTriangle*> triangles;
LodNode lod;
- public :
+public :
void display();
void displayNormals();
void drawAABB(); // DEBUG
@@ -21,7 +21,7 @@ class Chose {
virtual void triangulation() { triangles.clear(); };
virtual void updateAABB();
- protected :
+protected :
void addBBPoint(const Vertex v);
void addBBPoints(const Triangle t);
void addBBPoints(const Triangle t, float height);
@@ -70,6 +70,8 @@ class Chose {
Vertex neh, Vertex seh, Vertex swh, Vertex nwh,
unsigned int rgb);
void addGPUOcto(Quad q, Quad qh, unsigned int rgb);
+private:
+ void clearChildren();
};
#endif
diff --git a/view.cpp b/view.cpp
@@ -2,7 +2,7 @@
View::View(Chose* _root)
: root(_root),
- camera(Camera(Vertex(9600,10000,15300),0,179,1000,0.6f)),
+ camera(Camera(Vertex(9600,10000,15300 + 80000),0,179,1000,0.6f)),
lod(camera.cameraCenter, _root) {
fogColor[0] = 0.5;
@@ -152,7 +152,7 @@ void View::mainLoop() {
short continuer = 1;
SDL_Event event;
SDL_EnableKeyRepeat(40,40);
- SDL_WM_GrabInput(SDL_GRAB_ON);
+ SDL_WM_GrabInput(SDL_GRAB_OFF);
SDL_ShowCursor(SDL_DISABLE);
while ( SDL_PollEvent(&event) ); // empty queue.
