search

huxingyi / meshlite

(Depreciated) meshlite is a library with focus on 3D mesh generating and processing in rust language.
MIT License
45 stars 5 forks source link

More optimizations for `subdivide()` #6

Closed anderejd closed 6 years ago

anderejd commented 6 years ago

Before

faces     | vertices  | halfedges | edges     | verts/s   | time (ms)
----------+-----------+-----------+-----------+-----------+-----------
24        | 26        | 96        | 48        | 172082    | 0.10     
96        | 98        | 384       | 192       | 275558    | 0.26     
384       | 386       | 1536      | 768       | 290359    | 0.99     
1536      | 1538      | 6144      | 3072      | 319219    | 3.61     
6144      | 6146      | 24576     | 12288     | 297132    | 15.51    
24576     | 24578     | 98304     | 49152     | 293099    | 62.89    
98304     | 98306     | 393216    | 196608    | 285825    | 257.95   
393216    | 393218    | 1572864   | 786432    | 279832    | 1053.89  
1572864   | 1572866   | 6291456   | 3145728   | 274094    | 4303.81  
Vertices per second, min: 172082, max: 319219, avg: 276356

After

faces     | vertices  | halfedges | edges     | verts/s   | time (ms)
----------+-----------+-----------+-----------+-----------+-----------
24        | 26        | 96        | 48        | 389678    | 0.05     
96        | 98        | 384       | 192       | 474868    | 0.15     
384       | 386       | 1536      | 768       | 670404    | 0.43     
1536      | 1538      | 6144      | 3072      | 647458    | 1.78     
6144      | 6146      | 24576     | 12288     | 671209    | 6.87     
24576     | 24578     | 98304     | 49152     | 561476    | 32.83    
98304     | 98306     | 393216    | 196608    | 535278    | 137.74   
393216    | 393218    | 1572864   | 786432    | 507164    | 581.49   
1572864   | 1572866   | 6291456   | 3145728   | 485607    | 2429.22  
Vertices per second, min: 389678, max: 671209, avg: 549238

Roughly twice as fast as the master branch :)

I did also run rustfmt on the src/subdivide.rs as the last commit so it can easily be reverted if you don't like it.

huxingyi commented 6 years ago

Great work, really push the limitation 👍

anderejd commented 6 years ago

Thanks!

I'm going to spend at least one more full day on this before moving on to actually using the library, optimization is crazy fun... :slightly_smiling_face:

huxingyi commented 6 years ago

I guess you are going to heavily use subdivision in your project. BTW, Dust3D only use subdivision when user added a single node and choose to subdivide it. Hope some day you have time to touch the mesh boolean code. Currently with the mesh union algorithm, I am not using the meshlite, but CGAL. This part of the library need be rewrite some day to replace CGAL mesh union.

anderejd commented 6 years ago

I guess you are going to heavily use subdivision in your project.

Yes. My main reason for optimizing the subdivision is to explore if I can make meshlite handle meshes of high enough resolution and it seems like it's almost there. I haven't profiled any memory usage yet though, but that's less important for my use-case. I'm still not sure if half-edge mesh representation is the right choice for my project but I'm very happy with finding meshlite and not needing to write the mesh code from scratch.

Hope some day you have time to touch the mesh boolean code.

Sounds like fun :+1: If I find the time, then I'll make sure to open a github issue here to discuss it first.