commit d97593d9995fc6dcdcd44d68bb7375896e8ec62e
parent 73da98b6a31b0d964e9c5fc68d6a0e9069aaa859
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Sun, 27 Nov 2011 00:26:05 +0100
Notes sur l'algo permettant de décider quels objets seront split() ou merge(), et la récupération de tous les triangles dans un tableau à envoyer au GPU.
Diffstat:
3 files changed, 83 insertions(+), 2 deletions(-)
diff --git a/main.cpp b/main.cpp
@@ -14,5 +14,52 @@ int main() {
RectangleRoutes r(ne, sw);
r.subdivide();
// tile.subdivide tant qu'on n'a pas le niveau de détail désiré.
+
+ // TODO : diviser l'errorVolume par nbTriangles, pour avoir le gain/perte par triangle.
+ // Cela devrait donner des choix plus justes pour les split/merge.
+
+ // TODO : comment une tile peut-elle s'adapter à ses voisins (lors de la triangulation) ?
+ // Solution bof : maintenir une liste des voisins sur chaque segment/face, et lorsqu'un nouveau voisin est créé,
+ // mettre à jour la triangulation de notre tile.
+
+ // Invariants :
+ // * 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 :
+ // 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 :
+ // 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/chose.cpp b/rules/chose.cpp
@@ -21,10 +21,40 @@ void Chose::initTriangles(int n) {
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::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);
- // TODO : Ajouter t dans la liste des triangles à envoyer au GPU.
}
+
+/* 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;
+}
+
+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,6 +10,9 @@ public:
unsigned int seed;
std::vector<Chose*> children;
std::vector<Triangle*> triangles;
+ static Triangle* resetGPUTriangles(int n);
+ static int nGPUTriangles;
+ static Triangle* GPUTriangles;
public:
Chose();
inline void addEntropy(unsigned int x1) { seed = hash2(seed, x1); }
@@ -24,6 +27,7 @@ public:
void initTriangles(int n);
void addChild(Chose* c);
void addTriangle(Triangle* t);
+ void useTriangles(); // triangulation() doit déjà avoir été appelé.
virtual void subdivide() = 0;
virtual void triangulation() = 0;
};
