1 files changed, 97 insertions, 0 deletions
diff --git a/hw4/src/boundedVolumeNode.cpp b/hw4/src/boundedVolumeNode.cpp
new file mode 100644
index 0000000..fd143bb
--- /dev/null
+++ b/hw4/src/boundedVolumeNode.cpp
@@ -0,0 +1,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);
+}