[Octave-bug-tracker] [bug #55751] scatter3 performance regression bug in Octave 5.0.91

[Eddy]

Follow-up Comment #19, bug #55751 (project octave):

@Markus
Done some tests, and based on these observation, I tend to suggest include the
initial coplanar test. See attached file bug55751_inc_coplanar_v2.patch for
corresponding patch.

BTW, I forgot to turn off the check: facecolor_is ("none") && edgecolor_is
("none") in previous tests.

The (correct) time cost is:


                                   case 1,  case 2,  case 3,
scatter3 (no coplanar test)     :  0.095 s  0.095 s  0.097 s
__go_patch__ (+coplanar test)   :  0.094 s  0.227 s  0.225 s
coplanar split                  :  0.003 s  0.142 s  0.132 s
coplanar split + init full test :  0.003 s  0.145 s  0.003 s


Case 1: peaks (32).
Case 2: "2D Pseudo Quaterion Rotation Program", the ever-running one.
Case 3: coplanar point set. N = 45001; vecs=rand(N,2)*orth(rand(3,2))';

Test code of __go_patch__ (mimic implementation of scatter3):


  tic
  hax = newplot ();
  edgecolor = "r";  % trigger coplanar test, "none" to suppress.
  feval ('__go_patch__', hggroup (),
         "xdata", x, "ydata", y, "zdata", z,
         "facecolor", "none", "edgecolor", edgecolor,
         "faces", 1:numel (x), "vertices", [x, y, z],
         "marker", "o",
         "markeredgecolor", "none",
         "markerfacecolor", "b",
         "markersize", 3, "linestyle", "none");
  toc


So the impact of initial overall coplanar test is very minor, and the
improvement to coplanar input case is huge.

A more detailed time cost of different cases (test code below, time in table
below is only for the coplanar test C++ code):


with initial coplanar test
nc        4       5       10      20      50      1e6
random  : 1.974   2.297   2.818   3.107   3.307   3.391
coplanar: 1.157   0.919   0.492   0.263   0.139   0.067

no initial coplanar test
nc        4       5       10      20      50      1e6
random  : 1.193   1.585   2.396   2.806   3.118   3.227
coplanar: 1.115   1.478   2.185   2.605   2.779   2.830


nc: number of corners in a face, total number of vertex is 1e6.
random: random non-coplanar data.
coplanar: coplanar data.


# random
N = 1e6;
nc = 5;
vertices = rand(N, 3);
faces = 1:N;
faces = reshape (faces, nc, [])';
tic
hp = patch ('Vertices', vertices, 'Faces', faces);
toc

# coplanar
N = 1e6;
nc = 5;
vertices = rand(nc, 2) * orth(rand(3,2))';
faces = 1:nc;
faces = faces .* ones(N / nc, 1);
tic
hp = patch ('Vertices', vertices, 'Faces', faces);
toc


This time table provide information that when should we disable the overall
coplanar test. i.e. it should be disabled if nc == 4, otherwise the test
should be beneficial on average, assuming more than half cases are coplanar.

The attached file bug55751_inc_coplanar_v2_timing.diff is what I used for the
timing measure of coplanar test/face splitting. Apply after the patch.

Further speed up might be possilbe, such as use "rcond" for rank test, instead
of "eig". I didn't try it.

Appendix:

Here is some addtional background math in case someone (or me, in the future)
want to fully understand the algorithm and fine tune it.

Suppose [x y z] are always in a plane:
  a x + b y + c z + d = 0
To find {a,b,c,d}, we can minimize the variance of "epsilon" in 
  a x + b y + c z + d = epsilon
i.e
   min epsilon' * epsilon
 = min [a b c d] * [x y z ones()]' * [x y z ones()] * [a b c d]'
Let coor_cov = [x y z ones()]' * [x y z ones()], this is equivalant to
solve the minimum eigenvalue of coor_cov, which equals to min n*var(epsilon),
eigenvector is [a b c d]'. n is the number of points, e.g. length(x).

To avoid the extra "ones()", one need to fit a plane without constant term
  a*(x-mx) + b*(y-my) + c*(z-mz) = 0
where the pivot [mx my mz] = mean([x y z]), then follow the same analysis.
Alternatively, [mx my mz] can be other point (presumably) in the plane,
although different choice introduce diffence bias. Usually "mean([x y z])"
been the most "fair" one.
Other eigenvalues indicate the spreading of the points in other dimensions in
the plane.


(file #46498, file #46499)
    _______________________________________________________

Additional Item Attachment:

File name: bug55751_inc_coplanar_v2.patch Size:6 KB
   
<https://savannah.gnu.org/file/bug55751_inc_coplanar_v2.patch?file_id=46498>

File name: bug55751_inc_coplanar_v2_timing.diff Size:1 KB
   
<https://savannah.gnu.org/file/bug55751_inc_coplanar_v2_timing.diff?file_id=46499>



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?55751>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/