Fix crash if Num_walls=0
[btb/d2x.git] / 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