Skip to content

Instantly share code, notes, and snippets.

@d3x0r
Last active May 7, 2024 13:33
Show Gist options
  • Save d3x0r/5633f0548f4d7b283f8bab19e022acad to your computer and use it in GitHub Desktop.
Save d3x0r/5633f0548f4d7b283f8bab19e022acad to your computer and use it in GitHub Desktop.
Marching tetrahedrons; Marching Diamond Crystal Lattice; Marching Cubes/Sliced into 5 Tetrahedrons

Marching Diamond Crystal Lattice

Git Repository

https://github.com/d3x0r/MarchingTetrahedra

Marching Diamond Crystal Lattice Detail

graphic Layout Alternate notes, for plane meshing

See also

Testing framework : http://mikolalysenko.github.io/Isosurface/

https://github.com/mikolalysenko/isosurface.git

New Testing framework: https://d3x0r.github.io/MarchingTetrahedra/

Marching Tetrahedra 3 (DLC-Plane) mode slices a cloud a plane at a time, generating a single calculation for all shared points. Duduces the point count.

Quad emits do not work, because one of the triangles, sometimes, ends up with an inverted, although the face order is the same as emitting 2 triangles. It could be a boundary condition in the testing framework that sometimes flips triangels; this is visilble on Marching Tetrahedra 2 (DCL-Cell) still emits quads for the intersections between 4 lines; This surface does not have to be flat; there's no correlation between oposing corners that implies this surface is a single plane.

This yields really good results for opening spaces, does not suffer from any discontinuities. It is simpler if 0 is outside, and < 0 is outside; >0 has density.

in the case of distance to surface as point cloud data, the density is -distance; but then the option to use zero as inside surface must also be selected.

All triangles are trivially aligned with their proper normals. The accompanying source code is complete; but is less than optimal.

The tetrahedral computation (tetCompute) in this code assumes the following.

The triangle mesher, given any input point, the point is either inside, or outside.

  • (If 0 is 'inside') If it is inside, the face generation is inverted, and all values inverted. In the case of 0 the state does not change from 'outside' to 'inside' so the origin point, which is ALWAYS outside, and is the source of computing the delta from 0 to points 1,2, or 3, then those points could also be 0, resulting in a slope that has no delta; this is forced to 0 as a result, so a 0 'inside' point is as close to itself as it can be.
  • (If 0 is 'outside') then, since the first point must be outside, if it is 0, then no inversion takes place. If it isn't 0, then the delta computation for the slope will never be 0.

The conditions and plane generation can also all be reversed, such that 0 is 'inside' is proper, and the mesher expects the first inpoint point to be inside... which reverse all of the subtractions and >= to < comparisons.

Inspired from cells of diamond crystal lattice...

Diamond cubic lattice

Instead of blank cells, I have alternating same-cells (the inside tetrahdron is rotated 90 degrees each time, so the edge deltas are computed along the same diagonal in mating cells.

My original idea was actually more of a marching - cuboctohedron https://en.wikipedia.org/wiki/Cuboctahedron which is formed from trying to densly stack equilateral tetrahedrons... and then scalling a large stack down, in the middle you end up with 90 degree cuts...

The cell is actually simpler than that; being a marching-cube, but with the middle plane of it skewed 0.5 to the right and 'forward'/'up'? where the values of the skewed plane are an average of the 8 points around it. This ended up being 14 tetrahedrons, with 4 pyramidal penta-hedrons sliced into 2 tetrahedron each... But slicing the pyramids caused a lot of confusion in mapping inverted/notinverted to the tetrahedra face emission.

the final result was only 5 tetrahedra, and no fabricated points. (the above also required a 3x3x2 matrix of values, so the 0.5 skew to the right 1 cell could be calculated) This only requires the 5 points of the cell much like yours.

I was iterating through the tet vertices to find one that was 'outside' and then just always build from an outside point; but depending on ordering of the vertices that can be tricky; I ordered mine so every other point is inverted, and a mod4 can be applied to wrap the point indexing, reducing it to just 1 if case , and its sub-cases...

Inflation

inflation

The point cloud can have a scalar applied to inside/outside values to 'inflate' the mesh...

Earlier notes building on Diamond lattice framework

This is a parallel-piped cell, which is not what is implemented above. This adds additional complication to the above, and requires syntesizing a point from other points around it... but not knowing the nature of the coordinates, a pure average of the 8 points around the points required causes creases and indentations, especially on boundaries of the data. The above method, using 5 tetrahedrons is more appealing from a code simplicity viewpoint, while doing very well at opening void areas.

Bad piped cell drawing

Provided for historical context. Other works included rough sketches and models build from Geomag toys.

This is the cuboctohedral approach.... geometrically it ends up the same, because the pyramidal pentahedra have to be slice into two irregular tetrahedra anyway.


trying to find the centroid of the tetrahedron..

cos−1(−​1⁄3) = 109.4712206...° ≈ 109.5°

, if C is the centroid of the base, the distance from C to a vertex of the base is twice that from C to the midpoint of an edge of the base

edge = x
  sqrt(2/3) * X
  
  +/- 1 , 0, -1/sqrt(2)
  
  0, +/-1, 1/sqrt(2)
  
  
  cubocotohedron - 16 + 4 + 16   36 lines,       14-28 faces
  hourglass - dual inverted pyramids  16 lines   2-4 faces
  
  15 points skipped
  
  (8 + 4)  * 2  24
  6  * 4  * 2   48
  
  8             80  lines  32 cells
    4 points 12, 12, 8 8  40 radial
  
  
  
  computed from recti-linear 3d space, by synthesizing a center point from the 8 points on the corners of a cell.
  The partitioning of the tetrahedrons provide a high usage of unit tetrahedral cells, and isocolese pyramids.
  It's an impure spacial unit projection; that is, when constructed with physical objects, the aspect ratio is not correct...
  but mathemetically they should be congruent.  A single-axis scaling can be applied to stretch it to unit lengths internally.
  
  
  pyramid tesselation is a composition of 2 tetrahedrons.
  
  geometry of a layer is computed with inter-locked alternating cells.
  
  A single layer does not require points above or below it, but do require a span of points within the layer, and the top and bottom.
  
  var layer = [[[]],[[]]];  //[0][x][y], [1][x][y]
  
  centroid = avergae of [0][x(+1)][y(+1)]+[1][x(+1)][y(+1)]
  
  two passes should result in a sector mesh 1) indepednant, all edges - 1 on x, y... complete mesh on top and bottom.

  this is the array indexes of the 3x top;bottom matrix needed to mesh this area.
  they contain the values at the centroid points of density mesh.


	 // bottom and top layers, of the primary coordinates, and secondary required
	 // missing side, at edge of sector can be assume as infinitly dense or vacuum...  Absolute pressure is 0.
	 // the more dense, the less pressure it excerts.
	 // the more vacuous - the more pressure it pulls with... 


	 
	 // gradient is >0 is dense and 0 and below is vacuum.
	 // (there is no such thing as absolute vacuum)
	 // 0 is ground level atmosphere. 
	 // 0.5 - cork/lithium
	 // 0.8 - woods
	 // 1 is liquid
	 // 1.5 is sand
	 // 1.6 is dirt
	 // 2 is stone/brick
	 // 1.78 is magnesium
	 // 3 is granite
	 // 
	 // 7 density dirt doesn't exist... 
	 // zinc/iron
	 // no particular reasons... 
	 
	 // spacial objects like astoids will be very dense, pushing to the edge of the vacuum space on them... 
  
  
     6 7 8
     3 4 5
     0 1 2
     

    and the resulting 0 crossing value from outside to inside is given as a delta T along the line from one of the points.
	
	// sided-ness ends up purely computed from which is <=0 and >0
	//so number is from -1 to 0, the direction is reversed (from far point)... if from 0-1 the direction is forward from the point.
	
	
	 to have an average computed internally, the next values to the right and above have to also
    be factored into the computation... 
	 
	 a  a  a    a  a  a
     0  0  a    1  1  a
     0  0  a    1  1  a
  
     (0, 0 lower left)
	 
  
  0134
	0,0  +  0,1  +  1,0  +  1,1  +  3,0  +  3,1  +  4,0  +  4,1
	/8
	
  1245	
	1,0  +  1,1  +  2,0  +  2,1  +  4,0  +  4,1  +  5,0  +  5,1
	/8
	
  3467	
    3,0  +  3,1  +  4,0  +  4,1  +  6,0  +  6,1  +  7,0  +  7,1
	/8
	
  4578	
	4,0  +  4,1  +  5,0  +  5,1  +  7,0  +  7,1  +  8,0  +  8,1
	/8
	
	
  0 - bottom pyramid
    1 - back-left tetrahedron
       013,0  0134	
	   
	   * if points are inside/outside...
	   0,0-1,0     1,0-3,0    3,0-0,0    0,0-0134    1,0-0134    3,0-0134
	   
	   
	2 - forward-right tet
       134,0  0134	

	   * if points are inside/outside...
	   1,0-3,0     1,0-0134    3,0-4,0    3,0-0134    4,0-0134    4,0-1,0


  1 - top pyramid
    1 - lower-left tetrahedron
       013,1  0134

	   * if points are inside/outside...
	   0,1-1,1     1,1-3,1    3,1-0,1    0,1-0134    1,1-0134    3,1-0134

	2 - upper-right tet
       134,1  0134	
	   1,1-3,1     1,1-0134    3,1-4,1    3,1-0134    4,1-0134    4,1-1,1
	
  2 - right bottom tet
       14,0  0134 1245 
  3 - right top tet
       14,1  0134 1245 

  4 - forward bottom tet
       34,0  0134 3467
  5 - forward top tet
       34,1  0134 3467

  6 - forward right bottom pyramid
     1 - back-left tet
	    4,0  0134  1245 3467
	 2 - fore-right tet
	    4,0  1245 3467 4578
   
  7 - forward right top pyramid
     1 - back-left tet
	    4,1  0134  1245 3467
	 2 - fore-right tet
	    4,1  1245 3467 4578
	  


  The above also have a fixed geometry
    0  0,0,0  1,0,0   1,0,0 / 1,1,0
	   0.5,0.5,0.5
    1  0,0,1  1,0,1   1,0,1 / 1,1,1
	   0.5,0.5,0.5
	2 1,0,0  1,1,0  0.5,0.5,0.5  1.5,0.5,0.5
	3 1,0,1  1,1,1  0.5,0.5,0.5  1.5,0.5,0.5

	4 0,1,0  1,1,0  0.5,0.5,0.5  0.5,1.5,0.5
	5 0,1,1  1,1,1  0.5,0.5,0.5  0.5,1.5,0.5


    6  1,1,0  0.5,0.5,0.5  1.5,0.5,0.5   0.5,1.5,0.5
	   1,1,0  1.5,0.5,0.5  1.5,1.5,0.5   0.5,1.5,0.5

    7  1,1,1  0.5,0.5,0.5  1.5,0.5,0.5   0.5,1.5,0.5
	   1,1,1  1.5,0.5,0.5  1.5,1.5,0.5   0.5,1.5,0.5
	


ordering of the tetrahedrons matters to generate correctly sided output
there can be a simple invert passed to the mesher in the case of mirror inputs (top/bottom)


   0 1 3 2 

(inverted notes apply to that single point being outside (or notted inside) )
    0    1  (inverted)
    \   /
     \2/    (above page)
 	  |
	  |
	  3  (inverted)
	  



(0,1 outside ... 1,2  2,3  3,0  )
    0    1  // unfinished
    \   /
     \2/ 
 	  |
	  |
	  3  
	  


// changing the order of the points changes the inversion characteristic 90 degrees.
// (odd offset vs even offset)

  (inverted)	  
    0    1 
    \   /
     \3/ 
 	  |
	  |
	  2   (inverted)

// pyramid point ordering


    2 ----- 3
      \   / |
    |  \ /  |
    |   4   |(above page)
    |  / \  |
	  /   \ |
    0 ----- 1
	  
	  
	splits into two ordered tetrahedrons with
	
    0,2,4,1   1,2,4,3
	
	
	
	  
	  
      y                     x -1           1 x
                                1/sqrt(2)
	  1                             |
  x -1  1 x                 
                                    |
     -1                           1/sqrt(2)
      y                           0 y
	  
	  

so cubic cell structure with 45 degree tetrahedral containment

http://lampx.tugraz.at/~hadley/ss1/crystalstructure/structures/diamond/diamond.php

0,0,0   0,0,0       0,1,0   0,4,0       0,2,0   0,8,0
1,0,0   1,2,0       1,1,0   1,6,0       1,2,0   1,10,0
                                        
...                 ...                 ...
2,0,0   2,0,0       2,0,0   2,0,0       2,0,0   2,0,0
...                 ...                 ...
3,0,0   3,2,0       3,0,0   3,2,0       3,0,0   3,2,0

--------------

0,0,1   0,0+1,1       0,1,1   0,4+1,1       0,2,0   0,8+1,1
1,0,1   1,2+1,1       1,1,1   1,6+1,1       1,2,0   1,10+1,1
                                        
...                 ...                 ...
2,0,0   2,0,0       2,0,0   2,0,0       2,0,0   2,0,0
...                 ...                 ...
3,0,0   3,2,0       3,0,0   3,2,0       3,0,0   3,2,0

--------------

0,0,2   0+2,3,2       0,1,1   0+2,7,1       0,2,0   0+2,11,1
1,0,2   1+2,1,2       1,1,1   1+2,5,1       1,2,0   1+2,9,1
                                        
...                 ...                 ...
2,0,0   2,0,0       2,0,0   2,0,0       2,0,0   2,0,0
...                 ...                 ...
3,0,0   3,2,0       3,0,0   3,2,0       3,0,0   3,2,0

--------------

0,0,3   0-1,1,2       0,1,1   0+3,7,1       0,2,0   0+3,11,1
1,0,3   1+3,1,2       1,1,1   1+3,5,1       1,2,0   1+3,9,1
                                        
...                 ...                 ...
2,0,0   2,0,0       2,0,0   2,0,0       2,0,0   2,0,0
...                 ...                 ...
3,0,0   3,2,0       3,0,0   3,2,0       3,0,0   3,2,0



z = 0
   y = 0
      x = x
   y = 1 //y
      x = x + 2
   
z = 1
   x = x + 0.25
   y = y + 0.25

z = 2
   x = x + 0.5
   y = y
   
z = 3
   x = x + 0.75
   y = y + 0.25

z = 4 (0)
   x = x
   y = y


z=0 -> 1
  x = x -> x+0.25
  y = y -> y+0.25
  

// The MIT License (MIT)
//
// Copyright (c) 2020 d3x0r
//
// 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.
/**
* Marching Tetrahedra in Javascript
*
* Based on Unique Research
*
*
* Javascript port by d3x0r
*/
var MarchingTetrahedra2 = (function() {
const _debug = false;
const zero_is_outside = false;
return function(data, dims) {
var vertices = []
, faces = [];
// some working notes
// slope = ( values[1] - values[0] ) / 1;
// b = values[0]
// y = mx + b;
// x = (y-b)/m
// x = (0-values[0])/(values[1]-values[0] )
// x = (values[0])/(values[0]-values[1] )
// -3 8
// 3/11
// -3 3
// 3/6
/*
// inverted not applies to that point in or out of shape vs the others.
0 _ _ 1 (inverted)
|\ /|
\\2// (above page)
| | |
\|/
3 (inverted)
*/
const cellOrigin = [0,0,0];
var bufferOut = null;
var bufferPos = 0;
function e2(p) {
faces.push(p);
}
function emit( p ) {
vertices.push( p );
return vertices.length-1;
}
function lerp( p1, p2, del ) {
return [ cellOrigin[0] + p1[0] + (p2[0]-p1[0])*del
, cellOrigin[1] + p1[1] + (p2[1]-p1[1])*del
, cellOrigin[2] + p1[2] + (p2[2]-p1[2])*del ];
}
function tetCompute( values, geometry, invert ) {
_debug && console.log( "tet: v:", values, "g:", geometry );
if( ( values[0] >= 0 ) ) {
invert = !invert;
values[0] = 0-values[0];
values[1] = 0-values[1];
values[2] = 0-values[2];
values[3] = 0-values[3];
}
if( zero_is_outside ) {
//if( ( values[0] < 0 ) )
{
// 0 is outside
if( values[1] >= 0 ) {
// 1 is inside 0-1 crosses
if( !( values[1]-values[0] ) )
cross1 = 0;
else
cross1 = -values[0] / ( values[1]-values[0] );
if( values[2] >= 0 ) {
// 0-2 is also a cross
if( !( values[2]-values[0] ) )
cross2 = 0;
else
cross2 = -values[0] / ( values[2] - values[0] );
if( values[3] >= 0 ) {
// 0-3 is also a cross
if( !( values[3]-values[0] ) )
cross3 = 0;
else
cross3 = -values[0] / ( values[3] - values[0] );
// emit tri.
if( invert ) {
e2([emit( lerp( geometry[0], geometry[1], cross1 ) ),
emit(lerp( geometry[0], geometry[2], cross2 ) ),
emit( lerp( geometry[0], geometry[3], cross3 ) )]);
} else {
e2([emit( lerp( geometry[0], geometry[2], cross2 ) ),
emit( lerp( geometry[0], geometry[1], cross1 ) ),
emit( lerp( geometry[0], geometry[3], cross3 ) )] );
}
} else {
if( !( values[1]-values[3] ) )
cross3 = 0;
else
cross3 = -values[3] / ( values[1] - values[3] );
if( !( values[2]-values[3] ) )
cross4 = 0;
else
cross4 = -values[3] / ( values[2] - values[3] );
let a,b,c,d;
// emit quad
a=lerp( geometry[0], geometry[1], cross1 );
b=lerp( geometry[0], geometry[2], cross2 );
c=lerp( geometry[3], geometry[1], cross3 ); // always lerp from outside to inside.
d=lerp( geometry[3], geometry[2], cross4 );
a= emit(a);
b= emit(b);
c= emit(c);
d= emit(d);
// emit a,b,c b,c,d
if( invert ) {
e2( [a,b,d,c] );
//e2( [c,a,d] );
//e2( [d,a,b] );
}else{
e2( [a,c,d,b] );
//e2( [a,c,d] );
//e2( [a,d,b] );
}
}
} else {
if( values[3] >= 0 ) {
if( !( values[1]-values[2] ) )
cross2 = 0;
else
cross2 = -values[2] / ( values[1] - values[2] );
if( !( values[3]-values[0] ) )
cross3 = 0;
else
cross3 = -values[0] / ( values[3] - values[0] );
if( !( values[3]-values[2] ) )
cross4 = 0;
else
cross4 = -values[2] / ( values[3] - values[2] );
// emit quad
let a,b,c,d;
a=lerp( geometry[0], geometry[1], cross1 );
b=lerp( geometry[0], geometry[3], cross3 );
c=lerp( geometry[2], geometry[1], cross2 ); // always lerp from outside to inside.
d=lerp( geometry[2], geometry[3], cross4 );
// emit a,b,c b,c,d
a=emit(a);
b= emit(b);
c= emit(c);
d= emit(d);
if( invert ) {
e2( [b,a,c,d] );
//e2( [b,a,c] );
//e2( [d,b,c] );
}else {
e2( [b,d,c,a] );
//e2( [a,b,c] );
//e2( [b,d,c] );
}
} else {
// 0 out 1 in 2 out 3 out
if( !( values[1]-values[2] ) )
cross2 = 0;
else
cross2 = -values[2] / ( values[1] - values[2] );
if( !( values[1]-values[3] ) )
cross3 = 0;
else
cross3 = -values[3] / ( values[1] - values[3] );
// emit tri 2,3,0
if( !invert ) {
e2([emit(lerp( geometry[2], geometry[1], cross2 )),
emit(lerp( geometry[0], geometry[1], cross1 )),
emit(lerp( geometry[3], geometry[1], cross3 ))]);
} else {
e2([emit(lerp( geometry[0], geometry[1], cross1 )),
emit(lerp( geometry[2], geometry[1], cross2 )),
emit(lerp( geometry[3], geometry[1], cross3 ))]);
}
}
}
} else {
// 0,1 outside
if( values[2] >= 0 ) {
// 0-2 is also a cross
if( !( values[2]-values[0] ) )
cross1 = 0;
else
cross1 = -values[0] / ( values[2] - values[0] );
if( !( values[2]-values[1] ) )
cross2 = 0;
else
cross2 = -values[1] / ( values[2] - values[1] );
if( values[3] >= 0 ) {
// 0-3 is also a cross
if( !( values[3]-values[0] ) )
cross3 = 0;
else
cross3 = -values[0] / ( values[3] - values[0] );
if( !( values[3]-values[1] ) )
cross4 = 0;
else
cross4 = -values[1] / ( values[3] - values[1] );
// emit quad.
let a,b,c,d;
a=lerp( geometry[0], geometry[2], cross1 );
b=lerp( geometry[1], geometry[2], cross2 );
c=lerp( geometry[0], geometry[3], cross3 ); // always lerp from outside to inside.
d=lerp( geometry[1], geometry[3], cross4 );
a=emit(a);
b= emit(b);
c= emit(c);
d= emit(d);
if( !invert ) {
e2( [a,b,d,c] );
// e2( [d,a,b] );
// e2( [c,a,d] );
}else {
e2( [a,c,d,b] );
// e2( [a,d,b] );
// e2( [a,c,d] );
}
} else {
// 0 out 1 out 2 in 3 out
if( !( values[2]-values[3] ) )
cross3 = 0;
else
cross3 = -values[3] / ( values[2] - values[3] );
// emit tri 0,1,3
if( invert ) {
e2( [ emit( lerp( geometry[1], geometry[2], cross2 ) ),
emit( lerp( geometry[0], geometry[2], cross1 ) ),
emit( lerp( geometry[3], geometry[2], cross3 ) ) ] );
} else {
e2( [ emit( lerp( geometry[0], geometry[2], cross1 ) ),
emit(lerp( geometry[1], geometry[2], cross2 ) ),
emit(lerp( geometry[3], geometry[2], cross3 ) )]);
}
}
} else {
// 0,1,2 outside
if( values[3] >= 0 ) {
// 3 inside...
if( !( values[3]-values[0] ) )
cross1 = 0;
else
cross1 = -values[0] / ( values[3] - values[0] );
if( !( values[3]-values[1] ) )
cross2 = 0;
else
cross2 = -values[1] / ( values[3] - values[1] );
if( !( values[3]-values[2] ) )
cross3 = 0;
else
cross3 = -values[2] / ( values[3] - values[2] );
// emit tri
if( invert ) {
e2( [ emit( lerp( geometry[0], geometry[3], cross1 ) ),
emit( lerp( geometry[1], geometry[3], cross2 ) ),
emit( lerp( geometry[2], geometry[3], cross3 ) )]);
} else {
e2( [ emit( lerp( geometry[1], geometry[3], cross2 ) ),
emit( lerp( geometry[0], geometry[3], cross1 ) ),
emit( lerp( geometry[2], geometry[3], cross3 ) )]);
}
} else {
// all inside.
}
}
}
}
} else {
// 0 is outside.
if( ( values[0] <= 0 ) )
{
// 0 is outside
if( values[1] > 0 ) {
// 1 is inside 0-1 crosses
cross1 = -values[0] / ( values[1]-values[0] );
if( values[2] > 0 ) {
// 0-2 is also a cross
cross2 = -values[0] / ( values[2] - values[0] );
if( values[3] > 0 ) {
// 0-3 is also a cross
cross3 = -values[0] / ( values[3] - values[0] );
// emit tri.
if( invert ) {
e2([emit( lerp( geometry[0], geometry[1], cross1 ) ),
emit(lerp( geometry[0], geometry[2], cross2 ) ),
emit( lerp( geometry[0], geometry[3], cross3 ) )]);
} else {
e2([emit( lerp( geometry[0], geometry[2], cross2 ) ),
emit( lerp( geometry[0], geometry[1], cross1 ) ),
emit( lerp( geometry[0], geometry[3], cross3 ) )] );
}
} else {
cross3 = -values[3] / ( values[1] - values[3] );
cross4 = -values[3] / ( values[2] - values[3] );
let a,b,c,d;
// emit quad
a=lerp( geometry[0], geometry[1], cross1 );
b=lerp( geometry[0], geometry[2], cross2 );
c=lerp( geometry[3], geometry[1], cross3 ); // always lerp from outside to inside.
d=lerp( geometry[3], geometry[2], cross4 );
a= emit(a);
b= emit(b);
c= emit(c);
d= emit(d);
// emit a,b,c b,c,d
if( invert ) {
e2( [a,b,d,c] );
//e2( [c,a,d] );
//e2( [d,a,b] );
}else{
e2( [a,c,d,b] );
//e2( [a,c,d] );
//e2( [a,d,b] );
}
}
} else {
if( values[3] > 0 ) {
cross2 = -values[2] / ( values[1] - values[2] );
cross3 = -values[0] / ( values[3] - values[0] );
cross4 = -values[2] / ( values[3] - values[2] );
// emit quad
let a,b,c,d;
a=lerp( geometry[0], geometry[1], cross1 );
b=lerp( geometry[0], geometry[3], cross3 );
c=lerp( geometry[2], geometry[1], cross2 ); // always lerp from outside to inside.
d=lerp( geometry[2], geometry[3], cross4 );
// emit a,b,c b,c,d
a=emit(a);
b= emit(b);
c= emit(c);
d= emit(d);
//if(1) return; console.log( "a" );
// VERIFIED
if( invert ) {
e2( [b,a,c,d] );
//e2( [b,a,c] );
//e2( [d,b,c] );
}else {
e2( [b,d,c,a] );
//e2( [a,b,c] );
//e2( [b,d,c] );
}
} else {
// 0 out 1 in 2 out 3 out
cross2 = -values[2] / ( values[1] - values[2] );
cross3 = -values[3] / ( values[1] - values[3] );
// emit tri 2,3,0
//if(1) return; console.log( "a" );
if( !invert ) {
e2([emit(lerp( geometry[2], geometry[1], cross2 )),
emit(lerp( geometry[0], geometry[1], cross1 )),
emit(lerp( geometry[3], geometry[1], cross3 ))]);
} else {
e2([emit(lerp( geometry[0], geometry[1], cross1 )),
emit(lerp( geometry[2], geometry[1], cross2 )),
emit(lerp( geometry[3], geometry[1], cross3 ))]);
}
}
}
} else {
// 0,1 outside
if( values[2] > 0 ) {
// 0-2 is also a cross
cross1 = -values[0] / ( values[2] - values[0] );
cross2 = -values[1] / ( values[2] - values[1] );
if( values[3] > 0 ) {
// 0-3 is also a cross
cross3 = -values[0] / ( values[3] - values[0] );
cross4 = -values[1] / ( values[3] - values[1] );
// emit quad.
let a,b,c,d;
a=lerp( geometry[0], geometry[2], cross1 );
b=lerp( geometry[1], geometry[2], cross2 );
c=lerp( geometry[0], geometry[3], cross3 ); // always lerp from outside to inside.
d=lerp( geometry[1], geometry[3], cross4 );
a=emit(a);
b= emit(b);
c= emit(c);
d= emit(d);
if( !invert ) {
e2( [a,b,d,c] );
// e2( [d,a,b] );
// e2( [c,a,d] );
}else {
e2( [a,c,d,b] );
// e2( [a,d,b] );
// e2( [a,c,d] );
}
} else {
// 0 out 1 out 2 in 3 out
cross3 = -values[3] / ( values[2] - values[3] );
// emit tri 0,1,3
if( invert ) {
e2( [ emit( lerp( geometry[1], geometry[2], cross2 ) ),
emit( lerp( geometry[0], geometry[2], cross1 ) ),
emit( lerp( geometry[3], geometry[2], cross3 ) ) ] );
} else {
e2( [ emit( lerp( geometry[0], geometry[2], cross1 ) ),
emit(lerp( geometry[1], geometry[2], cross2 ) ),
emit(lerp( geometry[3], geometry[2], cross3 ) )]);
}
}
} else {
// 0,1,2 outside
if( values[3] > 0 ) {
// 3 inside...
if( !( values[3]-values[0] ) )
cross1 = 0;
else
cross1 = -values[0] / ( values[3] - values[0] );
if( !( values[3]-values[1] ) )
cross2 = 0;
else
cross2 = -values[1] / ( values[3] - values[1] );
if( !( values[3]-values[2] ) )
cross3 = 0;
else
cross3 = -values[2] / ( values[3] - values[2] );
// emit tri
if( invert ) {
e2( [ emit( lerp( geometry[0], geometry[3], cross1 ) ),
emit( lerp( geometry[1], geometry[3], cross2 ) ),
emit( lerp( geometry[2], geometry[3], cross3 ) )]);
} else {
e2( [ emit( lerp( geometry[1], geometry[3], cross2 ) ),
emit( lerp( geometry[0], geometry[3], cross1 ) ),
emit( lerp( geometry[2], geometry[3], cross3 ) )]);
}
} else {
// all inside.
}
}
}
}
}
}
// values input to this are in 2 planes for lower and upper values
const geom = [
[0,0,0], // bottom layer
[1,0,0],
[0,1,0],
[1,1,0],
[0,0,1], // 5 top layer
[1,0,1], // 6
[0,1,1], // 7
[1,1,1], // 8
]
// combinations of 0-4 1-1
// 4 of 8 points are only in 1 tetrahedron
// the other 4 points are in 4 tetrahedron
// 0,0 2,0 0,1 1,0
// 3,0 1,0 3,1 2,0
// 1,1 3,1 1,0 0,1
// 2,1 3,1 0,1 2,0
// center
// 0,1 3,1 0,1 0,2
const tetTable = [
[ 0,2,4,1 ],
[ 3,1,7,2 ],
[ 5,7,1,4 ],
[ 6,7,4,2 ],
[ 4,7,1,2 ],
]
const tetTable2 = [
[ 1,0,5,3 ],
[ 2,3,6,0 ],
[ 4,5,0,6 ],
[ 7,3,5,6 ],
[ 0,6,5,3 ],
]
function cellCompute( alt, values, geom ) {
let tets = tetTable.map( tet=>{ let r,tot = (r=tet.map( val=>val<=0 )).reduce( ((a,b)=>a+b),0 ); return [tot,r]; } );
_debug && showValues( values );
_debug && console.log( "Our local state:", values, tets );
let v = [0,0,0,0];
let g = [null,null,null,null];
let n = 0;
if( alt ) {
for( let tet of tetTable ) {
//if( n++ !== 0 ) continue;
v[0] = values[tet[0]>>2][tet[0]%4];
v[1] = values[tet[1]>>2][tet[1]%4];
v[2] = values[tet[2]>>2][tet[2]%4];
v[3] = values[tet[3]>>2][tet[3]%4];
g[0] = geom[tet[0]];
g[1] = geom[tet[1]];
g[2] = geom[tet[2]];
g[3] = geom[tet[3]];
tetCompute( v, g, false );
}
} else {
for( let tet of tetTable2 ) {
//if( n++ !== 2 ) continue;
v[0] = values[tet[0]>>2][tet[0]%4];
v[1] = values[tet[1]>>2][tet[1]%4];
v[2] = values[tet[2]>>2][tet[2]%4];
v[3] = values[tet[3]>>2][tet[3]%4];
g[0] = geom[tet[0]];
g[1] = geom[tet[1]];
g[2] = geom[tet[2]];
g[3] = geom[tet[3]];
tetCompute( v, g, false );
}
}
}
function showValues(values) {
var s = ''
s += values[0][2] + " " + values[0][3] + " " + values[1][2] + " " + values[1][3] + "\n";
s += values[0][0] + " " + values[0][1] + " " + values[1][0] + " " + values[1][1] + "\n";
console.log( JSON.stringify(values) );
console.log( "\n" + s );
}
var values = [[-1,-1,-1,-1],[-1,-1,-1,-1]];
if(1)
for( var x = -1; x < dims[0]; x++ ) {
cellOrigin[0] = x;
for( var y = -1; y < dims[1]; y++ ) {
cellOrigin[1] = y;
//if( /*y == 1 && */ x == 6)
for( var z = -1; z < dims[2]; z++ ) {
var tmp = values[0];
values[0] = values[1];
values[1] = tmp;
cellOrigin[2] = z;
if( z >= 0 )
{
if( x < 0 ) {
values[1][0] = -1;
} else
values[1][0] = 0-data[ z * dims[0]*dims[1] + (y+0) * dims[0] + (x+0) ];
if( x >= dims[0]-1 )
values[1][1] = -1;
else
values[1][1] = 0-data[ z * dims[0]*dims[1] + (y+0) * dims[0] + (x+1) ];
if(y < dims[1]-1 ) {
if( x < 0 )
values[1][2] = -1;
else
values[1][2] = 0-data[ z * dims[0]*dims[1] + (y+1) * dims[0] + (x+0) ];
if( x >= dims[0]-1 )
values[1][3] = -1;
else
values[1][3] = 0-data[ z * dims[0]*dims[1] + (y+1) * dims[0] + (x+1) ];
} else {
values[1][2] = -1;
values[1][3] = -1;
}
if( 1|| z == 4 ) {
_debug&&showValues(values);
cellCompute( (x+y+z)&1, values, geom );
}
}
else
{
values[1][0] = -1;
values[1][1] = -1;
values[1][2] = -1;
values[1][3] = -1;
}
}
}
}
return { vertices: vertices, faces: faces };
}
})();
if("undefined" != typeof exports) {
exports.mesher = MarchingTetrahedra;
}
// The MIT License (MIT)
//
// Copyright (c) 2020 d3x0r
//
// 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.
/**
* Marching Tetrahedra in Javascript
* This version meshes a plane of cells at a time to maximize shared vertices
* and reduce redundant calculations.
*
* Based on Unique Research
*
*
* Javascript port by d3x0r
*/
var MarchingTetrahedra3 = (function() {
const debug_ = false;
const zero_is_outside = true;
return function(data, dims) {
var vertices = []
, faces = [];
/*
// inverted not applies to that point in or out of shape vs the others.
0 _ _ 1 (inverted)
|\ /|
\\2// (above page)
| | |
\|/
3 (inverted)
*/
const cellOrigin = [0,0,0];
function e2(p) {
faces.push(p);
}
function emit( p ) {
vertices.push( p );
return vertices.length-1;
}
function lerp( p1, p2, del ) {
return [ cellOrigin[0] + p1[0] + (p2[0]-p1[0])*del
, cellOrigin[1] + p1[1] + (p2[1]-p1[1])*del
, cellOrigin[2] + p1[2] + (p2[2]-p1[2])*del ];
}
const geom = [
[0,0,0], // bottom layer
[1,0,0],
[0,1,0],
[1,1,0],
[0,0,1], // 5 top layer
[1,0,1], // 6
[0,1,1], // 7
[1,1,1], // 8
]
const linesOddMin = [ [0,2],[0,4],[4,6],[2,4], [0,1],[1,2],[1,4] , [4,5],[4,7] ];
const linesEvenMin = [ [0,2],[0,4],[4,6],[0,6], [0,1],[0,3],[0,5] , [4,5],[5,6] ];
const linesMin = [linesEvenMin,linesOddMin];
var pointHolder = [[],[]];
var crossHolder = [[],[]];
const dim0 = dims[0];
const dim1 = dims[1];
const dim2 = dims[2];
const dataOffset = [ 0,1, dim0, 1+dim0, 0 + dim0*dim1,1 + dim0*dim1,dim0 + dim0*dim1, 1+dim0 + dim0*dim1] ;
const pdim0 = dims[0];
const pdim1 = dims[1];
function planeCompute( z ) {
let tmp;
tmp = pointHolder[0]; pointHolder[0] = pointHolder[1]; pointHolder[1] = tmp;
tmp = crossHolder[0]; crossHolder[0] = crossHolder[1]; crossHolder[1] = tmp;
let points_ = pointHolder[1];
let crosses_ = crossHolder[1];
let points = pointHolder[0];//new Array((dim0+1)+(dim1+1)*9);
points.length = 0;
let crosses = crossHolder[0];
crosses.length = 0;
let odd = 0;
const dd = dim0 * dim1;
let zOdd = z & 1;
for( var y = 0; y < dim1; y++ ) {
for( var x = 0; x < dim0; x++ ) {
let del, d,e,t;
odd = (( x + y ) &1) ^ zOdd;
cellOrigin[0] = x; cellOrigin[1] = y; cellOrigin[2] = z;
let baseOffset = x+0 + y*dim0 + z * dim0*dim1;
const lineArray = linesMin[odd];
for( let l = 0; l < 9; l++ ) {
const pair = lineArray[l];
let data0, data1;
let p0 = pair[0];
let p1 = pair[1];
data0=baseOffset+dataOffset[p0];
data1=baseOffset+dataOffset[p1];
// when we actually do layers, this matters.
if( z ) {
// copy data from old table...
if( !(p0 & 4) && !(p1 & 4) ) {
switch(l) {
case 0:
points.push( points_[(x+y*pdim0)*9 + 2] );
crosses.push( crosses_[(x+y*pdim0)*9 + 2] );
break;
case 5:
points.push( points_[(x+y*pdim0)*9 + 8] );
crosses.push( crosses_[(x+y*pdim0)*9 + 8] );
break;
case 4:
points.push( points_[(x+y*pdim0)*9 + 7] );
crosses.push( crosses_[(x+y*pdim0)*9 + 7] );
break;
default:
debugger;
}
continue;
}
}
if( (x == (dim0-1)) &&( (p0 & 1) || (p1 &1) )) {
// this is an overflow, need to push fake data....
//console.log( "skip x overflow", x, y, z, l, p0, p1 );
points.push(null);
crosses.push(false);
continue;
}
if( (y == (dim1-1)) &&( (p0 & 2) || (p1 &2) )) {
// this is an overflow, need to push fake data....
//console.log( "skip y overflow", x, y, z, l, p0, p1 );
points.push(null);
crosses.push(false);
continue;
}
if( (z == (dim2-1)) &&( (p0 & 4) || (p1 & 4) )) {
// this is an overflow, need to push fake data....
//console.log( "skip z overflow", x, y, z, l, p0, p1 );
points.push(null);
crosses.push(false);
continue;
}
d=-data[data0]; e=-data[data1];
if( ( d <= 0 && e >0 )|| (d > 0 && e <= 0 ) ){
//console.log( "x, y is a cross:", (x+y*dim0)*9, crosses.length, l, x, y, p0, p1, data0, data1, `d:${d} e:${e}` );
if( e <= 0 ) {
(t = -e/(d-e));
points.push( emit(lerp( geom[p1], geom[p0], t )) );
} else {
(t = -d/(e-d));
points.push( emit(lerp( geom[p0], geom[p1], t )) );
}
crosses.push(true);
}
else {
//console.log( "x, y is NOT cross:", (x+y*dim0)*9, crosses.length, l, x, y, p0, p1, data0, data1, `d:${d} e:${e}` );
points.push( null );
crosses.push(false);
}
}
}
}
const vertToData = [
[ [ 2,3,6,0], [3,1,5,0], [4,6,5,0], [6,7,5,3], [0,6,5,3] ],
[ [ 0, 2,4,1], [3,1,7,2], [6,7,4,2], [4,7,5,1], [1,2,4,7] ],
];
for( let a = 0; a < 2; a++ ) for( let b = 0; b < 5; b++ ) for( let c = 0; c < 4; c++ ) vertToData[a][b][c] = dataOffset[vertToData[a][b][c]];
// vertex paths 0-1 0-2, 0-3 1-2 2-3 3-1
// this is the offset from dataOffset to the related value.
const edgeToComp = [
[ [ (pdim0)*9+4, (pdim0)*9+1, 0 , (pdim0)*9+6 , 3 , 5 ]
, [ (1)*9+0 , 1*9+3 , 5 , 1*9+1 , 6 , 4 ]
, [ 2 , 7 , 1 , 8 , 6 , 3 ]
, [ (pdim0)*9+7, 8 , (pdim0)*9+6, (1)*9+2 , (1)*9+3, (1+pdim0)*9+1 ]
, [ 3, 6, 5, 8, (1)*9+3, (pdim0)*9+6]
],
[ [0, 1, 4, 3, 6, 5]
, [ (1)*9+0, (1+pdim0)*9+1, (pdim0)*9 + 4, 1*9+3, (pdim0)*9+6, 5 ]
, [ (pdim0)*9+7, 2, (pdim0)*9+1, 8, 3, (pdim0)*9+6 ]
, [ 8, 7, 6, (1)*9+2, (1)*9+1, (1)*9+3 ]
, [ 5, 6, (1)*9+3, 3, 8, (pdim0)*9+6 ]
],
]
let a = [];
for( var y = 0; y < dim1-1; y++ ) {
for( var x = 0; x < dim0-1; x++ ) {
const nAble = -1;
let t;
let n;
let dataBaseOffset = (x + (y*dim0));
let baseOffset = (x + (y*pdim0))*9;
let odd = (( x + y ) &1) ^ zOdd;
const dataOffset = dataBaseOffset + z*dim1*dim0;
for( tet = 0; tet < 5; tet++ ) {
var f = null;
for( n = 0; n < 6; n++ ) {
a[n] =crosses[ baseOffset+edgeToComp[odd][tet][n] ];
}
if( crosses[ baseOffset+edgeToComp[odd][tet][0] ] ) {
//console.log( `Output: odd:${odd} tet:${tet} x:${x} y:${y} a:${JSON.stringify(a)}` );
if( a[1] ) {
if( a[2] ) {
if( data[dataOffset+vertToData[odd][tet][0]] >= 0 ) {
e2(f= [ points[baseOffset+edgeToComp[odd][tet][1]]
,points[baseOffset+edgeToComp[odd][tet][0]]
,points[baseOffset+edgeToComp[odd][tet][2]]] );
} else {
e2(f= [ points[baseOffset+edgeToComp[odd][tet][0]]
,points[baseOffset+edgeToComp[odd][tet][1]]
,points[baseOffset+edgeToComp[odd][tet][2]]] );
}
} else {
if( a[4] ) {
if( data[dataOffset+vertToData[odd][tet][0]] >= 0 ) {
e2(f= [ points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
e2(f= [ points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
} else {
e2(f= [ points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
e2(f= [ points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][1]]
] );
}
}
}
} else {
if( a[2] ) {
if( a[3] && a[4] && !a[5] ) {
if( data[dataOffset+vertToData[odd][tet][0]] >= 0 ) {
e2(f= [ points[baseOffset+edgeToComp[odd][tet][3]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
e2(f= [ points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][2]]
] );
} else {
e2(f= [ points[baseOffset+edgeToComp[odd][tet][2]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
e2(f= [ points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][3]]
] );
}
}
}else {
if( a[3] && !a[4] && a[5] ) {
if( data[dataOffset+vertToData[odd][tet][1]] >= 0 )
e2(f= [ points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][3]]
] );
else
e2(f= [ points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][3]]
] );
}
}
}
} else {
if( a[1] ) {
if( a[2] ) {
if( a[3] && !a[4] && a[5] ) {
debug_ && console.log( `Output: odd:${odd} tet:${tet} x:${x} y:${y} a:${JSON.stringify(a)}` );
if( data[dataOffset+vertToData[odd][tet][0]] >= 0 ) {
e2(f= [ points[baseOffset+edgeToComp[odd][tet][2]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
e2(f= [ points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][3]]
] );
}else{
e2(f= [ points[baseOffset+edgeToComp[odd][tet][3]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
e2(f= [ points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][2]]
] );
}
}
} else {
if( a[3] && a[4] && !a[5] ) {
if( data[dataOffset+vertToData[odd][tet][2]] >= 0 )
e2(f= [points[baseOffset+edgeToComp[odd][tet][3]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
else
e2(f= [points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][3]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
}
}
} else {
if( a[2] ) {
if( !a[3] && a[4] && a[5] ){
if( nAble & 64 )
if( data[dataOffset+vertToData[odd][tet][3]] >= 0 )
e2(f= [points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][2]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
else
e2(f= [points[baseOffset+edgeToComp[odd][tet][2]]
, points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
}
}
}
}
}
}
}
}
for( var z = 0; z < dim2-1; z++ ) {
planeCompute(z);
}
return { vertices: vertices, faces: faces };
}
})();
if("undefined" != typeof exports) {
exports.mesher = MarchingTetrahedra3;
}
/* https://github.com/d3x0r/MarchingTetrahedra src/marchingtetrahedra3.js.download */
// The MIT License (MIT)
//
// Copyright (c) 2020 d3x0r
//
// 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.
/**
* Marching Tetrahedra in Javascript
*
* Based on Unique Research
*
* (Several bug fixes were made to deal with oriented faces)
*
* Javascript port by d3x0r
*/
const debug_ = false;
const zero_is_outside = true;
/*
// there is a long combination of possible 3-4 bits some 50(?) of
// which only these 6 apply in reality
this is the vertex references on the right, and which 'vert N' applies.
0 _ _ 1
|\ /|
\\2// (above page)
| | |
\|/
3
this is the line index applied. each 'bit' of valid is this number...
. ____0____ .
|\ /| 01 02 03 12 23 31
\ \_1 3_/ /
| \ / |
\ \ / /
\ . / (above page)
2| | |5
\ 4 /
| | |
\|/
.
const validCombinations = [
{ val:[1,1,1,0,0,0], // valid (vert 0, 0,1,2) 0 in, 0 out
},
{ val:[1,1,0,0,1,1], // valid 0,1,4,5 (0-3,1-2)
},
{ val:[1,0,1,1,1,0], // valid 0,2,3,4 (0-2,1-3)
},
{ val:[1,0,0,1,0,1], // valid (vert 1, 0,3,5)
},
{ val:[0,1,1,1,0,1], // valid 1,2,3,5 (0-1,2,3)
},
{ val:[0,1,0,1,1,0], // valid (vert 2, 1,3,4 )
},
{ val:[0,0,1,0,1,1], // valid (vert 3, 2,4,5 )
},
]
*/
// static working buffers
var sizes = 0;
const pointHolder = [null,null];
const crossHolder = [null,null];
var bits = null;
const geom = [
[0,0,0], // bottom layer
[1,0,0],
[0,1,0],
[1,1,0],
[0,0,1], // 5 top layer
[1,0,1], // 6
[0,1,1], // 7
[1,1,1], // 8
]
const linesOddMin = [ [0,2],[0,4],[4,6],[2,4], [0,1],[1,2],[1,4] , [4,5],[4,7] ];
const linesEvenMin = [ [0,2],[0,4],[4,6],[0,6], [0,1],[0,3],[0,5] , [4,5],[5,6] ];
const linesMin = [linesEvenMin,linesOddMin];
const cellOrigin = [0,0,0];
const vertToDataOrig = [
[ [ 2,3,6,0], [3,1,5,0], [4,6,5,0], [6,7,5,3], [0,6,5,3] ],
[ [ 0, 2,4,1], [3,1,7,2], [6,7,4,2], [4,7,5,1], [1,2,4,7] ],
];
// index with [odd] [tet_of_cube] [0-3 vertex]
// result is point data rectangular offset... (until modified)
const vertToData = [
[ [ 2,3,6,0], [3,1,5,0], [4,6,5,0], [6,7,5,3], [0,6,5,3] ],
[ [ 0, 2,4,1], [3,1,7,2], [6,7,4,2], [4,7,5,1], [1,2,4,7] ],
];
// update base index to resolved data cloud offset
var MarchingTetrahedra3 = (function() {
return function(data, dims) {
var vertices = []
, faces = [];
// values input to this are in 2 planes for lower and upper values
const dim0 = dims[0];
const dim1 = dims[1];
const dim2 = dims[2];
const dataOffset = [ 0,1, dim0, 1+dim0, 0 + dim0*dim1,1 + dim0*dim1,dim0 + dim0*dim1, 1+dim0 + dim0*dim1] ;
for( let a = 0; a < 2; a++ ) for( let b = 0; b < 5; b++ ) for( let c = 0; c < 4; c++ ) vertToData[a][b][c] = dataOffset[vertToDataOrig[a][b][c]];
if( dim0*dim1*9 > sizes ) {
sizes = dim0 * dim1 * 9;
bits = new Uint8Array(dim0*dim1);
pointHolder[0] = new Uint32Array(sizes);
pointHolder[1] = new Uint32Array(sizes);
crossHolder[0] = new Uint8Array(sizes);
crossHolder[1] = new Uint8Array(sizes);
}
// vertex paths 0-1 0-2, 0-3 1-2 2-3 3-1
// this is the offset from dataOffset to the related value.
// index with [odd] [tet_of_cube] [0-5 line index]
// result is computed point cloud data offset.
const edgeToComp = [
[ [ (dim0)*9+4, (dim0)*9+1, 0 , (dim0)*9+6 , 3 , 5 ]
, [ (1)*9+0 , 1*9+3 , 5 , 1*9+1 , 6 , 4 ]
, [ 2 , 7 , 1 , 8 , 6 , 3 ]
, [ (dim0)*9+7, 8 , (dim0)*9+6, (1)*9+2 , (1)*9+3, (1+dim0)*9+1 ]
, [ 3, 6, 5, 8, (1)*9+3, (dim0)*9+6]
],
[ [0, 1, 4, 3, 6, 5]
, [ (1)*9+0, (1+dim0)*9+1, (dim0)*9 + 4, 1*9+3, (dim0)*9+6, 5 ]
, [ (dim0)*9+7, 2, (dim0)*9+1, 8, 3, (dim0)*9+6 ]
, [ 8, 7, 6, (1)*9+2, (1)*9+1, (1)*9+3 ]
, [ 5, 6, (1)*9+3, 3, 8, (dim0)*9+6 ]
],
]
let firstSet = false;
let firstY = 0;
let firstX = 0;
for( var z = 0; z < dim2-1; z++ ) {
{
let tmp;
tmp = pointHolder[0]; pointHolder[0] = pointHolder[1]; pointHolder[1] = tmp;
tmp = crossHolder[0]; crossHolder[0] = crossHolder[1]; crossHolder[1] = tmp;
const points_ = pointHolder[1];
const crosses_ = crossHolder[1];
let points = pointHolder[0];//new Array((dim0+1)+(dim1+1)*9);
//points.length = 0;
let crosses = crossHolder[0];
//crosses.length = 0;
let odd = 0;
let zOdd = z & 1;
//if( z !== 5 ) return;
cellOrigin[2] = z-0.5;
for( var y = 0; y < dim1; y++ ) {
cellOrigin[1] = y-0.5;
for( var x = 0; x < dim0; x++ ) {
odd = (( x + y ) &1) ^ zOdd;
cellOrigin[0] = x-0.5;
const baseHere = (x+0 + y*dim0)*9;
const baseOffset = x+0 + y*dim0 + z * dim0*dim1;
const lineArray = linesMin[odd];
bits[x+y*dim0] = 0;
for( let l = 0; l < 9; l++ ) {
const p0 = lineArray[l][0];
const p1 = lineArray[l][1];
const data0=baseOffset+dataOffset[p0];
const data1=baseOffset+dataOffset[p1];
// when we actually do layers, this matters.
if( z ) {
// copy data from old table...
if( !(p0 & 4) && !(p1 & 4) ) {
switch(l) {
case 0:
points[baseHere+l] = points_[baseHere+2];
crosses[baseHere+l] = crosses_[baseHere+2];
break;
case 5:
points[baseHere+l] = points_[baseHere+8];
crosses[baseHere+l] = crosses_[baseHere+8];
break;
case 4:
points[baseHere+l] = points_[baseHere+7];
crosses[baseHere+l] = crosses_[baseHere+7];
break;
default:
debugger;
}
bits[x+y*dim0] |= crosses[baseHere+l]; // set any 1 bit is set here.
continue;
}
}
if( (x == (dim0-1)) &&( (p0 & 1) || (p1 &1) )) {
// this is an overflow, need to push fake data....
points[baseHere+l] = null;
crosses[baseHere+l] = 0;
continue;
}
if( (y == (dim1-1)) &&( (p0 & 2) || (p1 &2) )) {
// this is an overflow, need to push fake data....
points[baseHere+l] = null;
crosses[baseHere+l] = 0;
continue;
}
if( (z == (dim2-1)) &&( (p0 & 4) || (p1 & 4) )) {
// this is an overflow, need to push fake data....
points[baseHere+l] = null;
crosses[baseHere+l] = 0;
continue;
}
d=-data[data0]; e=-data[data1];
if( ( d <= 0 && e >0 )|| (d > 0 && e <= 0 ) ){
let t;
//console.log( "x, y is a cross:", (x+y*dim0)*9, crosses.length, l, x, y, p0, p1, data0, data1, `d:${d} e:${e}` );
if( e <= 0 ) {
(t = -e/(d-e));
points[baseHere+l] = (vertices.push([cellOrigin[0]+ geom[p1][0]+( geom[p0][0]- geom[p1][0])* t ,cellOrigin[1]+ geom[p1][1]+( geom[p0][1]- geom[p1][1])* t, cellOrigin[2]+ geom[p1][2]+( geom[p0][2]- geom[p1][2])* t ]),vertices.length-1);
} else {
(t = -d/(e-d));
points[baseHere+l] =( vertices.push([cellOrigin[0]+ geom[p0][0]+( geom[p1][0]- geom[p0][0])* t
,cellOrigin[1]+ geom[p0][1]+( geom[p1][1]- geom[p0][1])* t
, cellOrigin[2]+ geom[p0][2]+( geom[p1][2]- geom[p0][2])* t ]),vertices.length-1 );
}
crosses[baseHere+l] = 1;
bits[x+y*dim0] = 1; // set any 1 bit is set here.
}
else {
//console.log( "x, y is NOT cross:", (x+y*dim0)*9, crosses.length, l, x, y, p0, p1, data0, data1, `d:${d} e:${e}` );
crosses[baseHere+l] = 0;
}
}
}
}
if( debug_ ) {
function zz(v) { var s = ' 2,7,8 3,1,0 1,4,6\n';for( var y = 0; y < dim1; y++ ) { s += `y:${y} \n`;
for( var x = 0; x < dim0; x++ ) {s += bits[(y*dim0+x)];s += " " } s += "\n";
for( var x = 0; x < dim0; x++ ) {s += (v[(y*dim0+x)*9 + 2]?"X":"_") + (v[(y*dim0+x)*9 + 8]?"X":"_") + (v[(y*dim0+x)*9 + 7]?"X":"_");s += " " } s += "\n";
for( var x = 0; x < dim0; x++ ) {s += (v[(y*dim0+x)*9 + 3]?"X":"_") + (v[(y*dim0+x)*9 + 1]?"X":"_") + (v[(y*dim0+x)*9 + 6]?"X":"_");s += " " } s += "\n";
for( var x = 0; x < dim0; x++ ) {s += (v[(y*dim0+x)*9 + 0]?"X":"_") + (v[(y*dim0+x)*9 + 5]?"X":"_") + (v[(y*dim0+x)*9 + 4]?"X":"_");s += " " } s += "\n\n"; }
return s;
}
console.log( "relavent computations:", zz( crosses,null), zz( points ) );
}
for( var y = 0; y < dim1-1; y++ ) {
for( var x = 0; x < dim0-1; x++ ) {
if( !bits[x+y*dim0] ) {
if( x >= (dim0-2))continue;
if( y >= (dim1-2))continue;
if( !bits[(x+1)+y*dim0] && !bits[(x)+(y+1)*dim0]) {
continue;
}
}
const baseOffset = (x + (y*dim0))*9;
const dataOffset = (x + (y*dim0)) + z*dim1*dim0;
odd = (( x + y ) &1) ^ zOdd;
for( tet = 0; tet < 5; tet++ ) {
if( crosses[ baseOffset+edgeToComp[odd][tet][0] ] ) {
//console.log( `Output: odd:${odd} tet:${tet} x:${x} y:${y} a:${JSON.stringify(a)}` );
if( crosses[ baseOffset+edgeToComp[odd][tet][1] ] ) {
if( crosses[ baseOffset+edgeToComp[odd][tet][2] ] ) {
if( data[dataOffset+vertToData[odd][tet][0]] >= 0 ) {
faces.push([ points[baseOffset+edgeToComp[odd][tet][1]]
,points[baseOffset+edgeToComp[odd][tet][0]]
,points[baseOffset+edgeToComp[odd][tet][2]]] );
} else {
faces.push([ points[baseOffset+edgeToComp[odd][tet][0]]
,points[baseOffset+edgeToComp[odd][tet][1]]
,points[baseOffset+edgeToComp[odd][tet][2]]] );
}
} else {
if( crosses[ baseOffset+edgeToComp[odd][tet][4] ] ) {
//if( !a[5] ) {
// console.log( "Expected point 5 is missing." );
//}
if( data[dataOffset+vertToData[odd][tet][0]] >= 0 ) {
faces.push([ points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
faces.push([ points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
} else {
faces.push([ points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
faces.push([ points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][1]]
] );
}
} else {
console.log( "Expecting point 4 missing" );
}
}
} else {
if( crosses[ baseOffset+edgeToComp[odd][tet][2] ] ) {
//if( a[3] && crosses[ baseOffset+edgeToComp[odd][tet][4] ]/* && !a[5] */ ) {
if( data[dataOffset+vertToData[odd][tet][0]] >= 0 ) {
faces.push([ points[baseOffset+edgeToComp[odd][tet][3]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
faces.push([ points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][2]]
] );
} else {
faces.push([ points[baseOffset+edgeToComp[odd][tet][2]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
faces.push([ points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][3]]
] );
}
//} else {
// console.log( "Failed to have proper intersections..." );
//}
}else {
//if( a[3] && !crosses[ baseOffset+edgeToComp[odd][tet][4] ] && a[5] ) {
if( data[dataOffset+vertToData[odd][tet][1]] >= 0 )
faces.push([ points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][3]]
] );
else
faces.push([ points[baseOffset+edgeToComp[odd][tet][0]]
, points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][3]]
] );
//} else {
// console.log( "Failed to have proper intersections..." );
//}
}
}
} else {
if( crosses[ baseOffset+edgeToComp[odd][tet][1] ] ) {
if( crosses[ baseOffset+edgeToComp[odd][tet][2] ] ) {
//if( !debug_ && ( a[3] && !crosses[ baseOffset+edgeToComp[odd][tet][4] ] && a[5] ) ) {
if( data[dataOffset+vertToData[odd][tet][0]] >= 0 ) {
faces.push([ points[baseOffset+edgeToComp[odd][tet][2]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
faces.push([ points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][3]]
] );
}else{
faces.push([ points[baseOffset+edgeToComp[odd][tet][3]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
faces.push([ points[baseOffset+edgeToComp[odd][tet][5]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][2]]
] );
}
//} else {
// console.log( "Failed to have proper intersections..." );
//}
} else {
//if( !debug_ && ( a[3] && crosses[ baseOffset+edgeToComp[odd][tet][4] ] && !a[5] )) {
if( data[dataOffset+vertToData[odd][tet][2]] >= 0 )
faces.push([points[baseOffset+edgeToComp[odd][tet][3]]
, points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
else
faces.push([points[baseOffset+edgeToComp[odd][tet][1]]
, points[baseOffset+edgeToComp[odd][tet][3]]
, points[baseOffset+edgeToComp[odd][tet][4]]
] );
//} else {
// console.log( "Expecting state mismatch (1)3,4,5 missing" );
//}
}
} else {
if( crosses[ baseOffset+edgeToComp[odd][tet][2] ] ) {
//if( !debug_ && ( !a[3] && crosses[ baseOffset+edgeToComp[odd][tet][4] ] && a[5] ) ){
if( data[dataOffset+vertToData[odd][tet][3]] >= 0 )
faces.push([points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][2]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
else
faces.push([points[baseOffset+edgeToComp[odd][tet][2]]
, points[baseOffset+edgeToComp[odd][tet][4]]
, points[baseOffset+edgeToComp[odd][tet][5]]
] );
//} else {
// console.log( "Expecting state mismatch (2)3,4,5 missing" );
//}
} else {
//if( a[3] || crosses[ baseOffset+edgeToComp[odd][tet][4] ] || a[5] )
// console.log( "Impossible intersection result" );
}
}
}
}
}
}
}
}
return { vertices: vertices, faces: faces };
}
})();
if("undefined" != typeof exports) {
exports.mesher = MarchingTetrahedra3;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment