naive-surface-nets-2d.js

var neighbors = [
	[ 0,  1,  0],
	[ 1,  0,  0],
	[ 0, -1,  0],
	[-1,  0,  0],
	[ 0,  0,  1],
	[ 0,  0, -1]
]

var cornerTopLeftFront     = [-0.5,  0.5,  0.5]
var cornerTopRightFront    = [ 0.5,  0.5,  0.5]
var cornerBottomRightFront = [ 0.5, -0.5,  0.5]
var cornerBottomLeftFront  = [-0.5, -0.5,  0.5]
var cornerTopLeftBack      = [-0.5,  0.5, -0.5]
var cornerTopRightBack     = [ 0.5,  0.5, -0.5]
var cornerBottomRightBack  = [ 0.5, -0.5, -0.5]
var cornerBottomLeftBack   = [-0.5, -0.5, -0.5]

var quads = [
	[    cornerTopLeftBack,     cornerTopLeftFront,    cornerTopRightFront,     cornerTopRightBack],
	[  cornerTopRightFront, cornerBottomRightFront,  cornerBottomRightBack,     cornerTopRightBack],
	[cornerBottomLeftFront,   cornerBottomLeftBack,  cornerBottomRightBack, cornerBottomRightFront],
	[    cornerTopLeftBack,   cornerBottomLeftBack,  cornerBottomLeftFront,     cornerTopLeftFront],
	[   cornerTopLeftFront,  cornerBottomLeftFront, cornerBottomRightFront,    cornerTopRightFront],
	[   cornerTopRightBack,  cornerBottomRightBack,   cornerBottomLeftBack,      cornerTopLeftBack]
]

var indices = [
	0, 1, 2,
	0, 2, 3
]

var edges = [
	[    cornerTopLeftFront,    cornerTopRightFront],
	[   cornerTopRightFront, cornerBottomRightFront],
	[cornerBottomRightFront,  cornerBottomLeftFront],
	[ cornerBottomLeftFront,     cornerTopLeftFront],
	[     cornerTopLeftBack,     cornerTopRightBack],
	[    cornerTopRightBack,  cornerBottomRightBack],
	[ cornerBottomRightBack,   cornerBottomLeftBack],
	[  cornerBottomLeftBack,      cornerTopLeftBack],
	[    cornerTopLeftFront,      cornerTopLeftBack],
	[   cornerTopRightFront,     cornerTopRightBack],
	[ cornerBottomLeftFront,   cornerBottomLeftBack],
	[cornerBottomRightFront,  cornerBottomRightBack]
]

var delta = 0.001

function generateSmoothMesh (sample, start, end) {
	var positions = []
	var normals = []
	for (var x = start[0]; x <= end[0]; x++) {
		for (var y = start[1]; y <= end[1]; y++) {
			for (var z = start[2]; z <= end[2]; z++) {
				if (sample(x, y, z) < 0) {
					for (var i = 0; i < neighbors.length; i++) {
						var neighbor = neighbors[i]
						if (sample(x + neighbor[0], y + neighbor[1], z + neighbor[2]) >= 0) {
							for (var j = 0; j < indices.length; j++) {
								var corner = quads[i][indices[j]]
								var cX = x + corner[0]
								var cY = y + corner[1]
								var cZ = z + corner[2]
								var sumX = 0
								var sumY = 0
								var sumZ = 0
								var count = 0
								for (var k = 0; k < edges.length; k++) {
									var edge = edges[k]
									var a = edge[0]
									var b = edge[1]
									var aX = cX + a[0]
									var aY = cY + a[1]
									var aZ = cZ + a[2]
									var bX = cX + b[0]
									var bY = cY + b[1]
									var bZ = cZ + b[2]
									var sampleA = sample(aX, aY, aZ)
									var sampleB = sample(bX, bY, bZ)
									if (sampleA < 0 !== sampleB < 0) {
										var alphaA = sampleA / (sampleA - sampleB)
										var alphaB = 1 - alphaA
										sumX += aX * alphaB + bX * alphaA
										sumY += aY * alphaB + bY * alphaA
										sumZ += aZ * alphaB + bZ * alphaA
										count++
									}
								}
								positions.push(
									sumX / count, 
									sumY / count, 
									sumZ / count
								)
								var normalX = (sample(cX + delta, cY, cZ) - sample(cX - delta, cY, cZ)) / delta / 2
								var normalY = (sample(cX, cY + delta, cZ) - sample(cX, cY - delta, cZ)) / delta / 2
								var normalZ = (sample(cX, cY, cZ + delta) - sample(cX, cY, cZ - delta)) / delta / 2
								var length = Math.sqrt(normalX * normalX + normalY * normalY + normalZ * normalZ)
								normals.push(
									normalX / length,
									normalY / length,
									normalZ / length
								)
							}
						}
					}
				}
			}
		}
	}
	return [positions, normals]
}

function generateBlockyMesh (sample, start, end) {
	var positions = []
	var normals = []
	for (var x = start[0]; x <= end[0]; x++) {
		for (var y = start[1]; y <= end[1]; y++) {
			for (var z = start[2]; z <= end[2]; z++) {
				if (sample(x, y, z) < 0) {
					for (var i = 0; i < neighbors.length; i++) {
						var neighbor = neighbors[i]
						if (sample(x + neighbor[0], y + neighbor[1], z + neighbor[2]) >= 0) {
							for (var j = 0; j < indices.length; j++) {
								var corner = quads[i][indices[j]]
								positions.push(
									x + corner[0], 
									y + corner[1], 
									z + corner[2]
								)
								normals.push(
									neighbor[0],
									neighbor[1],
									neighbor[2]
								)
							}
						}
					}
				}
			}
		}
	}
	return [positions, normals]
}

test.html

<script>

var neighbors = [
	[ 0,  1,  0],
	[ 1,  0,  0],
	[ 0, -1,  0],
	[-1,  0,  0],
	[ 0,  0,  1],
	[ 0,  0, -1]
]

var cornerTopLeftFront     = [-0.5,  0.5,  0.5]
var cornerTopRightFront    = [ 0.5,  0.5,  0.5]
var cornerBottomRightFront = [ 0.5, -0.5,  0.5]
var cornerBottomLeftFront  = [-0.5, -0.5,  0.5]
var cornerTopLeftBack      = [-0.5,  0.5, -0.5]
var cornerTopRightBack     = [ 0.5,  0.5, -0.5]
var cornerBottomRightBack  = [ 0.5, -0.5, -0.5]
var cornerBottomLeftBack   = [-0.5, -0.5, -0.5]

var quads = [
	[    cornerTopLeftBack,     cornerTopLeftFront,    cornerTopRightFront,     cornerTopRightBack],
	[  cornerTopRightFront, cornerBottomRightFront,  cornerBottomRightBack,     cornerTopRightBack],
	[cornerBottomLeftFront,   cornerBottomLeftBack,  cornerBottomRightBack, cornerBottomRightFront],
	[    cornerTopLeftBack,   cornerBottomLeftBack,  cornerBottomLeftFront,     cornerTopLeftFront],
	[   cornerTopLeftFront,  cornerBottomLeftFront, cornerBottomRightFront,    cornerTopRightFront],
	[   cornerTopRightBack,  cornerBottomRightBack,   cornerBottomLeftBack,      cornerTopLeftBack]
]

var indices = [
	0, 1, 2,
	0, 2, 3
]

var edges = [
	[    cornerTopLeftFront,    cornerTopRightFront],
	[   cornerTopRightFront, cornerBottomRightFront],
	[cornerBottomRightFront,  cornerBottomLeftFront],
	[ cornerBottomLeftFront,     cornerTopLeftFront],
	[     cornerTopLeftBack,     cornerTopRightBack],
	[    cornerTopRightBack,  cornerBottomRightBack],
	[ cornerBottomRightBack,   cornerBottomLeftBack],
	[  cornerBottomLeftBack,      cornerTopLeftBack],
	[    cornerTopLeftFront,      cornerTopLeftBack],
	[   cornerTopRightFront,     cornerTopRightBack],
	[ cornerBottomLeftFront,   cornerBottomLeftBack],
	[cornerBottomRightFront,  cornerBottomRightBack]
]

var delta = 0.001

function generateSmoothMesh (getSample, start, end) {
	var positions = []
	var normals = []
	var colors = []
	for (var x = start[0]; x <= end[0]; x++) {
		for (var y = start[1]; y <= end[1]; y++) {
			for (var z = start[2]; z <= end[2]; z++) {
				var sample = getSample(x, y, z)
				if (sample[0] < 0) {
					for (var i = 0; i < neighbors.length; i++) {
						var neighbor = neighbors[i]
						if (getSample(x + neighbor[0], y + neighbor[1], z + neighbor[2])[0] >= 0) {
							for (var j = 0; j < indices.length; j++) {
								var corner = quads[i][indices[j]]
								var cX = x + corner[0]
								var cY = y + corner[1]
								var cZ = z + corner[2]
								var sumX = 0
								var sumY = 0
								var sumZ = 0
								var sumR = 0
								var sumG = 0
								var sumB = 0
								var count = 0
								for (var k = 0; k < edges.length; k++) {
									var edge = edges[k]
									var a = edge[0]
									var b = edge[1]
									var aX = cX + a[0]
									var aY = cY + a[1]
									var aZ = cZ + a[2]
									var bX = cX + b[0]
									var bY = cY + b[1]
									var bZ = cZ + b[2]
									var sampleA = getSample(aX, aY, aZ)
									var sampleB = getSample(bX, bY, bZ)
									if (sampleA[0] < 0 !== sampleB[0] < 0) {
										var alphaA = sampleA[0] / (sampleA[0] - sampleB[0])
										var alphaB = 1 - alphaA
										sumX += aX * alphaB + bX * alphaA
										sumY += aY * alphaB + bY * alphaA
										sumZ += aZ * alphaB + bZ * alphaA
										sumR += sampleA[1][0] * alphaB + sampleB[1][0] * alphaA
										sumG += sampleA[1][1] * alphaB + sampleB[1][1] * alphaA
										sumB += sampleA[1][2] * alphaB + sampleB[1][2] * alphaA
										count++
									}
								}
								positions.push(
									sumX / count, 
									sumY / count, 
									sumZ / count
								)
								var normalX = (getSample(cX + delta, cY, cZ)[0] - getSample(cX - delta, cY, cZ)[0]) / delta / 2
								var normalY = (getSample(cX, cY + delta, cZ)[0] - getSample(cX, cY - delta, cZ)[0]) / delta / 2
								var normalZ = (getSample(cX, cY, cZ + delta)[0] - getSample(cX, cY, cZ - delta)[0]) / delta / 2
								var length = Math.sqrt(normalX * normalX + normalY * normalY + normalZ * normalZ)
								normals.push(
									normalX / length,
									normalY / length,
									normalZ / length
								)
								colors.push(
									sumR / count,
									sumG / count,
									sumB / count
								)
							}
						}
					}
				}
			}
		}
	}
	return [positions, normals, colors]
}

function generateBlockyMesh (getSample, start, end) {
	var positions = []
	var normals = []
	var colors = []
	for (var x = start[0]; x <= end[0]; x++) {
		for (var y = start[1]; y <= end[1]; y++) {
			for (var z = start[2]; z <= end[2]; z++) {
				var sample = getSample(x, y, z)
				if (sample[0] < 0) {
					for (var i = 0; i < neighbors.length; i++) {
						var neighbor = neighbors[i]
						if (getSample(x + neighbor[0], y + neighbor[1], z + neighbor[2])[0] >= 0) {
							for (var j = 0; j < indices.length; j++) {
								var corner = quads[i][indices[j]]
								positions.push(
									x + corner[0], 
									y + corner[1], 
									z + corner[2]
								)
								normals.push(
									neighbor[0],
									neighbor[1],
									neighbor[2]
								)
								colors.push(
									sample[1][0],
									sample[1][1],
									sample[1][2]
								)
							}
						}
					}
				}
			}
		}
	}
	return [positions, normals, colors]
}

function generateBlockyCode () {
	return `
		static List<float> Blocky2(Distance distance, int[] start, int[] end) {
			var positions = new List<float>();
			for (var x = start[0]; x <= end[0]; x++) {
				for (var y = start[1]; y <= end[1]; y++) {
					for (var z = start[2]; z <= end[2]; z++) {
						if (distance(x, y, z) < 0) {
							${neighbors.map(function (neighbor, i) {
								return `
									if (distance(x + ${neighbor[0]}, y + ${neighbor[1]}, z + ${neighbor[2]}) >= 0) {
										${indices.map(function (index) {
											var corner = quads[i][index]
											return `
												positions.Add(x + ${corner[0]}f);
												positions.Add(y + ${corner[1]}f);
												positions.Add(z + ${corner[2]}f);
											`
										}).join('')}
									}
								`
							}).join('')}
						}
					}
				}
			}
			return positions;
		}
	`
}
// console.log(generateBlockyCode())
// generateBlockyMesh = new Function('getSample', 'start', 'end', generateBlockyCode())()
// console.log(generateBlockyMesh)
</script>


<script type="importmap">
	{
		"imports": {
			"three": "https://esm.sh/three@0.160.0",
			"three/addons/": "https://esm.sh/three@0.160.0/examples/jsm/"
		}
	}
</script>
<script type="module">
	import {
		WebGLRenderer,
		PerspectiveCamera,
		Scene,
		AmbientLight,
		DirectionalLight,
		MeshPhongMaterial,
		Vector3,
		BufferGeometry,
		BufferAttribute,
		Mesh,
		MathUtils,
	} from 'three'
	import * as THREE from 'three'
	import { OrbitControls } from 'three/addons/controls/OrbitControls.js'
	const W = 160 * 5
	const H = 90 * 5
	const renderer = new WebGLRenderer({ antialias: true })
	const camera = new PerspectiveCamera(75, W / H, 1, 500)
	const scene = new Scene()
	const ambient = new AmbientLight()
	const directional = new DirectionalLight()
	const material = new MeshPhongMaterial({ vertexColors: true })
	const geometry = new BufferGeometry()
	const mesh = new Mesh(geometry, material)
	const controls = new OrbitControls(camera, renderer.domElement)
	renderer.setSize(W, H)
	document.body.append(renderer.domElement)
	camera.position.set(0, 30, 30)
	camera.lookAt(0, 0, 0)
	directional.position.set(1, 1, 1)
	scene.add(ambient)
	scene.add(directional)
	scene.add(mesh)
	function render () {
		renderer.render(scene, camera)
		requestAnimationFrame(render)
		controls.update()
	}
	render()
	function Translate ({
		x = 0, 
		y = 0,
		z = 0,
		value = Sphere()
	} = {}) {
		return function (x2, y2, z2) {
			return value(x - x2, y - y2, z - z2)
		}
	}
	function SmoothUnion({
		a = Sphere(),
		b = Sphere(),
		smoothness = 3
	} = {}) {
		return function (x, y, z) {
			var sampleA = a(x, y, z)
			var sampleB = b(x, y, z)
			var alpha = Math.min(Math.max(0.5 + 0.5 * (sampleB[0] - sampleA[0]) / smoothness, 0), 1)
			return [
				sampleB[0] + alpha * (sampleA[0] - sampleB[0]) - smoothness * alpha * (1.0 - alpha),
				[
					sampleB[1][0] + alpha * (sampleA[1][0] - sampleB[1][0]),
					sampleB[1][1] + alpha * (sampleA[1][1] - sampleB[1][1]),
					sampleB[1][2] + alpha * (sampleA[1][2] - sampleB[1][2]),
				]
			]
		}
	}
	function SmoothSubtract({
		a = Sphere(),
		b = Sphere(),
		smoothness = 3
	} = {}) {
		return function (x, y, z) {
			var sampleA = b(x, y, z)
			var sampleB = a(x, y, z)
			var alpha = Math.min(Math.max(0.5 - 0.5 * (sampleB[0] + sampleA[0]) / smoothness, 0), 1)
			return [
				sampleB[0] + alpha * (-sampleA[0] - sampleB[0]) - smoothness * alpha * (1.0 - alpha),
				[
					sampleB[1][0] + alpha * (sampleA[1][0] - sampleB[1][0]),
					sampleB[1][1] + alpha * (sampleA[1][1] - sampleB[1][1]),
					sampleB[1][2] + alpha * (sampleA[1][2] - sampleB[1][2]),
				]
			]
		}
	}
	function Union({
		a = Sphere(),
		b = Sphere(),
	} = {}) {
		return function (x, y, z) {
			var sampleA = a(x, y, z)
			var sampleB = b(x, y, z)
			if (sampleA[0] < sampleB[0]) {
				return sampleA
			} else {
				return sampleB
			}
		}
	}
	function Subtract({
		a = Sphere(),
		b = Sphere(),
	} = {}) {
		return function (x, y, z) {
			var sampleA = b(x, y, z)
			var sampleB = a(x, y, z)
			if (-sampleA[0] > sampleB[0]) {
				return [-sampleA[0], sampleA[1]]
			} else {
				return sampleB
			}
		}
	}
	function Torus ({
		color = [1, 0, 0],
		outer = 10,
		inner = 5
	} = {}) {
		return function (x, y, z) {
			var a = Math.sqrt(x * x + z * z) - outer
			var b = Math.sqrt(a * a + y * y)
			return [
				b - inner,
				color
			]
		}
	}
	function Sphere({
		color = [1, 0, 0],
		radius = 10
	} = {}) {
		return function (x, y, z) {
			return [
				Math.sqrt(x * x + y * y + z * z) - radius,
				color
			]
		}
	}
	function Repeat({
		value = Sphere(),
		spacing = [10, 10, 10]
	} = {}) {
		return function (x, y, z) {
			return value(
				x - spacing[0] * Math.round(x / spacing[0]),
				y - spacing[1] * Math.round(y / spacing[1]),
				z - spacing[2] * Math.round(z / spacing[2])
			)
		}
	}
	function RepeatX({
		value = Sphere(),
		spacing = 10
	} = {}) {
		return function (x, y, z) {
			return value(
				x - spacing * Math.round(x / spacing),
				y,
				z
			)
		}
	}
	function Scale({
		value = Sphere(),
		scaling = 1
	} = {}) {
		return function (x, y, z) {
			var sample = value(
				x / scaling,
				y / scaling,
				z / scaling
			)
			return [
				sample[0] * scaling,
				sample[1]
			]
		}
	}
	function TwoD({ value = Sphere() } = {}) {
		return function (x, y, z) {
			return value(x, y, 0)
		}
	}
	function torus (x, y, z) {
		var a = Math.sqrt(x * x + z * z) - 10
		var b = Math.sqrt(a * a + y * y)
		return [b - 5, [1, 1, 0]]
	}
	function sphere (x, y, z) {
		return Math.sqrt(x * x + y * y + z * z) - 10
	}
	var size = 64
	console.time()
	var getSample = Scale({
		scaling: 0.25,
		value: SmoothUnion({
			a: Translate({
				x: 20,
				value: Sphere({
					radius: 20,
					color: [0, 0, 1]
				})
			}),
			b: Sphere({
			})
		})
	})
	// var getSample = Sphere({ radius: 5 })

	var [positions, normals, colors] = generateSmoothMesh(getSample, [-size, -size, -size], [size, size, size])
	console.timeEnd()
	console.log('Values', positions.length)
	console.log('Triangles', (positions.length / 3).toLocaleString())
	geometry.setAttribute('position', new BufferAttribute(new Float32Array(positions), 3))
	geometry.setAttribute('normal', new BufferAttribute(new Float32Array(normals), 3))
	geometry.setAttribute('color', new BufferAttribute(new Float32Array(colors), 3))
</script>