Search
lxdream.org :: lxdream/src/pvr2/rendsort.c
lxdream 0.9.1
released Jun 29
Download Now
filename src/pvr2/rendsort.c
changeset 1298:d0eb2307b847
prev1154:5225c7c059ce
author nkeynes
date Wed Feb 04 08:38:23 2015 +1000 (5 years ago)
permissions -rw-r--r--
last change Fix assorted compile warnings reported by Clang
file annotate diff log raw
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
}
.