Skip to content

Instantly share code, notes, and snippets.

@nilspin
Created February 16, 2017 13:29
Show Gist options
  • Save nilspin/2e81f524a77e1fdc850404dd632bcdab to your computer and use it in GitHub Desktop.
Save nilspin/2e81f524a77e1fdc850404dd632bcdab to your computer and use it in GitHub Desktop.
octree implementation using only references, not working due to forward declaration.
#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