Discussion :

[megs]

DELPHI7 PRO
Bonjour a tous, Je remarque que il n'y a pas de pti coin pour l'interprétation algorithmique, dommage, du coup je ne sais pas trops ou poster mon truc.


Je tente d'interpréter un algorithme de remplissage de face triangulaire avec tri des point sur Y. J'utilise le précalc bresenham pour chaque segment, avant de démarrer le traçage.

Mon interprêtation de l'agorithme de bresenham légèrement détourné m'impose des defauts lors de l'affichage de ma surface. les contours sont parfois inexactes, et des bords parfois inexistants (pas tout le temps). Je présume une erreur dans l'organisation de ma procédure d'affichage (voir a partir de "PATCH MERDIQUE").

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
  self.SetLine(x1,y1,x3,y3,cl);  // PATCH merdique    OO
  self.SetLine(x2,y2,x3,y3,cl);  // PATCH merdique   OOOOOOOOOOOOOOOO  PATCH MERDIQUE
  self.SetLine(x1,y1,x2,y2,cl);  // PATCH merdique    OO
//////////////////////////////////////////////////////////////////////// <>
// BOUCLE <>
  for i := 1 to ABnumpixels do  //affiche les points de la ligne
  begin                     //une fois tous les calculs termin‚es
 
  if (ABy <= y3) then  begin // si ABy <= Cy
  // Tronçon AC -------------------------------------
 
    While (ACd <= 0)and(Aby > Acy)  do
      Begin
        ACd := ACd + ACdinc1;
        ACx := ACx + ACxinc1;
        ACy := ACy + ACyinc1;
      end;
    While (ACd > 0)and(Aby > Acy) do
      begin
        ACd := ACd + ACdinc2;
        ACx := ACx + ACxinc2;
        ACy := ACy + ACyinc2;
      end;
     self.SetLine(ABx,ABy,ACx,ACy,cl);
  end else begin
  // Tronçon CB -------------------------------------
 
    While (CBd <= 0) and (Aby > CBy) do
      begin
        CBd := CBd + CBdinc1;
        CBx := CBx + CBxinc1;
        CBy := CBy + CByinc1;
      end;
    While (CBd > 0) and (Aby > CBy) do
      begin
        CBd := CBd + CBdinc2;
        CBx := CBx + CBxinc2;
        CBy := CBy + CByinc2;
      end;
    self.SetLine(ABx,ABy,CBx,CBy,cl);
   end;
   // PARCOURS AB  -------------------------------------
  if ABd < 0 then
     begin
      ABd := ABd + ABdinc1;
      ABx := ABx + ABxinc1;
      ABy := ABy + AByinc1;
     end else begin
      ABd := ABd + ABdinc2;
      ABx := ABx + ABxinc2;
      ABy := ABy + AByinc2;
     end;

je ne dois pas avoir les idées suffisamment détaché du problème pour trouver le hic. Pourriez vous me dire ou je fait une boulette ?

[Paul TOTH]

je n'ai pas bien compris la question mais ça me rappelle un algo que j'avais utilisé sous Turbo Pascal pour remplir un triangle avec bresenham, est-ce de cela dont il est question ?

l'idée était de calculer via Bresenham les segments A-B et A-C pour remplir les lignes horizontales qui forment le triangle puis continuer, selon le cas, sur la fin de A-B et C-B - ou - la fin de A-C et B-C.

[megs]

Oui c'est cela même, j'utilise l'algo de bresenham. pour parcourir le segment le plus grand sur Y, et en parcourant les deux autres segments oposées tour à tour.

(je souhaite tout traduire en ASM apres avec un remplissage avec Rep stod donc obligé de faire comme ca).

Avec le résultat à l'ecran, avec affichage des points, et écriture des lignes de contour en blanc pour visualiser les imperfections. On remarque que le segment AC est presque toujours ignoré (reste blanc) sauf le premier pixel, et je ne pige pas pourquoi...

si j'y arrive voir ecran en piece jointe

[Paul TOTH]

euh...ce que je ne comprend pas dans ton code c'est que semble tracer des segments via Bresenham entre deux points des côtés

ton algorithme devrait tracer des lignes horizontales seulement

exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
   1
  22
 3333
444444
  55555
    6666
     7777
       888
         9

(dessin approximatif)

pour obtenir cela, tu alimentes deux tableaux xMin[ymin..ymax] et xMax[ymin..ymax] en parcourant les 3 segments par bresenham.

Ensuite il ne reste plus qu'à dessiner les lignes de xMin[y] à xMax[y].

[Caribensila]

Typiquement, l'algo de Bresenham ne dessine pas le dernier pixel du segment (pour permettre d'implémenter le polyline, je pense).

Il me semble bien que le défaut que tu constates vienne de là...

[Paul TOTH]

Typiquement, l'algo de Bresenham ne dessine pas le dernier pixel du segment (pour permettre d'implémenter le polyline, je pense).

Il me semble bien que le défaut que tu constates vienne de là...

euh...ça ne me dit rien ça...et de toute façon en parcourant les 3 segments comme je l'indique tu ne peux pas avoir tout un segment ignoré, au pire les trois sommets du triangle, mais j'en doute

[megs]

euh...ce que je ne comprend pas dans ton code c'est que semble tracer des segments via Bresenham entre deux points des côtés, ton algorithme devrait tracer des lignes horizontales seulement

Hé bien en fait, c'est pour éviter de travailler avec un tableau en assembleur ensuite que je fait ca. C'est vrais que c'est plus simple, mais en terme de performance on à une étape de plus en travaillant avec un tableau.

Ce que je fais pour ça est aussi très simple, plutôt que de calculer , puis stocker , destocker la valeur,puis tracer. En fait je calcul et je trace à chaud uniquement quand dans le parcours des segments les valeurs ABy=(ACy) puis ensuite (ABy=(CBy) quand ABy >= Cy).
donc en fait je travail avec les valeurs directement incrémentés par l'algo, et si elles sont fausse là, elle seront stocké fausse aussi dans le tableau... J'ai donc une bourde ailleurs (enfin je pense ).

Typiquement, l'algo de Bresenham ne dessine pas le dernier pixel du segment
J'avais remarqué ça pour les cercles et sont algo de bresenham, mais pas pour la ligne, en fait mon setline n'a pas de defaut et utilise le même algorithme sans pixel de plus à patcher, pourtant c'est cette fonction qui me montre les défauts du remplissage. donc j'ai vraiment dû raté quelque chose.

voici le précacl...qui viens avant l'implémentation du traçage:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
Procedure TGView.SetTrianglePlein(x1,y1,x2,y2,x3,y3,c:longint);
//-----------------------------------------------------------------------  <>
var
    i,cpos,dum: longint;
    // ligne AB
    ABdeltax, ABdeltay, ABnumpixels,
    ABd, ABdinc1, ABdinc2,
    ABx, ABxinc1, ABxinc2,
    ABy, AByinc1, AByinc2,
    // ligne AC
    ACdeltax, ACdeltay, ACnumpixels,
    ACd, ACdinc1, ACdinc2,
    ACx, ACxinc1, ACxinc2,
    ACy, ACyinc1, ACyinc2,
    // Ligne CB
    CBdeltax, CBdeltay, CBnumpixels,
    CBd, CBdinc1, CBdinc2,
    CBx, CBxinc1, CBxinc2,
    CBy, CByinc1, CByinc2 : integer;
    //
    p:pointer;
    W,H:longword;
 
begin
  W:=self.p_Buffer.Width; H:=self.p_Buffer.Height;
  p:=self.p_PTRBuffer;
  // TROUVER L'ORDRE DES POINTS PAR Y CROISSANT
  //////////////////////////////////////////////////////////////
  if (y1>y2) then begin         // 1 est tout le temps A
              dum:=y2; Y2:=Y1; Y1:=dum;
              dum:=x2; x2:=x1; x1:=dum;
              end;
  if (y1>y3) then begin          // 2 est tout le temps B
              dum:=y3; Y3:=Y1; Y1:=dum;
              dum:=x3; x3:=x1; x1:=dum;
              end;
  if (y2<y3) then begin          // 3 est tout le temp C
              dum:=y3; Y3:=Y2; Y2:=dum;
              dum:=x3; x3:=x2; x2:=dum;
              end;
  //debug
  Self.SetText(x1,self.p_Buffer.Height-Y1,$00FFFFFF,'A:'+IntToStr(x1)+','+IntToStr(y1));
  Self.SetText(x2,self.p_Buffer.Height-y2,$00FFFFFF,'B:'+IntToStr(x2)+','+IntToStr(y2));
  Self.SetText(x3,self.p_Buffer.Height-y3,$00FFFFFF,'C:'+IntToStr(x3)+','+IntToStr(y3));
 
  ABdeltax := abs(x2 - x1);
  ABdeltay := abs(y2 - y1);
  if ABdeltax >= ABdeltay then
    begin
      ABnumpixels := ABdeltax + 1;
      ABd := (ABdeltay SHl 1) - ABdeltax;
      ABdinc1 := ABdeltay Shl 1;
      ABdinc2 := (ABdeltay - ABdeltax) shl 1;
      ABxinc1 := 1;
      ABxinc2 := 1;
      AByinc1 := 0;
      AByinc2 := 1;
    end
  else
    begin
      ABnumpixels := ABdeltay + 1;
      ABd := (ABdeltax Shl 1) - ABdeltay;
      ABdinc1 := ABdeltax Shl 1;
      ABdinc2 := (ABdeltax - ABdeltay) shl 1;
      ABxinc1 := 0;
      ABxinc2 := 1;
      AByinc1 := 1;
      AByinc2 := 1;
    end;
  if x1 > x2 then
    begin
      ABxinc1 := - ABxinc1;
      ABxinc2 := - ABxinc2;
    end;
  if y1 > y2 then
    begin
      AByinc1 := - AByinc1;
      AByinc2 := - AByinc2;
    end;
  ABx := x1;
  ABy := y1;
 ///////////////////////////////////////////////////////////
 // PRECALC  AC
  ACdeltax := abs(x3 - x1);
  ACdeltay := abs(y3 - y1);
  if ACdeltax >= ACdeltay then
    begin
      ACnumpixels := ACdeltax + 1;
      ACd := (ACdeltay SHl 1) - ACdeltax;
      ACdinc1 := ACdeltay Shl 1;
      ACdinc2 := (ACdeltay - ACdeltax) shl 1;
      ACxinc1 := 1;
      ACxinc2 := 1;
      ACyinc1 := 0;
      ACyinc2 := 1;
    end
  else
    begin
      ACnumpixels := ACdeltay + 1;
      ACd := (ACdeltax Shl 1) - ACdeltay;
      ACdinc1 := ACdeltax Shl 1;
      ACdinc2 := (ACdeltax - ACdeltay) shl 1;
      ACxinc1 := 0;
      ACxinc2 := 1;
      ACyinc1 := 1;
      ACyinc2 := 1;
    end;
  if x1 > x3 then
    begin
      ACxinc1 := - ACxinc1;
      ACxinc2 := - ACxinc2;
    end;
  if y1 > y3 then
    begin
      ACyinc1 := - ACyinc1;
      ACyinc2 := - ACyinc2;
    end;
  ACx := x1;
  ACy := y1;
///////////////////////////////////////////////////////////
// PRECALC  CB
  CBdeltax := abs(x3 - x2);
  CBdeltay := abs(y3 - y2);
  if CBdeltax >= CBdeltay then
    begin
      CBnumpixels := CBdeltax + 1;
      CBd := (CBdeltay SHl 1) - CBdeltax;
      CBdinc1 := CBdeltay Shl 1;
      CBdinc2 := (CBdeltay - CBdeltax) shl 1;
      CBxinc1 := 1;
      CBxinc2 := 1;
      CByinc1 := 0;
      CByinc2 := 1;
    end
  else
    begin
      CBnumpixels := CBdeltay + 1;
      CBd := (CBdeltax Shl 1) - CBdeltay;
      CBdinc1 := CBdeltax Shl 1;
      CBdinc2 := (CBdeltax - CBdeltay) shl 1;
      CBxinc1 := 0;
      CBxinc2 := 1;
      CByinc1 := 1;
      CByinc2 := 1;
    end;
  if x3 > x2 then
    begin
      CBxinc1 := - CBxinc1;
      CBxinc2 := - CBxinc2;
    end;
  if y3 > y2 then
    begin
      CByinc1 := - CByinc1;
      CByinc2 := - CByinc2;
    end;
  CBx := x3;
  CBy := y3;

voilà.. si vous voyez ou est l'erreur avant moi, ou comment faire pour y remedier... ca m'interresse.

[Paul TOTH]

pour tester ton code il faut un bout de code qu'on puisse executer...c'est plus facile en mode debug qu'à lire comme ça.

j'ai retrouvé le code que j'avais utilisé, c'est dans ZED

ça allait même plus loin puisque mon algo dessine un triangle en 3D avec effet Gouraud avec Brenshenam sur X, Y, Z et la Couleur en même temps

mais si j'utilisais des tableaux c'est en fait que je pouvais dessiner des polygones (convexes) et pas seulement des triangles, l'algorithme reste exactement le même quelque soit le nombre de segments.

Le principe est similaire à MoveTo(x,y), LineTo(x,y) avec ScanX et ScanY qui gardent la dernière position

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
// init des tableaux et du point de départ (ScanX, ScanY, ScanZ)
   InitZPoly(Coords^[a].x,Coords^[a].y,Coords^[a].z);
// parcours des différents segments
   ScanZPoly(Coords^[b].x,Coords^[b].y,Coords^[b].z);
   ScanZPoly(Coords^[c].x,Coords^[c].y,Coords^[c].z);
   ScanZPoly(Coords^[a].x,Coords^[a].y,Coords^[a].z);
// rendu du tableau
   DrawZPoly(shade(TempNorm2^[i]));

voici le "lineto" en version non gouraud, non 3D

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
Procedure ScanPoly(x,y:integer);
 var
  dx,dy,dz:integer;
  ix,iy,iz:integer;
  ex,ey,ez:integer;
  ee,ii:integer;
  ValidX,ValidY,Valid:boolean;
 begin
  dx:=x-ScanX; if dx<0 then begin dx:=-dx; ix:=-1 end else ix:=1;
  dy:=y-ScanY; if dy<0 then begin dy:=-dy; iy:=-1 end else iy:=1;
 
  ValidY:=(ScanY>=0)and(ScanY<200);
  ValidX:=(ScanX>=0)and(ScanX<320);
  Valid :=ValidX and ValidY;
 
  if dx>dy then begin
 
   ee:=dy;
   for ii:=0 to dx do begin
    if Valid then begin
     if ScanX<ScanMin[ScanY] then ScanMin[ScanY]:=ScanX;
     if ScanX>ScanMax[ScanY] then ScanMax[ScanY]:=ScanX;
    end;
    inc(ee,dy);
    if ee>dx then begin
     dec(ee,dx);
     inc(ScanY,iy);
     ValidY:=(ScanY>=0)and(ScanY<200);
    end;
    inc(ScanX,ix);
    ValidX:=(ScanX>=0)and(ScanX<320);
    Valid :=ValidX and ValidY;
   end;
 
  end else begin
 
   ee:=dx;
   for ii:=0 to dy do begin
    if Valid then begin
     if ScanX<ScanMin[ScanY] then ScanMin[ScanY]:=ScanX;
     if ScanX>ScanMax[ScanY] then ScanMax[ScanY]:=ScanX;
    end;
    inc(ee,dx);
    if ee>dy then begin
     dec(ee,dy);
     inc(ScanX,ix);
     ValidX:=(ScanX>=0)and(ScanX<320);
    end;
    inc(ScanY,iy);
    ValidY:=(ScanY>=0)and(ScanY<200);
    Valid :=ValidX and ValidY;
   end;
 
  end;
 
 end;

et le rendu (en mode VGA 320x200x256 couleurs )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
Procedure DrawPoly(c:integer);
 var
  x,y:integer;
  x1,x2:integer;
 begin
  For y:=ScanTop to ScanBottom do begin
   x1:=ScanMin[y];
   x2:=ScanMax[y];
   if x1<=x2 then
    for x:=x1 to x2 do begin
     Port[$3c4]:=2;
     Port[$3c5]:=1 shl (x and 3);
     mem[SegA000:page+80*y+x shr 2]:=c;
    end;
  end;
 end;

les tableaux sont dimensionnés pour un écran 320x200

et pour répondre à ta remarque sur l'assembleur, un lookup dans un tableau n'est pas forcément pénalisant

Note qu'il est aussi possible d'éviter la différence dx/dy comme je le fais dans la version 3D (au lieu de gérer tous les cas différents)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
...
  ex:=dx;
  ey:=dy;
  ez:=dz;
 
  ee:=max(ex,max(ey,ez));
 
  for ii:=0 to ee do 
  begin
  ...
   if ex>ee then begin
    dec(ex,ee);
    inc(ScanX,ix);
   end;
   inc(ex,dx);
 
   if ey>ee then begin
    dec(ey,ee);
    inc(ScanY,iy);
   end;
   inc(ey,dy);
 
   if ez>ee then begin
    dec(ez,ee);
    inc(ScanZ,iz);
   end;
   inc(ez,dz);
  end;