# HG changeset patch
# User Sascha L. Teichmann <sascha.teichmann@intevation.de>
# Date 1551280538 -3600
# Node ID f3a9e125f630bd61ca7f6fad586055ae2bc2b4ae
# Parent  19beb7d1733757798e304dedc0cf9d0eb7d10cfe
Made octree builder concurrent.

diff -r 19beb7d17337 -r f3a9e125f630 pkg/octree/builder.go
--- a/pkg/octree/builder.go	Tue Feb 26 13:02:11 2019 +0100
+++ b/pkg/octree/builder.go	Wed Feb 27 16:15:38 2019 +0100
@@ -18,6 +18,9 @@
 	"encoding/binary"
 	"io"
 	"log"
+	"runtime"
+	"sync"
+	"sync/atomic"
 
 	"github.com/golang/snappy"
 )
@@ -28,8 +31,12 @@
 	nodes  int
 	leaves int
 	index  []int32
+
+	mu sync.Mutex
 }
 
+type buildStep func(chan buildStep)
+
 var cubes = [8][2]Vertex{
 	makeCube(0),
 	makeCube(1),
@@ -71,14 +78,129 @@
 		triangles[i] = int32(i)
 	}
 
+	n := runtime.NumCPU()
+
+	steps := make(chan buildStep, n)
+
+	var wg sync.WaitGroup
+	for i := 0; i < n; i++ {
+		wg.Add(1)
+		go func() {
+			defer wg.Done()
+			for step := range steps {
+				step(steps)
+			}
+		}()
+	}
+
 	tb.index = append(tb.index, 0)
 
-	tb.buildRecursive(triangles, tb.t.Min, tb.t.Max, 0)
-	tb.index[0] = int32(len(tb.index))
-	log.Printf("info: num nodes: %d\n", tb.index[0])
+	root := func(pos int32) {
+		tb.index[0] = pos
+		close(steps)
+	}
+
+	steps <- tb.buildConcurrent(
+		triangles,
+		tb.t.Min, tb.t.Max,
+		0,
+		root)
+
+	wg.Wait()
+}
+
+func (tb *Builder) buildConcurrent(
+	triangles []int32,
+	min, max Vertex,
+	depth int,
+	parent func(int32),
+) buildStep {
+
+	return func(steps chan buildStep) {
+
+		// none concurrent for small parts.
+		if len(triangles) < 1024 || depth > 8 {
+			parent(tb.buildRecursive(triangles, min, max, depth))
+			return
+		}
+
+		bbox := Interpolate(min, max)
+
+		bboxes := make([][2]Vertex, len(cubes))
+
+		for i := range cubes {
+			bboxes[i] = [2]Vertex{
+				bbox(cubes[i][0]),
+				bbox(cubes[i][1]),
+			}
+		}
+
+		var quandrants [8][]int32
+
+		for _, tri := range triangles {
+			triangle := tb.t.Triangles[tri]
+			v0 := tb.t.Vertices[triangle[0]]
+			v1 := tb.t.Vertices[triangle[1]]
+			v2 := tb.t.Vertices[triangle[2]]
+
+			l := v0
+			l.Minimize(v1)
+			l.Minimize(v2)
 
-	log.Printf("info: nodes: %d leaves: %d index %d\n",
-		tb.nodes, tb.leaves, tb.index[0])
+			h := v0
+			h.Maximize(v1)
+			h.Maximize(v2)
+
+			for i := range bboxes {
+				if !(h.Less(bboxes[i][0]) || bboxes[i][1].Less(l)) {
+					quandrants[i] = append(quandrants[i], tri)
+				}
+			}
+		}
+
+		var used int32
+		for i := range quandrants {
+			if len(quandrants[i]) > 0 {
+				used++
+			}
+		}
+
+		pos := tb.allocNode()
+
+		for i := range quandrants {
+			if len(quandrants[i]) > 0 {
+				j := i
+				parent := func(v int32) {
+					tb.index[j] = v
+					if atomic.AddInt32(&used, -1) == 0 {
+						parent(pos)
+					}
+				}
+				step := tb.buildConcurrent(
+					quandrants[j],
+					bboxes[j][0], bboxes[j][1],
+					depth+1,
+					parent)
+				select {
+				case steps <- step:
+				default:
+					// all slots busy -> execute directly.
+					step(steps)
+				}
+			}
+		}
+	}
+}
+
+func (tb *Builder) allocNode() int32 {
+	tb.mu.Lock()
+	pos := int32(len(tb.index))
+	tb.index = append(tb.index,
+		0, 0, 0, 0,
+		0, 0, 0, 0)
+	tb.nodes++
+	tb.mu.Unlock()
+	return pos
 }
 
 func (tb *Builder) buildRecursive(
@@ -87,19 +209,16 @@
 	depth int,
 ) int32 {
 	if len(triangles) <= 16 || depth > 8 {
+		tb.mu.Lock()
 		pos := len(tb.index)
 		tb.index = append(tb.index, int32(len(triangles)))
 		tb.index = append(tb.index, triangles...)
 		//log.Printf("leaf entries: %d (%d)\n", len(triangles), depth)
 		tb.leaves++
+		tb.mu.Unlock()
 		return int32(-(pos + 1))
 	}
 
-	pos := len(tb.index)
-	tb.index = append(tb.index,
-		0, 0, 0, 0,
-		0, 0, 0, 0)
-
 	bbox := Interpolate(min, max)
 
 	bboxes := make([][2]Vertex, len(cubes))
@@ -134,17 +253,19 @@
 		}
 	}
 
+	pos := tb.allocNode()
+
 	for i := range quandrants {
 		if len(quandrants[i]) > 0 {
 			child := tb.buildRecursive(
 				quandrants[i],
 				bboxes[i][0], bboxes[i][1],
 				depth+1)
-			tb.index[pos+i] = child
+			tb.index[pos+int32(i)] = child
 		}
 	}
 	tb.nodes++
-	return int32(pos)
+	return pos
 }
 
 func (tb *Builder) serialize(w io.Writer) error {