I have a relatively flat mesh that can be projected onto a plane. The area of this projected mesh can be easily calculated.

I will be projecting disks (cylinders with 0 height) onto this projected mesh which will result in ellipsoids.

I need to find the area left uncovered.

Originally to accomplish this I quantified the mesh into n uniform pieces and used a colouring algorithm where each dsicrete piece is marked as overlapped or not overlapped. Then I sum the areas of the overlapped pieces and subtract those from the total areas of the projected mesh.

This is implemented in a compute shader as part of an energy calculation for simulated annealing.

Unfortunately it is does not yield suitable performance at high resolutions, nor the accuracy required at lower resolutions.

Is there any other way to calculate this?

EDIT: Is there a name for this type of problem, I do not know what to search to find ideas.

**Edited by pondwater, 23 August 2013 - 04:35 PM.**