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

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

  function _getRequireWildcardCache(nodeInterop) { if (typeof WeakMap !== "function") return null; var cacheBabelInterop = new WeakMap(); var cacheNodeInterop = new WeakMap(); return (_getRequireWildcardCache = function _getRequireWildcardCache(nodeInterop) { return nodeInterop ? cacheNodeInterop : cacheBabelInterop; })(nodeInterop); }

  function _interopRequireWildcard(obj, nodeInterop) { if (!nodeInterop && obj && obj.__esModule) { return obj; } if (obj === null || typeof obj !== "object" && typeof obj !== "function") { return { default: obj }; } var cache = _getRequireWildcardCache(nodeInterop); if (cache && cache.has(obj)) { return cache.get(obj); } var newObj = {}; var hasPropertyDescriptor = Object.defineProperty && Object.getOwnPropertyDescriptor; for (var key in obj) { if (key !== "default" && Object.prototype.hasOwnProperty.call(obj, key)) { var desc = hasPropertyDescriptor ? Object.getOwnPropertyDescriptor(obj, key) : null; if (desc && (desc.get || desc.set)) { Object.defineProperty(newObj, key, desc); } else { newObj[key] = obj[key]; } } } newObj.default = obj; if (cache) { cache.set(obj, newObj); } return newObj; }

  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; }

  /**
   *	Simplification Geometry Modifier
   *    - based on code and technique
   *	  - by Stan Melax in 1998
   *	  - Progressive Mesh type Polygon Reduction Algorithm
   *    - http://www.melax.com/polychop/
   */
  var _cb = new _three.Vector3(),
      _ab = new _three.Vector3();

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

      if (BufferGeometryUtils === undefined) {
        throw 'THREE.SimplifyModifier relies on BufferGeometryUtils';
      }
    }

    _createClass(SimplifyModifier, [{
      key: "modify",
      value: function modify(geometry, count) {
        if (geometry.isGeometry === true) {
          console.error('THREE.SimplifyModifier no longer supports Geometry. Use BufferGeometry instead.');
          return;
        }

        geometry = geometry.clone();
        var attributes = geometry.attributes; // this modifier can only process indexed and non-indexed geomtries with a position attribute

        for (var name in attributes) {
          if (name !== 'position') geometry.deleteAttribute(name);
        }

        geometry = BufferGeometryUtils.mergeVertices(geometry); //
        // put data of original geometry in different data structures
        //

        var vertices = [];
        var faces = []; // add vertices

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

        for (var i = 0; i < positionAttribute.count; i++) {
          var v = new _three.Vector3().fromBufferAttribute(positionAttribute, i);
          var vertex = new Vertex(v);
          vertices.push(vertex);
        } // add faces


        var index = geometry.getIndex();

        if (index !== null) {
          for (var _i = 0; _i < index.count; _i += 3) {
            var a = index.getX(_i);
            var b = index.getX(_i + 1);
            var c = index.getX(_i + 2);
            var triangle = new Triangle(vertices[a], vertices[b], vertices[c], a, b, c);
            faces.push(triangle);
          }
        } else {
          for (var _i2 = 0; _i2 < positionAttribute.count; _i2 += 3) {
            var _a = _i2;

            var _b = _i2 + 1;

            var _c = _i2 + 2;

            var _triangle = new Triangle(vertices[_a], vertices[_b], vertices[_c], _a, _b, _c);

            faces.push(_triangle);
          }
        } // compute all edge collapse costs


        for (var _i3 = 0, il = vertices.length; _i3 < il; _i3++) {
          computeEdgeCostAtVertex(vertices[_i3]);
        }

        var nextVertex;
        var z = count;

        while (z--) {
          nextVertex = minimumCostEdge(vertices);

          if (!nextVertex) {
            console.log('THREE.SimplifyModifier: No next vertex');
            break;
          }

          collapse(vertices, faces, nextVertex, nextVertex.collapseNeighbor);
        } //


        var simplifiedGeometry = new _three.BufferGeometry();
        var position = [];
        index = []; //

        for (var _i4 = 0; _i4 < vertices.length; _i4++) {
          var _vertex = vertices[_i4].position;
          position.push(_vertex.x, _vertex.y, _vertex.z); // cache final index to GREATLY speed up faces reconstruction

          vertices[_i4].id = _i4;
        } //


        for (var _i5 = 0; _i5 < faces.length; _i5++) {
          var face = faces[_i5];
          index.push(face.v1.id, face.v2.id, face.v3.id);
        } //


        simplifiedGeometry.setAttribute('position', new _three.Float32BufferAttribute(position, 3));
        simplifiedGeometry.setIndex(index);
        return simplifiedGeometry;
      }
    }]);

    return SimplifyModifier;
  }();

  _exports.SimplifyModifier = SimplifyModifier;

  function pushIfUnique(array, object) {
    if (array.indexOf(object) === -1) array.push(object);
  }

  function removeFromArray(array, object) {
    var k = array.indexOf(object);
    if (k > -1) array.splice(k, 1);
  }

  function computeEdgeCollapseCost(u, v) {
    // if we collapse edge uv by moving u to v then how
    // much different will the model change, i.e. the "error".
    var edgelength = v.position.distanceTo(u.position);
    var curvature = 0;
    var sideFaces = []; // find the "sides" triangles that are on the edge uv

    for (var i = 0, il = u.faces.length; i < il; i++) {
      var face = u.faces[i];

      if (face.hasVertex(v)) {
        sideFaces.push(face);
      }
    } // use the triangle facing most away from the sides
    // to determine our curvature term


    for (var _i6 = 0, _il = u.faces.length; _i6 < _il; _i6++) {
      var minCurvature = 1;
      var _face = u.faces[_i6];

      for (var j = 0; j < sideFaces.length; j++) {
        var sideFace = sideFaces[j]; // use dot product of face normals.

        var dotProd = _face.normal.dot(sideFace.normal);

        minCurvature = Math.min(minCurvature, (1.001 - dotProd) / 2);
      }

      curvature = Math.max(curvature, minCurvature);
    } // crude approach in attempt to preserve borders
    // though it seems not to be totally correct


    var borders = 0;

    if (sideFaces.length < 2) {
      // we add some arbitrary cost for borders,
      // borders += 10;
      curvature = 1;
    }

    var amt = edgelength * curvature + borders;
    return amt;
  }

  function computeEdgeCostAtVertex(v) {
    // compute the edge collapse cost for all edges that start
    // from vertex v.  Since we are only interested in reducing
    // the object by selecting the min cost edge at each step, we
    // only cache the cost of the least cost edge at this vertex
    // (in member variable collapse) as well as the value of the
    // cost (in member variable collapseCost).
    if (v.neighbors.length === 0) {
      // collapse if no neighbors.
      v.collapseNeighbor = null;
      v.collapseCost = -0.01;
      return;
    }

    v.collapseCost = 100000;
    v.collapseNeighbor = null; // search all neighboring edges for "least cost" edge

    for (var i = 0; i < v.neighbors.length; i++) {
      var collapseCost = computeEdgeCollapseCost(v, v.neighbors[i]);

      if (!v.collapseNeighbor) {
        v.collapseNeighbor = v.neighbors[i];
        v.collapseCost = collapseCost;
        v.minCost = collapseCost;
        v.totalCost = 0;
        v.costCount = 0;
      }

      v.costCount++;
      v.totalCost += collapseCost;

      if (collapseCost < v.minCost) {
        v.collapseNeighbor = v.neighbors[i];
        v.minCost = collapseCost;
      }
    } // we average the cost of collapsing at this vertex


    v.collapseCost = v.totalCost / v.costCount; // v.collapseCost = v.minCost;
  }

  function removeVertex(v, vertices) {
    console.assert(v.faces.length === 0);

    while (v.neighbors.length) {
      var n = v.neighbors.pop();
      removeFromArray(n.neighbors, v);
    }

    removeFromArray(vertices, v);
  }

  function removeFace(f, faces) {
    removeFromArray(faces, f);
    if (f.v1) removeFromArray(f.v1.faces, f);
    if (f.v2) removeFromArray(f.v2.faces, f);
    if (f.v3) removeFromArray(f.v3.faces, f); // TODO optimize this!

    var vs = [f.v1, f.v2, f.v3];

    for (var i = 0; i < 3; i++) {
      var v1 = vs[i];
      var v2 = vs[(i + 1) % 3];
      if (!v1 || !v2) continue;
      v1.removeIfNonNeighbor(v2);
      v2.removeIfNonNeighbor(v1);
    }
  }

  function collapse(vertices, faces, u, v) {
    // u and v are pointers to vertices of an edge
    // Collapse the edge uv by moving vertex u onto v
    if (!v) {
      // u is a vertex all by itself so just delete it..
      removeVertex(u, vertices);
      return;
    }

    var tmpVertices = [];

    for (var i = 0; i < u.neighbors.length; i++) {
      tmpVertices.push(u.neighbors[i]);
    } // delete triangles on edge uv:


    for (var _i7 = u.faces.length - 1; _i7 >= 0; _i7--) {
      if (u.faces[_i7].hasVertex(v)) {
        removeFace(u.faces[_i7], faces);
      }
    } // update remaining triangles to have v instead of u


    for (var _i8 = u.faces.length - 1; _i8 >= 0; _i8--) {
      u.faces[_i8].replaceVertex(u, v);
    }

    removeVertex(u, vertices); // recompute the edge collapse costs in neighborhood

    for (var _i9 = 0; _i9 < tmpVertices.length; _i9++) {
      computeEdgeCostAtVertex(tmpVertices[_i9]);
    }
  }

  function minimumCostEdge(vertices) {
    // O(n * n) approach. TODO optimize this
    var least = vertices[0];

    for (var i = 0; i < vertices.length; i++) {
      if (vertices[i].collapseCost < least.collapseCost) {
        least = vertices[i];
      }
    }

    return least;
  } // we use a triangle class to represent structure of face slightly differently


  var Triangle = /*#__PURE__*/function () {
    function Triangle(v1, v2, v3, a, b, c) {
      _classCallCheck(this, Triangle);

      this.a = a;
      this.b = b;
      this.c = c;
      this.v1 = v1;
      this.v2 = v2;
      this.v3 = v3;
      this.normal = new _three.Vector3();
      this.computeNormal();
      v1.faces.push(this);
      v1.addUniqueNeighbor(v2);
      v1.addUniqueNeighbor(v3);
      v2.faces.push(this);
      v2.addUniqueNeighbor(v1);
      v2.addUniqueNeighbor(v3);
      v3.faces.push(this);
      v3.addUniqueNeighbor(v1);
      v3.addUniqueNeighbor(v2);
    }

    _createClass(Triangle, [{
      key: "computeNormal",
      value: function computeNormal() {
        var vA = this.v1.position;
        var vB = this.v2.position;
        var vC = this.v3.position;

        _cb.subVectors(vC, vB);

        _ab.subVectors(vA, vB);

        _cb.cross(_ab).normalize();

        this.normal.copy(_cb);
      }
    }, {
      key: "hasVertex",
      value: function hasVertex(v) {
        return v === this.v1 || v === this.v2 || v === this.v3;
      }
    }, {
      key: "replaceVertex",
      value: function replaceVertex(oldv, newv) {
        if (oldv === this.v1) this.v1 = newv;else if (oldv === this.v2) this.v2 = newv;else if (oldv === this.v3) this.v3 = newv;
        removeFromArray(oldv.faces, this);
        newv.faces.push(this);
        oldv.removeIfNonNeighbor(this.v1);
        this.v1.removeIfNonNeighbor(oldv);
        oldv.removeIfNonNeighbor(this.v2);
        this.v2.removeIfNonNeighbor(oldv);
        oldv.removeIfNonNeighbor(this.v3);
        this.v3.removeIfNonNeighbor(oldv);
        this.v1.addUniqueNeighbor(this.v2);
        this.v1.addUniqueNeighbor(this.v3);
        this.v2.addUniqueNeighbor(this.v1);
        this.v2.addUniqueNeighbor(this.v3);
        this.v3.addUniqueNeighbor(this.v1);
        this.v3.addUniqueNeighbor(this.v2);
        this.computeNormal();
      }
    }]);

    return Triangle;
  }();

  var Vertex = /*#__PURE__*/function () {
    function Vertex(v) {
      _classCallCheck(this, Vertex);

      this.position = v;
      this.id = -1; // external use position in vertices list (for e.g. face generation)

      this.faces = []; // faces vertex is connected

      this.neighbors = []; // neighbouring vertices aka "adjacentVertices"
      // these will be computed in computeEdgeCostAtVertex()

      this.collapseCost = 0; // cost of collapsing this vertex, the less the better. aka objdist

      this.collapseNeighbor = null; // best candinate for collapsing
    }

    _createClass(Vertex, [{
      key: "addUniqueNeighbor",
      value: function addUniqueNeighbor(vertex) {
        pushIfUnique(this.neighbors, vertex);
      }
    }, {
      key: "removeIfNonNeighbor",
      value: function removeIfNonNeighbor(n) {
        var neighbors = this.neighbors;
        var faces = this.faces;
        var offset = neighbors.indexOf(n);
        if (offset === -1) return;

        for (var i = 0; i < faces.length; i++) {
          if (faces[i].hasVertex(n)) return;
        }

        neighbors.splice(offset, 1);
      }
    }]);

    return Vertex;
  }();
});