Jump to content
  • Advertisement
Sign in to follow this  
udvat

Equally partitioning a Curve

This topic is 4073 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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by udvat
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.


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 this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
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.


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 this post


Link to post
Share on other sites
Quote:
Original post by The Reindeer Effect
Any 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 this post


Link to post
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;
}

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!