search

lime-rt / lime

Line Modeling Engine
http://www.nbi.dk/~brinch/index.php?page=lime
Other
25 stars 25 forks source link

Parallel Delaunay Triangulation #238

Open marc-evans opened 7 years ago

marc-evans commented 7 years ago

When building a grid using lots of points, which is especially necessary to produce accurate images of complex geometries, the Delaunay triangulation is a large bottleneck in the smoothing process. Can the Delaunay triangulation be parallelised like the non-LTE level population calculation and raytracing? I understand this is a difficult problem because a point may affect the entire triangulation, but I believe a partitioning method can be used- unfortunately that's the extent of my expertise here.

tlunttil commented 7 years ago

paging (and pestering...) @allegroLeiden

@lolMEvans : You could try using par->samplingAlgorithm=1, which won't do any smoothing at all. Anyway, the default sampling algorithm uses 20 smoothing iterations (set in lime.h with N_SMOOTH_ITERS), which is probably excessive. Maybe we should change the default value to, say, 5. Moreover, should the default par->samplingAlgorithm be changed to 1?

However, even without extra smoothing iterations the Delaunay triangulation may end up taking a long time if there's a lot of points. There some parallel Delaunay implementations, but changing LIME to use any them would probably be a bit of an undertaking. Switching to something other than qhull for triangulation has been in the plans for a number of reasons, but I'm not sure who will do that and when.

imckstewart commented 7 years ago

I don't have anything to add... I'm about to release 1.8, which I have checked out probably more thoroughly than any LIME so far, including for par->samplingAlgorithm=1.