Search
lxdream.org :: lxdream/src/pvr2/rendsort.c
lxdream 0.9.1
released Jun 29
Download Now
filename src/pvr2/rendsort.c
changeset 1143:8ec0f1f990aa
prev1138:3bcb705a7ebc
next1154:5225c7c059ce
author nkeynes
date Fri Oct 29 07:52:45 2010 +1000 (11 years ago)
permissions -rw-r--r--
last change Fix triangle extraction when the tile entry is a triangle but the polygon is
actually a strip (lead to extracting too many triangles)
view annotate diff log raw
     1 /**
     2  * $Id$
     3  *
     4  * PVR2 renderer routines for depth sorted polygons
     5  *
     6  * Copyright (c) 2005 Nathan Keynes.
     7  *
     8  * This program is free software; you can redistribute it and/or modify
     9  * it under the terms of the GNU General Public License as published by
    10  * the Free Software Foundation; either version 2 of the License, or
    11  * (at your option) any later version.
    12  *
    13  * This program is distributed in the hope that it will be useful,
    14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
    15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    16  * GNU General Public License for more details.
    17  */
    18 #include <sys/time.h>
    19 #include <string.h>
    20 #include <assert.h>
    21 #include "pvr2/pvr2.h"
    22 #include "pvr2/scene.h"
    23 #include "asic.h"
    25 #define MIN3( a,b,c ) ((a) < (b) ? ( (a) < (c) ? (a) : (c) ) : ((b) < (c) ? (b) : (c)) )
    26 #define MAX3( a,b,c ) ((a) > (b) ? ( (a) > (c) ? (a) : (c) ) : ((b) > (c) ? (b) : (c)) )
    27 #define EPSILON 0.0001
    29 struct sort_triangle {
    30     struct polygon_struct *poly;
    31     int triangle_num; // triangle number in the poly, from 0
    32     /* plane equation */
    33     float mx, my, mz, d;
    34     float bounds[6]; /* x1,x2,y1,y2,z1,z2 */
    35 };
    37 #define SENTINEL 0xDEADBEEF
    39 /**
    40  * Count the number of triangles in the list starting at the given 
    41  * pvr memory address. This is an upper bound as it includes
    42  * triangles that have been culled out.
    43  */
    44 static int sort_count_triangles( pvraddr_t tile_entry ) {
    45     uint32_t *tile_list = (uint32_t *)(pvr2_main_ram+tile_entry);
    46     int count = 0;
    47     while(1) {
    48         uint32_t entry = *tile_list++;
    49         if( entry >> 28 == 0x0F ) {
    50             break;
    51         } else if( entry >> 28 == 0x0E ) {
    52             tile_list = (uint32_t *)(pvr2_main_ram+(entry&0x007FFFFF));
    53         } else if( entry >> 29 == 0x04 ) { /* Triangle array */
    54             count += ((entry >> 25) & 0x0F)+1;
    55         } else if( entry >> 29 == 0x05 ) { /* Quad array */
    56             count += ((((entry >> 25) & 0x0F)+1)<<1);
    57         } else { /* Polygon */
    58             struct polygon_struct *poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
    59             while( poly != NULL ) {
    60                 if( poly->vertex_count != 0 )
    61                     count += poly->vertex_count-2;
    62                 poly = poly->sub_next;
    63             }
    64         }
    65     }
    66     return count;
    67 }
    69 static void sort_add_triangle( struct sort_triangle *triangle, struct polygon_struct *poly, int index )
    70 {
    71     struct vertex_struct *vertexes = &pvr2_scene.vertex_array[poly->vertex_index+index];
    72     triangle->poly = poly;
    73     triangle->triangle_num = index;
    75     /* Compute triangle bounding-box */
    76     triangle->bounds[0] = MIN3(vertexes[0].x,vertexes[1].x,vertexes[2].x);
    77     triangle->bounds[1] = MAX3(vertexes[0].x,vertexes[1].x,vertexes[2].x);
    78     triangle->bounds[2] = MIN3(vertexes[0].y,vertexes[1].y,vertexes[2].y);
    79     triangle->bounds[3] = MAX3(vertexes[0].y,vertexes[1].y,vertexes[2].y);
    80     triangle->bounds[4] = MIN3(vertexes[0].z,vertexes[1].z,vertexes[2].z);
    81     triangle->bounds[5] = MAX3(vertexes[0].z,vertexes[1].z,vertexes[2].z);
    83     /* Compute plane equation */
    84     float sx = vertexes[1].x - vertexes[0].x;
    85     float sy = vertexes[1].y - vertexes[0].y;
    86     float sz = vertexes[1].z - vertexes[0].z;
    87     float tx = vertexes[2].x - vertexes[0].x;
    88     float ty = vertexes[2].y - vertexes[0].y;
    89     float tz = vertexes[2].z - vertexes[0].z;
    90     triangle->mx = sy*tz - sz*ty;
    91     triangle->my = sz*tx - sx*tz;
    92     triangle->mz = sx*ty - sy*tx;
    93     triangle->d = -vertexes[0].x*triangle->mx - 
    94                   vertexes[0].y*triangle->my - 
    95                   vertexes[0].z*triangle->mz;
    96 }
   100 /**
   101  * Extract a triangle list from the tile (basically indexes into the polygon list, plus
   102  * computing maxz while we go through it
   103  */
   104 int sort_extract_triangles( pvraddr_t tile_entry, struct sort_triangle *triangles )
   105 {
   106     uint32_t *tile_list = (uint32_t *)(pvr2_main_ram+tile_entry);
   107     int strip_count;
   108     struct polygon_struct *poly;
   109     int count = 0, i;
   111     while(1) {
   112         uint32_t entry = *tile_list++;
   113         switch( entry >> 28 ) {
   114         case 0x0F:
   115             return count; // End-of-list
   116         case 0x0E:
   117             tile_list = (uint32_t *)(pvr2_main_ram + (entry&0x007FFFFF));
   118             break;
   119         case 0x08: case 0x09:
   120             strip_count = ((entry >> 25) & 0x0F)+1;
   121             poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
   122             while( strip_count > 0 ) {
   123                 assert( poly != NULL );
   124                 if( poly->vertex_count != 0 ) {
   125                     /* Triangle could point to a strip, but we only want
   126                      * the first one in this case
   127                      */
   128                     sort_add_triangle( &triangles[count], poly, 0 );
   129                     count++;
   130                 }
   131                 poly = poly->next;
   132                 strip_count--;
   133             }
   134             break;
   135         case 0x0A: case 0x0B:
   136             strip_count = ((entry >> 25) & 0x0F)+1;
   137             poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
   138             while( strip_count > 0 ) {
   139                 assert( poly != NULL );
   140                 for( i=0; i+2<poly->vertex_count && i < 2; i++ ) {
   141                     /* Note: quads can't have sub-polys */
   142                     sort_add_triangle( &triangles[count], poly, i );
   143                     count++;
   144                 }
   145                 poly = poly->next;
   146                 strip_count--;
   147             }
   148             break;
   149         default:
   150             if( entry & 0x7E000000 ) {
   151                 poly = pvr2_scene.buf_to_poly_map[entry&0x000FFFFF];
   152                 /* FIXME: This could end up including a triangle that was
   153                  * excluded from the tile, if it is part of a strip that
   154                  * still has some other triangles in the tile.
   155                  * (This couldn't happen with TA output though).
   156                  */
   157                 while( poly != NULL ) {
   158                     for( i=0; i+2<poly->vertex_count; i++ ) {
   159                         sort_add_triangle( &triangles[count], poly, i );
   160                         count++;
   161                     }
   162                     poly = poly->sub_next;
   163                 }
   164             }
   165         }
   166     }       
   168 }
   170 void sort_render_triangles( struct sort_triangle **triangles, int num_triangles )
   171 {
   172     int i;
   173     for( i=0; i<num_triangles; i++ ) {
   174         struct polygon_struct *poly = triangles[i]->poly;
   175         glBindTexture(GL_TEXTURE_2D, poly->tex_id);
   176         render_set_tsp_context( poly->context[0], poly->context[1] );
   177         glDrawArrays(GL_TRIANGLE_STRIP, poly->vertex_index + triangles[i]->triangle_num, 3 );
   178     }
   179 }
   181 static int sort_triangle_compare( const void *a, const void *b ) 
   182 {
   183     const struct sort_triangle *tri1 = a;
   184     const struct sort_triangle *tri2 = b;
   185     if( tri1->bounds[5] <= tri2->bounds[4] ) 
   186         return 1; /* tri1 is entirely under tri2 */
   187     else if( tri2->bounds[5] <= tri1->bounds[4] )
   188         return -1;  /* tri2 is entirely under tri1 */
   189     else if( tri1->bounds[1] <= tri2->bounds[0] ||
   190              tri2->bounds[1] <= tri1->bounds[0] ||
   191              tri1->bounds[3] <= tri2->bounds[2] ||
   192              tri2->bounds[3] <= tri1->bounds[2] )
   193         return 0; /* tri1 and tri2 don't actually overlap at all */
   194     else { 
   195         struct vertex_struct *tri1v = &pvr2_scene.vertex_array[tri1->poly->vertex_index + tri1->triangle_num];
   196         struct vertex_struct *tri2v = &pvr2_scene.vertex_array[tri2->poly->vertex_index + tri2->triangle_num];
   197         float v[3];
   198         int i;
   199         for( i=0; i<3; i++ ) {
   200             v[i] = tri1->mx * tri2v[i].x + tri1->my * tri2v[i].y + tri1->mz * tri2v[i].z + tri1->d;
   201             if( v[i] > -EPSILON && v[i] < EPSILON ) v[i] = 0;
   202         }
   203         if( v[0] == 0 && v[1] == 0 && v[2] == 0 ) {
   204             return 0; /* coplanar */
   205         }
   206         if( (v[0] >=0 && v[1] >= 0 && v[2] >= 0) ||
   207             (v[0] <= 0 && v[1] <= 0 && v[2] <= 0) ) {
   208             /* Tri is on one side of the plane. Pick an arbitrary point to determine which side */
   209             float t1z = -(tri1->mx * tri2v[0].x + tri1->my * tri2v[0].y + tri1->d) / tri1->mz;
   210             return tri2v[0].z - t1z;
   211         }
   213         /* If the above test failed, then tri2 intersects tri1's plane. This
   214          * doesn't necessarily mean the triangles intersect (although they may).
   215          * For now just return 0, and come back to this later as it's a fairly
   216          * uncommon case in practice. 
   217          */
   218         return 0;
   219     }
   220 }
   222 /**
   223  * This is pretty much a standard merge sort (Unfortunately can't depend on
   224  * the system to provide one. Note we can't use quicksort here - the sort
   225  * must be stable to preserve the order of coplanar triangles.
   226  */
   227 static void sort_triangles( struct sort_triangle **triangles, int num_triangles, struct sort_triangle **out )
   228 {
   229     if( num_triangles > 2 ) {
   230         int l = num_triangles>>1, r=num_triangles-l, i=0,j=0;
   231         struct sort_triangle *left[l];
   232         struct sort_triangle *right[r];
   233         sort_triangles( triangles, l, left );
   234         sort_triangles( triangles+l, r, right );
   236         /* Merge */
   237         while(1) {
   238             if( sort_triangle_compare(left[i], right[j]) <= 0 ) {
   239                 *out++ = left[i++];
   240                 if( i == l ) {
   241                     memcpy( out, &right[j], (r-j)*sizeof(struct sort_triangle *) );        
   242                     break;
   243                 }
   244             } else {
   245                 *out++ = right[j++];
   246                 if( j == r ) {
   247                     memcpy( out, &left[i], (l-i)*sizeof(struct sort_triangle *) );
   248                     break;
   249                 }
   250             }
   251         }
   252     } else if( num_triangles == 2 ) {
   253         if( sort_triangle_compare(triangles[0], triangles[1]) <= 0 ) {
   254             out[0] = triangles[0];
   255             out[1] = triangles[1];
   256         } else {
   257             struct sort_triangle *tmp = triangles[0];
   258             out[0] = triangles[1];
   259             out[1] = tmp;
   260         }
   261     } else {
   262         out[0] = triangles[0];
   263     }
   264 } 
   266 void render_autosort_tile( pvraddr_t tile_entry, int render_mode ) 
   267 {
   268     int num_triangles = sort_count_triangles(tile_entry);
   269     if( num_triangles == 0 ) {
   270         return; /* nothing to do */
   271     } else if( num_triangles == 1 ) { /* Triangle can hardly overlap with itself */
   272         glDepthMask(GL_FALSE);
   273         glDepthFunc(GL_GEQUAL);
   274         gl_render_tilelist(tile_entry, FALSE);
   275     } else { /* Ooh boy here we go... */
   276         int i;
   277         struct sort_triangle triangles[num_triangles+1];
   278         struct sort_triangle *triangle_order[num_triangles+1];
   279         triangles[num_triangles].poly = (void *)SENTINEL;
   280         for( i=0; i<num_triangles; i++ ) {
   281             triangle_order[i] = &triangles[i];
   282         }
   283         int extracted_triangles = sort_extract_triangles(tile_entry, triangles);
   284         assert( extracted_triangles <= num_triangles );
   285         sort_triangles( triangle_order, extracted_triangles, triangle_order );
   286         glDepthMask(GL_FALSE);
   287         glDepthFunc(GL_GEQUAL);
   288         sort_render_triangles(triangle_order, extracted_triangles);
   289         assert( triangles[num_triangles].poly == (void *)SENTINEL );
   290     }
   291 }
.