Dynamic Octree

The dynamic octree is a data structure that can efficiently handle dynamic changes to a set of objects in 3D space. It is "dynamic" because it allows for the insertion, removal, and movement of objects while maintaining an efficient representation of the spatial partitioning. This makes it particularly useful in scenarios where the object set is subject to frequent changes. ## Representation: The dynamic octree can be represented using mathematical notations as follows: 1. **Dynamic Octree Structure**: - $O = (N, A, P)$ - $N$ represents the set of nodes. - $A$ represents the set of atoms or objects. - $P$ represents the set of pointers. 2. **Node Attributes**: - Each node $n_i \in N$ has the following attributes: - $n_i.\text{NodeID}$ - Unique identifier for the node. - $n_i.\text{ParentPointer}$ - Pointer to the parent node. - $n_i.\text{ChildPointers}$ - Array of pointers to child nodes (for non-leaf nodes). - $n_i.\text{NumAtoms}$ - Number of atoms associated with the node. - $n_i.\text{NumFixed}$ - Number of fixed atoms in the node. - $n_i.\text{AtomIndices}$ - Array of atom indices within the node. - $n_i.\text{Leaf}$ - Indicator if the node is a leaf (1 for leaf, 0 for non-leaf). - $n_i.\text{IdCap}$ - Capacity of the node to store atom indices. 3. **Atom Attributes**: - Each atom $a_j \in A$ has the following attributes: - $a_j.\text{AtomID}$ - Unique identifier for the atom. - $a_j.\text{Position}$ - 3D position vector $(x_j, y_j, z_j)$. - $a_j.\text{Fixed}$ - Indicator if the atom is fixed (1 for fixed, 0 for non-fixed). - $a_j.\text{NodeID}$ - Identifier of the node the atom belongs to. 4. **Operations**: - $n_i.\text{ExpandNode}(..)$ - Function to expand a node $n_i$. - $n_i.\text{ContractNode}(..)$ - Function to contract a node $n_i$. - $n_i.\text{AddAtomToLeaf}(..)$ - Function to add an atom to a leaf node $n_i$. - $n_i.\text{RemoveAtomFromLeaf}(..)$ - Function to remove an atom from a leaf node $n_i$. - $n_i.\text{AddAtomToNonLeaf}(..)$ - Function to add an atom to a non-leaf node $n_i$. - $n_i.\text{RemoveAtomFromNonLeaf}(..)$ - Function to remove an atom from a non-leaf node $n_i$. 5. **Node Traversal and Search**: - $\text{Traverse}(O, P)$ - Function to traverse the dynamic octree starting from root node $O$ using pointer $P$. - $\text{Search}(O, a_j)$ - Function to search for atom $a_j$ in the dynamic octree starting from root node $O$. 6. **Memory Allocation**: - $n_i.\text{AllocateMemory}(..)$ - Function to allocate memory for a node $n_i$. - $n_i.\text{DeallocateMemory}(..)$ - Function to deallocate memory for a node $n_i$. - $n_i.\text{ReallocateMemory}(..)$ - Function to reallocate memory for a node $n_i$. 7. **Node Management**: - $O.\text{GetNextFreeNode}(..)$ - Function to get the index of the next free node in the dynamic octree $O$. 8. **Migration**: - $n_i.\text{UpwardMigration}(..)$ - Function to perform upward migration of an atom in node $n_i$. - $n_i.\text{DownwardMigration}(..)$ - Function to perform downward migration of an atom in node $n_i$. 9. **Splitting and Merging**: - $n_i.\text{SplitNode}(..)$ - Function to split a node $n_i$ into child nodes. - $n_i.\text{MergeNode}(..)$ - Function to merge a node $n_i$ with neighboring nodes. These notations provide a mathematical framework to describe the structure, attributes, and operations of a dynamic octree for representing objects in a changing environment. The entire process of making the dynamic octree dynamic involves several key steps: ## 1. Initialization - The dynamic octree is initialized by creating a root node that spans the entire 3D space. This root node is initially empty, and it serves as the starting point for building the octree. > bool DynamicOctree::buildOctree() > > The `buildOctree` function is responsible for constructing a dynamic octree data structure to efficiently represent a set of atoms in 3D space. The octree is built recursively by subdividing space into smaller cells, where each cell contains a limited number of atoms. This allows for faster spatial queries and proximity checks. ``` function buildOctree(): numAtoms = total number of atoms in the system // Allocate temporary memory for indices indices = allocate memory for int[numAtoms] indices_temp = allocate memory for int[numAtoms] // Get the root node of the octree octreeRoot = getNextFreeNode() // Compute the bounding box for the root node computeRootBoundingBox(octreeRoot, slackFactor, indices, 0, numAtoms - 1) // Set the root node's parent pointer to -1 (no parent) --- Root Node nodes[octreeRoot].setParentPointer(-1) // Recursively expand the octree octreeBuilt = expandOctreeNode(octreeRoot, indices, indices_temp, 0, numAtoms - 1) // Free the temporary memory deallocate memory for indices deallocate memory for indices_temp return octreeBuilt ``` --- ## 2. Expand Octree - The `expandOctreeNode` function is a crucial part of the dynamic octree construction process. It is responsible for expanding a node of the octree by recursively subdividing it and creating child nodes as needed. The function is called to construct the octree during the initialization phase. > bool DynamicOctree::expandOctreeNode() > **INPUT PARAMETERS**: > `node_id`: The index of the current node being processed. `indices`: An array containing the indices of the atoms that belong to the current node. `indices_temp`: A temporary array used for reordering the atom indices during subdivision. `start_id` and `end_id`: The indices that mark the range of atom indices within the indices array that are associated with the current node. > > The `expandOctreeNode` function is a recursive function used to expand an octree node and construct the dynamic octree. It subdivides the node and creates child nodes if necessary to accommodate the atoms within the node. If the node contains a small number of atoms (as determined by `needsExpansion`), it becomes a leaf node and stores the atom indices directly. Otherwise, it creates eight child nodes and redistributes the atoms among them based on their positions relative to the child nodes' bounding boxes. ``` function expandOctreeNode(node_id, indices, indices_temp, start_id, end_id): node = nodes[node_id] nAtoms = end_id - start_id + 1 node.setNumAtoms(nAtoms) // Check if the node needs expansion (subdivision) or can be a leaf if !needsExpansion(node): // The node is a leaf, handle leaf node logic node.setLeaf(1) // Allocate memory for the atom indices in the leaf node newIndices = allocateMemoryForLeafNode(2 * nAtoms) numFixedAtoms = 0 // Place fixed atoms first in the leaf node's index list // Set the number of fixed atoms in the leaf node // Place non-fixed atoms after the fixed atoms in the index list else: // The node needs expansion, handle subdivision logic node.setLeaf(0) // Count the number of atoms in each octant of the current node initialize count[8] to zero for i from start_id to end_id: j = indices[i] child_id = getChildId(node, atoms[j]) count[child_id]++ // Initialize start index and current index for each octant initialize start_index[8] and cur_index[8] to zero for i from 1 to 7: cur_index[i] = start_index[i] = start_index[i - 1] + count[i - 1] // Rearrange the atom indices based on octants for i from start_id to end_id: j = indices[i] child_id = getChildId(node, atoms[j]) indices_temp[cur_index[child_id]] = j cur_index[child_id]++ // Variable to track the total number of fixed atoms in the current node numFixedAtoms = 0 // Recursively expand each octant and update the total number of fixed atoms for i from 0 to 7: if count[i] > 0: // Get the next free node ID to expand the current octant new_node_id = getNextFreeNode() // Set the child pointer in the current node to the new expanded node node.setChildPointer(i, new_node_id) // Set the parent pointer in the new expanded node nodes[new_node_id].setParentPointer(node_id) // Compute the bounding box for the new expanded node computeNonRootBoundingBox(new_node_id, i) // Recursively expand the new node if !expandOctreeNode(new_node_id, indices_temp, indices, start_index[i], start_index[i] + count[i] - 1): return false // Update the total number of fixed atoms in the current node numFixedAtoms += nodes[new_node_id].getNumFixed() node.setNumFixed(numFixedAtoms) else: // If an octant has no atoms, set its child pointer to -1 node.setChildPointer(i, -1) return true ``` --- ## 3. Contract Octree - Contraction of Octree is an important function for maintaining the dynamic octree's efficiency by adjusting the node structure to adapt to changes in the distribution of atoms during the simulation. > bool DynamicOctree::contractOctreeNode(int node_id) > > The `contractOctreeNode` function is responsible for contracting a node of the dynamic octree when it becomes underutilized to save memory and improve performance. It is called when the number of atoms associated with a non-leaf node falls below a certain threshold, making it more efficient to store the atoms directly in the node itself instead of using child nodes. ``` function contractOctreeNode(node_id): node = nodes[node_id] // Get the octree node at the given node_id atoms = atoms // Get the array of atoms nAtoms = node.getNumAtoms() // Get the number of atoms in the node // Check if the node needs contraction (has excess capacity) if not needsContraction(node): return true // Compute the attributes of the non-leaf node (bounding box, etc.) computeNonLeafAttributes(node_id) // Allocate memory for a new array to store the contracted atom indices newIndices = allocate memory for int array of size 2 * nAtoms // Collect atom indices from the leaves of the octree and store them in the newIndices array collectAtomsFromLeaves(node_id, newIndices, 0) k = 0 // Separate fixed and non-fixed atoms in the newIndices array for i from 0 to nAtoms - 1: j = newIndices[i] // If the atom at index j is fixed, swap it with the next non-fixed atom if atoms[j] is fixed: l = newIndices[k] swap newIndices[i] and newIndices[k] k = k + 1 // Update the atom IDs to reflect their new positions in the contracted node for i from 0 to nAtoms - 1: j = newIndices[i] atoms[j].setId(create_octree_ptr(node_id, i)) // Mark the node as a leaf node and update its capacity and atom indices node.setLeaf(1) node.setIdCap(2 * nAtoms) node.setAtomIndices(newIndices) return true ```  --- > `updateOctree`: Purpose: The updateOctree function is used to update the position of an individual atom in the octree. It checks whether the atom's position is still within the node it currently belongs to, and if not, it performs the necessary adjustments to maintain the octree's structure. ## 4. Insertion - When a new object is added to the dynamic octree, the insertion process begins. The octree traverses down from the root to find the appropriate leaf node where the object belongs. If the leaf node becomes too full after insertion, it may need to split, creating child nodes and redistributing objects. > The `pushDown` function in the DynamicOctree class is responsible for adding an atom to the octree and recursively pushing it down to the appropriate leaf node. It traverses the octree, starting from the root node, to find the appropriate leaf node for a given atom. If the atom is already inside a leaf node, it is added to that node. If the atom needs to be added to a new leaf node, the function creates and expands the necessary non-leaf nodes along the path to the leaf level. > The `addAtomToLeaf` and `addAtomToNonLeaf` functions are used to add an atom to the octree. ``` addAtomToLeaf(node_id, atom_id): # Get the pointer to the node based on node_id node = nodes[node_id] # Get the pointer to the atom based on atom_id atom = atoms[atom_id] # Get the current number of atoms in the node n = node.getNumAtoms() # Check if the leaf node's atom indices array is full if n == node.getIdCap(): # Expand the capacity of the atom indices array node.setAtomIndices(reallocate (node.getAtomIndices(), node.getIdCap() * 2)) if atom.isFixed(): # Get the current number of fixed atoms in the node nf = node.getNumFixed() # Swap the last atom index in the array with the fixed atom's index node.setAtomIndex(n, node.getAtomIndex(nf)) # Set the new atom's ID to create an octree pointer atoms[node.getAtomIndex(n)].setId(create_octree_ptr(node_id, n)) # Swap the last fixed atom's index with the given atom's index node.setAtomIndex(nf, atom_id) # Set the fixed atom's ID to create an octree pointer atom.setId(create_octree_ptr(node_id, nf)) # Increment the number of fixed atoms in the node node.setNumFixed(nf + 1) else: node.setAtomIndex(n, atom_id) # Set the new atom's ID to create an octree pointer atom.setId(create_octree_ptr(node_id, n)) # Increment the number of atoms in the node node.setNumAtoms(n + 1) # Update the attributes of the node considering the new atom node.updateAttribs(atom, true) # Check if the node needs dynamic expansion if needsDynamicExpansion(node): # Allocate temporary storage temp = allocate_memory(n * sizeof(int)) # Copy the atom indices to the temporary storage for i = 0 to n-1: temp[i] = node.getAtomIndex(i) # Attempt to expand the node done = expandOctreeNode(node_id, node.getAtomIndices(), temp, 0, n-1) # Free the temporary storage free_memory(temp) # Return the result of the expansion (true if successful) return done # Return true (indicating successful addition to the leaf node) return true ``` ## 4. Removal - When an object is removed from the dynamic octree, the removal process begins. The octree traverses down from the root to find the leaf node containing the object and removes it. If the leaf node becomes too empty after removal, it may need to merge with neighboring nodes to maintain efficiency. > The `pullUp` function in the DynamicOctree class is responsible for moving an atom from its current node to the appropriate higher-level node in the octree when the atom's position has moved outside the boundaries of its current node. This function is used to maintain the structure and organization of the dynamic octree as atoms move within the simulation. > The two functions `removeAtomFromLeaf` and `removeAtomFromNonLeaf` are used to remove an atom from its current node in the dynamic octree when the atom is no longer inside that node's bounding box. These functions handle the removal of the atom from the leaf and non-leaf nodes, respectively. ``` function removeAtomFromNonLeaf(node_id, atom_id): node = nodes[node_id] // Get the non-leaf node using node_id atom = atoms[atom_id] // Get the atom to be removed using atom_id // Decrease the count of atoms in the non-leaf node node.decNumAtoms() if atom.isFixed(): // Decrease the count of fixed atoms in the non-leaf node node.decNumFixed() // Update node attributes after atom removal node.updateAttribs(atom, false) if needsDynamicContraction(node): // Check if the node needs dynamic contraction if not contractOctreeNode(node_id): // Contract the non-leaf node if needed return false return true // Successful atom removal ``` ``` function removeAtomFromLeaf(node_id, atom_id): node = nodes[node_id] // Get the leaf node using node_id atom = atoms[atom_id] // Get the atom to be removed using atom_id j = get_index_in_node(atom.id) // Get the index of the atom within the leaf node if atom.isFixed(): // Check if the atom is fixed // If fixed, swap the atom with the last fixed atom in the node nf = node.getNumFixed() - 1 node.setAtomIndex(j, node.getAtomIndex(nf)) node.setAtomIndex(nf, node.getAtomIndex(n-1)) // Swap atom IDs to maintain consistency indexNf = node.getAtomIndex(nf) indexJ = node.getAtomIndex(j) atoms[indexNf].setId(atoms[indexJ].getId()) atoms[indexJ].setId(atom.getId()) node.setNumFixed(nf) // Update the number of fixed atoms in the node else: // If not fixed, swap the atom with the last atom in the node node.setAtomIndex(j, node.getAtomIndex(n-1)) atoms[node.getAtomIndex(j)].setId(atom.getId()) node.setNumAtoms(n - 1) // Update the number of atoms in the node // If the node is less than 25% full if n <= (node.getIdCap() / 4): // Contract leaf storage newIndices = realloc(node.getAtomIndices(), node.getIdCap() / 2) node.setAtomIndices(newIndices) node.setIdCap(node.getIdCap() / 2) // Update the node's capacity // Update node attributes after atom removal node.updateAttribs(atom, false) // Mark the atom as removed from the octree atom.setId(-1) return true // Successful atom removal ``` ## 5. Movement - When an object moves within the 3D space, the dynamic octree must update its representation accordingly. This process involves removing the object from its current location and reinserting it at the new location. Depending on the displacement, the octree may need to redistribute objects among nodes to maintain balance. ## 6. Node Management - The dynamic octree optimizes its memory usage by dynamically allocating and deallocating memory for nodes. When nodes become empty, they are returned to a free node server, and the memory is freed. When new nodes are needed, the dynamic octree requests them from the free node server. > The `getNextFreeNode` function ensures that the octree has free nodes available for expansion or addition of new elements. It manages the pool of free nodes and provides the index of the next free node whenever required. If there are no free nodes, it allocates additional nodes and adds them to the pool. ``` getNextFreeNode(): # If there are no free nodes, allocate new nodes and set them as free nodes. if nextFreeNode == -1: # Calculate the desired number of new nodes new_num_nodes = 2 * numNodes # Allocate memory for the new nodes reallocateNodes(new_num_nodes) if nodes == NULL: # Return -1 indicating failure if memory allocation failed return -1 # Initialize the new nodes as free nodes and update nextFreeNode to point to the first free node for i from new_num_nodes - 1 down to numNodes: nodes[i].setParentPointer(nextFreeNode) nextFreeNode = i # Update the total number of nodes in the octree numNodes = new_num_nodes # Get the index of the next free node next_node = nextFreeNode # Update nextFreeNode to point to the next free node nextFreeNode = nodes[next_node].getParentPointer() # Return the index of the next free node return next_node ``` ## 7. Upward and Downward Migration - When an object moves between nodes during insertion or removal, it is said to migrate. The dynamic octree uses upward migration to find a suitable parent node for the object during insertion and downward migration to find a suitable leaf node during removal. ## 8. Node Splitting and Merging - As the object set changes, the dynamic octree performs node splitting and merging operations to maintain balance and efficiency. Node splitting occurs when a leaf node becomes too full, and it is split into multiple child nodes. Node merging happens when a leaf node becomes too empty, and it merges with neighboring nodes to reduce the tree's depth. This is implemented by `expandOctree` and `contractOctree` functions mentioned before. By dynamically managing node allocation and adapting to changes in the object set, the dynamic octree can efficiently handle real-time scenarios where objects are frequently inserted, removed, or moved, providing a flexible and scalable data structure for spatial partitioning and collision detection in 3D space. ---