Arc subdivision algorithm

Question

I'm looking to sample from a texture along a circular arc in a fragment shader. That kind of rules out recursive methods such as this.

I have come up with a few different ways to accomplish this: Two that seem the most reasonable are (Given start position p, center c, radius r = length(c-p), angle (arc extent) theta in radians and N positions):

1) Rotate the vector p-c about c by theta/N, N times: This requires the construction of a rotation matrix which will be repeatedly used: cost is two trig functions, N 2x2 matrix multiplies, N or so vector subtractions

2) Find the chord length of one segment traversing a sector: Its length is 2*r*sin(theta/2). Once I have the first vector I can rotate it and add it to the previous position to "step along" my arc. The problem with this method is that I still don't know the expression to obtain the orientation of my length 2*r*sin(theta/2) vector. Even if I did I'd likely need trig functions to construct it. I still need to rotate it so that might require me to still build a rotation matrix. Ugh.

Are there other methods I could consider?

Can you elaborate on what you mean by "sample ... along a circular arc"? Would you be sampling in a circle (or portion of a circle) around each pixel? And would the arc be the same for every pixel (same angle and/or radius)? Or something else? Also, why are you trying to do this? Are you by any chance trying to produce a radial blur? — user1118321, Jan 17 '12 at 04:21
I'll not reveal exactly what it is i'm doing. Hopefully you'll see it in a game someday. As for a radial blur, acceptable results are usually obtained by sampling along a line. — Steven Lu, Jan 17 '12 at 19:03
It is more of a curved blur. A blur that follows the motion of a rigid object, to be exact, and it is a linear combination of a circular motion about a fixed center (rotation) and linear motion — Steven Lu, Feb 13 '13 at 20:33

score 3 · Accepted Answer · answered Jan 17 '12 at 04:31

I think that once you start using circles and angles you are bound to have a couple of trig calls. Given that, the first method seems OK. I'd only note that I do not see the need for 2D matrix multiplies as such if act iteratively on the points.

void f(float cx, float cy, float px, float py, float theta, int N)
{
    float dx = px - cx;
    float dy = py - cy;
    float r2 = dx * dx + dy * dy;
    float r = sqrt(r2);
    float ctheta = cos(theta/(N-1));
    float stheta = sin(theta/(N-1));
    std::cout << cx + dx << "," << cy + dy << std::endl;
    for(int i = 1; i != N; ++i)
    {
        float dxtemp = ctheta * dx - stheta * dy;
        dy = stheta * dx + ctheta * dy;
        dx = dxtemp;
        std::cout << cx + dx << "," << cy + dy << std::endl;
    }
}

Given large N, you might find that some errors accumulate here. Given some assumptions around N and theta you might be able to make some small angle approximations for the trig.

Summary: If you want the specified number of points and are using arcs, I cannot see that you are really going to find a way to do much less computation than something close to option 1).

Seems to me like this is performing the same operations as a rotation matrix multiplication would. I reckon doing the matrix mult should be faster on the hardware. I figured if I know my value of `N` and `theta` to begin with I can generate the matrix in the vertex shader. Thanks though. — Steven Lu, Jan 17 '12 at 19:11
Fine! Fast and can even be made faster in cases where tens or thousands of arcs are drawn eg. rounded corners in polygons. I implemented a version where c/sthetas are calculated outside that function for full circle (angles 0-2PI) and implemented custom stopping criterion: drawing is started from px,py as normally, but there is also end coord `ex`, `ey` and the exit occurs when current x is more or less than ex (different behavior in upper and lower half). I added also CCW/CW functionality (essential in polygon drawing, there can be holes:). Thanks for this snippet! — Timo Kähkönen, Feb 11 '13 at 18:55

Arc subdivision algorithm

1 Answers1

Linked