/
greedy.js
71 lines (71 loc) · 2.01 KB
/
greedy.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function GreedyMesh(volume, dims) {
function f(i,j,k) {
return volume[i + dims[0] * (j + dims[1] * k)];
}
//Sweep over 3-axes
var quads = [];
for(var d=0; d<3; ++d) {
var i, j, k, l, w, h
, u = (d+1)%3
, v = (d+2)%3
, x = [0,0,0]
, q = [0,0,0]
, mask = new Int32Array(dims[u] * dims[v]);
q[d] = 1;
for(x[d]=-1; x[d]<dims[d]; ) {
//Compute mask
var n = 0;
for(x[v]=0; x[v]<dims[v]; ++x[v])
for(x[u]=0; x[u]<dims[u]; ++x[u]) {
mask[n++] =
(0 <= x[d] ? f(x[0], x[1], x[2]) : false) !=
(x[d] < dims[d]-1 ? f(x[0]+q[0], x[1]+q[1], x[2]+q[2]) : false);
}
//Increment x[d]
++x[d];
//Generate mesh for mask using lexicographic ordering
n = 0;
for(j=0; j<dims[v]; ++j)
for(i=0; i<dims[u]; ) {
if(mask[n]) {
//Compute width
for(w=1; mask[n+w] && i+w<dims[u]; ++w) {
}
//Compute height (this is slightly awkward
var done = false;
for(h=1; j+h<dims[v]; ++h) {
for(k=0; k<w; ++k) {
if(!mask[n+k+h*dims[u]]) {
done = true;
break;
}
}
if(done) {
break;
}
}
//Add quad
x[u] = i; x[v] = j;
var du = [0,0,0]; du[u] = w;
var dv = [0,0,0]; dv[v] = h;
quads.push([
[x[0], x[1], x[2] ]
, [x[0]+du[0], x[1]+du[1], x[2]+du[2] ]
, [x[0]+du[0]+dv[0], x[1]+du[1]+dv[1], x[2]+du[2]+dv[2]]
, [x[0] +dv[0], x[1] +dv[1], x[2] +dv[2]]
]);
//Zero-out mask
for(l=0; l<h; ++l)
for(k=0; k<w; ++k) {
mask[n+k+l*dims[u]] = false;
}
//Increment counters and continue
i += w; n += w;
} else {
++i; ++n;
}
}
}
}
return quads;
}