C++ Octree structure

[Alex Chitea]

Hi guys, I want to implement in C++ an octree data structure. This should look like a binary tree data structure, however instead of having 2 children, every node should have 8. Does any of you has this thing already implemented and can pass on to me the source code? Or do you know somebody that can help with writing my source code? Thanks a lot,

[David Crow]

I haven't written a binary tree since undergraduate school so here is a high-level overview of what might be required:

struct Node
{
// you'll probably want a data item/pointer here

// pointers to child nodes
Node \*p1;
Node \*p2;
Node \*p3;
Node \*p4;
Node \*p5;
Node \*p6;
Node \*p7;
Node \*p8;

} *pRoot = NULL;

void _Add( Node *pNode, Datum *pDatum )
{
if (NULL == pNode)
{
pNode = new Node;
// assign values accordingly to data items

    // make sure pointers start life as NULL
    pNode->p1 = NULL;
    pNode->p2 = NULL;
    ...
}
else if (...)
    \_Add(pNode->p1, pDatum);
else if (...)
    \_Add(pNode->p2, pDatum);
else if (...)
    \_Add(pNode->p3, pDatum);
else if (...)
    \_Add(pNode->p4, pDatum);
else if (...)
    \_Add(pNode->p5, pDatum);
else if (...)
    \_Add(pNode->p6, pDatum);
else if (...)
    \_Add(pNode->p7, pDatum);
else if (...)
    \_Add(pNode->p8, pDatum);
else
    assert(FALSE);

}

void Add( Datum *pDatum )
{
_Add(pRoot, pDatum);
}

---

Five birds are sitting on a fence. Three of them decide to fly off. How many are left?

[Hosam Aly Mahmoud]

Excuse me, but is your code somehow better than the following?

struct Node { Node * children[8]; } *pRoot = 0;

void _Add( Node *pNode, Datum* pDatum )
{
if ( 0 == pNode )
{
pNode = new Node;
// assign data

  memset( pNode->children, 8\*sizeof(Node\*) );
  return;

}
// else
if (...) { _Add(pNode->children[0], pDatum); return; }
// ...
}

Hosam Aly Mahmoud