Mercurial > gemma

comparison pkg/mesh/meshserialize_v2.go @ 5684:536e842d9bfa sr-v2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 33499bd1b829
children 0ee8ace01b60
comparison
equal deleted inserted replaced
5683:31973f6f5cca 5684:536e842d9bfa
11 // Author(s): 11 // Author(s):
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de> 12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
13 13
14 package mesh 14 package mesh
15 15
16 import (
17 "cmp"
18 "math"
19 "slices"
20 "sort"
21 )
22
16 func (s *STRTree) optimizeForSerializationV2() { 23 func (s *STRTree) optimizeForSerializationV2() {
17 s.removeUnusedTriangles() 24 s.removeUnusedTriangles()
18 // TODO: Implement me! 25 s.sortVertices()
19 s.sortIndices() 26 s.sortIndices()
20 } 27 }
21 28
22 // removeUnusedTriangles removes all triangles from the 29 // removeUnusedTriangles removes all triangles from the
23 // TIN that are not registered in the spatial index. 30 // TIN that are not registered in the spatial index.
47 for i, idx := range indices { 54 for i, idx := range indices {
48 indices[i] = remap[idx] 55 indices[i] = remap[idx]
49 } 56 }
50 }) 57 })
51 } 58 }
59
60 // sortVertices so that the deltas between neighbors are minimized.
61 func (s *STRTree) sortVertices() {
62 vertices := s.tin.Vertices
63 indices := make([]int32, len(vertices))
64 for i := range len(indices) {
65 indices[i] = int32(i)
66 }
67
68 slices.SortFunc(indices, func(a, b int32) int {
69 return cmp.Compare(vertices[a].X, vertices[b].X)
70 })
71
72 n := int(math.Sqrt(float64(len(vertices))))
73 m := len(vertices) / n
74
75 var (
76 up = func(a, b int32) int { return cmp.Compare(vertices[a].Y, vertices[b].Y) }
77 down = func(a, b int32) int { return cmp.Compare(vertices[b].Y, vertices[a].Y) }
78 )
79 for p := indices; len(p) > 0; up, down = down, up {
80 l := min(len(p), m)
81 slices.SortStableFunc(p[:l], down)
82 p = p[l:]
83 }
84
85 // We really need to to sort the vertices actually, too.
86 sort.Slice(vertices, func(i, j int) bool { return indices[i] < indices[j] })
87
88 reindices := make([]int32, len(indices))
89 for i, idx := range indices {
90 reindices[idx] = int32(i)
91 }
92
93 // Update the indices in the triangles.
94 for _, tri := range s.tin.Triangles {
95 for i, idx := range tri {
96 tri[i] = reindices[idx]
97 }
98 }
99 }