ErikZalm/Marlin — pull request #673 by fsantini (2013-12-06 21:03:22+00:00)
Title: Improvements to the auto bed leveling feature

The auto bed leveling feature is very useful and works well. However, I see the usage of just three points and an exact solution a shortcoming of the method, as it lacks in robustness in case of non perfectly flat bed or other probing errors. Moreover, I found some small inaccuracies in the original code.

This patch optimizes the original method by using a more direct solution for the calculation of the rotation matrix, only relying on the plane normal. Moreover, the matrix being a pure rotation and therefore orthogonal, it doesn't require the inversion as inverse == transpose. Calculating the transpose is faster, easier and more robust.

The second part of the patch introduces a more accurate method of probing the bed. By defining ACCURATE_BED_LEVELING in Configuration.h, the bed is probed on a grid (NxN) of equally spaced points between the original probe limits. The plane equation is solved by a linear least squares method, thus averaging out possible errors. This optional feature, when enabled, adds almost exactly 10kB to the binary.

The LSQ solver is taken from http://people.sc.fsu.edu/~%20jburkardt/c_src/qr_solve/qr_solve.html and originally released under LGPL, therefore compatible with Marlin GPL.

Please note that since the grid coordinates are known at compile time, the solver could be replaced by a precalculated Moore-Penrose preudoinverse or SVD pseudoinverse, but this would mean that the compilation cannot be done only in the Arduino environment, for this reason I decided to add the solver directly in the code.