commit 9036e2dea0b40eac2c4d07152ca076a692dd547f
parent 61ea30e35dbd1a7f63c9a92c142f99ef14df0c07
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Sat, 3 Dec 2011 15:19:44 +0100
Nettoyage des anciens fichiers .c qui ne sont plus utilisés.
Diffstat:
| D | display.c | | | 271 | ------------------------------------------------------------------------------- |
| D | display.h | | | 30 | ------------------------------ |
| D | roads.c | | | 562 | ------------------------------------------------------------------------------- |
| D | roads.h | | | 96 | ------------------------------------------------------------------------------- |
| D | roads.md | | | 225 | ------------------------------------------------------------------------------- |
| D | roam.c | | | 318 | ------------------------------------------------------------------------------- |
| D | roam.h | | | 32 | -------------------------------- |
| D | simple-terrain.c | | | 122 | ------------------------------------------------------------------------------- |
| D | square.c | | | 305 | ------------------------------------------------------------------------------- |
| D | square.h | | | 20 | -------------------- |
| D | terrain.md | | | 49 | ------------------------------------------------- |
11 files changed, 0 insertions(+), 2030 deletions(-)
diff --git a/display.c b/display.c
@@ -1,271 +0,0 @@
-#include "display.h"
-
-int initWindow() {
- SDL_Init(SDL_INIT_VIDEO);
- SDL_WM_SetCaption("Sortie terrain OpenGL",NULL);
- SDL_SetVideoMode(windowWidth, windowHeight, 32, SDL_OPENGL);
- glMatrixMode( GL_PROJECTION );
- glLoadIdentity();
- gluPerspective(70,(double)windowWidth/windowHeight,1,10000);
- glEnable(GL_DEPTH_TEST);
- glewInit();
-
- float MatSpec[4] = {0.0f, 0.0f, 0.0f, 1.0f};
- float MatDif[4] = {0.0f, 0.5f, 0.0f, 1.0f};
- float MatAmb[4] = {0.0f, 0.0f, 0.0f, 1.0f};
-
- float Light1Pos[4] = {0.0f, 1.0f, 0.0f, 0.0f};
- float Light1Dif[4] = {1.0f, 1.0f, 1.0f, 1.0f};
- float Light1Spec[4] = {0.0f, 0.0f, 0.0f, 1.0f};
- float Light1Amb[4] = {0.4f, 0.4f, 0.4f, 1.0f};
- float shininess = 128.0f;
-
- glMaterialfv(GL_FRONT_AND_BACK,GL_SPECULAR,MatSpec);
- glMaterialfv(GL_FRONT_AND_BACK,GL_DIFFUSE,MatDif);
- glMaterialfv(GL_FRONT_AND_BACK,GL_AMBIENT,MatAmb);
- glMaterialfv(GL_FRONT,GL_SHININESS,&shininess);
-
- glLightfv(GL_LIGHT0, GL_DIFFUSE, Light1Dif);
- glLightfv(GL_LIGHT0, GL_SPECULAR, Light1Spec);
- glLightfv(GL_LIGHT0, GL_AMBIENT, Light1Amb);
- glLightfv(GL_LIGHT0, GL_POSITION, Light1Pos);
-
- glEnable(GL_LIGHTING); // Active l'éclairage
- glEnable(GL_LIGHT0); // Active la lumière 0;
-
- return 0;
-}
-
-
-int mainLoop() {
- short continuer = 1;
- SDL_Event event;
-
- while (continuer) {
- SDL_WaitEvent(&event);
- switch(event.type) {
- case SDL_QUIT:
- continuer = 0;
- break;
- case SDL_KEYDOWN:
- switch(event.key.keysym.sym) {
- case SDLK_DOWN:
- ySight -= moveDist;
- break;
- case SDLK_UP:
- ySight += moveDist;
- break;
- case SDLK_LEFT:
- xSight -= moveDist;
- break;
- case SDLK_RIGHT:
- xSight += moveDist;
- break;
-
- default:
- break;
- }
- break;
-
- case SDL_MOUSEMOTION:
- xAngle = ((event.motion.x-windowWidth/2)*340/(windowWidth));
- yAngle = (event.motion.y-windowHeight/2)*340/(windowHeight);
- break;
-
- default:
- break;
- }
-
- renderScene();
- }
-
- SDL_Quit();
-
- return 0;
-}
-
-
-void drawAxes() {
- glDisable(GL_LIGHTING);
- glDisable(GL_TEXTURE_2D);
- glBegin(GL_LINES);
- glColor3ub(255,0,0);
- glVertex3f(0.0f, 0.0f, 0.0f); // origin of the line
- glVertex3f(2500.0f, 0.0f, 0.0f); // ending point of the line
- glEnd( );
-
- glBegin(GL_LINES);
- glColor3ub(0,255,0);
- glVertex3f(0.0f, 0.0f, 0.0f); // origin of the line
- glVertex3f(0.0f, 2500.0f, 0.0f); // ending point of the line
- glEnd( );
-
- glBegin(GL_LINES);
- glColor3ub(0,0,255);
- glVertex3f(0.0f, 0.0f, 0.0f); // origin of the line
- glVertex3f(0.0f, 0.0f, -2500.0f); // ending point of the line
- glEnd( );
- glEnable(GL_LIGHTING);
-}
-
-
-void renderScene() {
- glMatrixMode(GL_MODELVIEW);
- glLoadIdentity();
- //gluLookAt(1024,512,1356,1024,512,0,0,1,0);
-
- //glClearColor(1,1,1,1); // pour un fond blanc
- glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT) ;
-
- //gluLookAt(0,0,cameraDist, 0, 0, 0,0,1,0);
- glTranslated(-xSight,-ySight,-(zSight+cameraDist));
- glRotatef(-yAngle,1,0,0);
- glRotatef(-xAngle,0,0,1);
-
-
- drawAxes();
- displayQTTree(qtn);
-
- glFlush();
- SDL_GL_SwapBuffers();
-}
-
-void displayQTTree(QTNode *qn) {
- QT_enumerate(qn);
- //qn = qn;
-}
-
-/*
-int nbTriangles(Triangle *t) {
- int sum = 0;
-
- if(t->tLeftChild == NULL) {
- return 1;
- }
- else {
- sum += nbTriangles(t->tLeftChild);
- sum += nbTriangles(t->tRightChild);
- }
-
- return sum;
-}*/
-
-/*
-void insertValues(Triangle *t,int *vertices) {
- if(t->tLeftChild == NULL) {
- vertices[9*nbVertex] = t->vLeft->x;
- vertices[9*nbVertex+1] = t->vLeft->y;
- vertices[9*nbVertex+2] = t->vLeft->z;
- vertices[9*nbVertex+3] = t->vApex->x;
- vertices[9*nbVertex+4] = t->vApex->y;
- vertices[9*nbVertex+5] = t->vApex->z;
- vertices[9*nbVertex+6] = t->vRight->x;
- vertices[9*nbVertex+7] = t->vRight->y;
- vertices[9*nbVertex+8] = t->vRight->z;
- nbVertex++;
- }
- else {
- insertValues(t->tLeftChild,vertices);
- insertValues(t->tRightChild,vertices);
- }
-}*/
-
-/*
-void displayTree2() {
- glVertexAttribPointer(0, 3, GL_INT, GL_FALSE, 0, vertices);
- glEnableVertexAttribArray(0);
- glColor3ub(255,255,255);
- glDrawArrays(GL_LINE_LOOP,0, nbVertex*3);
-}*/
-
-int max3(int x,int y,int z) {
- if(x < y && x < z) return x;
- if(y < x && y < z) return y;
- if(z < x && z < y) return z;
- return 0;
-}
-/*
-void setNormals(Triangle *t) {
- if(t->tLeftChild == NULL) {
- int ax = t->vLeft->x - t->vApex->x;
- int ay = t->vLeft->y - t->vApex->y;
- int az = t->vLeft->z - t->vApex->z;
- int bx = t->vApex->x - t->vRight->x;
- int by = t->vApex->y - t->vRight->y;
- int bz = t->vApex->z - t->vRight->z;
-
- float x = (float)((ay * bz) - (az * by));
- float y = (float)((az * bx) - (ax * bz));
- float z = -(float)((ax * by) - (ay * bx));
- float length = sqrt(x*x + y*y + z*z);
-
- length = length;
- x = x/length;
- y = y/length;
- z = z/length;
-
- t->vLeft->xNormal = x;
- t->vLeft->yNormal = y;
- t->vLeft->zNormal = z;
- t->vRight->xNormal = x;
- t->vRight->yNormal = y;
- t->vRight->zNormal = z;
- t->vApex->xNormal = x;
- t->vApex->yNormal = y;
- t->vApex->zNormal = z;
- }
- else {
- setNormals(t->tLeftChild);
- setNormals(t->tRightChild);
- }
-}
-
-void displayTree(Triangle *t) {
- if(t->tLeftChild == NULL) {
- glNormal3f(t->vLeft->xNormal,t->vLeft->yNormal,t->vLeft->zNormal);
- //glNormal3f(0.075722,0.077664,0.99812);
- glBegin(GL_TRIANGLES);
- glVertex3d(t->vLeft->x,t->vLeft->y,t->vLeft->z);
- glVertex3d(t->vApex->x,t->vApex->y,t->vApex->z);
- glVertex3d(t->vRight->x,t->vRight->y,t->vRight->z);
- glEnd();
- }
- else {
- displayTree(t->tLeftChild);
- displayTree(t->tRightChild);
- }
-}*/
-
-
-int main() {
- initWindow();
- qtn = QT_example();
- //nbVertex = nbTriangles(t);
- //printf("nombre de triangles : %d\n",nbVertex);
-
- // Calcul des normales des traingles.
- //setNormals(t);
-
- // Réorganisation des sommets pour l'affichage optimisé.
- //vertices = (int*) malloc(sizeof(int) * nbTriangles(t)*9+1);
- //insertValues(t,vertices);
-
- mainLoop();
-
- // Pour afficher le terrain :
- /* int x; */
- /* int y; */
- /* #define SIZE 1024 */
- /* printf("P5 %d %d 255\n", SIZE, SIZE); */
- /* for (y = 0; y < SIZE; y++) { */
- /* for (x = 0; x < SIZE; x++) { */
- /* //int bit = y / (SIZE/32); */
- /* //int h = hash2(x, 300+y); */
- /* //if (y % (SIZE/32) == 0) h = 0; */
- /* //printf("%c", ((h >> (31-bit)) & 1) * 255); */
- /* //printf("%c", interpolation(256+x, 256+y, 256, 256, 512, 512, 0, 255, 255, 255)); */
- /* printf("%c", get_z(x,y)); */
- /* } */
- /* } */
- return 0;
-}
diff --git a/display.h b/display.h
@@ -1,30 +0,0 @@
-#include <SDL/SDL.h>
-#include <GL/glew.h>
-#include <GL/glu.h>
-#include "square.h"
-#include <math.h>
-
-int initWindow();
-int mainLoop();
-void renderScene();
-void displayQTTree(QTNode *qn);
-//void setNormals(Triangle *t);
-//void displayTree(Triangle *t);
-//void displayTree2();
-void Draw_Axes ();
-
-QTNode *qtn;
-int *vertices;
-int windowWidth = 1024;
-int windowHeight = 768;
-int nbVertex = 0;
-
-int cameraDist = 3000;
-
-int xSight = 0;
-int ySight = 0;
-int zSight = 0;
-
-float xAngle = 0;
-float yAngle = 0;
-int moveDist = 128;
diff --git a/roads.c b/roads.c
@@ -1,562 +0,0 @@
-#include "roads.h"
-
-void svg_start(int w, int h) {
- printf("<?xml version=\"1.0\" encoding=\"utf-8\"?>");
- printf("<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"%d\" height=\"%d\">", w, h);
-}
-
-void svg_end() {
- printf("</svg>");
-}
-
-void svg_line(Vertex* a, Vertex* b, short color) {
- if(color == 0)
- printf("<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" stroke=\"grey\" />", a->x, a->y, b->x, b->y);
- else if(color == 1)
- printf("<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" stroke=\"#A0A000\" />", a->x, a->y, b->x, b->y);
- else if(color == 2)
- printf("<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" stroke=\"blue\" />", a->x, a->y, b->x, b->y);
- else
- printf("<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" stroke=\"black\" />", a->x, a->y, b->x, b->y);
-}
-
-void svg_circle(int x, int y, int r) {
- printf("<circle cx=\"%d\" cy=\"%d\" r=\"%d\" stroke=\"black\" stroke-width=\"2\" fill=\"red\"/>",x,y,r);
-}
-
-void roads(Polygon* quartier) {
- quartier = quartier;
- Vertex center = { .x=400, .y=300 };
- svg_line(¢er, &(quartier[0]),6);
-}
-
-
-
-
-/* Fonctions de Yoann suffixée par "Y" */
-
-/* Initialisation de la liste de routes.
- */
-void initRoadslIst(int nb){
- roadsList = (roadPointY**) malloc(sizeof(roadPointY*)*nb);
-}
-
-
-/* La route est constituée d'une série de points, chaque point contient un nœd de route qui peut-être propre à cette route comme
- * appartenir à plusieurs routes. Le nœd contient un Vertex qui permet de le positionner sur la carte. Il contient également
- * le nombre et les portions de routes auxquelles il appartient.
- */
-
-// Transforme des coordonnées du plan en coordonées du tableau sur x.
-int toX(Vertex *v) {
- int x = v->x*(nbXSubDivision)/quarterWidth;
- if(x >= nbXSubDivision) return 0;
- return x;
-}
-
-
-// Transforme des coordonnées du plan en coordonées du tableau sur y.
-int toY(Vertex *v) {
- int y = v->y*(nbYSubDivision)/quarterHeight;
- if(y >= nbYSubDivision) return 0;
- return y;
-}
-
-
-/* Convertion de coordonnées polaires en coordonnées cartésiennes.
- * @param Vertex* origin : Origine du vecteur.
- * @param short angle : Angle.
- * @param short length : Taille du vecteur.
- * @return struct cartesianCoord* : Les coordonnées cartésiennes du point d'arrivée.
- */
-cartesianCoord* ptc(Vertex *origin, short angle, short length) {
- cartesianCoord *cc = (cartesianCoord*) malloc(sizeof(cartesianCoord));
- cc->x = origin->x + cos(M_PI*angle/180)*length;
- cc->y = origin->y + sin(M_PI*angle/180)*length;
-
- return cc;
-}
-
-
-/* Convertion de coordonnées cartésiennes en coordonnées polaires.
- * @param Vertex* origin : Origine du vecteur.
- * @param Vertex* end : Fin du vecteur.
- * @return struct polarCoord* : Les coordonnées polaires du point d'arrivée.
- */
-polarCoord* ctp(Vertex *origin, Vertex *end) {
- polarCoord *pc = (polarCoord*) malloc(sizeof(polarCoord));
- pc->length = distBetween(origin,end);
- pc->angle = acos((float)(end->x-origin->x)/(float)pc->length)*180/M_PI;
- if(end->y < origin->y)
- pc->angle = 360-pc->angle;
- return pc;
-}
-
-
-/* Initialise la grille de nœuds.
- * @param int width : Largeur du quartier à remplir.
- * @param int height : Hauteur du quartier à remplir.
- * @param int maxSegmentSize : Taille maximale d'un segment de route.
- */
-void grid_initvGrid(int width, int height, int segmentSize) {
- int xSize, ySize;
- xSize = (int)(width/segmentSize);
- ySize = (int)(height/segmentSize);
-
- vGrid = (Vertex****) malloc(sizeof(Vertex***)*xSize);
- int i,j,k;
-
- maxSegmentSize = segmentSize;
- nbXSubDivision = xSize;
- nbYSubDivision = ySize;
- quarterWidth = width;
- quarterHeight = height;
-
- for(i=0;i<xSize;i++) {
- vGrid[i] = (Vertex***) malloc(sizeof(Vertex**)*ySize);
- for(j=0;j<ySize;j++) {
- vGrid[i][j] = (Vertex**) malloc(sizeof(Vertex*)*maxNodesInGrid);
- for(k=0;k<maxNodesInGrid;k++)
- vGrid[i][j][k] = NULL;
- }
- }
-}
-
-
-/* Détermine si il existe une intersection entre deux segments de droite. Dans le cas
- * ou une intersection existe les coordonnées du point d'intersection sont retournées.
- * Dans le cas contraire la fonction retourne NULL.
- * @param Vertex *va : Point de départ du premier segment.
- * @param Vertex *vb : Point d'arrivé du premier segment.
- * @param Vertex *ua : Point de départ du second segment.
- * @param Vertex *vb : Point d'arrivé du second segment.
- * @return Vertex* : Coordonnées du point d'intersection si il existe, sinon NULL.
- */
-Vertex* intersectionBetween(Segment *sega, Segment *segb) {
- if(sega == NULL || segb == NULL)
- return NULL;
-
- sega = sega;
- segb = segb;
- Vertex *inter = (Vertex*) malloc(sizeof(Vertex));
- float m, k; // Coordonnées de l'intersection des vecteurs sur les droites.
- int Ix, Iy, Jx, Jy; // Vecteur I et J corespondant au segment v et u;
- Vertex *va, *vb, *ua, *ub;
-
- va = sega->u;
- vb = sega->v;
- ua = segb->u;
- ub = segb->v;
-
- Ix = vb->x - va->x;
- Iy = vb->y - va->y;
- Jx = ub->x - ua->x;
- Jy = ub->y - ua->y;
-
- m = (float)(-(-Ix*va->y+Ix*ua->y+Iy*va->x-Iy*ua->x))/(float)(Ix*Jy-Iy*Jx);
- k = (float)(-(va->x*Jy-ua->x*Jy-Jx*va->y+Jx*ua->y))/(float)(Ix*Jy-Iy*Jx);
-
- if(m < 1 && m > 0 && k < 1 && k > 0) {
- inter->x = va->x + k * Ix;
- inter->y = va->y + k * Iy;
- }
- else
- return NULL;
-
- return inter;
-}
-
-
-void grid_drawGrid() {
- int i, j;
-
- for(i=0;i<nbXSubDivision-1;i++)
- for(j=0;j<nbYSubDivision-1;j++) {
- Vertex v = { .x = i*maxSegmentSize, .y = j*maxSegmentSize };
- Vertex u = { .x = (i+1)*maxSegmentSize, .y = j*maxSegmentSize };
- svg_line(&v,&u,0);
- u.x = i*maxSegmentSize;
- u.y = (j+1)*maxSegmentSize;
- svg_line(&v,&u,0);
- }
-}
-
-
-short grid_insertVertex(Vertex *vtx) {
- if(vtx == NULL)
- return 0;
-
- int i;
- for(i=0;i<maxNodesInGrid;i++) {
- if(vGrid[toX(vtx)][toY(vtx)][i] == NULL) {
- vGrid[toX(vtx)][toY(vtx)][i] = vtx;
- return 1;
- }
- }
-
- return 0;
-}
-
-
-/* Retourne le nœd le plus proche dans un certain voisinage. Si aucun nœd n'est trouvé alors
- * la fonction renvoie NULL.
- * @param Vertex *v : Le nœd pour lequel on souhaite trouver un nœd proche.
- * @return roadNodeY* : le nœd de route le plus proche.
- */
-Vertex* grid_getNearestVertex(Vertex *v) {
- Vertex **vtx;
- Vertex *nearestVertex = NULL;
- int i,j;
- int x = toX(v);
- int y = toY(v);
- int distance = maxSegmentSize*2;
- Vertex *tmp = NULL;
- int count = 0;
-
- for(i=x-1; i<x+2; i++) {
- for(j=y-1; j<y+2; j++,count++) {
- if(i >= 0 && i < nbXSubDivision && y >= 0 && y < nbYSubDivision) {
-
- vtx = grid_getNearVertices2(i,j);
-
- int ind;
-
- for(tmp = vtx[0], ind = 0; tmp != NULL && ind < maxNodesInGrid; tmp = vtx[ind++]) {
- int dist = distBetween(v,tmp);
- if(dist < distance) {
- distance = dist;
- nearestVertex = tmp;
- }
-
- tmp = vtx[i];
- }
- }
- }
- }
-
- return nearestVertex;
-}
-
-
-Vertex* insertSegment(Segment *seg, int lag) {
- int segLength = distBetween(seg->u, seg->v);
- float coef = ((float)segLength-lag)/(float)segLength;
- Vertex *nearestVertex = NULL;
- Vertex tmpEnd, *va, *vb;
- int intersec = 0; // Booléen si intersection = 1 sinon = 0;
-
- va = seg->u;
- vb = seg->v;
-
- seg = seg;
- lag = lag;
- // ------- TODO à compléter et à vérifier.
- /*Segment **segs = grid_getNearSegments(rpb->rn->v->x,rpb->rn->v->y);
- Segment *seg = segs[0];
- int s = 0;
-
- while(seg != NULL) {
- Vertex *intersection = intersectionBetween(rpb->rn->v,rne->v,seg->u,seg->v);
-
- if(intersection != NULL) {
- // Créer un nœd, l'insérer au segment qui à causé l'intersection.
- // Ce nœd deviens le point d'arriver du segment à placer : rne;
- intersec = 1;
- }
- seg = segs[s++];
- }*/
- // -------
- if(intersec == 0) {
- tmpEnd.x = va->x + coef*(vb->x - va->x);
- tmpEnd.y = va->y + coef*(vb->y - va->y);
-
- nearestVertex = grid_getNearestVertex(&tmpEnd);
-
- if(nearestVertex != NULL && distBetween(nearestVertex,vb) < lag)
- vb = nearestVertex;
- }
-
- grid_insertVertex(va);
- grid_insertVertex(vb);
- return NULL;
-}
-
-
-int distBetween(Vertex *v, Vertex *u) {
- return sqrt((v->x-u->x)*(v->x-u->x)+(v->y-u->y)*(v->y-u->y));
-}
-
-Vertex** grid_getNearVertices(Vertex *v) {
- return vGrid[toX(v)][toY(v)];
-}
-
-
-Vertex** grid_getNearVertices2(int x, int y) {
- return vGrid[x][y];
-}
-
-
-/* Récupère tout les segement potentiellement sécant avec un segment ayant pour arrivée x et y.
- */
-void grid_getNearSegments(Map *m, int x, int y) {
- Vertex **vtx, *tmpVtx;
- Segment *tmpSegs;
- int i, j, s, k;
-
- s = 0;
- Vertex vv = {.x = x, .y = y};
- x = toX(&vv);
- y = toY(&vv);
-
- m->segments2_firstFree = 0;
-
- for(i=x-1;i<x+2;i++) {
- for(j=y-1;j<y+2;j++) {
- if(x >= 0 && x < nbXSubDivision && y >= 0 && y < nbYSubDivision) {
- vtx = grid_getNearVertices2(i,j);
- k = 0;
- tmpVtx = vtx[0];
- //fprintf(stderr,"Bonjour\n");
- // TODO Tester si le segment existe déjà dans la liste pour ne pas l'insérer en double.
-
- while(tmpVtx != NULL) {
- if(m->segments_firstFree >= segments_array_size)
- return;
-
- for(tmpSegs = tmpVtx->s; tmpSegs != NULL; tmpSegs = tmpSegs->nextU) {
- m->segments2[m->segments2_firstFree++] = tmpSegs;
- }
-
- for(tmpSegs = tmpVtx->s; tmpSegs != NULL; tmpSegs = tmpSegs->nextV) {
- m->segments2[m->segments2_firstFree++] = tmpSegs;
- }
-
- tmpVtx = vtx[k++];
- }
- }
- }
- }
-}
-
-
-
-
-
-
-// Algo « champs de force »
-typedef struct FVector { float x; float y; } FVector;
-inline FVector fVector_substract(FVector a, FVector b) { return (FVector){ .x = a.x - b.x, .y = a.y - b.y }; }
-inline FVector fVector_add(FVector a, FVector b) { return (FVector){ .x = a.x + b.x, .y = a.y + b.y }; }
-inline FVector fVector_rotate90(FVector v) { return (FVector){ .x = -v.y, .y = v.x }; }
-
-typedef struct FSegment { FVector from; FVector to; } FSegment;
-inline void fsegment_display(FSegment s) {
- printf("<line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\" stroke=\"black\" />", s.from.x, s.from.y, s.to.x, s.to.y);
-}
-
-
-// TODO : dimensionner correctement le tableau.
-#define FSegmentArray_SIZE 1024
-typedef struct FSegmentArray { FSegment seg[FSegmentArray_SIZE]; int firstUnseen; int firstFree; /* + CollisionGrid collision; */ } FSegmentArray;
-inline void fSegmentArray_push(FSegmentArray* a, FSegment s) {
- // TODO : check for collisions.
- if (a->firstFree >= FSegmentArray_SIZE) return;
- a->seg[a->firstFree++] = s;
-}
-inline FSegment fSegmentArray_pop(FSegmentArray* a) {
- return a->seg[a->firstUnseen++];
-}
-
-
-/* Choisir des champs de force. `f(x,y,vecteur)` renvoie tous les
- * vecteurs de routes qu'on peut faire partir du point `(x,y)`,
- * lorsqu'on y arrive par la direction `vecteur`. */
-// champ de force "ligne droite".
-// TODO : devrait prendre un segment en paramètre.
-void f(FSegment s, FSegmentArray* a) {
- FVector delta = fVector_substract(s.to, s.from);
- FSegment newS = {
- .from = s.to,
- .to = fVector_add(s.to, delta),
- };
- // TODO : s'accrocher aux points proches, et ne pas ajouter le segment à la queue si on s'accroche à un point existant.
- // TODO : ne pas utiliser des segments dans la file d'attente, mais juste des vertex, dont on peut énumérer les segments.
- fSegmentArray_push(a, newS);
- FSegment newS2 = {
- .from = s.to,
- .to = fVector_add(s.to, fVector_rotate90(delta)),
- };
- newS2.to.y += 3;
- fSegmentArray_push(a, newS2);
-}
-
-/* ***************************** */
-// Nouvelle version :
-
-
-Segment* segment_to(Map* m, Vertex* u, int x, int y) {
- if(m->vertices_firstFree >= vertices_array_size)
- return NULL;
-
- Vertex* v;
- Vertex tmp = { .x = x, .y = y};
- Vertex *nearest = grid_getNearestVertex(&tmp);
-
- if(nearest != NULL && distBetween(&tmp,nearest) < 5) {
- v = nearest;
- v->x = x;
- v->y = y;
- v->s = NULL;
- }
- else {
- v = &(m->vertices[m->vertices_firstFree++]);
- v->x = x;
- v->y = y;
- v->s = NULL;
- grid_insertVertex(v);
- }
-
- if(v == NULL || m->segments_firstFree >= segments_array_size)
- return NULL;
-
- // Code pour le calcul d'intersections.
-
- int distance = 1000;
- int i;
- Segment tmpSeg = { .u = u, .v = v};
- Segment *segmentCut = NULL;
- Vertex *coordInter = NULL;
-
- grid_getNearSegments(m,u->x,u->y);
-
- for(i = 0; i < m->segments2_firstFree; i++) {
- Vertex *intersection = intersectionBetween(m->segments2[i],&tmpSeg);
- if(intersection != NULL && distBetween(u,intersection) < distance) {
- distance = distBetween(u, intersection);
- segmentCut = m->segments2[i];
- coordInter = intersection;
- }
- }
-
- if(segmentCut != NULL) {
- Vertex *vInter = &(m->vertices[m->vertices_firstFree++]);
- Segment *segmentPartA = segmentCut;
- Segment *segmentPartB = &(m->segments[m->segments_firstFree++]);
-
- vInter->x = coordInter->x;
- vInter->y = coordInter->y;
-
- segmentPartA->v = vInter;
-
- segmentPartB->u = vInter;
- segmentPartB->nextU = NULL;
- segmentPartB->v = segmentPartA->v;
- segmentPartB->nextV = segmentPartA->nextV;
-
- segmentPartA->nextV = NULL;
-
- v = vInter;
- m->vertices_firstFree--;
- }
-
- Segment* s = &(m->segments[m->segments_firstFree++]);
- s->u = u;
- s->v = v;
- /*s->nextU = u->s;
- s->nextV = v->s;
- u->s = s;*/
- v->s = s;
-
- return s;
-}
-
-void fv(Map* m, Vertex *from) {
- // Tracer une ou des routes, en utilisant segment_to.
- if(from->s == NULL)
- return;
-
- Vertex *existing = from->s->u == from ? from->s->v : from->s->u;
- // Segment dans la continuation
- //Vertex new1 = vertex_add(from, vertex_substract(from, existing)); // from + (from - existing)
- Vertex new1 = { .x = from->x + (from->x - existing->x),
- .y = from->y + (from->y - existing->y),
- .s = NULL };
-
- // Segment perpendiculaire
- polarCoord *polar = ctp(existing,from);
- polar->angle += 90;
-
- cartesianCoord *c = ptc(from,polar->angle,polar->length);
- Vertex new2 = { .x = c->x, .y = c->y};
-
- segment_to(m, from, new1.x, new1.y);
- segment_to(m, from, new2.x, new2.y);
-}
-
-void segment_display(Segment* s) {
- printf("<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" stroke=\"black\" />",
- s->u->x, s->u->y, s->v->x, s->v->y);
-}
-
-void forceFields() {
- Map m;
- m.segments2_firstFree = 0;
- m.vertices[0] = (Vertex){ .x = 400, .y = 300, .s = NULL};
- m.vertices[1] = (Vertex){ .x = 401, .y = 309, .s = NULL};
- m.vertices_firstUnseen = 1;
- m.vertices_firstFree = 2;
-
- m.segments[0] = (Segment){ .u = &(m.vertices[0]), .v = &(m.vertices[1]), .nextU = NULL, .nextV = NULL};
- m.vertices[0].s = NULL;
- m.vertices[1].s = &(m.segments[0]);
- m.segments_firstFree = 1;
-
- grid_initvGrid(800, 600, 10);
- // TODO : insérer vertices[0] dans la grille.
- grid_insertVertex(&(m.vertices[0]));
- grid_insertVertex(&(m.vertices[1]));
-
- int i;
- while(m.vertices_firstFree < vertices_array_size-2) {
- //fprintf(stderr,"passage %d\n",i);
- if(m.vertices_firstUnseen >= m.vertices_firstFree) {
- break;
- }
-
- fv(&m, &(m.vertices[m.vertices_firstUnseen++]));
- }
-
- grid_drawGrid();
- for (i = 0; i < m.segments_firstFree; i++) {
- //fprintf(stderr,"Dessin du segment %d\n",i);
- segment_display(&(m.segments[i]));
- }
-}
-
-int main() {
- Vertex points[] = {
- { .x=10, .y=10 },
- { .x=790, .y=10 },
- { .x=600, .y=300 },
- { .x=790, .y=590 },
- { .x=10, .y=590 },
- };
- int n = 5;
-
- svg_start(800,600);
- //carreY();
- forceFields();
-
- //int i;
- //for (i = 0; i < n; i++) {
-// svg_line(&(points[i]), &(points[(i+1)%n]));
-// }
-
-// grid_drawGrid();
-
-n=n;
- //roads(points);
- points[0] = points[0];
- svg_end();
- return 0;
-}
diff --git a/roads.h b/roads.h
@@ -1,96 +0,0 @@
-#include <stdio.h>
-#include <stdlib.h>
-#include <math.h>
-
-typedef struct Vertex {
- int x;
- int y;
- struct Segment* s;
-} Vertex;
-
-typedef struct Segment {
- Vertex *u;
- Vertex *v;
- struct Segment* nextU;
- struct Segment* nextV;
-} Segment;
-
-typedef Vertex Polygon;
-
-/* Cette structure définie un nœd de route. Le nœd contient la liste de toute les intersections.
- */
-typedef struct roadNodeY {
- Vertex *v;
- short nbIntersec;
- struct intersectionY **intersec;
-} roadNodeY;
-
-typedef struct roadPointY {
- struct roadPointY *first;
- struct roadPointY *next;
- struct roadPointY *previous;
- roadNodeY *rn;
-} roadPointY;
-
-/* Définition d'une intersection. Permet de savoir quelle route est concernée par cette intersection.
- * Elle permet également de changer la navigation por parcourir une nouvelle route.
- * */
-typedef struct intersectionY {
- roadPointY *roadId; // Premier point de la route qui lui sert d'identifiant.
- roadNodeY *next; // Nœd de la route juste après l'intersection.
- roadNodeY *previous; // Nœd de la route juste avant l'intersection.
- int zIndex; // Index sur l'axe z de la route.
-} intersectionY;
-
-typedef struct cartesianCoord {
- int x; // Coordonnées sur x.
- int y; // Coordonnées sur y.
-} cartesianCoord;
-
-typedef struct polarCoord {
- int angle; // Angle en degrès.
- int length; // Norme du vecteur.
-} polarCoord;
-
-typedef struct roadSet {
- roadPointY *roadId; // Identifiant de la route.
- roadPointY *rpc; // Nœd courrant.
-} roadStep;
-
-#define vertices_array_size 800
-#define segments_array_size 1024
-typedef struct Map {
- Vertex vertices[vertices_array_size];
- Segment segments[segments_array_size];
- Segment* segments2[segments_array_size]; // Stockage temporaire d'un sous ensemble de segments.
- int vertices_firstUnseen;
- int vertices_firstFree;
- int segments_firstFree;
- int segments2_firstFree;
- // TODO : champ grid & co. On peut même l'utiliser à la place de
- // vertices.
-} Map;
-
-Vertex ****vGrid;
-roadPointY **roadsList;
-short nbXSubDivision;
-short nbYSubDivision;
-short maxSegmentSize;
-short maxNodesInGrid = 16;
-int quarterWidth;
-int quarterHeight;
-
-int toX(Vertex*);
-int toY(Vertex*);
-void grid_initNodesGrid(int w, int h, int maxSegmentSize);
-short grid_insertVertex(Vertex *rn);
-int distBetween(Vertex *v, Vertex *u);
-Vertex** grid_getNearVertices(Vertex *v);
-Vertex** grid_getNearVertices2(int x, int y);
-Vertex* grid_getNearestVertex(Vertex *v);
-void grid_drawGrid();
-
-cartesianCoord* ptc(Vertex *origin, short angle, short length);
-polarCoord* ctp(Vertex *origin, Vertex *end);
-
-void grid_getNearSegments(Map*, int x, int y);
diff --git a/roads.md b/roads.md
@@ -1,225 +0,0 @@
-Réseaux de routes/quartiers
-===========================
-
-On part d'un quartier qu'on subdivise en plus petits quartiers en y
-trançant des rues.
-
-Un quartier est un polygone (pas forcément convexe !). Sur les côtés
-du polygone, des routes entrantes et sortantes peuvent être
-marquées. La somme des entrées (+) et sorties (-) du polygone est
-nulle.
-
-Concentrique
-------------
-
-C'est équivalent à dé-polariser le repère et construire un « mur »
-(sorte de grille avec beaucoup d'horizontales de grande longueur).
-
-Il faut trouver un algorithme de construction de mur, puis le
-re-polariser afin de pouvoir le lancer avec plusieurs centres.
-
-Grille
-------
-
-Algo 1
-
-* Choisir un angle.
-* Tracer des routes suivant cet angle et cet angle + 90°.
-* Les routes doivent pouvoir être assez longues (le tracé doit
- survivre à une intersection).
-
-Algo 2
-
-* Choisir un angle.
-* Tracer des petits segments de route suivant l'angle et l'angle+90°
-* Inhiber la subdivision de segments (ne pas les couper en deux).
-* Raccrocher les bouts des routes à des points proches si possible (et
- tant qu'on ne dévie pas trop en angle).
-
-Algo 3
-* Prendre une grille carrée / rectangulaire.
-* La tourner d'un certain angle.
-* Rattacher au bord du quartier les segments de la grille qui le
- croisent.
-* Supprimer aléatoirement certains segments, en gardant le graphe
- connexe.
-
-Algo 4
-* Choisir un angle pour dessiner les croix.
-* Dessiner une grosse croix avec des angles de 90° entre les segments,
- ± au milieu du quartier.
-* Subdiviser de la même manière les quatre (ou plus si le quartier
- d'origine n'est pas convexe) quartiers ainsi créés, en gardant le
- même angle (petites variations possibles).
-
-« Mur »
--------
-
-Comme une grille, mais les angles ne sont pas vraiment à 90°, et il y
-a beaucoup de longues rues dans l'une ou l'autre des directions.
-
- .________________________.
- | | | | |
- |___|________|______|____|
- | | |______|
- |_________|_______| |
- |______|__________|______|
-
-TODO : trouver un algo pour générer des « murs »
-
-Arborescent
------------
-
-On subdivise le quartier en polygones plus ou moins réguliers (grille,
-voronoi, …), et on fait partir un arbre depuis un point, qu'on étend
-jusqu'à avoir touché tous les polygones. Chaque polygone est un
-sous-quartier.
-
-Il est possible de s'arrêter avant d'avoir touché tous les polygones,
-auquel cas il faut regrouper les polygones non touchés avec d'autres
-pour qu'ils forment un seul quartier.
-
-Courbes de niveau
------------------
-
-Faire des routes suivant les courbes de niveau, avec la possibilité de
-monter ou descendre très légèrement pour rejoindre une autre ligne.
-
-* Partir d'un point, et choisir le point à X de distance qui minimise
- le dénivellé
-* Continuer à partir du point ainsi créé, en s'interdisant les retours
- en arrière trop brutaux
-* Arrêter la ligne quand le dénivellé devient trop important, ou quand
- on rejoint une autre ligne.
-
-Calculs nécessaires
-===================
-
-Polygones
----------
-
-Il faut pouvoir, à partir d'une liste de lignes, déterminer les
-polygones ainsi découpés (ou bien maintenir un arbre de polygones
-qu'on découpe au fur et à mesure qu'on trace des lignes traversant un
-polygone), pour connaître les sous-quartiers créés en traçant les
-routes.
-
-Points proches
---------------
-
-Énumérer les points proches d'un point donné.
-
-Pour cela, faire un quadtree (un arbre avec 4 fils à chaque noeud)
-représentant des carrés composés de quatre carrés, et stocker dans
-chaque noeud s'il contient des points dans son sous-arbre ou non. Les
-noeuds feuille listent les points qu'ils contiennent. Quand on dépasse
-un certain seuil pour le nombre de points contenus dans un noeud
-feuille, on le subdivise.
-
-Lignes proches
---------------
-
-Énumérer les lignes proches d'un point donné.
-
-Quand on ajoute un point au graphe des routes, on l'insère à la bonne
-position dans le quadtree.
-
-Quand on trace un segment entre deux points, on indique sa présence
-dans tous les noeuds qu'il traverse. *TODO* : cela coûte cher en temps
-et en espace !
-
-Autre possibilité : forcer les routes à être sur le bord de polygones
-(comme les rivières). Quand on veut tracer une route quelque part, on
-subdivise le polygone contenant pour que le nouveau point soit sommet
-d'au moins un des polygones, et la route côté de ce polygone.
-
-Intérieur d'un polygone
---------------------
-
-Pouvoir sélectionner aléatoirement des points à l'intérieur d'un
-polygone (pour pouvoir faire les centres des réseaux concentriques par
-exemple).
-
-Angles et vecteurs
-------------------
-
-Pouvoir ajouter un vecteur à un point, appliquer une rotation sur le
-vecteur…
-
-Algo déformation de coordonées
-==============================
-
-Partir d'une grille idéale carrée et appliquer des déformations de
-coordonnées dessus, plus une fonction de densité de points (taille des
-bâtiments). Dé-transformer la fonction de densité de points,
-l'utiliser pour générer la grille parfaite avec des densités
-différentes, puis transformer cette grille.
-
-Algo champs de force
-====================
-
-Variables :
-* `vertices` est le tableau des vertices. Il se comporte comme une
- fifo : les vertex qui y sont ajoutés sont en attente de traitement.
-* `segments` est le tableau des segments de route.
-
-Algo :
-* Choisir des champs de force. `f(vertex)` ajoute aux tableaux les
- segments de route qu'on peut faire partir du point `(x,y)`.
-* Initialiser le tableau de stockage des vertices `vertices` à vide.
-* Initialiser le tableau de stockage des segments `segments` à vide.
-* Choisir un point de départ aléatoire, et insérer `(x,y)` dans
- `vertices`.
-* Tant qu'on n'a pas traité tous les vertices :
- * Prendre le premier point `(x,y)` non traité de `vertices`.
- * f(x,y).
-
-Algo de f(x,y) :
-* Pour chaque segment que l'on souhaite ajouter à partir de `(x,y)` :
- * Insérer le nouveau vertex dans la grille ou en prendre l'existant.
- * Si on inère le vertex, l'ajouter à `vertices`.
- * Ajouter le segment à `segments`.
-
-Représentation simpliste des segments et routes
-===============================================
-
-* Dans chaque vertex, avoir un pointeur vers un des segments auxquels
- il appartient.
-* Dans chaque segment, avoir un pointeur vers le segment de même
- origine suivant dans le sens des aiguilles d'une montre.
-* Dans chaque segment, avoir un pointeur vers le segment de même
- extrémité suivant dans le sens des aiguilles d'une montre.
-
-Algorithme de maintien des polygones
-====================================
-
-* Partir du périmètre du polygone de base.
-* Lorsqu'on ajoute un segment partant d'un point de ce périmètre,
- étendre ce périmètre pour qu'il fasse l'aller-retour sur le segment.
-* Lorsqu'on ajoute un segment reliant deux points existants du
- périmètre, séparer le périmètre en deux : le périmètre passant par
- le côté gauche du segment, et celui passant par le côté droit du
- segment.
-* TODO : gestion possible des « trous » ? (càd quand on ajoute un
- segment qui n'est pas relié au périmètre). Serait pratique pour
- pouvoir ajouter certains gros bâtiments avant la création des
- routes.
-
-Snapping des segments de route
-==============================
-
-Invariants :
-* Un segment qui part d'une case arrive forcément dans une des cases
- adjacentes.
-* Il n'y a qu'un seul vertex par case.
-
-Maintien des invariants :
-* Si nécessaire, ralonger ou raccourcir les segments.
-* Lorsqu'un segment atterrit dans une des cases voisines, s'il y a
- déjà un vertex, il s'y raccroche, sinon on crée l'unique vertex de
- la case.
-
-Idées en vrac :
-* Densité de probabilité de split (= créer de nouvelles routes à
- partir du point). Par exemple : 10% de chance de faire un split par
- mètre = en moyenne, un split tous les 10 mètres ?
diff --git a/roam.c b/roam.c
@@ -1,318 +0,0 @@
-#include "roam.h"
-#include "hash.h"
-
-/* Implémentation de ROAM
- * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.1811&rep=rep1&type=pdf
- *
- * Triangle T (apex, vLeft, vRight)
- * . vApex
- * /|\
- * / | \
- * tLeftChild / 90° \ tRightChild
- * / | \
- * / 45°|45° \
- * vLeft ._____._____. vRight
- * vCenter
- *
- * Le triangle T contient le champ `vCenter`, qui permet de construire
- * ses sous-triangles tLeftChild (vCenter, vApex, vLeft) et
- * tRightChild (vCenter, vRight, vApex), du moment qu'on connait
- * vApex, vLeft et vRight quand on manipule T. On les connaît car on a
- * traversé récursivement ses triangles parents avant d'y arriver.
- *
- * T est le tParent de tLeftChild et tRightChild.
- *
- * Voisins :
- *
- * Le tBaseNeighbor de T est le triangle en-dessous, qui partage son
- * côté (vLeft,vRight).
- *
- * Le tLeftNeighbor de T est le triangle à gauche, qui partage son
- * côté (vApex,vLeft).
- *
- * Le tRightNeighbor de T est le triangle à droite, qui partage son
- * côté (vApex,vRight).
- *
- */
-
-
-/* Permet de récupérer la taille de la base du triangle (hypoténuse).*/
-// TODO Optimisze la fonction pour éviter la racine carée.
-int getFirstTriangleSize(Triangle* t) {
- return sqrt(((t->vRight->x - t->vLeft->x)^2) + ((t->vRight->y - t->vLeft->y)^2));
-}
-
-/* Interpolation linéaire entre deux points.
- * (x,y) est le point dont on veut connaître la valeur
- * (x1,y1)--(x2,y2) est le carré dont on connaît les valeurs
- * ne,se,so,no sont les valeurs aux coins nord/sud-est/ouest du carré. */
-// A optimiser par aproximation.
-// Optimiser aussi le fait que la distance entre xy1 et xy2 est une puissance de 2, donc on peut faire un simple décalage.
-// Peut être réalisé par une multiplication de matrice (donc sur le GPU) : http://en.wikipedia.org/wiki/Bilinear_interpolation
-int interpolation(int x, int y, int x1, int y1, int x2, int y2, int ne, int se, int so, int no) {
- int ret = 0;
- // on multiplie chaque coin par la superficie du rectangle formé par (x,y) et ce coin.
- ret += so * (x2-x) * (y-y1);
- ret += no * (x2-x) * (y2-y);
- ret += ne * (x-x1) * (y2-y);
- ret += se * (x-x1) * (y-y1);
- return ret / ((x2-x1) * (y2-y1));
-}
-
-// renvoie un z entre 0 et 255
-int get_z(int x, int y) {
- x = x; /* Unused */
- y = y; /* Unused */
- int z = 0;
- int level;
- int maxlevel = 6;
- for (level = maxlevel; level >= 0; level--) {
- int step = (1 << level);
- int mask = step - 1;
- int zmax = 2*step - 1;
- int x1 = x & ~mask;
- int y1 = y & ~mask;
- int x2 = x1 + step;
- int y2 = y1 + step;
- z += interpolation(x, y, x1, y1, x2, y2, hash3(level, x2, y1) & zmax, hash3(level, x2, y2) & zmax, hash3(level, x1, y2) & zmax, hash3(level, x1, y1) & zmax);
- }
- // ici le résultat est entre 0 (inclus) et 2^(2+maxlevel) (non inclus)
- // On normalise sur [0,256[ sachant que 256 == 2^8.
- if (maxlevel > 6)
- z = z >> (-6+maxlevel);
- else if (maxlevel != 6)
- z = z << (6-maxlevel);
- return z;
-}
-
-void triangle_split(Triangle* t) {
- Triangle* b; /* base neighbor */
- Vertex* c; /* center vertex */
- Triangle* subTLeft;
- Triangle* subTRight;
- Triangle* subBLeft;
- Triangle* subBRight;
-
- b = t->tBaseNeighbor;
- if (b != NULL)
- if (b->tBaseNeighbor != t)
- /* T and its base neighbor aren't of the same LOD. */
- triangle_split(b);
- b = t->tBaseNeighbor;
-
- c = (Vertex*)malloc(sizeof(Vertex));
- c->x = (t->vLeft->x + t->vRight->x) / 2;
- c->y = (t->vLeft->y + t->vRight->y) / 2;
- c->z = get_z(c->x, c->y);
-
- subTLeft = (Triangle*)malloc(sizeof(Triangle));
- subTRight = (Triangle*)malloc(sizeof(Triangle));
- if (b != NULL) {
- subBLeft = (Triangle*)malloc(sizeof(Triangle));
- subBRight = (Triangle*)malloc(sizeof(Triangle));
- } else {
- subBLeft = NULL;
- subBRight = NULL;
- }
-
- /* subTLeft */
- {
- /* Vertices */
- subTLeft->vApex = c;
- subTLeft->vLeft = t->vApex;
- subTLeft->vRight = t->vLeft;
- /* Children */
- subTLeft->tLeftChild = NULL;
- subTLeft->tRightChild = NULL;
- /* To neighbors */
- subTLeft->tBaseNeighbor = t->tLeftNeighbor;
- subTLeft->tLeftNeighbor = subTRight;
- subTLeft->tRightNeighbor = subBRight;
- /* Parent */
- subTLeft->tParent = t;
- /* From neighbors */
- if (t->tLeftNeighbor != NULL) {
- if (t->tLeftNeighbor->tBaseNeighbor == t) {
- t->tLeftNeighbor->tBaseNeighbor = subTLeft;
- } else {
- t->tLeftNeighbor->tRightNeighbor = subTLeft;
- }
- }
- }
- /* subTRight */
- {
- /* Vertices */
- subTRight->vApex = c;
- subTRight->vLeft = t->vRight;
- subTRight->vRight = t->vApex;
- /* Children */
- subTRight->tLeftChild = NULL;
- subTRight->tRightChild = NULL;
- /* To neighbors */
- subTRight->tBaseNeighbor = t->tRightNeighbor;
- subTRight->tLeftNeighbor = subBLeft;
- subTRight->tRightNeighbor = subTLeft;
- /* Parent */
- subTRight->tParent = t;
- /* From neighbors */
- if (t->tRightNeighbor != NULL) {
- if (t->tRightNeighbor->tBaseNeighbor == t) {
- t->tRightNeighbor->tBaseNeighbor = subTRight;
- } else {
- t->tRightNeighbor->tLeftNeighbor = subTRight;
- }
- }
- }
- /* subBLeft */
- if (b != NULL) {
- /* Vertices */
- subBLeft->vApex = c;
- subBLeft->vLeft = b->vApex;
- subBLeft->vRight = t->vRight; /* == b->vLeft, mais a plus de chances d'être dans le cache, non ? */
- /* Children */
- subBLeft->tLeftChild = NULL;
- subBLeft->tRightChild = NULL;
- /* To neighbors */
- subBLeft->tBaseNeighbor = b->tLeftNeighbor;
- subBLeft->tLeftNeighbor = subBRight;
- subBLeft->tRightNeighbor = subTRight;
- /* Parent */
- subBLeft->tParent = t;
- /* From neighbors */
- if (b->tLeftNeighbor != NULL) {
- if (b->tLeftNeighbor->tBaseNeighbor == b) {
- b->tLeftNeighbor->tBaseNeighbor = subBLeft;
- } else {
- b->tLeftNeighbor->tRightNeighbor = subBLeft;
- }
- }
- }
- /* subBRight */
- if (b != NULL) {
- /* Vertices */
- subBRight->vApex = c;
- subBRight->vLeft = t->vLeft; /* == b->vRight, mais a plus de chances d'être dans le cache, non ? */
- subBRight->vRight = b->vApex;
- /* Children */
- subBRight->tLeftChild = NULL;
- subBRight->tRightChild = NULL;
- /* To neighbors */
- subBRight->tBaseNeighbor = b->tRightNeighbor;
- subBRight->tLeftNeighbor = subTLeft;
- subBRight->tRightNeighbor = subBLeft;
- /* Parent */
- subBRight->tParent = t;
- /* From neighbors */
- if (b->tRightNeighbor != NULL) {
- if (b->tRightNeighbor->tBaseNeighbor == b) {
- b->tRightNeighbor->tBaseNeighbor = subBRight;
- } else {
- b->tRightNeighbor->tLeftNeighbor = subBRight;
- }
- }
- }
- t->tLeftChild = subTLeft;
- t->tRightChild = subTRight;
- if (b != NULL) {
- b->tLeftChild = subBLeft;
- b->tRightChild = subBRight;
- }
-}
-
-void triangle_merge(Triangle* t, Triangle* b) {
- t = t;
- b = b;
- /* TODO : free récursivement les triangles… Peut-être pas
- * nécessaire vu qu'on peut les garbage-collecter en quelque sorte
- * lorsqu'on envoie tous les triangles à la carte (on verra ceux
- * qu'on n'envoie pas).
- */
- t->tLeftChild = NULL;
- t->tRightChild = NULL;
- b->tLeftChild = NULL;
- b->tRightChild = NULL;
-}
-
-/* TODO : MinMax Heap : http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node11.html
- * TODO : flexible memory usage : http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node15.html
- * TODO : pour l'instant les comparaisons se font sur les adresses !
- */
-
-/* Index des éléments du tas dans le tableau de stockage.
- * 0
- * 1 2
- * 3 4 5 6
- * 7 8 9 . . . . .
- */
-
-#define HEAP_PARENT(x) (((x)-1)/2)
-#define HEAP_LEFT_CHILD(x) ((x)*2+1)
-#define HEAP_RIGHT_CHILD(x) ((x)*2+2)
-#define SWAP(type, a, b) do { type SWAP_temp = (a); (a) = (b); (b) = SWAP_temp; } while (0)
-/* Insère `node` dans `heap`.
- * @param n : nombre de `node`s déjà dans le `heap`.
- */
-void maxheap_insert(Triangle** heap, Triangle* node, unsigned int n) {
- heap[n] = node;
- unsigned int x = n;
- while (x != 0 && heap[x] > heap[HEAP_PARENT(x)]) {
- SWAP(Triangle*, heap[x], heap[HEAP_PARENT(x)]);
- }
-}
-
-/* Récupère le plus grand élément de `heap`.
- * @param n : nombre de `node`s déjà dans le `heap`.
- */
-Triangle* maxheap_pop_max(Triangle** heap, unsigned int n) {
- Triangle* ret = heap[0];
- heap[0] = heap[n];
- unsigned int x = 0;
- while (x != n &&
- (heap[x] < heap[HEAP_LEFT_CHILD(x)] || heap[x] < heap[HEAP_RIGHT_CHILD(x)])) {
- if (heap[HEAP_LEFT_CHILD(x)] > heap[HEAP_RIGHT_CHILD(x)]) {
- SWAP(Triangle*, heap[x], heap[HEAP_LEFT_CHILD(x)]);
- } else {
- /* échanger right et x */
- SWAP(Triangle*, heap[x], heap[HEAP_RIGHT_CHILD(x)]);
- }
- }
- return ret;
-}
-
-void recursiveSplit(Triangle* t, int n) {
- if (n == 0) return;
- if (t->tLeftChild == NULL) { // t is not already split
- triangle_split(t);
- }
- recursiveSplit(t->tLeftChild, n-1);
- recursiveSplit(t->tRightChild, n-1);
-}
-
-Triangle* initDefaultExample() {
- Triangle* t = (Triangle*)malloc(sizeof(Triangle));
- Vertex* vApex = (Vertex*)malloc(sizeof(Vertex));
- Vertex* vLeft = (Vertex*)malloc(sizeof(Vertex));
- Vertex* vRight = (Vertex*)malloc(sizeof(Vertex));
-
- vApex->x = 256; vApex->y = 256; vApex->z = get_z(256,256);
- vLeft->x = 0; vLeft->y = 0; vLeft->z = get_z(0,0);
- vRight->x = 512; vRight->y = 0; vRight->z = get_z(512,0);
-
- t->vApex = vApex;
- t->vLeft = vLeft;
- t->vRight = vRight;
- t->tLeftChild = NULL;
- t->tRightChild = NULL;
- t->tBaseNeighbor = NULL;
- t->tLeftNeighbor = NULL;
- t->tRightNeighbor = NULL;
- t->tParent = NULL;
-
- recursiveSplit(t, 10);
- /* triangle_split(t); */
- /* triangle_split(t->tLeftChild); */
- /* triangle_split(t->tLeftChild->tLeftChild); */
- /* triangle_split(t->tLeftChild->tRightChild); */
-
- return t;
-}
diff --git a/roam.h b/roam.h
@@ -1,32 +0,0 @@
-#include <stdio.h>
-#include <stdlib.h>
-#include <math.h>
-
-typedef struct Vertex {
- int x;
- int y;
- int z;
- float xNormal;
- float yNormal;
- float zNormal;
- int refCount;
- struct Vertex* next[4];
- /* Ajouter des champs ici. */
-} Vertex;
-
-typedef struct Triangle {
- Vertex* vApex;
- Vertex* vLeft;
- Vertex* vRight;
- struct Triangle* tLeftChild;
- struct Triangle* tRightChild;
- struct Triangle* tBaseNeighbor;
- struct Triangle* tLeftNeighbor;
- struct Triangle* tRightNeighbor;
- struct Triangle* tParent;
-} Triangle;
-
-Triangle* initDefaultExample();
-int interpolation(int x, int y, int x1, int y1, int x2, int y2, int ne, int se, int so, int no);
-unsigned int hash2(unsigned int a, unsigned int b);
-int get_z(int x, int y);
diff --git a/simple-terrain.c b/simple-terrain.c
@@ -1,122 +0,0 @@
-#include <stdio.h>
-#include <math.h>
-
-#define SIZE 512
-// best value for MAX_DETAIL is 8
-#define MAX_DETAIL 8
-
-int bsr(int x) {
- asm volatile("bsr %0, %0" : "=r" (x) : "0" (x) : "0");
- return x;
-}
-
-int random_from_rec2(int a, int b, int c) {
- b += a; // b = a + b // 2 bytes
- a *= b; // a = a * (a + b) // 2 bytes
- b ^= a; // b = (a + b) ^ (a * (a + b)) // 2 bytes
- a += 211; // a = (a * (a + b)) + 5 // 2-3 bytes ; 211 is wonderfull.
- b /= 2; // b = ((a + b) ^ (a * (a + b))) / 2 // 2 bytes
-
- if (c == 0)
-// return a >> 2; // 3 bytes :( , but we can do with >>1 or even without.
- return a >> 1;
- return random_from_rec2(a, b, c-1);
-}
-
-unsigned char random_from(int a, int b) {
- return (random_from_rec2(a, b, 1)) & 0xff;
-}
-
-/* Alternate method to compute a single detail level for z.
- // This square
- z = random_from(xd, yd);
-
- // x interpolation
- zb = random_from(xd + 1, yd);
- z += ((zb-z) * (x & mask)) >> detail;
-
- // y interpolation
- zc = random_from(xd, yd + 1);
- zb = random_from(xd + 1, yd + 1);
- zc += ((zb-zc) * (x & mask)) >> detail;
- z += ((zc-z) * (y & mask)) >> detail;
-*/
-
-int get_z(int x, int y) {
- int detail, mask;
- int xd, yd;
- int z00, z01, z10, z11;
- int xm, ym, mxm, mym;
- unsigned int z, ztot;
-
- ztot = 0;
- for (detail = 0; detail < MAX_DETAIL; detail++) {
- x++; // slightly blurs vertical
- y++; // and horizontal artifacts.
-
- mask = (1<<detail) - 1;
- xd = x >> detail;
- yd = y >> detail;
-
- if (0 == 0) {
- // Method one
- z00 = random_from(xd + 0, yd + 0);
- z01 = random_from(xd + 0, yd + 1);
- z10 = random_from(xd + 1, yd + 0);
- z11 = random_from(xd + 1, yd + 1);
-
- xm = ((xd + 1) << detail) - x;
- ym = ((yd + 1) << detail) - y;
- mxm = (1 << detail) - xm;
- mym = (1 << detail) - ym;
-
- z = 0;
- z += z00 * xm * ym ;
- z += z01 * xm * mym;
- z += z10 * mxm * ym ;
- z += z11 * mxm * mym;
-
- z >>= ((detail * 2) + (MAX_DETAIL - detail));
- // Method two
- } else {
- // Alternate method
- int zb, zc;
- // This square
- z = random_from(xd, yd);
-
- // x interpolation
- zb = random_from(xd, yd + 1);
- z += ((zb-z) * (y & mask)) >> detail;
-
- // y interpolation
- zc = random_from(xd + 1, yd);
- zb = random_from(xd + 1, yd + 1);
- zc += ((zb-zc) * (y & mask)) >> detail;
- z += ((zc-z) * (x & mask)) >> detail;
-
- z >>= 0;
- // Alternate method
- }
-
- // add this detail level
- ztot += z;
- }
- //x = x - MAX_DETAIL; // when using x++ and y++
- //y = y - MAX_DETAIL; // to reduce artifacts.
-
- return ztot & 0xff;
-}
-
-int main(int argc, char** argv) {
- int y;
- int x;
- if (argc != 1) {
- fprintf(stderr, "Aide :\n");
- fprintf(stderr, "Utilisez ./simple-terrain | display pour visualiser la sortie.\n");
- fprintf(stderr, "Utilisez ./simple-terrain > fichier.pnm pour sauvegarder.\n");
- }
- printf("P5 %d %d 255\n", SIZE, SIZE);
- for (y=SIZE-1; y>=0; y--)
- for (x=0; x<SIZE; x++)
- printf("%c", (char)get_z(x,y));
-}
diff --git a/square.c b/square.c
@@ -1,305 +0,0 @@
-#include "square.h"
-
-// Positionne v à (xx,yy) et calcule z. Met ref_count à 0.
-inline void init_vertex(Vertex* v, int x, int y) {
- v->refCount = 0;
- v->x = x;
- v->y = y;
- v->z = get_z(x,y);
-}
-
-// ROTATE4(x,r) == x+r % 4
-#define ROTATE4(x,r) ((x+r) & 3)
-
-// L'ordre dans les tableaux est toujours {ne,se,so,no} ou bien {n,e,s,o}.
-typedef enum QTQuadrant { QT_NE = 0, QT_SE = 1, QT_SO = 2, QT_NO = 3 } QTQuadrant;
-typedef enum QTCardinal { QT_N = 0, QT_E = 1, QT_S = 2, QT_O = 3 } QTCardinal;
-
-#define ROT_NE (ROTATE4(QT_NE, r))
-#define ROT_SE (ROTATE4(QT_SE, r))
-#define ROT_SO (ROTATE4(QT_SO, r))
-#define ROT_NO (ROTATE4(QT_NO, r))
-
-#define ROT_N (ROTATE4(QT_N, r))
-#define ROT_E (ROTATE4(QT_E, r))
-#define ROT_S (ROTATE4(QT_S, r))
-#define ROT_O (ROTATE4(QT_O, r))
-
-
-static inline void vertex_link_create(Vertex* a, Vertex* b, QTCardinal directionAB) {
- //printf("vertex_link_create %x to %x direction %d (N=%d)\n", (int)a, (int)b, directionAB, QT_N);
- if (a != NULL) a->next[directionAB] = b;
- if (b != NULL) b->next[ROTATE4(directionAB, 2)] = a;
-}
-
-static inline void vertex_link_between(Vertex* vnew, Vertex* a, Vertex* b, QTCardinal directionAB) {
- vertex_link_create(a, vnew, directionAB);
- vertex_link_create(vnew, b, directionAB);
-}
-
-static inline void vertex_link_remove(Vertex* v) {
- vertex_link_create(v->next[QT_S], v->next[QT_N], QT_N);
- vertex_link_create(v->next[QT_O], v->next[QT_E], QT_E);
-}
-
-static inline void qtnode_link_create(QTNode* a, QTNode* b) {
- if (a != NULL) a->nextNode = b;
- if (b != NULL) b->previousNode = a;
-}
-
-inline Vertex* use_vertex(Vertex* v) { v->refCount++; return v; }
-inline void unuse_vertex(Vertex* v) {
- // TODO : assert(v->refCount > 0);
- if (--(v->refCount) == 0) {
- // Supprime le vertex des listes de parcours.
- vertex_link_remove(v);
- free(v);
- }
-}
-
-void QT_split(QTNode* parent) {
- // Ne pas split un noeud déjà split.
- if (parent->children[QT_NE] != NULL) return;
-
- int r;
- QTNode* q[4];
- for (r = 0; r < 4; r++) {
- q[ROT_NE] = malloc(sizeof(QTNode));
- }
-
- Vertex* new_vertices[4];
- for (r = 0; r < 4; r++) {
- // réutiliser le vertex existant (parent->top_neighbor->se_child->so ou bien parent->top_neighbor->so_child->se)
- if (parent->neighbors[ROT_N] != NULL && parent->neighbors[ROT_N]->children[ROT_SE] != NULL) {
- new_vertices[ROT_N] = parent->neighbors[ROT_N]->children[ROT_SE]->vertices[ROT_SO];
- } else {
- new_vertices[ROT_N] = (Vertex*)malloc(sizeof(Vertex));
- // Insère le nouveau vertex entre les deux coins de parent.
- vertex_link_between(new_vertices[ROT_N], parent->vertices[ROT_NO], parent->vertices[ROT_NE], ROT_E);
- // place le nouveau vertex après center.
- vertex_link_create(parent->center, new_vertices[ROT_N], ROT_N);
- // Définit x,y,z et ref_count.
- switch (r) { // TODO : Devrait être factorisé.
- case 0: init_vertex(new_vertices[0], parent->center->x, parent->vertices[QT_NE]->y); break;
- case 1: init_vertex(new_vertices[1], parent->vertices[QT_SE]->x, parent->center->y); break;
- case 2: init_vertex(new_vertices[2], parent->center->x, parent->vertices[QT_SO]->y); break;
- case 3: init_vertex(new_vertices[3], parent->vertices[QT_NO]->x, parent->center->y); break;
- }
- }
- }
-
- for (r = 0; r < 4; r++) { // Dans le corps de la boucle, positions pour le quadrant ne.
- q[ROT_NE]->center = malloc(sizeof(Vertex));
- // Pas besoin d'insérer center dans une des listes : à sa création il ne sera accédé dans aucun parcours de périmètre.
- // Coordonnées du centre de qne = moyenne du center et de parent->vertices[QT_NE].
- init_vertex(q[ROT_NE]->center, (parent->center->x + parent->vertices[ROT_NE]->x) / 2, (parent->center->y + parent->vertices[ROT_NE]->y) / 2);
- use_vertex(q[ROT_NE]->center);
-
- q[ROT_NE]->vertices[ROT_NE] = use_vertex(parent->vertices[ROT_NE]);
- q[ROT_NE]->vertices[ROT_SE] = use_vertex(new_vertices[ROT_E]);
- q[ROT_NE]->vertices[ROT_SO] = use_vertex(parent->center);
- q[ROT_NE]->vertices[ROT_NO] = use_vertex(new_vertices[ROT_N]);
-
- q[ROT_NE]->children[ROT_NE] = NULL;
- q[ROT_NE]->children[ROT_SE] = NULL;
- q[ROT_NE]->children[ROT_SO] = NULL;
- q[ROT_NE]->children[ROT_NO] = NULL;
-
- // Si le voisin du haut de parent a un se_child, c'est le voisin du haut de qne.
- if (parent->neighbors[ROT_N] != NULL) {
- q[ROT_NE]->neighbors[ROT_N] = parent->neighbors[ROT_N]->children[ROT_SE];
- if (parent->neighbors[ROT_N]->children[ROT_SE] != NULL)
- parent->neighbors[ROT_N]->children[ROT_SE]->neighbors[ROT_S] = q[ROT_NE];
- } else {
- q[ROT_NE]->neighbors[ROT_N] = NULL;
- }
- // Si le voisin de droite de parent a un no_child, c'est le voisin de droite de qne.
- if (parent->neighbors[ROT_E] != NULL) {
- q[ROT_NE]->neighbors[ROT_E] = parent->neighbors[ROT_E]->children[ROT_NO];
- if (parent->neighbors[ROT_E]->children[ROT_NO] != NULL)
- parent->neighbors[ROT_E]->children[ROT_NO]->neighbors[ROT_O] = q[ROT_NE];
- } else {
- q[ROT_NE]->neighbors[ROT_E] = NULL;
- }
- q[ROT_NE]->neighbors[ROT_S] = q[ROT_SE];
- q[ROT_NE]->neighbors[ROT_O] = q[ROT_NO];
-
- parent->children[ROT_NE] = q[ROT_NE];
- }
-
- // remplacer parent par ses quatre enfants dans la liste d'énumération de tous les QTNode feuilles.
- qtnode_link_create(parent->previousNode, q[QT_NO]);
- qtnode_link_create(q[QT_NO], q[QT_NE]);
- qtnode_link_create(q[QT_NE], q[QT_SE]);
- qtnode_link_create(q[QT_SE], q[QT_SO]);
- qtnode_link_create(q[QT_SO], parent->nextNode);
-
- // TODO : set minLOD = maxLOD = parent->LOD + 1; // À moins que ça soit le parcours récursif de màj du mesh qui écrive cette information ?
-}
-
-void QT_merge(QTNode* parent) {
- // Ne pas merge un noeud sans enfants.
- if (parent->children[QT_NE] == NULL) return;
-
- qtnode_link_create(parent->children[QT_NO]->previousNode, parent);
- qtnode_link_create(parent, parent->children[QT_SO]->nextNode);
-
- int r;
- for (r = 0; r < 4; r++) {
- // Merge récursif des enfants.
- QT_merge(parent->children[ROT_NE]);
-
- // reset à NULL les voisins qui pointaient vers des enfants.
- if (parent->neighbors[ROT_N] != NULL)
- if (parent->neighbors[ROT_N]->children[ROT_SE] != NULL)
- parent->neighbors[ROT_N]->children[ROT_SE]->neighbors[ROT_S] = NULL;
- if (parent->neighbors[ROT_E] != NULL)
- if (parent->neighbors[ROT_E]->children[ROT_NO] != NULL)
- parent->neighbors[ROT_E]->children[ROT_NO]->neighbors[ROT_O] = NULL;
-
- unuse_vertex(parent->children[ROT_NE]->center);
- int i;
- for (i = 0; i < 4; i++)
- unuse_vertex(parent->children[ROT_NE]->vertices[i]);
-
- free(parent->children[ROT_NE]);
- parent->children[ROT_NE] = NULL;
- }
-}
-
-QTNode* QT_baseNode() {
- int i;
- QTNode* q = malloc(sizeof(QTNode));
- Vertex* _v = (Vertex*) malloc(sizeof(Vertex)*5);
- Vertex* v[5]; for (i = 0; i < 5; i++) v[i] = &(_v[i]);
-
- vertex_link_create(v[1], v[2], QT_S);
- vertex_link_create(v[2], v[3], QT_O);
- vertex_link_create(v[3], v[4], QT_N);
- vertex_link_create(v[4], v[1], QT_E);
-
- init_vertex(v[0], 0, 0);
- init_vertex(v[1], +1024, -1024);
- init_vertex(v[2], +1024, +1024);
- init_vertex(v[3], -1024, +1024);
- init_vertex(v[4], -1024, -1024);
-
- q->center = use_vertex(v[0]);
-
- for (i = 0; i < 4; i++) {
- q->vertices[i] = use_vertex(v[i+1]);
- q->children[i] = NULL;
- q->neighbors[i] = NULL;
- }
-
- qtnode_link_create(q, NULL);
- qtnode_link_create(NULL, q);
-
- q->minLOD = 0;
- q->maxLOD = 0;
-
- return q;
-}
-
-void vertex_print(Vertex* v) {
- v=v;
- //printf("vertex %x(%d,%d,%d) N=%x E=%x S=%x O=%x\n", (unsigned int)v, v->x, v->y, v->z, (int)v->next[QT_N], (int)v->next[QT_E], (int)v->next[QT_S], (int)v->next[QT_O]);
-}
-
-void qtnode_print(QTNode* n) {
- //printf("node %x center=", (unsigned int)n);
- vertex_print(n->center);
-}
-
-void setNormal(Vertex *center, Vertex *va, Vertex *v) {
- int ax = va->x - center->x;
- int ay = va->y - center->y;
- int az = va->z - center->z;
- int bx = center->x - v->x;
- int by = center->y - v->y;
- int bz = center->z - v->z;
-
- float x = (float)((ay * bz) - (az * by));
- float y = (float)((az * bx) - (ax * bz));
- float z = -(float)((ax * by) - (ay * bx));
- float length = sqrt(x*x + y*y + z*z);
-
- length = length;
- x = x/length;
- y = y/length;
- z = z/length;
-
- /*va = center;
- glDisable(GL_LIGHTING);
- glDisable(GL_TEXTURE_2D);
- glColor3ub(255,255,255);
- glBegin(GL_LINES);
- glVertex3f(va->x,va->y,va->z);
- glVertex3f(va->x+500*x,va->y+500*y,va->z+500*z);
- glEnd();
- glEnable(GL_LIGHTING);*/
- glNormal3f(x,y,-z);
-}
-
-// first est le QTNode le plus en haut à gauche (NO). Par la suite, on
-// pourra créer un first artificiel qui évitera la descente récursive
-// jusqu'au NO le plus petit.
-void QT_enumerate(QTNode* first) {
- //printf("\nFRAME\n\n");
- while (first->children[QT_NO] != NULL)
- first = first->children[QT_NO];
-
- QTNode* n;
- int r;
- int i=0;
- Vertex* v;
- Vertex *center;
- Vertex *va = NULL;
-
- for (n = first; n != NULL; n = n->nextNode) {
- qtnode_print(n);
-
- glBegin(GL_TRIANGLE_FAN);
- setNormal(n->vertices[QT_NE],n->vertices[QT_SO],n->vertices[QT_SE]);
- // envoyer le vertex central
- center = n->center;
- setNormal(center,n->vertices[ROT_NO],n->vertices[ROT_NO]->next[ROT_E]);
- glVertex3f(center->x,center->y,center->z);
-
- // Pour chaque côté
- for (r = 0, i = 0; r < 4; r++) {
- // On parcourt tous les vertices le long du côté.
- for (v = n->vertices[ROT_NO]; v != n->vertices[ROT_NE]; i++, v = v->next[ROT_E]) {
- if(i <= 1){
- va = v;
- //setNormal(center,n->vertices[QT_SO],v);
- }
- else {
- setNormal(center,va,v);
- va = v;
- }
-
- glVertex3f(v->x,v->y,v->z);
- // envoyer un vertex du fan :
- //(void)(v);
- }
- }
-
- // Nécessaire ssi on fait un TRIANGLE_FAN et qu'on ne peut pas lui dire de fermer la boucle.
- // On renvoie le 1er vertex du bord :
- (void)(n->vertices[QT_NO]);
- setNormal(center,va,n->vertices[QT_NO]);
- glVertex3f(n->vertices[QT_NO]->x,n->vertices[QT_NO]->y,n->vertices[QT_NO]->z);
- glEnd();
- }
-}
-
-QTNode* QT_example() {
- QTNode* q = QT_baseNode();
- QT_split(q);
- QT_split(q->children[QT_NO]);
- QT_split(q->children[QT_NO]->children[QT_SE]);
- QT_split(q->children[QT_NO]->children[QT_SE]->children[QT_SO]);
- QT_split(q->children[QT_NO]->children[QT_SE]->children[QT_NE]);
- return q;
-}
diff --git a/square.h b/square.h
@@ -1,20 +0,0 @@
-// get_z()
-#include "roam.h"
-#include <GL/gl.h>
-
-// QuadTree Node.
-typedef struct QTNode {
- Vertex* center;
- Vertex* vertices[4];
- struct QTNode* children[4];
- struct QTNode* neighbors[4];
- // linked list across all nodes, for traversal when we display them.
- struct QTNode* nextNode;
- struct QTNode* previousNode;
- unsigned int minLOD;
- unsigned int maxLOD;
-} QTNode;
-
-QTNode* QT_example();
-void QT_enumerate(QTNode* first);
-void QT_split(QTNode* parent);
diff --git a/terrain.md b/terrain.md
@@ -1,49 +0,0 @@
-Liens
------
-
-* [Différents algos](http://www.sluniverse.com/php/vb/project-development/34994-automatically-generated-terrain-map.html) : Ridged Perlin Noise, Hills Algorithm, Craters, Erosion.
-* [Plein d'algos](http://planetgenesis.sourceforge.net/docs15/noise/noise.html#tileworley) dont plusieurs basés sur une sorte de voronoi donc à priori trop lents.
-* Affichage avec Ogre : [forum](http://www.ogre3d.org/forums/viewtopic.php?f=5&t=67177&p=442222), [doc](http://www.ogre3d.org/docs/api/html/classOgre_1_1BillboardSet.html)
-
-Perlin noise
-------------
-
-Ridged Perlin Noise
--------------------
-
-[Démo de Ridged Perlin Noise](http://www.inear.se/2010/04/ridged-perlin-noise/)
-
- // Fait des crêtes de montagnes ou vallées.
- abs(perlinNoise());
-
-Hills Algorithm
----------------
-
-Inverse de craters : on ajoute plein de cercles :
-
- repeat 1000 times :
- r=random();
- cx=random();
- cy=random();
- terrain[x][y] += r**2 + ((x-cx)**2 – (y-cy)**2)
-
-Craters
--------
-
-Soustraire des cercles (profondeur = f(distance au centre)) au terrain
-existant.
-Ou : générer un terrain nu, et soustraire plein de cercles aléatoirs.
-
-Erosion
--------
-
-Modélisation correcte : trop lent. À la place, outil "courbes" de gimp.
-
-Rivières
-========
-
-[Pathfinding pour créer des rivières](http://www.umbrarumregnum.net/articles/creating-rivers).
-Si on utilise une méthode de coût qui favorise de passer par un petit
-bout de bruit plutôt que de le contourner, mais favorise le
-contournement pour une grosse accumulation de bruit, on pourra même
-simuler l'érosion qui efface les méandres trop petits.
