`TopologicalMesh::toTriangleMesh()` is very slow

[hoshiryu]

While implementing attributes-aware subdivision, I found that converting a TopologicalMesh into a TriangleMesh is very slow (see figures below). This might be due to the unordered_map lookup. Regarding end-of-frame subdivision, which might be usefull for animated models (i.e. working on the corse mesh, then subdividing the result), I would suggest to do it in 3 steps:

• build the TopologicalMesh, subdivide it and convert it into a specific TriangleMesh at load time to store the subdivided topology;
• also register the map from the TopologicalMesh vertices to the TriangleMesh ones (and save it to a file so that it can be reloaded with the mesh without recomputing it);
• at the end of the frame, rebuild and resubdivide the TopologicalMesh from the coarse TriangleMesh and use the map to transfer the vertices positions and normals.

Times for the subdivision are given with the following steps:

• convert from coarse TriangleMesh to TopologicalMesh
• run n subdivision passes (CatmullClark)
• convert back from subdivided TopologicalMesh to TriangleMesh
• convert again from subdivided TriangleMesh to TopologicalMesh (just to mesure time, not needed in practice)

                         #####   Dana (1 subdiv)   #####
- 09:56:52 AM INFO: Try subdiv
- 09:56:52 AM INFO: Topo done
- 09:56:52 AM INFO: Subdiv done
- 09:56:52 AM INFO: Starting back to core
- 09:56:52 AM INFO:      add attributes done
- 09:56:52 AM INFO:      recompute normals done
- 09:56:55 AM INFO:      transferred 9% of faces (55510 vertices in the map)
- 09:57:01 AM INFO:      transferred 19% of faces (105845 vertices in the map)
- 09:57:11 AM INFO:      transferred 29% of faces (148265 vertices in the map)
- 09:57:22 AM INFO:      transferred 39% of faces (190816 vertices in the map)
- 09:57:35 AM INFO:      transferred 49% of faces (232853 vertices in the map)
- 09:57:49 AM INFO:      transferred 59% of faces (261208 vertices in the map)
- 09:58:03 AM INFO:      transferred 69% of faces (287485 vertices in the map)
- 09:58:19 AM INFO:      transferred 79% of faces (309608 vertices in the map)
- 09:58:38 AM INFO:      transferred 89% of faces (331849 vertices in the map)
- 09:58:56 AM INFO:      transferred 99% of faces (353716 vertices in the map)
- 09:58:56 AM INFO: Back to core done
- 09:58:56 AM INFO: Mesh ready
- 09:59:18 AM INFO: Just tried re-topo

                         #####   Dana (2 subdiv)   #####
- 10:25:26 AM INFO: Try subdiv
- 10:25:27 AM INFO: Topo done
- 10:25:28 AM INFO: Subdiv done
- 10:25:28 AM INFO: Starting back to core
- 10:25:28 AM INFO:      add attributes done
- 10:25:28 AM INFO:      recompute normals done
- 10:26:09 AM INFO:      transferred 9% of faces (234359 vertices in the map)
- 10:28:16 AM INFO:      transferred 19% of faces (432404 vertices in the map)
- 10:32:32 AM INFO:      transferred 29% of faces (609393 vertices in the map)
- 10:38:30 AM INFO:      transferred 39% of faces (774731 vertices in the map)
- 10:45:35 AM INFO:      transferred 49% of faces (939906 vertices in the map)
- 10:53:13 AM INFO:      transferred 59% of faces (1051070 vertices in the map)
- 11:00:24 AM INFO:      transferred 69% of faces (1153138 vertices in the map)
- 11:08:33 AM INFO:      transferred 79% of faces (1246521 vertices in the map)
- 11:18:25 AM INFO:      transferred 89% of faces (1334130 vertices in the map)
- 11:27:59 AM INFO:      transferred 99% of faces (1421966 vertices in the map)
- 11:27:59 AM INFO: Back to core done
- 11:27:59 AM INFO: Mesh ready
- 11:33:27 AM INFO: Just tried re-topo

                         #####   Hand (2 subdiv)   #####
- 10:27:39 AM INFO: Try subdiv
- 10:27:39 AM INFO: Topo done
- 10:27:40 AM INFO: Subdiv done
- 10:27:40 AM INFO: Starting back to core
- 10:27:40 AM INFO:      add attributes done
- 10:27:40 AM INFO:      recompute normals done
- 10:27:44 AM INFO:      transferred 10% of faces (107004 vertices in the map)
- 10:27:54 AM INFO:      transferred 20% of faces (197609 vertices in the map)
- 10:28:07 AM INFO:      transferred 30% of faces (279491 vertices in the map)
- 10:28:24 AM INFO:      transferred 40% of faces (355326 vertices in the map)
- 10:28:46 AM INFO:      transferred 50% of faces (430435 vertices in the map)
- 10:29:13 AM INFO:      transferred 60% of faces (481361 vertices in the map)
- 10:29:39 AM INFO:      transferred 70% of faces (528169 vertices in the map)
- 10:30:06 AM INFO:      transferred 80% of faces (571228 vertices in the map)
- 10:30:38 AM INFO:      transferred 90% of faces (612079 vertices in the map)
- 10:31:13 AM INFO:      transferred 100% of faces (652298 vertices in the map)
- 10:31:13 AM INFO: Back to core done
- 10:31:13 AM INFO: Mesh ready
- 10:31:45 AM INFO: Just tried re-topo

[hoshiryu]

Here are the stats for the hashing:

Dana 1 (202 536 faces): load_factor: 0.795805  -- max_load_factor: 1  -- #buckets: 444 487  -- #collisions: 353 705
Dana 2 (810 144 faces): load_factor: 0.775946  -- max_load_factor: 1  -- #buckets: 1 832 561  -- #collisions: 1 421 948
Hand 2 (369 840 faces): load_factor: 0.722781  -- max_load_factor: 1  -- #buckets: 902 483  -- #collisions: 652 220

using the following hashing (for both conversions):

size_t hx = std::hash<Scalar>()(lvalue[0]);
size_t hy = std::hash<Scalar>()(lvalue[1]);
size_t hz = std::hash<Scalar>()(lvalue[2]);
return (hx ^ (hy << 1)) ^ hz;

I get these timings (which are way better) and stats (which are strangely the same):

                                #####     Dana (1 subdiv)     #####
- 03:03:55 PM INFO: Try subdiv
- 03:03:55 PM INFO: Topo done
- 03:03:55 PM INFO: Subdiv done
- 03:03:55 PM INFO: Starting back to core (202536faces)
- 03:03:55 PM INFO:      add attributes done
- 03:03:55 PM INFO:      recompute normals done
- 03:03:55 PM INFO:      transferred 9% of faces (55510 vertices in the map)
- 03:03:55 PM INFO:      transferred 19% of faces (105845 vertices in the map)
- 03:03:55 PM INFO:      transferred 29% of faces (148265 vertices in the map)
- 03:03:55 PM INFO:      transferred 39% of faces (190816 vertices in the map)
- 03:03:55 PM INFO:      transferred 49% of faces (232853 vertices in the map)
- 03:03:55 PM INFO:      transferred 59% of faces (261208 vertices in the map)
- 03:03:55 PM INFO:      transferred 69% of faces (287485 vertices in the map)
- 03:03:55 PM INFO:      transferred 79% of faces (309608 vertices in the map)
- 03:03:55 PM INFO:      transferred 89% of faces (331849 vertices in the map)
- 03:03:55 PM INFO:      transferred 99% of faces (353716 vertices in the map)
- 03:03:55 PM INFO:      map info:0.795805  --  1  --  444487
- 03:03:55 PM INFO:      map collisions: 252421
- 03:03:55 PM INFO: Back to core done
- 03:03:55 PM INFO: Mesh ready
- 03:03:56 PM INFO: Just tried re-topo

                                #####     Dana (2 subdiv)     #####
- 03:01:36 PM INFO: Try subdiv
- 03:01:36 PM INFO: Topo done
- 03:01:37 PM INFO: Subdiv done
- 03:01:37 PM INFO: Starting back to core (810144faces)
- 03:01:37 PM INFO:      add attributes done
- 03:01:37 PM INFO:      recompute normals done
- 03:01:38 PM INFO:      transferred 9% of faces (234359 vertices in the map)
- 03:01:38 PM INFO:      transferred 19% of faces (432404 vertices in the map)
- 03:01:38 PM INFO:      transferred 29% of faces (609393 vertices in the map)
- 03:01:38 PM INFO:      transferred 39% of faces (774731 vertices in the map)
- 03:01:38 PM INFO:      transferred 49% of faces (939906 vertices in the map)
- 03:01:39 PM INFO:      transferred 59% of faces (1051070 vertices in the map)
- 03:01:39 PM INFO:      transferred 69% of faces (1153138 vertices in the map)
- 03:01:39 PM INFO:      transferred 79% of faces (1246521 vertices in the map)
- 03:01:39 PM INFO:      transferred 89% of faces (1334130 vertices in the map)
- 03:01:39 PM INFO:      transferred 99% of faces (1421966 vertices in the map)
- 03:01:39 PM INFO:      map info:0.775946  --  1  --  1832561
- 03:01:40 PM INFO:      map collisions: 1016828
- 03:01:40 PM INFO: Back to core done
- 03:01:40 PM INFO: Mesh ready
- 03:01:41 PM INFO: Just tried re-topo

                                #####     Hand (2 subdiv)     #####
- 03:02:42 PM INFO: Try subdiv
- 03:02:42 PM INFO: Topo done
- 03:02:42 PM INFO: Subdiv done
- 03:02:42 PM INFO: Starting back to core (369840faces)
- 03:02:42 PM INFO:      add attributes done
- 03:02:42 PM INFO:      recompute normals done
- 03:02:42 PM INFO:      transferred 10% of faces (107004 vertices in the map)
- 03:02:42 PM INFO:      transferred 20% of faces (197609 vertices in the map)
- 03:02:42 PM INFO:      transferred 30% of faces (279491 vertices in the map)
- 03:02:42 PM INFO:      transferred 40% of faces (355326 vertices in the map)
- 03:02:43 PM INFO:      transferred 50% of faces (430435 vertices in the map)
- 03:02:43 PM INFO:      transferred 60% of faces (481361 vertices in the map)
- 03:02:43 PM INFO:      transferred 70% of faces (528169 vertices in the map)
- 03:02:43 PM INFO:      transferred 80% of faces (571228 vertices in the map)
- 03:02:43 PM INFO:      transferred 90% of faces (612079 vertices in the map)
- 03:02:43 PM INFO:      transferred 100% of faces (652298 vertices in the map)
- 03:02:43 PM INFO:      map info:0.722781  --  1  --  902483
- 03:02:43 PM INFO:      map collisions: 467376
- 03:02:43 PM INFO: Back to core done
- 03:02:43 PM INFO: Mesh ready
- 03:02:44 PM INFO: Just tried re-topo