Google

Polygon rendering



void polygon3d(BITMAP *bmp, int type, BITMAP *texture, int vc, V3D *vtx[]);
void polygon3d_f(BITMAP *bmp, int type, BITMAP *texture, int vc, V3D_f *vtx[]);
Draw 3d polygons onto the specified bitmap, using the specified rendering mode. Unlike the regular polygon() function, these routines don't support concave or self-intersecting shapes, and they can't draw onto mode-X screen bitmaps (if you want to write 3d code in mode-X, draw onto a memory bitmap and then blit to the screen). The width and height of the texture bitmap must be powers of two, but can be different, eg. a 64x16 texture is fine, but a 17x3 one is not. The vertex count parameter (vc) should be followed by an array containing the appropriate number of pointers to vertex structures: polygon3d() uses the fixed point V3D structure, while polygon3d_f() uses the floating point V3D_f structure. These are defined as: 

   typedef struct V3D
   {
      fixed x, y, z;       - position
      fixed u, v;          - texture map coordinates
      int c;               - color
   } V3D;


   typedef struct V3D_f
   {
      float x, y, z;       - position
      float u, v;          - texture map coordinates
      int c;               - color
   } V3D_f;
How the vertex data is used depends on the rendering mode:

The x and y values specify the position of the vertex in 2d screen coordinates.

The z value is only required when doing perspective correct texture mapping, and specifies the depth of the point in 3d world coordinates.

The u and v coordinates are only required when doing texture mapping, and specify a point on the texture plane to be mapped on to this vertex. The texture plane is an infinite plane with the texture bitmap tiled across it. Each vertex in the polygon has a corresponding vertex on the texture plane, and the image of the resulting polygon in the texture plane will be mapped on to the polygon on the screen.

We refer to pixels in the texture plane as texels. Each texel is a block, not just a point, and whole numbers for u and v refer to the top-left corner of a texel. This has a few implications. If you want to draw a rectangular polygon and map a texture sized 32x32 on to it, you would use the texture coordinates (0,0), (0,32), (32,32) and (32,0), assuming the vertices are specified in anticlockwise order. The texture will then be mapped perfectly on to the polygon. However, note that when we set u=32, the last column of texels seen on the screen is the one at u=31, and the same goes for v. This is because the coordinates refer to the top-left corner of the texels. In effect, texture coordinates at the right and bottom on the texture plane are exclusive.

There is another interesting point here. If you have two polygons side by side sharing two vertices (like the two parts of folded piece of cardboard), and you want to map a texture across them seamlessly, the values of u and v on the vertices at the join will be the same for both polygons. For example, if they are both rectangular, one polygon may use (0,0), (0,32), (32,32) and (32,0), and the other may use (32,0), (32,32), (64,32), (64,0). This would create a seamless join.

Of course you can specify fractional numbers for u and v to indicate a point part-way across a texel. In addition, since the texture plane is infinite, you can specify larger values than the size of the texture. This can be used to tile the texture several times across the polygon.

The c value specifies the vertex color, and is interpreted differently by various rendering modes.

The type parameter specifies the polygon rendering mode, and can be any of the values:

POLYTYPE_FLAT:
A simple flat shaded polygon, taking the color from the c value of the first vertex. This polygon type is affected by the drawing_mode() function, so it can be used to render XOR or translucent polygons.

POLYTYPE_GCOL:
A single-color gouraud shaded polygon. The colors for each vertex are taken from the c value, and interpolated across the polygon. This is very fast, but will only work in 256 color modes if your palette contains a smooth gradient between the colors. In truecolor modes it interprets the color as a packed, display-format value as produced by the makecol() function.

POLYTYPE_GRGB:
A gouraud shaded polygon which interpolates RGB triplets rather than a single color. In 256 color modes this uses the global rgb_map table to convert the result to an 8 bit paletted color, so it must only be used after you have set up the RGB mapping table! The colors for each vertex are taken from the c value, which is interpreted as a 24 bit RGB triplet (0xFF0000 is red, 0x00FF00 is green, and 0x0000FF is blue).

POLYTYPE_ATEX:
An affine texture mapped polygon. This stretches the texture across the polygon with a simple 2d linear interpolation, which is fast but not mathematically correct. It can look ok if the polygon is fairly small or flat-on to the camera, but because it doesn't deal with perspective foreshortening, it can produce strange warping artifacts. To see what I mean, run test.exe and see what happens to the polygon3d() test when you zoom in very close to the cube.

POLYTYPE_PTEX:
A perspective-correct texture mapped polygon. This uses the z value from the vertex structure as well as the u/v coordinates, so textures are displayed correctly regardless of the angle they are viewed from. Because it involves division calculations in the inner texture mapping loop, this mode is a lot slower than POLYTYPE_ATEX, and it uses floating point so it will be very slow on anything less than a Pentium (even with an FPU, a 486 can't overlap floating point division with other integer operations like the Pentium can).

POLYTYPE_ATEX_MASK:
POLYTYPE_PTEX_MASK:
Like POLYTYPE_ATEX and POLYTYPE_PTEX, but zero texture map pixels are skipped, allowing parts of the texture map to be transparent.

POLYTYPE_ATEX_LIT:
POLYTYPE_PTEX_LIT:
Like POLYTYPE_ATEX and POLYTYPE_PTEX, but the global color_map table (for 256 color modes) or blender function (for non-MMX truecolor modes) is used to blend the texture with a light level taken from the c value in the vertex structure. This must only be used after you have set up the color mapping table or blender functions!

POLYTYPE_ATEX_MASK_LIT:
POLYTYPE_PTEX_MASK_LIT:
Like POLYTYPE_ATEX_LIT and POLYTYPE_PTEX_LIT, but zero texture map pixels are skipped, allowing parts of the texture map to be transparent.

POLYTYPE_ATEX_TRANS:
POLYTYPE_PTEX_TRANS:
Render translucent textures. All the general rules for drawing translucent things apply. However, these modes have a major limitation: they only work with memory bitmaps or linear frame buffers (not with banked frame buffers). Don't even try, they do not check and your program will die horribly (or at least draw wrong things).

POLYTYPE_ATEX_MASK_TRANS:
POLYTYPE_PTEX_MASK_TRANS:
Like POLYTYPE_ATEX_TRANS and POLYTYPE_PTEX_TRANS, but zero texture map pixels are skipped.

If the CPU_MMX flag of the cpu_capabilities global variable is set, the GRGB and truecolor *LIT routines will be optimised using MMX instructions. If the CPU_3DNOW flag is set, the truecolor PTEX*LIT routines will take advantage of the 3DNow! CPU extensions.

Using MMX for *LIT routines has a side effect: normally (without MMX), these routines use the blender functions used also for other lighting functions, set with set_trans_blender() or set_blender_mode(). The MMX versions only use the RGB value passed to set_trans_blender() and do the linear interpolation themselves. Therefore a new set of blender functions passed to set_blender_mode() is ignored.

void triangle3d(BITMAP *bmp, int type, BITMAP *tex, V3D *v1, *v2, *v3);
void triangle3d_f(BITMAP *bmp, int type, BITMAP *tex, V3D_f *v1, *v2, *v3);
Draw 3d triangles, using either fixed or floating point vertex structures. Unlike quad3d[_f], triangle3d[_f] functions are not wrappers of polygon3d[_f]. The triangle3d[_f] functions use their own routines taking into account the constantness of the gradients. Therefore triangle3d[_f](bmp, type, tex, v1, v2, v3) is faster than polygon3d[_f](bmp, type, tex, 3, v[]).

void quad3d(BITMAP *bmp, int type, BITMAP *tex, V3D *v1, *v2, *v3, *v4);
void quad3d_f(BITMAP *bmp, int type, BITMAP *tex, V3D_f *v1, *v2, *v3, *v4);
Draw 3d quads, using either fixed or floating point vertex structures. These are equivalent to calling polygon3d(bmp, type, tex, 4, v[]); or polygon3d_f(bmp, type, tex, 4, v[]);

int clip3d_f(int type, float min_z, float max_z, int vc, const V3D_f *vtx[], V3D_f *vout[], V3D_f *vtmp[], int out[]);
Clips the polygon given in vtx. The number of vertices is vc, the result goes in vout, and vtmp and out are needed for internal purposes. The pointers in vtx, vout and vtmp must point to valid V3D_f structures. As additional vertices may appear in the process of clipping, so the size of vout, vtmp and out should be at least vc * (1.5 ^ n), where n is the number of clipping planes (5 or 6), and '^' denotes "to the power of". The frustum (viewing volume) is defined by -z<x<z, -z<y<z, 0<min_z<z<max_z. If max_z<=min_z, the z<max_z clipping is not done. As you can see, clipping is done in the camera space, with perspective in mind, so this routine should be called after you apply the camera matrix, but before the perspective projection. The routine will correctly interpolate u, v, and c in the vertex structure. However, no provision is made for high/truecolor GCOL.

int clip3d(int type, fixed min_z, fixed max_z, int vc, const V3D *vtx[], V3D *vout[], V3D *vtmp[], int out[]);
Fixed point version of clip3d_f(). This function should be used with caution, due to the limited precision of fixed point arithmetic and high chance of rounding errors: the floating point code is better for most situations.

A Z-buffer stores the depth of each pixel that is drawn on a viewport. When a 3D object is rendered, the depth of each of its pixels is compared against the value stored into the Z-buffer: if the pixel is closer it is drawn, otherwise it is skipped.

No polygon sorting is needed. However, backface culling should be done because it prevents many invisible polygons being compared against the Z-buffer. Z-buffered rendering is the only algorithm supported by Allegro that directly solves penetrating shapes (see example exzbuf.c, for instance). The price to pay is more complex (and slower) routines.

Z-buffered polygons are designed as an extension of the normal POLYTYPE_* rendering styles. Just OR the POLYTYPE with the value POLYTYPE_ZBUF, and the normal polygon3d(), polygon3d_f(), quad3d(), etc. functions will render z-buffered polygons.

Example: 

   polygon3d(bmp, POLYTYPE_ATEX | POLYTYPE_ZBUF, tex, vc, vtx);

Of course, the z coordinates have to be valid regardless of rendering style.

A Z-buffered rendering procedure looks like a double-buffered rendering procedure. You should follow four steps: create a Z-buffer at the beginning of the program and make the library use it by calling set_zbuffer(). Then, for each frame, clear the Z-buffer and draw polygons with POLYTYPE_* | POLYTYPE_ZBUF and finally destroy the Z-buffer when leaving the program.

Notes on Z-buffered renderers:

  • Unlike the normal POLYTYPE_FLAT renderers, the Z-buffered ones don't use the hline() routine. Therefore DRAW_MODE has no effect.

  • The *LIT* routines work the traditional way - through the set of blender routines.

  • All the Z-buffered routines are much slower than their normal counterparts (they all use the FPU to interpolate and test 1/z values).

ZBUFFER *create_zbuffer(BITMAP *bmp);
Creates a Z-buffer using the size of the BITMAP you are planning to draw on. Several Z-buffers can be defined but only one can be used at the same time, so you must call set_zbuffer() to make this Z-buffer active.

ZBUFFER *create_sub_zbuffer(ZBUFFER *parent, int x, int y, int width, int height);
Creates a sub-z-buffer, ie. a z-buffer sharing drawing memory with a pre-existing z-buffer, but possibly with a different size. The same rules as for sub-bitmaps apply: the sub-z-buffer width and height can extend beyond the right and bottom edges of the parent (they will be clipped), but the origin point must lie within the parent region.

When drawing z-buffered to a bitmap, the top left corner of the bitmap is always mapped to the top left corner of the current z-buffer. So this function is primarily useful if you want to draw to a sub-bitmap and use the corresponding sub-area of the z-buffer. In other cases, eg. if you just want to draw to a sub-bitmap of screen (and not to other parts of screen), then you would usually want to create a normal z-buffer (not sub-z-buffer) the size of the visible screen. You don't need to first create a z-buffer the size of the virtual screen and then a sub-z-buffer of that.

void set_zbuffer(ZBUFFER *zbuf);
Makes the given Z-buffer be the active one. This should have been previously created with create_zbuffer().

void clear_zbuffer(ZBUFFER *zbuf, float z);
Writes z into the given Z-buffer (0 means far away). This function should be used to initialize the Z-buffer before each frame. Actually, low-level routines compare depth of the current pixel with 1/z: for example, if you want to clip polygons farther than 10, you must call clear_zbuffer(zbuf, 0.1);

void destroy_zbuffer(ZBUFFER *zbuf);
Destroys the Z-buffer when you are finished with it.

Allegro provides two simple approaches to remove hidden surfaces:

  • Z-buffering - (see above)

  • Scan-line algorithms - along each scanline on your screen, you keep track of what polygons you are "in" and which is the nearest. This status changes only where the scanline crosses some polygon edge. So you have to juggle an edge list and a polygon list. And you have to sort the edges for each scanline (this can be countered by keeping the order of the previous scanline - it won't change much). The BIG advantage is that you write each pixel only once. If you have a lot of overlapping polygons you can get incredible speeds compared to any of the previous algorithms. This algorithm is covered by the *_scene routines.


The scene rendering has approximately the following steps:

  • Initialize the scene (set the clip area, clear the bitmap, blit a background, etc.)

  • Call clear_scene().

  • Transform all your points to camera space.

  • Clip polygons.

  • Project with persp_project() or persp_project_f().

  • "Draw" polygons with scene_polygon3d() and/or scene_polygon3d_f(). This doesn't do any actual drawing, only initializes tables.

  • Render all the polygons defined previously to the bitmap with render_scene().

  • Overlay some non-3D graphics.

  • Show the bitmap (blit it to screen, flip the page, etc).


For each horizontal line in the viewport an x-sorted edge list is used to keep track of what polygons are "in" and which is the nearest. Vertical coherency is used - the edge list for a scanline is sorted starting from the previous one - it won't change much. The scene rendering routines use the same low-level asm routines as normal polygon3d().

Notes on scene rendering:

  • Unlike polygon3d(), scene_polygon3d() requires valid z coordinates for all vertices, regardless of rendering style (unlike polygon3d(), which only uses z coordinate for *PTEX*).

  • All polygons passed to scene_polygon3d() have to be persp_project()'ed.

  • After render_scene() the mode is reset to SOLID.

Using a lot of *MASK* polygons drastically reduces performance, because when a MASKed polygon is the first in line of sight, the polygons underneath have to be drawn too. The same applies to FLAT polygons drawn with DRAW_MODE_TRANS.

Z-buffered rendering works also within the scene renderer. It may be helpful when you have a few intersecting polygons, but most of the polygons may be safely rendered by the normal scanline sorting algo. Same as before: just OR the POLYTYPE with POLYTYPE_ZBUF. Also, you have to clear the z-buffer at the start of the frame. Example: 

   clear_scene(buffer);
   if (some_polys_are_zbuf) clear_zbuffer(0.);
   while (polygons) {
      ...
      if (this_poly_is_zbuf) type |= POLYTYPE_ZBUF;
      scene_polygon3d(type, tex, vc, vtx);
   }
   render_scene();

int create_scene(int nedge, int npoly);
Allocates memory for a scene, nedge and npoly are your estimates of how many edges and how many polygons you will render (you cannot get over the limit specified here). If you use same values in succesive calls, the space will be reused (no new malloc()).

The memory allocated is a little less than 150 * (nedge + npoly) bytes. Returns zero on success, or a negative number if allocations fail.

void clear_scene(BITMAP *bmp);
Initializes a scene. The bitmap is the bitmap you will eventually render on.

void destroy_scene();
Deallocate memory previously allocated by create_scene.

int scene_polygon3d(int type, BITMAP *texture, int vc, V3D *vtx[]);
int scene_polygon3d_f(int type, BITMAP *texture, int vc, V3D_f *vtx[]);
Puts a polygon in the rendering list. Nothing is really rendered at this moment. Should be called between clear_scene() and render_scene().

Arguments are the same as for polygon3d(), except the bitmap is missing. The one passed to clear_scene() will be used.

Unlike polygon3d(), the polygon may be concave or self-intersecting. Shapes that penetrate one another may look OK, but they are not really handled by this code.

Note that the texture is stored as a pointer only, and you should keep the actual bitmap around until render_scene(), where it is used.

Since the FLAT style is implemented with the low-level hline() funtion, the FLAT style is subject to DRAW_MODEs. All these modes are valid. Along with the polygon, this mode will be stored for the rendering moment, and also all the other related variables (color_map pointer, pattern pointer, anchor, blender values).

The settings of the CPU_MMX and CPU_3DNOW flags of the cpu_capabilities global variable on entry in this routine affect the choice of low-level asm routine that will be used by render_scene() for this polygon.

Returns zero on success, or a negative number if it won't be rendered for lack of a rendering routine.

void render_scene();
Renders all the specified scene_polygon3d()'s on the bitmap passed to clear_scene(). Rendering is done one scanline at a time, with no pixel being processed more than once.

Note that between clear_scene() and render_scene() you shouldn't change the clip rectangle of the destination bitmap. For speed reasons, you should set the clip rectangle to the minimum.

Note also that all the textures passed to scene_polygon3d() are stored as pointers only and actually used in render_scene().

extern float scene_gap;
This number (default value = 100.0) controls the behaviour of the z-sorting algorithm. When an edge is very close to another's polygon plane, there is an interval of uncertainty in which you cannot tell which object is visible (which z is smaller). This is due to cumulative numerical errors for edges that have undergone a lot of transformations and interpolations.

The default value means that if the 1/z values (in projected space) differ by only 1/100 (one percent), they are considered to be equal and the x-slopes of the planes are used to find out which plane is getting closer when we move to the right.

Larger values means narrower margins, and increasing the chance of missing true adjacent edges/planes. Smaller values means larger margins, and increasing the chance of mistaking close polygons for adjacent ones. The value of 100 is close to the optimum. However, the optimum shifts slightly with resolution, and may be application-dependent. It is here for you to fine-tune.