MOPS - Manifold Operations (Blockbench plugin powered by Manifold-3D library)

mops.js

const manifoldModule = function (moduleArg = {}) { /* Edited bindings to WASM from https://www.npmjs.com/package/manifold-3d */ };

/// <reference path="../../types/index.d.ts" />
const THREE_IMPL = globalThis.THREE;

let Manifold;
let GlMesh;
console.log({ manifoldModule });
manifoldModule({ locateFile: () => "...path to real wasm file... /blockbench-plugins/plugins/mops/src/manifold.wasm" })
	.then(module => {
		module.setup();
		Manifold = module.Manifold;
		GlMesh = module.Mesh;
	});

const tempThreeVector = new THREE_IMPL.Vector3();

function isQuadValid(points) {
	for (let i = 0; i < points.length; i++)
		for (let j = i + 1; j < points.length; j++)
			if (points[i].equals(points[j]))
				return false;

	function getCurvative(i) {
		const middle = points.at(i - 1).V3_toThree();
		const edgeBefore = points.at(i - 2).V3_toThree().sub(middle);
		const edgeAfter = points[i].V3_toThree().sub(middle);
		const cross = edgeBefore.cross(edgeAfter);
		return cross.x - cross.y - cross.z > 0;
	}
	const firstCurvative = getCurvative(0);
	return points.keys().drop(1).every(i => getCurvative(i) == firstCurvative);
}

/** @param { from?: number, to?: number, by?: number, times?: number } options @returns {Generator<number>} */
function* range(options) {
	const from = options.from ?? 0;
	const to = options.to ?? Infinity;
	if (to == from) return;
	const times = options.times ?? Infinity;
	const by = Math.sign(to - from) * Math.abs(options.by ?? 1);
	for (let value = from, idx = 0;
		(to - value) * Math.sign(by) > 0 && idx < times;
		value += by, idx += 1)
		yield value;
}

const VECTOR_3_AXES_INDICES = [0, 1, 2];
const VERTEX_POSITION_PROPERTY_INDICES = [0, 1, 2];
const VERTEX_UV_PROPERTY_INDICES = [3, 4];
const TRIANGLE_CORNER_INDICES = [0, 1, 2];

const CUBE_UV_INDICES = [[0, 1], [2, 1], [2, 3], [0, 3]];

function meshToOperandData(mesh) {
	const visibleFaces = Object.values(mesh.faces).filter(f => f.vertices.length > 2);
	return {
		vertices: Object.fromEntries(Array.from(new Set(visibleFaces.flatMap(f => f.vertices)),
			key => [key, mesh.mesh.localToWorld(tempThreeVector.fromArray(mesh.vertices[key])).toArray()])),
		faces: visibleFaces.map(face => ({
			texture: face.getTexture(),
			triangleFanVertices: new Map(face.getSortedVertices().map(vKey => [vKey, face.uv[vKey]]))
		}))
	}
}

function posMod(subject, divider) { return ((subject % divider) + divider) % divider; }

const CUBE_FACES_TRIANGLE_FANS = {
	east: ["east_up_north", "east_up_south", "east_down_south", "east_down_north"],
	west: ["west_up_south", "west_up_north", "west_down_north", "west_down_south"],
	up: ["east_up_north", "west_up_north", "west_up_south", "east_up_south"],
	down: ["east_down_south", "west_down_south", "west_down_north", "east_down_north"],
	south: ["east_up_south", "west_up_south", "west_down_south", "east_down_south"],
	north: ["west_up_north", "east_up_north", "east_down_north", "west_down_north"],
};

function cubeToOperandData(cube) {
	const from = cube.from.slice();
	const to = cube.to.slice();

	// ADJUST "FROM" AND "TO" FOR INFLATE AND STRETCH
	const size = cube.size();
	const stretch = "stretch" in cube ? cube.stretch : [1, 1, 1];
	for (const axis of VECTOR_3_AXES_INDICES) {
		const center = from[axis] + size[axis] / 2 - cube.origin[axis];
		const extent = (size[axis] / 2 + cube.inflate) * stretch[axis];
		from[axis] = center - extent;
		to[axis] = center + extent;
	}

	const vertices = {
		east_up_south: [to[0], to[1], to[2]],
		east_up_north: [to[0], to[1], from[2]],
		east_down_south: [to[0], from[1], to[2]],
		east_down_north: [to[0], from[1], from[2]],
		west_up_south: [from[0], to[1], to[2]],
		west_up_north: [from[0], to[1], from[2]],
		west_down_south: [from[0], from[1], to[2]],
		west_down_north: [from[0], from[1], from[2]],
	};

	for (const position of Object.values(vertices))
		cube.mesh.localToWorld(tempThreeVector.fromArray(position)).toArray(position);

	return {
		vertices,
		faces: Object.entries(CUBE_FACES_TRIANGLE_FANS).map(([direction, vertices]) => {
			const face = cube.faces[direction];
			const { uv, rotation } = cube.faces[direction];
			const uvIdxOffset = posMod(rotation || 0, 90);
			return {
				texture: face.getTexture(),
				triangleFanVertices: new Map(vertices.map((vKey, vIdx) => {
					const uvIdx = CUBE_UV_INDICES[(uvIdxOffset + vIdx) % 4];
					return [vKey, [uv[uvIdx[0]], uv[uvIdx[1]]]];
				}))
			};
		})
	}
}


function createIcon(path) {
	var icon = new Image();
	icon.src = `data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 -960 1920 1920"><path d="${path}" /></svg>`;
	return icon;
}

const _icon_outline = "M320-800c-88.64 0-160 71.36-160 160v800c0 88.64 71.36 160 160 160h320v320c0 88.64 71.36 160 160 160h800c88.64 0 160-71.36 160-160v-800c0-88.64-71.36-160-160-160h-320v-320c0-88.64-71.36-160-160-160z";
const disjunction_icon = createIcon(_icon_outline);
const abjunction_icon = createIcon(_icon_outline + "m480 640h800v800H800Z");
const conjunction_icon = createIcon(_icon_outline + "m0 160h800v320H800c-88.64 0-160 71.36-160 160v320H320Zm960 480h320v800H800V320h320c88.64 0 160-71.36 160-160z");

function isCubeOrMesh(element) { return element instanceof Cube || element instanceof Mesh; }

function canRunOperation(condition) { return condition(OutlinerElement.selected?.filter(e => isCubeOrMesh(e)) ?? []); }

const _category = "edit";
const operations = [
	{
		name: "disjunction", options: {
			name: "Union (Disjunction)",
			description: "Union all selected meshes and cubes and create output mesh (aka OR or DISJUNCTION)",
			// keybind: new Keybind({ key: "W", shift: true }),
			icon: disjunction_icon,
			category: _category,
			condition: { modes: ["edit"], features: ["meshes"], method: () => canRunOperation(operands => operands.length > 1) },
			click: () => runOperation(
				manifolds => Manifold.union(manifolds),
				names => names.join(" OR "),
				"Union (Disjunction)"),
		}
	}, {
		name: "abjunction",
		options: {
			name: "Subtract (Abjunction)",
			description: "Subtract all other selected meshes and cubes from first and create output mesh (AND_NOT or ABJUNCTION)",
			// keybind: new Keybind({ key: "W", shift: true }),
			icon: abjunction_icon,
			category: _category,
			condition: { modes: ["edit"], features: ["meshes"], method: () => canRunOperation(operands => operands.length > 1) },
			click: () => runOperation(
				manifolds => Manifold.difference(manifolds),
				names => names.join(" AND NOT "),
				"Subtract (Abjunction)"),
		}
	}, {
		name: "conjunction",
		options: {
			name: "Intersect (Conjunction)",
			description: "Intersect all selected meshes and cubes and create output mesh (AND or CONJUNCTION)",
			// keybind: new Keybind({ key: "W", shift: true }),
			icon: conjunction_icon,
			category: _category,
			condition: { modes: ["edit"], features: ["meshes"], method: () => canRunOperation(operands => operands.length > 1) },
			click: () => runOperation(
				manifolds => Manifold.intersection(manifolds),
				names => names.join(" AND "),
				"Intersect (Conjunction)"),
		}
	}, {
		name: "hull",
		options: {
			name: "Hull",
			description: "Convex Hull",
			// keybind: new Keybind({ key: "W", shift: true }),
			icon: conjunction_icon,
			category: _category,
			condition: { modes: ["edit"], features: ["meshes"], method: () => canRunOperation(operands => operands.length == 1) },
			click: () => runOperation(
				manifolds => Manifold.hull(manifolds),
				names => names.join(" HULL "),
				"Convex Hull"),
		}
	}, {
		name: "refine",
		options: {
			name: "Refine",
			description: "Refine",
			// keybind: new Keybind({ key: "W", shift: true }),
			icon: conjunction_icon,
			category: _category,
			condition: { modes: ["edit"], features: ["meshes"], method: () => canRunOperation(operands => operands.length == 1) },
			click: () => runOperation(
				manifolds => manifolds[0].refine(4),
				// refine(n: number): Manifold;
				// refineToLength(length: number): Manifold;
				// refineToTolerance(tolerance: number): Manifold;
				names => names[0] + " REFINED",
				"Refine"),
		}
	}, {
		name: "simplify",
		options: {
			name: "Simplify",
			description: "Simplify",
			// keybind: new Keybind({ key: "W", shift: true }),
			icon: conjunction_icon,
			category: _category,
			condition: { modes: ["edit"], features: ["meshes"], method: () => canRunOperation(operands => operands.length == 1) },
			click: () => runOperation(
				manifolds => manifolds[0].simplify(1000).refine(0),
				names => names[0] + " SIMPLIFIED",
				"Simplify"),
		}
	}, {
		name: "split_by_ground_plane",
		options: {
			name: "Split By Ground Plane",
			description: "Split By Ground Plane",
			// keybind: new Keybind({ key: "W", shift: true }),
			icon: conjunction_icon,
			category: _category,
			condition: { modes: ["edit"], features: ["meshes"], method: () => canRunOperation(operands => operands.length == 1) },
			click: () => runOperation(
				manifolds => manifolds[0].trimByPlane([0, 1, 0], 0),
				names => names[0] + " SPLITTED",
				"Split By Ground Plane"),
		}
	}
];

function runOperation(operation, generateName, description) {
	Undo.initEdit({ selection: true, collections: [], outliner: true, elements: [] });

	const operands = OutlinerElement.selected.filter(isCubeOrMesh);
	const firstOperand = operands[0];
	const operandsData = operands.map(e =>
		e instanceof Mesh ? meshToOperandData(e) :
			e instanceof Cube ? cubeToOperandData(e) : null).filter(d => d != null);


	// RESERVE TEXTURE IDS
	const usedTextures = []
	operandsData.flatMap(e => e.faces.map(f => f.texture)).forEach(texture => {
		if (!usedTextures.includes(texture)) usedTextures.push(texture);
	});
	const firstTextureId = Manifold.reserveIDs(usedTextures.length);


	// PASS-THROUGH FACE IDENTIFIER INITIALIZATION
	let currentFaceId = 0;

	const manifolds = [];

	for (const meshData of operandsData) {
		const textureIds = [];
		const textureRunsStartVertexIndices = [];
		const verticesPropertiesBuffer = [];
		const facesGroupsByTextureId =
			Map.groupBy(meshData.faces, face => firstTextureId + usedTextures.indexOf(face.texture));

		let processedVerticesCount = 0;
		const operationFaceIds = [];
		for (const [textureId, faces] of facesGroupsByTextureId.entries()) {
			textureRunsStartVertexIndices.push(processedVerticesCount);
			textureIds.push(textureId);
			for (const face of faces) {
				const triangleFanVertices = face.triangleFanVertices.entries().toArray();
				const trianglesCount = face.triangleFanVertices.size - 2;
				for (const triangleIdx of range({ to: trianglesCount })) {
					operationFaceIds.push(currentFaceId);
					[0, triangleIdx + 1, triangleIdx + 2].map(i => triangleFanVertices[i]).forEach(([vertexKey, uv]) =>
						verticesPropertiesBuffer.push(...meshData.vertices[vertexKey], ...uv));
				}

				processedVerticesCount += trianglesCount * 3;
				currentFaceId += 1;
			}
		}

		const runsOrder = Uint32Array.from(range({ to: textureRunsStartVertexIndices.length }))
			.sort((a, b) => textureRunsStartVertexIndices[a] - textureRunsStartVertexIndices[b]);
		const options = {
			numProp: 5, // x,y,z,u,v
			vertProperties: Float32Array.from(verticesPropertiesBuffer),
			triVerts: Uint32Array.from(range({ to: processedVerticesCount })),
			runIndex: Uint32Array.from(runsOrder, i => textureRunsStartVertexIndices[i]),
			runOriginalID: Uint32Array.from(runsOrder, i => textureIds[i]),
			faceID: Uint32Array.from(operationFaceIds),
		};

		const manifoldMesh = new GlMesh(options);
		manifoldMesh.merge();
		manifolds.push(new Manifold(manifoldMesh));
		currentFaceId += meshData.faces.length;
	}

	const {
		vertProperties,
		triVerts,
		numProp,
		numRun,
		runIndex,
		runOriginalID,
		faceID,
	} = operation(manifolds).getMesh();
	manifolds.forEach(m => m.delete());

	const getVertexProperty = (triangleIdx, cornerIdx, propertyIndices) =>
		[triVerts[triangleIdx * 3 + cornerIdx] * numProp]
			.flatMap(offset => propertyIndices.map(propertyIdx => offset + propertyIdx))
			.map(propertyAddress => vertProperties[propertyAddress]);

	const getVertexPosition = (triangleIdx, cornerIdx) =>
		// translate vertex position back to first mesh local space
		firstOperand.mesh.worldToLocal(tempThreeVector.fromArray(getVertexProperty(
			triangleIdx, cornerIdx, VERTEX_POSITION_PROPERTY_INDICES))).toArray();

	const getVertexUv = (triangleIdx, cornerIdx) =>
		getVertexProperty(triangleIdx, cornerIdx, VERTEX_UV_PROPERTY_INDICES);

	const mesh = new Mesh({
		vertices: {},
		color: firstOperand.color,
		name: generateName(operands.map(e => e.name)),
		origin: ("origin" in firstOperand) ? firstOperand.origin : undefined,
		rotation: ("rotation" in firstOperand) ? firstOperand.rotation : undefined,
		visibility: firstOperand.visibility,
	});
	mesh.parent = firstOperand.parent;

	const meshVertexCacheByStringifiedPosition = {};
	const getOrAddVertex = (position) =>
		meshVertexCacheByStringifiedPosition[JSON.stringify(position)] ??= mesh.addVertices(position)[0];

	const triangularFacesByFaceId = new Map();
	for (const runIdx of range({ to: numRun })) {
		const texture = usedTextures[runOriginalID[runIdx] - firstTextureId];
		for (const triangleIdx of range({ from: runIndex[runIdx] / 3, to: runIndex[runIdx + 1] / 3 })) {
			const vertices = TRIANGLE_CORNER_INDICES.map(cornerIdx =>
				getOrAddVertex(getVertexPosition(triangleIdx, cornerIdx)));
			const uv = Object.fromEntries(vertices.map((vertexKey, triangleCornerIdx) =>
				[vertexKey, getVertexUv(triangleIdx, triangleCornerIdx)]));


			// Merge this triangle with one of existing triangles to quad if possible
			const faceIdx = faceID[triangleIdx];
			let triangularFaces = triangularFacesByFaceId.get(faceIdx);
			if (!triangularFaces) {
				const face = new MeshFace(mesh, { texture, vertices, uv });
				triangularFacesByFaceId.set(faceIdx, [face]);
				mesh.addFaces(face);
			} else {
				let merged = false;
				for (const triangularFace of triangularFaces) {
					const triangularFaceNormal = triangularFace.getNormal(true);
					const newVertices = vertices.filter(v => !triangularFace.vertices.includes(v));
					if (newVertices.length == 1) {
						const newVertex = newVertices[0];
						const newQuad = new MeshFace(mesh, {
							texture,
							vertices: [...triangularFace.vertices, newVertex],
							uv: { [newVertex]: uv[newVertex], ...triangularFace.uv },
						});
						const sortedVertices = newQuad.getSortedVertices();
						if (isQuadValid(sortedVertices.map(v => mesh.vertices[v]))) {
							newQuad.vertices = sortedVertices;
							if (newQuad.getNormal(true).V3_toThree().dot(triangularFaceNormal.V3_toThree()) < 0) {
								newQuad.invert();
							}
							mesh.addFaces(newQuad);
							triangularFaces.remove(triangularFace);
							delete mesh.faces[triangularFace.getFaceKey()];
							merged = true;
							break;
						}
					}
				}
				if (!merged) {
					const face = new MeshFace(mesh, { texture, vertices, uv });
					triangularFaces.push(face);
					mesh.addFaces(face);
				}
			}
		}
	}

	mesh.init();
	mesh.select();
	Undo.finishEdit("Operation: " + description, { selection: true, collections: [], outliner: true, elements: [mesh] });
}

BBPlugin.register("mops", {
	title: "MOPS - Mesh binary operations plugin",
	author: "nklbdev",
	icon: "icon.svg",
	// tags: [],
	description: "Mesh binary operations plugin description",
	version: "1.0.0",
	min_version: "4.12.4",
	variant: "both",
	onload: () => {
		for (const operation of operations) {
			operation.action = new Action(operation.name, operation.options);
			Mesh.prototype.menu?.addAction(operation.action);
			Cube.prototype.menu?.addAction(operation.action);
		}
	},
	onunload: () => {
		for (const operation of operations) {
			if (!operation.action) continue;
			Mesh.prototype.menu?.removeAction(operation.action);
			Cube.prototype.menu?.removeAction(operation.action);
			operation.action.delete();
			operation.action = undefined;
		}
	},
});