/*
Copyright (C) 1996-1997 Id Software, Inc.

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.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/
// r_bsp.c

#include "quakedef.h"
#include "r_local.h"

//
// current entity info
//
qboolean		insubmodel;
entity_t		*currententity;
vec3_t			modelorg, base_modelorg;
// modelorg is the viewpoint reletive to
// the currently rendering entity
vec3_t			r_entorigin;	// the currently rendering entity in world
// coordinates

float			entity_rotation[3][3];

vec3_t			r_worldmodelorg;

int				r_currentbkey;

typedef enum {touchessolid, drawnode, nodrawnode} solidstate_t;

#define MAX_BMODEL_VERTS	500			// 6K
#define MAX_BMODEL_EDGES	1000		// 12K

static mvertex_t	*pbverts;
static bedge_t		*pbedges;
static int			numbverts, numbedges;

static mvertex_t	*pfrontenter, *pfrontexit;

static qboolean		makeclippededge;


//===========================================================================

/*
================
R_EntityRotate
================
*/
void R_EntityRotate(vec3_t vec)
{
    vec3_t	tvec;

    VectorCopy(vec, tvec);
    vec[0] = DotProduct(entity_rotation[0], tvec);
    vec[1] = DotProduct(entity_rotation[1], tvec);
    vec[2] = DotProduct(entity_rotation[2], tvec);
}


/*
================
R_RotateBmodel
================
*/
void R_RotateBmodel(void)
{
    float	angle, s, c, temp1[3][3], temp2[3][3], temp3[3][3];

// TODO: should use a look-up table
// TODO: should really be stored with the entity instead of being reconstructed
// TODO: could cache lazily, stored in the entity
// TODO: share work with R_SetUpAliasTransform

// yaw
    angle = currententity->angles[YAW];
    angle = angle * M_PI*2 / 360;
    s = sin(angle);
    c = cos(angle);

    temp1[0][0] = c;
    temp1[0][1] = s;
    temp1[0][2] = 0;
    temp1[1][0] = -s;
    temp1[1][1] = c;
    temp1[1][2] = 0;
    temp1[2][0] = 0;
    temp1[2][1] = 0;
    temp1[2][2] = 1;


// pitch
    angle = currententity->angles[PITCH];
    angle = angle * M_PI*2 / 360;
    s = sin(angle);
    c = cos(angle);

    temp2[0][0] = c;
    temp2[0][1] = 0;
    temp2[0][2] = -s;
    temp2[1][0] = 0;
    temp2[1][1] = 1;
    temp2[1][2] = 0;
    temp2[2][0] = s;
    temp2[2][1] = 0;
    temp2[2][2] = c;

    R_ConcatRotations(temp2, temp1, temp3);

// roll
    angle = currententity->angles[ROLL];
    angle = angle * M_PI*2 / 360;
    s = sin(angle);
    c = cos(angle);

    temp1[0][0] = 1;
    temp1[0][1] = 0;
    temp1[0][2] = 0;
    temp1[1][0] = 0;
    temp1[1][1] = c;
    temp1[1][2] = s;
    temp1[2][0] = 0;
    temp1[2][1] = -s;
    temp1[2][2] = c;

    R_ConcatRotations(temp1, temp3, entity_rotation);

//
// rotate modelorg and the transformation matrix
//
    R_EntityRotate(modelorg);
    R_EntityRotate(vpn);
    R_EntityRotate(vright);
    R_EntityRotate(vup);

    R_TransformFrustum();
}


/*
================
R_RecursiveClipBPoly
================
*/
void R_RecursiveClipBPoly(bedge_t *pedges, mnode_t *pnode, msurface_t *psurf)
{
    bedge_t		*psideedges[2], *pnextedge, *ptedge;
    int			i, side, lastside;
    float		dist, frac, lastdist;
    mplane_t	*splitplane, tplane;
    mvertex_t	*pvert, *plastvert, *ptvert;
    mnode_t		*pn;

    psideedges[0] = psideedges[1] = NULL;

    makeclippededge = false;

// transform the BSP plane into model space
// FIXME: cache these?
    splitplane = pnode->plane;
    tplane.dist = splitplane->dist -
                  DotProduct(r_entorigin, splitplane->normal);
    tplane.normal[0] = DotProduct(entity_rotation[0], splitplane->normal);
    tplane.normal[1] = DotProduct(entity_rotation[1], splitplane->normal);
    tplane.normal[2] = DotProduct(entity_rotation[2], splitplane->normal);

// clip edges to BSP plane
    for (; pedges ; pedges = pnextedge) {
        pnextedge = pedges->pnext;

        // set the status for the last point as the previous point
        // FIXME: cache this stuff somehow?
        plastvert = pedges->v[0];
        lastdist = DotProduct(plastvert->position, tplane.normal) -
                   tplane.dist;

        if (lastdist > 0) {
            lastside = 0;
        } else {
            lastside = 1;
        }

        pvert = pedges->v[1];

        dist = DotProduct(pvert->position, tplane.normal) - tplane.dist;

        if (dist > 0) {
            side = 0;
        } else {
            side = 1;
        }

        if (side != lastside) {
            // clipped
            if (numbverts >= MAX_BMODEL_VERTS) {
                return;
            }

            // generate the clipped vertex
            frac = lastdist / (lastdist - dist);
            ptvert = &pbverts[numbverts++];
            ptvert->position[0] = plastvert->position[0] +
                                  frac * (pvert->position[0] -
                                          plastvert->position[0]);
            ptvert->position[1] = plastvert->position[1] +
                                  frac * (pvert->position[1] -
                                          plastvert->position[1]);
            ptvert->position[2] = plastvert->position[2] +
                                  frac * (pvert->position[2] -
                                          plastvert->position[2]);

            // split into two edges, one on each side, and remember entering
            // and exiting points
            // FIXME: share the clip edge by having a winding direction flag?
            if (numbedges >= (MAX_BMODEL_EDGES - 1)) {
                Con_Printf("Out of edges for bmodel\n");
                return;
            }

            ptedge = &pbedges[numbedges];
            ptedge->pnext = psideedges[lastside];
            psideedges[lastside] = ptedge;
            ptedge->v[0] = plastvert;
            ptedge->v[1] = ptvert;

            ptedge = &pbedges[numbedges + 1];
            ptedge->pnext = psideedges[side];
            psideedges[side] = ptedge;
            ptedge->v[0] = ptvert;
            ptedge->v[1] = pvert;

            numbedges += 2;

            if (side == 0) {
                // entering for front, exiting for back
                pfrontenter = ptvert;
                makeclippededge = true;
            } else {
                pfrontexit = ptvert;
                makeclippededge = true;
            }
        } else {
            // add the edge to the appropriate side
            pedges->pnext = psideedges[side];
            psideedges[side] = pedges;
        }
    }

// if anything was clipped, reconstitute and add the edges along the clip
// plane to both sides (but in opposite directions)
    if (makeclippededge) {
        if (numbedges >= (MAX_BMODEL_EDGES - 2)) {
            Con_Printf("Out of edges for bmodel\n");
            return;
        }

        ptedge = &pbedges[numbedges];
        ptedge->pnext = psideedges[0];
        psideedges[0] = ptedge;
        ptedge->v[0] = pfrontexit;
        ptedge->v[1] = pfrontenter;

        ptedge = &pbedges[numbedges + 1];
        ptedge->pnext = psideedges[1];
        psideedges[1] = ptedge;
        ptedge->v[0] = pfrontenter;
        ptedge->v[1] = pfrontexit;

        numbedges += 2;
    }

// draw or recurse further
    for (i=0 ; i<2 ; i++) {
        if (psideedges[i]) {
            // draw if we've reached a non-solid leaf, done if all that's left is a
            // solid leaf, and continue down the tree if it's not a leaf
            pn = pnode->children[i];

            // we're done with this branch if the node or leaf isn't in the PVS
            if (pn->visframe == r_visframecount) {
                if (pn->contents < 0) {
                    if (pn->contents != CONTENTS_SOLID) {
                        r_currentbkey = ((mleaf_t *)pn)->key;
                        R_RenderBmodelFace(psideedges[i], psurf);
                    }
                } else {
                    R_RecursiveClipBPoly(psideedges[i], pnode->children[i],
                                         psurf);
                }
            }
        }
    }
}


/*
================
R_DrawSolidClippedSubmodelPolygons
================
*/
void R_DrawSolidClippedSubmodelPolygons(model_t *pmodel)
{
    int			i, j, lindex;
    vec_t		dot;
    msurface_t	*psurf;
    int			numsurfaces;
    mplane_t	*pplane;
    mvertex_t	bverts[MAX_BMODEL_VERTS];
    bedge_t		bedges[MAX_BMODEL_EDGES], *pbedge;
    medge_t		*pedge, *pedges;

// FIXME: use bounding-box-based frustum clipping info?

    psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
    numsurfaces = pmodel->nummodelsurfaces;
    pedges = pmodel->edges;

    for (i=0 ; i<numsurfaces ; i++, psurf++) {
        // find which side of the node we are on
        pplane = psurf->plane;

        dot = DotProduct(modelorg, pplane->normal) - pplane->dist;

        // draw the polygon
        if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
                (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON))) {
            // FIXME: use bounding-box-based frustum clipping info?

            // copy the edges to bedges, flipping if necessary so always
            // clockwise winding
            // FIXME: if edges and vertices get caches, these assignments must move
            // outside the loop, and overflow checking must be done here
            pbverts = bverts;
            pbedges = bedges;
            numbverts = numbedges = 0;

            if (psurf->numedges > 0) {
                pbedge = &bedges[numbedges];
                numbedges += psurf->numedges;

                for (j=0 ; j<psurf->numedges ; j++) {
                    lindex = pmodel->surfedges[psurf->firstedge+j];

                    if (lindex > 0) {
                        pedge = &pedges[lindex];
                        pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[0]];
                        pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[1]];
                    } else {
                        lindex = -lindex;
                        pedge = &pedges[lindex];
                        pbedge[j].v[0] = &r_pcurrentvertbase[pedge->v[1]];
                        pbedge[j].v[1] = &r_pcurrentvertbase[pedge->v[0]];
                    }

                    pbedge[j].pnext = &pbedge[j+1];
                }

                pbedge[j-1].pnext = NULL;	// mark end of edges

                R_RecursiveClipBPoly(pbedge, currententity->topnode, psurf);
            } else {
                Sys_Error("no edges in bmodel");
            }
        }
    }
}


/*
================
R_DrawSubmodelPolygons
================
*/
void R_DrawSubmodelPolygons(model_t *pmodel, int clipflags)
{
    int			i;
    vec_t		dot;
    msurface_t	*psurf;
    int			numsurfaces;
    mplane_t	*pplane;

// FIXME: use bounding-box-based frustum clipping info?

    psurf = &pmodel->surfaces[pmodel->firstmodelsurface];
    numsurfaces = pmodel->nummodelsurfaces;

    for (i=0 ; i<numsurfaces ; i++, psurf++) {
        // find which side of the node we are on
        pplane = psurf->plane;

        dot = DotProduct(modelorg, pplane->normal) - pplane->dist;

        // draw the polygon
        if (((psurf->flags & SURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
                (!(psurf->flags & SURF_PLANEBACK) && (dot > BACKFACE_EPSILON))) {
            r_currentkey = ((mleaf_t *)currententity->topnode)->key;

            // FIXME: use bounding-box-based frustum clipping info?
            R_RenderFace(psurf, clipflags);
        }
    }
}


/*
================
R_RecursiveWorldNode
================
*/
void R_RecursiveWorldNode(mnode_t *node, int clipflags)
{
    int			i, c, side, *pindex;
    vec3_t		acceptpt, rejectpt;
    mplane_t	*plane;
    msurface_t	*surf, **mark;
    mleaf_t		*pleaf;
    double		d, dot;

    if (node->contents == CONTENTS_SOLID) {
        return;    // solid
    }

    if (node->visframe != r_visframecount) {
        return;
    }

// cull the clipping planes if not trivial accept
// FIXME: the compiler is doing a lousy job of optimizing here; it could be
//  twice as fast in ASM
    if (clipflags) {
        for (i=0 ; i<4 ; i++) {
            if (!(clipflags & (1<<i))) {
                continue;    // don't need to clip against it
            }

            // generate accept and reject points
            // FIXME: do with fast look-ups or integer tests based on the sign bit
            // of the floating point values

            pindex = pfrustum_indexes[i];

            rejectpt[0] = (float)node->minmaxs[pindex[0]];
            rejectpt[1] = (float)node->minmaxs[pindex[1]];
            rejectpt[2] = (float)node->minmaxs[pindex[2]];

            d = DotProduct(rejectpt, view_clipplanes[i].normal);
            d -= view_clipplanes[i].dist;

            if (d <= 0) {
                return;
            }

            acceptpt[0] = (float)node->minmaxs[pindex[3+0]];
            acceptpt[1] = (float)node->minmaxs[pindex[3+1]];
            acceptpt[2] = (float)node->minmaxs[pindex[3+2]];

            d = DotProduct(acceptpt, view_clipplanes[i].normal);
            d -= view_clipplanes[i].dist;

            if (d >= 0) {
                clipflags &= ~(1<<i);    // node is entirely on screen
            }
        }
    }

// if a leaf node, draw stuff
    if (node->contents < 0) {
        pleaf = (mleaf_t *)node;

        mark = pleaf->firstmarksurface;
        c = pleaf->nummarksurfaces;

        if (c) {
            do {
                (*mark)->visframe = r_framecount;
                mark++;
            } while (--c);
        }

        // deal with model fragments in this leaf
        if (pleaf->efrags) {
            R_StoreEfrags(&pleaf->efrags);
        }

        pleaf->key = r_currentkey;
        r_currentkey++;		// all bmodels in a leaf share the same key
    } else {
        // node is just a decision point, so go down the apropriate sides

        // find which side of the node we are on
        plane = node->plane;

        switch (plane->type) {
        case PLANE_X:
            dot = modelorg[0] - plane->dist;
            break;
        case PLANE_Y:
            dot = modelorg[1] - plane->dist;
            break;
        case PLANE_Z:
            dot = modelorg[2] - plane->dist;
            break;
        default:
            dot = DotProduct(modelorg, plane->normal) - plane->dist;
            break;
        }

        if (dot >= 0) {
            side = 0;
        } else {
            side = 1;
        }

        // recurse down the children, front side first
        R_RecursiveWorldNode(node->children[side], clipflags);

        // draw stuff
        c = node->numsurfaces;

        if (c) {
            surf = cl.worldmodel->surfaces + node->firstsurface;

            if (dot < -BACKFACE_EPSILON) {
                do {
                    if ((surf->flags & SURF_PLANEBACK) &&
                            (surf->visframe == r_framecount)) {
                        if (r_drawpolys) {
                            if (r_worldpolysbacktofront) {
                                if (numbtofpolys < MAX_BTOFPOLYS) {
                                    pbtofpolys[numbtofpolys].clipflags =
                                        clipflags;
                                    pbtofpolys[numbtofpolys].psurf = surf;
                                    numbtofpolys++;
                                }
                            } else {
                                R_RenderPoly(surf, clipflags);
                            }
                        } else {
                            R_RenderFace(surf, clipflags);
                        }
                    }

                    surf++;
                } while (--c);
            } else if (dot > BACKFACE_EPSILON) {
                do {
                    if (!(surf->flags & SURF_PLANEBACK) &&
                            (surf->visframe == r_framecount)) {
                        if (r_drawpolys) {
                            if (r_worldpolysbacktofront) {
                                if (numbtofpolys < MAX_BTOFPOLYS) {
                                    pbtofpolys[numbtofpolys].clipflags =
                                        clipflags;
                                    pbtofpolys[numbtofpolys].psurf = surf;
                                    numbtofpolys++;
                                }
                            } else {
                                R_RenderPoly(surf, clipflags);
                            }
                        } else {
                            R_RenderFace(surf, clipflags);
                        }
                    }

                    surf++;
                } while (--c);
            }

            // all surfaces on the same node share the same sequence number
            r_currentkey++;
        }

        // recurse down the back side
        R_RecursiveWorldNode(node->children[!side], clipflags);
    }
}



/*
================
R_RenderWorld
================
*/
extern qboolean r_drawskybox; // skyboxes
extern void R_EmitSkyBox(void);  // skyboxes
void R_RenderWorld(void)
{
    int			i;
    model_t		*clmodel;
    btofpoly_t	btofpolys[MAX_BTOFPOLYS];

    pbtofpolys = btofpolys;

    currententity = &cl_entities[0];
    VectorCopy(r_origin, modelorg);
    clmodel = currententity->model;
    r_pcurrentvertbase = clmodel->vertexes;

    R_RecursiveWorldNode(clmodel->nodes, 15);
    if (r_drawskybox) { // skyboxes
        R_EmitSkyBox();    // skyboxes
    }

// if the driver wants the polygons back to front, play the visible ones back
// in that order
    if (r_worldpolysbacktofront) {
        for (i=numbtofpolys-1 ; i>=0 ; i--) {
            R_RenderPoly(btofpolys[i].psurf, btofpolys[i].clipflags);
        }
    }
}


