home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / libs / tsipp / tsipp.lha / tsipp3.0a / sippsrc / rendering.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-02  |  49.0 KB  |  1,706 lines
  1. /**
  2.  ** sipp - SImple Polygon Processor
  3.  **
  4.  **  A general 3d graphic package
  5.  **
  6.  **  Copyright Equivalent Software HB  1992
  7.  **
  8.  ** This program is free software; you can redistribute it and/or modify
  9.  ** it under the terms of the GNU General Public License as published by
  10.  ** the Free Software Foundation; either version 1, or any later version.
  11.  ** This program is distributed in the hope that it will be useful,
  12.  ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.  ** GNU General Public License for more details.
  15.  ** You can receive a copy of the GNU General Public License from the
  16.  ** Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17.  **/
  18.  
  19. /**
  20.  ** rendering.c - Functions that handles rendering of the scene.
  21.  **/
  22.  
  23. #include <stdio.h>
  24. #include <sys/types.h>
  25. #ifndef NOMEMCPY
  26. #include <memory.h>
  27. #endif
  28.  
  29. #include <xalloca.h>
  30. #include <smalloc.h>
  31.  
  32. #include <lightsource.h>
  33. #include <geometric.h>
  34. #include <rendering.h>
  35. #include <pixel.h>
  36. #include <objects.h>
  37. #include <sipp.h>
  38. #include <sipp_bitmap.h>
  39. #include <viewpoint.h>
  40.  
  41.  
  42. char *SIPP_VERSION = "3.0";
  43.  
  44. /*
  45.  * Static global variables.
  46.  */
  47. static bool          show_backfaces;  /* Don't do backface culling */
  48. static bool          shadows;         /* Calculate shadows */
  49. static bool          reverse_scan;    /* Render scan lines in reverse */
  50. static Edge        **y_bucket;        /* Y-bucket for edge lists. */
  51. static FILE         *image_file;      /* File to store image in      */
  52.                                       /* when rendering into a file. */
  53. static void        (*pixel_set)();    /* Pointer to function for setting  */
  54.                                       /* a pixel when rendering with user */
  55.                                       /* defined function.                */
  56. static void         *im_data;         /* Data to pixel_set() */
  57.  
  58.        int           depthmap_size;   /* Size of the depthmaps */
  59.  
  60.  
  61. /*
  62.  * Stack of transformation matrices used
  63.  * when traversing an object hierarchy.
  64.  */
  65. static struct tm_stack_t {
  66.     Transf_mat         mat;
  67.     struct tm_stack_t *next;
  68. } *tm_stack;
  69.  
  70. static Transf_mat      curr_mat;     /* Current transformation matrix */
  71.  
  72.  
  73.  
  74. /*
  75.  * Calculate the normal vector for all polygons in the polygon list PSTART.
  76.  *
  77.  * Check if the polygon is backfacing with respect to the current
  78.  * viewpoint.
  79.  *
  80.  * The normalized normal is added to a normal kept at each vertex
  81.  * in the polygon. This will produce, at each vertex, an average of the
  82.  * normals of the adjectent plygons.
  83.  */
  84. static void
  85. calc_normals(pstart, eyepoint)
  86.     Polygon *pstart;    /* Head of polygon list */
  87.     Vector   eyepoint;  /* Viewpoint transformed to local coordinate system */
  88. {
  89.     Polygon    *polyref;
  90.     Vertex    **vlist;
  91.     Vector      normal;
  92.     int         i, j;
  93.     double      plane_const;
  94.  
  95.  
  96.     for (polyref = pstart; polyref != NULL; polyref = polyref->next) {
  97.  
  98.         vlist = polyref->vertex;
  99.         MakeVector(normal, 0.0, 0.0, 0.0);
  100.  
  101.         for (i = 0; i < polyref->nvertices; i++) {
  102.             j = (i + 1) % polyref->nvertices;
  103.             normal.x += ((vlist[i]->pos.y - vlist[j]->pos.y)
  104.                          * (vlist[i]->pos.z + vlist[j]->pos.z));
  105.             normal.y += ((vlist[i]->pos.z - vlist[j]->pos.z)
  106.                          * (vlist[i]->pos.x + vlist[j]->pos.x));
  107.             normal.z += ((vlist[i]->pos.x - vlist[j]->pos.x)
  108.                          * (vlist[i]->pos.y + vlist[j]->pos.y));
  109.         }
  110.         vecnorm(&normal);
  111.  
  112.         /*
  113.          * Take care of backfacing polygons.
  114.          */
  115.         plane_const = VecDot(normal, vlist[0]->pos);
  116.         if (VecDot(eyepoint, normal) - plane_const <= 0.0) {
  117.             if (show_backfaces) {
  118.                 polyref->backface = FALSE;
  119.                 VecNegate(normal);
  120.             } else {
  121.                 polyref->backface = TRUE;
  122.             }
  123.         } else {
  124.             polyref->backface = FALSE;
  125.         }
  126.             
  127.         /*
  128.          * Add the calculated normal to all vertices
  129.          * in the poygon. This will result in an avaraged normal
  130.          * at each vertex after all polygons have been processed.
  131.          */
  132.         for (i = 0; i < polyref->nvertices; i++) {
  133.             VecAdd(vlist[i]->normal, vlist[i]->normal, normal)
  134.         }
  135.     }
  136. }
  137.  
  138.  
  139.  
  140. /*
  141.  * Walk around a polygon, create the surrounding
  142.  * edges and sort them into the y-bucket.
  143.  */
  144. static void
  145. create_edges(view_vert, polygon, surface, render_mode)
  146.     View_coord *view_vert;
  147.     int         polygon;
  148.     Surface    *surface;
  149.     int         render_mode;
  150. {
  151.     Edge       *edge;
  152.     View_coord *view_ref, *last;
  153.     int         nderiv, y1, y2;
  154.     double      deltay;
  155.     double      x1, x2;
  156.     double      hden1, hden2;
  157.     Vector      world1, world2;
  158.     Vector      norm1, norm2;
  159.     Vector      text1, text2;
  160.  
  161.  
  162.     view_ref = last = view_vert;
  163.  
  164.     do {
  165.         view_ref = view_ref->next;
  166.  
  167.         /*
  168.          * If we are drawing a line image we dont need
  169.          * to build a complete edgelist. We draw the
  170.          * lines directly instead.
  171.          *
  172.          * Since many lines are drawn twice (edges shared between
  173.          * two polygons) and many line drawing algorithms are unsymmetrical
  174.          * we need to make sure lines are always drawn in the same
  175.          * direction
  176.          */
  177.         if (render_mode == LINE) {
  178.             if (view_ref->view.y < view_ref->next->view.y) {
  179.                 (*pixel_set)(im_data, 
  180.                               (int)(view_ref->view.x + 0.5), 
  181.                               (int)(view_ref->view.y + 0.5),
  182.                               (int)(view_ref->next->view.x + 0.5), 
  183.                               (int)(view_ref->next->view.y + 0.5));
  184.             } else {
  185.                 (*pixel_set)(im_data, 
  186.                               (int)(view_ref->next->view.x + 0.5), 
  187.                               (int)(view_ref->next->view.y + 0.5), 
  188.                               (int)(view_ref->view.x + 0.5), 
  189.                               (int)(view_ref->view.y + 0.5));
  190.             }
  191.             continue;
  192.         }
  193.  
  194.         /*
  195.          * Check if the slope of the edge is positive or negative
  196.          * or zero.
  197.          */
  198.         y1 = (int)(view_ref->view.y + 0.5);
  199.         y2 = (int)(view_ref->next->view.y + 0.5);
  200.         deltay = (double)(y2 - y1);
  201.  
  202.         if (deltay > 0.0)
  203.             nderiv = 1;
  204.         else if (deltay < 0.0)
  205.             nderiv = -1;
  206.         else
  207.             nderiv = 0;
  208.  
  209.         /*
  210.          * Check if the edge is horizontal. In that case we
  211.          * just skip it.
  212.          */
  213.         if (nderiv != 0) {
  214.  
  215.             edge = (Edge *)smalloc(sizeof(Edge));
  216.  
  217.             x1 = view_ref->view.x;
  218.             x2 = view_ref->next->view.x;
  219.             hden1 = view_ref->hden;
  220.             hden2 = view_ref->next->hden;
  221.             world1 = view_ref->world;
  222.             world2 = view_ref->next->world;
  223.             norm1 = view_ref->normal;
  224.             norm2 = view_ref->next->normal;
  225.             text1 = view_ref->texture;
  226.             text2 = view_ref->next->texture;
  227.  
  228.             deltay = 1.0 / fabs(deltay);
  229.  
  230.             if ((reverse_scan    && nderiv <= 0) ||
  231.                 ((!reverse_scan) && nderiv  > 0)) {
  232.  
  233.                 /*
  234.                  * The edge has positive slope
  235.                  */
  236.                 edge->ystart = y2;
  237.                 edge->ystop = y1;
  238.                 edge->xstart = x2;
  239.                 edge->hden = hden2;
  240.                 edge->world = world2;
  241.                 edge->normal = norm2;
  242.                 edge->texture = text2;
  243.                 edge->xstep = (x1 - x2) * deltay;
  244.                 edge->hdenstep = (hden1 - hden2) * deltay;
  245.                 if (render_mode != FLAT) {
  246.                     VecComb(edge->normalstep, deltay, norm1, -deltay, norm2);
  247.                     VecComb(edge->texturestep, deltay, text1, -deltay, text2);
  248.                     if (render_mode == PHONG) {
  249.                         VecComb(edge->worldstep, deltay, world1, 
  250.                                 -deltay, world2);
  251.                     }
  252.                 }
  253.  
  254.             } else {
  255.  
  256.                 /*
  257.                  * The edge has negative slope.
  258.                  */
  259.                 edge->ystart = y1;
  260.                 edge->ystop = y2;
  261.                 edge->xstart = x1;
  262.                 edge->hden = hden1;
  263.                 edge->world = world1;
  264.                 edge->normal = norm1;
  265.                 edge->texture = text1;
  266.                 edge->xstep = (x2 - x1) * deltay;
  267.                 edge->hdenstep = (hden2 - hden1) * deltay;
  268.                 if (render_mode != FLAT) {
  269.                     VecComb(edge->normalstep, deltay, norm2, -deltay, norm1);
  270.                     VecComb(edge->texturestep, deltay, text2, -deltay, text1);
  271.                     if (render_mode == PHONG) {
  272.                         VecComb(edge->worldstep, deltay, world2, 
  273.                                 -deltay, world1);
  274.                     }
  275.                 }
  276.             }
  277.             edge->polygon = polygon;
  278.             edge->surface = surface;
  279.             edge->next = y_bucket[edge->ystart];
  280.             y_bucket[edge->ystart] = edge;
  281.         }
  282.     } while (view_ref != last);
  283. }
  284.  
  285.  
  286.  
  287. /*
  288.  * Calculate a new vertex by interpolation between
  289.  * V1 and V2.
  290.  */
  291. static View_coord *
  292. interpolate(v1, v2, ratio)
  293.     View_coord *v1, *v2;
  294.     double      ratio;
  295. {
  296.     View_coord *tmp;
  297.  
  298.     tmp = (View_coord *)smalloc(sizeof(View_coord));
  299.  
  300.     tmp->hden = (1.0 - ratio) * v1->hden + ratio * v2->hden;
  301.     VecComb(tmp->view, 1.0 - ratio, v1->view, ratio, v2->view);
  302.     VecComb(tmp->world, 1.0 - ratio, v1->world, ratio, v2->world);
  303.     VecComb(tmp->normal, 1.0 - ratio, v1->normal, ratio, v2->normal);
  304.     VecComb(tmp->texture, 1.0 - ratio, v1->texture, ratio, v2->texture);
  305.     tmp->next = NULL;
  306.  
  307.     return tmp;
  308. }
  309.  
  310.  
  311.  
  312. /*
  313.  * Reset the averaged normals in the vertex tree P.
  314.  */
  315. static void
  316. reset_normals(vref)
  317.     Vertex *vref;
  318. {
  319.     if (vref != NULL) {
  320.         MakeVector(vref->normal, 0.0, 0.0, 0.0);
  321.         reset_normals(vref->big);
  322.         reset_normals(vref->sml);
  323.     }
  324. }
  325.  
  326.  
  327.  
  328. /*
  329.  * Clip a polygon using the Sutherland-Hodgeman algorithm for
  330.  * reentrant clipping;
  331.  */
  332. #define XMIN 0
  333. #define XMAX 1
  334. #define YMIN 2
  335. #define YMAX 3
  336. #define ZMIN 4
  337. #define ZMAX 5
  338.  
  339. static View_coord *
  340. polygon_clip(vlist, plane, first_vert)
  341.     View_coord *vlist;
  342.     int         plane;
  343.     bool        first_vert;
  344. {
  345.     static View_coord   *first;
  346.     static View_coord   *curr;
  347.     View_coord          *out1;
  348.     View_coord          *out2;
  349.     double               curr_limit;
  350.     double               first_limit;
  351.     double               vlist_limit;
  352.     double               ratio;
  353.     bool                 visible;
  354.  
  355.     out1 = out2 = NULL;
  356.  
  357.     if (vlist == NULL) {
  358.  
  359.         /*
  360.          * Did we get an empty list from the start?
  361.          */
  362.         if (first_vert) {
  363.             return NULL;
  364.         }
  365.  
  366.         /*
  367.          * Last vertex, close the polygon.
  368.          */
  369.         ratio = 0.0;
  370.         curr_limit = curr->view.z * sipp_current_camera->focal_ratio;
  371.         first_limit = first->view.z * sipp_current_camera->focal_ratio;
  372.  
  373.         switch (plane) {
  374.  
  375.           case XMIN:
  376.             if ((curr->view.x < -curr_limit 
  377.                  && first->view.x >= -first_limit)
  378.                 || (curr->view.x >= -curr_limit 
  379.                     && first->view.x < -first_limit)) {
  380.                 ratio = fabs(curr->view.x + curr_limit);
  381.                 ratio /= (ratio + fabs(first->view.x + first_limit)); 
  382.             }
  383.             break;
  384.  
  385.           case XMAX:
  386.             if ((curr->view.x <= curr_limit 
  387.                  && first->view.x > first_limit)
  388.                 || (curr->view.x > curr_limit 
  389.                     && first->view.x <= first_limit)) {
  390.                 ratio = fabs(curr->view.x - curr_limit);
  391.                 ratio /= (ratio + fabs(first->view.x - first_limit));
  392.             }
  393.             break;
  394.  
  395.           case YMIN:
  396.             if ((curr->view.y < -curr_limit 
  397.                  && first->view.y >= -first_limit)
  398.                 || (curr->view.y >= -curr_limit 
  399.                     && first->view.y < -first_limit)) {
  400.                 ratio = fabs(curr->view.y + curr_limit);
  401.                 ratio /= (ratio + fabs(first->view.y + first_limit));
  402.             }
  403.             break;
  404.  
  405.           case YMAX:
  406.             if ((curr->view.y <= curr_limit 
  407.                  && first->view.y > first_limit)
  408.                 || (curr->view.y > curr_limit 
  409.                     && first->view.y <= first_limit)) {
  410.                 ratio = fabs(curr->view.y - curr_limit);
  411.                 ratio /= (ratio + fabs(first->view.y - first_limit));
  412.             }
  413.             break;
  414.  
  415.           case ZMIN:
  416.             if ((curr->view.z < hither 
  417.                  && first->view.z >= hither)
  418.                 || (curr->view.z >= hither 
  419.                     && first->view.z < hither)) {
  420.                 ratio = fabs(curr->view.z - hither);
  421.                 ratio = ratio / (ratio + fabs(first->view.z - hither));
  422.             }
  423.             break;
  424.  
  425.           case ZMAX:
  426.             if ((curr->view.z <= yon 
  427.                  && first->view.z > yon)
  428.                 || (curr->view.z > yon 
  429.                     && first->view.z <= yon)) {
  430.                 ratio = fabs(curr->view.z - yon);
  431.                 ratio = ratio / (ratio + fabs(first->view.z - yon));
  432.             }
  433.             break;
  434.         }
  435.  
  436.         if (ratio != 0.0) {
  437.             out1 = interpolate(curr, first, ratio);
  438.             return out1;
  439.         } else {
  440.             return NULL;
  441.         }
  442.     }
  443.  
  444.     vlist_limit = vlist->view.z * sipp_current_camera->focal_ratio;
  445.     
  446.     if (first_vert) {
  447.         first = vlist;
  448.     } else {
  449.         ratio = 0.0;
  450.         curr_limit = curr->view.z * sipp_current_camera->focal_ratio;
  451.  
  452.         switch (plane) {
  453.  
  454.           case XMIN:
  455.             if ((curr->view.x < -curr_limit 
  456.                  && vlist->view.x >= -vlist_limit)
  457.                 || (curr->view.x >= -curr_limit 
  458.                     && vlist->view.x < -vlist_limit)) {
  459.                 ratio = fabs(curr->view.x + curr_limit);
  460.                 ratio /= (ratio + fabs(vlist->view.x + vlist_limit));
  461.             }
  462.             break;
  463.  
  464.           case XMAX:
  465.             if ((curr->view.x <= curr_limit 
  466.                  && vlist->view.x > vlist_limit)
  467.                 || (curr->view.x > curr_limit 
  468.                     && vlist->view.x <= vlist_limit)) {
  469.                 ratio = fabs(curr->view.x - curr_limit);
  470.                 ratio /= (ratio + fabs(vlist->view.x - vlist_limit));
  471.             }
  472.             break;
  473.  
  474.           case YMIN:
  475.             if ((curr->view.y < -curr_limit 
  476.                  && vlist->view.y >= -vlist_limit)
  477.                 || (curr->view.y >= -curr_limit 
  478.                     && vlist->view.y < -vlist_limit)) {
  479.                 ratio = fabs(curr->view.y + curr_limit);
  480.                 ratio /= (ratio + fabs(vlist->view.y + vlist_limit));
  481.             }
  482.             break;
  483.  
  484.           case YMAX:
  485.             if ((curr->view.y <= curr_limit 
  486.                  && vlist->view.y > vlist_limit)
  487.                 || (curr->view.y > curr_limit 
  488.                     && vlist->view.y <= vlist_limit)) {
  489.                 ratio = fabs(curr->view.y - curr_limit);
  490.                 ratio /= (ratio + fabs(vlist->view.y - vlist_limit));
  491.             }
  492.             break;
  493.  
  494.           case ZMIN:
  495.             if ((curr->view.z < hither 
  496.                  && vlist->view.z >= hither)
  497.                 || (curr->view.z >= hither 
  498.                     && vlist->view.z < hither)) {
  499.                 ratio = fabs(curr->view.z - hither);
  500.                 ratio = ratio / (ratio + fabs(vlist->view.z - hither));
  501.             }
  502.             break;
  503.  
  504.           case ZMAX:
  505.             if ((curr->view.z <= yon 
  506.                  && vlist->view.z > yon)
  507.                 || (curr->view.z > yon 
  508.                     && vlist->view.z <= yon)) {
  509.                 ratio = fabs(curr->view.z - yon);
  510.                 ratio = ratio / (ratio + fabs(vlist->view.z - yon));
  511.             }
  512.             break;
  513.         }
  514.  
  515.         if (ratio != 0.0) {
  516.             out1 = interpolate(curr, vlist, ratio);
  517.             out1->next = vlist;
  518.         }
  519.     }
  520.  
  521.     curr = vlist;
  522.     visible = FALSE;
  523.     switch (plane) {
  524.  
  525.       case XMIN:
  526.         visible = (curr->view.x >= -vlist_limit);
  527.         break;
  528.  
  529.       case XMAX:
  530.         visible = (curr->view.x <= vlist_limit);
  531.         break;
  532.  
  533.       case YMIN:
  534.         visible = (curr->view.y >= -vlist_limit);
  535.         break;
  536.  
  537.       case YMAX:
  538.         visible = (curr->view.y <= vlist_limit);
  539.         break;
  540.  
  541.       case ZMIN:
  542.         visible = (curr->view.z >= hither);
  543.         break;
  544.  
  545.       case ZMAX:
  546.         visible = (curr->view.z <= yon);
  547.         break;
  548.     }
  549.  
  550.     if (visible) {
  551.         out2 = curr;
  552.         out2->next = polygon_clip(curr->next, plane, FALSE);
  553.         return ((out1) ? (out1) : (out2));
  554.  
  555.     } else {
  556.         if (out1) {
  557.             out1->next = polygon_clip(curr->next, plane, FALSE);
  558.         } else {
  559.             out1 = polygon_clip(curr->next, plane, FALSE);
  560.         }
  561.         sfree(vlist);
  562.         return out1;
  563.     }
  564. }
  565.  
  566.  
  567.  
  568. /*
  569.  * Transform vertices into view coordinates. The transform is
  570.  * defined in MATRIX. Store the transformed vertices in a
  571.  * temporary list, create edges in the y_bucket.
  572.  */
  573. static void
  574. transf_vertices(vertex, nvertices, surface, view_mat, tr_mat, 
  575.                 xsiz, ysiz, render_mode)
  576.     Vertex     *vertex[];
  577.     int         nvertices;
  578.     Surface    *surface;
  579.     Transf_mat *view_mat;
  580.     Transf_mat *tr_mat;
  581.     double      xsiz, ysiz;
  582.     int         render_mode;
  583. {
  584.     static int  polygon = 0;        /* incremented for each call to provide */
  585.                                     /* unique polygon id numbers */
  586.     View_coord *nhead;
  587.     View_coord *view_ref;
  588.     View_coord *mark;
  589.     Color       color;                    
  590.     Color       opacity;
  591.     double      persp_factor;
  592.     double      minsize;
  593.     double      tmp;
  594.     int         i;
  595.  
  596.     nhead = NULL;
  597.     minsize = ((xsiz > ysiz) ? ysiz : xsiz);
  598.  
  599.     for (i = 0; i < nvertices; i++) {
  600.  
  601.         view_ref = (View_coord *)smalloc(sizeof(View_coord));
  602.  
  603.         /* Transform the normal (world coordinates) but */
  604.         /* do not include the translation part. */
  605.         view_ref->normal.x = (vertex[i]->normal.x * tr_mat->mat[0][0]
  606.                               + vertex[i]->normal.y * tr_mat->mat[1][0]
  607.                               + vertex[i]->normal.z * tr_mat->mat[2][0]);
  608.         view_ref->normal.y = (vertex[i]->normal.x * tr_mat->mat[0][1]
  609.                               + vertex[i]->normal.y * tr_mat->mat[1][1]
  610.                               + vertex[i]->normal.z * tr_mat->mat[2][1]);
  611.         view_ref->normal.z = (vertex[i]->normal.x * tr_mat->mat[0][2]
  612.                               + vertex[i]->normal.y * tr_mat->mat[1][2]
  613.                               + vertex[i]->normal.z * tr_mat->mat[2][2]);
  614.  
  615.         /* Transform the vertex to its new world coordinates. */
  616.         point_transform(&view_ref->world, &vertex[i]->pos, tr_mat);
  617.  
  618.         /* Transform the vertex into view coordinates. */
  619.         point_transform(&view_ref->view, &vertex[i]->pos, view_mat);
  620.  
  621.         /* Texture coordinates is not affected by transformations. */
  622.         VecCopy(view_ref->texture, vertex[i]->texture);
  623.  
  624.         view_ref->next = nhead;
  625.         nhead = view_ref;
  626.     }
  627.  
  628.     /* 
  629.      * Clip the resulting polygon. We need to do this
  630.      * before the perpective transformation to keep texture
  631.      * coordinates correct.
  632.      */
  633.     nhead = polygon_clip(nhead, ZMIN, TRUE);
  634.     nhead = polygon_clip(nhead, ZMAX, TRUE);
  635.     if (xsiz > ysiz) {
  636.         tmp = sipp_current_camera->focal_ratio;
  637.         sipp_current_camera->focal_ratio *= xsiz / ysiz;
  638.         nhead = polygon_clip(nhead, XMIN, TRUE);
  639.         nhead = polygon_clip(nhead, XMAX, TRUE);
  640.         sipp_current_camera->focal_ratio = tmp;
  641.         nhead = polygon_clip(nhead, YMIN, TRUE);
  642.         nhead = polygon_clip(nhead, YMAX, TRUE);
  643.     } else {
  644.         tmp = sipp_current_camera->focal_ratio;
  645.         sipp_current_camera->focal_ratio *= ysiz / xsiz;
  646.         nhead = polygon_clip(nhead, YMIN, TRUE);
  647.         nhead = polygon_clip(nhead, YMAX, TRUE);
  648.         sipp_current_camera->focal_ratio = tmp;
  649.         nhead = polygon_clip(nhead, XMIN, TRUE);
  650.         nhead = polygon_clip(nhead, XMAX, TRUE);
  651.     }
  652.  
  653.     if (nhead == NULL) {    /* Nothing left? */
  654.         return;
  655.     }
  656.  
  657.  
  658.     
  659.     /*
  660.      * If we are flat shading, we need a color for the polygon.
  661.      * We call the shader at the first vertex to get this.
  662.      * (This is not quite correct since the normal here is
  663.      * an averaged normal of the surrounding polygons)
  664.      */
  665.     if (render_mode == FLAT) {
  666.         Vector view_vec;
  667.  
  668.         VecSub(view_vec, sipp_current_camera->position, nhead->world);
  669.         vecnorm(&view_vec);
  670.         (*surface->shader)
  671.             (&nhead->world, &nhead->normal, &nhead->texture, 
  672.              &view_vec, lightsrc_stack, surface->surface, 
  673.              &color, &opacity);
  674.     }
  675.  
  676.  
  677.     /*
  678.      * Walk around the new (clipped and transformed) polygon and 
  679.      * transform it into perspective screen coordinates.
  680.      * We also do a homgenous division of texture and world coordinates
  681.      * and store a "homogenous denominator" so we can do rational
  682.      * linear interpolation.
  683.      * If we are doing gouraud shading we call the shader at each
  684.      * vertex.
  685.      * Last we tie the head and tail together forming a cirkular
  686.      * list, this simplifies edge creation.
  687.      */
  688.     for (view_ref = nhead;; view_ref = view_ref->next) {
  689.         persp_factor = view_ref->view.z * sipp_current_camera->focal_ratio; 
  690.         view_ref->view.x  = view_ref->view.x * minsize / persp_factor + xsiz;
  691.         view_ref->view.y  = view_ref->view.y * minsize / persp_factor + ysiz;
  692.         view_ref->hden = 1.0 / persp_factor;
  693.  
  694.         if (render_mode == PHONG) {
  695.             VecScalMul(view_ref->world, view_ref->hden, view_ref->world);
  696.             VecScalMul(view_ref->texture, view_ref->hden, view_ref->texture);
  697.  
  698.         } else if (render_mode == GOURAUD) {
  699.             Vector view_vec;
  700.             
  701.             VecSub(view_vec, sipp_current_camera->position, view_ref->world);
  702.             vecnorm(&view_vec);
  703.             (*surface->shader)
  704.                 (&view_ref->world, &view_ref->normal, &view_ref->texture, 
  705.                  &view_vec, lightsrc_stack, surface->surface, 
  706.                  &color, &opacity);
  707.         } 
  708.  
  709.         if (render_mode == GOURAUD || render_mode == FLAT) {
  710.             MakeVector(view_ref->normal, color.red, color.grn, color.blu);
  711.             MakeVector(view_ref->texture, 
  712.                        opacity.red, opacity.grn, opacity.blu);
  713.         } 
  714.  
  715.         if (view_ref->next == NULL) {
  716.             view_ref->next = nhead;
  717.             break;
  718.         }
  719.     }
  720.  
  721.     create_edges(nhead, polygon++, surface, render_mode);
  722.  
  723.     /*
  724.      * Free the memory used by the transformed polygon.
  725.      */
  726.     mark = nhead;
  727.     do {
  728.         view_ref = nhead;
  729.         nhead = nhead->next;
  730.         sfree(view_ref);
  731.     } while (nhead != mark);
  732. }
  733.  
  734.  
  735.  
  736.  
  737. /*
  738.  * Read edge pairs from the edge list EDGE_LIST. Walk along the scanline
  739.  * and interpolate z value, world coordinates, texture coordinates and 
  740.  * normal vector as we go. Call the shader and store in scanline pixel buffer.
  741.  */
  742. static void
  743. render_scanline(res, scanline, edge_list, render_mode)
  744.     int      res;
  745.     int     *scanline;
  746.     Edge    *edge_list;
  747.     int      render_mode;
  748. {
  749.     Edge  *startedge, *stopedge;
  750.     double hden, hdenstep;
  751.     Vector world, worldstep;
  752.     Vector norm, normstep;
  753.     Vector text, textstep;
  754.     double zfact;
  755.     double real_z;
  756.     Vector real_world;
  757.     Vector real_text;
  758.     Vector view_vec;
  759.     double ratio;
  760.     double w;
  761.     Color  color;
  762.     Color  opacity;
  763.     int    xstart, xstop;
  764.     int    i, j;
  765.     
  766.     startedge = edge_list;
  767.     stopedge = NULL;
  768.  
  769.     zfact = 1.0 / sipp_current_camera->focal_ratio;
  770.  
  771.     while (startedge != NULL) {
  772.  
  773.         stopedge = startedge->next;
  774.         xstart = (int)(startedge->xstart + 0.5);
  775.         xstop  = (int)(stopedge->xstart - 0.5);
  776.         hden = startedge->hden;
  777.         VecCopy(world, startedge->world);
  778.         VecCopy(norm, startedge->normal);
  779.         VecCopy(text, startedge->texture);
  780.  
  781.         if (xstart < xstop) {
  782.             ratio = 1.0 / (double)(xstop - xstart);
  783.             hdenstep = (stopedge->hden - hden) * ratio;
  784.             if (render_mode != FLAT) {
  785.                 VecComb(normstep, ratio, stopedge->normal, -ratio, norm);
  786.                 VecComb(textstep, ratio, stopedge->texture, -ratio, text);
  787.                 if (render_mode == PHONG) {
  788.                     VecComb(worldstep, ratio, stopedge->world, -ratio, world);
  789.                 }
  790.             }
  791.  
  792.         } else {
  793.             hdenstep = 0.0;
  794.             MakeVector(worldstep, 0.0, 0.0, 0.0);
  795.             MakeVector(normstep, 0.0, 0.0, 0.0);
  796.             MakeVector(textstep, 0.0, 0.0, 0.0);
  797.         }
  798.  
  799.         for (i = xstart; i <= xstop; i++) {
  800.             real_z = zfact / hden;
  801.             if (pixel_visible(real_z, scanline[i])) {
  802.                 if (render_mode == PHONG) {
  803.                     VecScalMul(real_text, 1.0 / hden, text);
  804.                     VecScalMul(real_world, 1.0 / hden, world);
  805.                     VecSub(view_vec, sipp_current_camera->position, 
  806.                            real_world);
  807.                     vecnorm(&view_vec);
  808.                     (*startedge->surface->shader)
  809.                         (&real_world, &norm, &real_text, 
  810.                          &view_vec, lightsrc_stack, 
  811.                          startedge->surface->surface, &color, &opacity);
  812.                     scanline[i] = pixel_insert(scanline[i], 
  813.                                                real_z, &color, &opacity);
  814.                     
  815.                 } else {
  816.                     scanline[i] = pixel_insert(scanline[i], real_z, 
  817.                                                (Color *)&norm, 
  818.                                                (Color *)&text);
  819.                 }
  820.             }
  821.             
  822.             hden += hdenstep;
  823.             if (render_mode != FLAT) {
  824.                 VecAdd(norm, norm, normstep);
  825.                 VecAdd(text, text, textstep);
  826.                 if (render_mode == PHONG) {
  827.                     VecAdd(world, world, worldstep);
  828.                 }
  829.             }
  830.         }
  831.         startedge = stopedge->next;
  832.     }
  833. }
  834.  
  835.  
  836.  
  837.  
  838. /*
  839.  * Insert an edge into an edge list. Edges belonging to the same
  840.  * polygon must be inserted sorted in x, so that edge pairs are
  841.  * created.
  842.  */
  843. static Edge *
  844. insert_edge(edge_list, edge)
  845.     Edge *edge_list, *edge;
  846. {
  847.     Edge *edge_ref1;
  848.     Edge *edge_ref2;
  849.  
  850.     /*
  851.      * If list is empty, just insert the edge.
  852.      */
  853.     if (edge_list == NULL) {
  854.     edge->next = NULL;
  855.         return edge;
  856.     }
  857.  
  858.     /*
  859.      * If the edges to our polygon is first in the list, check
  860.      * if our edge should be inserted first.
  861.      */
  862.     if (edge_list->polygon == edge->polygon) {
  863.         if (edge_list->xstart > edge->xstart) {
  864.             edge->next = edge_list;
  865.             return edge;
  866.         } else if ((((int)(edge_list->xstart + 0.5))
  867.                     == ((int)(edge->xstart + 0.5)))
  868.                    && (edge_list->xstep > edge->xstep)) {
  869.             edge->next = edge_list;
  870.             return edge;
  871.         }
  872.     }
  873.  
  874.     /*
  875.      * Check if our polygon is in the list at all.
  876.      */
  877.     edge_ref1 = edge_list;
  878.     edge_ref2 = edge_list->next;
  879.     if (edge_ref1->polygon != edge->polygon) {
  880.         while (edge_ref2 != NULL && edge_ref2->polygon != edge->polygon) {
  881.             edge_ref1 = edge_ref2;
  882.             edge_ref2 = edge_ref2->next;
  883.         }
  884.     }
  885.  
  886.     /*
  887.      * Insert the edge at the right place,  sorted in x if our 
  888.      * polygon was found, otherwize last in the list.
  889.      */
  890.     while (1) {
  891.         if (edge_ref2 == NULL) {
  892.             edge->next = edge_ref2;
  893.             edge_ref1->next = edge;
  894.             break;
  895.         } else if ((edge_ref2->polygon != edge->polygon)
  896.                    || ((edge_ref2->xstart > edge->xstart)
  897.                        || ((((int)(edge_ref2->xstart + 0.5)) 
  898.                             == ((int)(edge->xstart + 0.5)))
  899.                            && (edge_ref2->xstep > edge->xstep)))) {
  900.             edge->next = edge_ref2;
  901.             edge_ref1->next = edge;
  902.             break;
  903.         } else {
  904.             edge_ref1 = edge_ref2;
  905.             edge_ref2 = edge_ref2->next;
  906.         }
  907.     }
  908.  
  909.     return edge_list;
  910. }
  911.         
  912.  
  913.  
  914. /*
  915.  * Merge two edge lists.
  916.  */
  917. static Edge *
  918. merge_edge_lists(list1, list2)
  919.     Edge *list1, *list2;
  920. {
  921.     Edge *eref1, *eref2, *next;
  922.     
  923.     if (list2 == NULL)
  924.         return list1;
  925.  
  926.     eref1 = list1;
  927.     eref2 = list2;
  928.     do {
  929.         next = eref2->next;
  930.         eref1 = insert_edge(eref1, eref2);
  931.     eref2 = next;
  932.     } while (eref2 != NULL);
  933.  
  934.     return eref1;
  935. }
  936.  
  937.  
  938.  
  939. /*
  940.  * Store a rendered line on the place indicated by STORAGE_MODE.
  941.  */
  942. static void
  943. store_line(buf, npixels, line, storage_mode)
  944.     u_char *buf;
  945.     int            npixels;
  946.     int            line;
  947.     int            storage_mode;
  948. {
  949.     int i, j;
  950.  
  951.     switch (storage_mode) {
  952.       case PPM_FILE:
  953.         fwrite(buf, sizeof(u_char), npixels * 3, image_file);
  954.         fflush(image_file);
  955.         break;
  956.  
  957.       case FUNCTION:
  958.         for (i = 0, j = 0; j < npixels; j++, i += 3) {
  959.             (*pixel_set)(im_data, j, line, buf[i], buf[i + 1], buf[i + 2]);
  960.         }
  961.         break;
  962.  
  963.       default:
  964.         break;
  965.     }
  966. }
  967.  
  968.  
  969.  
  970. static void
  971. buffer_clear(res, scanline)
  972.     int    res;
  973.     int   *scanline;
  974. {
  975.     int         i;
  976.     
  977.     for (i = 0; i < res; i++) {
  978.         scanline[i] = -1;
  979.     }
  980. }
  981.  
  982.     
  983.  
  984. /*
  985.  * Allocate the needed buffers. Create a list of active edges and
  986.  * move down the y-bucket, inserting and deleting edges from this
  987.  * active list as we go. Call render_scanline for each scanline and
  988.  * do an average filtering before storing the scanline.
  989.  */
  990. static void
  991. scan_and_render(xres, yres, storage_mode, render_mode, oversampl, field)
  992.     int   xres, yres;
  993.     int   storage_mode;
  994.     int   render_mode;
  995.     int   oversampl;
  996.     int   field;
  997. {
  998.     Edge         *active_list;
  999.     Edge         *edgep, *edgep2;
  1000.     int         **linebuf;
  1001.     u_char       *line;
  1002.     int           curr_line;
  1003.     int           scanline;
  1004.     int           y, next_edge, y_limit;
  1005.     Color        *pixel_color;
  1006.     Color         sum;
  1007.     int           i, j, k;
  1008.     
  1009.     line = (u_char *)smalloc(xres * 3 * sizeof(u_char));
  1010.     linebuf  = (int **)alloca(oversampl * sizeof(int *));
  1011.     for (i = 0; i < oversampl; i++) {
  1012.         linebuf[i] = (int *)scalloc(xres, sizeof(int));
  1013.     }
  1014.     pixels_setup(xres);
  1015.  
  1016.  
  1017.     if (storage_mode == PPM_FILE) {
  1018.         fprintf(image_file, "P6\n");
  1019.         fprintf(image_file, "#Image rendered with SIPP %s\n", SIPP_VERSION);
  1020.  
  1021.         switch (field) {
  1022.           case BOTH:
  1023.             fprintf(image_file, "%d\n%d\n255\n", xres / oversampl, 
  1024.                                                  yres / oversampl);
  1025.             break;
  1026.  
  1027.           case EVEN:
  1028.             fprintf(image_file, "#Image field containing EVEN lines\n");
  1029.             fprintf(image_file, "%d\n%d\n255\n", xres / oversampl, 
  1030.                     ((yres / oversampl) & 1)
  1031.                     ? ((yres / oversampl) >> 1) + 1
  1032.                     :  (yres / oversampl) >> 1);
  1033.             break;
  1034.  
  1035.           case ODD:
  1036.             fprintf(image_file, "#Image field containing ODD lines\n");
  1037.             fprintf(image_file, "%d\n%d\n255\n", xres / oversampl, 
  1038.                                                  (yres / oversampl) >> 1);
  1039.             break;
  1040.         }
  1041.     }
  1042.  
  1043.     if (reverse_scan) {
  1044.         y = 0;
  1045.         y_limit = yres;
  1046.         scanline =  (yres - 1) * oversampl;
  1047.     } else {
  1048.         y = yres - 1;
  1049.         y_limit = -1;
  1050.         scanline =  0;
  1051.     }
  1052.     active_list = NULL;
  1053.     curr_line = 0;
  1054.  
  1055.     while (y != y_limit) {
  1056.  
  1057.         active_list = merge_edge_lists(active_list, y_bucket[y]);
  1058.         y_bucket[y] = NULL;
  1059.  
  1060.         if (reverse_scan) {
  1061.             next_edge = y + 1;
  1062.             while (next_edge < y_limit && y_bucket[next_edge] == NULL)
  1063.                 next_edge++;
  1064.         } else {
  1065.             next_edge = y - 1;
  1066.             while (next_edge >= 0 && y_bucket[next_edge] == NULL)
  1067.                 next_edge--;
  1068.         }
  1069.         while ((reverse_scan    && (y < next_edge)) ||
  1070.                ((!reverse_scan) && (y > next_edge))) {
  1071.             if (field == BOTH || (scanline & 1) == field) {
  1072.                 buffer_clear(xres, linebuf[curr_line]);
  1073.                 render_scanline(xres, linebuf[curr_line], 
  1074.                                 active_list, render_mode); 
  1075.             }
  1076.  
  1077.             if (++curr_line == oversampl) {
  1078.  
  1079.                 if (field == BOTH || (scanline & 1) == field) {
  1080.                     /*
  1081.                      * Average the pixel.
  1082.                      */
  1083.                     for (i = 0; i < ((xres / oversampl)); i++) {
  1084.                         sum.red = 0.0;
  1085.                         sum.grn = 0.0;
  1086.                         sum.blu = 0.0;
  1087.                         for (j = i * oversampl;                          
  1088.                              j < (i * oversampl + oversampl); j++) {
  1089.                             for (k = 0; k < oversampl; k++) {
  1090.                                 pixel_color = pixel_collect(*(linebuf[k] + j));
  1091.                                 if (pixel_color != NULL) {
  1092.                                     sum.red += pixel_color->red;
  1093.                                     sum.grn += pixel_color->grn;
  1094.                                     sum.blu += pixel_color->blu;
  1095.                                 }
  1096.                             }
  1097.                         }
  1098.                         line[i * 3]    = (u_char)(sum.red 
  1099.                                                   / (oversampl * oversampl) 
  1100.                                                   * 255.0 + 0.5);
  1101.                         line[i * 3 + 1] = (u_char)(sum.grn
  1102.                                                    / (oversampl * oversampl) 
  1103.                                                    * 255.0 + 0.5);
  1104.                         line[i * 3 + 2] = (u_char)(sum.blu 
  1105.                                                    / (oversampl * oversampl) 
  1106.                                                    * 255.0 + 0.5);
  1107.                     }
  1108.                     store_line(line, xres / oversampl, scanline, 
  1109.                                storage_mode);
  1110.                     pixels_reinit();
  1111.                 }
  1112.  
  1113.                 curr_line = 0;
  1114.                 scanline += reverse_scan ? -1 : 1;
  1115.             }
  1116.             
  1117.         if (active_list != NULL) {
  1118.                 
  1119.             edgep2 = active_list;
  1120.             edgep = active_list->next;
  1121.             while (edgep != NULL) {
  1122.                 if ((reverse_scan &&
  1123.                          edgep->ystart >= (edgep->ystop - 1)) ||
  1124.                         ((!reverse_scan) &&
  1125.                          edgep->ystart <= (edgep->ystop + 1))) {
  1126.                         edgep2->next = edgep->next;
  1127.                 sfree(edgep);
  1128.                     edgep = edgep2->next;
  1129.             } else {
  1130.                 edgep2 = edgep;
  1131.                 edgep = edgep->next;
  1132.             }
  1133.                 }
  1134.                 
  1135.               if ((reverse_scan && 
  1136.                      active_list->ystart >= (active_list->ystop - 1)) ||
  1137.                     ((!reverse_scan) &&
  1138.                      active_list->ystart <= (active_list->ystop + 1))) {
  1139.                 edgep = active_list;
  1140.             active_list = active_list->next;
  1141.                 sfree(edgep);
  1142.             }
  1143.                 
  1144.             edgep = active_list;
  1145.             while (edgep != NULL) {
  1146.                 edgep->ystart += reverse_scan ? 1 : -1;
  1147.             edgep->xstart += edgep->xstep;
  1148.                     edgep->hden += edgep->hdenstep;
  1149.                     if (render_mode != FLAT) {
  1150.                         VecAdd(edgep->normal, edgep->normal,
  1151.                                edgep->normalstep); 
  1152.                         VecAdd(edgep->texture, edgep->texture,
  1153.                                edgep->texturestep); 
  1154.                         if (render_mode == PHONG) {
  1155.                             VecAdd(edgep->world, edgep->world, 
  1156.                                    edgep->worldstep);
  1157.                         }
  1158.                     }
  1159.             edgep = edgep->next;
  1160.             }
  1161.         }
  1162.             y += reverse_scan ? 1 : -1;
  1163.     }
  1164.     }
  1165.     sfree(line);
  1166.     for (i = 0; i < oversampl; i++) {
  1167.         sfree(linebuf[i]);
  1168.     }
  1169.     pixels_free();
  1170. }
  1171.  
  1172.  
  1173.  
  1174. /*
  1175.  * Push the current transformation matrix on the matrix stack.
  1176.  */
  1177. static void
  1178. matrix_push()
  1179. {
  1180.     struct tm_stack_t *new_tm;
  1181.  
  1182.     new_tm = (struct tm_stack_t *)smalloc(sizeof(struct tm_stack_t));
  1183.     MatCopy(&new_tm->mat, &curr_mat);
  1184.     new_tm->next = tm_stack;
  1185.     tm_stack     = new_tm;
  1186. }
  1187.  
  1188.  
  1189. /*
  1190.  * Pop the top of the matrix stack and make
  1191.  * it the new current transformation matrix.
  1192.  */
  1193. static void
  1194. matrix_pop()
  1195. {
  1196.     struct tm_stack_t *tmp;
  1197.  
  1198.     MatCopy(&curr_mat, &tm_stack->mat);
  1199.     tmp = tm_stack;
  1200.     tm_stack = tm_stack->next;
  1201.     sfree(tmp);
  1202. }
  1203.  
  1204.  
  1205.  
  1206. /*
  1207.  * Traverse an object hierarchy, transform each object
  1208.  * according to its transformation matrix.
  1209.  * Transform all polygons in the object to view coordinates.
  1210.  * Build the edge lists in y_bucket.
  1211.  */
  1212. static void
  1213. traverse_object_tree(object, view_mat, xres, yres, render_mode)
  1214.     Object      *object;
  1215.     Transf_mat  *view_mat;
  1216.     int          xres, yres;
  1217.     int          render_mode;
  1218. {
  1219.     Object      *objref;
  1220.     Surface     *surfref;
  1221.     Polygon     *polyref;
  1222.     Vector       eyepoint, tmp;
  1223.     Transf_mat   loc_view_mat;
  1224.     double       m[3][4], dtmp;
  1225.     int          i, j;
  1226.  
  1227.  
  1228.     if (object == NULL) {
  1229.         return;
  1230.     }
  1231.  
  1232.     for (objref = object; objref != NULL; objref = objref->next) {
  1233.  
  1234.         matrix_push();
  1235.         mat_mul(&curr_mat, &objref->transf, &curr_mat);
  1236.         mat_mul(&loc_view_mat, &curr_mat, view_mat);
  1237.  
  1238.         VecCopy(tmp, sipp_current_camera->position);
  1239.  
  1240.         /*
  1241.          * Do an inverse transformation of the viewpoint to use
  1242.          * when doing backface culling (in calc_normals()).
  1243.          */
  1244.         tmp.x -= curr_mat.mat[3][0];
  1245.         tmp.y -= curr_mat.mat[3][1];
  1246.         tmp.z -= curr_mat.mat[3][2];
  1247.         m[0][0] = curr_mat.mat[0][0] ; m[0][1] = curr_mat.mat[1][0];
  1248.         m[0][2] = curr_mat.mat[2][0] ; m[0][3] = tmp.x;
  1249.         m[1][0] = curr_mat.mat[0][1] ; m[1][1] = curr_mat.mat[1][1];
  1250.         m[1][2] = curr_mat.mat[2][1] ; m[1][3] = tmp.y;
  1251.         m[2][0] = curr_mat.mat[0][2] ; m[2][1] = curr_mat.mat[1][2];
  1252.         m[2][2] = curr_mat.mat[2][2] ; m[2][3] = tmp.z;
  1253.  
  1254.         if (m[0][0] == 0.0) {
  1255.             if (m[1][0] != 0.0)
  1256.                 j = 1;
  1257.             else
  1258.                 j = 2;
  1259.             for (i = 0; i < 4; i++) {
  1260.                 dtmp     = m[0][i];
  1261.                 m[0][i] = m[j][i];
  1262.                 m[j][i] = dtmp;
  1263.             }
  1264.         }
  1265.         
  1266.         for (j = 1; j < 3; j++) {
  1267.             m[j][0] /= (-m[0][0]);
  1268.             for (i = 1; i < 4; i++)
  1269.                 m[j][i] += m[0][i] * m[j][0];
  1270.         }
  1271.         
  1272.         if (m[1][1] == 0.0)
  1273.             for (i = 1; i < 4; i++) {
  1274.                 dtmp     = m[1][i];
  1275.                 m[1][i] = m[2][i];
  1276.                 m[2][i] = dtmp;
  1277.             }
  1278.         
  1279.         if (m[1][1] != 0.0) {
  1280.             m[2][1] /= (-m[1][1]);
  1281.             m[2][2] += m[1][2] * m[2][1];
  1282.             m[2][3] += m[1][3] * m[2][1];
  1283.         }
  1284.         
  1285.         eyepoint.z = m[2][3] / m[2][2];
  1286.         eyepoint.y = (m[1][3] - eyepoint.z * m[1][2]) / m[1][1];
  1287.         eyepoint.x = (m[0][3] - eyepoint.z * m[0][2] 
  1288.                       - eyepoint.y * m[0][1]) / m[0][0];
  1289.  
  1290.         for (surfref = objref->surfaces; surfref != NULL; 
  1291.              surfref = surfref->next) {
  1292.  
  1293.             calc_normals(surfref->polygons, eyepoint);
  1294.  
  1295.             for (polyref = surfref->polygons; polyref != NULL; 
  1296.                  polyref = polyref->next) {
  1297.  
  1298.                 if (!polyref->backface) {
  1299.                     transf_vertices(polyref->vertex, polyref->nvertices, 
  1300.                                     surfref, &loc_view_mat, &curr_mat, 
  1301.                                     (double)xres / 2.0, (double)yres / 2.0, 
  1302.                                     render_mode);
  1303.                 }
  1304.  
  1305.             }
  1306.             reset_normals(surfref->vertices);
  1307.  
  1308.         }
  1309.         traverse_object_tree(objref->sub_obj, view_mat, xres, yres, 
  1310.                              render_mode); 
  1311.         matrix_pop();
  1312.     }
  1313. }
  1314.  
  1315.  
  1316.  
  1317. /*
  1318.  * Render one scanline in a depth-map. This is just a stripped
  1319.  * version of render_scanline().
  1320.  */
  1321. static void
  1322. render_dmap_line(dmap_line, edge_list)
  1323.     float       *dmap_line;
  1324.     Edge        *edge_list;
  1325. {
  1326.     Edge  *startedge, *stopedge;
  1327.     double hden, hdenstep;
  1328.     float  zfact;
  1329.     float  real_z;
  1330.     double ratio;
  1331.     int    xstart, xstop;
  1332.     int    i;
  1333.     
  1334.     startedge = edge_list;
  1335.     stopedge = NULL;
  1336.  
  1337.     zfact = (float)(1.0 / sipp_current_camera->focal_ratio);
  1338.  
  1339.     while (startedge != NULL) {
  1340.  
  1341.         stopedge = startedge->next;
  1342.         xstart = (int)(startedge->xstart + 0.5);
  1343.         xstop  = (int)(stopedge->xstart + 0.5);
  1344.         hden = startedge->hden;
  1345.  
  1346.         if (xstart < xstop) {
  1347.             hdenstep = (stopedge->hden - hden) / (double)(xstop - xstart);
  1348.         } else {
  1349.             hdenstep = 0.0;
  1350.         }
  1351.  
  1352.         for (i = xstart; i <= xstop; i++) {
  1353.             real_z = zfact / hden;
  1354.             if (real_z < dmap_line[i]) {
  1355.                 dmap_line[i] = real_z;
  1356.             }
  1357.             hden += hdenstep;
  1358.         }
  1359.         startedge = stopedge->next;
  1360.     }
  1361. }
  1362.  
  1363.  
  1364.  
  1365. /*
  1366.  * Similar function to scan_and_render() used when rendering depthmaps.
  1367.  * Allocate the needed buffers. Create a list of active edges and
  1368.  * move down the y-bucket, inserting and deleting edges from this
  1369.  * active list as we go. Call render_dmap_line() for each scanline.
  1370.  */
  1371. static void
  1372. scan_depthmap(d_map, mat)
  1373.     float      *d_map;
  1374. {
  1375.     Edge            *active_list;
  1376.     Edge            *edgep, *edgep2;
  1377.     int              y, next_edge, y_limit;
  1378.     
  1379.     if (reverse_scan) {
  1380.         y = 0;
  1381.         y_limit = depthmap_size;
  1382.     } else {
  1383.         y = depthmap_size - 1;
  1384.         y_limit = -1;
  1385.     }
  1386.     active_list = NULL;
  1387.  
  1388.     while (y != y_limit) {
  1389.  
  1390.         active_list = merge_edge_lists(active_list, y_bucket[y]);
  1391.         y_bucket[y] = NULL;
  1392.         next_edge = y - 1;
  1393.  
  1394.         if (reverse_scan) {
  1395.             next_edge = y + 1;
  1396.             while (next_edge < y_limit && y_bucket[next_edge] == NULL)
  1397.                 next_edge++;
  1398.         } else {
  1399.             next_edge = y - 1;
  1400.             while (next_edge >= 0 && y_bucket[next_edge] == NULL)
  1401.                 next_edge--;
  1402.         }
  1403.  
  1404.         while ((reverse_scan    && (y < next_edge)) ||
  1405.                ((!reverse_scan) && (y > next_edge))) {
  1406.  
  1407.             render_dmap_line(d_map + (depthmap_size - 1 - y) * depthmap_size, 
  1408.                              active_list); 
  1409.  
  1410.         if (active_list != NULL) {
  1411.                 
  1412.             edgep2 = active_list;
  1413.             edgep = active_list->next;
  1414.             while (edgep != NULL) {
  1415.                 if ((reverse_scan &&
  1416.                          edgep->ystart >= (edgep->ystop - 1)) ||
  1417.                         ((!reverse_scan) &&
  1418.                          edgep->ystart <= (edgep->ystop + 1))) {
  1419.                         edgep2->next = edgep->next;
  1420.                 sfree(edgep);
  1421.                     edgep = edgep2->next;
  1422.             } else {
  1423.                 edgep2 = edgep;
  1424.                 edgep = edgep->next;
  1425.             }
  1426.                 }
  1427.                 
  1428.               if ((reverse_scan && 
  1429.                      active_list->ystart >= (active_list->ystop - 1)) ||
  1430.                     ((!reverse_scan) &&
  1431.                      active_list->ystart <= (active_list->ystop + 1))) {
  1432.                 edgep = active_list;
  1433.             active_list = active_list->next;
  1434.                 sfree(edgep);
  1435.             }
  1436.                 
  1437.             edgep = active_list;
  1438.             while (edgep != NULL) {
  1439.                 edgep->ystart += reverse_scan ? 1 : -1;
  1440.             edgep->xstart += edgep->xstep;
  1441.                     edgep->hden += edgep->hdenstep;
  1442.             edgep = edgep->next;
  1443.             }
  1444.         }
  1445.             y += reverse_scan ? 1 : -1;
  1446.     }
  1447.     }
  1448. }
  1449.  
  1450.  
  1451.  
  1452. /*
  1453.  * Render depthmaps for the lightsources that will cast
  1454.  * shadows. Place the camera in the position of each lightsource
  1455.  * in turn and render the depthmap. Store the matrix converting
  1456.  * from world coordinates to depthmap coordinates together with 
  1457.  * the depthmap.
  1458.  */
  1459. static void
  1460. render_depthmaps()
  1461. {
  1462.     Transf_mat      view_mat;
  1463.     Vector          view_vec;
  1464.     Lightsource    *lp;
  1465.     Camera         *tmp_camera;
  1466.     Camera         *light_camera;
  1467.     bool            backface_tmp;
  1468.  
  1469.     y_bucket = (Edge **)scalloc(depthmap_size, sizeof(Edge *));
  1470.  
  1471.     tmp_camera = sipp_current_camera;
  1472.     light_camera = camera_create();
  1473.     *light_camera = *sipp_current_camera;
  1474.     backface_tmp = show_backfaces;
  1475.     show_backfaces = FALSE;
  1476.  
  1477.     for (lp = lightsrc_stack; lp != NULL; lp = lp->next) {
  1478.         if (lp->shadow.active) {
  1479.             VecCopy(light_camera->position, 
  1480.                     ((Spot_light_info *)(lp->info))->pos);
  1481.             VecCopy(light_camera->lookat, 
  1482.                     ((Spot_light_info *)(lp->info))->point);
  1483.             light_camera->focal_ratio = lp->shadow.fov_factor;
  1484.             camera_use(light_camera);
  1485.             VecSub(view_vec, light_camera->position, light_camera->lookat);
  1486.             lp->shadow.bias = VecLen(view_vec) * 0.005;
  1487.             get_view_transf(&view_mat, light_camera, PHONG);
  1488.             lp->shadow.matrix = view_mat;
  1489.  
  1490.             MatCopy(&curr_mat, &ident_matrix);
  1491.             
  1492.             traverse_object_tree(sipp_world, &view_mat, 
  1493.                                  depthmap_size - 1, depthmap_size - 1, 
  1494.                                  PHONG);
  1495.             
  1496.             scan_depthmap(lp->shadow.d_map);
  1497.         }
  1498.     }
  1499.  
  1500.     camera_use(tmp_camera);
  1501.     camera_destruct(light_camera);
  1502.     show_backfaces = backface_tmp;
  1503.     sfree(y_bucket);
  1504. }
  1505.     
  1506.  
  1507.  
  1508. /*
  1509.  * "Main" functions in rendering. Allocate y-bucket, transform vertices
  1510.  * into viewing coordinates, make edges and sort them into the y-bucket.
  1511.  * Call scan_and_render to do the real work.
  1512.  */
  1513. static void
  1514. render_main(xres, yres, storage_mode, render_mode, oversampling, field)
  1515.     int   xres, yres;
  1516.     int   storage_mode;
  1517.     int   render_mode;
  1518.     int   oversampling;
  1519.     int   field;
  1520. {
  1521.     Transf_mat      view_mat;
  1522.     int i;
  1523.  
  1524.     if (render_mode != LINE) {
  1525.         if (shadows) {
  1526.             depthmaps_create();
  1527.             render_depthmaps();
  1528.         }
  1529.         xres *= oversampling;
  1530.         yres *= oversampling;
  1531.         y_bucket = (Edge **)scalloc(yres, sizeof(Edge *));
  1532.  
  1533.     } else if (storage_mode == PBM_FILE) {
  1534.         im_data = sipp_bitmap_create(xres, yres);
  1535.         pixel_set = sipp_bitmap_line;
  1536.     }
  1537.  
  1538.     get_view_transf(&view_mat, sipp_current_camera, render_mode);
  1539.     MatCopy(&curr_mat, &ident_matrix);
  1540.     
  1541.     traverse_object_tree(sipp_world, &view_mat, xres - 1, yres - 1, 
  1542.                          render_mode);
  1543.  
  1544.     if (render_mode != LINE) {
  1545.         scan_and_render(xres, yres, storage_mode, render_mode, 
  1546.                         oversampling, field);
  1547.         sfree(y_bucket);
  1548.         if (shadows) {
  1549.             depthmaps_destruct();
  1550.         }
  1551.  
  1552.     } else if (storage_mode == PBM_FILE) {
  1553.         sipp_bitmap_write(image_file, im_data);
  1554.         sipp_bitmap_destruct(im_data);
  1555.     }
  1556. }
  1557.     
  1558.  
  1559. void
  1560. render_image_file(xres, yres, im_file, render_mode, oversampling)
  1561.     int   xres, yres;
  1562.     FILE *im_file;
  1563.     int   render_mode;
  1564.     int   oversampling;
  1565. {
  1566.     image_file = im_file;
  1567.  
  1568.     if (render_mode == LINE) {
  1569.         render_main(xres, yres, PBM_FILE, render_mode, oversampling, BOTH);
  1570.     } else {
  1571.         render_main(xres, yres, PPM_FILE, render_mode, oversampling, BOTH);
  1572.     }
  1573. }
  1574.  
  1575.  
  1576. void
  1577. render_image_func(xres, yres, pixel_func, data, render_mode, oversampling)
  1578.     int     xres, yres;
  1579.     void  (*pixel_func)();
  1580.     void   *data;
  1581.     int     render_mode;
  1582.     int     oversampling;
  1583. {
  1584.     im_data = data;
  1585.     pixel_set = pixel_func;
  1586.     render_main(xres, yres, FUNCTION, render_mode, oversampling, BOTH);
  1587. }
  1588.  
  1589.  
  1590. void
  1591. render_field_file(xres, yres, im_file, render_mode, oversampling, field)
  1592.     int   xres, yres;
  1593.     FILE *im_file;
  1594.     int   render_mode;
  1595.     int   oversampling;
  1596.     int   field;
  1597. {
  1598.     image_file = im_file;
  1599.  
  1600.     if (render_mode == LINE) {
  1601.         fprintf(stderr, "render_field_file: Can't render line fields\n");
  1602.         return;
  1603.     } else {
  1604.         render_main(xres, yres, PPM_FILE, render_mode, oversampling, field);
  1605.     }
  1606. }
  1607.  
  1608.  
  1609. void
  1610. render_field_func(xres, yres, pixel_func, data, render_mode, 
  1611.                   oversampling, field)
  1612.     int     xres, yres;
  1613.     void  (*pixel_func)();
  1614.     void   *data;
  1615.     int     render_mode;
  1616.     int     oversampling;
  1617.     int     field;
  1618. {
  1619.     if (render_mode == LINE) {
  1620.         fprintf(stderr, "render_field_func: Can't render line fields\n");
  1621.         return;
  1622.     }
  1623.  
  1624.     im_data = data;
  1625.     pixel_set = pixel_func;
  1626.     render_main(xres, yres, FUNCTION, render_mode, oversampling, field);
  1627. }
  1628.  
  1629.  
  1630.  
  1631.  
  1632. /*============= Functions that handles global initializations==============*/
  1633.  
  1634. /*
  1635.  * If the argument is TRUE, render the scanlines in reverse.
  1636.  */
  1637. void
  1638. sipp_render_direction (flag)
  1639.     bool flag;
  1640. {
  1641.     reverse_scan = flag;
  1642. /*    reverse_scan = FALSE; /**/
  1643. }
  1644.  
  1645. /*
  1646.  * If called with TRUE as argument, no backface culling will 
  1647.  * be performed. If a polygon is backfacing it will be rendered
  1648.  * as facing in the opposit direction.
  1649.  */
  1650. void
  1651. sipp_show_backfaces(flag)
  1652.     bool flag;
  1653. {
  1654.     show_backfaces = flag;
  1655. }
  1656.  
  1657.  
  1658. /*
  1659.  * If called with TRUE, objects will cast shadows. The second
  1660.  * argument is then used as the size of the depthmaps.
  1661.  */
  1662. void
  1663. sipp_shadows(flag, size)
  1664.     bool flag;
  1665.     int  size;
  1666. {
  1667.     if ((shadows = flag) == TRUE) {
  1668.         if (size != 0) {
  1669.             depthmap_size = size;
  1670.         } else {
  1671.             depthmap_size = 256;
  1672.         }
  1673.     }
  1674. }
  1675.  
  1676.  
  1677.  
  1678. /*
  1679.  * Set the backgroung color of the image.
  1680.  */
  1681. void
  1682. sipp_background(red, grn, blu)
  1683.     double red, grn, blu;
  1684. {
  1685.     sipp_bgcol.red = red;
  1686.     sipp_bgcol.grn = grn;
  1687.     sipp_bgcol.blu = blu;
  1688. }
  1689.  
  1690.  
  1691.  
  1692. /*
  1693.  * Necessary initializations.
  1694.  */
  1695. void
  1696. sipp_init()
  1697. {
  1698.     objects_init();
  1699.     lightsource_init();
  1700.     camera_init();
  1701.     sipp_show_backfaces(FALSE);
  1702.     sipp_shadows(FALSE, 0);
  1703.     sipp_render_direction(FALSE);
  1704.     sipp_background(0.0, 0.0, 0.0);
  1705. }
  1706.