delatin - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

delatin.min.js

+export default class Delatin{constructor(e,t,s=t){this.data=e,this.width=t,this.height=s,this.coords=[],this.triangles=[],this._halfedges=[],this._candidates=[],this._queueIndices=[],this._queue=[],this._errors=[],this._pending=[],this._pendingLen=0,this._rmsdSum=0,this._init()}run(e=1){for(;this.getMaxError()>e;)this.refine()}refine(){this._step(),this._flush()}getMaxError(){return this._errors[0]}getRMSD(){return Math.sqrt(this._rmsdSum/this._errors.length)}heightAt(e,t){return this.data[this.width*t+e]}_init(){const e=this.width-1,t=this.height-1,s=this._addPoint(0,0),i=this._addPoint(e,0),h=this._addPoint(0,t),n=this._addPoint(e,t),r=this._addTriangle(n,s,h,-1,-1,-1);this._addTriangle(s,n,i,r,-1,-1),this._flush()}_flush(){const e=this.coords;for(let t=0;t<this._pendingLen;t++){const s=this._pending[t],i=2*this.triangles[3*s+0],h=2*this.triangles[3*s+1],n=2*this.triangles[3*s+2];this._findCandidate(e[i],e[i+1],e[h],e[h+1],e[n],e[n+1],s)}this._pendingLen=0}_findCandidate(e,t,s,i,h,n,r){const a=Math.min(e,s,h),_=Math.min(t,i,n),d=Math.max(e,s,h),o=Math.max(t,i,n);let l=orient(s,i,h,n,a,_),u=orient(h,n,e,t,a,_),g=orient(e,t,s,i,a,_);const c=i-t,f=e-s,q=n-i,p=s-h,m=t-n,w=h-e,M=orient(e,t,s,i,h,n),T=this.heightAt(e,t)/M,P=this.heightAt(s,i)/M,z=this.heightAt(h,n)/M;let S=0,x=0,L=0;for(let e=_;e<=o;e++){let t=0;l<0&&0!==q&&(t=Math.max(t,Math.floor(-l/q))),u<0&&0!==m&&(t=Math.max(t,Math.floor(-u/m))),g<0&&0!==c&&(t=Math.max(t,Math.floor(-g/c)));let s=l+q*t,i=u+m*t,h=g+c*t,n=!1;for(let r=a+t;r<=d;r++){if(s>=0&&i>=0&&h>=0){n=!0;const t=T*s+P*i+z*h,a=Math.abs(t-this.heightAt(r,e));a>S&&(S=a,x=r,L=e)}else if(n)break;s+=q,i+=m,h+=c}l+=p,u+=w,g+=f}(x===e&&L===t||x===s&&L===i||x===h&&L===n)&&(S=0),this._candidates[2*r]=x,this._candidates[2*r+1]=L,this._queuePush(r,S)}_step(){const e=this._queuePop(),t=3*e+0,s=3*e+1,i=3*e+2,h=this.triangles[t],n=this.triangles[s],r=this.triangles[i],a=this.coords[2*h],_=this.coords[2*h+1],d=this.coords[2*n],o=this.coords[2*n+1],l=this.coords[2*r],u=this.coords[2*r+1],g=this._candidates[2*e],c=this._candidates[2*e+1],f=this._addPoint(g,c);if(0===orient(a,_,d,o,g,c))this._handleCollinear(f,t);else if(0===orient(d,o,l,u,g,c))this._handleCollinear(f,s);else if(0===orient(l,u,a,_,g,c))this._handleCollinear(f,i);else{const e=this._halfedges[t],a=this._halfedges[s],_=this._halfedges[i],d=this._addTriangle(h,n,f,e,-1,-1,t),o=this._addTriangle(n,r,f,a,-1,d+1),l=this._addTriangle(r,h,f,_,d+2,o+1);this._legalize(d),this._legalize(o),this._legalize(l)}}_addPoint(e,t){const s=this.coords.length>>1;return this.coords.push(e,t),s}_addTriangle(e,t,s,i,h,n,r=this.triangles.length){const a=r/3;return this.triangles[r+0]=e,this.triangles[r+1]=t,this.triangles[r+2]=s,this._halfedges[r+0]=i,this._halfedges[r+1]=h,this._halfedges[r+2]=n,i>=0&&(this._halfedges[i]=r+0),h>=0&&(this._halfedges[h]=r+1),n>=0&&(this._halfedges[n]=r+2),this._candidates[2*a+0]=0,this._candidates[2*a+1]=0,this._queueIndices[a]=-1,this._pending[this._pendingLen++]=a,r}_legalize(e){const t=this._halfedges[e];if(t<0)return;const s=e-e%3,i=t-t%3,h=s+(e+1)%3,n=s+(e+2)%3,r=i+(t+2)%3,a=i+(t+1)%3,_=this.triangles[n],d=this.triangles[e],o=this.triangles[h],l=this.triangles[r],u=this.coords;if(!inCircle(u[2*_],u[2*_+1],u[2*d],u[2*d+1],u[2*o],u[2*o+1],u[2*l],u[2*l+1]))return;const g=this._halfedges[h],c=this._halfedges[n],f=this._halfedges[r],q=this._halfedges[a];this._queueRemove(s/3),this._queueRemove(i/3);const p=this._addTriangle(_,l,o,-1,f,g,s),m=this._addTriangle(l,_,d,p,c,q,i);this._legalize(p+1),this._legalize(m+2)}_handleCollinear(e,t){const s=t-t%3,i=s+(t+1)%3,h=s+(t+2)%3,n=this.triangles[h],r=this.triangles[t],a=this.triangles[i],_=this._halfedges[i],d=this._halfedges[h],o=this._halfedges[t];if(o<0){const t=this._addTriangle(e,n,r,-1,d,-1,s),i=this._addTriangle(n,e,a,t,-1,_);return this._legalize(t+1),void this._legalize(i+2)}const l=o-o%3,u=l+(o+2)%3,g=l+(o+1)%3,c=this.triangles[u],f=this._halfedges[u],q=this._halfedges[g];this._queueRemove(l/3);const p=this._addTriangle(n,r,e,d,-1,-1,s),m=this._addTriangle(r,c,e,q,-1,p+1,l),w=this._addTriangle(c,a,e,f,-1,m+1),M=this._addTriangle(a,n,e,_,p+2,w+1);this._legalize(p),this._legalize(m),this._legalize(w),this._legalize(M)}_queuePush(e,t){const s=this._queue.length;this._queueIndices[e]=s,this._queue.push(e),this._errors.push(t),this._rmsdSum+=t*t,this._queueUp(s)}_queuePop(){const e=this._queue.length-1;return this._queueSwap(0,e),this._queueDown(0,e),this._queuePopBack()}_queuePopBack(){const e=this._queue.pop(),t=this._errors.pop();return this._rmsdSum-=t*t,this._queueIndices[e]=-1,e}_queueRemove(e){const t=this._queueIndices[e];if(t<0){const t=this._pending.indexOf(e);if(-1===t)throw new Error("Broken triangulation (something went wrong).");return void(this._pending[t]=this._pending[--this._pendingLen])}const s=this._queue.length-1;s!==t&&(this._queueSwap(t,s),this._queueDown(t,s)||this._queueUp(t)),this._queuePopBack()}_queueLess(e,t){return this._errors[e]>this._errors[t]}_queueSwap(e,t){const s=this._queue[e],i=this._queue[t];this._queue[e]=i,this._queue[t]=s,this._queueIndices[s]=t,this._queueIndices[i]=e;const h=this._errors[e];this._errors[e]=this._errors[t],this._errors[t]=h}_queueUp(e){let t=e;for(;;){const e=t-1>>1;if(e===t||!this._queueLess(t,e))break;this._queueSwap(e,t),t=e}}_queueDown(e,t){let s=e;for(;;){const e=2*s+1;if(e>=t||e<0)break;const i=e+1;let h=e;if(i<t&&this._queueLess(i,e)&&(h=i),!this._queueLess(h,s))break;this._queueSwap(s,h),s=h}return s>e}}function orient(e,t,s,i,h,n){return(s-h)*(t-n)-(i-n)*(e-h)}function inCircle(e,t,s,i,h,n,r,a){const _=e-r,d=t-a,o=s-r,l=i-a,u=h-r,g=n-a,c=o*o+l*l,f=u*u+g*g;return _*(l*f-c*g)-d*(o*f-c*u)+(_*_+d*d)*(o*g-l*u)<0}

index.js

@@ -5,3 +5,3 @@
     constructor(data, width, height = width) {
-        this.data = data;
+        this.data = data; // height data
         this.width = width;
@@ -16,29 +16,37 @@ this.height = height;
         this._candidates = [];
-        this._errors = [];
         this._queueIndices = [];
 
         this._queue = []; // queue of added triangles
+        this._errors = [];
         this._pending = []; // triangles pending addition to queue
         this._pendingLen = 0;
 
+        this._rmsdSum = 0;
         this._init();
     }
 
+    // refine the mesh until its maximum error gets below the given one
     run(maxError = 1) {
         while (this.getMaxError() > maxError) {
-            this._step();
-            this._flush();
+            this.refine();
         }
     }
 
+    // refine the mesh with a single point
+    refine() {
+        this._step();
+        this._flush();
+    }
+
+    // max error of the current mesh
     getMaxError() {
-        return this._errors[this._queue[0]];
+        return this._errors[0];
     }
 
+    // root-mean-square deviation of the current mesh
     getRMSD() {
-        let sum = 0;
-        for (const e of this._errors) sum += e * e;
-        return Math.sqrt(sum / this._errors.length);
+        return Math.sqrt(this._rmsdSum / this._errors.length);
     }
 
+    // height value at a given position
     heightAt(x, y) {
@@ -62,2 +70,3 @@ return this.data[this.width * y + x];
 
+    // rasterize and queue all triangles that got added or updated in _step
     _flush() {
@@ -76,2 +85,3 @@ const coords = this.coords;
 
+    // rasterize a triangle, find its max error, and queue it for processing
     _findCandidate(p0x, p0y, p1x, p1y, p2x, p2y, t) {
@@ -155,12 +165,11 @@ // triangle bounding box
 
-        // update metadata
+        // update triangle metadata
         this._candidates[2 * t] = mx;
         this._candidates[2 * t + 1] = my;
 
-        this._errors[t] = maxError;
-
         // add triangle to priority queue
-        this._queuePush(t);
+        this._queuePush(t, maxError);
     }
 
+    // process the next triangle in the queue, splitting it with a new point
     _step() {
@@ -213,2 +222,3 @@ // pop triangle with highest error from priority queue
 
+    // add coordinates for a new vertex
     _addPoint(x, y) {
@@ -220,2 +230,3 @@ const i = this.coords.length >> 1;
 
+    // add or update a triangle in the mesh
     _addTriangle(a, b, c, ab, bc, ca, e = this.triangles.length) {
@@ -248,3 +259,2 @@ const t = e / 3; // new triangle index
         this._candidates[2 * t + 1] = 0;
-        this._errors[t] = 0;
         this._queueIndices[t] = -1;
@@ -316,2 +326,3 @@
 
+    // handle a case where new vertex is on the edge of a triangle
     _handleCollinear(pn, a) {
@@ -359,6 +370,8 @@ const a0 = a - a % 3;
 
-    _queuePush(t) {
+    _queuePush(t, error) {
         const i = this._queue.length;
         this._queueIndices[t] = i;
         this._queue.push(t);
+        this._errors.push(error);
+        this._rmsdSum += error * error;
         this._queueUp(i);
@@ -376,2 +389,4 @@ }
         const t = this._queue.pop();
+        const e = this._errors.pop();
+        this._rmsdSum -= e * e;
         this._queueIndices[t] = -1;
@@ -403,3 +418,3 @@ return t;
     _queueLess(i, j) {
-        return this._errors[this._queue[i]] > this._errors[this._queue[j]];
+        return this._errors[i] > this._errors[j];
     }
@@ -414,2 +429,5 @@
         this._queueIndices[pj] = i;
+        const e = this._errors[i];
+        this._errors[i] = this._errors[j];
+        this._errors[j] = e;
     }
@@ -416,0 +434,0 @@

package.json

 {
   "name": "delatin",
-  "version": "0.1.0",
+  "version": "0.2.0",
   "description": "JavaScript terrain mesh generation tool",
   "main": "index.js",
+  "module": "index.js",
   "type": "module",
+  "unpkg": "delatin.min.js",
   "scripts": {
-    "pretest": "eslint index.js test/test.js",
+    "pretest": "eslint index.js bench.js test/test.js",
     "test": "node -r esm test/test.js",
-    "prepublishOnly": "npm run test"
+    "bench": "node -r esm bench.js",
+    "build": "terser -c -m -- index.js > delatin.min.js",
+    "prepublishOnly": "npm run test && npm run build"
   },
   "files": [
-    "index.js"
+    "index.js",
+    "delatin.min.js"
   ],
@@ -32,4 +37,5 @@ "eslintConfig": {
     "pngjs": "^3.4.0",
-    "tape": "^4.11.0"
+    "tape": "^4.11.0",
+    "terser": "^4.3.4"
   }
 }

README.md

@@ -1,2 +0,2 @@
-# delatin
+# delatin [![Build Status](https://travis-ci.com/mapbox/delatin.svg?branch=master)](https://travis-ci.com/mapbox/delatin) [![Vlad's projects](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
 
@@ -14,3 +14,3 @@ A fast JavaScript **3D terrain mesh** generation tool. Approximates a height field with a Delaunay triangulation, minimizing the amount of points and triangles for a given maximum error.
 ```js
-const tin = new Delatin(heights, width, height);
+const tin = new Delatin(heightValues, width, height);
 
@@ -23,3 +23,3 @@ tin.run(0.3); // run mesh refinement until max error is less than 0.3
 
-#### `new Delatin(heights, width, height)`
+#### `new Delatin(heightValues, width, height)`
 
@@ -32,2 +32,6 @@ Creates a new Delatin instance given a height field in the form of a flat array of numbers (with `width * height` length).
 
+#### `tin.refine()`
+
+Runs a single iteration of mesh refinement, adding a single point to the mesh. Useful when generating the mesh with custom stop conditions (e.g. maximum number of points or triangles).
+
 #### `tin.getMaxError()`
@@ -43,3 +47,3 @@
 
-Returns the height value at position `x`, `y`.
+Returns the height value at a given position, with `x`, `y` being integer coordinates that reference the original height field.
 
@@ -53,1 +57,12 @@ #### `tin.coords`
 After running mesh refinement, this will be an an array of triangle indices of the final mesh. Each triple of numbers defines a triangle and references vertices in the `tin.coords` array.
+
+## Install
+
+Run `npm install delatin` or `yarn add delatin`. Delatin is exposed as a ES module, so you can use it like this in modern browsers:
+
+```html
+<script type="module">
+import Delatin from 'https://unpkg.com/delatin';
+```
+
+To use ES modules in Node, either use [esm](https://github.com/standard-things/esm) (`node -r esm app.js`), or `node --experimental-modules app.js` for Node v12+.

New alerts

Minified code

Quality

This package contains minified code. This may be harmless in some cases where minified code is included in packaged libraries, however packages on npm should not minify code.

Improved metrics

Total package byte prevSize

24465

45.64%

Number of package files

5

25%

Lines of code

423

10.73%

Number of lines in readme file

64

30.61%

Worsened metrics

Dev dependency count

6

20%

Number of low quality alerts

3

50%

No dependency changes