/*****************************************************************************************
 *                                                                                       *
 * OpenSpace                                                                             *
 *                                                                                       *
 * Copyright (c) 2014                                                                    *
 *                                                                                       *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this  *
 * software and associated documentation files (the "Software"), to deal in the Software *
 * without restriction, including without limitation the rights to use, copy, modify,    *
 * merge, publish, distribute, sublicense, and/or sell copies of the Software, and to    *
 * permit persons to whom the Software is furnished to do so, subject to the following   *
 * conditions:                                                                           *
 *                                                                                       *
 * The above copyright notice and this permission notice shall be included in all copies *
 * or substantial portions of the Software.                                              *
 *                                                                                       *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,   *
 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A         *
 * PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT    *
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF  *
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE  *
 * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                                         *
 ****************************************************************************************/
// Math defintions

#define TraverseBSTLimit 50
#define TraverseOctreeLimit 50

// TSP settings
uniform int   numValuesPerNode = 0;
uniform int   numOTNodes       = 0;
uniform int   timestep         = 0;

layout( std140, binding=0 ) buffer tspBuffer
{
  int tsp[ ];
};


#define   M_E       2.7182818284590452354
#define   M_LOG2E     1.4426950408889634074   /* log_2 e */
#define   M_LOG10E    0.43429448190325182765  /* log_10 e */
#define   M_LN2     0.69314718055994530942  /* log_e 2 */
#define   M_LN10    2.30258509299404568402  /* log_e 10 */
#define   M_PI      3.14159265358979323846  /* pi */
#define   M_PI_2    1.57079632679489661923  /* pi/2 */
#define   M_PI_4    0.78539816339744830962  /* pi/4 */
#define   M_1_PI    0.31830988618379067154  /* 1/pi */
#define   M_2_PI    0.63661977236758134308  /* 2/pi */
#define   M_2_SQRTPI  1.12837916709551257390  /* 2/sqrt(pi) */
#define   M_SQRT2   1.41421356237309504880  /* sqrt(2) */
#define   M_SQRT1_2   0.70710678118654752440  /* 1/sqrt(2) */
#define   M_SQRT1_3 0.57735026919     /* 1/sqrt(3) */

vec3 CartesianToSpherical(vec3 _cartesian) {
  // Put cartesian in [-1..1] range first
  vec3 cartesian = vec3(-1.0,-1.0,-1.0) + _cartesian * 2.0f;
  
  float r = length(cartesian);
  float theta, phi;

  if (r == 0.0) {
    theta = phi = 0.0;
  } else {
    theta = acos(cartesian.z/r) / M_PI;
    phi = (M_PI + atan(cartesian.y, cartesian.x)) / (2.0*M_PI );
  }
  r *= M_SQRT1_3;
  // r = r / sqrt(3.0f);
  
  // Sampler ignores w component
  return vec3(r, theta, phi);
}

// Return index to the octree root (same index as BST root at that OT node)
int OctreeRootNodeIndex() {
  return 0;
}

// Return index to left BST child (low timespan)
int LeftBST(int _bstNodeIndex, bool _bstRoot) {
  // If the BST node is a root, the child pointer is used for the OT. 
  // The child index is next to the root.
  // If not root, look up in TSP structure.
  if (_bstRoot) {
    return (_bstNodeIndex + numOTNodes);
    //return _bstNodeIndex + 1;
  } else {
    return tsp[uint(_bstNodeIndex*numValuesPerNode + 1)];
  }
}

// Return index to right BST child (high timespan)
int RightBST(int _bstNodeIndex, bool _bstRoot) {
  if (_bstRoot) {
    return (_bstNodeIndex + numOTNodes*2);
  } else {
    return (tsp[uint(_bstNodeIndex*numValuesPerNode + 1)] + numOTNodes);
  }
}

// Return child node index given a BST node, a time span and a timestep
// Updates timespan
int ChildNodeIndex(int _bstNodeIndex, 
                   inout int _timespanStart,
                   inout int  _timespanEnd,
                   bool _bstRoot) {
  // Choose left or right child
  int middle = _timespanStart + (_timespanEnd - _timespanStart)/2; 
  if (timestep <= middle) {
    // Left subtree
    _timespanEnd = middle;
    return LeftBST(_bstNodeIndex, _bstRoot);
  } else {
    // Right subtree
    _timespanStart = middle+1;
    return RightBST(_bstNodeIndex, _bstRoot);
  }
}

// Return the brick index that a BST node represents
int BrickIndex(int _bstNodeIndex) {
    return tsp[uint(_bstNodeIndex*numValuesPerNode + 0)];
}

// Checks if a BST node is a leaf ot not
bool IsBSTLeaf(int _bstNodeIndex, bool _bstRoot) {
  if (_bstRoot) return false;
    return (tsp[uint(_bstNodeIndex*numValuesPerNode + 1)] == -1);
}

// Checks if an OT node is a leaf or not
bool IsOctreeLeaf(int _otNodeIndex) {
    // CHILD_INDEX is at offset 1, and -1 represents leaf
    return (tsp[uint(_otNodeIndex*numValuesPerNode + 1)] == -1);
}

// Return OT child index given current node and child number (0-7)
int OTChildIndex(int _otNodeIndex, int _child) {
    int firstChild = tsp[uint(_otNodeIndex*numValuesPerNode+1)];
    return firstChild + _child;
}

float TemporalError(int _bstNodeIndex) {
  return float(tsp[uint(_bstNodeIndex*numValuesPerNode + 3)]);
}

float SpatialError(int _bstNodeIndex) {
  return float(tsp[uint(_bstNodeIndex*numValuesPerNode + 2)]);
}

// Given a point, a box mid value and an offset, return enclosing child
int EnclosingChild(vec3 _P, float _boxMid, vec3 _offset) {
  if (_P.x < _boxMid+_offset.x) {
    if (_P.y < _boxMid+_offset.y) {
      if (_P.z < _boxMid+_offset.z) {
        return 0;
      } else {
        return 4;
      }
    } else {
      if (_P.z < _boxMid+_offset.z) {
        return 2;
      } else {
        return 6;
      }
    }
  } else {
    if (_P.y < _boxMid+_offset.y) {
      if (_P.z < _boxMid+_offset.z) {
        return 1;
      } else {
        return 5;
      }
    } else {
      if (_P.z < _boxMid+_offset.z) {
        return 3;
      } else {
        return 7;
      }
    }
  }
}

void UpdateOffset(inout vec3 _offset, float _boxDim, int _child) {
  if (_child == 0) {
    // do nothing
  } else if (_child == 1) {
    _offset.x += _boxDim;
  } else if (_child == 2) {
    _offset.y += _boxDim;
  } else if (_child == 3) {
    _offset.x += _boxDim;
    _offset.y += _boxDim;
  } else if (_child == 4) {
    _offset.z += _boxDim;
  } else if (_child == 5) {
    _offset.x += _boxDim;
    _offset.z += _boxDim;
  } else if (_child == 6) {
    _offset.y += _boxDim;
    _offset.z += _boxDim;
  } else if (_child == 7) {
    _offset += vec3(_boxDim,_boxDim,_boxDim);
  }
}