PathTracing/KDTree.cpp at master · gtremper/PathTracing · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/* Implementation of KDTree acceleration structure */

#include <iostream>
#include <vector>

#include "Shapes.h"
#include "Intersection.h"
#include "KDTree.h"

using namespace std;

#define TREELIMIT 5
#define EPSILON 0.000001

/***  TREENODE  ***/
struct ShapeSorter {
	ShapeSorter(int ax){this->axis = ax;}
	bool operator() (Shape* i, Shape* j) {
		return i->aabb.center[axis] < j->aabb.center[axis];
	}
	int axis;
};

TreeNode::TreeNode(vector<Shape*>& prims, AABB& bigBox){
	this->aabb = bigBox;

	vec3 diff = bigBox.aabbmax - bigBox.aabbmin;
	if (diff[0]>diff[1] && diff[0]>diff[1]){
		this->axis = 0;
	} else if (diff[1]>diff[2]){
		this->axis = 1;
	} else {
		this->axis = 2;
	}

	ShapeSorter s(axis);
	sort(prims.begin(), prims.end(),s);
	double split = prims[prims.size()/2]->aabb.center[axis];

	vector<Shape*> leftPrims;
	vector<Shape*>::iterator it=prims.begin();
	for(;it!=prims.end(); ++it){
		if((*it)->aabb.aabbmin[axis]<(split+EPSILON)){
			leftPrims.push_back(*it);
		}
	}

	vector<Shape*> rightPrims;
	for(it=prims.begin(); it!=prims.end(); ++it){
		if((*it)->aabb.aabbmax[axis]>(split-EPSILON)){
			rightPrims.push_back(*it);
		}
	}

	unsigned int threshold = (prims.size()/TREELIMIT) * (2*TREELIMIT-1);
	unsigned int rsize = rightPrims.size();
	unsigned int lsize = leftPrims.size();
	bool above_tresh = (lsize + rsize) > threshold;

	if( above_tresh || prims.size()==lsize || prims.size()==rsize || prims.size()<=TREELIMIT){
		left = NULL;
		right = NULL;
		primatives = prims;
	}else{
		AABB leftAABB = AABB(aabb);
		leftAABB.aabbmax[axis] = split;

		AABB rightAABB = AABB(aabb);
		rightAABB.aabbmin[axis] = split;

		left = new TreeNode(leftPrims, leftAABB);
		right = new TreeNode(rightPrims, rightAABB);
	}

}

TreeNode::~TreeNode(){
	if(left){
		delete left;
		delete right;
	}
}

Intersection TreeNode::intersect(Ray& ray){
	if(!left){
		return Intersection(primatives,ray);
	}

	double hitLeft = left->aabb.intersect(ray);
	double hitRight = right->aabb.intersect(ray);

	if(!hitLeft && !hitRight) return Intersection();

	if (!hitLeft) {
		return right->intersect(ray);
	}
	if (!hitRight) {
		return left->intersect(ray);
	}

	Intersection hit;
	if (hitLeft > hitRight){
		hit = right->intersect(ray);
		if (!hit.primative){
			hit = left->intersect(ray);
		}
		return hit;
	} else {
		hit = left->intersect(ray);
		if (!hit.primative){
			hit = right->intersect(ray);
		}
		return hit;
	}

}