icomesh
icomesh copied to clipboard
mourner
Limit midpoint cache to icosahedron edges
In theory, if we replace repeated subdivision with grid-like iteration over each icosahedron face, we could reduce the midpoint cache needed for the algorithm down to just the points on icosahedron edges, which would be a small fraction of the current case:
Not sure if it can be implemented in a simple way, but dropping the idea here anyway. cc @IvanSanchez @MaxGraey
This led me to a simpler idea that got us 3x perf improvement! https://github.com/mourner/icomesh/commit/4cc07dcf001d145b8ea82b68980d0d68de332268
Gonna leave this here.
The idea is split each face of the original polyhedron into the final faces in one go. The IDs for the inner vertices, the "upside" triangles and the "downside" triangles can be assigned deterministically. Only the IDs for the outer vertices (on the split edges of the original polyhedron) need to be looked up.
But that look-up can happen only one per face-edge (by creating a map of edge ID to an array of vertex IDs). Even better, the vertex IDs can be calculated by ( 20 + 20 * edgeID * frequency + position along the edge )
Numbering is easier when using Cantor's pairing function for this (just add some checks for x==0 || y==0 || x+y == freq for the vertices):
@mourner Another simple improvement which I see is build iterative subdivision only for one side and copy this side to rest 11 places used rotation and remove common vertices on edges.
@mourner Another simple improvement which I see is build iterative subdivision only for one side and copy this side to rest 11 places used rotation and remove common vertices on edges.
I guess you mean more like calculating only 10 sides, then mirroring those 10 sides (any other kind of rotations would involve trigonometry functions, which are computationally expensive and thus undesireable).
That approach suffers from a similar drawback than #5: What to do at the face boundaries. Think about it: the vertices needed to represent 10 faces are not the same amount as half the vertices needed to represent 20 faces.
(On the plus side, mirroring a half could save half of the calculations currently being done for normalizing the point distances to the origin)