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