commit c8f30f064ee93dc9ae64800582a18cb9da964805
parent f5cf397376564982df372ae8da0224743f13fa73
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Thu, 22 Dec 2011 15:41:56 +0100
Simplification de Lod.
Diffstat:
6 files changed, 52 insertions(+), 44 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,8 +1,9 @@
CXX=g++
# -ansi -pedantic -Wconversion
CCWARN=-Wall -Wextra -Werror
-# -flto (nécessite GCC 4.5) -m32 ou -m64
-CFLAGS=-O0 -I. $(CCWARN)
+# TODO : -O3 -m32 ou -m64
+# -g -rdynamic uniquement pour le debug.
+CFLAGS=-O0 -I. $(CCWARN) -g -rdynamic
SOURCES = $(shell echo *.cpp rules/*.cpp rules/*/*.cpp)
HEADERS = $(shell echo *.hh rules/*.hh rules/*/*.hh)
diff --git a/all_includes.hh b/all_includes.hh
@@ -5,6 +5,9 @@ typedef long long int64;
class Chose;
+// DEBUG
+#include <typeinfo>
+
#include <iostream>
#include <cstdlib>
#include <cmath>
diff --git a/heap.cpp b/heap.cpp
@@ -3,9 +3,9 @@ Heap::Heap()
bucketArraySize(1), lastNode(-1) {
}
-void Heap::setId(int id) { this->id = id; }
+void Heap::init(int id, int factor) { this->id = id; this->factor = factor; }
-void Heap::insert(int key, Chose* value) {
+void Heap::insert(float key, Chose* value) {
{ // DEBUG
int _d_node = value->lod.heaps[id];
if (_d_node <= lastNode && _d_node >= 0 &&
@@ -23,8 +23,6 @@ void Heap::insert(int key, Chose* value) {
siftUp(lastNode);
}
-void handler();
-int global = 0;
void Heap::remove(Chose* value) {
int node = value->lod.heaps[id];
@@ -57,8 +55,12 @@ void Heap::remove(Chose* value) {
siftDown(node);
}
-Chose* Heap::popIfLessThan(int key) {
- if (lastNode >= 0 && buckets[0][0].key < key) {
+bool Heap::lessThan(float a, float b) {
+ return (a * factor < b * factor);
+}
+
+Chose* Heap::popIfLessThan(float key) {
+ if (lastNode >= 0 && buckets[0][0].key * factor < key * factor) {
Chose* ret = buckets[0][0].value;
remove(ret);
return ret;
@@ -75,7 +77,7 @@ void Heap::siftUp(int node) {
break;
int p = parent(node);
np = &(buckets[getBucket(p)][getIndex(p)]);
- if (n->key >= np->key)
+ if (n->key * factor <= np->key * factor)
break;
HeapNode temp = *n;
*n = *np;
@@ -102,8 +104,9 @@ void Heap::siftDown(int node) {
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);
+ 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;
diff --git a/heap.hh b/heap.hh
@@ -1,5 +1,5 @@
struct HeapNode {
- int key;
+ float key;
Chose* value;
};
@@ -19,17 +19,19 @@ private:
inline int getIndex(int node) {
return (node & (bucketSize - 1));
}
- void allocateBucket(); // Allocate into last+1
- void freeBucket(); // free last
+ 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:
+ int factor;
Heap();
- void insert(int key, Chose* value);
+ void insert(float key, Chose* value);
void remove(Chose* value);
- Chose* popIfLessThan(int key);
- void setId(int id);
+ 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
};
diff --git a/lod.cpp b/lod.cpp
@@ -1,8 +1,11 @@
#include "all_includes.hh"
Lod::Lod(Vertex camera, Chose* root) {
- for (int i = 0; i < 6; i++) merge[i].setId(i);
- for (int i = 0; i < 12; i++) split[i].setId(6+i);
+ 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(6+i, (i & 1) ? -1 : 1);
+ }
this->camera[0] = camera.x;
this->camera[1] = camera.y;
this->camera[2] = camera.z;
@@ -18,8 +21,7 @@ void Lod::setCamera(Vertex newCamera) {
// Merge.
for(int i = 0; i < 6; i++) {
Chose* c;
- int pos = NegateEven(camera[i>>1], i);
- while((c = merge[i].popIfLessThan(pos))) {
+ while((c = merge[i].popIfLessThan(camera[i>>1]))) {
for(int j = 0; j < 6; j++) {
if(i == j) continue;
merge[j].remove(c);
@@ -30,18 +32,19 @@ void Lod::setCamera(Vertex newCamera) {
// Split out vers split in.
for(int i = 0; i < 6; i++) {
Chose* c;
- int pos = NegateOdd(camera[i>>1], i);
- while((c = split[2*i+1].popIfLessThan(pos))) {
+ while((c = splitOut[i].popIfLessThan(camera[i>>1]))) {
+ // std::cout << "soi " << c->lod.inCounter + 1 << " ";
+ // std::cout << typeid(*c).name() << " " << c << std::endl;
if(c->lod.inCounter == 5) {
for(int j = 0; j < 6; j++) {
if(i == j) continue;
- split[2*j].remove(c);
+ splitIn[j].remove(c);
}
doSplit(c);
}
else {
c->lod.inCounter++;
- split[2*i].insert(c->lod.splitBox[i], c);
+ splitIn[i].insert(c->lod.splitBox[i], c);
}
}
}
@@ -49,10 +52,9 @@ void Lod::setCamera(Vertex newCamera) {
// Split in vers split out.
for(int i = 0; i < 6; i++) {
Chose* c;
- int pos = NegateEven(camera[i>>1], i);
- while((c = split[2*i].popIfLessThan(pos))) {
+ while((c = splitIn[i].popIfLessThan(camera[i>>1]))) {
c->lod.inCounter--;
- split[2*i+1].insert(c->lod.splitBox[i], c);
+ splitOut[i].insert(c->lod.splitBox[i], c);
}
}
}
@@ -77,24 +79,26 @@ void Lod::doSplit(Chose* c) {
void Lod::addMergeCube(Chose* chose) {
for(int i = 0; i < 5; i++)
- merge[i].insert(NegateEven(chose->lod.mergeBox[i], i), chose);
+ merge[i].insert(chose->lod.mergeBox[i], chose);
}
void Lod::addSplitCube(Chose* chose) {
chose->lod.inCounter = 0;
for(int i = 0; i < 6; i++) {
- if(NegateEven(chose->lod.splitBox[i] - camera[i>>1], i) >= 0) {
+ // std::cout << chose->lod.splitBox[i] << " " << camera[i>>1] << " " << splitOut[i].factor;
+ // std::cout << " " << (splitOut[i].lessThan(chose->lod.splitBox[i], camera[i>>1]) ? "t" : "f");
+ // std::cout << std::endl;
+ if(splitOut[i].lessThan(chose->lod.splitBox[i], camera[i>>1])) {
chose->lod.inCounter++;
- split[2*i].insert(NegateEven(chose->lod.splitBox[i],i), chose);
+ splitIn[i].insert(chose->lod.splitBox[i], chose);
} else {
- split[2*i+1].insert(NegateOdd(chose->lod.splitBox[i],i), chose);
+ splitOut[i].insert(chose->lod.splitBox[i], chose);
}
}
- // TODO : si chose->inCounter == 6, il faut le split immédiatement.
+ // TODO : plutôt que d'ajouter puis enlever, précalculer puis enlever si nécessaire.
if (chose->lod.inCounter == 6) {
- for(int i = 0; i < 6; i++) {
- split[2*i].remove(chose);
- }
+ for(int i = 0; i < 6; i++)
+ splitIn[i].remove(chose);
doSplit(chose);
}
}
diff --git a/lod.hh b/lod.hh
@@ -4,16 +4,11 @@
class Lod {
private :
- Heap merge[6]; // {xMin, xMax, yMin, yMax, zMin, zMax}.
- Heap split[12]; // {xMinIn, xMinOut, xMaxIn, xMaxOut, yMinIn, yMaxOut, yMaxIn, yMaxOut, zMinIn, zMinOut, zMaxIn, zMaxOut}.
+ Heap merge[6]; // {xMin, xMax, yMin, yMax, zMin, zMax}.
+ Heap splitIn[6]; // {xMinIn, xMaxIn, yMinIn, yMaxIn, zMinIn, zMaxIn}.
+ Heap splitOut[6]; // {xMinOut, xMaxOut, yMinOut, yMaxOut, zMinOut, zMaxOut}.
float camera[3];
private:
- inline float NegateEven(float value, int evenodd) {
- return (value*((evenodd&1) ? 1 : -1));
- }
- inline float NegateOdd(float value, int evenodd) {
- return (value*((evenodd&1) ? -1 : 1));
- }
void doSplit(Chose* c);
public :
Lod(Vertex camera, Chose* root);
