Open frankNiessen opened 1 year ago
An entirely new implementation of calcGrains might be in order - possibly some mex file could handle the heavy calculation? Seems like when calcGrains was first implemented maps were quite a bit smaller.
It probably is already optimized, as the internal code is hidden, but yes, an entire remake is in order.
Hi, this is requested several times and here's some thoughts.
The status is that the matlab implementation for the computation of the voronoi diagram works for large datasets, the qhull used by matlab is so ancient, that it does not work for very large maps - is however faster (~2-3x). Both - at least at my machine - have the problem that they run single threaded. Also many other libraries do not multithread since it seems not so easy for the problem. Voro++ (there's also a mex version https://github.com/smr29git/MATLAB-Voro) can run multithreaded - but here each polygon is computed separately. In the tests I did, it is still much much slower despite using 12 cores. Modern qhull versions are a variably faster that the old one in Matlab, however, one needs to find the time to adapt to Matlab. It seems Mathworks will have no interest to upgrade to a more recent version.
Grain computation is faster when we are sticking to the grid ('unicell') and that is what the commercial programs do (as far as I can see). But since the way mtex can deal with nonexistend data, computing a true delaunay triangulation and voronoi diagram sounds like the thing to do.
One thought would be to subdivide the map into e.g. n parts (e.g. one for each cpu core), compute the voronoi diagram for each part in a parfor loop and then find the joints and re-index the vertices and edges. The big disadvantage is that this would make the parallel computing toolbox as a dependency.
Cheers, Rüdiger
Hi Rüdiger,
I am aware that improving on the current implementation of calcGrains has been on the wishlist for quite a while, it was not my attention to ask for it again in this thread but it seems inevitable =) Thanks for summarizing the current situation/limitations, I will think about whether there is anything to be done.
Best wishes Frank
Here is an interesting repository containing code from the 90s, when some comparisons between triangulation algorithms were conducted. A paper is included in the repository where the code is shown to compare favorably to qhull. This was a while ago, of course.
https://github.com/rexdwyer/DelaunayTriangulation
The code seems to be in C. I have no idea how difficult it would be to implement for making grain maps in MTEX.
(Rüdiger wrote) One thought would be to subdivide the map into e.g. n parts (e.g. one for each cpu core), compute the voronoi diagram for each part in a parfor loop and then find the joints and re-index the vertices and edges. The big disadvantage is that this would make the parallel computing toolbox as a dependency.
I'm running into this issue as well (I'll blame the new EBSD detectors that let me acquire ~10^8 points, not my own willingness to do so :). ) I'd be open to prototyping this approach if other want to try. I could see either using this as an option passed to calcGrains, or separate function calcGrainsParallel?
One thought: would it be faster to calculate an initial grain map using 'unitCell', then calculating a voronoi diagram only for the boundary pixels, then linking those areas? This would reduce the amount of pixels that needs to be considered.
I will try to find the time to give this a try, but if someone feels inspired by this then by all means go ahead :)
Grains are conventionally reconstructed using the command
grains = calcGrains(ebsd)
. Sometimes this can take quite a while, especially when using non-standard ways of reconstructing the grains. It would be super useful to have progress-bar within the MATLAB command window showing the progress of grain reconstruction.As a developer, I tried looking at the issue myself, and I got down to that most of the computational time is spent in the MATLAB internal function
voronoiDiagram
. As the function is MATLAB internal, it is not immediately possible to grap the progress and the implementation is thus tricky, maybe even impossible. I still wanted to flag that this would be a desireable feature.BW Frank