Spline curve tesselation / LOD

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

Recommended Posts

Can anyone recommend a simple and stable scheme for spline/curve LOD tessellation/rendering? Do the only decent solutions involve computing parameterizations on arc-length or curvature?

I've been playing with variations on the following recursive subdivision scheme I came up with, which doesn't work too well (Please excuse my funky pseudo-code ;):

Let f be the spline function defined on interval [0, 1].
Let t0 and t1 be curve parameters with 0 <= t0 <= t1 <= 1.
Let tol be some error tolerance.
Let depth be recursive depth.
Let max_depth be the maximum allowable recursion depth.
Let points be a list of points built by my algorithm.
Let ||.|| denote vector length.
begin procedure split_curve  add f(0) to points  call split_curve_helper(0, 1, 0)  add f(1) to pointsend procedurebegin procedure split_curve_helper(t0, t1, depth)    if depth < max_depth    t = (t0 + t1) * 0.5    l = ||f(t1) - f(t0)||     l' = ||f(t) - f(t0)|| + ||f(t1) - f(t)||    if ((l' - l) / l') > tol      call split_curve_helper(t0, t, depth + 1)      add f(t) to points      call split_curve_helper(t, t1, depth + 1)    end if  end ifend procedure

The idea is that the subdivided segments better approximate the curve, where (l' - l) / l') provides a measure of error. The pathological case arises when f(t) == (f(t0) + f(t1)) * 0.5 and things break :( Thanks.

Share on other sites
I'm not sure I like the way you've defined tol, in your pseudo-code. You are looking at the length of a given chord of the curve, from t0 to t1 and comparing against the sum of two chords built by subdividing [t0, t1] into [t0, t] and [t, t1]. I wouldn't expect this to give you the best result because for many curves you'd probably find that particular error is small even when the curve is coarsely tessellated. (Any part of the curve where radius of curvature varies slowly would allow very coarse tessellations with only a small error as you have defined it.) I think the curvature approach would work better, and you can approximate curvature error by looking at the distance between the midpoint of the chord from f(t0) to f(t1) and the accurate, computed midpoint, f(t). And might as well let tol be based on the square of that distance to save some computation. So, that would look like:

if (depth < depth_max)  t = (t0 + t1) * 0.5  a = f(t0) + 0.5 * (f(t1) - f(t0))  b = f(t)  if (LengthSquared(a, b) > tol)    call split_curve_helper(t0, t, depth + 1)    add b to points    call split_curve_helper(t, t1, depth + 1)  end ifend if

So, a is the midpoint along the linear chord from f(t0) to f(t1) and b is the actual midpoint, f(t), accurate to floating point precision. LengthSquared is a representative error, the Euclidian distance error, between your current chord and the actual curve.

So, the nice thing about this approach is that it is easy to associate it with a screen resolution. If you know how your physical units map to screen pixels (e.g., via the model transform, projection and viewpoint matrices), you can easily determine a value of tol to pass in so that you can subdivide the curve so that there is no error larger than 1 pixel....you would then be drawing the curve as accurate as is necessary for a given viewpoint.

You could also do something that computes the actual radius of curvature at the point, but I don't think that would be as convenient as this approach.

[Edited by - grhodes_at_work on August 31, 2010 10:53:12 AM]

Share on other sites
Unfortunately your approach still suffers from the pathological case that mine does currently. The image below demonstrates the problem.

First, for simplicty, note that f(t0) + 0.5 * (f(t1) - f(t0)) = 0.5 * (f(t0) + f(1)). In the image above, we have the case where (f(t0) + f(t1)) * 0.5 = f(t) for t0 = 0, t1 = 1, and t = 0.5. This in fact occurs at the very fist level of recursion. Both of our stopping criteria will incorrectly terminate recrusion.

In my case, we have ||f(t) - f(t0)|| + ||f(t1) - f(t)|| = ||f(t1) - f(t0)||.

In your case, we have ||(f(t0) + f(t1)) * 0.5 - f(t)|| = 0.

Aside for this one huge, deal-breaking problem, I do agree that your approach has the substantial benefit of enabling a simple LOD scheme parameterized on screen-space error. Nice touch ;).

Share on other sites
Ah, yes. :) Right you are!

So, I can think of pathological cases of all sorts that would prevent doing localized error checks on completely general splines (e.g., that might have repeated knots to generate discontinuities). But you can probably do better, albeit perhaps slightly slower.

You could go ahead and make the leap to look at local radius of curvature. With 3 points, f(t0), f(t), and f(t1), you can compute a circumcircle to get the radius of curvature..of course if the 3 points are collinear you would just have a special case. Depending on the basis functions you are using, you may be able to find a closed form solution for the radius of curvature at f(t). Otherwise, you could use two additional points around f(t), some very small distance, epsilon, away, then compute a second circumcircle with f(t-epsilon), f(t), f(t+epsilon) and compare the radii of the two circumcircles.

The other thing you could do, which you'll consider less desirable but it should work, is simply to subdivide until the length of the segment f(t0)-f(t1) is less than some tolerance length...regardless of any error measurement against the actual curve...and in thinking about screen space error that length could be one pixel. You could make this a bit faster by using a 1-norm (add the x and y components of the vector) instead of a 2-norm (the standard Euclidian length) when checking the length.

[Edited by - grhodes_at_work on September 3, 2010 11:50:14 AM]

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

• 10
• 11
• 9
• 9
• 10
• Forum Statistics

• Total Topics
631753
• Total Posts
3002098
×

Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!