Re: hidden3d very slow in gnuplot 3.8k

On Wed, 31 Mar 2004, Glyn Edwards wrote:

> Hi, I have been plotting some data I have that has a large number of
> points say 500x300. I have noticed that this is considerably slower in
> gnuplot 3.8 that 3.7.3, so much so that i have reverted back to the
> previous version. Has anyone else come across this?

The root of this problem is 500x300 is a rather excessive number of 
points to plot as a wireframe mesh.  You'll want to build gnuplot with
the undocumented flag -DTEST_QUADTREE=1 in this case.

The basic problem is that a hidden-line removal algorithm in a setting
like gnuplot's terminal API, which cannot rely on erasing any portion of a
line after it has been drawn, has an unescaple worst-case behaviour of
O(N^2) for input size N (number of points, polygons or edges), and
gnuplot's hidden3d code in default compilation will even have an expected
O(N^2).  It essentially tests every edge in the mesh against every
triangle.  That'll be a small factor times (2*2*500x300)^2 = 3.6e11 tests,
which _will_ take rather a lot of time, even with the highly optimized way
the tests are done.

-- 
Hans-Bernhard Broeker (br...@ph...)
Even if all the snow were burnt, ashes would remain.