---

zbf.c

Go to the documentation of this file.

/*
** -------------------------------------------------------------------
**
** zbf.c - Module to fill polygons in raster (image) coordinates
**         using the z-buffer algorithm.
**
** -------------------------------------------------------------------
*/

/*
** -------------------------------------------------------------------
** Global variables and definitions:
*/
#ifdef _UNIX_
#include <memory.h>    /* function memset */
#else
#include <string.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include "cd.h"
#include "zbf.h"

/*
** -------------------------------------------------------------------
** Local variables and definitions:
*/

#ifndef UINT_MAX
#define UINT_MAX      0xffffffff    /* maximum unsigned int value */
#endif

#ifndef MAX
#define MAX(a,b) (((a)>(b))?(a):(b))
#endif

#ifndef MIN
#define MIN(a,b) (((a)<(b))?(a):(b))
#endif

typedef struct {
  double x, y, z;
 } NscPnt;

static NscPnt *zbf_poly = NULL;

static int sizepoly = 0;

static int npolyverts = 0;

typedef struct {
  int    y_max;
  int    y_min;
  double xs;
  double dxs;
  double zs;
  double dzs;
 } Edge;

static Edge  *poly_edge = NULL;

typedef struct {
  int    x;
  double z;
 } Pixel;

static Pixel *scanline_vtx = NULL;

static long int curr_color;

static int cv_width;

static int cv_height;

/* Memory for z-buffer */
static unsigned *zbuff;


/*
** -------------------------------------------------------------------
** Local functions:
*/

/* =========================== zbfNSCtoRaster ======================== */
void zbfNSCtoRaster( double xnsc, double ynsc, double znsc,
                     int *xr, int *yr, unsigned *zr )
{
 double zconvfac = (double)((UINT_MAX-1)/2);

/*** COMPLETE HERE: 55 ***/

 *zr = (unsigned)(zconvfac * (1.0 - znsc));

 if     ( *xr < 0 )            *xr = 0;
 else if( *xr > cv_width-1 )   *xr = cv_width-1;
 if     ( *yr < 0 )            *yr = 0;
 else if( *yr > cv_height-1 )  *yr = cv_height-1;
 if     ( *zr < 0 )            *zr = 0;
 else if( *zr > UINT_MAX )     *zr = UINT_MAX;
}

/* =======================  zbfOrderIntersections  ====================== */

static void zbfOrderIntersections( Pixel *vtx, int left, int right )
{
 register int i, j;
 int mid;
 
 i = left;
 j = right;
 mid = vtx[(left + right) / 2].x;
 
 do
 {
  while( i < right && vtx[i].x < mid )
   i++;
  while( j > left && mid < vtx[j].x )
   j--;
  if( i <= j )
  {
   Pixel aux;

   aux = vtx[i];
   vtx[i] = vtx[j];
   vtx[j] = aux;
   i++;
   j--;
  }    
 } while( i <= j );
    
 if( left < j )
  zbfOrderIntersections( vtx, left, j );
 if( i < right )
  zbfOrderIntersections( vtx, i, right );
}

/* =========================  zbfScanLine  ======================== */
static void zbfScanLine( Pixel *vtx_lft, Pixel *vtx_rgt, int ys )
{
 unsigned int offset;
 int    xl = vtx_lft->x + 1; /* Step over first point */
 int    xr = vtx_rgt->x;   
 int    dx = vtx_rgt->x - vtx_lft->x;
 double z  = vtx_lft->z;
 double dz;
 
 if( dx == 0 )
  return;

 dz = (vtx_rgt->z - vtx_lft->z) / dx;
 z += dz; /* Step over first point */
 offset = (unsigned int)( cv_width * ys );

 while( xl <= xr )
 {
  if( z >= zbuff[offset+xl] )
  {    
   int x0 = xl;
   do
   {
    zbuff[offset+xl] = (unsigned)z;
    xl++;
    z += dz;
   } while( xl <= xr && z >= zbuff[offset+xl] );
   if( (xl-x0) == 1 )
    cdPixel( x0,  ys, curr_color );
   else
    cdLine( x0,  ys, xl-1, ys );
  }
  else
  {
   xl++;
   z += dz;
  }
 }
}

/* ========================  zbfMountEdges  ====================== */
static int zbfMountEdges( Edge *edge, int *ymin, int *ymax, 
                          int npoints, NscPnt *poly )
{
 int i, nedges = 0;
 int x0, y0;
 unsigned z0;

 zbfNSCtoRaster(poly[0].x, poly[0].y, poly[0].z, &x0, &y0, &z0);
 *ymin = y0;
 *ymax = y0;
 for( i = 0; i < npoints; i++ )
 {
  int j = (i+1)%npoints;
  int xi, yi;
  unsigned zi, zj;
  int xj, yj;

  zbfNSCtoRaster( poly[i].x, poly[i].y, poly[i].z, &xi, &yi, &zi );
  zbfNSCtoRaster( poly[j].x, poly[j].y, poly[j].z, &xj, &yj, &zj );

  if( yi != yj )
  {
   int dy = (yj - yi);
   edge[nedges].y_max = MAX(yi, yj);
   edge[nedges].y_min = MIN(yi, yj);
   edge[nedges].dxs = (double)(xj - xi) / dy;
   edge[nedges].dzs = (double)((double)zj - zi) / dy;
   if( edge[nedges].y_max == yi )
   {
    edge[nedges].xs = xi;
    edge[nedges].zs = zi;
   }
   else
   {
    edge[nedges].xs = xj;
    edge[nedges].zs = zj;
   }
   if( edge[nedges].y_max > *ymax )
    *ymax = edge[nedges].y_max;
   if( edge[nedges].y_min < *ymin )
    *ymin = edge[nedges].y_min;
   nedges++;
  }
 }
 return( nedges );
}

/* ========================  zbfMountInt  ======================== */
static int zbfMountInt( Pixel *vtx, Edge *edge, int *nedges, int ys )
{
 int i, ninters = 0;
 for( i = 0; i < *nedges; i++ )
 {
  /* delete from edge list */
  if( edge[i].y_min > ys )
  {
   edge[i] = edge[*nedges-1];
   *nedges = *nedges-1;
  }
  /* intersection */
  if( (ys >= edge[i].y_min) && (ys < edge[i].y_max) )
  {
   /* update xs for this scanline */
   edge[i].xs -= edge[i].dxs;
   vtx[ninters].x = (int)edge[i].xs;

   /* update zs for this scanline */
   edge[i].zs -= edge[i].dzs;
   vtx[ninters].z = edge[i].zs;

   ninters++;
  }
 } 
 return( ninters );
}

/* ========================  zbfFillPoly  ======================== */
static void zbfFillPoly( int npoints, NscPnt *poly )
{
 static int   old_npts = 0;     /* number of points of last call */
 int          ymin, ymax;       /* polygon limits */
 int          nedges;           /* number of edges */
 int          ys;               /* current y coordinate of scanline */
 int          ninters;          /* number of intersections of scanline */
 int          i;
 
/* Reallocation
 */
 if (npoints > old_npts)
 {
  old_npts = 0;
  if( scanline_vtx )
   free( scanline_vtx );
  if( poly_edge )
   free( poly_edge );
  scanline_vtx = (Pixel*)malloc( (npoints+1)*sizeof(Pixel) );
  poly_edge = (Edge*)malloc( (npoints+1)*sizeof(Edge) );
  if( !scanline_vtx || !poly_edge )
   return;
  old_npts = npoints;
 }

/* Mount edge table
 */
 nedges = zbfMountEdges( poly_edge, &ymin, &ymax, npoints, poly );

/* Paint scanlines
 */
 for( ys = ymax; ys >= ymin; ys-- )
 {
  /* Mount intersection vector for current scanline */
  ninters = zbfMountInt( scanline_vtx, poly_edge, &nedges, ys );

  /* Sort intersection vector */
  zbfOrderIntersections( scanline_vtx, 0, ninters-1 );

  /* Paint it */
  for( i = 0; i < ninters; i += 2 )
  {
   if( scanline_vtx[i].x < scanline_vtx[i+1].x )
   {
    zbfScanLine( &scanline_vtx[i], &scanline_vtx[i+1], ys );
   }
  }
 }
}

/* =======================  zbfRelease  ======================= */

static void zbfRelease( void )
{
 if( zbuff )
  free( zbuff );
 zbuff = NULL;

 if( zbf_poly )
  free( zbf_poly );
 zbf_poly = NULL;
 sizepoly = 0;
 npolyverts = 0;
}

/* =======================  zbfAlloc  ========================= */

static int zbfAlloc( void  )
{
 long int size = (long int)(cv_width*cv_height);

 zbfRelease( );

 zbuff = (unsigned *)calloc( size, sizeof(unsigned) );
 if( zbuff == NULL )
  return( 0 );

 sizepoly = 10;
 zbf_poly = (NscPnt *)calloc( sizepoly, sizeof(NscPnt) );

 return( 1 );
}


/*
** -------------------------------------------------------------------
** Public functions:
*/

/* =========================  zbfInit  ======================== */

int zbfInit( int w, int h )
{
 cv_width = w;
 cv_height = h;
 if( ! zbfAlloc( ) )
  return( 0 );

/* Clear zbuffer
 */
 memset( zbuff, 0, cv_width*cv_height*sizeof(unsigned) );

 return( 1 );
}

/* ========================  zbfClose  ======================== */

void zbfClose( void )
{
 zbfRelease( );
 cv_width = 0;
 cv_height = 0;
}

/* ======================  zbfBeginPoly  ====================== */

void zbfBeginPoly( long int color )
{
 if( ! zbuff )
  return;

 curr_color = color;
 cdForeground( curr_color );

 npolyverts = 0;
}

/* =======================  zbfVertex  ======================== */

void zbfVertex( double x, double y, double z )
{
 if( ! zbuff )
  return;

 if( npolyverts == sizepoly )
 {
  sizepoly *= 2;
  zbf_poly = (NscPnt *)realloc( zbf_poly, sizepoly * sizeof(NscPnt) );
 }

 zbf_poly[npolyverts].x = x;
 zbf_poly[npolyverts].y = y;
 zbf_poly[npolyverts].z = z;
 npolyverts++;
}

/* =======================  zbfEndPoly  ======================= */

void zbfEndPoly( void )
{
 int  i;

/* Verify whether one of the polygon vertex is outside 
 * the view volume.  If that is the case, reject the polygon.
 * This is necessary because the polygons are not being 
 * clipped against the view volume.
 * The z-buffer algorithm will not work for polygon points
 * outside the ranges of -1 to +1 of the normalize screen
 * coordinates.
 */
 for( i = 0; i < npolyverts; i++ )
 {
  if     ( zbf_poly[i].x < -1.0 )
   return;
  else if( zbf_poly[i].x >  1.0 )
   return;
  if     ( zbf_poly[i].y < -1.0 )
   return;
  else if( zbf_poly[i].y >  1.0 )
   return;
  if     ( zbf_poly[i].z < -1.0 )
   return;
  else if( zbf_poly[i].z >  1.0 )
   return;
 }

 zbfFillPoly( npolyverts, zbf_poly );
}

ew volume.
 * The z-buffer algorithm will not work for polygon points
 * outside the ranges of -1 to +1 of the normalize screen
 * coordinates.
 */
 for( i = 0; i < npolyverts; i++ )
 {
  if     ( zbf_poly[i].x < -1.0 )
   return;
  else if( zbf_poly[i].x >  1.0 )
   return;
  if     ( zbf_poly[i].y < -1.0 )
   return;
  else if( zbf_poly[i].y >  1.0 )
   return;
  if     ( zbf_poly[i].z < -1.0 )
   return;
  else if( zbf_poly[i].z >  1.0 )
   return;
 }

 zbfFillPoly( npolyverts, zbf_poly );
}

---