Hi,

I have a triangle mesh, and I need to construct its Laplace-Beltrami matrix efficiently.

Currently I'm iterating the triangles, and I add a weight for each triangle edge to the sparse matrix using coeffRef. Even for 20k vertices, this process takes a minute. An obvious solution would be to reconstruct a neighborhood graph, and iterate vertices instead of triangles. But I wonder if I might have missed a solution, such as using another matrix representation (still must be sparse for large models) that would be usable with triangles iteration?

Thanks

You need to reserve enough space per column (or row) via the .reserve() method. The best is to do a first loop over mesh to compute the valence of each vertex in a "VectorXi valences(nb_vertices)". Then call mat.reserve(valences). If you know in advance the maximal valence, you can also do: mat.reserve(VectorXi::Constant(maxValence)).

Okay, now I'm down from 54 seconds to 3 seconds. But I'm confused, since I thought that the time was wasted on the sort/search. From the iterators I'm guessing that the underlying structure of the sparse matrix is an array of sparse rows. So does it mean that the whole time was wasted on reallocating the row arrays?

Also for a mesh with 172k vertices it takes five and a half minutes, while I have a .mex in matlab that does it in one and a half seconds; what am I missing?

Sorry, my bad. I got confused by the valence, since it's actually valence+1, because of the diagonal elements. Now it constructs the laplacian under a second.
I read the doc more thoroughly and you use a compressed matrix as the data structure for the sparse, so I understand how it works.

Thanks

Hi Zohar,
At IGL we're using Eigen to build the Laplacian the same way as you (looping over triangles). We're usually working with manifold triangle meshes so we know that reserving 7*#vertices will be a good approximation of the number of non-zeros.
I'm surprised it takes so long on a 20K mesh. On a 30K vertex (64K triangle) mesh, our routine takes 0.028 seconds.
(I assume you're compiling with compiler optimization flags on).
Alec

What's up Alec, I've just been referring to your [Jacobson11] and [Jacobson12] in my EG rebuttal (trashing the first, praising the latter ). Thanks again for your cyclops result, but I didn't manage to add it in time.

7*#vertices sounds appealing, but I think you should consider more, since I think you will incur penalty at vertices with higher valence. I think it's better wrong on the superfluous. Anyway, after I solved the bug, as I noted, the Armadillo is loaded in less than a second.