1/************************************************************************** 2 * 3 * Copyright 2007 VMware, Inc. 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 VMWARE 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 Drawing stage for polygon culling 30 */ 31 32/* Authors: Keith Whitwell <keithw@vmware.com> 33 */ 34 35 36#include "util/u_math.h" 37#include "util/u_memory.h" 38#include "pipe/p_defines.h" 39#include "draw_pipe.h" 40 41 42struct cull_stage { 43 struct draw_stage stage; 44 unsigned cull_face; /**< which face(s) to cull (one of PIPE_FACE_x) */ 45 unsigned front_ccw; 46}; 47 48 49static inline struct cull_stage *cull_stage( struct draw_stage *stage ) 50{ 51 return (struct cull_stage *)stage; 52} 53 54static inline boolean 55cull_distance_is_out(float dist) 56{ 57 return (dist < 0.0f) || util_is_inf_or_nan(dist); 58} 59 60/* 61 * If the shader writes the culldistance then we can 62 * perform distance based culling. Distance based 63 * culling doesn't require a face and can be performed 64 * on primitives without faces (e.g. points and lines) 65 */ 66static void cull_point( struct draw_stage *stage, 67 struct prim_header *header ) 68{ 69 const unsigned num_written_culldistances = 70 draw_current_shader_num_written_culldistances(stage->draw); 71 const unsigned num_written_clipdistances = 72 draw_current_shader_num_written_clipdistances(stage->draw); 73 unsigned i; 74 75 debug_assert(num_written_culldistances); 76 77 for (i = 0; i < num_written_culldistances; ++i) { 78 unsigned cull_idx = (num_written_clipdistances + i) / 4; 79 unsigned out_idx = 80 draw_current_shader_ccdistance_output(stage->draw, cull_idx); 81 unsigned idx = (num_written_clipdistances + i) % 4; 82 float cull1 = header->v[0]->data[out_idx][idx]; 83 boolean vert1_out = cull_distance_is_out(cull1); 84 if (vert1_out) 85 return; 86 } 87 stage->next->point( stage->next, header ); 88} 89 90/* 91 * If the shader writes the culldistance then we can 92 * perform distance based culling. Distance based 93 * culling doesn't require a face and can be performed 94 * on primitives without faces (e.g. points and lines) 95 */ 96static void cull_line( struct draw_stage *stage, 97 struct prim_header *header ) 98{ 99 const unsigned num_written_culldistances = 100 draw_current_shader_num_written_culldistances(stage->draw); 101 const unsigned num_written_clipdistances = 102 draw_current_shader_num_written_clipdistances(stage->draw); 103 unsigned i; 104 105 debug_assert(num_written_culldistances); 106 107 for (i = 0; i < num_written_culldistances; ++i) { 108 unsigned cull_idx = (num_written_clipdistances + i) / 4; 109 unsigned out_idx = 110 draw_current_shader_ccdistance_output(stage->draw, cull_idx); 111 unsigned idx = (num_written_clipdistances + i) % 4; 112 float cull1 = header->v[0]->data[out_idx][idx]; 113 float cull2 = header->v[1]->data[out_idx][idx]; 114 boolean vert1_out = cull_distance_is_out(cull1); 115 boolean vert2_out = cull_distance_is_out(cull2); 116 if (vert1_out && vert2_out) 117 return; 118 } 119 stage->next->line( stage->next, header ); 120} 121 122/* 123 * Triangles can be culled either using the cull distance 124 * shader outputs or the regular face culling. If required 125 * this function performs both, starting with distance culling. 126 */ 127static void cull_tri( struct draw_stage *stage, 128 struct prim_header *header ) 129{ 130 const unsigned num_written_culldistances = 131 draw_current_shader_num_written_culldistances(stage->draw); 132 const unsigned num_written_clipdistances = 133 draw_current_shader_num_written_clipdistances(stage->draw); 134 /* Do the distance culling */ 135 if (num_written_culldistances) { 136 unsigned i; 137 for (i = 0; i < num_written_culldistances; ++i) { 138 unsigned cull_idx = (num_written_clipdistances + i) / 4; 139 unsigned out_idx = 140 draw_current_shader_ccdistance_output(stage->draw, cull_idx); 141 unsigned idx = (num_written_clipdistances + i) % 4; 142 float cull1 = header->v[0]->data[out_idx][idx]; 143 float cull2 = header->v[1]->data[out_idx][idx]; 144 float cull3 = header->v[2]->data[out_idx][idx]; 145 boolean vert1_out = cull_distance_is_out(cull1); 146 boolean vert2_out = cull_distance_is_out(cull2); 147 boolean vert3_out = cull_distance_is_out(cull3); 148 if (vert1_out && vert2_out && vert3_out) 149 return; 150 } 151 } 152 153 /* Do the regular face culling */ 154 { 155 const unsigned pos = draw_current_shader_position_output(stage->draw); 156 /* Window coords: */ 157 const float *v0 = header->v[0]->data[pos]; 158 const float *v1 = header->v[1]->data[pos]; 159 const float *v2 = header->v[2]->data[pos]; 160 161 /* edge vectors: e = v0 - v2, f = v1 - v2 */ 162 const float ex = v0[0] - v2[0]; 163 const float ey = v0[1] - v2[1]; 164 const float fx = v1[0] - v2[0]; 165 const float fy = v1[1] - v2[1]; 166 167 168 /* det = cross(e,f).z */ 169 header->det = ex * fy - ey * fx; 170 171 if (header->det != 0) { 172 /* if det < 0 then Z points toward the camera and the triangle is 173 * counter-clockwise winding. 174 */ 175 unsigned ccw = (header->det < 0); 176 unsigned face = ((ccw == cull_stage(stage)->front_ccw) ? 177 PIPE_FACE_FRONT : 178 PIPE_FACE_BACK); 179 180 if ((face & cull_stage(stage)->cull_face) == 0) { 181 /* triangle is not culled, pass to next stage */ 182 stage->next->tri( stage->next, header ); 183 } 184 } 185 } 186} 187 188static void cull_first_point( struct draw_stage *stage, 189 struct prim_header *header ) 190{ 191 const unsigned num_written_culldistances = 192 draw_current_shader_num_written_culldistances(stage->draw); 193 194 if (num_written_culldistances) { 195 stage->point = cull_point; 196 stage->point( stage, header ); 197 } else { 198 stage->point = draw_pipe_passthrough_point; 199 stage->point( stage, header ); 200 } 201} 202 203static void cull_first_line( struct draw_stage *stage, 204 struct prim_header *header ) 205{ 206 const unsigned num_written_culldistances = 207 draw_current_shader_num_written_culldistances(stage->draw); 208 209 if (num_written_culldistances) { 210 stage->line = cull_line; 211 stage->line( stage, header ); 212 } else { 213 stage->line = draw_pipe_passthrough_line; 214 stage->line( stage, header ); 215 } 216} 217 218static void cull_first_tri( struct draw_stage *stage, 219 struct prim_header *header ) 220{ 221 struct cull_stage *cull = cull_stage(stage); 222 223 cull->cull_face = stage->draw->rasterizer->cull_face; 224 cull->front_ccw = stage->draw->rasterizer->front_ccw; 225 226 stage->tri = cull_tri; 227 stage->tri( stage, header ); 228} 229 230 231static void cull_flush( struct draw_stage *stage, unsigned flags ) 232{ 233 stage->point = cull_first_point; 234 stage->line = cull_first_line; 235 stage->tri = cull_first_tri; 236 stage->next->flush( stage->next, flags ); 237} 238 239 240static void cull_reset_stipple_counter( struct draw_stage *stage ) 241{ 242 stage->next->reset_stipple_counter( stage->next ); 243} 244 245 246static void cull_destroy( struct draw_stage *stage ) 247{ 248 draw_free_temp_verts( stage ); 249 FREE( stage ); 250} 251 252 253/** 254 * Create a new polygon culling stage. 255 */ 256struct draw_stage *draw_cull_stage( struct draw_context *draw ) 257{ 258 struct cull_stage *cull = CALLOC_STRUCT(cull_stage); 259 if (!cull) 260 goto fail; 261 262 cull->stage.draw = draw; 263 cull->stage.name = "cull"; 264 cull->stage.next = NULL; 265 cull->stage.point = cull_first_point; 266 cull->stage.line = cull_first_line; 267 cull->stage.tri = cull_first_tri; 268 cull->stage.flush = cull_flush; 269 cull->stage.reset_stipple_counter = cull_reset_stipple_counter; 270 cull->stage.destroy = cull_destroy; 271 272 if (!draw_alloc_temp_verts( &cull->stage, 0 )) 273 goto fail; 274 275 return &cull->stage; 276 277fail: 278 if (cull) 279 cull->stage.destroy( &cull->stage ); 280 281 return NULL; 282} 283