💾 Archived View for gemini.spam.works › mirrors › textfiles › computers › DOCUMENTATION › poly.txt captured on 2022-07-16 at 23:40:56.
⬅️ Previous capture (2022-06-12)
-=-=-=-=-=-=-
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.