evert/Voxel mesher

mesher.js · 3.7 KiB · JavaScript Raw

function mesh (params) {
    const dims = params.dims
    const vertices = []
    const indices = []
    const normals = []

for (let backFace = true, b = false; b !== backFace; backFace = backFace && b, b = !b) {
      // Sweep over 3-axes
      for (let d = 0; d < 3; ++d) {
        let i, j, k, l, w, h, side
        const u = (d + 1) % 3
        const v = (d + 2) % 3
        const x = [0, 0, 0]
        const q = [0, 0, 0]

// Here we're keeping track of the side that we're meshing.
        if (d === 0) side = backFace ? LEFT : RIGHT
        else if (d === 1) side = backFace ? BOTTOM : TOP
        else if (d === 2) side = backFace ? BACK : FRONT

const mask = new Int32Array(dims[u] * dims[v])
        q[d] = 1
        // Move through the dimension from front to back
        for (x[d] = -1; x[d] < dims[d];) {
          // Compute mask
          let n = 0
          for (x[v] = 0; x[v] < dims[v]; ++x[v]) {
            for (x[u] = 0; x[u] < dims[u]; ++x[u]) {
              const current = this.getBlockAt(params, dims, x[0], x[1], x[2])
              const ajacent = this.getBlockAt(params, dims, x[0] + q[0], x[1] + q[1], x[2] + q[2])
              mask[n++] = ((current && ajacent && current === ajacent)) ? null : (backFace ? ajacent : current)
            }
          }

// 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] && mask[n + w] === mask[n] && i + w < dims[u]; ++w) {}

// Compute height
                let done = false
                for (h = 1; j + h < dims[v]; ++h) {
                  for (k = 0; k < w; ++k) {
                    if (!mask[n + k + h * dims[u]] || mask[n + k + h * dims[u]] !== mask[n]) {
                      done = true
                      break
                    }
                  }
                  if (done) break
                }

// Create quad
                x[u] = i
                x[v] = j

const du = [0, 0, 0]
                du[u] = w

const dv = [0, 0, 0]
                dv[v] = h

const quad = [
                  [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]]
                ]

// Add vertices and normals
                const mul = backFace ? -1 : 1
                for (var qindex = 0; qindex < 4; ++qindex) {
                  vertices.push(quad[qindex][0], quad[qindex][1], quad[qindex][2])
                  normals.push(q[0] * mul, q[1] * mul, q[2] * mul)
                }

// Add indices
                const indexi = vertices.length / 3 - 4
                if (backFace) {
                  indices.push(indexi + 2, indexi + 1, indexi)
                  indices.push(indexi + 3, indexi + 2, indexi)
                } else {
                  indices.push(indexi, indexi + 1, indexi + 2)
                  indices.push(indexi, indexi + 2, indexi + 3)
                }

// 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 { vertices, indices, normals }
  }
}

1	function mesh (params) {
2	const dims = params.dims
3	const vertices = []
4	const indices = []
5	const normals = []
6
7	for (let backFace = true, b = false; b !== backFace; backFace = backFace && b, b = !b) {
8	// Sweep over 3-axes
9	for (let d = 0; d < 3; ++d) {
10	let i, j, k, l, w, h, side
11	const u = (d + 1) % 3
12	const v = (d + 2) % 3
13	const x = [0, 0, 0]
14	const q = [0, 0, 0]
15
16	// Here we're keeping track of the side that we're meshing.
17	if (d === 0) side = backFace ? LEFT : RIGHT
18	else if (d === 1) side = backFace ? BOTTOM : TOP
19	else if (d === 2) side = backFace ? BACK : FRONT
20
21	const mask = new Int32Array(dims[u] * dims[v])
22	q[d] = 1
23	// Move through the dimension from front to back
24	for (x[d] = -1; x[d] < dims[d];) {
25	// Compute mask
26	let n = 0
27	for (x[v] = 0; x[v] < dims[v]; ++x[v]) {
28	for (x[u] = 0; x[u] < dims[u]; ++x[u]) {
29	const current = this.getBlockAt(params, dims, x[0], x[1], x[2])
30	const ajacent = this.getBlockAt(params, dims, x[0] + q[0], x[1] + q[1], x[2] + q[2])
31	mask[n++] = ((current && ajacent && current === ajacent)) ? null : (backFace ? ajacent : current)
32	}
33	}
34
35	// Increment x[d]
36	++x[d]
37
38	// Generate mesh for mask using lexicographic ordering
39	n = 0
40	for (j = 0; j < dims[v]; ++j) {
41	for (i = 0; i < dims[u];) {
42	if (mask[n]) {
43	// Compute width
44	for (w = 1; mask[n + w] && mask[n + w] === mask[n] && i + w < dims[u]; ++w) {}
45
46	// Compute height
47	let done = false
48	for (h = 1; j + h < dims[v]; ++h) {
49	for (k = 0; k < w; ++k) {
50	if (!mask[n + k + h * dims[u]] \|\| mask[n + k + h * dims[u]] !== mask[n]) {
51	done = true
52	break
53	}
54	}
55	if (done) break
56	}
57
58	// Create quad
59	x[u] = i
60	x[v] = j
61
62	const du = [0, 0, 0]
63	du[u] = w
64
65	const dv = [0, 0, 0]
66	dv[v] = h
67
68	const quad = [
69	[x[0], x[1], x[2]],
70	[x[0] + du[0], x[1] + du[1], x[2] + du[2]],
71	[x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2]],
72	[x[0] + dv[0], x[1] + dv[1], x[2] + dv[2]]
73	]
74
75	// Add vertices and normals
76	const mul = backFace ? -1 : 1
77	for (var qindex = 0; qindex < 4; ++qindex) {
78	vertices.push(quad[qindex][0], quad[qindex][1], quad[qindex][2])
79	normals.push(q[0] * mul, q[1] * mul, q[2] * mul)
80	}
81
82	// Add indices
83	const indexi = vertices.length / 3 - 4
84	if (backFace) {
85	indices.push(indexi + 2, indexi + 1, indexi)
86	indices.push(indexi + 3, indexi + 2, indexi)
87	} else {
88	indices.push(indexi, indexi + 1, indexi + 2)
89	indices.push(indexi, indexi + 2, indexi + 3)
90	}
91
92	// Zero-out mask
93	for (l = 0; l < h; ++l) {
94	for (k = 0; k < w; ++k) {
95	mask[n + k + l * dims[u]] = false
96	}
97	}
98
99	// Increment counters and continue
100	i += w
101	n += w
102	} else {
103	++i
104	++n
105	}
106	}
107	}
108	}
109	}
110	}
111
112	return { vertices, indices, normals }
113	}
114	}