sorry but the backslash does weird things...
_____x_____
(-)| |(+)
_-y_ _+y_
| | | |
-z +z -z +z
| | | | | | | |
n1 n2 n3 n4 n5 n6 n7 n8
possible new octree format
Author
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:
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.
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.
Author
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?
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?
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__
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.
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.
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.
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).
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; // SimpleKdTree<Leaf*, 2, float, Vec2> rectTree; // Simple 2D tree with customized vector classKdTree<Leaf*, 2, unsigned short> collisionMap; // Screen spaced 2d collision maskIt'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).
Author
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];c1[7]#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();}Quote:Original post by adam17
i initialize an array of nodes like this->now whenever i try to access it like this ->node *c1[8];there is an access violation.c1[7]
Unless I missed a line, are you actually ever _creating_ the nodes behind your array of pointers?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
