commit 46189836f548499ff77e33c4886db48b8b768e67
parent d171be98925f3aba1811330447fd9b8cb968b7cd
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Sun, 18 Dec 2011 22:36:45 +0100
Tas pour le LOD.
Diffstat:
6 files changed, 214 insertions(+), 28 deletions(-)
diff --git a/all_includes.hh b/all_includes.hh
@@ -25,6 +25,7 @@ class Chose;
#include "hash.hh"
#include "view.hh"
+// LOD must be included before chose.hh
#include "lod.hh"
#include "rules/chose.hh"
diff --git a/lod.cpp b/lod.cpp
@@ -33,9 +33,6 @@ Chose* Abr::popIfLessThan(int key) {
}
}
-
-
-
#define NegateEven(v, i) ((v)*(((i)&1) ? 1 : -1))
Lod::Lod(){};
@@ -109,3 +106,132 @@ void Lod::addSplitCube(Chose* chose, int limits[6]) {
split[2*i+1].insert(NegateEven(limits[i],i+1), chose);
}
}
+
+Heap::Heap(int id)
+ : id(id), buckets(new HeapNode*[1]), lastAllocatedBucket(-1),
+ bucketArraySize(1), lastNode(-1) {
+}
+
+void Heap::insert(int 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);
+}
+
+void Heap::remove(int node) {
+ --lastNode;
+
+ if (node > lastNode) { // On a supprimé le dernier noeud.
+ // + 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)];
+
+ // + 1 pour garder au moins un bucket "en cache".
+ if (getBucket(lastNode) + 1 < lastAllocatedBucket) {
+ freeBucket();
+ }
+
+ siftDown(node);
+}
+
+Chose* Heap::popIfLessThan(int key) {
+ if (lastNode >= 0 && buckets[0][0].key < key) {
+ Chose* ret = buckets[0][0].value;
+ remove(0);
+ 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 >= np->key)
+ 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 > nlc->key);
+ bool exchRight = (rc <= lastNode) && (n->key > nrc->key) && (nlc->key > nrc->key);
+ 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/lod.hh b/lod.hh
@@ -28,4 +28,48 @@ class Lod {
void setCamera(float camera[3]);
};
+struct HeapNode {
+ int key;
+ Chose* 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 last+1
+ void freeBucket(); // free last
+ 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:
+ Heap(int id);
+ void insert(int key, Chose* value);
+ void remove(int node);
+ Chose* popIfLessThan(int key);
+};
+
+class LodNode {
+public:
+ int heaps[18];
+ int aabb[6];
+ int inCounter;
+ HeapNode* splitCube[12];
+ HeapNode* mergeCube[6];
+};
+
#endif
diff --git a/main.cpp b/main.cpp
@@ -29,12 +29,20 @@ int main() {
Chose* c = QuartierQuad::factory(Chose::initialSeed, 0, ne, se, sw, nw);
// c->subdivide();
recursiveSubdivide(c);
-
+
+ Heap h(1);
+ (void)h;
+ h.insert(43,c);
+ h.insert(42,c->children[0]);
+ h.popIfLessThan(42); // NULL
+ h.popIfLessThan(43); // c->children[0]
+ h.popIfLessThan(44); // c
+ h.popIfLessThan(44); // NULL
+
View *v = new View(c);
Vertex cc = v->camera.cameraCenter;
float camera[3] = {cc.x, cc.y, cc.z};
camera[0] = camera[0];
Lod lod(camera);
- // tile.subdivide tant qu'on n'a pas le niveau de détail désiré.
return 0;
}
diff --git a/rules/chose.cpp b/rules/chose.cpp
@@ -2,23 +2,16 @@
Chose::Chose() : seed(initialSeed), children() {}
-std::ostream& operator<<(std::ostream& os, const Chose* r) {
- return os << *r;
-}
-
-std::ostream& operator<<(std::ostream& os, const Chose& r) {
- (void)r; // unused
- return os << "Chose";
-}
-
void Chose::addChild(Chose* c) {
children.push_back(c);
- // TODO : Ajouter c dans une file d'attente des éléments pouvant être split.
}
void Chose::addTriangle(Triangle* t) {
triangles.push_back(t);
- // TODO : Ajouter t dans la liste des triangles à envoyer au GPU.
+}
+
+void Chose::merge() {
+ triangles.clear();
}
void Chose::display() {
diff --git a/rules/chose.hh b/rules/chose.hh
@@ -10,6 +10,7 @@ class Chose {
unsigned int seed;
std::vector<Chose*> children;
std::vector<Triangle*> triangles;
+ LodNode lod;
int inCounter;
int splitCube[6];
int mergeCube[6];
@@ -17,25 +18,38 @@ class Chose {
public :
void display();
virtual bool subdivide() = 0;
+ virtual void merge();
protected :
Chose();
- inline void addEntropy(unsigned int x1) { seed = hash2(seed, x1); }
- inline void addEntropy(unsigned int x1, unsigned int x2) { addEntropy(x1); addEntropy(x2); }
- inline void addEntropy(unsigned int x1, unsigned int x2, unsigned int x3) { addEntropy(x1, x2); addEntropy(x3); }
- inline void addEntropy(unsigned int x1, unsigned int x2, unsigned int x3, unsigned int x4) { addEntropy(x1, x2); addEntropy(x3, x4); }
- inline void addEntropy(Vertex v1) { addEntropy(v1.x, v1.y); }
- inline void addEntropy(Vertex v1, Vertex v2) { addEntropy(v1); addEntropy(v2); }
- inline void addEntropy(Vertex v1, Vertex v2, Vertex v3) { addEntropy(v1, v2); addEntropy(v3); }
- inline void addEntropy(Vertex v1, Vertex v2, Vertex v3, Vertex v4) { addEntropy(v1, v2); addEntropy(v3, v4); }
+ inline void addEntropy(unsigned int x1) {
+ seed = hash2(seed, x1);
+ }
+ inline void addEntropy(unsigned int x1, unsigned int x2) {
+ addEntropy(x1); addEntropy(x2);
+ }
+ inline void addEntropy(unsigned int x1, unsigned int x2, unsigned int x3) {
+ addEntropy(x1, x2); addEntropy(x3);
+ }
+ inline void addEntropy(unsigned int x1, unsigned int x2, unsigned int x3, unsigned int x4) {
+ addEntropy(x1, x2); addEntropy(x3, x4);
+ }
+ inline void addEntropy(Vertex v1) {
+ addEntropy(v1.x, v1.y);
+ }
+ inline void addEntropy(Vertex v1, Vertex v2) {
+ addEntropy(v1); addEntropy(v2);
+ }
+ inline void addEntropy(Vertex v1, Vertex v2, Vertex v3) {
+ addEntropy(v1, v2); addEntropy(v3);
+ }
+ inline void addEntropy(Vertex v1, Vertex v2, Vertex v3, Vertex v4) {
+ addEntropy(v1, v2); addEntropy(v3, v4);
+ }
void addChild(Chose* c);
void addTriangle(Triangle* t);
virtual void triangulation() = 0;
virtual std::vector<Vertex*> getBoundingBoxPoints() const = 0;
-
};
-std::ostream& operator<<(std::ostream& os, const Chose& r);
-std::ostream& operator<<(std::ostream& os, const Chose* r);
-
#endif
