//BSD License
//DXGfx® - http://www.eteractions.com
//Copyright (c) 2005
//by Guillaume Randon
//Permission is hereby granted, free of charge, to any person obtaining a copy of this software
//and associated documentation files (the "Software"), to deal in the Software without restriction,
//including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
//and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
//subject to the following conditions:
//The above copyright notice and this permission notice shall be included in all copies or substantial
//portions of the Software.
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
//INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE 
//AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
//DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Drawing;
using System.Diagnostics;
using Microsoft.DirectX;
using Microsoft.DirectX.Direct3D;
using Microsoft.Samples.DirectX.UtilityToolkit;

namespace DXGfxLib
{
    /// <summary>
    /// This is the main reason why this small library exist. I wanted to be able to display an outdoor scene with terrain
    /// without throwing everything I would have in that scene to the video card for each render pass.
    /// OutDoorScene inherits from the Scene class it does refine the algorithms for scene graph organisation upadte and draw
    /// using the asumption that the is a classical outdoor scene featuring a large terrain. Internally this class uses a quadtree.
    /// Some optimization impose that the depth of the quadtree has to be lower than 8. As it might be performance unfriendly to
    /// have a too deep tree I use a 4 level deep quadtree. This could be easily changed if needed.
    /// </summary>
    public class OutDoorScene : Scene, IPositionConstraint
    {
        #region MovedFromDXGfxManager
        /// <summary>
        /// This has been moved from DXGfxManager class to here as I retain, the avatar, the input handler and the camera
        /// are properties of a specific scene.
        /// </summary>
        public Avatar CurrentAvatar
        {
            get
            {
                return currentInputHandler.CurrentAvatar;
            }
            set
            {
                CurrentInputHandler.CurrentAvatar = value;
                CurrentCamera.Person = currentInputHandler.CurrentAvatar.associatedSceneObject;
                avatarName = currentInputHandler.CurrentAvatar.associatedSceneObject.name;

                CurrentCamera.camera.positionConstraint = this;
                CurrentCamera.Person.positionConstraint = this;
            }
        }

        public string avatarName = "";

        private ThirdPersonCamera currentCamera = null;

        public ThirdPersonCamera CurrentCamera
        {
            get 
            {
                if (currentCamera == null)
                    currentCamera = new ThirdPersonCamera();

                return currentCamera; 
            }
            set
            {
                currentCamera = value;
            }
        }

        public Frustrum frustrum = null;

        public Matrix matView;
        public Matrix matProj;

        /// <summary>
        /// This is a reference to the input handler we want to be used. Inputs should be forwarded to that instance
        /// of the InputHandler class who will take the appropriate actions.
        /// </summary>
        private IInputHandler currentInputHandler = null;

        public IInputHandler CurrentInputHandler
        {
            get
            {
                if (currentInputHandler == null)
                {
                    currentInputHandler = new PointAndClickHandler();
                }
                return currentInputHandler;
            }
            set
            {
                currentInputHandler = value;
            }
        }
        #endregion

        // For  refraction reflection
        private Texture backBufferTex = null;
        private Texture reflectionMap = null;
        private RenderToSurface rts = null;
        private Plane reflectPlane;
        private Rectangle rect;

        /// <summary>
        /// This value is used when we check for camera position. The camera should at least be three meters higher
        /// than the ground position.
        /// </summary>
        public float cameraHeightOffset = 3.0f;

        /// <summary>
        /// We need to keep our nodes somewhere.
        /// </summary>
        internal QuadTreeNode[][] nodes = null;

        /// <summary>
        /// 
        /// </summary>
        private int[] levelNumCells;

        /// <summary>
        /// Self explicit
        /// </summary>
        private float[] sizeOfCells;

        /// <summary>
        /// This will keep track of our quadtree depth.
        /// </summary>
        public int depth = -1;

        /// <summary>
        /// Maximum depth allowed for our quadtree implementation. The mechanism we use to
        /// fast query which quadtree node contain which position won't allow us to have depth higher
        /// than that (at least the way it is implemented at the moment).
        /// </summary>
        public const int maxDepth = 8;

        /// <summary>
        /// Each time nodes are moved in 3D space they might need repositioning in the Quadtree.
        /// This list contain all such nodes for each run. Most of the time the list will be empty except
        /// if you have a lot of nodes moving all the time (which might happen after all).
        /// </summary>
        private List<SceneNode> nodesToPositionInTree = null;


        private Vector3 scale;
        private Vector3 extents;

        /// <summary>
        /// This property allow you to retrieve the dimensions of the outdoorscene along each individual axis.
        /// </summary>
        public Vector3 Extents
        {
            get { return extents; }
        }

        /// <summary>
        /// We want to have a bounding box for the whole outdoorscene. Here it is.
        /// </summary>
        private AABBox worldAABBox;

        /// <summary>
        /// This value represent the number of different cells we will have along X and Z!
        /// </summary>
        private const int numDimCells = 256;

        /// <summary>
        /// This represent the number of cells I can have along the Y axs (which point up).
        /// </summary>
        private const int numHeigthCells = 32;

        /// <summary>
        /// An outdoor scene display a terrain. So we keep a ref on our Terrain instance.
        /// </summary>
        private Terrain sceneTerrain;

        /// <summary>
        /// Accessors for sceneTerrain
        /// </summary>
        public Terrain SceneTerrain
        {
            get { return sceneTerrain; }
            set { sceneTerrain = value; }
        }


        /// <summary>
        /// We want to be able to add water to our outdoor scene, if we have some water we want to keep
        /// a reference on the Water here.
        /// </summary>
        private Water2 sceneWater;

        /// <summary>
        /// Here are the accessors for the SceneWater.
        /// </summary>
        public Water2 SceneWater
        {
            set { sceneWater = value; }
            get { return sceneWater; }
        }

        /// <summary>
        /// Most of the time our outdoor scene will also display a SkyBox, we keep the ref on the SkyBox instance here.
        /// </summary>
        private SkyDome sceneSky;

        /// <summary>
        /// Accessors for the SkyBox instance associated with the outdoorscene.
        /// </summary>
        public SkyDome SceneSky
        {
            set { sceneSky = value; }
            get { return sceneSky; }
        }

        public Texture env = null;

        private Effect refractionMaskEffect = null;

		/// <summary>
		/// The constructor of our QuadTree. You can specify a bounding box for the world that the QuadTree will encompass
		/// and the depth of the QuadTree that you want to use. By Default it's 4.
		/// </summary>
		/// <param name="worldBBox">The box that you want your outdoorscene to fill. This is important as when you load
        /// a terrain from a 257 per 257 bitmap it is going to be streched/compressed to cover the XZ surface defined
        /// by this bounding box.</param>
		/// <param name="depth">The depth of the Quadtree to build. By default it is 4, which I have always found is an
        /// efficient value.</param>
		public OutDoorScene(AABBox worldBBox, int depth) : base()
		{
            Initialize(worldBBox, depth);
        }

        public void Initialize(AABBox worldBBox, int depth)
        {
            base.Initialize();

			nodesToPositionInTree = new List<SceneNode>();

			if(depth>maxDepth)
				depth=maxDepth;

			this.depth = depth;
			this.extents = worldBBox.Size();

			this.worldAABBox = worldBBox;

			scale.X = numDimCells/extents.X;
			scale.Z = numDimCells/extents.Z;
			scale.Y = numHeigthCells/extents.Y;

			nodes = new QuadTreeNode[depth+1][];
			levelNumCells = new int[depth+1];
			sizeOfCells = new float[depth+1];

			for(int i=0; i<depth+1; i++)
			{
				levelNumCells[i] = (int)(System.Math.Pow(2, i));
				sizeOfCells[i] = extents.X / levelNumCells[i];
				nodes[i] = new QuadTreeNode[levelNumCells[i]*levelNumCells[i]];
			}

			nodes[0][0] = new QuadTreeNode();
			rootNode = nodes[0][0];
            rootNode.scene = this;
            rootNode.Moved +=new NodeMovedEventHandler(RegisterForPositionUpdate);
			rootNode.worldAABBox.vMin.X = worldBBox.vMin.X;
			rootNode.worldAABBox.vMin.Y = worldBBox.vMin.Y;
			rootNode.worldAABBox.vMin.Z = worldBBox.vMin.Z;

			rootNode.worldAABBox.vMax.X = worldBBox.vMax.X;
			rootNode.worldAABBox.vMax.Y = worldBBox.vMax.Y;
			rootNode.worldAABBox.vMax.Z = worldBBox.vMax.Z;

			for(int i=1; i<depth+1; i++)
			{
				for(int z=0; z<levelNumCells[i]; z++)
				{
					for(int x=0; x<levelNumCells[i]; x++)
					{
						QuadTreeNode tmpNode = new QuadTreeNode();
                        tmpNode.Moved +=new NodeMovedEventHandler(RegisterForPositionUpdate);
						AABBox tmpBBox = new AABBox();
						tmpBBox.vMin.Y = this.worldAABBox.vMin.Y;
						tmpBBox.vMax.Y = this.worldAABBox.vMax.Y;

						tmpBBox.vMin.X = this.worldAABBox.vMin.X + (this.extents.X / (levelNumCells[i])) * x;
						tmpBBox.vMax.X = this.worldAABBox.vMin.X + (this.extents.X / (levelNumCells[i])) * (x+1);

						tmpBBox.vMin.Z = this.worldAABBox.vMin.Z + (this.extents.Z / (levelNumCells[i])) * (z);
						tmpBBox.vMax.Z = this.worldAABBox.vMin.Z + (this.extents.Z / (levelNumCells[i])) * (z+1);
						
						tmpNode.worldAABBox = tmpBBox;
                        tmpNode.ForceWorldMatValueWithoutUpdate(Matrix.Translation(tmpBBox.MinPoint()));

						nodes[i][x+z*levelNumCells[i]] = tmpNode;

						int xParent = (int)System.Math.Floor((double)x/2);
						int zParent = (int)System.Math.Floor((double)z/2);
						(nodes[i-1][xParent+zParent*levelNumCells[i-1]]).AddChild(tmpNode);
					}
				}
			}
		}

        private void InitRefractionReflection()
        {
            Device dev = DXGfxManager.GetGlobalInstance().d3dDevice;
            SurfaceDescription backBufferDescription = DXGfxManager.GetGlobalInstance().backBufferDescription;

            reflectPlane = Microsoft.DirectX.Plane.FromPointNormal(new Vector3(0, 0.0f, 0), new Vector3(0, 1, 0));

            reflectionMap = new Texture(dev, backBufferDescription.Width, backBufferDescription.Height, 1, Usage.RenderTarget, backBufferDescription.Format, Pool.Default);
            backBufferTex = new Texture(dev, backBufferDescription.Width, backBufferDescription.Height, 1, Usage.RenderTarget, backBufferDescription.Format, Pool.Default);
            rts = new RenderToSurface(dev, backBufferDescription.Width, backBufferDescription.Height, backBufferDescription.Format, true, DepthFormat.D16);
            rect = new Rectangle(0, 0, backBufferDescription.Width, backBufferDescription.Height);
        }

        public override void GetPrepared()
        {
            IDictionaryEnumerator sceneObjects = sceneContent.GetEnumerator();

            while (sceneObjects.MoveNext())
            {
                SceneObject currObj = sceneObjects.Value as SceneObject;
                if ((currObj != null)&&(currObj.GetType()!=typeof(Water))&&(currObj.GetType()!=typeof(SkyBox))&&
                    (currObj.GetType() != typeof(Water2)) && (currObj.GetType() != typeof(SkyDome)))
                {
                    currObj.GetPrepared();
                    Attach(currObj);
                }
            }

            if (sceneSky != null)
            {
                sceneSky.GetPrepared();
            }
            if (sceneWater != null)
            {
                sceneWater.GetPrepared();
            }

            if (avatarName != "")
            {
                CurrentAvatar = new Avatar(sceneContent[avatarName] as SceneObject);
            }
        }

        public override void Dispose()
        {
            if (currentInputHandler != null)
            {
                currentInputHandler.Dispose();
                currentInputHandler = null;
            }
            if (rootNode != null)
            {
            }
        }

        /// <summary>
        /// The outdoorscene can impose constraints on node positionning. For example most of the time we want the nodes
        /// to be above ground level. We do that here. For each node we consider 0,0,0 in local space is at the center of
        /// the node bounding box so the size of the node bounding box halved by two is used for the repositionning operation.
        /// This position constraint is enforce through calls to this method.
        /// In derived class from OutDoorScene it is through this method that additional constraints can be imposed!
        /// </summary>
        /// <param name="node">The node to reposition.</param>
        public void ValidateOrMove(ref SceneNode node)
        {
            ValidateOrMove(ref node, 0);
        }

        /// <summary>
        /// The outdoorscene can impose constraints on node positionning. For example most of the time we want the nodes
        /// to be above ground level. We do that here. Unlike the above method that reposition based on its bounding box size
        /// here we can specify explicitely the offset we want above ground level.
        /// </summary>
        /// <param name="node"></param>
        /// <param name="offset"></param>
        public void ValidateOrMove(ref SceneNode node, float offset)
        {
            Vector3 pos = node.Position;
            float y = GetHeigth(pos.X, pos.Z)+offset;
            if ((y > pos.Y) && (y < 1000))
            {
                pos.Y = y;
                node.Position = pos;
            }
        }

        /// <summary>
        /// This is quite coarce we just send back a transformation matrix that would move the object up
        /// to its ground level if we see that the object is below the ground!
        /// This is based only on the size of the object along the y axis. So a vertical line, a car and
        /// a train would be dealt in the same way. This means depending on the object you use some
        /// part of it can go through the ground!
        /// </summary>
        /// <param name="pos">The position we would like for the geometry encompassed by the bbox</param>
        /// <param name="localBBox"></param>
        /// <returns></returns>
        public Matrix ValidateOrMove(Vector3 pos, BBox localBBox)
        {
            Matrix res = Matrix.Identity;

            float y = GetHeigth(pos.X, pos.Z) + 0.5f * localBBox.Size().Y;
            if ((y > pos.Y) && (y < 1000))
            {
                res = Matrix.Translation(0.0f, y - pos.Y, 0.0f);
            }

            return res;
        }

        /// <summary>
        /// OutdoorScene can impose constraints on the camera position. This is done through this specific method.
        /// </summary>
        /// <param name="camera"></param>
        /// <param name="subject"></param>
        public void ValidateCameraOrMove(ref SceneNode camera, ref SceneNode subject)
        {
            // First let's validate or move our two nodes
            ValidateOrMove(ref subject);
            ValidateOrMove(ref camera, 3.0f);
        }

        /// <summary>
        /// If our d3ddevice is changed we need to perform some operation on all the resources we use that might bound to the
        /// device.
        /// </summary>
        /// <param name="d3ddevice"></param>
        public virtual void DeviceChanged(Device d3ddevice)
        {
            sceneTerrain.DeviceChanged(d3ddevice, this);
            defaultState = null;
        }

        /// <summary>
        /// This method return the  ground height at x,z (y is looking up). x looks right z look far away and x=0 z=0 is
        /// right in the center of our Terrain and outdoorscene bounding box!
        /// </summary>
        /// <param name="x"></param>
        /// <param name="z"></param>
        /// <returns></returns>
        public float GetHeigth(float x, float z)
        {
            float heigth = 0.0f;

            if (sceneTerrain != null)
            {
                heigth = sceneTerrain.GetHeigth(this, x, z);    
            }
            return heigth;
        }

        /// <summary>
        /// In this method we performed all updates related to our scene. First every node in the scene graph is
        /// going to be updated then we will update the water surface if there is any then the skybox (it might not need
        /// upadtes but we let the SkyBox instance or the instance of a derived class decide whether or not it needs to perform
        /// some operations).
        /// </summary>
        /// <param name="appTime">Aboslute time value</param>
        /// <param name="elapsedTime">Elapsed time since last update.</param>
        /// <param name="frustrum">Viewing frustrum at the time of the update. This is used by scene node to know
        /// whether or not they are in the viewing frsutrum and thus need to be rendered or not!</param>
        /// <param name="objectsToBeRendered">Each node that decides that it needs to be rendered on screen need to add itself
        /// to the list of objects to be rendered for this frame.</param>
        public override void Update(double appTime, float elapsedTime, Frustrum frustrum, List<IDrawable> objectsToBeRendered)
        {
            this.frustrum = frustrum;

            base.Update(appTime, elapsedTime, frustrum, objectsToBeRendered);

            if (sceneWater != null)
            {
                sceneWater.Update(frustrum, appTime, elapsedTime);
            }

            if (sceneSky != null)
            {
                sceneSky.Update(frustrum, appTime, elapsedTime);
            }

            UpdatePositionInTree();
        }

        public void Update(Device d3ddevice, double appTime, float elapsedTime)
        {
            matView = Matrix.Multiply(currentCamera.WorldMatrix, currentCamera.ViewMatrix);
            matProj = currentCamera.ProjectionMatrix;
            Update(d3ddevice, matView, currentCamera.ProjectionMatrix, appTime, elapsedTime);
        }

        public override void RenderScene(Device d3ddevice, Frustrum frustrum)
        {
            d3ddevice.SetTransform(TransformType.World, Matrix.Identity);
            RenderScene(d3ddevice, frustrum.matView, frustrum.matProj);
        }

        /// <summary>
        /// This will draw all objects in the list of objects to be rendered. Billboards objects are sorted based on their 
        /// distance to the camera in order to get correct display of their associated textures with alpha.
        /// </summary>
        /// <param name="d3ddevice"></param>
        public override void RenderScene(Device d3ddevice, Matrix matView, Matrix matProj)
        {
            d3ddevice.SetTransform(TransformType.World, Matrix.Identity);

            if (SceneWater != null)
            {
                CheckRefractionReflectionReady();
                CreateReflectionMap(d3ddevice);
            }

            // Clear the render target and the zbuffer 
            d3ddevice.Clear(ClearFlags.ZBuffer | ClearFlags.Target, 0x002D32AA, 1.0f, 0);
            d3ddevice.Transform.World = Matrix.Identity;
            d3ddevice.Transform.View = matView;
            d3ddevice.Transform.Projection = matProj;

	        d3ddevice.BeginScene();

            RenderObjectAndSky(d3ddevice);

            if (SceneWater != null)
            {
                CreateRefractionMap(d3ddevice);
                SceneWater.Render(d3ddevice, backBufferTex, reflectionMap);
            }

	        d3ddevice.EndScene();
        }

        public void CheckRefractionReflectionReady()
        {
            if ((reflectionMap == null) || (backBufferTex == null))
            {
                InitRefractionReflection();
            }
        }

        private void RenderObjectAndSky(Device d3ddevice)
        {

            RenderObjects(d3ddevice);

            if (sceneSky != null)
            {
                sceneSky.RenderSky(d3ddevice);
                //int skyPasses = sceneSky.AssociatedEffectGroup.Default.Begin(0);
                //for (int skyPass = 0; skyPass < skyPasses; skyPass++)
                //{
                //    sceneSky.AssociatedEffectGroup.Default.BeginPass(skyPass);
                //    sceneSky.Draw(d3ddevice);
                //    sceneSky.AssociatedEffectGroup.Default.EndPass();
                //}
                //sceneSky.AssociatedEffectGroup.Default.End();
            }
        }

        private void RenderObjects(Device d3ddevice)
        {
            EffectGroup nextEG = DXGfxManager.GetGlobalInstance().defaultEffectGroup;
            EffectGroup currentEG = null;
            int startAt = 0;

            while ((nextEG != null) && (objectsToBeRendered.Count > 0))
            {
                currentEG = nextEG;
                int passes = currentEG.Default.Begin(0);
                bool lastPassDone = false;

                for (int pass = 0; pass < passes; pass++)
                {
                    currentEG.Default.BeginPass(pass);

                    for (int i = startAt; i < objectsToBeRendered.Count; i++)
                    {
                        if (currentEG.CompareTo(objectsToBeRendered[i].AssociatedEffectGroup) == 0)
                        {
                            objectsToBeRendered[i].SetEffectsValues(d3ddevice, currentEG.Default, pass);

                            objectsToBeRendered[i].Draw(d3ddevice);

                        }
                        else
                        {
                            if (pass == passes - 1)
                            {
                                nextEG = objectsToBeRendered[i].AssociatedEffectGroup;
                                startAt = i;
                                lastPassDone = true;
                            }
                            break;
                        }

                        if (i == objectsToBeRendered.Count - 1)
                        {
                            // If we are here we have rendered everything so just set effectToUse==null
                            // to avoid rendering everything again.
                            nextEG = null;
                        }
                    }
                    currentEG.Default.EndPass();

                    // We have two different situation to deal with here.
                    // If this is the last pass then change nextEG and startAt.
                    // else just break to draw all the objects that have been rendered
                    // but with second pass of the defaul effect.
                    if (lastPassDone)
                    {
                        break;
                    }


                }
                currentEG.Default.End();
            }
            TerrainTile.settedPass = -1;
        }

        public void CreateRefractionMap(Device device)
        {
            device.RenderState.ZBufferFunction = Compare.LessEqual;
            device.RenderState.ColorWriteEnable = ColorWriteEnable.Alpha;

            if (refractionMaskEffect == null)
            {
                DXGfxManager.GetGlobalInstance().LoadEffect(device, "RefeactionMaskHLSL.fx", ref refractionMaskEffect);
            }

            refractionMaskEffect.SetValue("g_WorldViewProj", SceneWater.WorldMat * frustrum.matView * frustrum.matProj);
            refractionMaskEffect.Technique = "RenderRefractionMask14";

            device.VertexFormat = CustomVertex.PositionNormalTextured.Format;
            // Water
            device.Transform.World = SceneWater.WorldMat;
            device.SetStreamSource(0, SceneWater.waterVBuff, 0);
            device.Indices = SceneWater.waterIBuff;

            // Apply the technique contained in the effect 
            int passes = refractionMaskEffect.Begin(0);
            for (int pass = 0; pass < passes; pass++)
            {
                refractionMaskEffect.BeginPass(pass);

                // Draw the mesh subset
                device.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0, SceneWater.numberVertices, 0, SceneWater.numberTri);

                refractionMaskEffect.EndPass();
            }
            refractionMaskEffect.End();
            device.RenderState.ColorWriteEnable = ColorWriteEnable.RedGreenBlueAlpha;

            device.StretchRectangle(device.GetBackBuffer(0, 0, BackBufferType.Mono),
                rect, backBufferTex.GetSurfaceLevel(0), rect, TextureFilter.Linear);
        }

        public void CreateReflectionMap(Device device)
        {
            bool fogStatus = device.RenderState.FogEnable;
            device.RenderState.FogEnable = false;

            Surface surface = reflectionMap.GetSurfaceLevel(0);

            Viewport view = new Viewport();
            view.Width = DXGfxManager.GetGlobalInstance().backBufferDescription.Width;
            view.Height = DXGfxManager.GetGlobalInstance().backBufferDescription.Height;
            view.MaxZ = 1.0f;

            rts.BeginScene(surface, view);

            device.Clear(ClearFlags.Target | ClearFlags.ZBuffer, 0x00efefff, 1.0f, 0);
            

            // Do magic reflection stuff				
            Matrix reflectViewMatrix = Matrix.Identity;
            reflectViewMatrix.Reflect(reflectPlane);
            reflectViewMatrix = reflectViewMatrix * frustrum.matView;

            device.Transform.View = reflectViewMatrix;
            device.Transform.Projection = frustrum.matProj;

            device.ClipPlanes[0].Enabled = true;
            device.ClipPlanes[0].Plane = reflectPlane;
            device.RenderState.Clipping = true;

            // render scene                
            RenderObjectAndSky(device);

            // reset render states
            device.RenderState.Clipping = false;
            device.ClipPlanes[0].Enabled = false;

            // end RTS
            rts.EndScene(Filter.None);

            device.RenderState.FogEnable = fogStatus;
        }

        /// <summary>
        /// Get the node at the specified level and x z position (remember y looks up, x look right and z far away at least if
        /// your camera has default position and lookat).
        /// </summary>
        /// <param name="level">There are several level in the quadtree, at each level the whole x z scope is covered so 
        /// you need to decide when calling this method at which level you want a quadtree node to be picked up!</param>
        /// <param name="x"></param>
        /// <param name="z"></param>
        /// <returns></returns>
        public QuadTreeNode GetNode(int level, int x, int z)
        {
            QuadTreeNode res = null;

            if ((level <= depth) && (x < levelNumCells[level]) && (z < levelNumCells[level]))
                res = nodes[level][x + z * levelNumCells[level]];

            if (res == null)
                res = rootNode as QuadTreeNode;

            return res;
        }

        /// <summary>
        /// Get the optimum quadtree node to which the bounding box should be attached. Alternatively, the returned
        /// node will the quadtree node which encompass all the space which should be of interest for collision detection
        /// for the specified bounding box. This method used the principle described in the "Direct Access QuadTree Lookup" article from Matt Pritchard
        /// in game programming gems II. The implementation used here is mine and might be a little less effective than the one described in
        /// that article :). 
        /// </summary>
        /// <param name="boundingBox"></param>
        /// <returns></returns>
        public SceneNode GetParent(BBox boundingBox)
        {
            // Guess what, if we are not passed a valid boundingbox we just return the rootNode.
            if (boundingBox == null)
            {
                return rootNode;
            }

            int xMinEnclosedRow;
            int xMaxEnclosedRow;

            int zMinEnclosedRow;
            int zMaxEnclosedRow;

            AABBox aaBox = new AABBox(boundingBox);

            aaBox.vMin += new Vector3(0.01f, 0.01f, 0.01f);
            aaBox.vMax -= new Vector3(0.01f, 0.01f, 0.01f);

            xMinEnclosedRow = (int)System.Math.Floor(((aaBox.vMin.X - this.worldAABBox.vMin.X) / extents.X) * numDimCells);
            xMaxEnclosedRow = (int)System.Math.Floor(((aaBox.vMax.X - this.worldAABBox.vMin.X) / extents.X) * numDimCells);

            zMinEnclosedRow = (int)System.Math.Floor(((aaBox.vMin.Z - this.worldAABBox.vMin.Z) / extents.Z) * numDimCells);
            zMaxEnclosedRow = (int)System.Math.Floor(((aaBox.vMax.Z - this.worldAABBox.vMin.Z) / extents.Z) * numDimCells);

            xMinEnclosedRow = (int)MathUtil.Clamp(xMinEnclosedRow, 0, 255);
            xMaxEnclosedRow = (int)MathUtil.Clamp(xMaxEnclosedRow, xMinEnclosedRow + 1, 255);

            zMinEnclosedRow = (int)MathUtil.Clamp(zMinEnclosedRow, 0, 255);
            zMaxEnclosedRow = (int)MathUtil.Clamp(zMaxEnclosedRow, zMinEnclosedRow + 1, 255);

            int xPattern = (xMinEnclosedRow ^ xMaxEnclosedRow);
            int zPattern = (zMinEnclosedRow ^ zMaxEnclosedRow);

            int bitPattern = System.Math.Max(xPattern, zPattern);

            BitVector32 bitVec = new BitVector32(bitPattern);
            int myBit1 = BitVector32.CreateMask();
            int myBit2 = BitVector32.CreateMask(myBit1);
            int myBit3 = BitVector32.CreateMask(myBit2);
            int myBit4 = BitVector32.CreateMask(myBit3);
            int myBit5 = BitVector32.CreateMask(myBit4);
            int myBit6 = BitVector32.CreateMask(myBit5);
            int myBit7 = BitVector32.CreateMask(myBit6);
            int myBit8 = BitVector32.CreateMask(myBit7);

            int destLevel = 0;

            if (bitVec[myBit1])
                destLevel = maxDepth - 1;
            if (bitVec[myBit2])
                destLevel = maxDepth - 2;
            if (bitVec[myBit3])
                destLevel = maxDepth - 3;
            if (bitVec[myBit4])
                destLevel = maxDepth - 4;
            if (bitVec[myBit5])
                destLevel = maxDepth - 5;
            if (bitVec[myBit6])
                destLevel = maxDepth - 6;
            if (bitVec[myBit7])
                destLevel = maxDepth - 7;
            if (bitVec[myBit8])
                destLevel = maxDepth - 8;

            destLevel = (int)MathUtil.Clamp(destLevel, 0, depth);

            int x = (int)System.Math.Floor(((aaBox.vMin.X - this.worldAABBox.vMin.X) / extents.X) * levelNumCells[destLevel]);
            int z = (int)System.Math.Floor(((aaBox.vMin.Z - this.worldAABBox.vMin.Z) / extents.Z) * levelNumCells[destLevel]);

            SceneNode res = GetNode(destLevel, (int)MathUtil.Clamp(x, 0, levelNumCells[destLevel]),
                (int)MathUtil.Clamp(z, 0, levelNumCells[destLevel]));

            if (aaBox.IsInside(res.worldAABBox))
            {
                return res;
            }
            else
            {
                return rootNode;
            }
        }

        /// <summary>
        /// Another GetParent method. In fact this method will use the bounding box of the specified node and 
        /// the above described method to get the best parent.
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public SceneNode GetParent(SceneNode node)
        {
            return GetParent(node.worldAABBox);
        }

        /// <summary>
        /// Nodes that have changed position might have to be attach to different quadtree nodes now, this method
        /// will allow nodes to register for a latter repositionning in the quadtree.
        /// </summary>
        /// <param name="node"></param>
        public void RegisterForPositionUpdate(SceneNode node)
        {
            // Check a simple check! QuadTree nodes should not move in the tree.
            // SceneNode can move but QuedTree nodes are not expected to move!
            // Let's check it
            QuadTreeNode testNode = node as QuadTreeNode;
            if (testNode != null)
            {
                throw new ArgumentException("Any SceneNode can move but we don't expect to see quadtree nodes here!?");
            }

            nodesToPositionInTree.Add(node);
        }

        /// <summary>
        /// Nodes that have changed position might have to be attach to different quadtree nodes now, this method
        /// will ensure that all nodes that have registered for it will be repositionned in the quadtree. It's the
        /// responsability of the node to register for such an update.
        /// </summary>
        public void UpdatePositionInTree()
        {
            foreach (SceneNode tmpNode in this.nodesToPositionInTree)
            {
                SceneNode oldParent = tmpNode.parent;
                SceneNode newParent = GetParent(tmpNode);

                if (oldParent == null)
                {
                    throw new NullReferenceException("This should not ever happen!");
                }
                if (newParent == null)
                {
                    throw new NullReferenceException("This should not ever happen!");
                }
                if (oldParent != newParent)
                {
                    oldParent.RemoveChild(tmpNode);
                    newParent.AddChild(tmpNode);
                }
            }
            this.nodesToPositionInTree.Clear();
        }

        /// <summary>
        /// See comments for the above Attach method. They apply here also. This method can be used when you have created
        /// the sceneobject or an instance of a derived class yourself and that you just want that instance to be managed
        /// by the scene from now on. After that updates on the instance will be made from you and it will have the opportunity
        /// to attach when it is in the viewing frustrum.
        /// </summary>
        /// <param name="sceneObj"></param>
        public override void Attach(SceneObject sceneObj)
        {
            SceneNode parent = GetParent(sceneObj);
            sceneObj.parent = parent;
            sceneObj.scene = this;
            parent.AddChild(sceneObj);
        }

        /// <summary>
        /// See comments for the above Attach method. They apply here also. This method can be used when you have created
        /// the sceneobject or an instance of a derived class yourself and that you just want that instance to be managed
        /// by the scene from now on. After that updates on the instance will be made from you and it will have the opportunity
        /// to attach when it is in the viewing frustrum.
        /// </summary>
        /// <param name="sceneObj"></param>
        public virtual void AttachStatic(SceneObject sceneObj)
        {
            TerrainTile tile = sceneTerrain.FindTile(this, sceneObj.Position.X, sceneObj.Position.Z);
            tile.AddChild(sceneObj);
        }

        struct BatchInterm
        {
            public Mesh theMesh;
            public Material[] materials;
            public Texture[] textures;
            public List<Matrix> matrices;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="mesh"></param>
        /// <param name="materials"></param>
        /// <param name="textues"></param>
        /// <param name="matrices"></param>
        public virtual void AttachBatch(Mesh mesh, Material[] materials, Texture[] textures, Matrix[] matrices)
        {
            Hashtable tmpBatches = new Hashtable();

            foreach (Matrix mat in matrices)
            {
                TerrainTile tile = sceneTerrain.FindTile(this, mat.M41, mat.M43);


                
                if (tmpBatches.ContainsKey(tile))
                {
                    BatchInterm interm = (BatchInterm)tmpBatches[tile];
                    interm.matrices.Add(mat);
                }
                else
                {
                    BatchInterm interm = new BatchInterm();
                    interm.theMesh = mesh;
                    interm.materials = materials;
                    interm.textures = textures;
                    interm.matrices = new List<Matrix>();
                    interm.matrices.Add(mat);
                    tmpBatches.Add(tile, interm);
                }
            }

            IDictionaryEnumerator enumerator = tmpBatches.GetEnumerator();

            while (enumerator.MoveNext())
            {
                TerrainTile tile = (TerrainTile)enumerator.Key;
                BatchInterm interm = (BatchInterm)enumerator.Value;

                Batch batch = new Batch();
                batch.Populate(interm.theMesh, interm.materials, interm.textures, interm.matrices.ToArray());

                tile.batches.Add(batch);
            }
        }

        /// <summary>
        /// If you want to add a node to the quadtree you should use this method. This method will first search
        /// for the right parent node and will add the specified node to it.
        /// </summary>
        /// <param name="node"></param>
        public void Add(SceneNode node)
        {
            SceneNode parent = GetParent(node);
            

            if (parent == null) // Means we don't have container, in that case we just attach to the rootNode.
                parent = rootNode;
            parent.AddChild(node);
        }

        /// <summary>
        /// This method will check the quadTree for entities colliding with the specified node. If there is at least one
        /// collision true will be returned and the colliding scene object will be added to the arraylist of colliding objects.
        /// SceneNode are not returned to the list if they are not also implementing ISceneObject.
        /// Spatial coherency is used to optimize the collision detection. It uses the GetParent method to start
        /// searching from the best node in the quad tree. This means that if the bounding box of the node you specified
        /// is in a portion of the virtual space that we already know that only objects attached to a specific quadtree node
        /// can collide with it, we will use that information to start our testing from that node and not from the 
        /// rootnode of the quadtree. Besides as you can see described in the GetParent method documentation, that
        /// GetParent method has been optimized to found very quickly the quadTree node of interest.</summary>
        /// <param name="sceneNode"></param>
        /// <param name="collidingSceneObjects"></param>
        /// <returns></returns>
        public override bool Collide(SceneNode sceneNode, ref List<SceneObject> collidingSceneObjects)
        {
            SceneNode parentSceneNode = GetParent(sceneNode);

            return parentSceneNode.Collide(sceneNode, ref collidingSceneObjects);
        }

        /// <summary>
        /// This method will check the quadTree for entities colliding with the specified node. If there is at least one
        /// collision true will be returned and the colliding scene object will be added to the arraylist of colliding objects.
        /// SceneNode are not returned to the list if they are not also implementing ISceneObject.
        /// Spatial coherency is used to optimize the collision detection. It uses the GetParent method to start
        /// searching from the best node in the quad tree. This means that if the bounding box of the node you specified
        /// is in a portion of the virtual space that we already know that only objects attached to a specific quadtree node
        /// can collide with it, we will use that information to start our testing from that node and not from the 
        /// rootnode of the quadtree. Besides as you can see described in the GetParent method documentation, that
        /// GetParent method has been optimized to found very quickly the quadTree node of interest.
        /// 
        /// In fact his is the same as the Collid method with the same signature except that here only scene objects
        /// flagged as solid are considered.
        /// </summary>
        /// <param name="sceneNode"></param>
        /// <param name="collidingSceneObjects"></param>
        /// <returns></returns>
        public override bool CollideSolid(SceneNode sceneNode, ref List<SceneObject> collidingSceneObjects)
        {
            SceneNode parentSceneNode = GetParent(sceneNode);

            return parentSceneNode.CollideSolid(sceneNode, ref collidingSceneObjects);
        }

        /// <summary>
        /// Same as above except that you specify the type of entities you want to check collision with. Apart from that
        /// this method works exactly like the one described above.
        /// </summary>
        /// <param name="sceneNode"></param>
        /// <param name="collidingSceneObjects"></param>
        /// <param name="desiredType"></param>
        /// <returns></returns>
        public override bool Collide(SceneNode sceneNode, ref List<SceneObject> collidingSceneObjects, System.Type desiredType)
        {
            SceneNode parentSceneNode = GetParent(sceneNode);

            return parentSceneNode.Collide(sceneNode, ref collidingSceneObjects, desiredType);
        }

        /// <summary>
        /// Same as above except that here only scene objects flagged as solid are considered.
        /// </summary>
        /// <param name="sceneNode"></param>
        /// <param name="collidingSceneObjects"></param>
        /// <param name="desiredType"></param>
        /// <returns></returns>
        public override bool CollideSolid(SceneNode sceneNode, ref List<SceneObject> collidingSceneObjects, System.Type desiredType)
        {
            SceneNode parentSceneNode = GetParent(sceneNode);

            return parentSceneNode.CollideSolid(sceneNode, ref collidingSceneObjects, desiredType);
        }

        /// <summary>
        /// This method build a terrain from the values in a 257x257 bitmap. As described in the ISceneManager interface
        /// this method will try to load the grass.bmp snow.bmp and lightmap.dds texture. I will let you checl the ISceneManager
        /// for more details. You should not have to call this method directly and you should call the LoadTerrain method
        /// of the Eter.Graphics.Manager. You can get a reference on that one from the control thorugh the graphics field.
        /// </summary>
        /// <param name="filename"></param>
        /// <returns></returns>
        public Terrain LoadTerrain(string filename)
        {
            if (DXGfxManager.GetGlobalInstance().d3dDevice == null)
            {
                throw new Exception("DXGfxManager.d3dDevice is null, loading of terrain is impossible without a valid device!");
            }

            return LoadTerrain(DXGfxManager.GetGlobalInstance().d3dDevice, filename);
        }

        /// <summary>
        /// This method build a terrain from the values in a 257x257 bitmap. As described in the ISceneManager interface
        /// this method will try to load the grass.bmp snow.bmp and lightmap.dds texture. I will let you checl the ISceneManager
        /// for more details. You should not have to call this method directly and you should call the LoadTerrain method
        /// of the Eter.Graphics.Manager. You can get a reference on that one from the control thorugh the graphics field.
        /// </summary>
        /// <param name="filename"></param>
        /// <returns></returns>
        public Terrain LoadTerrain(Device d3ddevice, string filename)
        {
            sceneTerrain = new Terrain(1024, 1024);
            sceneTerrain.Load(d3ddevice, this, filename);

            return sceneTerrain;
        }

        /// <summary>
        /// Same as above except you can specify the base texture the secondtexture and the texture to be used for it's alpha values.
        /// The first texture will be applied everywhere on the ground, the second texture will be applied only where the alpha values
        /// in lightmap say it should be applied.
        /// </summary>
        /// <param name="fileName"></param>
        /// <param name="baseTextureFile"></param>
        /// <param name="secondTextureFile"></param>
        /// <param name="alphaMapFile"></param>
        /// <returns></returns>
        public Terrain LoadTerrain(Device d3ddevice, string fileName, string baseTextureFile, string secondTextureFile, string alphaMapFile)
        {
            sceneTerrain = new Terrain(1024, 1024);
            sceneTerrain.Load(d3ddevice, this, fileName, baseTextureFile, secondTextureFile);

            return sceneTerrain;
        }

        /// <summary>
        /// When you click or double click in the rendering window with the mouse it is often interesting to know
        /// on which object you did click. This method does just that. You need to provide the screenposition, the viewport
        /// and view and projection matrices (they are needed to build a 3D ray from the 2D screen position that goes through 
        /// our scene)
        /// </summary>
        /// <param name="viewport"></param>
        /// <param name="proj"></param>
        /// <param name="view"></param>
        /// <param name="screenPos"></param>
        /// <returns></returns>
        public override SceneObject PickObject(Viewport viewport, Matrix proj, Matrix view, Vector2 screenPos)
        {
            return base.PickObject(viewport, proj, view, screenPos);
        }

        /// <summary>
        /// You might also want to know what was the terrain position clicked by the mouse, this is what this method performs.
        /// Like for pickobject you need to provide viewport, screen position view and projection matrices.
        /// </summary>
        /// <param name="viewport"></param>
        /// <param name="proj"></param>
        /// <param name="view"></param>
        /// <param name="screenPos"></param>
        /// <returns></returns>
        public override Vector3 PickEnvironmentPosition(Viewport viewport, Matrix proj, Matrix view, Vector2 screenPos)
        {
            Vector3 rayOrig;
            Vector3 rayDir;
            MathUtil.RayFromScreenPos(viewport, proj, view, screenPos, out rayOrig, out rayDir);

            List<SceneObject> collidingSceneObjects = new List<SceneObject>();

            bool any = Intersect(rayOrig, rayDir, ref collidingSceneObjects, typeof(TerrainTile));

            Vector3 position = new Vector3();
            if (any)
            {
                float refVal = 10000.0f;
                TerrainTile res = null;

                foreach (SceneObject sceneObj in collidingSceneObjects)
                {
                    TerrainTile tile = sceneObj as TerrainTile;

                    if (tile == null)
                        continue;

                    Microsoft.DirectX.Direct3D.IntersectInformation closestHit = new IntersectInformation();

                    bool intersect = tile.Intersect(rayOrig, rayDir, out closestHit);

                    if (!intersect)
                        continue;

                    if (closestHit.Dist < refVal)
                    {
                        res = tile;
                        refVal = closestHit.Dist;
                    }
                }

                position = rayOrig + refVal * rayDir;
            }
            return position;
        }

        /// <summary>
        /// This method can be used when you want to add several instances of a single mesh to the scene.
        /// Not implemented yet but implementation would certainly use the Batch class.
        /// </summary>
        /// <param name="mesh"></param>
        /// <param name="instancesInfo"></param>
        public void AddInstances(FrameworkMesh mesh, InstanceInfo[] instancesInfo)
        {
            if (sceneTerrain == null)
            {
                throw new Exception("terrain is null. It should be initialized before calling this method!");
            }

        }
    }
}
