• Advertisement
Sign in to follow this  

Circle Tessellation with tolerance

This topic is 3000 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'm trying to approximate a circle as a series of connected line segments (points spaced evenly around the circle), and I need a heuristic to determine the granularity of the approximation (i.e how many points to generate). This is for a vector renderer, so my desire is to keep the tessellation fine enough for individual segments to be invisible, while keeping the number of generated segments as low as possible. Currently my heuristic is "maximum segment length", i.e I determine the smallest number of segments needed such that each segment will be no longer than the specified max length. Unfortunately this is not the best solution: it over-tessellates large circles, and under-tessellates small circles. It seems like what I want to minimize isn't the length of each segment, but some measurement involving curvature, such as "the area of the region bounded by the segment and the circular arc which the segment is approximating", or "the distance from the segment's midpoint to the circle's surface". I can't find anything useful via google, probably because I don't know the exact term for what I'm trying to do.. If anyone has any tips/advice or useful links I'd appreciate it. thanks, Raigan

Share this post


Link to post
Share on other sites
Advertisement
For me "maximum segment length" sounds like it should work (although I'm tired today..). Do you have any picture showing the problems?

Share this post


Link to post
Share on other sites
I don't have any pics :(

The problem is that the quality varies depending on the radius of the circle relative to the seg length. For instance, a 200pix-radius circle drawn with 4pix-length segments looks great (it's probably over-tesselated, e.g using max-length of 8pix may be visually identical) while an 8pix-radius circle drawn with 4pix-length segments looks poor (it's under-tesselated, individual segments are visible).

At the limit, when max seg length > circle's diameter, the max-seg-length heuristic will choose to use a single segment, which is totally wrong.

As the size of the circle decreases, the curvature of the arc between segment endpoints increases; it seems to me that the problem is that the size of the segments in screenspace isn't really what we're trying to optimize.. instead we'd like the line segments to be so close to the surface of the circle that they're indistinguishable. So some sort of measurement of curvature or distance from segment to surface center seems in order.

It seems like for a given circle there should be a single "perfect" tessellation such that decreasing the number of segments would change the visual appearance, while increasing the number of segments wouldn't change the appearance at all -- in fact I can find such an optimum tessellation by hand/interactively for a given circle, but I need some sort of formula so that it can be calculated automatically.

Share this post


Link to post
Share on other sites
Quote:
Currently my heuristic is "maximum segment length"


Are they not all the same? Most people (including me) simply approximate a circle by a regular n-gon.

Quote:
It seems like what I want to minimize isn't the length of each segment,


This again surprises me. I understand that this is a vector graphics program, but the circles are still ultimately viewed on a screen with pixels of a certain size. It would seem to me that what you want -- and this is what I typically do -- is to fix the length of each segment at about 1 pixel. I just scale the number of segments linearly with radius, myself, since this is how circumference scales.

Quote:
It seems like what I want to minimize isn't the length of each segment, but some measurement involving curvature, such as "the area of the region bounded by the segment and the circular arc which the segment is approximating", or "the distance from the segment's midpoint to the circle's surface".


Disregarding my previous comments, it seems like this should not be too difficult. Let's say that you approximate a circle by inscribing a regular N-gon, consisting of the points,

x[k] = r cos(2 π k / N)
y[k] = r sin(2 π k / N)

for k=0...N-1.

Then the maximum distance between the polygon and the circle it is approximating is given by,

emax = r [ 1 - (1/2) sqrt[(1 + cos(2 π/N))2 + sin2(2 π/N) ] ]

modulo arithmetic errors. :-) (Just consider the midpoint of a segment; compute its distance from the center of the circle and subtract this from the radius).

Share this post


Link to post
Share on other sites
A typical approach is to use the distance between the interpolated midpoint and the true midpoint of a segment. If this distance is too great, say one or two pixels, then subdivide (in which case you already have the midpoint you need).

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Most people (including me) simply approximate a circle by a regular n-gon.
..what I typically do -- is to fix the length of each segment at about 1 pixel.


I'm using a regular n-gon, sorry -- I should have made this more clear, I'm just trying to find the "best" value for n. Using 1pixel-per-segment does indeed give high-quality results, but it's very wasteful when dealing with large circles.

For example, for a circle with relatively large radius (200-300 pixels), I can use segments that are 8 or more pixels in length without the tessellation being visible.

My guess was that segment length was only indirectly related to perceived error; Lord Crc has suggested a measurement of error that seems to fit my experiments much better -- measure the maximum distance between n-gon and true circle, which occurs at the midpoint of n-gon edges.

You could imagine that for large circles, segments which are several pixels in length nevertheless result in no perceptible error, because they're less than 1pix away from the circle's surface at their midpoint; this matches what I'm seeing in my tests.


I'm not sure how you arrived at your formula; it also seems like it might be a bit tricky to rearrange it so that I can easily calculate N for a given error.

Thankfully, trying to figure out your derivation led me to the term "apothem", which is the length of the line from circle center to segment midpoint -- exactly what we need!

Based on this I came up with the following:


given: radius r, # segs n, desired error r

a = r * cos(pi/n) //definition of apothem length

e = r - a
= r - (r * cos(pi/n))
= r * (1 - cos(pi/n))

rearrange to get:

n = pi / acos(1 - (e/r))


However I'm not sure if this is correct -- using e=0.1, it looks perfect, however I would have thought e=1 would look fine, and it doesn't.. this leads me to suspect that the formula is wrong and e=0.1 simply results in an overly-fine tesselation.


thanks,
Raigan

[Edited by - raigan on December 4, 2009 3:05:47 PM]

Share this post


Link to post
Share on other sites
[EDIT]
I actually made a mistake in the formula I posted. I redid it and got formula almost identical to yours, except for a factor of 2:
n = 2*pi/acos(1/(1+e/r))
[/EDIT]

I would use either your formula or mine and pick a value for e that looks OK.

Share this post


Link to post
Share on other sites
Thanks alvaro, I'll try that out; using my formula seems to result in more verts than necessary at small sizes, possibly yours is better in such cases.

Could you explain which measurement of error it's based on? I feel like I made a mistake with my derivation, but I can't find it..

Share this post


Link to post
Share on other sites
Quote:
Original post by raigan
Thanks alvaro, I'll try that out; using my formula seems to result in more verts than necessary at small sizes, possibly yours is better in such cases.


No, the two are almost identical. Fix e, plot the number of vertices as a function of the radius and you'll see that the two are basically on top of each other.

Quote:
Could you explain which measurement of error it's based on? I feel like I made a mistake with my derivation, but I can't find it..


It's complicated to explain, and it won't add anything of value.

If you are still not satisfied with your results, I'll suggest a more empirical approach: Pick a few representative radii and write down the desired n for each one. You can find that desired n by playing around with it until it looks good. Then some sort of interpolation between the values you obtain will probably work just fine.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Quote:
Original post by raigan
Thanks alvaro, I'll try that out; using my formula seems to result in more verts than necessary at small sizes, possibly yours is better in such cases.


No, the two are almost identical. Fix e, plot the number of vertices as a function of the radius and you'll see that the two are basically on top of each other.


AFAIK they're both supposed to be formulas for the same thing:

Define a desired error,
e = Radius - Apothem(n, Radius)
and solve for n.

[If so, then] [s]imply one of the formulas (yours or alvaro's) is incorrect.
[EDIT: But it turns out that this was not actually what alvaro was solving for.]

What I get (by simplifying what I wrote in my previous post and solving) agrees with raigan's answer. More precisely, I get,



which is equal to what raigan wrote for . (I verified this to my satisfaction by plotting the two on top of each other; proving equivalence using trig identities is left as an exercise for the reader ;-) ). (And since raigan's answer is more heavily simplified [than mine], I'd go with that in an implementation of course.)


Quote:
If you are still not satisfied with your results, I'll suggest a more empirical approach: Pick a few representative radii and write down the desired n for each one. You can find that desired n by playing around with it until it looks good. Then some sort of interpolation between the values you obtain will probably work just fine.


Aye, when human perception is involved, sometimes messy empiricism is all you've got. But in this case I don't see why using ceil(n) vertices with e=0.5 in the above formula should be anything short of perfect.

[EDIT: Moved equations from texify.org to codecog's Online LaTeX Equation Editor since texify seems to be having some problems on the server side...]

[Edited by - Emergent on December 6, 2009 4:56:00 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Quote:
Original post by alvaro
Quote:
Original post by raigan
Thanks alvaro, I'll try that out; using my formula seems to result in more verts than necessary at small sizes, possibly yours is better in such cases.


No, the two are almost identical. Fix e, plot the number of vertices as a function of the radius and you'll see that the two are basically on top of each other.


AFAIK they're both supposed to be formulas for the same thing:

Define a desired error,
e = Radius - Apothem(n, Radius)
and solve for n.

Although that's perfectly reasonable, I used something else, to see if I would get an easier formula. Draw a circle of radius 1 with center at the origin, draw a vertical segment going up from (1,0), say to (1,t). The distance between (0,0) and (1,t) is 1/cos(alpha), where alpha is the angle (1,0)-(0,0)-(1,t). I just tried to use 1/cos(alpha)-1 as a measure of how far from the circle a segment of length t is. That results in the formula I posted. The factor of 2 comes from the fact that I didn't consider the segment to be (1,-t) to (1,t), which might have been better.

It turns out that this doesn't result in a simpler formula, and the practical result of both is the same (as I expected).

Quote:
Simply one of the formulas (yours or alvaro's) is incorrect.

Whatever.

EDIT: Since for small values of x, x = sin(x) = tan(x) for all practical purposes, I played around with that kind of substitution and I arrived at a simpler formula that again gives almost indistinguishable results:

n = pi*sqrt(r/(2*e))

Then I realized that this approximation can be found by simply using the Taylor approximation cos(x)=1-.5*x^2 in your formula.

[Edited by - alvaro on December 6, 2009 1:32:13 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Although that's perfectly reasonable, I used something else[...]


Ah, ok.

Quote:
EDIT: Since for small values of x, x = sin(x) = tan(x) for all practical purposes, I played around with that kind of substitution and I arrived at a simpler formula that again gives almost indistinguishable results:

n = pi*sqrt(r/(2*e))


I like this a lot; it's a really good approximation for what raigan and I have, and should be somewhat faster to compute.... In fact, it
1 - Is an overestimate, so you will never under-tessellate your circle if you use this, and
2 - It differs from the exact formula by less than 0.25 -- so at the absolute worst, after you ceil the result it'll use only one extra vertex.

Share this post


Link to post
Share on other sites
Thanks for the great replies!

I can't find a mistake in my formula, but the reason I feel there might be an error somewhere is that I need to set e = 0.1 for it to look "perfect"; in contrast, Alvaro's original formula looks perfect using e = 0.5. This seems wrong to me since e should be in the same units in both cases..

Output from the new approximate formula almost exactly matches my formula; the difference appears to actually be *much* less than 0.25 for all radiuses I tested (1 to 500), I think at most it was less than 0.1, and the difference decreased as the radius increased.

But, the approximation uses e = 0.1, which really bugs me for some reason -- I don't understand why anything less than 1 isn't good enough.. the error's measured in pixels after all. I suppose it might be that, due to anti-aliasing, sub-pixel error is visible.

Anyway, this is definitely good enough for all practical purposes and I should really move on to more important things; actually the suggestion to simply build a table of known good values for n is the sort of practical solution I should keep in mind more often. I just really want to understand why my intuition regarding the error measurement is so far off!

Thanks again for all your help. :)

Share this post


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

  • Advertisement