SceneGraph Interviewee Task, C#

SceneGraph Interviewee Task

using System;
using System.Collections.Generic;

// In this test, a typical scene graph is given.
// The scene graph contains a game object and a bounding box.
// The game object is the root of a hierarchy.
// Every game object can have an arbitrary number of game objects as its children
// while every child also has a reference to its parent (except for the root which does not have a parent).
// The classes for the bounding box, the scene graph and the game objects can all be found in the file GameObject.cs
// Every game object contains vertices in a list.
// Furthermore, every game object has a matrix which transforms it relative to the parent.

// Two simple classes for vectors and matrices are also given.
// Examples of how to use them are shown in the main function

// Task 1: Write a function that takes a game object and computes its AABB. 
// The AABB is based on the vertices which have to be transformed by the game object's transform.
// The game object already has a m_BoundingBox member where the AABB shall be stored.

// Task 2: Compute the AABB for the whole scene graph that is created in the first line of the main function.
// The scene graph also containts a m_BoundingBox member to store it.
// The AABB has to enclose all children (with their vertices) in the hierarchy.
// The function from Task 1 can be used here.

//------------------------------------------------------------------------------------
// Math helpers (not relevant for test)
//------------------------------------------------------------------------------------

public class Vector4
{
    public float x = 0.0f, y = 0.0f, z = 0.0f, w = 1.0f;

public Vector4() { }

public Vector4(Vector4 other)
    {
        this.x = other.x;
        this.y = other.y;
        this.z = other.z;
        this.w = other.w;
    }

public Vector4(float x, float y, float z)
    {
        this.x = x;
        this.y = y;
        this.z = z;
        this.w = 1.0f;
    }

public Vector4(float x, float y, float z, float w)
    {
        this.x = x;
        this.y = y;
        this.z = z;
        this.w = w;
    }

public float this[int i]
    {
        get
        {
            switch (i)
            {
                case 0:
                    return x;
                case 1:
                    return y;
                case 2:
                    return z;
                default:
                    return w;
            }
        }

set
        {
            switch (i)
            {
                case 0:
                    x = value;
                    break;
                case 1:
                    y = value;
                    break;
                case 2:
                    z = value;
                    break;
                default:
                    w = value;
                    break;
            }
        }
    }

public static float Dot(Vector4 left, Vector4 right)
    {
        return left.x * right.x + left.y * right.y + left.z * right.z + left.w * right.w;
    }
}

public class Matrix4x4
{
    public Vector4[] columns;

public Vector4 this[int i]
    {
        get { return columns[i]; }
        set { columns[i] = new Vector4(value); }
    }

public static Matrix4x4 operator *(Matrix4x4 left, Matrix4x4 right)
    {
        Matrix4x4 result = new Matrix4x4();

result.columns[0][0] = Vector4.Dot(new Vector4(left.columns[0][0], left.columns[1][0], left.columns[2][0], left.columns[3][0]), right.columns[0]);
        result.columns[0][1] = Vector4.Dot(new Vector4(left.columns[0][1], left.columns[1][1], left.columns[2][1], left.columns[3][1]), right.columns[0]);
        result.columns[0][2] = Vector4.Dot(new Vector4(left.columns[0][2], left.columns[1][2], left.columns[2][2], left.columns[3][2]), right.columns[0]);
        result.columns[0][3] = Vector4.Dot(new Vector4(left.columns[0][3], left.columns[1][3], left.columns[2][3], left.columns[3][3]), right.columns[0]);

result.columns[1][0] = Vector4.Dot(new Vector4(left.columns[0][0], left.columns[1][0], left.columns[2][0], left.columns[3][0]), right.columns[1]);
        result.columns[1][1] = Vector4.Dot(new Vector4(left.columns[0][1], left.columns[1][1], left.columns[2][1], left.columns[3][1]), right.columns[1]);
        result.columns[1][2] = Vector4.Dot(new Vector4(left.columns[0][2], left.columns[1][2], left.columns[2][2], left.columns[3][2]), right.columns[1]);
        result.columns[1][3] = Vector4.Dot(new Vector4(left.columns[0][3], left.columns[1][3], left.columns[2][3], left.columns[3][3]), right.columns[1]);

result.columns[2][0] = Vector4.Dot(new Vector4(left.columns[0][0], left.columns[1][0], left.columns[2][0], left.columns[3][0]), right.columns[2]);
        result.columns[2][1] = Vector4.Dot(new Vector4(left.columns[0][1], left.columns[1][1], left.columns[2][1], left.columns[3][1]), right.columns[2]);
        result.columns[2][2] = Vector4.Dot(new Vector4(left.columns[0][2], left.columns[1][2], left.columns[2][2], left.columns[3][2]), right.columns[2]);
        result.columns[2][3] = Vector4.Dot(new Vector4(left.columns[0][3], left.columns[1][3], left.columns[2][3], left.columns[3][3]), right.columns[2]);

result.columns[3][0] = Vector4.Dot(new Vector4(left.columns[0][0], left.columns[1][0], left.columns[2][0], left.columns[3][0]), right.columns[3]);
        result.columns[3][1] = Vector4.Dot(new Vector4(left.columns[0][1], left.columns[1][1], left.columns[2][1], left.columns[3][1]), right.columns[3]);
        result.columns[3][2] = Vector4.Dot(new Vector4(left.columns[0][2], left.columns[1][2], left.columns[2][2], left.columns[3][2]), right.columns[3]);
        result.columns[3][3] = Vector4.Dot(new Vector4(left.columns[0][3], left.columns[1][3], left.columns[2][3], left.columns[3][3]), right.columns[3]);

return result;
    }

public static Vector4 operator *(Matrix4x4 matrix, Vector4 vector)
    {
        Vector4 result = new Vector4();

for (int row = 0; row < 4; ++row)
        {
            result[row] = matrix[0][row] * vector[0] + matrix[1][row] * vector[1] + matrix[2][row] * vector[2] + matrix[3][row] * vector[3];
        }

return result;
    }

public Matrix4x4()
    {
        columns = new Vector4[4];

for (int i = 0; i < 4; ++i)
        {
            columns[i] = new Vector4(0.0f, 0.0f, 0.0f, 0.0f);
        }

for (int i = 0; i < 4; ++i)
        {
            this[i][i] = 1.0f;
        }
    }

public Matrix4x4(float m00, float m10, float m20, float m30,
        float m01, float m11, float m21, float m31,
        float m02, float m12, float m22, float m32,
        float m03, float m13, float m23, float m33)
        : this()
    {
        columns[0][0] = m00;
        columns[0][1] = m01;
        columns[0][2] = m02;
        columns[0][3] = m03;

columns[1][0] = m10;
        columns[1][1] = m11;
        columns[1][2] = m12;
        columns[1][3] = m13;

columns[2][0] = m20;
        columns[2][1] = m21;
        columns[2][2] = m22;
        columns[2][3] = m23;

columns[3][0] = m30;
        columns[3][1] = m31;
        columns[3][2] = m32;
        columns[3][3] = m33;
    }
}

//------------------------------------------------------------------------------------
// These classes are relevant for the test
//------------------------------------------------------------------------------------

public class CAABB
{
    public float minX, maxX;
    public float minY, maxY;
    public float minZ, maxZ;
}

public class CGameObject
{
    public Matrix4x4 m_Transform;
    public CGameObject m_Parent;
    public List<CGameObject> m_Children;

public List<Vector4> m_Vertices;

public CAABB m_BoundingBox;

public CGameObject()
    {
        m_Children = new List<CGameObject>();
        m_Vertices = new List<Vector4>();
    }
}

public class CSceneGraph
{
    public CGameObject m_Root;
    public CAABB m_BoundingBox;

public CSceneGraph()
    {
		m_BoundingBox = new CAABB();
        BuildSceneGraph();
    }

//------------------------------------------------------------------------------------
    // Build the scene graph (not relevant for test)
    //------------------------------------------------------------------------------------

private void BuildSceneGraph()
    {
        // Root

var Root = new CGameObject();

Root.m_Transform = new Matrix4x4(
            1.0f, 0.0f, 0.0f, -5.0f,
            0.0f, 1.0f, 0.0f, 10.0f,
            0.0f, 0.0f, 1.0f, 10.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Root.m_Vertices.Add(new Vector4(1.0f, 1.0f, 1.0f));
        Root.m_Vertices.Add(new Vector4(0.0f, 0.0f, 0.0f));
        Root.m_Vertices.Add(new Vector4(1.0f, -1.0f, 1.0f));

// Level1

var Level1_1 = new CGameObject();

Level1_1.m_Transform = new Matrix4x4(
            1.0f, 0.0f, 0.0f, 3.0f,
            0.0f, 1.0f, 0.0f, 1.0f,
            0.0f, 0.0f, 1.0f, 5.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Level1_1.m_Vertices.Add(new Vector4(-1.0f, -1.0f, -1.0f));
        Level1_1.m_Vertices.Add(new Vector4(0.0f, 0.0f, 0.0f));
        Level1_1.m_Vertices.Add(new Vector4(1.0f, -1.0f, 1.0f));

var Level1_2 = new CGameObject();

Level1_2.m_Transform = new Matrix4x4(
            1.0f, 0.0f, 0.0f, -8.5f,
            0.0f, 1.0f, 0.0f, 10.0f,
            0.0f, 0.0f, 1.0f, -3.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Level1_2.m_Vertices.Add(new Vector4(0.5f, 2.0f, 3.0f));
        Level1_2.m_Vertices.Add(new Vector4(2.0f, 2.0f, 2.0f));
        Level1_2.m_Vertices.Add(new Vector4(0.5f, 0.5f, 0.5f));

// Level2

var Level2_1 = new CGameObject();

Level2_1.m_Transform = new Matrix4x4(
            0.5f, 0.0f, 0.0f, 4.5f,
            0.0f, 0.5f, 0.0f, -1.5f,
            0.0f, 0.0f, 0.5f, -2.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Level2_1.m_Vertices.Add(new Vector4(3.0f, 2.0f, 1.0f));
        Level2_1.m_Vertices.Add(new Vector4(-1.0f, 0.0f, 0.0f));
        Level2_1.m_Vertices.Add(new Vector4(1.5f, 0.5f, 2.5f));

var Level2_2 = new CGameObject();

Level2_2.m_Transform = new Matrix4x4(
            1.0f, 0.0f, 0.0f, 0.0f,
            0.0f, 1.0f, 0.0f, 5.0f,
            0.0f, 0.0f, 1.0f, -8.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Level2_2.m_Vertices.Add(new Vector4(-2.0f, -2.0f, -2.0f));
        Level2_2.m_Vertices.Add(new Vector4(0.0f, 0.0f, 0.0f));
        Level2_2.m_Vertices.Add(new Vector4(-1.0f, -1.0f, -1.0f));

var Level2_3 = new CGameObject();

Level2_3.m_Transform = new Matrix4x4(
            1.0f, 0.0f, 0.0f, -10.0f,
            0.0f, 1.0f, 0.0f, -2.0f,
            0.0f, 0.0f, 1.0f, -4.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Level2_3.m_Vertices.Add(new Vector4(2.0f, 2.0f, 2.0f));
        Level2_3.m_Vertices.Add(new Vector4(1.0f, 1.0f, 1.0f));
        Level2_3.m_Vertices.Add(new Vector4(0.0f, 0.0f, 0.0f));

// Level3

var Level3_1 = new CGameObject();

Level3_1.m_Transform = new Matrix4x4(
            1.0f, 0.0f, 0.0f, 10.0f,
            0.0f, 1.0f, 0.0f, 2.5f,
            0.0f, 0.0f, 1.0f, -8.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Level3_1.m_Vertices.Add(new Vector4(3.0f, 0.5f, 2.0f));
        Level3_1.m_Vertices.Add(new Vector4(-0.5f, -1.0f, -2.0f));
        Level3_1.m_Vertices.Add(new Vector4(3.5f, 1.0f, 0.0f));

var Level3_2 = new CGameObject();

Level3_2.m_Transform = new Matrix4x4(
            0.2f, 0.0f, 0.0f, 1.0f,
            0.0f, 0.2f, 0.0f, 0.0f,
            0.0f, 0.0f, 0.2f, 3.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Level3_2.m_Vertices.Add(new Vector4(2.0f, 1.5f, -0.5f));
        Level3_2.m_Vertices.Add(new Vector4(1.5f, -1.0f, 2.0f));
        Level3_2.m_Vertices.Add(new Vector4(0.5f, -1.0f, -3.0f));

var Level3_3 = new CGameObject();

Level3_3.m_Transform = new Matrix4x4(
            1.0f, 0.0f, 0.0f, 3.0f,
            0.0f, 1.0f, 0.0f, 1.5f,
            0.0f, 0.0f, 1.0f, -2.0f,
            0.0f, 0.0f, 0.0f, 1.0f
        );

Level3_3.m_Vertices.Add(new Vector4(-1.0f, 1.0f, 0.5f));
        Level3_3.m_Vertices.Add(new Vector4(0.5f, 2.0f, -2.0f));
        Level3_3.m_Vertices.Add(new Vector4(-1.5f, 0.0f, 1.5f));

//               Root
        //              /     \
        //             /       \
        //       Level1_1   Level1_2
        //           /  \           \
        //          /    \           \
        //    Level2_1   Level2_2    Level2_3
        //                  /   \          \
        //                 /     \          \
        //          Level3_1   Level3_2    Level3_3

ConnectNodes(Level2_2, Level3_1);
        ConnectNodes(Level2_2, Level3_2);
        ConnectNodes(Level2_3, Level3_3);

ConnectNodes(Level1_1, Level2_1);
        ConnectNodes(Level1_1, Level2_2);
        ConnectNodes(Level1_2, Level2_3);

ConnectNodes(Root, Level1_1);
        ConnectNodes(Root, Level1_2);

m_Root = Root;
    }

private void ConnectNodes(CGameObject Parent, CGameObject Child)
    {
        Parent.m_Children.Add(Child);
        Child.m_Parent = Parent;
    }
}

namespace Rextester
{
    public class Program
    {
        //------------------------------------------------------------------------------------
        // Write the functions here before the main function
        //------------------------------------------------------------------------------------
        
        public static void Main(string[] args)
        {
            var SceneGraph = new CSceneGraph();

// Call your functions here....

Console.WriteLine("Correct solution:");
            Console.WriteLine("minX: -23.5");
            Console.WriteLine("maxX: 11.5");
            Console.WriteLine("minY: 9");
            Console.WriteLine("maxY: 22");
            Console.WriteLine("minZ: -3");
            Console.WriteLine("maxZ: 16");

Console.WriteLine("Current solution:");
            Console.WriteLine("minX: " + SceneGraph.m_BoundingBox.minX);
            Console.WriteLine("maxX: " + SceneGraph.m_BoundingBox.maxX);
            Console.WriteLine("minY: " + SceneGraph.m_BoundingBox.minY);
            Console.WriteLine("maxY: " + SceneGraph.m_BoundingBox.maxY);
            Console.WriteLine("minZ: " + SceneGraph.m_BoundingBox.minZ);
            Console.WriteLine("maxZ: " + SceneGraph.m_BoundingBox.maxZ);
			
			// Example of vector/matrix calculation
			// Everything after this comment can be deleted

// A simple 4D vector representing homogeneous coordinates. w is automatically 1
			// Vector fields can be accessed in two ways:
			// v.x or v[0]

var V = new Vector4(10.0f, 10.0f, 10.0f);

// A matrix class
			// A constructor without parameters gives an identity matrix

// Example of a translation matrix
			var M1 = new Matrix4x4(
				1.0f, 0.0f, 0.0f, -50.0f,
				0.0f, 1.0f, 0.0f, 10.0f,
				0.0f, 0.0f, 1.0f, 100.0f,
				0.0f, 0.0f, 0.0f, 1.0f
			);

// Example of a scaling matrix
			var M2 = new Matrix4x4(
				0.5f, 0.0f, 0.0f, 0.0f,
				0.0f, 0.5f, 0.0f, 0.0f,
				0.0f, 0.0f, 0.5f, 0.0f,
				0.0f, 0.0f, 0.0f, 1.0f
			);

// Matrix multiplication is possible
			Matrix4x4 M3 = M1 * M2;

// Vectors can be transformed by matrices
			Vector4 Result = M3 * V;

Console.WriteLine(Result.x);
			Console.WriteLine(Result.y);
			Console.WriteLine(Result.z);
			Console.WriteLine(Result.w);
        }
    }
}


run \| edit \| history \| help	0