zbf.cpp

Go to the documentation of this file.

/*
** -------------------------------------------------------------------
**
** zbf.cpp - Class 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"

/*
** ---------------------------------------------------------------
** Initialization of class variables:
*/
cdCanvas* Zbf::canvas = NULL;

Zbf::NscPnt* Zbf::poly = NULL;

int Zbf::sizepoly = 0;

int Zbf::npolyverts = 0;

Zbf::Edge* Zbf::poly_edge = NULL;

Zbf::Pixel* Zbf::scanline_vtx = NULL;

long int Zbf::curr_color = 0x0L;

int Zbf::cv_width = 100;

int Zbf::cv_height = 100;

/* Memory for z-buffer */
unsigned int* Zbf::zbuff = NULL;

/*
** ---------------------------------------------------------------
** Private class functions:
*/
/* =========================== Zbf::NSCtoRaster ======================== */

void Zbf::NSCtoRaster( double xnsc, double ynsc, double znsc,
                       int* xr, int* yr, unsigned int* zr )
{
 double zconvfac = (double)((UINT_MAX-1)/2);
 // UINT_MAX is the maximum unsigned int value

/*** COMPLETE AQUI: ZBF-01 ***/


/*** COMPLETE AQUI: ZBF-01 ***/
 *zr = (unsigned int)(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;
}

/* =======================  Zbf::OrderIntersections  ====================== */

void Zbf::OrderIntersections( Zbf::Pixel* vtx, int left, int right )
{
 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 )
  OrderIntersections( vtx, left, j );
 if( i < right )
  OrderIntersections( vtx, i, right );
}

/* =========================  Zbf::ScanLine  ======================== */

void Zbf::ScanLine( Zbf::Pixel* vtx_lft, Zbf::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 int)z;
    xl++;
    z += dz;
   } while( xl <= xr && z >= zbuff[offset+xl] );
   if( (xl-x0) == 1 )
    cdCanvasPixel( canvas, x0,  ys, curr_color );
   else
    cdCanvasLine( canvas, x0,  ys, xl-1, ys );
  }
  else
  {
   xl++;
   z += dz;
  }
 }
}

/* ========================  Zbf::MountEdges  ====================== */

int Zbf::MountEdges( Zbf::Edge* edge, int* ymin, int* ymax, 
                     int npoints, Zbf::NscPnt *poly )
{
 int i, nedges = 0;
 int x0, y0;
 unsigned int z0;

 NSCtoRaster(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 int zi, zj;
  int xj, yj;

  NSCtoRaster( poly[i].x, poly[i].y, poly[i].z, &xi, &yi, &zi );
  NSCtoRaster( 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 );
}

/* ========================  Zbf::MountInt  ======================== */

int Zbf::MountInt( Zbf::Pixel* vtx, Zbf::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 );
}

/* ========================  Zbf::FillPoly  ======================== */

void Zbf::FillPoly( int npoints, Zbf::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 = MountEdges( poly_edge, &ymin, &ymax, npoints, poly );

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

  /* Order intersection vector from left to right */
  OrderIntersections( scanline_vtx, 0, ninters-1 );

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

/* =======================  Zbf::Release  ======================= */

void Zbf::Release( void )
{
 if( zbuff )
  free( zbuff );
 zbuff = NULL;

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

/* =======================  Zbf::Alloc  ========================= */

int Zbf::Alloc( void  )
{
 long int size = (long int)(cv_width*cv_height);

 Release( );

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

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

 return( 1 );
}


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

/* =========================  Zbf::Init  ======================== */

int Zbf::Init( cdCanvas* cv )
{
 canvas = cv;

 cdCanvasGetSize( canvas, &cv_width, &cv_height, 0L, 0L );

 if( ! Alloc( ) )
  return( 0 );

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

 return( 1 );
}

/* ========================  Zbf::Close  ======================== */

void Zbf::Close( void )
{
 Release( );
 cv_width = 0;
 cv_height = 0;
}

/* ======================  Zbf::BeginPoly  ====================== */

void Zbf::BeginPoly( long int color )
{
 if( ! zbuff )
  return;

 curr_color = color;
 cdCanvasForeground( canvas, curr_color );

 npolyverts = 0;
}

/* =======================  Zbf::Vertex  ======================== */

void Zbf::Vertex( double x, double y, double z )
{
 if( ! zbuff )
  return;

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

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

/* =======================  Zbf::EndPoly  ======================= */

void Zbf::EndPoly( 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     ( poly[i].x < -1.0 )
   return;
  else if( poly[i].x >  1.0 )
   return;
  if     ( poly[i].y < -1.0 )
   return;
  else if( poly[i].y >  1.0 )
   return;
  if     ( poly[i].z < -1.0 )
   return;
  else if( poly[i].z >  1.0 )
   return;
 }

 FillPoly( npolyverts, poly );
}

---