draw_pipe_clip.c revision 743432039ccd4c4af03aa4ef274a7922f871bc38
1/************************************************************************** 2 * 3 * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas. 4 * All Rights Reserved. 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a 7 * copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sub license, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice (including the 15 * next paragraph) shall be included in all copies or substantial portions 16 * of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 21 * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR 22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 * 26 **************************************************************************/ 27 28/** 29 * \brief Clipping stage 30 * 31 * \author Keith Whitwell <keith@tungstengraphics.com> 32 */ 33 34 35#include "util/u_memory.h" 36#include "util/u_math.h" 37 38#include "pipe/p_shader_tokens.h" 39 40#include "draw_vs.h" 41#include "draw_pipe.h" 42 43 44#ifndef IS_NEGATIVE 45#define IS_NEGATIVE(X) ((X) < 0.0) 46#endif 47 48#ifndef DIFFERENT_SIGNS 49#define DIFFERENT_SIGNS(x, y) ((x) * (y) <= 0.0F && (x) - (y) != 0.0F) 50#endif 51 52#define MAX_CLIPPED_VERTICES ((2 * (6 + PIPE_MAX_CLIP_PLANES))+1) 53 54 55 56struct clip_stage { 57 struct draw_stage stage; /**< base class */ 58 59 /* Basically duplicate some of the flatshading logic here: 60 */ 61 boolean flat; 62 uint num_color_attribs; 63 uint color_attribs[4]; /* front/back primary/secondary colors */ 64 65 float (*plane)[4]; 66}; 67 68 69/** Cast wrapper */ 70static INLINE struct clip_stage *clip_stage( struct draw_stage *stage ) 71{ 72 return (struct clip_stage *)stage; 73} 74 75 76#define LINTERP(T, OUT, IN) ((OUT) + (T) * ((IN) - (OUT))) 77 78 79/* All attributes are float[4], so this is easy: 80 */ 81static void interp_attr( float dst[4], 82 float t, 83 const float in[4], 84 const float out[4] ) 85{ 86 dst[0] = LINTERP( t, out[0], in[0] ); 87 dst[1] = LINTERP( t, out[1], in[1] ); 88 dst[2] = LINTERP( t, out[2], in[2] ); 89 dst[3] = LINTERP( t, out[3], in[3] ); 90} 91 92 93/** 94 * Copy front/back, primary/secondary colors from src vertex to dst vertex. 95 * Used when flat shading. 96 */ 97static void copy_colors( struct draw_stage *stage, 98 struct vertex_header *dst, 99 const struct vertex_header *src ) 100{ 101 const struct clip_stage *clipper = clip_stage(stage); 102 uint i; 103 for (i = 0; i < clipper->num_color_attribs; i++) { 104 const uint attr = clipper->color_attribs[i]; 105 COPY_4FV(dst->data[attr], src->data[attr]); 106 } 107} 108 109 110 111/* Interpolate between two vertices to produce a third. 112 */ 113static void interp( const struct clip_stage *clip, 114 struct vertex_header *dst, 115 float t, 116 const struct vertex_header *out, 117 const struct vertex_header *in ) 118{ 119 const unsigned nr_attrs = draw_current_shader_outputs(clip->stage.draw); 120 const unsigned pos_attr = draw_current_shader_position_output(clip->stage.draw); 121 const unsigned clip_attr = draw_current_shader_clipvertex_output(clip->stage.draw); 122 unsigned j; 123 124 /* Vertex header. 125 */ 126 dst->clipmask = 0; 127 dst->edgeflag = 0; /* will get overwritten later */ 128 dst->have_clipdist = in->have_clipdist; 129 dst->vertex_id = UNDEFINED_VERTEX_ID; 130 131 /* Interpolate the clip-space coords. 132 */ 133 interp_attr(dst->clip, t, in->clip, out->clip); 134 /* interpolate the clip-space position */ 135 interp_attr(dst->pre_clip_pos, t, in->pre_clip_pos, out->pre_clip_pos); 136 137 /* Do the projective divide and viewport transformation to get 138 * new window coordinates: 139 */ 140 { 141 const float *pos = dst->pre_clip_pos; 142 const float *scale = clip->stage.draw->viewport.scale; 143 const float *trans = clip->stage.draw->viewport.translate; 144 const float oow = 1.0f / pos[3]; 145 146 dst->data[pos_attr][0] = pos[0] * oow * scale[0] + trans[0]; 147 dst->data[pos_attr][1] = pos[1] * oow * scale[1] + trans[1]; 148 dst->data[pos_attr][2] = pos[2] * oow * scale[2] + trans[2]; 149 dst->data[pos_attr][3] = oow; 150 } 151 152 /* Other attributes 153 */ 154 for (j = 0; j < nr_attrs; j++) { 155 if (j != pos_attr && j != clip_attr) 156 interp_attr(dst->data[j], t, in->data[j], out->data[j]); 157 } 158} 159 160 161/** 162 * Emit a post-clip polygon to the next pipeline stage. The polygon 163 * will be convex and the provoking vertex will always be vertex[0]. 164 */ 165static void emit_poly( struct draw_stage *stage, 166 struct vertex_header **inlist, 167 const boolean *edgeflags, 168 unsigned n, 169 const struct prim_header *origPrim) 170{ 171 struct prim_header header; 172 unsigned i; 173 ushort edge_first, edge_middle, edge_last; 174 175 if (stage->draw->rasterizer->flatshade_first) { 176 edge_first = DRAW_PIPE_EDGE_FLAG_0; 177 edge_middle = DRAW_PIPE_EDGE_FLAG_1; 178 edge_last = DRAW_PIPE_EDGE_FLAG_2; 179 } 180 else { 181 edge_first = DRAW_PIPE_EDGE_FLAG_2; 182 edge_middle = DRAW_PIPE_EDGE_FLAG_0; 183 edge_last = DRAW_PIPE_EDGE_FLAG_1; 184 } 185 186 if (!edgeflags[0]) 187 edge_first = 0; 188 189 /* later stages may need the determinant, but only the sign matters */ 190 header.det = origPrim->det; 191 header.flags = DRAW_PIPE_RESET_STIPPLE | edge_first | edge_middle; 192 header.pad = 0; 193 194 for (i = 2; i < n; i++, header.flags = edge_middle) { 195 /* order the triangle verts to respect the provoking vertex mode */ 196 if (stage->draw->rasterizer->flatshade_first) { 197 header.v[0] = inlist[0]; /* the provoking vertex */ 198 header.v[1] = inlist[i-1]; 199 header.v[2] = inlist[i]; 200 } 201 else { 202 header.v[0] = inlist[i-1]; 203 header.v[1] = inlist[i]; 204 header.v[2] = inlist[0]; /* the provoking vertex */ 205 } 206 207 if (!edgeflags[i-1]) { 208 header.flags &= ~edge_middle; 209 } 210 211 if (i == n - 1 && edgeflags[i]) 212 header.flags |= edge_last; 213 214 if (0) { 215 const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader; 216 uint j, k; 217 debug_printf("Clipped tri: (flat-shade-first = %d)\n", 218 stage->draw->rasterizer->flatshade_first); 219 for (j = 0; j < 3; j++) { 220 for (k = 0; k < vs->info.num_outputs; k++) { 221 debug_printf(" Vert %d: Attr %d: %f %f %f %f\n", j, k, 222 header.v[j]->data[k][0], 223 header.v[j]->data[k][1], 224 header.v[j]->data[k][2], 225 header.v[j]->data[k][3]); 226 } 227 } 228 } 229 230 stage->next->tri( stage->next, &header ); 231 } 232} 233 234 235static INLINE float 236dot4(const float *a, const float *b) 237{ 238 return (a[0] * b[0] + 239 a[1] * b[1] + 240 a[2] * b[2] + 241 a[3] * b[3]); 242} 243 244/* 245 * this function extracts the clip distance for the current plane, 246 * it first checks if the shader provided a clip distance, otherwise 247 * it works out the value using the clipvertex 248 */ 249static INLINE float getclipdist(const struct clip_stage *clipper, 250 struct vertex_header *vert, 251 int plane_idx) 252{ 253 const float *plane; 254 float dp; 255 if (vert->have_clipdist && plane_idx >= 6) { 256 /* pick the correct clipdistance element from the output vectors */ 257 int _idx = plane_idx - 6; 258 int cdi = _idx >= 4; 259 int vidx = cdi ? _idx - 4 : _idx; 260 dp = vert->data[draw_current_shader_clipdistance_output(clipper->stage.draw, cdi)][vidx]; 261 } else { 262 plane = clipper->plane[plane_idx]; 263 dp = dot4(vert->clip, plane); 264 } 265 return dp; 266} 267 268/* Clip a triangle against the viewport and user clip planes. 269 */ 270static void 271do_clip_tri( struct draw_stage *stage, 272 struct prim_header *header, 273 unsigned clipmask ) 274{ 275 struct clip_stage *clipper = clip_stage( stage ); 276 struct vertex_header *a[MAX_CLIPPED_VERTICES]; 277 struct vertex_header *b[MAX_CLIPPED_VERTICES]; 278 struct vertex_header **inlist = a; 279 struct vertex_header **outlist = b; 280 unsigned tmpnr = 0; 281 unsigned n = 3; 282 unsigned i; 283 boolean aEdges[MAX_CLIPPED_VERTICES]; 284 boolean bEdges[MAX_CLIPPED_VERTICES]; 285 boolean *inEdges = aEdges; 286 boolean *outEdges = bEdges; 287 288 inlist[0] = header->v[0]; 289 inlist[1] = header->v[1]; 290 inlist[2] = header->v[2]; 291 292 /* 293 * Note: at this point we can't just use the per-vertex edge flags. 294 * We have to observe the edge flag bits set in header->flags which 295 * were set during primitive decomposition. Put those flags into 296 * an edge flags array which parallels the vertex array. 297 * Later, in the 'unfilled' pipeline stage we'll draw the edge if both 298 * the header.flags bit is set AND the per-vertex edgeflag field is set. 299 */ 300 inEdges[0] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_0); 301 inEdges[1] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_1); 302 inEdges[2] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_2); 303 304 while (clipmask && n >= 3) { 305 const unsigned plane_idx = ffs(clipmask)-1; 306 const boolean is_user_clip_plane = plane_idx >= 6; 307 struct vertex_header *vert_prev = inlist[0]; 308 boolean *edge_prev = &inEdges[0]; 309 float dp_prev; 310 unsigned outcount = 0; 311 312 dp_prev = getclipdist(clipper, vert_prev, plane_idx); 313 clipmask &= ~(1<<plane_idx); 314 315 assert(n < MAX_CLIPPED_VERTICES); 316 if (n >= MAX_CLIPPED_VERTICES) 317 return; 318 inlist[n] = inlist[0]; /* prevent rotation of vertices */ 319 inEdges[n] = inEdges[0]; 320 321 for (i = 1; i <= n; i++) { 322 struct vertex_header *vert = inlist[i]; 323 boolean *edge = &inEdges[i]; 324 325 float dp = getclipdist(clipper, vert, plane_idx); 326 327 if (!IS_NEGATIVE(dp_prev)) { 328 assert(outcount < MAX_CLIPPED_VERTICES); 329 if (outcount >= MAX_CLIPPED_VERTICES) 330 return; 331 outEdges[outcount] = *edge_prev; 332 outlist[outcount++] = vert_prev; 333 } 334 335 if (DIFFERENT_SIGNS(dp, dp_prev)) { 336 struct vertex_header *new_vert; 337 boolean *new_edge; 338 339 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 340 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 341 return; 342 new_vert = clipper->stage.tmp[tmpnr++]; 343 344 assert(outcount < MAX_CLIPPED_VERTICES); 345 if (outcount >= MAX_CLIPPED_VERTICES) 346 return; 347 348 new_edge = &outEdges[outcount]; 349 outlist[outcount++] = new_vert; 350 351 if (IS_NEGATIVE(dp)) { 352 /* Going out of bounds. Avoid division by zero as we 353 * know dp != dp_prev from DIFFERENT_SIGNS, above. 354 */ 355 float t = dp / (dp - dp_prev); 356 interp( clipper, new_vert, t, vert, vert_prev ); 357 358 /* Whether or not to set edge flag for the new vert depends 359 * on whether it's a user-defined clipping plane. We're 360 * copying NVIDIA's behaviour here. 361 */ 362 if (is_user_clip_plane) { 363 /* we want to see an edge along the clip plane */ 364 *new_edge = TRUE; 365 new_vert->edgeflag = TRUE; 366 } 367 else { 368 /* we don't want to see an edge along the frustum clip plane */ 369 *new_edge = *edge_prev; 370 new_vert->edgeflag = FALSE; 371 } 372 } 373 else { 374 /* Coming back in. 375 */ 376 float t = dp_prev / (dp_prev - dp); 377 interp( clipper, new_vert, t, vert_prev, vert ); 378 379 /* Copy starting vert's edgeflag: 380 */ 381 new_vert->edgeflag = vert_prev->edgeflag; 382 *new_edge = *edge_prev; 383 } 384 } 385 386 vert_prev = vert; 387 edge_prev = edge; 388 dp_prev = dp; 389 } 390 391 /* swap in/out lists */ 392 { 393 struct vertex_header **tmp = inlist; 394 inlist = outlist; 395 outlist = tmp; 396 n = outcount; 397 } 398 { 399 boolean *tmp = inEdges; 400 inEdges = outEdges; 401 outEdges = tmp; 402 } 403 404 } 405 406 /* If flat-shading, copy provoking vertex color to polygon vertex[0] 407 */ 408 if (n >= 3) { 409 if (clipper->flat) { 410 if (stage->draw->rasterizer->flatshade_first) { 411 if (inlist[0] != header->v[0]) { 412 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 413 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 414 return; 415 inlist[0] = dup_vert(stage, inlist[0], tmpnr++); 416 copy_colors(stage, inlist[0], header->v[0]); 417 } 418 } 419 else { 420 if (inlist[0] != header->v[2]) { 421 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 422 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 423 return; 424 inlist[0] = dup_vert(stage, inlist[0], tmpnr++); 425 copy_colors(stage, inlist[0], header->v[2]); 426 } 427 } 428 } 429 430 /* Emit the polygon as triangles to the setup stage: 431 */ 432 emit_poly( stage, inlist, inEdges, n, header ); 433 } 434} 435 436 437/* Clip a line against the viewport and user clip planes. 438 */ 439static void 440do_clip_line( struct draw_stage *stage, 441 struct prim_header *header, 442 unsigned clipmask ) 443{ 444 const struct clip_stage *clipper = clip_stage( stage ); 445 struct vertex_header *v0 = header->v[0]; 446 struct vertex_header *v1 = header->v[1]; 447 float t0 = 0.0F; 448 float t1 = 0.0F; 449 struct prim_header newprim; 450 451 while (clipmask) { 452 const unsigned plane_idx = ffs(clipmask)-1; 453 const float dp0 = getclipdist(clipper, v0, plane_idx); 454 const float dp1 = getclipdist(clipper, v1, plane_idx); 455 456 if (dp1 < 0.0F) { 457 float t = dp1 / (dp1 - dp0); 458 t1 = MAX2(t1, t); 459 } 460 461 if (dp0 < 0.0F) { 462 float t = dp0 / (dp0 - dp1); 463 t0 = MAX2(t0, t); 464 } 465 466 if (t0 + t1 >= 1.0F) 467 return; /* discard */ 468 469 clipmask &= ~(1 << plane_idx); /* turn off this plane's bit */ 470 } 471 472 if (v0->clipmask) { 473 interp( clipper, stage->tmp[0], t0, v0, v1 ); 474 475 if (clipper->flat) 476 copy_colors(stage, stage->tmp[0], v0); 477 478 newprim.v[0] = stage->tmp[0]; 479 } 480 else { 481 newprim.v[0] = v0; 482 } 483 484 if (v1->clipmask) { 485 interp( clipper, stage->tmp[1], t1, v1, v0 ); 486 newprim.v[1] = stage->tmp[1]; 487 } 488 else { 489 newprim.v[1] = v1; 490 } 491 492 stage->next->line( stage->next, &newprim ); 493} 494 495 496static void 497clip_point( struct draw_stage *stage, 498 struct prim_header *header ) 499{ 500 if (header->v[0]->clipmask == 0) 501 stage->next->point( stage->next, header ); 502} 503 504 505static void 506clip_line( struct draw_stage *stage, 507 struct prim_header *header ) 508{ 509 unsigned clipmask = (header->v[0]->clipmask | 510 header->v[1]->clipmask); 511 512 if (clipmask == 0) { 513 /* no clipping needed */ 514 stage->next->line( stage->next, header ); 515 } 516 else if ((header->v[0]->clipmask & 517 header->v[1]->clipmask) == 0) { 518 do_clip_line(stage, header, clipmask); 519 } 520 /* else, totally clipped */ 521} 522 523 524static void 525clip_tri( struct draw_stage *stage, 526 struct prim_header *header ) 527{ 528 unsigned clipmask = (header->v[0]->clipmask | 529 header->v[1]->clipmask | 530 header->v[2]->clipmask); 531 532 if (clipmask == 0) { 533 /* no clipping needed */ 534 stage->next->tri( stage->next, header ); 535 } 536 else if ((header->v[0]->clipmask & 537 header->v[1]->clipmask & 538 header->v[2]->clipmask) == 0) { 539 do_clip_tri(stage, header, clipmask); 540 } 541} 542 543 544/* Update state. Could further delay this until we hit the first 545 * primitive that really requires clipping. 546 */ 547static void 548clip_init_state( struct draw_stage *stage ) 549{ 550 struct clip_stage *clipper = clip_stage( stage ); 551 552 clipper->flat = stage->draw->rasterizer->flatshade ? TRUE : FALSE; 553 554 if (clipper->flat) { 555 const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader; 556 uint i; 557 558 clipper->num_color_attribs = 0; 559 for (i = 0; i < vs->info.num_outputs; i++) { 560 if (vs->info.output_semantic_name[i] == TGSI_SEMANTIC_COLOR || 561 vs->info.output_semantic_name[i] == TGSI_SEMANTIC_BCOLOR) { 562 clipper->color_attribs[clipper->num_color_attribs++] = i; 563 } 564 } 565 } 566 567 stage->tri = clip_tri; 568 stage->line = clip_line; 569} 570 571 572 573static void clip_first_tri( struct draw_stage *stage, 574 struct prim_header *header ) 575{ 576 clip_init_state( stage ); 577 stage->tri( stage, header ); 578} 579 580static void clip_first_line( struct draw_stage *stage, 581 struct prim_header *header ) 582{ 583 clip_init_state( stage ); 584 stage->line( stage, header ); 585} 586 587 588static void clip_flush( struct draw_stage *stage, 589 unsigned flags ) 590{ 591 stage->tri = clip_first_tri; 592 stage->line = clip_first_line; 593 stage->next->flush( stage->next, flags ); 594} 595 596 597static void clip_reset_stipple_counter( struct draw_stage *stage ) 598{ 599 stage->next->reset_stipple_counter( stage->next ); 600} 601 602 603static void clip_destroy( struct draw_stage *stage ) 604{ 605 draw_free_temp_verts( stage ); 606 FREE( stage ); 607} 608 609 610/** 611 * Allocate a new clipper stage. 612 * \return pointer to new stage object 613 */ 614struct draw_stage *draw_clip_stage( struct draw_context *draw ) 615{ 616 struct clip_stage *clipper = CALLOC_STRUCT(clip_stage); 617 if (clipper == NULL) 618 goto fail; 619 620 clipper->stage.draw = draw; 621 clipper->stage.name = "clipper"; 622 clipper->stage.point = clip_point; 623 clipper->stage.line = clip_first_line; 624 clipper->stage.tri = clip_first_tri; 625 clipper->stage.flush = clip_flush; 626 clipper->stage.reset_stipple_counter = clip_reset_stipple_counter; 627 clipper->stage.destroy = clip_destroy; 628 629 clipper->plane = draw->plane; 630 631 if (!draw_alloc_temp_verts( &clipper->stage, MAX_CLIPPED_VERTICES+1 )) 632 goto fail; 633 634 return &clipper->stage; 635 636 fail: 637 if (clipper) 638 clipper->stage.destroy( &clipper->stage ); 639 640 return NULL; 641} 642