voxel = function (opts) {
if (!opts.generateVoxelChunk) opts.generateVoxelChunk = function(low, high) {
return generate(low, high, module.exports.generator['Valley'])
}
return chunker(opts)
}n/a
function Chunker(opts) {
this.distance = opts.chunkDistance || 2
this.chunkSize = opts.chunkSize || 32
this.chunkPad = opts.chunkPad !== undefined ? opts.chunkPad : 0
this.cubeSize = opts.cubeSize || 25
this.generateVoxelChunk = opts.generateVoxelChunk
this.chunks = {}
this.meshes = {}
if (this.chunkSize & this.chunkSize-1 !== 0)
throw new Error('chunkSize must be a power of 2')
var bits = 0;
for (var size = this.chunkSize; size > 0; size >>= 1) bits++;
this.chunkBits = bits - 1;
this.chunkMask = (1 << this.chunkBits) - 1
this.chunkPadHalf = this.chunkPad >> 1
}n/a
chunker = function (opts) {
return new Chunker(opts)
}n/a
function generate(lo, hi, fn, game) {
// To fix the display gaps, we need to pad the bounds
lo[0]--
lo[1]--
lo[2]--
hi[0]++
hi[1]++
hi[2]++
var dims = [hi[2]-lo[2], hi[1]-lo[1], hi[0]-lo[0]]
var data = ndarray(new Uint16Array(dims[2] * dims[1] * dims[0]), dims)
for (var k = lo[2]; k < hi[2]; k++)
for (var j = lo[1]; j < hi[1]; j++)
for(var i = lo[0]; i < hi[0]; i++) {
data.set(k-lo[2], j-lo[1], i-lo[0], fn(i, j, k))
}
return data
}...
```
in a browser:
use `voxel-browser.js`
# usage
## require('voxel').generate(low, high, iterator)
where `low` and `high` are `[x, y, z]` start and end positions to iterate over and `iterator` is the function that visits each voxel
returns an object like this: `{ "voxels": "a 1D Int32Array filled with voxel data", "dims": [x, y,
z] }`
example that creates randomly colored voxels:
...generateExamples = function () {
return {
'Sphere': generate([-16,-16,-16], [16,16,16], module.exports.generator['Sphere']),
'Noise': generate([0,0,0], [16,16,16], module.exports.generator['Noise']),
'Dense Noise': generate([0,0,0], [16,16,16], module.exports.generator['Dense Noise']),
'Checker': generate([0,0,0], [8,8,8], module.exports.generator['Checker']),
'Hill': generate([-16, 0, -16], [16,16,16], module.exports.generator['Hill']),
'Valley': generate([0,0,0], [32,32,32], module.exports.generator['Valley']),
'Hilly Terrain': generate([0, 0, 0], [32,32,32], module.exports.generator['Hilly Terrain'])
}
}...
`meshers` is an object with `stupid`, `culled`, `monotone` and `greedy` mesher functions. you probably want to just use `greedy`.
all mesher functions accept voxel data in the format the gets returned by the `generate` function.
## require('voxel').generator
an object that contains a bunch of voxel generation functions to play with, from http://mikolalysenko.github.com/MinecraftMeshes2
/
## require('voxel').generateExamples()
returns an object that contains a bunch of pre-generated voxel geometries to play with, from http://mikolalysenko.github.com/MinecraftMeshes2
/
# license
MIT
...scale = function ( x, fromLow, fromHigh, toLow, toHigh ) {
return ( x - fromLow ) * ( toHigh - toLow ) / ( fromHigh - fromLow ) + toLow
}n/a
function Chunker(opts) {
this.distance = opts.chunkDistance || 2
this.chunkSize = opts.chunkSize || 32
this.chunkPad = opts.chunkPad !== undefined ? opts.chunkPad : 0
this.cubeSize = opts.cubeSize || 25
this.generateVoxelChunk = opts.generateVoxelChunk
this.chunks = {}
this.meshes = {}
if (this.chunkSize & this.chunkSize-1 !== 0)
throw new Error('chunkSize must be a power of 2')
var bits = 0;
for (var size = this.chunkSize; size > 0; size >>= 1) bits++;
this.chunkBits = bits - 1;
this.chunkMask = (1 << this.chunkBits) - 1
this.chunkPadHalf = this.chunkPad >> 1
}n/a
function EventEmitter() {
EventEmitter.init.call(this);
}n/a
chunkAtCoordinates = function (x, y, z) {
var bits = this.chunkBits;
var cx = x >> bits;
var cy = y >> bits;
var cz = z >> bits;
var chunkPos = [cx, cy, cz];
return chunkPos;
}...
}
Chunker.prototype.chunkAtPosition = function(position) {
var cubeSize = this.cubeSize;
var x = Math.floor(position[0] / cubeSize)
var y = Math.floor(position[1] / cubeSize)
var z = Math.floor(position[2] / cubeSize)
var chunkPos = this.chunkAtCoordinates(x, y, z)
return chunkPos
};
Chunker.prototype.voxelIndexFromCoordinates = function(x, y, z) {
throw new Error('Chunker.prototype.voxelIndexFromCoordinates removed, use voxelAtCoordinates')
}
...chunkAtPosition = function (position) {
var cubeSize = this.cubeSize;
var x = Math.floor(position[0] / cubeSize)
var y = Math.floor(position[1] / cubeSize)
var z = Math.floor(position[2] / cubeSize)
var chunkPos = this.chunkAtCoordinates(x, y, z)
return chunkPos
}...
this.chunkMask = (1 << this.chunkBits) - 1
this.chunkPadHalf = this.chunkPad >> 1
}
inherits(Chunker, events.EventEmitter)
Chunker.prototype.nearbyChunks = function(position, distance) {
var current = this.chunkAtPosition(position)
var x = current[0]
var y = current[1]
var z = current[2]
var dist = distance || this.distance
var nearby = []
for (var cx = (x - dist); cx !== (x + dist); ++cx) {
for (var cy = (y - dist); cy !== (y + dist); ++cy) {
...generateChunk = function (x, y, z) {
var self = this
var bounds = this.getBounds(x, y, z)
var chunk = this.generateVoxelChunk(bounds[0], bounds[1], x, y, z)
var position = [x, y, z]
chunk.position = position
this.chunks[position.join('|')] = chunk
return chunk
}...
var chunker = voxel({chunkDistance: 2, chunkSize: 32, cubeSize: 1})
t.deepEqual(chunker.nearbyChunks([0, 0, 0], 1), [[-1, -1, -1], [-1, -1, 0], [-1, 0, -1], [-1, 0, 0], [0, -1, -1], [0, -1, 0], [
0, 0, -1], [0, 0, 0]])
t.end()
})
test('generateChunk', function (t) {
var chunker = voxel({chunkDistance: 2, chunkSize: 32, cubeSize: 1})
chunker.generateChunk(0, 0, 0)
t.equal(!!chunker.chunks['0|0|0'], true)
chunker.generateChunk(1, 0, 0)
t.equal(!!chunker.chunks['1|0|0'], true)
chunker.generateChunk(-1, 0, 0)
t.equal(!!chunker.chunks['-1|0|0'], true)
t.end()
})
...getBounds = function (x, y, z) {
var bits = this.chunkBits
var low = [x << bits, y << bits, z << bits]
var high = [(x+1) << bits, (y+1) << bits, (z+1) << bits]
return [low, high]
}...
var low = [x << bits, y << bits, z << bits]
var high = [(x+1) << bits, (y+1) << bits, (z+1) << bits]
return [low, high]
}
Chunker.prototype.generateChunk = function(x, y, z) {
var self = this
var bounds = this.getBounds(x, y, z)
var chunk = this.generateVoxelChunk(bounds[0], bounds[1], x, y, z)
var position = [x, y, z]
chunk.position = position
this.chunks[position.join('|')] = chunk
return chunk
}
...nearbyChunks = function (position, distance) {
var current = this.chunkAtPosition(position)
var x = current[0]
var y = current[1]
var z = current[2]
var dist = distance || this.distance
var nearby = []
for (var cx = (x - dist); cx !== (x + dist); ++cx) {
for (var cy = (y - dist); cy !== (y + dist); ++cy) {
for (var cz = (z - dist); cz !== (z + dist); ++cz) {
nearby.push([cx, cy, cz])
}
}
}
return nearby
}...
}
}
return nearby
}
Chunker.prototype.requestMissingChunks = function(position) {
var self = this
this.nearbyChunks(position).map(function(chunk) {
if (!self.chunks[chunk.join('|')]) {
self.emit('missingChunk', chunk)
}
})
}
Chunker.prototype.getBounds = function(x, y, z) {
...requestMissingChunks = function (position) {
var self = this
this.nearbyChunks(position).map(function(chunk) {
if (!self.chunks[chunk.join('|')]) {
self.emit('missingChunk', chunk)
}
})
}...
chunker.generateChunk(0, 0, 0)
chunker.generateChunk(1, 0, 0)
chunker.generateChunk(-1, 0, 0)
var missing = []
chunker.on('missingChunk', function (pos) {
missing.push(pos)
})
chunker.requestMissingChunks([0, 0, 0])
t.deepEqual(missing, [[-1, -1, -1], [-1, -1, 0], [-1, 0, -1], [0, -1, -1], [0, -1, 0], [0, 0, -1]])
t.end()
})
test('voxelAtCoordinates', function (t) {
var chunker = voxel({chunkDistance: 2, chunkSize: 32, cubeSize: 1})
chunker.generateChunk(0, 0, 0)
...voxelAtCoordinates = function (x, y, z, val) {
var ckey = this.chunkAtCoordinates(x, y, z).join('|')
var chunk = this.chunks[ckey]
if (!chunk) return false
var mask = this.chunkMask
var h = this.chunkPadHalf
var mx = x & mask
var my = y & mask
var mz = z & mask
var v = chunk.get(mx+h, my+h, mz+h)
if (typeof val !== 'undefined') {
chunk.set(mx+h, my+h, mz+h, val)
}
return v
}...
}
Chunker.prototype.voxelAtPosition = function(pos, val) {
var cubeSize = this.cubeSize;
var x = Math.floor(pos[0] / cubeSize)
var y = Math.floor(pos[1] / cubeSize)
var z = Math.floor(pos[2] / cubeSize)
var v = this.voxelAtCoordinates(x, y, z, val)
return v;
}
...voxelAtPosition = function (pos, val) {
var cubeSize = this.cubeSize;
var x = Math.floor(pos[0] / cubeSize)
var y = Math.floor(pos[1] / cubeSize)
var z = Math.floor(pos[2] / cubeSize)
var v = this.voxelAtCoordinates(x, y, z, val)
return v;
}...
t.equal(chunker.voxelAtCoordinates(-1, 0, 0), false)
t.end()
})
test('voxelAtPosition', function (t) {
var chunker = voxel({chunkDistance: 2, chunkSize: 32, cubeSize: 1})
chunker.generateChunk(0, 0, 0)
t.equal(chunker.voxelAtPosition([0, 16, 0], 1), 0)
t.equal(chunker.voxelAtPosition([0, 16.9999, 0]), 1)
t.end()
})
...voxelIndexFromCoordinates = function (x, y, z) {
throw new Error('Chunker.prototype.voxelIndexFromCoordinates removed, use voxelAtCoordinates')
}n/a
chunker = function (opts) {
return new Chunker(opts)
}n/a
function Chunker(opts) {
this.distance = opts.chunkDistance || 2
this.chunkSize = opts.chunkSize || 32
this.chunkPad = opts.chunkPad !== undefined ? opts.chunkPad : 0
this.cubeSize = opts.cubeSize || 25
this.generateVoxelChunk = opts.generateVoxelChunk
this.chunks = {}
this.meshes = {}
if (this.chunkSize & this.chunkSize-1 !== 0)
throw new Error('chunkSize must be a power of 2')
var bits = 0;
for (var size = this.chunkSize; size > 0; size >>= 1) bits++;
this.chunkBits = bits - 1;
this.chunkMask = (1 << this.chunkBits) - 1
this.chunkPadHalf = this.chunkPad >> 1
}n/a
function CulledMesh(volume, dims) {
//Precalculate direction vectors for convenience
var dir = new Array(3);
for(var i=0; i<3; ++i) {
dir[i] = [[0,0,0], [0,0,0]];
dir[i][0][(i+1)%3] = 1;
dir[i][1][(i+2)%3] = 1;
}
//March over the volume
var vertices = []
, faces = []
, x = [0,0,0]
, B = [[false,true] //Incrementally update bounds (this is a bit ugly)
,[false,true]
,[false,true]]
, n = -dims[0]*dims[1];
for( B[2]=[false,true],x[2]=-1; x[2]<dims[2]; B[2]=[true,(++x[2]<dims[2]-1)])
for(n-=dims[0],B[1]=[false,true],x[1]=-1; x[1]<dims[1]; B[1]=[true,(++x[1]<dims[1]-1)])
for(n-=1, B[0]=[false,true],x[0]=-1; x[0]<dims[0]; B[0]=[true,(++x[0]<dims[0]-1)], ++n) {
//Read current voxel and 3 neighboring voxels using bounds check results
var p = (B[0][0] && B[1][0] && B[2][0]) ? volume[n] : 0
, b = [ (B[0][1] && B[1][0] && B[2][0]) ? volume[n+1] : 0
, (B[0][0] && B[1][1] && B[2][0]) ? volume[n+dims[0]] : 0
, (B[0][0] && B[1][0] && B[2][1]) ? volume[n+dims[0]*dims[1]] : 0
];
//Generate faces
for(var d=0; d<3; ++d)
if((!!p) !== (!!b[d])) {
var s = !p ? 1 : 0;
var t = [x[0],x[1],x[2]]
, u = dir[d][s]
, v = dir[d][s^1];
++t[d];
var vertex_count = vertices.length;
vertices.push([t[0], t[1], t[2] ]);
vertices.push([t[0]+u[0], t[1]+u[1], t[2]+u[2] ]);
vertices.push([t[0]+u[0]+v[0], t[1]+u[1]+v[1], t[2]+u[2]+v[2]]);
vertices.push([t[0] +v[0], t[1] +v[1], t[2] +v[2]]);
faces.push([vertex_count, vertex_count+1, vertex_count+2, vertex_count+3, s ? b[d] : p]);
}
}
return { vertices:vertices, faces:faces };
}n/a
Checker = function (i, j, k) {
return !!((i+j+k)&1) ? (((i^j^k)&2) ? 1 : 0xffffff) : 0;
}n/a
Hill = function (i, j, k) {
return j <= 16 * Math.exp(-(i*i + k*k) / 64) ? 1 : 0;
}n/a
Noise = function (i, j, k) {
return Math.random() < 0.1 ? Math.random() * 0xffffff : 0;
}n/a
Sphere = function (i, j, k) {
return i*i+j*j+k*k <= 16*16 ? 1 : 0
}n/a
Valley = function (i, j, k) {
return j <= (i*i + k*k) * 31 / (32*32*2) + 1 ? 1 + (1<<15) : 0;
}n/a
mesher = function (volume, dims) {
var vertices = [], faces = []
, dimsX = dims[0]
, dimsY = dims[1]
, dimsXY = dimsX * dimsY;
//Sweep over 3-axes
for(var d=0; d<3; ++d) {
var i, j, k, l, w, W, h, n, c
, u = (d+1)%3
, v = (d+2)%3
, x = [0,0,0]
, q = [0,0,0]
, du = [0,0,0]
, dv = [0,0,0]
, dimsD = dims[d]
, dimsU = dims[u]
, dimsV = dims[v]
, qdimsX, qdimsXY
, xd
if (mask.length < dimsU * dimsV) {
mask = new Int32Array(dimsU * dimsV);
}
q[d] = 1;
x[d] = -1;
qdimsX = dimsX * q[1]
qdimsXY = dimsXY * q[2]
// Compute mask
while (x[d] < dimsD) {
xd = x[d]
n = 0;
for(x[v] = 0; x[v] < dimsV; ++x[v]) {
for(x[u] = 0; x[u] < dimsU; ++x[u], ++n) {
var a = xd >= 0 && volume[x[0] + dimsX * x[1] + dimsXY * x[2] ]
, b = xd < dimsD-1 && volume[x[0]+q[0] + dimsX * x[1] + qdimsX + dimsXY * x[2] + qdimsXY]
if (a ? b : !b) {
mask[n] = 0; continue;
}
mask[n] = a ? a : -b;
}
}
++x[d];
// Generate mesh for mask using lexicographic ordering
n = 0;
for (j=0; j < dimsV; ++j) {
for (i=0; i < dimsU; ) {
c = mask[n];
if (!c) {
i++; n++; continue;
}
//Compute width
w = 1;
while (c === mask[n+w] && i+w < dimsU) w++;
//Compute height (this is slightly awkward)
for (h=1; j+h < dimsV; ++h) {
k = 0;
while (k < w && c === mask[n+k+h*dimsU]) k++
if (k < w) break;
}
// Add quad
// The du/dv arrays are reused/reset
// for each iteration.
du[d] = 0; dv[d] = 0;
x[u] = i; x[v] = j;
if (c > 0) {
dv[v] = h; dv[u] = 0;
du[u] = w; du[v] = 0;
} else {
c = -c;
du[v] = h; du[u] = 0;
dv[u] = w; dv[v] = 0;
}
var vertex_count = vertices.length;
vertices.push([x[0], x[1], x[2] ]);
vertices.push([x[0]+du[0], x[1]+du[1], x[2]+du[2] ]);
vertices.push([x[0]+du[0]+dv[0], x[1]+du[1]+dv[1], x[2]+du[2]+dv[2]]);
vertices.push([x[0] +dv[0], x[1] +dv[1], x[2] +dv[2]]);
faces.push([vertex_count, vertex_count+1, vertex_count+2, vertex_count+3, c]);
//Zero-out mask
W = n + w;
for(l=0; l<h; ++l) {
for(k=n; k<W; ++k) {
mask[k+l*dimsU] = 0;
}
}
//Increment counters and continue
i += w; n += w;
}
}
}
}
return { vertices:vertices, faces:faces };
}n/a
function CulledMesh(volume, dims) {
//Precalculate direction vectors for convenience
var dir = new Array(3);
for(var i=0; i<3; ++i) {
dir[i] = [[0,0,0], [0,0,0]];
dir[i][0][(i+1)%3] = 1;
dir[i][1][(i+2)%3] = 1;
}
//March over the volume
var vertices = []
, faces = []
, x = [0,0,0]
, B = [[false,true] //Incrementally update bounds (this is a bit ugly)
,[false,true]
,[false,true]]
, n = -dims[0]*dims[1];
for( B[2]=[false,true],x[2]=-1; x[2]<dims[2]; B[2]=[true,(++x[2]<dims[2]-1)])
for(n-=dims[0],B[1]=[false,true],x[1]=-1; x[1]<dims[1]; B[1]=[true,(++x[1]<dims[1]-1)])
for(n-=1, B[0]=[false,true],x[0]=-1; x[0]<dims[0]; B[0]=[true,(++x[0]<dims[0]-1)], ++n) {
//Read current voxel and 3 neighboring voxels using bounds check results
var p = (B[0][0] && B[1][0] && B[2][0]) ? volume[n] : 0
, b = [ (B[0][1] && B[1][0] && B[2][0]) ? volume[n+1] : 0
, (B[0][0] && B[1][1] && B[2][0]) ? volume[n+dims[0]] : 0
, (B[0][0] && B[1][0] && B[2][1]) ? volume[n+dims[0]*dims[1]] : 0
];
//Generate faces
for(var d=0; d<3; ++d)
if((!!p) !== (!!b[d])) {
var s = !p ? 1 : 0;
var t = [x[0],x[1],x[2]]
, u = dir[d][s]
, v = dir[d][s^1];
++t[d];
var vertex_count = vertices.length;
vertices.push([t[0], t[1], t[2] ]);
vertices.push([t[0]+u[0], t[1]+u[1], t[2]+u[2] ]);
vertices.push([t[0]+u[0]+v[0], t[1]+u[1]+v[1], t[2]+u[2]+v[2]]);
vertices.push([t[0] +v[0], t[1] +v[1], t[2] +v[2]]);
faces.push([vertex_count, vertex_count+1, vertex_count+2, vertex_count+3, s ? b[d] : p]);
}
}
return { vertices:vertices, faces:faces };
}n/a
greedy = function (volume, dims) {
var vertices = [], faces = []
, dimsX = dims[0]
, dimsY = dims[1]
, dimsXY = dimsX * dimsY;
//Sweep over 3-axes
for(var d=0; d<3; ++d) {
var i, j, k, l, w, W, h, n, c
, u = (d+1)%3
, v = (d+2)%3
, x = [0,0,0]
, q = [0,0,0]
, du = [0,0,0]
, dv = [0,0,0]
, dimsD = dims[d]
, dimsU = dims[u]
, dimsV = dims[v]
, qdimsX, qdimsXY
, xd
if (mask.length < dimsU * dimsV) {
mask = new Int32Array(dimsU * dimsV);
}
q[d] = 1;
x[d] = -1;
qdimsX = dimsX * q[1]
qdimsXY = dimsXY * q[2]
// Compute mask
while (x[d] < dimsD) {
xd = x[d]
n = 0;
for(x[v] = 0; x[v] < dimsV; ++x[v]) {
for(x[u] = 0; x[u] < dimsU; ++x[u], ++n) {
var a = xd >= 0 && volume[x[0] + dimsX * x[1] + dimsXY * x[2] ]
, b = xd < dimsD-1 && volume[x[0]+q[0] + dimsX * x[1] + qdimsX + dimsXY * x[2] + qdimsXY]
if (a ? b : !b) {
mask[n] = 0; continue;
}
mask[n] = a ? a : -b;
}
}
++x[d];
// Generate mesh for mask using lexicographic ordering
n = 0;
for (j=0; j < dimsV; ++j) {
for (i=0; i < dimsU; ) {
c = mask[n];
if (!c) {
i++; n++; continue;
}
//Compute width
w = 1;
while (c === mask[n+w] && i+w < dimsU) w++;
//Compute height (this is slightly awkward)
for (h=1; j+h < dimsV; ++h) {
k = 0;
while (k < w && c === mask[n+k+h*dimsU]) k++
if (k < w) break;
}
// Add quad
// The du/dv arrays are reused/reset
// for each iteration.
du[d] = 0; dv[d] = 0;
x[u] = i; x[v] = j;
if (c > 0) {
dv[v] = h; dv[u] = 0;
du[u] = w; du[v] = 0;
} else {
c = -c;
du[v] = h; du[u] = 0;
dv[u] = w; dv[v] = 0;
}
var vertex_count = vertices.length;
vertices.push([x[0], x[1], x[2] ]);
vertices.push([x[0]+du[0], x[1]+du[1], x[2]+du[2] ]);
vertices.push([x[0]+du[0]+dv[0], x[1]+du[1]+dv[1], x[2]+du[2]+dv[2]]);
vertices.push([x[0] +dv[0], x[1] +dv[1], x[2] +dv[2]]);
faces.push([vertex_count, vertex_count+1, vertex_count+2, vertex_count+3, c]);
//Zero-out mask
W = n + w;
for(l=0; l<h; ++l) {
for(k=n; k<W; ++k) {
mask[k+l*dimsU] = 0;
}
}
//Increment counters and continue
i += w; n += w;
}
}
}
}
return { vertices:vertices, faces:faces };
}n/a
monotone = function (volume, dims) {
function f(i,j,k) {
return volume[i + dims[0] * (j + dims[1] * k)];
}
//Sweep over 3-axes
var vertices = [], faces = [];
for(var d=0; d<3; ++d) {
var i, j, k
, u = (d+1)%3 //u and v are orthogonal directions to d
, v = (d+2)%3
, x = new Int32Array(3)
, q = new Int32Array(3)
, runs = new Int32Array(2 * (dims[u]+1))
, frontier = new Int32Array(dims[u]) //Frontier is list of pointers to polygons
, next_frontier = new Int32Array(dims[u])
, left_index = new Int32Array(2 * dims[v])
, right_index = new Int32Array(2 * dims[v])
, stack = new Int32Array(24 * dims[v])
, delta = [[0,0], [0,0]];
//q points along d-direction
q[d] = 1;
//Initialize sentinel
for(x[d]=-1; x[d]<dims[d]; ) {
// --- Perform monotone polygon subdivision ---
var n = 0
, polygons = []
, nf = 0;
for(x[v]=0; x[v]<dims[v]; ++x[v]) {
//Make one pass over the u-scan line of the volume to run-length encode polygon
var nr = 0, p = 0, c = 0;
for(x[u]=0; x[u]<dims[u]; ++x[u], p = c) {
//Compute the type for this face
var a = (0 <= x[d] ? f(x[0], x[1], x[2]) : 0)
, b = (x[d] < dims[d]-1 ? f(x[0]+q[0], x[1]+q[1], x[2]+q[2]) : 0);
c = a;
if((!a) === (!b)) {
c = 0;
} else if(!a) {
c = -b;
}
//If cell type doesn't match, start a new run
if(p !== c) {
runs[nr++] = x[u];
runs[nr++] = c;
}
}
//Add sentinel run
runs[nr++] = dims[u];
runs[nr++] = 0;
//Update frontier by merging runs
var fp = 0;
for(var i=0, j=0; i<nf && j<nr-2; ) {
var p = polygons[frontier[i]]
, p_l = p.left[p.left.length-1][0]
, p_r = p.right[p.right.length-1][0]
, p_c = p.color
, r_l = runs[j] //Start of run
, r_r = runs[j+2] //End of run
, r_c = runs[j+1]; //Color of run
//Check if we can merge run with polygon
if(r_r > p_l && p_r > r_l && r_c === p_c) {
//Merge run
p.merge_run(x[v], r_l, r_r);
//Insert polygon into frontier
next_frontier[fp++] = frontier[i];
++i;
j += 2;
} else {
//Check if we need to advance the run pointer
if(r_r <= p_r) {
if(!!r_c) {
var n_poly = new MonotonePolygon(r_c, x[v], r_l, r_r);
next_frontier[fp++] = polygons.length;
polygons.push(n_poly);
}
j += 2;
}
//Check if we need to advance the frontier pointer
if(p_r <= r_r) {
p.close_off(x[v]);
++i;
}
}
}
//Close off any residual polygons
for(; i<nf; ++i) {
polygons[frontier[i]].close_off(x[v]);
}
//Add any extra runs to frontier
for(; j<nr-2; j+=2) {
var r_l = runs[j]
, r_r = runs[j+2]
, r_c = runs[j+1];
if(!!r_c) {
var n_poly = new MonotonePolygon(r_c, x[v], r_l, r_r);
next_frontier[fp++] = polygons.length;
polygons.push(n_poly);
}
}
//Swap frontiers
var tmp = next_frontier;
next_frontier = frontier;
frontier = tmp;
nf = fp;
}
//Close off frontier
for(var i=0; i<nf; ++i) {
var p = polygons[frontier[i]];
p.close_off(dims[v]);
}
// --- Monotone subdivision of polygon is complete at this point ---
x[d]++;
//Now we just need to triangulate each monotone polygon
for(var i=0; i<polygons.length; ++i) {
var p = polygons[i]
, c = p.color
, flipped = false;
if(c < 0) {
flipped = true;
c = -c;
}
for(var j ...n/a
function StupidMesh(volume, dims) {
var vertices = [], faces = [], x = [0,0,0], n = 0;
for(x[2]=0; x[2]<dims[2]; ++x[2])
for(x[1]=0; x[1]<dims[1]; ++x[1])
for(x[0]=0; x[0]<dims[0]; ++x[0], ++n)
if(!!volume[n]) {
for(var d=0; d<3; ++d) {
var t = [x[0], x[1], x[2]]
, u = [0,0,0]
, v = [0,0,0];
u[(d+1)%3] = 1;
v[(d+2)%3] = 1;
for(var s=0; s<2; ++s) {
t[d] = x[d] + s;
var tmp = u;
u = v;
v = tmp;
var vertex_count = vertices.length;
vertices.push([t[0], t[1], t[2] ]);
vertices.push([t[0]+u[0], t[1]+u[1], t[2]+u[2] ]);
vertices.push([t[0]+u[0]+v[0], t[1]+u[1]+v[1], t[2]+u[2]+v[2]]);
vertices.push([t[0] +v[0], t[1] +v[1], t[2] +v[2]]);
faces.push([vertex_count, vertex_count+1, vertex_count+2, vertex_count+3, volume[n]]);
}
}
}
return { vertices:vertices, faces:faces };
}n/a
function ohSoGreedyMesher(volume, dims, mesherExtraData) {
var vertices = [], faces = []
, dimsX = dims[0]
, dimsY = dims[1]
, dimsXY = dimsX * dimsY;
var tVertices = [], tFaces = []
var transparentTypes = mesherExtraData ? (mesherExtraData.transparentTypes || {}) : {};
var getType = function(voxels, offset) {
var type = voxels[offset];
return type | (type in transparentTypes ? kTransparentMask : 0);
}
//Sweep over 3-axes
for(var d=0; d<3; ++d) {
var i, j, k, l, w, W, h, n, c
, u = (d+1)%3
, v = (d+2)%3
, x = [0,0,0]
, q = [0,0,0]
, du = [0,0,0]
, dv = [0,0,0]
, dimsD = dims[d]
, dimsU = dims[u]
, dimsV = dims[v]
, qdimsX, qdimsXY
, xd
if (mask.length < dimsU * dimsV) {
mask = new Int32Array(dimsU * dimsV);
invMask = new Int32Array(dimsU * dimsV);
}
q[d] = 1;
x[d] = -1;
qdimsX = dimsX * q[1]
qdimsXY = dimsXY * q[2]
// Compute mask
while (x[d] < dimsD) {
xd = x[d]
n = 0;
for(x[v] = 0; x[v] < dimsV; ++x[v]) {
for(x[u] = 0; x[u] < dimsU; ++x[u], ++n) {
// Modified to read through getType()
var a = xd >= 0 && getType(volume, x[0] + dimsX * x[1] + dimsXY * x[2] )
, b = xd < dimsD-1 && getType(volume, x[0]+q[0] + dimsX * x[1] + qdimsX + dimsXY * x[2] + qdimsXY)
// both are transparent, add to both directions
if (isTransparent(a) && isTransparent(b)) {
mask[n] = a;
invMask[n] = b;
// if a is solid and b is not there or transparent
} else if (a && (!b || isTransparent(b))) {
mask[n] = a;
invMask[n] = 0
// if b is solid and a is not there or transparent
} else if (b && (!a || isTransparent(a))) {
mask[n] = 0
invMask[n] = b;
// dont draw this face
} else {
mask[n] = 0
invMask[n] = 0
}
}
}
++x[d];
// Generate mesh for mask using lexicographic ordering
function generateMesh(mask, dimsV, dimsU, vertices, faces, clockwise) {
clockwise = clockwise === undefined ? true : clockwise;
var n, j, i, c, w, h, k, du = [0,0,0], dv = [0,0,0];
n = 0;
for (j=0; j < dimsV; ++j) {
for (i=0; i < dimsU; ) {
c = mask[n];
if (!c) {
i++; n++; continue;
}
//Compute width
w = 1;
while (c === mask[n+w] && i+w < dimsU) w++;
//Compute height (this is slightly awkward)
for (h=1; j+h < dimsV; ++h) {
k = 0;
while (k < w && c === mask[n+k+h*dimsU]) k++
if (k < w) break;
}
// Add quad
// The du/dv arrays are reused/reset
// for each iteration.
du[d] = 0; dv[d] = 0;
x[u] = i; x[v] = j;
if (clockwise) {
// if (c > 0) {
dv[v] = h; dv[u] = 0;
du[u] = w; du[v] = 0;
} else {
// c = -c;
du[v] = h; du[u] = 0;
dv[u] = w; dv[v] = 0;
}
// ## enable code to ensure that transparent faces are last in the list
// if (!isTransparent(c)) {
var vertex_count = vertices.length;
vertices.push([x[0], x[1], x[2] ]);
vertices.push([x[0]+du[0], x[1]+du[1], x[2]+du[2] ]);
vertices.push([x[0]+du[0]+dv[0], x[1]+du[1]+dv[1], x[2]+du[2]+dv[2]]);
vertices.push([x[0] +dv[0], x[1] +dv[1], x[2] +dv[2]]);
faces.push([vertex_count, vertex_count+1, vertex_count+2, vertex_count+3, removeFlags(c)]);
// } else {
// var vertex_count = tVertices.length;
// tVertices.push([x[0], x[1], x[2] ]);
/ ...n/a
mesher = function (volume, dims) {
function f(i,j,k) {
return volume[i + dims[0] * (j + dims[1] * k)];
}
//Sweep over 3-axes
var vertices = [], faces = [];
for(var d=0; d<3; ++d) {
var i, j, k
, u = (d+1)%3 //u and v are orthogonal directions to d
, v = (d+2)%3
, x = new Int32Array(3)
, q = new Int32Array(3)
, runs = new Int32Array(2 * (dims[u]+1))
, frontier = new Int32Array(dims[u]) //Frontier is list of pointers to polygons
, next_frontier = new Int32Array(dims[u])
, left_index = new Int32Array(2 * dims[v])
, right_index = new Int32Array(2 * dims[v])
, stack = new Int32Array(24 * dims[v])
, delta = [[0,0], [0,0]];
//q points along d-direction
q[d] = 1;
//Initialize sentinel
for(x[d]=-1; x[d]<dims[d]; ) {
// --- Perform monotone polygon subdivision ---
var n = 0
, polygons = []
, nf = 0;
for(x[v]=0; x[v]<dims[v]; ++x[v]) {
//Make one pass over the u-scan line of the volume to run-length encode polygon
var nr = 0, p = 0, c = 0;
for(x[u]=0; x[u]<dims[u]; ++x[u], p = c) {
//Compute the type for this face
var a = (0 <= x[d] ? f(x[0], x[1], x[2]) : 0)
, b = (x[d] < dims[d]-1 ? f(x[0]+q[0], x[1]+q[1], x[2]+q[2]) : 0);
c = a;
if((!a) === (!b)) {
c = 0;
} else if(!a) {
c = -b;
}
//If cell type doesn't match, start a new run
if(p !== c) {
runs[nr++] = x[u];
runs[nr++] = c;
}
}
//Add sentinel run
runs[nr++] = dims[u];
runs[nr++] = 0;
//Update frontier by merging runs
var fp = 0;
for(var i=0, j=0; i<nf && j<nr-2; ) {
var p = polygons[frontier[i]]
, p_l = p.left[p.left.length-1][0]
, p_r = p.right[p.right.length-1][0]
, p_c = p.color
, r_l = runs[j] //Start of run
, r_r = runs[j+2] //End of run
, r_c = runs[j+1]; //Color of run
//Check if we can merge run with polygon
if(r_r > p_l && p_r > r_l && r_c === p_c) {
//Merge run
p.merge_run(x[v], r_l, r_r);
//Insert polygon into frontier
next_frontier[fp++] = frontier[i];
++i;
j += 2;
} else {
//Check if we need to advance the run pointer
if(r_r <= p_r) {
if(!!r_c) {
var n_poly = new MonotonePolygon(r_c, x[v], r_l, r_r);
next_frontier[fp++] = polygons.length;
polygons.push(n_poly);
}
j += 2;
}
//Check if we need to advance the frontier pointer
if(p_r <= r_r) {
p.close_off(x[v]);
++i;
}
}
}
//Close off any residual polygons
for(; i<nf; ++i) {
polygons[frontier[i]].close_off(x[v]);
}
//Add any extra runs to frontier
for(; j<nr-2; j+=2) {
var r_l = runs[j]
, r_r = runs[j+2]
, r_c = runs[j+1];
if(!!r_c) {
var n_poly = new MonotonePolygon(r_c, x[v], r_l, r_r);
next_frontier[fp++] = polygons.length;
polygons.push(n_poly);
}
}
//Swap frontiers
var tmp = next_frontier;
next_frontier = frontier;
frontier = tmp;
nf = fp;
}
//Close off frontier
for(var i=0; i<nf; ++i) {
var p = polygons[frontier[i]];
p.close_off(dims[v]);
}
// --- Monotone subdivision of polygon is complete at this point ---
x[d]++;
//Now we just need to triangulate each monotone polygon
for(var i=0; i<polygons.length; ++i) {
var p = polygons[i]
, c = p.color
, flipped = false;
if(c < 0) {
flipped = true;
c = -c;
}
for(var j ...n/a
function StupidMesh(volume, dims) {
var vertices = [], faces = [], x = [0,0,0], n = 0;
for(x[2]=0; x[2]<dims[2]; ++x[2])
for(x[1]=0; x[1]<dims[1]; ++x[1])
for(x[0]=0; x[0]<dims[0]; ++x[0], ++n)
if(!!volume[n]) {
for(var d=0; d<3; ++d) {
var t = [x[0], x[1], x[2]]
, u = [0,0,0]
, v = [0,0,0];
u[(d+1)%3] = 1;
v[(d+2)%3] = 1;
for(var s=0; s<2; ++s) {
t[d] = x[d] + s;
var tmp = u;
u = v;
v = tmp;
var vertex_count = vertices.length;
vertices.push([t[0], t[1], t[2] ]);
vertices.push([t[0]+u[0], t[1]+u[1], t[2]+u[2] ]);
vertices.push([t[0]+u[0]+v[0], t[1]+u[1]+v[1], t[2]+u[2]+v[2]]);
vertices.push([t[0] +v[0], t[1] +v[1], t[2] +v[2]]);
faces.push([vertex_count, vertex_count+1, vertex_count+2, vertex_count+3, volume[n]]);
}
}
}
return { vertices:vertices, faces:faces };
}n/a
function ohSoGreedyMesher(volume, dims, mesherExtraData) {
var vertices = [], faces = []
, dimsX = dims[0]
, dimsY = dims[1]
, dimsXY = dimsX * dimsY;
var tVertices = [], tFaces = []
var transparentTypes = mesherExtraData ? (mesherExtraData.transparentTypes || {}) : {};
var getType = function(voxels, offset) {
var type = voxels[offset];
return type | (type in transparentTypes ? kTransparentMask : 0);
}
//Sweep over 3-axes
for(var d=0; d<3; ++d) {
var i, j, k, l, w, W, h, n, c
, u = (d+1)%3
, v = (d+2)%3
, x = [0,0,0]
, q = [0,0,0]
, du = [0,0,0]
, dv = [0,0,0]
, dimsD = dims[d]
, dimsU = dims[u]
, dimsV = dims[v]
, qdimsX, qdimsXY
, xd
if (mask.length < dimsU * dimsV) {
mask = new Int32Array(dimsU * dimsV);
invMask = new Int32Array(dimsU * dimsV);
}
q[d] = 1;
x[d] = -1;
qdimsX = dimsX * q[1]
qdimsXY = dimsXY * q[2]
// Compute mask
while (x[d] < dimsD) {
xd = x[d]
n = 0;
for(x[v] = 0; x[v] < dimsV; ++x[v]) {
for(x[u] = 0; x[u] < dimsU; ++x[u], ++n) {
// Modified to read through getType()
var a = xd >= 0 && getType(volume, x[0] + dimsX * x[1] + dimsXY * x[2] )
, b = xd < dimsD-1 && getType(volume, x[0]+q[0] + dimsX * x[1] + qdimsX + dimsXY * x[2] + qdimsXY)
// both are transparent, add to both directions
if (isTransparent(a) && isTransparent(b)) {
mask[n] = a;
invMask[n] = b;
// if a is solid and b is not there or transparent
} else if (a && (!b || isTransparent(b))) {
mask[n] = a;
invMask[n] = 0
// if b is solid and a is not there or transparent
} else if (b && (!a || isTransparent(a))) {
mask[n] = 0
invMask[n] = b;
// dont draw this face
} else {
mask[n] = 0
invMask[n] = 0
}
}
}
++x[d];
// Generate mesh for mask using lexicographic ordering
function generateMesh(mask, dimsV, dimsU, vertices, faces, clockwise) {
clockwise = clockwise === undefined ? true : clockwise;
var n, j, i, c, w, h, k, du = [0,0,0], dv = [0,0,0];
n = 0;
for (j=0; j < dimsV; ++j) {
for (i=0; i < dimsU; ) {
c = mask[n];
if (!c) {
i++; n++; continue;
}
//Compute width
w = 1;
while (c === mask[n+w] && i+w < dimsU) w++;
//Compute height (this is slightly awkward)
for (h=1; j+h < dimsV; ++h) {
k = 0;
while (k < w && c === mask[n+k+h*dimsU]) k++
if (k < w) break;
}
// Add quad
// The du/dv arrays are reused/reset
// for each iteration.
du[d] = 0; dv[d] = 0;
x[u] = i; x[v] = j;
if (clockwise) {
// if (c > 0) {
dv[v] = h; dv[u] = 0;
du[u] = w; du[v] = 0;
} else {
// c = -c;
du[v] = h; du[u] = 0;
dv[u] = w; dv[v] = 0;
}
// ## enable code to ensure that transparent faces are last in the list
// if (!isTransparent(c)) {
var vertex_count = vertices.length;
vertices.push([x[0], x[1], x[2] ]);
vertices.push([x[0]+du[0], x[1]+du[1], x[2]+du[2] ]);
vertices.push([x[0]+du[0]+dv[0], x[1]+du[1]+dv[1], x[2]+du[2]+dv[2]]);
vertices.push([x[0] +dv[0], x[1] +dv[1], x[2] +dv[2]]);
faces.push([vertex_count, vertex_count+1, vertex_count+2, vertex_count+3, removeFlags(c)]);
// } else {
// var vertex_count = tVertices.length;
// tVertices.push([x[0], x[1], x[2] ]);
/ ...n/a