Sign in to follow this  
adam17

possible new octree format

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
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
instead of a NxNxN octree you could use a slightly modified model that covers only those dimensons that are really filled with content

e.g.: in many egoshooters you have large and pretty flat maps that behave like this

6x6x(1-2) you can spare 2 third of the nodes


you could create a quadtree fill all the nodes on the lowest level and remove the empty once

then on each gridpoint(where the quadtree nodes touch the neighbour nodes you calculate the z height +add a offset for flying objects

then splitt these nodes in the center of the z direction and perform a bottom up merge

3D Nodes -> 2d quadtree nodes
2d quadtree nodes -> ....->2d quadtree rootnode

this works perfect for fps games and will be implemented into my engine

in conjunction with predicates(function objects) that allow the customization of culling, you have a really powerful tool if implemented properly

you can also add clipping portals that clip the back of a hill, just consider them as quads that represent a faked near clipping plane

I also consider implementing some sort of indoor octree:
The mapper places a hull around the indoor areas and the geometry inside the hull will the handled by a seperate octree that supports occlusion culling

and it will be linked to the outdoor grad via portals that are cube spanning the bounding volume(the one the mapper places) of the interior

i think this is an easy and pretty powerful way to perform decent culling without much of an effort




Share this post


Link to post
Share on other sites
Quote:
Original post by Trienco
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?


nope. i figured it would create them by itself. i was never really versed in arrays inside of structs and classes. would you care to enlighten me?

thanks

Share this post


Link to post
Share on other sites
Quote:
Original post by adam17
nope. i figured it would create them by itself. i was never really versed in arrays inside of structs and classes. would you care to enlighten me?


You are creating an array of pointers with:
type* name[x]
That will allocate space for x pointers but just like
int* x
it will NOT create actual data behind the pointer (that would be plain horrible, you usually want a pointer to point at already existing data).

If you want an array of type, it's simply
type name[x] (note that type needs to have a default constructor or no instances can be created)

If you don't know the size in advance (no constant)
It's
type* name = new type[x] (but don't forget to delete[] name when you don't need it anymore)

Short: pointers will always be 4byte long memory addresses (well, size might vary with platform) with nothing behind it until you point them at something yourself (ie. assign the address of something).

c1[7] isn't where it goes wrong. It goes wrong when you dereference this pointer because it's going nowhere (or rather: to some random address, though debug builds tend to initialize them with some value representing "not initialized".. for example if a pointer has the hex-value baadf00d it's not a good sign.

Share this post


Link to post
Share on other sites
why don t you use std:vector and std:auto_prt ?

this deletes your objects when the vector's destructor deletes the auto_ptr objects and you get rid of memory leaks


on the other hand, the memory will be released anyways if you exit the program at least on linux

Share this post


Link to post
Share on other sites
im using the arrays for the pointers to the leafs of the quadtree. is it possible to use std::vector for it? i assumed it would be easier than making 4 seperate pointers like n0, n1, n2, etc. or am i wrong?

Share this post


Link to post
Share on other sites
Quote:
Original post by Basiror
why don t you use std:vector and std:auto_prt ?

this deletes your objects when the vector's destructor deletes the auto_ptr objects and you get rid of memory leaks
Woah, hold on a minute - an auto_ptr is not safe to put in a container!

Before using auto_ptr, read this,
http://www.gotw.ca/gotw/025.htm
(Herb Sutter never lies)

Then check out Boost's shared_ptr instead.
http://www.boost.org/

Quote:
Original post by Basiror
on the other hand, the memory will be released anyways if you exit the program at least on linux
Which is of course a robust and elegant solution! ;-)

Also, if you're leaking every frame, then the whole PC will slow down to a crawl after a few minutes.

Hope this helps,

Pete

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this