# HG changeset patch # User Sascha L. Teichmann # Date 1537347251 -7200 # Node ID 010cc30fdf48db45efda6c1a97ea4715de8d354e # Parent be0327dc311966c321b1968386f95793b35cbe01 octree: renamed file containing the tree builder to a more suited name. diff -r be0327dc3119 -r 010cc30fdf48 cmd/tin2octree/builder.go --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cmd/tin2octree/builder.go Wed Sep 19 10:54:11 2018 +0200 @@ -0,0 +1,134 @@ +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 +} diff -r be0327dc3119 -r 010cc30fdf48 cmd/tin2octree/tree.go --- a/cmd/tin2octree/tree.go Wed Sep 19 10:52:20 2018 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,134 +0,0 @@ -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 -}