package main

import (
	"encoding/binary"
	"io"
	"log"
)

type treeBuilder 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 (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("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 *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(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 *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
}