triangles-delta-encoding.go

package main

import (
	"bytes"
	"encoding/binary"
	"fmt"
	"io/ioutil"
)

// v represents a Vertex ID.
type v uint16

// triangles are Vertex triplets.
var triangles [][3]v

// result is buffered in memory, before serialization.
var out bytes.Buffer

func main() {
	readInputFile("triangles.bin")
	//rotate()
	//bubble()
	//rotateJoin()
	delta()
	writeFlat()
	writeOutputFile("strips.bin")
	proof("strips.bin", "proof.bin")
}

// delta encodes each vertex index as the difference with previous index.
// All numbers are modulo 2^16.
func delta() {
	var offset v
	for i := range triangles {
		tri := &triangles[i]
		for j := range tri {
			tmp := tri[j]
			tri[j] -= offset
			offset = tmp
		}
	}
}

// Inverse of delta
func undelta() {
	var offset v
	for i := range triangles {
		tri := &triangles[i]
		for j := range tri {
			offset += tri[j]
			tri[j] = offset
		}
	}
}

// Reorder triangles : next triangle is preferably a neighbour,
// i.e. sharing 1 edge (2 vertices) with current triangle.
func bubble() {
	common := func(i, j int) int {
		tri1, tri2 := triangles[i], triangles[j]
		shared := 0
		for a := 0; a < 3; a++ {
			for b := 0; b < 3; b++ {
				if tri1[a] == tri2[b] {
					shared++
				}
			}
		}
		return shared
	}
	neighbour := func(i, j int) bool {
		return common(i, j) == 2
	}
	countAdjacent := func() {
		n := 0
		for i := 0; i < len(triangles)-1; i++ {
			if neighbour(i, i+1) {
				n++
			}
		}
		log(n, "adjacent out of", len(triangles))
	}
	_ = countAdjacent

	//countAdjacent()
	for i := 0; i < len(triangles)-2; i++ {
		if !neighbour(i, i+1) {
			for j := i + 2; j < len(triangles); j++ {
				if neighbour(i, j) {
					triangles[i+1], triangles[j] = triangles[j], triangles[i+1]
					break
				}
			}
		}
	}
	//countAdjacent()
}

// Each triplet may be rotated so that smallest index is first
func rotate() {
	for i := range triangles {
		if triangles[i][1] < triangles[i][0] {
			if triangles[i][2] < triangles[i][1] {
				triangles[i][0], triangles[i][1], triangles[i][2] = triangles[i][2], triangles[i][0], triangles[i][1]
			} else {
				triangles[i][0], triangles[i][1], triangles[i][2] = triangles[i][1], triangles[i][2], triangles[i][0]
			}
		} else {
			if triangles[i][2] < triangles[i][0] {
				triangles[i][0], triangles[i][1], triangles[i][2] = triangles[i][2], triangles[i][0], triangles[i][1]
			}
		}
	}
}

// Each triplet may be rotated its first vertex is equal to last vertex of previous triangle
func rotateJoin() {
	for i := 1; i < len(triangles); i++ {
		switch {
		case triangles[i][1] == triangles[i-1][2]:
			triangles[i][0], triangles[i][1], triangles[i][2] = triangles[i][1], triangles[i][2], triangles[i][0]
		case triangles[i][2] == triangles[i-1][2]:
			triangles[i][0], triangles[i][1], triangles[i][2] = triangles[i][2], triangles[i][0], triangles[i][1]
		}
	}
}

// A memory buffer of just 2 bytes
var buf [2]byte

func readInputFile(filepath string) {
	data, err := ioutil.ReadFile(filepath)
	checkerr(err)
	reader := bytes.NewReader(data)

	read := func() v {
		_, err := reader.Read(buf[:])
		checkerr(err)
		return v(binary.LittleEndian.Uint16(buf[:]))
	}

	N := read()
	triangles = make([][3]v, N)
	for i := range triangles {
		A, B, C := read(), read(), read()
		triangles[i] = [3]v{A, B, C}
	}
}

// Write 2 bytes into the output buffer
func write(i v) {
	binary.LittleEndian.PutUint16(buf[:], uint16(i))
	_, err := out.Write(buf[:])
	checkerr(err)
}

// Write the complete output buffer :
// - 2 bytes for the number N of triangles
// - N * 3 * 2 bytes for the triangles
func writeFlat() {
	write(v(len(triangles)))
	for _, tri := range triangles {
		for _, p := range tri {
			write(p)
		}
	}
}

func writeOutputFile(filepath string) {
	ioutil.WriteFile(filepath, out.Bytes(), 0777)
}

// Reverse the encoding.
// Write the result into file.
// File should be identical to original file.
// (Unless some semi-destructive operations were applied, e.g. reordering)
func proof(inputFilepath, outputFilepath string) {
	readInputFile(inputFilepath)
	undelta()
	out.Reset()
	writeFlat()
	writeOutputFile(outputFilepath)
}

func log(x ...interface{}) {
	fmt.Println(x...)
}

func checkerr(err error) {
	if err != nil {
		panic(err)
	}
}