Vol. 2 Iss. 1 - March 2001

Basic Poly Filling

By Sane <sane@telia.com>

This is the first part of a series about graphics programming techniques that I will be writing for QBCM, and I hope you'll enjoy it, and learn some new stuff.

The word polygon means something like "shape with 3 or more sides", but I will only cover drawing of polys with 3 sides (triangles), cause they're the ones mostly used in 3D programming, and any polygon with more than 3 sides could be made out of 3 side polygons anyways, using a technique called "polygon triangulation", which I won't cover (at least not in this part) though.

I won't have much theory about poly drawing, cause I don't think anyone would care anyways :) Flatshaded polygons (polygons made using one color only), the type of polygon that's easiest to fill (except for wireframe polys, that aren't filled anyways, so I don't know why I even write this comment :), are most often made using these three steps:

- point sorting
- slope calculating
- drawing

Point sorting is basically needed to make life easier when doing the other stuff, cause you won't have to check if the y between two points should be increasing or decreasing, and it also makes stuff such as gouraud shading and such a bit easier.

Slope calculating is needed to calculate all x values for every y in the poly, and is done using the formula m=(x1-y1)/(x2-y2), where m is the medium slope value.

Drawing is quite a good thing too... :) The drawing is the easiest part, and is done by drawing horizontal lines between the x:es calculated when calculating the slopes.

We will sort the points as shown in the picture:

Here's an example of how the routine could be implemented:

'Made by Sane at the 23st of February 2001, for QBCM SUB flatpoly (xx1, yy1, xx2, yy2, xx3, yy3, c) 'Declare an array for storing slopes DIM poly(199, 1) 'Point sorting IF yy1 < yy2 AND yy1 < yy3 THEN x1 = xx1: y1 = yy1 IF yy2 < yy1 AND yy2 < yy3 THEN x1 = xx2: y1 = yy2 IF yy3 < yy1 AND yy3 < yy2 THEN x1 = xx3: y1 = yy3 IF yy1 < yy2 AND yy1 < yy3 THEN x3 = xx1: y3 = yy1 IF yy2 < yy1 AND yy2 < yy3 THEN x3 = xx2: y3 = yy2 IF yy3 < yy1 AND yy3 < yy2 THEN x3 = xx3: y3 = yy3 IF yy1 <> y1 AND yy1 <> y3 THEN x2 = xx1: y2 = yy1 IF yy2 <> y1 AND yy2 <> y3 THEN x2 = xx2: y2 = yy2 IF yy3 <> y1 AND yy3 <> y3 THEN x2 = xx3: y2 = yy3 'Calculating of the slope from point 1 to point 2 m = 0 x = 0 IF x1 + x2 <> 0 AND y1 + y2 <> 0 THEN m = (x1 - x2) / (y1 - y2) FOR y = y1 TO y2 poly(y, 0) = x + x1 x = x + m NEXT y 'Calculating of the slope from point 2 to point 3 m = 0 x = 0 IF x2 + x3 <> 0 AND y2 + y3 <> 0 THEN m = (x2 - x3) / (y2 - y3) FOR y = y2 TO y3 poly(y, 0) = x + x2 x = x + m NEXT y 'Calculating of the slope from point 1 to point 3 m = 0 x = 0 IF x1 + x3 <> 0 AND y1 + y3 <> 0 THEN m = (x1 - x3) / (y1 - y3) FOR y = y1 TO y3 poly(y, 1) = x + x1 x = x + m NEXT y 'The easiest part, drawing FOR y = y1 TO y3 LINE (poly(y, 0), y)-(poly(y, 1), y), c NEXT y END SUB

And here's some simple test code for it:

'Made by Sane at the 23st of February 2001, for QBCM SCREEN 13 oldtimer! = TIMER DO UNTIL INKEY$ = CHR$(27) x1 = INT(RND * 320) x2 = INT(RND * 320) x3 = INT(RND * 320) y1 = INT(RND * 200) y2 = INT(RND * 200) y3 = INT(RND * 200) flatpoly x1, y1, x2, y2, x3, y3, INT(RND * 15) polynum = polynum + 1 IF TIMER > oldtimer! + 1 THEN LOCATE 1, 1: PRINT polynum: oldtimer! = TIMER: polynum = 0 LOOP

I wrote this code in a hurry (this is the afternoon before the articles have to be sent in), but I got about 170 randomized polys/sec on my K6 233 mHz, uncompiled and unoptimized.

In case you're too lazy to write the code into QB, there should be a file called "POLY.BAS" together with QBCM if you've downloaded the zip version.

This was all from me this time, please mail any comments to <sane@telia.com>, I'd love to get any feedback.

Next part will probably be about gouraud shading, maybe other poly filling techniques too, but if you'd like me to write about something else, or have any ideas for future subjects, mail me at the same address as above, <sane@telia.com>, see ya then, and good luck with your poly coding :)