Marlin: MBL: Mesh area lookup change will cause various problems

[epatel]

This commit https://github.com/MarlinFirmware/Marlin/commit/bc5a547d55722a87d41d2e4ee6ad32ed9db736ba change the MBL class methods select_x_index() and select_y_index().

Their intended use and implementation was to; from a XY position return indexes to which area a point belongs to (not to return the closest mesh point).

See image below, a 3x3 mesh containing 2x2 mesh areas. Point A and point B are on the same 00 area but will after the commit above be in different areas. A in 00 and B in 10 (select_x_index() will return 1 and not 0 for B https://github.com/thinkyhead/Marlin/blob/13175ce7da7a1cc260e923df3bf81f801fb6438d/Marlin/mesh_bed_leveling.h#L77)

The mesh Z height is calculated with a bi-linear method and uses the 4 corner points of an area to _interpolate_ the height. The above commit changes this so point B will now be _extrapolated_ from area 10. See image below. So its calculated height is not at B but rather B2

Then there is the issue about line splitting. Because MBL will make a non-linear compensation (meaning straight lines might not be straight anymore) a line splitting on mesh boundaries is required. These are calculated in the mesh_plan_buffer_line() function . See image below. Splitting a line between A and B at C.

Lines that uses select_x/y_index() in mesh_plan_buffer_line() https://github.com/MarlinFirmware/Marlin/blob/dee6322bf012c117f4fbb434aaf775ddaffc3334/Marlin/Marlin_main.cpp#L7206-L7209

But after the commit above we will see splitting of lines that are in the same area. See image below. Where there should be a straight line between A and B (no splitting) we will see a split and the new split point will be at C (_new x_ nx for the split point is taken from here https://github.com/MarlinFirmware/Marlin/blob/dee6322bf012c117f4fbb434aaf775ddaffc3334/Marlin/Marlin_main.cpp#L7222 and 3 other places depending on the which boundary is split on)

Above I have tried to show 2 problems introduced by that change in select_x/y_index(). The first affect might not be noticeable, specially if one have a very flat build plate or printing with thick first layers. The second might not be noticeable at first if one print small objects or one use a 2x2 mesh, the 2x2 mesh will clamp the indexes on these lines https://github.com/MarlinFirmware/Marlin/blob/dee6322bf012c117f4fbb434aaf775ddaffc3334/Marlin/Marlin_main.cpp#L7210-L7213

Two other problems I see.

The old method would also _extrapolate_ for points outside the mesh making the outside areas continue the slope from the inner part of the mesh outward. I think this behavior has also been broken i.e this line https://github.com/thinkyhead/Marlin/blob/13175ce7da7a1cc260e923df3bf81f801fb6438d/Marlin/mesh_bed_leveling.h#L79 and other parts, like the max edge of the mesh will experience strange behaviors I can't imagine as indexes will lookup wrong Z heights (due to array memory layout).

The change can also cause reading outside the mesh array, i.e this line https://github.com/thinkyhead/Marlin/blob/13175ce7da7a1cc260e923df3bf81f801fb6438d/Marlin/mesh_bed_leveling.h#L85 because select_x/y_index() now can return the index of the last point and thus the x_index + 1 and y_index + 1 (when reading from the z_values array) will cause reading beyond what was intended.

I strongly suggest reverting the changes to select_x/y_index()

[thinkyhead]

I see. Thank you for the clear and concise explanation. I suggest that there be two separate methods. One for the use of M421 (nearest grid line) and one for the use of your line-splitting routine (past the grid line). I will provide a PR with this specific change, which will cover all cases. (#3812)

[Roxy-3D]

One for the use of M421 (nearest grid line) and one for the use of your line-splitting routine (past the grid line). I will provide a PR with this specific change, which will cover all cases. (#3812)

Just to be clear: M421 isn't being changed in the Release Candidate, right?

[thinkyhead]

@Roxy-3DPrintBoard No. This would change nothing, but it would fix the functions that need a "cel index" versus those that need a "probe index." The bug was the result of my own standing confusion.

[Roxy-3D]

OK. Thanks! The reason I'm asking is I've extended the capability of M421 for the Unified Bed Leveling and I was hoping I wasn't going to have to re-think that part of things.

[jbrazio]

@epatel do you agree that PR #3812 closes this issue ?

[epatel]

@jbrazio Hard to say, have anyone tested it? Looked just now and I see that the PR have changed since last time I looked + he changed the method for calculation which I do not think will be identical. But hey, it might be close enough. And you know, the code is in so I guess we'll see.

[testing and verifying is hard because one need to cover as many edge cases as possible]

[epatel]

I have tried to lead by example with my latest PR which was tested by @brainscan and my next PR that today code wise was tested/verified by @WheresWaldo (I did also test some myself for this one)

[thinkyhead]

he changed the method for calculation which I do not think will be identical

Indeed, it is not identical, but nearly so. For a grid with probe line falling at X = 100, in the old code X<=100 would return a cel index of 0, while X>100 would return a cel index of 1. The new code will return cel index 0 for X<100, but index 1 for X>=100. The new code is actually "more correct" in this instance, but it's hardly any difference really. Only values nearly-equal to 100 are affected.

I ran the updated cel-index and probe-index functions through some loops to ensure correct output. My text editor helpfully allows me to compile and run snippets of C++ code. I also tested the time required, and the new methods do appear to be consistently faster than the old loop-based methods.

#include <iostream>
#include <math.h>
using namespace std;

#define constrain(v,l,h) ((v) < (l) ? (l) : (v) > (h) ? (h) : (v))

#define TEST_X 100
#define TEST_Y 100.001

#define MESH_MIN_X 10
#define MESH_MIN_Y 10
#define MESH_NUM_X_POINTS 3
#define MESH_NUM_Y_POINTS 3
#define MESH_X_DIST ((200 - MESH_MIN_X - MESH_MIN_X) / (MESH_NUM_X_POINTS - 1)) // 90
#define MESH_Y_DIST ((200 - MESH_MIN_Y - MESH_MIN_Y) / (MESH_NUM_Y_POINTS - 1)) // 90
#define FUDGE_FACTOR 0

float get_probe_x(int8_t i) { return MESH_MIN_X + (MESH_X_DIST) * i; }
float get_probe_y(int8_t i) { return MESH_MIN_Y + (MESH_Y_DIST) * i; }

int8_t old_cel_index_x(float x) {
  int8_t cx = 1;
  while (x > get_probe_x(cx) && cx < MESH_NUM_X_POINTS - 1) cx++;
  return cx - 1;
}

int8_t old_cel_index_y(float y) {
  int8_t cy = 1;
  while (y > get_probe_y(cy) && cy < MESH_NUM_Y_POINTS - 1) cy++;
  return cy - 1;
}

int8_t old_probe_index_x(float x) {
  for (int8_t px = MESH_NUM_X_POINTS; px--;)
    if (fabs(x - get_probe_x(px)) <= (MESH_X_DIST) / 2)
      return px;
  return -1;
}

int8_t old_probe_index_y(float y) {
  for (int8_t py = MESH_NUM_Y_POINTS; py--;)
    if (fabs(y - get_probe_y(py)) <= (MESH_Y_DIST) / 2)
      return py;
  return -1;
}

int8_t cel_index_x(float x) {
  int8_t cx = int(x + FUDGE_FACTOR - (MESH_MIN_X)) / (MESH_X_DIST);
  return constrain(cx, 0, (MESH_NUM_X_POINTS) - 2);
}

int8_t cel_index_y(float y) {
  int8_t cy = int(y + FUDGE_FACTOR - (MESH_MIN_Y)) / (MESH_Y_DIST);
  return constrain(cy, 0, MESH_NUM_Y_POINTS - 2);
}

int8_t probe_index_x(float x) {
  int8_t px = int(x + FUDGE_FACTOR - (MESH_MIN_X) + (MESH_X_DIST) / 2) / (MESH_X_DIST);
  return (px >= 0 && px < (MESH_NUM_X_POINTS)) ? px : -1;
}

int8_t probe_index_y(float y) {
  int8_t py = int(y + FUDGE_FACTOR - (MESH_MIN_Y) + (MESH_Y_DIST) / 2) / (MESH_Y_DIST);
  return (py >= 0 && py < (MESH_NUM_Y_POINTS)) ? py : -1;
}

int main(int argc, char const *argv[]) {

  cout << "      cel_index_x(" << TEST_X << ") is " << (int)cel_index_x(TEST_X) << endl;
  cout << "  old_cel_index_x(" << TEST_X << ") is " << (int)old_cel_index_x(TEST_X) << endl;
  cout << "    probe_index_x(" << TEST_X << ") is " << (int)probe_index_x(TEST_X) << endl;
  cout << "old_probe_index_x(" << TEST_X << ") is " << (int)old_probe_index_x(TEST_X) << endl;
  cout << "      cel_index_y(" << TEST_Y << ") is " << (int)cel_index_y(TEST_Y) << endl;
  cout << "  old_cel_index_y(" << TEST_Y << ") is " << (int)old_cel_index_y(TEST_Y) << endl;
  cout << "    probe_index_y(" << TEST_Y << ") is " << (int)probe_index_y(TEST_Y) << endl;
  cout << "old_probe_index_y(" << TEST_Y << ") is " << (int)old_probe_index_y(TEST_Y) << endl;

  long avg_total = 0;
  for (int i=100; i--;) {
    long t1 = clock();
    for (long q=400000; q--;) {
      float rnd = q % 90 + 100;
      volatile int test_x_index = old_cel_index_x(rnd);
      volatile int test_y_index = old_probe_index_y(rnd);
    }
    long t2 = clock();
    avg_total += (t2 - t1);
  }
  cout << "OLD Avg time " << (avg_total / 100) << endl;

  avg_total = 0;
  for (int i=100; i--;) {
    long t1 = clock();
    for (long q=400000; q--;) {
      float rnd = q % 90 + 100;
      volatile int test_x_index = cel_index_x(rnd);
      volatile int test_y_index = probe_index_y(rnd);
    }
    long t2 = clock();
    avg_total += (t2 - t1);
  }
  cout << "NEW Avg time " << (avg_total / 100) << endl;
}

[epatel]

Well actually, it is not about the calculation, maybe rather actually doing a separate one (changing the method).

About being on a grid line and what area that is, that should not matter as the bi-lin calc should boil down to the same line-interpolation.

So, why did I write it like that in the first place? The real reason is to use the same math/grid that is used for probing and sampling (calculating z values for compensation). By using get_x/y() as from the original, I am using the same source/numbers as when probing and in get_z() so all grid calculation get _synched_ and I believe any errors will then be canceled. By disconnect this and introduce a new calculation here I think things can get slightly skewed. Maybe not dangerous because slightly skewed in x/y, millimeters, should maybe affect Z very very very little (not dangerous). Still, when @Roxy-3DPrintBoard comes with her 15x15 grid things might scale up. And I really hope the errors is not accumulated anywhere.

@jbrazio You see what I mean?

The original code. No calculation, just using the same get_x() as used by other parts of MBL, thus syncing/aligning with them.

    int select_x_index(float x) {
      int i = 1;
      while (x > get_x(i) && i < MESH_NUM_X_POINTS - 1) i++;
      return i - 1;
    }

[epatel]

If one want speed I imagine get_x/y() could be translated into arrays that can be populated in the constructor of mbl...and select_x/y_index() could maybe be rewritten to a binsearch. But I would wait for that until it is shown to be needed.

[AnHardt]

About the inline-mania.
Almost all code for 'special functions' of the printer can be optimized for size, safety and readability, because it's used rarely. What matters is all the code used by a simple G1/G0 (input, parsing, planing, stepping, applying bed leveling, delta calculations) and what is done regularly (sensors, heaters, display). For homing, probing, filament changes, deep menu functions, saving EEPROM data, initializations, ... we can take as much time as it needs, because it does not really contribute to the time a print takes, or how fast we can print.

[epatel]

@AnHardt Funny you mention that https://github.com/MarlinFirmware/Marlin/pull/3835#discussion_r64647897

[thinkyhead]

About the inline-mania.

I'm happy to let the compiler decide in most cases. But Marlin seems to want the extra benefit from having the calc_timer function expanded in-place (and others as well, probably). I've been assuming that FORCE_INLINE will ensure this. But, is there no way al all, within GCC, to force inline expansion on a static class method now?

[jbrazio]

I read somewhere about gcc that even if you use FORCE_INLINE the compiler will take the ultimate decision to what to do thus despite the use of the word FORCE gcc can decide not to inline the function.

[thinkyhead]

@jbrazio Well, I went through the process with my various "static Singletons" PRs (#3922, #3923, #3924, #3925, #3926). I simply compared code size with and without inline and FORCE_INLINE specifiers. Some of the code did reduce in size, and some of it stayed the same. Of course, in no case did code size _increase_ by removing inline. Anyway, the Stepper, Endstops, and Temperature classes are the most important ones to keep optimized. So I have retained FORCE_INLINE in those places where removing it caused the code size to reduce.