Last active
February 16, 2017 09:56
-
-
Save nilspin/f69e7031e305cbe1d29af070f53c05c4 to your computer and use it in GitHub Desktop.
Simple Octree class
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef OCTREE_H | |
#define OCTREE_H | |
#include <memory> | |
#include <iostream> | |
#include <cstdint> | |
#include <bitset> | |
#include <glm/glm.hpp> | |
using namespace glm; | |
using namespace std; | |
float minCellWidth = 0.0001; | |
class octreeNode : std::enable_shared_from_this<octreeNode> | |
{ | |
private: | |
octreeNode* root; | |
octreeNode* children[8]; | |
octreeNode* parent; | |
vec3 center; | |
float halfSize; | |
vec3 data; //actual point stored at this grid cell | |
int level = 0; | |
int maxLevel = 10; | |
bool split() | |
{ | |
float childWidth = 0.5*halfSize; | |
if(childWidth < minCellWidth) | |
{ | |
cout<<"Point could not be added, grid cell size is too small. skipping.\n"; | |
return false; | |
} | |
for(uint8_t i = 0;i<=7;++i) | |
{ | |
vec3 childCenter; | |
uint8_t tempCode; | |
switch(i) | |
{ | |
case 0: childCenter = center + vec3(-childWidth, -childWidth, -childWidth); | |
break; | |
case 1: childCenter = center + vec3(-childWidth, -childWidth, childWidth); | |
break; | |
case 2: childCenter = center + vec3(-childWidth, childWidth, -childWidth); | |
break; | |
case 3: childCenter = center + vec3(-childWidth, childWidth, childWidth); | |
break; | |
case 4: childCenter = center + vec3(childWidth, -childWidth, -childWidth); | |
break; | |
case 5: childCenter = center + vec3(childWidth, -childWidth, childWidth); | |
break; | |
case 6: childCenter = center + vec3(childWidth, childWidth, -childWidth); | |
break; | |
case 7: childCenter = center + vec3(childWidth, childWidth, childWidth); | |
break; | |
} | |
children[i] = new octreeNode(this, level+1, childCenter, halfSize*0.5); | |
children[i]->code = i; | |
} | |
isLeaf = false; | |
return true; | |
}; | |
void insert(octreeNode* ptr,vec3 point) | |
{ | |
if(!ptr->isLeaf) | |
{ | |
octreeNode* child = ptr->children[getOctantContainingPoint(point)]; | |
child->insert(child, point); | |
} | |
else | |
{ | |
//if leaf node | |
if(!ptr->isDataSet) | |
{ | |
ptr->setData(point); | |
} | |
else | |
{ | |
//if leaf already contains data then split this node and | |
//add insert recursively | |
vec3 oldData = data; | |
ptr->isDataSet = false; | |
if(!ptr->split()) return; | |
//ptr to node where oldData is to be inserted | |
octreeNode* child1 = ptr->children[getOctantContainingPoint(oldData)]; | |
//ptr to node where new point is to be inserted | |
octreeNode* child2 = ptr->children[getOctantContainingPoint(point)]; | |
std::cout<<"Restoring ("<<oldData.x<<" "<<oldData.y<<" "<<oldData.z<<") to node "<<std::bitset<4>(child1->code)<<"\n"; | |
child1->insert(child1, oldData); | |
std::cout<<"Adding ("<<point.x<<" "<<point.y<<" "<<point.z<<") to node "<<std::bitset<4>(child2->code)<<"\n"; | |
child2->insert(child2, point); | |
} | |
} | |
}; | |
uint8_t getOctantContainingPoint(vec3 point) | |
{ | |
uint8_t code = 0; | |
if(point.x > center.x) code|=4; | |
if(point.y > center.y) code|=2; | |
if(point.z > center.z) code|=1; | |
return code; | |
}; | |
public: | |
bool isLeaf = true; | |
bool isDataSet = false; | |
uint8_t code; | |
octreeNode() | |
{ | |
root = this; | |
parent = nullptr; | |
code = 0; | |
}; | |
octreeNode(octreeNode* p, int l, vec3 c, float hs) | |
{ | |
parent = p; | |
center = c; | |
halfSize = hs; | |
level = l; | |
isLeaf = true; | |
}; | |
void insert(vec3 point) | |
{ | |
insert(this, point); | |
}; | |
void setData(vec3 p) | |
{ | |
data = p; | |
isDataSet = true; | |
}; | |
}; | |
#endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment