Fast Eigen::MatrixXd type casting to points

[BBBBBbruce]

Hello, I am wondering if there is a fast way to cast the MatrixXd/MatrixXi to points_3? I saw issue #3161, but it is using the for-loop.

In my case, I have multiple(3, to be specific) tetrahedral meshes(GMSH, *.msh), loading by libigl. The vertices and tetrahedrons are stored in one MatrixXd and one MatrixXi separately. And they would have millions of points which for loop would be quite a pain in run time speed.

I wonder how can I do this efficiently?

Thanks for the help

[lrineau]

@mglisse Is there a chance that could be done using Epick_d in dimension 3? I know you are using Eigen types natively, in that kernel.

[mglisse]

What do you want to do exactly? It sounds like you have an array that you can interpret as a sequence of vectors (points) from Eigen, and you would like a sequence of CGAL points? The answer really depends on what you want to do with that sequence of CGAL points... Are you trying to build a CGAL mesh?
For some uses, I would use some form of transform_iterator to keep the original matrix in memory and build the Point_3 where it is used, which most likely would come for free as the copy would get folded into the immediate use.
Copying a few million points doesn't sound that expensive if you only do it a few times.

@lrineau By default Epick_d uses std::array/std::vector. It is possible to make it use a wrapper over Eigen vectors. It is also possible to build a similar traits class that uses Eigen vectors directly as points (drop the wrapper). But that still won't be exactly the same type as you get when accessing the i-th column of an array.

[BBBBBbruce]

Hi, thanks for the reply.

I am planning to use CGAL to do the collision detection for a simulation. The meshes are stored as Eigen matrices. The reason I thought it would be expensive is I need to visualise the meshes at each frame(so, it wont be a few), which CGAL does not support (*.msh) print (based on what I see from the document). So, I need to convert back to Eigen and do the visualisation(libigl has built-in visualisation functions for *.msh).

Currently, I have two options, (if converting from Eigen to CGAL and converting back for each frame is too expensive) 1. keep both eigen mesh and cgal mesh in my program(could cause memory-intensive problems); 2. writing the CGAL visualiser for *.msh(this would take me quite a while since I have not worked with OpenGL for a quite long time).

[lrineau]

@lrineau By default Epick_d uses std::array/std::vector. It is possible to make it use a wrapper over Eigen vectors. It is also possible to build a similar traits class that uses Eigen vectors directly as points (drop the wrapper). But that still won't be exactly the same type as you get when accessing the i-th column of an array.

@mglisse My dream would be a kernel type allowing any struct or array containing three double to be a K::Point_3. I do not understand why we have not yet created such a modular kernel. That kernel could even be parametrized by a meta-programming types map, so that the user could decide to gives the implementation for a given subset of kernel objects, and the CGAL implementation would provide the missing types, (and the predicates/construction functors).

[mglisse]

My dream would be a kernel type allowing any struct or array containing three double to be a K::Point_3. I do not understand why we have not yet created such a modular kernel. That kernel could even be parametrized by a meta-programming types map, so that the user could decide to gives the implementation for a given subset of kernel objects, and the CGAL implementation would provide the missing types, (and the predicates/construction functors).

That's not so far from what I have in NewKernel_d. The 3rd parameter of Cartesian_LA_base_d describes a vector (type, how to read/write), and the rest is built on top of it. If you do the same typedefs as for Epick_d except for Cartesian_wrap, you get that vector type directly as K::Point_d. You can specialize a functor for a kernel, or let it use the default one built on top of other functors. Etc.

in libigl a vector of N points is not not a vector of N triplets, but a vector of 3 vectors of size N.

You could still have as point type a struct that just contains an int (using directly int might cause trouble), as long as you define how to access the coordinates. One reason I wanted stateful kernels was precisely to support this kind of thing, although I think I never quite finished that (?) so it may be required to make the array global.

One problem is when you want to mix types. If your input is an IGL matrix, you may not be able to construct a new point of that type. Then what do you do for constructions, have 2 different point types in the same kernel?

[BBBBBbruce]

What do you mean by

you may not be able to construct a new point of that type

Having 2 different point types in one kernel is one possible solution, but that would limit my models or scene to a relatively simple one.

[afabri]

This was also my dream up to the moment that I discovered that in libigl a vector of N points is not not a vector of N triplets, but a vector of 3 vectors of size N.

[lrineau]

in libigl a vector of N points is not not a vector of N triplets, but a vector of 3 vectors of size N

That is wrong. A vector of N points in libigl is a Eigen::MatrixXd of size N×3: that means that the XYZ coordinates of a point are contiguous in memory. What is difficult with such a representation is that it is intrinsically const: one cannot create just a new point, but only a full sequence of points (probably part of a mesh). So, our constructors like Construct_midpoint_3 cannot work because they cannot create just a new point. We can probably create a CGAL "kernel" with only predicates, but not one creating new points.

[mglisse]

SoA (structure of arrays) does exist, even if libigl doesn't use it.

For the particular case of points stored in a MatrixXd, there could be a possibility to resize the matrix to add points, but it may be that Block (what you get with mat.col(i)) and Matrix are compatible enough that telling CGAL that the points are Matrix<double,3,1> while giving it mat.col(i) might work and still allow constructing new points. But again that's going to depend a lot on what we are doing with those points exactly.

[afabri]

@BBBBBbruce what do you mean with collision detection? What CGAL functions do you want to apply on your libigl mesh? Does it stay unmodified, or do you change coordinates from the CGAL side?

[afabri]

If more or less all points change coordinates, will the main problem not be that the AABB tree must be constructed at each frame? That will even be more costly than just copying a point.

[BBBBBbruce]

So, if I understand correctly, I cannot change the coordinates in the AABB class? I thought I can create it once and keep it updating

[afabri]

Just as any tree data structure you cannot just change a value of a leaf node and expect the tree to be correct. Say you have an std::set<int> the values in the leaves in an inorder traversal are sorted, and you cannot just replace a value in a leaf hoping that the set remains ordered.

[BBBBBbruce]

Oh, I see, thank you, I didn't notice this. I will need to reconsider the method.

[afabri]

Note that if the points only move a little it is maybe enough to update the bounding boxes in a bottom up way.

[sloriot]

Note that you may want to consider the following class:
https://doc.cgal.org/latest/Polygon_mesh_processing/classCGAL_1_1Rigid__triangle__mesh__collision__detection.html

It is working even if global affine transformations are applied to the input meshes, without having to rebuild the trees.