mirror of
https://github.com/opsxcq/mirror-textfiles.com.git
synced 2025-08-09 13:26:57 +02:00
252 lines
9.2 KiB
Plaintext
252 lines
9.2 KiB
Plaintext
WGT Graphics Tutorial #1
|
|
Topic: Filled Polygons
|
|
By Chris Egerter
|
|
October 7, 1994
|
|
|
|
Introduction
|
|
------------
|
|
This series of tutorials describes a method of drawing filled polygons
|
|
using 3 rendering techniques: Solid, Gouraud shading, and texture mapping.
|
|
|
|
The code in this tutorial was written in Turbo C++ but can be ported to
|
|
other graphics libraries and operating systems. I did not use the
|
|
WGT functions in this one, so the wgtgfx.c file contains a few routines
|
|
which are needed for the demo. I have decided to explain the method
|
|
used for these routines since I had to discover them on my own, and
|
|
think you can learn from the code.
|
|
|
|
1.0 - What is a Polygon?
|
|
------------------------
|
|
To start things off, we should first define what a polygon is. A
|
|
polygon is a any figure that is composed of straight lines. It can have any
|
|
number of sides, and may or may not be closed. We will be discussing closed
|
|
polygons in this article mainly because they allow you to fill the interior
|
|
with a colour. An open polygon can only have its edges drawn because there
|
|
is no difference between the inside and outside. Furthermore, we will
|
|
only discuss convex polygons. If you draw a horizontal line across the
|
|
polygon, it must cross exactly two edges at any given vertical position.
|
|
If the polygon passes this test, it is convex.
|
|
|
|
|
|
2.0 - Drawing Polygons with Horizontal Lines
|
|
--------------------------------------------
|
|
In computer graphics, the screen is comprised of an x and a y axis,
|
|
with the coordinate (0,0) being the top left corner. Each polygon consists
|
|
of a number of vertices, each of which contain an (x,y) coordinate on the
|
|
screen. Our first task is to draw a filled polygon given a set of vertices.
|
|
A simple way to fill the polygon would be to draw lines between the vertices
|
|
(making sure to connect the first to the last) and using a region fill
|
|
routine to fill in the interior. This works in most cases however it is
|
|
slow, and not very useful in a program that requires animation. The other
|
|
method, is to draw a series of horizontal lines that make up the polygon.
|
|
|
|
3.0 - The algorithm
|
|
-------------------
|
|
The reason for dealing with only convex polygons is simple. Knowing
|
|
that we can draw the polygon using horizontal lines, we can simply store
|
|
the starting and ending x coordinate of the horizontal line on each y
|
|
coordinate of the polygon. Non-convex polygons would require several
|
|
horizontal lines per y coordinate, and things get a bit more complicated.
|
|
|
|
Our basic algorithm for drawing polygons is this:
|
|
1. Calculate the starting and ending x coordinate of the horizontal line
|
|
on each y coordinate. We can do this by using a standard line algorithm
|
|
but instead of plotting pixels, store the x coordinates into an array.
|
|
Simply calculate the lines between all vertices and connect the first
|
|
and last vertex with a line to close the figure.
|
|
2. Draw each horizontal line given the row, and two columns.
|
|
|
|
As you can see here, a polygon may be drawn using two simple, well
|
|
known routines: The line (with any slope), and the horizontal line.
|
|
|
|
|
|
4.0 - Keeping Track of the Left and Right Edges
|
|
-----------------------------------------------
|
|
Let's define two arrays which will contain our horizontal line
|
|
coordinates. These routines assume you are using 320x200x256 graphics mode,
|
|
however they can be easily ported to another mode by changing the 200 to the
|
|
number of rows the mode has.
|
|
|
|
int startx[200];
|
|
int endx[200];
|
|
|
|
Before the polygon is drawn, each value in these arrays will be set
|
|
to an impossible number to indicate that no point has been found on that y
|
|
coordinate. For the following examples, I will use -16000 as the impossible
|
|
number that would never be used.
|
|
|
|
|
|
5.0 - Scan Converting the Edges of the Polygon
|
|
----------------------------------------------
|
|
Our next step is to create a routine that will calculate a line and
|
|
store the x coordinates for every y coordinate. When we store the x
|
|
coordinate, first check the startx array. If it is -16000, this is the
|
|
first point found on this row. We will then store the x coordinate into
|
|
the startx array and continue with the line. If startx is not -16000, this
|
|
means a point has already been found, and we can store the coordinate in the
|
|
endx array (since we already know each row has exactly two intersections with
|
|
the polygon).
|
|
|
|
Below is the code for this routine:
|
|
|
|
void polyline (int x1, int y1, int x2, int y2)
|
|
/* Calculates the coordinates of a line given two
|
|
vertices (x1,y1) an (x2,y2).
|
|
|
|
We will use fixed point math to speed things up.
|
|
The x coordinate is multiplied by 256 and for each row,
|
|
a constant m is added to x. This is a simplified version
|
|
of a line algorithm because we only have to store 1 x coordinate
|
|
for every y coordinate.
|
|
|
|
*/
|
|
{
|
|
int tmp,y;
|
|
long x,m;
|
|
|
|
if (y2 != y1) /* This isn't a horizontal line */
|
|
{
|
|
if (y2 < y1) /* Make sure y2 is greater than y1 */
|
|
{
|
|
tmp = y1; /* Swap the y coordinate */
|
|
y1 = y2;
|
|
y2 = tmp;
|
|
|
|
tmp = x1; /* Swap the corresponding x coordinates */
|
|
x1 = x2;
|
|
x2 = tmp;
|
|
}
|
|
|
|
x = (long)x1<<8; /* Multiply be 256 */
|
|
|
|
m = ((long)(x2 - x1)<<8) / ((long)(y2 - y1));
|
|
/* m is the fractional amount to add to the x coordinate every row.
|
|
m is equal to (delta x) / (delta y). In other words, the x coordinate
|
|
has to change by (x2 - x1) columns in (y2 - y1) rows. */
|
|
|
|
x += m; /* We ALWAYS skip the first point in every line. This is done */
|
|
y1++; /* because we do not want to store the point where two lines
|
|
meet, twice. This would result in a single point being drawn. */
|
|
|
|
for (y = y1; y <= y2; y++) /* Go through each row */
|
|
{
|
|
if ((y >= 0) & (y < 200)) /* If the coordinate is on the screen */
|
|
if (startx[y] == -16000) /* Store the first coordinate */
|
|
startx[y] = x>>8;
|
|
else
|
|
endx[y] = x>>8; /* Store the last coordinate */
|
|
x += m; /* Add our constant to x */
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
6.0 - Calling the Polyline Routine
|
|
----------------------------------
|
|
Next we need to write a routine that will go through our vertex list
|
|
and call this routine. Once that is complete, we can draw all of our
|
|
horizontal lines.
|
|
|
|
First of all, let's make a structure for our vertices.
|
|
This segment should appear at the top of your program with the startx and
|
|
endx arrays.
|
|
|
|
typedef struct
|
|
{
|
|
int x,y;
|
|
} point;
|
|
|
|
Our main polygon routine will take an array of points, call the
|
|
polyline routine between each of the points, and finally draw each
|
|
horizontal line in the array.
|
|
|
|
Below is the filled polygon main routine:
|
|
|
|
void fillpoly (point *vertexlist, int numvertex)
|
|
/* Draws a filled polygon given an array of vertices. */
|
|
{
|
|
int i;
|
|
point *curpt,*nextpt;
|
|
/* Two pointers to a vertex. These are used to connect to vertices
|
|
together in when calling the polyline routine. */
|
|
|
|
curpt = vertexlist; /* Set to the first vertex in the array */
|
|
nextpt = vertexlist + 1; /* and to the second vertex */
|
|
|
|
for (i = 0; i < 200; i++)
|
|
{
|
|
startx[i] = -16000; /* Set up our impossible values */
|
|
endx[i] = -16000;
|
|
}
|
|
|
|
for (i = 1; i < numvertex; i++)
|
|
{
|
|
polyline (curpt->x, curpt->y, nextpt->x, nextpt->y);
|
|
/* Calculate the edge of this line. */
|
|
|
|
curpt += 1; /* Go to the next line */
|
|
nextpt += 1;
|
|
}
|
|
|
|
nextpt = vertexlist; /* Now close the polygon by doing a line between
|
|
the first and last vertex. */
|
|
polyline (curpt->x, curpt->y, nextpt->x, nextpt->y);
|
|
|
|
for (i = 0; i < 200; i++) /* Now draw the horizontal line list */
|
|
if (startx[i] != -16000) /* Indicates there is a line on this row */
|
|
{
|
|
if (endx[i] == -16000)
|
|
endx[i] = startx[i]; /* In case there was only one
|
|
point found on this row */
|
|
line (startx[i], i, endx[i], i);
|
|
/* Draw a line between the two x coordinates, on the row i. */
|
|
}
|
|
}
|
|
|
|
|
|
Now we should make a small test program to use these functions:
|
|
|
|
point mypoints[10];
|
|
|
|
void main (void)
|
|
{
|
|
initialize_graphics ();
|
|
|
|
mypoints[0].x = 160;
|
|
mypoints[0].y = 30;
|
|
mypoints[1].x = 50;
|
|
mypoints[1].y = 150;
|
|
mypoints[2].x = 270;
|
|
mypoints[2].y = 180;
|
|
|
|
fillpoly (&mypoints, 3);
|
|
getch ();
|
|
close_graphics ();
|
|
}
|
|
|
|
This will draw a triangle in the middle of the screen.
|
|
You can use these routines with any graphics library. The only routines
|
|
you will need to rename are the graphics initialization and closing routines,
|
|
and the line routine.
|
|
|
|
That's are there is to it. This is a simple case however. There are
|
|
other methods to fill a polygon with something other than solid colours. The
|
|
two techniques I will discuss in the next issues are Gouraud shading and
|
|
texture mapping.
|
|
|
|
The code and test program contained in this text file has been put into
|
|
two files:
|
|
|
|
fillpoly.c - contains the original (portable) code
|
|
poly256.c - contains a demonstration in the 320x200x256 graphics mode
|
|
|
|
wgtgfx.c - Various graphics support routines
|
|
wgtgfx.h - Header file for support routines
|
|
|
|
poly256 has been compiled into poly256.exe so you can view what these
|
|
routines do instantly. To compile poly256, make a project file and
|
|
compile and link poly256.c and wgtgfx.c together.
|
|
|
|
|
|
|