/**

  * $Id$

  *

  * PVR2 renderer routines for depth sorted polygons

  *

  * Copyright (c) 2005 Nathan Keynes.

  *

  * This program is free software; you can redistribute it and/or modify

  * it under the terms of the GNU General Public License as published by

  * the Free Software Foundation; either version 2 of the License, or

  * (at your option) any later version.

  *

  * This program is distributed in the hope that it will be useful,

  * but WITHOUT ANY WARRANTY; without even the implied warranty of

  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

  * GNU General Public License for more details.

  */

 #include <sys/time.h>

 #include <string.h>

 #include <assert.h>

 #include "pvr2/pvr2.h"

 #include "pvr2/scene.h"

 #include "asic.h"

 #define MIN3( a,b,c ) ((a) < (b) ? ( (a) < (c) ? (a) : (c) ) : ((b) < (c) ? (b) : (c)) )

 #define MAX3( a,b,c ) ((a) > (b) ? ( (a) > (c) ? (a) : (c) ) : ((b) > (c) ? (b) : (c)) )

 #define EPSILON 0.0001

 struct sort_triangle {

     struct polygon_struct *poly;

     int triangle_num; // triangle number in the poly, from 0

     /* plane equation */

     float mx, my, mz, d;

     float bounds[6]; /* x1,x2,y1,y2,z1,z2 */

 };

 #define SENTINEL 0xDEADBEEF

 /**

  * Count the number of triangles in the list starting at the given 

  * pvr memory address.

  */

 static int sort_count_triangles( pvraddr_t tile_entry ) {

     uint32_t *tile_list = (uint32_t *)(video_base+tile_entry);

     int count = 0;

     while(1) {

         uint32_t entry = *tile_list++;

         if( entry >> 28 == 0x0F ) {

             break;

         } else if( entry >> 28 == 0x0E ) {

             tile_list = (uint32_t *)(video_base+(entry&0x007FFFFF));

         } else if( entry >> 29 == 0x04 ) { /* Triangle array */

             count += ((entry >> 25) & 0x0F)+1;

         } else if( entry >> 29 == 0x05 ) { /* Quad array */

             count += ((((entry >> 25) & 0x0F)+1)<<1);

         } else { /* Polygon */

             int i;

             for( i=0; i<6; i++ ) {

                 if( entry & (0x40000000>>i) ) {

                     count++;

                 }

             }

         }

     }

     return count;

 }

 static void sort_add_triangle( struct sort_triangle *triangle, struct polygon_struct *poly, int index )

 {

     struct vertex_struct *vertexes = &pvr2_scene.vertex_array[poly->vertex_index+index];

     triangle->poly = poly;

     triangle->triangle_num = index;

     /* Compute triangle bounding-box */

     triangle->bounds[0] = MIN3(vertexes[0].x,vertexes[1].x,vertexes[2].x);

     triangle->bounds[1] = MAX3(vertexes[0].x,vertexes[1].x,vertexes[2].x);

     triangle->bounds[2] = MIN3(vertexes[0].y,vertexes[1].y,vertexes[2].y);

     triangle->bounds[3] = MAX3(vertexes[0].y,vertexes[1].y,vertexes[2].y);

     triangle->bounds[4] = MIN3(vertexes[0].z,vertexes[1].z,vertexes[2].z);

     triangle->bounds[5] = MAX3(vertexes[0].z,vertexes[1].z,vertexes[2].z);

     /* Compute plane equation */

     float sx = vertexes[1].x - vertexes[0].x;

     float sy = vertexes[1].y - vertexes[0].y;

     float sz = vertexes[1].z - vertexes[0].z;

     float tx = vertexes[2].x - vertexes[0].x;

     float ty = vertexes[2].y - vertexes[0].y;

     float tz = vertexes[2].z - vertexes[0].z;

     triangle->mx = sy*tz - sz*ty;

     triangle->my = sz*tx - sx*tz;

     triangle->mz = sx*ty - sy*tx;

     triangle->d = -vertexes[0].x*triangle->mx - 

                   vertexes[0].y*triangle->my - 

                   vertexes[0].z*triangle->mz;

 }

 /**

  * Extract a triangle list from the tile (basically indexes into the polygon list, plus

  * computing maxz while we go through it

  */

 int sort_extract_triangles( pvraddr_t tile_entry, struct sort_triangle *triangles )

 {

     uint32_t *tile_list = (uint32_t *)(video_base+tile_entry);

     int strip_count;

     struct polygon_struct *poly;

     int count = 0, i;

     while(1) {

         uint32_t entry = *tile_list++;

         switch( entry >> 28 ) {

         case 0x0F:

             return count; // End-of-list

         case 0x0E:

             tile_list = (uint32_t *)(video_base + (entry&0x007FFFFF));

             break;

         case 0x08: case 0x09: case 0x0A: case 0x0B:

             strip_count = ((entry >> 25) & 0x0F)+1;

             poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];

             while( strip_count > 0 ) {

                 assert( poly != NULL );

                 for( i=0; i<poly->vertex_count-2; i++ ) {

                     sort_add_triangle( &triangles[count], poly, i );

                     count++;

                 }

                 poly = poly->next;

                 strip_count--;

             }

             break;

         default:

             if( entry & 0x7E000000 ) {

                 poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];

                 for( i=0; i<6; i++ ) {

                     if( entry & (0x40000000>>i) ) {

                         sort_add_triangle( &triangles[count], poly, i );

                         count++;

                     }

                 }

             }

         }

     }       

 }

 void sort_render_triangles( struct sort_triangle **triangles, int num_triangles )

 {

     int i;

     for( i=0; i<num_triangles; i++ ) {

         struct polygon_struct *poly = triangles[i]->poly;

         if( poly->tex_id != -1 ) {

             glBindTexture(GL_TEXTURE_2D, poly->tex_id);

         }

         render_set_context( poly->context, GL_GEQUAL );

         glDepthMask(GL_FALSE);

         /* Fix cull direction */

         if( triangles[i]->triangle_num & 1 ) {

             glCullFace(GL_FRONT);

         } else {

             glCullFace(GL_BACK);

         }

         glDrawArrays(GL_TRIANGLE_STRIP, poly->vertex_index + triangles[i]->triangle_num, 3 );

     }

 }

 static int sort_triangle_compare( const void *a, const void *b ) 

 {

     const struct sort_triangle *tri1 = a;

     const struct sort_triangle *tri2 = b;

     if( tri1->bounds[5] <= tri2->bounds[4] ) 

         return 1; /* tri1 is entirely under tri2 */

     else if( tri2->bounds[5] <= tri1->bounds[4] )

         return -1;  /* tri2 is entirely under tri1 */

     else if( tri1->bounds[1] <= tri2->bounds[0] ||

              tri2->bounds[1] <= tri1->bounds[0] ||

              tri1->bounds[3] <= tri2->bounds[2] ||

              tri2->bounds[3] <= tri1->bounds[2] )

         return 0; /* tri1 and tri2 don't actually overlap at all */

     else { 

         struct vertex_struct *tri1v = &pvr2_scene.vertex_array[tri1->poly->vertex_index + tri1->triangle_num];

         struct vertex_struct *tri2v = &pvr2_scene.vertex_array[tri2->poly->vertex_index + tri2->triangle_num];

         float v[3];

         int i;

         for( i=0; i<3; i++ ) {

             v[i] = tri1->mx * tri2v[i].x + tri1->my * tri2v[i].y + tri1->mz * tri2v[i].z + tri1->d;

             if( v[i] > -EPSILON && v[i] < EPSILON ) v[i] = 0;

         }

         if( v[0] == 0 && v[1] == 0 && v[2] == 0 ) {

             return 0; /* coplanar */

         }

         if( (v[0] >=0 && v[1] >= 0 && v[2] >= 0) ||

             (v[0] <= 0 && v[1] <= 0 && v[2] <= 0) ) {

             /* Tri is on one side of the plane. Pick an arbitrary point to determine which side */

             float t1z = -(tri1->mx * tri2v[0].x + tri1->my * tri2v[0].y + tri1->d) / tri1->mz;

             return tri2v[0].z - t1z;

         }

         /* If the above test failed, then tri2 intersects tri1's plane. This

          * doesn't necessarily mean the triangles intersect (although they may).

          * For now just return 0, and come back to this later as it's a fairly

          * uncommon case in practice. 

          */

         return 0;

     }

 }

 /**

  * This is pretty much a standard merge sort (Unfortunately can't depend on

  * the system to provide one. Note we can't use quicksort here - the sort

  * must be stable to preserve the order of coplanar triangles.

  */

 static void sort_triangles( struct sort_triangle **triangles, int num_triangles, struct sort_triangle **out )

 {

     if( num_triangles > 2 ) {

         int l = num_triangles>>1, r=num_triangles-l, i=0,j=0;

         struct sort_triangle *left[l];

         struct sort_triangle *right[r];

         sort_triangles( triangles, l, left );

         sort_triangles( triangles+l, r, right );

         /* Merge */

         while(1) {

             if( sort_triangle_compare(left[i], right[j]) <= 0 ) {

                 *out++ = left[i++];

                 if( i == l ) {

                     memcpy( out, &right[j], (r-j)*sizeof(struct sort_triangle *) );        

                     break;

                 }

             } else {

                 *out++ = right[j++];

                 if( j == r ) {

                     memcpy( out, &left[i], (l-i)*sizeof(struct sort_triangle *) );

                     break;

                 }

             }

         }

     } else if( num_triangles == 2 ) {

         if( sort_triangle_compare(triangles[0], triangles[1]) <= 0 ) {

             out[0] = triangles[0];

             out[1] = triangles[1];

         } else {

             struct sort_triangle *tmp = triangles[0];

             out[0] = triangles[1];

             out[1] = tmp;

         }

     } else {

         out[0] = triangles[0];

     }

 } 

 void render_autosort_tile( pvraddr_t tile_entry, int render_mode ) 

 {

     int num_triangles = sort_count_triangles(tile_entry);

     if( num_triangles == 0 ) {

         return; /* nothing to do */

     } else if( num_triangles == 1 ) { /* Triangle can hardly overlap with itself */

         gl_render_tilelist(tile_entry, GL_GEQUAL);

     } else { /* Ooh boy here we go... */

         int i;

         struct sort_triangle triangles[num_triangles+1];

         struct sort_triangle *triangle_order[num_triangles+1];

         triangles[num_triangles].poly = (void *)SENTINEL;

         for( i=0; i<num_triangles; i++ ) {

             triangle_order[i] = &triangles[i];

         }

         int extracted_triangles = sort_extract_triangles(tile_entry, triangles);

         assert( extracted_triangles == num_triangles );

         sort_triangles( triangle_order, num_triangles, triangle_order );

         sort_render_triangles(triangle_order, num_triangles);

         glCullFace(GL_BACK);

         assert( triangles[num_triangles].poly == (void *)SENTINEL );

     }

 }