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 */ 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 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 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 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 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 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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