[Solved]: The most efficient way of finding/storing neighbourhood info during octree creation

Problem Detail: 

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(n²/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...

Asked By : G.Rassovsky

Answered By : user3613886

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])     } 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33550