3d/clipper.c

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