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
|
/******************************************************************/
/* This file is part of the homework assignments for CSCI-427/527 */
/* at The College of William & Mary and authored by Pieter Peers. */
/* No part of this file, whether altered or in original form, can */
/* be distributed or used outside the context of CSCI-427/527 */
/* without consent of either the College of William & Mary or */
/* Pieter Peers. */
/******************************************************************/
#include <cassert>
#include <algorithm>
#include "boundedVolumeNode.h"
#include "random_number.h"
#include <iostream> // remove before submission
#include <stdio.h> // remove before submission
boundedVolumeNode::boundedVolumeNode(const std::vector<std::shared_ptr<const boundedPrimitive>>::iterator& start, const std::vector<std::shared_ptr<const boundedPrimitive>>::iterator& end)
: _left(nullptr), _right(nullptr), boundedPrimitive()
{
// HW4: Implement this.
// Constructs the bounding volume hierarchy. You can alter the order of elements between
// the 'start' and 'end' iterator. The _left and _right node can either be a boundedPrimitive
// or a new boundedVolume node (see _left and _right below respectively for an example of both).
// Don't forget to initialize the bounding box (_bb). Average time complexity: O(NlogN).
// Modifies: _left, _right, and _bb.
// Returns: nothing.
// create bounding box _bb for the incoming vector of primitives
_bb = boundingBox();
for (auto itr = start; itr != end; itr++) { _bb += (**itr).boundingbox(); }
// select random axis to work with
unsigned int axis = random_int(2);
// terminate recursion with final remaining primitives
switch(std::distance(start, end)) {
case 0: return; // no elements remain
case 1: _left = *start; return; // single element remains; chose _left node
case 2: { // two elements remain; sort and set
if (getAxis(*start, axis) > getAxis(*(end - 1), axis)) {
std::swap(*start, *(end - 1));
}
_left = *start;
_right = *(end - 1);
return;
}
}
// perform quicksort-style reordering of vector
auto i = start;
auto j = end - 1;
// select random pivot
vec3d::value_type pivot = getAxis(*(start + random_int(std::distance(start, end) - 1)), axis);
while (i < j) {
while (getAxis(*j, axis) > pivot && j > i) { j--; }
while (getAxis(*i, axis) < pivot && i <= j) { i++; }
if (i < j) {
std::swap(*i, *j);
i++;
}
}
// recurse upon remaining elements
_right = std::shared_ptr<const boundedPrimitive>(new boundedVolumeNode(j, end));
_left = std::shared_ptr<const boundedPrimitive>(new boundedVolumeNode(start, i));
// Done.
}
vec3d::value_type boundedVolumeNode::getAxis(const std::shared_ptr<const boundedPrimitive>& primitive, unsigned int axis) {
switch(axis) {
case 0: return (*primitive).boundingbox().center().x;
case 1: return (*primitive).boundingbox().center().y;
case 2: return (*primitive).boundingbox().center().z;
}
}
intersectionPoint boundedVolumeNode::intersect(const ray& r) const
{
// HW4: Implement this
// Intersect the bounding volume hierarchy, and return the nearest intersection point.
// You will need to explore both _left and _right. Average time complexity: O(logN).
intersectionPoint ip, ip_left, ip_right;
ip = intersectionPoint();
if (!hitBoundingBox(r)) { return ip; }
if (_left && _left->hitBoundingBox(r)) { ip_left = _left->intersect(r); }
if (_right && _right->hitBoundingBox(r)) { ip_right = _right->intersect(r); }
return (ip_left < ip_right ? ip_left : ip_right);
}
|
