(function (global, factory) {
  if (typeof define === "function" && define.amd) {
    define(["exports", "three", "../math/Capsule.js"], factory);
  } else if (typeof exports !== "undefined") {
    factory(exports, require("three"), require("../math/Capsule.js"));
  } else {
    var mod = {
      exports: {}
    };
    factory(mod.exports, global.three, global.Capsule);
    global.Octree = mod.exports;
  }
})(typeof globalThis !== "undefined" ? globalThis : typeof self !== "undefined" ? self : this, function (_exports, _three, _Capsule) {
  "use strict";

  Object.defineProperty(_exports, "__esModule", {
    value: true
  });
  _exports.Octree = void 0;

  function _slicedToArray(arr, i) { return _arrayWithHoles(arr) || _iterableToArrayLimit(arr, i) || _unsupportedIterableToArray(arr, i) || _nonIterableRest(); }

  function _nonIterableRest() { throw new TypeError("Invalid attempt to destructure non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method."); }

  function _unsupportedIterableToArray(o, minLen) { if (!o) return; if (typeof o === "string") return _arrayLikeToArray(o, minLen); var n = Object.prototype.toString.call(o).slice(8, -1); if (n === "Object" && o.constructor) n = o.constructor.name; if (n === "Map" || n === "Set") return Array.from(o); if (n === "Arguments" || /^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)) return _arrayLikeToArray(o, minLen); }

  function _arrayLikeToArray(arr, len) { if (len == null || len > arr.length) len = arr.length; for (var i = 0, arr2 = new Array(len); i < len; i++) { arr2[i] = arr[i]; } return arr2; }

  function _iterableToArrayLimit(arr, i) { var _i = arr == null ? null : typeof Symbol !== "undefined" && arr[Symbol.iterator] || arr["@@iterator"]; if (_i == null) return; var _arr = []; var _n = true; var _d = false; var _s, _e; try { for (_i = _i.call(arr); !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"] != null) _i["return"](); } finally { if (_d) throw _e; } } return _arr; }

  function _arrayWithHoles(arr) { if (Array.isArray(arr)) return arr; }

  function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }

  function _defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } }

  function _createClass(Constructor, protoProps, staticProps) { if (protoProps) _defineProperties(Constructor.prototype, protoProps); if (staticProps) _defineProperties(Constructor, staticProps); Object.defineProperty(Constructor, "prototype", { writable: false }); return Constructor; }

  var _v1 = new _three.Vector3();

  var _v2 = new _three.Vector3();

  var _plane = new _three.Plane();

  var _line1 = new _three.Line3();

  var _line2 = new _three.Line3();

  var _sphere = new _three.Sphere();

  var _capsule = new _Capsule.Capsule();

  var Octree = /*#__PURE__*/function () {
    function Octree(box) {
      _classCallCheck(this, Octree);

      this.triangles = [];
      this.box = box;
      this.subTrees = [];
    }

    _createClass(Octree, [{
      key: "addTriangle",
      value: function addTriangle(triangle) {
        if (!this.bounds) this.bounds = new _three.Box3();
        this.bounds.min.x = Math.min(this.bounds.min.x, triangle.a.x, triangle.b.x, triangle.c.x);
        this.bounds.min.y = Math.min(this.bounds.min.y, triangle.a.y, triangle.b.y, triangle.c.y);
        this.bounds.min.z = Math.min(this.bounds.min.z, triangle.a.z, triangle.b.z, triangle.c.z);
        this.bounds.max.x = Math.max(this.bounds.max.x, triangle.a.x, triangle.b.x, triangle.c.x);
        this.bounds.max.y = Math.max(this.bounds.max.y, triangle.a.y, triangle.b.y, triangle.c.y);
        this.bounds.max.z = Math.max(this.bounds.max.z, triangle.a.z, triangle.b.z, triangle.c.z);
        this.triangles.push(triangle);
        return this;
      }
    }, {
      key: "calcBox",
      value: function calcBox() {
        this.box = this.bounds.clone(); // offset small ammount to account for regular grid

        this.box.min.x -= 0.01;
        this.box.min.y -= 0.01;
        this.box.min.z -= 0.01;
        return this;
      }
    }, {
      key: "split",
      value: function split(level) {
        if (!this.box) return;
        var subTrees = [];

        var halfsize = _v2.copy(this.box.max).sub(this.box.min).multiplyScalar(0.5);

        for (var x = 0; x < 2; x++) {
          for (var y = 0; y < 2; y++) {
            for (var z = 0; z < 2; z++) {
              var box = new _three.Box3();

              var v = _v1.set(x, y, z);

              box.min.copy(this.box.min).add(v.multiply(halfsize));
              box.max.copy(box.min).add(halfsize);
              subTrees.push(new Octree(box));
            }
          }
        }

        var triangle;

        while (triangle = this.triangles.pop()) {
          for (var i = 0; i < subTrees.length; i++) {
            if (subTrees[i].box.intersectsTriangle(triangle)) {
              subTrees[i].triangles.push(triangle);
            }
          }
        }

        for (var _i = 0; _i < subTrees.length; _i++) {
          var len = subTrees[_i].triangles.length;

          if (len > 8 && level < 16) {
            subTrees[_i].split(level + 1);
          }

          if (len !== 0) {
            this.subTrees.push(subTrees[_i]);
          }
        }

        return this;
      }
    }, {
      key: "build",
      value: function build() {
        this.calcBox();
        this.split(0);
        return this;
      }
    }, {
      key: "getRayTriangles",
      value: function getRayTriangles(ray, triangles) {
        for (var i = 0; i < this.subTrees.length; i++) {
          var subTree = this.subTrees[i];
          if (!ray.intersectsBox(subTree.box)) continue;

          if (subTree.triangles.length > 0) {
            for (var j = 0; j < subTree.triangles.length; j++) {
              if (triangles.indexOf(subTree.triangles[j]) === -1) triangles.push(subTree.triangles[j]);
            }
          } else {
            subTree.getRayTriangles(ray, triangles);
          }
        }

        return triangles;
      }
    }, {
      key: "triangleCapsuleIntersect",
      value: function triangleCapsuleIntersect(capsule, triangle) {
        triangle.getPlane(_plane);
        var d1 = _plane.distanceToPoint(capsule.start) - capsule.radius;
        var d2 = _plane.distanceToPoint(capsule.end) - capsule.radius;

        if (d1 > 0 && d2 > 0 || d1 < -capsule.radius && d2 < -capsule.radius) {
          return false;
        }

        var delta = Math.abs(d1 / (Math.abs(d1) + Math.abs(d2)));

        var intersectPoint = _v1.copy(capsule.start).lerp(capsule.end, delta);

        if (triangle.containsPoint(intersectPoint)) {
          return {
            normal: _plane.normal.clone(),
            point: intersectPoint.clone(),
            depth: Math.abs(Math.min(d1, d2))
          };
        }

        var r2 = capsule.radius * capsule.radius;

        var line1 = _line1.set(capsule.start, capsule.end);

        var lines = [[triangle.a, triangle.b], [triangle.b, triangle.c], [triangle.c, triangle.a]];

        for (var i = 0; i < lines.length; i++) {
          var line2 = _line2.set(lines[i][0], lines[i][1]);

          var _capsule$lineLineMini = capsule.lineLineMinimumPoints(line1, line2),
              _capsule$lineLineMini2 = _slicedToArray(_capsule$lineLineMini, 2),
              point1 = _capsule$lineLineMini2[0],
              point2 = _capsule$lineLineMini2[1];

          if (point1.distanceToSquared(point2) < r2) {
            return {
              normal: point1.clone().sub(point2).normalize(),
              point: point2.clone(),
              depth: capsule.radius - point1.distanceTo(point2)
            };
          }
        }

        return false;
      }
    }, {
      key: "triangleSphereIntersect",
      value: function triangleSphereIntersect(sphere, triangle) {
        triangle.getPlane(_plane);
        if (!sphere.intersectsPlane(_plane)) return false;
        var depth = Math.abs(_plane.distanceToSphere(sphere));
        var r2 = sphere.radius * sphere.radius - depth * depth;

        var plainPoint = _plane.projectPoint(sphere.center, _v1);

        if (triangle.containsPoint(sphere.center)) {
          return {
            normal: _plane.normal.clone(),
            point: plainPoint.clone(),
            depth: Math.abs(_plane.distanceToSphere(sphere))
          };
        }

        var lines = [[triangle.a, triangle.b], [triangle.b, triangle.c], [triangle.c, triangle.a]];

        for (var i = 0; i < lines.length; i++) {
          _line1.set(lines[i][0], lines[i][1]);

          _line1.closestPointToPoint(plainPoint, true, _v2);

          var d = _v2.distanceToSquared(sphere.center);

          if (d < r2) {
            return {
              normal: sphere.center.clone().sub(_v2).normalize(),
              point: _v2.clone(),
              depth: sphere.radius - Math.sqrt(d)
            };
          }
        }

        return false;
      }
    }, {
      key: "getSphereTriangles",
      value: function getSphereTriangles(sphere, triangles) {
        for (var i = 0; i < this.subTrees.length; i++) {
          var subTree = this.subTrees[i];
          if (!sphere.intersectsBox(subTree.box)) continue;

          if (subTree.triangles.length > 0) {
            for (var j = 0; j < subTree.triangles.length; j++) {
              if (triangles.indexOf(subTree.triangles[j]) === -1) triangles.push(subTree.triangles[j]);
            }
          } else {
            subTree.getSphereTriangles(sphere, triangles);
          }
        }
      }
    }, {
      key: "getCapsuleTriangles",
      value: function getCapsuleTriangles(capsule, triangles) {
        for (var i = 0; i < this.subTrees.length; i++) {
          var subTree = this.subTrees[i];
          if (!capsule.intersectsBox(subTree.box)) continue;

          if (subTree.triangles.length > 0) {
            for (var j = 0; j < subTree.triangles.length; j++) {
              if (triangles.indexOf(subTree.triangles[j]) === -1) triangles.push(subTree.triangles[j]);
            }
          } else {
            subTree.getCapsuleTriangles(capsule, triangles);
          }
        }
      }
    }, {
      key: "sphereIntersect",
      value: function sphereIntersect(sphere) {
        _sphere.copy(sphere);

        var triangles = [];
        var result,
            hit = false;
        this.getSphereTriangles(sphere, triangles);

        for (var i = 0; i < triangles.length; i++) {
          if (result = this.triangleSphereIntersect(_sphere, triangles[i])) {
            hit = true;

            _sphere.center.add(result.normal.multiplyScalar(result.depth));
          }
        }

        if (hit) {
          var collisionVector = _sphere.center.clone().sub(sphere.center);

          var depth = collisionVector.length();
          return {
            normal: collisionVector.normalize(),
            depth: depth
          };
        }

        return false;
      }
    }, {
      key: "capsuleIntersect",
      value: function capsuleIntersect(capsule) {
        _capsule.copy(capsule);

        var triangles = [];
        var result,
            hit = false;
        this.getCapsuleTriangles(_capsule, triangles);

        for (var i = 0; i < triangles.length; i++) {
          if (result = this.triangleCapsuleIntersect(_capsule, triangles[i])) {
            hit = true;

            _capsule.translate(result.normal.multiplyScalar(result.depth));
          }
        }

        if (hit) {
          var collisionVector = _capsule.getCenter(new _three.Vector3()).sub(capsule.getCenter(_v1));

          var depth = collisionVector.length();
          return {
            normal: collisionVector.normalize(),
            depth: depth
          };
        }

        return false;
      }
    }, {
      key: "rayIntersect",
      value: function rayIntersect(ray) {
        if (ray.direction.length() === 0) return;
        var triangles = [];
        var triangle,
            position,
            distance = 1e100;
        this.getRayTriangles(ray, triangles);

        for (var i = 0; i < triangles.length; i++) {
          var result = ray.intersectTriangle(triangles[i].a, triangles[i].b, triangles[i].c, true, _v1);

          if (result) {
            var newdistance = result.sub(ray.origin).length();

            if (distance > newdistance) {
              position = result.clone().add(ray.origin);
              distance = newdistance;
              triangle = triangles[i];
            }
          }
        }

        return distance < 1e100 ? {
          distance: distance,
          triangle: triangle,
          position: position
        } : false;
      }
    }, {
      key: "fromGraphNode",
      value: function fromGraphNode(group) {
        var _this = this;

        group.updateWorldMatrix(true, true);
        group.traverse(function (obj) {
          if (obj.isMesh === true) {
            var geometry,
                isTemp = false;

            if (obj.geometry.index !== null) {
              isTemp = true;
              geometry = obj.geometry.toNonIndexed();
            } else {
              geometry = obj.geometry;
            }

            var positionAttribute = geometry.getAttribute('position');

            for (var i = 0; i < positionAttribute.count; i += 3) {
              var v1 = new _three.Vector3().fromBufferAttribute(positionAttribute, i);
              var v2 = new _three.Vector3().fromBufferAttribute(positionAttribute, i + 1);
              var v3 = new _three.Vector3().fromBufferAttribute(positionAttribute, i + 2);
              v1.applyMatrix4(obj.matrixWorld);
              v2.applyMatrix4(obj.matrixWorld);
              v3.applyMatrix4(obj.matrixWorld);

              _this.addTriangle(new _three.Triangle(v1, v2, v3));
            }

            if (isTemp) {
              geometry.dispose();
            }
          }
        });
        this.build();
        return this;
      }
    }]);

    return Octree;
  }();

  _exports.Octree = Octree;
});