--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/pkg/octree/tree.go	Sat Sep 22 21:58:15 2018 +0200
@@ -0,0 +1,81 @@
+package octree
+
+import (
+	"math"
+)
+
+type Tree struct {
+	EPSG uint32
+
+	vertices  []Vertex
+	triangles [][]int32
+	index     []int32
+
+	Min Vertex
+	Max Vertex
+}
+
+func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) {
+
+	type frame struct {
+		pos int32
+		min float64
+		max float64
+	}
+
+	if h < ot.Min.Z || ot.Max.Z < h {
+		return
+	}
+
+	stack := []frame{{1, ot.Min.Z, ot.Max.Z}}
+
+	dupes := map[int32]struct{}{}
+
+	for len(stack) > 0 {
+		top := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+
+		pos := top.pos
+		if pos == 0 {
+			continue
+		}
+		min, max := top.min, top.max
+
+		if pos > 0 { // node
+			if mid := (max-min)*0.5 + min; h >= mid {
+				pos += 4 // nodes with z-bit set
+				min = mid
+			} else {
+				max = mid
+			}
+			stack = append(stack,
+				frame{ot.index[pos+0], min, max},
+				frame{ot.index[pos+1], min, max},
+				frame{ot.index[pos+2], min, max},
+				frame{ot.index[pos+3], min, max})
+		} else { // leaf
+			pos = -pos - 1
+			n := ot.index[pos]
+			//log.Printf("%d %d %d\n", pos, n, len(ot.index))
+			indices := ot.index[pos+1 : pos+1+n]
+
+			for _, idx := range indices {
+				if _, found := dupes[idx]; found {
+					continue
+				}
+				tri := ot.triangles[idx]
+				t := Triangle{
+					ot.vertices[tri[0]],
+					ot.vertices[tri[1]],
+					ot.vertices[tri[2]],
+				}
+
+				if !(math.Min(t[0].Z, math.Min(t[1].Z, t[2].Z)) > h ||
+					math.Max(t[0].Z, math.Max(t[1].Z, t[2].Z)) < h) {
+					dupes[idx] = struct{}{}
+					fn(&t)
+				}
+			}
+		}
+	}
+}