home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / C⁄C++ / Peter's Final Project / src / render.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-10  |  13.3 KB  |  588 lines  |  [TEXT/KAHL]
  1. /*
  2.  *  Peter's Final Project -- A texture mapping demonstration
  3.  *  © 1995, Peter Mattis
  4.  *
  5.  *  E-mail:
  6.  *  petm@soda.csua.berkeley.edu
  7.  *
  8.  *  Snail-mail:
  9.  *   Peter Mattis
  10.  *   557 Fort Laramie Dr.
  11.  *   Sunnyvale, CA 94087
  12.  *
  13.  *  Avaible from:
  14.  *  http://www.csua.berkeley.edu/~petm/final.html
  15.  *
  16.  *  This program is free software; you can redistribute it and/or modify
  17.  *  it under the terms of the GNU General Public License as published by
  18.  *  the Free Software Foundation; either version 2 of the License, or
  19.  *  (at your option) any later version.
  20.  *
  21.  *  This program is distributed in the hope that it will be useful,
  22.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  23.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24.  *  GNU General Public License for more details.
  25.  *
  26.  *  You should have received a copy of the GNU General Public License
  27.  *  along with this program; if not, write to the Free Software
  28.  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  29.  */
  30.  
  31. #include <math.h>
  32. #include <stdio.h>
  33. #include <stdlib.h>
  34.  
  35. #include "clip.h"
  36. #include "face.h"
  37. #include "object.h"
  38. #include "point.h"
  39. #include "render.h"
  40. #include "scan.h"
  41. #include "sector.h"
  42. #include "sys.stuff.h"
  43.  
  44. /*
  45.  * Declare the functions private to this module.
  46.  */
  47.  
  48. static void render_reset (CAMERA);
  49. static void render_sectors (SECTOR);
  50. static short render_sector (SECTOR);
  51. static void render_object (OBJECT);
  52. static void render_sector_face (FACE);
  53. static void render_object_face (FACE, MATRIX, NUM, NUM, NUM);
  54. static POINTS render_transform (POINTS, MATRIX, short);
  55. static void render_shade (POINTS, VECTOR);
  56.  
  57. /*
  58.  * We keep track of the frame number here (as well as in "engine.c").
  59.  * For convience, store the current camera and its position at the
  60.  *  top level.
  61.  */
  62. static long frame_num = 0;
  63. static CAMERA cur_camera;
  64. static NUM x_pos, y_pos, z_pos;
  65.  
  66. /*
  67.  * Render a world from an objects view.
  68.  */
  69.  
  70. void
  71. do_render_world (o)
  72.     OBJECT o;
  73. {
  74.     scan_reset ();
  75.     render_reset (object_camera (o));
  76.     render_sectors (object_sector (o));
  77.     scan_finish ();
  78. }
  79.  
  80. /*
  81.  * Reset the renderer.
  82.  */
  83.  
  84. static void
  85. render_reset (c)
  86.     CAMERA c;
  87. {
  88.     cur_camera = c;
  89.  
  90.     x_pos = camera_pos_x (c);
  91.     y_pos = camera_pos_y (c);
  92.     z_pos = camera_pos_z (c);
  93.  
  94.     frame_num++;
  95. }
  96.  
  97. /*
  98.  * Render the sectors. (Here's where it all happens).
  99.  */
  100.  
  101. static void
  102. render_sectors (s)
  103.     SECTOR s;
  104. {
  105.     SECTORS sector_queue;
  106.     SECTORS neighbors;
  107.     SECTOR temp_sector;
  108.     LIST temp_list;
  109.  
  110.     /*
  111.      * The method used is to render the current sector,
  112.      *  then render all its neighbors, then render all
  113.      *  the neighbors neighbors, etc. We make sure to
  114.      *  not render a sector twice by setting its val to
  115.      *  the frame number. If a sectors val is less than
  116.      *  the frame number, then it needs to be rendered.
  117.      * Basically, we traverse the graph of sectors starting
  118.      *  from the current sector in a breadth first search.
  119.      *  To this end, we'll use a queue. A sector will only
  120.      *  get placed on the queue if it is to be drawn. When
  121.      *  the sector is drawn, we place its neighbors on the
  122.      *  stack.
  123.      */
  124.     
  125.     /*
  126.      * Always draw the start sector. So lets place it on
  127.      *  the queue.
  128.      */
  129.     set_sector_val (s, frame_num);
  130.     sector_queue = sectors_add_sector ((SECTORS) NULL, s);
  131.  
  132.     /*
  133.      * While there are sectors in the queue...
  134.      */
  135.     while (sector_queue)
  136.     {
  137.         /*
  138.          * Get the next sector on the queue and draw it.
  139.          * "render_sector" will return true if the screen
  140.          *  is filled. (Which means we should quit).
  141.          */
  142.         s = sectors_first (sector_queue);
  143.         if (render_sector (s))
  144.             break;
  145.  
  146.         /*
  147.          * Take that first link on the sector queue and
  148.          *  delete it.
  149.          */
  150.         temp_list = sector_queue;
  151.         sector_queue = sectors_rest (sector_queue);
  152.  
  153.         free_list (temp_list);
  154.  
  155.         /*
  156.          * Add all of the sectors neighbors to the queue,
  157.          *  but only if they haven't been drawn already.
  158.          */
  159.         neighbors = sector_neighbors (s);
  160.         while (neighbors)
  161.         {
  162.             temp_sector = sectors_first (neighbors);
  163.             neighbors = sectors_rest (neighbors);
  164.  
  165.             if (sector_val (temp_sector) < frame_num)
  166.             {
  167.                 set_sector_val (temp_sector, frame_num);
  168.                 sector_queue = sectors_append_sector (sector_queue, temp_sector);
  169.             }
  170.         }
  171.     }
  172.  
  173.     /*
  174.      * The sector queue might still have items in it if
  175.      *  rendering ended early. (Which, hopefully it did).
  176.      *  So we need to destroy the queue.
  177.      */
  178.     while (sector_queue)
  179.     {
  180.         temp_list = sector_queue;
  181.         sector_queue = sectors_rest (sector_queue);
  182.         free_list (temp_list);
  183.     }
  184. }
  185.  
  186. /*
  187.  * Render a single sector.
  188.  */
  189.  
  190. static short
  191. render_sector (s)
  192.     SECTOR s;
  193. {
  194.     OBJECTS objects;
  195.     OBJECT object;
  196.     FACES faces;
  197.     FACE face;
  198.  
  199.     /*
  200.      * First render the objects in this sector. I really
  201.      *  don't handle this correctly. I should depth sort
  202.      *  the objects and draw them from front to back.
  203.      */
  204.     objects = sector_objects (s);
  205.     while (objects)
  206.     {
  207.         object = objects_first (objects);
  208.         objects = objects_rest (objects);
  209.  
  210.         render_object (object);
  211.     }
  212.  
  213.     /*
  214.      * Next render the faces in this sector.
  215.      */
  216.     faces = sector_faces (s);
  217.     while (faces)
  218.     {
  219.         face = faces_first (faces);
  220.         faces = faces_rest (faces);
  221.  
  222.         render_sector_face (face);
  223.     }
  224.  
  225.     /*
  226.      * Return whether we are finished yet, or not.
  227.      */
  228.     return scan_complete ();
  229. }
  230.  
  231. /*
  232.  * Render an object.
  233.  */
  234.  
  235. static void
  236. render_object (o)
  237.     OBJECT o;
  238. {
  239.     FACES faces;
  240.     FACE face;
  241.     MATRIX m1, m2, m3, m4;
  242.     VECTOR u, v, n;
  243.  
  244.     /*
  245.      * Only render the object if it hasn't been rendered
  246.      *  already. An object may be rendered multiple times
  247.      *  because it can overlap multiple sectors (getting
  248.      *  drawn by each sector). 
  249.      */
  250.     if (object_val (o) < frame_num)
  251.     {
  252.         set_object_val (o, frame_num);
  253.  
  254.         /*
  255.          * Set up a matrix that rotates the object. Without
  256.          *  this, an object would not appear to rotate as
  257.          *  it turned.
  258.          */
  259.         set_vector_x (n, object_dir_x (o));
  260.         set_vector_y (n, object_dir_y (o));
  261.         set_vector_z (n, object_dir_z (o));
  262.         set_vector_w (n, NUM_ZERO);
  263.  
  264.         set_vector_x (v, NUM_ZERO);
  265.         set_vector_y (v, -NUM_ONE);
  266.         set_vector_z (v, NUM_ZERO);
  267.         set_vector_w (v, NUM_ZERO);
  268.  
  269.         vector_cross (v, n, u);
  270.         set_vector_w (u, NUM_ZERO);
  271.  
  272.         matrix_clear (m1);
  273.         vector_copy (u, m1[0]);
  274.         vector_copy (v, m1[1]);
  275.         vector_copy (n, m1[2]);
  276.  
  277.         /*
  278.          * Set up a matrix to translate the object. Without
  279.          *  this, an object would not appear to move.
  280.          */
  281.         matrix_translate (m2, object_pos_x (o), object_pos_y (o), object_pos_z (o));
  282.  
  283.         /*
  284.          * Compose the two matrices with the objects own matrix.
  285.          */
  286.         matrix_compose (m1, object_matrix (o), m3);
  287.         matrix_compose (m2, m3, m4);
  288.  
  289.         /*
  290.          * Then simply render every face in the object with
  291.          *  the composited matrix.
  292.          */
  293.         faces = object_faces (o);
  294.         while (faces)
  295.         {
  296.             face = faces_first (faces);
  297.             faces = faces_rest (faces);
  298.  
  299.             render_object_face (face, m4, object_red (o), object_green (o), object_blue (o));
  300.         }
  301.     }
  302. }
  303.  
  304. /*
  305.  * Render a face of a sector. (They're textured).
  306.  */
  307.  
  308. static void
  309. render_sector_face (f)
  310.     FACE f;
  311. {
  312.     POINTS t_pts;
  313.     POINTS c_pts;
  314.     POINTS p_pts;
  315.     POINT p;
  316.     VECTOR v1, v2, n;
  317.     VECTOR to, tu, tv;
  318.     NUM dot;
  319.  
  320.     /*
  321.      * Determine if this face is front facing or not.
  322.      *  (ie Should it be backface culled).
  323.      */
  324.     p = points_first (face_points (f));
  325.     vector_copy (point_coord (p), v1);
  326.     vector_copy (point_coord (face_normal (f)), n);
  327.     vector_sub (camera_pos (cur_camera), v1, v2);
  328.  
  329.     dot = vector_dot (v2, n);
  330.     if (dot > 0)
  331.     {
  332.         /*
  333.          * Transform the face by the orientation matrix.
  334.          */
  335.         t_pts = render_transform (face_points (f), camera_matrix_orientation (cur_camera), 0);
  336.         
  337.         /*
  338.          * Clip the face to the view volume.
  339.          */
  340.         c_pts = clip_polygon (t_pts);
  341.  
  342.         /*
  343.          * If something remains after clipping...
  344.          */
  345.         if (c_pts)
  346.         {
  347.             /*
  348.              * Transform what remains by the mapping matrix.
  349.              * We also set the "screenify" flag which tells "render_transform"
  350.              *  to homogenize the new points and to round there x and y values.
  351.              *  The homogenization accomplishes the perspective division. The
  352.              *  rounding takes care of truncation artefacts.
  353.              */
  354.             p_pts = render_transform (c_pts, camera_matrix_mapping (cur_camera), 1);
  355.  
  356.             /*
  357.              * Transform the texture points by the orientation matrix.
  358.              */
  359.             matrix_vector (camera_matrix_orientation (cur_camera), point_coord (face_texture_o (f)), to);
  360.             matrix_vector (camera_matrix_orientation (cur_camera), point_coord (face_texture_u (f)), v1);
  361.             matrix_vector (camera_matrix_orientation (cur_camera), point_coord (face_texture_v (f)), v2);
  362.             
  363.             /*
  364.              * Calculate the texture vectors from the transform texture points.
  365.              */
  366.             vector_sub (v1, to, tu);
  367.             vector_sub (v2, to, tv);
  368.  
  369.             /*
  370.              * Transform the normal by the orientation matrix.
  371.              */
  372.             matrix_vector (camera_matrix_orientation (cur_camera), point_coord (face_normal (f)), n);
  373.  
  374.             /*
  375.              * Use the texture mapping scan conversion function.
  376.              */
  377.             scan_texture (p_pts, n, to, tu, tv, face_texture (f));
  378.  
  379.             /*
  380.              * Free the clipped and project points.
  381.              * (The clipping function free'd the transformed points).
  382.              */
  383.             free_points (c_pts);
  384.             free_points (p_pts);
  385.         }
  386.     }
  387. }
  388.  
  389. /*
  390.  * Render an object of a sector. (They're Gourad shaded).
  391.  */
  392.  
  393. static void
  394. render_object_face (f, m, r, g, b)
  395.     FACE f;
  396.     MATRIX m;
  397.     NUM r, g, b;
  398. {
  399.     POINTS t_pts;
  400.     POINTS c_pts;
  401.     POINTS p_pts;
  402.     POINT p;
  403.     VECTOR v1, v2, n;
  404.     NUM dot;
  405.     MATRIX mat;
  406.  
  407.     /*
  408.      * Determine if this face is front facing or not.
  409.      *  (ie Should it be backface culled).
  410.      * This is a little bit more complicated than with
  411.      *  sector faces since we must multiply the vectors
  412.      *  by the passed in matrix.
  413.      */
  414.     p = points_first (face_points (f));
  415.     matrix_vector (m, point_coord (p), v1);
  416.     matrix_vector (m, point_coord (face_normal (f)), n);
  417.     vector_sub (camera_pos (cur_camera), v1, v2);
  418.  
  419.     dot = vector_dot (v2, n);
  420.     if (dot > 0)
  421.     {
  422.         /*
  423.          * Compose the new orientation matrix.
  424.          */
  425.         matrix_compose (camera_matrix_orientation (cur_camera), m, mat);
  426.         
  427.         /*
  428.          * Transform the face by the new orientation matrix.
  429.          */
  430.         t_pts = render_transform (face_points (f), mat, 0);
  431.  
  432.         /*
  433.          * At this point the face is shaded. Intensity values
  434.          *  are calculated for each point. (The transformed normal
  435.          *  to the face is needed for this calculation).
  436.          */
  437.         matrix_vector (mat, point_coord (face_normal (f)), n);
  438.         vector_normalize (n);
  439.         render_shade (t_pts, n);
  440.  
  441.         /*
  442.          * Clip the face to the view volume.
  443.          */
  444.         c_pts = clip_polygon (t_pts);
  445.  
  446.         /*
  447.          * If something remains after clipping...
  448.          */
  449.         if (c_pts)
  450.         {
  451.             /*
  452.              * Transform what remains by the mapping matrix.
  453.              * We also set the "screenify" flag which tells "render_transform"
  454.              *  to homogenize the new points and to round there x and y values.
  455.              *  The homogenization accomplishes the perspective division. The
  456.              *  rounding takes care of truncation artefacts.
  457.              */
  458.             p_pts = render_transform (c_pts, camera_matrix_mapping (cur_camera), 1);
  459.  
  460.             /*
  461.              * Use the shading scan conversion function.
  462.              */
  463.             scan_shade (p_pts, r, g, b);
  464.  
  465.             /*
  466.              * Free the clipped and project points.
  467.              * (The clipping function free'd the transformed points).
  468.              */
  469.             free_points (c_pts);
  470.             free_points (p_pts);
  471.         }
  472.     }
  473. }
  474.  
  475. /*
  476.  * Transform a list of points by a matrix and return
  477.  *  a new list of the transformed points.
  478.  */
  479.  
  480. static POINTS
  481. render_transform (pts, m, screenify)
  482.     POINTS pts;
  483.     MATRIX m;
  484.     short screenify;
  485. {
  486.     POINTS new_pts = NULL;
  487.     POINT pt, new_pt;
  488.  
  489.     /*
  490.      * Simply apply the matrix to every point in the list,
  491.      *  building up a new list as we go.
  492.      * Notice that the order of the points in the new list
  493.      *  may be reversed, but we don't care. (Actually, at 
  494.      *  present, the points are reversed).
  495.      */
  496.     while (pts)
  497.     {
  498.         pt = points_first (pts);
  499.         pts = points_rest (pts);
  500.  
  501.         new_pt = make_point ();
  502.         new_pts = points_add_point (new_pts, new_pt);
  503.  
  504.         matrix_vector (m, point_coord (pt), point_coord (new_pt));
  505.         set_point_intensity (new_pt, point_intensity (pt));
  506.  
  507.         /*
  508.          * Homogenize and round if desired.
  509.          */
  510.         if (screenify)
  511.         {
  512.             vector_homogenize (point_coord (new_pt));
  513.             set_point_x (new_pt, my_num_to_int (ROUND (point_x (new_pt))));
  514.             set_point_y (new_pt, my_num_to_int (ROUND (point_y (new_pt))));
  515.             set_point_z (new_pt, point_z (pt));
  516.         }
  517.     }
  518.  
  519.     return new_pts;
  520. }
  521.  
  522. /*
  523.  * Shade the list of points.
  524.  */
  525.  
  526. static void
  527. render_shade (pts, normal)
  528.     POINTS pts;
  529.     VECTOR normal;
  530. {
  531.     POINT pt;
  532.     VECTOR light;
  533.     NUM dot;
  534.     NUM dist;
  535.     NUM intensity;
  536.  
  537.     while (pts)
  538.     {
  539.         pt = points_first (pts);
  540.         pts = points_rest (pts);
  541.  
  542.         /*
  543.          * The light vector is the vector from the point to
  544.          * the light source (the viewer...at the origin).
  545.          */
  546.         set_vector_x (light, -point_x (pt));
  547.         set_vector_y (light, -point_y (pt));
  548.         set_vector_z (light, -point_z (pt));
  549.         
  550.         /*
  551.          * Normalize the light vector so that dot product
  552.          *  calculations relate to the angle between vectors.
  553.          */
  554.         vector_normalize (light);
  555.  
  556.         /*
  557.          * Calculate the cosine of the angle between the
  558.          *  normal and the light vector.
  559.          * Also calculate the distance to the point.
  560.          */
  561.         dot = vector_dot (normal, light);
  562.         dist = vector_magnitude (point_coord (pt));
  563.         if (dist < NUM_ONE)
  564.             dist = NUM_ONE;
  565.  
  566.         /*
  567.          * The lighting of the point depends partially on ambient
  568.          *  light (0.3) and partially on diffuse reflect light (0.7).
  569.          */
  570.         intensity = my_mul (my_float_to_num (0.7), dot) + my_float_to_num (0.3);
  571.         
  572.         /*
  573.          * Divide the intensity by the points distance and clamp
  574.          *  the intensity between 0 and 1.
  575.          */
  576.         intensity = my_div (intensity, my_mul (dist, NUM_ONE));
  577.         if (intensity > NUM_ONE)
  578.             intensity = NUM_ONE;
  579.         if (intensity < NUM_ZERO)
  580.             intensity = NUM_ZERO;
  581.  
  582.         /*
  583.          * Set the points intensity.
  584.          */
  585.         set_point_intensity (pt, intensity);
  586.     }
  587. }
  588.