microwerx's website

Here is an algorithm I came up with to do CSG merge of two polygonal models. It is necessary to build a BSP tree of both models A and B although you don’t need to split the polygons to insert, just use the plane equations. I think that the time complexity is O(N^2). The first half is O(N^2) while the second is O(N log N). More to follow (probably a beautifully large paper!).

A is a linked list, B is a linked list

1. Split Intersecting Polygons
for Pa in A do
	for Pb in B do
		if (Pb has been intersected)
			continue
		if Pa intersects Pb do
			Split Pa against Pb and store as Pa_in and Pa_out
			Split Pb against Pa and store as Pb_in and Pb_out
			// Pa_in means Pa inside of B
			// Pa_out means Pa outside of B
			Mark Pa as "split"
			Mark Pb as "split"

			Add Pa_in to A
			Add Pa_out to A
			Add Pb_in to B
			Add Pb_out to B
		end
	end
end

2. Split into 4 sets: A_minus_B, B_minus_A, A_intersect_B, A_union_B
for Pa in A do
	If Pa has been intersected
		continue
	if Pa is inside of B
		Add -Pa to B_minus_A
		Add -Pa to A_intersect_B
	else
		Add Pa to A_minus_B
		Add Pa to A_union_B
	end
end

for Pb in B do
	If Pb has been intersected
		continue
	if Pb is inside of A
		Add -Pb to A_minus_B
		Add -Pb to A_intersect_B
	else
		Add Pb to B_minus_A
		Add Pb to A_union_B
	end
end