Jump to content

  • Log In with Google      Sign In   
  • Create Account


Calculating area left uncovered by overlapping projected circles on a plane


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 pondwater   Members   -  Reputation: 191

Like
0Likes
Like

Posted 23 August 2013 - 12: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.


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


Sponsor:

#2 nonoptimalrobot   Members   -  Reputation: 408

Like
1Likes
Like

Posted 23 August 2013 - 02: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.



#3 pondwater   Members   -  Reputation: 191

Like
0Likes
Like

Posted 23 August 2013 - 03: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.


Edited by pondwater, 23 August 2013 - 03:49 PM.


#4 nonoptimalrobot   Members   -  Reputation: 408

Like
1Likes
Like

Posted 23 August 2013 - 04: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.


Edited by nonoptimalrobot, 23 August 2013 - 04:46 PM.


#5 unbird   Crossbones+   -  Reputation: 4816

Like
0Likes
Like

Posted 25 August 2013 - 05: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.

Edited by unbird, 25 August 2013 - 05:18 AM.


#6 pondwater   Members   -  Reputation: 191

Like
0Likes
Like

Posted 25 August 2013 - 07:35 PM

@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

 

cKjqH9v.png






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS