///////////////////////////////////////////////////////////////////////////////
/// @file deOccludeRaster.cpp
///
/// @brief software rasterizer for doing occlusion culling with
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// </hr>
///
/// @date May 2003
/// @author Assassin
/// @remarks Initial Creation
///
///////////////////////////////////////////////////////////////////////////////

//#pragma comment(lib, "advapi32")

#include "deOccludeRaster.hpp"
#include "deArray.hpp"
#include "deProfile.hpp"

#pragma todo(test for removal of d3dx library usage)

extern "C" void * Internal_ASM_memset(void *Ptr1, int C, long Len);
extern "C" void * Internal_ASM_MMX_memset(void *Ptr1, int C, long Len);

long OcclusionTestProfileID = 0;
long OcclusionRenderProfileID = 0;
long OcclusionExtentsProfileID = 0;
long OcclusionHierarchyProfileID = 0;
long OcclusionClearProfileID = 0;

// a few helper functions
static inline DWORD BiggestPow2SmallerThan(DWORD input)
{
#ifdef __GNUC__
	DWORD RetVal;
	RetVal = 1;
	do
	{
		RetVal = RetVal << 1;
	} while(RetVal < input);
	
	if (RetVal >= input)
		RetVal /= 2;
	return RetVal;
	
#else
	DWORD RetVal;
	__asm
	{
		mov ecx, input
			mov eax, 1
again:
		ror eax, 1
			test eax, ecx
			jz again
			mov RetVal, eax
	}

	if (RetVal == input)
		RetVal /= 2;
	return RetVal;
#endif
}

static inline DWORD SmallestPow2BiggerThan(DWORD input)
{
	return BiggestPow2SmallerThan(input)*2;
}

template <class T>
static void Swap(T& x, T& y)
{
	T z(x);
	x = y;
	y = z;
}

static float half = 0.5f;
static const float* phalf = &half;
static inline float SUB_PIX(const float input)
{
	float   retCode;
#ifdef __GNUC__
#pragma asm   fld     input
#pragma asm   fld     input
#pragma asm   fsub    dword ptr phalf
#pragma asm   frndint
#pragma asm   fsubp   st(1), st
#pragma asm   fld1
#pragma asm   fsubrp  st(1), st
#pragma asm   fstp    retCode
#else
	__asm   fld     input
	__asm   fld     input
	__asm   fsub    dword ptr phalf
	__asm   frndint
	__asm   fsubp   st(1), st
	__asm   fld1
	__asm   fsubrp  st(1), st
	__asm   fstp    retCode
#endif
	
	return retCode;
}

template <class T>
static inline void ProjectVec4(T &OutVec, const deVec4d &InVec)
{
	deDouble OneOverW = 1.0f/InVec.w;
	OutVec.x = InVec.x * OneOverW;
	OutVec.y = InVec.y * OneOverW;
	OutVec.z = InVec.z * OneOverW;
}

template <class T>
static inline void ProjectVec4NoZ(T &OutVec, const deVec4d &InVec)
{
	deDouble OneOverW = 1.0f/InVec.w;
	OutVec.x = InVec.x * OneOverW;
	OutVec.y = InVec.y * OneOverW;
	OutVec.z = InVec.z;
}



//
// deOccludeRasterizer implementation
//

deOccludeRasterizer::deOccludeRasterizer()
{
	m_Buffer = NULL;
	m_Hierarchy = NULL;
	m_Width = m_Height = 0;
	m_HierarchyDepth = 0;
	m_GradientCutoff = 0;
	m_Viewport.Left = m_Viewport.Right = m_Viewport.Top = m_Viewport.Bottom = 0;
	m_ScissorRect.Left = m_ScissorRect.Right = m_ScissorRect.Top = m_ScissorRect.Bottom = 0;
	// transforms set up automatically
	m_LastProjectionColumn[0] = 0;
	m_LastProjectionColumn[1] = 0;
	m_LastProjectionColumn[2] = 0;
	m_LastProjectionColumn[3] = 1;
	m_TransformsChanged = deTRUE;
	m_BufferSizeChanged = deTRUE;
	m_DirtyBuffer = deFALSE;
	m_CountPixels = deTRUE;
}

deOccludeRasterizer::~deOccludeRasterizer()
{
	m_Width = m_Height = 0;
	BuildHierarchy(deTRUE);
	delete[] m_Buffer;
}

void deOccludeRasterizer::SetBufferSize(short Width, short Height)
{
	DE_ASSERT(Width > 0 && Height > 0);
	m_Width = Width;
	m_Height = Height;
	m_BufferSizeChanged = deTRUE;
	deRect NewViewRect;
	NewViewRect.Left = 0;
	NewViewRect.Top = 0;
	NewViewRect.Right = m_Width;
	NewViewRect.Bottom = m_Height;
	SetViewport(NewViewRect);
}

void deOccludeRasterizer::SetViewport(const deRect& ViewRect)
{
	m_Viewport = ViewRect;
	m_TransformsChanged = deTRUE;
}

void deOccludeRasterizer::SetScissorRect(const deRect& ScissorRect)
{
	m_ScissorRect = ScissorRect;
}

void deOccludeRasterizer::SetGradientCutoff(deFloat Cutoff)
{
	m_GradientCutoff = Cutoff;
}

void deOccludeRasterizer::SetPixelCounting(deBoolean CountPixels)
{
	m_CountPixels = CountPixels;
}

void deOccludeRasterizer::SetWorldTransform(const deTransformInfo & World)
{
	m_WorldTransform = World;
	m_TransformsChanged = deTRUE;
}

void deOccludeRasterizer::SetViewTransform(const deTransformInfo & View)
{
	m_ViewPosTransform = View;
	m_TransformsChanged = deTRUE;
}

void deOccludeRasterizer::SetFOVClipping(float FOVY, float Aspect, float ClipNear, float ClipFar, deFloatRect* FSubRect)
{
	//deVec3d l,u,i;
	deDouble (&proj)[4][4] = m_ProjectionTransform.m;
	m_TransformsChanged = deTRUE;
	if (FSubRect)
	{
		float right, top;
		float fov2, left2, right2, bottom2, top2;

		fov2 = FOVY * 0.5f;

		top = ClipNear/(cosf(fov2)/sinf(fov2));
		right = top * Aspect;

		if (FSubRect->Left == 0.5) // dead center
			left2 = 0;
		else
			left2 = 2 * right * (FSubRect->Left - 0.5f);

		if (FSubRect->Right == 0.5) // dead center
			right2 = 0;
		else
			right2 = 2 * right * (FSubRect->Right - 0.5f);

		if (FSubRect->Bottom == 0.5) // dead center
			bottom2 = 0;
		else
			bottom2 = 2 * top * (FSubRect->Bottom - 0.5f);

		if (FSubRect->Top == 0.5) // dead center
			top2 = 0;
		else
			top2 = 2 * top * (FSubRect->Top - 0.5f);

		/*
		2*zn/(r-l)   0            0              0
		0            2*zn/(t-b)   0              0
		(l+r)/(l-r)  (t+b)/(b-t)  zf/(zf-zn)     1
		0            0            zn*zf/(zn-zf)  0
		*/

		proj[0][0] = 2*ClipNear/(right2-left2);
		proj[0][1] = 0;
		proj[0][2] = 0;
		proj[0][3] = 0;

		proj[1][0] = 0;
		proj[1][1] = 2*ClipNear/(top2-bottom2);
		proj[1][2] = 0;
		proj[1][3] = 0;

		proj[2][0] = (left2+right2)/(left2-right2);
		proj[2][1] = (top2+bottom2)/(bottom2-top2);
		proj[2][2] = ClipFar/(ClipFar-ClipNear);
		proj[2][3] = 1;

		proj[3][0] = 0;
		proj[3][1] = 0;
		proj[3][2] = (ClipNear*ClipFar)/(ClipNear-ClipFar);
		proj[3][3] = 0;

		/*
		m_ProjectionTransform.SetLeftUpIn(l, u, i);

		m_ProjectionTransform.Translation.x = 0;
		m_ProjectionTransform.Translation.y = 0;
		m_ProjectionTransform.Translation.z = (ClipNear*ClipFar)/(ClipNear-ClipFar);

		m_LastProjectionColumn[0] = 0;
		m_LastProjectionColumn[1] = 0;
		m_LastProjectionColumn[2] = 1;
		m_LastProjectionColumn[3] = 0;
		*/
	}
	else
	{
		float fov2;
		register float w, h;
		// the d3d docs for D3DXMatrixPerspectiveFovLH are wrong for _11 and _22

		fov2 = FOVY/2;
		h = cosf(fov2) / sinf(fov2);
		w = h / Aspect;

		proj[0][0] = w; //2*ClipNear/w;
		proj[0][1] = 0;
		proj[0][2] = 0;
		proj[0][3] = 0;

		proj[1][0] = 0;
		proj[1][1] = h; //2*ClipNear/h;
		proj[1][2] = 0;
		proj[1][3] = 0;

		proj[2][0] = 0;
		proj[2][1] = 0;
		proj[2][2] = ClipFar/(ClipFar-ClipNear);
		proj[2][3] = 1;
		
		proj[3][0] = 0;
		proj[3][1] = 0;
		proj[3][2] = -ClipNear * proj[2][2];
		proj[3][3] = 0;
		/*
		m_ProjectionTransform.SetLeftUpIn(l, u, i);

		m_ProjectionTransform.Translation.x = 0;
		m_ProjectionTransform.Translation.y = 0;
		m_ProjectionTransform.Translation.z = -ClipNear * i.z;

		m_LastProjectionColumn[0] = 0;
		m_LastProjectionColumn[1] = 0;
		m_LastProjectionColumn[2] = 1;
		m_LastProjectionColumn[3] = 0;
		*/
	}
	m_NearClip = ClipNear;
	m_FarClip = ClipFar;
}

void deOccludeRasterizer::SetOrthoClipping(float Width, float Height, float ClipNear, float ClipFar, deBoolean Invert, deFloatRect* FSubRect)
{
	//deVec3d l,u,i;
	deDouble (&proj)[4][4] = m_ProjectionTransform.m;
	m_TransformsChanged = deTRUE;
	if (FSubRect)
	{
		/*
		2/(r-l)      0            0           0
		0            2/(t-b)      0           0
		0            0            1/(zf-zn)   0
		(l+r)/(l-r)  (t+b)/(b-t)  zn/(zn-zf)  1
		*/

		FSubRect->Left *= Width;
		FSubRect->Right *= Width;
		FSubRect->Top *= Height;
		FSubRect->Bottom *= Height;

		proj[0][0] = 2/(FSubRect->Right - FSubRect->Left);
		proj[0][1] = 0;
		proj[0][2] = 0;
		proj[0][3] = 0;

		proj[1][0] = 0;
		proj[1][1] = 2/(FSubRect->Bottom - FSubRect->Top);
		proj[1][2] = 0;
		proj[1][3] = 0;
		
		if (Invert)
			proj[1][1] *= -1;		

		proj[2][0] = 0;
		proj[2][1] = 0;
		proj[2][2] = 1/(ClipFar - ClipNear);
		proj[2][3] = 0;

		proj[3][0] = (FSubRect->Left + FSubRect->Right)/(FSubRect->Left - FSubRect->Right);
		proj[3][1] = (FSubRect->Top + FSubRect->Bottom)/(FSubRect->Bottom - FSubRect->Top);
		proj[3][2] = ClipNear/(ClipNear-ClipFar);
		proj[3][3] = 1;

		/*
		m_ProjectionTransform.SetLeftUpIn(l, u, i);

		m_ProjectionTransform.Translation.x = (FSubRect->Left + FSubRect->Right)/(FSubRect->Left - FSubRect->Right);
		m_ProjectionTransform.Translation.y = (FSubRect->Top + FSubRect->Bottom)/(FSubRect->Bottom - FSubRect->Top);
		m_ProjectionTransform.Translation.z = ClipNear/(ClipNear-ClipFar);
		
		m_LastProjectionColumn[0] = 0;
		m_LastProjectionColumn[1] = 0;
		m_LastProjectionColumn[2] = 0;
		m_LastProjectionColumn[3] = 1;
		*/
	}
	else
	{
		/*
		2/w  0    0           0
		0    2/h  0           0
		0    0    1/(zf-zf)   0
		0    0    zn/(zn-zf)  1
		*/

		proj[0][0] = 2/(FSubRect->Right - FSubRect->Left);
		proj[0][1] = 0;
		proj[0][2] = 0;
		proj[0][3] = 0;
		
		proj[1][0] = 0;
		proj[1][1] = 2/(FSubRect->Bottom - FSubRect->Top);
		proj[1][2] = 0;
		proj[1][3] = 0;
		
		if (Invert)
			proj[1][1] *= -1;		
		
		proj[2][0] = 0;
		proj[2][1] = 0;
		proj[2][2] = 1/(ClipFar - ClipNear);
		proj[2][3] = 0;
		
		proj[3][0] = 0;
		proj[3][1] = 0;
		proj[3][2] = ClipNear*proj[2][2];
		proj[3][3] = 1;
		
		/*
		m_ProjectionTransform.SetLeftUpIn(l, u, i);

		m_ProjectionTransform.Translation.x = 0;
		m_ProjectionTransform.Translation.y = 0;
		m_ProjectionTransform.Translation.z = ClipNear/(ClipNear-ClipFar);
		
		m_LastProjectionColumn[0] = 0;
		m_LastProjectionColumn[1] = 0;
		m_LastProjectionColumn[2] = 0;
		m_LastProjectionColumn[3] = 1;
		*/
	}
	m_NearClip = ClipNear;
	m_FarClip = ClipFar;
}

/*
#if OCCLUDE_MINBUFFER
#pragma warning (disable : 4100)
#endif
*/
#if OCCLUDE_MINBUFFER
const deOccludeRasterizer::BufferType* deOccludeRasterizer::GetBuffer(long level, deBoolean MinNotMax) const
#else
const deOccludeRasterizer::BufferType* deOccludeRasterizer::GetBuffer(long level, deBoolean /*MinNotMax*/) const
#endif
{
	if (level < 0)
		return m_Buffer;
#if OCCLUDE_MINBUFFER
	if (MinNotMax)
		return m_Hierarchy[level].MinBuffer;
	else
#endif
		return m_Hierarchy[level].MaxBuffer;
}
/*
#if OCCLUDE_MINBUFFER
#pragma warning (default : 4100)
#endif
*/
long deOccludeRasterizer::GetBufferDepth() const
{
	return m_HierarchyDepth;
}

void deOccludeRasterizer::GetBufferSize(short& Width, short& Height, long level) const
{
	if (level < 0)
	{
		Width = m_Width;
		Height = m_Height;
	}
	else
	{
		Width = m_Hierarchy[level].Width;
		Height = m_Hierarchy[level].Height;
	}
}

void deOccludeRasterizer::GetViewport(deRect & ViewRect) const
{
	ViewRect = m_Viewport;
}

void deOccludeRasterizer::GetScissorRect(deRect & ScissorRect) const
{
	ScissorRect = m_ScissorRect;
}

deFloat deOccludeRasterizer::GetGradientCutoff() const
{
	return m_GradientCutoff;
}

void deOccludeRasterizer::ConcatenateMatrices()
{
	if (m_TransformsChanged)
	{
		deMatrix44 tempmat1(m_WorldTransform);
		deMatrix44 tempmat2(m_ViewPosTransform);
		deMatrix44 tempmat3;

		tempmat1.Multiply(tempmat2, tempmat3);
		tempmat3.Multiply(m_ProjectionTransform, m_ConcatenatedTransform);

		/*
		m_WorldTransform.ToFloat44(tempmat1.m);
		m_ViewPosTransform.ToFloat44(tempmat2.m);
		D3DXMatrixMultiply(&tempmat3, &tempmat1, &tempmat2);
		m_ProjectionTransform.ToFloat44(tempmat1.m);
		tempmat1._14 = m_LastProjectionColumn[0];
		tempmat1._24 = m_LastProjectionColumn[1];
		tempmat1._34 = m_LastProjectionColumn[2];
		tempmat1._44 = m_LastProjectionColumn[3];
		D3DXMatrixMultiply(&tempmat2, &tempmat3, &tempmat1);
		D3DXMatrixScaling(&tempmat1, (float)m_Width, (float)-m_Height, 1);
		D3DXMatrixMultiply(&tempmat3, &tempmat2, &tempmat1);
		D3DXMatrixTranslation(&tempmat1, (float)m_Width/2, (float)m_Height/2, 0);
		D3DXMatrixMultiply(&tempmat2, &tempmat3, &tempmat1);

		//m_ConcatenatedTransform.FromD3DMatrix(&tempmat2);
		memcpy(m_ConcatenatedTransform, tempmat2.m, 16*sizeof(float));
		*/

		m_ViewportTransform.Reset();
		m_ViewportTransform.ApplyScaling(m_Width/2, -m_Height/2, 1);//1/(m_FarClip-m_NearClip));
		m_ViewportTransform.Translation.x = m_Width/2;
		m_ViewportTransform.Translation.y = m_Height/2;

		m_TransformsChanged = deFALSE;
	}
}

void deOccludeRasterizer::ResizeBuffer()
{
	if (m_BufferSizeChanged)
	{
		delete[] m_Buffer;
		m_Buffer = new BufferType[m_Width*m_Height];
		m_BufferSizeChanged = deFALSE;
		ClearBuffer();
		m_DirtyBuffer = deFALSE;
		BuildHierarchy(deTRUE);
		m_DirtyBuffer = deTRUE;
	}
}

void deOccludeRasterizer::ClearBuffer()
{
	PROFILE_ID_NAME(&OcclusionClearProfileID, "OcclusionClear");
	if (m_Buffer)
	{
		memset(m_Buffer, 0xff, sizeof(BufferType)*m_Width*m_Height);
		//Internal_ASM_MMX_memset(m_Buffer, 0xff, sizeof(BufferType)*m_Width*m_Height);
	}
	m_DirtyBuffer = deTRUE;
}

void deOccludeRasterizer::BuildHierarchy(deBoolean ForceTearDown)
{
	PROFILE_ID_NAME(&OcclusionHierarchyProfileID, "OcclusionHierarchy");
	if (ForceTearDown)
	{
		// main buffer was resized, need to resize these too
		short x, y, i;
		if (m_Hierarchy)
		{
			for (i = 0; i < m_HierarchyDepth; ++i)
			{
				delete[] m_Hierarchy[i].MaxBuffer;
#if OCCLUDE_MINBUFFER
				delete[] m_Hierarchy[i].MinBuffer;
#endif
			}
			delete[] m_Hierarchy;
			m_Hierarchy = NULL;
		}
		x = m_Width;
		y = m_Height;
		i = max(x,y);
		if (i == 0)
			return;
		m_HierarchyDepth = 0;
		while (i > 0)
		{
			i /= 2;
			++m_HierarchyDepth;
		}
		m_Hierarchy = new BufferLevel_t[m_HierarchyDepth];
		for (i = 0; i < m_HierarchyDepth; ++i)
		{
			x = (short)ceilf(x/2.0f);
			y = (short)ceilf(y/2.0f);
			if (x & 1 && x > 1)
				x += 1;
			if (y & 1 && y > 1)
				y += 1;

			m_Hierarchy[i].MaxBuffer = new BufferType[x*y];
#if OCCLUDE_MINBUFFER
			m_Hierarchy[i].MinBuffer = new BufferType[x*y];
#endif
			m_Hierarchy[i].Width = x;
			m_Hierarchy[i].Height = y;

			// fill max with 0's so that the border padding occludes everything
			memset(m_Hierarchy[i].MaxBuffer, 0x00, x*y*sizeof(BufferType));
#if OCCLUDE_MINBUFFER
			// fill min with 1's so that anything else is smaller
			memset(m_Hierarchy[i].MinBuffer, 0xff, x*y*sizeof(BufferType));
#endif
		}
	}
	if (m_DirtyBuffer)
	{
		m_DirtyBuffer = deFALSE;
		int k, y, index1, stopy, width;
//		deDouble XFraction, YFraction;
		BufferType * ThisBuffer;
		BufferType * SubBuffer;
		register BufferType Max1;
		register BufferType Max2;
		register BufferType Sample;
		register int x,stopx,index2,subwidth;
//		XFraction = deDouble(m_Width)/SmallestPow2BiggerThan(m_Width);
//		YFraction = deDouble(m_Height)/SmallestPow2BiggerThan(m_Height);
		// loop through all bufffers, including the main buffer
		for (k = -1; k < m_HierarchyDepth-1; ++k)
		{
			// MAX buffer
			
			// test if this is the main buffer
			if (k >= 0)
			{
				// hierarchy buffers are all square
				ThisBuffer = m_Hierarchy[k].MaxBuffer;
				width = m_Hierarchy[k].Width;
				stopx = width;
				stopy = m_Hierarchy[k].Height;
			}
			else
			{
				// main buffer is screen-shaped
				ThisBuffer = m_Buffer;
				width = m_Width;
				stopx = m_Width;
				stopy = m_Height;
			}

			// get the buffer we'll be sub-sampling into
			SubBuffer = m_Hierarchy[k+1].MaxBuffer;
			subwidth = m_Hierarchy[k+1].Width;
			// every 2 scanlines
			for (y = 0; y < stopy; y+=2)
			{
				// super-sample buffer index offset
				index1 = y*width;
				// every 2 pixels in scanline
				for (x = 0; x < stopx; x += 2)
				{
					// take 2 samples
					index2 = index1+x;
					Max1 = ThisBuffer[index2];
					Sample = ThisBuffer[index2+1];
					if (Sample > Max1)
						Max1 = Sample;
					// take another 2 samples
					index2 += width;
					Max2 = ThisBuffer[index2];
					Sample = ThisBuffer[index2+1];
					if (Sample > Max2)
						Max2 = Sample;
					// take max of 4 samples
					if (Max2 > Max1)
						Max1 = Max2;
					// sub-sample buffer index
					index2 = (y*subwidth + x)/2;
					// write max
					SubBuffer[index2] = Max1;
				}
			}
#if OCCLUDE_MINBUFFER
			// MIN buffer

			// test if this is the main buffer
			if (k >= 0)
			{
				// hierarchy buffers are all square
				ThisBuffer = m_Hierarchy[k].MinBuffer;
				width = m_Hierarchy[k].Width;
				stopx = width;
				stopy = m_Hierarchy[k].Height;
			}
			else
			{
				// main buffer is screen-shaped
				ThisBuffer = m_Buffer;
				width = m_Width;
				stopx = m_Width;
				stopy = m_Height;
			}
			
			// get the buffer we'll be sub-sampling into
			SubBuffer = m_Hierarchy[k+1].MinBuffer;
			subwidth = m_Hierarchy[k+1].Width;
			// every 2 scanlines
			for (y = 0; y < stopy; y+=2)
			{
				// super-sample buffer index offset
				index1 = y*width;
				// every 2 pixels in scanline
				for (x = 0; x < stopx; x += 2)
				{
					// take 2 samples
					index2 = index1+x;
					Max1 = ThisBuffer[index2];
					Sample = ThisBuffer[index2+1];
					if (Sample < Max1)
						Max1 = Sample;
					// take another 2 samples
					index2 += width;
					Max2 = ThisBuffer[index2];
					Sample = ThisBuffer[index2+1];
					if (Sample < Max2)
						Max2 = Sample;
					// take max of 4 samples
					if (Max2 < Max1)
						Max1 = Max2;
					// sub-sample buffer index
					index2 = (y*subwidth + x)/2;
					// write min
					SubBuffer[index2] = Max1;
				}
			}
#endif
		}
	}
}

deBoolean deOccludeRasterizer::TestScreenExtentsVisible(const deFloatRect& FullExtents, DWORD MinZ, int MaxLevel)
{
	PROFILE_ID_NAME(&OcclusionExtentsProfileID, "OcclusionExtents");
	int i,y;
	register int x,index;
	deRect ShrunkRect;
#if OCCLUDE_MINBUFFER
	BufferType* minbuffer;
#endif
	BufferType* maxbuffer;
	int Visible;
	MaxLevel = m_HierarchyDepth - MaxLevel;
	if (MaxLevel < 0)
		MaxLevel = 0;
#if OCCLUDE_16BIT
	MinZ >>= 16;
#endif
	// loop through all hierarchy levels, from smallest to largest
	for (i = m_HierarchyDepth-1; i >= MaxLevel; --i)
	{
		// get the rect that fits inside this hierarchy buffer
		ShrunkRect.Top = (int)((FullExtents.Top) / (1 << (i+1)));
		ShrunkRect.Left = (int)((FullExtents.Left) / (1 << (i+1)));
		ShrunkRect.Right = (int)ceil((FullExtents.Right) / (1 << (i+1)));
		ShrunkRect.Bottom = (int)ceil((FullExtents.Bottom) / (1 << (i+1)));
		// scan-convert the box and test depth values
		maxbuffer = m_Hierarchy[i].MaxBuffer;
#if OCCLUDE_MINBUFFER
		minbuffer = m_Hierarchy[i].MinBuffer;
#endif
		Visible = 1;
		for (y = ShrunkRect.Top; y < ShrunkRect.Bottom; ++y)
		{
			index = m_Hierarchy[i].Width*y;
			// if the pixel is visible, then the whole test is done for this hierarchy level
			// worst spot to have visible is the bottom right corner
			for (x = ShrunkRect.Left; x < ShrunkRect.Right; ++x)
			{
#if OCCLUDE_MINBUFFER
				if (minbuffer[index+x] > MinZ)
				{
					return deTRUE;
				}
#endif
				if (maxbuffer[index+x] > MinZ)
					break;
			}
			if (x != ShrunkRect.Right)
				break;
		}
		// if we get here, then no pixels were visible
		if (y == ShrunkRect.Bottom)
			return deFALSE;
	}
	ShrunkRect.Top = (int)(FullExtents.Top);
	ShrunkRect.Left = (int)(FullExtents.Left);
	ShrunkRect.Right = (int)ceil(FullExtents.Right);
	ShrunkRect.Bottom = (int)ceil(FullExtents.Bottom);
	// now test main buffer
	for (y = ShrunkRect.Top; y < ShrunkRect.Bottom; ++y)
	{
		index = m_Width*y;
		for (x = ShrunkRect.Left; x < ShrunkRect.Right; ++x)
		{
			// if the pixel is visible, then the whole test is done
			if (m_Buffer[index+x] > MinZ)
				return deTRUE;
		}
	}
	// if we get here, then no pixels were visible
	return deFALSE;
}

#pragma warning (disable : 4701) // variable may have been used without being initialized
int deOccludeRasterizer::RenderIndexedTriangles(deBoolean TestOnly, 
												 const deVertex * Vertices, long NumVertices, 
												 const WORD * Indices, long NumIndices)
{
	if (Vertices == NULL)
		DEBUGRETURN(0, "RenderIndexedTriangles: Vertices was NULL");
	
	long * ref = &OcclusionRenderProfileID;
	char * str = "OcclusionRender";
	if (TestOnly)
	{
		ref = &OcclusionTestProfileID;
		str = "OcclusionTest";
	}
	PROFILE_ID_NAME(ref, str);

	ConcatenateMatrices();
	ResizeBuffer();

	if (TestOnly)
		BuildHierarchy();
	else
		m_DirtyBuffer = deTRUE;

	struct CacheVert_t
	{
		deVec4d	Vert;
		long	Index;
	};

	const int VERTCACHESIZE = 16;
	CacheVert_t VertexCache[VERTCACHESIZE];
	register int x, RealStopX, index;
	register int PixelsRendered;
	int i, NumTris;
	int k, ClippedTris, ClipLocation;
	int y, StopY;
	deVec4d TransformedTri[3];
	deVec3d CurrentTri[4];
	deDouble GradientL, GradientR;
	deDouble ZGradientL;
	DWORD DepthVal;
	int DepthDelta;
	deBoolean Left1;
	deDouble StartX, StopX, StartZ;
	deDouble DeltaZ, NearClipInv;
	deDouble ZVal;
//	deMatrix44 d3dmat(m_ConcatenatedTransform);

#pragma note (extents testing might want to clip instead of auto-rejecting if clipping would occur)

//	ClipDistInv = 1/(m_FarClip-m_NearClip);
	NearClipInv = 1/m_NearClip;
	if (TestOnly)
	{
		deVec3d Min, Max;
		deBoolean FailOcclusion = deFALSE;
		Min.x = m_Width;
		Min.y = m_Height;
		Min.z = m_FarClip-m_NearClip;
		Max.x = 0;
		Max.y = 0;
		Max.z = 0;
		for (i = 0; i < NumVertices; ++i)
		{
			// Transform into screen-space
			//D3DXVec3Transform(&TransformedTri[0], (D3DXVECTOR3*)&Vertices[i], &d3dmat);
			m_ConcatenatedTransform.Transform(Vertices[i], TransformedTri[0]);
			
			if (TransformedTri[0].z < 0)
			{
				// fail if the object penetrates the near clip plane
				FailOcclusion = deTRUE;
				break;
			}
			
			// perspective divide
			ProjectVec4NoZ(CurrentTri[0], TransformedTri[0]);

			// translate & scale into viewport size
			m_ViewportTransform.Transform(CurrentTri[0], CurrentTri[0]);

			Min.x = min(Min.x, CurrentTri[0].x);
			Min.y = min(Min.y, CurrentTri[0].y);
			Min.z = min(Min.z, CurrentTri[0].z);
			Max.x = max(Max.x, CurrentTri[0].x);
			Max.y = max(Max.y, CurrentTri[0].y);
			Max.z = max(Max.z, CurrentTri[0].z);
		}
		if (!FailOcclusion)
		{
			deFloatRect Extents;
			DWORD MinZ;
			Extents.Left = (deFloat)max(0.0,Min.x);
			Extents.Top = (deFloat)max(0.0,Min.y);
			Extents.Right = (deFloat)min(m_Width,Max.x);
			Extents.Bottom = (deFloat)min(m_Height,Max.y);
			MinZ = (DWORD)(Min.z*0xffffffff);
			if (!TestScreenExtentsVisible(Extents, MinZ, m_HierarchyDepth))
				return 0;
		}
		if (!m_CountPixels)
			return 1;
	}
	PixelsRendered = 0;
	if (Indices)
	{
		NumTris = NumIndices/3;
		memset(VertexCache, -1, sizeof(CacheVert_t)*VERTCACHESIZE);
	}
	else
	{
		NumTris = NumVertices/3;
	}
	for (i = 0; i < NumTris; ++i)
	{
		// Transform into screen-space
		if (Indices)
		{
			for (k = 0; k < 3; ++k)
			{
				x = Indices[i*3+k];
				y = x % VERTCACHESIZE;
				if (VertexCache[y].Index == x)
				{
					TransformedTri[k] = VertexCache[y].Vert;
				}
				else
				{
					VertexCache[y].Index = x;
					//D3DXVec3Transform(&TransformedTri[k], (D3DXVECTOR3*)&Vertices[x], &d3dmat);
					m_ConcatenatedTransform.Transform(Vertices[x], TransformedTri[k]);
					VertexCache[y].Vert = TransformedTri[k];
				}
			}
		}
		else
		{
			//D3DXVec3Transform(&TransformedTri[0], (D3DXVECTOR3*)&Vertices[i*3+0], &d3dmat);
			//D3DXVec3Transform(&TransformedTri[1], (D3DXVECTOR3*)&Vertices[i*3+1], &d3dmat);
			//D3DXVec3Transform(&TransformedTri[2], (D3DXVECTOR3*)&Vertices[i*3+2], &d3dmat);
			m_ConcatenatedTransform.Transform(Vertices[i*3+0], TransformedTri[0]);
			m_ConcatenatedTransform.Transform(Vertices[i*3+1], TransformedTri[1]);
			m_ConcatenatedTransform.Transform(Vertices[i*3+2], TransformedTri[2]);
		}

		if (TransformedTri[0].w >= m_FarClip && TransformedTri[1].w >= m_FarClip && TransformedTri[2].w >= m_FarClip)
			continue;
		
		// store the combination of hidden vertices as bitflags
		ClippedTris = (TransformedTri[0].z < 0) << 0;
		ClippedTris |= (TransformedTri[1].z < 0) << 1;
		ClippedTris |= (TransformedTri[2].z < 0) << 2;

		if (ClippedTris)
		{
			// clip against near plane
			int OddOne, Other1, Other2;
			switch (ClippedTris)
			{
			// 1 behind makes it a quad
			case 1:		// [0] behind near plane
				ClippedTris = 2;
				OddOne = 0;
				break;
			case 2:		// [1] behind
				ClippedTris = 2;
				OddOne = 1;
				break;
			case 4:		// [2] behind
				ClippedTris = 2;
				OddOne = 2;
				break;
			// 2 behind keeps it a triangle
			case 3:		// [0]&[1] behind
				ClippedTris = 1;
				OddOne = 2;
				break;
			case 5:		// [0]&[2] behind
				ClippedTris = 1;
				OddOne = 1;
				break;
			case 6:		// [1]&[2] behind
				ClippedTris = 1;
				OddOne = 0;
				break;
			// 3 behind means it's invisible
			case 7:
				continue; // go to the next triangle
			}
			Other1 = (OddOne+1)%3;
			Other2 = (OddOne+2)%3;

			if (ClippedTris == 1)
			{
				// 2 behind, stays as 1 tri
				ProjectVec4(CurrentTri[OddOne], TransformedTri[OddOne]);
				ZVal = (TransformedTri[OddOne].z)/(TransformedTri[OddOne].z - TransformedTri[Other1].z);
				DeltaZ = 1 - ZVal;
				CurrentTri[Other1].x = ZVal * TransformedTri[Other1].x + DeltaZ * TransformedTri[OddOne].x;
				CurrentTri[Other1].y = ZVal * TransformedTri[Other1].y + DeltaZ * TransformedTri[OddOne].y;
				CurrentTri[Other1].z = 0;
				CurrentTri[Other1].x *= NearClipInv;
				CurrentTri[Other1].y *= NearClipInv;
				ZVal = (TransformedTri[OddOne].z)/(TransformedTri[OddOne].z - TransformedTri[Other2].z);
				DeltaZ = 1 - ZVal;
				CurrentTri[Other2].x = ZVal * TransformedTri[Other2].x + DeltaZ * TransformedTri[OddOne].x;
				CurrentTri[Other2].y = ZVal * TransformedTri[Other2].y + DeltaZ * TransformedTri[OddOne].y;
				CurrentTri[Other2].z = 0;
				CurrentTri[Other2].x *= NearClipInv;
				CurrentTri[Other2].y *= NearClipInv;
			}
			else
			{
				// one behind, make 2 tri's
				ProjectVec4(CurrentTri[0], TransformedTri[Other1]);
				ProjectVec4(CurrentTri[1], TransformedTri[Other2]);
				ZVal = (TransformedTri[OddOne].z)/(TransformedTri[OddOne].z - TransformedTri[Other1].z);
				DeltaZ = 1 - ZVal;
				CurrentTri[2].x = ZVal * TransformedTri[Other1].x + DeltaZ * TransformedTri[OddOne].x;
				CurrentTri[2].y = ZVal * TransformedTri[Other1].y + DeltaZ * TransformedTri[OddOne].y;
				CurrentTri[2].z = 0;
				CurrentTri[2].x *= NearClipInv;
				CurrentTri[2].y *= NearClipInv;
				ZVal = (TransformedTri[OddOne].z)/(TransformedTri[OddOne].z - TransformedTri[Other2].z);
				DeltaZ = 1 - ZVal;
				CurrentTri[3].x = ZVal * TransformedTri[Other2].x + DeltaZ * TransformedTri[OddOne].x;
				CurrentTri[3].y = ZVal * TransformedTri[Other2].y + DeltaZ * TransformedTri[OddOne].y;
				CurrentTri[3].z = 0;
				CurrentTri[3].x *= NearClipInv;
				CurrentTri[3].y *= NearClipInv;
			}
		}
		else
		{
			ClippedTris = 1;
			// perspective divide
			ProjectVec4(CurrentTri[0], TransformedTri[0]);
			ProjectVec4(CurrentTri[1], TransformedTri[1]);
			ProjectVec4(CurrentTri[2], TransformedTri[2]);
		}

		// translate & scale into viewport size
		m_ViewportTransform.TransformArray(CurrentTri, CurrentTri, 2+ClippedTris);

/*
		// backface culling
		ZVal = (CurrentTri[0].x - CurrentTri[1].x)*(CurrentTri[0].x - CurrentTri[2].x);
		ZVal += (CurrentTri[0].y - CurrentTri[1].y)*(CurrentTri[0].y - CurrentTri[2].y);
		if (ZVal < 0)
			continue;
*/

		ClipLocation = 3;
		for (; ClippedTris > 0; ClippedTris--)
		{

		if (ClipLocation != 3)
		{
			CurrentTri[ClipLocation] = CurrentTri[3];
		}

		// scan-conversion setup
		// 0 = highest, 2 = lowest
		if (CurrentTri[1].y < CurrentTri[0].y)
		{
			Swap(CurrentTri[1], CurrentTri[0]);
			ClipLocation = 1;
		}
		else
			ClipLocation = 0;
		if (CurrentTri[2].y < CurrentTri[0].y)
		{
			Swap(CurrentTri[2], CurrentTri[0]);
			if (ClipLocation != 0)
				ClipLocation = 2;
		}
		if (CurrentTri[2].y < CurrentTri[1].y)
		{
			Swap(CurrentTri[2], CurrentTri[1]);
			if (ClipLocation == 1)
				ClipLocation = 2;
			else if (ClipLocation == 2)
				ClipLocation = 1;
		}

		if (CurrentTri[0].z > 1 && CurrentTri[1].z > 1 && CurrentTri[2].z > 1)
			continue;

		// Z-gradient calculation
		ZVal = (CurrentTri[1].y - CurrentTri[0].y) / (CurrentTri[2].y - CurrentTri[0].y);
		DeltaZ = (CurrentTri[0].z + (ZVal)*(CurrentTri[2].z-CurrentTri[0].z) - CurrentTri[1].z);
		DeltaZ /=(CurrentTri[0].x + (ZVal)*(CurrentTri[2].x-CurrentTri[0].x) - CurrentTri[1].x);
		DepthDelta = (int)(DeltaZ * 0xffffffff);
		
		for (k = 0; k < 2; ++k)
		{
			if (k == 0)
			{
				// top half
				if ((int)CurrentTri[0].y == (int)CurrentTri[1].y)
				{
					// put 1 on the left
					if (CurrentTri[1].x > CurrentTri[0].x)
					{
						Swap(CurrentTri[0], CurrentTri[1]);
						if (ClipLocation == 0)
							ClipLocation = 1;
						else if (ClipLocation == 1)
							ClipLocation = 0;
					}
					// set up some values for the bottom half to start with
					GradientL = (CurrentTri[2].x - CurrentTri[1].x)/(CurrentTri[2].y - CurrentTri[1].y);
					GradientR = (CurrentTri[2].x - CurrentTri[0].x)/(CurrentTri[2].y - CurrentTri[0].y);
					ZGradientL = (CurrentTri[2].z - CurrentTri[1].z)/(CurrentTri[2].y - CurrentTri[1].y);
					StartX = CurrentTri[1].x;
					StopX  = CurrentTri[0].x;
					StartZ = CurrentTri[1].z;
					y = (int)max(0.0,CurrentTri[0].y);
					StopY = y;
					Left1 = deTRUE;
				}
				else
				{
					// scan-convert the top half
					StopY = (int)min(CurrentTri[1].y, CurrentTri[2].y);
					StopY = (int)min(StopY, m_Height);
					GradientL = (CurrentTri[1].x - CurrentTri[0].x)/(CurrentTri[1].y - CurrentTri[0].y);
					GradientR = (CurrentTri[2].x - CurrentTri[0].x)/(CurrentTri[2].y - CurrentTri[0].y);
					ZGradientL = (CurrentTri[1].z - CurrentTri[0].z)/(CurrentTri[1].y - CurrentTri[0].y);
					if (GradientR < GradientL)
					{
						Swap(GradientR, GradientL);
						ZGradientL = (CurrentTri[2].z - CurrentTri[0].z)/(CurrentTri[2].y - CurrentTri[0].y);
						Left1 = deFALSE;
					}
					else
					{
						Left1 = deTRUE;
					}
					
					StartX = StopX = CurrentTri[0].x;
					StartZ = CurrentTri[0].z;
					y = (int)CurrentTri[0].y;
				}
				if (y < 0)
				{
					StartZ += -y*ZGradientL;
					StartX += -y*GradientL;
					StopX += -y*GradientR;
					y = 0;
				}
			}
			else //if (k == 1)
			{
				// bottom half
				StopY = (int)max(CurrentTri[1].y, CurrentTri[2].y);
				StopY = (int)min(StopY, m_Height);
				y = (int)CurrentTri[1].y;
				if (Left1)
				{
					GradientL = (CurrentTri[2].x - CurrentTri[1].x)/(CurrentTri[2].y - CurrentTri[1].y);
					ZGradientL = (CurrentTri[2].z - CurrentTri[1].z)/(CurrentTri[2].y - CurrentTri[1].y);
				//	StartZGradient = (CurrentTri[2].z - CurrentTri[1].z)/(CurrentTri[2].y - CurrentTri[1].y);
					StartX = CurrentTri[1].x;
					StartZ = CurrentTri[1].z;
					if (y < 0)
					{
						StartZ += -y*ZGradientL;
						StartX += -y*GradientL;
						y = 0;
					}
				}
				else
				{
					GradientR = (CurrentTri[2].x - CurrentTri[1].x)/(CurrentTri[2].y - CurrentTri[1].y);
					StopX = CurrentTri[1].x, m_Width;
					if (y < 0)
					{
						StopX += -y*GradientR;
						y = 0;
					}
				}
			}

			// foreach scanline
			for (; y < StopY; ++y)
			{
				index = y*m_Width;
				RealStopX = (int)min(StopX, m_Width);
				ZVal = (RealStopX-StartX)*DeltaZ + StartZ;
				if (ZVal > 1)
				{
					if (DeltaZ <= 0)
						goto scanline_end;
					while (ZVal > 1)
					{
						RealStopX--;
						ZVal -= DeltaZ;
					}
				}
				x = (int)StartX;
				ZVal = StartZ;
				if (x < 0)
				{
					ZVal += -x*DeltaZ;
					x = 0;
				}
				if (ZVal > 1)
				{
					if (DeltaZ >= 0)
						goto scanline_end;
					while (ZVal > 1)
					{
						x++;
						ZVal += DeltaZ;
					}
				}
				DepthVal = (DWORD)(ZVal * 0xffffffff);
				if (TestOnly)
				{
					for (; x < RealStopX; ++x)
					{
#if OCCLUDE_16BIT
						if ((DepthVal>>16) < m_Buffer[index+x])
#else
						if (DepthVal < m_Buffer[index+x])
#endif
						{
							PixelsRendered++;
						}
						ZVal += DeltaZ;
						DepthVal += DepthDelta;
					}
				}
				else
				{
					for (; x < RealStopX; ++x)
					{
#if OCCLUDE_16BIT
						if ((DepthVal>>16) < m_Buffer[index+x])
#else
						if (DepthVal < m_Buffer[index+x])
#endif
						{
							//PixelsRendered++;
#if OCCLUDE_16BIT
							m_Buffer[index+x] = (BufferType)(DepthVal>>16);
#else
							m_Buffer[index+x] = DepthVal;
#endif
						}
						//ZVal += DeltaZ;
						DepthVal += DepthDelta;
					}
				}
			scanline_end:
				StartZ += ZGradientL;
				// sub-pixel accuracy
				StartX += GradientL * SUB_PIX((float)y);
				StopX += GradientR * SUB_PIX((float)y);
			}
		}
		} // for (ClippedTris >= 0)
	}

	return PixelsRendered;
}

