Previous | Table of Contents | Next

LISTING 51.5 POLYGON.H

    /* POLYGON.H: Header file for polygon-filling code, also includes a number of
       useful items for 3D animation. */
    #define MAX_POLY_LENGTH 4  /* four vertices is the max per poly */
    #define SCREEN_WIDTH 320
    #define SCREEN_HEIGHT 240
    #define PAGE0_START_OFFSET 0
    #define PAGE1_START_OFFSET (((long)SCREEN_HEIGHT*SCREEN_WIDTH)/4)
    /* Ratio: distance from viewpoint to projection plane / width of projection
       plane. Defines the width of the field of view. Lower absolute values = wider
       fields of view; higher values = narrower. */
    #define PROJECTION_RATIO   -2.0 /* negative because visible Z coordinates are negative */
    /* Draws the polygon described by the point list PointList in color Color with
       all vertices offset by (X,Y) */
    #define DRAW_POLYGON(PointList,NumPoints,Color,X,Y)          \
       Polygon.Length = NumPoints; Polygon.PointPtr = PointList; \
       FillConvexPolygon(&Polygon, Color, X, Y);
    /* Describes a single 2D point */
    struct Point {
       int X;   /* X coordinate */
       int Y;   /* Y coordinate */
    };
    /* Describes a single 3D point in homogeneous coordinates */
    struct Point3 {
       double X;   /* X coordinate */
       double Y;   /* Y coordinate */
       double Z;   /* Z coordinate */
       double W;
    };
    /* Describes a series of points (used to store a list of vertices that
       describe a polygon; each vertex is assumed to connect to the two adjacent
       vertices, and the last vertex is assumed to connect to the first) */
       struct PointListHeader {
       int Length;                /* # of points */
       struct Point * PointPtr;   /* pointer to list of points */
    };
    /* Describes beginning and ending X coordinates of a single horizontal line */
    struct HLine {
       int XStart; /* X coordinate of leftmost pixel in line */
       int XEnd;   /* X coordinate of rightmost pixel in line */
    };
    /* Describes a Length-long series of horizontal lines, all assumed to be on
       contiguous scan lines starting at YStart and proceeding downward (describes
       a scan-converted polygon to low-level hardware-dependent drawing code) */
    struct HLineList {
       int Length;                /* # of horizontal lines */
       int YStart;                /* Y coordinate of topmost line */
       struct HLine * HLinePtr;   /* pointer to list of horz lines */
    };
    struct Rect { int Left, Top, Right, Bottom; };
    /* Structure describing one face of an object (one polygon) */
    struct Face {
       int * VertNums;   /* pointer to vertex ptrs */
       int NumVerts;     /* # of vertices */
       int Color;        /* polygon color */
    };
    /* Structure describing an object */
    struct Object {
       int NumVerts;
       struct Point3 * VertexList;
       struct Point3 * XformedVertexList;
       struct Point3 * ProjectedVertexList;
       struct Point * ScreenVertexList;
       int NumFaces;
       struct Face * FaceList;
    };
    extern void XformVec(double Xform[4][4], double * SourceVec, double * DestVec);
    extern void ConcatXforms(double SourceXform1[4][4],
       double SourceXform2[4][4], double DestXform[4][4]);
    extern void XformAndProjectPoly(double Xform[4][4],
       struct Point3 * Poly, int PolyLength, int Color);
    extern int FillConvexPolygon(struct PointListHeader *, int, int, int);
    extern void Set320x240Mode(void);
    extern void ShowPage(unsigned int StartOffset);
    extern void FillRectangleX(int StartX, int StartY, int EndX,
       int EndY, unsigned int PageBase, int Color);
    extern void XformAndProjectPoints(double Xform[4][4],struct Object * ObjectToXform);
    extern void DrawVisibleFaces(struct Object * ObjectToXform);
    extern void AppendRotationX(double XformToChange[4][4], double Angle);
    extern void AppendRotationY(double XformToChange[4][4], double Angle);
    extern void AppendRotationZ(double XformToChange[4][4], double Angle);
    extern int DisplayedPage, NonDisplayedPage;
    extern struct Rect EraseRect[];

### A Note on Rounding Negative Numbers

In the previous chapter, I added 0.5 and truncated in order to round values from floating-point to integer format. Here, in Listing 51.2, I’ve switched to adding 0.5 and using the floor() function. For positive values, the two approaches are equivalent; for negative values, only the floor() approach works properly.

### Object Representation

Each object consists of a list of vertices and a list of faces, with the vertices of each face defined by pointers into the vertex list; this allows each vertex to be transformed exactly once, even though several faces may share a single vertex. Each object contains the vertices not only in their original, untransformed state, but in three other forms as well: transformed to view space, transformed and projected to screen space, and converted to screen coordinates. Earlier, we saw that it can be convenient to store the screen coordinates within the object, so that if the object hasn’t moved with respect to the viewer, it can be redrawn without the need for recalculation, but why bother storing the view and screen space forms of the vertices as well?

The screen space vertices are useful for some sorts of hidden surface removal. For example, to determine whether two polygons overlap as seen by the viewer, you must first know how they look to the viewer, accounting for perspective; screen space provides that information. (So do the final screen coordinates, but with less accuracy, and without any Z information.) The view space vertices are useful for collision and proximity detection; screen space can’t be used here, because objects are distorted by the perspective projection into screen space. World space would serve as well as view space for collision detection, but because it’s possible to transform directly from object space to view space with a single matrix, it’s often preferable to skip over world space. It’s not mandatory that vertices be stored for all these different spaces, but the coordinates in all those spaces have to be calculated as intermediate steps anyway, so we might as well keep them around for those occasions when they’re needed.

Previous | Table of Contents | Next

Graphics Programming Black Book © 2001 Michael Abrash