Created
February 16, 2017 13:29
-
-
Save nilspin/2e81f524a77e1fdc850404dd632bcdab to your computer and use it in GitHub Desktop.
octree implementation using only references, not working due to forward declaration.
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 <vector> | |
#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; | |
octreeNode& self(){return *this;}; | |
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(self(), level+1, childCenter, childWidth); | |
children[i].code = i; | |
} | |
isLeaf = false; | |
return true; | |
}; | |
void insert(octreeNode& ptr,vec3 point) | |
{ | |
std::cout<<"Current level "<<level<<"\n"; | |
if(!ptr.isLeaf) | |
{ | |
octreeNode child = ptr.children[getOctantContainingPoint(point)]; | |
child.insert(std::ref(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(std::ref(child1), oldData); | |
std::cout<<"Adding ("<<point.x<<" "<<point.y<<" "<<point.z<<") to node "<<std::bitset<4>(child2.code)<<"\n"; | |
child2.insert(std::ref(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 = self(); | |
parent = self(); | |
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(self(), 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