• 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
DeathRay2K

Area of circle within square

18 posts in this topic

I'm trying to find the area of the portion of a circle within a square. I'm doing this for a non-realtime rendering of 2D circles; I plan to use the area to calculate the antialiasing. Unfortunately I really have no idea how to go about this, and the closest thing I've been able to find with Google is squares fully with circles, which is of course no help at all. Any help would be much appreciated!
0

Share this post


Link to post
Share on other sites
assuming im correctly interpreting your question..

area of a circle is pi*r^2
area of a square is w^2 where w = width and w = 2*r

so square = 4r^2
and circle is pi*r^2 so the ratio of a squares area to the area of the circle inside of it is (4r^2)/(pi*r^2) or 4/pi
0

Share this post


Link to post
Share on other sites
I don't want the ratio of areas, I want to figure out how much of the circle is within the square.
This image shows what I mean; I would want to figure out the area of the darker region in this example:

You see, I don't want to figure out how much area a circle takes up in the square formed by its extremities, I want to know how much some circle overlaps some square, where the two have no relation at all.
0

Share this post


Link to post
Share on other sites
How comfortable are you with integrals?

I would create a function to represent the circle and clamp it to the range [0,1] then integrate that function over the domain from [0,1] and the result would be exactly the area of the circle in that range. Let me work something out to start you off.
0

Share this post


Link to post
Share on other sites
From your picture you can calculate the area of the overlapping square and circle like this:

* You know that every angle inside of a square is 90 degrees.
* You need to find the distance from the corner of the square that is inside the circle to the edge of the circle -- this will be your radius

So:

angle = 90 deg (t)
radius = point_2 - point_1 (r)
overlapping area = 0.5t*r^2

NOTE: This is in radians.

radians = pi / 180 degrees
0

Share this post


Link to post
Share on other sites
The circle isn't necessarily (And certainly will very rarely be) aligned in any fashion with the square, so I can't simply figure out the radius around a corner, because the circle is unlikely to be perfectly aligned with a corner, or simply overlapping one corner.

I have little experience with integrals, but I am certainly happy to learn and attempt them if necessary.
0

Share this post


Link to post
Share on other sites
So here is what I think may work:

function for a circle centered at (x0, y0) with radius r


f(x) = +-sqrt( r^2 - (x-x0)^2 ) - y0 and 0 where invalid


You can then integrate this function over the range [0,1]. But since you only want the parts in the square you would clamp f(x) to the range [0,1].

something like this:


area = integral( 0, 1, clamp( f(x), 0, 1 ) )


Though I think clamp needs a little work. it may be a bit different than that. Its pretty close I imagine.

Additions:
Basically it assumes that the lower left corner of the square is at the origin and the sides of length one. You can integrate over the x in the range zero to one.

The tricky part will to make sure the integral does not count any part of the circle that is completely above or below the pixel. This is what I was trying to accomplish with the clamp. Basically if the bottom edge of the circle is greater than one or the top edge of the circle is lower than zero for any given value of x, you will need to set the function to zero.

[Edited by - Lexdysic on July 28, 2008 12:12:51 AM]
0

Share this post


Link to post
Share on other sites
How accurate and how fast does it have to be? You want a numerical method?

Else, you can use some rendering callbacks by rendering both, and give you the number of pixels overlapping.

Otherwise it will be quite complicated. My intuition says you'll have to clip the circle using the rectangle's plane, but I wouldn't know exactly how to derive the area for the clipped region, which would rely on integral calculus.
0

Share this post


Link to post
Share on other sites
He mentions anti-aliasing, so I think he's looking for sub-pixel precision here.

The easiest solution may simply be to super-sample pixels on the edge of the mathematical circle, choosing enough samples to yield acceptable visual quality. Four or nine sample grids, 2x2 and 3x3 respectively, per pixel might be accurate enough for your needs. If not, you can subdivide greater powers of two, and trivially accept/reject entire blocks of sub-samples... Not sure how this compares speed-wise to a pure numerical function, but its worth investigating. I would think that an 16 sample, optimized test would be sufficiently fast and accurate for most needs, and it would probably lend itself well to parallelism and running on SSE or similar instruction sets.
0

Share this post


Link to post
Share on other sites

  1. Get area of circle
  2. Multiply by fraction of circle covered by chord ( = area of pie slice)
  3. Subtract area of isosceles triangle ( = area of circular segment)
  4. Add area of right triangle


[Edited by - AngleWyrm on July 28, 2008 5:30:50 AM]
0

Share this post


Link to post
Share on other sites
Quote:
Original post by AngleWyrm

  1. Get area of circle
  2. Multiply by fraction of circle covered by chord ( = area of pie slice)
  3. Subtract area of isosceles triangle ( = area of circular segment)
  4. Add area of right triangle


Wouldnt that fail if the circle intersected parallel edges of the square?
0

Share this post


Link to post
Share on other sites
I think it would be easier to generalize this idea to triangles and make your rectangle out of two triangles. Then you have not so many cases of how the circle can intersect the rectangle. A sum of areas of triangles and integrals over a circle will give you the final result. Here I have drawn some possible cases one would need to deal with:
some cases
Or you could check for all possible cases of intersection between the square and the circle. In both cases you end up with a sum of triangle areas and circle portions. The area of the triangles is easy to calculate. Portions of a circle you can calculate either with an integral:
some cases
...or by:
some cases
Let me know if you need some help with the math.
0

Share this post


Link to post
Share on other sites
That seems like your best solution. The area of a polygon is easy to find, as is the cord(?) areas.

Finding the actual inner polygon isn't that hard if you know how to intersect a segment with a circle.
0

Share this post


Link to post
Share on other sites
I think some of this stuff is a bit over my head, so for now at least, I've decided to simply supersample the edges, which gives me decent quality and great speed. It might not be as accurate as a strictly mathematical solution, but it's really quite fast, even with 16x16 samples (Though 4x4 usually seems to be good enough). Thanks for all the help! If I decide to go to something more advanced I expect I'll be asking again. ;)
0

Share this post


Link to post
Share on other sites
Odd... this is the same sort of thing I've been trying to figure out all day. The question I posted elsewhere was this:

-------

Say you have a circle who's diameter is the same as the width of one quadrant. How would you find the area of this circle that falls into each quadrant if the circle's center point was not at the origin?

-------

Same basic problem. I'm good with the math I know, but my studies ended just before trig, so I'm clueless. Surely there's some formula which could take as input the x and y offset of the circle and assume the circle's diameter and the sides of each of the four boxes (quadrants) all equalled 1.
0

Share this post


Link to post
Share on other sites
I just took a math class this past year and we totally did this stuff, I totally forget how to solve this, search on Google, there are steps and formulas to solve this.
0

Share this post


Link to post
Share on other sites
Here's what I came up with...

(Look at AngleWyrm's picture to see what I mean...)

Find the area of the triangle that falls within the square.

Find the area of the circle segment, which is the rounded portion outside the triangle.

The formula for finding the circle segment can be found here:

http://www.mathopenref.com/segmentarea.html

I'm going to verify all of this, so this reply might get editted.
0

Share this post


Link to post
Share on other sites
Finding the intersection points of a line and a circle (2D) or sphere (3D) is useful in many situations. So I just wanted to post a function that finds those intersection points.

Intersection of a line and a circle
A and B are points of the line, P is the center of the circle.

int IntersectionLineSphere(vec *Q1, vec *Q2, vec A, vec B, vec P, float r)
{
vec pa = A - P;
vec ab = B - A;

float a = dot(ab,ab);
float b = dot(pa,ab);
float c = dot(pa,pa) - r*r;
float d = b/a;

float s = d*d-c/a;

if (s < 0.0f)
return 0; // sphere and line do not intersect
else
s = sqrtf(s);

float t1 = -d+s;
float t2 = -d-s;

*Q2 = A + ab * t1; // closer to B
*Q1 = A + ab * t2; // closer to A

int intersections = 0;

// intersection points within line segment?
if (t1 > 0.0f && t1 < 1.0f)
intersections++;
if (t2 > 0.0f && t2 < 1.0f)
intersections++;

// will be either 1 or 2
return intersections;
}


The function is valid for 2D and 3D, and not optimized (const pointers to A and B). Having found the intersection points Q1 and Q2 one can find the "theta area" of the circle.

float SegmentOfCircle(vec Q1, vec Q2, vec P, float r)
{
vec s1 = Q1 - P;
vec s2 = Q2 - P;

float costheta = dot(s1,s2)/(length(s1)*length(s2));
return 0.5f*acosf(costheta)*r*r;
}



float AreaOfTriangle(vec A, vec B, vec C)
{
vec s1 = B - A;
vec s2 = C - A;
vec cr = cross(s1,s2);

return 0.5f * length(cr);
}


Now DeathRay2K found a good approximative solution, but the functions above would be the tools to find the correct area of the portion of a circle within a triangle (2 triangles = square). Of course it shouln't be done in real time. If someone is interested in finding this area I could post some code (~150 lines).
0

Share this post


Link to post
Share on other sites
There is also the sampling option: you generate many random samples in a shape that contains both the square and the circle. Then you count how many samples are inside the square, how many inside the circle and how many inside both. From that you can find the overlapping area...

I don't really think this is what you need, but I though to put it here nonetheless, you never know....
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