Remplir un triangle pixel par pixel

Quels pixels sont dans un triangle ?

Remplir un triangle, c’est décider pour chaque pixel s’il est dedans ou dehors. Toute forme d’un jeu en 3D est découpée en triangles, et la carte graphique répond à cette question des millions de fois par seconde.

Ici, c’est votre programme qui répond, pixel après pixel, avec un test très simple.

À la fin de cette leçon

Remarque

Je peux dire si un pixel est dans un triangle avec trois tests d’arête.

Mots clés

Mot	Ce que ça veut dire
Triangle	une forme à trois sommets et trois arêtes
Arête	un côté du triangle, d’un sommet à l’autre
Test d’arête	un nombre dont le signe dit de quel côté on est
Poids barycentriques	trois nombres qui situent un point dans le triangle
Balayage	le parcours de tous les pixels, ligne après ligne

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

On balaie tous les pixels de la grille

Le plus simple pour remplir un triangle est de parcourir chaque ligne y, puis chaque colonne x. Pour chaque pixel, on pose une seule question : est-il dans le triangle ?

La réponse vient d’un test sur chacune des trois arêtes. On gagne du temps en ne balayant que le petit rectangle qui entoure le triangle.

Le signe dit de quel côté on est

Pour une arête qui va de p à q, on calcule : (qx − px) × (y − py) − (qy − py) × (x − px). Le résultat est positif d’un côté de l’arête, négatif de l’autre et nul sur l’arête elle-même.

Un pixel est dans le triangle quand les trois arêtes lui donnent le même signe.

Calculer le côté d’un point

Code: python

# Le côté d'un point par rapport à l'arête de (0, 0) à (8, 0).
def cote(p, q, x, y):
    return (q[0] - p[0]) * (y - p[1]) - (q[1] - p[1]) * (x - p[0])

for y in (-2, 0, 2):
    print("y =", y, "valeur", cote([0, 0], [8, 0], 3, y))
# Quel signe a la valeur de chaque côté de l'arête ?

Exemple travaillé : un triangle, ligne par ligne

Ligne y	Pixels dedans	Colonnes
1	1	1
2	8	2 à 9
3	6	2 à 7
4	5	2 à 6
5	3	3 à 5
6	2	3 et 4
7	1	3

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

Compter les pixels du triangle

Commande

docker exec jupyter python3 -c "a,b,c=(1,1),(9,2),(3,7); e=lambda p,q,x,y:(q[0]-p[0])*(y-p[1])-(q[1]-p[1])*(x-p[0]); print(e(a,b,c[0],c[1]), sum(1 for y in range(9) for x in range(11) if e(a,b,x,y)>=0 and e(b,c,x,y)>=0 and e(c,a,x,y)>=0))"

Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.

Lire le nombre de pixels

La commande affiche 46 26. Le premier nombre est le test d’arête appliqué au troisième sommet. Il est positif : ici, dedans veut dire trois valeurs positives ou nulles. C’est aussi le double de l’aire.

Le second nombre, 26, est la somme de la colonne du tableau : 1, 8, 6, 5, 3, 2 et 1 pixels.

Une erreur fréquente

Attention

Beaucoup pensent que dedans veut toujours dire trois valeurs positives. Ce n’est pas juste : si on nomme les sommets dans l’autre sens, tout change de signe. Comparez donc avec le signe de l’aire, ou acceptez trois valeurs négatives.

Dessiner le triangle en texte