1 /* $Id: clip.c,v 1.16 1998/02/03 23:45:36 brianp Exp $ */
2
3 /*
4 * Mesa 3-D graphics library
5 * Version: 2.6
6 * Copyright (C) 1995-1997 Brian Paul
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Library General Public
10 * License as published by the Free Software Foundation; either
11 * version 2 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Library General Public License for more details.
17 *
18 * You should have received a copy of the GNU Library General Public
19 * License along with this library; if not, write to the Free
20 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 */
22
23
24 /*
25 * $Log: clip.c,v $
26 * Revision 1.16 1998/02/03 23:45:36 brianp
27 * added space parameter to clip interpolation functions
28 *
29 * Revision 1.15 1998/01/06 02:40:52 brianp
30 * added DavidB's clipping interpolation optimization
31 *
32 * Revision 1.14 1997/07/24 01:24:45 brianp
33 * changed precompiled header symbol from PCH to PC_HEADER
34 *
35 * Revision 1.13 1997/05/28 03:23:48 brianp
36 * added precompiled header (PCH) support
37 *
38 * Revision 1.12 1997/04/02 03:10:06 brianp
39 * call gl_analyze_modelview_matrix instead of gl_compute_modelview_inverse
40 *
41 * Revision 1.11 1997/02/13 21:16:09 brianp
42 * if too many vertices in polygon return VB_SIZE-1, not VB_SIZE
43 *
44 * Revision 1.10 1997/02/10 21:16:12 brianp
45 * added checks in polygon clippers to prevent array overflows
46 *
47 * Revision 1.9 1997/02/04 19:39:39 brianp
48 * changed size of vlist2[] arrays to VB_SIZE per Randy Frank
49 *
50 * Revision 1.8 1996/12/02 20:10:07 brianp
51 * changed the macros in gl_viewclip_polygon() to be like gl_viewclip_line()
52 *
53 * Revision 1.7 1996/10/29 02:55:02 brianp
54 * fixed duplicate vertex bug in gl_viewclip_polygon()
55 *
56 * Revision 1.6 1996/10/07 23:48:33 brianp
57 * changed temporaries to GLdouble in gl_viewclip_polygon()
58 *
59 * Revision 1.5 1996/10/03 01:43:45 brianp
60 * changed INSIDE() macro in gl_viewclip_polygon() to work like other macros
61 *
62 * Revision 1.4 1996/10/03 01:36:33 brianp
63 * changed COMPUTE_INTERSECTION macros in gl_viewclip_polygon to avoid
64 * potential roundoff errors
65 *
66 * Revision 1.3 1996/09/27 01:24:23 brianp
67 * removed unused variables
68 *
69 * Revision 1.2 1996/09/15 01:48:58 brianp
70 * removed #define NULL 0
71 *
72 * Revision 1.1 1996/09/13 01:38:16 brianp
73 * Initial revision
74 *
75 */
76
77
78 #ifdef PC_HEADER
79 #include "all.h"
80 #else
81 #include <string.h>
82 #include "clip.h"
83 #include "context.h"
84 #include "dlist.h"
85 #include "macros.h"
86 #include "matrix.h"
87 #include "types.h"
88 #include "vb.h"
89 #include "xform.h"
90 #endif
91
92
93
94
95 /* Linear interpolation between A and B: */
96 #define LINTERP( T, A, B ) ( (A) + (T) * ( (B) - (A) ) )
97
98
99 /* Clipping coordinate spaces */
100 #define EYE_SPACE 1
101 #define CLIP_SPACE 2
102
103
104
105 /*
106 * This function is used to interpolate colors, indexes, and texture
107 * coordinates when clipping has to be done. In general, we compute
108 * aux[dst] = aux[in] + t * (aux[out] - aux[in])
109 * where aux is the quantity to be interpolated.
110 * Input: space - either EYE_SPACE or CLIP_SPACE
111 * dst - index of array position to store interpolated value
112 * t - a value in [0,1]
113 * in - index of array position corresponding to 'inside' vertex
114 * out - index of array position corresponding to 'outside' vertex
115 */
interpolate_aux(GLcontext * ctx,GLuint space,GLuint dst,GLfloat t,GLuint in,GLuint out)116 void interpolate_aux( GLcontext* ctx, GLuint space,
117 GLuint dst, GLfloat t, GLuint in, GLuint out )
118 {
119 struct vertex_buffer* VB = ctx->VB;
120
121 if (ctx->ClipMask & CLIP_FCOLOR_BIT) {
122 VB->Fcolor[dst][0] = LINTERP( t, VB->Fcolor[in][0], VB->Fcolor[out][0] );
123 VB->Fcolor[dst][1] = LINTERP( t, VB->Fcolor[in][1], VB->Fcolor[out][1] );
124 VB->Fcolor[dst][2] = LINTERP( t, VB->Fcolor[in][2], VB->Fcolor[out][2] );
125 VB->Fcolor[dst][3] = LINTERP( t, VB->Fcolor[in][3], VB->Fcolor[out][3] );
126 }
127 else if (ctx->ClipMask & CLIP_FINDEX_BIT) {
128 VB->Findex[dst] = (GLuint) (GLint) LINTERP( t, (GLfloat) VB->Findex[in],
129 (GLfloat) VB->Findex[out] );
130 }
131
132 if (ctx->ClipMask & CLIP_BCOLOR_BIT) {
133 VB->Bcolor[dst][0] = LINTERP( t, VB->Bcolor[in][0], VB->Bcolor[out][0] );
134 VB->Bcolor[dst][1] = LINTERP( t, VB->Bcolor[in][1], VB->Bcolor[out][1] );
135 VB->Bcolor[dst][2] = LINTERP( t, VB->Bcolor[in][2], VB->Bcolor[out][2] );
136 VB->Bcolor[dst][3] = LINTERP( t, VB->Bcolor[in][3], VB->Bcolor[out][3] );
137 }
138 else if (ctx->ClipMask & CLIP_BINDEX_BIT) {
139 VB->Bindex[dst] = (GLuint) (GLint) LINTERP( t, (GLfloat) VB->Bindex[in],
140 (GLfloat) VB->Bindex[out] );
141 }
142
143 if (ctx->ClipMask & CLIP_TEXTURE_BIT) {
144 /* TODO: is more sophisticated texture coord interpolation needed?? */
145 if (space==CLIP_SPACE) {
146 /* also interpolate eye Z component */
147 VB->Eye[dst][2] = LINTERP( t, VB->Eye[in][2], VB->Eye[out][2] );
148 }
149 VB->TexCoord[dst][0] = LINTERP(t,VB->TexCoord[in][0],VB->TexCoord[out][0]);
150 VB->TexCoord[dst][1] = LINTERP(t,VB->TexCoord[in][1],VB->TexCoord[out][1]);
151 VB->TexCoord[dst][2] = LINTERP(t,VB->TexCoord[in][2],VB->TexCoord[out][2]);
152 VB->TexCoord[dst][3] = LINTERP(t,VB->TexCoord[in][3],VB->TexCoord[out][3]);
153 }
154
155 }
156
157
158 /*
159 * Some specialized version of the interpolate_aux
160 *
161 */
162
interpolate_aux_color_tex2(GLcontext * ctx,GLuint space,GLuint dst,GLfloat t,GLuint in,GLuint out)163 void interpolate_aux_color_tex2( GLcontext* ctx, GLuint space,
164 GLuint dst, GLfloat t, GLuint in, GLuint out )
165 {
166 struct vertex_buffer* VB = ctx->VB;
167
168 VB->Fcolor[dst][0] = LINTERP( t, VB->Fcolor[in][0], VB->Fcolor[out][0] );
169 VB->Fcolor[dst][1] = LINTERP( t, VB->Fcolor[in][1], VB->Fcolor[out][1] );
170 VB->Fcolor[dst][2] = LINTERP( t, VB->Fcolor[in][2], VB->Fcolor[out][2] );
171 VB->Fcolor[dst][3] = LINTERP( t, VB->Fcolor[in][3], VB->Fcolor[out][3] );
172
173 VB->Eye[dst][2] = LINTERP( t, VB->Eye[in][2], VB->Eye[out][2] );
174 VB->TexCoord[dst][0] = LINTERP(t,VB->TexCoord[in][0],VB->TexCoord[out][0]);
175 VB->TexCoord[dst][1] = LINTERP(t,VB->TexCoord[in][1],VB->TexCoord[out][1]);
176 }
177
178
interpolate_aux_tex2(GLcontext * ctx,GLuint space,GLuint dst,GLfloat t,GLuint in,GLuint out)179 void interpolate_aux_tex2( GLcontext* ctx, GLuint space,
180 GLuint dst, GLfloat t, GLuint in, GLuint out )
181 {
182 struct vertex_buffer* VB = ctx->VB;
183
184 VB->Eye[dst][2] = LINTERP( t, VB->Eye[in][2], VB->Eye[out][2] );
185 VB->TexCoord[dst][0] = LINTERP(t,VB->TexCoord[in][0],VB->TexCoord[out][0]);
186 VB->TexCoord[dst][1] = LINTERP(t,VB->TexCoord[in][1],VB->TexCoord[out][1]);
187 }
188
189
interpolate_aux_color(GLcontext * ctx,GLuint space,GLuint dst,GLfloat t,GLuint in,GLuint out)190 void interpolate_aux_color( GLcontext* ctx, GLuint space,
191 GLuint dst, GLfloat t, GLuint in, GLuint out )
192 {
193 struct vertex_buffer* VB = ctx->VB;
194
195 VB->Fcolor[dst][0] = LINTERP( t, VB->Fcolor[in][0], VB->Fcolor[out][0] );
196 VB->Fcolor[dst][1] = LINTERP( t, VB->Fcolor[in][1], VB->Fcolor[out][1] );
197 VB->Fcolor[dst][2] = LINTERP( t, VB->Fcolor[in][2], VB->Fcolor[out][2] );
198 VB->Fcolor[dst][3] = LINTERP( t, VB->Fcolor[in][3], VB->Fcolor[out][3] );
199 }
200
201
202
203
gl_ClipPlane(GLcontext * ctx,GLenum plane,const GLfloat * equation)204 void gl_ClipPlane( GLcontext* ctx, GLenum plane, const GLfloat *equation )
205 {
206 GLint p;
207
208 p = (GLint) plane - (GLint) GL_CLIP_PLANE0;
209 if (p<0 || p>=MAX_CLIP_PLANES) {
210 gl_error( ctx, GL_INVALID_ENUM, "glClipPlane" );
211 return;
212 }
213
214 /*
215 * The equation is transformed by the transpose of the inverse of the
216 * current modelview matrix and stored in the resulting eye coordinates.
217 */
218 if (ctx->NewModelViewMatrix) {
219 gl_analyze_modelview_matrix(ctx);
220 }
221 gl_transform_vector( ctx->Transform.ClipEquation[p], equation,
222 ctx->ModelViewInv );
223 }
224
225
226
gl_GetClipPlane(GLcontext * ctx,GLenum plane,GLdouble * equation)227 void gl_GetClipPlane( GLcontext* ctx, GLenum plane, GLdouble *equation )
228 {
229 GLint p;
230
231 if (INSIDE_BEGIN_END(ctx)) {
232 gl_error( ctx, GL_INVALID_OPERATION, "glGetClipPlane" );
233 return;
234 }
235
236 p = (GLint) (plane - GL_CLIP_PLANE0);
237 if (p<0 || p>=MAX_CLIP_PLANES) {
238 gl_error( ctx, GL_INVALID_ENUM, "glGetClipPlane" );
239 return;
240 }
241
242 equation[0] = (GLdouble) ctx->Transform.ClipEquation[p][0];
243 equation[1] = (GLdouble) ctx->Transform.ClipEquation[p][1];
244 equation[2] = (GLdouble) ctx->Transform.ClipEquation[p][2];
245 equation[3] = (GLdouble) ctx->Transform.ClipEquation[p][3];
246 }
247
248
249
250
251 /**********************************************************************/
252 /* View volume clipping. */
253 /**********************************************************************/
254
255
256 /*
257 * Clip a point against the view volume.
258 * Input: v - vertex-vector describing the point to clip
259 * Return: 0 = outside view volume
260 * 1 = inside view volume
261 */
gl_viewclip_point(const GLfloat v[])262 GLuint gl_viewclip_point( const GLfloat v[] )
263 {
264 if ( v[0] > v[3] || v[0] < -v[3]
265 || v[1] > v[3] || v[1] < -v[3]
266 || v[2] > v[3] || v[2] < -v[3] ) {
267 return 0;
268 }
269 else {
270 return 1;
271 }
272 }
273
274
275
276
277 /*
278 * Clip a line segment against the view volume defined by -w<=x,y,z<=w.
279 * Input: i, j - indexes into VB->V* of endpoints of the line
280 * Return: 0 = line completely outside of view
281 * 1 = line is inside view.
282 */
gl_viewclip_line(GLcontext * ctx,GLuint * i,GLuint * j)283 GLuint gl_viewclip_line( GLcontext* ctx, GLuint *i, GLuint *j )
284 {
285 struct vertex_buffer* VB = ctx->VB;
286 GLfloat (*coord)[4] = VB->Clip;
287
288 GLfloat t, dx, dy, dz, dw;
289 register GLuint ii, jj;
290
291 ii = *i;
292 jj = *j;
293
294 /*
295 * We use 6 instances of this code to clip agains the 6 planes.
296 * For each plane, we define the OUTSIDE and COMPUTE_INTERSECTION
297 * macros apprpriately.
298 */
299 #define GENERAL_CLIP \
300 if (OUTSIDE(ii)) { \
301 if (OUTSIDE(jj)) { \
302 /* both verts are outside ==> return 0 */ \
303 return 0; \
304 } \
305 else { \
306 /* ii is outside, jj is inside ==> clip */ \
307 /* new vertex put in position VB->Free */ \
308 COMPUTE_INTERSECTION( VB->Free, jj, ii ) \
309 if (ctx->ClipMask) \
310 ctx->ClipInterpAuxFunc( ctx, CLIP_SPACE, VB->Free, t, jj, ii );\
311 ii = VB->Free; \
312 VB->Free++; \
313 if (VB->Free==VB_SIZE) VB->Free = 1; \
314 } \
315 } \
316 else { \
317 if (OUTSIDE(jj)) { \
318 /* ii is inside, jj is outside ==> clip */ \
319 /* new vertex put in position VB->Free */ \
320 COMPUTE_INTERSECTION( VB->Free, ii, jj ); \
321 if (ctx->ClipMask) \
322 ctx->ClipInterpAuxFunc( ctx, CLIP_SPACE, VB->Free, t, ii, jj );\
323 jj = VB->Free; \
324 VB->Free++; \
325 if (VB->Free==VB_SIZE) VB->Free = 1; \
326 } \
327 /* else both verts are inside ==> do nothing */ \
328 }
329
330
331 #define X(I) coord[I][0]
332 #define Y(I) coord[I][1]
333 #define Z(I) coord[I][2]
334 #define W(I) coord[I][3]
335
336 /*
337 * Begin clipping
338 */
339
340 /*** Clip against +X side ***/
341 #define OUTSIDE(K) (X(K) > W(K))
342 #define COMPUTE_INTERSECTION( new, in, out ) \
343 dx = X(out) - X(in); \
344 dw = W(out) - W(in); \
345 t = (X(in) - W(in)) / (dw-dx); \
346 X(new) = X(in) + t * dx; \
347 Y(new) = Y(in) + t * (Y(out) - Y(in)); \
348 Z(new) = Z(in) + t * (Z(out) - Z(in)); \
349 W(new) = W(in) + t * dw;
350
351 GENERAL_CLIP
352
353 #undef OUTSIDE
354 #undef COMPUTE_INTERSECTION
355
356
357 /*** Clip against -X side ***/
358 #define OUTSIDE(K) (X(K) < -W(K))
359 #define COMPUTE_INTERSECTION( new, in, out ) \
360 dx = X(out) - X(in); \
361 dw = W(out) - W(in); \
362 t = -(X(in) + W(in)) / (dw+dx); \
363 X(new) = X(in) + t * dx; \
364 Y(new) = Y(in) + t * (Y(out) - Y(in)); \
365 Z(new) = Z(in) + t * (Z(out) - Z(in)); \
366 W(new) = W(in) + t * dw;
367
368 GENERAL_CLIP
369
370 #undef OUTSIDE
371 #undef COMPUTE_INTERSECTION
372
373
374 /*** Clip against +Y side ***/
375 #define OUTSIDE(K) (Y(K) > W(K))
376 #define COMPUTE_INTERSECTION( new, in, out ) \
377 dy = Y(out) - Y(in); \
378 dw = W(out) - W(in); \
379 t = (Y(in) - W(in)) / (dw-dy); \
380 X(new) = X(in) + t * (X(out) - X(in)); \
381 Y(new) = Y(in) + t * dy; \
382 Z(new) = Z(in) + t * (Z(out) - Z(in)); \
383 W(new) = W(in) + t * dw;
384
385 GENERAL_CLIP
386
387 #undef OUTSIDE
388 #undef COMPUTE_INTERSECTION
389
390
391 /*** Clip against -Y side ***/
392 #define OUTSIDE(K) (Y(K) < -W(K))
393 #define COMPUTE_INTERSECTION( new, in, out ) \
394 dy = Y(out) - Y(in); \
395 dw = W(out) - W(in); \
396 t = -(Y(in) + W(in)) / (dw+dy); \
397 X(new) = X(in) + t * (X(out) - X(in)); \
398 Y(new) = Y(in) + t * dy; \
399 Z(new) = Z(in) + t * (Z(out) - Z(in)); \
400 W(new) = W(in) + t * dw;
401
402 GENERAL_CLIP
403
404 #undef OUTSIDE
405 #undef COMPUTE_INTERSECTION
406
407
408 /*** Clip against +Z side ***/
409 #define OUTSIDE(K) (Z(K) > W(K))
410 #define COMPUTE_INTERSECTION( new, in, out ) \
411 dz = Z(out) - Z(in); \
412 dw = W(out) - W(in); \
413 t = (Z(in) - W(in)) / (dw-dz); \
414 X(new) = X(in) + t * (X(out) - X(in)); \
415 Y(new) = Y(in) + t * (Y(out) - Y(in)); \
416 Z(new) = Z(in) + t * dz; \
417 W(new) = W(in) + t * dw;
418
419 GENERAL_CLIP
420
421 #undef OUTSIDE
422 #undef COMPUTE_INTERSECTION
423
424
425 /*** Clip against -Z side ***/
426 #define OUTSIDE(K) (Z(K) < -W(K))
427 #define COMPUTE_INTERSECTION( new, in, out ) \
428 dz = Z(out) - Z(in); \
429 dw = W(out) - W(in); \
430 t = -(Z(in) + W(in)) / (dw+dz); \
431 X(new) = X(in) + t * (X(out) - X(in)); \
432 Y(new) = Y(in) + t * (Y(out) - Y(in)); \
433 Z(new) = Z(in) + t * dz; \
434 W(new) = W(in) + t * dw;
435
436 GENERAL_CLIP
437
438 #undef OUTSIDE
439 #undef COMPUTE_INTERSECTION
440
441 #undef GENERAL_CLIP
442
443 *i = ii;
444 *j = jj;
445 return 1;
446 }
447
448
449
450
451 /*
452 * Clip a polygon against the view volume defined by -w<=x,y,z<=w.
453 * Input: n - number of vertices in input polygon.
454 * vlist - list of indexes into VB->V* of polygon to clip.
455 * Output: vlist - modified list of vertex indexes
456 * Return: number of vertices in resulting polygon
457 */
gl_viewclip_polygon(GLcontext * ctx,GLuint n,GLuint vlist[])458 GLuint gl_viewclip_polygon( GLcontext* ctx, GLuint n, GLuint vlist[] )
459
460 {
461 struct vertex_buffer* VB = ctx->VB;
462 GLfloat (*coord)[4] = VB->Clip;
463
464 GLuint previ, prevj;
465 GLuint curri, currj;
466 GLuint vlist2[VB_SIZE];
467 GLuint n2;
468 GLdouble dx, dy, dz, dw, t, neww;
469
470 /*
471 * We use 6 instances of this code to implement clipping against the
472 * 6 sides of the view volume. Prior to each we define the macros:
473 * INLIST = array which lists input vertices
474 * OUTLIST = array which lists output vertices
475 * INCOUNT = variable which is the number of vertices in INLIST[]
476 * OUTCOUNT = variable which is the number of vertices in OUTLIST[]
477 * INSIDE(i) = test if vertex v[i] is inside the view volume
478 * COMPUTE_INTERSECTION(in,out,new) = compute intersection of line
479 * from v[in] to v[out] with the clipping plane and store
480 * the result in v[new]
481 */
482
483 #define GENERAL_CLIP \
484 if (INCOUNT<3) return 0; \
485 previ = INCOUNT-1; /* let previous = last vertex */ \
486 prevj = INLIST[previ]; \
487 OUTCOUNT = 0; \
488 for (curri=0;curri<INCOUNT;curri++) { \
489 currj = INLIST[curri]; \
490 if (INSIDE(currj)) { \
491 if (INSIDE(prevj)) { \
492 /* both verts are inside ==> copy current to outlist */ \
493 OUTLIST[OUTCOUNT] = currj; \
494 OUTCOUNT++; \
495 } \
496 else { \
497 /* current is inside and previous is outside ==> clip */ \
498 COMPUTE_INTERSECTION( currj, prevj, VB->Free ) \
499 /* if new point not coincident with previous point... */ \
500 if (t>0.0) { \
501 /* interpolate aux info using the value of t */ \
502 if (ctx->ClipMask) \
503 ctx->ClipInterpAuxFunc( ctx, CLIP_SPACE, VB->Free, t, currj, prevj ); \
504 VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj]; \
505 /* output new point */ \
506 OUTLIST[OUTCOUNT] = VB->Free; \
507 VB->Free++; \
508 if (VB->Free==VB_SIZE) VB->Free = 1; \
509 OUTCOUNT++; \
510 } \
511 /* Output current */ \
512 OUTLIST[OUTCOUNT] = currj; \
513 OUTCOUNT++; \
514 } \
515 } \
516 else { \
517 if (INSIDE(prevj)) { \
518 /* current is outside and previous is inside ==> clip */ \
519 COMPUTE_INTERSECTION( prevj, currj, VB->Free ) \
520 /* if new point not coincident with previous point... */ \
521 if (t>0.0) { \
522 /* interpolate aux info using the value of t */ \
523 if (ctx->ClipMask) \
524 ctx->ClipInterpAuxFunc( ctx, CLIP_SPACE, VB->Free, t, prevj, currj ); \
525 VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj]; \
526 /* output new point */ \
527 OUTLIST[OUTCOUNT] = VB->Free; \
528 VB->Free++; \
529 if (VB->Free==VB_SIZE) VB->Free = 1; \
530 OUTCOUNT++; \
531 } \
532 } \
533 /* else both verts are outside ==> do nothing */ \
534 } \
535 /* let previous = current */ \
536 previ = curri; \
537 prevj = currj; \
538 /* check for overflowing vertex buffer */ \
539 if (OUTCOUNT>=VB_SIZE-1) { \
540 /* Too many vertices */ \
541 if (OUTLIST==vlist2) { \
542 /* copy OUTLIST[] to vlist[] */ \
543 int i; \
544 for (i=0;i<VB_SIZE;i++) { \
545 vlist[i] = OUTLIST[i]; \
546 } \
547 } \
548 return VB_SIZE-1; \
549 } \
550 }
551
552
553 #define X(I) coord[I][0]
554 #define Y(I) coord[I][1]
555 #define Z(I) coord[I][2]
556 #define W(I) coord[I][3]
557
558 /*
559 * Clip against +X
560 */
561 #define INCOUNT n
562 #define OUTCOUNT n2
563 #define INLIST vlist
564 #define OUTLIST vlist2
565 #define INSIDE(K) (X(K) <= W(K))
566
567 #define COMPUTE_INTERSECTION( in, out, new ) \
568 dx = X(out) - X(in); \
569 dw = W(out) - W(in); \
570 t = (X(in)-W(in)) / (dw-dx); \
571 neww = W(in) + t * dw; \
572 X(new) = neww; \
573 Y(new) = Y(in) + t * (Y(out) - Y(in)); \
574 Z(new) = Z(in) + t * (Z(out) - Z(in)); \
575 W(new) = neww;
576
577 GENERAL_CLIP
578
579 #undef INCOUNT
580 #undef OUTCOUNT
581 #undef INLIST
582 #undef OUTLIST
583 #undef INSIDE
584 #undef COMPUTE_INTERSECTION
585
586
587 /*
588 * Clip against -X
589 */
590 #define INCOUNT n2
591 #define OUTCOUNT n
592 #define INLIST vlist2
593 #define OUTLIST vlist
594 #define INSIDE(K) (X(K) >= -W(K))
595 #define COMPUTE_INTERSECTION( in, out, new ) \
596 dx = X(out)-X(in); \
597 dw = W(out)-W(in); \
598 t = -(X(in)+W(in)) / (dw+dx); \
599 neww = W(in) + t * dw; \
600 X(new) = -neww; \
601 Y(new) = Y(in) + t * (Y(out) - Y(in)); \
602 Z(new) = Z(in) + t * (Z(out) - Z(in)); \
603 W(new) = neww;
604
605 GENERAL_CLIP
606
607 #undef INCOUNT
608 #undef OUTCOUNT
609 #undef INLIST
610 #undef OUTLIST
611 #undef INSIDE
612 #undef COMPUTE_INTERSECTION
613
614
615 /*
616 * Clip against +Y
617 */
618 #define INCOUNT n
619 #define OUTCOUNT n2
620 #define INLIST vlist
621 #define OUTLIST vlist2
622 #define INSIDE(K) (Y(K) <= W(K))
623 #define COMPUTE_INTERSECTION( in, out, new ) \
624 dy = Y(out)-Y(in); \
625 dw = W(out)-W(in); \
626 t = (Y(in)-W(in)) / (dw-dy); \
627 neww = W(in) + t * dw; \
628 X(new) = X(in) + t * (X(out) - X(in)); \
629 Y(new) = neww; \
630 Z(new) = Z(in) + t * (Z(out) - Z(in)); \
631 W(new) = neww;
632
633 GENERAL_CLIP
634
635 #undef INCOUNT
636 #undef OUTCOUNT
637 #undef INLIST
638 #undef OUTLIST
639 #undef INSIDE
640 #undef COMPUTE_INTERSECTION
641
642
643 /*
644 * Clip against -Y
645 */
646 #define INCOUNT n2
647 #define OUTCOUNT n
648 #define INLIST vlist2
649 #define OUTLIST vlist
650 #define INSIDE(K) (Y(K) >= -W(K))
651 #define COMPUTE_INTERSECTION( in, out, new ) \
652 dy = Y(out)-Y(in); \
653 dw = W(out)-W(in); \
654 t = -(Y(in)+W(in)) / (dw+dy); \
655 neww = W(in) + t * dw; \
656 X(new) = X(in) + t * (X(out) - X(in)); \
657 Y(new) = -neww; \
658 Z(new) = Z(in) + t * (Z(out) - Z(in)); \
659 W(new) = neww;
660
661 GENERAL_CLIP
662
663 #undef INCOUNT
664 #undef OUTCOUNT
665 #undef INLIST
666 #undef OUTLIST
667 #undef INSIDE
668 #undef COMPUTE_INTERSECTION
669
670
671
672 /*
673 * Clip against +Z
674 */
675 #define INCOUNT n
676 #define OUTCOUNT n2
677 #define INLIST vlist
678 #define OUTLIST vlist2
679 #define INSIDE(K) (Z(K) <= W(K))
680 #define COMPUTE_INTERSECTION( in, out, new ) \
681 dz = Z(out)-Z(in); \
682 dw = W(out)-W(in); \
683 t = (Z(in)-W(in)) / (dw-dz); \
684 neww = W(in) + t * dw; \
685 X(new) = X(in) + t * (X(out) - X(in)); \
686 Y(new) = Y(in) + t * (Y(out) - Y(in)); \
687 Z(new) = neww; \
688 W(new) = neww;
689
690 GENERAL_CLIP
691
692 #undef INCOUNT
693 #undef OUTCOUNT
694 #undef INLIST
695 #undef OUTLIST
696 #undef INSIDE
697 #undef COMPUTE_INTERSECTION
698
699
700 /*
701 * Clip against -Z
702 */
703 #define INCOUNT n2
704 #define OUTCOUNT n
705 #define INLIST vlist2
706 #define OUTLIST vlist
707 #define INSIDE(K) (Z(K) >= -W(K))
708 #define COMPUTE_INTERSECTION( in, out, new ) \
709 dz = Z(out)-Z(in); \
710 dw = W(out)-W(in); \
711 t = -(Z(in)+W(in)) / (dw+dz); \
712 neww = W(in) + t * dw; \
713 X(new) = X(in) + t * (X(out) - X(in)); \
714 Y(new) = Y(in) + t * (Y(out) - Y(in)); \
715 Z(new) = -neww; \
716 W(new) = neww;
717
718 GENERAL_CLIP
719
720 #undef INCOUNT
721 #undef INLIST
722 #undef OUTLIST
723 #undef INSIDE
724 #undef COMPUTE_INTERSECTION
725
726 /* 'OUTCOUNT' clipped vertices are now back in v[] */
727 return OUTCOUNT;
728
729 #undef GENERAL_CLIP
730 #undef OUTCOUNT
731 }
732
733
734
735
736 /**********************************************************************/
737 /* Clipping against user-defined clipping planes. */
738 /**********************************************************************/
739
740
741
742 /*
743 * If the dot product of the eye coordinates of a vertex with the
744 * stored plane equation components is positive or zero, the vertex
745 * is in with respect to that clipping plane, otherwise it is out.
746 */
747
748
749
750 /*
751 * Clip a point against the user clipping planes.
752 * Input: v - vertex-vector describing the point to clip.
753 * Return: 0 = point was clipped
754 * 1 = point not clipped
755 */
gl_userclip_point(GLcontext * ctx,const GLfloat v[])756 GLuint gl_userclip_point( GLcontext* ctx, const GLfloat v[] )
757 {
758 GLuint p;
759
760 for (p=0;p<MAX_CLIP_PLANES;p++) {
761 if (ctx->Transform.ClipEnabled[p]) {
762 GLfloat dot = v[0] * ctx->Transform.ClipEquation[p][0]
763 + v[1] * ctx->Transform.ClipEquation[p][1]
764 + v[2] * ctx->Transform.ClipEquation[p][2]
765 + v[3] * ctx->Transform.ClipEquation[p][3];
766 if (dot < 0.0F) {
767 return 0;
768 }
769 }
770 }
771
772 return 1;
773 }
774
775
776 #define MAGIC_NUMBER -0.8e-03F
777
778
779 /* Test if VB->Eye[J] is inside the clipping plane defined by A,B,C,D */
780 #define INSIDE( J, A, B, C, D ) \
781 ( (VB->Eye[J][0] * A + VB->Eye[J][1] * B \
782 + VB->Eye[J][2] * C + VB->Eye[J][3] * D) >= MAGIC_NUMBER )
783
784
785 /* Test if VB->Eye[J] is outside the clipping plane defined by A,B,C,D */
786 #define OUTSIDE( J, A, B, C, D ) \
787 ( (VB->Eye[J][0] * A + VB->Eye[J][1] * B \
788 + VB->Eye[J][2] * C + VB->Eye[J][3] * D) < MAGIC_NUMBER )
789
790
791 /*
792 * Clip a line against the user clipping planes.
793 * Input: i, j - indexes into VB->V*[] of endpoints
794 * Output: i, j - indexes into VB->V*[] of (possibly clipped) endpoints
795 * Return: 0 = line completely clipped
796 * 1 = line is visible
797 */
gl_userclip_line(GLcontext * ctx,GLuint * i,GLuint * j)798 GLuint gl_userclip_line( GLcontext* ctx, GLuint *i, GLuint *j )
799 {
800 struct vertex_buffer* VB = ctx->VB;
801
802 GLuint p, ii, jj;
803
804 ii = *i;
805 jj = *j;
806
807 for (p=0;p<MAX_CLIP_PLANES;p++) {
808 if (ctx->Transform.ClipEnabled[p]) {
809 register GLfloat a, b, c, d;
810 a = ctx->Transform.ClipEquation[p][0];
811 b = ctx->Transform.ClipEquation[p][1];
812 c = ctx->Transform.ClipEquation[p][2];
813 d = ctx->Transform.ClipEquation[p][3];
814
815 if (OUTSIDE( ii, a,b,c,d )) {
816 if (OUTSIDE( jj, a,b,c,d )) {
817 /* ii and jj outside ==> quit */
818 return 0;
819 }
820 else {
821 /* ii is outside, jj is inside ==> clip */
822 GLfloat dx, dy, dz, dw, t, denom;
823 dx = VB->Eye[ii][0] - VB->Eye[jj][0];
824 dy = VB->Eye[ii][1] - VB->Eye[jj][1];
825 dz = VB->Eye[ii][2] - VB->Eye[jj][2];
826 dw = VB->Eye[ii][3] - VB->Eye[jj][3];
827 denom = dx*a + dy*b + dz*c + dw*d;
828 if (denom==0.0) {
829 t = 0.0;
830 }
831 else {
832 t = -(VB->Eye[jj][0]*a+VB->Eye[jj][1]*b
833 +VB->Eye[jj][2]*c+VB->Eye[jj][3]*d) / denom;
834 if (t>1.0F) t = 1.0F;
835 }
836 VB->Eye[VB->Free][0] = VB->Eye[jj][0] + t * dx;
837 VB->Eye[VB->Free][1] = VB->Eye[jj][1] + t * dy;
838 VB->Eye[VB->Free][2] = VB->Eye[jj][2] + t * dz;
839 VB->Eye[VB->Free][3] = VB->Eye[jj][3] + t * dw;
840
841 /* Interpolate colors, indexes, and/or texture coords */
842 if (ctx->ClipMask)
843 interpolate_aux( ctx, EYE_SPACE, VB->Free, t, jj, ii );
844
845 ii = VB->Free;
846 VB->Free++;
847 if (VB->Free==VB_SIZE) VB->Free = 1;
848 }
849 }
850 else {
851 if (OUTSIDE( jj, a,b,c,d )) {
852 /* ii is inside, jj is outside ==> clip */
853 GLfloat dx, dy, dz, dw, t, denom;
854 dx = VB->Eye[jj][0] - VB->Eye[ii][0];
855 dy = VB->Eye[jj][1] - VB->Eye[ii][1];
856 dz = VB->Eye[jj][2] - VB->Eye[ii][2];
857 dw = VB->Eye[jj][3] - VB->Eye[ii][3];
858 denom = dx*a + dy*b + dz*c + dw*d;
859 if (denom==0.0) {
860 t = 0.0;
861 }
862 else {
863 t = -(VB->Eye[ii][0]*a+VB->Eye[ii][1]*b
864 +VB->Eye[ii][2]*c+VB->Eye[ii][3]*d) / denom;
865 if (t>1.0F) t = 1.0F;
866 }
867 VB->Eye[VB->Free][0] = VB->Eye[ii][0] + t * dx;
868 VB->Eye[VB->Free][1] = VB->Eye[ii][1] + t * dy;
869 VB->Eye[VB->Free][2] = VB->Eye[ii][2] + t * dz;
870 VB->Eye[VB->Free][3] = VB->Eye[ii][3] + t * dw;
871
872 /* Interpolate colors, indexes, and/or texture coords */
873 if (ctx->ClipMask)
874 interpolate_aux( ctx, EYE_SPACE, VB->Free, t, ii, jj );
875
876 jj = VB->Free;
877 VB->Free++;
878 if (VB->Free==VB_SIZE) VB->Free = 1;
879 }
880 else {
881 /* ii and jj inside ==> do nothing */
882 }
883 }
884 }
885 }
886
887 *i = ii;
888 *j = jj;
889 return 1;
890 }
891
892
893
894
895 /*
896 * Clip a polygon against the user clipping planes defined in eye coordinates.
897 * Input: n - number of vertices.
898 * vlist - list of vertices in input polygon.
899 * Output: vlist - list of vertices in output polygon.
900 * Return: number of vertices after clipping.
901 */
gl_userclip_polygon(GLcontext * ctx,GLuint n,GLuint vlist[])902 GLuint gl_userclip_polygon( GLcontext* ctx, GLuint n, GLuint vlist[] )
903 {
904 struct vertex_buffer* VB = ctx->VB;
905
906 GLuint vlist2[VB_SIZE];
907 GLuint *inlist, *outlist;
908 GLuint incount, outcount;
909 GLuint curri, currj;
910 GLuint previ, prevj;
911 GLuint p;
912
913 /* initialize input vertex list */
914 incount = n;
915 inlist = vlist;
916 outlist = vlist2;
917
918 for (p=0;p<MAX_CLIP_PLANES;p++) {
919 if (ctx->Transform.ClipEnabled[p]) {
920 register float a = ctx->Transform.ClipEquation[p][0];
921 register float b = ctx->Transform.ClipEquation[p][1];
922 register float c = ctx->Transform.ClipEquation[p][2];
923 register float d = ctx->Transform.ClipEquation[p][3];
924
925 if (incount<3) return 0;
926
927 /* initialize prev to be last in the input list */
928 previ = incount - 1;
929 prevj = inlist[previ];
930
931 outcount = 0;
932
933 for (curri=0;curri<incount;curri++) {
934 currj = inlist[curri];
935
936 if (INSIDE(currj, a,b,c,d)) {
937 if (INSIDE(prevj, a,b,c,d)) {
938 /* both verts are inside ==> copy current to outlist */
939 outlist[outcount++] = currj;
940 }
941 else {
942 /* current is inside and previous is outside ==> clip */
943 GLfloat dx, dy, dz, dw, t, denom;
944 /* compute t */
945 dx = VB->Eye[prevj][0] - VB->Eye[currj][0];
946 dy = VB->Eye[prevj][1] - VB->Eye[currj][1];
947 dz = VB->Eye[prevj][2] - VB->Eye[currj][2];
948 dw = VB->Eye[prevj][3] - VB->Eye[currj][3];
949 denom = dx*a + dy*b + dz*c + dw*d;
950 if (denom==0.0) {
951 t = 0.0;
952 }
953 else {
954 t = -(VB->Eye[currj][0]*a+VB->Eye[currj][1]*b
955 +VB->Eye[currj][2]*c+VB->Eye[currj][3]*d) / denom;
956 if (t>1.0F) {
957 t = 1.0F;
958 }
959 }
960 /* interpolate new vertex position */
961 VB->Eye[VB->Free][0] = VB->Eye[currj][0] + t*dx;
962 VB->Eye[VB->Free][1] = VB->Eye[currj][1] + t*dy;
963 VB->Eye[VB->Free][2] = VB->Eye[currj][2] + t*dz;
964 VB->Eye[VB->Free][3] = VB->Eye[currj][3] + t*dw;
965
966 /* interpolate color, index, and/or texture coord */
967 if (ctx->ClipMask) {
968 interpolate_aux( ctx, EYE_SPACE, VB->Free, t, currj, prevj);
969 }
970 VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];
971
972 /* output new vertex */
973 outlist[outcount++] = VB->Free;
974 VB->Free++;
975 if (VB->Free==VB_SIZE) VB->Free = 1;
976 /* output current vertex */
977 outlist[outcount++] = currj;
978 }
979 }
980 else {
981 if (INSIDE(prevj, a,b,c,d)) {
982 /* current is outside and previous is inside ==> clip */
983 GLfloat dx, dy, dz, dw, t, denom;
984 /* compute t */
985 dx = VB->Eye[currj][0]-VB->Eye[prevj][0];
986 dy = VB->Eye[currj][1]-VB->Eye[prevj][1];
987 dz = VB->Eye[currj][2]-VB->Eye[prevj][2];
988 dw = VB->Eye[currj][3]-VB->Eye[prevj][3];
989 denom = dx*a + dy*b + dz*c + dw*d;
990 if (denom==0.0) {
991 t = 0.0;
992 }
993 else {
994 t = -(VB->Eye[prevj][0]*a+VB->Eye[prevj][1]*b
995 +VB->Eye[prevj][2]*c+VB->Eye[prevj][3]*d) / denom;
996 if (t>1.0F) {
997 t = 1.0F;
998 }
999 }
1000 /* interpolate new vertex position */
1001 VB->Eye[VB->Free][0] = VB->Eye[prevj][0] + t*dx;
1002 VB->Eye[VB->Free][1] = VB->Eye[prevj][1] + t*dy;
1003 VB->Eye[VB->Free][2] = VB->Eye[prevj][2] + t*dz;
1004 VB->Eye[VB->Free][3] = VB->Eye[prevj][3] + t*dw;
1005
1006 /* interpolate color, index, and/or texture coord */
1007 if (ctx->ClipMask) {
1008 interpolate_aux( ctx, EYE_SPACE, VB->Free, t, prevj, currj);
1009 }
1010 VB->Edgeflag[VB->Free] = VB->Edgeflag[prevj];
1011
1012 /* output new vertex */
1013 outlist[outcount++] = VB->Free;
1014 VB->Free++;
1015 if (VB->Free==VB_SIZE) VB->Free = 1;
1016 }
1017 /* else both verts are outside ==> do nothing */
1018 }
1019
1020 previ = curri;
1021 prevj = currj;
1022
1023 /* check for overflowing vertex buffer */
1024 if (outcount>=VB_SIZE-1) {
1025 /* Too many vertices */
1026 if (outlist!=vlist2) {
1027 MEMCPY( vlist, vlist2, outcount * sizeof(GLuint) );
1028 }
1029 return VB_SIZE-1;
1030 }
1031
1032 } /* for i */
1033
1034 /* swap inlist and outlist pointers */
1035 {
1036 GLuint *tmp;
1037 tmp = inlist;
1038 inlist = outlist;
1039 outlist = tmp;
1040 incount = outcount;
1041 }
1042
1043 } /* if */
1044 } /* for p */
1045
1046 /* outlist points to the list of vertices resulting from the last */
1047 /* clipping. If outlist == vlist2 then we have to copy the vertices */
1048 /* back to vlist */
1049 if (outlist!=vlist2) {
1050 MEMCPY( vlist, vlist2, outcount * sizeof(GLuint) );
1051 }
1052
1053 return outcount;
1054 }
1055
1056