BOPS (Boolean Operations) - plugin for Blockbench

main.ts

/**
 * @author nklbdev
 * @github https://github.com/nklbdev
 */

// TODO Add ability to replace first operand with result
// TODO Add shortcuts
// TODO Add error handling (like "NotManifold")

/// <reference types="blockbench-types" />

import THREE from 'three';
const THREE_IMPL = globalThis.THREE;

import {
	default as createManifoldTop,
	Manifold,
} from 'manifold-3d';

const _manifoldTop = await createManifoldTop({
	locateFile: () => "D:/Blockbench/custom_plugins/bops/dist/assets/manifold.wasm"
});
_manifoldTop.setup();
const MNF_ManifoldImpl = _manifoldTop.Manifold;
const MNF_MeshImpl = _manifoldTop.Mesh;


const tempThreeVector: THREE.Vector3 = new THREE_IMPL.Vector3();








function isQuadValid(points: ArrayVector3[]): boolean {
	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: number): boolean {
		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);
}

function* range(options: { from?: number, to?: number, by?: number, times?: number }): Generator<number> {
	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]];

type FaceData = {
	texture: Texture | undefined,
	triangleFanVertices: Map<string, ArrayVector2>,
}

type OperandData = {
	vertices: { [k: string]: ArrayVector3 },
	faces: FaceData[],
};


function meshToOperandData(mesh: Mesh): OperandData {
	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: number, divider: number): number {
	return ((subject % divider) + divider) % divider
}

type Direction =
	| "east"
	| "west"
	| "up"
	| "down"
	| "south"
	| "north";

type CubeVertexKey =
	| "east_up_south"
	| "east_up_north"
	| "east_down_south"
	| "east_down_north"
	| "west_up_south"
	| "west_up_north"
	| "west_down_south"
	| "west_down_north";

type CubeFaceVertices = [CubeVertexKey, CubeVertexKey, CubeVertexKey, CubeVertexKey];

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"],
} as { [k in Direction]: CubeFaceVertices };

function cubeToOperandData(cube: Cube): OperandData {
	const from = cube.from.slice() as ArrayVector3;
	const to = cube.to.slice() as ArrayVector3;

	// ADJUST "FROM" AND "TO" FOR INFLATE AND STRETCH
	const size = cube.size() as ArrayVector3;
	const stretch = "stretch" in cube ? cube.stretch as ArrayVector3 : [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]],
	} as { [k in CubeVertexKey]: ArrayVector3 };

	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: string): string {
	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 as unknown as string;
}

const _icon_outline: string = "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: string = createIcon(_icon_outline);
const abjunction_icon: string = createIcon(_icon_outline + "m480 640h800v800H800Z");
const conjunction_icon: string = createIcon(_icon_outline + "m0 160h800v320H800c-88.64 0-160 71.36-160 160v320H320Zm960 480h320v800H800V320h320c88.64 0 160-71.36 160-160z");

interface OperationInfo {
	name: string
	options: ActionOptions
	action?: Action
}

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

const canRunBooleanOperation = (): boolean => {
	const elements = OutlinerElement.selected;
	if (!elements) return false;
	if (elements.length < 2) return false;
	if (!isCubeOrMesh(elements[0])) return false;
	if (elements.filter(e => isCubeOrMesh(e)).length < 2) return false;
	return true;
}

type BooleanOp = "union" | "difference" | "intersection";
const _category = "edit";
const _condition = { modes: ["edit"], features: ["meshes"], method: canRunBooleanOperation };
const operations: OperationInfo[] = [
	{
		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: _condition,
			click: (): void => runBooleanOperation(
				"union", // MNF_ManifoldImpl.union,
				(names: string[]) => 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: _condition,
			click: (): void => runBooleanOperation(
				"difference", // MNF_ManifoldImpl.difference,
				(names: string[]) => 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: _condition,
			click: (): void => runBooleanOperation(
				"intersection", // MNF_ManifoldImpl.intersection,
				(names: string[]) => names.join(" AND "),
				"Intersect (Conjunction)"),
		}
	}
];

//   3--------2
//  /|       /|
// 0--------1 |
// | |      | |
// | 7------|-6
// |/       |/
// 4--------5
//
// materials: [vertical_side, horizontal_side]
// vertices: [0, 1, 2, 3, 4, 5, 6, 7]
//
// numProp: 3 (only positions)
// index of triVerts array:     | 0  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|
// triVerts:                    | 0  4  5| 5  1  0| 1  5  6| 6  2  1| 2  6  7| 7  3  2| 3  7  4| 4  0  3| 0  1  2| 2  3  0| 6  5  4| 4  7  6|
// indices of triangles:        | 0      | 1      | 2      | 3      | 4      | 5      | 6      | 7      | 8      | 9      |10      |11      |
// runIndex (by vertices):      | 0 (triangle index)                                                    | 8 (triangle index)                |
// runOriginalID (by vertices): | 0 (texture index)                                                     | 1 (texture index)                 |
// faceID (by triangles):       | 0      | 0      | 1      | 1      | 2      | 2      | 3      | 3      | 4      | 4      | 5      | 5      |

function runBooleanOperation(
	operation: BooleanOp,
	generateName: ((names: string[]) => string),
	description: string,
): void {
	Undo.initEdit({ selection: true, collections: [], outliner: true, elements: [] });

	if (!canRunBooleanOperation()) return;

	const operands = (OutlinerElement.selected as OutlinerElement[]).filter(isCubeOrMesh) as (Mesh | Cube)[];
	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: (Texture | undefined)[] = []
	operandsData.flatMap(e => e.faces.map(f => f.texture)).forEach(texture => {
		if (!usedTextures.includes(texture)) usedTextures.push(texture);
	});
	const firstTextureId = MNF_ManifoldImpl.reserveIDs(usedTextures.length);


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

	const manifolds: Manifold[] = [];

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

		let processedVerticesCount: number = 0;
		const operationFaceIds: number[] = [];
		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 MNF_MeshImpl(options);
		manifoldMesh.merge();
		manifolds.push(new MNF_ManifoldImpl(manifoldMesh));
		currentFaceId += meshData.faces.length;
	}

	const {
		vertProperties,
		triVerts,
		numProp,
		numRun,
		runIndex,
		runOriginalID,
		faceID,
	} = MNF_ManifoldImpl[operation](manifolds).getMesh();

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

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

	const getVertexUv = (triangleIdx: number, cornerIdx: number): ArrayVector2 =>
		getVertexProperty(triangleIdx, cornerIdx, VERTEX_UV_PROPERTY_INDICES) as ArrayVector2;

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

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

	const triangularFacesByFaceId = new Map<number, MeshFace[]>();
	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("Boolean operation: " + description, { selection: true, collections: [], outliner: true, elements: [mesh] });
}




BBPlugin.register('bops', {
	title: 'BOPS - Mesh binary operations plugin',
	author: 'nklbdev',
	icon: 'radio_button_unchecked',
	description: 'Mesh binary operations plugin description',
	version: '0.0.1',
	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;
		}
	},
});