--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/pkg/octree/builder.go	Wed Oct 17 16:00:49 2018 +0200
@@ -0,0 +1,171 @@
+package octree
+
+import (
+	"encoding/binary"
+	"io"
+	"log"
+
+	"github.com/golang/snappy"
+)
+
+type Builder struct {
+	t      *Tin
+	nodes  int
+	leaves int
+	index  []int32
+}
+
+var cubes = [8][2]Vertex{
+	makeCube(0),
+	makeCube(1),
+	makeCube(2),
+	makeCube(3),
+	makeCube(4),
+	makeCube(5),
+	makeCube(6),
+	makeCube(7),
+}
+
+func makeCube(i int) [2]Vertex {
+	var d Vertex
+	if i&1 == 1 {
+		d.X = 0.5
+	}
+	if i&2 == 2 {
+		d.Y = 0.5
+	}
+	if i&4 == 4 {
+		d.Z = 0.5
+	}
+	return [2]Vertex{
+		Vertex{0.0, 0.0, 0.0}.Add(d),
+		Vertex{0.5, 0.5, 0.5}.Add(d),
+	}
+}
+
+func NewBuilder(t *Tin) *Builder {
+	return &Builder{t: t}
+}
+
+func (tb *Builder) 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("num nodes: %d\n", tb.index[0])
+
+	log.Printf("nodes: %d leaves: %d index %d\n",
+		tb.nodes, tb.leaves, tb.index[0])
+}
+
+func (tb *Builder) 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(triangles)))
+		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,
+		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 *Builder) 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
+}
+
+func (tb *Builder) WriteTo(w io.Writer) error {
+	out := snappy.NewBufferedWriter(w)
+	if err := tb.t.Serialize(out); err != nil {
+		return err
+	}
+	if err := tb.Serialize(out); err != nil {
+		return err
+	}
+	return out.Flush()
+}