Compute the volume of a constructive solid geometry

I have a constructive solid geometry of ellipsoids that cut a cube. I need to compute the volume of the porous cube. How can I do this?

There is always the dumb approximating solution. For that you need only a decision function whether a point is inside an ellipsoid.

Keep a Cube

• Dimension (maybe only once outside the class, the outer dimension)
• filling: with state: empty, filled, mixed
• if mixed 8 sub-Cube-s
• there is a minimal block size

Then filling with an ellipsoid will split cubes, where mixed cubes (a bit filled) will need splitting for more precise calculation.

The algorithm itself can vary. Rescaling to (0, 0, 0) - (2”, 2”, 2”) might be usefull, as the blocks do a ²log division of the space.

At the end of this computation one has an approximation and even knows the error range (sum of filled + half of sum of mixed).

---

One way would be to recurse with that from the entire Cube, checking overlaps with the 8 sub-cubes:

• When all 8 corners of a cube are inside the ellipsoid the it is filled, and you need not recurse further to the minimal block size.
• When all 8 corners are outside and the center of the ellipsoid does not lie inside, it is empty, end of recursion.