title: Octrees as data structure

text:
# Question
Title: Octrees as data structure
In my cube world, I want to use octrees to represent my chunks of 20x20x20 cubes for frustum and occlusion culling. I understand how octrees work, I just dont know if I'm going about this the right way.

My base octree class is taken from here: http://www.xnawiki.com/index.php/Octree. The link is now dead but the code can be found below.

What I'm wondering is how to apply occlusion culling using this class. Does it make sense to have one octree for each cube chunk? Or should I make the octree bigger? Since I'm using cubes, each cube should fit into a node without overlap so that won't be an issue

```
using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
using Microsoft.Xna.Framework.Storage;

namespace Game
{

//    Copyright (C) 2011 Daniel Rosser
//    This program is free software: you can redistribute it and/or modify
//    it under the terms of the GNU General Public License as published by
//    the Free Software Foundation, either version 3 of the License, or
//    (at your option) any later version.
//
//    This program 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 General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with this program. See /LICENSES/gpl-3.0.txt
//    If not, see <http://www.gnu.org/licenses/>.
//
//    Daniel Rosser <danoli3@gmail.com>

    public class Octree
    {
        private const int maxObjectsInNode = 4;
        private const float minSize = 4.0f;

        // center coordinate point for the octree
        private Vector3 center;
        // size of the octree space
        private float size;

        List<Entity> objects;
        private BoundingBox bounds = default(BoundingBox);

        Octree parent = null;
        Octree nodeUFL;
        Octree nodeUFR;
        Octree nodeUBL;
        Octree nodeUBR;
        Octree nodeDFL;
        Octree nodeDFR;
        Octree nodeDBL;
        Octree nodeDBR;
        List<Octree> children;

        public static int modelsDrawn;
        private static int modelsStoredinOctreeTree;
        private static int modelsFullyContainedInNodes;
        private static int modelsIntersectionsInNodes;

        private static String collisionName;

        public int ModelsDrawn { get { return modelsDrawn; } set { modelsDrawn = value; } }
        public int ModelsInOctree { get { return modelsStoredinOctreeTree; } set { modelsStoredinOctreeTree = value; } }
        public int ModelsFullyContainedInNodes { get { return modelsFullyContainedInNodes; } set { modelsFullyContainedInNodes = value; } }
        public int ModelsIntersectionsInNodes { get { return modelsIntersectionsInNodes; } set { modelsIntersectionsInNodes = value; } }

        public static int modelsInNodes;
        public int ModelsInNodes { get { return modelsInNodes; } set { modelsInNodes = value; } }

        /// <summary>
        /// Octree - Creates a spatial partitioning octree
        /// </summary>
        /// <param name="center">Center of the Octree</param>
        /// <param name="size">How large is the octree</param>
        /// <param name="parent">The parent node (if not the root)</param>
        public Octree(Vector3 center, float size, Octree parent = null)
        {
            this.parent = parent;
            this.center = center;
            this.size = size;
            objects = new List<Entity>();
            children = new List<Octree>(8);

            Vector3 diagonalVector = new Vector3(size / 2.0f, size / 2.0f, size / 2.0f);
            bounds = new BoundingBox(center - diagonalVector, center + diagonalVector);

        }

        /// <summary>
        /// Return the Size of the Octree
        /// </summary>
        /// <returns>float</returns>
        public float WorldSize()
        {
            return size;
        }

        /// <summary>
        /// Returns the 8 children of this node so one can iterate over them
        /// </summary>
        /// <returns>List of Octree Nodes</returns>
        public List<Octree> GetChildren()
        {
            return children;
        }

        /// <summary>
        /// NeedSplit - Does this Node need to be split (max objects contained)
        /// </summary>
        private Boolean NeedSplit
        {
            get
            {
                return (objects.Count != 0 && maxObjectsInNode < objects.Count && size >= minSize);
            }
        }
        /// <summary>
        /// Is this Node Empty
        /// </summary>
        protected Boolean IsEmpty
        {
            get
            {
                return ((objects.Count == 0) && (HasChildren == false));
            }
        }

        /// <summary>
        /// Are the children nodes emtpy
        /// </summary>
        protected Boolean AreChildrenEmpty
        {
            get
            {
                if (HasChildren == false)
                    return true;

                for (int i = 0; i < 8; ++i)
                {
                    if (!children[i].IsEmpty)
                        return false;
                }
                return true;
            }
        }

        /// <summary>
        /// Does this Node have children
        /// </summary>
        private Boolean HasChildren
        {
            get
            {
                return (children.Count != 0);
            }
        }

        /// <summary>
        /// What type of containment is this bounding box to this
        /// </summary>
        /// <param name="bsbounds">ref bouding box</param>
        /// <returns>ContainmentType (Disjoint, Intersects, Contained)</returns>
        protected ContainmentType Containment(ref BoundingBox bbbounds)
        {
            ContainmentType containmentType;
            bounds.Contains(ref bbbounds, out containmentType);
            return (containmentType);
        }
        /// <summary>
        /// What type of containment is this bounding sphere to this
        /// </summary>
        /// <param name="bsbounds">ref bouding sphere</param>
        /// <returns>ContainmentType (Disjoint, Intersects, Contained)</returns>
        protected ContainmentType Containment(ref BoundingSphere bsbounds)
        {
            ContainmentType containmentType;
            bounds.Contains(ref bsbounds, out containmentType);
            return (containmentType);
        }

        /// <summary>
        /// Can this Node contain this bounding sphere
        /// </summary>
        /// <param name="bsbounds">ref bouding sphere</param>
        /// <returns>Boolean</returns>
        protected Boolean CanContain(ref BoundingSphere bsbounds)
        {
            return (ContainmentType.Contains == Containment(ref bsbounds));
        }
        /// <summary>
        /// Can this Node contain this bounding box
        /// </summary>
        /// <param name="bsbounds">ref bouding box</param>
        /// <returns>Boolean</returns>
        protected Boolean CanContain(ref BoundingBox bbounds)
        {
            return (ContainmentType.Contains == Containment(ref bbounds));
        }
        /// <summary>
        /// Can this bounding box intersect
        /// </summary>
        /// <param name="bbounds">ref bounding box</param>
        /// <returns>Boolean</returns>
        protected Boolean CanIntersect(ref BoundingBox bbounds)
        {
            return (ContainmentType.Intersects == Containment(ref bbounds));
        }
        /// <summary>
        /// Can this bounding sphere intersect
        /// </summary>
        /// <param name="bbounds">ref bounding box</param>
        /// <returns>Boolean</returns>
        protected Boolean CanIntersect(ref BoundingSphere bsbounds)
        {
            return (ContainmentType.Intersects == Containment(ref bsbounds));
        }
        /// <summary>
        /// Can this Octree node contain or intersect this Entity
        /// </summary>
        /// <param name="entity">Object Entity</param>
        /// <returns>Boolean</returns>
        protected Boolean CanContainOrIntersect(Entity entity)
        {
            if (entity.collision == Entity.Collision.BoundingSphere)
                return CanContainOrIntersect(entity.boundsphere);
            else
                return CanContainOrIntersect(entity.bounds);

        }

        protected Boolean CanContainOrIntersect(BoundingBox bbounds)
        {
            if (ContainmentType.Disjoint == Containment(ref bbounds))
                return false;
            else
                return true;
        }
        protected Boolean CanContainOrIntersect(BoundingSphere bsbounds)
        {
            if (ContainmentType.Disjoint == Containment(ref bsbounds))
                return false;
            else
                return true;
        }

        /// <summary>
        /// Can this Octree Node contain this entity
        /// </summary>
        /// <param name="entity">Object Entity</param>
        /// <returns>Boolean</returns>
        public Boolean CanContain(Entity entity)
        {
            if(entity.collision == Entity.Collision.BoundingSphere)
                return CanContain(ref entity.boundsphere);
            else
                return CanContain(ref entity.bounds);
        }

        public Boolean containsObjects()
        {
            if (objects.Count != 0)
                return true;

            if (children.Count != 0)
            {

                for (int index = 0; index < children.Count; index++)
                {
                    if (children[index].containsObjects() == true)
                        return true;
                }
            }

            return false;
        }

        public void Add(Entity entity)
        {
            entity.ID = modelsStoredinOctreeTree++;
            AddObject(entity);
        }

        /// <summary>
        /// Find the First Parent of the Entity
        /// </summary>
        /// <param name="entity">Object Entity</param>
        /// <returns>Octree</returns>
        private Octree FindEntityParent(Entity entity)
        {
            Octree octree = null;
            for (int index = 0; index < objects.Count; index++)
            {
                if (objects[index] == entity)
                {
                    return this;
                }
            }

            int child = 0;
            while ((octree == null) && (child < children.Count))
            {
                octree = children[child++].FindEntityParent(entity);
                if (octree != null)
                    break;
            }

            return octree;
        }

        /// <summary>
        /// Remove Entity based on its ID and return it // TODO add recursive
        /// </summary>
        /// <param name="modelID"></param>
        /// <returns></returns>
        private Entity RemoveEntity(int modelID)
        {
            Entity entity = null;

            for (int index = 0; index < objects.Count; index++)
            {
                if (objects[index].ID == modelID)
                {
                    entity = objects[index];
                    objects.Remove(entity);
                    Collapse(this);
                    return entity;
                }
            }

            int child = 0;
            while ((entity == null) && (child < children.Count))
            {
                entity = children[child++].RemoveEntity(modelID);
                if (entity != null)
                    break;
            }

            return entity;
        }

        private void RemoveObject(int objectIndex, Boolean merge = true)
        {
            // remove the object
            objects.RemoveAt(objectIndex);
            modelsInNodes--;

            if (merge == true)
            {
                // if all the children are empty lets clear the list
                if (AreChildrenEmpty)
                    children.Clear();

                // try and collapse / merge the Octree by notifying the parent to check other children
                if (IsEmpty)
                {
                    if (parent != null)
                        parent.AttemptMerge(this);
                }
            }
        }

        public Boolean RemoveObject(Entity octreeEntity)
        {
            if (octreeEntity == null) { throw new NullReferenceException("octreeEntity"); }

            if (!CanContain(octreeEntity)) // Object is definitely not in this tree
                return false;

            if (RemoveObjectHere(octreeEntity))//was pressent in this node
            {
                return true;
            }
            else //check child nodes
            {
                if (children.Count == 0)
                    return false;

                foreach (Octree child in children)
                {
                    if (child.RemoveObject(octreeEntity))
                        return true;
                }
            }

            return false;
        }

        public void RemoveObjectRecursively(Entity octreeEntity)
        {
            if (octreeEntity == null) { throw new NullReferenceException("octreeEntity"); }

            RemoveObjectHere(octreeEntity, false);
            if (children.Count != 0)
            {
                foreach (Octree child in children)
                    child.RemoveObjectRecursively(octreeEntity);
            }
        }

        protected Boolean RemoveObjectHere(Entity octreeEntity, Boolean merge = true)
        {
            if (objects.Count == 0)
                return false;       // no objects to remove

            int objIndex = objects.IndexOf(octreeEntity);
            if (-1 == objIndex)
                return false;

            octreeEntity.InsideNodes--;
            RemoveObject(objIndex, merge);
            return true;
        }

        protected void AttemptMerge(Octree abandonedChild)
        {
            if (AreChildrenEmpty)
            {
                children.Clear();

                if (parent != null && objects.Count == 0)
                {
                    parent.AttemptMerge(this);
                }
            }
        }

        public void Collapse(Octree octree)
        {
            int childrenNumber = octree.children.Count;
            if (childrenNumber != 0)
            {
                int counter = 0;
                for (int index = 0; index < childrenNumber; index++)
                {
                    if (octree.children[index].containsObjects() == false && octree.parent != null)
                    {
                        octree.children[index].Collapse();
                        counter++;
                    }
                }
                if (counter == childrenNumber)
                {
                    for (int index = (childrenNumber - 1); index >= 0; index--)
                    {
                        octree.children.Remove(octree.children[index]);
                    }
                    //octree.children.Clear();
                }

            }

            if (octree.objects.Count > 0)
                return;
            else if (octree.children.Count > 0)
                return;
            else
            {
                if (octree.parent != null)
                {
                    octree.parent.Collapse(octree.parent);
                }
            }

        }

        public void Collapse()
        {
            int childrenNumber = children.Count;
            if (childrenNumber != 0)
            {
                int counter = 0;
                for (int index = 0; index < childrenNumber; index++)
                {
                    if (children[index].containsObjects() == false)
                    {
                        children[index].Collapse();
                        if (parent != null)
                            counter++; // meaning we don't remove the top octree root
                    }
                }
                if (counter == childrenNumber)
                {
                    for (int index = (childrenNumber - 1); index >= 0; index--)
                    {
                        children.Remove(children[index]);
                    }
                    //children.Clear();
                }

            }

        }

        public Boolean AddObject(Entity octreeEntity)
        {
            if (octreeEntity == null) { throw new NullReferenceException("octreeEntity"); }

            if (!CanContainOrIntersect(octreeEntity))
                return false;

            //if (!CanContain(octreeEntity) ||

            if (!HasChildren || NeedSplit) // If no children
            {
                AddObjectHere(octreeEntity);

                if (NeedSplit)
                {
                    CreateChildren();
                    DistributeObjectsToChildren();
                }
            }
            else
            {
                if (!AddObjectToChildren(octreeEntity))
                {
                    AddObjectHere(octreeEntity);
                }
            }

            return true;
        }

        protected void AddObjectHere(Entity octreeEntity)
        {
            modelsInNodes++;
            octreeEntity.InsideNodes++;
            // debug remove in production
            if (CanContain(octreeEntity) == true)
                modelsFullyContainedInNodes++;
            if (CanIntersect(ref octreeEntity.bounds) == true)
                modelsIntersectionsInNodes++;
            objects.Add(octreeEntity);
        }

        private void CreateChildren()
        {
            float sizeOver2 = size / 2.0f;
            float sizeOver4 = size / 4.0f;

            nodeUFR = new Octree(center + new Vector3(sizeOver4, sizeOver4, -sizeOver4), sizeOver2, this);
            nodeUFL = new Octree(center + new Vector3(-sizeOver4, sizeOver4, -sizeOver4), sizeOver2, this);
            nodeUBR = new Octree(center + new Vector3(sizeOver4, sizeOver4, sizeOver4), sizeOver2, this);
            nodeUBL = new Octree(center + new Vector3(-sizeOver4, sizeOver4, sizeOver4), sizeOver2, this);
            nodeDFR = new Octree(center + new Vector3(sizeOver4, -sizeOver4, -sizeOver4), sizeOver2, this);
            nodeDFL = new Octree(center + new Vector3(-sizeOver4, -sizeOver4, -sizeOver4), sizeOver2, this);
            nodeDBR = new Octree(center + new Vector3(sizeOver4, -sizeOver4, sizeOver4), sizeOver2, this);
            nodeDBL = new Octree(center + new Vector3(-sizeOver4, -sizeOver4, sizeOver4), sizeOver2, this);

            children.Add(nodeUFR);
            children.Add(nodeUFL);
            children.Add(nodeUBR);
            children.Add(nodeUBL);
            children.Add(nodeDFR);
            children.Add(nodeDFL);
            children.Add(nodeDBR);
            children.Add(nodeDBL);
        }

        protected void DistributeObjectsToChildren()
        {
            if (children.Count != 0 && objects.Count != 0)
            {
                for (int i = objects.Count - 1; i >= 0; --i)
                {
                    Entity octreeObject = objects[i];
                    if (AddObjectToChildren(octreeObject))
                    {
                        RemoveObject(i);
                    }
                    //else
                        //AddObjectHere(octreeObject); // it is left in the parent
                }
            }
        }

        protected Boolean AddObjectToChildren(Entity entity)
        {
            if (children.Count != 0)
            {
                for (int index = 0; index < children.Count; index++)
                {
                    if (children[index].CanContain(entity) == true)
                    {
                        children[index].AddObject(entity);
                        return true;
                    }
                }
                Boolean added = false;
                int counter = 0;
                for (int index = 0; index < children.Count; index++)
                {
                    if (children[index].Containment(ref entity.bounds) == ContainmentType.Intersects)
                        counter++;
                }
                if (counter == children.Count)
                    return false;

                for (int index = 0; index < children.Count; index++)
                {
                    if (children[index].Containment(ref entity.bounds) == ContainmentType.Intersects)
                    {
                        children[index].AddObject(entity);
                        added = true;
                    }

                }
                return added;
            }

            return false;
        }

        protected void AddObjectToParent(Entity octreeEntity)
        {
            if (octreeEntity == null) { throw new NullReferenceException("octreeEntity null"); }
            if (!AddObject(octreeEntity))
            {
                if (parent != null)
                    parent.AddObjectToParent(octreeEntity);
            }
        }

        /// <summary>
        /// Check if the Ray intersects the Octree node
        /// </summary>
        /// <param name="ray"></param>
        /// <returns></returns>
        private Boolean CheckRay(Ray ray)
        {
            if (ray.Intersects(this.bounds) != null)
            {
                return true;
            }
            else
                return false;
        }

        public Boolean ContainsDynamic(BoundingBox bounds)
        {
            if (bounds == null) { throw new NullReferenceException("bounds null"); }
            List<Octree> containers = new List<Octree>(FindContainers(bounds));
            collisionNodesTraversedLast = containers.Count;
            if (containers.Count != 0)
            {
                foreach (Octree octree in containers)
                {
                    if (octree.objects.Count != 0)
                    {
                        collisionObjectCompaisions = 0;
                        foreach (Entity comparedEntity in octree.objects)
                        {
                            if (comparedEntity.CheckCollision(bounds) == true && comparedEntity.type == Entity.Type.DYNAMIC)
                            {
                                return true;
                            }
                        }
                    }
                }
            }
            return false;
        }

        public Boolean ContainsStatic(BoundingBox bounds)
        {
            if (bounds == null) { throw new NullReferenceException("bounds null"); }
            List<Octree> containers = new List<Octree>(FindContainers(bounds));
            collisionNodesTraversedLast = containers.Count;
            if (containers.Count != 0)
            {
                foreach (Octree octree in containers)
                {
                    if (octree.objects.Count != 0)
                    {
                        collisionObjectCompaisions = 0;
                        foreach (Entity comparedEntity in octree.objects)
                        {
                              if (comparedEntity.CheckCollision(bounds) == true && comparedEntity.type == Entity.Type.STATIC)
                              {
                                  return true;
                              }
                        }
                    }
                }
            }
            return false;
        }

        /// <summary>
        /// If ObjectChanged Update the node that it is located in (as it has tranformed in space and possibly moved nodes)
        /// </summary>
        /// <param name="octreeEntity"></param>
        public void ObjectChanged(Entity octreeEntity)
        {
            if (octreeEntity == null) { throw new NullReferenceException("octreeEntity null"); }
            Octree octree = FindEntityParent(octreeEntity);

            if (octree != null)
            {
                if(octree.parent != null)
                    octree.parent.RemoveObjectRecursively(octreeEntity); //destroy all instances of this entity
                else
                    octree.RemoveObjectRecursively(octreeEntity);

                if (octreeEntity.InsideNodes != 0)
                    this.RemoveObjectRecursively(octreeEntity);

                if (!octree.CanContain(octreeEntity)) // if the current top node cant contain the object
                {
                    if (octree.parent != null) // if parent is not null
                    {
                        if (octree.parent.CanContain(octreeEntity)) // if the parent can contain
                        {
                            if (!octree.parent.AddObject(octreeEntity))
                            { throw new NullReferenceException("Octree: ObjectChanged(): Object could not be added to parent node"); }
                        }
                        else if (octree.parent.parent != null)
                        {
                            if (octree.parent.parent.CanContain(octreeEntity)) // if the parents parent can contain (2 branches up as max, else be better putting into root)
                            {
                                if (!octree.parent.parent.AddObject(octreeEntity))
                                { throw new NullReferenceException("Octree: ObjectChanged(): Object could not be added to parent.parent node"); }
                            }
                            else
                            {
                                if (!this.AddObject(octreeEntity))
                                { throw new NullReferenceException("Octree: ObjectChanged(): Object could not be added to the root octree"); }
                            }
                        }
                        else
                        {
                            if (!this.AddObject(octreeEntity))
                            { throw new NullReferenceException("Octree: ObjectChanged(): Object could not be added to the root octree"); }
                        }
                    }
                    else
                    {
                        if (!this.AddObject(octreeEntity))
                        { throw new NullReferenceException("Octree: ObjectChanged(): Object could not be added to the root octree"); }
                    }
                }
                else
                    if (!octree.AddObject(octreeEntity))
                        throw new NullReferenceException("Octree: ObjectChanged(): Object could not be added back to its current node");
            }
            else
            {
                //throw new NullReferenceException("Octree: ObjectChanged(): Parent of changed object was null? Debug this!");
                if (!this.AddObject(octreeEntity))
                    throw new NullReferenceException("Octree: ObjectChanged(): Object could not be added to the root octree!!!???? out of range?");
            }

            if(octree != null)
                Collapse(octree);

        }

        /// <summary>
        /// Draw
        /// </summary>
        /// <param name="viewMatrix">View Matrix</param>
        /// <param name="projectionMatrix">Project Matrix</param>
        /// <param name="cameraFrustrum">Bounding Camera Frustrum</param>
        public void Draw(Matrix viewMatrix, Matrix projectionMatrix, BoundingFrustum cameraFrustrum)
        {
            ContainmentType cameraNodeContainment = cameraFrustrum.Contains(bounds);
            if (cameraNodeContainment != ContainmentType.Disjoint)
            {
                if (objects.Count != 0)
                {
                    foreach (Entity entity in objects)
                    {
                        if (entity.drawn == false)
                        {
                            entity.Draw(viewMatrix, projectionMatrix);
                            modelsDrawn++;
                            entity.drawn = true;
                        }
                    }
                }

                foreach (Octree childNode in children)
                    childNode.Draw(viewMatrix, projectionMatrix, cameraFrustrum);
            }
        }

        public void DrawBoxLines(Matrix viewMatrix, Matrix projectionMatrix, GraphicsDevice device, BasicEffect basicEffect)
        {
            foreach (Octree childNode in children)
                childNode.DrawBoxLines(viewMatrix, projectionMatrix, device, basicEffect);

            if (children.Count == 0)
                Utilities.DrawBoundingBox(bounds, device, basicEffect, Matrix.Identity, viewMatrix, projectionMatrix);
        }

        public void DrawZoneOfDeath(Matrix viewMatrix, Matrix projectionMatrix, GraphicsDevice device, BasicEffect basicEffect)
        {
            Vector3 diagonalVector = new Vector3(2, 2, 2);
            Utilities.DrawBoundingBox(new BoundingBox(center - diagonalVector, center + diagonalVector), device, basicEffect, Matrix.Identity, viewMatrix, projectionMatrix, Color.Orange);
        }
    }
}

```

# Answer
For occlusion culling with an octree, you could build low-res hierarchical depth buffer first from potential occluders (taking max depth of 4 samples for lower-res LOD) and test the octree against it. You need to determine the octree node size in screen and pick the proper LOD to test against to reduce the test to 4 samples per octree node.

The main issue is how you build the initial occlusion buffer to test the octree against without rendering everything. You could: 1) Hand pick larger models and render them to the buffer 2) Reproject previous frame depth (only stationary objects), but this introduces holes so you would need to patch it somehow 3) Render objects which were visible last frame, but you need some way to determine which objects were visible (e.g. render object ID buffer)

Since you said you are using instancing, this could be done entirely in GPU side by building an instance stream thus you don't need to figure out how to get the rasterized depth buffer to CPU (without latency issues). You might be better off not using octree though but just throwing all the instances in FOV to the shader which does the occlusion test and builds your visible instance stream.
> 1 votes

# Answer
This question deals with the same problem, even if its c++ & opengl most of the concept apply to your case too. There is also a good general article on Gamasutra regarding visibility culling.

For your special case you could construct an octree, where the leaves contain batches of cubes and than use bounding boxes to check if a region is visible or not.

Just to make sure if you are familiar with the general concept: Occlusion Culling with octree works this way: You develop a simplified visibility check and divide your word into an octree. You start on a higher level and move down the tree. If a branch isn´t visible all the sub branches and leaves can be discarded too.

Using the class given, you could probably make use of the `CanContainOrIntersect` method to test for visibility.

But I also agree with Steven, if you have problems with 20x20x20 cubes you should definitely look into some other optimizations.
> 0 votes

---
Tags: c#, octree
---


title: Can not remove cube in UDK

text:
# Question
Title: Can not remove cube in UDK
For some reason, I can't move or remove an 'invisible' cube which is on my map. I searched on Google to find a solution but somehow I still can't remove it.

The cube looks like this: http://screencloud.net/v/uNyz

In Brush Wireframe: http://screencloud.net/v/3C0c

In Wireframe: screencloud.net/v/oGBj

As you can see, I want to delete the brown cube. Selecting it and pressing the DEL button won't do anything.

So, how do you delete the brown cube?

---

EDIT: Seriously, I wrote this post a few minutes ago and I found the solution. However, I still don't know how to delete the brown cube.

# Answer
The "brown cube" that you are referring to sounds like it's the builder brush. It is commonly referred to as red and it can be various shapes depending on your last brush setting. You can toggle it's display with the 'B' key.

You may also be referring to a BSP wireframe, in which case you must Ctrl+Shift+click to select it unless you are in a wireframe viewmode.
> 1 votes

# Answer
This is a common mistake for many beginner UDK users. The brown cube is probably the builder brush, a very useful tool for creating meshes that physically affect your character in UDK. *(If you are creating a more complicated project, I would strongly recommend either avoiding them or converting them to 'Static Meshes' - see the referenced tutorial.)* The brown cube is important lots of the time - if you hide it by pressing B, know that you can bring it back by pressing B again.

It could also be a BSP wireframe. (This is something that has been created by the builder brush.) If the above does not work, you can then go into wireframe mode, click on the frame of the 'brown' cube, and press 'Del'/'Delete' on your keyboard (or right click and select delete.) Of course, it is unlikely that it is a BSP wireframe as it would probably appear with its default material - checkered blue and white.

If you are a beginner UDK user, I strongly recommend "Brainspace Showcase"'s UDK tutorials. These were very helpful for me.
> 1 votes

---
Tags: udk
---


# Question
Title: Road network geometry in Unity: one big mesh or a bunch of smaller meshes?
I'm in the beginning stages of building a road system in Unity. It'll be your basic SimCity style road construction, with building and destroying roads done on the fly at runtime. When doing thing, given the fact that geometry will be so often added and destroyed, should I keep a separate mesh for each segment of road, or should I maintain one big road mesh for the whole scene and add and remove vertices to it when roads are modified? In larger road networks would there be any performance difference between the two? I'm not so familiar with this sort of optimization in Unity, so any help is appreciated.

So basically, many small meshes or one big mesh? Does it matter?

# Answer
Yes it matters but there's no general rule, it depends on the specific scenario and requirements. Here's some hints:

**1 Mesh Scenario**

Pros:

* Reduce drawcalls(state changes).

Cons:

* No occlusion culling(it's done on a per GameObject resolution in Unity)
* Potentially time consuming updating the required vertices (depends on the geometry complexity, but for a large street network it may not be the best choice)

**Multiple Mesh Scenario**

Pros:

* Easy to update
* Occlusion culling (even with static batched geometry)

Cons:

* 1 drawcall per object/material without batching
* Memory footprint increase with static batching
* If static batching is used modify geometry at runtime could be difficult (definitely possible but eventually requires some work)

A possible approach I think you could evaluate is to subdivide your world into several patches. For each patch use a single mesh for the street network. In such a way you can potentially have reasonable performances dynamically updating the geometry, while still relying on culling for geometry outside the frustum or occluded.
> 6 votes

# Answer
You should keep in mind there's a set limit to mesh sizes in Unity3D.

The maximum number of vertices a mesh can have in Unity3D is 65,534 vertices. Regardless of the merits of using a single mesh, this will almost certainly force you to separate your meshes.
> 1 votes

---
Tags: unity, 3d-meshes
---


# Question
Title: How can I manually construct a right-handed orthographic projection matrix?
I need the formula to create a orthographic projection matrix. I am using GLM math libary and DirectX11. The reason I cannot use GLM to create it is because the NDC spaces are different between DX11 and OpenGL, thus I need to manually create one.

I am however using right-handed coordinate system and column-major matrices, just like GLM.

This is my attempt, but I get wrongly images when rendering with it, so it is probably wrong. I am using it for cascading shadow maps, and from the graphics debugger, I probably need to mirror it, but it is just a guess. Any ideas?

```
Mat4 OrthographicMatrix(const float left, const float right, const float top, const float bottom, const float zNear, const float zFar)
{
    Mat4 ret(1.0f);

    ret[0][0] = 2.0f / (right - left);
    ret[1][1] = 2.0f / (top - bottom);
    ret[2][2] = 1.0f / (zNear - zFar);
    ret[3][0] = (left + right) / (left - right);
    ret[3][1] = (top + bottom) / (bottom - top);
    ret[3][2] = (zNear) / (zNear - zFar);

    return ret;
}

```

# Answer
> 4 votes
The D3DX function `D3DXMatrixOrthoOffCenterRH` constructs an orthographic projection matrix based on the top/left/right/bottom coordinates of the view volume. Per the documentation, the formula used is:

\begin{matrix} 2/(r-l) & 0 & 0 & 0 \\ 0 & 2/(t-b) & 0 & 0 \\ 0 & 0 & 1/(zn-zf) & 0 \\ (l+r)/(l-r) & (t+b)/(b-t) & zn/(zn-zf) & 1 \end{matrix}

where top, left, bottom and right coordinates are represented as `t`, `l`, `b` and `r` respectively. The minimum and maximum depth values are `zn` and `zf`.

Since the math here appears to be the identical to the math for your individual components, you're probably seeing a problem in the storage of those components (resulting in an effective transposition). I'd verify the storage location of your last three components is actually what you need it to be.

(Don't just blindly transpose your storage; it's possible you have two transpose-esque bugs elsewhere cancelling eachother out and you're just adding a third; you'll want to review your matrix storage class carefully as where as everywhere in your basic pipeline that you are expecting right-handed systems and conventions to make sure you're not accidentally doing the wrong thing.)

# Answer
> 2 votes
Rather than use the legacy D3DXMath, consider using DirectXMath instead
Plus you get all the source in the header.

This computes the matrix as a row-major, right-handed matrix:

```
inline XMMATRIX XMMatrixOrthographicOffCenterRH
(
    float ViewLeft,
    float ViewRight,
    float ViewBottom,
    float ViewTop,
    float NearZ,
    float FarZ
)
{
    assert(!XMScalarNearEqual(ViewRight, ViewLeft, 0.00001f));
    assert(!XMScalarNearEqual(ViewTop, ViewBottom, 0.00001f));
    assert(!XMScalarNearEqual(FarZ, NearZ, 0.00001f));

#if defined(_XM_NO_INTRINSICS_)

    float ReciprocalWidth = 1.0f / (ViewRight - ViewLeft);
    float ReciprocalHeight = 1.0f / (ViewTop - ViewBottom);
    float fRange = 1.0f / (NearZ-FarZ);

    XMMATRIX M;
    M.m[0][0] = ReciprocalWidth + ReciprocalWidth;
    M.m[0][1] = 0.0f;
    M.m[0][2] = 0.0f;
    M.m[0][3] = 0.0f;

    M.m[1][0] = 0.0f;
    M.m[1][1] = ReciprocalHeight + ReciprocalHeight;
    M.m[1][2] = 0.0f;
    M.m[1][3] = 0.0f;

    M.m[2][0] = 0.0f;
    M.m[2][1] = 0.0f;
    M.m[2][2] = fRange;
    M.m[2][3] = 0.0f;

    M.r[3] = XMVectorSet(-(ViewLeft + ViewRight) * ReciprocalWidth,
                         -(ViewTop + ViewBottom) * ReciprocalHeight,
                         fRange * NearZ,
                         1.0f);
    return M;

```

You can transpose it to get the column-major version.

---
Tags: mathematics, directx, matrix
---


# Question
Title: How to implement camera pan like in Maya?
I am trying to implement camera pan like the one in Maya. I've got it almost working.

The problem is that the mouse cursor is moving faster than the 3d mesh (in fact I am moving the camera but I said mesh, because it is more intuitive), while in Maya the distance between the mouse position and the mesh stays always the same.

This is what my code looks like :

```
glm::vec3 dist = cameraPos-modelPos;
float len=glm::length(dist);

float clipX = startX*2.0 / width - 1.0;
float clipY = 1.0 - startY*2.0 / height;

float clipEndX = lastX*2.0 / width - 1.0;
float clipEndY = 1.0 - lastY*2.0 / height;

// convert begin and end mouse positions into world space
glm::mat4 inverseMVP = glm::inverse(projection*view*modelMatrix);
glm::vec4 outVector = inverseMVP*glm::vec4(clipX, clipY, 0.0, 1.0);
glm::vec3 worldPos(outVector.x/outVector.w, outVector.y/outVector.w, outVector.z/outVector.w);

glm::vec4 outEndVec = inverseMVP*glm::vec4(clipEndX, clipEndY, 0.0, 1.0);
glm::vec3 worldPos2(outEndVec.x/outEndVec.w, outEndVec.y/outEndVec.w, outEndVec.z/outEndVec.w);

glm::vec3 dir = worldPos2 - worldPos;

glm::vec3 offset=glm::length(dir)*glm::normalize(dir)*angleFovRatio*len/2.f;
cameraPos-=offset;
cameraTarget-=offset;

```

Where `angleFovRatio = std::tan(cameraFov*0.5f)` I am using `glm::lookAt(cameraPos, cameraTarget, cameraUp);` for my `view` matrix

I will add picture of what my problem is:

As you can see, when I drag to the right, the red dots are my begin and end mouse positions. But the teapot is on the blue dot, which is not what I want. It must be centered on the second red dot (mouse end position, just like in maya).

# Answer
> 2 votes
This is a general explanation answer, you'll have to check with the code yourself.

Perspective projection looks like this from above:

Near clipping plane is what you see on your screen. Now see that the farther you get from it, the more you need to move the object to have it in the same position on the screen.

For example take Blue point, it got moved from the middle to the right by 10m. If you move Red point by the same 10m you get it way to the right (hollow red point). To have Red point in the same place on the screen you need to move it by only 8m. Same applies to the Green point - to preserve it relative position on the screen it needs to be moved ~12m, otherwise it will appear to be moved too close relative to Blue point.

Another look at the situation is when you move the Camera 10m to the left. Imagine original setup with points being in the center of the Camera (hollow Red, Blue, hollow Green). When you move camera 10m to the left, points remain in place, but their projection to the screen changes - Green remains closer to center, Blue - farther and Red in the middle.

So it seems that when you move your cursor 100px you get the required distance from Blue points plane (10m), but your teapot object is in Green points plane, so it is moved the same 10m and it makes it look as moved too little on the screen (just 80px).

TL;DR: Calculate pan distance for the selected objects distance from camera.

---
Tags: opengl, c++, camera, maya
---


# Question
Title: Doing a turntable camera animation on a world matrix rather than view matrix
I have a camera class that contains a 4x4 view matrix as a member variable. Most of my camera controls work fine when doing them directly on the view matrix. In an attempt to unify all of my scene objects I want to do all of these transformations on the local matrix.

I plan on ultimately switching to a model with scale, position and rotation stored separately but that isn't the question at the moment.

Here my question again in a (hopefully more clear way):

I want to perform a turn table animation on a camera (rotation around an arbitrary point) I have working code for doing it directly on the view matrix. Also very important, the rotation must be around a set up axis (in my case +Y).

How can I achieve the same affect by transforming the local matrix directly?

**Working turn table control directly on view matrix**

```
// dX and dY are mouse deltas for the current frame
Vector3 position = viewMatrix.getPosition();
Vector3 forward = viewMatrix.getForward();
Vector3 right = viewMatrix.getRight();

// rotate around the focal point in front of us
Vector3 rotationPoint = position + forward * focalPoint;

Matrix4 rot;
rot.translate(rotationPoint);
rot.rotate(-dY, right);
rot.rotate(-dX, Vector3::Y_AXIS);
rot.translate(-rotationPoint);

viewMatrix = viewMatrix * rot;

```

**Attempt to make it work on the local matrix:**

```
// dX and dY are mouse deltas for the current frame
Vector3 position = localMatrix.getPosition();
Vector3 forward = localMatrix.getForward();
Vector3 right = localMatrix.getRight();

// rotate around the focal point in front of us
Vector3 rotationPoint = position + forward * focalPoint;

Matrix4 rot;
rot.translate(-rotationPoint);
rot.rotate(dX, Vector3::Y_AXIS);
rot.rotate(dY, right);
rot.translate(rotationPoint);

localMatrix = localMatrix * rot;

```

What happens: The animation is wonky, the pivot point seem to move while I rotate and the camera slowly drifts away.

Additional information:

Why do I need that? I want to be able to transform any scene object the same way. I might want to rotate a mesh around a point like I do the camera.

Is it easier to achieve what I want with a scale/position/rotation model? Even if it is I'm still interested on where I'm making a mistake here.

I will edit this post in the morning if there are any uncertain parts.

**------------------------------------------------------**

**Edit:**

I tried to rephrase my problem a bit I will leave the initial post for now, I hope I am more clear in this second attempt.

My Problem: I have working code for controlling a cameras view matrix and orbiting around a point in space.

Here is said code:

```
// get position and look at, look up and look right directions for the view matrix
Vector3 pos, la, lu, lr;
viewMatrix.lookAt(&pos, &la, &lu, &lr);

// rotate around point 5 units in front of us
Vector3 rotationPoint = pos+ la * 5;

Matrix4 rot;
rot.translate(rotationPoint);
rot.rotate(-dY, lr);
rot.rotate(-dX, Vector3(0,1,0));
rot.translate(-rotationPoint);
viewMatrix *= rot;

```

here is the code for the lookAt function used above: It will retrieve you the position and forward, right, up directions from a VIEW matrix.

```
void Matrix4::lookAt(Vector3* eye, Vector3* at, Vector3* up, Vector3* ri)
{
    Matrix3 invRot(_m);               // get the current view matrix
    invRot.translation(0,0,0);          // remove the translation
    invRot.transpose();                 // transpose it to get inverse rot.
    eye->set(invRot.multVec(-translation())); // setMatrix eye
    ri->set( _m[0], _m[4], _m[8]);            // normalized look right vector
    up->set( _m[1], _m[5], _m[9]);            // normalized look up vector
    at->set(-_m[2],-_m[6],-_m[10]);           // normalized look at vector
}

```

Note: the matrices are column major.

The code above works, the camera orbits an object around the world Y axis perfeclty. What I want to do: I want this same behaviour, but on a cube or other mesh! So I obviously don't need to do it on the view matrix then, since the transformation of that cube uses a world matrix. Now I could of course use the above and just invert it, but that is kind of cheating.

Here is my attempt to make the above work on a world space matrix:

```
// get the position and the three axis directions for the world matrix
Vector3 pos, la, lu, lr;
pos = worldMatrix.translation();
la.set(-worldMatrix.m(8), -worldMatrix.m(9), -worldMatrix.m(10));
lr.set(worldMatrix.m(0), worldMatrix.m(1), worldMatrix.m(2));
lu.set(worldMatrix.m(4), worldMatrix.m(5), worldMatrix.m(6));

Vector3 rotationPoint = pos + la * 5;

Matrix4 rot;
rot.translate(-rotationPoint);
rot.rotate(dX, Vector3(0,1,0));
rot.rotate(dY, lr);
rot.translate(rotationPoint);

worldMatrix *= rot;

```

The matrix is still column major. The retrieved position, look at, look right and look up vectors are correct. But when I print out the rotationPoint it moves. So the question is as simple as: Why does the above world matrix code not rotate my cube around the Y and look right axis around 'rotationPoint'?

# Answer
> 1 votes
Assuming you are dealing with additive operations (i.e. rotation translation order is important). Generally you would want to update your Camera matrix in this order:

1. Take identity matrix.
2. Translate to `FocalPoint`
3. Rotate to look in to the right direction
4. Translate away from the `FocalPoint` by the `DistanceFromFocal`

Same works with any Object that you want to place instead of Camera.

If above approach works for the Camera, but not for the Object, then there's a bug in your code somewhere

---
Tags: opengl, camera, matrix
---


# Question
Title: How to sync client and server at the first frame
I'm making a game where an authoritative server sends information to all clients about states and positions for objects in a 3d world. The player can control his character by clicking on the screen to set a destination for the character, much like in the *Diablo* series.

I've read most information I can find online about interpolation, reconciliation, and general networking architecture (Valve's for instance). I think I understand everything but one thing seems to be missing in every article I read. Let say we have an interpolation delay of 100ms, server tickrate=50ms, latency=200ms; How do I know when 100ms has past on the client? If the server sends the first update on t=0, can I assume it arrives at t=200, therefore assuming that all packets takes the same amount of time to reach the client? What if the first packet arrives a little quick, for instance at t=150. I would then be starting the client with t=150 and at t=250 it will think it has past 100ms since its connect to the server when it in fact only 50ms has past.

Hopefully the above paragraph is understandable. The summarized question would be: How do I know at what tick to start simulating the client?

EDIT: This is how I ended up doing it: The client keeps a clock (approximately) in sync with the server. The client then simulates the world at

```
simulationTime = syncedTime - avg(RTT)/2 - interpolationTime

```

The round-trip time can fluctuate so therefore I average it out over time. By only keeping the most recent values when calculating the average I hope to adapt to more permanent changes in latency. It's still to early to draw any conclusion. I'm currently simulating bad network connections, but it's looking good so far.

Anyone see any possible problems?

# Answer
There are two approaches to this.

**Lock Step**

In Lock Step all clients send there data for frame 1 to the server and then wait. The server collects the frame 1 data from all clients and only processes them once all are received. It then sends the result back to all clients and gives the clients the go-ahead to start working on frame two. Note that with frame here I mean 'simulation frame' the client can still continue animating, smoothing etc... The network rate could be 15FPS while the game is still looking smooth, animated at 60FPS.

The benefit of this technique is that its very easy to keep everything synchronized, as everybody just waits for each other. Its also very easy to send all information, as only what has changed (or what influenced those changes, such as key presses) needs to be send since all clients are in the same step of the simulation. The drawback is that one slow-client can make the game slower for all users.

Remember the little turtle on the bottom right while playing Age of Empires? Or the time going a lot slower than it should be in Supreme Commander? This indicated that one of the clients was slower, and it was slowing the other clients down.

**Authorative (non-lockstep) server**

The other approach is for the clients to not wait for each other. The clients continuously send their changes and the server approves/disapproves them on a first-come-first-served basis while also sending back the the state of the simulation on which this approving/disapproving was based. (Which is also the state the client should be at as soon as possible). There is no really synchronous beginning. (Though you should have clients wait until every other client is connected as well)

This approach is heavier on network traffic but simpler to implement and slow clients do not slow down other clients.
> 8 votes

# Answer
There are 2 approaches to that

**You make clients synchronized - Lock-Step model:**

Firstly - read this 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond. It's about RTS, but from your description that applies to your game as well.

Every client gets a Tick 0 moment (e.g. server sends message to start in MaxLag - ClientLag ms to all clients) and runs it's local timer from that.

Now when messages arrive early they are queued for execution at a later point, so not to break order of events. We want every client to do A B C on exactly the same ticks in exactly that order. Early execution is not allowed, because it will make clients states loose sync.

When tick occurs and there'a yet no message arrived, client should pause and wait for the message (that's lag that player sees).

**You make the server keep the logic**

This way you make the server to do all the games logic. Clients are only displaying the most recent state (whatever that is) and collect players actions and send them to server. In this case you don't care about timing and just display ASAP. That is usually used in racing games and FPS, where things need to be fast and precision is not that important.
> 3 votes

---
Tags: networking, synchronization
---


# Question
Title: Opengl ES 2.0: Is there a way to use less resources to draw in-game background texture
1.Should my in-game background be drawn with my game loop renderer, or if

2.I don't want to draw my background image every frame in my main renderer since it could possibly be a heavy job while the game loop is running. Do I need to use a separate thread or some other method to achieve this?

FYI, the background should be able to scale and translate with zooming function, it should be flexible.

# Answer
> 1 votes
You are going to have background rendered either way. OpenGL redraws the whole frame each time. So what does it matter for performance where are you drawing it from? :)

It does not matter, unless you are doing some heavy computations to generate the background on CPU.

What you probably do is just updating the background location each frame (position, scale, rotation), which is practically free. Doing that less often wont affect performance by more than 0.0001%. If it does affect performance - then you are doing something wrong or not describing the whole picture in your question.

Adding threads for this "free" task will just slow you down due to threads synchronization and cross-communication.

P.S. Always test your performance (that's called Profiling) before and after optimizations, you'll be surprised ;)

---
Tags: android, textures, opengl-es2
---


title: Prefab random rotation in editor

text:
# Question
Title: Prefab random rotation in editor
Is it possible to automacicaly random rotate pefab during placement in editor in unity 4.5.3?

I can make it autorotate in game(at start) but I want it to be visible in editor and at fixed rotation after placement.

# Answer
> 5 votes
Found it! Attribute `[ExecuteInEditMode]` does what I want

```
[ExecuteInEditMode]
public class RandomRotation : MonoBehaviour {
    void Start () {
#if UNITY_EDITOR
        this.transform.Rotate(0, MyRandom.Rotate(this.GetInstanceID()), 0);
        this.transform.localScale = MyRandom.Scale (this.GetInstanceID(), 0.4f, 1f);
        Debug.Log("Editor");

#else
        Debug.Log("Game");
#endif
    }
}

```

---
Tags: unity, unityscript
---


title: Detecting Hitbox Collisions (Rectangle)

text:
# Question
Title: Detecting Hitbox Collisions (Rectangle)
So I have some Hitboxes set up on 2 classes, HealthPickup and Player.

```
public static Rectangle Hitbox;

public override void Initialize()
{
    Hitbox = new Rectangle(Pos.X, Pos.Y, 32, 32);
}

```

That's just general code, there are other things in the classes too. So what I want to know is why this doesn't work:

```
// This is in the HealthPickup class' Update function.
if (Hitbox.Intersects(Player.Hitbox))
{
    Console.Beep();
}

```

Doesn't work if I put it in the main update function either. Am I missing something?

# Answer
> 3 votes
It's likely the hitboxes are never colliding.

It's not clear how you're creating the player hitbox, but if it's the same way, they'll never collide. You're creating a rectangle based off the position your object starts at. You should create a hitbox on the fly, based on the current position of the object at the time of the collision check. This ensures your hitboxes are actually where you think they are in the world, and can correctly detect when an intersection happens.

# Answer
> 1 votes
What I would to is set a key to show the hit box. I tend to use F1 and that way when I hit the F1 key all my hit boxes show up as red. In order to get that to work you would create a 1x1 blank texture and :

In LoadContent:

```
content.Load<Texture2D>(@"1x1");//or replace 1x1 with where you put the image

```

In Update:

```
KeyboardState keyst=Keyboard.GetState();

If (keyst.IsKeyDown(Keys.F1))
{

    drawHitbox(spritebatch);

}

```

new Draw Function:

```
void drawHitbox(SpriteBatch spriteB)
{

    spriteB.Begin();

    spriteB.draw(1x1Tex,HitboxRect,Color.Red);//NOTE you might need multiple calls to draw depending on how your code is set up.

    spriteB.End();

}

```

This way you can tell where your hit boxes are and if they are actually colliding / moving as long as you hold down the F1 key.

---
Tags: xna, c#, 2d, xna-4.0
---


# Question
Title: How can I modify this projectile class to support movement in an arbitrary direction?
Hi I have the following class which Updates and Draws a projectile:

```
public class TierOneProjectile : IProjectile
{
    private AnimatedTexture animation;
    private Vector2 screenPosition, framesPerSecond, origin;
    private float rotation, scale, depth;
    private int velocity;

    public TierOneProjectile(Vector2 _screenPosition,int _velocity,AnimatedTexture _animation)
    {
        screenPosition = _screenPosition;
        animation = _animation;
        velocity = _velocity;
    }

    public void Update(float elapsedGameTime)
    {
        animation.UpdateFrame(elapsedGameTime);
        screenPosition.X -= velocity;

    }

    public void Draw(SpriteBatch spriteBatch)
    {
        animation.DrawFrame(spriteBatch,screenPosition);
    }

    public Rectangle getBoundingBox()
    {
        return new Rectangle((int)screenPosition.X, (int)screenPosition.Y, (int)animation.GetTextureWH().X, (int)animation.GetTextureWH().Y);
    }
}

```

Currently the projectile alway flies to the left. Little did I know when I created this class. Now I want to pass a direction to the constructor so every projectile could fly into a different direction. What would be the smartest solution for this? I do not want you to write the code for me. But maybe you could give me a hint how this could be done.

# Answer
What you have now is essentially:

```
screenPosition.X -= velocity * 1.0;
screenPosition.Y -= velocity * 0.0;

```

You need to explicitly add a `Direction` variable which is a 2D vector (you are dealing with 2D, right?).

```
Direction = (1.0, 0.0);

```

You might be already seeing my lead. You need to scale `Velocity` by `Direction` and add to your `Position` like so:

```
screenPosition.X -= velocity * Direction.X;
screenPosition.Y -= velocity * Direction.Y;

```

Adding parameter to a constructor and a new field to the class is trivial.

P.S. I don't think there's anything smarter than simplicity in this case ;)
> 2 votes

---
Tags: xna, direction
---


# Question
Title: How do you break apart art into components for animation?
I am a programmer and brand new to the game world, trying to get a sense of what it would take to draw simple characters like you'd see in Don't Starve or indie games like that.

I have seen in their forums images of the characters all broken up into pieces, and found Spriter for windows, and eventually Spine 2D for mac which looks amazing. They have many tutorials that show taking a set of images, applying them to a skeleton, and animating them.

My question is, what is the workflow for creating the characters so you end up with all of these character *parts*, which you can then use in a skeletal animation?

* Do you open up photoshop or some image editor, and just start drawing a foot or an eye?
* Or do you draw the whole character first, and then methodically go through and break it apart into individual images?
* If so, what is your workflow for doing that? In some of these broken apart images (like the above), many of the pieces overlap in some way.
* So it's like, if you draw a complete arm, and then break it up into a hand, a forearm, and an upper arm, in the process of breaking it apart, you would have a technique for somehow closing off the ends where you made the cut, so it is "ideal" for animating. Is there a technique for this?

This is probably a really basic question.. I have been learning to draw by hand and wonder what things you want to pay attention to if you were preparing them for a game.

# Answer
> 1 votes
What I've used among personal projects and projects for clients (when I'm part of a team that has dedicated artists) is a workflow similar to this one. Maybe there are obvious steps, but that's the pipeline.

1. Create the character first draft (to put a name) and preferably work everything on layers (e.g. Photoshop layers and layer folders)
2. Define the different actions for it
3. Decide which actions require frame-by-frame animation or just code (rotating things, moving things a little -e.g. weapon's kickback-)
4. Split up the animation pieces (head, limbs, etc). Some of them require sub-division (lips, eyes, etc)
5. Rearrange the layers if needed
6. Create every animation piece as a frame and export it (e.g. .png files)
7. Arrange those frames in one or several atlases (a.k.a. sprite sheets), depending on the technology you're using, max. texture resolution, etc.
8. Export atlases.

# Answer
> -1 votes
Your image looks like texture. The most obvious way of using it is to map to polygons of model. In your case it is 2D planes with textures on it. They can be layered like paper doll and dresses.

So, you need to create texture image first and then map its parts to polygons

Read more about texture mapping

---
Tags: 2d, animation, assets, art, skeletal-animation
---


# Question
Title: What kind of algorithms could I use to generate biome borders like in Minecraft?
After I've found this post I'm curious what kind of algorithms they use to generate these shapes (second image).

I can't imagine that the basic shapes are basing on a perlin or simplex noise or a voronoi diagram. With voronoi I'm a bit uncertain to be honest.

Well, so what do you think. What algorithm could be used to generate biome borders like they do?

# Answer
> 0 votes
you first create a set of parameters that you will generate, for example elevation, humidity, temperature

then you can define a function that will return a biome from any combination of these parameters

how you generate those parameters is usually with perlin or simplex noise but you can let it depends on other (previously generated) parameters like elevation and prevailing wind to create a rain shadow.

---
Tags: procedural-generation, minecraft-modding, perlin-noise
---


# Question
Title: How do I achieve supersampling / anti-aliasing in pixel shaders?
I am trying to write a couple pixel shaders to apply to images similar to Photoshop effects. For example this effect:

But I noticed there is aliasing in my resulting image (the above image is a sample from the linked website).

What can I do to prevent this? I couldn't find any article that explains how to solve this. I read some techniques like rendering in a higher resolution and then downsizing the image, but I need to solve this in a pixel shader capacity.

# Answer
**Super Sampling**

Super sampling and anti-aliasing are two different things. Super sampling is just rendering a frame at a higher resolution so that you have more information . This higher-resolution image is then down-sampled. This is especially useful when objects are very thin and might have been missed when sampling on a lower resolution. Down sampling from a higher resolution means they still have some influence. However since you can't super sample in a shader let's move on!

**Shader based anti-aliasing**

There are actually several techniques for shader based anti-aliasing. You could look up papers and example code of FXAA and MLAA. A nice comparison of quality can be found here. Let me out-line the general idea.

A naive approach to anti-aliasing would just be to gather information from neighboring pixels. While this does get rid of jagged edges somewhat it also blurs important details.

FXAA and MLAA are used in modern graphics pipelines where the normals, depth, and color information is often available separately even during the post-processing step. FXAA and MLAA use the color and depth/and or normal information to compute where edges occur. An edge could be the pixels on the line between the roof of a house and the horizon. These kinds of edges can be blurred to decreased aliasing without losing too much details in textures.
> 2 votes

---
Tags: c#, graphics, hlsl, fragment-shader, antialiasing
---


# Question
Title: Why does this code to render a triangle in SlimDX only show a black screen?
Here is the code:

```
 var elements = new VertexElement[] {
                    new VertexElement(0,0,DeclarationType.Float3,DeclarationMethod.Default,
                            DeclarationUsage.Position | DeclarationUsage.Color,0),

                    VertexElement.VertexDeclarationEnd
                };

            VertexDeclaration vd = new VertexDeclaration(m_device, elements);
            m_device.VertexDeclaration = vd;

            var vb = new VertexBuffer(this.m_device, 3 * SizeOf<CustomVertex>(), Usage.Points,
                                                         VertexFormat.PositionRhw | VertexFormat.Diffuse, Pool.Default);

            var ds = vb.Lock(0, 3 * SizeOf<CustomVertex>(), LockFlags.None);
            ds.Write(new CustomVertex(0.0f, 0.5f, 0.5f,0.3f));
            ds.Write(new CustomVertex(0.5f, -0.5f, 0.5f,0.2f));
            ds.Write(new CustomVertex(-0.5f, -0.5f, 0.5f,0.1f));
            ds.Position = 0;
            vb.Unlock();

            this.m_device.BeginScene();
            this.m_device.SetStreamSource(0, vb, 0, 3 * SizeOf<CustomVertex>());
            this.m_device.DrawPrimitives(SlimDX.Direct3D9.PrimitiveType.TriangleStrip, 0, 2);
            this.m_device.EndScene();
            this.m_device.Present();

```

The `CustomVertex` struct is defined as below:

```
 internal struct CustomVertex
    {
        public float x, y, z;
        public float color;

        public CustomVertex(float x,float y,float z,float color)
        {
            this.x = x;
            this.y = y;
            this.z = z;
            this.color = color;
        }
    };

```

The function `SizeOf` defined as below:

```
public static int SizeOf<T>()
{
    return System.Runtime.InteropServices.Marshal.SizeOf(typeof(T));
}

```

I am trying to display a simple triangle by using code above, without luck, only a black screen pops up. What am I doing wrong?

# Answer
> 3 votes
You've got quite a few problems here.

First, the `DeclarationUsage` enumeration maps to `D3DDECLUSAGE` under the hood; these values are not flags, so or'ing them together doesn't make sense. When you create the vertex element array for a vertex declaration, each vertex attribute (position, color, et cetera) must be its own element. Thus, you should initialize `elements` like this:

```
var elements = new [] {
  new VertexElement(0, 0, DeclarationType.Float3, DeclarationMethod.Default, DeclarationUsage.Position, 0),
  new VertexElement(0, 3 * sizeof(float), DeclarationType.Color, DeclarationMethod.Default, DeclarationUsage.Color, 0),
  VertexElement.VertexDeclarationEnd
};

```

Position and color are each given their own vertex element, and (importantly) the color element specifies an offset of `3 * sizeof(float)` since the position element consists of three floats.

Second, you need to make sure your actual vertex data (and thus the vertex structure) matches this declaration. Your current structure has three floats for the X, Y and Z component of position... but only a single float for color. Color is generally a three or four component float (or a 32-bit integer). In the above example, I changed your declaration use `DeclarationType.Color`, which is the 32-bit integer version where each RGBA color component is packed into a particular byte of the integer. Thus, your vertex structure should become:

```
internal struct CustomVertex
{
    public float x, y, z;
    public int color;

    public CustomVertex(float x, float y, float z, int color)
    {
        this.x = x;
        this.y = y;
        this.z = z;
        this.color = color;
    }
};

```

You will obviously have to change how you fill the vertex buffer (write into the data stream) as well to account for this, or you'll continue to get black screens / garbage because the buffer is misaligned relative to the declaration.

Third, you're also specifying a FVF code to the vertex buffer when you create it; since you're using vertex declarations, you don't need to do that (especially since your FVF code does not match your declaration, either). Instead pass `VertexFormat.None`; you already set the vertex declaration.

Fourth, you specify a usage value of "points" but then try to render a triangle strip. For simplicity, you probably want to put your buffer in the managed pool so you don't have to recreate it when you lose the device. Your buffer creation code can look like this:

```
var vb = new VertexBuffer(m_device, 3 * SizeOf<CustomVertex>(), Usage.None, VertexFormat.None, Pool.Managed);

```

You can also render your scene as a simple triangle list, since you only have one triangle:

```
m_device.DrawPrimitives(SlimDX.Direct3D9.PrimitiveType.TriangleList, 0, 1);

```

Finally, this code looks to all be in a single function. That means you're likely re-creating your resources every frame (bad) or only drawing once (also bad) depending on where the code is located.

I **strongly** suggest that you take a look at the SlimDX MiniTri sample for D3D9, which demonstrates a very simple, straightforward way to render a triangle in just about as few lines of code as possible.

---
Tags: c#, directx, slimdx
---


# Question
Title: (XNA) Stretching Images (Sprites) without Blur (Rasterizing?)
thanks for clicking on this question although it has likely one of the most un-specific and confusing titles on this site. I am somewhat new to XNA and I have only posted 1 question on this site before which I didn't understand the answer to fully, but I'll give it another go.

I am looking to create a game which allows the user to either go full-screen or re-size the window to a few preset values, like many mainstream games nowadays allow you to do. I believe I know how to do this in XNA, the problem is, when I toggle full-screen, and it stretches the sprites, they appear blurry.

I know this is a very obvious problem, as stretching = blur (logically). The thing is, I was wondering if there was a way to make it so regardless of the zoom, your sprites look crisp and not blurry? I asked a friend of mine in real life and he said something about rasterizing (which i don't know anything about). The only other thing I can think of

I've seen this done a few times in Flash. For examples of what I mean the only game I can think of is Super Smash Flash 2. It seems regardless of the screen size, most of the sprites and images appear crisp, even on the largest of screens.

If anybody knows anything about this, please share! -Thanks.

# Answer
How do I disable texture filtering for sprite scaling in XNA 4.0?

This looks like it might be a solution for you. It seems the textures are being sample in such a way that when one pixel on the screen lies between two texture pixels, it's interpolating the colours. You can change it so it uses the closest pixel colour instead. This will look blocky, but less blurry.

http://gregs-blog.com/2008/01/14/how-to-turn-off-bilinear-filtering-in-opengl/

This gives a good explanation of what's going on. It's OpenGL, but the important part is the concept of the texture filtering.
> 1 votes

---
Tags: xna, screen, rasterization
---


# Question
Title: How do I find the angle between two 3D angles represented in this form?
I have two 3D angles, represented by \[a1,a2\] \[a1,a2\] where the a2 is \< 180. My coordinates are represented as \[X,Y,Z\], where X,Y,Z are 64 bit ints (longs in my lang). My direction angles are represented as (Angle1, Angle2) where Angle1 is 360 degrees along the X/Y plane, and Angle2 is 180 degrees along the Z axis.

In this case, I know for a fact that both angles were calculated from a single starting point, so there should be a single angle between them. However, the math eludes me. I sure would appreciate some help.

I've read the stuff on calculating the angle between two vectors, which is great, but for me would involve multiplying two longs together, which is 1. not practical, and 2. shouldn't be necessary.

My goal is to determine whether obj1 is moving generally towards obj2. One of the angles is the direction of movement of obj1, and the other is the direction from obj1 to obj2. Can I get there from here?

# Answer
> 2 votes
A possible solution is to use the Dot Product. Of course, you need two vectors and not two angles, but I guess you're using them (otherwise I wouldn't explain how you're having 3D angles).

Quoting Van Verth & Bishop from the book *Essential Mathematics for Games & Interactive Applications*, page 30-31:

> A more common use of the dot product is to test the angle between two vectors. If **v·w** \> 0, then we know the angle is less than 90 degrees. If **v·w** \< 0, then we know the angle is greater than 90 degrees, and if **v·w** = 0, then the angle is exactly 90 degrees. \[...\]
>
> For example, suppose that we have an AI agent that is looking for enemy agents in the game. The AI has a view vector **v** and a vector **t** which points toward an object in our scene. If **v·t** \< 0, then the object is behind us and therefore not visible \[...\]

That could solve your current problem because outside that range, your objects probably won't collide, but you also need to consider the distance between them for that statement to be true.

---
Tags: collision-detection, 3d, vector, angles
---


title: Plot HDR tonemap curves

text:
# Question
Title: Plot HDR tonemap curves
I am using a tonemapper in our project and a friend of mine asked if I could provide him with a plot of the tonemapper used (different functions are implemented). I tried in MATLAB to copy the tone-mapper function and use luma values from -5 to 5.0 to feed to the function, but the resulting plot is nothing like a classic tonemap function plot as I happen to see around. The function is totally correct, but am I missing something stupid that must be taken into account when trying to plot them?

# Answer
> 1 votes
Luma values should always be positive. You might be confusing it with log-luminance. A lot of these plots are shown with a log scale for the x axis. On a log scale you can see the characteristic "S curve", while on a scale whose x axis is linear luminance, it doesn't look like an S.

For example, my favorite tone curve is Jim Hejl's curve as reported by John Hable, used in Infamous Second Son and probably other games. Here's what the curve looks like in linear space (i.e. just graphing the equation on that slide):

Here's what it looks like if I convert the x-axis to a log scale (in other words, replace x by 2^x in the equation, so that x is now the log2 of luminance):

Now that looks more like the S-curve that I guess you were probably looking for. Here are the equations on Desmos if you want to play around with them.

---
Tags: hdr
---


# Question
Title: Marching cubes over an octree dual - how?
In Dual Marching Cubes the dual of an octree is tessellated via the standard marching cubes method. But the classical marching cubes algorithm operates only on cubes with eight vertices (it uses signs at eight corners of the cube to construct a bitmask and select the proper configuration of triangles), while cells of octree duals can actually have more than eight edges.

For example, in the following picture a quadtree dual is shown, where the lower left cell has 8 links to neighboring dual vertices:

although the marching squares algorithm needs only 4 corner vertices (4-bit masks - 16 cases) for contouring the grid.

And how to build the surface in this case? Which edges to select to form a bitmask used in the marching cubes/squares algorithm as the algorithm needs only 8/4 points as input?

# Answer
The thick black lines in the picture aren't an illustration of the connectivity of the dual grid: Those lines *are the dual grid itself*. The light blue lines show the squares of the quadtree but its not the quadtree that's marching.

The lower left cell of the dual grid is a square. All the other cells in it are either square, some other quad or a "degenerate quad" where some vertices are shared i.e. they're triangles. These are the cells that the original algorithm gets run on to generate the surface.

Back in 3 dimensions every cell would be a possibly degenerate cuboid.

It should be noted though that in the full algorithm the vertices of the dual grid aren't always placed in the centres of the original cells. Instead they are placed wherever in their cell provides the best approximation to the desired implicit function. This is the "Feature Isolation" stage described in the paper.
> 5 votes

---
Tags: octree, marching-cubes
---


title: Okami Drawing Mechanic in Monogame

text:
# Question
Title: Okami Drawing Mechanic in Monogame
I was wondering what would be the best way to go about using the drawing mechanic of Okami in my own game. Basically I want to be able to track joystick movement in a closed region, and have it appear on the screen like Okami.

# Answer
Three steps:

1. Have an array of positions.
2. Each frame, read the joystick's position and write it into the array, after the position from the previous frame.
3. Each frame, draw lines between the positions you recorded in the array.
> 0 votes

---
Tags: joystick, hand-drawn
---


# Question
Title: glDrawElements vs glDrawArrays for polygons that do not reuse vertices
Is it better to use `glDrawElements` or `glDrawArrays` when **not** reusing vertices? There must be some difference, otherwise people would always use `glDrawElements`?

I suppose the question could be reworded as the following:

Does `glDrawElements` function the same as `glDrawArrays` if it is passed a blank indices table?

# Answer
`glDrawElements()` doesn't support a "blank indices table". `glDrawElements()` must always be given explicit data about in what order vertex indices are to be drawn, either using a pointer to a memory buffer (OpenGL \<= 2.1 only), or an offset into a bound VBO.

`glDrawArrays()` acts like `glDrawElements()` would if it had been given an array of values \[0, 1, 2, ... , n\], where 'n' is the `count` value passed into either function.

In theory, `glDrawArrays()` requires less data than `glDrawElements()` (in that the order of indices is implicit, instead of requiring a block of data to be transferred to the GPU), and so it should be marginally faster if your data is in that format. But in practice, the difference is unlikely to be worth worrying about.
> 7 votes

---
Tags: opengl, performance
---


# Question
Title: Slow uniform array in shader causing FPS drop
I'm trying to use an uniform array of matrices in my compute shader. However, it's really slow. I've narrowed it down to this lines of code:

```
uniform mat4 someMatrixArray[64];
...
vec4 result = vec4(0);
for (int i = 0; i < 2048; i++) {
    result += someMatrixArray[i%64][0] * 0.01;
}

```

When not accessing someMatrixArray I get 700+ fps. When accessing it, I have 10 fps. Anybody has an idea what could cause this? Could it be a driver issue?

I already tried to unroll the loops (via `#pragma optionNV (unroll all)`) but that didn't help. I'm using a GTX670 with the latest drivers on windows 7.

**Edit:**

The generated assembly for the inner loop is:

```
MAD.F R0.xyz, c[196], {0.0099999998, 0, 0, 0}.x, R0;

```

# Answer
> 1 votes
Yes, accessing memory can always be substantially slower than not accessing memory. Particularly in a for loop that's executing 2000 times inside a shader.

I don't think there's anything particularly surprising, here -- breaking the task up into smaller steps that can each be executed in parallel and using smaller amounts of data should definitely help.

---
Tags: opengl, shaders, performance
---


# Question
Title: Is a dynamic enviroment map using pincushion curvilinear perspective projection possible?
I'm wondering if it is possible to generate a dynamic spherical environment map using a single frame render using a pincushion curvilinear perspective projection matrix (phew, that's a mouthful)?

I've been researching this for a few days now and the closest thing I can find is a curvilinear perspective but it isn't a commonly used projection matrix so there isn't any help I was easily able to find and I still don't know if it supports a full circle FOV.

**Why?**

The standard perspective matrix but it begins to look very strange and distorted above 180 degrees vertical FOV and completely fails to render when approaching 360 degrees. So instead most games render the scene six times using 90 degree FOV facing the faces of a cube.

Rendering the scene 6 times seems like a waste if it might be possible to simply imagine a camera that has a 360 degree view across both axis and then render that to a spherical environment map.

# Answer
> 8 votes
In practice, even when a scene is built to minimise problems, a 360-degree-FOV camera tends to introduce so much distortion in some directions that its results are useless for most purposes.

If you want to avoid the expense of rendering a full texture cube, you can get a similar effect by using dual paraboloid environment maps, in which you render two parabolic views of the scene, and then use those two resulting images as your environment map, instead of using a texture cube's six maps.

# Answer
> 5 votes
The short answer is: yes, it is possible, but since the projection you desire is nonlinear, you must do one of two things:

* Subdivide the geometry finely and implement the projection math in the vertex shader (or domain shader if using hardware tessellation), or
* Render a standard environment map (e.g. cubemap) first and then resample it to the desired projection using a post-processing pass.

For more details you can see my answer to this related question, where I've talked about this at greater length.

The takeaway, though, is that rendering with a nonlinear projection generally requires you to do some sort of extra work and isn't terribly likely to be an optimization over simply rendering a cubemap, despite the fact that you then have to draw the scene six times (or, perhaps better, use a geometry shader to replicate primitives to all cube faces).

---
Tags: matrix, projection, cubemap
---


# Question
Title: Warp GameObject Size When Entering/Leaving Area
Below I have an image describing the desired functionality I am going for. Let's say you control a square and when you move this square into a given area, any part of your rigidbody/model inside of the area will be magnified upon entering and shrunk upon leaving. So now you more or less are made up of two rectangles, one small and one large.

What would be an elegant approach towards achieving this effect?

# Answer
> 1 votes
You can't do that with physics very easily (if at all).

A much simpler solution would be to use a second camera and calculate the viewport. The psuedocode would be something like:

```
if(magnificationCameraGO.IsVisible)
    magnificationCamera.enable;
    magnificationCamera.pixelRect.x = ConvertGameObjectPositionToCameraPosition(magnificationCameraGO.position.x)

```

You'd place the magnification camera on a gameobject, and position that gameobject where you want the magnification to appear

---
Tags: 2d, unity, rigid-body-dynamics, intersection, masking
---


title: XBox controller in while loop

text:
# Question
Title: XBox controller in while loop
I have a while loop that goes for ever. The goal is if I press `A` button, a message should be printed out showing this button has been pressed `A has been pressed`. I've done the loop and connecting XBox controller but the problem is that the message is printed out many times if I press the button one time. My question is why the message is being shown many times while I just press the button one time? Should I make some kind of sleep?

---

Edit: This is the part of the code

```
while(true)
    {
        if(Player->IsConnected())
        {
            if( Player->GetState().Gamepad.wButtons & XINPUT_GAMEPAD_A )
                std::cout << " A button has been pressed ..." << std::endl;
        }
        else
        {
            std::cout << "\nERROR: Connect XBox Controller ... \n";
            std::cout << "Press Any Key To Exit.";
            std::cin.get();
            break;
        }
    }

```

The result when I only press once.

```
Press A to be printed out ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...
 A button has been pressed ...

```

# Answer
> 3 votes
The reason, why the message is printed several times, is, due to the fact, that you read the state of the button every loop. *Player-\>GetState().Gamepad.wButtons* gives you the current state of the buttons. That means, as long as a button is pressed, requesting the state and checking for that button will be true.

What you can do, is, declare a boolean variable on top of the loop, that saves the state of a specified button of the last update.

This could look similar to this.

```
bool btnADown = false;

...

while(true)
{
    if(Player->IsConnected())
    {
        if( Player->GetState().Gamepad.wButtons & XINPUT_GAMEPAD_A )
        {
            if(!btnADown)
            {
                std::cout << " A button has been pressed ..." << std::endl;
                btnADown = true;
            }
        }
        else
        {
            btnADown = false;
        }
    }
    else
    {
        std::cout << "\nERROR: Connect XBox Controller ... \n";
        std::cout << "Press Any Key To Exit.";
        std::cin.get();
        break;
    }
}

```

---
Tags: xbox360
---


# Question
Title: Measuring enemy "success" against player
I've been toying with an idea for a game prototype where the player must defend against waves of enemies, but between each wave the enemies "evolve" to better combat whatever tactics the player is using. Essentially each enemy type has some genetic information that can be used to generate their health, speed, attack type and so on; with the more "successful" enemy types being mutated into new sub-types, while ineffective enemy types are phased out.

What I'm trying to figure out, is *what is a good way of measuring "success" against the player?*

EDIT: Although I don't really want to get too specific about the game mechanics, let's assume that the game world is complex enough that you cannot figure out if an enemy type will be effective against the player without testing it.

So far I've thought of two basic solutions:

* Use heuristics like whether a certain enemy deals damage to the player or survives a long time without being killed.

The problem I have with this approach is that it can be exploited if (when) the player figures out how the algorithm works. For example you would be able to deliberately let the weakest enemies land a few free hits to trick the game into creating more of them. It may be possible to improve this with better heuristics however.
* Only use about half the pool of enemy types at once and swap types in and out randomly between waves. Analysis could then be performed on the player's performance throughout the wave and each participating enemy type would be considered equally successful/unsuccessful. After a number of waves the success of enemy types would be varied enough to perform mutation/deletion.

This solution seems intuitively harder to exploit and it would also pick up on successful combinations of enemy types that might not be possible to detect by looking at individuals, however it might also result in anomalies where useless enemy types are considered successful because they happened to get assigned to waves with stronger enemy types backing them up.

To clarify, I'm not asking about the actual process of evolving enemies, just about how to measure which enemies are successful against the player.

# Answer
I'm wondering whether you could simplify the matter by focusing on how the player fights:

If you have a range of weapons, that effectively provide different ways of fighting, then you can have set classification variables that iterate on use. Think of it as elements and then element resistances for the creatures.

As an example:

You have a range of weapons and whenever the player uses a weapon the variable for that weapon iterates up.

Whenever the game generates a new wave it looks for the top *x* variables and sends creatures with attributes that make them good against the player's favourite weapons.

-The player uses flame weapons a lot so when the game generates it's next wave it sends a swarm of creatures with flame proof skin.-
> 1 votes

# Answer
I would measuring the success of an enemy against the player by a costs vs. damage relation.

You have some costs for "producing" the enemy unit (e.g. money, time, other resources). Your unit causes damage to the player in form of resources (e.g. needs to use medikit for healing, kills some of his units \[costs for replacing them\], ..). The same calculation can be done for e.g. destroyed harvesters, as the player gains less resources of some type for a given period.

So, track what kind of costs you had to producing the unit and to finally cause the damage (=time) and track which kind of damage you did and what a 1:1 replacement costs. Then you can calculate the efficiency for each ressource:

```
efficiency(resource) = damage_costs(resource) / own_costs(resource)

```

Replacement costs can vary with time, as your player maybe improves some building and is able to produce units faster for less money. So you should recalculate the efficiency during the game regularly based on current courses.

Defeating the player means driving some or all of the resources of the player down to zero. Which in the end means that he can not produce some or any new units.

So even a harvester working near to the player can cause damage to him, as it is harvesting his resources, which in the end isn't available to the player anymore. So the player must e.g. invest more time to gain such resources.
> 1 votes

# Answer
This is a good concept that is not in enough games. The best way to implement this would be to use both of your strategies. Concerning your first strategy I wouldn't be too worried about a player exploiting it because if they let an enemy damage them then they still took damage so they can't do that exploit forever. I still think your second strategy concerning multiple enemies in conjunction is important I'll give the following example. If you have a large "tank" enemy with low DPS and a sniper enemy that hides behind with high DPS the two of them could be a big problem where separately they were weak.

**Suggested Improvements for Strat 1** Ways to improve this could be to rank the various heuristics the damage an enemy does is ranked higher than enemy lifetime.

More heuristic ideas for you assuming some type of shooter 1st person, 3rd person or top down. Other heuristics could be ammo user fires at said enemy (hard to track). User movement while fighting an enemy (measure if they are working harder/dodging more against this enemy type).

**Suggested Improvements for Strat 2** I would suggest something like swapping out one enemy per level (evolution cycle) and keeping them in reserve, measuring that wave and determining if it did better or worse without that enemy. Cycle out other enemy types next round and measure again.
> 0 votes

# Answer
Before I would try solving the problem, I would first create a mock setup (with random enemies) and log the data (enemy health over time, other stats, etc...) Then, I would see if there is a pattern that matches up with enemies the player perceived as "tough" and try to replicate that.

I'd imagine that a successful enemy would be one that the player would react to more. As in, one that the player tries to stay away from, rush to for a quick kill to get it out of the way, focuses fire on, one that elicits the most response from the player. Maybe that's too hard to implement, though.

I hope this helps somewhat!
> 0 votes

---
Tags: ai, difficulty, evolution, dynamic-difficulty, heuristics
---


# Question
Title: Can I export animated models from Unity? Into what formats?
I have an animated 3D model from the Unity Asset Store that I would like a new animator to touch up (the license allows this). But they need it in a format they can use (in Maya or... something else?). All I have been able to find so far is:

* how to export from the Editor into Unity Package format
* scripts to export the mesh (only?) into OBJ format \[1\]

Is it possible to export a textured and rigged model from Unity? If so, into what formats and how?

\[1\] ObjExporter and ExportOBJ

# Answer
> 0 votes
Unity does not provide an export option for additional modelling. However, it does provide the option to export an animated model (and other things) into `.unitypackage` format using *Assets* \> *Export package...*

(As far as I can tell this includes the FBX files you can find in the project folder.)

In my case this was sufficient for the artist to inspect the model and animation visually in Unity, and the texture files directly. In the end, rather than adjusting the animation we used it as a reference.

---
Tags: unity, 3d, animation, models, export
---


# Question
Title: How can I keep chase camera behind player when player rotates?
I have implemented a follow camera in Unity 3D. However, if the player object rotates, the camera does not rotate with it. To fix this I used RotateAround as follows:

```
playerRotation = CastPositive(player.EulerAngles.y) //guarantees 0-360
cameraRotation = CastPositive(transform.EulerAngles.y)
difference = playerRotation - cameraRotation
transform.RotateAround(player.position, Vector3.up, difference * time.deltaTime)

```

This works in general. However at some point the difference snaps from -50 to 210. When this happens, the camera swings in the opposite direction all the way round the player object, instead of continuing on its orbit.

How can I avoid this value jump?

* I've tried clamping the various values to no avail, but maybe I've missed something?
* Quaternions?

# Answer
> 0 votes
Code provided by Katherine Rix:

```
// Position camera to follow behind player's head.
private void Follow(){

    // orientation as an angle when projected onto the XZ plane
    // this functionality is modularise into a separate method because
    // I use it elsewhere
    float playerAngle = AngleOnXZPlane (player);
    float cameraAngle = AngleOnXZPlane (transform);

    // difference in orientations
    float rotationDiff = Mathf.DeltaAngle(cameraAngle, playerAngle);

    // rotate around target by time-sensitive difference between these angles
    transform.RotateAround(GetTarget(), Vector3.up, rotationDiff * Time.deltaTime);
}

// Find the angle made when projecting the rotation onto the xz plane.
// You could pass in the rotation as a parameter instead of the transform.
private float AngleOnXZPlane(Transform item){

    // get rotation as vector (relative to parent)
    Vector3 direction = item.rotation * item.parent.forward;

    // return angle in degrees when projected onto xz plane
    return Mathf.Atan2(direction.x, direction.z) * Mathf.Rad2Deg;
}

```

# Answer
> 3 votes
I don't know which is the specific error in your case, but at least from my experience, I'd use quaternion instead. You can just lerp between your current camera rotation and the desired one. Something like:

```
transform.rotation = Quaternion.Lerp(transform.rotation, player.transform.rotation,Time.deltaTime * speed);

```

In general quaternions offer a simple and natural way to interpolate rotations, preventing problems like gimbal lock.

---
Tags: c#, unity, camera
---