/**************************************************************************
 * 
 * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas.
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sub license, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice (including the
 * next paragraph) shall be included in all copies or substantial portions
 * of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
 * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 * 
 **************************************************************************/

/**
 * \brief  Clipping stage
 *
 * \author  Keith Whitwell <keith@tungstengraphics.com>
 */


#include "pipe/p_util.h"
#include "draw_context.h"
#include "draw_private.h"


#ifndef IS_NEGATIVE
#define IS_NEGATIVE(X) ((X) < 0.0)
#endif

#ifndef DIFFERENT_SIGNS
#define DIFFERENT_SIGNS(x, y) ((x) * (y) <= 0.0F && (x) - (y) != 0.0F)
#endif

#ifndef MAX_CLIPPED_VERTICES
#define MAX_CLIPPED_VERTICES ((2 * (6 + PIPE_MAX_CLIP_PLANES))+1)
#endif


/** bitmask for the first view-frustum clip planes */
#define VIEWPLANE_MASK ((1 << 6) - 1)

/** bitmask for the user-defined clip planes */
#define USERPLANE_MASK (((1 << PIPE_MAX_CLIP_PLANES) - 1) << 6)



struct clipper {
   struct draw_stage stage;      /**< base class */

   float (*plane)[4];
};


/* This is a bit confusing:
 */
static INLINE struct clipper *clipper_stage( struct draw_stage *stage )
{
   return (struct clipper *)stage;
}


#define LINTERP(T, OUT, IN) ((OUT) + (T) * ((IN) - (OUT)))


/* All attributes are float[4], so this is easy:
 */
static void interp_attr( float *fdst,
			 float t,
			 const float *fin,
			 const float *fout )
{  
   fdst[0] = LINTERP( t, fout[0], fin[0] );
   fdst[1] = LINTERP( t, fout[1], fin[1] );
   fdst[2] = LINTERP( t, fout[2], fin[2] );
   fdst[3] = LINTERP( t, fout[3], fin[3] );
}




/* Interpolate between two vertices to produce a third.  
 */
static void interp( const struct clipper *clip,
		    struct vertex_header *dst,
		    float t,
		    const struct vertex_header *out, 
		    const struct vertex_header *in )
{
   const unsigned nr_attrs = clip->stage.draw->vertex_info.num_attribs;
   unsigned j;

   /* Vertex header.
    */
   {
      dst->clipmask = 0;
      dst->edgeflag = 0;
      dst->pad = 0;
   }

   /* Clip coordinates:  interpolate normally
    */
   {
      interp_attr(dst->clip, t, in->clip, out->clip);
   }

   /* Do the projective divide and insert window coordinates:
    */
   {
      const float *pos = dst->clip;
      const float *scale = clip->stage.draw->viewport.scale;
      const float *trans = clip->stage.draw->viewport.translate;
      const float oow = 1.0f / pos[3];

      dst->data[0][0] = pos[0] * oow * scale[0] + trans[0];
      dst->data[0][1] = pos[1] * oow * scale[1] + trans[1];
      dst->data[0][2] = pos[2] * oow * scale[2] + trans[2];
      dst->data[0][3] = oow;
   }

   /* Other attributes
    * Note: start at 1 to skip winpos (data[0]) since we just computed
    * it above.
    * Subtract two from nr_attrs since the first two attribs (always 
    * VF_ATTRIB_VERTEX_HEADER and VF_ATTRIB_CLIP_POS, see
    * draw_set_vertex_attributes()) are in the vertex_header struct,
    * not in the data[] array.
    */
   for (j = 1; j < nr_attrs - 2; j++) {
      interp_attr(dst->data[j], t, in->data[j], out->data[j]);
   }
}



static INLINE float dot4( const float *a,
			    const float *b )
{
   float result = (a[0]*b[0] +
		     a[1]*b[1] +
		     a[2]*b[2] +
		     a[3]*b[3]);

   return result;
}


#if 0   
static INLINE void do_tri( struct draw_stage *next,
			   struct prim_header *header )
{
   unsigned i;
   for (i = 0; i < 3; i++) {
      float *ndc = header->v[i]->data[0];
      _mesa_printf("ndc %f %f %f\n", ndc[0], ndc[1], ndc[2]);
      assert(ndc[0] >= -1 && ndc[0] <= 641);
      assert(ndc[1] >= 30 && ndc[1] <= 481);
   }
   _mesa_printf("\n");
   next->tri(next, header);
}
#endif


static void emit_poly( struct draw_stage *stage,
		       struct vertex_header **inlist,
		       unsigned n )
{
   struct prim_header header;
   unsigned i;

   for (i = 2; i < n; i++) {
      header.v[0] = inlist[0];
      header.v[1] = inlist[i-1];
      header.v[2] = inlist[i];
	
      {
	 unsigned tmp0 = header.v[0]->edgeflag;
	 unsigned tmp2 = header.v[2]->edgeflag;

	 if (i != 2)   header.v[0]->edgeflag = 0;
	 if (i != n-1) header.v[2]->edgeflag = 0;

	 stage->next->tri( stage->next, &header );

	 header.v[0]->edgeflag = tmp0;
	 header.v[2]->edgeflag = tmp2;
      }
   }
}


#if 0
static void emit_poly( struct draw_stage *stage )
{
   unsigned i;

   for (i = 2; i < n; i++) {
      header->v[0] = inlist[0];
      header->v[1] = inlist[i-1];
      header->v[2] = inlist[i];
	 
      stage->next->tri( stage->next, header );
   }
}
#endif


/* Clip a triangle against the viewport and user clip planes.
 */
static void
do_clip_tri( struct draw_stage *stage, 
	     struct prim_header *header,
	     unsigned clipmask )
{
   struct clipper *clipper = clipper_stage( stage );
   struct vertex_header *a[MAX_CLIPPED_VERTICES];
   struct vertex_header *b[MAX_CLIPPED_VERTICES];
   struct vertex_header **inlist = a;
   struct vertex_header **outlist = b;
   unsigned tmpnr = 0;
   unsigned n = 3;
   unsigned i;

   inlist[0] = header->v[0];
   inlist[1] = header->v[1];
   inlist[2] = header->v[2];

   clipmask &= ~CLIP_CULL_BIT;

   while (clipmask && n >= 3) {
      const unsigned plane_idx = ffs(clipmask)-1;
      const float *plane = clipper->plane[plane_idx];
      struct vertex_header *vert_prev = inlist[0];
      float dp_prev = dot4( vert_prev->clip, plane );
      unsigned outcount = 0;

      clipmask &= ~(1<<plane_idx);

      inlist[n] = inlist[0]; /* prevent rotation of vertices */

      for (i = 1; i <= n; i++) {
	 struct vertex_header *vert = inlist[i];

	 float dp = dot4( vert->clip, plane );

	 if (!IS_NEGATIVE(dp_prev)) {
	    outlist[outcount++] = vert_prev;
	 }

	 if (DIFFERENT_SIGNS(dp, dp_prev)) {
	    struct vertex_header *new_vert = clipper->stage.tmp[tmpnr++];
	    outlist[outcount++] = new_vert;

	    if (IS_NEGATIVE(dp)) {
	       /* Going out of bounds.  Avoid division by zero as we
		* know dp != dp_prev from DIFFERENT_SIGNS, above.
		*/
	       float t = dp / (dp - dp_prev);
	       interp( clipper, new_vert, t, vert, vert_prev );
	       
	       /* Force edgeflag true in this case:
		*/
	       new_vert->edgeflag = 1;
	    } else {
	       /* Coming back in.
		*/
	       float t = dp_prev / (dp_prev - dp);
	       interp( clipper, new_vert, t, vert_prev, vert );

	       /* Copy starting vert's edgeflag:
		*/
	       new_vert->edgeflag = vert_prev->edgeflag;
	    }
	 }

	 vert_prev = vert;
	 dp_prev = dp;
      }

      {
	 struct vertex_header **tmp = inlist;
	 inlist = outlist;
	 outlist = tmp;
	 n = outcount;
      }
   }

   /* Emit the polygon as triangles to the setup stage:
    */
   if (n >= 3)
      emit_poly( stage, inlist, n );
}


/* Clip a line against the viewport and user clip planes.
 */
static void
do_clip_line( struct draw_stage *stage,
	      struct prim_header *header,
	      unsigned clipmask )
{
   const struct clipper *clipper = clipper_stage( stage );
   struct vertex_header *v0 = header->v[0];
   struct vertex_header *v1 = header->v[1];
   const float *pos0 = v0->clip;
   const float *pos1 = v1->clip;
   float t0 = 0.0F;
   float t1 = 0.0F;
   struct prim_header newprim;

   clipmask &= ~CLIP_CULL_BIT;

   while (clipmask) {
      const unsigned plane_idx = ffs(clipmask)-1;
      const float *plane = clipper->plane[plane_idx];
      const float dp0 = dot4( pos0, plane );
      const float dp1 = dot4( pos1, plane );

      /* need this to handle user-clip planes properly */
      if (dp0 < 0.0F && dp1 < 0.0F)
         return;

      if (dp1 < 0.0F) {
	 float t = dp1 / (dp1 - dp0);
         t1 = MAX2(t1, t);
      } 

      if (dp0 < 0.0F) {
	 float t = dp0 / (dp0 - dp1);
         t0 = MAX2(t0, t);
      }

      if (t0 + t1 >= 1.0F)
	 return; /* discard */

      clipmask &= ~(1 << plane_idx);  /* turn off this plane's bit */
   }

   if (v0->clipmask) {
      interp( clipper, stage->tmp[0], t0, v0, v1 );
      newprim.v[0] = stage->tmp[0];
   }
   else {
      newprim.v[0] = v0;
   }

   if (v1->clipmask) {
      interp( clipper, stage->tmp[1], t1, v1, v0 );
      newprim.v[1] = stage->tmp[1];
   }
   else {
      newprim.v[1] = v1;
   }

   stage->next->line( stage->next, &newprim );
}


static void clip_begin( struct draw_stage *stage )
{
   /* sanity checks.  If these fail, review the clip/interp code! */
   assert(stage->draw->vertex_info.num_attribs >= 3);
   assert(stage->draw->vertex_info.slot_to_attrib[0] == TGSI_ATTRIB_VERTEX_HEADER);
   assert(stage->draw->vertex_info.slot_to_attrib[1] == TGSI_ATTRIB_CLIP_POS);

   stage->next->begin( stage->next );
}


static void
clip_point( struct draw_stage *stage, 
	    struct prim_header *header )
{
   if (header->v[0]->clipmask == 0) {
      stage->next->point( stage->next, header );
   }
   else if (header->v[0]->clipmask & USERPLANE_MASK) {
      /* test against user clip planes now */
      const struct clipper *clipper = clipper_stage( stage );
      uint i;
      for (i = 6; i < stage->draw->nr_planes; i++) {
         float dot = dot4(clipper->plane[i], header->v[0]->clip);
         if (dot < 0.0F)
            return; /* clipped! */
      }
      /* not clipped */
      stage->next->point( stage->next, header );
   }
}


static void
clip_line( struct draw_stage *stage,
	   struct prim_header *header )
{
   unsigned clipmask = (header->v[0]->clipmask | 
                        header->v[1]->clipmask);
   
   if (clipmask == 0) {
      /* no clipping needed */
      stage->next->line( stage->next, header );
   }
   else if (((header->v[0]->clipmask &
              header->v[1]->clipmask &
              VIEWPLANE_MASK) == 0) ||
            (clipmask & USERPLANE_MASK)) {
      /* About the above predicate: the clipmask bits for the view volume
       * exactly indicate whether the coordinate is inside or outside each
       * frustum plane.  However, the bits for user-defined planes are set
       * if the plane is enabled, and does not really indicate if the
       * coordinate is inside or outside the user-defined plane.
       *
       * To change this (so that the user-plane bits really indicate
       * inside/outside) we'd have to compute the dot products earlier
       * in the draw_prim.c code (see compute_clipmask()).
       * We will probably do that when we have support for user clip coord
       * in vertex shaders...
       */
      do_clip_line(stage, header, clipmask);
   }
   /* else, totally clipped */
}


static void
clip_tri( struct draw_stage *stage,
	  struct prim_header *header )
{
   unsigned clipmask = (header->v[0]->clipmask | 
                        header->v[1]->clipmask | 
                        header->v[2]->clipmask);
   
   if (clipmask == 0) {
      /* no clipping needed */
      stage->next->tri( stage->next, header );
   }
   else if (((header->v[0]->clipmask & 
              header->v[1]->clipmask & 
              header->v[2]->clipmask &
              VIEWPLANE_MASK) == 0) ||
            (clipmask & USERPLANE_MASK)) {
      do_clip_tri(stage, header, clipmask);
   }
}


static void clip_end( struct draw_stage *stage )
{
   stage->next->end( stage->next );
}


static void clip_reset_stipple_counter( struct draw_stage *stage )
{
   stage->next->reset_stipple_counter( stage->next );
}


/**
 * Allocate a new clipper stage.
 * \return pointer to new stage object
 */
struct draw_stage *draw_clip_stage( struct draw_context *draw )
{
   struct clipper *clipper = CALLOC_STRUCT(clipper);

   draw_alloc_tmps( &clipper->stage, MAX_CLIPPED_VERTICES );

   clipper->stage.draw = draw;
   clipper->stage.begin = clip_begin;
   clipper->stage.point = clip_point;
   clipper->stage.line = clip_line;
   clipper->stage.tri = clip_tri;
   clipper->stage.end = clip_end;
   clipper->stage.reset_stipple_counter = clip_reset_stipple_counter;

   clipper->plane = draw->plane;

   return &clipper->stage;
}