Re: VisAD 3D surface graph performance

Hi Lezlie,

To give you some more background on Delaunay: it is actually not a single algorithm, but a term used to describe the optimal triangulation structure for a collection of points. VisAD includes three algorithms for generating Delaunay triangulations: DelaunayClarkson, originally written by Ken Clarkson in C as part of a program called hull; DelaunayWatson, originally written by Dave Watson in C as part of a program called nnsort; and DelaunayFast, written by me, which does not compute a true Delaunay triangulation, but rather an approximation using a divide and conquer scheme.

DelaunayClarkson operates in O(n log n) time on samples in N dimensions, but has a high overhead cost. DelaunayWatson operates in O(n^2) on samples in 2 or 3 dimensions, with a low overhead cost. DelaunayFast operates on samples in 2-D only. On my machine, DelaunayWatson is faster than DelaunayClarkson for ~3700 samples or less due to DelaunayClarkson's high overhead. The static Delaunay.factory method takes this into account in its heuristic, using DelaunayWatson for samples <= 3000, DelaunayClarkson for 3000 < samples <= 10000, and DelaunayFast for samples > 10000 (if the dimension is 2 and an exact triangulation is not required).

Actually, there is another Delaunay approximation algorithm for 2D data of a very specialized organization (overlapping grids) that I wrote called DelaunayOverlap, but to my knowledge it is not being used for anything.

You can try out the various Delaunay algorithms using the DelaunayTest class in the visad/examples directory. Run "java DelaunayTest" for a list of options.

I also second what Bill said about using DelaunayCustom. If you have any geometric knowledge of your samples' structure, it is often possible to compute your own triangulation more quickly or accurately than the included Delaunay algorithms could. If the triangulation you create is not perfect, you can even improve it by calling the Delaunay.improve method to perform a number of improvement passes (a greedy algorithm that performs edge flips to bring the triangulation closer to the optimal one).

Lastly, again along the lines of what Bill said, if your samples actually lie in a grid structure, even if the grid is twisted or uneven, as long as each grid box is convex, you can use a GriddedSet instead of an IrregularSet to greatly improve your performance.

-Curtis

Lezlie Fort wrote:

Hi Bill,

Thanks so much for your reply. I should preface my response by indicating my hope that you saw the second addendum message that I sent out. The number in my initial mail (380) referred to a single "group" of Depth parameters. There were 20 such groups in my data set, so the true number of points was 7600. But even that number is small compared to the 42000 that you mentioned in your first reply! I think that you nailed my problem, though, in your p.s. I am using the TextAdapter to read in my data files, and I looked at TextAdapter.java to see what was going on. Sure enough, based on my defined math type, it is creating an Irregular set using the Delaunay algorithm. I did some brief research online and found out that performance of Delaunay can be as high as O(n^2), so that helped me to understand what was happening. I read one post where someone was plotting over 100,000 points using the algorithm, and had to wait for over 8 hours for the calculations to complete. I read about other algorithms out there, but Delaunay seems to be one that is prevalent. I feel better just having an explanation for what I am seeing. If I have time, I might do a little more research into the Delaunay algorithm. One post suggested that a way to reduce performance time is to pre-sort one of the vectors involved in the calculations (the vector that is associated with the most dramatic changes in data values). They indicated that such a step could result in a performance savings of 25%. But, like I said, this is just cursory research.

At any rate, I have been very pleased with VisAD, and this is really the only issue that I've run into (although I've had a few questions along the way, as my recent posts will attest ;). And it's not really an issue, in the long run. For large data sets I can always plot 3D line graphs, which are extremely quick.

Thanks again!
lzf