Jump to content
  • Advertisement
Sign in to follow this  
adam17

possible new octree format

This topic is 4615 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i was thinking of what space partitioning i should implement into my engine and i got to thinking of a way to optimize an octree structure. its possible its been done before. im not sure if its very feasible or not. ive been studying BSPs and octrees and came up with a traditional octree but instead it is a 4 level binary tree (including the node root). here is a visual representation:
sorry but the backslash does weird things...

      _____x_____
  (-)|           |(+)
   _-y_        _+y_
  |    |      |    |
 -z    +z    -z    +z
 | |   | |   | |   | |
n1 n2 n3 n4 n5 n6 n7 n8
this way if there are no objects on 1 half of a node, you can just set it to NULL. x (the root of the node) is the root of n1-n8 at the bottom, so it can be used as a tree structure. yay or nay?

Share this post


Link to post
Share on other sites
Advertisement
I'm thinking nay.

If the Octree is very sparse, maybe this will help. But in the average case
you have added between 3 and 6 new pointer indirections per octree level.
So, considering sections of the octree that are mostly filled (in say the XY plane, like a flat terrain) you still have to check both X,Y,and Z field pointers.
Say the +z pointers are invalid, you removed 4 pointer checks on node(i) and replaced it with 2 X pointers, 2 Y pointers and 4 Z pointer checks, losing any benifit since it took 4 more pointer checks.

Something makes me think that since you must already check obj.x vs node.center.x and in_fustum(node.center) in a standard octree, having to check if the +x pointer is valid, and then traversing it is just adding another step.


-edit:
If the binary tree is not pointer based, but array based.
there might be more of a benifit. Maybe even bitflag based, due to the small size of the tree. But you are still adding conditional jumps if the octree is not sparse.

Share this post


Link to post
Share on other sites
thanks i appreciate the input! im glad i got somebody elses opinion before i continued with it lol.

i havent seen any structure design for an octree yet. i understand the concept but thats it. well since im still working on my octree structure what is the best way of going about them?

create 8 pointers inside of a node?
create a std::array of 8 nodes? (im using c++ btw)

any other suggestions?

should i go for BSP instead since i have the tree idea down?

Share this post


Link to post
Share on other sites
Here's my octree's header file...


#ifndef Scream__Octree_h__
#define Scream__Octree_h__

#include "Math/Cube3.h"
#include "Math/Capsule3.h"
#include "Math/Point3.h"
#include "Math/Sphere3.h"
#include "Math/Frustum3.h"

#include <list>

namespace Scream
{;

class OctreeNode;

class ENGINE_EXPORT Octree
{
public:
friend OctreeNode;

class Item
{
public:
friend OctreeNode;
enum CapsuleType
{
Unknown,
Point,
Sphere,
LineSegment,
Capsule
};

Item( const Capsule3f & obj, void * const data );
~Item();
const Capsule3f & Bound() const;
CapsuleType BoundType() const;
void * Data() const;
void Remove();
void Move( const Capsule3f &bound );

private:

// disable copy, assignment.
Item();
Item( const Item & );
Item &operator=( const Item & );

Octree * _owner;
void * _data;
Capsule3f _bound;
CapsuleType _type;

friend Octree;

};

public:
typedef void QueryCB( const Item &, void *userdata );


Octree( const Cube3f &box );
~Octree();

Item * Insert( const Capsule3f &capsule, void * const data );
void Remove( Item * const item );
Item * Find( void *arg );

template< class Class > void Query( const Class &frusutm, QueryCB cb );
void Query( const Capsule3f &capsule, QueryCB cb, void *userdata = 0 );
void Query( const Frustum3f &frusutm, QueryCB cb, void *userdata = 0 );
void Query( QueryCB cb, void *userdata = 0 );

void Dump() const;
unsigned int Size() const;

void Move( Item * const item, const Capsule3f &bound );

private:
// this is the "maximum" number of items allowed in an
// octree before it tries to create children and becomes
// a non-leaf. obviously, there can be more than this
// number in the item list.
static const unsigned int MaxItems = 4;

typedef std::list< Item * > ItemList;
typedef ItemList::iterator ItemListIterator;
typedef ItemList::const_iterator ConstItemListIterator;

void DeleteChild( Octree *child );
void Insert( Item *item );
void AdjustSize( int value );
int Classify( const Item * const item ) const;
int Classify( const Point3f &point ) const;
int Classify( const Sphere3f &sphere ) const;
int Classify( const LineSegment3f &line ) const;
int Classify( const Capsule3f &capsule ) const;

Cube3f _box;
Octree * _child[ 8 ];
Octree * _parent;
ItemList _items;
bool _leaf;
int _size;
};

typedef Octree::Item OtItem;

} // namespace Scream

#endif // Scream__Octree_h__

Share this post


Link to post
Share on other sites
For now I would say "just make it work", using pointers or any structure you feel comfortable with. Later you can start optimizing if the need for it shows up. Fancy way is to "serialize" the tree. For shortness sake I stick with a binary tree, using a parent.node notation. It would then then be 0, 0.1, 0.2, 1.1, 1.2, 2.1, 2.2, etc.
The nice thing is that to navigate your tree you can use simple bitshifts on the index to move to the first child of you current node or it's parent. Meaning there won't be any child or parent pointers necessary, because a simple and fast bitshift tell's you where it is. Also makes collecting the leaves a lot easier, because you don't need to traverse the full tree. You know at which index the leaves are starting and can just sequentially read them out.

Downside: obviously only works for a complete tree. You can't just leave out empty branches and need to know the depth of the tree in advance. Usefull for maybe a terrain quadtree, messy or useless for a tree that is changing a lot. Might be wasting just far too much memory for an octree in a big world, where most of it would be empty, but still require all nodes down to the smallest cell size.

Share this post


Link to post
Share on other sites
What's the difference to a KD-tree, sounds the same to me?
Kd-tree:
Instead of splitting a volume on all 3 axises at the same time, only one axis is choosen at each tree node, either imlicit or explicit (needs to store the axis).
Optionally, instead of always splitting in the centre of the "cube", you can store the split point.
I.e:
struct TreeNode
{
float m_splitPos; // Optional, can always split in the centre of the cube
int m_splitAxis; // Optional, can used axis based on tree level
TreeNode* m_lower;
TreeNode* m_upper;
}

This type of tree has the benefit that it can be used in any dimension, I've got a templated version that I use for 3d and 2d partitioning, it's very nifty IMO.

Edit:
For reference I include my über template declaration for the tree, mainly to show how flexible this kind of tree can be.


template <class LeafType, int DimensionCount = 3, class ScalarType = float, class VectorType = ScalarType[DimensionCount], class NodeType = KdTreeNode<ScalarType, DimensionCount> > class KdTree;

// Sample usages:

KdTree<Leaf*> tree; // Simple
KdTree<Leaf*, 2, float, Vec2> rectTree; // Simple 2D tree with customized vector class
KdTree<Leaf*, 2, unsigned short> collisionMap; // Screen spaced 2d collision mask



It's a bit over the top but you can use float, int, even bytes or fixed point classes as your coordinate type. Works in any dimension, can have customized leaf-types, have customized tree node types (can compress data for some nodes).

Share this post


Link to post
Share on other sites
ok, ive been trying to build an octree structure. its been going ok until i start sorting the faces. i initialize an array of nodes like this->
node *c1[8];
now whenever i try to access it like this ->
c1[7]
there is an access violation. if you like here is my program (its short and a test bed) for my octree.



#include <iomanip>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
//#include "vector.h"

const int MAX_FACE = 1;
typedef float GLfloat;

GLfloat array[72] = {
1,1,1, 0.5f,0.5f,0.5f, 0.5f,0.1f,0.5f,
-1,1,1, -0.5f,0.5f,0.5f, -0.5f,0.1f,0.5f,
1,-1,1, 0.5f,-0.5f,0.5f, 0.5f,-0.1f,0.5f,
-1,-1,1, -0.5f,-0.5f,0.5f, -0.5f,-0.1f,0.5f,
1,1,-1, 0.5f,0.5f,-0.5f, 0.5f,0.1f,-0.5f,
-1,1,-1, -0.5f,0.5f,-0.5f, -0.5f,0.1f,-0.5f,
1,-1,-1, 0.5f,-0.5f,-0.5f, 0.5f,-0.1f,-0.5f,
-1,-1,-1, -0.5f,-0.5f,-0.5f -0.5f,-0.1f,-0.5f
};

struct octree
{
private:
struct node
{
GLfloat *vert_array;
int numFace;
node *c1[ 8 ];
node();
void add(int subnode, float a, float b, float c);
};

node root;
float x, y, z;
float w;

void findWidth(float *arr, int numFace);
void sort(node *arr, int numFace, float x, float y, float z);
//void output(node *leaf);
public:
octree();

void insert(float *arr, int numFace);
void output();
};

octree::node::node()
{
numFace=0;
vert_array=NULL;
}

void octree::node::add(int subnode, float a, float b, float c)
{
int pos = c1[subnode]->numFace;
c1[subnode]->numFace++;
c1[subnode]->vert_array = new GLfloat[3];
c1[subnode]->vert_array[pos] = a;
c1[subnode]->vert_array[pos+1]=b;
c1[subnode]->vert_array[pos+2]=c;
}

octree::octree()
{
w = -1;
}

void octree::findWidth(float *arr, int numFace)
{
float x, y, z, d;

for(int i=0; i<numFace*3; i++)
{
x = arr[3*i];
y = arr[3*i+1];
z = arr[3*i+2];
d = sqrt(x*x + y*y + z*z);

if(d>w)
{
w = d;
}
}
w = w*2;
w = ceil(w);
printf("width = %f\n", w);
}


void octree::sort(node *arr, int numFace, float x, float y, float z)
{
float a, b, c;
a = 0.0;
b = 0.0;
c = 0.0;
bool right, up, back;
right = true;
up = true;
back = true;

root.vert_array = new GLfloat[numFace*9];
for(int i=0; i<numFace*3; i++)
{
a = arr->vert_array[i*3];
b = arr->vert_array[i*3+1];
c = arr->vert_array[i*3+2];

if(a > x)
right = true;
else
right = false;

if(b > y)
up = true;
else
up = false;

if(c > z)
back = true;
else
back = false;

if(right)
{
if(up)
{
if(back)
arr->add(0, a, b, c);
if(!back)
arr->add(1, a, b, c);
}
if(!up)
{
if(back)
arr->add(2, a, b, c);
if(!back)
arr->add(3, a, b, c);
}
}
if(!right)
{
if(up)
{
if(back)
arr->add(4, a, b, c);
if(!back)
arr->add(5, a, b, c);
}
if(!up)
{
if(back)
arr->add(6, a, b, c);
if(!back)
arr->add(7, a, b, c);
}
}
}
}

void octree::insert(float *arr, int numFace)
{
findWidth(arr, numFace);

root.vert_array = new GLfloat[numFace*9];
for(int i=0; i<numFace*3; i++)
{
root.vert_array[i*3] = arr[i*3];
root.vert_array[i*3+1]=arr[i*3+1];
root.vert_array[i*3+2]=arr[i*3+2];

printf("v %f, %f, %f\n", root.vert_array[i*3], root.vert_array[i*3+1], root.vert_array[i*3+2]);
}

if(numFace > MAX_FACE)
sort(&root, numFace, 0, 0, 0);
}


void main()
{
octree tree;

int numVert = sizeof(array)/sizeof(GLfloat)/3;
int numFace = numVert/3;

printf("numVert %i\n", numVert);
printf("numFace %i\n", numFace);

tree.insert(array, numFace);

_getch();
}

Share this post


Link to post
Share on other sites
Quote:
Original post by adam17
i initialize an array of nodes like this->
node *c1[8];
now whenever i try to access it like this ->
c1[7]
there is an access violation.


Unless I missed a line, are you actually ever _creating_ the nodes behind your array of pointers?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!