commit 86c862658666b2ef73fdac3a6b2d791293851f65
parent d97593d9995fc6dcdcd44d68bb7375896e8ec62e
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Mon, 28 Nov 2011 07:41:30 +0100
Zut
Diffstat:
18 files changed, 181 insertions(+), 99 deletions(-)
diff --git a/Makefile b/Makefile
@@ -4,7 +4,7 @@ CCWARN=-Wall -Wextra -Werror
# -flto (nécessite GCC 4.5) -m32 ou -m64
CFLAGS=-O3 -g3 -I. $(CCWARN)
-OBJECTS = main.o hash.o segment.o vertex.o triangle.o io.o rules/chose.o rules/rectangleroutes.o rules/route.o rules/carrefour.o rules/batiment.o
+OBJECTS = main.o hash.o segment.o vertex.o triangle.o gputriangles.o rules/chose.o rules/rectangleroutes.o rules/route.o rules/carrefour.o rules/batiment.o
EXECUTABLE = city
.PHONY: test
diff --git a/all_includes.hh b/all_includes.hh
@@ -6,18 +6,14 @@
#include <cmath>
#include <vector>
+class Chose;
+
#include "vertex.hh"
#include "segment.hh"
#include "triangle.hh"
#include "directions.hh"
-#include "io.hh"
#include "hash.hh"
-
-class Chose;
-// class Batiment;
-// class Carrefour;
-// class Route;
-// class RectangleRoutes;
+#include "gputriangles.hh"
#include "rules/chose.hh"
#include "rules/batiment.hh"
diff --git a/gputriangles.cpp b/gputriangles.cpp
@@ -0,0 +1,44 @@
+#include "all_includes.hh"
+
+// TODO : Lorsque le GPU est suffisemment puissant pour qu'on puisse envoyer plus de maxSize triangles,
+// Tout supprimer et repartir avec un GPUTriangles vide, avec i, maxSize plus grand.
+GPUTriangles::GPUTriangles(int maxSize) : current(0), aim(std::min(100, maxSize)), maxSize(maxSize) {
+ triangles = static_cast<Triangle*>(operator new[](maxSize * sizeof(Triangle)));
+
+ nToAdd = 0;
+ nTrianglesToAdd = 0;
+ cToAdd = new Chose*[maxSize];
+
+ nToRemove = 0;
+ nTrianglesToRemove = 0;
+ cToRemove = new Chose*[maxSize];
+}
+
+void GPUTriangles::add(Chose* c) {
+ cToAdd[nToAdd++] = c;
+ nTrianglesToAdd += c->triangles.size();
+}
+
+void GPUTriangles::remove(Chose* c) {
+ cToRemove[nToRemove++] = c;
+ nTrianglesToRemove += c->triangles.size();
+}
+
+bool GPUTriangles::canAdd(Chose* c) {
+ return (current + nTrianglesToAdd + ((int)c->triangles.size()) - nTrianglesToRemove <= aim);
+}
+
+bool GPUTriangles::canCommit() {
+ return (current + nTrianglesToAdd - nTrianglesToRemove <= aim);
+}
+
+void GPUTriangles::commit() {
+ // Supprimer les triangles du tableau, en les insérant dans une freelist
+ // Trier la freelist pour insérer les nouveaux triangles au début.
+ // Ajouter les triangles en consommant de la freelist
+ // Compacter la fin du tableau.
+ nToAdd = 0;
+ nTrianglesToAdd = 0;
+ nToRemove = 0;
+ nTrianglesToRemove = 0;
+}
diff --git a/gputriangles.hh b/gputriangles.hh
@@ -0,0 +1,30 @@
+#ifndef _GPUTRIANGLES_HH_
+#define _GPUTRIANGLES_HH_
+
+#include "all_includes.hh"
+
+class GPUTriangles {
+private:
+ int current;
+ int aim;
+ int maxSize;
+ Triangle* triangles;
+
+ int nToAdd;
+ int nTrianglesToAdd;
+ Chose** cToAdd;
+
+ int nTrianglesToRemove;
+ int nToRemove;
+ Chose** cToRemove;
+public:
+ GPUTriangles(int maxSize);
+ void add(Chose*);
+ void remove(Chose*);
+ void commit();
+ // Renvoie true si on peut commit, false s'il y a trop de triangles.
+ bool canCommit();
+ bool canAdd(Chose* c);
+};
+
+#endif
diff --git a/io.cpp b/io.cpp
@@ -1,3 +0,0 @@
-#include "io.hh"
-
-IO::IO(): in(0), out(0) {}
diff --git a/io.hh b/io.hh
@@ -1,13 +0,0 @@
-#ifndef _IO_HH_
-#define _IO_HH_
-
-class IO {
-public:
- int in;
- int out;
-public:
- IO();
- //IO(int in, int out);
-};
-
-#endif
diff --git a/main.cpp b/main.cpp
@@ -23,43 +23,46 @@ int main() {
// mettre à jour la triangulation de notre tile.
// Invariants :
- // * tile.errorVolume ≤ somme(tile.children.errorVolume)
+ // * tile.errorVolume < somme(tile.children.errorVolume) // TODO : pour ordonner deux tiles égales, on prend en compte leur profondeur.
// * tile.nbTriangles < somme(tile.children.nbTriangles)
- // Pour calculer le gain d'une Chose :
- // Lorsqu'on utilise une Chose c, on la split d'abbord (on n'utilisera pas les fils tout de suite, donc pas de récursion),
- // Calculer c.errorVolume dans le constructeur (idem pour chaque fils donc).
- // // Calcul d'une approximation de la surface d'erreur, en considérant que l'objet est plaqué sur un plan perpendiculaire au sol.
- // gainVolumeErreurParTriangle = (c.errorVolume / c.nbTriangles) - sum(x in c.children : x.errorVolume / x.nbTriangles)
- // c.gainSurfaceErreurParTriangle = pow(volumeErreurParTriangle, 2.f/3.f);
- // Pour calculer son gain :
- // int gainParTriangle(distance)
- // // Calcul de la surface de la projection de la surface d'erreur sur l'écran :
- // return c.gainSurfaceErreurParTriangle * (frontFrustumDist * frontFrustumDist) / (dist * dist)
-
// Pour trouver le split() qui rapportera le plus :
- // Set<Chose*> ensemble = { racine }
- // Calculer le gain min et max des fils de toutes les Chose d'ensemble.
- // Chose* best = la Chose avec le plus grand gain max
- // if (best est une feuille) return best;
- // ensemble = { c | c.max ≥ best.min }
+ // findMaxSplit(Vertex camera) {
+ // std::set<Chose*> ensemble(); // TODO : mettre un comparateur qui trie les éléments selon leur gain max, en ordre décroissant.
+ // std::set<Chose*>::iterator it;
+ // ensemble.insert(this);
+ // for (it = ensemble.begin(); it != ensemble.end(); it++) {
+ // // TODO : Calculer le gain min et max des fils de toutes les Chose d'ensemble.
+ // // Pour cela, écrire et utiliser int Chose::gainMinScreenSurfacePerTriangle(Vertex camera)
+ // // et int Chose::gainMax… qui calculeront le gain en utilisant la distance
+ // // du point le plus proche et le plus éloigné de la chose et de ses children.
+ // gainScreenSurfacePerTriangle(camera);
+ // }
+ // Chose* best = ensemble.begin(); // la Chose avec le plus grand gain max
+ // if (best->isLeafNode) return best;
+ //
+ // ensemble = std::set<Chose*>(ensemble.begin(), ensemble.upper_bound(best->gainMin)); // { c | c.max ≥ best.min } // TODO : comparateur
+ // }
// Pour optimiser les Chose :
+ // GPUTriangles* gpu = new GPUTriangles(10);
+ // while(!gpu->canCommit()) {
+ // gpu->remove(findMinMerge());
+ // gpu->commit();
+ // }
// while (42) {
- // Trouver la Chose dont le split() rapportera le plus
- // if (GPUTriangles::current + nbNewTriangles > GPUTriangles::aim) {
- // Trouver les choses avec le merge() qui coûtera le moins,
- // En ayant suffisemment de triangles pour que
- // (GPUTriangles::current + nbNewTriangles - nbDeleteTriangles <= GPUTriangles::aim)
- // Faire autant de split() (qui rapportent le plus) que possible sans dépasser le nombre de triangles autorisés
- // => De cette manière, si on a dû faire un gros merge() qui coûte cher, il sera peut-être compensé par plein de petits split().
- // if (somme des coûts >= gain) {
- // break; // while (42)
- // }
+ // gpu->add(findMaxSplit());
+ // while(!gpu->canCommit()) {
+ // gpu->remove(findMinMerge());
+ // }
+ // while ((s = findMaxSplit()) && gpu->canAdd(s)) {
+ // gpu->add(s);
+ // }
+ // if (gpu->isImprovement()) {
+ // gpu->commit();
+ // } else {
+ // break; // while (42)
// }
- // Supprimer les triangles du tableau, en les insérant dans une freelist
- // Ajouter les triangles en consommant de la freelist
// }
- // Consommer la freeList en créant des triangles "bidon" (les trois sommets en (0,0,0) par ex.)
return 0;
}
diff --git a/rules/batiment.cpp b/rules/batiment.cpp
@@ -1,6 +1,11 @@
#include "all_includes.hh"
-Batiment::Batiment(Vertex ne, Vertex sw) : ne(ne), sw(sw) {
+Batiment::Batiment(Vertex ne, Vertex sw) : Chose(), ne(ne), sw(sw) {
+ triangulation();
+ // TODO : cet errorVolume est celui d'un bâtiment non détaillé
+ // (juste un cube), donc il nous faut un niveau de détail
+ // supplémentaire pour la triangulation actuelle.
+ setErrorVolume((std::abs(ne.x - sw.x)) * (std::abs(ne.y - sw.y)) * (6 + 6/5)); // l*L*h
std::cout << this << std::endl;
}
@@ -48,3 +53,10 @@ std::ostream& operator<<(std::ostream& os, const Batiment* r) {
std::ostream& operator<<(std::ostream& os, const Batiment& r) {
return os << "Batiment " << r.ne << "-" << r.sw;
}
+
+virtual float distanceMin(Vertex v) {
+
+}
+
+virtual float distanceMax(Vertex v) {
+}
diff --git a/rules/carrefour.cpp b/rules/carrefour.cpp
@@ -1,10 +1,12 @@
#include "carrefour.hh"
-Carrefour::Carrefour(Vertex ne, Vertex se, Vertex sw, Vertex nw) {
+Carrefour::Carrefour(Vertex ne, Vertex se, Vertex sw, Vertex nw) : Chose() {
corners[NE]=ne;
corners[SE]=se;
corners[SW]=sw;
corners[NW]=nw;
+ triangulation();
+ setErrorVolume(0);
std::cout << this << std::endl;
}
diff --git a/rules/carrefour.hh b/rules/carrefour.hh
@@ -3,7 +3,7 @@
#include "all_includes.hh"
-class Carrefour : Chose {
+class Carrefour : public Chose {
public:
Vertex corners[4];
public:
diff --git a/rules/chose.cpp b/rules/chose.cpp
@@ -2,12 +2,12 @@
Chose::Chose() : seed(initialSeed) {}
-std::ostream& operator<<(std::ostream& os, const Chose* r) {
- return os << *r;
+std::ostream& operator<<(std::ostream& os, const Chose* c) {
+ return os << *c;
}
-std::ostream& operator<<(std::ostream& os, const Chose& r) {
- (void)r; // unused
+std::ostream& operator<<(std::ostream& os, const Chose& c) {
+ (void)c; // unused
return os << "Chose";
}
@@ -23,38 +23,36 @@ void Chose::addChild(Chose* c) {
children.push_back(c);
}
-void Chose::useTriangles() {
- // TODO
- // Ajouter t dans la liste des triangles à envoyer au GPU.
-
-
- // Maintenir une liste "add" et une liste "delete".
- // Quand on flush les triangles, s'il y a plus de delete que de add :
- // * trier la liste delete.
- // * Choisir l'extrémité (début ou fin) vers laquelle on va rappatrier les éléments de l'autre extrémité.
- // * Écraser les delete avec les add en partant du côté vers lequel on rappatrie.
- // * Copier des éléments de l'extrémité vers les cases libres.
- // * Enregistrer l'indice min et l'indice max.
- // Problème : Pas real-time : on ne peut pas arrêter le processus n'importe quand…
+void Chose::use() {
+ // Lorsqu'on utilise une Chose c, on la split d'abbord (on
+ // n'utilisera pas les fils tout de suite, donc pas de récursion).
+ subdivide();
+ gainErrorSurfacePerTriangle = errorSurfacePerTriangle;
+ std::vector<Chose*>::iterator it;
+ for (it = children.begin(); it != children.end(); ++it) {
+ gainErrorSurfacePerTriangle -= it->errorSurfacePerTriangle);
+ }
+ // TODO : isLeaf = true;
+}
+
+void Chose::unuse() {
+ // TODO : isLeaf = false;
}
void Chose::addTriangle(Triangle* t) {
triangles.push_back(t);
}
-/* TODO : quand on se rend compte qu'on peut utiliser plus de
- triangles (le GPU suit sans problème au FPS voulu), allouer un
- autre tableau plus grand, vers lequel on déplacera les triangles
- petit à petit (pour rester real-time).
-
- Pour l'instant, on alloue simplement un tableau suffisemment grand.
- */
-
-Triangle* Chose::resetGPUTriangles(int n) {
- Chose::GPUTriangles = static_cast<Triangle*>(operator new[](n * sizeof(Triangle)));
- return Chose::GPUTriangles;
+void Chose::setErrorVolume(int errorVolume) {
+ // Calcul d'une approximation de la surface d'erreur à l'écran, en
+ // considérant que l'objet est en fait juste une texture plaquée
+ // sur un plan perpendiculaire au sol et parallèle à l'écran.
+ errorSurfacePerTriangle = pow((float)errorVolume / (float)triangles.size(), 2.f/3.f);
}
-int Chose::nGPUTriangles = 1000;
-// http://stackoverflow.com/questions/4754763/c-object-array-initialization-without-default-constructor
-Triangle* Chose::GPUTriangles = Chose::resetGPUTriangles(Chose::nGPUTriangles);
+// int Chose::gainScreenSurfacePerTriangle(Vertex camera) {
+int Chose::gainScreenSurfacePerTriangle(Vertex camera) {
+ int frontFrustumDist = 1; // TODO : valeur bidon.
+ // Surface de la projection à l'écran de la surface d'erreur :
+ return (int)(gainErrorSurfacePerTriangle * (frontFrustumDist * frontFrustumDist) / (distance * distance));
+}
diff --git a/rules/chose.hh b/rules/chose.hh
@@ -10,9 +10,8 @@ public:
unsigned int seed;
std::vector<Chose*> children;
std::vector<Triangle*> triangles;
- static Triangle* resetGPUTriangles(int n);
- static int nGPUTriangles;
- static Triangle* GPUTriangles;
+ float errorSurfacePerTriangle;
+ float gainErrorSurfacePerTriangle;
public:
Chose();
inline void addEntropy(unsigned int x1) { seed = hash2(seed, x1); }
@@ -27,12 +26,17 @@ public:
void initTriangles(int n);
void addChild(Chose* c);
void addTriangle(Triangle* t);
- void useTriangles(); // triangulation() doit déjà avoir été appelé.
+ void setErrorVolume(int errorVolume);
+ int gainScreenSurfacePerTriangle(Vertex camera);
+ void use(); // triangulation() doit déjà avoir été appelé.
+ void unuse();
virtual void subdivide() = 0;
virtual void triangulation() = 0;
+ virtual float distanceMin(Vertex v);
+ virtual float distanceMax(Vertex v);
};
-std::ostream& operator<<(std::ostream& os, const Chose& r);
-std::ostream& operator<<(std::ostream& os, const Chose* r);
+std::ostream& operator<<(std::ostream& os, const Chose& c);
+std::ostream& operator<<(std::ostream& os, const Chose* c);
#endif
diff --git a/rules/rectangleroutes.cpp b/rules/rectangleroutes.cpp
@@ -1,8 +1,10 @@
#include "all_includes.hh"
-RectangleRoutes::RectangleRoutes(Vertex ne, Vertex sw) : ne(ne), sw(sw) {
+RectangleRoutes::RectangleRoutes(Vertex ne, Vertex sw) : Chose(), ne(ne), sw(sw) {
addEntropy(ne);
addEntropy(sw);
+ triangulation();
+ setErrorVolume((std::abs(ne.x - sw.x)) * (std::abs(ne.y - sw.y)) * 20); // l*L*h, 20=hauteur max d'un bâtiment.
std::cout << this << std::endl;
}
diff --git a/rules/rectangleroutes.hh b/rules/rectangleroutes.hh
@@ -4,7 +4,7 @@
#include "all_includes.hh"
// RectangleRoutes est un quadrilatère de routes avec des angles aux coins égaux à 90°.
-class RectangleRoutes : Chose {
+class RectangleRoutes : public Chose {
public:
Vertex ne;
Vertex sw;
diff --git a/rules/route.cpp b/rules/route.cpp
@@ -2,11 +2,13 @@
#include "../vertex.hh"
#include "../directions.hh"
-Route::Route(Vertex ne, Vertex se, Vertex sw, Vertex nw) {
+Route::Route(Vertex ne, Vertex se, Vertex sw, Vertex nw) : Chose() {
corners[NE]=ne;
corners[SE]=se;
corners[SW]=sw;
corners[NW]=nw;
+ triangulation();
+ setErrorVolume(0);
std::cout << this << std::endl;
}
diff --git a/rules/route.hh b/rules/route.hh
@@ -3,7 +3,7 @@
#include "all_includes.hh"
-class Route : Chose {
+class Route : public Chose {
public:
Vertex corners[4];
public:
diff --git a/triangle.cpp b/triangle.cpp
@@ -1,7 +1,11 @@
#include "all_includes.hh"
Triangle::Triangle(Vertex a, Vertex b, Vertex c): a(a), b(b), c(c) {
- std::cout << this << std::endl;
+ // TODO : calcul de la normale.
+}
+
+std::ostream& operator<<(std::ostream& os, const Triangle* t) {
+ return os << *t;
}
std::ostream& operator<<(std::ostream& os, const Triangle& t) {
diff --git a/triangle.hh b/triangle.hh
@@ -11,6 +11,7 @@ public:
public:
Triangle(Vertex a, Vertex b, Vertex c);
public:
+ friend std::ostream& operator<<(std::ostream& os, const Triangle* t);
friend std::ostream& operator<<(std::ostream& os, const Triangle& t);
};
