SceneGraph Interviewee Task, C++ (clang)

Language: Layout:

#include <iostream>
#include <vector>
#include <memory>

// 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 numer of game objects as its children
// while every child also has a pointer to its parent (except for the root which does not have a parent).
// The classes/structs for the bounding box, the scene graph and the game objects can all be found int the file game_object.h
// Every game object contains vertices in a vector.
// 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)
//------------------------------------------------------------------------------------

struct Vector4
{
    float x, y, z, w;

Vector4()
        : x(0.0f)
        , y(0.0f)
        , z(0.0f)
        , w(1.0f)
    {

}

Vector4(float x, float y, float z)
        : x(x)
        , y(y)
        , z(z)
        , w(1.0f)
    {

}

Vector4(float x, float y, float z, float w)
        : x(x)
        , y(y)
        , z(z)
        , w(w)
    {

}

float& operator[](int i)
    {
        return *(&x + i);
    }

const float& operator[](int i) const
    {
        return *(&x + i);
    }
};

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

struct Matrix4x4
{
    Vector4 columns[4];

float& operator()(int col, int row)
    {
        return columns[col][row];
    }

const float& operator()(int col, int row) const
    {
        return columns[col][row];
    }

Matrix4x4 operator*(const Matrix4x4& other) const
    {
        Matrix4x4 result;

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

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

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

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

return result;
    }

Matrix4x4()
    {
        for (int i = 0; i < 4; ++i)
        {
            operator()(i, i) = 1.0f;
        }
    }

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)
    {
        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;
    }
};

Vector4 operator*(const Matrix4x4& matrix, const Vector4& vector)
{
    Vector4 result;

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;
}

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

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

struct CGameObject
{
    Matrix4x4 m_Transform;
    CGameObject* m_pParent;
    std::vector<std::shared_ptr<CGameObject>> m_Children;

std::vector<Vector4> m_Vertices;

CAABB m_BoundingBox;
};

using CGameObjectPtr = std::shared_ptr<CGameObject>;

struct CSceneGraph
{
    CGameObjectPtr m_pRoot;
    CAABB m_BoundingBox;
};

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

inline void ConnectNodes(CGameObjectPtr pParent, CGameObjectPtr pChild)
{
    pParent->m_Children.push_back(pChild);
    pChild->m_pParent = pParent.get();
}

inline CSceneGraph BuildSceneGraph()
{
    // Root

auto pRoot = std::make_shared<CGameObject>();

pRoot->m_Transform = 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
    );

pRoot->m_Vertices.push_back(Vector4(1.0f, 1.0f, 1.0f));
    pRoot->m_Vertices.push_back(Vector4(0.0f, 0.0f, 0.0f));
    pRoot->m_Vertices.push_back(Vector4(1.0f, -1.0f, 1.0f));

// Level1

auto pLevel1_1 = std::make_shared<CGameObject>();

pLevel1_1->m_Transform = 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
    );

pLevel1_1->m_Vertices.push_back(Vector4(-1.0f, -1.0f, -1.0f));
    pLevel1_1->m_Vertices.push_back(Vector4(0.0f, 0.0f, 0.0f));
    pLevel1_1->m_Vertices.push_back(Vector4(1.0f, -1.0f, 1.0f));

auto pLevel1_2 = std::make_shared<CGameObject>();

pLevel1_2->m_Transform = 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
    );

pLevel1_2->m_Vertices.push_back(Vector4(0.5f, 2.0f, 3.0f));
    pLevel1_2->m_Vertices.push_back(Vector4(2.0f, 2.0f, 2.0f));
    pLevel1_2->m_Vertices.push_back(Vector4(0.5f, 0.5f, 0.5f));

// Level2

auto pLevel2_1 = std::make_shared<CGameObject>();

pLevel2_1->m_Transform = 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
    );

pLevel2_1->m_Vertices.push_back(Vector4(3.0f, 2.0f, 1.0f));
    pLevel2_1->m_Vertices.push_back(Vector4(-1.0f, 0.0f, 0.0f));
    pLevel2_1->m_Vertices.push_back(Vector4(1.5f, 0.5f, 2.5f));

auto pLevel2_2 = std::make_shared<CGameObject>();

pLevel2_2->m_Transform = 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
    );

pLevel2_2->m_Vertices.push_back(Vector4(-2.0f, -2.0f, -2.0f));
    pLevel2_2->m_Vertices.push_back(Vector4(0.0f, 0.0f, 0.0f));
    pLevel2_2->m_Vertices.push_back(Vector4(-1.0f, -1.0f, -1.0f));

auto pLevel2_3 = std::make_shared<CGameObject>();

pLevel2_3->m_Transform = 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
    );

pLevel2_3->m_Vertices.push_back(Vector4(2.0f, 2.0f, 2.0f));
    pLevel2_3->m_Vertices.push_back(Vector4(1.0f, 1.0f, 1.0f));
    pLevel2_3->m_Vertices.push_back(Vector4(0.0f, 0.0f, 0.0f));

// Level3

auto pLevel3_1 = std::make_shared<CGameObject>();

pLevel3_1->m_Transform = 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
    );

pLevel3_1->m_Vertices.push_back(Vector4(3.0f, 0.5f, 2.0f));
    pLevel3_1->m_Vertices.push_back(Vector4(-0.5f, -1.0f, -2.0f));
    pLevel3_1->m_Vertices.push_back(Vector4(3.5f, 1.0f, 0.0f));

auto pLevel3_2 = std::make_shared<CGameObject>();

pLevel3_2->m_Transform = 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
    );

pLevel3_2->m_Vertices.push_back(Vector4(2.0f, 1.5f, -0.5f));
    pLevel3_2->m_Vertices.push_back(Vector4(1.5f, -1.0f, 2.0f));
    pLevel3_2->m_Vertices.push_back(Vector4(0.5f, -1.0f, -3.0f));

auto pLevel3_3 = std::make_shared<CGameObject>();

pLevel3_3->m_Transform = 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
    );

pLevel3_3->m_Vertices.push_back(Vector4(-1.0f, 1.0f, 0.5f));
    pLevel3_3->m_Vertices.push_back(Vector4(0.5f, 2.0f, -2.0f));
    pLevel3_3->m_Vertices.push_back(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(pLevel2_2, pLevel3_1);
    ConnectNodes(pLevel2_2, pLevel3_2);
    ConnectNodes(pLevel2_3, pLevel3_3);

ConnectNodes(pLevel1_1, pLevel2_1);
    ConnectNodes(pLevel1_1, pLevel2_2);
    ConnectNodes(pLevel1_2, pLevel2_3);

ConnectNodes(pRoot, pLevel1_1);
    ConnectNodes(pRoot, pLevel1_2);

CSceneGraph SceneGraph;

SceneGraph.m_pRoot = pRoot;

return SceneGraph;
}

//------------------------------------------------------------------------------------
// Write the functions here before the main function
//------------------------------------------------------------------------------------

int main()
{
    CSceneGraph SceneGraph = BuildSceneGraph();

// Call your functions here....

std::cout << "Correct solution:\n"
        << "minX: -23.5\n"
        << "maxX: 11.5\n"
        << "minY: 9\n"
        << "maxY: 22\n"
        << "minZ: -3\n"
        << "maxZ: 16\n";

std::cout << "Current solution:\n"
        << "minX: " << SceneGraph.m_BoundingBox.minX << '\n'
        << "maxX: " << SceneGraph.m_BoundingBox.maxX << '\n'
        << "minY: " << SceneGraph.m_BoundingBox.minY << '\n'
        << "maxY: " << SceneGraph.m_BoundingBox.maxY << '\n'
        << "minZ: " << SceneGraph.m_BoundingBox.minZ << '\n'
        << "maxZ: " << SceneGraph.m_BoundingBox.maxZ << '\n';

// 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]

Vector4 V(10.0f, 10.0f, 10.0f);

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

// Example of a translation matrix
    Matrix4x4 M1(
        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
    Matrix4x4 M2(
        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;

std::cout << Result.x << '\n' << Result.y << '\n' << Result.z << '\n' << Result.w << '\n';
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 1.12 sec, absolute running time: 0.17 sec, cpu time: 0.01 sec, memory peak: 5 Mb, absolute service time: 1,43 sec