| 62 | |
| 63 | |
| 64 | class Octree: |
| 65 | def __init__(self, worldSize): |
| 66 | # Init the world bounding root cube |
| 67 | # all world geometry is inside this |
| 68 | # it will first be created as a leaf node (ie, without branches) |
| 69 | # this is because it has no objects, which is less than MAX_OBJECTS_PER_CUBE |
| 70 | # if we insert more objects into it than MAX_OBJECTS_PER_CUBE, then it will subdivide itself. |
| 71 | self.root = self.addNode((0,0,0), worldSize, []) |
| 72 | self.worldSize = worldSize |
| 73 | |
| 74 | def addNode(self, position, size, objects): |
| 75 | # This creates the actual OctNode itself. |
| 76 | return OctNode(position, size, objects) |
| 77 | |
| 78 | def insertNode(self, root, size, parent, objData): |
| 79 | if root == None: |
| 80 | # we're inserting a single object, so if we reach an empty node, insert it here |
| 81 | # Our new node will be a leaf with one object, our object |
| 82 | # More may be added later, or the node maybe subdivided if too many are added |
| 83 | # Find the Real Geometric centre point of our new node: |
| 84 | # Found from the position of the parent node supplied in the arguments |
| 85 | pos = parent.position |
| 86 | # offset is halfway across the size allocated for this node |
| 87 | offset = size / 2 |
| 88 | # find out which direction we're heading in |
| 89 | branch = self.findBranch(parent, objData.position) |
| 90 | # new center = parent position + (branch direction * offset) |
| 91 | newCenter = (0,0,0) |
| 92 | if branch == 0: |
| 93 | # left down back |
| 94 | newCenter = (pos[0] - offset, pos[1] - offset, pos[2] - offset ) |
| 95 | |
| 96 | elif branch == 1: |
| 97 | # left down forwards |
| 98 | newCenter = (pos[0] - offset, pos[1] - offset, pos[2] + offset ) |
| 99 | |
| 100 | elif branch == 2: |
| 101 | # right down forwards |
| 102 | newCenter = (pos[0] + offset, pos[1] - offset, pos[2] + offset ) |
| 103 | |
| 104 | elif branch == 3: |
| 105 | # right down back |
| 106 | newCenter = (pos[0] + offset, pos[1] - offset, pos[2] - offset ) |
| 107 | |
| 108 | elif branch == 4: |
| 109 | # left up back |
| 110 | newCenter = (pos[0] - offset, pos[1] + offset, pos[2] - offset ) |
| 111 | |
| 112 | elif branch == 5: |
| 113 | # left up forward |
| 114 | newCenter = (pos[0] - offset, pos[1] + offset, pos[2] + offset ) |
| 115 | |
| 116 | elif branch == 6: |
| 117 | # right up forward |
| 118 | newCenter = (pos[0] + offset, pos[1] - offset, pos[2] - offset ) |
| 119 | |
| 120 | elif branch == 7: |
| 121 | # right up back |