-
Notifications
You must be signed in to change notification settings - Fork 0
/
BspTree.java
62 lines (51 loc) · 1.78 KB
/
BspTree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.*;
public class BspTree {
private BspNode root;
public BspNode getRoot() {
return this.root;
}
//set up the tree using the list of nodes provided.
public void compile(List<BspNode> nodes) {
SideAssignment assignment = this.assignSides(nodes);
this.root = compileRec(assignment.front, assignment.middle, assignment.back);
}
private BspNode compileRec(List<BspNode> frontNodes, BspNode middle, List<BspNode> backNodes) {
if(frontNodes.size() > 0) {
SideAssignment a = this.assignSides(frontNodes);
middle.setFront(compileRec(a.front, a.middle, a.back));
}
if(backNodes.size() > 0) {
SideAssignment a = this.assignSides(backNodes);
middle.setBack(compileRec(a.front, a.middle, a.back));
}
return middle;
}
private class SideAssignment {
public List<BspNode> front = new ArrayList<BspNode>();
public BspNode middle;
public List<BspNode> back = new ArrayList<BspNode>();
}
//split the nodes array up by seleting the middle node, and assigning the rest of the nodes to
//be either in front of or behind it.
private SideAssignment assignSides(List<BspNode> nodes) {
SideAssignment a = new SideAssignment();
a.middle = nodes.remove(nodes.size() / 2);
Wall mid = a.middle.getWall();
for(int i = 0; i < nodes.size(); i++) {
BspNode n = nodes.get(i);
Wall wall = n.getWall();
if(mid.intersects(wall)) {
Wall[] split = mid.split(wall);
a.front.add(new BspNode(split[0]));
a.back.add(new BspNode(split[1]));
}
else if(wall.inFrontOf(mid)) {
a.front.add(n);
}
else {
a.back.add(n);
}
}
return a;
}
}