# Board index » delphi » Polygon filling

## Polygon filling

I am searching for a method to filling polygones (like in BGI)?
It should be possibly FAST, but i will thank you for everything
you send me...

## Re:Polygon filling

##### Quote
>Subject: Polygon filling
>From: Udo Giacomozzi <giaud...@schule.provinz.bt.it>
>Date: Sat, 06 Sep 1997 14:55:17 -0700
>Message-id: <3411D145....@schule.provinz.bt.it>

>I am searching for a method to filling polygones (like in BGI)?
>It should be possibly FAST, but i will thank you for everything
>you send me...

Did you try the FillPoly procedure in TP's Graph unit?  Or are you trying
to do this without the Graph unit?

## Re:Polygon filling

##### Quote
>>I am searching for a method to filling polygones (like in BGI)?
>>It should be possibly FAST, but i will thank you for everything
>>you send me...

>Did you try the FillPoly procedure in TP's Graph unit?  Or are you trying
>to do this without the Graph unit?

He said fast :) hehe..

Anyway, here is how you fill a poly (in theory.. if you have problems with
implementing it just ask, and I'll send you a rutine)

First of all, the smartest thing is to build everything from triangle polys,
that way you dont have to mess with N-sided ones, and polys that have irregular
sides.

We will use these var's : Point1.X,Point1.Y,Point2.X,Point2.Y,Point3.X,Point3.Y;

These are our three points on-screen, and the area we want the polygon to cover.
The first thing to do is to find the highest and lowest Y Value.

Lets say that Point1.Y is highest and Point3.Y is lowest. What you do next is to
have two arrays of integers that cover the entire screen in Y axis
(array[1..199] in mode 13h) .. Now.. Draw a line from P1.Y to P3.Y, but instead
of plotting the pixel, put the X value in the correct Y slot in the first array.

Now do the same between P1.Y - P2.Y and P2.Y - P3.Y but this time you put the
values into the other array..

Now you have the lines that make up the poly defined, all you have to do is to
fill it. Do it like this:

For Counter:=Lowest_Y to Highest_Y do
Begin
Draw_Horisontal_Line(PolyArray1[Counter],PolyArray2[Counter],Counter,Color)
{ Draw_Horisontal_Line(X1,X2,Y,Color) }
End;

Thats it. You have just drawn a polygon.

--
Kim Robert Blix  ( kimrb...@online.no  &  http://home.sn.no/~kblix )

"How do you shoot the devil in the back?"
"What if you miss?" -Verbal Kint
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

## Re:Polygon filling

##### Quote
>I am searching for a method to filling polygones (like in BGI)?
>It should be possibly FAST, but i will thank you for everything
>you send me...

Here is the fillypoly we use.

Limitations:
You must allocate the HlineList somewhere before the call to fillpoly
(ie, new(hLineList); ... draw your polygons ... dispose(hLineList);
You must supply your own horizline() routine.
It only fills convex polygons.
The calling convention is the same as the BGIs, but has an extra paramater
for colour.

Notes:

This fillpoly is based loosely on Michael Abrash's code.  However, we
changed the clipping code.  On a 486-100 it created 4000 [clipped] polygons
per second in 1280x1024x8bpp.  YMMV.  If you need a fast polygon that
only has 4 sides, I recommend looking at Ansgar Scherp's fillpoly in
his wormhol3 demo.  This polygon filler supports a maximum of
16384 sides.  I just typed this in from my laptop, so there may be errors.
Email me if you want the non-copied version.

{ --- snip --- }
type TLineList=[0..1199] of record xleft, xright:integer end;
var HLineList:^TLineList;

procedure FillConvexPoly(NumPoints:word;
var PolyPoints:array of PointType;
colour:byte);

var outcode:integer;
var count:integer;
andresult,OrResult:word;
firstInB:Integer;
yStart,yEnd:integer;
linecount:word;
var i, MinIndexL, MaxIndex,MinIndexR,Temp,
MinPoint_Y, MaxPoint_Y, LeftEdgeDir,
NextIndex, CurrentIndex, PreviousIndex,
DeltaXN,DEltaYN, DeltaXP, DeltaYP:integer;
ScanLines:integer;
TopIsFlat:boolean;

{nested procedure}
procedure scanedge(x1,y1,x2,y2:integer;SetXLEft:boolean); assembler;
height:word;
asm
les     di,HlineList
mov     ax,y1
shl     ax,2
add     di,ax   ; {seek into linelist}

cmp     setXleft,True   ;  {are we setting the left edge?}
jz      @@HLinePtrSet   ;  {yes, DI points to the first Xstart}

@@HLinePtrSet:

mov     bx,y2
sub     bx,y1
jle     @@ScanEdgeDone
mov     Height,bx
xor     cx,cx

mov     dx,1
mov     ax,x2
sub     ax,x1
jz      @@IsVertical
mov     cx,1
sub     cx,bx
neg     dx
neg     ax

; { Figure out whether the edge is diagonal, x-major (more horizontal),}
; { or Y-major (more vertical) and handle appropiately }

cmp     ax,bx
jz      @@IsDiagonal
jb      @@yMajor

xor     dx,dx
div     bx

mov     si,ax

neg     si

mov     ax,x1

@@XMajorLoop:

mov     es:[di],ax

sub     cx,Height

dec     bx
jnz     @@XMajorLoop
jmp     @@ScanEdgeDone

@@IsVertical:
mov     ax,x1
cmp     bx,0
je      @@ScanEdgeDone
@@VerticalLoop:
mov     es:[di],ax
dec     bx
jnz     @@VerticalLoop
jmp     @@ScanEdgeDone

@@IsDiagonal:

mov     ax,x1

@@DiagonalLoop:

mov     es:[di],ax
dec     bx
jnz     @@DiagonalLoop
jmp     @@ScanEdgeDone

@@YMajor:
push    bp
mov     si,x1
mov     bp,bx

@@YMajorLoop:

mov     es:[di],si
sub     cx,bp
dec     bx
jnz     @@YMajorLoop
pop     bp
@@ScanEdgeDone:
end;

{another nested procedure}
{plotline will clip a line against the screen.}
procedure plotline(x1,y1,x2,y2:integer;SetXStart:Boolean);
var temp,tx1,ty1,tx2,ty2:integer;
xvs,yvs:integer;
AndResult,OrResult,OutCode:word;

begin
xvs:=0;
yvs:=0;

andresult:=15;
orresult:=0;
outcode:=0;

if x1<0 then inc(outcode,8);
if x1>getmaxX then inc(outcode,4);
if y1<0 then inc(outcode,2);
if y1>getmaxY then inc(outcode);
andresult:=andresult and outcode;
orresult:=orresult or outcode;
outcode:=0;

if x2<0 then inc(outcode,8);
if x2>getmaxX then inc(outcode,4);
if y2<0 then inc(outcode,2);
if y2>getmaxY then inc(outcode);
andresult:=andresult and outcode;
orresult:=orresult or outcode;

if andresult>0 then exit; {line is completely off the screen}
if orresult=0 then
begin
scanedge(x1,y1,x2,y2,SetXStart);
if y1<ystart then ystart:=y1 else if y1>yend then yend:=y1;
if y2<ystart then ystart:=y2 else if y2>yend then yend:=y2;
exit;
end;
tx1:=x1;
tx2:=x2;
ty1:=y1;
ty2:=y2;
{clip line to the screen}
if (x1<0) then
begin
ty1:=(x2*longint(y1)-x1*longint(y2)) div (x2-x1);
tx1:=0;
end else
if (x2<0) then
begin
ty2:=(x2*longint(y1)-x2*longint(y2)) div (x2-x1);
tx2:=0;
end;

if (X1>GetMaxX) then
begin
ty1:=(longint(y1)*(x2-getMaxX)+longint(y2)*(getMaxX-x1)) div (X2-x1);
tx1:=GetMaxX
end else
if (X2>GetMaxX) then
begin
ty2:=(longint(y1)*(x2-getMaxX)+longint(y2)*(getMaxX-x1)) div (x2-x1);
tx2:=GetMaxX
end;
if ((ty1<0) and (ty2<0)) or ((ty1>GetMaxY) and (ty2>GetMaxY) then exit;
if (ty1<0) then
begin
tx1:=(x1*longint(y2)-x2*longint(y1)) div (y2-y1);
ty1:=0
end else
if (ty2<0) then
begin
tx2:=(x1*longint(y2)-x2*longint(y1)) div (y2-y1);
ty2:=0;
end;

if (ty2>GetMaxY) then
begin
tx1:=(longint(x1)*(y2-getmaxy)+longint(x2)*(GetMaxY-y1)) div (y2-y1);
ty1:=GetMaxY
end
else
if (ty2>GetMaxY) then
begin
tx2:=(longint(x1)*(y2-GetMaxy)+longint(x2)*(GetMaxY-y1)) div (y2-y1);
ty2:=GetMaxy;
end;
if (tx1<0) or (tx2<0) or (tx1>getmaxx) or (tx2>getmaxx) then exit;
Scanedge(tx1,ty1,tx2,ty2,SetXStart);
if y1<ystart then ystart:=y1 else if y1>yend then yend:=y1;
if y2<ystart then ystart:=y2 else if y2>yend then yend:=y2;
inc(linecount);
end;

begin
if (numpoints<=1) then exit; {reject null polygons}
andresult:=15;
firstinb:=-1;
orresult:=0;
for count:=0 to NumPoints-1 do
with PolyPoints[count] do
begin
outcode:=0;
if x<0 then inc(outcode,8)
if x>GetMaxX then inc(outcode,4);
if y<0 then inc(outcode,2);
if y>getmaxy then inc(outcode);
andresult:=andresult and outcode;
orresult:=orresult or outcode;
end;
if andresult>0 then exit; {polygon is completely off the screen}
ystart:=PolyPoints[0].y;
yend:=ystart;

for count:=1 to NumPoints-1 do
with PolyPoints[count] do
if y<yend then yend:=y else if y>ystart then ystart:=y;

if yend<0 then yend:=0;  {yes, they are reversed.  Don't ask}
if ystart>getmaxy then ystart:=getmaxy;

for count:=yend to ystart do
with hlinelist^[count] do
begin
xleft:=0;
xright:=getmaxx
end;

MinIndexL:=0;
MaxIndex:=0;
MinPoint_Y:=PolyPoints[0].y;
MaxPoint_Y:=MinPoint_Y;

for i:=1 to NumPoints-1 do
with PolyPoints[i] do
begin
if (y < MinPoint_Y) then
begin
MinIndexL:=i;
MinPoint_Y:=y;
end
else if (y>MaxPoint_Y) then
begin
MaxIndex:=i;
MaxPoint_Y:=y;
end;
end;
if (MinPoint_Y = MaxPoint_Y) then exit;

{ scan in ascending order to find the last top-edge point }
MinIndexR:=MinIndexL;
while (PolyPoints[MinIndexR].Y=MinPoint_Y) do
MinIndexR:=(MinIndexR+1) mod NumPoints;
MinIndexR:=(MinIndexR+NumPoints-1) mod NumPoints;

{ Now scan in descending order to find the first top-edge point }
while (PolyPoints[MinIndexL].Y = MinPoint_Y) do
MinIndexL:=(MinIndexL+NumPoints-1) mod NumPoints;
MinIndexL:=(MinIndexL+1) mod NumPoints;

{ Figure out which direction through the vertex list from the top
vertex is the left edge and which is the right }

LefEdgeDir:=-1;

{this was ported from C, can't you tell? ;)}
TopIsFlat:=PolyPoints[MinIndexL].X<>PolyPoints[MinIndexR].X;

if (TopIsFlat) then
begin
{ If the top is flat, just see which of the ends is leftmost }
if (PolyPoints[MinIndexL].X > PolyPoints[MinINdexR].X) then
begin
LeftEdgeDir:=1;
Temp:=MinIndexL;
MinIndexL:=MinIndexR;
MinINdexr:=Temp;
end
end else
begin
{ Point to the downward end of the first line of each of the
two edges down from the top }
NextIndex:=MinIndexR;
NextIndex:=(NextIndex+1) mod NumPoints;
PreviousIndex:=MinIndexL;
PreviousIndex:=(PreviousIndex+NumPoints-1) mod NumPoints;

DeltaXN:=PolyPoints[NextIndex].X - PolyPoints[MinIndexL].X;
DeltaYN:=PolyPoints[NextIndex].Y - PolyPoints[MinIndexL].Y;
DeltaXP:=PolyPoints[PreviousIndex].X - PolyPoints[MinIndexL].X;
DeltaYP:=PolyPoints[PreviousIndex].Y - PolyPoints[MinIndexL].Y;
if ((longint(DeltaXN)*DeltaYP - longint(DeltaYN)*DeltaXP) < 0) then
begin
LeftEdgeDir:=1;
Temp:=MinINdexL;
MinIndexL:=MinIndexR;
MinINdexR:=Temp;
end;
end;

{ Set the # of scan lines in the polygon, skipping the bottom edge
and also skipping the top vertex if the top isn't flat because
in that case the top vertex has a right edge component, and set
the top scan line to draw, which is likewise the second line of
the polygon unless the top is flat }

ScanLines:=MaxPoint_Y-MinPoint_Y+byte(TopIsFlat);
if scanlines<=0 then exit;

CurrentIndex:=MinIndexL;
PreviousIndex:=MinIndexL;

repeat
if (LeftEdgeDir>0) then
CurrentIndex:=(CurrentIndex+1) mod NumPoints
else
CurrentIndex:=(CurrentIndex-1+NumPoints) mod NumPoints;
PlotLine(PolyPoints[PreviousIndex].X,
PolyPoints[PreviousIndex.Y,
PolyPoints[CurrentIndex].X,
PolyPoints[CurrentIndex].Y, TRUE);
PreviousIndex:=CurrentIndex;
until (CurrentIndex=MaxIndex);

CurrentIndex:=MinIndexR;
PreviousIndex:=MinIndexR;

repeat
if (-LeftEdgeDir>0) then
CurrentIndex:=(CurrentIndex+1) mod NumPoints
else
CurrentIndex:=(CurrentIndex - 1 + NumPoints) mod NumPoints;
PlotLine(PolyPoints[PreviousIndex].X,
PolyPoints[PreviousIndex.Y,
PolyPoints[CurrentIndex].X,
PolyPoints[CurrentIndex].Y, FALSE);
PreviousIndex:=CurrentIndex;
until (CurrentIndex=MaxIndex);

if ystart<0 then ystart:=0;
if yend>getmaxy then yend:=getmaxy;

for count:=ystart to yend-1 do
with hlinelist^[count] do
horizline(xleft,xright,count,colour);
end;

{ --- snip --- }

--Mark Iuzzolino
one of the monst...@monstersoft.com  |  "Uhm, the
...