Half Life Game Level Viewer

//
//	HFBSPGraph.cpp
//
//	Class to implement the ISceneGraph interface based on Half-Life BSP scene file.
//	This class uses the ICamera object to track player movement and look orientation in the 
//	BSP level and to render the scene from that perspective.  The BSPData class is used to
//	load a BSP level file and then to determine player collision with level geometry and 
//	entity models.  The BSPData class is also used to efficiently find all visible faces
//	to be rendered.  The IRenderer (via DX) object is used for face and texture rendering, 
//	including light map and optional flash light textures.  
//
//	Copyright 2005 Paul Higinbotham
//

#include "stdafx.h"
#include "..\..\memorymgr\PoolAllocator.h"			// Includes std C++ <new> and so uses throwing new operator
#include "HFBSPGraph.h"
#include "..\..\Renderer\DirectXRenderer\DXDefines.h"
#include "..\..\math\Plane.h"


using namespace ZGraphics;


// Constructor
HFBSPGraph::HFBSPGraph()
{
	m_pSGDX9Vertices = 0;
	//
	m_pCamera = 0;
	m_pRenderer = 0;
	//
	m_pCamLeaf = 0;
	//
	m_pD3DRenderCaps = 0;
	m_bSceneLoaded = false;
	m_bMultiTexCapable = false;
	m_bShaderCapable = false;
	m_bHaveVertexShader = false;
	//
	m_VisLeafs.SetSize(100);
	m_VisLeafs.SetGrowSize(50);
	m_VisFaces.SetSize(500);
	m_VisFaces.SetGrowSize(300);
	m_aIntersections.SetSize(20);
	m_aIntersections.SetGrowSize(20);
	//
	// Flash-light texture, transform info
	//
	m_bFlashlight = false;
	m_pDXFLTexture = 0;
	m_pDXNFLTexture = 0;
	m_nFLTextureSize = 128;
	m_mtxFLProjection.MakeZero();
	m_mtxFLProjection(0, 0) = 1.5f;		// f1, 1.7
	m_mtxFLProjection(1, 1) = 1.5f;		// f1, 1.7
	m_mtxFLProjection(2, 0) = 0.50f;
	m_mtxFLProjection(2, 1) = 0.50f;
	m_mtxFLProjection(2, 2) = 1.0f;
	m_mtxFLProjection(2, 3) = 1.0f;
	//
	m_pVertexShader1 = 0;
}

HFBSPGraph::~HFBSPGraph()
{
	_cleanup();
}


//
//	ISceneGraph public methods
//

// Loads scene data from provided bsp file name, creates global geometry data, and places
// camera at initial position.
bool HFBSPGraph::LoadScene(const char * pszFilename)
{
	// Clean up any earlier scene data
	_cleanUpScene();

	// Load scene data lumps from BSP file, create BSP tree data structure
	m_BSPData.LoadData(pszFilename);

	// Load textures from WAD file
	m_Textures.LoadWADTextures(m_BSPData);

	// Create single DX vertex list for all static data, and a map of faces to the list.
	// Also create all DX face textures, light-map and flash-light textures.
	_createStaticGeomData();

	// Find player start entity and place camera accordingly
	_placeCamera();

	m_bSceneLoaded = true;

	return m_bSceneLoaded;
}

void HFBSPGraph::SetCamera(ICamera * pCamera)
{
	m_pCamera = pCamera;
}

// Updates the camera position and look orientation based on the given
// time change (time delta).  Checks for camera (player) collision with level
// geometry and objects, and adjusts its position accordingly.
void HFBSPGraph::UpdateCamera(unsigned long ulTimeDeluSec)
{
	assert(m_pCamera);
	if (!m_pCamera)
		return;

	// Update camera orientation and position
	// ulTimeDel is in uSecs
	Vector3f vOldCamPos = m_pCamera->Position();
	const BSPNode * pOldCamLeaf = m_pCamLeaf;
	m_pCamera->Update(ulTimeDeluSec);

	// Adjust camera position to keep its bounding box inside world boundaries
	_adjustCamPosition(vOldCamPos);

	// Get the BSP level leaf node where the camera is.
	m_pCamLeaf = m_BSPData.FindLeaf(m_pCamera->Position());

	// The camera must stay within a valid empty leaf node.  If for some reason the camera
	// is in an invalid leaf, move it back to its previous position.
	if (m_pCamLeaf->nLeaf == 0)
	{
		m_pCamera->Position() = vOldCamPos;
		m_pCamLeaf = pOldCamLeaf;
	}

	// Make sure the camera frustrum is correctly computed for the final camera position
	m_pCamera->Update(0);
}

// Releases all IRenderer (D3D) objects.  Used for windowed/full-screen mode transitions.
void HFBSPGraph::ReleaseRenderObjects()
{
	m_pD3DRenderCaps = 0;
	m_pRenderer = 0;
	_releaseDXVertices();
	_releaseDXTextures();
	SAFE_RELEASE(m_pDXFLTexture);
	SAFE_RELEASE(m_pDXNFLTexture);

	if (m_pVertexShader1)
		m_pVertexShader1->ReleaseShader();
}

// Recreates all IRenderer (D3D) objects.  Used for windowed/full-screen mode transitions.
void HFBSPGraph::RestoreRenderObjects(IRenderer * pRenderer)
{
	SetRenderer(pRenderer);
	if (m_bSceneLoaded)
	{
		// Creates DX objects for scene vertex buffer and face/light-map, and flashlight textures
		_createStaticGeomData();
	}
}

void HFBSPGraph::ToggleFlashlight()
{
	m_bFlashlight = !m_bFlashlight;
}

// Receives an IRenderer object to be used for scene rendering.  Also enumerates renderer
// capabilities, compiles the vertex shader (if supported), and sets global render states.
void HFBSPGraph::SetRenderer(IRenderer * pRenderer)
{
	m_pRenderer = pRenderer;
	assert(m_pRenderer && m_pCamera);

	// Device capabilities
	m_pD3DRenderCaps = m_pRenderer->GetD3DCaps();
	m_bMultiTexCapable = (m_pD3DRenderCaps->MaxSimultaneousTextures > 2);
	m_bShaderCapable = m_pD3DRenderCaps->VertexShaderVersion >= D3DVS_VERSION(1,1);

	// Get and compile vertex shader if vs_11 is supported
	m_bHaveVertexShader = _setVertexShader();

	// Set world matrix, this only converts HL world coordinates to DX9 world coordinate space
	// For HL world, swap z = x, y = z, x = -y
	m_mtxWorld.MakeZero();
	m_mtxWorld(0, 2) = 1.0f;
	m_mtxWorld(1, 0) = -1.0f;
	m_mtxWorld(2, 1) = 1.0f;
	m_mtxWorld(3, 3) = 1.0f;
	m_pRenderer->SetTransform(D3DTS_WORLD, m_mtxWorld);

	// Set the projection matrix
	const ZView & cView = m_pCamera->GetView();
	m_pRenderer->CreateProjectionMatrixLH(m_mtxProjection, cView.AngleBeta(), cView.AspectRatio(), cView.NearPlaneDistance(), cView.FarPlaneDistance());
	m_pRenderer->SetTransform(D3DTS_PROJECTION, m_mtxProjection);

	// Set static renderer states
	m_pRenderer->SetRenderState(D3DRS_SPECULARENABLE,	FALSE);
	m_pRenderer->SetRenderState(D3DRS_LIGHTING,			FALSE);
	m_pRenderer->SetRenderState(D3DRS_ZENABLE,			TRUE);
	m_pRenderer->SetRenderState(D3DRS_FILLMODE,			D3DFILL_SOLID);
	m_pRenderer->SetRenderState(D3DRS_CULLMODE,			D3DCULL_CCW);
	m_pRenderer->SetRenderState(D3DRS_STENCILENABLE,	FALSE);
	m_pRenderer->SetRenderState(D3DRS_CLIPPING,			TRUE);
}

// Main rendering method.  Computes the new view matrix based on current camera orientation
// and renders scene.
void HFBSPGraph::Render()
{
	assert(m_pRenderer);
	assert(m_pCamLeaf);

	// Set the view (camera) matrix based on current camera world position
	Matrix4f mtxView;
	_createViewMatrix(mtxView, m_mtxWorld);
	m_pRenderer->SetTransform(D3DTS_VIEW, mtxView);

	HRESULT hr = m_pRenderer->Clear(0, 0, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER, 0xff303030, 1.0f, 0);
	hr = m_pRenderer->BeginScene();
	if (SUCCEEDED(hr))
	{
		// Render map and entity brush geometry.
		_setSGRenderStates();
		_renderStaticGeometry(mtxView);
		_renderEntities(mtxView);

		// (TODO) Render studio models

		m_pRenderer->EndScene();
	}

	m_pRenderer->Present(0, 0, 0, 0);
}


//
//	Internal methods
//

void HFBSPGraph::_cleanup()
{
	_cleanUpScene();
	DELETE_PTR(m_pVertexShader1);
}

void HFBSPGraph::_cleanUpScene()
{
	m_bSceneLoaded = false;
	_releaseDXTextures();
	_releaseDXVertices();
	SAFE_RELEASE(m_pDXFLTexture);
	SAFE_RELEASE(m_pDXNFLTexture);

	m_pCamLeaf = 0;
}

// Helper method to set renderer texture and sampler states for scene rendering.  Supports hardware
// with and without multi-texture capablitiy, however no multi-texture cap provides poorer experience.
// If multi-texture cap is present then three texture stages are used.  The first is to apply the 
// geometry texture, the second is to apply the lightmap texture, and the third applies the optional
// flashlight texture.
// If there is no multi-texture cap then the textures are applied in three rendering passes.
// Flashlight lightmap texture coordinates are computed in the vertex shader if supported, otherwise
// the flashlight projection matrix is used (but flashlight effect is not very realistic).
void HFBSPGraph::_setSGRenderStates()
{
	// @todo  Create state block for these settings

	// Multi-texturing light-map texture set up (if supported).
	if (m_bMultiTexCapable)
	{
		// Light-map texture
		m_pRenderer->SetTextureState(0, D3DTSS_TEXCOORDINDEX, 0);
		m_pRenderer->SetTextureState(0, D3DTSS_COLOROP,		D3DTOP_SELECTARG1);
		m_pRenderer->SetTextureState(0, D3DTSS_COLORARG1,	D3DTA_TEXTURE);
		m_pRenderer->SetSamplerState(0, D3DSAMP_MINFILTER,	D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(0, D3DSAMP_MAGFILTER,	D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(0, D3DSAMP_ADDRESSU,	D3DTADDRESS_CLAMP);
		m_pRenderer->SetSamplerState(0, D3DSAMP_ADDRESSV,	D3DTADDRESS_CLAMP);

		// Flashlight texture
		if (m_bHaveVertexShader)
		{
			// Let shader create the texture coordinates for flashlight (tex coord 1)
			m_pRenderer->SetTextureState(1, D3DTSS_TEXCOORDINDEX, 1);
			m_pRenderer->SetTextureState(1, D3DTSS_TEXTURETRANSFORMFLAGS, D3DTTFF_DISABLE);
		}
		else
		{
			// Auto-generate texture coordinates for tex stage 1
			m_pRenderer->SetTextureState(1, D3DTSS_TEXTURETRANSFORMFLAGS, D3DTTFF_COUNT3 | D3DTTFF_PROJECTED);
			m_pRenderer->SetTextureState(1, D3DTSS_TEXCOORDINDEX, D3DTSS_TCI_CAMERASPACEPOSITION);
			m_pRenderer->SetTransform(D3DTS_TEXTURE1, m_mtxFLProjection);
		}

		m_pRenderer->SetTextureState(1, D3DTSS_COLOROP,		D3DTOP_ADD);
		m_pRenderer->SetTextureState(1, D3DTSS_COLORARG1,	D3DTA_TEXTURE);
		m_pRenderer->SetTextureState(1, D3DTSS_COLORARG2,	D3DTA_CURRENT);
		m_pRenderer->SetSamplerState(1, D3DSAMP_MINFILTER,	D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(1, D3DSAMP_MAGFILTER,	D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(1, D3DSAMP_ADDRESSU,	D3DTADDRESS_CLAMP);
		m_pRenderer->SetSamplerState(1, D3DSAMP_ADDRESSV,	D3DTADDRESS_CLAMP);

		// Basic texture face texturing set up
		if (m_bHaveVertexShader)
		{
			m_pRenderer->SetTextureState(2, D3DTSS_TEXCOORDINDEX, 2);
		}
		else
		{
			m_pRenderer->SetTextureState(2, D3DTSS_TEXCOORDINDEX, 1);
		}
		m_pRenderer->SetTextureState(2, D3DTSS_COLOROP,		D3DTOP_MODULATE2X);
		m_pRenderer->SetTextureState(2, D3DTSS_COLORARG1,	D3DTA_TEXTURE);
		m_pRenderer->SetTextureState(2, D3DTSS_COLORARG2,	D3DTA_CURRENT);
		m_pRenderer->SetSamplerState(2, D3DSAMP_MINFILTER,	D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(2, D3DSAMP_MAGFILTER,	D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(2, D3DSAMP_MIPFILTER,	D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(2, D3DSAMP_ADDRESSU,	D3DTADDRESS_WRAP);
		m_pRenderer->SetSamplerState(2, D3DSAMP_ADDRESSV,	D3DTADDRESS_WRAP);
	}
	else
	{
		// Turn on texture blending for multi-pass texturing
		m_pRenderer->SetRenderState(D3DRS_ALPHABLENDENABLE, true);
		m_pRenderer->SetRenderState(D3DRS_SRCBLENDALPHA,	D3DBLEND_ONE);
		m_pRenderer->SetRenderState(D3DRS_DESTBLENDALPHA,	D3DBLEND_ZERO);

		// Basic texture face texturing set up
		m_pRenderer->SetSamplerState(0, D3DSAMP_MINFILTER, D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(0, D3DSAMP_MAGFILTER, D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(0, D3DSAMP_MIPFILTER, D3DTEXF_LINEAR);
		m_pRenderer->SetSamplerState(0, D3DSAMP_ADDRESSU,	D3DTADDRESS_WRAP);
		m_pRenderer->SetSamplerState(0, D3DSAMP_ADDRESSV,	D3DTADDRESS_WRAP);

		//m_pRenderer->SetTransform(D3DTS_TEXTURE0, m_mtxFLProjection);
	}
}

// Main method for rendering the static level geometry (everything but entity and character models).
// First potentially visible leafs are gathered from the BSP tree in an array in front to back order.  
// Next all potentially visible polygon faces are collected in an array object and this and used
// to do the actual rendering.
void HFBSPGraph::_renderStaticGeometry(const Matrix4f & mtxView)
{
	const Array<int> * pVisLeafs = _visibleLeafsFtoB();
	const Array<lface> * pVisFaces = _getFaces(pVisLeafs);

	_renderFaces(pVisFaces, mtxView, m_mtxWorld);
}

// Main method for rendering entity models.  Entity model objects are divided into to groups. 
// The first group are "solid" objects that player cannot pass through (collision detection is
// peformed with these objects), and are rendered without any transparency.
// The second group are "transparent" objects that the player can pass through (collision 
// detection is turned off for these objects), and are rendered with a small amount of transparency
// to indicate to the player that they can be passed through.
// Transparent objects can also be breakable windows, and in order to make transparency work correctly
// the non-transparent faces are rendered first and the transparent faces second, so that geometry
// and entities behind the transparent entity objects can be seen.
// Transparency is achieved by using the IRenderer (DX) alpha blending capabilities.
void HFBSPGraph::_renderEntities(const Matrix4f & mtxView)
{
	// Turn alpha blending state on
	m_pRenderer->SetRenderState(D3DRS_ALPHABLENDENABLE, true);
	m_pRenderer->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_SRCALPHA);
	m_pRenderer->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_INVSRCALPHA);
	m_pRenderer->SetRenderState(D3DRS_BLENDOP, D3DBLENDOP_ADD);

	// Set alpha channel
	m_pRenderer->SetTextureState(2, D3DTSS_ALPHAARG1, D3DTA_TEXTURE);
	m_pRenderer->SetTextureState(2, D3DTSS_ALPHAOP, D3DTOP_SELECTARG1);

	// First all opaque faces
	_renderEntFaces(false, mtxView);

	// Then all transparent faces
	_renderEntFaces(true, mtxView);

	// Turn off alpha blending state
	m_pRenderer->SetRenderState(D3DRS_ALPHABLENDENABLE, false);
}

// Main method for rendering either static geometry or entity model faces.  
// If multi-texturing is supported then each face is rendered in "one-pass", i.e., one call
// to the IRenderer DrawPrimitive method.  Otherwise three separate DrawPrimitive calls are
// made to apply each of the three texture maps (face texture, lightmap texture, optional
// flashlight lightmap texture).
void HFBSPGraph::_renderFaces(const Array<lface> * pFaces, const Matrix4f & mtxView, const Matrix4f & mtxWorld)
{
	// Set the vertex shader matrix constants
	if (m_pVertexShader1)
	{
		Matrix4f mtxWorldView = mtxWorld * mtxView;
		m_pVertexShader1->SetCTMatrix("WorldView", mtxWorldView);

		Matrix4f mtxWorldViewProj = mtxWorldView * m_mtxProjection;
		m_pVertexShader1->SetCTMatrix("WorldViewProj", mtxWorldViewProj);
	}

	if (m_bMultiTexCapable)
	{
		// Set up the flashlight texture
		if (m_bFlashlight)
			m_pRenderer->SetTexture(1, m_pDXFLTexture);		// Light map texture that illuminates scene.
		else
			m_pRenderer->SetTexture(1, m_pDXNFLTexture);	// Null light map texture that has no affect on scene.
	}

	// Render loop for static world models.
	IDirect3DTexture9 * pDXTexture = 0;
	int nMipTexLast = -1;
	for (int n=0; n<(int)pFaces->GetArrayCount(); n++)
	{
		int nMipTex = (*pFaces)[n].nMipTex;

		const bspf_face * pFace = &(m_BSPData.Faces()->m_pArray[pFaces->Get(n).nFaceIndex]);
		const int * pnVertIndex = m_SGFaceToVertex.IsInMap(pFaces->Get(n).nFaceIndex);
		assert(*pnVertIndex > -1);

		int nNumPrimitives = pFace->cEdges - 2;
		IDirect3DTexture9 * pDXLMTexture = _getLMTexture(pFace);

		// If multi-texturing in one pass is supported then include light-map texture blending.
		if (m_bMultiTexCapable)
		{
			// Light-map texture
			m_pRenderer->SetTexture(0, pDXLMTexture);

			// Surface texture.
			// Only get and set texture if it has changed.
			if (nMipTex != nMipTexLast)
			{
				pDXTexture = _getDXTexture(nMipTex);
				m_pRenderer->SetTexture(2, pDXTexture);
				nMipTexLast = nMipTex;
			}

			m_pRenderer->DrawPrimitive(D3DPT_TRIANGLEFAN, *pnVertIndex, nNumPrimitives);
		}
		else
		{
			// If we are not multi-texture capable.  Render in three passes, first for light-map,
			// next for flashlight, next for texture.

			// Light-map
			m_pRenderer->SetTexture(0, pDXLMTexture);
			m_pRenderer->SetTextureState(0, D3DTSS_TEXCOORDINDEX, 0);
			m_pRenderer->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_ONE);
			m_pRenderer->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_ZERO);
			m_pRenderer->SetSamplerState(0, D3DSAMP_ADDRESSU, D3DTADDRESS_CLAMP);
			m_pRenderer->SetSamplerState(0, D3DSAMP_ADDRESSV, D3DTADDRESS_CLAMP);
			m_pRenderer->DrawPrimitive(D3DPT_TRIANGLEFAN, *pnVertIndex, nNumPrimitives);

			/*
			// Flashlight
			if (m_bFlashlight)
				m_pRenderer->SetTexture(0, m_pDXFLTexture);
			else
				m_pRenderer->SetTexture(0, m_pDXNFLTexture);
			m_pRenderer->SetTextureState(0, D3DTSS_TEXTURETRANSFORMFLAGS, D3DTTFF_COUNT3 | D3DTTFF_PROJECTED);
			m_pRenderer->SetTextureState(0, D3DTSS_TEXCOORDINDEX, D3DTSS_TCI_CAMERASPACEPOSITION);
			m_pRenderer->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_DESTCOLOR);
			m_pRenderer->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_SRCCOLOR);
			m_pRenderer->DrawPrimitive(D3DPT_TRIANGLEFAN, *pnVertIndex, nNumPrimitives);
			*/

			// Texture
			pDXTexture = _getDXTexture(nMipTex);
			m_pRenderer->SetTexture(0, pDXTexture);
			m_pRenderer->SetTextureState(0, D3DTSS_TEXTURETRANSFORMFLAGS, D3DTTFF_DISABLE);
			m_pRenderer->SetTextureState(0, D3DTSS_TEXCOORDINDEX, 1);
			m_pRenderer->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_DESTCOLOR);
			m_pRenderer->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_SRCCOLOR);
			m_pRenderer->SetSamplerState(0, D3DSAMP_ADDRESSU, D3DTADDRESS_WRAP);
			m_pRenderer->SetSamplerState(0, D3DSAMP_ADDRESSV, D3DTADDRESS_WRAP);
			m_pRenderer->DrawPrimitive(D3DPT_TRIANGLEFAN, *pnVertIndex, nNumPrimitives);
		}
	}
}

// Creates the current camera view matrix and converts to DX9 coordinate space.
__forceinline void HFBSPGraph::_createViewMatrix(Matrix4f & mtxView, const Matrix4f & mtxWorld)
{
	// Create the view transformation matrix for DX9 coord space by first creating the view
	// transformation matrix in HL coord space and then transforming:
	// ViewMtx(DX9) = (Inv_WorldMatrix) * ViewMtx(HF) * (WorldMatrix)
	// where WorldMatrix is the matrix that transforms HL coordinates to DX9 coordinates
	m_pCamera->GetViewMatrix(mtxView);

	// Transform view matrix from HL coord space to DX coord space
	Matrix4f mtxWorld_Inv = mtxWorld.Transpose();	// World matrix is only rotations so inverse == transpose
	mtxView = mtxWorld_Inv * mtxView * mtxWorld;
}

// Method to collect all vertices from a given HL face structure, create a DX9 vertex structure,
// and then add these DX9 vertices to the provided vertex list.  
// The DX9 HFVERTEX structure, defined in IRenderer.h, specifies vertex coordinates, and two sets of 
// texture (u,v) coordinates.  The two texture coordinates are for the face texture and the lightmap 
// texture.  This method provides all of these coordinates for each face polygon vertex.  
// !!NOTE!! that an HFVERTEX structure passed to IRenderer is actually specified to have THREE texture
// coordinates, but only TWO are supplied in this method.  The third set of texture coordinates are
// for the flashlight lightmap texture and are provided by the vertex shader OR the m_mtxFLProjection
// projection matrix if a vertex shader is not supported.
// This method also creates a lightmap texture for the face and adds it to a map object to be
// used later during acutal rendering.
// Keep in mind that this method is not used during rendering of a scene but is called ONLY ONCE when 
// the bsp level is loaded and then this data is cached in the vertex list object.
void HFBSPGraph::_collectFaceVertices(const bspf_face * pFace, Array<HFVERTEX> * pVertexList)
{
	assert (pFace->cEdges > 1);

	// Get texutre information
	const bspf_textinfo * pTextInfo = &(m_BSPData.TextInfo()->m_pArray[pFace->nTextureInfo]);
	int nMipTex = pTextInfo->nMipTex;
	const bspf_miptex * pMipTex = m_BSPData.MipInfoPtr(nMipTex);

	// Walk through each face edge and triangularize
	// Assume a convex face and create a triangle fan
	// @todo  Look at making a triangle strip ... more efficient than a triangle fan.
	Vector3f v0, v1;
	float fUMin = 100000.0f;
	float fUMax = -10000.0f;
	float fVMin = 100000.0f;
	float fVMax = -10000.0f;
	int nStartIndex = (int)pVertexList->GetArrayCount();
	for (int nEdge=0; nEdge<pFace->cEdges; nEdge++)
	{
		_getEdgeVertices(v0, v1, pFace->nE1 + nEdge);

		// Add vertex information
		HFVERTEX vertex(v0);

		// Generate texture coordinates for face
		vertex.u =  v0[0] * pTextInfo->uAxis[0] + v0[1] * pTextInfo->uAxis[1] + v0[2] * pTextInfo->uAxis[2] + pTextInfo->uOffset;
		vertex.v =  v0[0] * pTextInfo->vAxis[0] + v0[1] * pTextInfo->vAxis[1] + v0[2] * pTextInfo->vAxis[2] + pTextInfo->vOffset;
		vertex.u /= (float)pMipTex->width;
		vertex.v /= (float)pMipTex->height;
		vertex.lu = vertex.u;
		vertex.lv = vertex.v;

		fUMin = (vertex.u < fUMin) ? vertex.u : fUMin;
		fUMax = (vertex.u > fUMax) ? vertex.u : fUMax;
		fVMin = (vertex.v < fVMin) ? vertex.v : fVMin;
		fVMax = (vertex.v > fVMax) ? vertex.v : fVMax;

		pVertexList->Add(vertex);
	}

	// Create a light-map texture for this face
	int nLMWidth = (int)(ceil((fUMax * pMipTex->width) / 16.0f) - floor((fUMin * pMipTex->width) / 16.0f) + 1.0f);
	int nLMHeight = (int)(ceil((fVMax * pMipTex->height) / 16.0f) - floor((fVMin * pMipTex->height) / 16.0f) + 1.0f);
	_createLMTexture(pFace, nLMWidth, nLMHeight);

	// Update light-map vertex u, v coordinates.  These should range from [0.0 -> 1.0] over face.
	float fUDel = (fUMax - fUMin);
	if (fUDel > Math<float>::cZeroTolerance)
		fUDel = 1.0f / fUDel;
	else
		fUDel = 1.0f;
	float fVDel = (fVMax - fVMin);
	if (fVDel > Math<float>::cZeroTolerance)
		fVDel = 1.0f / fVDel;
	else
		fVDel = 1.0f;
	for (int n=nStartIndex; n<(int)pVertexList->GetArrayCount(); n++)
	{
		(*pVertexList)[n].lu = ((*pVertexList)[n].lu - fUMin) * fUDel;
		(*pVertexList)[n].lv = ((*pVertexList)[n].lv - fVMin) * fVDel;
	}

	// Adjust texture coordinates so that they always begin inside [0.0 -> 1.0].
	float fFrac;
	fFrac = modf(fUMin, &fUMin);
	if (fUMin < 0.0f && fabs(fFrac) > 0.0001f)
		fUMin -= 1.0f;
	fFrac = modf(fVMin, &fVMin);
	if (fVMin < 0.0f && fabs(fFrac) > 0.0001f)
		fVMin -= 1.0f;

	for (n=nStartIndex; n<(int)pVertexList->GetArrayCount(); n++)
	{
		(*pVertexList)[n].u = (*pVertexList)[n].u - fUMin;
		(*pVertexList)[n].v = (*pVertexList)[n].v - fVMin;
	}
}

// Helper method to get the two vertex points associated with the given edge reference, 
// where the two vertices are in the correct winding order (v1 -> v2).
__forceinline void HFBSPGraph::_getEdgeVertices(Vector3f & v1, Vector3f & v2, int nEdge)
{
	// Get the edge index for this face.
	int nEdgeIndex = (int)m_BSPData.FaceEdges()->m_pArray[nEdge];
	short nV1, nV2;
	const bspf_edge * pEdge;

	// Get the vertex indices in the correct winding order.
	if (nEdgeIndex < 0)
	{
		pEdge = &(m_BSPData.Edges()->m_pArray[-nEdgeIndex]);
		nV1 = pEdge->nV2;
		nV2 = pEdge->nV1;
	}
	else
	{
		pEdge = &(m_BSPData.Edges()->m_pArray[nEdgeIndex]);
		nV1 = pEdge->nV1;
		nV2 = pEdge->nV2;
	}

	// Get the actual vertex points.
	for (int n=0; n<3; n++)
	{
		v1[n] = m_BSPData.Vertices()->m_pArray[nV1].fPoint[n];
		v2[n] = m_BSPData.Vertices()->m_pArray[nV2].fPoint[n];
	}
}

// Get the face texture from the reference index.  All face textures should be in the
// m_DXTextures map object since they were pre-loaded at level load time.
IDirect3DTexture9 * HFBSPGraph::_getDXTexture(int nMipTex)
{
	// Check to see if DX (device ready) texture has already been created and is in map
	IDirect3DTexture9 * pDXTexture = 0;
	IDirect3DTexture9 *const * ppDXTexture = m_DXTextures.IsInMap(nMipTex);

	if (ppDXTexture)
	{
		// Found
		pDXTexture = const_cast<IDirect3DTexture9 *>(*ppDXTexture);
		assert(pDXTexture);
	}
	else
	{
		assert(0);
	}

	return pDXTexture;
}

// Method to look up the RGB texture for this face, convert it to DX compatible texture data, and
// add it to the DX texture map object.
void HFBSPGraph::_createDXTexture(const bspf_face * pFace)
{
	const bspf_textinfo * pTextInfo = &(m_BSPData.TextInfo()->m_pArray[pFace->nTextureInfo]);
	int nMipTex = pTextInfo->nMipTex;

	IDirect3DTexture9 * const * ppDXTexture = m_DXTextures.IsInMap(nMipTex);
	if (ppDXTexture)
		return;

	// If not found then create DX texture from WAD RGB texture
	const wtexture * pWTexture = m_Textures.GetWTexture(nMipTex);
	assert(pWTexture);

	// Create the DX texture
	rgbtex RGBTex = pWTexture->RGBTexture;
	IDirect3DTexture9 * pDXTexture;
	pDXTexture = m_pRenderer->GetTexture((BYTE *)(RGBTex.pRGBTex), 0, D3DUSAGE_AUTOGENMIPMAP, D3DFMT_A8R8G8B8, RGBTex.nWidth, RGBTex.nHeight);
	assert(pDXTexture);

	// Add texture to map
	m_DXTextures.Add(nMipTex, pDXTexture);
}

// Method to create DX compatible flash light textures, one texture illuminates and the other does nothing.
void HFBSPGraph::_createFLDXTexture()
{
	SAFE_RELEASE(m_pDXFLTexture);
	SAFE_RELEASE(m_pDXNFLTexture);

	unsigned long * pRGBFLTexture;
	unsigned long * pRGBNFLTexture;

	m_Textures.CreateFLTextures(&pRGBFLTexture, &pRGBNFLTexture, m_nFLTextureSize);

	// Next create the DX device texture object
	m_pDXFLTexture = m_pRenderer->GetTexture((BYTE *)(pRGBFLTexture), 1, 0, D3DFMT_X8R8G8B8, m_nFLTextureSize, m_nFLTextureSize);
	assert(m_pDXFLTexture);

	m_pDXNFLTexture = m_pRenderer->GetTexture((BYTE *)(pRGBNFLTexture), 1, 0, D3DFMT_X8R8G8B8, m_nFLTextureSize, m_nFLTextureSize);
	assert(m_pDXNFLTexture);

	// clean up
	DELETE_PTR(pRGBFLTexture);
	DELETE_PTR(pRGBNFLTexture);

	/*
	// @test
	HRESULT hr = m_pRenderer->SaveTextureToFile("flashTexture.bmp", m_pDXFLTexture, D3DXIFF_BMP);
	*/
}

// Get the light map texture for given face.  All face light map textures should be in the
// m_DXLMTextures map object since they were pre-loaded at level load time.
IDirect3DTexture9 * HFBSPGraph::_getLMTexture(const bspf_face * pFace)
{
	// Check to see if DX (device ready) LM texture has already been created and is in map
	IDirect3DTexture9 * pDXLMTexture = 0;
	IDirect3DTexture9 *const * ppDXLMTexture = m_DXLMTextures.IsInMap(pFace->nLightMapOfs);

	if (ppDXLMTexture)
	{
		// Found
		pDXLMTexture = const_cast<IDirect3DTexture9 *>(*ppDXLMTexture);
		assert(pDXLMTexture);
	}

	return pDXLMTexture;
}

// Helper method to create a DX compatible RGB light map texture for the given face, and add
// it to the light map texture map object.
void HFBSPGraph::_createLMTexture(const bspf_face * pFace, int nLMWidth, int nLMHeight)
{
	if ( unsigned long * pLMRGBTexture = m_Textures.CreateLMTexture(m_BSPData, pFace, nLMWidth, nLMHeight) )
	{
		if (m_DXLMTextures.IsInMap(pFace->nLightMapOfs) == 0)
		{
			// Next create a DX device texture
			IDirect3DTexture9 * pDXLMTexture = m_pRenderer->GetTexture((BYTE *)(pLMRGBTexture), 1, 0, D3DFMT_X8R8G8B8, nLMWidth, nLMHeight);
			assert(pDXLMTexture);

			// Add LM texture to map
			m_DXLMTextures.Add(pFace->nLightMapOfs, pDXLMTexture);
		}

		DELETE_ARRAY_PTR(pLMRGBTexture);
	}
}

// Method to create all non-changing data for the current loaded bsp level.  This includes an array
// object containing all vertex information for the level (and which is IRenderer (DX) compatible), 
// all face textures, all face light map textures, and the flashlight light map texture.
// Note that IRenderer (DX) vertex information includes vertex, and texture coordinates for all
// textures applied.  See definition of HFVERTEX in IRenderer.h file.
void HFBSPGraph::_createStaticGeomData()
{
	assert(m_pRenderer);

	// Prepare array of face indices to DX vertex indices
	m_SGFaceToVertex.Clear();
	m_SGFaceToVertex.SetSize(5000);
	m_SGFaceToVertex.SetGrowSize(1000);
	m_SGFaceToVertex.SetCompareFn(CompareIntSet);

	// Prepare array for DX device ready textures
	m_DXTextures.Clear();
	m_DXTextures.SetSize(200);
	m_DXTextures.SetCompareFn(CompareIntSet);

	// Prepare array for LightMap (LM) DX device ready textures
	m_DXLMTextures.Clear();
	m_DXLMTextures.SetSize(200);
	m_DXLMTextures.SetCompareFn(CompareIntSet);

	// Start by creating an array of vertices and a map from face index to vertex index.
	// Also create the texture and light-map for this face.
	Array<HFVERTEX> m_Vertices(20000);
	m_Vertices.SetGrowSize(5000);
	for (int n=0; n<m_BSPData.Faces()->m_cSize; n++)
	{
		const bspf_face * pFace = &(m_BSPData.Faces()->m_pArray[n]);
		m_SGFaceToVertex.Add(n, (int)m_Vertices.GetArrayCount());	// Add face index and vertex array index to map

		_collectFaceVertices(pFace, &m_Vertices);					// Get face vertices and create face light-map

		_createDXTexture(pFace);									// Create DX textures
	}

	// Creates the DX flash-light texture
	_createFLDXTexture();

	// Create new DX9 vertex buffer to hold all face vertices for static geometry
	SAFE_RELEASE(m_pSGDX9Vertices);
	m_pRenderer->CreateVertexBuffer(&m_Vertices, &m_pSGDX9Vertices);
	m_pRenderer->SetStreamSource(0, m_pSGDX9Vertices, 0);
}

// Method to initially place the camera in the current bsp level.  The starting location of 
// the camera (and player) is determined by the "info_player_start" entity class.
void HFBSPGraph::_placeCamera()
{
	const EntVars * pEnt = m_BSPData.FindEntity(cString("info_player_start"));
	if (pEnt)
	{
		m_pCamera->Position() = pEnt->vOrigin;
		m_pCamera->SetYawAngle(pEnt->fYawAngle);
	}
	else
	{
		throw "Error:  Unable to find player starting position for this level.";
	}

	m_pCamera->SetCrouched(false);

	// Make sure camera is not embedded in floor
	_adjustCamPosition(Vector3f::cZero, true);
}

// Step height defines maximum height player will automatically step up without first jumping.
static float s_fStepHeight = 18.0f;

// Compute the center point of a given bounding box.
__forceinline Vector3f _computeCenterPt(const Vector3f vBB[2])
{
	Vector3f ptCenter;
	ptCenter[0] = (vBB[1][0] - vBB[0][0]) / 2.0f + vBB[0][0];
	ptCenter[1] = (vBB[1][1] - vBB[0][1]) / 2.0f + vBB[0][1];
	ptCenter[2] = (vBB[1][2] - vBB[0][2]) / 2.0f + vBB[0][2];

	return ptCenter;
}

// Computes the difference vector along a plane normal.  Used to find adjustment vector to avoid
// collision to a face.
__forceinline Vector3f _computeDiffVector(const Planef fPlane, const Vector3f & ptIntersect, const Vector3f & ptTest)
{
	return fPlane.Normal() * (fPlane.Normal().Dot((ptIntersect - ptTest)));
}

// Shrinks a bounding box in all directions by given amount value.
__forceinline void _shrinkVBB(Vector3f vBB[2], float fAmount)
{
	Vector3f vAmount(fAmount, fAmount, fAmount);
	vBB[0] += vAmount;
	vBB[1] -= vAmount;
}

// Structure to hold plane normal information, includes normal vector and depth of penetration.
struct PlaneNormal
{
	float		fDepth;
	Vector3f	vNormal;

	PlaneNormal()
	{
		fDepth = 0.0f;
	}
	PlaneNormal(float fDpth, Vector3f const& vNorm)
	{
		fDepth = fDpth;
		vNormal = vNorm;
	}
};

// Helper function to remove any z component in the intersection plane and then re-normalize
// the plane normal vector and recompute the intersection distance (penetration depth).
void _adjustPlaneForZ(SectInfo& sectInfo)
{
	Planef& fPlane = sectInfo.fPlane;
	if ( fabs(fPlane.Normal()[2]) > 0.01f )
	{
		fPlane.Normal()[2] = 0.0f;
		fPlane.Normal().Normalize();

		Vector3f ptIntersect = sectInfo.ptIntersect;
		fPlane.Distance() = sqrt( ptIntersect[0]*ptIntersect[0] + ptIntersect[1]*ptIntersect[2] );
	}
}

// Helper function to look at array of bounding box intersections and remove items that are
// uninteresting for lateral intersections (recall that z coordinate is the vertical in HL
// world).
// Also checks to see if any two intersection planes are positioned in a concave manner,
// and if so returns true.
bool _cleanUpData(Array<SectInfo> & aIntersections, Vector3f const& vPosDir)
{
	for ( int j=(int)aIntersections.GetArrayCount()-1; j>=0; --j )
	{
		// Remove nonsense intersection planes
		SectInfo & sectInfo = aIntersections[j];
		if ( sectInfo.fDepth < 0.01f || sectInfo.fPlane.Normal().Dot( vPosDir ) >= 0.0f)
		{
			aIntersections.Remove(j);
		}
		else
		{
			// Remove Z component from planes
			_adjustPlaneForZ(sectInfo);
		}
	}

	if ( aIntersections.GetArrayCount() == 0 )
		return false;

	// Look for concave planes
	for ( j=0; j<(int)aIntersections.GetArrayCount(); ++j )
	{
		SectInfo& sectInfo1 = aIntersections[j];

		for ( int n=j+1; n<(int)aIntersections.GetArrayCount(); ++n )
		{
			SectInfo& sectInfo2 = aIntersections[n];
			float fDot = sectInfo1.fPlane.Normal().Dot( sectInfo2.fPlane.Normal() );
			if ( fDot < 0.90f )
			{
				float t1 = sectInfo1.fPlane.TestPoint( sectInfo2.ptIntersect );
				float t2 = sectInfo2.fPlane.TestPoint( sectInfo1.ptIntersect );
				if ( t1 >= 0.0f || t2 >= 0.0f )
				{
					// Found planes forming a concave shape
					return true;
				}
			}
		}
	}

	return false;
}

// Helper function to check the intersections data for concave planes where bounding box
// intersections occurred.  If any are found then this function returns true and means
// that the camera (player) cannot be moved from keyboard commands and must remain
// where it is.
bool _checkForIntersections(Array<SectInfo> & aIntersections, Vector3f const& vPosDir)
{
	// Clean up data and look for concave intersection
	if ( _cleanUpData(aIntersections, vPosDir) )
	{
		return true;
	}

	// Check for any valid multiple plane intersection, where planes are almost perpendicular
	size_t ncount = aIntersections.GetArrayCount();
	if ( ncount > 1 )
	{
		for (size_t n=0; n<ncount; ++n)
		{
			for (size_t m=n+1; m<ncount; ++m)
			{
				SectInfo sectInfo1 = aIntersections[n];
				SectInfo sectInfo2 = aIntersections[m];
				float fDot = sectInfo1.fPlane.Normal().Dot( sectInfo2.fPlane.Normal() );
				if ( (fabs(fDot) < 0.30f) && (sectInfo1.fDepth > 0.01f && sectInfo2.fDepth > 0.01f) )
				{
					return true;
				}
			}
		}
	}

	return false;
}

// This is the main method adjusts the camera (player) position based on whether any intersections
// of the camera bounding box into "solid space" is found.  This method uses the BSPData class 
// geometry/entity intersection functions to determine if the camera is being moved into solid
// space, and if so computes an adjustment to the camera so that it stays in empty space.
// Collisions are tested in three main areas:
//  a) Collisions during camera lateral motion.
//  b) Collisions of the camera with the ground.
//  c) Collisions of the camera with the ceiling.
// Special adjustments are made for:
//  a) Lateral collision with two faces forming a concave shape (in which case the camera cannot move).
//  b) Collision with the ground while moving along the ground.
//  c) Allow motion along the non-level ground (allow a ramp of about 45 deg or less).
//  d) Allow automatic step up a set height change (s_fStepHeight).
//  e) Allow jump action only when camera is on ground.
//  f) Disallow rise from crouch if insufficient height.
// This code works reasonably well but is far from perfect.  This code is a result of a lot of
// experimentation and has become pretty messy.  Some effort should be made to clean this code up, 
// probably by re-thinking and re-writing most of it.
void HFBSPGraph::_adjustCamPosition(const Vector3f & ptCamOld, bool bIgnoreStep)
{
	Vector3f vBB[2];

	//
	// First check for lateral intersection adjustments
	//

	Vector3f vPosDelta(m_pCamera->Position() - ptCamOld);
	if ( vPosDelta.MagSquared() > 0.001f )
	{
		m_pCamera->GetBB(vBB);
		Vector3f ptCamera = _computeCenterPt(vBB);
		vBB[0][2] += s_fStepHeight;
		Vector3f vPosDir = vPosDelta; vPosDir.Normalize();

		// Collect intersection data, if any.
		m_aIntersections.Clear();
		m_BSPData.BBIntersectGeometry(vBB, m_aIntersections);
		m_BSPData.BBIntersectEntities(ptCamera, vBB, m_aIntersections);

		if ( _cleanUpData(m_aIntersections, vPosDir) )
		{
			// We found two concave planes.  Disallow lateral movement
			m_aIntersections.Clear();
			m_pCamera->Position() = ptCamOld;
		}

		// Skip this work if no lateral intersections were found.
		if ( m_aIntersections.GetArrayCount() > 0 )
		{
			Array<PlaneNormal> aNormals; aNormals.SetSize(m_aIntersections.GetArrayCount());
			while ( m_aIntersections.GetArrayCount() > 0 )
			{
				SectInfo sectInfo(m_aIntersections[0]);
				m_aIntersections.Remove(0);

				// Combine similar plane orientations and create set of plane normals for intersection
				for ( int n=(int)m_aIntersections.GetArrayCount()-1; n>=0; --n )
				{
					SectInfo& sectInfo2 = m_aIntersections[n];
					float fDot = sectInfo.fPlane.Normal().Dot( sectInfo2.fPlane.Normal() );

					// Check for plane with same orientation
					if ( (fDot > 0.99f && fDot < 1.01f) )
					{
						sectInfo.fDepth = (sectInfo2.fDepth > sectInfo.fDepth) ? sectInfo2.fDepth : sectInfo.fDepth;
						sectInfo.ptIntersect = (sectInfo.ptIntersect+sectInfo2.ptIntersect) / 2.0f;
						m_aIntersections.Remove(n);
						continue;
					}
				}

				// Save plane normal
				if ( sectInfo.fDepth > 0.0f )
					aNormals.Add( PlaneNormal(sectInfo.fDepth, sectInfo.fPlane.Normal()) );
			}

			if ( aNormals.GetArrayCount() > 0 )
			{
				// Add all plane normals together.
				Vector3f vNormal = Vector3f::cZero;
				float fDepth = 0.0f;
				for ( int n=0; n<(int)aNormals.GetArrayCount(); ++n )
				{
					vNormal += aNormals[n].vNormal;
					fDepth = (fDepth > aNormals[n].fDepth) ? fDepth : aNormals[n].fDepth;
				}
				vNormal.Normalize();

				float fPosDepth = vNormal.Dot(-vPosDelta);

				// Increase fPosDepth if we are moving in the Z direction (HACK)
				float fZMove = fabs(vPosDelta[2]);
				if (fZMove > 0.0f)
					fPosDepth += fZMove;

				fDepth = (fPosDepth < fDepth) ? fPosDepth : fDepth;
				m_pCamera->Position() += (vNormal * fDepth);

				if (!bIgnoreStep)
				{
					// Check camera movement to ensure it doesn't bring the BB into a collision with concave shapes
					m_pCamera->GetBB(vBB);
					Vector3f ptCamera = _computeCenterPt(vBB);
					vBB[0][2] += s_fStepHeight;
					m_aIntersections.Clear();
					m_BSPData.BBIntersectGeometry(vBB, m_aIntersections);
					m_BSPData.BBIntersectEntities(ptCamera, vBB, m_aIntersections);

					if ( _checkForIntersections(m_aIntersections, vPosDir) )
					{
						m_pCamera->Position() = ptCamOld;
					}
				}
			}
		}
	}

	//
	// Test camera bottom for intersection with floor.
	//
	Vector3f ptStart, ptTest, ptIntersect, ptIntSect;
	Planef fPlane;
	m_pCamera->GetBB(vBB);
	_shrinkVBB(vBB, 2.0f);
	Vector3f ptCenter = _computeCenterPt(vBB);
	float fZDiff = 0.0f;
	int nx, ny;

	// Check corners
	for (nx=0; nx<2; nx++)
	{
		for (ny=0; ny<2; ny++)
		{
			ptStart = Vector3f(vBB[nx][0], vBB[ny][1], vBB[1][2]);
			ptTest = Vector3f(vBB[nx][0], vBB[ny][1], vBB[0][2]);

			// Static geometry
			if ( m_BSPData.RayIntersectFace(ptStart, ptTest, fPlane, ptIntersect) )
			{
				// Only account for true floor surfaces, including ramps
				if (fPlane.Normal()[2] > 0.70f)
				{
					Vector3f ptTemp = _computeDiffVector(fPlane, ptIntersect, ptTest);
					if (fZDiff == 0.0f)
					{
						ptIntSect = ptIntersect;
						fZDiff = ptTemp[2];
					}
					else if (ptTemp[2] < fZDiff)
					{
						ptIntSect = ptIntersect;
						fZDiff = ptTemp[2];
					}
				}
			}

			// Entity model geometry
			m_BSPData.IntersectEntBB(ptStart, ptTest, vBB, m_aIntersections);
			for (int n=0; n<(int)m_aIntersections.GetArrayCount(); n++)
			{
				fPlane = m_aIntersections[n].fPlane;
				ptIntersect = m_aIntersections[n].ptIntersect;
				if (fPlane.Normal()[2] > 0.70f)
				{
					Vector3f ptTemp = _computeDiffVector(fPlane, ptIntersect, ptTest);
					if (fZDiff == 0.0f)
					{
						ptIntSect = ptIntersect;
						fZDiff = ptTemp[2];
					}
					else if (ptTemp[2] < fZDiff)
					{
						ptIntSect = ptIntersect;
						fZDiff = ptTemp[2];
					}
				}
			}
		}
	}

	// Check center of camera volume
	ptStart = Vector3f(ptCenter[0], ptCenter[1], vBB[1][2]);
	ptTest = Vector3f(ptCenter[0], ptCenter[1], vBB[0][2]);
	if ( m_BSPData.RayIntersectFace(ptStart, ptTest, fPlane, ptIntersect) )
	{
		// Only account for true floor surfaces, including ramps
		if (fPlane.Normal()[2] > 0.70f)
		{
			Vector3f ptTemp = _computeDiffVector(fPlane, ptIntersect, ptTest);
			if (fZDiff == 0.0f)
			{
				ptIntSect = ptIntersect;
				fZDiff = ptTemp[2];
			}
			else if (ptTemp[2] < fZDiff)
			{
				ptIntSect = ptIntersect;
				fZDiff = ptTemp[2];
			}
		}
	}

	bool bBottomIntersect = false;
	if (fZDiff > 0.0f)
	{
		// We have a floor collision.
		if (bIgnoreStep || fZDiff < s_fStepHeight)
		{
			// Adjust camera to remain above the floor.
			m_pCamera->Position()[2] += fZDiff;
			m_pCamera->GetBB(vBB);
			_shrinkVBB(vBB, 2.0f);
			m_pCamera->StopJump();
		}
		// Otherwise ran into something too large for a stair step.  May be a desk so don't
		// adjust camera height to be on top.
		bBottomIntersect = true;
	}

	// If not bottom intersection then we may be above the floor and need to fall.
	bool bOnFloor = bBottomIntersect;
	if (!bBottomIntersect)
	{
		// Test point in center (x/y) of camera BB
		ptStart = ptCenter;
		ptTest = ptCenter;
		ptTest[2] = vBB[0][2] - 0.5f;
		if ( m_BSPData.RayIntersectFace(ptStart, ptTest, fPlane, ptIntersect) )
		{
			bOnFloor = true;
		}
		
		if (!bOnFloor)
		{
			m_pCamera->StartFall();
		}
	}
	m_pCamera->SetCamOnFloor(bOnFloor);

	//
	// Check for top intersection
	//
	m_pCamera->GetBB(vBB);
	_shrinkVBB(vBB, 2.0f);
	ptCenter = _computeCenterPt(vBB);
	fZDiff = 0.0f;
	bool bAllPoints = true;
	for (nx=0; nx<2; nx++)
	{
		for (ny=0; ny<2; ny++)
		{
			ptStart = Vector3f(vBB[nx][0], vBB[ny][1], vBB[0][2]);
			ptTest = Vector3f(vBB[nx][0], vBB[ny][1], vBB[1][2]);

			// Static geometry
			if ( m_BSPData.RayIntersectFace(ptStart, ptTest, fPlane, ptIntersect) )
			{
				Vector3f ptTemp = _computeDiffVector(fPlane, ptIntersect, ptTest);
				if (ptTemp[2] < fZDiff)
				{
					fZDiff = ptTemp[2];
					ptIntSect = ptIntersect;
				}
			}
			else
			{
				// Entity model geometry
				m_BSPData.IntersectEntBB(ptStart, ptTest, vBB, m_aIntersections);
				int nCount = (int)m_aIntersections.GetArrayCount();
				bAllPoints = nCount > 0;
				for (int n=0; n<nCount; n++)
				{
					fPlane = m_aIntersections[n].fPlane;
					ptIntersect = m_aIntersections[n].ptIntersect;
					Vector3f ptTemp = _computeDiffVector(fPlane, ptIntersect, ptTest);
					if (ptTemp[2] < fZDiff)
					{
						fZDiff = ptTemp[2];
						ptIntSect = ptIntersect;
					}
				}
			}
		}
	}
	if (!bAllPoints)
	{
		// Check center point
		ptStart = ptCenter;
		ptTest = ptCenter;
		ptTest[2] = vBB[1][2];
		if ( m_BSPData.RayIntersectFace(ptStart, ptTest, fPlane, ptIntersect) )
		{
			Vector3f ptTemp = _computeDiffVector(fPlane, ptIntersect, ptTest);
			fZDiff = ptTemp[2];
			ptIntSect = ptIntersect;
		}
		else
			fZDiff = 0.0f;
	}
	if (fZDiff < 0.0f)
	{
		// We have a ceiling collision.
		if (bAllPoints && (bBottomIntersect || bOnFloor))
		{
			// If we also have a floor collision we don't have enough room and need to crouch
			// m_pCamera->HandleTooTall(-fZDiff);
			m_pCamera->Position() = ptCamOld;
		}
		else
		{
			// Otherwise adjust camera position down to clear ceiling.
			m_pCamera->Position()[2] += fZDiff;
		}

		m_pCamera->LimitJump();
		m_pCamera->StopLevitate();
	}
	else if (m_pCamera->IsCrouched())
	{
		// No top intersection.  If we are currently crouched then see if there is enough room to rise.
		ptStart = ptCenter;
		ptTest = ptCenter;
		ptTest[2] = vBB[0][2] + m_pCamera->GetUprightHeight();
		if ( !m_BSPData.RayIntersectFace(ptStart, ptTest, fPlane, ptIntersect) )
		{
			// Clear to rise.
			m_pCamera->StartRise();
		}
	}
}

// Walks the BSP tree, starting from the leaf where the camera currently resides, and collects all
// potentially visible leaf nodes (recall that the BSP tree leaf nodes contain the faces to render).
// The walking of the tree is done recursively.
// Non visible leafs are rejected by:
//  a) Rejecting large parts of the BSP tree that are outside the viewing frustum.
//	b) Rejecting any remaining leaf nodes that are not part of the PVS (potentially visible set).
const Array<int> * HFBSPGraph::_visibleLeafsFtoB()
{
	assert(m_pCamLeaf);

	m_VisLeafs.Clear();

	// Get visibility set for this leaf
	const unsigned char * pVisSet = m_BSPData.VisSet(m_BSPData.Leafs()->m_pArray[m_pCamLeaf->nLeaf].ofsCluster);
	assert(pVisSet);

	// Walk BSP tree front to back, culling nodes outside camera frustum, collecting faces to draw
	// only in visible leaves (using PVS).
	const BSPNode * pCurrNode = m_pCamLeaf;
	const BSPNode * pParent = m_pCamLeaf->pParent;
	_collectLeafsFtoB_r(pCurrNode, &m_VisLeafs, pVisSet);
	while (pParent)
	{
		if (pParent->pFront == pCurrNode)
		{
			_collectLeafsFtoB_r(pParent->pBack, &m_VisLeafs, pVisSet);
		}
		else
		{
			_collectLeafsFtoB_r(pParent->pFront, &m_VisLeafs, pVisSet);
		}

		pCurrNode = pParent;
		pParent = pCurrNode->pParent;
	}

	return &m_VisLeafs;
}

// Helper method to recursively collect potentially visible leafs (called by _visibleLeafsFtoB method).
void HFBSPGraph::_collectLeafsFtoB_r(const BSPNode * pNode, Array<int> * pLeafs, const unsigned char * pVisSet)
{
	// Cull nodes outside camera frustum
	if (!pNode || !_intersectFrustum(pNode))
		return;

	// Add leaf nodes (nLeaf > -1) to collection array
	// Skip non-drawable solid leaves (nLeaf == 0) and all non-visible leaves
	if ( (pNode->nLeaf > 0) && m_BSPData.IsLeafVisible(pVisSet, pNode->nLeaf) )
	{
		pLeafs->Add(pNode->nLeaf);
		return;
	}

	// Recurse into tree front to back order
	if ( m_BSPData.SPlanes()->m_pArray[pNode->nPlane].TestPoint(m_pCamera->Position()) > 0.0f )
	{
		_collectLeafsFtoB_r(pNode->pFront, pLeafs, pVisSet);
		_collectLeafsFtoB_r(pNode->pBack, pLeafs, pVisSet);
	}
	else
	{
		_collectLeafsFtoB_r(pNode->pBack, pLeafs, pVisSet);
		_collectLeafsFtoB_r(pNode->pFront, pLeafs, pVisSet);
	}
}

// Method to test if a single polygon face is potentially visible.  First test checks to 
// see if face is pointing toward or away from the camera (if away it is rejected).  Second
// test is to see if the face bounding box is within the viewing frustum (note that there
// is a special WorldFrustum for this which is the camera frustum in HL world coordinates).
bool HFBSPGraph::_isFaceVisible(const bspf_face * pFace)
{
	assert(pFace);

	// Cull back facing faces
	// Get Look vector and compare to face normal.  Need to adjust for largest field of view angle.
	Planef facePlane(m_BSPData.SPlanes()->m_pArray[pFace->nPlane]);
	if (pFace->cSide == 1)
		facePlane.InvertPlane();
	Vector3f vLook = m_pCamera->GetViewLookVector();
	if (vLook.Dot(facePlane.Normal()) > m_pCamera->GetLargestViewSin())
		return false;

	// Create bounding box for face
	Vector3f vBB[2];
	vBB[0] = Vector3f(10000.0f, 10000.0f, 10000.0f);			// Min point
	vBB[1] = Vector3f(-10000.0f, -10000.0f, -10000.0f);			// Max point

	for (int nEdge=0; nEdge<pFace->cEdges; nEdge++)
	{
		int nEdgeIndex = (int)m_BSPData.FaceEdges()->m_pArray[pFace->nE1 + nEdge];
		const bspf_edge * pEdge = &(m_BSPData.Edges()->m_pArray[abs(nEdgeIndex)]);
		for (int n=0; n<3; n++)
		{
			float fValue;
			
			if (nEdgeIndex < 0)
				fValue = m_BSPData.Vertices()->m_pArray[pEdge->nV2].fPoint[n];
			else
				fValue = m_BSPData.Vertices()->m_pArray[pEdge->nV1].fPoint[n];
			vBB[0][n] = (fValue < vBB[0][n]) ? fValue : vBB[0][n];
			vBB[1][n] = (fValue > vBB[1][n]) ? fValue : vBB[1][n];
		}
	}

	// Check for intersection of world camera frustum with face world bounding box
	return m_pCamera->WorldFrustum()->TestBoundingBox(vBB) == 0;
}

// Helper method to check if a node bounding box is inside or outside the view frustum.
bool HFBSPGraph::_intersectFrustum(const BSPNode * pNode)
{
	if (pNode->nLeaf > -1)
	{
		// Leaf node.  Return true.  Leaf faces will be tested later.
		return true;
	}

	Vector3f vBB[2] = { Vector3f(pNode->MinBox[0], pNode->MinBox[1], pNode->MinBox[2]), 
						Vector3f(pNode->MaxBox[0], pNode->MaxBox[1], pNode->MaxBox[2]) };

	// Check for intersection of world camera frustum with leaf world bounding box
	return m_pCamera->WorldFrustum()->TestBoundingBox(vBB) == 0;
}

bool CompareFaces(const lface & Ele1, const lface & Ele2)
{
	return (Ele1.nMipTex > Ele2.nMipTex);
}

// Iterates through the provided potentially visible leaf array and fills the face
// array object with potentially visible faces to be rendered.  The actual rendering
// uses this face array for the faces to render.
const Array<lface> * HFBSPGraph::_getFaces(const Array<int> * pVisLeafs)
{
	m_VisFaces.Clear();

	for (int n=0; n<(int)pVisLeafs->GetArrayCount(); n++)
	{
		size_t tStart = m_VisFaces.GetArrayCount();
		const bspf_leaf * pLeaf = &(m_BSPData.Leafs()->m_pArray[pVisLeafs->Get(n)]);
		for (int i=0; i<pLeaf->cFaces; i++)
		{
			int nFaceIndex = m_BSPData.LeafFaces()->m_pArray[pLeaf->nFirstFace+i];
			const bspf_face * pFace = &(m_BSPData.Faces()->m_pArray[nFaceIndex]);

			// Check to see if face is visible inside camera frustum
			if (!_isFaceVisible(pFace))
				continue;

			const bspf_textinfo * pTextInfo = &(m_BSPData.TextInfo()->m_pArray[pFace->nTextureInfo]);
			lface lFace;
			lFace.nFaceIndex = nFaceIndex;
			lFace.nMipTex = pTextInfo->nMipTex;
			m_VisFaces.Add(lFace);
		}

		// Sort faces within a leaf based on nMipTex (group all faces with same texture together)
		// Probably doesn't help much and can be removed.
		size_t tCount = m_VisFaces.GetArrayCount();
		m_VisFaces.Sort(CompareFaces, tStart, (tCount-tStart));
	}

	return &m_VisFaces;
}

// Method to render entity model faces for all entities in the potentially visible entity
// list (based on the current camera position in the level).  The entities are divided
// into two parts: transparent and solid, and this method takes a boolean parameter to
// determine which set of entities are rendered.
void HFBSPGraph::_renderEntFaces(bool bTransparent, const Matrix4f & mtxView)
{
	// Go through all potentially visible brush entities and render if in view frustum
	const VisEnts * pVEnts = m_BSPData.GetVisibleEntities(m_pCamLeaf->nLeaf);
	for (int n=0; n<(int)pVEnts->GetSetCount(); n++)
	{
		const EntVars * pEnt = &(m_BSPData.GetEntities()->Get(pVEnts->Get(n)));
		int nBrushIndex = pEnt->nBrush_model_index;

		// Cull non-brush entities, entities that don't meet the transparency condition, and special entities
		if ( (nBrushIndex <= 0) || 
			 (bTransparent && (pEnt->flags & ENTITY_TRANSPARENT) == 0) || 
			 (!bTransparent && (pEnt->flags & ENTITY_OPAQUE) == 0) ||
			 (pEnt->flags & ENTITY_SPECIAL) != 0 ||
			 (pEnt->vOrigin != Vector3f::cZero) )
		{
			continue;
		}

		const bspf_dmodel * pModel = &(m_BSPData.Models()->m_pArray[nBrushIndex]);

		// Cull to view frustum
		Vector3f vBB[2] = { Vector3f(pModel->mins), Vector3f(pModel->maxs) };
		if ( m_pCamera->WorldFrustum()->TestBoundingBox(vBB) == 0 )
		{
			m_VisFaces.Clear();

			for (int i=0; i<pModel->numfaces; i++)
			{
				int nFaceIndex = pModel->firstface + i;
				const bspf_face * pFace = &(m_BSPData.Faces()->m_pArray[nFaceIndex]);
				const bspf_textinfo * pTextInfo = &(m_BSPData.TextInfo()->m_pArray[pFace->nTextureInfo]);
				lface lFace;
				lFace.nFaceIndex = nFaceIndex;
				lFace.nMipTex = pTextInfo->nMipTex;
				m_VisFaces.Add(lFace);
			}

			// Group all faces with the same texture together (reduce SetTexture state changes)
			m_VisFaces.Sort(CompareFaces);

			// @review  Not sure about model translation.  Doesn't seem to be necessary for brush models.
			// What is pEnt->vOrigin?
			/*
			Matrix4f mtxWorld;
			if (pEnt->vOrigin != Vector3f::cZero)
			{
				Vector4f vTranslate(pEnt->vOrigin);
				mtxWorld = m_mtxWorld;
				mtxWorld.SetRow(3, vTranslate);
			}
			else
			{
				mtxWorld = m_mtxWorld;
			}
			m_pRenderer->SetTransform(D3DTS_WORLD, mtxWorld);
			*/

			if (bTransparent)
			{
				int nfactor = (int)(pEnt->fRenderamt * 255.0f);
				DWORD dwBlend = MAKE_ARGB(nfactor, nfactor, nfactor, nfactor);

				if (dwBlend != 0)
				{
					m_pRenderer->SetRenderState(D3DRS_TEXTUREFACTOR, dwBlend);
					m_pRenderer->SetTextureState(2, D3DTSS_ALPHAARG1, D3DTA_TFACTOR);
					m_pRenderer->SetTextureState(2, D3DTSS_ALPHAOP, D3DTOP_SELECTARG1);
				}
			}
			_renderFaces(&m_VisFaces, mtxView, m_mtxWorld);
			if (bTransparent)
			{
				m_pRenderer->SetRenderState(D3DRS_TEXTUREFACTOR, 0xFFFFFFFF);
			}
		}
	}

	/*
	// Restore world transform to non-translated
	m_pRenderer->SetTransform(D3DTS_WORLD, m_mtxWorld);
	*/
}

// Helper method to create the vertex shader object.  This includes compiling the vertex shader
// file (VertexShader1.fx) and this file must reside in the same directory as the binary files
// for this application.
bool HFBSPGraph::_setVertexShader()
{
	if (!m_bShaderCapable)
	{
		m_pRenderer->SetVertexShader(NULL);
		DELETE_PTR(m_pVertexShader1);
		return false;
	}

	if (m_pVertexShader1)
	{
		return m_pVertexShader1->ReCreateShader(m_pRenderer);
	}

	const char szFuncName[] = "VS_Flashlight";
	const char szFileName[] = "VertexShader1.fx";
	m_pVertexShader1 = DXVertexShader::CreateShader(szFileName, szFuncName, m_pRenderer);
	if (m_pVertexShader1)
	{
		return m_pVertexShader1->SetShader();
	}

	return false;
}

void HFBSPGraph::_releaseDXTextures()
{
	for (int n=0; n<(int)m_DXTextures.GetMapCount(); n++)
	{
		IDirect3DTexture9 * pDXTexture = m_DXTextures[n].value;
		SAFE_RELEASE(pDXTexture);
	}
	m_DXTextures.Clear();

	for (n=0; n<(int)m_DXLMTextures.GetMapCount(); n++)
	{
		IDirect3DTexture9 * pDXLMTexture = m_DXLMTextures[n].value;
		SAFE_RELEASE(pDXLMTexture);
	}
	m_DXLMTextures.Clear();
}

void HFBSPGraph::_releaseDXVertices()
{
	SAFE_RELEASE(m_pSGDX9Vertices);
	m_SGFaceToVertex.Clear();
}