Sketcher: Bezier curves

[DeepSOIC]

Recently, I've been thinking quite a lot about introducing Bezier curves and B-splines into sketcher. B-splines are a bit too complex, so I think it's better to start with Beziers.

I have not started any coding so far, and I'm not sure I will any time soon, I just want to share the thoughts.

Design goals:
1. Support high-degree Beziers (up to OCC's maximum of 25)
2. Support for insertion and removal of control points (aka poles)
3. Support for point-on-curve and tangent/perp./angle-via-point. And, coincident for endpoints and control points, of course.
4. Support constraining points to self-intersections.
5. (not essential) Trimmed Bezier support.

Here are a few challenges.
challenge 1. Control points
As some may know, Sketcher code supports only three points per object: start point, and point, middle point. That means, there can be only three points on the screen being part of Bezier, which is really not acceptable.

I see at least two ways of adding the control points:
1. Using internal alignment constraints, the necessary points will be constrained to the Bezier.
There are a few disadvantages of the approach:
- a lot of bloat in constraint list and element list
- the control points are not visually distinguishable
- potentially slow because of the bloat: lots of constraints means larger matrix to analyze (not solve?), and lots of geometry (points) to copy around (which is done a lot there)
2. Extending Sketcher code to support the control points. E.g. positive values of pointpos are the usual start/end/middle, but negative values are index of control point.
+ minimal bloat
- elements widget will need a rework
+ control points can be rendered differently, becoming visually obvious.

challenge 2. Point-on-curve constraint
I have thought about it a bit, and I think that the constraint has to be different from the existing by that it should keep track of the parameter value associated with the point. This is because I'm unable to formulate an error function for the regular constraint, and I believe even if it is possible to formulate such a function, the constraint will behave extremely poor if the Bezier has self-intersections. Moreover, knowing the t parameter of the point allows easy computation of tangent and normal vectors, required for angle, tangent and perpendicular constraints.

Again, I see two ways of implementing it:
1. introduce new type of point - a point that is forever stuck on a curve, and knows its t value.
+ point knows its t -> easy to calculate tangent/normal.
+ the points can be used to set trim to the curve
- confusion for users
2. introduce a new type of point-on-curve constraint - a datum version of one. This path requires to implement measurement constraints (the constraint that computes its value, rather than enforcing it). I know there are a few requests for this already on the forum, and it seems to be a good excuse for actually fulfilling the requests.
- finding out point's t requires linkage to the constraint -> tricky code.
- tricky code to trim the curve
+ fits well into existing workflow
+ bonus - measurement constraints
+ ability to fix t is valuable itself -> new feature for existing shapes

That's it so far Any ideas? Comments? Opinions?

[ulrich1a]

All my understanding of Bezier curves is, that those are polynomes with a max degree of 3. (Correct me, if I am wrong.) Polynomes itself should not be that difficult. The trap is, Bezier curves end at a special values, whereas the polynome definition does not end at these values. All I know about constraints in sketcher, is that the constraints are valid for the whole definition range of that function. Defining any constraint for a Bezier curve must cover now the discontinuities in the definition of the Bezier curve. (If clauses in the derivates?) This is tough.

Ulrich

[DeepSOIC]

that those are polynomes with a max degree of 3. (Correct me, if I am wrong.)

No. http://en.wikipedia.org/wiki/B%C3%A9zier_curve
The degree can be anything. It is just common that cubic Beziers are the only available (in graphics editors, for example). And no, Beziers do pass through their endpoints (not control points). B-splines, however, generally don't.

[wmayer]

The degree can be anything. It is just common that cubic Beziers are the only available (in graphics editors, for example).

Not related to sketcher -- but when you compute a Bezier/B-spline curve/surface to approximate a set of points you usually limit the degree because otherwise the curve/surface may oscillate heavily. Also some file formats like SVG support Beziers to a degree up to 3. In case you have a Bezier curve of a higher degree you must re-approximate it with a set of Bezier curves of degree of 3 which results in a certain loss of accuracy.

B-splines, however, generally don't.

Theoretically correct but practically you usually choose a multiplicity of first and last knot that the curve goes through its first and last control point, too. This way you can easily achieve a tangency between two connected curves, you just have to make sure that:
* the last control point is coincident with the first control point of the second curve
* the second control point of the second curve is collinear to last and second last control points of the first curve

Recently, I've been thinking quite a lot about introducing Bezier curves and B-splines into sketcher. B-splines are a bit too complex, so I think it's better to start with Beziers.

B-splines are a generalization* of Bezier curves and since B-splines will be added anyway so why doing something special for Bezier curves.

As some may know, Sketcher code supports only three points per object: start point, and point, middle point. That means, there can be only three points on the screen being part of Bezier, which is really not acceptable.

Actually instead of adding a Bezier/B-spline curve as a single entity to the solver you can work with its control polygon. This way the three point categories are sufficient. However, when it comes point-on-curve constraints or the like I don't know how far you come.

Also, I wonder whether we should support rational Bezier/B-spline curves.


*) A B-spline degenerates to a Bezier curve when it has a knot vector of the form [0,..,0, 1, ..., 1].

[wmayer]

See also the related Mantis ticket: http://www.freecadweb.org/tracker/view.php?id=940

[DeepSOIC]

Thanks Werner for explanations!
Full support of B-splines is a tricky business because I don't know how to set up user interface for controlling degrees, weights, knots and multiplicities (and I don't even have good knowledge of what they do). I would like to keep things simple, that's why Beziers. They are MUCH simpler since the set of control points is enough to fully define it (I want to drop weights, i.e. rational Beziers, for the same reason of simplicity).

Speaking otherwise, I'm not ready for coding B-spline support.

[shoogen]

Full support of B-splines is a tricky business because I don't know how to set up user interface for controlling degrees, weights, knots and multiplicities (and I don't even have good knowledge of what they do).

I got some ideas:
Degree: I a natural number. -> A numerical constrain. (visualized by the local continuity, see below)
Weights: Color of a control point or circle around a control point, (or the length of the colored segment between the pole and knot markers on the curve. There would be one line per knot affected by the pole (thus indicating the multiplicity)
knots/mutiplciites: Knots as points on the curve. If they are not evenly distributes they should have their numerical value visible. If they are only the first and last should show the numerical value. (Unless they are 0 and 1).
These knot indecators could be color coded to indicate the local continuity (degree - multiplicity) Black (-1), Red (0), Yellow (1), Green (2), Blue (3), purple (>=3). A continuity of -1 can only appear on the endpoints. A continuity of C0 breaks certain algorithms in OCCT . Therefore the BSpline should be split into multiple edges. (Not necessarily for the sketcher itself, but with respect to the created shape)
A BSpline representing a piecewise bezier multiplicities:[deg+1,deg,...,deg,deg+1] would have black knot markers at the end and Red ones along the curve.
A quasi-uniform cubic BSpline multiplicities:[4,1,...,1,4] would have green (2) knot indicators on the inside.
A quasi-uniform quadractic BSpline multiplicites:[3,1,..,1,3] would have yellow (1) knot indicators on the inside.
A polyline (quasi-uniform linear BSpline multiplicities:[2,1,...,1,2]) would have red (0) knot indicators on the inside.

What we should support is periodic BSplines

[DeepSOIC]

OK, thanks to your input, I have a new concept born: piecewise assembly of splines in Sketcher
The tools:
* a plain* polynomial (Bezier?) piece with settable degree n (=> n+1 control points => 2*(n+1) DOFs)
* a plain rational polynomial piece (2*(n+1)+n DOFs)
* a continuity constraint that joins two polynomial pieces and has a settable continuity (c=0 = coincident, C=1 - tangent, C>1 - no equivalent so far).
* a hide/restore internal geometry to reveal individual control points
* a special constraint to set weights explicitly
The good:
+ Easy to implement (not much math required - most of the tricky stuff is handled by sketcher solver).
+ A bit easier to understand for someone not familiar with splines (no need to understand what are multiplicity, control points, weights, to start working and utilize full power).
+ no need to extend sketcher points
+ inherent support for periodic splines (requires no coding at all)
The bad:
- extreme bloat and performance penalty for big splines
- point-on-curve will be unable to jump between segments (trace the whole spline).
- tricky code in links to external geometry

*) by plain, I mean minimalistic: no control points are exposed; only start point, end point and the curve are exposed to the user.
blue=edits

[abdullah]

Any work done ?

[wmayer]

I would only go for B-Spline curves and completely ignore Bezier curves because:
* as mentioned above a B-Spline with the knot vector [0,...,0, 1, ...,1] where the multiplicity of the 0's and 1's is degree + 1 is also a Bezier curve
* a Bezier curve has the bad behaviour that when you change one of its control points the whole curve changes and this makes it hard to predict how the shape will change. A general B-Spline curve doesn't suffer from this problem because only the local segment will change its form.

Any work done ?

Not yet. However, when we started with the first draft of the sketcher I implemented a few things. Parts of the code should be still there.