search

fogleman / hmm

Heightmap meshing utility.
MIT License
571 stars 50 forks source link

Optimize triangle data footprint #7

Closed mourner closed 5 years ago

mourner commented 5 years ago

@fogleman Just something I noticed when porting this to JS — currently, triangle data is always appended to triangles / halfedges / candidates / errors / queueIndexes arrays, leaving a ton of redundant old triangles that flipped on legalization.

An easy fix is to add an optional argument to addTriangle which is an existing halfedge index, and use that instead of a new one if provided. Then you can pass that to the first addTriangle after every QueueRemove or QueuePop.

This reduces the size of the arrays above at the end of a run by ~4x (they should exactly match the number of output triangles), and also modestly improves overall running time because of better cache locality / less allocation.

fogleman commented 5 years ago

Good idea. I tried to do something about that but your approach sounds simpler - I might give it a try!

fogleman commented 5 years ago

Fixed in 0e0fdaa4c88028ba263831f3677eae675b888428