Search
lxdream.org :: lxdream/src/pvr2/rendbkg.c
lxdream 0.9.1
released Jun 29
Download Now
filename src/pvr2/rendbkg.c
changeset 649:620c5c6496b5
prev645:a7392098299c
author nkeynes
date Tue Mar 11 08:50:16 2008 +0000 (12 years ago)
branchlxdream-render
permissions -rw-r--r--
last change Use maxz rather than minz for tri sorting (better results atm)
Change depth-test-disable to depth-mask (more correct)
Implement alpha test for punchthru polys
file annotate diff log raw
nkeynes@219
     1
/**
nkeynes@561
     2
 * $Id$
nkeynes@219
     3
 *
nkeynes@219
     4
 * PVR2 background renderer. 
nkeynes@219
     5
 *
nkeynes@219
     6
 * Yes, it uses the same basic data structure. Yes, it needs to be handled
nkeynes@219
     7
 * completely differently.
nkeynes@219
     8
 *
nkeynes@239
     9
 * PVR2 backgrounds are defined as a set of three fully specified vertexes,
nkeynes@239
    10
 * stored in compiled-vertex format. The vertexes form a triangle which is
nkeynes@239
    11
 * rendered in the normal fashion. Points outside the triangle are rendered
nkeynes@239
    12
 * by extrapolating from the gradients established by the triangle, giving
nkeynes@239
    13
 * an overall smooth gradient across the background. Points are colour-clamped
nkeynes@239
    14
 * prior to output to the buffer.
nkeynes@239
    15
 *
nkeynes@239
    16
 * As a special case, if all three points lie on the same line (or are the same
nkeynes@239
    17
 * point, the third point is used by itself to define the entire buffer (ie
nkeynes@239
    18
 * effectively a solid colour).
nkeynes@239
    19
 *
nkeynes@221
    20
 * Note: this would be really simple if GL did unclamped colour interpolation
nkeynes@221
    21
 * but it doesn't (portably), which makes this roughly 2 orders of magnitude
nkeynes@221
    22
 * more complicated than it otherwise would be.
nkeynes@221
    23
 *
nkeynes@219
    24
 * Copyright (c) 2005 Nathan Keynes.
nkeynes@219
    25
 *
nkeynes@219
    26
 * This program is free software; you can redistribute it and/or modify
nkeynes@219
    27
 * it under the terms of the GNU General Public License as published by
nkeynes@219
    28
 * the Free Software Foundation; either version 2 of the License, or
nkeynes@219
    29
 * (at your option) any later version.
nkeynes@219
    30
 *
nkeynes@219
    31
 * This program is distributed in the hope that it will be useful,
nkeynes@219
    32
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
nkeynes@219
    33
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
nkeynes@219
    34
 * GNU General Public License for more details.
nkeynes@219
    35
 */
nkeynes@219
    36
nkeynes@219
    37
#include <sys/time.h>
nkeynes@540
    38
#include "display.h"
nkeynes@219
    39
#include "pvr2/pvr2.h"
nkeynes@221
    40
#include <math.h>
nkeynes@219
    41
nkeynes@221
    42
#define MAX_CLAMP_LINES 8
nkeynes@221
    43
#define MAX_VERTEXES 256
nkeynes@221
    44
#define MAX_REGIONS  256
nkeynes@219
    45
nkeynes@219
    46
#define FARGB_A(x) (((float)(((x)>>24)+1))/256.0)
nkeynes@219
    47
#define FARGB_R(x) (((float)((((x)>>16)&0xFF)+1))/256.0)
nkeynes@219
    48
#define FARGB_G(x) (((float)((((x)>>8)&0xFF)+1))/256.0)
nkeynes@219
    49
#define FARGB_B(x) (((float)(((x)&0xFF)+1))/256.0)
nkeynes@219
    50
nkeynes@219
    51
/**
nkeynes@645
    52
 * Convert a half-float (16-bit) FP number to a regular 32-bit float.
nkeynes@645
    53
 * Source is 1-bit sign, 5-bit exponent, 10-bit mantissa.
nkeynes@645
    54
 * TODO: Check the correctness of this.
nkeynes@645
    55
 */
nkeynes@645
    56
static float halftofloat( uint16_t half )
nkeynes@645
    57
{
nkeynes@645
    58
    union {
nkeynes@645
    59
        float f;
nkeynes@645
    60
        uint32_t i;
nkeynes@645
    61
    } temp;
nkeynes@645
    62
    /* int e = ((half & 0x7C00) >> 10) - 15 + 127;
nkeynes@645
    63
nkeynes@645
    64
    temp.i = ((half & 0x8000) << 16) | (e << 23) |
nkeynes@645
    65
    ((half & 0x03FF) << 13); */
nkeynes@645
    66
    temp.i = ((uint32_t)half)<<16;
nkeynes@645
    67
    return temp.f;
nkeynes@645
    68
}
nkeynes@645
    69
nkeynes@645
    70
void render_unpack_vertexes( struct vertex_unpacked *out, uint32_t poly1, 
nkeynes@645
    71
			     uint32_t *vertexes, int num_vertexes,
nkeynes@645
    72
			     int vertex_size, int render_mode )
nkeynes@645
    73
{
nkeynes@645
    74
    int m = 0, i;
nkeynes@645
    75
    if( render_mode == RENDER_FULLMOD ) {
nkeynes@645
    76
	m = (vertex_size - 3)/2;
nkeynes@645
    77
    }
nkeynes@645
    78
nkeynes@645
    79
    for( i=0; i<num_vertexes; i++ ) {
nkeynes@645
    80
	float *vertexf = (float *)vertexes;
nkeynes@645
    81
	int k = m + 3;
nkeynes@645
    82
	out[i].x = vertexf[0];
nkeynes@645
    83
	out[i].y = vertexf[1];
nkeynes@645
    84
	out[i].z = vertexf[2];
nkeynes@645
    85
    	if( POLY1_TEXTURED(poly1) ) {
nkeynes@645
    86
	    if( POLY1_UV16(poly1) ) {
nkeynes@645
    87
		out[i].u = halftofloat(vertexes[k]>>16);
nkeynes@645
    88
		out[i].v = halftofloat(vertexes[k]);
nkeynes@645
    89
		k++;
nkeynes@645
    90
	    } else {
nkeynes@645
    91
		out[i].u = vertexf[k];
nkeynes@645
    92
		out[i].v = vertexf[k+1];
nkeynes@645
    93
		k+=2;
nkeynes@645
    94
	    }
nkeynes@645
    95
	} else {
nkeynes@645
    96
	    out[i].u = 0;
nkeynes@645
    97
	    out[i].v = 0;
nkeynes@645
    98
	}
nkeynes@645
    99
	uint32_t argb = vertexes[k++];
nkeynes@645
   100
	out[i].rgba[0] = FARGB_R(argb);
nkeynes@645
   101
	out[i].rgba[1] = FARGB_G(argb);
nkeynes@645
   102
        out[i].rgba[2] = FARGB_B(argb);
nkeynes@645
   103
	out[i].rgba[3] = FARGB_A(argb);
nkeynes@645
   104
	if( POLY1_SPECULAR(poly1) ) {
nkeynes@645
   105
	    uint32_t offset = vertexes[k++];
nkeynes@645
   106
	    out[i].offset_rgba[0] = FARGB_R(offset);
nkeynes@645
   107
	    out[i].offset_rgba[1] = FARGB_G(offset);
nkeynes@645
   108
	    out[i].offset_rgba[2] = FARGB_B(offset);
nkeynes@645
   109
	    out[i].offset_rgba[3] = FARGB_A(offset);
nkeynes@645
   110
	}
nkeynes@645
   111
	vertexes += vertex_size;
nkeynes@645
   112
    }
nkeynes@645
   113
}
nkeynes@645
   114
nkeynes@645
   115
/**
nkeynes@221
   116
 * Compute the line where k = target_k, (where k is normally one of
nkeynes@221
   117
 * r,g,b,a, or z) and determines the points at which the line intersects
nkeynes@221
   118
 * the viewport (0,0,width,height).
nkeynes@221
   119
 *
nkeynes@221
   120
 * @param center_x the x value for the center position
nkeynes@221
   121
 * @param center_y the y value for the center position
nkeynes@221
   122
 * @param center_k the k value for the center position
nkeynes@221
   123
 * @param width Width of the viewport (ie 640)
nkeynes@221
   124
 * @param height Height of the viewport (ie 480)
nkeynes@221
   125
 * @param target_k determine the line where k = this value, ie 1.0
nkeynes@221
   126
 * @param detxy
nkeynes@221
   127
 * @param target Array to write the resultant x,y pairs to (note this
nkeynes@221
   128
 * function only sets x and y values).
nkeynes@221
   129
 * @return number of vertexes written to the target.
nkeynes@221
   130
 */
nkeynes@221
   131
static int compute_colour_line( float center_x, float center_y, float center_k, 
nkeynes@221
   132
		  int width, int height, float target_k,
nkeynes@221
   133
		  float detxy, float detxk, float detyk,
nkeynes@339
   134
		  struct vertex_unpacked *target ) {
nkeynes@221
   135
    int num_points = 0;
nkeynes@221
   136
    float tmpk = (target_k - center_k) * detxy;
nkeynes@221
   137
    float x0 = -1;
nkeynes@221
   138
    float x1 = -1;
nkeynes@221
   139
    
nkeynes@221
   140
    if( detyk != 0 ) {
nkeynes@221
   141
	x0 = (tmpk - ((0-center_y)*detxk))/detyk + center_x; /* x where y=0 */
nkeynes@221
   142
	if( x0 >= 0.0 && x0 <= width ) {
nkeynes@221
   143
	    target[num_points].x = x0;
nkeynes@221
   144
	    target[num_points].y = 0.0;
nkeynes@221
   145
	    num_points++;
nkeynes@221
   146
	}
nkeynes@221
   147
	
nkeynes@221
   148
	x1 = (tmpk - ((height-center_y)*detxk))/detyk + center_x; /* x where y=height */
nkeynes@221
   149
	if( x1 >= 0.0 && x1 <= width ) {
nkeynes@221
   150
	    target[num_points].x = x1;
nkeynes@221
   151
	    target[num_points].y = height;
nkeynes@221
   152
	    num_points++;
nkeynes@221
   153
	}
nkeynes@221
   154
    }
nkeynes@221
   155
    
nkeynes@221
   156
    if( detxk != 0 ) {
nkeynes@221
   157
	if( x0 != 0.0 && x1 != 0.0 ) { /* If x0 == 0 or x1 == 0, then we already have this one */
nkeynes@221
   158
	    float y0 = (tmpk - ((0-center_x)*detyk))/detxk + center_y; /* y where x=0 */
nkeynes@221
   159
	    if( y0 >= 0.0 && y0 <= height ) {
nkeynes@221
   160
		target[num_points].x = 0.0;
nkeynes@221
   161
		target[num_points].y = y0;
nkeynes@221
   162
		num_points++;
nkeynes@221
   163
	    }
nkeynes@221
   164
	}
nkeynes@221
   165
	
nkeynes@221
   166
	if( x0 != width && x1 != width ) {
nkeynes@221
   167
	    float y1 = (tmpk - ((width-center_x)*detyk))/detxk + center_y; /* y where x=width */
nkeynes@221
   168
	    if( y1 >= 0.0 && y1 <= height ) {
nkeynes@221
   169
		target[num_points].x = width;
nkeynes@221
   170
		target[num_points].y = y1;
nkeynes@221
   171
		num_points++;
nkeynes@221
   172
	    }
nkeynes@221
   173
	}
nkeynes@221
   174
    }
nkeynes@221
   175
nkeynes@221
   176
    if( num_points == 0 || num_points == 2 ) {
nkeynes@221
   177
	/* 0 = no points - line doesn't pass through the viewport */
nkeynes@221
   178
	/* 2 = normal case - got 2 endpoints */
nkeynes@221
   179
	return num_points;
nkeynes@221
   180
    } else {
nkeynes@221
   181
	ERROR( "compute_colour_line got bad number of points: %d", num_points );
nkeynes@221
   182
	return 0;
nkeynes@221
   183
    }
nkeynes@221
   184
}
nkeynes@221
   185
nkeynes@221
   186
/**
nkeynes@221
   187
 * A region describes a portion of the screen, possibly subdivided by a line.
nkeynes@221
   188
 * if region_left and region_right are -1, this is a terminal region that can
nkeynes@221
   189
 * be rendered directly. Otherwise region_left and region_right refer two 
nkeynes@221
   190
 * sub-regions that are separated by the line segment vertex1-vertex2.
nkeynes@221
   191
 */
nkeynes@221
   192
struct bkg_region {
nkeynes@221
   193
    /* Vertexes marking the line segment that splits this region */
nkeynes@221
   194
    int vertex1;
nkeynes@221
   195
    int vertex2;
nkeynes@221
   196
    /* Index of the left sub-region */
nkeynes@221
   197
    int region_left;
nkeynes@221
   198
    /* Index of the right sub-region */
nkeynes@221
   199
    int region_right;
nkeynes@221
   200
};
nkeynes@221
   201
nkeynes@221
   202
/**
nkeynes@221
   203
 * Convenience structure to bundle together the vertex and region data.
nkeynes@221
   204
 */
nkeynes@221
   205
struct bkg_scene {
nkeynes@221
   206
    int num_vertexes;
nkeynes@221
   207
    int num_regions;
nkeynes@339
   208
    struct vertex_unpacked vertexes[MAX_VERTEXES];
nkeynes@221
   209
    struct bkg_region regions[MAX_REGIONS];
nkeynes@221
   210
};
nkeynes@221
   211
nkeynes@221
   212
/**
nkeynes@221
   213
 * Constants returned by compute_line_intersection. Note that for these purposes,
nkeynes@221
   214
 * "Left" means the point(s) result in a negative value in the line equation, while
nkeynes@221
   215
 * "Right" means the points(s) result in a positive value in the line equation. The
nkeynes@221
   216
 * exact meaning isn't particularly important though, as long as we're consistent
nkeynes@221
   217
 * throughout this process
nkeynes@221
   218
 */
nkeynes@221
   219
#define LINE_COLLINEAR 0   /* The line segments are part of the same line */
nkeynes@221
   220
#define LINE_SIDE_LEFT 1   /* The second line is entirely to the "left" of the first line */
nkeynes@221
   221
#define LINE_SIDE_RIGHT 2  /* The second line is entirely to the "right" of the first line */
nkeynes@221
   222
#define LINE_INTERSECT_FROM_LEFT 3 /* The lines intersect, and (x3,y3) is to the "left" of the first line */
nkeynes@221
   223
#define LINE_INTERSECT_FROM_RIGHT 4 /* The lines intersect, and (x3,y3) is to the "right" of the first line */
nkeynes@221
   224
#define LINE_SKEW 5        /* The line segments neither intersect nor do any of the above apply (should never happen here) */
nkeynes@221
   225
nkeynes@221
   226
/**
nkeynes@221
   227
 * Compute the intersection of two line segments, where 
nkeynes@221
   228
 * (x1,y1)-(x2,y2) defines the target segment, and
nkeynes@221
   229
 * (x3,y3)-(x4,y4) defines the line intersecting it.
nkeynes@221
   230
 *
nkeynes@221
   231
 * Based off work by Mukesh Prasad (http://www.acm.org/pubs/tog/GraphicsGems/index.html)
nkeynes@221
   232
 *
nkeynes@221
   233
 * @return one of the above LINE_* constants
nkeynes@221
   234
 */
nkeynes@221
   235
static int compute_line_intersection( float x1, float y1,   /* First line segment */
nkeynes@221
   236
				      float x2, float y2,
nkeynes@221
   237
				      float x3, float y3,   /* Second line segment */
nkeynes@221
   238
				      float x4, float y4,
nkeynes@221
   239
				      float *x, float *y  )  /* Output value: */
nkeynes@221
   240
{
nkeynes@221
   241
    float a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
nkeynes@221
   242
    float r1, r2, r3, r4;         /* test values */
nkeynes@221
   243
    float denom;     /* Intermediate values */
nkeynes@221
   244
nkeynes@221
   245
    /* Compute a1, b1, c1, where line joining points 1 and 2
nkeynes@221
   246
     * is "a1 x  +  b1 y  +  c1  =  0".
nkeynes@221
   247
     */
nkeynes@221
   248
nkeynes@221
   249
    a1 = y2 - y1;
nkeynes@221
   250
    b1 = x1 - x2;
nkeynes@221
   251
    c1 = x2 * y1 - x1 * y2;
nkeynes@221
   252
nkeynes@221
   253
    /* Compute r3 and r4. */
nkeynes@221
   254
nkeynes@221
   255
    r3 = a1 * x3 + b1 * y3 + c1;
nkeynes@221
   256
    r4 = a1 * x4 + b1 * y4 + c1;
nkeynes@221
   257
nkeynes@221
   258
    /* Check signs of r3 and r4.  If both point 3 and point 4 lie on
nkeynes@221
   259
     * same side of line 1, the line segments do not intersect.
nkeynes@221
   260
     */
nkeynes@221
   261
nkeynes@221
   262
    if( r3 == 0 && r4 == 0 ) {
nkeynes@221
   263
	return LINE_COLLINEAR;
nkeynes@221
   264
    } else if( r3 <= 0 && r4 <= 0 ) {
nkeynes@221
   265
	return LINE_SIDE_LEFT;
nkeynes@221
   266
    } else if( r3 >= 0 && r4 >= 0 ) {
nkeynes@221
   267
	return LINE_SIDE_RIGHT;
nkeynes@221
   268
    }
nkeynes@221
   269
nkeynes@221
   270
    /* Compute a2, b2, c2 */
nkeynes@221
   271
nkeynes@221
   272
    a2 = y4 - y3;
nkeynes@221
   273
    b2 = x3 - x4;
nkeynes@221
   274
    c2 = x4 * y3 - x3 * y4;
nkeynes@221
   275
nkeynes@221
   276
    /* Compute r1 and r2 */
nkeynes@221
   277
nkeynes@221
   278
    r1 = a2 * x1 + b2 * y1 + c2;
nkeynes@221
   279
    r2 = a2 * x2 + b2 * y2 + c2;
nkeynes@221
   280
nkeynes@221
   281
    /* Check signs of r1 and r2.  If both point 1 and point 2 lie
nkeynes@221
   282
     * on same side of second line segment, the line segments do
nkeynes@221
   283
     * not intersect.
nkeynes@221
   284
     */
nkeynes@221
   285
nkeynes@221
   286
    if ( r1 != 0 && r2 != 0 &&
nkeynes@221
   287
         signbit(r1) == signbit(r2) ) {
nkeynes@221
   288
        return LINE_SKEW; /* Should never happen */
nkeynes@221
   289
    }
nkeynes@221
   290
nkeynes@221
   291
    /* Cmpute intersection point. 
nkeynes@221
   292
     */
nkeynes@221
   293
    denom = a1 * b2 - a2 * b1;
nkeynes@221
   294
    if ( denom == 0 )
nkeynes@221
   295
        return LINE_COLLINEAR; /* Should never get to this point either */
nkeynes@221
   296
nkeynes@221
   297
    *x = (b1 * c2 - b2 * c1) / denom;
nkeynes@221
   298
    *y = (a2 * c1 - a1 * c2) / denom;
nkeynes@221
   299
nkeynes@221
   300
    if( r3 <= 0 && r4 >= 0 ) {
nkeynes@221
   301
	return LINE_INTERSECT_FROM_LEFT;
nkeynes@221
   302
    } else {
nkeynes@221
   303
	return LINE_INTERSECT_FROM_RIGHT;
nkeynes@221
   304
    }
nkeynes@221
   305
}
nkeynes@221
   306
nkeynes@221
   307
/**
nkeynes@221
   308
 * Given a set of vertexes and a line segment to use to split them, generates
nkeynes@221
   309
 * two sets of vertexes representing the polygon on either side of the line
nkeynes@221
   310
 * segment. This method preserves the winding direction of the input vertexes.
nkeynes@221
   311
 */
nkeynes@221
   312
static void compute_subregions( struct bkg_scene *scene,
nkeynes@221
   313
				int splitv1, int splitv2,
nkeynes@221
   314
				int *vertex_in, int num_vertex_in,
nkeynes@221
   315
				int *left_vertex_out, int *num_left_vertex_out,
nkeynes@221
   316
				int *right_vertex_out, int *num_right_vertex_out )
nkeynes@221
   317
{
nkeynes@221
   318
    float x1 = scene->vertexes[splitv1].x;
nkeynes@221
   319
    float y1 = scene->vertexes[splitv1].y;
nkeynes@221
   320
    float x2 = scene->vertexes[splitv2].x;
nkeynes@221
   321
    float y2 = scene->vertexes[splitv2].y;
nkeynes@221
   322
nkeynes@221
   323
    float a1 = y2 - y1;
nkeynes@221
   324
    float b1 = x1 - x2;
nkeynes@221
   325
    float c1 = x2 * y1 - x1 * y2;
nkeynes@221
   326
    int i;
nkeynes@221
   327
    
nkeynes@221
   328
    *num_left_vertex_out = 0;
nkeynes@221
   329
    *num_right_vertex_out = 0;
nkeynes@221
   330
    int last = 0;
nkeynes@221
   331
    for( i=0; i<num_vertex_in; i++ ) {
nkeynes@339
   332
	struct vertex_unpacked *vertex = &scene->vertexes[vertex_in[i]];
nkeynes@221
   333
	float r = a1 * vertex->x + b1 * vertex->y + c1;
nkeynes@221
   334
	if( r <= 0 ) {
nkeynes@221
   335
	    if( last == 1 ) {
nkeynes@221
   336
		/* cross-point. add the split vertexes */
nkeynes@221
   337
		int v1 = vertex_in[i-1];
nkeynes@221
   338
		int v2 = vertex_in[i];
nkeynes@221
   339
		/* Determine which point is closer to the line. Strictly speaking
nkeynes@221
   340
		 * one of them must be ON the line, but this way allows for floating
nkeynes@221
   341
		 * point inaccuracies.
nkeynes@221
   342
		 */
nkeynes@221
   343
		float a2 = scene->vertexes[v2].y - scene->vertexes[v1].y;
nkeynes@221
   344
		float b2 = scene->vertexes[v1].x - scene->vertexes[v2].x;
nkeynes@221
   345
		float c2 = scene->vertexes[v2].x * scene->vertexes[v1].y - 
nkeynes@221
   346
		    scene->vertexes[v1].x * scene->vertexes[v2].y;
nkeynes@221
   347
		float r1 = a2 * x1 + b2 * y1 + c2;
nkeynes@221
   348
		float r2 = a2 * x2 + b2 * y2 + c2;
nkeynes@221
   349
		if( fabsf(r1) > fabs(r2) ) {
nkeynes@221
   350
		    int tmp = splitv1;
nkeynes@221
   351
		    splitv1 = splitv2;
nkeynes@221
   352
		    splitv2 = tmp;
nkeynes@221
   353
		}
nkeynes@221
   354
		right_vertex_out[(*num_right_vertex_out)++] = splitv1;
nkeynes@221
   355
		right_vertex_out[(*num_right_vertex_out)++] = splitv2;
nkeynes@221
   356
		left_vertex_out[(*num_left_vertex_out)++] = splitv2;
nkeynes@221
   357
		left_vertex_out[(*num_left_vertex_out)++] = splitv1;
nkeynes@221
   358
		last = 2;
nkeynes@221
   359
	    } else if( last != 2 ) {
nkeynes@221
   360
		last = -1;
nkeynes@221
   361
	    }
nkeynes@221
   362
	    left_vertex_out[(*num_left_vertex_out)++] = vertex_in[i];
nkeynes@221
   363
	} else {
nkeynes@221
   364
	    if( last == -1 ) {
nkeynes@221
   365
		/* cross-point. add the split vertexes */
nkeynes@221
   366
		int v1 = vertex_in[i-1];
nkeynes@221
   367
		int v2 = vertex_in[i];
nkeynes@221
   368
		/* Determine which point is closer to the line. Strictly speaking
nkeynes@221
   369
		 * one of them must be ON the line, but this way allows for floating
nkeynes@221
   370
		 * point inaccuracies.
nkeynes@221
   371
		 */
nkeynes@221
   372
		float a2 = scene->vertexes[v2].y - scene->vertexes[v1].y;
nkeynes@221
   373
		float b2 = scene->vertexes[v1].x - scene->vertexes[v2].x;
nkeynes@221
   374
		float c2 = scene->vertexes[v2].x * scene->vertexes[v1].y - 
nkeynes@221
   375
		    scene->vertexes[v1].x * scene->vertexes[v2].y;
nkeynes@221
   376
		float r1 = a2 * x1 + b2 * y1 + c2;
nkeynes@221
   377
		float r2 = a2 * x2 + b2 * y2 + c2;
nkeynes@221
   378
		if( fabsf(r1) > fabs(r2) ) {
nkeynes@221
   379
		    int tmp = splitv1;
nkeynes@221
   380
		    splitv1 = splitv2;
nkeynes@221
   381
		    splitv2 = tmp;
nkeynes@221
   382
		}
nkeynes@221
   383
		left_vertex_out[(*num_left_vertex_out)++] = splitv1;
nkeynes@221
   384
		left_vertex_out[(*num_left_vertex_out)++] = splitv2;
nkeynes@221
   385
		right_vertex_out[(*num_right_vertex_out)++] = splitv2;
nkeynes@221
   386
		right_vertex_out[(*num_right_vertex_out)++] = splitv1;
nkeynes@221
   387
		last = 2;
nkeynes@221
   388
	    } else if( last != 2 ) {
nkeynes@221
   389
		last = 1;
nkeynes@221
   390
	    }
nkeynes@221
   391
	    right_vertex_out[(*num_right_vertex_out)++] = vertex_in[i];
nkeynes@221
   392
	}
nkeynes@221
   393
    }
nkeynes@221
   394
}
nkeynes@221
   395
nkeynes@221
   396
/**
nkeynes@221
   397
 * Subdivide the region tree by splitting it along a given line.
nkeynes@221
   398
 * 
nkeynes@221
   399
 * @param scene  current bkg scene data
nkeynes@221
   400
 * @param region current region under examination
nkeynes@221
   401
 * @param vertex1 first vertex of the new line segment
nkeynes@221
   402
 * @param vertex2 second vertex of the new line segment
nkeynes@221
   403
 */
nkeynes@221
   404
static void bkg_region_subdivide( struct bkg_scene *scene, int region, int vertex1, int vertex2 ) {
nkeynes@221
   405
    struct bkg_region *this_region = &scene->regions[region];
nkeynes@221
   406
    
nkeynes@221
   407
    if( scene->regions[region].region_left == -1 || scene->regions[region].region_right == -1 ) {
nkeynes@221
   408
	/* Reached the end of the tree. Setup new left+right regions */
nkeynes@221
   409
	int i = scene->num_regions;
nkeynes@221
   410
	scene->regions[i].region_left = scene->regions[i].region_right = -1;
nkeynes@221
   411
	scene->regions[i+1].region_left = scene->regions[i+1].region_right = -1;
nkeynes@221
   412
	this_region->region_left = i;
nkeynes@221
   413
	this_region->region_right = i+1;
nkeynes@221
   414
	this_region->vertex1 = vertex1;
nkeynes@221
   415
	this_region->vertex2 = vertex2;
nkeynes@221
   416
	scene->num_regions += 2;
nkeynes@221
   417
    } else {
nkeynes@221
   418
	float x,y;
nkeynes@221
   419
	int thisv1 = this_region->vertex1;
nkeynes@221
   420
	int thisv2 = this_region->vertex2;
nkeynes@221
   421
	int vertex3;
nkeynes@221
   422
	int status = 
nkeynes@221
   423
	    compute_line_intersection( scene->vertexes[thisv1].x, scene->vertexes[thisv1].y,
nkeynes@221
   424
				       scene->vertexes[thisv2].x, scene->vertexes[thisv2].y,
nkeynes@221
   425
				       scene->vertexes[vertex1].x, scene->vertexes[vertex1].y,
nkeynes@221
   426
				       scene->vertexes[vertex2].x, scene->vertexes[vertex2].y,
nkeynes@221
   427
				       &x, &y );
nkeynes@221
   428
	switch( status ) {
nkeynes@221
   429
	case LINE_INTERSECT_FROM_LEFT:
nkeynes@221
   430
	    /* if new line segment intersects our current line segment,
nkeynes@221
   431
	     * subdivide the segment (add a new vertex) and recurse on both
nkeynes@221
   432
	     * sub trees 
nkeynes@221
   433
	     */
nkeynes@221
   434
	    /* Compute split-point vertex */
nkeynes@221
   435
	    vertex3 = scene->num_vertexes++;
nkeynes@221
   436
	    scene->vertexes[vertex3].x = x;
nkeynes@221
   437
	    scene->vertexes[vertex3].y = y;
nkeynes@221
   438
	    /* Recurse */
nkeynes@221
   439
	    bkg_region_subdivide( scene, scene->regions[region].region_left, vertex1,vertex3 );
nkeynes@221
   440
	    bkg_region_subdivide( scene, scene->regions[region].region_right, vertex3, vertex2 );
nkeynes@221
   441
	    break;
nkeynes@221
   442
	case LINE_INTERSECT_FROM_RIGHT:
nkeynes@221
   443
	    /* Same except line runs in the opposite direction */
nkeynes@221
   444
	    vertex3 = scene->num_vertexes++;
nkeynes@221
   445
	    scene->vertexes[vertex3].x = x;
nkeynes@221
   446
	    scene->vertexes[vertex3].y = y;
nkeynes@221
   447
	    /* Recurse */
nkeynes@221
   448
	    bkg_region_subdivide( scene, scene->regions[region].region_left, vertex2,vertex3 );
nkeynes@221
   449
	    bkg_region_subdivide( scene, scene->regions[region].region_right, vertex3, vertex1 );
nkeynes@221
   450
	    break;
nkeynes@221
   451
	case LINE_COLLINEAR:
nkeynes@221
   452
	case LINE_SKEW:
nkeynes@221
   453
	    /* Collinear - ignore */
nkeynes@221
   454
	    break;
nkeynes@221
   455
	case LINE_SIDE_LEFT:
nkeynes@221
   456
	    /* else if line segment passes through the left sub-region alone,
nkeynes@221
   457
	     * left-recurse only.
nkeynes@221
   458
	     */
nkeynes@221
   459
	    bkg_region_subdivide( scene, scene->regions[region].region_left, vertex1, vertex2 );
nkeynes@221
   460
	    break;
nkeynes@221
   461
	case LINE_SIDE_RIGHT:
nkeynes@221
   462
	    /* Otherwise line segment passes through the right sub-region alone,
nkeynes@221
   463
	     * so right-recurse.
nkeynes@221
   464
	     */
nkeynes@221
   465
	    bkg_region_subdivide( scene, scene->regions[region].region_right, vertex1, vertex2 );
nkeynes@221
   466
	    break;
nkeynes@221
   467
	}
nkeynes@221
   468
    }
nkeynes@221
   469
}
nkeynes@221
   470
nkeynes@221
   471
	
nkeynes@221
   472
nkeynes@221
   473
/**
nkeynes@219
   474
 * Compute the values for an array of vertexes, given x,y for each
nkeynes@219
   475
 * vertex and the base 3-vertex triple used to define the background
nkeynes@219
   476
 * plane. Essentially the base vertexes are used to find the
nkeynes@219
   477
 * plane equation for each of z,a,r,g,b,etc, which is then solved for
nkeynes@219
   478
 * each of the required compute vertexes (normally the corner points).
nkeynes@219
   479
 *
nkeynes@219
   480
 * @param base The 3 vertexes supplied as the background definition
nkeynes@219
   481
 * @param compute An array of vertexes to compute. x and y must be
nkeynes@219
   482
 *   preset, other values are computed.
nkeynes@219
   483
 */
nkeynes@339
   484
static void bkg_compute_scene( struct vertex_unpacked *base, int width, int height,
nkeynes@221
   485
				struct bkg_scene *scene )
nkeynes@219
   486
{
nkeynes@339
   487
    struct vertex_unpacked center;
nkeynes@339
   488
    struct vertex_unpacked diff0, diff1;
nkeynes@221
   489
    int i,k;
nkeynes@219
   490
nkeynes@219
   491
    center.x = base[1].x;
nkeynes@219
   492
    center.y = base[1].y;
nkeynes@635
   493
    center.z = base[1].z;
nkeynes@429
   494
    center.u = base[1].u;
nkeynes@429
   495
    center.v = base[1].v;
nkeynes@339
   496
    diff0.x = base[0].x - center.x;
nkeynes@339
   497
    diff0.y = base[0].y - center.y;
nkeynes@635
   498
    diff0.z = base[0].z - center.z;
nkeynes@339
   499
    diff1.x = base[2].x - center.x;
nkeynes@339
   500
    diff1.y = base[2].y - center.y;
nkeynes@635
   501
    diff1.z = base[2].z - center.z;
nkeynes@219
   502
nkeynes@221
   503
    float detxy = ((diff1.y) * (diff0.x)) - ((diff0.y) * (diff1.x));
nkeynes@221
   504
    
nkeynes@221
   505
    /* Corner points first */
nkeynes@221
   506
    scene->vertexes[0].x = 0.0;
nkeynes@221
   507
    scene->vertexes[0].y = 0.0;
nkeynes@221
   508
    scene->vertexes[1].x = width;
nkeynes@221
   509
    scene->vertexes[1].y = 0.0;
nkeynes@221
   510
    scene->vertexes[2].x = width;
nkeynes@221
   511
    scene->vertexes[2].y = height;
nkeynes@221
   512
    scene->vertexes[3].x = 0.0;
nkeynes@221
   513
    scene->vertexes[3].y = height;
nkeynes@221
   514
    scene->regions[0].region_left = -1;
nkeynes@221
   515
    scene->regions[0].region_right = -1;
nkeynes@221
   516
    scene->num_vertexes = 4;
nkeynes@221
   517
    scene->num_regions = 1;
nkeynes@221
   518
nkeynes@221
   519
    if( detxy == 0 ) {
nkeynes@221
   520
	/* The points lie on a single line - no plane for you. Use the values
nkeynes@221
   521
	 * from the 3rd point for the whole screen.
nkeynes@221
   522
	 */
nkeynes@221
   523
	for( i=0; i<4; i++ ) {
nkeynes@221
   524
	    scene->vertexes[i].rgba[0] = base[2].rgba[0];
nkeynes@221
   525
	    scene->vertexes[i].rgba[1] = base[2].rgba[1];
nkeynes@221
   526
	    scene->vertexes[i].rgba[2] = base[2].rgba[2];
nkeynes@221
   527
	    scene->vertexes[i].rgba[3] = base[2].rgba[3];
nkeynes@635
   528
	    scene->vertexes[i].z = base[2].z;
nkeynes@221
   529
	    scene->vertexes[i].u = base[2].u;
nkeynes@221
   530
	    scene->vertexes[i].v = base[2].v;
nkeynes@221
   531
	}
nkeynes@219
   532
    } else {
nkeynes@221
   533
	/* Compute the colour values at each corner */
nkeynes@221
   534
	center.rgba[0] = base[1].rgba[0];
nkeynes@221
   535
	center.rgba[1] = base[1].rgba[1];
nkeynes@221
   536
	center.rgba[2] = base[1].rgba[2];
nkeynes@221
   537
	center.rgba[3] = base[1].rgba[3];
nkeynes@221
   538
	diff0.rgba[0] = base[0].rgba[0] - center.rgba[0];
nkeynes@221
   539
	diff0.rgba[1] = base[0].rgba[1] - center.rgba[1];
nkeynes@221
   540
	diff0.rgba[2] = base[0].rgba[2] - center.rgba[2];
nkeynes@221
   541
	diff0.rgba[3] = base[0].rgba[3] - center.rgba[3];
nkeynes@221
   542
	diff0.u = base[0].u - center.u;
nkeynes@221
   543
	diff0.v = base[0].v - center.v;
nkeynes@221
   544
	diff1.rgba[0] = base[2].rgba[0] - center.rgba[0];
nkeynes@221
   545
	diff1.rgba[1] = base[2].rgba[1] - center.rgba[1];
nkeynes@221
   546
	diff1.rgba[2] = base[2].rgba[2] - center.rgba[2];
nkeynes@221
   547
	diff1.rgba[3] = base[2].rgba[3] - center.rgba[3];
nkeynes@221
   548
	diff1.u = base[2].u - center.u;
nkeynes@221
   549
	diff1.v = base[2].v - center.v;
nkeynes@221
   550
	for( i=0; i<4; i++ ) {
nkeynes@221
   551
	    float t = ((scene->vertexes[i].x - center.x) * diff1.y -
nkeynes@221
   552
		       (scene->vertexes[i].y - center.y) * diff1.x) / detxy;
nkeynes@221
   553
	    float s = ((scene->vertexes[i].y - center.y) * diff0.x -
nkeynes@221
   554
		       (scene->vertexes[i].x - center.x) * diff0.y) / detxy;
nkeynes@221
   555
	    scene->vertexes[i].z = center.z + (t*diff0.z) + (s*diff1.z);
nkeynes@221
   556
	    scene->vertexes[i].rgba[0] = center.rgba[0] + (t*diff0.rgba[0]) + (s*diff1.rgba[0]);
nkeynes@221
   557
	    scene->vertexes[i].rgba[1] = center.rgba[1] + (t*diff0.rgba[1]) + (s*diff1.rgba[1]);
nkeynes@221
   558
	    scene->vertexes[i].rgba[2] = center.rgba[2] + (t*diff0.rgba[2]) + (s*diff1.rgba[2]);
nkeynes@221
   559
	    scene->vertexes[i].rgba[3] = center.rgba[3] + (t*diff0.rgba[3]) + (s*diff1.rgba[3]);
nkeynes@221
   560
	    scene->vertexes[i].u = center.u + (t*diff0.u) + (s*diff1.u);
nkeynes@221
   561
	    scene->vertexes[i].v = center.v + (t*diff0.v) + (s*diff1.v);
nkeynes@221
   562
	}
nkeynes@221
   563
nkeynes@221
   564
	/* Check for values > 1.0 | < 0.0 */
nkeynes@221
   565
	for( k=0; k<4; k++ ) {
nkeynes@221
   566
	    float detyk = ((diff1.y) * (diff0.rgba[k])) - ((diff0.y)*(diff1.rgba[k]));
nkeynes@221
   567
	    float detxk = ((diff0.x) * (diff1.rgba[k])) - ((diff1.x)*(diff0.rgba[k]));
nkeynes@221
   568
	    if( scene->vertexes[0].rgba[k] > 1.0 || scene->vertexes[1].rgba[k] > 1.0 || 
nkeynes@221
   569
		scene->vertexes[2].rgba[k] > 1.0 || scene->vertexes[3].rgba[k] > 1.0 ) {
nkeynes@221
   570
		int v1 = scene->num_vertexes;
nkeynes@221
   571
		scene->num_vertexes += compute_colour_line(center.x, center.y, center.rgba[k],
nkeynes@221
   572
						    width, height, 1.0,
nkeynes@221
   573
						    detxy, detxk, detyk, 
nkeynes@221
   574
						    scene->vertexes+scene->num_vertexes );
nkeynes@221
   575
		if( scene->num_vertexes != v1 ) {
nkeynes@221
   576
		    bkg_region_subdivide( scene, 0, v1, v1+1 );
nkeynes@221
   577
		}
nkeynes@221
   578
	    }
nkeynes@221
   579
nkeynes@221
   580
	    if( scene->vertexes[0].rgba[k] < 0.0 || scene->vertexes[1].rgba[k] < 0.0 || 
nkeynes@221
   581
		scene->vertexes[2].rgba[k] < 0.0 || scene->vertexes[3].rgba[k] < 0.0 ) {
nkeynes@221
   582
		int v1 = scene->num_vertexes;
nkeynes@221
   583
		scene->num_vertexes += compute_colour_line(center.x, center.y, center.rgba[k],
nkeynes@221
   584
						    width, height, 0.0,
nkeynes@221
   585
						    detxy, detxk, detyk, 
nkeynes@221
   586
						    scene->vertexes+scene->num_vertexes );
nkeynes@221
   587
		if( scene->num_vertexes != v1 ) {
nkeynes@221
   588
		    bkg_region_subdivide( scene, 0, v1, v1+1 );
nkeynes@221
   589
		}
nkeynes@221
   590
nkeynes@221
   591
	    }
nkeynes@221
   592
	}
nkeynes@221
   593
nkeynes@221
   594
	/* Finally compute the colour values for all vertexes 
nkeynes@221
   595
	 * (excluding the 4 we did upfront) */
nkeynes@221
   596
	for( i=4; i<scene->num_vertexes; i++ ) {
nkeynes@221
   597
	    float t = ((scene->vertexes[i].x - center.x) * diff1.y -
nkeynes@221
   598
		       (scene->vertexes[i].y - center.y) * diff1.x) / detxy;
nkeynes@221
   599
	    float s = ((scene->vertexes[i].y - center.y) * diff0.x -
nkeynes@221
   600
		       (scene->vertexes[i].x - center.x) * diff0.y) / detxy;
nkeynes@221
   601
	    scene->vertexes[i].z = center.z + (t*diff0.z) + (s*diff1.z);
nkeynes@221
   602
	    scene->vertexes[i].rgba[0] = center.rgba[0] + (t*diff0.rgba[0]) + (s*diff1.rgba[0]);
nkeynes@221
   603
	    scene->vertexes[i].rgba[1] = center.rgba[1] + (t*diff0.rgba[1]) + (s*diff1.rgba[1]);
nkeynes@221
   604
	    scene->vertexes[i].rgba[2] = center.rgba[2] + (t*diff0.rgba[2]) + (s*diff1.rgba[2]);
nkeynes@221
   605
	    scene->vertexes[i].rgba[3] = center.rgba[3] + (t*diff0.rgba[3]) + (s*diff1.rgba[3]);
nkeynes@221
   606
	    scene->vertexes[i].u = center.u + (t*diff0.u) + (s*diff1.u);
nkeynes@221
   607
	    scene->vertexes[i].v = center.v + (t*diff0.v) + (s*diff1.v);
nkeynes@219
   608
	}
nkeynes@219
   609
    }
nkeynes@219
   610
}
nkeynes@219
   611
nkeynes@221
   612
/**
nkeynes@221
   613
 * Render a bkg_region.
nkeynes@221
   614
 * @param scene the background scene data
nkeynes@221
   615
 * @param region the region to render
nkeynes@221
   616
 * @param vertexes the vertexes surrounding the region
nkeynes@221
   617
 * @param num_vertexes the number of vertexes in the vertex array
nkeynes@221
   618
 */
nkeynes@221
   619
void bkg_render_region( struct bkg_scene *scene, int region, int *vertexes, int num_vertexes,
nkeynes@221
   620
			uint32_t poly1 )
nkeynes@221
   621
{
nkeynes@221
   622
    if( scene->regions[region].region_left == -1 && scene->regions[region].region_right == -1 ) {
nkeynes@221
   623
	/* Leaf node - render the points as given */
nkeynes@221
   624
	int i,k;
nkeynes@221
   625
	glBegin(GL_POLYGON);
nkeynes@221
   626
	for( i=0; i<num_vertexes; i++ ) {
nkeynes@221
   627
	    k = vertexes[i];
nkeynes@221
   628
	    glColor4fv(scene->vertexes[k].rgba);
nkeynes@221
   629
	    if( POLY1_TEXTURED(poly1) ) {
nkeynes@221
   630
		glTexCoord2f(scene->vertexes[k].u, scene->vertexes[k].v);
nkeynes@221
   631
	    }
nkeynes@221
   632
	    glVertex3f(scene->vertexes[k].x, scene->vertexes[k].y, scene->vertexes[k].z);
nkeynes@221
   633
	}
nkeynes@221
   634
	glEnd();
nkeynes@221
   635
    } else {
nkeynes@221
   636
	/* split the region into left and right regions */
nkeynes@221
   637
	int left_vertexes[num_vertexes+1];
nkeynes@221
   638
	int right_vertexes[num_vertexes+1];
nkeynes@221
   639
	int num_left = 0;
nkeynes@221
   640
	int num_right = 0;
nkeynes@221
   641
	struct bkg_region *reg = &scene->regions[region];
nkeynes@221
   642
	compute_subregions( scene, reg->vertex1, reg->vertex2, vertexes, num_vertexes,
nkeynes@221
   643
			    left_vertexes, &num_left, right_vertexes, &num_right );
nkeynes@221
   644
	bkg_render_region( scene, reg->region_left, left_vertexes, num_left, poly1 );
nkeynes@221
   645
	bkg_render_region( scene, reg->region_right, right_vertexes, num_right, poly1 );
nkeynes@221
   646
    }
nkeynes@221
   647
    
nkeynes@221
   648
}
nkeynes@221
   649
nkeynes@221
   650
nkeynes@219
   651
void render_backplane( uint32_t *polygon, uint32_t width, uint32_t height, uint32_t mode ) {
nkeynes@339
   652
    struct vertex_unpacked vertex[3];
nkeynes@221
   653
    int screen_vertexes[4] = {0,1,2,3};
nkeynes@221
   654
    struct bkg_scene scene;
nkeynes@339
   655
    int vertex_length = (mode >> 24) & 0x07;
nkeynes@339
   656
    int cheap_shadow = MMIO_READ( PVR2, RENDER_SHADOW ) & 0x100;
nkeynes@339
   657
    int is_modified = mode & 0x08000000;
nkeynes@339
   658
    int context_length = 3;
nkeynes@339
   659
    if( is_modified && !cheap_shadow ) {
nkeynes@339
   660
	context_length = 5;
nkeynes@339
   661
	vertex_length *= 2;
nkeynes@339
   662
    }
nkeynes@339
   663
    vertex_length += 3;
nkeynes@339
   664
    context_length += (mode & 0x07) * vertex_length;
nkeynes@339
   665
    
nkeynes@219
   666
nkeynes@339
   667
    render_unpack_vertexes( vertex, *polygon, polygon+context_length, 3, vertex_length,
nkeynes@339
   668
			    RENDER_NORMAL );
nkeynes@339
   669
    bkg_compute_scene(vertex, width, height, &scene);
nkeynes@339
   670
    render_set_context(polygon, RENDER_NORMAL);
nkeynes@221
   671
    glDisable(GL_CULL_FACE);
nkeynes@221
   672
    glDisable(GL_DEPTH_TEST);
nkeynes@221
   673
    glBlendFunc(GL_ONE, GL_ZERO); /* For now, just disable alpha blending on the bkg */
nkeynes@221
   674
    bkg_render_region(&scene, 0, screen_vertexes, 4, *polygon);
nkeynes@649
   675
    glEnable(GL_CULL_FACE);
nkeynes@649
   676
    glEnable(GL_DEPTH_TEST);
nkeynes@219
   677
}
.