home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / graphtal / z_buffer.c < prev    next >
C/C++ Source or Header  |  1992-10-20  |  8KB  |  329 lines
  1. /*
  2.  * Z_Buffer.C - zBuffer implementation for concave polygons.
  3.  *
  4.  * Copyright (C) 1992, Christoph Streit (streit@iam.unibe.ch)
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  */
  17.  
  18. #include <values.h>
  19. #include "Z_Buffer.h"
  20.  
  21. //___________________________________________________________ EdgeElement
  22.  
  23. struct EdgeElement {
  24.   real x;
  25.   real z;
  26. };
  27.  
  28. declareList(EdgeList, EdgeElement);
  29. implementList(EdgeList, EdgeElement);
  30.  
  31. //___________________________________________________________ Z_Buffer
  32.  
  33. Z_Buffer::Z_Buffer(ViewTransform* v, const rcString& msg, const rcString& oname)
  34. : view(v), remark(msg), ymin(resY), ymax(0), numPrimitives(0)
  35. {
  36.   resY = view->getResY();
  37.   resX = view->getResX(); 
  38.  
  39.   /*
  40.    * Create the yBuckets.
  41.    */
  42.   yBuckets = new EdgeList*[resY];
  43.   for (register int i=0; i<resY; i++) 
  44.     yBuckets[i] = new EdgeList(2);
  45.  
  46.   /*
  47.    * Create and initialize z-Buffer array.
  48.    */
  49.   zBuffer = new float[resY*resX];
  50.   for (i=0; i<resY*resX; i++)
  51.     zBuffer[i] = MAXFLOAT;
  52.  
  53.   /*
  54.    * Create and initialize pixmap.
  55.    */
  56.   pixmap = new unsigned char[resY*resX*3];
  57.   memset(pixmap, 0, resY*resX*3);
  58.  
  59.   /*
  60.    * Attach stream to outfile.
  61.    */
  62.   if (oname == "cout")
  63.     outfile = stdout;
  64.   else
  65.     outfile = fopen((const char*) oname, "w");
  66.  
  67.   if (outfile == NULL)
  68.     Error(ERR_PANIC, "can't open file " + oname);
  69. }
  70.   
  71. Z_Buffer::~Z_Buffer()
  72. {
  73.   delete view;
  74.   delete [] zBuffer;
  75.   delete [] pixmap;
  76.   for (register int i=0; i<resY; i++)
  77.     delete yBuckets[i];
  78.   delete [] yBuckets;
  79. }
  80.  
  81. void Z_Buffer::renderTriangle(const Color& color, const Vector& p1, 
  82.                   const Vector& p2, const Vector& p3)
  83. {
  84.   numPrimitives++;
  85.  
  86.   Vector tp1 = view->transformWorld2View(p1);
  87.   Vector tp2 = view->transformWorld2View(p2);
  88.   Vector tp3 = view->transformWorld2View(p3);
  89.  
  90.   /*
  91.    * Front plane clipping (z=0).
  92.    */
  93.   if (tp1[2] < 0 || tp2[2] < 0 || tp3[2] < 0)
  94.     return;
  95.  
  96.   Vector normal = (tp2-tp1)*(tp3-tp1);
  97.   if (!normal.normalize())
  98.     return;
  99.  
  100.   Vector lightVector = (tp1+tp2+tp3)/3;
  101.   calculateColor(color, normal, lightVector);
  102.  
  103.   tp1 = view->transformView2Screen(tp1);
  104.   tp2 = view->transformView2Screen(tp2);
  105.   tp3 = view->transformView2Screen(tp3);
  106.  
  107.   addEdge(tp1, tp2);
  108.   addEdge(tp2, tp3);
  109.   addEdge(tp3, tp1);
  110.  
  111.   render();
  112. }
  113.  
  114. void Z_Buffer::renderRectangle(const Color& color, const Vector& p1, const Vector& p2, 
  115.                    const Vector& p3, const Vector& p4)
  116. {
  117.   numPrimitives++;
  118.  
  119.   Vector tp1 = view->transformWorld2View(p1);
  120.   Vector tp2 = view->transformWorld2View(p2);
  121.   Vector tp3 = view->transformWorld2View(p3);
  122.   Vector tp4 = view->transformWorld2View(p4);
  123.  
  124.   /*
  125.    * Front plane clipping (z=0).
  126.    */
  127.   if (tp1[2] < 0 || tp2[2] < 0 || tp3[2] < 0 || tp4[2] < 0)
  128.     return;
  129.  
  130.   Vector normal = (tp2-tp1)*(tp4-tp1);
  131.   if (!normal.normalize())
  132.     return;
  133.  
  134.   Vector lightVector = (tp1+tp2+tp3+tp4)/4;
  135.   calculateColor(color, normal, lightVector);
  136.  
  137.   tp1 = view->transformView2Screen(tp1);
  138.   tp2 = view->transformView2Screen(tp2);
  139.   tp3 = view->transformView2Screen(tp3);
  140.   tp4 = view->transformView2Screen(tp4);
  141.  
  142.   addEdge(tp1, tp2);
  143.   addEdge(tp2, tp3);
  144.   addEdge(tp3, tp4);
  145.   addEdge(tp4, tp1);
  146.  
  147.   render();
  148. }
  149.  
  150. void Z_Buffer::renderPolygon(const Color& color, Polygon* p)
  151. {
  152.   numPrimitives++;
  153.  
  154.   /*
  155.    * Degenerate polygon?
  156.    */
  157.   if (p->numVertices() < 3)
  158.     return;
  159.  
  160.   /*
  161.    * Transform polygon to view space.
  162.    */
  163.   p->transform(view->getViewmat());
  164.  
  165.   /*
  166.    * Front plane clipping (z=0).
  167.    */
  168.   for (register long i=0; i<p->numVertices(); i++) 
  169.     if (p->vertex(i)[2] < 0)
  170.       return;
  171.  
  172.   Vector normal = p->normal();
  173.   if (normal.zero())
  174.     return;
  175.  
  176.   Vector lightVector;
  177.   for (i=0; i<p->numVertices(); i++)
  178.     lightVector += p->vertex(i);
  179.   lightVector /= p->numVertices();
  180.  
  181.   calculateColor(color, normal, lightVector);
  182.  
  183.   /*
  184.    * Add each edge of the polygon in the y-bucket structure.
  185.    */
  186.   Vector p1 = view->transformView2Screen(p->vertex(0));
  187.   Vector p2;
  188.   for (i=1; i<p->numVertices(); i++) {
  189.     p2 = view->transformView2Screen(p->vertex(i));
  190.     addEdge(p1, p2);
  191.     p1 = p2;
  192.   }
  193.   p2 = view->transformView2Screen(p->vertex(0));
  194.   addEdge(p1, p2);
  195.  
  196.   render();
  197.   delete p;
  198. }
  199.  
  200. void Z_Buffer::writePixmap()
  201. {
  202.   fprintf(outfile, "P6\n");
  203.   fprintf(outfile, "#%s\n", (const char*) remark);
  204.   fprintf(outfile, "%d\n%d\n255\n", resX, resY);
  205.   fwrite((char*)pixmap, resX*resY*3, 1, outfile);
  206.   fclose(outfile);
  207. }
  208.  
  209. void Z_Buffer::addEdge(const Vector& p1, const Vector& p2)
  210. {
  211.   const Vector& start = (p1[1] <= p2[1]) ? p1 : p2;
  212.   const Vector& end   = (p1[1] <= p2[1]) ? p2 : p1;
  213.  
  214.   int y1 = (int)(start[1]);
  215.   int y2 = (int)(end[1]);
  216.  
  217.   /*
  218.    * Horizontal edge, do nothing.
  219.    */
  220.   if (y1 == y2)
  221.     return;
  222.  
  223.   if (y1 < ymin) ymin = y1;
  224.   if (y2 > ymax) ymax = y2;
  225.  
  226.   /*
  227.    * Set up increments.
  228.    */
  229.   real x = start[0];
  230.   real z = start[2];
  231.   real denom = 1/(end[1]-start[1]);
  232.   real dx = (end[0]-x)*denom;
  233.   real dz = (end[2]-z)*denom;
  234.  
  235.   EdgeElement edgeElement;
  236.  
  237.   for (register int y=y1; y<y2; y++, x+=dx, z+=dz) {
  238.  
  239.     /*
  240.      * No clipping is done, so we have to check for out of screen space.
  241.      */
  242.     if (y<0) continue;
  243.     if (y>=resY) break;
  244.  
  245.     /*
  246.      * Create new EdgeElement entry in the Edgelist sorted by x.
  247.      */
  248.     edgeElement.x = x;
  249.     edgeElement.z = z;
  250.     register long i=0;
  251.     while (1) {
  252.       if (i>=yBuckets[y]->count()) {
  253.     yBuckets[y]->append(edgeElement);
  254.     break;
  255.       }
  256.       if (yBuckets[y]->item(i).x > x) {
  257.     yBuckets[y]->insert(i, edgeElement);
  258.     break;
  259.       }
  260.       i++;
  261.     }
  262.   }
  263. }
  264.  
  265. void Z_Buffer::render()
  266. {
  267.   int x1, x2, offset;
  268.   real dx, dz, z;
  269.   unsigned char* pixmapPos;
  270.  
  271.   if (ymin < 0)    ymin = 0;
  272.   if (ymax > resY) ymax = resY;
  273.  
  274.   for (register int y=ymin; y < ymax; y++) {
  275.     EdgeList* yBucket = yBuckets[y];
  276.  
  277.     offset = (resY-y)*resY;
  278.     for (register long i=0; i < yBucket->count(); i+=2) {
  279.       x1 = (int)(yBucket->item(i).x);
  280.       x2 = (int)(yBucket->item(i+1).x);
  281.  
  282.       if (x1 != x2) {
  283.     dx = yBucket->item(i+1).x - yBucket->item(i).x;
  284.     dz = (yBucket->item(i+1).z - yBucket->item(i).z)/dx;
  285.     z  = yBucket->item(i).z + (yBucket->item(i).x-x1)*dz; 
  286.  
  287.     for (register int x=x1; x < x2; x++) {
  288.       if (x >= 0 && x < resX) {
  289.         pixmapPos = pixmap + 3*(offset+x);
  290.         if (z < zBuffer[offset+x]) {
  291.           zBuffer[offset+x] = z;
  292.           *pixmapPos++ = (unsigned char)(R*255);
  293.           *pixmapPos++ = (unsigned char)(G*255);
  294.           *pixmapPos   = (unsigned char)(B*255);
  295.         }
  296.       }
  297.       z += dz;
  298.     }
  299.       }
  300.     }
  301.     yBucket->remove_all();
  302.   }
  303.  
  304.   ymin = resY;
  305.   ymax = 0;
  306. }
  307.  
  308. void Z_Buffer::calculateColor(const Color& color, const Vector& normal, const Vector& p)
  309. {
  310.   /*
  311.    * we don't do back face culling, so take absolute value of dot(light,normal).
  312.    *  our light sits at (0,0,0) = eye point (=> light vector = (0,0,0) - p)
  313.    */
  314.   Vector toEye = -p; toEye.normalize();
  315.   float intensity = fabs(toEye^normal);
  316.   
  317.   /*
  318.    * we don't calculate the intensity vor each vertex and take an 
  319.    *  average intensity => as a result the color ist usually too dark
  320.    *                    => add an ambient term.
  321.    */
  322.   intensity += 0.25; // add an ambient term, because intenisty
  323.   if (intensity>1) intensity = 1;
  324.  
  325.   R = color.r()*intensity;
  326.   G = color.g()*intensity;
  327.   B = color.b()*intensity;
  328. }
  329.