Visualisation de blob en 2d avec l'algorithme du marching square

Soyez le premier à donner votre avis sur cette source.

Vue 9 634 fois - Téléchargée 466 fois

Description

C'est juste un petit code, pour montrer comme fonctionne l'algorithme du marching square. C'est comme le marching cube, mais en 2D. Ce code permet aussi de montrer une surface implicite : les blobs. Cela ressemble un peu au lampe à lave.
Le blob est composées de plusieurs cercles (des spheres quand c'est en 3D), qui on une zone d'influence. Quand deux cercles sont proches l'un de l'autres, leur influences se cumulent, et font transformer les 2 cercles en une seule forme qui se modifie quand les cercles bougent.
Le marching squares fonctionne de la manière suivante : on decoupe l'espace avec une grille régulière, sur chaque point de la grille on calcul l'inflence du blob, si celui ci depasse un certain niveau, on active le point. Apres dans chaque carré de la grille, on relie les points qui sont activées.

Source / Exemple :


#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <GL/glut.h>

#define BOTTOM j*inter
#define TOP (j+1)*inter
#define RIGHT (i+1)*inter
#define LEFT i*inter
#define TRUE  1
#define FALSE 0
#define BOOL char
/*coleur de fond*/
float background[]={0,0,0};
/*couleur du blob*/
float g_foward[]={1,0,0};
/*structure simple de cercle*/
typedef struct{
	float x;
	float y;
	float rayon;
} Cercle;

/* nombre de case dans la grille*/
int g_tailleGrille;
/* zone d'g_influence des cercle qui composent le  blob*/
double g_influence;
/* stockage des g_cercles*/
Cercle g_cercles[5];

/* distance d'un point a un cercle */
float equationSphere(Cercle c, float px, float py){
	return ((px-c.x)*(px-c.x)+(py-c.y)*(py-c.y)-c.rayon*c.rayon);
}

/* fonction qui calcule le "poids" d'un point sur la grille */
double calculBlob(float posx, float posy){
	double val = 0;
	int k;
	for(k=0; k<5; k++){
		val += exp(-100*equationSphere(g_cercles[k], posx, posy));
	}
	val/=5;
	return val;
}
/* calcul de l'interpolation lineaire entre 2 points */
double inter_lin(float Fp,float Fq){
	return (g_influence-Fp)/(Fq-Fp);
}

/* fonction qui parcours la grilles pour savoir quelle points appartiennent

    • au blobs et, dessin des blobs*/
void marchingSquares(){ int i,j; /*pour le parcours de la grille*/ float inter = 1.0/g_tailleGrille; /*espace entre 2 lignes de la grille*/ BOOL bl, br, tr, tl; /* booleens sur les 4 sommets du carré*/ float fbl, fbr, ftr, ftl; /* poids de chaque sommet */ float p1x, p1y, p2x, p2y, p3x, p3y, p4x, p4y; /* valeur des points "intermédaires" sur les cotés du carré */ int actifs; for(i=0; i<g_tailleGrille; i++){ for(j=0; j<g_tailleGrille; j++){ /* on calcule le poids de chaque sommet du carré*/ fbl = calculBlob(LEFT,BOTTOM); if(fbl >= g_influence) bl = TRUE; else bl= FALSE; fbr = calculBlob(RIGHT,BOTTOM); if(fbr >= g_influence) br = TRUE; else br= FALSE; ftr = calculBlob(RIGHT,TOP); if(ftr >= g_influence) tr = TRUE; else tr= FALSE; ftl = calculBlob(LEFT,TOP); if(ftl >= g_influence) tl = TRUE; else tl= FALSE; /* calcul des positions intermédaires */ p1x = LEFT; p1y = j*inter+inter*inter_lin(fbl, ftl); p2x = i*inter+inter*inter_lin(fbl, fbr); p2y = BOTTOM; p3x = RIGHT; p3y = j*inter+inter*inter_lin(fbr, ftr); p4x = i*inter+inter*inter_lin(ftl, ftr); p4y = TOP; /* En fonction des poids de chaque sommet on dessin le carré différement*/ actifs = bl+br+tr+tl; glColor3fv(g_foward); if(actifs == 4){ /* Les 4 sommets dedans*/ if(bl && br && tr && tl){ /* dessin d'un carré normal */ glBegin(GL_QUADS); glVertex2f(LEFT, BOTTOM); glVertex2f(RIGHT, BOTTOM); glVertex2f(RIGHT, TOP); glVertex2f(LEFT, TOP); glEnd(); } } else if(actifs == 3){ /* 3 points dedans */ /* dessin d'un carré avec une corne en moins */ /* (utilisation des valeurs intermédiares calculées avant */ glBegin(GL_TRIANGLE_FAN); if(bl==FALSE){ glVertex2f(p1x, p1y); glVertex2f(p2x, p2y); glVertex2f(RIGHT, BOTTOM); glVertex2f(RIGHT, TOP); glVertex2f(LEFT, TOP); glVertex2f(p1x, p1y); } else if(br==FALSE){ glVertex2f(LEFT, BOTTOM); glVertex2f(p2x, p2y); glVertex2f(p3x, p3y); glVertex2f(RIGHT, TOP); glVertex2f(LEFT, TOP); glVertex2f(LEFT, BOTTOM); } else if(tr==FALSE){ glVertex2f(p3x, p3y); glVertex2f(p4x, p4y); glVertex2f(LEFT, TOP); glVertex2f(LEFT, BOTTOM); glVertex2f(RIGHT, BOTTOM); glVertex2f(p3x, p3y); } else if(tl==FALSE){ glVertex2f(p4x, p4y); glVertex2f(p1x, p1y); glVertex2f(LEFT, BOTTOM); glVertex2f(RIGHT, BOTTOM); glVertex2f(RIGHT, TOP); glVertex2f(p4x, p4y); } glEnd(); } else if(actifs == 2){ /* 2 points d'activé*/ if(bl == tl){ if(bl==TRUE){ glBegin(GL_QUADS); glVertex2f(p2x, p2y); glVertex2f(p4x, p4y); glVertex2f(LEFT, TOP); glVertex2f(LEFT, BOTTOM); glEnd(); } else{ glBegin(GL_QUADS); glVertex2f(p2x, p2y); glVertex2f(RIGHT, BOTTOM); glVertex2f(RIGHT, TOP); glVertex2f(p4x, p4y); glEnd(); } } else if(bl == br){ if(bl==TRUE){ glBegin(GL_QUADS); glVertex2f(LEFT, BOTTOM); glVertex2f(RIGHT, BOTTOM); glVertex2f(p3x, p3y); glVertex2f(p1x, p1y); glEnd(); } else{ glBegin(GL_QUADS); glVertex2f(p3x, p3y); glVertex2f(RIGHT, TOP); glVertex2f(LEFT, TOP); glVertex2f(p1x, p1y); glEnd(); } } else{ if(bl == tr && bl == FALSE){ glBegin(GL_TRIANGLE_FAN); glVertex2f(p1x, p1y); glVertex2f(p2x, p2y); glVertex2f(RIGHT, BOTTOM); glVertex2f(p3x, p3y); glVertex2f(p4x, p4y); glVertex2f(LEFT, TOP); glEnd(); } else{ glBegin(GL_TRIANGLE_FAN); glVertex2f(LEFT, BOTTOM); glVertex2f(p2x, p2y); glVertex2f(p3x, p3y); glVertex2f(RIGHT, TOP); glVertex2f(p4x, p4y); glVertex2f(p1x, p1y); glEnd(); } } } else if(actifs==1){ /* juste un sommet dans le blob*/ glBegin(GL_TRIANGLES); if(bl==TRUE){ glVertex2f(p1x, p1y); glVertex2f(LEFT, BOTTOM); glVertex2f(p2x, p2y); } else if(br==TRUE){ glVertex2f(p2x, p2y); glVertex2f(RIGHT, BOTTOM); glVertex2f(p3x, p3y); } else if(tr==TRUE){ glVertex2f(p3x, p3y); glVertex2f(RIGHT, TOP); glVertex2f(p4x, p4y); } else if(tl==TRUE){ glVertex2f(p4x, p4y); glVertex2f(LEFT, TOP); glVertex2f(p1x, p1y); } glEnd(); } } } } void randg_cercles(){ /* génération de g_cercles de tailles aléatoire*/ g_cercles[0].x = 0.5; g_cercles[0].y = 0.5; g_cercles[0].rayon = 0.15; g_cercles[1].x = 0.25; g_cercles[1].y = 0.25; g_cercles[1].rayon = (((float)rand()/6)/RAND_MAX)+0.1; g_cercles[2].x = 0.25; g_cercles[2].y = 0.75; g_cercles[2].rayon = (((float)rand()/6)/RAND_MAX)+0.1; g_cercles[3].x = 0.75; g_cercles[3].y = 0.25; g_cercles[3].rayon = (((float)rand()/6)/RAND_MAX)+0.1; g_cercles[4].x = 0.75; g_cercles[4].y = 0.75; g_cercles[4].rayon = (((float)rand()/6)/RAND_MAX)+0.1; g_influence = 0.5; } /* fonctions openGL */ /* rafraississement de la scene */ void reshape(int width, int height) { glViewport(0, 0, width, height); glMatrixMode(GL_PROJECTION); glLoadIdentity(); glMatrixMode(GL_MODELVIEW); glLoadIdentity(); } /* affichage de la scene */ void display(void){ int i=0; glClearColor(0.0, 0.0, 0.0, 0.0); glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glLoadIdentity(); glTranslatef(-1,-1, 0); glScalef(2, 2, 2); /*dessin du blob*/ marchingSquares(); float inter=1.0/g_tailleGrille; /*dessin de la grille*/ glColor3f(0.5,0.5,0.5); glBegin(GL_LINES); for(i=0; i<=g_tailleGrille; i++){ glVertex2f(i*inter,0); glVertex2f(i*inter,1); glVertex2f(0, i*inter); glVertex2f(1, i*inter); } glEnd(); glutSwapBuffers(); glutPostRedisplay(); } /* gestion clavier */ void keyboard(unsigned char key, int x, int y){ switch (key) { default: case 'q': exit(1); break; } glutPostRedisplay(); } /* gestion des touches spéciales du clavier */ void keyboardSpe(int key, int x, int y){ switch(key){ case GLUT_KEY_UP: g_tailleGrille++; break; case GLUT_KEY_DOWN: if(g_tailleGrille>2) g_tailleGrille--; break; case GLUT_KEY_RIGHT: if(g_influence<0.5) g_influence += 0.1; break; case GLUT_KEY_LEFT: if(g_influence>0.2) g_influence -= 0.1; break; case GLUT_KEY_F1: randg_cercles(); break; default: break; } glutPostRedisplay(); } /* deplacement de la souris*/ void motion(int x, int y){ float posx = ((float)x)/512; float posy = 1-((float)y)/512; g_cercles[0].x = posx; g_cercles[0].y = posy; glutPostRedisplay(); } int main(int argc, char* argv[]){ printf("Commandes: souris -> deplacement du blob\ntouches haut/bas -> augmentation/diminution taille grille\ntouches gauche/droite -> augmentation/diminution de l'g_influence des blobs\nF1 -> changement de la taille des blobs"); srand(time(0)); g_tailleGrille = 50; g_influence = 0.5; randg_cercles(); glutInitDisplayMode(GLUT_RGB | GLUT_DEPTH | GLUT_DOUBLE); glutInitWindowSize(512, 512); glutInitWindowPosition(50, 50); glutCreateWindow("MS"); glutReshapeFunc(reshape); glutDisplayFunc(display); glutKeyboardFunc(keyboard); glutSpecialFunc(keyboardSpe); /* dès que la souris passe sur la fentre le blob bouge*/ glutPassiveMotionFunc(motion); glutMainLoop(); return 0; }

Conclusion :


Pour l'instant pas de bugs connus.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

MuPuF
Messages postés
536
Date d'inscription
mercredi 27 avril 2005
Statut
Membre
Dernière intervention
22 août 2008
-
Ca a au moins le mérite d'être jolie ;-)
C'est bien structuré, c'est bien

Bon now les critiques (a la con lol)
# /* distance d'un point a un cercle */
# float equationSphere(Cercle c, float px, float py){
# return ((px-c.x)*(px-c.x)+(py-c.y)*(py-c.y)-c.rayon*c.rayon); --> c'est distance² que tu retourne pas la distance lol, faut préciser au cas où quelqu'un reprendrait ta fonction
# }

Une petite doc qui t'aurais permis de faire ça serais sympa, perso je suis moyen en math lol, j'ai compris le principe en trés gros, mais sans doc, c'est un peu chaud de comprendre (c'est bien un S.I. qui parle, sans doc on est perdus lol)
cs_laurent1024
Messages postés
987
Date d'inscription
mardi 31 mai 2005
Statut
Membre
Dernière intervention
30 août 2012
11 -
Je vais essayer de faire une documentation en essayant d'etre clair, mais j'ai pas trop le temps en ce moment donc faudra peut etre attendre un peu
int a;
a++;
dPompei2
Messages postés
56
Date d'inscription
samedi 27 mars 2004
Statut
Membre
Dernière intervention
1 septembre 2006
-
C'est un peu à lagame of life si j'ai bien compris ?

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.