nkeynes@222: /**
nkeynes@561:  * $Id$
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@653: #include <string.h>
nkeynes@653: #include <assert.h>
nkeynes@222: #include "pvr2/pvr2.h"
nkeynes@653: #include "pvr2/scene.h"
nkeynes@222: #include "asic.h"
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@653: struct sort_triangle {
nkeynes@653:     struct polygon_struct *poly;
nkeynes@653:     int triangle_num; // triangle number in the poly, from 0
nkeynes@653:     float maxz;
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@653: int sort_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@736:         uint32_t entry = *tile_list++;
nkeynes@736:         if( entry >> 28 == 0x0F ) {
nkeynes@736:             break;
nkeynes@736:         } else if( entry >> 28 == 0x0E ) {
nkeynes@736:             tile_list = (uint32_t *)(video_base+(entry&0x007FFFFF));
nkeynes@736:         } else if( entry >> 29 == 0x04 ) { /* Triangle array */
nkeynes@736:             count += ((entry >> 25) & 0x0F)+1;
nkeynes@736:         } else if( entry >> 29 == 0x05 ) { /* Quad array */
nkeynes@736:             count += ((((entry >> 25) & 0x0F)+1)<<1);
nkeynes@736:         } else { /* Polygon */
nkeynes@736:             int i;
nkeynes@736:             for( i=0; i<6; i++ ) {
nkeynes@736:                 if( entry & (0x40000000>>i) ) {
nkeynes@736:                     count++;
nkeynes@736:                 }
nkeynes@736:             }
nkeynes@736:         }
nkeynes@222:     }
nkeynes@222:     return count;
nkeynes@222: }
nkeynes@222: 
nkeynes@653: /**
nkeynes@653:  * Extract a triangle list from the tile (basically indexes into the polygon list, plus
nkeynes@653:  * computing maxz while we go through it
nkeynes@653:  */
nkeynes@653: int sort_extract_triangles( pvraddr_t tile_entry, struct sort_triangle *triangles )
nkeynes@222: {
nkeynes@222:     uint32_t *tile_list = (uint32_t *)(video_base+tile_entry);
nkeynes@222:     int count = 0;
nkeynes@222:     while(1) {
nkeynes@736:         uint32_t entry = *tile_list++;
nkeynes@736:         if( entry >> 28 == 0x0F ) {
nkeynes@736:             break;
nkeynes@736:         } else if( entry >> 28 == 0x0E ) {
nkeynes@736:             tile_list = (uint32_t *)(video_base+(entry&0x007FFFFF));
nkeynes@736:         } else {
nkeynes@736:             uint32_t poly_addr = entry & 0x000FFFFF;
nkeynes@736:             int is_modified = entry & 0x01000000;
nkeynes@736:             int vertex_length = (entry >> 21) & 0x07;
nkeynes@736:             int context_length = 3;
nkeynes@736:             if( is_modified && pvr2_scene.full_shadow ) {
nkeynes@736:                 context_length = 5;
nkeynes@736:                 vertex_length *= 2 ;
nkeynes@736:             }
nkeynes@736:             vertex_length += 3;
nkeynes@222: 
nkeynes@736:             if( (entry & 0xE0000000) == 0x80000000 ) {
nkeynes@736:                 /* Triangle(s) */
nkeynes@736:                 int strip_count = ((entry >> 25) & 0x0F)+1;
nkeynes@736:                 int polygon_length = 3 * vertex_length + context_length;
nkeynes@736:                 int i;
nkeynes@736:                 for( i=0; i<strip_count; i++ ) {
nkeynes@736:                     struct polygon_struct *poly = pvr2_scene.buf_to_poly_map[poly_addr];
nkeynes@736:                     triangles[count].poly = poly;
nkeynes@736:                     triangles[count].triangle_num = 0;
nkeynes@736:                     triangles[count].maxz = MAX3( pvr2_scene.vertex_array[poly->vertex_index].z,
nkeynes@736:                             pvr2_scene.vertex_array[poly->vertex_index+1].z,
nkeynes@736:                             pvr2_scene.vertex_array[poly->vertex_index+2].z );
nkeynes@736:                     poly_addr += polygon_length;
nkeynes@736:                     count++;
nkeynes@736:                 }
nkeynes@736:             } else if( (entry & 0xE0000000) == 0xA0000000 ) {
nkeynes@736:                 /* Quad(s) */
nkeynes@736:                 int strip_count = ((entry >> 25) & 0x0F)+1;
nkeynes@736:                 int polygon_length = 4 * vertex_length + context_length;
nkeynes@736:                 int i;
nkeynes@736:                 for( i=0; i<strip_count; i++ ) {
nkeynes@736:                     struct polygon_struct *poly = pvr2_scene.buf_to_poly_map[poly_addr];
nkeynes@736:                     triangles[count].poly = poly;
nkeynes@736:                     triangles[count].triangle_num = 0;
nkeynes@736:                     triangles[count].maxz = MAX3( pvr2_scene.vertex_array[poly->vertex_index].z,
nkeynes@736:                             pvr2_scene.vertex_array[poly->vertex_index+1].z,
nkeynes@736:                             pvr2_scene.vertex_array[poly->vertex_index+2].z );
nkeynes@736:                     count++;
nkeynes@736:                     triangles[count].poly = poly;
nkeynes@736:                     triangles[count].triangle_num = 1;
nkeynes@736:                     triangles[count].maxz = MAX3( pvr2_scene.vertex_array[poly->vertex_index+1].z,
nkeynes@736:                             pvr2_scene.vertex_array[poly->vertex_index+2].z,
nkeynes@736:                             pvr2_scene.vertex_array[poly->vertex_index+3].z );
nkeynes@736:                     count++;
nkeynes@736:                     poly_addr += polygon_length;
nkeynes@736:                 }
nkeynes@736:             } else {
nkeynes@736:                 /* Polygon */
nkeynes@736:                 int i;
nkeynes@736:                 struct polygon_struct *poly = pvr2_scene.buf_to_poly_map[poly_addr];
nkeynes@736:                 for( i=0; i<6; i++ ) {
nkeynes@736:                     if( entry & (0x40000000>>i) ) {
nkeynes@736:                         triangles[count].poly = poly;
nkeynes@736:                         triangles[count].triangle_num = i;
nkeynes@736:                         triangles[count].maxz = MAX3( pvr2_scene.vertex_array[poly->vertex_index+i].z,
nkeynes@736:                                 pvr2_scene.vertex_array[poly->vertex_index+i+1].z,
nkeynes@736:                                 pvr2_scene.vertex_array[poly->vertex_index+i+2].z );
nkeynes@736:                         count++;
nkeynes@736:                     }
nkeynes@736:                 }
nkeynes@736:             }
nkeynes@736:         }
nkeynes@222:     }
nkeynes@653:     return count;
nkeynes@222: }
nkeynes@222: 
nkeynes@653: void sort_render_triangles( struct sort_triangle *triangles, int num_triangles,
nkeynes@736:                             int render_mode )
nkeynes@222: {
nkeynes@429:     int i;
nkeynes@222:     for( i=0; i<num_triangles; i++ ) {
nkeynes@736:         struct polygon_struct *poly = triangles[i].poly;
nkeynes@736:         if( poly->tex_id != -1 ) {
nkeynes@736:             glBindTexture(GL_TEXTURE_2D, poly->tex_id);
nkeynes@736:         }
nkeynes@736:         render_set_context( poly->context, RENDER_NORMAL );
nkeynes@736:         glDepthMask(GL_FALSE);
nkeynes@736:         glDepthFunc(GL_GEQUAL);
nkeynes@736:         /* Fix cull direction */
nkeynes@736:         if( triangles[i].triangle_num & 1 ) {
nkeynes@736:             glCullFace(GL_FRONT);
nkeynes@736:         } else {
nkeynes@736:             glCullFace(GL_BACK);
nkeynes@736:         }
nkeynes@736: 
nkeynes@736:         glDrawArrays(GL_TRIANGLE_STRIP, poly->vertex_index + triangles[i].triangle_num, 3 );
nkeynes@222:     }
nkeynes@222: }
nkeynes@222: 
nkeynes@429: int compare_triangles( const void *a, const void *b ) 
nkeynes@222: {
nkeynes@653:     const struct sort_triangle *tri1 = a;
nkeynes@653:     const struct sort_triangle *tri2 = b;
nkeynes@653:     return tri2->maxz - tri1->maxz;
nkeynes@222: }
nkeynes@222: 
nkeynes@653: void sort_triangles( struct sort_triangle *triangles, int num_triangles )
nkeynes@222: {
nkeynes@653:     qsort( triangles, num_triangles, sizeof(struct sort_triangle), compare_triangles );
nkeynes@222: } 
nkeynes@736: 
nkeynes@653: void render_autosort_tile( pvraddr_t tile_entry, int render_mode ) 
nkeynes@222: {
nkeynes@653:     int num_triangles = sort_count_triangles(tile_entry);
nkeynes@222:     if( num_triangles == 0 ) {
nkeynes@736:         return; /* nothing to do */
nkeynes@222:     } else if( num_triangles == 1 ) { /* Triangle can hardly overlap with itself */
nkeynes@736:         gl_render_tilelist(tile_entry);
nkeynes@222:     } else { /* Ooh boy here we go... */
nkeynes@736:         struct sort_triangle triangles[num_triangles+1];
nkeynes@736:         // Reserve space for num_triangles / 2 * 4 vertexes (maximum possible number of
nkeynes@736:         // quad vertices)
nkeynes@736:         triangles[num_triangles].poly = (void *)SENTINEL;
nkeynes@736:         int extracted_triangles = sort_extract_triangles(tile_entry, triangles);
nkeynes@736:         assert( extracted_triangles == num_triangles );
nkeynes@736:         sort_triangles( triangles, num_triangles );
nkeynes@736:         sort_render_triangles(triangles, num_triangles, render_mode);
nkeynes@736:         glCullFace(GL_BACK);
nkeynes@736:         assert( triangles[num_triangles].poly == (void *)SENTINEL );
nkeynes@222:     }
nkeynes@222: }