B-Splines: Difference between revisions

From FreeCAD Documentation
(→‎Math: typo)
(→‎Basics: cleanup)
Line 85: Line 85:
=== Basics ===
=== Basics ===


[https://www.youtube.com/watch?v=bE1MrrqBAl8 This video] lists at the beginning the practical problems with Bézier curves. For example that adding or changing a control point changes the whole curve. These problems can be resolved by joining several Bézier curves. The result is a so-called spline, in particular a B-spline (base spline). The video also explains that a union of quadratic Bézier curves form a uniform quadratic B-spline and that a union of cubic Bézier curves form a uniform cubic B-spline.
If you are interested in more details how a B-Spline is derived from Bézier curves, have a look at these nice explanation videos: [https://www.youtube.com/watch?v=bE1MrrqBAl8 this] and [https://www.youtube.com/watch?v=xXJylM2S72s this].


From the videos we can collect useful "rules" for B-splines:
The first video lists at the beginning the practical problems with Bézier curves. For example that adding or changing a control point changes the whole curve. These problems can be resolved by joining several Bézier curves. The result is a so-called spline, in particular a B-spline (base spline). The first video also explains that a union of quadratic Bézier curves form a uniform quadratic B-spline and that a union of cubic Bézier curves form a uniform cubic B-spline.

From the videos we can also collect useful "rules" for B-splines:
* The first and last control point is the end/start point of the spline.
* The first and last control point is the end/start point of the spline.
* Like for Bézier curves, splines always begins tangentially to the line between the startpoint and the first control point (and ends tangentially to the line between the last control point and the endpoint).
* Like for Bézier curves, splines always begin tangentially to the line between the startpoint and the first control point (and end tangentially to the line between the last control point and the endpoint).
* A union of <math>S</math> Bézier curves with the degree <math>D</math> has needs <math>S+D</math> control points.
* A union of <math>S</math> Bézier curves with the degree <math>D</math> has <math>S+D</math> control points.
** Since one is in most cases working with cubic B-splines we can then state that <math>N</math> control points leads to <math>N-3</math> spline segments and in turn <math>N-4</math> segment junction points.
** Since one is in most cases working with cubic B-splines we can then state that <math>N</math> control points lead to <math>N-3</math> Bézier segments and in turn <math>N-4</math> segment junction points.
* A B-spline with the degree <math>D</math> offers at every point a continuous <math>D-1</math> order derivative.
* A B-spline with the degree <math>D</math> offers at every point a continuous <math>D-1</math> order derivative.
** For a cubic B-spline this means that the curvature (second order derivative) of the curve does not change when traveling from one segment to the next one. This is a very useful feature as we will later see.
** For a cubic B-spline this means that the curvature (second order derivative) does not change when traveling from one segment to the next one. This is a very useful feature as we will later see.

If you are interested in more details about B-Spline properties, have a look at [https://www.youtube.com/watch?v=xXJylM2S72s this video].


=== Basis ===
=== Basis ===

Revision as of 02:52, 8 March 2021

This documentation is a work in progress. Please don't mark it as translatable since it will change in the next hours and days.

This page describes how to use B-splines in FreeCAD. It gives also background information what B-splines are and for what applications they are useful.

Motivation

If you know already about B-splines and their application, you can directly continue with section B-splines in FreeCAD.

Let's assume you want to design a part that should be produced with a 3D printer. The part must have an edge this way:

You have to print the part in direction of the sketch's bottom to the top. Outer support structures might not be an option. Therefore you need to add a support directly to your part. What options do you have?

  • Option 1: you could add a line from point (20, 0) to point (80, 40):

However this solution needs a lot of volume, thus weight and material.

  • Option 2: you can connect the two points with an arc of a circle. To save volume, the arc should end tangentially in point (80,40). Then your solution looks like this:

OK. But at the bottom you don't need immediate support.

  • Option 3: you could save some more volume if the connection between the 2 points is a curve that begins tangentially at (0, 20) and ends tangentially at (80, 40):

So a curve with which you can connect two points tangentially to a reference point can be very useful for constructions. Bézier curves provide this feature.

Bézier curves

Derivation

Bézier curves are polynomials to describe the connection between 2 points. The simplest polynomial connecting 2 points is a line () thus also linear Bézier curves are linear:

Animation 1: Linear Bézier curve.

However a polynomial becomes first be useful when we can control it. So there should be a point between the 2 endpoints that allows us to define how the endpoints are connected. Like in the above example option 3 the curve is helpful when it starts and ends tangentially to lines crossing the endpoints. And this is a main feature of Bézier curves. So let's add a control point between the 2 endpoints. The curve will start tangentially towards this control point, meaning it is tangential to the line that we can draw between the startpoint and the control point. Going backwards from the endpoint the curve will also be tangential to the line we can draw between the control point and the end point. Animation 2 shows how such a curve looks.

Animation 2: Quadratic Bézier curve. P1 is hereby the control point.

The animation makes clear what the curve basically is - a transition from P0 to P2 by rotating the line P0-P1 to become the line P1-P2. Therefore we get the nice tangential start/end feature.

Such a curve can only be described by a quadratic polynomial. (The number of left-hand/right-hand turns + 1 is the necessary polynomial order. A quadratic polynomial is a single turn, a cubic polynomial is a combination of a left-hand and right-hand turn, and so on.) Therefore a Bézier curve with one control point is a quadratic (second order) Bézier curve.

Having only control point is often not sufficient. Take the above motivation example. There in option 3 we end the curve tangentially in x-direction. But how can you connect the points (20, 0) and (80, 40) so that the curve ends tangentially in y-direction? To achieve this you need first a right-hand and then a left-hand turn, so a cubic (third order) polynomial. And that means for a Bézier curve that we need (or you can say we gain) a second control point. Animation 3 shows a cubic Bézier curve.

Animation 3: Cubic Bézier curve.

To answer the question, the solution with the tangential y-direction ending for the example is this one:

Math

If you are interested to understand the background math, here are the basics.

A Bézier curve is calculated using this formula:

n is hereby the degree of the curve. So a Bézier curve of degree n is a polygon with order n. The factors are hereby in fact the coordinates of the Bézier curves' control points. For a visualization see this page.

If you are further interested, have a look at this website with a nicely animated derivation of the math of Bézier curves.

Rules

In the above derivation you might already noticed some "rules" for Bézier curves:

  • The polynomial degree is also the degree of the curves.
  • If you need turns, you need at least a degree Bézier curve.
  • A Bézier curve always begins tangentially to the line between the startpoint and the first control point (and ends tangentially to the line between the last control point and the endpoint).

B-Splines

Basics

This video lists at the beginning the practical problems with Bézier curves. For example that adding or changing a control point changes the whole curve. These problems can be resolved by joining several Bézier curves. The result is a so-called spline, in particular a B-spline (base spline). The video also explains that a union of quadratic Bézier curves form a uniform quadratic B-spline and that a union of cubic Bézier curves form a uniform cubic B-spline.

From the videos we can collect useful "rules" for B-splines:

  • The first and last control point is the end/start point of the spline.
  • Like for Bézier curves, splines always begin tangentially to the line between the startpoint and the first control point (and end tangentially to the line between the last control point and the endpoint).
  • A union of Bézier curves with the degree has control points.
    • Since one is in most cases working with cubic B-splines we can then state that control points lead to Bézier segments and in turn segment junction points.
  • A B-spline with the degree offers at every point a continuous order derivative.
    • For a cubic B-spline this means that the curvature (second order derivative) does not change when traveling from one segment to the next one. This is a very useful feature as we will later see.

If you are interested in more details about B-Spline properties, have a look at this video.

Basis

The name B-spline stands for Basis spline. Instead of forming the spline as a combination of Bézier curves, the approach is to to model the same spline a different way. The idea is hereby to use a set of polynomial as basis. A linear combination of these basis polynomials with the order form the B-spline. This video explains the transition from the Bézier control points to the polynomial basis functions to describe the spline. Mathematically we can write that a B-spline can be describe with this formula:

Hereby is the -th control point of the B-spline and also a factor for the -th base polynomial . Every basis polynomial describe the spline in a certain region and therefore moving a control point does not affect the whole spline. Tho understand this, it is highly recommended to have a look at this video starting at minute 2:23.

As explained in the video the basis polynomials are Bernstein polynomials. The set of basis polynomials for a certain B-spline can be visualized this way:

A set of Bernstein polynomials with order 4. They describe a 4th order B-spline with 5 control points.

At every spline position the sum of polynomials is 1 (indicated by the orange line). At the start only the red polynomial has an influence since all other polynomials are there 0. At greater the spline is described by a linear combinations of different basis polynomials. In the image above, every polynomial is greater than 1 for the whole range . This is not necessarily the case. As shown in the video, the basis polynomials are basically only greater than 0 for a part of the spline position. The interval at which a basis polynomial is greater than 0 is described by the knot vector. If you are interested in learning about the knot vector, have a look at this video.

Non-uniform B-splines

A property of the Bernstein polynomials is that when one takes the resulting B-spline and takes a look at its different Bézier parts, the path length of every part is the same. (the path length id often called the travel time). As you can imagine, it can be useful to have B-splines whose Bézier parts have different path length. This can be achieved by weighting the different control points:

is hereby the weight of the -th control point. When not all weights are equal, the B-spline is called non-uniform.

Especially when B-splines should be used for 3D modelling, normalized non-uniform B-splines are necessary. Therefore the weighted spline is divided by weighted basis to get the normalization that when all are equal, we get a a uniform B-spline, independent on the weight itself:

These B-splines are non-uniform rational B-splines, often called NURBS. Looking at their formula, we can see that we in fact have a B-spline with a weighted basis :

whereas

B-splines in FreeCAD

FreeCAD offers to create uniform or non-uniform B-splines of any degree in 2D via the Sketcher workbench.

Creation

To create B-splines, go into a sketch ans use the toolbar button Create B-spline. Then left-click to set a control point, move the mouse left-click to set the next control point and so on. Finally right-click to finish the definition and create the B-spline.

By default uniform cubic splines are created, except there are not enough control points to do this. So when you create a B-spline with only 2 control point, you get of course a spline that is single linear Bézier curve, for 3 control points you get a quadratic Bézier curve, first with 5 control points you get a cubic B-spline consisting of 2 Bézier segments.

To create periodic B-splines (B-splines that form a closed curve), use the toolbar button Periodic B-spline. It is not necessary onto set the last control point to the first one because the B-spline will automatically be closed:

B-splines can also be generated out of existing sketch segments. To do this, select the elements and press the the toolbar button Convert Geometry to B-spline.

Changing the Degree

Tho change the spline degree, select the B-spline and use either the toolbar button Increase B-spline degree or Decrease B-spline degree.

Note: decreasing the degree cannot revert a prior increase of the degree, see the Wiki page Decrease B-spline degree for an explanation.

Changing the Knot Multiplicity

The points where two Bézier curves are connected to form the B-spline are called knots. The knot multiplicity determines how the Bézier parts are connected, see the Wiki page Increase knot multiplicity for details.

To change the knot multiplicity, use the toolbar buttons B-spline increase knot multiplicity or B-spline decrease knot multiplicity.

Note: Creating 2 B-Splines that are connected to each other will not unite to a single new B-spline. So their connection point is not a knot. The only way to get a new knot in an existing B-spline is to decreae the degree of the B-spline. However, you may get tons of new knots, thus the better choice is to redraw the B-spline.

Changing the Weight

Around every control point you see a dark yellow circle. Its radius sets the weight for the corresponding control point. By default all circles have the radius 1. This is indicated with a dimension constraint for the first control point circle.

To create a non-uniform B-spline the weights have to be non-uniform. To achieve that you can either change the radius of the first control point circle:

File:Sketcher Changing-control-point-weigth-constraint.gif

or you delete the constraint that all circles are equal and then set a radius constraint for the circles.

You can also change the radius by dragging:

In the dragging example you can see that a high weight attracts the curve to the control point while a very low weight changes the curve so as if the control point does almost not exist.

When you look at the creation function for non-uniform rational B-splines you see that a weight of zero would lead to a division by zero. Therefore you can only specify weights greater than zero.

Display Information

Since the form of a B-spline does not tell much about its properties, FreeCAD offers different tools to display the properties:

Property Toolbar button
Degree Show/Hide B-spline degree
Control polygon Show/hide B-spline control polygon
Curvature comb Show/hide B-spline curvature comb
Knot multiplicity Show/hide B-spline knot multiplicity
Weights Show/hide B-spline control point weight