commit 60a49d96a1233b27564f8d5a9b83ba0dcd9e5be9
parent 86c862658666b2ef73fdac3a6b2d791293851f65
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Mon, 28 Nov 2011 07:41:41 +0100
Revert "Zut"
This reverts commit 86c862658666b2ef73fdac3a6b2d791293851f65.
Diffstat:
18 files changed, 99 insertions(+), 181 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 gputriangles.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 io.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,14 +6,18 @@
#include <cmath>
#include <vector>
-class Chose;
-
#include "vertex.hh"
#include "segment.hh"
#include "triangle.hh"
#include "directions.hh"
+#include "io.hh"
#include "hash.hh"
-#include "gputriangles.hh"
+
+class Chose;
+// class Batiment;
+// class Carrefour;
+// class Route;
+// class RectangleRoutes;
#include "rules/chose.hh"
#include "rules/batiment.hh"
diff --git a/gputriangles.cpp b/gputriangles.cpp
@@ -1,44 +0,0 @@
-#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
@@ -1,30 +0,0 @@
-#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
@@ -0,0 +1,3 @@
+#include "io.hh"
+
+IO::IO(): in(0), out(0) {}
diff --git a/io.hh b/io.hh
@@ -0,0 +1,13 @@
+#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,46 +23,43 @@ int main() {
// mettre à jour la triangulation de notre tile.
// Invariants :
- // * tile.errorVolume < somme(tile.children.errorVolume) // TODO : pour ordonner deux tiles égales, on prend en compte leur profondeur.
+ // * tile.errorVolume ≤ somme(tile.children.errorVolume)
// * 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 :
- // 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
- // }
+ // 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 }
// Pour optimiser les Chose :
- // GPUTriangles* gpu = new GPUTriangles(10);
- // while(!gpu->canCommit()) {
- // gpu->remove(findMinMerge());
- // gpu->commit();
- // }
// 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)
+ // 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)
+ // }
// }
+ // 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,11 +1,6 @@
#include "all_includes.hh"
-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
+Batiment::Batiment(Vertex ne, Vertex sw) : ne(ne), sw(sw) {
std::cout << this << std::endl;
}
@@ -53,10 +48,3 @@ 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,12 +1,10 @@
#include "carrefour.hh"
-Carrefour::Carrefour(Vertex ne, Vertex se, Vertex sw, Vertex nw) : Chose() {
+Carrefour::Carrefour(Vertex ne, Vertex se, Vertex sw, Vertex nw) {
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 : public Chose {
+class Carrefour : 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* c) {
- return os << *c;
+std::ostream& operator<<(std::ostream& os, const Chose* r) {
+ return os << *r;
}
-std::ostream& operator<<(std::ostream& os, const Chose& c) {
- (void)c; // unused
+std::ostream& operator<<(std::ostream& os, const Chose& r) {
+ (void)r; // unused
return os << "Chose";
}
@@ -23,36 +23,38 @@ void Chose::addChild(Chose* c) {
children.push_back(c);
}
-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::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::addTriangle(Triangle* t) {
triangles.push_back(t);
}
-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);
-}
+/* 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).
-// 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));
+ 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;
}
+
+int Chose::nGPUTriangles = 1000;
+// http://stackoverflow.com/questions/4754763/c-object-array-initialization-without-default-constructor
+Triangle* Chose::GPUTriangles = Chose::resetGPUTriangles(Chose::nGPUTriangles);
diff --git a/rules/chose.hh b/rules/chose.hh
@@ -10,8 +10,9 @@ public:
unsigned int seed;
std::vector<Chose*> children;
std::vector<Triangle*> triangles;
- float errorSurfacePerTriangle;
- float gainErrorSurfacePerTriangle;
+ static Triangle* resetGPUTriangles(int n);
+ static int nGPUTriangles;
+ static Triangle* GPUTriangles;
public:
Chose();
inline void addEntropy(unsigned int x1) { seed = hash2(seed, x1); }
@@ -26,17 +27,12 @@ public:
void initTriangles(int n);
void addChild(Chose* c);
void addTriangle(Triangle* t);
- void setErrorVolume(int errorVolume);
- int gainScreenSurfacePerTriangle(Vertex camera);
- void use(); // triangulation() doit déjà avoir été appelé.
- void unuse();
+ void useTriangles(); // triangulation() doit déjà avoir été appelé.
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& c);
-std::ostream& operator<<(std::ostream& os, const Chose* c);
+std::ostream& operator<<(std::ostream& os, const Chose& r);
+std::ostream& operator<<(std::ostream& os, const Chose* r);
#endif
diff --git a/rules/rectangleroutes.cpp b/rules/rectangleroutes.cpp
@@ -1,10 +1,8 @@
#include "all_includes.hh"
-RectangleRoutes::RectangleRoutes(Vertex ne, Vertex sw) : Chose(), ne(ne), sw(sw) {
+RectangleRoutes::RectangleRoutes(Vertex ne, Vertex sw) : 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 : public Chose {
+class RectangleRoutes : Chose {
public:
Vertex ne;
Vertex sw;
diff --git a/rules/route.cpp b/rules/route.cpp
@@ -2,13 +2,11 @@
#include "../vertex.hh"
#include "../directions.hh"
-Route::Route(Vertex ne, Vertex se, Vertex sw, Vertex nw) : Chose() {
+Route::Route(Vertex ne, Vertex se, Vertex sw, Vertex nw) {
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 : public Chose {
+class Route : Chose {
public:
Vertex corners[4];
public:
diff --git a/triangle.cpp b/triangle.cpp
@@ -1,11 +1,7 @@
#include "all_includes.hh"
Triangle::Triangle(Vertex a, Vertex b, Vertex c): a(a), b(b), c(c) {
- // TODO : calcul de la normale.
-}
-
-std::ostream& operator<<(std::ostream& os, const Triangle* t) {
- return os << *t;
+ std::cout << this << std::endl;
}
std::ostream& operator<<(std::ostream& os, const Triangle& t) {
diff --git a/triangle.hh b/triangle.hh
@@ -11,7 +11,6 @@ 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);
};
