draw_pipe_clip.c revision 40c5987ed84f9f0b8bb1f707bb13c1aafc39330a
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->pad = 0; 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/* Clip a triangle against the viewport and user clip planes. 246 */ 247static void 248do_clip_tri( struct draw_stage *stage, 249 struct prim_header *header, 250 unsigned clipmask ) 251{ 252 struct clip_stage *clipper = clip_stage( stage ); 253 struct vertex_header *a[MAX_CLIPPED_VERTICES]; 254 struct vertex_header *b[MAX_CLIPPED_VERTICES]; 255 struct vertex_header **inlist = a; 256 struct vertex_header **outlist = b; 257 unsigned tmpnr = 0; 258 unsigned n = 3; 259 unsigned i; 260 boolean aEdges[MAX_CLIPPED_VERTICES]; 261 boolean bEdges[MAX_CLIPPED_VERTICES]; 262 boolean *inEdges = aEdges; 263 boolean *outEdges = bEdges; 264 265 inlist[0] = header->v[0]; 266 inlist[1] = header->v[1]; 267 inlist[2] = header->v[2]; 268 269 /* 270 * Note: at this point we can't just use the per-vertex edge flags. 271 * We have to observe the edge flag bits set in header->flags which 272 * were set during primitive decomposition. Put those flags into 273 * an edge flags array which parallels the vertex array. 274 * Later, in the 'unfilled' pipeline stage we'll draw the edge if both 275 * the header.flags bit is set AND the per-vertex edgeflag field is set. 276 */ 277 inEdges[0] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_0); 278 inEdges[1] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_1); 279 inEdges[2] = !!(header->flags & DRAW_PIPE_EDGE_FLAG_2); 280 281 while (clipmask && n >= 3) { 282 const unsigned plane_idx = ffs(clipmask)-1; 283 const boolean is_user_clip_plane = plane_idx >= 6; 284 const float *plane = clipper->plane[plane_idx]; 285 struct vertex_header *vert_prev = inlist[0]; 286 boolean *edge_prev = &inEdges[0]; 287 float dp_prev = dot4( vert_prev->clip, plane ); 288 unsigned outcount = 0; 289 290 clipmask &= ~(1<<plane_idx); 291 292 assert(n < MAX_CLIPPED_VERTICES); 293 if (n >= MAX_CLIPPED_VERTICES) 294 return; 295 inlist[n] = inlist[0]; /* prevent rotation of vertices */ 296 inEdges[n] = inEdges[0]; 297 298 for (i = 1; i <= n; i++) { 299 struct vertex_header *vert = inlist[i]; 300 boolean *edge = &inEdges[i]; 301 302 float dp = dot4( vert->clip, plane ); 303 304 if (!IS_NEGATIVE(dp_prev)) { 305 assert(outcount < MAX_CLIPPED_VERTICES); 306 if (outcount >= MAX_CLIPPED_VERTICES) 307 return; 308 outEdges[outcount] = *edge_prev; 309 outlist[outcount++] = vert_prev; 310 } 311 312 if (DIFFERENT_SIGNS(dp, dp_prev)) { 313 struct vertex_header *new_vert; 314 boolean *new_edge; 315 316 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 317 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 318 return; 319 new_vert = clipper->stage.tmp[tmpnr++]; 320 321 assert(outcount < MAX_CLIPPED_VERTICES); 322 if (outcount >= MAX_CLIPPED_VERTICES) 323 return; 324 325 new_edge = &outEdges[outcount]; 326 outlist[outcount++] = new_vert; 327 328 if (IS_NEGATIVE(dp)) { 329 /* Going out of bounds. Avoid division by zero as we 330 * know dp != dp_prev from DIFFERENT_SIGNS, above. 331 */ 332 float t = dp / (dp - dp_prev); 333 interp( clipper, new_vert, t, vert, vert_prev ); 334 335 /* Whether or not to set edge flag for the new vert depends 336 * on whether it's a user-defined clipping plane. We're 337 * copying NVIDIA's behaviour here. 338 */ 339 if (is_user_clip_plane) { 340 /* we want to see an edge along the clip plane */ 341 *new_edge = TRUE; 342 new_vert->edgeflag = TRUE; 343 } 344 else { 345 /* we don't want to see an edge along the frustum clip plane */ 346 *new_edge = *edge_prev; 347 new_vert->edgeflag = FALSE; 348 } 349 } 350 else { 351 /* Coming back in. 352 */ 353 float t = dp_prev / (dp_prev - dp); 354 interp( clipper, new_vert, t, vert_prev, vert ); 355 356 /* Copy starting vert's edgeflag: 357 */ 358 new_vert->edgeflag = vert_prev->edgeflag; 359 *new_edge = *edge_prev; 360 } 361 } 362 363 vert_prev = vert; 364 edge_prev = edge; 365 dp_prev = dp; 366 } 367 368 /* swap in/out lists */ 369 { 370 struct vertex_header **tmp = inlist; 371 inlist = outlist; 372 outlist = tmp; 373 n = outcount; 374 } 375 { 376 boolean *tmp = inEdges; 377 inEdges = outEdges; 378 outEdges = tmp; 379 } 380 381 } 382 383 /* If flat-shading, copy provoking vertex color to polygon vertex[0] 384 */ 385 if (n >= 3) { 386 if (clipper->flat) { 387 if (stage->draw->rasterizer->flatshade_first) { 388 if (inlist[0] != header->v[0]) { 389 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 390 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 391 return; 392 inlist[0] = dup_vert(stage, inlist[0], tmpnr++); 393 copy_colors(stage, inlist[0], header->v[0]); 394 } 395 } 396 else { 397 if (inlist[0] != header->v[2]) { 398 assert(tmpnr < MAX_CLIPPED_VERTICES + 1); 399 if (tmpnr >= MAX_CLIPPED_VERTICES + 1) 400 return; 401 inlist[0] = dup_vert(stage, inlist[0], tmpnr++); 402 copy_colors(stage, inlist[0], header->v[2]); 403 } 404 } 405 } 406 407 /* Emit the polygon as triangles to the setup stage: 408 */ 409 emit_poly( stage, inlist, inEdges, n, header ); 410 } 411} 412 413 414/* Clip a line against the viewport and user clip planes. 415 */ 416static void 417do_clip_line( struct draw_stage *stage, 418 struct prim_header *header, 419 unsigned clipmask ) 420{ 421 const struct clip_stage *clipper = clip_stage( stage ); 422 struct vertex_header *v0 = header->v[0]; 423 struct vertex_header *v1 = header->v[1]; 424 const float *pos0 = v0->clip; 425 const float *pos1 = v1->clip; 426 float t0 = 0.0F; 427 float t1 = 0.0F; 428 struct prim_header newprim; 429 430 while (clipmask) { 431 const unsigned plane_idx = ffs(clipmask)-1; 432 const float *plane = clipper->plane[plane_idx]; 433 const float dp0 = dot4( pos0, plane ); 434 const float dp1 = dot4( pos1, plane ); 435 436 if (dp1 < 0.0F) { 437 float t = dp1 / (dp1 - dp0); 438 t1 = MAX2(t1, t); 439 } 440 441 if (dp0 < 0.0F) { 442 float t = dp0 / (dp0 - dp1); 443 t0 = MAX2(t0, t); 444 } 445 446 if (t0 + t1 >= 1.0F) 447 return; /* discard */ 448 449 clipmask &= ~(1 << plane_idx); /* turn off this plane's bit */ 450 } 451 452 if (v0->clipmask) { 453 interp( clipper, stage->tmp[0], t0, v0, v1 ); 454 455 if (clipper->flat) 456 copy_colors(stage, stage->tmp[0], v0); 457 458 newprim.v[0] = stage->tmp[0]; 459 } 460 else { 461 newprim.v[0] = v0; 462 } 463 464 if (v1->clipmask) { 465 interp( clipper, stage->tmp[1], t1, v1, v0 ); 466 newprim.v[1] = stage->tmp[1]; 467 } 468 else { 469 newprim.v[1] = v1; 470 } 471 472 stage->next->line( stage->next, &newprim ); 473} 474 475 476static void 477clip_point( struct draw_stage *stage, 478 struct prim_header *header ) 479{ 480 if (header->v[0]->clipmask == 0) 481 stage->next->point( stage->next, header ); 482} 483 484 485static void 486clip_line( struct draw_stage *stage, 487 struct prim_header *header ) 488{ 489 unsigned clipmask = (header->v[0]->clipmask | 490 header->v[1]->clipmask); 491 492 if (clipmask == 0) { 493 /* no clipping needed */ 494 stage->next->line( stage->next, header ); 495 } 496 else if ((header->v[0]->clipmask & 497 header->v[1]->clipmask) == 0) { 498 do_clip_line(stage, header, clipmask); 499 } 500 /* else, totally clipped */ 501} 502 503 504static void 505clip_tri( struct draw_stage *stage, 506 struct prim_header *header ) 507{ 508 unsigned clipmask = (header->v[0]->clipmask | 509 header->v[1]->clipmask | 510 header->v[2]->clipmask); 511 512 if (clipmask == 0) { 513 /* no clipping needed */ 514 stage->next->tri( stage->next, header ); 515 } 516 else if ((header->v[0]->clipmask & 517 header->v[1]->clipmask & 518 header->v[2]->clipmask) == 0) { 519 do_clip_tri(stage, header, clipmask); 520 } 521} 522 523 524/* Update state. Could further delay this until we hit the first 525 * primitive that really requires clipping. 526 */ 527static void 528clip_init_state( struct draw_stage *stage ) 529{ 530 struct clip_stage *clipper = clip_stage( stage ); 531 532 clipper->flat = stage->draw->rasterizer->flatshade ? TRUE : FALSE; 533 534 if (clipper->flat) { 535 const struct draw_vertex_shader *vs = stage->draw->vs.vertex_shader; 536 uint i; 537 538 clipper->num_color_attribs = 0; 539 for (i = 0; i < vs->info.num_outputs; i++) { 540 if (vs->info.output_semantic_name[i] == TGSI_SEMANTIC_COLOR || 541 vs->info.output_semantic_name[i] == TGSI_SEMANTIC_BCOLOR) { 542 clipper->color_attribs[clipper->num_color_attribs++] = i; 543 } 544 } 545 } 546 547 stage->tri = clip_tri; 548 stage->line = clip_line; 549} 550 551 552 553static void clip_first_tri( struct draw_stage *stage, 554 struct prim_header *header ) 555{ 556 clip_init_state( stage ); 557 stage->tri( stage, header ); 558} 559 560static void clip_first_line( struct draw_stage *stage, 561 struct prim_header *header ) 562{ 563 clip_init_state( stage ); 564 stage->line( stage, header ); 565} 566 567 568static void clip_flush( struct draw_stage *stage, 569 unsigned flags ) 570{ 571 stage->tri = clip_first_tri; 572 stage->line = clip_first_line; 573 stage->next->flush( stage->next, flags ); 574} 575 576 577static void clip_reset_stipple_counter( struct draw_stage *stage ) 578{ 579 stage->next->reset_stipple_counter( stage->next ); 580} 581 582 583static void clip_destroy( struct draw_stage *stage ) 584{ 585 draw_free_temp_verts( stage ); 586 FREE( stage ); 587} 588 589 590/** 591 * Allocate a new clipper stage. 592 * \return pointer to new stage object 593 */ 594struct draw_stage *draw_clip_stage( struct draw_context *draw ) 595{ 596 struct clip_stage *clipper = CALLOC_STRUCT(clip_stage); 597 if (clipper == NULL) 598 goto fail; 599 600 clipper->stage.draw = draw; 601 clipper->stage.name = "clipper"; 602 clipper->stage.point = clip_point; 603 clipper->stage.line = clip_first_line; 604 clipper->stage.tri = clip_first_tri; 605 clipper->stage.flush = clip_flush; 606 clipper->stage.reset_stipple_counter = clip_reset_stipple_counter; 607 clipper->stage.destroy = clip_destroy; 608 609 clipper->plane = draw->plane; 610 611 if (!draw_alloc_temp_verts( &clipper->stage, MAX_CLIPPED_VERTICES+1 )) 612 goto fail; 613 614 return &clipper->stage; 615 616 fail: 617 if (clipper) 618 clipper->stage.destroy( &clipper->stage ); 619 620 return NULL; 621} 622