draw: implement distance culling

Works similarly to clip distance. If the cull distance is negative
for all vertices against a specific plane then the primitive
is culled.

Signed-off-by: Zack Rusin <[email protected]>
Reviewed-by: Jose Fonseca <[email protected]>
Reviewed-by: Brian Paul <[email protected]>
Reviewed-by: Roland Scheidegger <[email protected]>

8 files changed, 198 insertions, 31 deletions

diff --git a/src/gallium/auxiliary/draw/draw_context.c b/src/gallium/auxiliary/draw/draw_context.c
index 81b3068553d..0dbddb45111 100644
--- a/src/gallium/auxiliary/draw/draw_context.c
+++ b/src/gallium/auxiliary/draw/draw_context.c
@@ -752,6 +752,23 @@ draw_current_shader_num_written_clipdistances(const struct draw_context *draw)
    return draw->vs.vertex_shader->info.num_written_clipdistance;
 }
 
+
+uint
+draw_current_shader_culldistance_output(const struct draw_context *draw, int index)
+{
+   if (draw->gs.geometry_shader)
+      return draw->gs.geometry_shader->culldistance_output[index];
+   return draw->vs.vertex_shader->culldistance_output[index];
+}
+
+uint
+draw_current_shader_num_written_culldistances(const struct draw_context *draw)
+{
+   if (draw->gs.geometry_shader)
+      return draw->gs.geometry_shader->info.num_written_culldistance;
+   return draw->vs.vertex_shader->info.num_written_culldistance;
+}
+
 /**
  * Return a pointer/handle for a driver/CSO rasterizer object which
  * disabled culling, stippling, unfilled tris, etc.
diff --git a/src/gallium/auxiliary/draw/draw_gs.c b/src/gallium/auxiliary/draw/draw_gs.c
index 74c6279d648..b762dd6cb57 100644
--- a/src/gallium/auxiliary/draw/draw_gs.c
+++ b/src/gallium/auxiliary/draw/draw_gs.c
@@ -797,6 +797,10 @@ draw_create_geometry_shader(struct draw_context *draw,
          else
             gs->clipdistance_output[1] = i;
       }
+      if (gs->info.output_semantic_name[i] == TGSI_SEMANTIC_CULLDIST) {
+         debug_assert(gs->info.output_semantic_index[i] < Elements(gs->culldistance_output));
+         gs->culldistance_output[gs->info.output_semantic_index[i]] = i;
+      }
    }
 
    gs->machine = draw->gs.tgsi.machine;
diff --git a/src/gallium/auxiliary/draw/draw_gs.h b/src/gallium/auxiliary/draw/draw_gs.h
index 543b32d4202..05d666d752d 100644
--- a/src/gallium/auxiliary/draw/draw_gs.h
+++ b/src/gallium/auxiliary/draw/draw_gs.h
@@ -68,6 +68,7 @@ struct draw_geometry_shader {
    unsigned position_output;
    unsigned viewport_index_output;
    unsigned clipdistance_output[2];
+   unsigned culldistance_output[2];
 
    unsigned max_output_vertices;
    unsigned primitive_boundary;
diff --git a/src/gallium/auxiliary/draw/draw_pipe_cull.c b/src/gallium/auxiliary/draw/draw_pipe_cull.c
index 2f4d01d23ab..50a25e357b7 100644
--- a/src/gallium/auxiliary/draw/draw_pipe_cull.c
+++ b/src/gallium/auxiliary/draw/draw_pipe_cull.c
@@ -33,6 +33,7 @@
  */
 
 
+#include "util/u_math.h"
 #include "util/u_memory.h"
 #include "pipe/p_defines.h"
 #include "draw_pipe.h"
@@ -50,42 +51,171 @@ static INLINE struct cull_stage *cull_stage( struct draw_stage *stage )
    return (struct cull_stage *)stage;
 }
 
+static INLINE
+boolean cull_distance_is_out(float dist)
+{
+   return (dist < 0) || util_is_inf_or_nan(dist);
+}
+
+/*
+ * If the shader writes the culldistance then we can
+ * perform distance based culling. Distance based
+ * culling doesn't require a face and can be performed
+ * on primitives without faces (e.g. points and lines)
+ */
+static void cull_point( struct draw_stage *stage,
+                        struct prim_header *header )
+{
+   const unsigned num_written_culldistances =
+      draw_current_shader_num_written_culldistances(stage->draw);
+
+   if (num_written_culldistances) {
+      unsigned i;
+      boolean culled = FALSE;
+      for (i = 0; i < num_written_culldistances; ++i) {
+         unsigned cull_idx = i / 4;
+         unsigned out_idx =
+            draw_current_shader_culldistance_output(stage->draw, cull_idx);
+         unsigned idx = i % 4;
+         float cull1 = header->v[0]->data[out_idx][idx];
+         boolean vert1_out = cull_distance_is_out(cull1);
+         if (vert1_out)
+            culled = TRUE;
+      }
+      if (!culled)
+         stage->next->point( stage->next, header );
+   }
+}
 
+/*
+ * If the shader writes the culldistance then we can
+ * perform distance based culling. Distance based
+ * culling doesn't require a face and can be performed
+ * on primitives without faces (e.g. points and lines)
+ */
+static void cull_line( struct draw_stage *stage,
+		      struct prim_header *header )
+{
+   const unsigned num_written_culldistances =
+      draw_current_shader_num_written_culldistances(stage->draw);
+
+   if (num_written_culldistances) {
+      unsigned i;
+      boolean culled = FALSE;
+      for (i = 0; i < num_written_culldistances; ++i) {
+         unsigned cull_idx = i / 4;
+         unsigned out_idx =
+            draw_current_shader_culldistance_output(stage->draw, cull_idx);
+         unsigned idx = i % 4;
+         float cull1 = header->v[0]->data[out_idx][idx];
+         float cull2 = header->v[1]->data[out_idx][idx];
+         boolean vert1_out = cull_distance_is_out(cull1);
+         boolean vert2_out = cull_distance_is_out(cull2);
+         if (vert1_out && vert2_out)
+            culled = TRUE;
+      }
+      if (!culled)
+         stage->next->line( stage->next, header );
+   }
+}
+
+/*
+ * Triangles can be culled either using the cull distance
+ * shader outputs or the regular face culling. If required
+ * this function performs both, starting with distance culling.
+ */
 static void cull_tri( struct draw_stage *stage,
 		      struct prim_header *header )
 {
-   const unsigned pos = draw_current_shader_position_output(stage->draw);
-
-   /* Window coords: */
-   const float *v0 = header->v[0]->data[pos];
-   const float *v1 = header->v[1]->data[pos];
-   const float *v2 = header->v[2]->data[pos];
-
-   /* edge vectors: e = v0 - v2, f = v1 - v2 */
-   const float ex = v0[0] - v2[0];
-   const float ey = v0[1] - v2[1];
-   const float fx = v1[0] - v2[0];
-   const float fy = v1[1] - v2[1];
+   const unsigned num_written_culldistances =
+      draw_current_shader_num_written_culldistances(stage->draw);
+
+   /* Do the distance culling */
+   if (num_written_culldistances) {
+      unsigned i;
+      boolean culled = FALSE;
+      for (i = 0; i < num_written_culldistances; ++i) {
+         unsigned cull_idx = i / 4;
+         unsigned out_idx =
+            draw_current_shader_culldistance_output(stage->draw, cull_idx);
+         unsigned idx = i % 4;
+         float cull1 = header->v[0]->data[out_idx][idx];
+         float cull2 = header->v[1]->data[out_idx][idx];
+         float cull3 = header->v[2]->data[out_idx][idx];
+         boolean vert1_out = cull_distance_is_out(cull1);
+         boolean vert2_out = cull_distance_is_out(cull2);
+         boolean vert3_out = cull_distance_is_out(cull3);
+         if (vert1_out && vert2_out && vert3_out)
+            culled = TRUE;
+      }
+      if (!culled)
+         stage->next->tri( stage->next, header );
+   }
+
+   /* Do the regular face culling */
+   {
+      const unsigned pos = draw_current_shader_position_output(stage->draw);
+      /* Window coords: */
+      const float *v0 = header->v[0]->data[pos];
+      const float *v1 = header->v[1]->data[pos];
+      const float *v2 = header->v[2]->data[pos];
+
+      /* edge vectors: e = v0 - v2, f = v1 - v2 */
+      const float ex = v0[0] - v2[0];
+      const float ey = v0[1] - v2[1];
+      const float fx = v1[0] - v2[0];
+      const float fy = v1[1] - v2[1];
+
    
-   /* det = cross(e,f).z */
-   header->det = ex * fy - ey * fx;
-
-   if (header->det != 0) {
-      /* if det < 0 then Z points toward the camera and the triangle is 
-       * counter-clockwise winding.
-       */
-      unsigned ccw = (header->det < 0);
-      unsigned face = ((ccw == cull_stage(stage)->front_ccw) ?
-                       PIPE_FACE_FRONT :
-                       PIPE_FACE_BACK);
-
-      if ((face & cull_stage(stage)->cull_face) == 0) {
-         /* triangle is not culled, pass to next stage */
-	 stage->next->tri( stage->next, header );
+      /* det = cross(e,f).z */
+      header->det = ex * fy - ey * fx;
+
+      if (header->det != 0) {
+         /* if det < 0 then Z points toward the camera and the triangle is
+          * counter-clockwise winding.
+          */
+         unsigned ccw = (header->det < 0);
+         unsigned face = ((ccw == cull_stage(stage)->front_ccw) ?
+                          PIPE_FACE_FRONT :
+                          PIPE_FACE_BACK);
+
+         if ((face & cull_stage(stage)->cull_face) == 0) {
+            /* triangle is not culled, pass to next stage */
+            stage->next->tri( stage->next, header );
+         }
       }
    }
 }
 
+static void cull_first_point( struct draw_stage *stage,
+                              struct prim_header *header )
+{
+   const unsigned num_written_culldistances =
+      draw_current_shader_num_written_culldistances(stage->draw);
+
+   if (num_written_culldistances) {
+      stage->point = cull_point;
+      stage->point( stage, header );
+   } else {
+      stage->point = draw_pipe_passthrough_point;
+      stage->point( stage, header );
+   }
+}
+
+static void cull_first_line( struct draw_stage *stage,
+			    struct prim_header *header )
+{
+   const unsigned num_written_culldistances =
+      draw_current_shader_num_written_culldistances(stage->draw);
+
+   if (num_written_culldistances) {
+      stage->line = cull_line;
+      stage->line( stage, header );
+   } else {
+      stage->line = draw_pipe_passthrough_line;
+      stage->line( stage, header );
+   }
+}
 
 static void cull_first_tri( struct draw_stage *stage, 
 			    struct prim_header *header )
@@ -102,6 +232,8 @@ static void cull_first_tri( struct draw_stage *stage,
 
 static void cull_flush( struct draw_stage *stage, unsigned flags )
 {
+   stage->point = cull_first_point;
+   stage->line = cull_first_line;
    stage->tri = cull_first_tri;
    stage->next->flush( stage->next, flags );
 }
@@ -132,8 +264,8 @@ struct draw_stage *draw_cull_stage( struct draw_context *draw )
    cull->stage.draw = draw;
    cull->stage.name = "cull";
    cull->stage.next = NULL;
-   cull->stage.point = draw_pipe_passthrough_point;
-   cull->stage.line = draw_pipe_passthrough_line;
+   cull->stage.point = cull_first_point;
+   cull->stage.line = cull_first_line;
    cull->stage.tri = cull_first_tri;
    cull->stage.flush = cull_flush;
    cull->stage.reset_stipple_counter = cull_reset_stipple_counter;
diff --git a/src/gallium/auxiliary/draw/draw_pipe_validate.c b/src/gallium/auxiliary/draw/draw_pipe_validate.c
index 4b0ed148129..2dbb95c82ab 100644
--- a/src/gallium/auxiliary/draw/draw_pipe_validate.c
+++ b/src/gallium/auxiliary/draw/draw_pipe_validate.c
@@ -93,6 +93,9 @@ draw_need_pipeline(const struct draw_context *draw,
       /* AA lines */
       if (rasterizer->line_smooth && draw->pipeline.aaline)
          return TRUE;
+
+      if (draw_current_shader_num_written_culldistances(draw))
+         return TRUE;
    }
 
    if (points(prim))
@@ -136,6 +139,9 @@ draw_need_pipeline(const struct draw_context *draw,
       /* two-side lighting */
       if (rasterizer->light_twoside)
          return TRUE;
+
+      if (draw_current_shader_num_written_culldistances(draw))
+         return TRUE;
    }
 
    /* polygon cull - this is difficult - hardware can cull just fine
@@ -145,7 +151,7 @@ draw_need_pipeline(const struct draw_context *draw,
     *
    if (rasterizer->cull_mode)
       return TRUE;
-    */
+   */
 
    return FALSE;
 }
@@ -260,7 +266,8 @@ static struct draw_stage *validate_pipeline( struct draw_stage *stage )
     * to less work emitting vertices, smaller vertex buffers, etc.
     * It's difficult to say whether this will be true in general.
     */
-   if (need_det || rast->cull_face != PIPE_FACE_NONE) {
+   if (need_det || rast->cull_face != PIPE_FACE_NONE ||
+       draw_current_shader_num_written_culldistances(draw)) {
       draw->pipeline.cull->next = next;
       next = draw->pipeline.cull;
    }
diff --git a/src/gallium/auxiliary/draw/draw_private.h b/src/gallium/auxiliary/draw/draw_private.h
index e08173580b7..fd52c2d6b4c 100644
--- a/src/gallium/auxiliary/draw/draw_private.h
+++ b/src/gallium/auxiliary/draw/draw_private.h
@@ -390,6 +390,8 @@ uint draw_current_shader_viewport_index_output(const struct draw_context *draw);
 uint draw_current_shader_clipvertex_output(const struct draw_context *draw);
 uint draw_current_shader_clipdistance_output(const struct draw_context *draw, int index);
 uint draw_current_shader_num_written_clipdistances(const struct draw_context *draw);
+uint draw_current_shader_culldistance_output(const struct draw_context *draw, int index);
+uint draw_current_shader_num_written_culldistances(const struct draw_context *draw);
 int draw_alloc_extra_vertex_attrib(struct draw_context *draw,
                                    uint semantic_name, uint semantic_index);
 void draw_remove_extra_vertex_attribs(struct draw_context *draw);
diff --git a/src/gallium/auxiliary/draw/draw_vs.c b/src/gallium/auxiliary/draw/draw_vs.c
index 95f678ab2cd..a0bebcc7666 100644
--- a/src/gallium/auxiliary/draw/draw_vs.c
+++ b/src/gallium/auxiliary/draw/draw_vs.c
@@ -90,6 +90,9 @@ draw_create_vertex_shader(struct draw_context *draw,
                vs->clipdistance_output[0] = i;
             else
                vs->clipdistance_output[1] = i;
+         } else if (vs->info.output_semantic_name[i] == TGSI_SEMANTIC_CULLDIST) {
+            debug_assert(vs->info.output_semantic_index[i] < Elements(vs->culldistance_output));
+            vs->culldistance_output[vs->info.output_semantic_index[i]] = i;
          }
       }
       if (!found_clipvertex)
diff --git a/src/gallium/auxiliary/draw/draw_vs.h b/src/gallium/auxiliary/draw/draw_vs.h
index 798b004ebd4..7635abaade5 100644
--- a/src/gallium/auxiliary/draw/draw_vs.h
+++ b/src/gallium/auxiliary/draw/draw_vs.h
@@ -113,6 +113,7 @@ struct draw_vertex_shader {
    unsigned edgeflag_output;
    unsigned clipvertex_output;
    unsigned clipdistance_output[2];
+   unsigned culldistance_output[2];
    /* Extracted from shader:
     */
    const float (*immediates)[4];