--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/engine/core/view/layercache.cpp	Thu Apr 29 13:51:45 2010 +0000
@@ -0,0 +1,345 @@
+/***************************************************************************
+ *   Copyright (C) 2005-2008 by the FIFE team                              *
+ *   http://www.fifengine.de                                               *
+ *   This file is part of FIFE.                                            *
+ *                                                                         *
+ *   FIFE is free software; you can redistribute it and/or                 *
+ *   modify it under the terms of the GNU Lesser General Public            *
+ *   License as published by the Free Software Foundation; either          *
+ *   version 2.1 of the License, or (at your option) any later version.    *
+ *                                                                         *
+ *   This library is distributed in the hope that it will be useful,       *
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
+ *   Lesser General Public License for more details.                       *
+ *                                                                         *
+ *   You should have received a copy of the GNU Lesser General Public      *
+ *   License along with this library; if not, write to the                 *
+ *   Free Software Foundation, Inc.,                                       *
+ *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA          *
+ ***************************************************************************/
+
+// Standard C++ library includes
+
+// 3rd party library includes
+#include <SDL.h>
+
+// FIFE includes
+// These includes are split up in two parts, separated by one empty line
+// First block: files included from the FIFE root src directory
+// Second block: files included from the same folder
+
+#include "model/metamodel/grids/cellgrid.h"
+#include "model/metamodel/action.h"
+#include "model/structures/layer.h"
+#include "model/structures/instance.h"
+#include "model/structures/location.h"
+#include "util/base/exception.h"
+#include "util/log/logger.h"
+#include "util/math/fife_math.h"
+#include "util/math/angles.h"
+#include "video/renderbackend.h"
+#include "video/image.h"
+#include "video/imagepool.h"
+#include "video/animation.h"
+#include "video/animationpool.h"
+
+#include "camera.h"
+#include "layercache.h"
+#include "visual.h"
+
+
+namespace FIFE {
+	static Logger _log(LM_CAMERA);
+
+	class CacheLayerChangeListener : public LayerChangeListener {
+	public:
+		CacheLayerChangeListener(LayerCache* cache)
+		{
+			m_cache = cache;
+		}
+		virtual ~CacheLayerChangeListener() {};
+
+		virtual void onLayerChanged(Layer* layer, std::vector<Instance*>& instances)
+		{
+			for(std::vector<Instance*>::iterator i = instances.begin();
+				i != instances.end(); ++i) {
+				m_cache->updateInstance(*i);
+			}
+		}
+
+		virtual void onInstanceCreate(Layer* layer, Instance* instance)
+		{
+			m_cache->addInstance(instance);
+		}
+
+		virtual void onInstanceDelete(Layer* layer, Instance* instance)
+		{
+			m_cache->removeInstance(instance);
+		}
+	private:
+		LayerCache* m_cache;
+	};
+
+	LayerCache::LayerCache(Camera* camera, ImagePool* image_pool, AnimationPool* animation_pool) {
+		m_camera = camera;
+		m_image_pool = image_pool;
+		m_animation_pool = animation_pool;
+		m_layer = 0;
+		m_tree = 0;
+	}
+
+	LayerCache::~LayerCache() {
+		m_layer->removeChangeListener(m_layer_observer);
+		delete m_layer_observer;
+		delete m_tree;
+	}
+
+	void LayerCache::setLayer(Layer* layer) {
+		m_layer = layer;
+		m_layer_observer = new CacheLayerChangeListener(this);
+		layer->addChangeListener(m_layer_observer);
+		reset();
+	}
+
+	void LayerCache::reset() {
+		m_instances.clear();
+		delete m_tree;
+		m_tree = new CacheTree;
+		const std::vector<Instance*>& instances = m_layer->getInstances();
+		for(std::vector<Instance*>::const_iterator i = instances.begin();
+			i != instances.end(); ++i) {
+			addInstance(*i);
+		}
+	}
+
+	void LayerCache::addInstance(Instance* instance) {
+		if(m_instance_map.find(instance)!=m_instance_map.end()) {
+			throw new Duplicate(instance->getId());
+		}
+
+		RenderItem item;
+		Entry entry;
+		item.instance = instance;
+		m_instances.push_back(item);
+		m_instance_map[instance] = m_instances.size() - 1;
+
+		entry.node = 0;
+		entry.instance_index = m_instances.size() - 1;
+		entry.entry_index = m_entries.size();
+		m_entries.push_back(entry);
+		updateEntry(m_entries.back());
+	}
+
+	void LayerCache::removeInstance(Instance* instance) {
+		// FIXME
+		// The way LayerCache stores it's data
+		// it's pretty much impossible to cleanly remove
+		// added instances.
+
+		// This has to get fixed.
+		if(m_instance_map.find(instance) == m_instance_map.end()) {
+			throw new NotFound(instance->getId());
+		}
+		Entry& item = m_entries[m_instance_map[instance]];
+		assert(item.instance_index == m_instance_map[instance]);
+
+		if(item.node)
+			item.node->data().erase(item.entry_index);
+		item.node = 0;
+		item.instance_index = unsigned(-1);
+		m_instance_map.erase(instance);
+	}
+
+	void LayerCache::updateInstance(Instance* instance) {
+		Entry& entry = m_entries[m_instance_map[instance]];
+		updateEntry(entry);
+	}
+
+	void LayerCache::updateEntry(LayerCache::Entry& item) {
+		if(item.instance_index ==  unsigned(-1)) {
+			return;
+		}
+		if(item.node) {
+			item.node->data().erase(item.entry_index);
+		}
+		RenderItem& render_item = m_instances[item.instance_index];
+		Instance* instance = render_item.instance;
+
+		DoublePoint3D screen_position = m_camera->toVirtualScreenCoordinates(instance->getLocationRef().getMapCoordinates());
+
+		render_item.facing_angle = getAngleBetween(instance->getLocationRef(), instance->getFacingLocation());
+		int angle = m_camera->getRotation() + render_item.facing_angle + instance->getRotation();
+
+		Image* image = NULL;
+		Action* action = instance->getCurrentAction();
+		int w = 0;
+		int h = 0;
+		int xshift = 0;
+		int yshift = 0;
+
+		if(!action) {
+			// Try static images then default action.
+			int image_id = render_item.getStaticImageIndexByAngle(angle, instance);
+			if(image_id == Pool::INVALID_ID) {
+				action = instance->getObject()->getDefaultAction();
+			} else {
+				image = &m_image_pool->getImage(image_id);
+			}
+		}
+		item.force_update = bool(action);
+
+		if(action) {
+			int animation_id = action->getVisual<ActionVisual>()->getAnimationIndexByAngle(render_item.facing_angle + m_camera->getRotation());
+			Animation& animation = m_animation_pool->getAnimation(animation_id);
+			unsigned animation_time = instance->getActionRuntime() % animation.getDuration();
+			image = animation.getFrameByTimestamp(animation_time);
+
+			int facing_angle = render_item.facing_angle;
+			if (facing_angle < 0){
+				facing_angle += 360;
+			}
+			instance->setRotation(facing_angle);
+		}
+
+		if (image) {
+			w = image->getWidth();
+			h = image->getHeight();
+			xshift = image->getXShift();
+			yshift = image->getYShift();
+		}
+
+		screen_position.x -= w / 2;
+		screen_position.x += xshift;
+		screen_position.y -= h / 2;
+		screen_position.y += yshift;
+
+		render_item.image = image;
+		render_item.screenpoint = screen_position;
+
+		render_item.bbox.x = screen_position.x;
+		render_item.bbox.y = screen_position.y;
+		render_item.bbox.w = w;
+		render_item.bbox.h = h;
+
+		render_item.dimensions.x = screen_position.x;
+		render_item.dimensions.y = screen_position.y;
+		render_item.dimensions.w = w;
+		render_item.dimensions.h = h;
+
+		CacheTree::Node* node = m_tree->find_container(render_item.bbox);
+		item.node = node;
+		node->data().insert(item.entry_index);
+	}
+
+	class CacheTreeCollector {
+			std::vector<int>& m_indices;
+			Rect m_viewport;
+		public:
+			CacheTreeCollector(std::vector<int>& indices, const Rect& _viewport)
+			: m_indices(indices), m_viewport(_viewport) {
+			}
+			bool visit(LayerCache::CacheTree::Node* node, int d = -1);
+	};
+
+	bool CacheTreeCollector::visit(LayerCache::CacheTree::Node* node, int d) {
+		if(!m_viewport.intersects(Rect(node->x(), node->y(),node->size(),node->size())))
+			return false;
+		std::set<int>& list = node->data();
+		for(std::set<int>::iterator i = list.begin(); i!=list.end();++i) {
+			m_indices.push_back(*i);
+		}
+		return true;
+	}
+
+	void LayerCache::collect(const Rect& viewport, std::vector<int>& index_list) {
+		CacheTree::Node * node = m_tree->find_container(viewport);
+		CacheTreeCollector collector(index_list, viewport);
+		node->apply_visitor(collector);
+		node = node->parent();
+		while(node) {
+			collector.visit(node);
+			node = node->parent();
+		}
+	}
+
+	void LayerCache::fullUpdate() {
+		for(unsigned i=0; i!=m_entries.size(); ++i)
+			updateEntry(m_entries[i]);
+	}
+
+	class InstanceDistanceSort {
+	public:
+		inline bool operator()(RenderItem* const & lhs, RenderItem* const & rhs) {
+			if (lhs->screenpoint.z == rhs->screenpoint.z) {
+				InstanceVisual* liv = lhs->instance->getVisual<InstanceVisual>();
+				InstanceVisual* riv = rhs->instance->getVisual<InstanceVisual>();
+				return liv->getStackPosition() < riv->getStackPosition();
+			}
+			return lhs->screenpoint.z < rhs->screenpoint.z;
+		}
+	};
+
+	void LayerCache::update(Camera::Transform transform, RenderList& renderlist) {
+		const double OVERDRAW = 2.5;
+		renderlist.clear();
+		bool isWarped = transform == Camera::WarpedTransform;
+		if( isWarped )
+			fullUpdate();
+
+		Rect viewport = m_camera->getViewPort();
+		Rect screen_viewport = viewport;
+		float zoom = m_camera->getZoom();
+		DoublePoint3D viewport_a = m_camera->screenToVirtualScreen(Point3D(viewport.x, viewport.y));
+		DoublePoint3D viewport_b = m_camera->screenToVirtualScreen(Point3D(viewport.right(), viewport.bottom()));
+		viewport.x = std::min(viewport_a.x, viewport_b.x);
+		viewport.y = std::min(viewport_a.y, viewport_b.y);
+		viewport.w = std::max(viewport_a.x, viewport_b.x) - viewport.x;
+		viewport.h = std::max(viewport_a.y, viewport_b.y) - viewport.y;
+
+		// FL_LOG(_log, LMsg("camera-update viewport") << viewport);
+		std::vector<int> index_list;
+		collect(viewport, index_list);
+		for(unsigned i=0; i!=index_list.size();++i) {
+			Entry& entry = m_entries[index_list[i]];
+			// NOTE
+			// An update is forced if the item has an animation/action.
+			// This update only happens if it is _already_ included in the viewport
+			// Nevertheless: Moving instances - which might move into the viewport will be updated
+			// By the layer change listener.
+			if(entry.force_update)
+				updateEntry(entry);
+
+			RenderItem& item = m_instances[entry.instance_index];
+			if(!item.image)
+				continue;
+
+			Point3D screen_point = m_camera->virtualScreenToScreen(item.screenpoint);
+			// NOTE:
+			// One would expect this to be necessary here,
+			// however it works the same without, sofar
+			// m_camera->calculateZValue(screen_point);
+			// item.screenpoint.z = -screen_point.z;
+
+			item.dimensions.x = screen_point.x;
+			item.dimensions.y = screen_point.y;
+			item.dimensions.w = unsigned(double(item.bbox.w) * zoom + OVERDRAW);
+			item.dimensions.h = unsigned(double(item.bbox.h) * zoom + OVERDRAW);
+
+			if (zoom != 1.0) {
+				// NOTE: Due to image alignment, there is additional additions on image dimensions 
+				//       There's probabaly some better solution for this, but works "good enough" for now. 
+				//       In case additions are removed, gaps appear between tiles. 
+				item.dimensions.w = unsigned(ceil(double(item.bbox.w) * zoom)) + OVERDRAW;
+				item.dimensions.h = unsigned(ceil(double(item.bbox.h) * zoom)) + OVERDRAW;
+			}
+
+			if(item.dimensions.intersects(screen_viewport))
+				renderlist.push_back(&item);
+		}
+
+		InstanceDistanceSort ids;
+		std::stable_sort(renderlist.begin(), renderlist.end(), ids);
+		//  FL_LOG(_log, LMsg("camera-update ") << " N=" <<renderlist.size() << "/" << m_instances.size() << "/" << index_list.size());
+	}
+}