je cherche à faire un moteur graphique 3D avec la biblihotèque SDL2 en C. Cependant on ne peut que dessiner des rectangles et je cherche à dessiner destriangles pleins. Il faut donc que je trouve un algorithme pour qu'avec 3 coordonées entières (à 2 dimensions) de 3 points je puisse trouver l'ensemble des pixels à remplir.
J'envisage une piste: couper le triangle, en triangles rectangles dont deux côtés sont verticales et horizontales (le problème devient simple :p) mais je ne sais même pas si c'est toujours possible.
Par contre je préfère ne pas utiliser la méthode de tester tout les pixels et voir si ils appartiennent au triangle, méthode trop gourmande je pense.
Voilà j'espère que vous avez des idées je ne sais pas si c'est le bon endroit pour poser ma question, mais il n'y a pas de forum algorithmique donc bon
merci d'avance
- Edité par Aymeric Nguyen 23 avril 2020 à 21:45:42
Je ne connais pas cette bibliothèque. En fait, quand j'ai appris qu'elle ne disposait pas de fonctions pour tracer des droites ou des courbes, je m'y suis détourné. Mais je me souviens qu'il existe un site d'un participant régulier des forums qui explique comment tracer divers objets, par exemple des droites. Voyons dans mes favoris... Oui, c'est ici : http://fvirtman.free.fr/recueil/index.html chapitre 2. Il y a notamment le dessin de segments, qui permettra de tracer des rectangles. Mais pas de les remplir, zut...
> Par contre je préfère ne pas utiliser la méthode de tester tout les pixels et voir si ils appartiennent au triangle, méthode trop gourmande je pense.
Si tu testes tous les pixels de l'image, oui, c'est trop gourmand. Il faut juste tester les pixels dont les coordonnées (x, y) vérifient Xmin <= x <= Xmax et Ymin <= y <= Ymax, où Xmin est le plus petit x des trois sommets, Xmax le plus grand, et idem en y.
Mais je ne ferais pas ainsi (sauf si les triangles sont petits, car alors il y a peu de tests). Voici ce que je propose :
--> On appelle A le sommet le plus à gauche (x = Xmin), B le plus à droite (x = Xmax) et C le troisième sommet. Soit C est au-dessus de [AB], soit il est en-dessous. Je vais supposer par la suite qu'il est en-dessous (donc que son y est supérieur, puisque l'axe des y pointe vers le bas). L'autre cas se traite de même.
Idée : on va balayer les x de xA à xB. Pour chaque x, on va tracer les pixels du triangle associés à cet x, autrement dit on va tracer des segments verticaux allant de la base à l'un des côtés. (Surtout, faire un dessin pour suivre mon raisonnement !)
Tout d'abord, on a besoin d'écrire les équations de (AB), (AC) et (BC). Équations cartésiennes au cas où l'un des côtés serait verticaux. Ce calcul doit être fait une fois pour toutes au début. (En fait, on calcule les coefficients, et on doit les stocker. Je propose qu'on normalise les équations cartésiennes en choisissant y = 1, ça fera gagner une division plus loin.)
Par hypothèse, xC est compris entre xA et xB. Aussi la boucle principale (parcours des x) aura deux parties :
1) x varie de xA à xC. On doit tracer les segments verticaux allant de [AB] à [AC]. Pour chaque x, on calcule le y du point de [AB] et le y du point de [AC] en utilisant les équations de ces droites (rappel : si ax + y + c = 0, alors y = -ax - c).
2) x varie de xC à xB. On doit tracer les segments verticaux allant de [AB] à [CB]. Pour chaque x, on calcule le y du point de [AB] et le y du point de [CB] en utilisant les équations de ces droites.
Si le point C était en haut (yC plus petit), il faudrait aller du y du point de [AC] au y du point de [AB] (ou bien faire comme plus haut mais en décrémentant y).
J'avais vu une vidéo de Bisqwit récemment sur le sujet, si tu n'es pas allergique à l'anglais, elle est assez bien faite ! Et c'est pile ce que tu demandes.
(lui il implémente en C++ très récent, mais comme il explique tout bien étape par étape, tu auras tout l'algo)
EDIT :
Et puis en effet sur mon site, j'ai quelques fonctions pour tracer des lignes en biais avec Bresenham. Il "suffira" de les tracer progressivement puis de relier les bords avec des segments horizontaux (simple for)
Tu peux avoir un algorithme naïf et peu efficace :
Avant de tracer un triangle plein il faut savoir tracer une ligne.
Pour tracer une ligne de (X1,Y1) à (X2,Y2) , tu calcules le coef directeur (X2-X1)/(Y1-Y2), et tu calcules les coordonnées de chaque point de ta ligne(Xa,Ya).
Maintenant pour ton triangle reliant les point A,B et C il suffit de calculer les points du segment [AB] et ceux tu segment [AC] (ou [BC]). Et tu traces une ligne entre chacun des points.
Il y a bien sur pas mal d'optimisations à faire et de cas particuliers.
J'ai opté pour ta méthode @robun. En effet, j'ai survolé la vidéo de @Fvirtman, ça a l'aire d'ètre le même principe en reliant des bords.
J'obtiens avec des triangles de 10 000 pxl, 2500 triangles par seconde ce qui est pas énorme mais peu suffire (sachant que les triangles très nombreux seront très petits).
Par contre, @raoullevert c'est en effet pas très éfficace(je pense que tu dois multiplier le nombre d'opérations en trop proportionnellement à la dimension de ton triangle), et je n'ai pas vu d'optimisation.
voilà mon code pour ceux que ca intéresserait ou si quelqu'un peu peut-être l'optimiser:
void _drawFillTrianglePXL(SDL_Renderer* renderer, int x1, int y1, int x2, int y2, int x3, int y3) {
int A[2];
int B[2];
int C[2];
if (x1>x2) { //mise au bonne endroit des points
if (x2>x3) {
A[0]=x1;A[1]=y1; B[0]=x3;B[1]=y3; C[0]=x2;C[1]=y2;
}
else {
if (x1>x3) {
A[0]=x1;A[1]=y1; B[0]=x2;B[1]=y2; C[0]=x3;C[1]=y3;
}
else {
A[0]=x3;A[1]=y3; B[0]=x2;B[1]=y2; C[0]=x1;C[1]=y1;
}
}
}
else {
if(x1>x3) {
A[0]=x2;A[1]=y2; B[0]=x3;B[1]=y3; C[0]=x1;C[1]=y1;
}
else {
if (x2<x3) {
A[0]=x3;A[1]=y3; B[0]=x1;B[1]=y1; C[0]=x2;C[1]=y2;
}
else {
A[0]=x2;A[1]=y2; B[0]=x1;B[1]=y1; C[0]=x3;C[1]=y3;
}
}
}
//equation (AB)
float AB_a = A[1]-B[1]; //-x2
float AB_b = B[0]-A[0]; //x1
float AB_c = -(AB_a*A[0]+AB_b*A[1]); //c=-(a*xA+b*yA)
AB_a /=AB_b; AB_c/=AB_b; //normalisation pour y
//equation (AC)
float AC_a = A[1]-C[1]; //-x2
float AC_b = C[0]-A[0]; //x1
float AC_c = -(AC_a*A[0]+AC_b*A[1]); //c=-(a*xA+b*yA)
AC_a /=AC_b; AC_c/=AC_b; //normalisation pour y
//equation (BC)
float BC_a = B[1]-C[1]; //-x2
float BC_b = C[0]-B[0]; //x1
float BC_c = -(BC_a*B[0]+BC_b*B[1]); //c=-(a*xB+b*yB)
BC_a /=BC_b; BC_c/=BC_b; //normalisation pour y
for (int x = B[0]; x < C[0]; ++x) //partie [BA [BC]
{
SDL_RenderDrawLine(renderer,x,-(AB_a*x+AB_c),x,-(BC_a*x+BC_c));
}
for (int x = C[0]; x < A[0]; ++x) //parite BA] [AC]
{
SDL_RenderDrawLine(renderer,x,-(AB_a*x+AB_c),x,-(AC_a*x+AC_c));
}
}
voilà ma petite avancée:
il ne me manque plus que le clipping et quelques trucs.
Après je passerais peut-être au ray-tracing
En tout cas merci beaucoup!
- Edité par Aymeric Nguyen 27 avril 2020 à 20:32:30
@robun alors je n'ai pas eu besoin de les séparer parce qu'en utilisant la fonction SDL_RenderDrawLine on a pas besoin de savoir quel point est le plus haut (on relie juste les points). Cependant j'avais penser à prendre le signe de la norme du produit vectoriel entre BA et BC et on peut ainsi connaître dans quel cas on se trouve.
> on a pas besoin de savoir quel point est le plus haut (on relie juste les points)
Ah oui, tout simplement !
Algorithme de dessin d'un triangle plein
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html