/**

 * $Id$

 *

 * Manage the internal vertex/polygon buffers and scene data structure.

 *

 * Copyright (c) 2005 Nathan Keynes.

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 2 of the License, or

 * (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 */

#include <assert.h>

#include <string.h>

#include <math.h>

#include "lxdream.h"

#include "display.h"

#include "pvr2/pvr2.h"

#include "pvr2/pvr2mmio.h"

#include "pvr2/glutil.h"

#include "pvr2/scene.h"

#define U8TOFLOAT(n)  (((float)((n)+1))/256.0)

#define POLY_IDX(addr) ( ((uint32_t *)addr) - ((uint32_t *)pvr2_scene.pvr2_pbuf))

static void unpack_bgra(uint32_t bgra, float *rgba)

{

    rgba[0] = ((float)(((bgra&0x00FF0000)>>16) + 1)) / 256.0;

    rgba[1] = ((float)(((bgra&0x0000FF00)>>8) + 1)) / 256.0;

    rgba[2] = ((float)((bgra&0x000000FF) + 1)) / 256.0;

    rgba[3] = ((float)(((bgra&0xFF000000)>>24) + 1)) / 256.0;

}

/**

 * Convert a half-float (16-bit) FP number to a regular 32-bit float.

 * Source is 1-bit sign, 5-bit exponent, 10-bit mantissa.

 * TODO: Check the correctness of this.

 */

static float halftofloat( uint16_t half )

{

    union {

        float f;

        uint32_t i;

    } temp;

    temp.i = ((uint32_t)half)<<16;

    return temp.f;

}

static float parse_fog_density( uint32_t value )

{

    union {

        uint32_t i;

        float f;

    } u;

    u.i = (((value+127)&0xFF)<<23)|((value & 0xFF00)<<7);

    return u.f;

}

struct pvr2_scene_struct pvr2_scene;

static float scene_shadow_intensity = 0.0;

static vertex_buffer_t vbuf = NULL;

static void vertex_buffer_map()

{

    // Allow 8 vertexes for the background (4+4)

    uint32_t size = (pvr2_scene.vertex_count + 8) * sizeof(struct vertex_struct);

    pvr2_scene.vertex_array = vbuf->map(vbuf, size);

}

static void vertex_buffer_unmap()

{

    pvr2_scene.vertex_array = vbuf->unmap(vbuf);

}

/**

 * Allocate vertex buffer + temporary structures. GL context must have been initialized before this

 * point.

 */

void pvr2_scene_init()

{

    if( vbuf == NULL ) {

        vbuf = display_driver->create_vertex_buffer();

        pvr2_scene.vertex_array = NULL;

        pvr2_scene.vertex_array_size = 0;

        pvr2_scene.poly_array = g_malloc( MAX_POLY_BUFFER_SIZE );

        pvr2_scene.buf_to_poly_map = g_malloc0( BUF_POLY_MAP_SIZE );

    }

}

/**

 * Clear the scene data structures in preparation for fresh data

 */

void pvr2_scene_reset()

{

    /* Faster to just clear the active entries */

    for( int i=0; i<pvr2_scene.poly_count; i++ ) {

        pvr2_scene.buf_to_poly_map[POLY_IDX(pvr2_scene.poly_array[i].context)] = 0;

    }

    pvr2_scene.poly_count = 0;

    pvr2_scene.vertex_count = 0;

 }

void pvr2_scene_shutdown()

{

    vbuf->destroy(vbuf);

    vbuf = NULL;

    g_free( pvr2_scene.poly_array );

    pvr2_scene.poly_array = NULL;

    g_free( pvr2_scene.buf_to_poly_map );

    pvr2_scene.buf_to_poly_map = NULL;

}

static struct polygon_struct *scene_add_polygon( pvraddr_t poly_idx, int vertex_count,

                                                 shadow_mode_t is_modified )

{

    int vert_mul = is_modified != SHADOW_NONE ? 2 : 1;

    if( pvr2_scene.buf_to_poly_map[poly_idx] != NULL ) {

        if( vertex_count > pvr2_scene.buf_to_poly_map[poly_idx]->vertex_count ) {

            pvr2_scene.vertex_count += (vertex_count - pvr2_scene.buf_to_poly_map[poly_idx]->vertex_count) * vert_mul;

            pvr2_scene.buf_to_poly_map[poly_idx]->vertex_count = vertex_count;

        }

        return pvr2_scene.buf_to_poly_map[poly_idx];

    } else {

        struct polygon_struct *poly = &pvr2_scene.poly_array[pvr2_scene.poly_count++];

        poly->context = &pvr2_scene.pvr2_pbuf[poly_idx];

        poly->vertex_count = vertex_count;

        poly->vertex_index = -1;

        poly->mod_vertex_index = -1;

        poly->next = NULL;

        poly->sub_next = NULL;

        pvr2_scene.buf_to_poly_map[poly_idx] = poly;

        pvr2_scene.vertex_count += (vertex_count * vert_mul);

        return poly;

    }

}

/**

 * Given a starting polygon, break it at the specified triangle so that the

 * preceding triangles are retained, and the remainder are contained in a

 * new sub-polygon. Does not preserve winding.

 */

static struct polygon_struct *scene_split_subpolygon( struct polygon_struct *parent, int split_offset )

{

    assert( split_offset > 0 && split_offset < (parent->vertex_count-2) );

    assert( pvr2_scene.poly_count < MAX_POLYGONS );

    struct polygon_struct *poly = &pvr2_scene.poly_array[pvr2_scene.poly_count++];

    poly->vertex_count = parent->vertex_count - split_offset;

    poly->vertex_index = parent->vertex_index + split_offset;

    if( parent->mod_vertex_index == -1 ) {

        poly->mod_vertex_index = -1;

    } else {

        poly->mod_vertex_index = parent->mod_vertex_index + split_offset;

    }

    poly->context = parent->context;

    poly->next = NULL;

    poly->sub_next = parent->sub_next;

    parent->sub_next = poly;

    parent->vertex_count = split_offset + 2;

    return poly;

}

static float scene_get_palette_offset( uint32_t tex )

{

    uint32_t fmt = (tex & PVR2_TEX_FORMAT_MASK);

    if( fmt == PVR2_TEX_FORMAT_IDX4 ) {

        return ((float)((tex & 0x07E00000) >> 17))/1024.0 + 0.0002;

    } else if( fmt == PVR2_TEX_FORMAT_IDX8 ) {

        return ((float)((tex & 0x06000000) >> 17))/1024.0 + 0.0002;

    } else {

        return -1.0;

    }

}

/**

 * Decode a single PVR2 renderable vertex (opaque/trans/punch-out, but not shadow

 * volume)

 * @param vert Pointer to output vertex structure

 * @param poly1 First word of polygon context (needed to understand vertex)

 * @param poly2 Second word of polygon context

 * @param pvr2_data Pointer to raw pvr2 vertex data (in VRAM)

 * @param modify_offset Offset in 32-bit words to the tex/color data. 0 for

 *        the normal vertex, half the vertex length for the modified vertex.

 */

static void scene_decode_vertex( struct vertex_struct *vert, uint32_t poly1,

                                       uint32_t poly2, uint32_t tex, uint32_t *pvr2_data,

                                       int modify_offset )

{

    gboolean force_alpha = !POLY2_ALPHA_ENABLE(poly2);

    union pvr2_data_type {

        uint32_t *ival;

        float *fval;

    } data;

    data.ival = pvr2_data;

    vert->x = *data.fval++;

    vert->y = *data.fval++;

    float z = *data.fval++;

    if( !isfinite(z) ) {

        z = 0;

    } else if( z != 0 ) {

        z = 1/z;

    }

    if( z > pvr2_scene.bounds[5] ) {

        pvr2_scene.bounds[5] = z;

    } else if( z < pvr2_scene.bounds[4] && z != 0 ) {

        pvr2_scene.bounds[4] = z;

    }

    vert->z = z;

    data.ival += modify_offset;

    if( POLY1_TEXTURED(poly1) ) {

        if( POLY1_UV16(poly1) ) {

            vert->u = halftofloat( *data.ival>>16 );

            vert->v = halftofloat( *data.ival );

            data.ival++;

        } else {

            vert->u = *data.fval++;

            vert->v = *data.fval++;

        }

        switch( POLY2_TEX_BLEND(poly2) ) {

        case 0:/* Convert replace => modulate by setting colour values to 1.0 */

            vert->rgba[0] = vert->rgba[1] = vert->rgba[2] = vert->rgba[3] = 1.0;

            vert->tex_mode = 0.0;

            data.ival++; /* Skip the colour word */

            break;

        case 2: /* Decal */

            vert->tex_mode = 1.0;

            unpack_bgra(*data.ival++, vert->rgba);

            break;

        case 1:

            force_alpha = TRUE;

            /* fall-through */

        default:

            vert->tex_mode = 0.0;

            unpack_bgra(*data.ival++, vert->rgba);

            break;

        }

        vert->r = scene_get_palette_offset(tex);

    } else {

        vert->tex_mode = 2.0;

        vert->r = -1.0;

        unpack_bgra(*data.ival++, vert->rgba);

    }

    if( POLY1_SPECULAR(poly1) ) {

        unpack_bgra(*data.ival++, vert->offset_rgba);

    } else {

        vert->offset_rgba[0] = 0.0;

        vert->offset_rgba[1] = 0.0;

        vert->offset_rgba[2] = 0.0;

        vert->offset_rgba[3] = 0.0;

    }

    if( force_alpha ) {

        vert->rgba[3] = 1.0;

    }

}

/**

 * Compute texture, colour, and z values for 1 or more result points by interpolating from

 * a set of 3 input points. The result point(s) must define their x,y.

 */

static void scene_compute_vertexes( struct vertex_struct *result,

                                    int result_count,

                                    struct vertex_struct *input,

                                    gboolean is_solid_shaded )

{

    int i,j;

    float sx = input[2].x - input[1].x;

    float sy = input[2].y - input[1].y;

    float tx = input[0].x - input[1].x;

    float ty = input[0].y - input[1].y;

    float detxy = ((sy) * (tx)) - ((ty) * (sx));

    if( detxy == 0 ) {

        // If the input points fall on a line, they don't define a usable

        // polygon - the PVR2 takes the last input point as the result in

        // this case.

        for( i=0; i<result_count; i++ ) {

            float x = result[i].x;

            float y = result[i].y;

            memcpy( &result[i], &input[2], sizeof(struct vertex_struct) );

            result[i].x = x;

            result[i].y = y;

        }

        return;

    }

    float sz = input[2].z - input[1].z;

    float tz = input[0].z - input[1].z;

    float su = input[2].u - input[1].u;

    float tu = input[0].u - input[1].u;

    float sv = input[2].v - input[1].v;

    float tv = input[0].v - input[1].v;

    for( i=0; i<result_count; i++ ) {

        float t = ((result[i].x - input[1].x) * sy -

                (result[i].y - input[1].y) * sx) / detxy;

        float s = ((result[i].y - input[1].y) * tx -

                (result[i].x - input[1].x) * ty) / detxy;

        float rz = input[1].z + (t*tz) + (s*sz);

        if( rz > pvr2_scene.bounds[5] ) {

            pvr2_scene.bounds[5] = rz;

        } else if( rz < pvr2_scene.bounds[4] ) {

            pvr2_scene.bounds[4] = rz;

        }

        result[i].z = rz;

        result[i].u = input[1].u + (t*tu) + (s*su);

        result[i].v = input[1].v + (t*tv) + (s*sv);

        result[i].r = input[1].r; /* Last two components are flat */

        result[i].tex_mode = input[1].tex_mode;

        if( is_solid_shaded ) {

            memcpy( result->rgba, input[2].rgba, sizeof(result->rgba) );

            memcpy( result->offset_rgba, input[2].offset_rgba, sizeof(result->offset_rgba) );

        } else {

            float *rgba0 = input[0].rgba;

            float *rgba1 = input[1].rgba;

            float *rgba2 = input[2].rgba;

            float *rgba3 = result[i].rgba;

            for( j=0; j<8; j++ ) {

                float tc = *rgba0++ - *rgba1;

                float sc = *rgba2++ - *rgba1;

                float rc = *rgba1++ + (t*tc) + (s*sc);

                *rgba3++ = rc;

            }

        }

    }

}

static float scene_compute_lut_fog_vertex( float z, float fog_density, float fog_table[][2] )

{

    union {

        uint32_t i;

        float f;

    } v;

    v.f = z * fog_density;

    if( v.f < 1.0 ) v.f = 1.0;

    else if( v.f > 255.9999 ) v.f = 255.9999;

    uint32_t index = ((v.i >> 18) & 0x0F)|((v.i>>19)&0x70);

    return fog_table[index][0];

}

/**

 * Compute the fog coefficients for all polygons using lookup-table fog. It's 

 * a little more convenient to do this as a separate pass, since we don't have

 * to worry about computed vertexes.

 */

static void scene_compute_lut_fog( )

{

    int i,j;

    float fog_density = parse_fog_density(MMIO_READ( PVR2, RENDER_FOGCOEFF ));

    float fog_table[128][2];

    /* Parse fog table out into floating-point format */

    for( i=0; i<128; i++ ) {

        uint32_t ent = MMIO_READ( PVR2, RENDER_FOGTABLE + (i<<2) );

        fog_table[i][0] = ((float)(((ent&0x0000FF00)>>8) + 1)) / 256.0;

        fog_table[i][1] = ((float)((ent&0x000000FF) + 1)) / 256.0;

    }

    for( i=0; i<pvr2_scene.poly_count; i++ ) {

        int mode = POLY2_FOG_MODE(pvr2_scene.poly_array[i].context[1]);

        uint32_t index = pvr2_scene.poly_array[i].vertex_index;

        if( mode == PVR2_POLY_FOG_LOOKUP ) {

            for( j=0; j<pvr2_scene.poly_array[i].vertex_count; j++ ) {

                float fog = scene_compute_lut_fog_vertex( pvr2_scene.vertex_array[index+j].z, fog_density, fog_table );

                if( display_driver->capabilities.has_sl )

                    pvr2_scene.vertex_array[index+j].offset_rgba[3] = -fog;

                else

                    pvr2_scene.vertex_array[index+j].offset_rgba[3] = fog;

            }

        } else if( mode == PVR2_POLY_FOG_LOOKUP2 ) {

            for( j=0; j<pvr2_scene.poly_array[i].vertex_count; j++ ) {

                pvr2_scene.vertex_array[index+j].rgba[0] = pvr2_scene.fog_lut_colour[0];

                pvr2_scene.vertex_array[index+j].rgba[1] = pvr2_scene.fog_lut_colour[1];

                pvr2_scene.vertex_array[index+j].rgba[2] = pvr2_scene.fog_lut_colour[2];

                pvr2_scene.vertex_array[index+j].rgba[3] = 

                    scene_compute_lut_fog_vertex( pvr2_scene.vertex_array[index+j].z, fog_density, fog_table );

                pvr2_scene.vertex_array[index+j].offset_rgba[3] = 0;

            }

        } else if( mode == PVR2_POLY_FOG_DISABLED ) {

            for( j=0; j<pvr2_scene.poly_array[i].vertex_count; j++ ) {

                pvr2_scene.vertex_array[index+j].offset_rgba[3] = 0;

            }

        }

    }    

}

/**

 * Manually cull back-facing polygons where we can - this actually saves

 * us a lot of time vs passing everything to GL to do it.

 */

static void scene_backface_cull()

{

    unsigned poly_idx;

    unsigned poly_count = pvr2_scene.poly_count; /* Note: we don't want to process any sub-polygons created here */

    for( poly_idx = 0; poly_idx<poly_count; poly_idx++ ) {

        uint32_t poly1 = pvr2_scene.poly_array[poly_idx].context[0];

        if( POLY1_CULL_ENABLE(poly1) ) {

            struct polygon_struct *poly = &pvr2_scene.poly_array[poly_idx];

            unsigned vert_idx = poly->vertex_index;

            unsigned tri_count = poly->vertex_count-2;

            struct vertex_struct *vert = &pvr2_scene.vertex_array[vert_idx];

            unsigned i;

            gboolean ccw = (POLY1_CULL_MODE(poly1) == CULL_CCW);

            int first_visible = -1, last_visible = -1;

            for( i=0; i<tri_count; i++ ) {

                float ux = vert[i+1].x - vert[i].x;

                float uy = vert[i+1].y - vert[i].y;

                float vx = vert[i+2].x - vert[i].x;

                float vy = vert[i+2].y - vert[i].y;

                float nz = (ux*vy) - (uy*vx);

                if( ccw ? nz > 0 : nz < 0 ) {

                    /* Surface is visible */

                    if( first_visible == -1 ) {

                        first_visible = i;

                        /* Elide the initial hidden triangles (note we don't

                         * need to care about winding anymore here) */

                        poly->vertex_index += i;

                        poly->vertex_count -= i;

                        if( poly->mod_vertex_index != -1 )

                            poly->mod_vertex_index += i;

                    } else if( last_visible != i-1 ) {

                        /* And... here we have to split the polygon. Allocate a new

                         * sub-polygon to hold the vertex references */

                        struct polygon_struct *sub = scene_split_subpolygon(poly, (i-first_visible));

                        poly->vertex_count -= (i-first_visible-1) - last_visible;

                        first_visible = i;

                        poly = sub;

                    }

                    last_visible = i;

                } /* Else culled */

                /* Invert ccw flag for triangle strip processing */

                ccw = !ccw;

            }

            if( last_visible == -1 ) {

                /* No visible surfaces, so we can mark the whole polygon as being vertex-less */

                poly->vertex_count = 0;

            } else if( last_visible != tri_count-1 ) {

                /* Remove final hidden tris */

                poly->vertex_count -= (tri_count - 1 - last_visible);

            }

        }

    }

}

static void scene_add_cheap_shadow_vertexes( struct vertex_struct *src, struct vertex_struct *dest, int count )

{

    unsigned int i;

    for( i=0; i<count; i++ ) {

        dest->x = src->x;

        dest->y = src->y;

        dest->z = src->z;

        dest->u = src->u;

        dest->v = src->v;

        dest->r = src->r;

        dest->tex_mode = src->tex_mode;

        dest->rgba[0] = src->rgba[0] * scene_shadow_intensity;

        dest->rgba[1] = src->rgba[1] * scene_shadow_intensity;

        dest->rgba[2] = src->rgba[2] * scene_shadow_intensity;

        dest->rgba[3] = src->rgba[3] * scene_shadow_intensity;

        dest->offset_rgba[0] = src->offset_rgba[0] * scene_shadow_intensity;

        dest->offset_rgba[1] = src->offset_rgba[1] * scene_shadow_intensity;

        dest->offset_rgba[2] = src->offset_rgba[2] * scene_shadow_intensity;

        dest->offset_rgba[3] = src->offset_rgba[3];

        dest++;

        src++;

    }

}

static void scene_add_vertexes( pvraddr_t poly_idx, int vertex_length,

                                shadow_mode_t is_modified )

{

    struct polygon_struct *poly = pvr2_scene.buf_to_poly_map[poly_idx];

    uint32_t *ptr = &pvr2_scene.pvr2_pbuf[poly_idx];

    uint32_t *context = ptr;

    unsigned int i;

    if( poly->vertex_index == -1 ) {

        ptr += (is_modified == SHADOW_FULL ? 5 : 3 );

        poly->vertex_index = pvr2_scene.vertex_index;

        assert( poly != NULL );

        assert( pvr2_scene.vertex_index + poly->vertex_count <= pvr2_scene.vertex_count );

        for( i=0; i<poly->vertex_count; i++ ) {

            scene_decode_vertex( &pvr2_scene.vertex_array[pvr2_scene.vertex_index++], context[0], context[1], context[2], ptr, 0 );

            ptr += vertex_length;

        }

        if( is_modified ) {

            assert( pvr2_scene.vertex_index + poly->vertex_count <= pvr2_scene.vertex_count );

            poly->mod_vertex_index = pvr2_scene.vertex_index;

            if( is_modified == SHADOW_FULL ) {

                int mod_offset = (vertex_length - 3)>>1;

                ptr = &pvr2_scene.pvr2_pbuf[poly_idx] + 5;

                for( i=0; i<poly->vertex_count; i++ ) {

                    scene_decode_vertex( &pvr2_scene.vertex_array[pvr2_scene.vertex_index++], context[0], context[3], context[4], ptr, mod_offset );

                    ptr += vertex_length;

                }

            } else {

                scene_add_cheap_shadow_vertexes( &pvr2_scene.vertex_array[poly->vertex_index], 

                        &pvr2_scene.vertex_array[poly->mod_vertex_index], poly->vertex_count );

                pvr2_scene.vertex_index += poly->vertex_count;

            }

        }

    }

}

static void scene_add_quad_vertexes( pvraddr_t poly_idx, int vertex_length,

                                     shadow_mode_t is_modified )

{

    struct polygon_struct *poly = pvr2_scene.buf_to_poly_map[poly_idx];

    uint32_t *ptr = &pvr2_scene.pvr2_pbuf[poly_idx];

    uint32_t *context = ptr;

    unsigned int i;

    if( poly->vertex_index == -1 ) {

        // Construct it locally and copy to the vertex buffer, as the VBO is

        // allowed to be horribly slow for reads (ie it could be direct-mapped

        // vram).

        struct vertex_struct quad[4];

        assert( poly != NULL );

        assert( pvr2_scene.vertex_index + poly->vertex_count <= pvr2_scene.vertex_count );

        ptr += (is_modified == SHADOW_FULL ? 5 : 3 );

        poly->vertex_index = pvr2_scene.vertex_index;

        for( i=0; i<4; i++ ) {

            scene_decode_vertex( &quad[i], context[0], context[1], context[2], ptr, 0 );

            ptr += vertex_length;

        }

        scene_compute_vertexes( &quad[3], 1, &quad[0], !POLY1_GOURAUD_SHADED(context[0]) );

        // Swap last two vertexes (quad arrangement => tri strip arrangement)

        memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index], quad, sizeof(struct vertex_struct)*2 );

        memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index+2], &quad[3], sizeof(struct vertex_struct) );

        memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index+3], &quad[2], sizeof(struct vertex_struct) );

        if( !POLY1_GOURAUD_SHADED(context[0]) ) {

            memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index].rgba, &pvr2_scene.vertex_array[pvr2_scene.vertex_index+3].rgba, sizeof(float)*8 );

            memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index+1].rgba, &pvr2_scene.vertex_array[pvr2_scene.vertex_index+3].rgba, sizeof(float)*8 );

        }

        pvr2_scene.vertex_index += 4;

        if( is_modified ) {

            assert( pvr2_scene.vertex_index + poly->vertex_count <= pvr2_scene.vertex_count );

            poly->mod_vertex_index = pvr2_scene.vertex_index;

            if( is_modified == SHADOW_FULL ) {

                int mod_offset = (vertex_length - 3)>>1;

                ptr = &pvr2_scene.pvr2_pbuf[poly_idx] + 5;

                for( i=0; i<4; i++ ) {

                    scene_decode_vertex( &quad[4], context[0], context[3], context[4], ptr, mod_offset );

                    ptr += vertex_length;

                }

                scene_compute_vertexes( &quad[3], 1, &quad[0], !POLY1_GOURAUD_SHADED(context[0]) );

                memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index], quad, sizeof(struct vertex_struct)*2 );

                memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index+2], &quad[3], sizeof(struct vertex_struct) );

                memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index+3], &quad[2], sizeof(struct vertex_struct) );

                if( !POLY1_GOURAUD_SHADED(context[0]) ) {

                    memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index].rgba, &pvr2_scene.vertex_array[pvr2_scene.vertex_index+3].rgba, sizeof(float)*8 );

                    memcpy( &pvr2_scene.vertex_array[pvr2_scene.vertex_index+1].rgba, &pvr2_scene.vertex_array[pvr2_scene.vertex_index+3].rgba, sizeof(float)*8 );

                }

            } else {

                scene_add_cheap_shadow_vertexes( &pvr2_scene.vertex_array[poly->vertex_index], 

                        &pvr2_scene.vertex_array[poly->mod_vertex_index], poly->vertex_count );

                pvr2_scene.vertex_index += poly->vertex_count;

            }

            pvr2_scene.vertex_index += 4;

        }

    }

}

static void scene_extract_polygons( pvraddr_t tile_entry )

{

    uint32_t *tile_list = (uint32_t *)(pvr2_main_ram+tile_entry);

    do {

        uint32_t entry = *tile_list++;

        if( entry >> 28 == 0x0F ) {

            break;

        } else if( entry >> 28 == 0x0E ) {

            tile_list = (uint32_t *)(pvr2_main_ram + (entry&0x007FFFFF));

        } else {

            pvraddr_t polyaddr = entry&0x000FFFFF;

            shadow_mode_t is_modified = (entry & 0x01000000) ? pvr2_scene.shadow_mode : SHADOW_NONE;

            int vertex_length = (entry >> 21) & 0x07;

            int context_length = 3;

            if( is_modified == SHADOW_FULL ) {

                context_length = 5;

                vertex_length <<= 1 ;

            }

            vertex_length += 3;

            if( (entry & 0xE0000000) == 0x80000000 ) {

                /* Triangle(s) */

                int strip_count = ((entry >> 25) & 0x0F)+1;

                int polygon_length = 3 * vertex_length + context_length;

                int i;

                struct polygon_struct *last_poly = NULL;

                for( i=0; i<strip_count; i++ ) {

                    struct polygon_struct *poly = scene_add_polygon( polyaddr, 3, is_modified );

                    polyaddr += polygon_length;

                    if( last_poly != NULL && last_poly->next == NULL ) {

                        last_poly->next = poly;

                    }

                    last_poly = poly;

                }

            } else if( (entry & 0xE0000000) == 0xA0000000 ) {

                /* Sprite(s) */

                int strip_count = ((entry >> 25) & 0x0F)+1;

                int polygon_length = 4 * vertex_length + context_length;

                int i;

                struct polygon_struct *last_poly = NULL;

                for( i=0; i<strip_count; i++ ) {

                    struct polygon_struct *poly = scene_add_polygon( polyaddr, 4, is_modified );

                    polyaddr += polygon_length;

                    if( last_poly != NULL && last_poly->next == NULL ) {

                        last_poly->next = poly;

                    }

                    last_poly = poly;

                }

            } else {

                /* Polygon */

                int i, last = -1;

                for( i=5; i>=0; i-- ) {

                    if( entry & (0x40000000>>i) ) {

                        last = i;

                        break;

                    }

                }

                if( last != -1 ) {

                    scene_add_polygon( polyaddr, last+3, is_modified );

                }

            }

        }

    } while( 1 );

}

static void scene_extract_vertexes( pvraddr_t tile_entry )

{

    uint32_t *tile_list = (uint32_t *)(pvr2_main_ram+tile_entry);

    do {

        uint32_t entry = *tile_list++;

        if( entry >> 28 == 0x0F ) {

            break;

        } else if( entry >> 28 == 0x0E ) {

            tile_list = (uint32_t *)(pvr2_main_ram + (entry&0x007FFFFF));

        } else {

            pvraddr_t polyaddr = entry&0x000FFFFF;

            shadow_mode_t is_modified = (entry & 0x01000000) ? pvr2_scene.shadow_mode : SHADOW_NONE;

            int vertex_length = (entry >> 21) & 0x07;

            int context_length = 3;

            if( is_modified == SHADOW_FULL ) {

                context_length = 5;

                vertex_length <<=1 ;

            }

            vertex_length += 3;

            if( (entry & 0xE0000000) == 0x80000000 ) {

                /* Triangle(s) */

                int strip_count = ((entry >> 25) & 0x0F)+1;

                int polygon_length = 3 * vertex_length + context_length;

                int i;

                for( i=0; i<strip_count; i++ ) {

                    scene_add_vertexes( polyaddr, vertex_length, is_modified );

                    polyaddr += polygon_length;

                }

            } else if( (entry & 0xE0000000) == 0xA0000000 ) {

                /* Sprite(s) */

                int strip_count = ((entry >> 25) & 0x0F)+1;

                int polygon_length = 4 * vertex_length + context_length;

                int i;

                for( i=0; i<strip_count; i++ ) {

                    scene_add_quad_vertexes( polyaddr, vertex_length, is_modified );

                    polyaddr += polygon_length;

                }

            } else {

                /* Polygon */

                int i, last = -1;

                for( i=5; i>=0; i-- ) {

                    if( entry & (0x40000000>>i) ) {

                        last = i;

                        break;

                    }

                }

                if( last != -1 ) {

                    scene_add_vertexes( polyaddr, vertex_length, is_modified );

                }

            }

        }

    } while( 1 );

}

static void scene_extract_background( void )

{

    uint32_t bgplane = MMIO_READ(PVR2, RENDER_BGPLANE);

    int vertex_length = (bgplane >> 24) & 0x07;

    int context_length = 3, i;

    shadow_mode_t is_modified = (bgplane & 0x08000000) ? pvr2_scene.shadow_mode : SHADOW_NONE;

    struct polygon_struct *poly = &pvr2_scene.poly_array[pvr2_scene.poly_count++];

    uint32_t *context = &pvr2_scene.pvr2_pbuf[(bgplane & 0x00FFFFFF)>>3];

    poly->context = context;

    poly->vertex_count = 4;

    poly->vertex_index = pvr2_scene.vertex_count;

    if( is_modified == SHADOW_FULL ) {

        context_length = 5;

        vertex_length <<= 1;

    }

    if( is_modified != SHADOW_NONE ) {

        poly->mod_vertex_index = pvr2_scene.vertex_count + 4;

        pvr2_scene.vertex_count += 8;

    } else {

        poly->mod_vertex_index = -1;

        pvr2_scene.vertex_count += 4;

    }

    vertex_length += 3;

    context_length += (bgplane & 0x07) * vertex_length;

    poly->next = NULL;

    poly->sub_next = NULL;

    pvr2_scene.bkgnd_poly = poly;

    struct vertex_struct base_vertexes[3];

    uint32_t *ptr = context + context_length;

    for( i=0; i<3; i++ ) {

        scene_decode_vertex( &base_vertexes[i], context[0], context[1], context[2],

                ptr, 0 );

        ptr += vertex_length;

    }

    struct vertex_struct *result_vertexes = &pvr2_scene.vertex_array[poly->vertex_index];

    result_vertexes[0].x = result_vertexes[0].y = 0;

    result_vertexes[1].x = result_vertexes[3].x = pvr2_scene.buffer_width;

    result_vertexes[1].y = result_vertexes[2].x = 0;

    result_vertexes[2].y = result_vertexes[3].y  = pvr2_scene.buffer_height;

    scene_compute_vertexes( result_vertexes, 4, base_vertexes, !POLY1_GOURAUD_SHADED(context[0]) );

    if( is_modified == SHADOW_FULL ) {

        int mod_offset = (vertex_length - 3)>>1;

        ptr = context + context_length;

        for( i=0; i<3; i++ ) {

            scene_decode_vertex( &base_vertexes[i], context[0], context[3], context[4],

                    ptr, mod_offset );

            ptr += vertex_length;

        }

        result_vertexes = &pvr2_scene.vertex_array[poly->mod_vertex_index];

        result_vertexes[0].x = result_vertexes[0].y = 0;

        result_vertexes[1].x = result_vertexes[3].x = pvr2_scene.buffer_width;

        result_vertexes[1].y = result_vertexes[2].x = 0;

        result_vertexes[2].y = result_vertexes[3].y  = pvr2_scene.buffer_height;

        scene_compute_vertexes( result_vertexes, 4, base_vertexes, !POLY1_GOURAUD_SHADED(context[0]) );

    } else if( is_modified == SHADOW_CHEAP ) {

        scene_add_cheap_shadow_vertexes( &pvr2_scene.vertex_array[poly->vertex_index], 

                &pvr2_scene.vertex_array[poly->mod_vertex_index], poly->vertex_count );

        pvr2_scene.vertex_index += poly->vertex_count;

    }

}

uint32_t pvr2_scene_buffer_width()

{

    return pvr2_scene.buffer_width;

}

uint32_t pvr2_scene_buffer_height()

{

    return pvr2_scene.buffer_height;

}

/**

 * Extract the current scene into the rendering structures. We run two passes

 * - first pass extracts the polygons into pvr2_scene.poly_array (finding vertex counts),

 * second pass extracts the vertex data into the VBO/vertex array.

 *

 * Difficult to do in single pass as we don't generally know the size of a

 * polygon for certain until we've seen all tiles containing it. It also means we

 * can count the vertexes and allocate the appropriate size VBO.

 *

 * FIXME: accesses into VRAM need to be bounds-checked properly

 */

void pvr2_scene_read( void )

{

    pvr2_scene_init();

    pvr2_scene_reset();

    pvr2_scene.bounds[0] = MMIO_READ( PVR2, RENDER_HCLIP ) & 0x03FF;

    pvr2_scene.bounds[1] = ((MMIO_READ( PVR2, RENDER_HCLIP ) >> 16) & 0x03FF) + 1;

    pvr2_scene.bounds[2] = MMIO_READ( PVR2, RENDER_VCLIP ) & 0x03FF;

    pvr2_scene.bounds[3] = ((MMIO_READ( PVR2, RENDER_VCLIP ) >> 16) & 0x03FF) + 1;

    pvr2_scene.bounds[4] = pvr2_scene.bounds[5] = MMIO_READF( PVR2, RENDER_FARCLIP );

    uint32_t scaler = MMIO_READ( PVR2, RENDER_SCALER );

    if( scaler & SCALER_HSCALE ) {

    	/* If the horizontal scaler is in use, we're (in principle) supposed to

    	 * divide everything by 2. However in the interests of display quality,

    	 * instead we want to render to the unscaled resolution and downsample

    	 * only if/when required.

    	 */

    	pvr2_scene.bounds[1] *= 2;

    }

    uint32_t fog_col = MMIO_READ( PVR2, RENDER_FOGTBLCOL );

    unpack_bgra( fog_col, pvr2_scene.fog_lut_colour );

    fog_col = MMIO_READ( PVR2, RENDER_FOGVRTCOL );

    unpack_bgra( fog_col, pvr2_scene.fog_vert_colour );

    uint32_t *tilebuffer = (uint32_t *)(pvr2_main_ram + MMIO_READ( PVR2, RENDER_TILEBASE ));

    uint32_t *segment = tilebuffer;

    uint32_t shadow = MMIO_READ(PVR2,RENDER_SHADOW);

    pvr2_scene.segment_list = (struct tile_segment *)tilebuffer;

    pvr2_scene.pvr2_pbuf = (uint32_t *)(pvr2_main_ram + MMIO_READ(PVR2,RENDER_POLYBASE));

    pvr2_scene.shadow_mode = shadow & 0x100 ? SHADOW_CHEAP : SHADOW_FULL;

    scene_shadow_intensity = U8TOFLOAT(shadow&0xFF);

    int max_tile_x = 0;

    int max_tile_y = 0;

    int obj_config = MMIO_READ( PVR2, RENDER_OBJCFG );

    int isp_config = MMIO_READ( PVR2, RENDER_ISPCFG );

    if( (obj_config & 0x00200000) == 0 ) {

        if( isp_config & 1 ) {

            pvr2_scene.sort_mode = SORT_NEVER;

        } else {

            pvr2_scene.sort_mode = SORT_ALWAYS;

        }

    } else {

        pvr2_scene.sort_mode = SORT_TILEFLAG;

    }

    // Pass 1: Extract polygon list

    uint32_t control;

    int i;

    do {

        control = *segment++;

        int tile_x = SEGMENT_X(control);

        int tile_y = SEGMENT_Y(control);

        if( tile_x > max_tile_x ) {

            max_tile_x = tile_x;

        }

        if( tile_y > max_tile_y ) {

            max_tile_y = tile_y;

        }

        for( i=0; i<5; i++ ) {

            if( (*segment & NO_POINTER) == 0 ) {

                scene_extract_polygons( *segment );

            }

            segment++;

        }

    } while( (control & SEGMENT_END) == 0 );

    pvr2_scene.buffer_width = (max_tile_x+1)<<5;

    pvr2_scene.buffer_height = (max_tile_y+1)<<5;

    // Pass 2: Extract vertex data

    vertex_buffer_map();

    pvr2_scene.vertex_index = 0;

    segment = tilebuffer;

    do {

        control = *segment++;

        for( i=0; i<5; i++ ) {

            if( (*segment & NO_POINTER) == 0 ) {

                scene_extract_vertexes( *segment );

            }

            segment++;

        }

    } while( (control & SEGMENT_END) == 0 );

    scene_extract_background();

    scene_compute_lut_fog();

    scene_backface_cull();

    vertex_buffer_unmap();

}

void pvr2_scene_finished( )

{

    vbuf->finished(vbuf);

}

/**

 * Dump the current scene to file in a (mostly) human readable form

 */

void pvr2_scene_print( FILE *f )

{

    int i,j;

    fprintf( f, "Polygons: %d\n", pvr2_scene.poly_count );

    for( i=0; i<pvr2_scene.poly_count; i++ ) {

        struct polygon_struct *poly = &pvr2_scene.poly_array[i];

        fprintf( f, "  %08X ", (uint32_t)(((unsigned char *)poly->context) - pvr2_main_ram) );

        switch( poly->vertex_count ) {

        case 3: fprintf( f, "Tri     " ); break;

        case 4: fprintf( f, "Quad    " ); break;

        default: fprintf( f,"%d-Strip ", poly->vertex_count-2 ); break;

        }

        fprintf( f, "%08X %08X %08X ", poly->context[0], poly->context[1], poly->context[2] );

        if( poly->mod_vertex_index != -1 ) {

            fprintf( f, "%08X %08X\n", poly->context[3], poly->context[5] );

        } else {

            fprintf( f, "\n" );

        }

        for( j=0; j<poly->vertex_count; j++ ) {

            struct vertex_struct *v = &pvr2_scene.vertex_array[poly->vertex_index+j];

            fprintf( f, "    %.5f %.5f %.5f, (%.5f,%.5f)  %.5f,%.5f,%.5f,%.5f  %.5f %.5f %.5f %.5f\n", v->x, v->y, v->z, v->u, v->v,

                     v->rgba[0], v->rgba[1], v->rgba[2], v->rgba[3],

                     v->offset_rgba[0], v->offset_rgba[1], v->offset_rgba[2], v->offset_rgba[3] );

        }

        if( poly->mod_vertex_index != -1 ) {

            fprintf( f, "  ---\n" );

            for( j=0; j<poly->vertex_count; j++ ) {

                struct vertex_struct *v = &pvr2_scene.vertex_array[poly->mod_vertex_index+j];

                fprintf( f, "    %.5f %.5f %.5f, (%.5f,%.5f)  %.5f,%.5f,%.5f,%.5f  %.5f %.5f %.5f %.5f\n", v->x, v->y, v->z, v->u, v->v,

                         v->rgba[0], v->rgba[1], v->rgba[2], v->rgba[3],

                         v->offset_rgba[0], v->offset_rgba[1], v->offset_rgba[2], v->offset_rgba[3] );

            }

        }

    }

}

void pvr2_scene_dump()

{

    pvr2_scene_print(stdout);

}