draw_pipe_clip.c revision 1865f341d8f45b389061fc08d2da90b7aa8a6099
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 clip_dist[2]; 123 unsigned j; 124 125 clip_dist[0] = draw_current_shader_clipdistance_output(clip->stage.draw, 0); 126 clip_dist[1] = draw_current_shader_clipdistance_output(clip->stage.draw, 1); 127 128 /* Vertex header. 129 */ 130 dst->clipmask = 0; 131 dst->edgeflag = 0; /* will get overwritten later */ 132 dst->have_clipdist = in->have_clipdist; 133 dst->vertex_id = UNDEFINED_VERTEX_ID; 134 135 /* Interpolate the clip-space coords. 136 */ 137 interp_attr(dst->clip, t, in->clip, out->clip); 138 /* interpolate the clip-space position */ 139 interp_attr(dst->pre_clip_pos, t, in->pre_clip_pos, out->pre_clip_pos); 140 141 /* Do the projective divide and viewport transformation to get 142 * new window coordinates: 143 */ 144 { 145 const float *pos = dst->pre_clip_pos; 146 const float *scale = clip->stage.draw->viewport.scale; 147 const float *trans = clip->stage.draw->viewport.translate; 148 const float oow = 1.0f / pos[3]; 149 150 dst->data[pos_attr][0] = pos[0] * oow * scale[0] + trans[0]; 151 dst->data[pos_attr][1] = pos[1] * oow * scale[1] + trans[1]; 152 dst->data[pos_attr][2] = pos[2] * oow * scale[2] + trans[2]; 153 dst->data[pos_attr][3] = oow; 154 } 155 156 /* Other attributes 157 */ 158 for (j = 0; j < nr_attrs; j++) { 159 if (j != pos_attr && j != clip_attr) 160 interp_attr(dst->data[j], t, in->data[j], out->data[j]); 161 } 162} 163 164 165/** 166 * Emit a post-clip polygon to the next pipeline stage. The polygon 167 * will be convex and the provoking vertex will always be vertex[0]. 168 */ 169static void emit_poly( struct draw_stage *stage, 170 struct vertex_header **inlist, 171 const boolean *edgeflags, 172 unsigned n, 173 const struct prim_header *origPrim) 174{ 175 struct prim_header header; 176 unsigned i; 177 ushort edge_first, edge_middle, edge_last; 178 179 if (stage->draw->rasterizer->flatshade_first) { 180 edge_first = DRAW_PIPE_EDGE_FLAG_0; 181 edge_middle = DRAW_PIPE_EDGE_FLAG_1; 182 edge_last = DRAW_PIPE_EDGE_FLAG_2; 183 } 184 else { 185 edge_first = DRAW_PIPE_EDGE_FLAG_2; 186 edge_middle = DRAW_PIPE_EDGE_FLAG_0; 187 edge_last = DRAW_PIPE_EDGE_FLAG_1; 188 } 189 190 if (!edgeflags[0]) 191 edge_first = 0; 192 193 /* later stages may need the determinant, but only the sign matters */ 194 header.det = origPrim->det; 195 header.flags = DRAW_PIPE_RESET_STIPPLE | edge_first | edge_middle; 196 header.pad = 0; 197 198 for (i = 2; i < n; i++, header.flags = edge_middle) { 199 /* order the triangle verts to respect the provoking vertex mode */ 200 if (stage->draw->rasterizer->flatshade_first) { 201 header.v[0] = inlist[0]; /* the provoking vertex */ 202 header.v[1] = inlist[i-1]; 203 header.v[2] = inlist[i]; 204 } 205 else { 206 header.v[0] = inlist[i-1]; 207 header.v[1] = inlist[i]; 208 header.v[2] = inlist[0]; /* the provoking vertex */ 209 } 210 211 if (!edgeflags[i-1]) { 212 header.flags &= ~edge_middle; 213 } 214 215 if (i == n - 1 && edgeflags[i]) 216 header.flags |= edge_last; 217 218 if (0) { 219 const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader; 220 uint j, k; 221 debug_printf("Clipped tri: (flat-shade-first = %d)\n", 222 stage->draw->rasterizer->flatshade_first); 223 for (j = 0; j < 3; j++) { 224 for (k = 0; k < vs->info.num_outputs; k++) { 225 debug_printf(" Vert %d: Attr %d: %f %f %f %f\n", j, k, 226 header.v[j]->data[k][0], 227 header.v[j]->data[k][1], 228 header.v[j]->data[k][2], 229 header.v[j]->data[k][3]); 230 } 231 } 232 } 233 234 stage->next->tri( stage->next, &header ); 235 } 236} 237 238 239static INLINE float 240dot4(const float *a, const float *b) 241{ 242 return (a[0] * b[0] + 243 a[1] * b[1] + 244 a[2] * b[2] + 245 a[3] * b[3]); 246} 247 248/* 249 * this function extracts the clip distance for the current plane, 250 * it first checks if the shader provided a clip distance, otherwise 251 * it works out the value using the clipvertex 252 */ 253static INLINE float getclipdist(const struct clip_stage *clipper, 254 struct vertex_header *vert, 255 int plane_idx) 256{ 257 const float *plane; 258 float dp; 259 if (vert->have_clipdist && plane_idx >= 6) { 260 /* pick the correct clipdistance element from the output vectors */ 261 int _idx = plane_idx - 6; 262 int cdi = _idx >= 4; 263 int vidx = cdi ? _idx - 4 : _idx; 264 dp = vert->data[draw_current_shader_clipdistance_output(clipper->stage.draw, cdi)][vidx]; 265 } else { 266 plane = clipper->plane[plane_idx]; 267 dp = dot4(vert->clip, plane); 268 } 269 return dp; 270} 271 272/* Clip a triangle against the viewport and user clip planes. 273 */ 274static void 275do_clip_tri( struct draw_stage *stage, 276 struct prim_header *header, 277 unsigned clipmask ) 278{ 279 struct clip_stage *clipper = clip_stage( stage ); 280 struct vertex_header *a[MAX_CLIPPED_VERTICES]; 281 struct vertex_header *b[MAX_CLIPPED_VERTICES]; 282 struct vertex_header **inlist = a; 283 struct vertex_header **outlist = b; 284 unsigned tmpnr = 0; 285 unsigned n = 3; 286 unsigned i; 287 boolean aEdges[MAX_CLIPPED_VERTICES]; 288 boolean bEdges[MAX_CLIPPED_VERTICES]; 289 boolean *inEdges = aEdges; 290 boolean *outEdges = bEdges; 291 292 inlist[0] = header->v[0]; 293 inlist[1] = header->v[1]; 294 inlist[2] = header->v[2]; 295 296 /* 297 * Note: at this point we can't just use the per-vertex edge flags. 298 * We have to observe the edge flag bits set in header->flags which 299 * were set during primitive decomposition. Put those flags into 300 * an edge flags array which parallels the vertex array. 301 * Later, in the 'unfilled' pipeline stage we'll draw the edge if both 302 * the header.flags bit is set AND the per-vertex edgeflag field is set. 303 */ 304 inEdges[0] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_0); 305 inEdges[1] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_1); 306 inEdges[2] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_2); 307 308 while (clipmask && n >= 3) { 309 const unsigned plane_idx = ffs(clipmask)-1; 310 const boolean is_user_clip_plane = plane_idx >= 6; 311 struct vertex_header *vert_prev = inlist[0]; 312 boolean *edge_prev = &inEdges[0]; 313 float dp_prev; 314 unsigned outcount = 0; 315 316 dp_prev = getclipdist(clipper, vert_prev, plane_idx); 317 clipmask &= ~(1<<plane_idx); 318 319 assert(n < MAX_CLIPPED_VERTICES); 320 if (n >= MAX_CLIPPED_VERTICES) 321 return; 322 inlist[n] = inlist[0]; /* prevent rotation of vertices */ 323 inEdges[n] = inEdges[0]; 324 325 for (i = 1; i <= n; i++) { 326 struct vertex_header *vert = inlist[i]; 327 boolean *edge = &inEdges[i]; 328 329 float dp = getclipdist(clipper, vert, plane_idx); 330 331 if (!IS_NEGATIVE(dp_prev)) { 332 assert(outcount < MAX_CLIPPED_VERTICES); 333 if (outcount >= MAX_CLIPPED_VERTICES) 334 return; 335 outEdges[outcount] = *edge_prev; 336 outlist[outcount++] = vert_prev; 337 } 338 339 if (DIFFERENT_SIGNS(dp, dp_prev)) { 340 struct vertex_header *new_vert; 341 boolean *new_edge; 342 343 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 344 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 345 return; 346 new_vert = clipper->stage.tmp[tmpnr++]; 347 348 assert(outcount < MAX_CLIPPED_VERTICES); 349 if (outcount >= MAX_CLIPPED_VERTICES) 350 return; 351 352 new_edge = &outEdges[outcount]; 353 outlist[outcount++] = new_vert; 354 355 if (IS_NEGATIVE(dp)) { 356 /* Going out of bounds. Avoid division by zero as we 357 * know dp != dp_prev from DIFFERENT_SIGNS, above. 358 */ 359 float t = dp / (dp - dp_prev); 360 interp( clipper, new_vert, t, vert, vert_prev ); 361 362 /* Whether or not to set edge flag for the new vert depends 363 * on whether it's a user-defined clipping plane. We're 364 * copying NVIDIA's behaviour here. 365 */ 366 if (is_user_clip_plane) { 367 /* we want to see an edge along the clip plane */ 368 *new_edge = TRUE; 369 new_vert->edgeflag = TRUE; 370 } 371 else { 372 /* we don't want to see an edge along the frustum clip plane */ 373 *new_edge = *edge_prev; 374 new_vert->edgeflag = FALSE; 375 } 376 } 377 else { 378 /* Coming back in. 379 */ 380 float t = dp_prev / (dp_prev - dp); 381 interp( clipper, new_vert, t, vert_prev, vert ); 382 383 /* Copy starting vert's edgeflag: 384 */ 385 new_vert->edgeflag = vert_prev->edgeflag; 386 *new_edge = *edge_prev; 387 } 388 } 389 390 vert_prev = vert; 391 edge_prev = edge; 392 dp_prev = dp; 393 } 394 395 /* swap in/out lists */ 396 { 397 struct vertex_header **tmp = inlist; 398 inlist = outlist; 399 outlist = tmp; 400 n = outcount; 401 } 402 { 403 boolean *tmp = inEdges; 404 inEdges = outEdges; 405 outEdges = tmp; 406 } 407 408 } 409 410 /* If flat-shading, copy provoking vertex color to polygon vertex[0] 411 */ 412 if (n >= 3) { 413 if (clipper->flat) { 414 if (stage->draw->rasterizer->flatshade_first) { 415 if (inlist[0] != header->v[0]) { 416 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 417 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 418 return; 419 inlist[0] = dup_vert(stage, inlist[0], tmpnr++); 420 copy_colors(stage, inlist[0], header->v[0]); 421 } 422 } 423 else { 424 if (inlist[0] != header->v[2]) { 425 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 426 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 427 return; 428 inlist[0] = dup_vert(stage, inlist[0], tmpnr++); 429 copy_colors(stage, inlist[0], header->v[2]); 430 } 431 } 432 } 433 434 /* Emit the polygon as triangles to the setup stage: 435 */ 436 emit_poly( stage, inlist, inEdges, n, header ); 437 } 438} 439 440 441/* Clip a line against the viewport and user clip planes. 442 */ 443static void 444do_clip_line( struct draw_stage *stage, 445 struct prim_header *header, 446 unsigned clipmask ) 447{ 448 const struct clip_stage *clipper = clip_stage( stage ); 449 struct vertex_header *v0 = header->v[0]; 450 struct vertex_header *v1 = header->v[1]; 451 float t0 = 0.0F; 452 float t1 = 0.0F; 453 struct prim_header newprim; 454 455 while (clipmask) { 456 const unsigned plane_idx = ffs(clipmask)-1; 457 const float dp0 = getclipdist(clipper, v0, plane_idx); 458 const float dp1 = getclipdist(clipper, v1, plane_idx); 459 460 if (dp1 < 0.0F) { 461 float t = dp1 / (dp1 - dp0); 462 t1 = MAX2(t1, t); 463 } 464 465 if (dp0 < 0.0F) { 466 float t = dp0 / (dp0 - dp1); 467 t0 = MAX2(t0, t); 468 } 469 470 if (t0 + t1 >= 1.0F) 471 return; /* discard */ 472 473 clipmask &= ~(1 << plane_idx); /* turn off this plane's bit */ 474 } 475 476 if (v0->clipmask) { 477 interp( clipper, stage->tmp[0], t0, v0, v1 ); 478 479 if (clipper->flat) 480 copy_colors(stage, stage->tmp[0], v0); 481 482 newprim.v[0] = stage->tmp[0]; 483 } 484 else { 485 newprim.v[0] = v0; 486 } 487 488 if (v1->clipmask) { 489 interp( clipper, stage->tmp[1], t1, v1, v0 ); 490 newprim.v[1] = stage->tmp[1]; 491 } 492 else { 493 newprim.v[1] = v1; 494 } 495 496 stage->next->line( stage->next, &newprim ); 497} 498 499 500static void 501clip_point( struct draw_stage *stage, 502 struct prim_header *header ) 503{ 504 if (header->v[0]->clipmask == 0) 505 stage->next->point( stage->next, header ); 506} 507 508 509static void 510clip_line( struct draw_stage *stage, 511 struct prim_header *header ) 512{ 513 unsigned clipmask = (header->v[0]->clipmask | 514 header->v[1]->clipmask); 515 516 if (clipmask == 0) { 517 /* no clipping needed */ 518 stage->next->line( stage->next, header ); 519 } 520 else if ((header->v[0]->clipmask & 521 header->v[1]->clipmask) == 0) { 522 do_clip_line(stage, header, clipmask); 523 } 524 /* else, totally clipped */ 525} 526 527 528static void 529clip_tri( struct draw_stage *stage, 530 struct prim_header *header ) 531{ 532 unsigned clipmask = (header->v[0]->clipmask | 533 header->v[1]->clipmask | 534 header->v[2]->clipmask); 535 536 if (clipmask == 0) { 537 /* no clipping needed */ 538 stage->next->tri( stage->next, header ); 539 } 540 else if ((header->v[0]->clipmask & 541 header->v[1]->clipmask & 542 header->v[2]->clipmask) == 0) { 543 do_clip_tri(stage, header, clipmask); 544 } 545} 546 547 548/* Update state. Could further delay this until we hit the first 549 * primitive that really requires clipping. 550 */ 551static void 552clip_init_state( struct draw_stage *stage ) 553{ 554 struct clip_stage *clipper = clip_stage( stage ); 555 556 clipper->flat = stage->draw->rasterizer->flatshade ? TRUE : FALSE; 557 558 if (clipper->flat) { 559 const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader; 560 uint i; 561 562 clipper->num_color_attribs = 0; 563 for (i = 0; i < vs->info.num_outputs; i++) { 564 if (vs->info.output_semantic_name[i] == TGSI_SEMANTIC_COLOR || 565 vs->info.output_semantic_name[i] == TGSI_SEMANTIC_BCOLOR) { 566 clipper->color_attribs[clipper->num_color_attribs++] = i; 567 } 568 } 569 } 570 571 stage->tri = clip_tri; 572 stage->line = clip_line; 573} 574 575 576 577static void clip_first_tri( struct draw_stage *stage, 578 struct prim_header *header ) 579{ 580 clip_init_state( stage ); 581 stage->tri( stage, header ); 582} 583 584static void clip_first_line( struct draw_stage *stage, 585 struct prim_header *header ) 586{ 587 clip_init_state( stage ); 588 stage->line( stage, header ); 589} 590 591 592static void clip_flush( struct draw_stage *stage, 593 unsigned flags ) 594{ 595 stage->tri = clip_first_tri; 596 stage->line = clip_first_line; 597 stage->next->flush( stage->next, flags ); 598} 599 600 601static void clip_reset_stipple_counter( struct draw_stage *stage ) 602{ 603 stage->next->reset_stipple_counter( stage->next ); 604} 605 606 607static void clip_destroy( struct draw_stage *stage ) 608{ 609 draw_free_temp_verts( stage ); 610 FREE( stage ); 611} 612 613 614/** 615 * Allocate a new clipper stage. 616 * \return pointer to new stage object 617 */ 618struct draw_stage *draw_clip_stage( struct draw_context *draw ) 619{ 620 struct clip_stage *clipper = CALLOC_STRUCT(clip_stage); 621 if (clipper == NULL) 622 goto fail; 623 624 clipper->stage.draw = draw; 625 clipper->stage.name = "clipper"; 626 clipper->stage.point = clip_point; 627 clipper->stage.line = clip_first_line; 628 clipper->stage.tri = clip_first_tri; 629 clipper->stage.flush = clip_flush; 630 clipper->stage.reset_stipple_counter = clip_reset_stipple_counter; 631 clipper->stage.destroy = clip_destroy; 632 633 clipper->plane = draw->plane; 634 635 if (!draw_alloc_temp_verts( &clipper->stage, MAX_CLIPPED_VERTICES+1 )) 636 goto fail; 637 638 return &clipper->stage; 639 640 fail: 641 if (clipper) 642 clipper->stage.destroy( &clipper->stage ); 643 644 return NULL; 645} 646