extract arc/circle definition from bspline

Question

I must decode STEP cad file in which a 3d circle can be defined as a spline. I want being able to decode that the spline is an arc or a circle.

At first I have the step B_SPLINE_CURVE_WITH_KNOTS element.

 #307 = B_SPLINE_CURVE_WITH_KNOTS ( 'NONE', 3,( #114, #212, #179, #317, #91, #191, #141, #97, #150, #63, #121, #243, #75, #43, #15, #164, #315, #284, #302, #70, #269, #251, #151, #220, #178, #172, #248, #185, #156, #249, #300, #47, #124, #335, #360, #59, #357, #343, #12, #5, #112, #324, #344, #193, #329, #320, #313, #222, #51, #167, #286, #268, #310, #32, #267, #52, #66, #69 ),.UNSPECIFIED., .T., .F., ( 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4 ), ( 0.0000000000000000000, 0.0003907630664662950000, 0.0007815261329325900100, 0.001172289199398885000, 0.001563052265865180000, 0.002344578398797811600, 0.003126104531730443300, 0.003516867598196761600, 0.003907630664663080300, 0.004298393731129399400, 0.004689156797595717700, 0.005079919864062035900, 0.005470682930528354200, 0.005861445996994673300, 0.006252209063460992400, 0.006642972129927311600, 0.007033735196393629000, 0.007815261329326231600, 0.008206024395792531700, 0.008596787462258833500, 0.008987550528725133500, 0.009378313595191433600, 0.009769076661657735300, 0.01015983972812403500, 0.01055060279459033500, 0.01094136586105663500, 0.01133212892752293700, 0.01172289199398923700, 0.01250441812692185600 ), .UNSPECIFIED. ) ;

So if I am right, I decoded :
58 control points
29 knot_multiciplities
29 knots
degree 3
closed_curve argument = True

now, the idea would be to convert it to beziers curve in order to find arc/circles, but I am stuck in front of these parameters.

Answer 1

You can work out the arc through 3 consecutive knots. If the arc is constant for all the triples of your bspline, the curve is an arc itself.

Answer 2

An arc or a full circle cannot be exactly represented by an integral B-spline curve. So, if you are sure the B-spline curve in the STEP file is not rational, then it only represents an arc or a full circle approximately. If this is the case, you can do the following:

• Sample some points on the B-spline curve,
  
• Do a least square fit against the sampled points to obtain the best-fit circle and the deviation associated with each sampled point.
  
• If the max deviation is smaller than a certain threshold, then you get your circle/arc. Otherwise, this B-spline curve is not a circle/arc.
  

This approach will work regardless whether you have a rational or integral B-spline curve.

Answer 3

The main problem at first is the understanding of the STEP BSPLINE_CURVE_WITH_KNOTS definition :

knot_multicplicites = ( 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4 )

knots = ( 0.0000000000000000000, 0.0003907630664662950000, 0.0007815261329325900100, 0.001172289199398885000, 0.001563052265865180000, 0.002344578398797811600, 0.003126104531730443300, 0.003516867598196761600, 0.003907630664663080300, 0.004298393731129399400, 0.004689156797595717700, 0.005079919864062035900, 0.005470682930528354200, 0.005861445996994673300, 0.006252209063460992400, 0.006642972129927311600, 0.007033735196393629000, 0.007815261329326231600, 0.008206024395792531700, 0.008596787462258833500, 0.008987550528725133500, 0.009378313595191433600, 0.009769076661657735300, 0.01015983972812403500, 0.01055060279459033500, 0.01094136586105663500, 0.01133212892752293700, 0.01172289199398923700, 0.01250441812692185600 )

I suppose that means knots must be decoded as :

(0.000000000000000000,0.000000000000000000,0.000000000000000000,0.000000000000000000 , 0.0003907630664662950000, 0.0003907630664662950000, 0.0007815261329325900100, 0.0007815261329325900100 ....

But what worries me is that the multiplicity (4) is greater than the degree : 3 ! .

Answer 4

Each interior knot has multiplicity = 2. This means that the spline is C_1, and is tangent to the legs of the control polygon. Specifically, if t[i-1], t[i] and t[i+1} are three knots, each with multiplicity = 2, then the spline is tangent to a control polygon leg at a point that divides the leg in the ratio
t[i+1] - t[i] : t[i] - t[i-1] . In the picture below, these tangency points are shown as hollow circles, and the red circles are control points:

In fact, in your particular example, the inter-knot spacing is uniform, for the most part -- there are many cases where t[i+1] - t[i] = t[i] - t[i-1] = 0.000391. This means there are many places where the spline is tangent to a leg of the control polygon at it's mid-point.

Using the control points and tangency points, you can calculate the end-points (P and Q) and the unit-length end tangents (U and V). of each cubic segment

A little trigonometry and vector arithmetic will then give you the radius and center of the corresponding circle. Example pseudo-code is as follows. It assumes some obvious vector functions, and it avoids use of trig functions:

// Input:
// P: start point
// Q: end point
// U: start tangent (assumed to be of unit length)
// V: end   tangent (assumed to be of unit length)

Vector C = Q - P;    // chord vector

// Test that tangent vectors make same angle with chord
double UdotC = U*C;      
double VdotC = V*C;         
double epsilon = some small number, say around 0.000001;
if (Math.Abs(UdotC - VdotC) > epsilon) throw;  // Tangents not symmetric

// Test that tangents and chord are coplanar
Vector UcrossC = Vector.Cross(U, C);  
double det = V*UcrossC;
if (det > epsilon) throw;   // Tangents and chord not coplanar

double CdotC = C*C;
double radius = 0.5 * CdotC / Vector.Norm(UcrossC);

double c2 = (UdotC*UdotC)/CdotC;
Vector dW = 0.25*(UdotC/(1-c2))*(V - U);
Position center = P + 0.5*C + dW;

If the circles you create this way have equal centers and radii (to within some reasonable tolerance), then it's fairly safe to assume that the "intent" of the spline is a circle.

I think that using points and tangents in this way is better than fitting circles to arbitrary points on the spline. There is a very good chance that the code in the sending system constructed the spline by so-called "Hermite" methods (using points and tangents). If this is the case, it's likely that the points and tangents calculated as above will exactly match those of the original circle (if there is one). Arbitrarily calculated points on the spline will not lie exactly on the original circle, so you'll run into a lot more tolerance problems.