Calculating area left uncovered by overlapping projected circles on a plane

Math and Physics Programming

Started by pondwater August 23, 2013 06:56 PM

4 comments, last by pondwater 10 years, 7 months ago

192

Author

August 23, 2013 06:56 PM

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.

nonoptimalrobot

420

August 23, 2013 08:38 PM

Assuming I'm following you (and I might not be), it sounds like you can turn this into a rendering problem use occlusion queries.

http://nonoptimalrobot.wordpress.com/

http://robot-asylum.com/

pondwater

192

Author

August 23, 2013 09:48 PM

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.

nonoptimalrobot

420

August 23, 2013 10:44 PM

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.

http://nonoptimalrobot.wordpress.com/

http://robot-asylum.com/

unbird

8,359

August 25, 2013 11:07 AM

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.

pondwater

192

Author

August 26, 2013 01:35 AM

@nonoptimalrobot

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.

@unbird

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

Calculating area left uncovered by overlapping projected circles on a plane

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Calculating area left uncovered by overlapping projected circles on a plane

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines