Webcam/include/engine/core/octree_renderable.cpp

/* -----------------------------------------------------------------------------
	GSFramework
	Copyright 2001-2013 Emmanuel Julien. All Rights Reserved.
----------------------------------------------------------------------------- */


		#include "core/octree_renderable.h"
		#include "core/camera.h"
		#include "timing/benchmark.h"
		#include "sort/sort.h"
		#include "log/log.h"

		using namespace GS;
		using namespace GS::Core;


//------------------------------------------------------------------------------
OctreeCullingSystem::Node *OctreeCullingSystem::InsertList(List <CachedNode *> &list)
{
	AutoPtr <Node> node(new Node);
	if	(node.IsNull())
		return NULL;

	bool to_child = false;
	if	(list.GetCount() <= 4)
		to_child = true;

	else
	{
		// Build list AABB.
		bool first = true;

		MinMax mm;
		ListForeachPtr(CachedNode *, cnode, list)
		{
			if	(first)
					mm = cnode->minmax;
			else	mm.Grow(cnode->minmax);
			first = false;
		}

		// Select split axis.
		Vector4	size = mm.mx - mm.mn;

		uint	axis = 2;
				if	((size.x > size.y) && (size.x > size.z))
				axis = 0;
		else	if	((size.y > size.x) && (size.y > size.z))
				axis = 1;

		List <CachedNode *> split_list[2];

		// Check list for renderable occupying more than 50% of the split axis.
		bool exclusion_split = false;
		float size_threshold = size[axis] * 0.5f;

		ListForeachPtr(CachedNode *, cnode, list)
			if	((cnode->minmax.mx[axis] - cnode->minmax.mn[axis]) > size_threshold)
			{
				exclusion_split = true;
				break;
			}

		if	(exclusion_split)
			ListForeachPtr(CachedNode *, cnode, list)
				split_list[(cnode->minmax.mx[axis] - cnode->minmax.mn[axis]) > size_threshold ? 0 : 1].Add(cnode);
		else
		{
			float split_coord = (mm.mn[axis] + mm.mx[axis]) * 0.5f;
			ListForeachPtr(CachedNode *, cnode, list)
				split_list[cnode->minmax.GetCenter()[axis] < split_coord ? 0 : 1].Add(cnode);
		}

		// Recurse split lists.
		if	(!split_list[0].GetCount() || !split_list[1].GetCount())
			to_child = true;

		else
		{
			node->child[0] = InsertList(split_list[0]);
			node->child[1] = InsertList(split_list[1]);
			node->minmax = node->child[0]->minmax;
			node->minmax.Grow(node->child[1]->minmax);
		}
	}

	if	(to_child)
	{
		if	(node->cached_node.Allocate(list.GetCount()))
		{
			bool first = true;

			uint n = 0;
			ListForeachPtr(CachedNode *, cnode, list)
			{
				node->cached_node[n++] = cnode;
				if	(first)
						node->minmax = cnode->minmax;
				else	node->minmax.Grow(cnode->minmax);
				first = false;
			}
		}
		else
			__ERR__(__LOG_E__ << "Failed to allocatel leaf container.\n", NULL)
	}
	return node.Detach();
}
bool				OctreeCullingSystem::Update()
{
	root = NULL;

	if	(renderable_list.GetCount())
	{
		if	(!nodes.Allocate(renderable_list.GetCount()))
			return false;

		uint n = 0;
		ArrayListForeachPtr(Renderable *, renderable, renderable_list)
		{
			nodes[n].renderable = renderable;
			renderable->ComputeRenderableMinMax(nodes[n].minmax);
			++n;
		}

		// Build root list.
		List <CachedNode *> root_list;
		for	(uint n = 0; n < nodes.GetCount(); ++n)
			root_list.Add(&nodes[n]);

		// Perform insertion.
		root = InsertList(root_list);
	}

	dirty = false;
	return true;
}
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
void				OctreeCullingSystem::ComputeRenderableMinMax(MinMax &mm)
{
	if	(root)
		mm = root->minmax;
}
void				OctreeCullingSystem::GetNodeRenderablePrimitive(Node *node, const Camera &view, const Camera &default_view, Stack <Render::Primitive *> &list, Context ctx)
{
	// Grab leaf content.
	if	(uint count = node->cached_node.GetCount())
	{
		for	(uint n = 0; n < count; ++n)
		{
			Renderable *renderable = node->cached_node[n]->renderable;
			if	(renderable->IsRenderable())
				renderable->GetRenderablePrimitiveList(view, default_view, list, ctx, false);
		}
	}
	else
	{
		// Gather branches.
		GetNodeRenderablePrimitive(node->child[0], view, default_view, list, ctx);
		GetNodeRenderablePrimitive(node->child[1], view, default_view, list, ctx);
	}
}
void				OctreeCullingSystem::CullNodeRenderablePrimitive(Node *node, const Camera &view, const Camera &default_view, Stack <Render::Primitive *> &list, Context ctx)
{
	if	(node->cached_node.GetCount())
		GetNodeRenderablePrimitive(node, view, default_view, list, ctx);

	else
		switch (view.frustum.ClassifyMinMax(node->minmax))
		{
			case Frustum::Outside:
				break;
			case Frustum::Clipped:
				CullNodeRenderablePrimitive(node->child[0], view, default_view, list, ctx);
				CullNodeRenderablePrimitive(node->child[1], view, default_view, list, ctx);
				break;
			case Frustum::Inside:
				GetNodeRenderablePrimitive(node->child[0], view, default_view, list, ctx);
				GetNodeRenderablePrimitive(node->child[1], view, default_view, list, ctx);
				break;
		}
}
uint				OctreeCullingSystem::GetRenderablePrimitiveList(const Camera &view, const Camera &default_view, Stack <Render::Primitive *> &list, Context ctx, bool cull)
{
	// Rebuild tree if octree is dirty.
	if	(dirty)
		Update();

	if	(root)
	{
		if	(cull)
				CullNodeRenderablePrimitive(root, view, default_view, list, ctx);
		else	GetNodeRenderablePrimitive(root, view, default_view, list, ctx);
	}
	return renderable_list.GetCount();
}
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
void				OctreeCullingSystem::AddRenderable(Renderable *r)
{
	renderable_list.Add(r);
	dirty = true;
}
void				OctreeCullingSystem::DeleteRenderable(Renderable *r)
{
	renderable_list.Remove(r);
	dirty = true;
}
//------------------------------------------------------------------------------