Mercurial > gemma
view pkg/octree/builder.go @ 1548:ccf4fc8a6402
Import queue: Give milliseconds in JSON output, too.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Mon, 10 Dec 2018 16:49:34 +0100 |
parents | fbdd7c3cfeac |
children | de09bd3b5c05 |
line wrap: on
line source
// This is Free Software under GNU Affero General Public License v >= 3.0 // without warranty, see README.md and license for details. // // SPDX-License-Identifier: AGPL-3.0-or-later // License-Filename: LICENSES/AGPL-3.0.txt // // Copyright (C) 2018 by via donau // – Österreichische Wasserstraßen-Gesellschaft mbH // Software engineering by Intevation GmbH // // Author(s): // * Sascha L. Teichmann <sascha.teichmann@intevation.de> package octree import ( "bytes" "encoding/binary" "io" "log" "github.com/golang/snappy" ) type Builder 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 NewBuilder(t *Tin) *Builder { return &Builder{t: t} } func (tb *Builder) 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 *Builder) 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 *Builder) 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 } func (tb *Builder) writeTo(w io.Writer) error { out := snappy.NewBufferedWriter(w) if err := tb.t.Serialize(out); err != nil { return err } if err := tb.Serialize(out); err != nil { return err } return out.Flush() } func (tb *Builder) Bytes() ([]byte, error) { var buf bytes.Buffer if err := tb.writeTo(&buf); err != nil { return nil, err } return buf.Bytes(), nil } func (tb *Builder) Tree() *Tree { return &Tree{ EPSG: tb.t.EPSG, vertices: tb.t.Vertices, triangles: tb.t.Triangles, index: tb.index, Min: tb.t.Min, Max: tb.t.Max, } }