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
}