The Polygon Fill Subroutine

Extending Atari High Resolution Graphics

Part 1: The Polygon Fill Subroutine

Phil Dunn

In this three-part series, Mr. Dunn introduces the reader to advanced graphics techniques, from a flexible fill routine to realistic "textured" graphics, and concludes with a technique that allows more than 66 pseudo-colors in Graphics Mode 8.

Polyfil is a versatile subroutine that permits filling in any shape, not just boxes and trapezoids, as with the XIO Fill command.

This is the first of three essays which will develop some methods to aid in creating more dramatic displays in the Atari high resolution graphics modes. The intent is to show how we can use the hi-res modes more effectively, and to set up techniques that enable us to do these things in the easiest possible way.

One very useful function that is not in the Atari BASIC repertoire is the polygon fill subroutine. The ease with which this function enables us to create pictures with large complex shapes is so significant that any graphics system lacking it should probably be considered incomplete.

A type of color fill is available within the Atari BASIC function options. However, its limitations are such that it provides very little convenience for developing pictures with shapes and areas that have many angles and irregular boundaries. Naturally, the most interesting pictures usually have just this characteristic!

The example program shows the power of the polygon colorfill subroutine, Polyfil. Let's scan the program to get an overview of how it works. Lines 200 to 240 establish Graphics mode 7 without the text window and set the four color registers (that we are allowed) to the colors that we choose. Lines 250 to 400 set up the numeric values and transfer them to Polyfil, which starts at line 17000. The actual data used by the Polyfil subroutine to create this particular picture are on lines 420 to 730. You can use this program to create your own scene by changing these lines.

Lines 800 to 959 have nothing to do with the polygon fill. They set the images of two figures in the usual PLOT-DRAWTO way. You may note that there is almost as much coding in lines 800 to 955 for these two little figures as there is in lines 430 to 730 for the rest of the entire picture done with Polyfil.

A Programming Trick

Incidentally, there is a little programming trick used here that you might want to note. I was not sure of the exact screen locations that would most effectively, aesthetically locate the figures. So I calculated the X, Y pixel locations relative to a reference pixel at the head of each figure. Then that number is added to the variable XX or YY for the PLOT-DRAWTO commands. I just changed the XX and YY values until the image looked appropriate. The same thing could have been done in lines 350 and 360, to add bias numbers to the X, Y values for the area vertex points if I weren't sure of the placement of these large areas.

Lines 16000 to 16130 just describe the input and variable requirements for the Polyfil subroutine. The actual subroutine itself only consists of lines 17000 to 17190. This subroutine was "mashed" for minimum memory usage, and then carefully "unmashed" for ease in transcribing. If you want to type it in as a mashed version, all you have to do is to chain all the lines that are not even multiples of ten into the previous line that is. Thus, lines 17001, 17002, 17003, 17004, and 17005 can all be chained into line 17000. Similarly, lines 17020 and 17021 can be combined, and lines 17030, 17031, 17032, 17033, and 17034 can all be placed on the same line.

How To Set Up POLYFIL

Now let's get into the input requirements for the Polyfil subroutine. The first value it must have is the number of vertex points around the perimeter of the polygon, entered in the variable NP. For a triangular area, this number would be three, for a rectangle it would be four, etc. Then it needs the X, Y values for each perimeter vertex point.

The user must have previously DIMensioned the array variables X(), Y(), R(), and S(). The DIMension size must be equal to or greater than the number of vertex points. The vertex point values must be loaded into the array elements, starting with X(1), Y(1). Polyfil then proceeds to fill the area with the usual PLOT-DRAWTO commands. It should be noted that Polyfil uses the variable names Q1, Q2, I, J, YMAX, YMIN, YNOW, IM, IP, XA, and XB.

For those who want to understand how Polyfil works, an explanation follows. For each line segment around the perimeter, the slope and Y axis intercept are calculated in lines 17020 and 17021, respectively. Then the maximum and minimum Y axis values of the perimeter vertex points are determined in lines 17034 and 17040. The initial starting point is established as the smallest Y axis value on line 17051.

The Y value is then increased by one on line 17130 and the intercept points on the horizontally opposite sides are calculated as XA and XB on lines 17090 and 17110. A horizontal line is then drawn connecting the two points on line 17120. Y is then increased again and this is repeated until Y is the maximum polygon value. There is additional logic for vertical lines where the slope is not calculable, and to switch intercept calculations from one line segment to another as vertex points are passed over.

Now let's go over the program in some detail so we can see exactly what is done to use the Polyfil routine. First, an explanation of those code numbers in the data. The first number in each DATA statement assigns a color register to that shape. So, the mountain data on line 430 is assigned to color register 2. The second number specifies the number of vertex points in the shape. The mountain has six vertex points. The remainder of the data consists of the X, Y values for each vertex point. So, the first specified vertex point for the mountain is the X, Y values of 54, 42, the second vertex point is 68, 30, etc.

It should be noted that, when establishing these areas for Polyfil, the farthest background areas should be defined first and the nearest foreground areas should be defined last. That's how you get the visual effect of distance, where the "near" object is drawn over the "far" object.

There are only two limitations on how the vertex point data must be specified for Polyfil. The first restriction is that the points must be specified in a sequential order around the polygon perimeter. The second restriction is that the polygon shape must not have any indentations that require the fill technique to skip over empty spaces. Since the fill method used here consists of a series of horizontal lines, this means that "E" and "L" type shapes are ok, but "U" and "H" type shapes will not be filled properly. This is no major limitation, since any unacceptable shape can always be split up into two or more acceptable shapes, each of which can be filled separately.

Now, back to the essential program factors for using the Polyfil subroutine. Line 250 DIMensions the variables X(), Y(), S(), T().

Line 320 READs the first two bytes of DATA and assigns them to the variables COLR and NP, respectively. However, if it READs a -1 value for COLR, that signifies the end of DATA, and the program then jumps to line 800. Lines 330 to 370 then use that NP value to READ the next NP amount of number-pairs and store them into the X(), Y() arrays. Line 380 then applies the value in the COLR variable to set the COLOR command. Finally, line 390 GOSUBs to the Polyfil subroutine which does the job.

By now you may have loaded the example program and seen the picture. Within its limitations, it "works" the way I intended it to. Not only is it a good example for using the Polyfil subroutine, but it has aesthetic quality. Within the limitations of the graphics techniques we are using here, the picture is ok.

However, because of these limitations of Graphics Mode 7, only four colors, and slightly rough resolution relative to Mode 8, the picture seems somewhat flat and blocky.

Of course, we could spruce it up a little. We could get more colors by replacing the figures and the tree trunks with player-missile images. We could use David Small's Display List Interrupt driver routine to assign different colors to our registers at different vertical heights down the screen.

All these things could be used to improve the picture to a certain extent. However, the picture would still have a somewhat blocky and flat appearance.

The next essay on "Extending High Resolution Graphics" will address some aspects of this problem.

PROGRAM. The Polygon Fill Subroutine.


100 REM =============================

105 REM = {4 SPACES} POLYFIL Subroutine {5 SPACES} =

110 REM = Demonstration Program {3 SPACES} =

120 REM =============================

125 REM = {11 SPACES} by : {13 SPACES} =

130 REM = {8 SPACES} Phil Dunn {10 SPACES} =

135 REM = {6 SPACES} 12 Monroe Ave. {7 SPACES} =

140 REM = {3 SPACES} Hicksville, NY 11801 {4 SPACES} =

150 REM =============================

170 REM

200 GRAPHICS 7 + 16

210 SETCOLOR 0, 5, 6 : REM C.1 = MAROON

220 SETCOLOR 1, 10, 8 : REM C.2 = GREEN

230 SETCOLOR 2, 9, 10 : REM C.3 = WHITE, WINDO

240 SETCOLOR 4, 8, 8 : REM C.0 = BLUE, BACKG.

250 DIM X(12), Y(12), S(12), T(12)

280 POLYFIL = 17000

305 REM Read areas and fill them in

315 REM First read the color & no. of points.

320 READ COLR, NP

322 IF COLR = -1 THEN 800

325 REM Now read in all the vertex point coordinates

330 FOR N = 1 TO NP

340 READ XX, YY

350 X(N) = XX

360 Y(N) = YY

370 NEXT N

375 REM Now set the color

380 COLOR COLR

385 REM Now let the subroutine fill it in

390 GOSUB POLYFIL

400 GOTO 320

402 REM =============================

403 REM = {4 SPACES} Scene from the book {4 SPACES} =

404 REM = 'Stranger By The River' =

405 REM = {4 SPACES} by Paul Twitchell {5 SPACES} =

406 REM =============================

420 REM MOUNTAIN

430 DATA 2, 6, 54, 42, 68, 30, 85, 22, 110, 35, 118, 45, 54, 45

440 REM MOUNTAIN TOP

450 DATA 3, 6, 85, 22, 98, 29, 95, 30, 88, 32, 78, 29, 74, 27

470 REM LOWLANDS

480 DATA 2, 5, 0, 44, 80, 40, 159, 44, 159, 45, 0, 45

520 REM FOREGROUND

530 DATA 2, 4, 0, 65, 159, 65, 159, 96, 0, 96

540 REM RIVER

550 DATA 3, 12, 0, 44, 159, 44, 159, 66, 140, 68, 125, 70, 105, 74, 80, 77, 60, 78, 47, 78, 40, 77, 25, 75, 0, 69

630 REM LEFT TREE TOP

650 DATA 2, 12, 25, 25, 37, 34, 32, 35, 36, 40, 30, 43, 33, 55, 18, 59, 5, 50, 12, 41, 8, 37, 15, 32, 12, 30

660 REM RIGHT TREE TOP

670 DATA 2, 8, 130, 32, 149, 39, 145, 48, 153, 56, 135, 68, 116, 61, 120, 53, 115, 47

690 REM LEFT TREE TRUNK

700 DATA 1, 6, 11, 80, 16, 56, 19, 52, 21, 57, 17, 81, 14, 83

720 REM RIGHT TREE TRUNK

730 DATA 1, 6, 131, 83, 130, 65, 133, 59, 136, 65, 141, 82, 136, 85

750 DATA -1, -1

800 REM Paul

805 COLOR 0

810 XX = 55

820 YY = 80

825 PLOT XX - 1, YY + 3 : DRAWTO XX - 1, YY + 8

830 PLOT XX, YY : DRAWTO XX, YY + 8

835 PLOT XX + 1, YY + 3 : DRAWTO XX + 1, YY + 8

840 PLOT XX + 4, YY + 4 : DRAWTO XX + 4, YY + 8

845 PLOT XX + 1, YY : PLOT XX + 1, YY + 1

850 PLOT XX + 2, YY + 4 : PLOT XX + 3, YY + 4

855 PLOT XX + 3, YY + 5 : PLOT XX + 3, YY + 6

860 PLOT XX + 2, YY + 6 : PLOT XX + 2, YY + 7

865 PLOT XX + 5, YY + 8

870 PLOT XX + 1, YY : PLOT XX + 1, YY + 1

880 PLOT XX + 2, YY + 4 : PLOT XX + 3, YY + 4

900 REM Rebezar

905 COLOR 1

910 XX = 65

915 YY = 70

920 PLOT XX - 1, YY + 2 : DRAWTO XX - 1, YY + 13

925 PLOT XX, YY : DRAWTO XX, YY + 10

930 PLOT XX + 1, YY : DRAWTO XX + 1, YY + 10

935 PLOT XX + 2, YY + 2 : DRAWTO XX + 2, YY + 13

940 PLOT XX + 5, YY + 1 : DRAWTO XX + 5, YY + 13

945 PLOT XX - 4, Y Y + 1 : PLOT XX - 3, YY + 2

950 PLOT XX - 2, Y Y + 2 : PLOT XX + 3, YY + 3

955 PLOT XX + 4, YY + 4

999 GOTO 999

16000 REM ===========================

16005 REM = {8 SPACES} POLYFIL{10 SPACES} =

16010 REM = A Polygon Fill Subroutine =

16020 REM = {5 SPACES} by Phil Dunn{8 SPACES} =

16025 REM ===========================

16030 REM Enter with the values…

16040 REM NP = No. of vertex points.

16050 REM X = DIM array of X values

16060 REM Y = DIM array of y values

16070 REM S = DIM array used here

16080 REM T = DIM array used here

16090 REM Uses variables…

16100 REM Q1, Q2, I, J, YMAX, YMIN, YNOW

16110 REM IM, IP, XA, XB

17000 Q1 = 1

17001 Q2 = 1000

17003 FOR I = Q1 TO NP

17004 J = I + Q1

17005 IF J > NP THEN J = Q1

17010 IF X(I) = X(J) THEN S(I) = Q2 : GOTO 17030

17020 S(I) = (Y(J) - Y(I)) / (X(J) - X(I))

17021 T(I) = Y(I) - S(I) * X(I)

17030 NEXT I

17031 YMAX = -Q2

17032 YMIN = Q2

17033 FOR I = Q1 TO NP

17034 IF YMAX < Y(I) THEN YMAX = Y(I)

17040 IF YMIN > Y(I) THEN YMIN = Y(I) : J = I

17050 NEXT I

17051 YNOW = YMIN

17052 IM = J - Q1

17053 IF IM < Q1 THEN IM = NP

17060 IP = J + Q1

17061 IF IP > NP THEN IP = Q1

17070 GOTO 17130

17080 IF S(J) = Q2 THEN XA = X(J) : GOTO 17100

17090 XA = (YNOW - T(J)) / S(J)

17100 IF S(IM) = Q2 THEN XB = X(IM) : GOTO 17120

17110 XB = (YNOW - T(IM)) / S(IM)

17120 PLOT XA, YNOW : DRAWTO XB, YNOW

17130 YNOW = YNOW + Q1

17131 IF YNOW < Y(IP) THEN 17160

17140 IF Y(IP) = YMAX THEN RETURN

17150 J = IP

17151 IP = IP + Q1

17152 IF IP > NP THEN IP = Q1

17160 IF YNOW < Y(IM) THEN 17080

17170 IF Y(IM) = YMAX THEN RETURN

17180 IM = IM - Q1

17181 IF IM < Q1 THEN IM = NP

17190 GOTO 17080

Return to Table of Contents | Previous Section | Next Section