next up previous
Next: Examples Up: Energy fairing Previous: Ranking number


The algorithm

We are now ready to summarize the previous developments to a complete automatic fairing algorithm which, of course, has the same structure as the algorithm of Farin and Sapidis already described:
  1. Compute the ranking numbers $z_i \; ; \; 0 \le i \le n \;$.
  2. Find $z_r = \max \{ z_i \; : \: 0 \le i \le n \} \;$.
  3. Compute the new location $\widetilde{\mbox{\bf d}}_r$ (resp. $\widetilde{\mbox{\bf d}}_r^{\; \ast}$ satisfying the $\delta $-distance constraint).
  4. If a suitable criterion to stop is fulfilled then exit else goto step 1.

There are only two interruptions possible in the present algorithm: either the number of iterations is restricted or the algorithm stops if the actual improvement $z_r$ is smaller than a certain amount. In the examples which we shall present afterwards, we have always limited the number of iterations. Please note that we cannot consider the increase of the global fairness criterion $E_l$ as a possible interruption since its decrease is ensured in every iteration step.

It is remarkable that the algorithm, as stated above, allows the modification of all control points. This might not be convenient if we are dealing with B-splines which itself are part of a composed spline curve. Thus we always exchange the expression $\;0 \le i \le n\;$ by $\;2 \le i \le n-2\;$ to achieve $C^1$-continuity between the original and the faired B-spline curve at the two end points. Similar arguments are valid for continuities of different order.

If the number of control points is large, a faster strategy to get a smooth curve is to determine a so-called ranking list by ordering all points according to their ranking number. Then this ranking list can be used as the computational order for the fairing algorithm. In most cases, it will be sufficient to use only the first quarter of the ranking list. Afterwards the ranking list should be rebuilt. This process is repeated $rank$_$repeat$-times whereby $rank$_$repeat$ is a variable which will be set individually for every example in the next subsection. Moreover we realized that it is further advantageous to limit the number each point can be changed during the algorithm. Doing so, a only local fairing effect due to the restrictions (23) is avoided.

Finally it should be remarked that the ranking list has to be calculated only in the first step for all points which can be changed. The reason is that the control point $\widetilde{\bf d}_r$ influences only the ranking numbers $z_i$ with the index $r - k + 1\le i \le r + k - 1$ and only these ranking numbers have to be recalculated in the next step.