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;
var AdvanceAmt:Integer;
    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}
        add     di,2            ;  {adjust pointer to xright}

@@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
        jns     @@SetAdvanceAmt
        mov     cx,1
        sub     cx,bx
        neg     dx
        neg     ax
@@SetAdvanceAmt:
        mov     AdvanceAmt,dx

; { 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
        test    AdvanceAmt,8000h

        jz      @@XMajorAdvanceAmtSet
        neg     si

@@XMajorAdvanceAmtSet:
        mov     ax,x1

@@XMajorLoop:

        mov     es:[di],ax
        add     di,4
        add     ax,si
        add     cx,dx
        jle     @@XMajorNoAdvance

        add     ax,AdvanceAmt
        sub     cx,Height

@@XMajorNoAdvance:
        dec     bx
        jnz     @@XMajorLoop
        jmp     @@ScanEdgeDone

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

@@IsDiagonal:

        mov     ax,x1

@@DiagonalLoop:

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

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

@@YMajorLoop:

        mov     es:[di],si
        add     di,4
        add     cx,ax
        jle     @@YMajorNoAdvance
        add     si,dx
        sub     cx,bp
@@YMajorNoAdvance:
        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
...

read more »

Other Threads