A couple of minor things I will have to add in the near future. Have a simple BSP bounding volume for my shapes so I can quickly reject the polygons that could not possibly be affected by the shape. A very cheap AABB test before that would be super cheap as well. And the other, to use the resulting cut polygons as hints about what polygons to use for rebuilding the tree. The polygon that got cut the most is obviously touching a large part of the other tree and therefor would be a better choice than just the first one, or a random one.
Best try to punch a few characters in while the son is transfixed by his toy.
V 