Knot multiplicity greater than order of curve erro

I’m debugging some graphics software in Visual Studio 6.0 that uses OpenGL. The code comntains the following call:-

gluNurbsSurface(m_pNurbsRenderer,l_N1,l_pKnots1,l_N2, l_pKnots2, l_K2*3, 3,l_pControlPoints ,UOrder,VOrder,GL_MAP2_VERTEX_3);

But we get the following error when the code is executed:-

“An OpenGL error has occured - Knot multiplicity greater than order of curve”

I’ve checked all the parameters and they all appear to be correct. both UOrder and VOrder are 4 and there are no more than 4 consecutive knots of the same value in either knot vector.

Does anyone know what is really causing the error and/or how to fix it ?

Probably, there are sort of a few problems going on here. Mathematically, there never needs to be more than the curve’s degree number of equal valued knots, though most computer implementations have incorrectly required or allowed the curve’s order number of equal valued knots at the ends (and only the ends) of the knot vectors. I don’t know how gluNurbsSurface() has been implemented, but probably the “wrong” way. Few people understand NURBS very well.

That’s probably not your problem, but probably leads up to it. On the interior of your knot vectors, you should not have more than the curve’s degree number of equal valued knots. In other words, you should not have more than three knots of the same value in the interior of either knot vector, given that both UOrder and VOrder are four. If so, the error message is wrong, because the real limit is the degree of the curve, not the order of the curve (except, due to incorrect implementation, at the ends). Given the probable screw up described in the first paragraph, and possible laziness on the gluNurbsSurface() programmer (not distinguishing the interior of knot vectors from the ends), could lead to an incorrectly worded error message that you received.

How to fix your problem? Make sure that your knot vector is non-decreasing and that you have no more than three equal-valued knots in the interior of your knot vectors. Also, make sure that you are taking into account the finite precision of the values in your knot vector: the knots are floats, which means they have only about five digits of significance. In other words, if you have a knot vector like this:
…, 1.0, 1.0, 1.0, 1.000001, …
then you really have four equal valued knots, because each of those four values is stored as a float identically to the others.

P.S. Despite what’s mathematically required, if gluNurbsSurface() was incorrectly implemented as it almost certainly was, then you must have however many knots in your knot vectors as it requires.

Hi

Thanks for your help. It was very informative, unfortunately the NURBS surface involved is being imported from a STEP AP203 CAD file so we don’t have the ability to change the original definition of the knot vectors.

We could possibly change the knot vectors as we import them but whatever we did to get this particular surface to render correctly we would need to condifident we could do in software to any other NURBS surfaces with the same problem.

If we were to remove any duplicate knots from the knot vectors I presume we would also have to remove coresponding control points as well. Is this correct ? If so how do we identify the correct control points to remove ?

Thanks again. Nigel

Since the STEP format specification is expensive and difficult to obtain (at least it was the last time I looked), I have not obtained a copy or studied how it defines the representation of NURBS curves and surfaces, though I have studied the IGES format specification extensively. As I understand, NURBS in most formats are stored suboptimally, i.e., with an extra knot at each end of the knot vectors. That’s a shame, because the only reason for NURBS to exist at all is because they are a compressed format for representing rational Bezier curves and surfaces.

Anyway, it is essential that your NURBS code be consistent with your NURBS data; if one is suboptimal, then both must be, if one is optimal, then both must be. For you to write general NURBS code, you have to detect and compensate for the differences.

NURBS are nothing more than a complicated way of representing a sequence of the much simpler rational Beziers, so that a few bytes might possibly be saved.

One of the purposes of the knot vector is to define the amount of redundancy removed from each junction of rational Beziers in the NURBS representation. When the knot multiplicity equals the NURBS degree, then the junction that knot multiplicity represents has had no redundancy removed. That is either because the degree of continuity is zero at that junction of rational Beziers, or because not all the redundancy was removed in defining the NURBS. When the knot multiplicity is one less the the degree of the NURBS curve, then one level of redundancy has been removed, and the junction represented by that knot multiplicity has a degree of continuity of one (which will be higher if not all the redundancy was removed). Etc. The redundancy I refer to has to do with the control points.

For example, in your case you said that the order of your NURBS surface is four in both dimensions. That means the degree is three, so each of the NURBS curves defining your NURBS surface consists of one or more cubic rational Bezier curves. Cubic Bezier curves require four control points each. The control points of Bezier curves define the derivatives of the Bezier curve at its endpoints. The degree of continuity at the junction of two Bezier curves is the number of derivatives at that junction that match. NURBS exploit the degree of continuity and the matching derivatives to remove redundant control points, which is reflected in the knot vector. The control points aren’t necessarily simply removed, though, instead several may be replaced with a set of the appropriate intermediate control points as defined by the de Castlejau algorithm.

That, incidentally, is a presentation on NURBS curves unlike any you are likely to see anywhere else. It seems nearly everyone else likes to talk about NURBS curves in terms of basis functions, even though basis functions actually have nothing to do with anything, though they do just happen to be true.

The point of me writing all that is to say that there isn’t a simple correspondence between the knots in a knot vector and the control points. Really, the only reasonable way to deal with interior knots is to convert a NURBS curve to its sequence of equivalent rational Bezier curves. Then you don’t have any knot vector at all, and life becomes easy. It’s easy to exactly convert a NURBS curve into an equivalent sequence of rational Bezier curves with the de Boor blossom algorithm. However, all of this requires that your NURBS curves are defined consistent with the way your NURBS evaluator works, and this gets back to the knot vectors you have.

In any case, if the NURBS curves are defined correctly (disregarding the ends of the knot vectors), and it is just a question of whether or not the ends of the knot vectors are defined optimally/consistent with the NURBS evaluator code, then all you need to know is how to determine whether there are the curve’s order or degree number of knots required at the ends of the vector. In an optimally defined NURBS curve, there are as many control points as the number of knots plus one minus the degree of the curve. If there are two more knots than that, then you can assume that the NURBS curve has been defined suboptimally and the first and last knot of the vector is mathematically unnecessary. The easiest way to write NURBS code that works universally is to write it for the optimal definition, and then determine whether the NURBS curve is consistent with that or not (as described by the relation I provided above). If the NURBS curve has been defined suboptimally, begin indexing the knot vector from its second element rather than from its first element.

On the other hand, if you have to live with code that requires suboptimal NURBS curves/surfaces, and your NURBS has been defined optimally, then you need to insert a dummy value at each end of each knot vector so that it will be consistent with the algorithm. The dummy knot values must still be reasonable, however, and that means that each must be a duplicate of the value it precedes (at the start) or follows (at the end).

I know all this sounds confusing. Believe it or not, one of the main attractions of Bezier curves is their simplicity (in every aspect). Sometimes people lose sight of the point of something and in a desire to improve it, just make it more complicated instead. That’s what NURBS are. Maybe in the days when disk storage cost thousands of dollars per megabyte, saving a few bytes at the expense of increased complexity made sense. Today, with sub $100 terabyte hard disks, NURBS have outlived their usefulness (if they ever really had any).

I need to assimulate the information a but you’ve given me a couple of ideasd on how to proceed. Thanks again for your help.

This topic was automatically closed 183 days after the last reply. New replies are no longer allowed.