Equation of a line.

On a previous thread, David posted that A+t*(B-A) was the expression for any linear curve in any number of dimensions. I was not sure, but I figured that A and B must be vectors, and t was a parameter, and made the below definition to try it out. (lots of components to draw a line, but I'm just trying to understand the equation)

I had been searching for advice on some geometry topics worth exploring for a class, and now I'm in the class and the teacher wants me to start by learning about splines in general (not nurbs). I just spent the day learning linear spline interpolation, then quadratic, then cubic. I didn't try working them by hand yet, but I'm getting the concepts. It seems cubic is the lowest degree where you can get C2 continuity, which makes it smooth. I read over parameterization and how that simplifies the number of equations. I read about space curves, and then the differences between Hermite, Catmull-Rom, and Cardinal spline, but then got tired and had a cocktail.

So I guess I'm looking for any direction or advice on how to understand parametric curves in 3d space, and how they can be defined (splines or otherwise). Thanks!!!

Replies to This Discussion

Permalink Reply by David Rutten on January 10, 2010 at 3:49am

Hi Chris,

nice job, A and B are actually points, not vectors. They are the start and end points of the finite segment.

If you sample the line segment purely on the 0.0 to 1.0 parameter range, you'll 'discover' the {1,1,2} and {2,-1,-1} points as the extremes.

You can of course rewrite the line equation using a point and a vector, for example:

A + t * S

where A is the start point of the line, t is the parameter along the line and S is the direction vector of the line. The direction of course is the vector from A to B, which is why you can replace (B-A) with S without changing the line in the slightest.

A+t*(B-A) is usually used to define finite and infinite line segments, whereas A+t*S is more often used to define rays (semi-infinite line segments).

My cubic spline math is not really up to snuff, but it is reasonably easy to create a deCasteljau evaluator for a 4-point, cubic, bezier curve (no weights allowed). deCastelau allows you to evaluate the location and the tangent of a cubic spline in a very visual way. There are other algorithms to evaluate these properties (better algorithms), but they don't allow you to visually construct the answers.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

Permalink Reply by Chris Wilkins on January 10, 2010 at 5:10pm

Ahhh... Providing the endpoints does seem much more intuitive way to define the line.

Thanks for the deCastelau reference. I only tried four control points so far, but it looks just like what the nurbs curve component outputs. Is that coincidental?

I'll try doing it with equations and function components next. What are the better algorithms you mentioned?

Permalink Reply by David Rutten on January 11, 2010 at 2:09am

Nope, no coincidence. Cubic Beziers are a subset of Nurbs curves. Unless you assign weights to a 4-point, degree=3 nurbs curve, you get the exact same shape.

A more numerically stable algorithm (and also more versatile) would be deBoor's algorithm

--
David Rutten
david@mcneel.com
Poprad, Slovakia

Permalink Reply by Suryansh Chandra on January 11, 2010 at 4:08am

This indeed is a very useful discussion. This is what I had tried to embark upon somewhat in a discussion quite a while ago here. But I suppose I could never explain it well.

One question though: what Chris gets in the end is a polyline which has got a resolution directly proportional to processing time. I believe when Rhino draws a curve, there is another algorithm involved which interpolates those points into a curve and not a polyline, and probably does it really really fast?

This brings me to another question I've had in mind for a while: what is the most accurate way of duplicating a curve:
1. Divide the curve into several 100s of points (depending on the complexity of the curve) and then interpolate the new curve through these points?
2. Get CVs of the original curve, and use those to make the new one.

This is not a copy operation, I asked because I often came across this problem whenever morphing between two curves, and some other occasions as well. I always found the second method to be far lighter and several times more precise...

Permalink Reply by Vicente Soler on January 11, 2010 at 5:16am

My guess is:
Using the method mentioned above you get world space resolution.
Rhino draws the curves using screen space resolution (pixels in the screen).

The most accurate way would be number 2 but you have to also know the degree of the curve, if the weight of any control point has been changed, if it is closed and periodic.

Permalink Reply by David Rutten on January 11, 2010 at 5:21am

Hi Suryansh,

Rhino eventually draws only straight line segments I believe (but don't quote me on that). We do however cache nurbs curves for display purposes as simple Bezier curves, which then get subdivided on the fly when needed. We dynamically adjust the subdivision accuracy based on redraw rates and other factors. I believe we are also looking into view-based subdivision for Rhino5 in an attempt to speed up the drawing routines even more for far away geometry.

Recreating a curve by fitting it through a set of sample-points is a terrible way to approximate something. Just ask lower-case-jim on the Rhino newsgroup and he'll embark upon another diatribe about why this method should almost never be used, how stupid we are to still use it anyway and what problems it is causing down the line. He's right of course (he tends to be), but the alternatives are either very difficult to backport into Rhino, very difficult to write in the first place, or perform worse in certain cases.

One of the major problems with indiscriminate curve fitting is that it totally and utterly fails to recognize platonic curve types such as Line and Arc segments. So, when you trim a surface with a circle, Rhino solves several thousand intersection points, then fits a curve through these points which is indeed accurate to within tolerance, but it is not an arc.

There are other methods to approximate curves, and the FitCrv command in Rhino uses the best general purpose one we have. I'm afraid I don't know how it works, but I'm certain that it is woefully complicated, as it has been adjusted and fine-tuned and upgraded and improved for over 10 years.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

Permalink Reply by Vicente Soler on January 11, 2010 at 6:23am

I find it very strange that there is no adaptive subdivision depending view position and resolution. I remember reading about programming the display of a bezier curve and one of the main points was to use adaptive subdivisions for faster redraw depending on these factors.

OpenGL handles bezier curves natively, so i guess rhino takes advantage of this. I'm not sure if opengl will then adapt the subdivisions to fit the screen or rhino has to set them manually.

Permalink Reply by David Rutten on January 11, 2010 at 6:36am

The problem is you have to make the code that determines the level of subdivision perform faster than the total benefit you get out of not drawing segments in low-density areas.

Graphics cards can draw line segments very quickly, which means that the optimized code has to be very optimized indeed to make a difference. Essentially, you have to write an optimization that runs on the CPU which has to compete with the GPU.

--
David Rutten
david@mcneel.com
Poprad, Slovakia

Permalink Reply by Suryansh Chandra on January 11, 2010 at 9:51am

"why this method should almost never be used, how stupid we are to still use it anyway and what problems it is causing down the line"

This does surprise me.. that in the end, it all IS interpolated.. I was expecting a more complex algorithm doing the hard work. Though looking at the way some other softwares (eg. AutoCAD) work and the frequent need to regenerate viewports does indicate that this is indeed is a widely applied technique.

RSS