1

Peut être que le sujet a plus ou moins déjà été abordé mais là j'ai besoin d'une solution extrêmement "performante", c.a.d. optimisée en rapidité.

Soit un triangle avec x1,y1,x2,y2,x3,y3.

L'image est de type "bitmap 16 couleurs", chaque octet contient deux points (sur l'axe Y) de l'image.

Quelle solution est la plus rapide pour dessiner un triangle avec une couleur N (avec N de 0 à F en hexa) ?
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

2

C'est pour la Lynx je suppose ?

Je dirais la rasterization classique, à savoir dessiner des segments horizontaux superposés. Pour chaque ligne tu calcules l'abscisse du début et de la fin du segment avec un algo en virgule fixe rapide, et tu le traces.

!call Orion_
--- Call : Orion_ appelé(e) sur ce topic ...

!call SebRmv
--- Call : SebRmv appelé(e) sur ce topic ...

(ils ont écrit ce genre d'algo sur Jaguar)
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

3

(cross)

_il faudra commencer par faire un setPixel(x,y,c)

des points de départ:

http://www.developpez.net/forums/d336516/applications/developpement-2d-3d-jeux/algorithme-remplissage-triangle/

http://www.cppfrance.com/forum/sujet-TRIANGLE-PLEIN_1158482.aspx -> message de acx01b

http://rzr.online.fr/docs/net3d/tech3d.htm
Remplissage de Triangles
L'algorithme optimal et de décomposer un triangle en deux triangles : suppérieur et inférieur et de balayer ligne par ligne (calculer les coefficients directeurs des droites limites)

sinon

!_call iwannabear
--- Call : iwannabear appelé(e) sur ce topic ...

4

squalyl (./3) :
il faudra commencer par faire un setPixel(x,y,c)
Non surtout pas, c'est beaucoup trop lent. Il ne faut pas décomposer en pixels, mais au contraire remplir le maximum de pixels en une seule opération.

(et le dernier lien, ça détaille ce que je disais ^^)
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

5

Edited_3676

6

Je crois que l'algo de Genlib est très performant, peut-être ça pourrait t'inspirer. Si ça te fait suer de lire du 68k, je veux bien essayer de te transcrire l'algo en c-like.
A moins que les fonctions fournies par ton matériel diffère trop d'un 68k pour être efficace.

7

!call black book
--- Call : black book n'existe pas !

8

9

De mémoire, ExtGraph a également un découpage entre triangle supérieur et triangle inférieur.
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

10

Je me demande quelle bibliothèque est la plus rapide. Il faudrait en débattre, à l'occasion.

11

Hmm... c'est sérieux ? Le terme "débattre" me ferait plutôt penser à un gros débat Genlib / ExtGraph (GraphX / XLib / etc.) comme au bon vieux temps grin
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

12

(tu mets les pieds dans le troll de Pen^2 qui n'attend que le troll grin)

13

Je sais pas si Vince appréciera un troll dans un topic sérieux.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

14

(#triange#) (tiens, on dirait des vortex cheeky)

15

J'ai détecté le troll, et je n'avais pas l'intention de troller grin
avatar
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.

16

Pen^2 (./8) :
http://www.gamedev.net/page/resources/_/reference/programming/140/283/graphics-programming-black-book-r1698

Han, c'est nul, il n'y a aps un seul PDF qui contient tout sad

(bon en meme temps j'ai l'original, c'est carrement mieux ^^)

Edit:

J'ai ressortit d'un carton ce que j'avais fait il y a 2ans, c'est surement pas optimal, et je n'ai pas mis la fonction pixmal_Fill, elle est dépendante du framebuffer, mais c'est une fonciton optimisé pour dessiner un rectangle plein sur un framebuffer, mais c'est dépendant du FB, donc aucun interet a etre mis ici.

You are free to comment wink
/* * This source code is licenced under the gPL v1 (godzil Public Licence version 1) * You must conform with it for using the corresponding source code */ typedef struct point_t { uint32_t x, y; } point_t; typedef struct fpoint_t { float x, y; } fpoint_t; int drawHLine (int contextId, int32_t x1, int32_t x2, int32_t y, int32_t color) { int result = 0; context_t *context = (context_t *) contextId; int32_t xs, xe, w; #ifdef DEBUG printf("%s(%d, %d, %d, %d, %d)\n", __func__, contextId, x1, x2, y, color); #endif if (x1 < x2) { xs = x1; xe = x2; } else { xs = x2; xe = x1; } /* this is madnessssss !!!! */ result = pixmap_Fill(context->pixmapId, xs, y, xe-xs, 1, color); #ifdef DEBUG printf("%s return %d\n", __func__, result); #endif return result; } #define SetPoint(pt1,pt2) pt1.x=pt2.x; pt1.y=pt2.y int drawFillTri (int contextId, point_t p1, point_t p2, point_t p3, uint32_t color) { int result = 0; context_t *context = (context_t *) contextId; fpoint_t A, B, C, S, E; float dx1, dx2, dx3; #ifdef DEBUG printf("%s(context:%d, p1:{%d, %d}, p2:{%d, %d}, p3:{%d, %d}, color: %d)\n", __func__, contextId, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, color); #endif /* put ABC in the good order (A.y<=B.y<=C.y) */ if ((p1.y <= p2.y) && (p2.y <= p3.y)) { /* 1 2 3 */ SetPoint(A,p1); SetPoint(B,p2); SetPoint(C,p3); } else if ((p1.y <= p3.y) && (p3.y <= p2.y)) { /* 1 3 2 */ SetPoint(A,p1); SetPoint(B,p3); SetPoint(C,p2); } else if ((p2.y <= p1.y) && (p1.y <= p3.y)) { /* 2 1 3 */ SetPoint(A,p2); SetPoint(B,p1); SetPoint(C,p3); } else if ((p2.y <= p3.y) && (p3.y <= p1.y)) { /* 2 3 1 */ SetPoint(A,p2); SetPoint(B,p3); SetPoint(C,p1); } else if ((p3.y <= p1.y) && (p1.y <= p2.y)) { /* 3 1 2 */ SetPoint(A,p3); SetPoint(B,p1); SetPoint(C,p2); } else/*if ((p3.y <= p2.y) && (p2.y <= p1.y))*/ { /* 3 2 1 */ SetPoint(A,p3); SetPoint(B,p2); SetPoint(C,p1); } #ifdef DEBUG if ((A.y > B.y) || (B.y > C.y) || (A.y > C.y)) { printf("ERROR WHILE ORDERING ITEMS...\n"); goto exit; } #endif if ((B.y-A.y) > 0) { dx1=(B.x-A.x)/(B.y-A.y); } else { dx1=0.0 }; if ((C.y-A.y) > 0) { dx2=(C.x-A.x)/(C.y-A.y); } else { dx2=0.0 }; if ((C.y-B.y) > 0) { dx3=(C.x-B.x)/(C.y-B.y); } else { dx3=0.0 }; #ifdef DEBUG printf("dx1:%f dx2:%f dx3:%f\n", dx1, dx2, dx3); #endif S.x=E.x=A.x; S.y=E.y=A.y; /* Starting ugly code... */ if(dx1 > dx2) { #ifdef DEBUG printf("dx1/dx2 >"); #endif for(; S.y <= B.y ; S.y++, E.y++, S.x += dx2, E.x += dx1) { drawHLine(contextId, S.x ,E.x, S.y, color); } SetPoint(E, B); #ifdef DEBUG printf("dx2/dx3 >"); #endif for(; S.y <= C.y ; S.y++, E.y++, S.x += dx2, E.x += dx3) { drawHLine(contextId, S.x, E.x, S.y, color); } } else { #ifdef DEBUG printf("dx1/dx2 <"); #endif for(; S.y <= B.y ; S.y++, E.y++, S.x += dx1, E.x += dx2) { drawHLine(contextId, S.x, E.x, S.y, color); } SetPoint(S, B); E.x-=dx2; #ifdef DEBUG printf("dx2/dx3 <"); #endif for(; S.y <= C.y ; S.y++, E.y++, S.x += dx3, E.x += dx2) { drawHLine(contextId, S.x, E.x, S.y, color); } } exit: #ifdef DEBUG printf("%s return %d", __func__, result); #endif return result; }
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

17

Godzil (./16) :
This source code is licenced under the gPL v1 (godzil Public Licence version 1)
grin
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

18

hehe

Juste un détail sur le pourquoi de "pixmap_Fill", le contexte sur lequel je bossait, la base de dessin était une lib "pixmap" ou les seuls primitives accesibles sont :


Copy d'un pixmap vers un autre (un blit quoi)
Fill d'une zone rectangulaire
Jouer avec les CLUT (pour les FB compatibles)
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

19

Lionel Debroux (./15) :
J'ai détecté le troll, et je n'avais pas l'intention de troller grin

Awwwwwwwww sad

Godzil (./16) :
Han, c'est nul, il n'y a aps un seul PDF qui contient tout frown.gif
(bon en meme temps j'ai l'original, c'est carrement mieux ^^)
Bah c'est aussi l'original, c'est un PDF officiel pour autant que je sache tongue

20

Bon par contre, pour le cas de Vince, il faudra dégager les floats et réécrire ça en virgule fixe.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

21

Pen^2 (./19) :
(bon en meme temps j'ai l'original, c'est carrement mieux ^^)
Bah c'est aussi l'original, c'est un PDF officiel pour autant que je sache tongue
[/cite]
Je parle du livre papier banana

Zero: bien sur ^^ Ce n'est qu'un exemple d'implémentation smile
avatar
Proud to be CAKE©®™


GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.

22

Pour trier 3 valeurs plus vite : (

// tri à bulle
point_t * tmp, n1 = &p1 ,n2 = &p2, n3 = &p3; // permet de ne pas copier les structures entières
if (p1.y > p2.y){                            // on n'est pas obligés d'utiliser les pointeurs la première fois
   tmp = n2; n2 = n1; n1 = tmp;
}
if (n2->y > n3->y){
    tmp = n3; n3 = n2; n2 = tmp;
}
if (n1->y > n2->y){
   tmp = n2; n2 = n1; n1 = tmp;
}
SetPoint(A,*n1);
SetPoint(B,*n2);
SetPoint(C,*n3);

23

./21 oué mais le PDF est gratuit comme un ours embarrassed

24

Je viens après la bataille mais ouais!
Une petite fonction hfill pour tracer une ligne horizontale.
Et on calcule les extrêmités des côtés en interpolant. Il doit même y avoir du code source ASM pour Jag sur mon site smile
(je m'étais fait chier à faire plus que les triangles, mais au final, c'est une mauvaise idée...
c'est d'ailleurs sur ma TODO list de récrire les algo de remplissage juste pour les triangles)

Dans les How To Code (diskmag Atari), il doit même y avoir la solution pour le problème de Vince (mode plan, 4 bits... j'imagine que dans ce cas, il faut faire un peu de code généré pour les fonctions hfill)

25

vince> t'es sur quelle archi? t'as acces a des instructions SIMD? cherche "halfspace rasterization", ca sera probablement plus rapide sur une archi moderne qu'un simple algo scanline. sinon, ca peut quand meme valoir le coup point de vue perfs, meme sur un vieux truc.
et ta couleur, elle est constante sur l'ensemble du triangle? ou il faut l'interpoler? pas de texture?
avatar
HURRRR !