Jump to content
  • Advertisement
Sign in to follow this  

Calculating area left uncovered by overlapping projected circles on a plane

This topic is 2155 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post

Link to post
Share on other sites

Currently I run 256 to 1024 compute shader invocations depending on the resolution of my current approach, each calculating the overlapped area asyncronously.


I was considering using a rendering type approach as you suggested, but drawing and counting pixels instead of simply querying. Do you think there would be a performance gain in what would effectively be 256-1024 sequential occlusion queuries per annealing iteration?


I do not have any experience with the ARB_occlusion_query OpenGL extension so I do not know anything about its performance.

Edited by pondwater

Share this post

Link to post
Share on other sites

Ah, yes but the terms "colouring algorithm" and "simulated annealing" in the first post are not jiving well with the mental model I have of the problem you are trying to solve.  In any case, occlusion queries are pretty simple:


1) Render some things to populate the depth buffer

2) Issue a begin occlusion query command

3) Render some more stuff

4) Issue an end occlusion query command

5) Get the result 'N' from the query which tells you the number of pixels that have failed the depth buffer test.


To start out you will have to render your mesh between a begin and end query command in such a way that you know every pixel will fail so you know its initial pixel count; you can subtract 'N' from this value down the road to get the area left uncovered by your disks.  You will want to use an orthographic projection so each pixel, regardless of its depth, has the same projected area.


In my experience using compute shaders to solve a generic problem is never a performance win unless you aggressively restructure the algorithm to accommodate the various quirks of the GPU architecture.   The amount of work it takes to optimization a compute shader solution is often similar to the amount of work in takes to recast your algorithm into a rasterization task.  For reasons that are not entirely clear to me GPUs nudge closer to their peak theoretical performance when you are blasting triangles instead of running compute shaders making a rasterization method a clear winner in a lot of cases.  This may not be true with workstation cards and OpenCL does a good job at parallelizing your entire machine (even the integrated graphics) so there might be performance wins in that department.

Edited by nonoptimalrobot

Share this post

Link to post
Share on other sites
I just had an alternative idea using rasterization (if I understand your problem right, and you can project everything to a rectangular area):

- use a rendertarget, one channel, maybe even float precision, as big as you can/wish
- project your circles with simple alpha blending. You could even anti-alias the border
- do a manual mip-map downscale to compute the sum (parallel reduction)

Anyway: You got some screenshots/sketches for illustration ?

Hope that helps.

Edit: There's also the analytic way. The Area of Intersecting Ellipses (Eberly): Not sure if this covers "tilted" ellipses. This one does. Though I wonder if this is feasible/applicable if you have more than two ellipses overlapping. Edited by unbird

Share this post

Link to post
Share on other sites



Sorry the colouring algorithm (which your right, probably isn't even the correct term) is used to compute a value in the objective function of the annealing algorithm. The annealing is used to optimize the placement of these ellipses over a mesh. I'm using a GPU approach similar to the on used in:


Han, Y., Roy, S., & Chakraborty, K. (2011, March). Optimizing simulated annealing on GPU: A case study with IC floorplanning. In Quality Electronic Design (ISQED), 2011 12th International Symposium on (pp. 1-7). IEEE.


It works very nicely so far, except that i've hit a bottle neck on this particular area calculation. When i mentioned: "Currently I run 256 to 1024 compute shader invocations depending on the resolution of my current approach, each calculating the overlapped area asyncronously." I meant that each compute shader invocation is computing the area for their respective energy value from the objective function.




Here is an image example:


Top (Side view):


    Red = original mesh surface

    Blue = projected mesh surface

    Black = disks and their projections


Bottom (Top-Down view):


    Blue = projected surfaces

    Green = uncovered area I want to calculate



Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!