# Equally partitioning a Curve

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

## Recommended Posts

have to equally partition a curve. -------------------------------------------------------------------------- let the parametric eqn of curve is, C(s)=(u(s),v(s),w(s)); where s is in [s0,sN] according to Bartels and Hardtke method, the length of an arc of C is related as, dl/ds = f(s).............(4) f(s)=sqrt( (du/ds)^2 + (dv/ds)^2 +(dw/ds)^2 )...................(5) the total length of C can be calculated by L= integrating f(s)ds in the range [s0,sN].........................(6) Inversion of eqn(4) yields, ds/dl=1/f(s)................................(7) Given the initial condition s(0), eqn(7) describes parameter s as a function of the arc length l.By numerically integrating (7) in n consecutive intervals of length delL=L/n, we obtain a sequence of parameter values s. ------------------------------------------------------------------ My questions: 1. Based on the above informations,is the following correct??? s(1)=s(0)+dels where dels=1/f(s0).delL s(2)=s(1)+dels where dels=1/f(s1).delL 2.The Runge-kutta method for solving diff eqn is defined as yn+1=yn + h+f(xn,yn) May I apply it on ds/dl=1/f(s)? In Runge-kutta f is taking 2 parameters where my one just have one parameter s. How can I apply Runge-kutta ? Or plz suggest any other method.

##### Share on other sites
Unfortunately I can't help you with your problem, but it strikes me that 'Maths & Physics' will be a better place to ask for help - I'll move this over for you [smile]

Cheers,
Jack

##### Share on other sites
When performing Runge-Kutta, you would be sampling not only at each step along the curve from S0 to SN, but also taking samples around these steps to detect any deviation in the curvature of the path (ie: a curved curve).

Gaffer on Games shows how to do this for the integration of velocity.

##### Share on other sites
Runge-Kutta is really overkill here, since arc-length parameterization isn't a differential equation. I suppose you might be able to use RK, but I can't immediately see how.

Conceptually, you're just approximating the spline as a bunch of consecutive line segments and summing their length. There are adaptive thingies you can do if your splines are spiky or badly conditioned or you need high accuracy, but if you're not pressed for processing time even those aren't generally necessary.

##### Share on other sites
Dave Eberly has an arc-length parameterization article here which covers a lot of the details. It would be possible to use RK to implement the Integral method.

##### Share on other sites
Quote:
 Original post by udvatInversion of eqn(4) yields,ds/dl=1/f(s)................................(7)Given the initial condition s(0), eqn(7) describes parameter s as a function of the arc length l.By numerically integrating (7) in n consecutive intervals of length delL=L/n, we obtain a sequence of parameter values s.

When you want to integrate the equation ds/dl = 1/f(s), you need to solve for dl = f(s) ds, which means using the reciprocal ds/dl gets you nowhere. You would have to use dl/ds = f(s) when applying Runge-Kutta, but this tells you "l" in terms of "s", but you really want "s" in terms of "l". The PDF link shows how to relate s to l using numerical methods.

In that PDF, I use "s" for the arc-length parameter (your "l") and "t" for the original curve parameter (your "s"). The document shows how to compute "t" for a specified "s". You pay this cost at runtime. In practice, when the curve never changes during runtime, it is better to use the numerical method in my PDF to compute offline a set of n samples t given s, 0 <= i < n, and then fit the (s,t) pairs with a polyline or higher-degree polynomial function, say t = g(s). The idea is that the approximations for t given s are "close enough" and that the evaluation of g(s) at runtime is much less expensive than the numerical method I describe in the PDF. (I will update the PDF shortly to show how to do this.)

Edit: I should mention that you can solve ds/dl = 1/f(s) using a numerical method for differential equations. The main concern is whether f(s) nearly zero causes numerical problems. The approach I mentioned in my PDF has a similar issue, because there is a division that occurs in that process. It would be interesting to compare the results of the two approaches.

[Edited by - Dave Eberly on April 23, 2007 10:12:58 AM]

##### Share on other sites
Quote:
 Original post by SneftelRunge-Kutta is really overkill here, since arc-length parameterization isn't a differential equation. I suppose you might be able to use RK, but I can't immediately see how.

Any definite integral can be converted into a differential equation pretty easily, using the fundamental theorem of calculus.

To the OP: Do you have any information at all about u,v,w (e.g. they are polynomials?). To do this generally looks like it would require a lot of computation.

Arc length is
int [a,x] of | c'(t) |

let F'(t) = | c'(t) |
and F(a) = 0

solving the IVP gives
F(x) = arc length from a to x

Now we want [s_1,s_2,...,s_n)] such that s_1 = a, s_n = b (endpoints)
This is a partition of n-1 path segments

and let G(x,i) = | F(x) - (i-1)*L / (n-1) | where L = arc length on [a,b]

We want to minimize G(x,i) for i=[2..n-1]. For each i we can do a simple binary search over [a,b] and cutoff when G(x,i) is below some threshold. The result is that s_i ~= argmin G(x,i)

##### Share on other sites
Quote:
 Original post by The Reindeer EffectAny definite integral can be converted into a differential equation pretty easily, using the fundamental theorem of calculus.

As I mentioned, you can formulate the problem so that a numerical ODE solver may be applied. The problem, though, is that you have to iterate the ODE solver a large number of times when the specified arc length is large. The numerical inversion that I discuss in my PDF has a more "global" flavor, requiring many fewer iterations.

##### Share on other sites
My question is to Dave Eberly.............

would you plz explain the '*' marked lines in your pseudocode?
when they are needed?

Point Y (float t); // The parameterization of the curve, a <= t <= b.
Point DY (float t); // The derivative of Y(t), a <= t <= b.
float Speed (float t) { return Length(DY(t)); }
float ArcLength (float t) { return Integral(a,t,Length(DY()); }

float GetT (float s) // 0 <= s <= total_arc_length
{

float L = ArcLength(b); // precompute L if you frequently call GetT
float t = a + s*(b-a)/L; // precompute (b-a)/L if you frequently call GetT

for (int i = 0; i < max; i++) // ‘max’ is application-specified
{
float F = ArcLength(t) - s;
*****if ( Abs(F) < epsilon ) // ‘epsilon’ is application-specified
*****return t;
float DF = Speed(t);
t -= F/DF; // warning: DF = 0 might be a problem
}
// maximum iterations exceeded, you might want to trap this
return t;
}

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633663
• Total Posts
3013232
×