text: // COPYRIGHT © 2018 Esri
  //
  // All rights reserved under the copyright laws of the United States
  // and applicable international laws, treaties, and conventions.
  //
  // This material is licensed for use under the Esri Master License
  // Agreement (MLA), and is bound by the terms of that agreement.
  // You may redistribute and use this code without modification,
  // provided you adhere to the terms of the MLA and include this
  // copyright notice.
  //
  // See use restrictions at http://www.esri.com/legal/pdfs/mla_e204_e300/english
  //
  // For additional information, contact:
  // Environmental Systems Research Institute, Inc.
  // Attn: Contracts and Legal Services Department
  // 380 New York Street
  // Redlands, California, USA 92373
  // USA
  //
  // email: contracts@esri.com
  //
  // See http://js.arcgis.com/4.10/esri/copyright.txt for details.
  
  define(["require","exports","../../../../core/PooledArray","../../../../core/libs/gl-matrix-2/gl-matrix","../../support/geometryUtils","./Util"],function(e,t,r,n,i,o){function a(e,t,r){e[0]=Math.min(e[0],t[0]-r),e[1]=Math.min(e[1],t[1]-r),e[2]=Math.min(e[2],t[2]-r)}function s(e,t,r){e[0]=Math.max(e[0],t[0]+r),e[1]=Math.max(e[1],t[1]+r),e[2]=Math.max(e[2],t[2]+r)}function c(e,t,r){return r=r||e,r[0]=e[0]+t,r[1]=e[1]+t,r[2]=e[2]+t,r}function h(e,t,r){return!i.frustum.intersectsSphere(r,i.sphere.wrap(t,e))}function u(e,t,r){if(!F.length)for(var n=0;n<8;++n)F[n]={index:0,distance:0};for(var n=0;n<8;++n){var i=m[n];F[n].index=n,F[n].distance=d(e,t,i)}F.sort(function(e,t){return e.distance-t.distance});for(var n=0;n<8;++n)r[n]=F[n].index;return r}function f(e,t){for(var r=1/0,n=null,i=0;i<8;++i){var o=d(e,t,v[i]);o<r&&(r=o,n=v[i])}return n}function d(e,t,r){return t*(e[0]*r[0]+e[1]*r[1]+e[2]*r[2])}var l,p=function(){function e(e,t,r,i){this._maximumObjectsPerNode=10,this._maximumDepth=20,this._degenerateObjects=new Set,this._objectCount=0,this._objectToBoundingSphere=r,i&&(void 0!==i.maximumObjectsPerNode&&(this._maximumObjectsPerNode=i.maximumObjectsPerNode),void 0!==i.maximumDepth&&(this._maximumDepth=i.maximumDepth)),isNaN(e[0])||isNaN(e[1])||isNaN(e[2])||isNaN(t)?this._root=new _(null,n.vec3f64.fromValues(0,0,0),.5):this._root=new _(null,e,t/2)}return Object.defineProperty(e.prototype,"center",{get:function(){return this._root.center},enumerable:!0,configurable:!0}),Object.defineProperty(e.prototype,"size",{get:function(){return 2*this._root.halfSize},enumerable:!0,configurable:!0}),Object.defineProperty(e.prototype,"root",{get:function(){return this._root.node},enumerable:!0,configurable:!0}),Object.defineProperty(e.prototype,"maximumObjectsPerNode",{get:function(){return this._maximumObjectsPerNode},enumerable:!0,configurable:!0}),Object.defineProperty(e.prototype,"maximumDepth",{get:function(){return this._maximumDepth},enumerable:!0,configurable:!0}),Object.defineProperty(e.prototype,"objectCount",{get:function(){return this._objectCount},enumerable:!0,configurable:!0}),e.prototype.add=function(e,t){var r=this._objectOrObjectsArray(e);t=null==t?r.length:t,this._objectCount+=t,this._grow(r);for(var n=_.acquire(),i=0;i<t;i++){var o=r[i];n.init(this._root),this._isDegenerate(o)?this._degenerateObjects.add(o):this._add(o,n)}_.release(n)},e.prototype.remove=function(e,t){var r=this._objectOrObjectsArray(e);this._objectCount-=r.length;for(var n=_.acquire(),i=0;i<r.length;i++){var o=r[i],a=t||this._boundingSphereFromObject(o,x);this._isValidRadius(a.radius)?(n.init(this._root),this._remove(o,a,n)):this._degenerateObjects.delete(o)}_.release(n),this._shrink()},e.prototype.update=function(e,t){!this._isValidRadius(t.radius)&&this._isDegenerate(e)||(this.remove(e,t),this.add(e))},e.prototype.forEachAlongRay=function(e,t,r){var n=this;this._forEachNode(this._root,function(i){if(!n._intersectsNode(e,t,i))return!1;var o=i.node;return o.terminals.forEach(function(i){n._intersectsObject(e,t,i)&&r(i)}),null!==o.residents&&o.residents.forEach(function(i){n._intersectsObject(e,t,i)&&r(i)}),!0})},e.prototype.forEach=function(e){this._forEachNode(this._root,function(t){var r=t.node;return r.terminals.forEach(e),null!==r.residents&&r.residents.forEach(e),!0}),this._degenerateObjects.forEach(e)},e.prototype.forEachDegenerateObject=function(e){this._degenerateObjects.forEach(e)},e.prototype.findClosest=function(e,t,r,n,i){return this._findClosest(e,"front-to-back"===t?l.FRONT_TO_BACK:l.BACK_TO_FRONT,r,n,i)},e.prototype.forEachInDepthRange=function(e,t,r,n,i,o,a,s){this._forEachInDepthRange(e,t,"front-to-back"===r?l.FRONT_TO_BACK:l.BACK_TO_FRONT,n,i,o,a,s)},e.prototype.forEachNode=function(e){this._forEachNode(this._root,function(t){return e(t.node,t.center,2*t.halfSize)})},e.prototype._intersectsNode=function(e,t,r){return c(r.center,2*-r.halfSize,j),c(r.center,2*r.halfSize,S),o.rayBoxTest(e,t,j,S)},e.prototype._intersectsObject=function(e,t,r){var n=this._objectToBoundingSphere.getRadius(r);return!(n>0)||i.sphere.intersectsRay(i.sphere.wrap(n,this._objectToBoundingSphere.getCenter(r)),i.ray.wrap(e,t))},e.prototype._forEachNode=function(e,t){for(var r=_.acquire().init(e),n=[r];0!==n.length;){if(r=n.pop(),t(r)&&!r.isLeaf())for(var i=0;i<r.node.children.length;i++){var o=r.node.children[i];o&&n.push(_.acquire().init(r).advance(i))}_.release(r)}},e.prototype._forEachNodeDepthOrdered=function(e,t,r,n){void 0===n&&(n=l.FRONT_TO_BACK);for(var i=_.acquire().init(e),o=[i],a=u(r,n,z);0!==o.length;){if(i=o.pop(),t(i)&&!i.isLeaf())for(var s=7;s>=0;--s){var c=a[s];if(!(c>=i.node.children.length)){var h=i.node.children[c];h&&o.push(_.acquire().init(i).advance(c))}}_.release(i)}},e.prototype._findClosest=function(e,t,r,i,o){var a=this,s=1/0,c=1/0,u=null,l=f(e,t),p=0,_=function(n){if(++p,!i||i(n)){var o=a._objectToBoundingSphere.getCenter(n),f=a._objectToBoundingSphere.getRadius(n);if(!r||!h(o,f,r)){var l=d(e,t,o),_=l-f,m=l+f;_<s&&(s=_,c=m,u=n)}}};return this._forEachNodeDepthOrdered(this._root,function(i){if(null!=o&&p>=o)return!1;if(r&&h(i.center,i.halfSize*g,r))return!1;if(n.vec3.scale(O,l,i.halfSize),n.vec3.add(O,O,i.center),d(e,t,O)>c)return!1;var a=i.node;return a.terminals.forEach(function(e){_(e)}),null!==a.residents&&a.residents.forEach(function(e){_(e)}),!0},e,t),u},e.prototype._forEachInDepthRange=function(e,t,r,i,o,a,s,c){var u=this,p=-1/0,_=1/0,m={setRange:function(e){r===l.FRONT_TO_BACK?(p=Math.max(p,e.near),_=Math.min(_,e.far)):(p=Math.max(p,-e.far),_=Math.min(_,-e.near))}};m.setRange(i);var v=d(t,r,e),b=f(t,r),y=f(t,-1*r),j=0,S=function(e){if(++j,!s||s(e)){var n=u._objectToBoundingSphere.getCenter(e),i=u._objectToBoundingSphere.getRadius(e),c=d(t,r,n)-v,f=c-i,l=c+i;f>_||l<p||a&&h(n,i,a)||o(e,m)}};this._forEachNodeDepthOrdered(this._root,function(e){if(null!=c&&j>=c)return!1;if(a&&h(e.center,e.halfSize*g,a))return!1;if(n.vec3.scale(O,b,e.halfSize),n.vec3.add(O,O,e.center),d(t,r,O)-v>_)return!1;if(n.vec3.scale(O,y,e.halfSize),n.vec3.add(O,O,e.center),d(t,r,O)-v<p)return!1;var i=e.node;return i.terminals.forEach(function(e){S(e)}),null!==i.residents&&i.residents.forEach(function(e){S(e)}),!0},t,r)},e.prototype._objectOrObjectsArray=function(e){return Array.isArray(e)?e:(b[0]=e,b)},e.prototype._remove=function(e,t,r){N.length=0;var n=r.advanceTo(t,function(e,t){N.push(e.node,t)}),i=n?r.node.terminals:r.node.residents;if(i.removeUnordered(e),0===i.length)for(var o=N.length-2;o>=0;o-=2){var a=N[o],s=N[o+1];if(!this._purge(a,s))break}},e.prototype._nodeIsEmpty=function(e){if(0!==e.terminals.length)return!1;if(null!==e.residents)return 0===e.residents.length;for(var t=0;t<e.children.length;t++)if(e.children[t])return!1;return!0},e.prototype._purge=function(e,t){return t>=0&&(e.children[t]=null),!!this._nodeIsEmpty(e)&&(null===e.residents&&(e.residents=new r({shrink:!0})),!0)},e.prototype._add=function(e,t){t.advanceTo(this._boundingSphereFromObject(e,x))?t.node.terminals.push(e):(t.node.residents.push(e),t.node.residents.length>this._maximumObjectsPerNode&&t.depth<this._maximumDepth&&this._split(t))},e.prototype._split=function(e){var t=e.node.residents;e.node.residents=null;for(var r=0;r<t.length;r++){var n=_.acquire().init(e);this._add(t.data[r],n),_.release(n)}},e.prototype._grow=function(e){var t=this;if(0!==e.length){var r=this._boundingSphereFromObjects(e,function(e,r){return t._boundingSphereFromObject(e,r)},T);if(this._isValidRadius(r.radius)&&!this._fitsInsideTree(r))if(this._nodeIsEmpty(this._root.node))n.vec3.copy(this._root.center,r.center),this._root.halfSize=1.25*r.radius;else{var i=_.acquire();this._rootBoundsForRootAsSubNode(r,i),this._placingRootViolatesMaxDepth(i)?this._rebuildTree(r,i):this._growRootAsSubNode(i),_.release(i)}}},e.prototype._rebuildTree=function(e,t){var r=this;n.vec3.copy(E.center,t.center),E.radius=t.halfSize;var i=this._boundingSphereFromObjects([e,E],function(e){return e},R),o=_.acquire().init(this._root);this._root.initFrom(null,i.center,1.25*i.radius),this._forEachNode(o,function(e){return r.add(e.node.terminals.data,e.node.terminals.length),null!==e.node.residents&&r.add(e.node.residents.data,e.node.residents.length),!0}),_.release(o)},e.prototype._placingRootViolatesMaxDepth=function(e){var t=0;return this._forEachNode(this._root,function(e){return t=Math.max(t,e.depth),!0}),t+Math.log(e.halfSize/this._root.halfSize)*Math.LOG2E>this._maximumDepth},e.prototype._rootBoundsForRootAsSubNode=function(e,t){for(var r=e.radius,n=e.center,i=-1/0,o=this._root.center,a=this._root.halfSize,s=0;s<3;s++){var c=o[s]-a-(n[s]-r),h=n[s]+r-(o[s]+a),u=Math.max(0,Math.ceil(c/(2*a))),f=Math.max(0,Math.ceil(h/(2*a)))+1,d=Math.pow(2,Math.ceil(Math.log(u+f)*Math.LOG2E));i=Math.max(i,d),M[s].min=u,M[s].max=f}for(var s=0;s<3;s++){var u=M[s].min,f=M[s].max,l=(i-(u+f))/2;u+=Math.ceil(l),f+=Math.floor(l);var p=o[s]-a-u*a*2;y[s]=p+(f+u)*a}return t.initFrom(null,y,i*a,0)},e.prototype._growRootAsSubNode=function(e){var t=this._root.node;n.vec3.copy(T.center,this._root.center),T.radius=this._root.halfSize,this._root.init(e),e.advanceTo(T,null,!0),e.node.children=t.children,e.node.residents=t.residents,e.node.terminals=t.terminals},e.prototype._shrink=function(){for(;;){var e=this._findShrinkIndex();if(-1===e)break;this._root.advance(e),this._root.depth=0}},e.prototype._findShrinkIndex=function(){if(0!==this._root.node.terminals.length||this._root.isLeaf())return-1;for(var e=null,t=this._root.node.children,r=0,n=0;n<t.length&&null==e;)r=n++,e=t[r];for(;n<t.length;)if(t[n++])return-1;return r},e.prototype._isDegenerate=function(e){var t=this._objectToBoundingSphere.getRadius(e);return!this._isValidRadius(t)},e.prototype._isValidRadius=function(e){return!isNaN(e)&&e!==-1/0&&e!==1/0&&e>0},e.prototype._fitsInsideTree=function(e){var t=this._root.center,r=this._root.halfSize,n=e.center;return e.radius<=r&&n[0]>=t[0]-r&&n[0]<=t[0]+r&&n[1]>=t[1]-r&&n[1]<=t[1]+r&&n[2]>=t[2]-r&&n[2]<=t[2]+r},e.prototype._boundingSphereFromObject=function(e,t){return n.vec3.copy(t.center,this._objectToBoundingSphere.getCenter(e)),t.radius=this._objectToBoundingSphere.getRadius(e),t},e.prototype._boundingSphereFromObjects=function(e,t,r){if(1===e.length){var i=t(e[0],T);n.vec3.copy(r.center,i.center),r.radius=i.radius}else{j[0]=1/0,j[1]=1/0,j[2]=1/0,S[0]=-1/0,S[1]=-1/0,S[2]=-1/0;for(var o=0;o<e.length;o++){var i=t(e[o],T);this._isValidRadius(i.radius)&&(a(j,i.center,i.radius),s(S,i.center,i.radius))}n.vec3.lerp(r.center,j,S,.5),r.radius=Math.max(S[0]-j[0],S[1]-j[1],S[2]-j[2])/2}return r},e}(),_=function(){function e(e,t,r,i){void 0===r&&(r=0),void 0===i&&(i=0),this.center=n.vec3f64.create(),this.initFrom(e,t,r,0)}return e.prototype.init=function(e){return this.initFrom(e.node,e.center,e.halfSize,e.depth)},e.prototype.initFrom=function(t,r,i,o){return void 0===t&&(t=null),void 0===i&&(i=this.halfSize),void 0===o&&(o=this.depth),this.node=t||e.createEmptyNode(),r&&n.vec3.copy(this.center,r),this.halfSize=i,this.depth=o,this},e.prototype.advance=function(t){var r=this.node.children[t];r||(r=e.createEmptyNode(),this.node.children[t]=r),this.node=r,this.halfSize/=2,this.depth++;var n=m[t];return this.center[0]+=n[0]*this.halfSize,this.center[1]+=n[1]*this.halfSize,this.center[2]+=n[2]*this.halfSize,this},e.prototype.advanceTo=function(e,t,r){for(void 0===r&&(r=!1);;){if(this.isTerminalFor(e))return t&&t(this,-1),!0;if(this.isLeaf()&&!r)return t&&t(this,-1),!1;this.isLeaf()&&(this.node.residents=null);var n=this._childIndex(e);t&&t(this,n),this.advance(n)}},e.prototype.isLeaf=function(){return null!=this.node.residents},e.prototype.isTerminalFor=function(e){return e.radius>this.halfSize/2},e.prototype._childIndex=function(e){for(var t=e.center,r=this.center,n=0,i=0;i<3;i++)r[i]<t[i]&&(n|=1<<i);return n},e.createEmptyNode=function(){return{children:[null,null,null,null,null,null,null,null],terminals:new r({shrink:!0}),residents:new r({shrink:!0})}},e.acquire=function(){if(0===this._pool.length)return new e;var t=this._pool[this._pool.length-1];return this._pool.length--,t},e.release=function(e){this._pool.push(e)},e._pool=[],e}();!function(e){e[e.FRONT_TO_BACK=1]="FRONT_TO_BACK",e[e.BACK_TO_FRONT=-1]="BACK_TO_FRONT"}(l||(l={}));var m=[n.vec3f64.fromValues(-1,-1,-1),n.vec3f64.fromValues(1,-1,-1),n.vec3f64.fromValues(-1,1,-1),n.vec3f64.fromValues(1,1,-1),n.vec3f64.fromValues(-1,-1,1),n.vec3f64.fromValues(1,-1,1),n.vec3f64.fromValues(-1,1,1),n.vec3f64.fromValues(1,1,1)],v=[n.vec3f64.fromValues(-1,-1,-1),n.vec3f64.fromValues(-1,-1,1),n.vec3f64.fromValues(-1,1,-1),n.vec3f64.fromValues(-1,1,1),n.vec3f64.fromValues(1,-1,-1),n.vec3f64.fromValues(1,-1,1),n.vec3f64.fromValues(1,1,-1),n.vec3f64.fromValues(1,1,1)],g=Math.sqrt(3),b=[null],y=n.vec3f64.create(),O=n.vec3f64.create(),j=n.vec3f64.create(),S=n.vec3f64.create(),N=[],x={center:n.vec3f64.create(),radius:0},T={center:n.vec3f64.create(),radius:0},E={center:n.vec3f64.create(),radius:0},R={center:n.vec3f64.create(),radius:0},M=[{min:0,max:0},{min:0,max:0},{min:0,max:0}],F=[],z=[];return p});