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