Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Algorithms and Analysis
COSC 2123/1285
Assignment 1: Binary Space Partitioning (BSP)
In the submission (your report) you will be required to certify that the submitted solution represents your own work only by agreeing to the following statement:
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 calcula- tions 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 structure1.
Assessment Type
Pair (Group of 2) Assignment.
Marks
15
We (I) certify that this is all our (my) own original work. If we (I) took any parts from elsewhere, then they were non-essential parts of the as- signment, and they are clearly attributed in my submission. We (I) will show we (I) agree to this honor code by typing “Yes”:
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 com- mon 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 com- puting 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.
• Printoutallthenodesinacertainorder,includingpreorder,inorder,andpostorder. 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.
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.
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: 4
For linked list, you must program your own implementation, and not use ex- isting 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 implemen- tation and attract 0 marks for that data structure.