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 / clip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-10  |  10.6 KB  |  487 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 "clip.h"
  32. #include "matrix.vector.h"
  33. #include "sys.stuff.h"
  34.  
  35. /*
  36.  * Define some cases for clipping
  37.  */
  38.  
  39. #define TRIVIAL_ACCEPT 1
  40. #define TRIVIAL_REJECT 2
  41. #define NON_TRIVIAL    3
  42.  
  43. /*
  44.  * Define some function types. We need a comparison
  45.  *  function and an intersection function.
  46.  */
  47.  
  48. typedef short (*CLIP_COMPARE) (POINT);
  49. typedef short (*CLIP_INTERSECT) (POINT, POINT, POINT *);
  50.  
  51. /*
  52.  * Declare the functions private to this module.
  53.  */
  54.  
  55. static short clip_calculate_case (POINTS);
  56. static POINTS clip_plane (POINTS, CLIP_COMPARE, CLIP_INTERSECT);
  57.  
  58. static short clip_compare_all (POINT);
  59. static short clip_compare_left (POINT);
  60. static short clip_compare_right (POINT);
  61. static short clip_compare_top (POINT);
  62. static short clip_compare_bottom (POINT);
  63. static short clip_compare_front (POINT);
  64.  
  65. static short clip_left (POINT, POINT, POINT *);
  66. static short clip_right (POINT, POINT, POINT *);
  67. static short clip_top (POINT, POINT, POINT *);
  68. static short clip_bottom (POINT, POINT, POINT *);
  69. static short clip_front (POINT, POINT, POINT *);
  70.  
  71. /*
  72.  * We need to know what the front clipping plane
  73.  *  distance is. Make sure the value is valid even
  74.  *  if it is never set by the program.
  75.  */
  76. static NUM z_min = NUM_ONE * 0.1;
  77.  
  78. /*
  79.  * Sets the 'z_min' clip value.
  80.  */
  81.  
  82. void
  83. clip_set_z_min (new_z_min)
  84.     NUM new_z_min;
  85. {
  86.     z_min = new_z_min;
  87. }
  88.  
  89. /*
  90.  * Clips the polygon defined by 'points' to the clip rectangle
  91.  *  defined by 'x_min', 'x_max', 'y_min', and 'y_max'.
  92.  * It returns the clipped polygon.
  93.  * Note: This function may possibly destroy the points passed
  94.  *       into it. So be sure not to pass in any points that you
  95.  *       don't want destroyed. (i.e. Make a copy first).
  96.  * 
  97.  * I do some hanky, panky #define magic in this function. Read
  98.  *  up in K&R to see what the '##' does in defines. It's really
  99.  *  quite neat.
  100.  */
  101.  
  102. POINTS
  103. clip_polygon (points)
  104.     POINTS points;
  105. {
  106. #define CLIP(plane)   clip_compare_##plane, clip_##plane
  107.  
  108.     switch (clip_calculate_case (points))
  109.     {
  110.     case TRIVIAL_ACCEPT:
  111.         return points;
  112.         break;
  113.     case TRIVIAL_REJECT:
  114.         return NULL;
  115.         break;
  116.     }
  117.  
  118.     /*
  119.      * Clip to the left, right, bottom, top, front and back planes using a
  120.      *  generic 'clip_plane' routine.
  121.      * Only continue to clip if the polygon has not degenerated.
  122.      */
  123.  
  124.     if ((points = clip_plane (points, CLIP (front))) != NULL)
  125.         if ((points = clip_plane (points, CLIP (left))) != NULL)
  126.             if ((points = clip_plane (points, CLIP (right))) != NULL)
  127.                 if ((points = clip_plane (points, CLIP (bottom))) != NULL)
  128.                     points = clip_plane (points, CLIP (top));
  129.  
  130.     return points;
  131. }
  132.  
  133. /*
  134.  * Determine if the polygon to be clipped is a trivial case.
  135.  */
  136.  
  137. static short
  138. clip_calculate_case (points)
  139.     POINTS points;
  140. {
  141.     POINT point;
  142.  
  143.     if (points)
  144.     {
  145.         while (points)
  146.         {
  147.             point = points_first (points);
  148.             points = points_rest (points);
  149.  
  150.             if (!clip_compare_all (point))
  151.                 return NON_TRIVIAL;
  152.         }
  153.  
  154.         return TRIVIAL_ACCEPT;
  155.     }
  156.  
  157.     return TRIVIAL_REJECT;
  158. }
  159.  
  160. /*
  161.  * Clips the polygon defined by 'points' to a given edge.
  162.  * Note: This is basically the Sutherland-Hodgeman clipping
  163.  *       algorithm given in the book. The 'inside' and 'intersect'
  164.  *       functions are present so that the same routine can be
  165.  *       used to clip against each of the four clip edges.
  166.  */
  167.  
  168. static POINTS
  169. clip_plane (points, inside, intersect)
  170.     POINTS points;
  171.     CLIP_COMPARE inside;
  172.     CLIP_INTERSECT intersect;
  173. {
  174. /*
  175.  * Use some defines to simplify calling the compare function
  176.  *  and to make output of polygons look nicer. (Makes the code
  177.  *  more readable.
  178.  */
  179. #define OUTPUT(set, p)         (set) = points_add_point((set), (p))
  180. #define INSIDE(p)              ((*inside) (p))
  181. #define INTERSECT(p1, p2, p3)  ((*intersect) (p1, p2, p3))
  182. #define CLONE_POINT(p)         (point_clone(p))
  183.  
  184.     POINTS out_points;
  185.     POINTS local_points;
  186.     POINT current_point;
  187.     POINT next_point;
  188.     POINT new_point;
  189.  
  190.     out_points = NULL;
  191.     local_points = points;
  192.     current_point = points_first (points_last (local_points));
  193.  
  194.     /*
  195.      * While there are still points in the polygon...
  196.      */
  197.     while (local_points)
  198.     {
  199.         /*
  200.          * Set 'next_point' to the first of the remaining points to clip.
  201.          */
  202.         next_point = points_first (local_points);
  203.  
  204.         /*
  205.          * If the point is inside (the current clip boundary)...
  206.          */
  207.         if (INSIDE (current_point))
  208.         {
  209.             /*
  210.              * ...then output 'current_point'...
  211.              */
  212.  
  213.             OUTPUT (out_points, CLONE_POINT (current_point));
  214.  
  215.             /*
  216.              * ...and if 'next_point' is outside the current clip boundary
  217.              *  then clip the line to the clip boundary and output the new
  218.              *  point.
  219.              */
  220.             if (!INSIDE (next_point))
  221.             {
  222.                 INTERSECT (current_point, next_point, &new_point);
  223.                 OUTPUT (out_points, new_point);
  224.             }
  225.         }
  226.         else if (INSIDE (next_point))
  227.         {
  228.             /*
  229.              * ...else if 'next_point' is inside the clip boundary,
  230.              *  then clip the line to the clip boundary and output the
  231.              *  new point.
  232.              */
  233.             INTERSECT (current_point, next_point, &new_point);
  234.             OUTPUT (out_points, new_point);
  235.         }
  236.  
  237.         /*
  238.          * Increment to the next point.
  239.          */
  240.         local_points = points_rest (local_points);
  241.         current_point = next_point;
  242.     }
  243.  
  244.     /*
  245.      * Free up the points passed in.
  246.      */
  247.     free_points (points);
  248.  
  249.     /*
  250.      * Return the clipped points.
  251.      */
  252.     return out_points;
  253. }
  254.  
  255. /*
  256.  * Compare the point to all clip planes.
  257.  */
  258.  
  259. static short
  260. clip_compare_all (p)
  261.     POINT p;
  262. {
  263.     return (clip_compare_left (p) & clip_compare_right (p) &
  264.         clip_compare_top (p) & clip_compare_bottom (p) &
  265.         clip_compare_front (p));
  266. }
  267.  
  268. /*
  269.  * Compare the point to the left clip plane.
  270.  */
  271.  
  272. static short
  273. clip_compare_left (p)
  274.     POINT p;
  275. {
  276.     return (point_x (p) >= point_z (p));
  277. }
  278.  
  279. /*
  280.  * Compare the point to the right clip plane.
  281.  */
  282.  
  283. static short
  284. clip_compare_right (p)
  285.     POINT p;
  286. {
  287.     return (point_x (p) <= -point_z (p));
  288. }
  289.  
  290. /*
  291.  * Compare the point to the top clip plane.
  292.  */
  293.  
  294. static short
  295. clip_compare_top (p)
  296.     POINT p;
  297. {
  298.     return (point_y (p) <= -point_z (p));
  299. }
  300.  
  301. /*
  302.  * Compare the point to the bottom clip plane.
  303.  */
  304.  
  305. static short
  306. clip_compare_bottom (p)
  307.     POINT p;
  308. {
  309.     return (point_y (p) >= point_z (p));
  310. }
  311.  
  312. /*
  313.  * Compare the point to the front clip plane.
  314.  */
  315.  
  316. static short
  317. clip_compare_front (p)
  318.     POINT p;
  319. {
  320.     return (point_z (p) <= z_min);
  321. }
  322.  
  323. /*
  324.  * Clip the segment to the left clip plane.
  325.  */
  326.  
  327. static short
  328. clip_left (start, end, p)
  329.     POINT start, end, *p;
  330. {
  331.     NUM t, dx, dy, dz, di;
  332.     short val;
  333.  
  334.     dx = point_x (end) - point_x (start);
  335.     dy = point_y (end) - point_y (start);
  336.     dz = point_z (end) - point_z (start);
  337.     di = point_intensity (end) - point_intensity (start);
  338.  
  339.     t = my_div (-point_x (start) + point_z (start), dx - dz);
  340.     if ((t == NUM_ZERO) || (t == NUM_ONE))
  341.         val = 0;
  342.     else
  343.         val = 1;
  344.  
  345.     *p = make_point ();
  346.     set_point_x (*p, point_x (start) + my_mul (dx, t));
  347.     set_point_y (*p, point_y (start) + my_mul (dy, t));
  348.     set_point_z (*p, point_z (start) + my_mul (dz, t));
  349.     set_point_w (*p, NUM_ONE);
  350.  
  351.     set_point_intensity (*p, point_intensity (start) + my_mul (di, t));
  352.  
  353.     return val;
  354. }
  355.  
  356. /*
  357.  * Clip the segment to the right clip plane.
  358.  */
  359.  
  360. static short
  361. clip_right (start, end, p)
  362.     POINT start, end, *p;
  363. {
  364.     NUM t, dx, dy, dz, di;
  365.     short val;
  366.  
  367.     dx = point_x (end) - point_x (start);
  368.     dy = point_y (end) - point_y (start);
  369.     dz = point_z (end) - point_z (start);
  370.     di = point_intensity (end) - point_intensity (start);
  371.  
  372.     t = my_div (point_x (start) + point_z (start), -dx - dz);
  373.     if ((t == NUM_ZERO) || (t == NUM_ONE))
  374.         val = 0;
  375.     else
  376.         val = 1;
  377.  
  378.     *p = make_point ();
  379.     set_point_x (*p, point_x (start) + my_mul (dx, t));
  380.     set_point_y (*p, point_y (start) + my_mul (dy, t));
  381.     set_point_z (*p, point_z (start) + my_mul (dz, t));
  382.     set_point_w (*p, NUM_ONE);
  383.  
  384.     set_point_intensity (*p, point_intensity (start) + my_mul (di, t));
  385.  
  386.     return val;
  387. }
  388.  
  389. /*
  390.  * Clip the segment to the top clip plane.
  391.  */
  392.  
  393. static short
  394. clip_top (start, end, p)
  395.     POINT start, end, *p;
  396. {
  397.     NUM t, dx, dy, dz, di;
  398.     short val;
  399.  
  400.     dx = point_x (end) - point_x (start);
  401.     dy = point_y (end) - point_y (start);
  402.     dz = point_z (end) - point_z (start);
  403.     di = point_intensity (end) - point_intensity (start);
  404.  
  405.     t = my_div (point_y (start) + point_z (start), -dy - dz);
  406.     if ((t == NUM_ZERO) || (t == NUM_ONE))
  407.         val = 0;
  408.     else
  409.         val = 1;
  410.  
  411.     *p = make_point ();
  412.     set_point_x (*p, point_x (start) + my_mul (dx, t));
  413.     set_point_y (*p, point_y (start) + my_mul (dy, t));
  414.     set_point_z (*p, point_z (start) + my_mul (dz, t));
  415.     set_point_w (*p, NUM_ONE);
  416.  
  417.     set_point_intensity (*p, point_intensity (start) + my_mul (di, t));
  418.  
  419.     return val;
  420. }
  421.  
  422. /*
  423.  * Clip the segment to the bottom clip plane.
  424.  */
  425.  
  426. static short
  427. clip_bottom (start, end, p)
  428.     POINT start, end, *p;
  429. {
  430.     NUM t, dx, dy, dz, di;
  431.     short val;
  432.  
  433.     dx = point_x (end) - point_x (start);
  434.     dy = point_y (end) - point_y (start);
  435.     dz = point_z (end) - point_z (start);
  436.     di = point_intensity (end) - point_intensity (start);
  437.  
  438.     t = my_div (-point_y (start) + point_z (start), dy - dz);
  439.     if ((t == NUM_ZERO) || (t == NUM_ONE))
  440.         val = 0;
  441.     else
  442.         val = 1;
  443.  
  444.     *p = make_point ();
  445.     set_point_x (*p, point_x (start) + my_mul (dx, t));
  446.     set_point_y (*p, point_y (start) + my_mul (dy, t));
  447.     set_point_z (*p, point_z (start) + my_mul (dz, t));
  448.     set_point_w (*p, NUM_ONE);
  449.  
  450.     set_point_intensity (*p, point_intensity (start) + my_mul (di, t));
  451.  
  452.     return val;
  453. }
  454.  
  455. /*
  456.  * Clip the segment to the front clip plane.
  457.  */
  458.  
  459. static short
  460. clip_front (start, end, p)
  461.     POINT start, end, *p;
  462. {
  463.     NUM t, dx, dy, dz, di;
  464.     short val;
  465.  
  466.     dx = point_x (end) - point_x (start);
  467.     dy = point_y (end) - point_y (start);
  468.     dz = point_z (end) - point_z (start);
  469.     di = point_intensity (end) - point_intensity (start);
  470.  
  471.     t = my_div (point_z (start) - z_min, -dz);
  472.     if ((t == NUM_ZERO) || (t == NUM_ONE))
  473.         val = 0;
  474.     else
  475.         val = 1;
  476.  
  477.     *p = make_point ();
  478.     set_point_x (*p, point_x (start) + my_mul (dx, t));
  479.     set_point_y (*p, point_y (start) + my_mul (dy, t));
  480.     set_point_z (*p, point_z (start) + my_mul (dz, t));
  481.     set_point_w (*p, NUM_ONE);
  482.  
  483.     set_point_intensity (*p, point_intensity (start) + my_mul (di, t));
  484.  
  485.     return val;
  486. }
  487.