# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1707683182 -3600
# Node ID 33499bd1b8291b7c24d0af14311bfa5ddb95b97f
# Parent  c09d55e9f098ad8e33018d75d1d42286f565b39f
Sort indices in spatial index.

diff -r c09d55e9f098 -r 33499bd1b829 pkg/mesh/meshserialize_v2.go
--- a/pkg/mesh/meshserialize_v2.go	Sun Feb 11 18:44:03 2024 +0100
+++ b/pkg/mesh/meshserialize_v2.go	Sun Feb 11 21:26:22 2024 +0100
@@ -16,6 +16,7 @@
 func (s *STRTree) optimizeForSerializationV2() {
 	s.removeUnusedTriangles()
 	// TODO: Implement me!
+	s.sortIndices()
 }
 
 // removeUnusedTriangles removes all triangles from the
diff -r c09d55e9f098 -r 33499bd1b829 pkg/mesh/strtree.go
--- a/pkg/mesh/strtree.go	Sun Feb 11 18:44:03 2024 +0100
+++ b/pkg/mesh/strtree.go	Sun Feb 11 21:26:22 2024 +0100
@@ -14,8 +14,9 @@
 package mesh
 
 import (
+	"cmp"
 	"math"
-	"sort"
+	"slices"
 )
 
 // STRTreeDefaultEntries is the default number of children per node and leaf.
@@ -265,10 +266,10 @@
 }
 
 func (s *STRTree) build(items []int32) int32 {
-	sort.Slice(items, func(i, j int) bool {
-		ti := s.tin.Triangles[items[i]]
-		tj := s.tin.Triangles[items[j]]
-		return s.tin.Vertices[ti[0]].X < s.tin.Vertices[tj[0]].X
+	slices.SortFunc(items, func(i, j int32) int {
+		ti := s.tin.Triangles[i]
+		tj := s.tin.Triangles[j]
+		return cmp.Compare(s.tin.Vertices[ti[0]].X, s.tin.Vertices[tj[0]].X)
 	})
 
 	P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
@@ -278,10 +279,10 @@
 
 	leaves := s.strJoin(
 		slices, S,
-		func(i, j int32) bool {
+		func(i, j int32) int {
 			ti := s.tin.Triangles[i]
 			tj := s.tin.Triangles[j]
-			return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y
+			return cmp.Compare(s.tin.Vertices[ti[0]].Y, s.tin.Vertices[tj[0]].Y)
 		},
 		s.allocLeaf,
 	)
@@ -295,8 +296,8 @@
 		return s.allocNode(items)
 	}
 
-	sort.Slice(items, func(i, j int) bool {
-		return s.bbox(items[i]).X1 < s.bbox(items[j]).X1
+	slices.SortFunc(items, func(i, j int32) int {
+		return cmp.Compare(s.bbox(i).X1, s.bbox(j).X1)
 	})
 
 	P := int(math.Ceil(float64(len(items)) / float64(s.Entries)))
@@ -306,7 +307,7 @@
 
 	nodes := s.strJoin(
 		slices, S,
-		func(i, j int32) bool { return s.bbox(i).Y1 < s.bbox(j).Y1 },
+		func(i, j int32) int { return cmp.Compare(s.bbox(i).Y1, s.bbox(j).Y1) },
 		s.allocNode,
 	)
 
@@ -337,16 +338,14 @@
 }
 
 func (s *STRTree) strJoin(
-	slices [][]int32, S int,
-	less func(int32, int32) bool,
+	slics [][]int32, S int,
+	cmp func(int32, int32) int,
 	alloc func([]int32) int32,
 ) []int32 {
 	nodes := make([]int32, 0, S*S)
 
-	for _, slice := range slices {
-		sort.Slice(slice, func(i, j int) bool {
-			return less(slice[i], slice[j])
-		})
+	for _, slice := range slics {
+		slices.SortFunc(slice, cmp)
 
 		for len(slice) > 0 {
 			var n int
@@ -426,3 +425,26 @@
 		}
 	}
 }
+
+// sortIndices sorts the indices in the inner nodes and leaves of the tree.
+// This helps if the index array is delta encoded in serialization.
+// It also may help reduding CPU cache line misses during usage because
+// redirects are ordered closer together.
+func (s *STRTree) sortIndices() {
+	stack := []int32{s.index[0]}
+	for len(stack) > 0 {
+		top := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+		if top > 0 { // node
+			n := s.index[top+1]
+			children := s.index[top+2 : top+2+n]
+			stack = append(stack, children...)
+			slices.Sort(children)
+		} else { // leaf
+			top = -top - 1
+			n := s.index[top+1]
+			triangles := s.index[top+2 : top+2+n]
+			slices.Sort(triangles)
+		}
+	}
+}