# Circle Tessellation with tolerance

This topic is 3243 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
For me "maximum segment length" sounds like it should work (although I'm tired today..). Do you have any picture showing the problems?

##### 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 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 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 on other sites
Quote:
 Original post by EmergentMost 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 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 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 on other sites
Quote:
 Original post by raiganThanks 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 on other sites
Quote:
Original post by alvaro
Quote:
 Original post by raiganThanks 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,
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,

$n = \frac{2 \pi}{\cos^{-1}\left(2 \left(1 - \frac{e}{R} \right)^2 - 1 \right)}$

which is equal to what raigan wrote for $\frac{e}{R} \in (0,1]$. (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]

1. 1
Rutin
48
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 16
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633003
• Total Posts
3009845
• ### Who's Online (See full list)

There are no registered users currently online

×