path: root/hw4/src/boundedVolumeNode.cpp

/******************************************************************/
/* 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);
}