3d/clipper.c

   1 /*
   2 THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
   3 SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
   4 END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
   5 ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
   6 IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
   7 SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
   8 FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
   9 CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  10 AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
  11 COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12 */
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include <conf.h>
  16 #endif
  17
  18 #include "fix.h"
  19 #include "vecmat.h"
  20 #include "gr.h"
  21 #include "3d.h"
  22 #include "globvars.h"
  23 #include "clipper.h"
  24 #include "error.h"
  25
  26 int free_point_num=0;
  27
  28 g3s_point temp_points[MAX_POINTS_IN_POLY];
  29 g3s_point *free_points[MAX_POINTS_IN_POLY];
  30
  31 void init_free_points(void)
  32 {
  33         int i;
  34
  35         for (i=0;i<MAX_POINTS_IN_POLY;i++)
  36                 free_points[i] = &temp_points[i];
  37 }
  38
  39
  40 g3s_point *get_temp_point()
  41 {
  42         g3s_point *p;
  43
  44         Assert (free_point_num < MAX_POINTS_IN_POLY );
  45         p = free_points[free_point_num++];
  46
  47         p->p3_flags = PF_TEMP_POINT;
  48
  49         return p;
  50 }
  51
  52 void free_temp_point(g3s_point *p)
  53 {
  54         Assert(p->p3_flags & PF_TEMP_POINT);
  55
  56         free_points[--free_point_num] = p;
  57
  58         p->p3_flags &= ~PF_TEMP_POINT;
  59 }
  60
  61 //clips an edge against one plane.
  62 g3s_point *clip_edge(int plane_flag,g3s_point *on_pnt,g3s_point *off_pnt)
  63 {
  64         fix psx_ratio;
  65         fix a,b,kn,kd;
  66         g3s_point *tmp;
  67
  68         //compute clipping value k = (xs-zs) / (xs-xe-zs+ze)
  69         //use x or y as appropriate, and negate x/y value as appropriate
  70
  71         if (plane_flag & (CC_OFF_RIGHT | CC_OFF_LEFT)) {
  72                 a = on_pnt->p3_x;
  73                 b = off_pnt->p3_x;
  74         }
  75         else {
  76                 a = on_pnt->p3_y;
  77                 b = off_pnt->p3_y;
  78         }
  79
  80         if (plane_flag & (CC_OFF_LEFT | CC_OFF_BOT)) {
  81                 a = -a;
  82                 b = -b;
  83         }
  84
  85         kn = a - on_pnt->p3_z;                                          //xs-zs
  86         kd = kn - b + off_pnt->p3_z;                            //xs-zs-xe+ze
  87
  88         tmp = get_temp_point();
  89
  90         psx_ratio = fixdiv( kn, kd );
  91
  92
  93 // PSX_HACK!!!!
  94 //      tmp->p3_x = on_pnt->p3_x + fixmuldiv(off_pnt->p3_x-on_pnt->p3_x,kn,kd);
  95 //      tmp->p3_y = on_pnt->p3_y + fixmuldiv(off_pnt->p3_y-on_pnt->p3_y,kn,kd);
  96
  97         tmp->p3_x = on_pnt->p3_x + fixmul( (off_pnt->p3_x-on_pnt->p3_x), psx_ratio);
  98         tmp->p3_y = on_pnt->p3_y + fixmul( (off_pnt->p3_y-on_pnt->p3_y), psx_ratio);
  99
 100         if (plane_flag & (CC_OFF_TOP|CC_OFF_BOT))
 101                 tmp->p3_z = tmp->p3_y;
 102         else
 103                 tmp->p3_z = tmp->p3_x;
 104
 105         if (plane_flag & (CC_OFF_LEFT|CC_OFF_BOT))
 106                 tmp->p3_z = -tmp->p3_z;
 107
 108         if (on_pnt->p3_flags & PF_UVS) {
 109 // PSX_HACK!!!!
 110 //              tmp->p3_u = on_pnt->p3_u + fixmuldiv(off_pnt->p3_u-on_pnt->p3_u,kn,kd);
 111 //              tmp->p3_v = on_pnt->p3_v + fixmuldiv(off_pnt->p3_v-on_pnt->p3_v,kn,kd);
 112                 tmp->p3_u = on_pnt->p3_u + fixmul((off_pnt->p3_u-on_pnt->p3_u), psx_ratio);
 113                 tmp->p3_v = on_pnt->p3_v + fixmul((off_pnt->p3_v-on_pnt->p3_v), psx_ratio);
 114
 115                 tmp->p3_flags |= PF_UVS;
 116         }
 117
 118         if (on_pnt->p3_flags & PF_LS) {
 119 // PSX_HACK
 120 //              tmp->p3_r = on_pnt->p3_r + fixmuldiv(off_pnt->p3_r-on_pnt->p3_r,kn,kd);
 121 //              tmp->p3_g = on_pnt->p3_g + fixmuldiv(off_pnt->p3_g-on_pnt->p3_g,kn,kd);
 122 //              tmp->p3_b = on_pnt->p3_b + fixmuldiv(off_pnt->p3_b-on_pnt->p3_b,kn,kd);
 123
 124                 tmp->p3_l = on_pnt->p3_l + fixmul((off_pnt->p3_l-on_pnt->p3_l), psx_ratio);
 125
 126                 tmp->p3_flags |= PF_LS;
 127         }
 128
 129         g3_code_point(tmp);
 130
 131         return tmp;
 132 }
 133
 134 //clips a line to the viewing pyramid.
 135 void clip_line(g3s_point **p0,g3s_point **p1,ubyte codes_or)
 136 {
 137         int plane_flag;
 138         g3s_point *old_p1;
 139
 140         //might have these left over
 141         (*p0)->p3_flags &= ~(PF_UVS|PF_LS);
 142         (*p1)->p3_flags &= ~(PF_UVS|PF_LS);
 143
 144         for (plane_flag=1;plane_flag<16;plane_flag<<=1)
 145                 if (codes_or & plane_flag) {
 146
 147                         if ((*p0)->p3_codes & plane_flag)
 148                                 {g3s_point *t=*p0; *p0=*p1; *p1=t;}     //swap!
 149
 150                         old_p1 = *p1;
 151
 152                         *p1 = clip_edge(plane_flag,*p0,*p1);
 153
 154                         if (old_p1->p3_flags & PF_TEMP_POINT)
 155                                 free_temp_point(old_p1);
 156                 }
 157
 158 }
 159
 160
 161 int clip_plane(int plane_flag,g3s_point **src,g3s_point **dest,int *nv,g3s_codes *cc)
 162 {
 163         int i;
 164         g3s_point **save_dest=dest;
 165
 166         //copy first two verts to end
 167         src[*nv] = src[0];
 168         src[*nv+1] = src[1];
 169
 170         cc->and = 0xff; cc->or = 0;
 171
 172         for (i=1;i<=*nv;i++) {
 173
 174                 if (src[i]->p3_codes & plane_flag) {                            //cur point off?
 175
 176                         if (! (src[i-1]->p3_codes & plane_flag)) {      //prev not off?
 177
 178                                 *dest = clip_edge(plane_flag,src[i-1],src[i]);
 179                                 cc->or  |= (*dest)->p3_codes;
 180                                 cc->and &= (*dest)->p3_codes;
 181                                 dest++;
 182                         }
 183
 184                         if (! (src[i+1]->p3_codes & plane_flag)) {
 185
 186                                 *dest = clip_edge(plane_flag,src[i+1],src[i]);
 187                                 cc->or  |= (*dest)->p3_codes;
 188                                 cc->and &= (*dest)->p3_codes;
 189                                 dest++;
 190                         }
 191
 192                         //see if must free discarded point
 193
 194                         if (src[i]->p3_flags & PF_TEMP_POINT)
 195                                 free_temp_point(src[i]);
 196                 }
 197                 else {                  //cur not off, copy to dest buffer
 198
 199                         *dest++ = src[i];
 200
 201                         cc->or  |= src[i]->p3_codes;
 202                         cc->and &= src[i]->p3_codes;
 203                 }
 204         }
 205
 206         return (dest-save_dest);
 207 }
 208
 209
 210 g3s_point **clip_polygon(g3s_point **src,g3s_point **dest,int *nv,g3s_codes *cc)
 211 {
 212         int plane_flag;
 213         g3s_point **t;
 214
 215         for (plane_flag=1;plane_flag<16;plane_flag<<=1)
 216
 217                 if (cc->or & plane_flag) {
 218
 219                         *nv = clip_plane(plane_flag,src,dest,nv,cc);
 220
 221                         if (cc->and)            //clipped away
 222                                 return dest;
 223
 224                         t = src; src = dest; dest = t;
 225
 226                 }
 227
 228         return src;             //we swapped after we copied
 229 }
 230