nkeynes@222: /**
nkeynes@331:  * $Id: rendsort.c,v 1.5 2007-01-26 01:37:39 nkeynes Exp $
nkeynes@222:  *
nkeynes@222:  * PVR2 renderer routines for depth sorted polygons
nkeynes@222:  *
nkeynes@222:  * Copyright (c) 2005 Nathan Keynes.
nkeynes@222:  *
nkeynes@222:  * This program is free software; you can redistribute it and/or modify
nkeynes@222:  * it under the terms of the GNU General Public License as published by
nkeynes@222:  * the Free Software Foundation; either version 2 of the License, or
nkeynes@222:  * (at your option) any later version.
nkeynes@222:  *
nkeynes@222:  * This program is distributed in the hope that it will be useful,
nkeynes@222:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
nkeynes@222:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
nkeynes@222:  * GNU General Public License for more details.
nkeynes@222:  */
nkeynes@222: #include <sys/time.h>
nkeynes@222: #include "pvr2/pvr2.h"
nkeynes@222: #include "asic.h"
nkeynes@222: 
nkeynes@222: extern char *video_base;
nkeynes@318: extern gboolean pvr2_force_fragment_alpha;
nkeynes@222: 
nkeynes@222: #define MIN3( a,b,c ) ((a) < (b) ? ( (a) < (c) ? (a) : (c) ) : ((b) < (c) ? (b) : (c)) )
nkeynes@222: #define MAX3( a,b,c ) ((a) > (b) ? ( (a) > (c) ? (a) : (c) ) : ((b) > (c) ? (b) : (c)) )
nkeynes@222: 
nkeynes@222: struct render_triangle {
nkeynes@222:     uint32_t *polygon;
nkeynes@319:     int vertex_length; /* Number of 32-bit words in vertex, or 0 for an unpacked vertex */
nkeynes@222:     float minx,miny,minz;
nkeynes@222:     float maxx,maxy,maxz;
nkeynes@222:     float *vertexes[3];
nkeynes@222: };
nkeynes@222: 
nkeynes@318: #define SENTINEL 0xDEADBEEF
nkeynes@318: 
nkeynes@222: /**
nkeynes@222:  * Count the number of triangles in the list starting at the given 
nkeynes@222:  * pvr memory address.
nkeynes@222:  */
nkeynes@222: int render_count_triangles( pvraddr_t tile_entry ) {
nkeynes@222:     uint32_t *tile_list = (uint32_t *)(video_base+tile_entry);
nkeynes@222:     int count = 0;
nkeynes@222:     while(1) {
nkeynes@222: 	uint32_t entry = *tile_list++;
nkeynes@222: 	if( entry >> 28 == 0x0F ) {
nkeynes@222: 	    break;
nkeynes@222: 	} else if( entry >> 28 == 0x0E ) {
nkeynes@222: 	    tile_list = (uint32_t *)(video_base+(entry&0x007FFFFF));
nkeynes@222: 	} else if( entry >> 29 == 0x04 ) { /* Triangle array */
nkeynes@222: 	    count += ((entry >> 25) & 0x0F)+1;
nkeynes@222: 	} else if( entry >> 29 == 0x05 ) { /* Quad array */
nkeynes@222: 	    count += ((((entry >> 25) & 0x0F)+1)<<1);
nkeynes@222: 	} else { /* Polygon */
nkeynes@222: 	    int i;
nkeynes@222: 	    for( i=0; i<6; i++ ) {
nkeynes@222: 		if( entry & (0x40000000>>i) ) {
nkeynes@222: 		    count++;
nkeynes@222: 		}
nkeynes@222: 	    }
nkeynes@222: 	}
nkeynes@222:     }
nkeynes@222:     return count;
nkeynes@222: }
nkeynes@222: 
nkeynes@222: static void compute_triangle_boxes( struct render_triangle *triangle, int num_triangles )
nkeynes@222: {
nkeynes@222:     int i;
nkeynes@222:     for( i=0; i<num_triangles; i++ ) {
nkeynes@222: 	triangle[i].minx = MIN3(triangle[i].vertexes[0][0],triangle[i].vertexes[1][0],triangle[i].vertexes[2][0]);
nkeynes@222: 	triangle[i].maxx = MAX3(triangle[i].vertexes[0][0],triangle[i].vertexes[1][0],triangle[i].vertexes[2][0]);
nkeynes@222: 	triangle[i].miny = MIN3(triangle[i].vertexes[0][1],triangle[i].vertexes[1][1],triangle[i].vertexes[2][1]);
nkeynes@222: 	triangle[i].maxy = MAX3(triangle[i].vertexes[0][1],triangle[i].vertexes[1][1],triangle[i].vertexes[2][1]);
nkeynes@331: 	float az = 1/triangle[i].vertexes[0][2];
nkeynes@331: 	float bz = 1/triangle[i].vertexes[1][2];
nkeynes@331: 	float cz = 1/triangle[i].vertexes[2][2];
nkeynes@331: 	triangle[i].minz = MIN3(az,bz,cz);
nkeynes@331: 	triangle[i].maxz = MAX3(az,bz,cz);
nkeynes@222:     }
nkeynes@222: }
nkeynes@222: 
nkeynes@222: void render_extract_triangles( pvraddr_t tile_entry, gboolean cheap_modifier_mode, 
nkeynes@319: 			       struct render_triangle *triangles, int num_triangles,
nkeynes@319: 			       struct vertex_unpacked *vertex_space, int render_mode )
nkeynes@222: {
nkeynes@222:     uint32_t poly_bank = MMIO_READ(PVR2,RENDER_POLYBASE);
nkeynes@222:     uint32_t *tile_list = (uint32_t *)(video_base+tile_entry);
nkeynes@222:     int count = 0;
nkeynes@222:     while(1) {
nkeynes@222: 	uint32_t entry = *tile_list++;
nkeynes@222: 	if( entry >> 28 == 0x0F ) {
nkeynes@222: 	    break;
nkeynes@222: 	} else if( entry >> 28 == 0x0E ) {
nkeynes@222: 	    tile_list = (uint32_t *)(video_base+(entry&0x007FFFFF));
nkeynes@222: 	} else {
nkeynes@222: 	    uint32_t *polygon = (uint32_t *)(video_base + poly_bank + ((entry & 0x000FFFFF) << 2));
nkeynes@222: 	    int is_modified = entry & 0x01000000;
nkeynes@222: 	    int vertex_length = (entry >> 21) & 0x07;
nkeynes@222: 	    int context_length = 3;
nkeynes@222: 	    if( is_modified && !cheap_modifier_mode ) {
nkeynes@222: 		context_length = 5;
nkeynes@222: 		vertex_length *= 2 ;
nkeynes@222: 	    }
nkeynes@222: 	    vertex_length += 3;
nkeynes@222: 
nkeynes@222: 	    if( (entry & 0xE0000000) == 0x80000000 ) {
nkeynes@222: 		/* Triangle(s) */
nkeynes@222: 		int strip_count = ((entry >> 25) & 0x0F)+1;
nkeynes@222: 		int polygon_length = 3 * vertex_length + context_length;
nkeynes@222: 		int i;
nkeynes@222: 		for( i=0; i<strip_count; i++ ) {
nkeynes@222: 		    float *vertex = (float *)(polygon+context_length);
nkeynes@222: 		    triangles[count].polygon = polygon;
nkeynes@222: 		    triangles[count].vertex_length = vertex_length;
nkeynes@222: 		    triangles[count].vertexes[0] = vertex;
nkeynes@222: 		    vertex+=vertex_length;
nkeynes@222: 		    triangles[count].vertexes[1] = vertex;
nkeynes@222: 		    vertex+=vertex_length;
nkeynes@222: 		    triangles[count].vertexes[2] = vertex;
nkeynes@222: 		    polygon += polygon_length;
nkeynes@222: 		    count++;
nkeynes@222: 		}
nkeynes@222: 	    } else if( (entry & 0xE0000000) == 0xA0000000 ) {
nkeynes@319: 		/* Quad(s) */
nkeynes@276: 		int strip_count = ((entry >> 25) & 0x0F)+1;
nkeynes@222: 		int polygon_length = 4 * vertex_length + context_length;
nkeynes@319: 		
nkeynes@222: 		int i;
nkeynes@222: 		for( i=0; i<strip_count; i++ ) {
nkeynes@319: 		    render_unpack_quad( vertex_space, *polygon, (polygon+context_length),
nkeynes@319: 					vertex_length, render_mode );
nkeynes@222: 		    triangles[count].polygon = polygon;
nkeynes@319: 		    triangles[count].vertex_length = 0;
nkeynes@319: 		    triangles[count].vertexes[0] = (float *)vertex_space;
nkeynes@319: 		    triangles[count].vertexes[1] = (float *)(vertex_space + 1);
nkeynes@319: 		    triangles[count].vertexes[2] = (float *)(vertex_space + 3);
nkeynes@222: 		    count++;
nkeynes@222: 		    /* Preserve face direction */
nkeynes@222: 		    triangles[count].polygon = polygon;
nkeynes@319: 		    triangles[count].vertex_length = 0;
nkeynes@319: 		    triangles[count].vertexes[0] = (float *)(vertex_space + 1);
nkeynes@319: 		    triangles[count].vertexes[1] = (float *)(vertex_space + 2);
nkeynes@319: 		    triangles[count].vertexes[2] = (float *)(vertex_space + 3);
nkeynes@222: 		    count++;
nkeynes@319: 		    vertex_space += 4;
nkeynes@222: 		    polygon += polygon_length;
nkeynes@222: 		}
nkeynes@222: 	    } else {
nkeynes@222: 		/* Polygon */
nkeynes@222: 		int i, first=-1, last = -1;
nkeynes@222: 		float *vertex = (float *)polygon+context_length;
nkeynes@222: 		for( i=0; i<6; i++ ) {
nkeynes@222: 		    if( entry & (0x40000000>>i) ) {
nkeynes@222: 			triangles[count].polygon = polygon;
nkeynes@222: 			triangles[count].vertex_length = vertex_length;
nkeynes@222: 			if( i&1 ) {
nkeynes@222: 			    triangles[count].vertexes[0] = vertex + vertex_length;
nkeynes@222: 			    triangles[count].vertexes[1] = vertex;
nkeynes@222: 			    triangles[count].vertexes[2] = vertex + (vertex_length<<1);
nkeynes@222: 			} else {
nkeynes@222: 			    triangles[count].vertexes[0] = vertex;
nkeynes@222: 			    triangles[count].vertexes[1] = vertex + vertex_length;
nkeynes@222: 			    triangles[count].vertexes[2] = vertex + (vertex_length<<1);
nkeynes@222: 			}
nkeynes@222: 			count++;
nkeynes@222: 		    }
nkeynes@222: 		    vertex += vertex_length;
nkeynes@222: 		}
nkeynes@222: 	    }
nkeynes@222: 	}
nkeynes@222:     }
nkeynes@318:     if( count != num_triangles ) {
nkeynes@318: 	ERROR( "Extracted triangles do not match expected count!" );
nkeynes@318:     }
nkeynes@222: }
nkeynes@222: 
nkeynes@222: void render_triangles( struct render_triangle *triangles, int num_triangles,
nkeynes@222: 		       int render_mode )
nkeynes@222: {
nkeynes@318:     int i,j, k, m = 0;
nkeynes@222:     for( i=0; i<num_triangles; i++ ) {
nkeynes@222: 	render_set_context( triangles[i].polygon, render_mode );
nkeynes@331: 	glEnable(GL_DEPTH_TEST);
nkeynes@331: 	glDepthFunc(GL_GEQUAL);
nkeynes@319: 	if( triangles[i].vertex_length == 0 ) {
nkeynes@319: 	    render_unpacked_vertex_array( *triangles[i].polygon, (struct vertex_unpacked **)triangles[i].vertexes, 3 );
nkeynes@319: 	} else {
nkeynes@319: 	    render_vertex_array( *triangles[i].polygon, (uint32_t **)triangles[i].vertexes, 3,
nkeynes@319: 				 triangles[i].vertex_length, render_mode );
nkeynes@222: 	}
nkeynes@222:     }
nkeynes@222: 
nkeynes@222: 
nkeynes@222: }
nkeynes@222: 
nkeynes@222: int compare_triangles( void *a, void *b ) 
nkeynes@222: {
nkeynes@222:     struct render_triangle *tri1 = a;
nkeynes@222:     struct render_triangle *tri2 = b;
nkeynes@331:     if( tri1->minz < tri2->minz ) {  
nkeynes@331: 	return 1; // No these _aren't_ back to front...
nkeynes@331:     } else if( tri1->minz > tri2->minz ) {
nkeynes@222: 	return -1;
nkeynes@222:     } else {
nkeynes@222: 	return 0;
nkeynes@222:     }
nkeynes@222: }
nkeynes@222: 
nkeynes@222: void sort_triangles( struct render_triangle *triangles, int num_triangles )
nkeynes@222: {
nkeynes@222:     qsort( triangles, num_triangles, sizeof(struct render_triangle), compare_triangles );
nkeynes@222: } 
nkeynes@222: 			
nkeynes@222: void render_autosort_tile( pvraddr_t tile_entry, int render_mode, gboolean cheap_modifier_mode ) 
nkeynes@222: {
nkeynes@222:     int num_triangles = render_count_triangles(tile_entry);
nkeynes@222:     if( num_triangles == 0 ) {
nkeynes@222: 	return; /* nothing to do */
nkeynes@222:     } else if( num_triangles == 1 ) { /* Triangle can hardly overlap with itself */
nkeynes@222: 	render_tile( tile_entry, render_mode, cheap_modifier_mode );
nkeynes@222:     } else { /* Ooh boy here we go... */
nkeynes@318: 	struct render_triangle triangles[num_triangles+1];
nkeynes@319: 	struct vertex_unpacked vertex_space[num_triangles << 1]; 
nkeynes@319: 	// Reserve space for num_triangles / 2 * 4 vertexes (maximum possible number of
nkeynes@319: 	// quad vertices)
nkeynes@318: 	triangles[num_triangles].polygon = (void *)SENTINEL;
nkeynes@319: 	render_extract_triangles(tile_entry, cheap_modifier_mode, triangles, num_triangles, vertex_space, render_mode);
nkeynes@222: 	compute_triangle_boxes(triangles, num_triangles);
nkeynes@222: 	sort_triangles( triangles, num_triangles );
nkeynes@222: 	render_triangles(triangles, num_triangles, render_mode);
nkeynes@318: 	if( triangles[num_triangles].polygon != (void *)SENTINEL ) {
nkeynes@318: 	    fprintf( stderr, "Triangle overflow in render_autosort_tile!" );
nkeynes@318: 	}
nkeynes@222:     }
nkeynes@222: }