Description
1 Overview
You may hear of some famous games (e.g. Doom and Quake), but did you know they had used a technique called Binary Space Partitioning (BSP) to speed up visibility calculations in 3D Rendering? Visibility calculations means “only visible walls and objects must be drawn, and they must be drawn in the right order (close walls should be drawn in front of far away walls)”.
In computer science, BSP is a technique that recursively subdivides a space into two convex sets via hyperplanes as partitions. It generates a representation of objects within the space, which is in the form of a tree data structure[1].
To render maps in a game, the visibility calculation needs to be performed so that it can be used many times later. Note, for assignment purposes, we only consider static maps here. These calculations will be stored in a tree structure, and will be used in the game.
Briefly, BSP divides the map into many convex polygons, which is a polygon where all its internal angles ≤ 180 degrees. Fig. 1 shows an example of convex and non-convex polygon.
Figure 1: Examples of convex and non-convex polygon
For example, Fig. 2-1 is a given map, which is considered a non-convex polygon. Then, we can draw a line to divide it into two sub-polygons, as shown in Fig. 2-2. In this step, two sub-polygons are created. The corresponding tree structure for this operation is shown at the bottom of Fig. 2-2. BSP keeps dividing these two sub-polygons recursively until the entire map is divided into convex polygons. During this process, each division generates a new branch in the tree structure. Finally, the leaves of the tree are the convex polygons.
Figure 2: Example of BSP [2]
The core of the visibility ordering system lies in the order in which the rendering function recurses. That is, whether the left or right subtree of the given node is rendered first. For any particular node, there is a dividing line where it splits into two subnodes. If this line is extended to infinity, the viewpoint from which we are rendering can be considered to be on either the “left” or “right” side. The side viewpoint is on determines which of the subnodes is rendered first.
Rendering using BSP trees is also done using a recursive algorithm. The most common approach is to start at the root node (the top of the tree) and work down recursively.
This is why it is desirable to make sure the efficiency of doing operations on this tree. In class, we studied two methods to represent the tree,
- the Sequential Representation, and
- the Linked Representation.
The performance of each representation varies depending on the characteristics of the tree.
In this assignment, we will implement both representations, and evaluate how well they perform when representing some given Binary Space Partitioning Trees and computing the average speed of visiting nodes in the tree.
2 Tasks
The assignment is broken up into a number of tasks, to help you progressively complete the project.
Task A: Implement the Tree Representations and their Operations (5 marks)
In this task, you will implement the tree using Sequential Representation and Linked Representation. Each representation will be implemented by a data structure. Your implementation should support the following operations:
- Create an empty tree (implemented as a constructor that takes zero arguments).
- Set a root node for the tree.
- Split a node into two children nodes.
- Find a node in the tree.
- Find a parent node of a given node.
- Find children nodes of a given node.
- Print out all the nodes in a certain order, including preorder, inorder, and postorder. This is actually Tree-traversal, which refers to the process of recursively visiting (examining and/or updating) each node in a tree data structure, exactly once, in a systematic Such traversals are classified by the order in which the nodes are visited. Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed defines the traversal type. These steps are: performing an action on the current node (referred to as “visiting” the node), traversing to the left child node, and traversing to the right child node. Although we didn’t go through this in lectures, it is interesting to know about traversals. Consider the following traversal approaches and example as shown in Fig. 3.
Figure 3: Examples of tree-traversal methods
Data Structure Details
Trees can be implemented using a number of data structures. You are to implement the tree abstract data type using the following data structures:
- Sequential Representation, using a 1D array.
- Linked Representation, using a linked list.
For linked list, you must program your own implementation, and not use existing libraries in any kind, e.g. the LinkedList, Set, MultiSet or Tree type of data structures in java.utils or any other libraries. You must implement your own nodes and methods to handle the operations. If you use java.utils or other implementation from libraries, this will be considered as an invalid implementation and attract 0 marks for that data structure.
Operations Details
Operations to perform on the implemented tree abstract data type are specified on the command line. They are in the following format:
<operation> [arguments]
where operation is one of {RN, SP, FN, FP, FC, TP, TI, TS, Q} and arguments is for optional arguments of some of the operations. The operations take the following form:
- RN <nodeLabel> – sets a root node with label ‘nodeLabel’ into an empty tree. There should have no output for this operation.
- SP <nodeLabel> <leftChild> <rightChild> – splits the given node into two children nodes like the operations in Fig. 2-2. There should have no output for this operation.
- FN <nodeLabel> – finds a node with label ‘nodeLabel’ in the tree. The output should be true if find it, otherwise false.
- FP <nodeLabel> – finds the parent node of the given node with label ‘nodeLabel’ in the tree. The format of the output for node ‘B’ should take the form:
B <the label of B’s parent node>,
e.g., ‘B A’ or ‘B ’ if node B has no parent.
- FC <nodeLabel> – finds the children nodes of the given node with label ‘nodeLabel’ in the tree. The format of the output for node ‘A’ should take the form:
A <the label of A’s left child node> <the label of A’s right child node>, e.g., “A B C”
- TP – prints all the nodes in the preorder The print operation outputs the nodes in the tree in a single line. The line should specify all the valid nodes (note labels) in the tree.
<node1> <node2> <node3> …
- TI – prints all the nodes in the inorder The same output format like TP.
- TS – prints all the nodes in the postorder The same output format like
TP.
- Q – quits the program.
Refer to the javaDoc of BSPTree.java for more implementation requirements. As an example of the operations, consider the output from the following list of operations:
RN A
SP A B C
SP B D E
SP C F G
FN C
FN H
FP F
FP A FC B
FC C
FC G
TP
Q
The output should be:
true false
F C
A
- D E
- F G
G
A B D E C F G
Testing Framework
We provide Java skeleton code (see Table 1) to help you get started and automate the correctness testing. You may add your own Java files to your final submission, but please ensure that they work with the supplied Python testing script (see below).
TreeTester.java Code that reads in operation commands from
stdin then executes those on the selected tree implementation. Do not modify this file.
BSPTree.java Interface for BSP trees. All implementations should implement the BSPTree class defined in this file. Read the javaDoc of each method carefully and do not modify this file.
SequentialRepresentation.java Code that implements the sequential representation of a tree. Complete the implementation (implement parts labelled “Implement me!”).
LinkedRepresentation.java Code that implements the linked representation of a tree. Complete the implementation (implement parts labelled “Implement me!”).
Table 1: Table of Java files.
In addition, we provide a Python script that automates testing, based on input files of operations (such as example above). A detailed instruction about how to use this Python script is included at the top of the python file itself. These are fed into the Java framework which calls your implementations. The outputs resulting from any print operations are stored, then compared with the expected output. We have provided two sample input and expected files for your testing and examination.
For our evaluation of the correctness of your implementation, we will use the same Python script and input/expected files that are in the same format as the provided examples. To avoid unexpected failures, please do not change the Python script nor TreeTester.java. If you wish to use the script for your timing evaluation, make a copy and use the unaltered script to test the correctness of your implementations, and modify the copy for your timing evaluation. Same suggestion applies for TreeTester.java.
As the instructions for the assignment are getting too lengthy, instructions on how the python script runs are available within the header of the script.
