COSC2123-1285 -Algorithms and Analysis -Assignment 1- Binary Space Partitioning - Solved

    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 way. 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 traversal. 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 traversal. The same output format like TP.

•   TS – prints all the nodes in the postorder traversal. 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

B   D E

C   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).

file                                                 description
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.

Notes
•   Use the output of the provided sample implementation (sample is the actual name of the implementation) to help you determine the right output format for the operations. If you correctly implement the “Implement me!” parts, you in fact do not need to do anything else to get the correct output formatting. TreeTester.java will handle this.

•   We will run the supplied test script on your implementation on one of the following university’s core teaching servers:

–   titan.csit.rmit.edu.au

–   jupiter.csit.rmit.edu.au

–   saturn.csit.rmit.edu.au

If you develop on your own machines, please ensure your code compiles and runs on these servers. You don’t want to find out last minute that your code doesn’t compile on these servers. If your code doesn’t run on these servers, we unfortunately do not have the resources to debug each one and cannot award marks for testing.

•   All submissions should compile with no warnings on Oracle Java 8.

Test Data
We provide a Binary Space Partition example of about 4000 nodes in a file called “BSP_combined.txt”. This is real, sampled part of a game map.

Task B: Evaluate your Data Structures (5 marks)
In this second task, you will evaluate your two implemented structures in terms of their time complexities for the different operations and different use case scenarios. Scenarios arise from the possible BSP usage.

Write a report on your analysis and evaluation of the different implementations. Consider and recommend in which scenarios each type of implementation would be most appropriate. The report should be 6 pages or less, in font size 12. See the assessment rubric (Appendix A) for the criteria we are seeking in the report.

Use Case Scenarios
Typically, you use real usage data to evaluate your data structures. However, for this assignment, you will write data generators to enable testing over different scenarios of interest. There are many possibilities, but for this assignment, consider the following scenarios:

Scenario 1 Growing BSP Tree (Additions): In this scenario, the BSP tree is growing while a map is being divided into smaller new polygons (nodes). In this scenario, you are to evaluate the performance of your implementations in terms of:

•   node addition;

•   node splitting;

Assume the tree that you start with is the BSP_combined.txt one. You are to evaluate the performance the node addition and splitting operations as the complexity of the initial tree is varied.

Scenario 2 Finding a Node and Its Parent Node and Children Nodes: In this scenario, the tree is not changing, but important operations such as Finding the Node and/or its parent node and/or children nodes are required.

Assume the tree that you start with is the BSP_combined.txt one. You are to evaluate the performance of the finding node and its parent/children node(s) implementations as the complexity of the initial tree is varied.

Scenario 3 Printing the Nodes (Traversal):

This is to evaluate the performance of your implementation in terms of:

•   preorder traversal

•   inorder traversal

•   postorder traversal

Assume the tree that you start with is the one that we provided you with. You are to evaluate the performance the traversal operations as the complexity of the initial tree is varied.

Analysis
In your analysis, you should evaluate each of your representations and data structures in terms of the different scenarios outlined above. For generating tree with different initial complexities, you may want to either generate a series of split node operations (‘SP’) to grow the tree to the desired complexity, then evaluate for the appropriate scenario. Alternatively, you can consider writing a data generator within Java to insert directly into the data structures. Whichever method you decide to use, remember to generate tree of different complexities to evaluate on (Specifically, this means that you need to generate tress with different sizes, e.g. trees with various the depth or the number of nodes. For example, the number of nodes can be 102, 103 or 106). Due to the randomness of the data, you may wish to generate a few datasets with the same parameters settings (same tree complexity and a scenario) and take the average across a number of runs.

Note, you may be generating and evaluating a significant number of datasets, hence we advise you to get started on this part relatively early.
Task C: Theoretical Complexity Analysis (5 Marks)
Question C1. Complexities of tree operations [3 mark] Fill in the following table with YES/NO answers to indicate whether the corresponding tree operations belong to certain complexity classes in the worst case, and explain why. Here n is the number of nodes in the tree implementation for the BSP. Please note answers without explanations will attract zero marks.

 
O(1)
O(log(n))
O(n)
O(n!)
Find parent
 
 
 
 
Find a node
 
 
 
 
Print all nodes
 
 
 
 
Question C2. Guessing the age of an alien [2 mark] An astronaut, after an emergency landing on a remote planet, was faced by an alien. Using his portable universal language translator, the desperate astronaut asked the alien for water and food. Luckily, the alien agreed to help, with one condition: the astronaut must be able to guess correctly its age by asking just YES/NO questions before he died of hunger. As there was no way to tell how old the planet or the alien is, the astronaut had to assume that the alien was of any age between 1 to N years old, where N is a very large number. For instance, to be on the safe side, N is around 14 billion, which is the estimated age of the universe. Now, let’s consider two strategies for asking the questions.

1.   (Strategy 1) The astronaut asked the questions "Are you n years old?" for every n = 1,2,..., N in any order. If the alien answered YES, the astronaut won the supplies. If not, he continued his questions. What are the number of questions he needed to ask before getting his food in the worst case? Same question for the average case, assuming that every age between 1 and N are equally likely with probability 1/N? If N = 14 billion and that each question and answer took just one second to complete, roughly how long would it take the astronaut before he can have a drink in the worst case and in the average case?

2.   (Strategy 2) The astronaut asked a series of questions "Are you at most X years old?" and represented them as nodes in a binary tree. He could start off at Node 1 by asking "Are you at most X1 years old?". If YES, he create Node 2, which is a leftchild of Node 1 and continues asking "Are you at most X2 years old?", while if NO, he create Node 3, which is a right-child of Node 1 and continues asking "Are you at most X3 years old?", and so forth. Using the best design of such a tree to minimize the number of questions asked, how many questions do you think the astronaut needed to ask in the worst case and in the average case? If N = 14 billion, how many questions did he need in both cases?

3    Report Structure
As a guide, the report could contain the following sections:

•   Explain your data generation and experimental setup. Things to include are (brief) explanations of the generated data you decide to evaluate on, the complexity parameters you tested on, describe how the scenarios were generated (a paragraph and perhaps a figure or high level pseudo code suffice), which approach(es) you decide to use for measuring the timing results, and briefly describe the fixed set(s) you used to generate the elements for node addition.

•   Evaluation of the data structures using the generated data. Analyse, compare and discuss your results across different densities, representations and scenarios. Provide your explanation on why you think the results are as you observed. You may consider using the known theoretical time complexities of the operations of each data structure to help in your explanation.

•   Summarise your analysis as recommendations, e.g., for this certain data scenario of this complexity, I recommend using this data structure because... We suggest you refer to your previous analysis to help.

•   Detail your solutions to Task C.




 
[1] https://en.wikipedia.org/wiki/Binary_space_partitioning
[2] The picture in https://en.wikipedia.org/wiki/Binary_space_partitioning