1
$\begingroup$

Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box intersection check.

Since that is causing a bottleneck in my program I am looking to optimise this stage by somehow assigning the neighbours during octree-creation stage.

I am building a 'depth-first' recursive octree, which means that I go to the deepest level for every node, before moving on to it's neighbour...

What would be the best way to do something like this?

EDIT: The definition of 'neighbours' is the following. A neighbour is each node of the same level/depth which shares a face with the current node. Nodes which only share an edge or vertex should not be considered as neighbours. The picture below provides more clarity...enter image description here

$\endgroup$
0
+50
$\begingroup$

I don't know if there is a way while constructing the oct tree. But here is way after you created the tree, which runs in O(N), where N is the number of Nodes. For each node there has to be a maximal comparison of 8*6+7 = 55. This might can be reduced but this might be fast enough.

loops through all nodes breadth-first. A neighbour of a child is a neighbour child of the parent or a child of a the parents neighbours.

The comparison if two points are neighbours is here distance(node_1,node_2) == SMALLEST. I don't know how you compare it. Maybe you can insert your code. You could caluclate for each level the Euclidian distance of the points if you have equally spaced cuboids and compare them. That would be the fastest way.

when nothing works, you can just make a list for each of the 8 comparisons, sort them and keep the lowest one.

call function calc_neighbours(root_node) after you created the oct tree

class Node:
    Node **childs // array of size 8 and pointers to the child node pointers
    Node *parent
    Neighbours **neighbours

function calc_neighbours(root_node):
    queue = create_queue()
    queue.add(root_node)
    while (queue.isEmpty() == false)
    {
        parent_node = queue.pop()
        for (int i = 0; i < 8; i++) // for each child_cube
        {
            queue.push(parent_node->child[i])
            for (int j = 0; j < 8; j++) // for each neighbour child_cube
                 if (i != j && distance(parent_node->child[i],parent_node->child[j]) == SMALLEST)
                    // filter out those who share only vertex/edge
                    parent_node->child[i]->neighbours.add(parent_node->child[j])
        }
        if (parent_node != root_node)
        // root node has no neighbours, loops through all neighbours of the parent's neighbour's child
            for (int n = 0; n < parent_node->neighbours->size(); n++)
                for (int i = 0; i < 8; i++) // for each child_cube
                    for (int j = 0; j < 8; j++) // for each neighbour child_cube
                         if (distance(parent_node->child[i],parent_node->neighbours[n]->child[j]) == SMALLEST)
                            parent_node->child[i]->neighbours.add(parent_node->neighbours[n]->child[j])
    }
$\endgroup$
  • $\begingroup$ storing all neighbours of the node of the same level/depth while creating the octtree is relatively easy. I have no idea what "shares a face" with the current node is. You seem to store some specific information in the octtree, which you did not mention. $\endgroup$ – user3613886 Jan 15 '15 at 14:42
  • $\begingroup$ So i assume you store something like in the picture here (en.wikipedia.org/wiki/Octree). and each node contains the 3D-Coordinates of the center of each cube and each level decides how many cubes exists. $\endgroup$ – user3613886 Jan 15 '15 at 15:02
  • $\begingroup$ A cuboid has only 6 sides/faces $\endgroup$ – user3613886 Jan 15 '15 at 15:24
  • $\begingroup$ An octree node is a virtual cell (cuboid), each cell has 6 sides/faces. 2 cells of the same depth sharing a side/face are neighbours... /thanks for correction/ $\endgroup$ – G.Rassovsky Jan 15 '15 at 15:27
  • $\begingroup$ ok and is my comment before right that every node contains the 3D-Coordinates of each center of each cuboid? So the neighbours are the ones with the smallest euclidian distance $\endgroup$ – user3613886 Jan 15 '15 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.