Making the library faster

[chpark1111]

Is there a way to accelerate this library? It doesn't matter if the precision of volume or other meshes get slightly lower. Is there something I can control like the precision and get speed up? I can modify in a code level for only my use.

I already tried the parallelization but didn't help. (It more likely made it slower) Because what I need is rapid small calculations not speeding up one large calculation.

[pca006132]

Ah, we already tried to accelerate this as much as we can, so there is probably no low hanging fruits. Precision doesn't really affect the performance except for SDF. We can probably try to use the SIMD sort to replace some of the sorting calls, but even if that can help, it will only affect large meshes.

If you want to, you can tell us your use cases, ideally with a demo code, so we can see where is the bottleneck.

[chpark1111]

Oh what I exactly need is to make the triangularization faster. (The function converting manifold to mesh) I think the triangularization will be accelerated if we can control the ideal length of the triangle meshes. How can I control this? I think the SDF part is what I need I guess? How to you guys decide the number of vertices or length of edges when converting manifold to mesh?

To elaborate more, I need rapid mesh boolean operations and get the volume of the results. Do you see any improvements in this pipeline. (Doesn't matter if it fails to triangularize really small intersections or any)

[elalish]

@chpark1111 How do you know the triangulation is causing the slowness? Can you show us some code you ran? Also, have you run it in verbose mode, so that it'll print how long each step takes?

Yes, I'm sure the triangulation could be sped up, but ideally there shouldn't be that much triangulation. Do you have a lot of co-linear/co-planar intersections? That may slow things down. Or triangles of very different sizes intersecting?

This library is about geometric robustness, so if you don't care about triangulation failing, this library may be overkill.

[chpark1111]

@elalish I didn't notice about the verbose mode. I'll try them!
Yep! I think I have lot of them since I'm merging many bounding boxes (possibly intersecting lot) and subtracting it from the mesh.

I do care about triangulation but I just meant that it won't much matter for small volume triangular meshes to fail only if I can accelerate it.

So, is there a way we can speed up the triangulation??

My code is just boolean adding some number of bounding boxes and subtracting the mesh (or vice versa) and calculating the volume. That's all.

[elalish]

Show us the benchmarks and try @pca006132's intersection idea and then we'll talk. We've done a lot to make things fast already - feel free to open a PR if you have a performance improvement idea.

[pca006132]

Oh triangulation... It is known that the triangulation algorithm is not fast and does not benefit much from parallelization. I don't have much idea about this. What I know is that the algorithm is different from other commonly used triangulation algorithms, will produce skinny triangles, but is more robust when encountering self intersection or something. @elalish What do you think?

[pca006132]

Thinking about it, if your models don't have much overlap, maybe you can try to do intersection instead of union/subtraction for volume calculation, as the mesh may be smaller with intersection.

[chpark1111]

Thanks for the thoughts! But what I need to calculate is volume of boolean union of many meshes... But maybe those kind of optimizations might work in such setup!