Mercurial > gemma
changeset 5684:536e842d9bfa sr-v2
Reorder vertices in tins to minimize delta distances.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Sun, 11 Feb 2024 22:32:55 +0100 |
parents | 31973f6f5cca |
children | 0ee8ace01b60 |
files | pkg/mesh/meshserialize_v2.go |
diffstat | 1 files changed, 49 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- a/pkg/mesh/meshserialize_v2.go Sun Feb 11 21:37:00 2024 +0100 +++ b/pkg/mesh/meshserialize_v2.go Sun Feb 11 22:32:55 2024 +0100 @@ -13,9 +13,16 @@ package mesh +import ( + "cmp" + "math" + "slices" + "sort" +) + func (s *STRTree) optimizeForSerializationV2() { s.removeUnusedTriangles() - // TODO: Implement me! + s.sortVertices() s.sortIndices() } @@ -49,3 +56,44 @@ } }) } + +// sortVertices so that the deltas between neighbors are minimized. +func (s *STRTree) sortVertices() { + vertices := s.tin.Vertices + indices := make([]int32, len(vertices)) + for i := range len(indices) { + indices[i] = int32(i) + } + + slices.SortFunc(indices, func(a, b int32) int { + return cmp.Compare(vertices[a].X, vertices[b].X) + }) + + n := int(math.Sqrt(float64(len(vertices)))) + m := len(vertices) / n + + var ( + up = func(a, b int32) int { return cmp.Compare(vertices[a].Y, vertices[b].Y) } + down = func(a, b int32) int { return cmp.Compare(vertices[b].Y, vertices[a].Y) } + ) + for p := indices; len(p) > 0; up, down = down, up { + l := min(len(p), m) + slices.SortStableFunc(p[:l], down) + p = p[l:] + } + + // We really need to to sort the vertices actually, too. + sort.Slice(vertices, func(i, j int) bool { return indices[i] < indices[j] }) + + reindices := make([]int32, len(indices)) + for i, idx := range indices { + reindices[idx] = int32(i) + } + + // Update the indices in the triangles. + for _, tri := range s.tin.Triangles { + for i, idx := range tri { + tri[i] = reindices[idx] + } + } +}