SceneGraph Interviewee Task, Python 3

Language: Layout:

# 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 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 int the file game_object.py
# 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)
#------------------------------------------------------------------------------------

class Vector4:
    def __init__(self, x = None, y = None, z = None, w = 1.0):
        self.x, self.y, self.z, self.w = x, y, z, w

if x == None:
            self.x = 0.0
        if y == None:
            self.y = 0.0
        if z == None:
            self.z = 0.0
    
    def __getitem__(self, index):
        data = [self.x, self.y, self.z, self.w]
        return data[index]

def __setitem__(self, index, value):
        if (index == 0):
            self.x = value
        elif (index == 1):
            self.y = value
        elif (index == 2):
            self.z = value
        elif (index == 3):
            self.w = value

def Dot(left, right):
    return left.x * right.x + left.y * right.y + left.z * right.z + left.w * right.w

class Matrix4x4:
    def __init__(self, m00 = None, m10 = None, m20 = None, m30 = None, m01 = None, m11 = None, m21 = None, m31 = None, m02 = None, m12 = None, m22 = None, m32 = None, m03 = None, m13 = None, m23 = None, m33 = None):
        self.columns = [Vector4(1.0, 0.0, 0.0, 0.0), Vector4(0.0, 1.0, 0.0, 0.0), Vector4(0.0, 0.0, 1.0, 0.0), Vector4(0.0, 0.0, 0.0, 1.0)]

if m00 != None:
            self.columns[0][0] = m00
            self.columns[0][1] = m01
            self.columns[0][2] = m02
            self.columns[0][3] = m03

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

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

self.columns[3][0] = m30
            self.columns[3][1] = m31
            self.columns[3][2] = m32
            self.columns[3][3] = m33

def __getitem__(self, index):
        return self.columns[index]
    
    def MulMatrix(self, other):        
        result = Matrix4x4()

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

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

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

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

return result
    
    def MulVector(self, vector):
        result = Vector4()

for row in range(4):
            result[row] = self[0][row] * vector[0] + self[1][row] * vector[1] + self[2][row] * vector[2] + self[3][row] * vector[3]

return result

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

class CAABB:
    def __init__(self):
        self.minX, self.maxX, self.minY, self.maxY, self.minZ, self.maxZ = 0.0, 0.0, 0.0, 0.0, 0.0, 0.0

class CGameObject:
    def __init__(self):
        self.m_Transform = Matrix4x4()
        self.m_Children = []
        self.m_Vertices = []
        self.m_BoundingBox = CAABB()
        self.m_Parent = None

class CSceneGraph:
    def __init__(self):
        self.m_Root = None
        self.m_BoundingBox = CAABB()

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

def ConnectNodes(Parent, Child):
    Parent.m_Children.append(Child)
    Child.m_Parent = Parent

def BuildSceneGraph():

# Root

Root = CGameObject()

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

Root.m_Vertices.append(Vector4(1.0, 1.0, 1.0))
    Root.m_Vertices.append(Vector4(0.0, 0.0, 0.0))
    Root.m_Vertices.append(Vector4(1.0, -1.0, 1.0))

# Level1

Level1_1 = CGameObject()

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

Level1_1.m_Vertices.append(Vector4(-1.0, -1.0, -1.0))
    Level1_1.m_Vertices.append(Vector4(0.0, 0.0, 0.0))
    Level1_1.m_Vertices.append(Vector4(1.0, -1.0, 1.0))

Level1_2 = CGameObject()

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

Level1_2.m_Vertices.append(Vector4(0.5, 2.0, 3.0))
    Level1_2.m_Vertices.append(Vector4(2.0, 2.0, 2.0))
    Level1_2.m_Vertices.append(Vector4(0.5, 0.5, 0.5))

# Level2

Level2_1 = CGameObject()

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

Level2_1.m_Vertices.append(Vector4(3.0, 2.0, 1.0))
    Level2_1.m_Vertices.append(Vector4(-1.0, 0.0, 0.0))
    Level2_1.m_Vertices.append(Vector4(1.5, 0.5, 2.5))

Level2_2 = CGameObject()

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

Level2_2.m_Vertices.append(Vector4(-2.0, -2.0, -2.0))
    Level2_2.m_Vertices.append(Vector4(0.0, 0.0, 0.0))
    Level2_2.m_Vertices.append(Vector4(-1.0, -1.0, -1.0))

Level2_3 = CGameObject()

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

Level2_3.m_Vertices.append(Vector4(2.0, 2.0, 2.0))
    Level2_3.m_Vertices.append(Vector4(1.0, 1.0, 1.0))
    Level2_3.m_Vertices.append(Vector4(0.0, 0.0, 0.0))

# Level3

Level3_1 = CGameObject()

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

Level3_1.m_Vertices.append(Vector4(3.0, 0.5, 2.0))
    Level3_1.m_Vertices.append(Vector4(-0.5, -1.0, -2.0))
    Level3_1.m_Vertices.append(Vector4(3.5, 1.0, 0.0))

Level3_2 = CGameObject()

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

Level3_2.m_Vertices.append(Vector4(2.0, 1.5, -0.5))
    Level3_2.m_Vertices.append(Vector4(1.5, -1.0, 2.0))
    Level3_2.m_Vertices.append(Vector4(0.5, -1.0, -3.0))

Level3_3 = CGameObject()

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

Level3_3.m_Vertices.append(Vector4(-1.0, 1.0, 0.5))
    Level3_3.m_Vertices.append(Vector4(0.5, 2.0, -2.0))
    Level3_3.m_Vertices.append(Vector4(-1.5, 0.0, 1.5))

#               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)

SceneGraph = CSceneGraph()

SceneGraph.m_Root = Root

return SceneGraph

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

if __name__ == "__main__":
    SceneGraph = BuildSceneGraph()

# Call your functions here....

print("Correct solution:")
    print("minX: -23.5")
    print("maxX: 11.5")
    print("minY: 9")
    print("maxY: 22")
    print("minZ: -3")
    print("maxZ: 16")

print("Current solution:")
    print("minX: " + str(SceneGraph.m_BoundingBox.minX))
    print("maxX: " + str(SceneGraph.m_BoundingBox.maxX))
    print("minY: " + str(SceneGraph.m_BoundingBox.minY))
    print("maxY: " + str(SceneGraph.m_BoundingBox.maxY))
    print("minZ: " + str(SceneGraph.m_BoundingBox.minZ))
    print("maxZ: " + str(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]

Vec = Vector4(10.0, 10.0, 10.0)

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

# Example of a translation matrix
    Mat1 = Matrix4x4(
        1.0, 0.0, 0.0, -50.0,
        0.0, 1.0, 0.0, 10.0,
        0.0, 0.0, 1.0, 100.0,
        0.0, 0.0, 0.0, 1.0
    )

# Example of a scaling matrix
    Mat2 = Matrix4x4(
        0.5, 0.0, 0.0, 0.0,
        0.0, 0.5, 0.0, 0.0,
        0.0, 0.0, 0.5, 0.0,
        0.0, 0.0, 0.0, 1.0
    )

# Matrix multiplication is possible
    Mat3 = Mat1.MulMatrix(Mat2)

# Vectors can be transformed by matrices
    ResultVector = Mat3.MulVector(Vec)

print(ResultVector.x)
    print(ResultVector.y)
    print(ResultVector.z)
    print(ResultVector.w)

[ + ] Show input
Absolute running time: 0.19 sec, cpu time: 0.05 sec, memory peak: 9 Mb, absolute service time: 0,33 sec