• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
pondwater

Calculating area left uncovered by overlapping projected circles on a plane

5 posts in this topic

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
0

Share this post


Link to post
Share on other sites

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

1

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
0

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
1

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
0

Share this post


Link to post
Share on other sites

@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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0