1.1 --- a/src/pvr2/rendsort.c	Tue Oct 14 08:44:37 2008 +0000
     1.2 +++ b/src/pvr2/rendsort.c	Thu Oct 16 04:46:33 2008 +0000
     1.3 @@ -24,11 +24,14 @@
     1.4  
     1.5  #define MIN3( a,b,c ) ((a) < (b) ? ( (a) < (c) ? (a) : (c) ) : ((b) < (c) ? (b) : (c)) )
     1.6  #define MAX3( a,b,c ) ((a) > (b) ? ( (a) > (c) ? (a) : (c) ) : ((b) > (c) ? (b) : (c)) )
     1.7 +#define EPSILON 0.0001
     1.8  
     1.9  struct sort_triangle {
    1.10      struct polygon_struct *poly;
    1.11      int triangle_num; // triangle number in the poly, from 0
    1.12 -    float maxz;
    1.13 +    /* plane equation */
    1.14 +    float mx, my, mz, d;
    1.15 +    float bounds[6]; /* x1,x2,y1,y2,z1,z2 */
    1.16  };
    1.17  
    1.18  #define SENTINEL 0xDEADBEEF
    1.19 @@ -37,7 +40,7 @@
    1.20   * Count the number of triangles in the list starting at the given 
    1.21   * pvr memory address.
    1.22   */
    1.23 -int sort_count_triangles( pvraddr_t tile_entry ) {
    1.24 +static int sort_count_triangles( pvraddr_t tile_entry ) {
    1.25      uint32_t *tile_list = (uint32_t *)(video_base+tile_entry);
    1.26      int count = 0;
    1.27      while(1) {
    1.28 @@ -62,6 +65,35 @@
    1.29      return count;
    1.30  }
    1.31  
    1.32 +static void sort_add_triangle( struct sort_triangle *triangle, struct polygon_struct *poly, int index )
    1.33 +{
    1.34 +    struct vertex_struct *vertexes = &pvr2_scene.vertex_array[poly->vertex_index+index];
    1.35 +    triangle->poly = poly;
    1.36 +    triangle->triangle_num = index;
    1.37 +
    1.38 +    /* Compute triangle bounding-box */
    1.39 +    triangle->bounds[0] = MIN3(vertexes[0].x,vertexes[1].x,vertexes[2].x);
    1.40 +    triangle->bounds[1] = MAX3(vertexes[0].x,vertexes[1].x,vertexes[2].x);
    1.41 +    triangle->bounds[2] = MIN3(vertexes[0].y,vertexes[1].y,vertexes[2].y);
    1.42 +    triangle->bounds[3] = MAX3(vertexes[0].y,vertexes[1].y,vertexes[2].y);
    1.43 +    triangle->bounds[4] = MIN3(vertexes[0].z,vertexes[1].z,vertexes[2].z);
    1.44 +    triangle->bounds[5] = MAX3(vertexes[0].z,vertexes[1].z,vertexes[2].z);
    1.45 +
    1.46 +    /* Compute plane equation */
    1.47 +    float sx = vertexes[1].x - vertexes[0].x;
    1.48 +    float sy = vertexes[1].y - vertexes[0].y;
    1.49 +    float sz = vertexes[1].z - vertexes[0].z;
    1.50 +    float tx = vertexes[2].x - vertexes[0].x;
    1.51 +    float ty = vertexes[2].y - vertexes[0].y;
    1.52 +    float tz = vertexes[2].z - vertexes[0].z;
    1.53 +    triangle->mx = sy*tz - sz*ty;
    1.54 +    triangle->my = sz*tx - sx*tz;
    1.55 +    triangle->mz = sx*ty - sy*tx;
    1.56 +    triangle->d = -vertexes[0].x*triangle->mx - 
    1.57 +                  vertexes[0].y*triangle->my - 
    1.58 +                  vertexes[0].z*triangle->mz;
    1.59 +}
    1.60 +
    1.61  /**
    1.62   * Extract a triangle list from the tile (basically indexes into the polygon list, plus
    1.63   * computing maxz while we go through it
    1.64 @@ -86,12 +118,8 @@
    1.65              poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
    1.66              while( strip_count > 0 ) {
    1.67                  assert( poly != NULL );
    1.68 -                for( i=0; i<poly->vertex_count-2; i++ ) { 
    1.69 -                    triangles[count].poly = poly;
    1.70 -                    triangles[count].triangle_num = i;
    1.71 -                    triangles[count].maxz = MAX3( pvr2_scene.vertex_array[poly->vertex_index+i].z,
    1.72 -                            pvr2_scene.vertex_array[poly->vertex_index+i+1].z,
    1.73 -                            pvr2_scene.vertex_array[poly->vertex_index+i+2].z );
    1.74 +                for( i=0; i<poly->vertex_count-2; i++ ) {
    1.75 +                    sort_add_triangle( &triangles[count], poly, i );
    1.76                      count++;
    1.77                  }
    1.78                  poly = poly->next;
    1.79 @@ -103,11 +131,7 @@
    1.80                  poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
    1.81                  for( i=0; i<6; i++ ) {
    1.82                      if( entry & (0x40000000>>i) ) {
    1.83 -                        triangles[count].poly = poly;
    1.84 -                        triangles[count].triangle_num = i;
    1.85 -                        triangles[count].maxz = MAX3( pvr2_scene.vertex_array[poly->vertex_index+i].z,
    1.86 -                                pvr2_scene.vertex_array[poly->vertex_index+i+1].z,
    1.87 -                                pvr2_scene.vertex_array[poly->vertex_index+i+2].z );
    1.88 +                        sort_add_triangle( &triangles[count], poly, i );
    1.89                          count++;
    1.90                      }
    1.91                  }
    1.92 @@ -117,38 +141,110 @@
    1.93  
    1.94  }
    1.95  
    1.96 -void sort_render_triangles( struct sort_triangle *triangles, int num_triangles,
    1.97 -                            int render_mode )
    1.98 +void sort_render_triangles( struct sort_triangle **triangles, int num_triangles )
    1.99  {
   1.100      int i;
   1.101      for( i=0; i<num_triangles; i++ ) {
   1.102 -        struct polygon_struct *poly = triangles[i].poly;
   1.103 +        struct polygon_struct *poly = triangles[i]->poly;
   1.104          if( poly->tex_id != -1 ) {
   1.105              glBindTexture(GL_TEXTURE_2D, poly->tex_id);
   1.106          }
   1.107          render_set_context( poly->context, GL_GEQUAL );
   1.108          glDepthMask(GL_FALSE);
   1.109          /* Fix cull direction */
   1.110 -        if( triangles[i].triangle_num & 1 ) {
   1.111 +        if( triangles[i]->triangle_num & 1 ) {
   1.112              glCullFace(GL_FRONT);
   1.113          } else {
   1.114              glCullFace(GL_BACK);
   1.115          }
   1.116  
   1.117 -        glDrawArrays(GL_TRIANGLE_STRIP, poly->vertex_index + triangles[i].triangle_num, 3 );
   1.118 +        glDrawArrays(GL_TRIANGLE_STRIP, poly->vertex_index + triangles[i]->triangle_num, 3 );
   1.119      }
   1.120  }
   1.121  
   1.122 -int compare_triangles( const void *a, const void *b ) 
   1.123 +static int sort_triangle_compare( const void *a, const void *b ) 
   1.124  {
   1.125      const struct sort_triangle *tri1 = a;
   1.126      const struct sort_triangle *tri2 = b;
   1.127 -    return tri2->maxz - tri1->maxz;
   1.128 +    if( tri1->bounds[5] <= tri2->bounds[4] ) 
   1.129 +        return 1; /* tri1 is entirely under tri2 */
   1.130 +    else if( tri2->bounds[5] <= tri1->bounds[4] )
   1.131 +        return -1;  /* tri2 is entirely under tri1 */
   1.132 +    else if( tri1->bounds[1] <= tri2->bounds[0] ||
   1.133 +             tri2->bounds[1] <= tri1->bounds[0] ||
   1.134 +             tri1->bounds[3] <= tri2->bounds[2] ||
   1.135 +             tri2->bounds[3] <= tri1->bounds[2] )
   1.136 +        return 0; /* tri1 and tri2 don't actually overlap at all */
   1.137 +    else { 
   1.138 +        struct vertex_struct *tri1v = &pvr2_scene.vertex_array[tri1->poly->vertex_index + tri1->triangle_num];
   1.139 +        struct vertex_struct *tri2v = &pvr2_scene.vertex_array[tri2->poly->vertex_index + tri2->triangle_num];
   1.140 +        float v[3];
   1.141 +        int i;
   1.142 +        for( i=0; i<3; i++ ) {
   1.143 +            v[i] = tri1->mx * tri2v[i].x + tri1->my * tri2v[i].y + tri1->mz * tri2v[i].z + tri1->d;
   1.144 +            if( v[i] > -EPSILON && v[i] < EPSILON ) v[i] = 0;
   1.145 +        }
   1.146 +        if( v[0] == 0 && v[1] == 0 && v[2] == 0 ) {
   1.147 +            return 0; /* coplanar */
   1.148 +        }
   1.149 +        if( (v[0] >=0 && v[1] >= 0 && v[2] >= 0) ||
   1.150 +            (v[0] <= 0 && v[1] <= 0 && v[2] <= 0) ) {
   1.151 +            /* Tri is on one side of the plane. Pick an arbitrary point to determine which side */
   1.152 +            float t1z = -(tri1->mx * tri2v[0].x + tri1->my * tri2v[0].y + tri1->d) / tri1->mz;
   1.153 +            return tri2v[0].z - t1z;
   1.154 +        }
   1.155 +        
   1.156 +        /* If the above test failed, then tri2 intersects tri1's plane. This
   1.157 +         * doesn't necessarily mean the triangles intersect (although they may).
   1.158 +         * For now just return 0, and come back to this later as it's a fairly
   1.159 +         * uncommon case in practice. 
   1.160 +         */
   1.161 +        return 0;
   1.162 +    }
   1.163  }
   1.164  
   1.165 -void sort_triangles( struct sort_triangle *triangles, int num_triangles )
   1.166 +/**
   1.167 + * This is pretty much a standard merge sort (Unfortunately can't depend on
   1.168 + * the system to provide one. Note we can't use quicksort here - the sort
   1.169 + * must be stable to preserve the order of coplanar triangles.
   1.170 + */
   1.171 +static void sort_triangles( struct sort_triangle **triangles, int num_triangles, struct sort_triangle **out )
   1.172  {
   1.173 -    qsort( triangles, num_triangles, sizeof(struct sort_triangle), compare_triangles );
   1.174 +    if( num_triangles > 2 ) {
   1.175 +        int l = num_triangles>>1, r=num_triangles-l, i=0,j=0;
   1.176 +        struct sort_triangle *left[l];
   1.177 +        struct sort_triangle *right[r];
   1.178 +        sort_triangles( triangles, l, left );
   1.179 +        sort_triangles( triangles+l, r, right );
   1.180 +        
   1.181 +        /* Merge */
   1.182 +        while(1) {
   1.183 +            if( sort_triangle_compare(left[i], right[j]) <= 0 ) {
   1.184 +                *out++ = left[i++];
   1.185 +                if( i == l ) {
   1.186 +                    memcpy( out, &right[j], (r-j)*sizeof(struct sort_triangle *) );        
   1.187 +                    break;
   1.188 +                }
   1.189 +            } else {
   1.190 +                *out++ = right[j++];
   1.191 +                if( j == r ) {
   1.192 +                    memcpy( out, &left[i], (l-i)*sizeof(struct sort_triangle *) );
   1.193 +                    break;
   1.194 +                }
   1.195 +            }
   1.196 +        }
   1.197 +    } else if( num_triangles == 2 ) {
   1.198 +        if( sort_triangle_compare(triangles[0], triangles[1]) <= 0 ) {
   1.199 +            out[0] = triangles[0];
   1.200 +            out[1] = triangles[1];
   1.201 +        } else {
   1.202 +            struct sort_triangle *tmp = triangles[0];
   1.203 +            out[0] = triangles[1];
   1.204 +            out[1] = tmp;
   1.205 +        }
   1.206 +    } else {
   1.207 +        out[0] = triangles[0];
   1.208 +    }
   1.209  } 
   1.210  
   1.211  void render_autosort_tile( pvraddr_t tile_entry, int render_mode ) 
   1.212 @@ -159,14 +255,17 @@
   1.213      } else if( num_triangles == 1 ) { /* Triangle can hardly overlap with itself */
   1.214          gl_render_tilelist(tile_entry, GL_LEQUAL);
   1.215      } else { /* Ooh boy here we go... */
   1.216 +        int i;
   1.217          struct sort_triangle triangles[num_triangles+1];
   1.218 -        // Reserve space for num_triangles / 2 * 4 vertexes (maximum possible number of
   1.219 -        // quad vertices)
   1.220 +        struct sort_triangle *triangle_order[num_triangles+1];
   1.221          triangles[num_triangles].poly = (void *)SENTINEL;
   1.222 +        for( i=0; i<num_triangles; i++ ) {
   1.223 +            triangle_order[i] = &triangles[i];
   1.224 +        }
   1.225          int extracted_triangles = sort_extract_triangles(tile_entry, triangles);
   1.226          assert( extracted_triangles == num_triangles );
   1.227 -        sort_triangles( triangles, num_triangles );
   1.228 -        sort_render_triangles(triangles, num_triangles, render_mode);
   1.229 +        sort_triangles( triangle_order, num_triangles, triangle_order );
   1.230 +        sort_render_triangles(triangle_order, num_triangles);
   1.231          glCullFace(GL_BACK);
   1.232          assert( triangles[num_triangles].poly == (void *)SENTINEL );
   1.233      }