Subversion Repositories Kolibri OS

/*

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

	{

	// 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 ; jnumedges ; 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

	{

	// 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<

				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<

		}

	}

// 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

================

*/

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 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);

		}

	}

}