//=============================================================================
//
// Copyright 1998 by Captivation Digital Laboratories, Inc.
// All Rights Reserved.
//
//=============================================================================
//
// "KRAD" -- Kamui Rendering/Animation Demonstration
//
// Definitions of Scene Management classes
//		SceneNode	- primarily tree management and virtual holders
//		SceneRoot	- owner of the tree; has main loops
//		SceneCamera	- the camera class is tightly meshed with SceneRoot
//
//=============================================================================
//-----------------------------------------------------------------------------
// $Revision: 8 $
// $NoKeywords: $
//=============================================================================

#include "krad.h"
#include "scene3d.h"
#include "globals.h"

//=============================================================================
//============================================================================= MODULE DEFINITIONS
//=============================================================================
uint	SceneNodeCount = 0;

//=============================================================================
//============================================================================= CLASS SceneNode
//=============================================================================

//-----------------------------------------------------------------------------
//----------------------------------------------------------------------------- SceneNode Tree Management
//-----------------------------------------------------------------------------
// The Tree Management routines are written with heavy bulletproofing in
// mind. The existence of subtle errors can be difficult to detect and can
// introduct odd errors later.
//-----------------------------------------------------------------------------

//============================================================================= SceneNode::SceneNode()
// The basic constructor
//-----------------------------------------------------------------------------
SceneNode::SceneNode (NODE_DELETE_STYLE ndel, SceneNode* parent)
{
	SceneNodeCount++;

	// is it auto-deleted when we're done with it?
	mDelStyle		= ndel;

	// initialize the structure
	mParent			= NULL;
	mNextSibling	= NULL;
	mPrevSibling	= NULL;
	mFirstChild		= NULL;
	mLastChild		= NULL;

	mBoundingRadius = 0.0f;
	mListBits		= NODE_LIST_OPAQUE;

	// initialize the coordinate space members
	mTransform = mToWorld = Identity;
	mToWorldTimeStamp = 0;

	// connect it in
	if (parent)
		AttachToParent (parent);
}

//============================================================================= SceneNode::~SceneNode()
// The basic destructor
//-----------------------------------------------------------------------------
SceneNode::~SceneNode()
{
	// disconnect from the tree
	if (mParent)
		Detach();

	// take out any "auto-delete" children; disconnect "manual-delete" children
	DestroyChildren();

	SceneNodeCount--;
}

//============================================================================= SceneNode::AttachToParent()
// This connects a node/branch to as the "last child" of the specified
// parent node.
//
// If the node currently has a parent, it is detached first -- the effect
// is that of "moving" a node.
//
// NOTE: this function has multiple exits
//-----------------------------------------------------------------------------
void SceneNode::AttachToParent (SceneNode* newparent)
{
	// detach from existing parent first
	if (mParent)
		Detach();

	assert (mParent==NULL);
	assert (mNextSibling==NULL);
	assert (mPrevSibling==NULL);

	assert (newparent);

	// CASE: NEW PARENT HAS NO EXISTING CHILDREN
	if ((newparent->mLastChild) == NULL)
	{
		assert ((newparent->mFirstChild) == NULL);

		mParent = newparent;
		mParent->mFirstChild = this;
		mParent->mLastChild = this;
		return;
	}

	// CASE: NEW PARENT HAS EXISTING CHILDREN
	{
		assert (newparent->mFirstChild);
		assert (newparent->mLastChild);
		assert ((newparent->mLastChild->mNextSibling)==NULL);
		assert ((newparent->mLastChild->mParent)==newparent);

		mParent = newparent;
		mPrevSibling = mParent->mLastChild;
		mParent->mLastChild->mNextSibling = this;
		mParent->mLastChild = this;
	}
}

//============================================================================= SceneNode::DestroyChildren
// Child nodes are "destroyed"
//		- they are detached from the tree
//		- they are "deleted" if the NODE_DELETE_STYLE is "AUTO" flag is set
//
// This function winds up being recursive. The "delete" call will call
// DestroyChildren to take care of continuing depths.
//-----------------------------------------------------------------------------
void SceneNode::DestroyChildren (void)
{
	// -- tree walk must be careful so we don't lose position
	SceneNode*	p = mFirstChild;
	SceneNode*	next;

	while (p)
	{
		next = p->mNextSibling;
		p->Detach();

		if (p->mDelStyle==NODE_DEL_AUTO)
			delete p;

		p=next;
	}
}

//============================================================================= SceneNode::Detach
// this disconnects a branch from the tree, isolating it.
//
// the link must be removed from it's parent's list of children
// the link must be removed from the siblings.
//
// NOTE: this function has multiple exits
//-----------------------------------------------------------------------------
void SceneNode::Detach (void)
{
	// CASE: NOT A CHILD -- handle trivial case of being unattached
	if (mParent==NULL)
	{
		assert (mNextSibling==NULL);
		assert (mPrevSibling==NULL);
		return;
	}

	// now we know we have an actual parent, make sure it has children
	assert (mParent);
	assert (mParent->mFirstChild);
	assert (mParent->mLastChild);

	// CASE: ONLY-CHILD -- This can actually be handled automatically
	// by the first and last child cases, but this aids in more
	// robust error checking during debug mode.
	if ((mParent->mFirstChild) == (mParent->mLastChild))
	{
		assert ((mParent->mFirstChild)==this);
		assert 	(mNextSibling==NULL);
		assert 	(mPrevSibling==NULL);

		mParent->mFirstChild = NULL;
		mParent->mLastChild = NULL;

		mParent		 = NULL;

		return;
	}

	// CASE: FIRST CHILD OF MULTIPLE
	if ((mParent->mFirstChild) == this)
	{
		assert 	(mPrevSibling == NULL);
		assert 	(mNextSibling);
		assert ((mNextSibling->mParent) == mParent);
		assert ((mNextSibling->mPrevSibling) == this);

		mNextSibling->mPrevSibling = NULL;
		mParent->mFirstChild = mNextSibling;

		mParent		 = NULL;
		mNextSibling = NULL;
		return;
	}

	// CASE: LAST CHILD OF MULTIPLE
	if ((mParent->mLastChild) == this)
	{
		assert 	(mNextSibling == NULL);
		assert 	(mPrevSibling);
		assert ((mPrevSibling->mParent) == mParent);
		assert ((mPrevSibling->mNextSibling) == this);

		mPrevSibling->mNextSibling = NULL;
		mParent->mLastChild = mPrevSibling;

		mParent		 = NULL;
		mPrevSibling = NULL;
		return;
	}

	// CASE: MIDDLE CHILD OF MULTIPLE
	{
		assert ((mParent->mFirstChild)!=this);
		assert ((mParent->mLastChild)!=this);

		assert	(mNextSibling);
		assert	(mPrevSibling);

		assert ((mNextSibling->mParent) == mParent);
		assert ((mPrevSibling->mParent) == mParent);

		assert ((mNextSibling->mPrevSibling) == this);
		assert ((mPrevSibling->mNextSibling) == this);

		mPrevSibling->mNextSibling = mNextSibling;
		mNextSibling->mPrevSibling = mPrevSibling;

		mParent		 = NULL;
		mNextSibling = NULL;
		mPrevSibling = NULL;
		return;
	}
}

//============================================================================= SceneNode::DFNext
// Iterates a forward Depth-First search through nodes
//
// Parents are always evaluated before children; siblings are evaluated in order
//
// This function can yield incorrect results if node are moved or deleted
// during the iteration. As a result, care should be used by keeping track of
// a local "next" pointer during deletion. Movement should just be avoided.
//-----------------------------------------------------------------------------
SceneNode* SceneNode::DFNext(void)
{
	// if the current node has a child, it goes next
	if (mFirstChild)
		return(mFirstChild);

	// the current node has no children, the next sibling is called
	if (mNextSibling)
		return(mNextSibling);

	// no children, no siblings -- find a [nth order]parent that has a sibling
	SceneNode* p = this;
	while (p->mParent)
	{
		p = p->mParent;
		if (p->mNextSibling)
			return(p->mNextSibling);
	}

	// no nodes left to do...
	return(NULL);
}

//=============================================================================
//============================================================================= CLASS SceneRoot
//=============================================================================
// The SceneRoot is the center of attention for rendering the scene.
//
// In order to maintain performance, a number of structures are used:
//
// mListOpaque, et. al.
// --------------------
//		These four lists are used to track which SceneNodes are active. If
//		a node is found to be active (falling within the view frustrum of
//		any active camera), it is added to one of the Active lists.
//
//		The lists are sorted by ListType to allow the use of Kamui's Direct
//		rendering mode.
//
//		The lists have a dynamic size that grows when needed. Note that it
//		does not return added space when it is no longer needed.
//
//		The lists are zero-terminated at the end of construction, prior to
//		rendering traversal. Otherwise, the lists are left dirty.
//
// mActiveCameras
// --------------
//		This array of 32 SceneCamera pointers is used to track which
//		Cameras are "Active", or contribute to a Scene's rendering tasks.
//
//		The positions in the array also correspond to a bitfield which is
//		used for gross rejection.
//
//		The zero'th entry of the array is always the primary camera. It
//		must exists. It is used to render the frame buffer of display.
//-----------------------------------------------------------------------------

//============================================================================= SceneRoot::SceneRoot()
// This constructor initializes the scene state and renderer
//-----------------------------------------------------------------------------
SceneRoot::SceneRoot (NODE_DELETE_STYLE ndel)
		: 	SceneNode (ndel, NULL),
			mListOpaque		(NULL),
			mListOpaqueMod	(NULL),
			mListTrans		(NULL),
			mListTransMod	(NULL),
			mListCount		(0)
{
	// -- initialize the active camera array --
	for (int i=0; i<MAX_ACTIVE_CAMERAS; i++ )
		mActiveCameras[i] = NULL;
}

//============================================================================= SceneRoot::~SceneRoot()
// This constructor initializes the scene state and renderer
//-----------------------------------------------------------------------------
SceneRoot::~SceneRoot ()
{
	// -- deallocate the list space --
	if (mListOpaque)		delete [] mListOpaque;
	if (mListOpaqueMod)		delete [] mListOpaqueMod;
	if (mListTrans)			delete [] mListTrans;
	if (mListTransMod)		delete [] mListTransMod;
}

//============================================================================= SceneRoot::ActivatePrimaryCamera()
void SceneRoot::ActivatePrimaryCamera (SceneCamera& camera)
{
	// -- if the camera is already primary, go away
	if (mActiveCameras[0] = &camera)
		return;

	// -- if the camera is already active, stop it
	if (camera.IsActive())
		DeactivateCamera(camera);

	// -- deactivate the current primary camera
	if (mActiveCameras[0])
		DeactivateCamera(*mActiveCameras[0]);

	// -- make this camera the primary --
	mActiveCameras[0] = &camera;
	camera.IsActive() = true;
}

//============================================================================= SceneRoot::ActivateCamera()
void SceneRoot::ActivateCamera (SceneCamera& camera)
{
	// -- if the camera is already active, go away
	if (camera.IsActive())
		return;

	// -- find a camera slot
	for (int i=1; i<MAX_ACTIVE_CAMERAS; i++ )
	{
		if (mActiveCameras[i] == NULL)
		{	// -- turn it off
			mActiveCameras[i] = &camera;
			camera.IsActive() = true;
		}
	}
	assert (0);	// we ran out of camera slots!
}

//============================================================================= SceneRoot::DeactivateCamera()
void SceneRoot::DeactivateCamera (SceneCamera& camera)
{
	// -- find the camera
	for (int i=0; i<MAX_ACTIVE_CAMERAS; i++ )
	{
		if (mActiveCameras[i] == &camera)
		{	// -- turn it off
			mActiveCameras[i] = NULL;
			camera.IsActive() = false;
			return;
		}
	}
}

//============================================================================= SceneRoot::GetNodeCount()
// Returns the number of active nodes in the scene
//-----------------------------------------------------------------------------
uint32 SceneRoot::GetNodeCount (void)
{
	return(SceneNodeCount);
}

//============================================================================= SceneRoot::ValidateCameraList()
// Packs the camera array to eliminate dead space
// Returns: the highest camera index used.
//-----------------------------------------------------------------------------
uint32 SceneRoot::ValidateCameraList (void)
{
	// -- make sure we have a primary --
	assert (mActiveCameras[0]);

	// -- for all the non-primary cameras --
	int position=1;
	for (int i=1; i<MAX_ACTIVE_CAMERAS; i++)
	{	// -- get a camera
		if (mActiveCameras[i])
		{
			if (i==position)
			{	// -- this camera is okay --
				position++;
			}
			else
			{	// -- move this camera up --
				assert (mActiveCameras[position] == NULL);
				mActiveCameras[position] = mActiveCameras[i];
				mActiveCameras[i] = NULL;
				position++;
			}
		}
	}
	return(position-1);
}

//============================================================================= SceneRoot::ValidateNodeLists()
// Ensures that the node lists are legal sized
//-----------------------------------------------------------------------------
void SceneRoot::ValidateNodeLists (void)
{
	// -- are the lists big enough? --
	if (GetNodeCount() >= mListCount)
	{
		// -- deallocate the current list space --
		if (mListOpaque)		delete [] mListOpaque;
		if (mListOpaqueMod)		delete [] mListOpaqueMod;
		if (mListTrans)			delete [] mListTrans;
		if (mListTransMod)		delete [] mListTransMod;

		// -- determine new size of lists --
		mListCount = ((GetNodeCount()/100)+1)*100;	// new size is alloc'd with a granularity of 100
		assert (GetNodeCount() < mListCount);

		// -- allocate the new lists --
		mListOpaque		= new SceneNodeDatum [mListCount];
		mListOpaqueMod	= new SceneNodeDatum [mListCount];
		mListTrans		= new SceneNodeDatum [mListCount];
		mListTransMod	= new SceneNodeDatum [mListCount];
	}

	// -- just to make sure --
	assert (mListOpaque);
	assert (mListOpaqueMod);
	assert (mListTrans);
	assert (mListTransMod);
}

//============================================================================= SceneRoot::EvaluateAndRender()
// This is essentially the "main loop" of the renderer
//-----------------------------------------------------------------------------
bool SceneRoot::EvaluateAndRender (void)
{
	// -- Make sure we're neat and tidy --
	uint32 topcam = ValidateCameraList();
	ValidateNodeLists();

	// -- Prep the active lists --
	SceneNodeDatum* currOpaque		= mListOpaque;
	SceneNodeDatum* currOpaqueMod	= mListOpaqueMod;
	SceneNodeDatum* currTrans		= mListTrans;
	SceneNodeDatum* currTransMod	= mListTransMod;

	// -----------------------------------
	// -- Walk the tree and build the Active lists --
	SceneNode* ptr = this;
	SceneNode* next= ptr->DFNext();
	while (next)
	{
		ptr = next;
		next = ptr->DFNext();
		// ### DETECT Kills, Remove Me's, Disables, Sleeps, etc

		// -- call the update function --
		ptr->EvaluateState();

		// -- make the ToWorld matrix --
		//### need time stamp management
		ptr->mToWorld = ptr->mParent->mToWorld * ptr->mTransform;

		// -- test for visibility to all cameras --
		uint32 visible = 0;
		uint32 cambit  = 1;
		for (uint32 cam=0; cam<= topcam; cam++)
		{
			if (ptr->InFrustrum())
				visible |= cambit;
			cambit = cambit << 1;
		}

		// -- Visible nodes get added to active lists, by list type --
		if (visible)
		{
			NODE_LIST_BITS lbits = ptr->GetListTypes();

			if (lbits & NODE_LIST_OPAQUE)
			{
				currOpaque->mNodePtr		= ptr;
				currOpaque->mCameraBits		= visible;
				currOpaque++;
			}

			if (lbits & NODE_LIST_OPAQUE_MODIFIER)
			{
				currOpaqueMod->mNodePtr		= ptr;
				currOpaqueMod->mCameraBits	= visible;
				currOpaqueMod++;
			}

			if (lbits & NODE_LIST_TRANS)
			{
				currTrans->mNodePtr			= ptr;
				currTrans->mCameraBits		= visible;
				currTrans++;
			}

			if (lbits & NODE_LIST_TRANS_MODIFIER)
			{
				currTransMod->mNodePtr		= ptr;
				currTransMod->mCameraBits	= visible;
				currTransMod++;
			}
		}
	}	// while (next)

	// -----------------------------------
	// -- Terminate the active lists --
	currOpaque		->mNodePtr	= NULL;
	currOpaqueMod	->mNodePtr	= NULL;
	currTrans		->mNodePtr	= NULL;
	currTransMod	->mNodePtr	= NULL;

	// -----------------------------------
	// ### IF THE LISTS NEED TO BE SORTED AT ALL, NOW'S A GOOD SPOT

	// -----------------------------------
	// ### calc lights by running through active list (not for modifiers)
	// ###	transform each light to object space, assume all verts at 0,0,0

	// -----------------------------------
	// -- RENDER EACH CAMERA --
	NODE_LIST_BITS	nlbit;
	int32			cam = topcam;
	uint32			cambit = 1 << topcam;
	kmatrix			WorldToScreen;
	kmatrix			NodeToScreen;

	while (cam>=0)
	{
		// -- copy the trans matrix --
		WorldToScreen = mActiveCameras[cam]->mToScreen;

		SceneNodeDatum* active;
		for (int list = 0; list<4; list++ )
		{	// -- for each list type --
			switch (list)
			{	// -- pick the right list --
				case 0:		active = mListOpaque;		nlbit = NODE_LIST_OPAQUE;			break;
				case 1:		active = mListOpaqueMod;	nlbit = NODE_LIST_OPAQUE_MODIFIER;	break;
				case 2:		active = mListTrans;		nlbit = NODE_LIST_TRANS;			break;
				case 3:		active = mListTransMod;		nlbit = NODE_LIST_TRANS_MODIFIER;	break;
				default:	assert(0);
							active = mListOpaque;		nlbit = NODE_LIST_OPAQUE;			break;
			}

			// -- run the list --
			while (active->mNodePtr)
			{	// -- process each node that is visible to current camera --
				if ((active->mCameraBits) & cambit)
				{
					NodeToScreen = WorldToScreen * active->mNodePtr->mToWorld;
					active->mNodePtr->TransformAndRegisterTristrips(&NodeToScreen, nlbit);
				}
				active++;
			}

			// -- tag the end of list for Kamui --
			KAMUI_TRY (KAMUI_SET_END_OF_LIST());
		}

		// -- RENDER IT --
		if (cam)
		{
			//### KAMUI_TRY (KAMUI_RENDER_TEXTURE (texturebufferdescptr));
		}
		else
		{
			KAMUI_TRY (KAMUI_RENDER());
			KAMUI_TRY (kmFlipFrameBuffer());
		}

		// -- GO ON TO NEXT CAMERA --
		cambit = cambit >> 1;
		cam--;
	}	// while (cam)

	// -----------------------------------
	// -- BYE --
	return(true);

}

//=============================================================================
//============================================================================= CLASS SceneCamera
//=============================================================================

//============================================================================= SceneCamera::SceneCamera()
//-----------------------------------------------------------------------------
SceneCamera::SceneCamera (NODE_DELETE_STYLE	ndel, SceneNode* parent)
		:	SceneNode	(ndel, parent),
			mActive		(FALSE)
{
	mCenterX = 320.0f;
	mCenterY = 240.0f;
	SetFOV (90.0);
}

//============================================================================= SceneCamera::~SceneCamera()
//-----------------------------------------------------------------------------
SceneCamera::~SceneCamera ()
{

}

//============================================================================= SceneCamera::Activate()
void SceneCamera::Activate (void)
{
	theScene->ActivateCamera(*this);
}

//============================================================================= SceneCamera::ActivateAsPrimary()
void SceneCamera::ActivateAsPrimary	(void)
{
	theScene->ActivatePrimaryCamera(*this);
}

//============================================================================= SceneCamera::Deactivate()
void SceneCamera::Deactivate (void)
{
	theScene->DeactivateCamera(*this);
}

//============================================================================= SceneCamera::EvaluateState()
void SceneCamera::EvaluateState (void)
{
	static float zed = -1000.0f;			//### HACK
	zed += 0.5f;							//### HACK
	kvector ctrans (0,zed,0);				//### HACK
	mTransform.t = ctrans;					//### HACK

	mFromWorld.inverse(mTransform);

	mToScreen = mScreenProjection * mFromWorld;
}

//============================================================================= SceneCamera::SetFOV()
// This function calculates the matrix needed to transform worldspace
// to view space, minus the perspective divide
//
// FOV is the entire angle of view. If the screen is non-square, the width
// is used for coverage. This will be overkill for the vertical, but be lossy
// in the corners. It's close enough for us though.
//
// The FOV is used to calculate the depth value:
//
//		tan (FOV/2) = height / depth;
//
//-----------------------------------------------------------------------------
void SceneCamera::SetFOV	(float newfov)
{
	mFOV	= newfov;
	mDepth	= mCenterX / (float) atan (DEG2RAD(mFOV));		// CenterX: width is a little more natural than height...

	kmatrix CameraAxisSwapper	(	kvector( 1.0f, 0.0f, 0.0f),
							 		kvector( 0.0f, 0.0f,-1.0f),
							 		kvector( 0.0f, 1.0f, 0.0f),
							 		kvector( 0.0f, 0.0f, 0.0f));	// position

	kmatrix CameraDepthScaler	(	kvector(mDepth,  0.0f, 0.0f),
							 		kvector(  0.0f,mDepth, 0.0f),
							 		kvector(  0.0f,  0.0f, 1.0f),
							 		kvector(  0.0f,  0.0f, 0.0f));	// position

	mScreenProjection = CameraDepthScaler * CameraAxisSwapper;
}
//=============================================================================	END-OF-FILE