2 * $Id: rendbkg.c,v 1.7 2007-10-08 11:52:13 nkeynes Exp $
4 * PVR2 background renderer.
6 * Yes, it uses the same basic data structure. Yes, it needs to be handled
7 * completely differently.
9 * PVR2 backgrounds are defined as a set of three fully specified vertexes,
10 * stored in compiled-vertex format. The vertexes form a triangle which is
11 * rendered in the normal fashion. Points outside the triangle are rendered
12 * by extrapolating from the gradients established by the triangle, giving
13 * an overall smooth gradient across the background. Points are colour-clamped
14 * prior to output to the buffer.
16 * As a special case, if all three points lie on the same line (or are the same
17 * point, the third point is used by itself to define the entire buffer (ie
18 * effectively a solid colour).
20 * Note: this would be really simple if GL did unclamped colour interpolation
21 * but it doesn't (portably), which makes this roughly 2 orders of magnitude
22 * more complicated than it otherwise would be.
24 * Copyright (c) 2005 Nathan Keynes.
26 * This program is free software; you can redistribute it and/or modify
27 * it under the terms of the GNU General Public License as published by
28 * the Free Software Foundation; either version 2 of the License, or
29 * (at your option) any later version.
31 * This program is distributed in the hope that it will be useful,
32 * but WITHOUT ANY WARRANTY; without even the implied warranty of
33 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
34 * GNU General Public License for more details.
39 #include "pvr2/pvr2.h"
42 #define MAX_CLAMP_LINES 8
43 #define MAX_VERTEXES 256
44 #define MAX_REGIONS 256
46 #define FARGB_A(x) (((float)(((x)>>24)+1))/256.0)
47 #define FARGB_R(x) (((float)((((x)>>16)&0xFF)+1))/256.0)
48 #define FARGB_G(x) (((float)((((x)>>8)&0xFF)+1))/256.0)
49 #define FARGB_B(x) (((float)(((x)&0xFF)+1))/256.0)
52 * Compute the line where k = target_k, (where k is normally one of
53 * r,g,b,a, or z) and determines the points at which the line intersects
54 * the viewport (0,0,width,height).
56 * @param center_x the x value for the center position
57 * @param center_y the y value for the center position
58 * @param center_k the k value for the center position
59 * @param width Width of the viewport (ie 640)
60 * @param height Height of the viewport (ie 480)
61 * @param target_k determine the line where k = this value, ie 1.0
63 * @param target Array to write the resultant x,y pairs to (note this
64 * function only sets x and y values).
65 * @return number of vertexes written to the target.
67 static int compute_colour_line( float center_x, float center_y, float center_k,
68 int width, int height, float target_k,
69 float detxy, float detxk, float detyk,
70 struct vertex_unpacked *target ) {
72 float tmpk = (target_k - center_k) * detxy;
77 x0 = (tmpk - ((0-center_y)*detxk))/detyk + center_x; /* x where y=0 */
78 if( x0 >= 0.0 && x0 <= width ) {
79 target[num_points].x = x0;
80 target[num_points].y = 0.0;
84 x1 = (tmpk - ((height-center_y)*detxk))/detyk + center_x; /* x where y=height */
85 if( x1 >= 0.0 && x1 <= width ) {
86 target[num_points].x = x1;
87 target[num_points].y = height;
93 if( x0 != 0.0 && x1 != 0.0 ) { /* If x0 == 0 or x1 == 0, then we already have this one */
94 float y0 = (tmpk - ((0-center_x)*detyk))/detxk + center_y; /* y where x=0 */
95 if( y0 >= 0.0 && y0 <= height ) {
96 target[num_points].x = 0.0;
97 target[num_points].y = y0;
102 if( x0 != width && x1 != width ) {
103 float y1 = (tmpk - ((width-center_x)*detyk))/detxk + center_y; /* y where x=width */
104 if( y1 >= 0.0 && y1 <= height ) {
105 target[num_points].x = width;
106 target[num_points].y = y1;
112 if( num_points == 0 || num_points == 2 ) {
113 /* 0 = no points - line doesn't pass through the viewport */
114 /* 2 = normal case - got 2 endpoints */
117 ERROR( "compute_colour_line got bad number of points: %d", num_points );
123 * A region describes a portion of the screen, possibly subdivided by a line.
124 * if region_left and region_right are -1, this is a terminal region that can
125 * be rendered directly. Otherwise region_left and region_right refer two
126 * sub-regions that are separated by the line segment vertex1-vertex2.
129 /* Vertexes marking the line segment that splits this region */
132 /* Index of the left sub-region */
134 /* Index of the right sub-region */
139 * Convenience structure to bundle together the vertex and region data.
144 struct vertex_unpacked vertexes[MAX_VERTEXES];
145 struct bkg_region regions[MAX_REGIONS];
149 * Constants returned by compute_line_intersection. Note that for these purposes,
150 * "Left" means the point(s) result in a negative value in the line equation, while
151 * "Right" means the points(s) result in a positive value in the line equation. The
152 * exact meaning isn't particularly important though, as long as we're consistent
153 * throughout this process
155 #define LINE_COLLINEAR 0 /* The line segments are part of the same line */
156 #define LINE_SIDE_LEFT 1 /* The second line is entirely to the "left" of the first line */
157 #define LINE_SIDE_RIGHT 2 /* The second line is entirely to the "right" of the first line */
158 #define LINE_INTERSECT_FROM_LEFT 3 /* The lines intersect, and (x3,y3) is to the "left" of the first line */
159 #define LINE_INTERSECT_FROM_RIGHT 4 /* The lines intersect, and (x3,y3) is to the "right" of the first line */
160 #define LINE_SKEW 5 /* The line segments neither intersect nor do any of the above apply (should never happen here) */
163 * Compute the intersection of two line segments, where
164 * (x1,y1)-(x2,y2) defines the target segment, and
165 * (x3,y3)-(x4,y4) defines the line intersecting it.
167 * Based off work by Mukesh Prasad (http://www.acm.org/pubs/tog/GraphicsGems/index.html)
169 * @return one of the above LINE_* constants
171 static int compute_line_intersection( float x1, float y1, /* First line segment */
173 float x3, float y3, /* Second line segment */
175 float *x, float *y ) /* Output value: */
177 float a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
178 float r1, r2, r3, r4; /* test values */
179 float denom; /* Intermediate values */
181 /* Compute a1, b1, c1, where line joining points 1 and 2
182 * is "a1 x + b1 y + c1 = 0".
187 c1 = x2 * y1 - x1 * y2;
189 /* Compute r3 and r4. */
191 r3 = a1 * x3 + b1 * y3 + c1;
192 r4 = a1 * x4 + b1 * y4 + c1;
194 /* Check signs of r3 and r4. If both point 3 and point 4 lie on
195 * same side of line 1, the line segments do not intersect.
198 if( r3 == 0 && r4 == 0 ) {
199 return LINE_COLLINEAR;
200 } else if( r3 <= 0 && r4 <= 0 ) {
201 return LINE_SIDE_LEFT;
202 } else if( r3 >= 0 && r4 >= 0 ) {
203 return LINE_SIDE_RIGHT;
206 /* Compute a2, b2, c2 */
210 c2 = x4 * y3 - x3 * y4;
212 /* Compute r1 and r2 */
214 r1 = a2 * x1 + b2 * y1 + c2;
215 r2 = a2 * x2 + b2 * y2 + c2;
217 /* Check signs of r1 and r2. If both point 1 and point 2 lie
218 * on same side of second line segment, the line segments do
222 if ( r1 != 0 && r2 != 0 &&
223 signbit(r1) == signbit(r2) ) {
224 return LINE_SKEW; /* Should never happen */
227 /* Cmpute intersection point.
229 denom = a1 * b2 - a2 * b1;
231 return LINE_COLLINEAR; /* Should never get to this point either */
233 *x = (b1 * c2 - b2 * c1) / denom;
234 *y = (a2 * c1 - a1 * c2) / denom;
236 if( r3 <= 0 && r4 >= 0 ) {
237 return LINE_INTERSECT_FROM_LEFT;
239 return LINE_INTERSECT_FROM_RIGHT;
244 * Given a set of vertexes and a line segment to use to split them, generates
245 * two sets of vertexes representing the polygon on either side of the line
246 * segment. This method preserves the winding direction of the input vertexes.
248 static void compute_subregions( struct bkg_scene *scene,
249 int splitv1, int splitv2,
250 int *vertex_in, int num_vertex_in,
251 int *left_vertex_out, int *num_left_vertex_out,
252 int *right_vertex_out, int *num_right_vertex_out )
254 float x1 = scene->vertexes[splitv1].x;
255 float y1 = scene->vertexes[splitv1].y;
256 float x2 = scene->vertexes[splitv2].x;
257 float y2 = scene->vertexes[splitv2].y;
261 float c1 = x2 * y1 - x1 * y2;
264 *num_left_vertex_out = 0;
265 *num_right_vertex_out = 0;
267 for( i=0; i<num_vertex_in; i++ ) {
268 struct vertex_unpacked *vertex = &scene->vertexes[vertex_in[i]];
269 float r = a1 * vertex->x + b1 * vertex->y + c1;
272 /* cross-point. add the split vertexes */
273 int v1 = vertex_in[i-1];
274 int v2 = vertex_in[i];
275 /* Determine which point is closer to the line. Strictly speaking
276 * one of them must be ON the line, but this way allows for floating
277 * point inaccuracies.
279 float a2 = scene->vertexes[v2].y - scene->vertexes[v1].y;
280 float b2 = scene->vertexes[v1].x - scene->vertexes[v2].x;
281 float c2 = scene->vertexes[v2].x * scene->vertexes[v1].y -
282 scene->vertexes[v1].x * scene->vertexes[v2].y;
283 float r1 = a2 * x1 + b2 * y1 + c2;
284 float r2 = a2 * x2 + b2 * y2 + c2;
285 if( fabsf(r1) > fabs(r2) ) {
290 right_vertex_out[(*num_right_vertex_out)++] = splitv1;
291 right_vertex_out[(*num_right_vertex_out)++] = splitv2;
292 left_vertex_out[(*num_left_vertex_out)++] = splitv2;
293 left_vertex_out[(*num_left_vertex_out)++] = splitv1;
295 } else if( last != 2 ) {
298 left_vertex_out[(*num_left_vertex_out)++] = vertex_in[i];
301 /* cross-point. add the split vertexes */
302 int v1 = vertex_in[i-1];
303 int v2 = vertex_in[i];
304 /* Determine which point is closer to the line. Strictly speaking
305 * one of them must be ON the line, but this way allows for floating
306 * point inaccuracies.
308 float a2 = scene->vertexes[v2].y - scene->vertexes[v1].y;
309 float b2 = scene->vertexes[v1].x - scene->vertexes[v2].x;
310 float c2 = scene->vertexes[v2].x * scene->vertexes[v1].y -
311 scene->vertexes[v1].x * scene->vertexes[v2].y;
312 float r1 = a2 * x1 + b2 * y1 + c2;
313 float r2 = a2 * x2 + b2 * y2 + c2;
314 if( fabsf(r1) > fabs(r2) ) {
319 left_vertex_out[(*num_left_vertex_out)++] = splitv1;
320 left_vertex_out[(*num_left_vertex_out)++] = splitv2;
321 right_vertex_out[(*num_right_vertex_out)++] = splitv2;
322 right_vertex_out[(*num_right_vertex_out)++] = splitv1;
324 } else if( last != 2 ) {
327 right_vertex_out[(*num_right_vertex_out)++] = vertex_in[i];
333 * Subdivide the region tree by splitting it along a given line.
335 * @param scene current bkg scene data
336 * @param region current region under examination
337 * @param vertex1 first vertex of the new line segment
338 * @param vertex2 second vertex of the new line segment
340 static void bkg_region_subdivide( struct bkg_scene *scene, int region, int vertex1, int vertex2 ) {
341 struct bkg_region *this_region = &scene->regions[region];
343 if( scene->regions[region].region_left == -1 || scene->regions[region].region_right == -1 ) {
344 /* Reached the end of the tree. Setup new left+right regions */
345 int i = scene->num_regions;
346 scene->regions[i].region_left = scene->regions[i].region_right = -1;
347 scene->regions[i+1].region_left = scene->regions[i+1].region_right = -1;
348 this_region->region_left = i;
349 this_region->region_right = i+1;
350 this_region->vertex1 = vertex1;
351 this_region->vertex2 = vertex2;
352 scene->num_regions += 2;
355 int thisv1 = this_region->vertex1;
356 int thisv2 = this_region->vertex2;
359 compute_line_intersection( scene->vertexes[thisv1].x, scene->vertexes[thisv1].y,
360 scene->vertexes[thisv2].x, scene->vertexes[thisv2].y,
361 scene->vertexes[vertex1].x, scene->vertexes[vertex1].y,
362 scene->vertexes[vertex2].x, scene->vertexes[vertex2].y,
365 case LINE_INTERSECT_FROM_LEFT:
366 /* if new line segment intersects our current line segment,
367 * subdivide the segment (add a new vertex) and recurse on both
370 /* Compute split-point vertex */
371 vertex3 = scene->num_vertexes++;
372 scene->vertexes[vertex3].x = x;
373 scene->vertexes[vertex3].y = y;
375 bkg_region_subdivide( scene, scene->regions[region].region_left, vertex1,vertex3 );
376 bkg_region_subdivide( scene, scene->regions[region].region_right, vertex3, vertex2 );
378 case LINE_INTERSECT_FROM_RIGHT:
379 /* Same except line runs in the opposite direction */
380 vertex3 = scene->num_vertexes++;
381 scene->vertexes[vertex3].x = x;
382 scene->vertexes[vertex3].y = y;
384 bkg_region_subdivide( scene, scene->regions[region].region_left, vertex2,vertex3 );
385 bkg_region_subdivide( scene, scene->regions[region].region_right, vertex3, vertex1 );
389 /* Collinear - ignore */
392 /* else if line segment passes through the left sub-region alone,
395 bkg_region_subdivide( scene, scene->regions[region].region_left, vertex1, vertex2 );
397 case LINE_SIDE_RIGHT:
398 /* Otherwise line segment passes through the right sub-region alone,
401 bkg_region_subdivide( scene, scene->regions[region].region_right, vertex1, vertex2 );
410 * Compute the values for an array of vertexes, given x,y for each
411 * vertex and the base 3-vertex triple used to define the background
412 * plane. Essentially the base vertexes are used to find the
413 * plane equation for each of z,a,r,g,b,etc, which is then solved for
414 * each of the required compute vertexes (normally the corner points).
416 * @param base The 3 vertexes supplied as the background definition
417 * @param compute An array of vertexes to compute. x and y must be
418 * preset, other values are computed.
420 static void bkg_compute_scene( struct vertex_unpacked *base, int width, int height,
421 struct bkg_scene *scene )
423 struct vertex_unpacked center;
424 struct vertex_unpacked diff0, diff1;
427 center.x = base[1].x;
428 center.y = base[1].y;
429 center.z = (1/base[1].z);
430 center.u = base[1].u;
431 center.v = base[1].v;
432 diff0.x = base[0].x - center.x;
433 diff0.y = base[0].y - center.y;
434 diff0.z = (1/base[0].z) - center.z;
435 diff1.x = base[2].x - center.x;
436 diff1.y = base[2].y - center.y;
437 diff1.z = (1/base[2].z) - center.z;
439 float detxy = ((diff1.y) * (diff0.x)) - ((diff0.y) * (diff1.x));
441 /* Corner points first */
442 scene->vertexes[0].x = 0.0;
443 scene->vertexes[0].y = 0.0;
444 scene->vertexes[1].x = width;
445 scene->vertexes[1].y = 0.0;
446 scene->vertexes[2].x = width;
447 scene->vertexes[2].y = height;
448 scene->vertexes[3].x = 0.0;
449 scene->vertexes[3].y = height;
450 scene->regions[0].region_left = -1;
451 scene->regions[0].region_right = -1;
452 scene->num_vertexes = 4;
453 scene->num_regions = 1;
456 /* The points lie on a single line - no plane for you. Use the values
457 * from the 3rd point for the whole screen.
459 for( i=0; i<4; i++ ) {
460 scene->vertexes[i].rgba[0] = base[2].rgba[0];
461 scene->vertexes[i].rgba[1] = base[2].rgba[1];
462 scene->vertexes[i].rgba[2] = base[2].rgba[2];
463 scene->vertexes[i].rgba[3] = base[2].rgba[3];
464 scene->vertexes[i].z = 1/base[2].z;
465 scene->vertexes[i].u = base[2].u;
466 scene->vertexes[i].v = base[2].v;
469 /* Compute the colour values at each corner */
470 center.rgba[0] = base[1].rgba[0];
471 center.rgba[1] = base[1].rgba[1];
472 center.rgba[2] = base[1].rgba[2];
473 center.rgba[3] = base[1].rgba[3];
474 diff0.rgba[0] = base[0].rgba[0] - center.rgba[0];
475 diff0.rgba[1] = base[0].rgba[1] - center.rgba[1];
476 diff0.rgba[2] = base[0].rgba[2] - center.rgba[2];
477 diff0.rgba[3] = base[0].rgba[3] - center.rgba[3];
478 diff0.u = base[0].u - center.u;
479 diff0.v = base[0].v - center.v;
480 diff1.rgba[0] = base[2].rgba[0] - center.rgba[0];
481 diff1.rgba[1] = base[2].rgba[1] - center.rgba[1];
482 diff1.rgba[2] = base[2].rgba[2] - center.rgba[2];
483 diff1.rgba[3] = base[2].rgba[3] - center.rgba[3];
484 diff1.u = base[2].u - center.u;
485 diff1.v = base[2].v - center.v;
486 for( i=0; i<4; i++ ) {
487 float t = ((scene->vertexes[i].x - center.x) * diff1.y -
488 (scene->vertexes[i].y - center.y) * diff1.x) / detxy;
489 float s = ((scene->vertexes[i].y - center.y) * diff0.x -
490 (scene->vertexes[i].x - center.x) * diff0.y) / detxy;
491 scene->vertexes[i].z = center.z + (t*diff0.z) + (s*diff1.z);
492 scene->vertexes[i].rgba[0] = center.rgba[0] + (t*diff0.rgba[0]) + (s*diff1.rgba[0]);
493 scene->vertexes[i].rgba[1] = center.rgba[1] + (t*diff0.rgba[1]) + (s*diff1.rgba[1]);
494 scene->vertexes[i].rgba[2] = center.rgba[2] + (t*diff0.rgba[2]) + (s*diff1.rgba[2]);
495 scene->vertexes[i].rgba[3] = center.rgba[3] + (t*diff0.rgba[3]) + (s*diff1.rgba[3]);
496 scene->vertexes[i].u = center.u + (t*diff0.u) + (s*diff1.u);
497 scene->vertexes[i].v = center.v + (t*diff0.v) + (s*diff1.v);
500 /* Check for values > 1.0 | < 0.0 */
501 for( k=0; k<4; k++ ) {
502 float detyk = ((diff1.y) * (diff0.rgba[k])) - ((diff0.y)*(diff1.rgba[k]));
503 float detxk = ((diff0.x) * (diff1.rgba[k])) - ((diff1.x)*(diff0.rgba[k]));
504 if( scene->vertexes[0].rgba[k] > 1.0 || scene->vertexes[1].rgba[k] > 1.0 ||
505 scene->vertexes[2].rgba[k] > 1.0 || scene->vertexes[3].rgba[k] > 1.0 ) {
506 int v1 = scene->num_vertexes;
507 scene->num_vertexes += compute_colour_line(center.x, center.y, center.rgba[k],
510 scene->vertexes+scene->num_vertexes );
511 if( scene->num_vertexes != v1 ) {
512 bkg_region_subdivide( scene, 0, v1, v1+1 );
516 if( scene->vertexes[0].rgba[k] < 0.0 || scene->vertexes[1].rgba[k] < 0.0 ||
517 scene->vertexes[2].rgba[k] < 0.0 || scene->vertexes[3].rgba[k] < 0.0 ) {
518 int v1 = scene->num_vertexes;
519 scene->num_vertexes += compute_colour_line(center.x, center.y, center.rgba[k],
522 scene->vertexes+scene->num_vertexes );
523 if( scene->num_vertexes != v1 ) {
524 bkg_region_subdivide( scene, 0, v1, v1+1 );
530 /* Finally compute the colour values for all vertexes
531 * (excluding the 4 we did upfront) */
532 for( i=4; i<scene->num_vertexes; i++ ) {
533 float t = ((scene->vertexes[i].x - center.x) * diff1.y -
534 (scene->vertexes[i].y - center.y) * diff1.x) / detxy;
535 float s = ((scene->vertexes[i].y - center.y) * diff0.x -
536 (scene->vertexes[i].x - center.x) * diff0.y) / detxy;
537 scene->vertexes[i].z = center.z + (t*diff0.z) + (s*diff1.z);
538 scene->vertexes[i].rgba[0] = center.rgba[0] + (t*diff0.rgba[0]) + (s*diff1.rgba[0]);
539 scene->vertexes[i].rgba[1] = center.rgba[1] + (t*diff0.rgba[1]) + (s*diff1.rgba[1]);
540 scene->vertexes[i].rgba[2] = center.rgba[2] + (t*diff0.rgba[2]) + (s*diff1.rgba[2]);
541 scene->vertexes[i].rgba[3] = center.rgba[3] + (t*diff0.rgba[3]) + (s*diff1.rgba[3]);
542 scene->vertexes[i].u = center.u + (t*diff0.u) + (s*diff1.u);
543 scene->vertexes[i].v = center.v + (t*diff0.v) + (s*diff1.v);
549 * Render a bkg_region.
550 * @param scene the background scene data
551 * @param region the region to render
552 * @param vertexes the vertexes surrounding the region
553 * @param num_vertexes the number of vertexes in the vertex array
555 void bkg_render_region( struct bkg_scene *scene, int region, int *vertexes, int num_vertexes,
558 if( scene->regions[region].region_left == -1 && scene->regions[region].region_right == -1 ) {
559 /* Leaf node - render the points as given */
562 for( i=0; i<num_vertexes; i++ ) {
564 glColor4fv(scene->vertexes[k].rgba);
565 if( POLY1_TEXTURED(poly1) ) {
566 glTexCoord2f(scene->vertexes[k].u, scene->vertexes[k].v);
568 glVertex3f(scene->vertexes[k].x, scene->vertexes[k].y, scene->vertexes[k].z);
572 /* split the region into left and right regions */
573 int left_vertexes[num_vertexes+1];
574 int right_vertexes[num_vertexes+1];
577 struct bkg_region *reg = &scene->regions[region];
578 compute_subregions( scene, reg->vertex1, reg->vertex2, vertexes, num_vertexes,
579 left_vertexes, &num_left, right_vertexes, &num_right );
580 bkg_render_region( scene, reg->region_left, left_vertexes, num_left, poly1 );
581 bkg_render_region( scene, reg->region_right, right_vertexes, num_right, poly1 );
587 void render_backplane( uint32_t *polygon, uint32_t width, uint32_t height, uint32_t mode ) {
588 struct vertex_unpacked vertex[3];
589 int screen_vertexes[4] = {0,1,2,3};
590 struct bkg_scene scene;
591 int vertex_length = (mode >> 24) & 0x07;
592 int cheap_shadow = MMIO_READ( PVR2, RENDER_SHADOW ) & 0x100;
593 int is_modified = mode & 0x08000000;
594 int context_length = 3;
595 if( is_modified && !cheap_shadow ) {
600 context_length += (mode & 0x07) * vertex_length;
603 render_unpack_vertexes( vertex, *polygon, polygon+context_length, 3, vertex_length,
605 bkg_compute_scene(vertex, width, height, &scene);
606 render_set_context(polygon, RENDER_NORMAL);
607 glDisable(GL_CULL_FACE);
608 glDisable(GL_DEPTH_TEST);
609 glBlendFunc(GL_ONE, GL_ZERO); /* For now, just disable alpha blending on the bkg */
610 bkg_render_region(&scene, 0, screen_vertexes, 4, *polygon);
.