--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/cmd/tin2octree/builder.go	Wed Sep 19 10:54:11 2018 +0200
@@ -0,0 +1,134 @@
+package main
+
+import (
+	"encoding/binary"
+	"io"
+	"log"
+)
+
+type treeBuilder struct {
+	t      *tin
+	nodes  int
+	leaves int
+	index  []int32
+}
+
+var cubes = [8][2]vertex{
+	{{0.0, 0.0, 0.0}, {0.5, 0.5, 0.5}},
+	{{0.5, 0.0, 0.0}, {1.0, 0.5, 0.5}},
+	{{0.0, 0.0, 0.5}, {0.5, 0.5, 1.0}},
+	{{0.0, 0.5, 0.5}, {0.5, 1.0, 1.0}},
+	{{0.5, 0.0, 0.0}, {1.0, 0.5, 0.5}},
+	{{0.5, 0.5, 0.0}, {1.0, 1.0, 0.5}},
+	{{0.5, 0.0, 0.5}, {1.0, 0.5, 1.0}},
+	{{0.5, 0.5, 0.5}, {1.0, 1.0, 1.0}},
+}
+
+func (tb *treeBuilder) build() {
+
+	triangles := make([]int32, len(tb.t.triangles))
+	for i := range triangles {
+		triangles[i] = int32(i)
+	}
+
+	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("nodes: %d leaves: %d index %d\n",
+		tb.nodes, tb.leaves, tb.index[0])
+}
+
+func (tb *treeBuilder) buildRecursive(
+	triangles []int32,
+	min, max vertex,
+	depth int,
+) int32 {
+	if len(triangles) <= 16 || depth > 8 {
+		pos := len(tb.index)
+		tb.index = append(tb.index, int32(len(tb.index)))
+		tb.index = append(tb.index, triangles...)
+		//log.Printf("leaf entries: %d (%d)\n", len(triangles), depth)
+		tb.leaves++
+		return int32(-(pos + 1))
+	}
+
+	pos := len(tb.index)
+	tb.index = append(tb.index, 0, 0, 0, 0)
+
+	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)
+
+		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)
+			}
+		}
+	}
+
+	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.nodes++
+	return int32(pos)
+}
+
+func (tb *treeBuilder) Serialize(w io.Writer) error {
+	var buf [binary.MaxVarintLen32]byte
+
+	if err := binary.Write(w, binary.LittleEndian, tb.index[0]); err != nil {
+		return err
+	}
+
+	var last int32
+	var written int
+
+	for _, x := range tb.index[1:] {
+		delta := x - last
+		n := binary.PutVarint(buf[:], int64(delta))
+		for p := buf[:n]; len(p) > 0; p = p[n:] {
+			var err error
+			if n, err = w.Write(p); err != nil {
+				return err
+			}
+			written += n
+		}
+
+		last = x
+	}
+	log.Printf("compressed octree index in bytes: %d (%d)\n",
+		written, 4*len(tb.index))
+
+	return nil
+}