Mercurial > gemma

comparison pkg/octree/builder.go @ 968:a4fe07a21ba7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Moved octree builder into octree package to be reusable by the sounding result import job.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Wed, 17 Oct 2018 16:00:49 +0200
parents
children b6fec8f85599
comparison
equal deleted inserted replaced
967:2025074ad835 968:a4fe07a21ba7
1 package octree
2
3 import (
4 "encoding/binary"
5 "io"
6 "log"
7
8 "github.com/golang/snappy"
9 )
10
11 type Builder struct {
12 t *Tin
13 nodes int
14 leaves int
15 index []int32
16 }
17
18 var cubes = [8][2]Vertex{
19 makeCube(0),
20 makeCube(1),
21 makeCube(2),
22 makeCube(3),
23 makeCube(4),
24 makeCube(5),
25 makeCube(6),
26 makeCube(7),
27 }
28
29 func makeCube(i int) [2]Vertex {
30 var d Vertex
31 if i&1 == 1 {
32 d.X = 0.5
33 }
34 if i&2 == 2 {
35 d.Y = 0.5
36 }
37 if i&4 == 4 {
38 d.Z = 0.5
39 }
40 return [2]Vertex{
41 Vertex{0.0, 0.0, 0.0}.Add(d),
42 Vertex{0.5, 0.5, 0.5}.Add(d),
43 }
44 }
45
46 func NewBuilder(t *Tin) *Builder {
47 return &Builder{t: t}
48 }
49
50 func (tb *Builder) Build() {
51
52 triangles := make([]int32, len(tb.t.Triangles))
53 for i := range triangles {
54 triangles[i] = int32(i)
55 }
56
57 tb.index = append(tb.index, 0)
58
59 tb.buildRecursive(triangles, tb.t.Min, tb.t.Max, 0)
60 tb.index[0] = int32(len(tb.index))
61 log.Printf("num nodes: %d\n", tb.index[0])
62
63 log.Printf("nodes: %d leaves: %d index %d\n",
64 tb.nodes, tb.leaves, tb.index[0])
65 }
66
67 func (tb *Builder) buildRecursive(
68 triangles []int32,
69 min, max Vertex,
70 depth int,
71 ) int32 {
72 if len(triangles) <= 16 || depth > 8 {
73 pos := len(tb.index)
74 tb.index = append(tb.index, int32(len(triangles)))
75 tb.index = append(tb.index, triangles...)
76 //log.Printf("leaf entries: %d (%d)\n", len(triangles), depth)
77 tb.leaves++
78 return int32(-(pos + 1))
79 }
80
81 pos := len(tb.index)
82 tb.index = append(tb.index,
83 0, 0, 0, 0,
84 0, 0, 0, 0)
85
86 bbox := Interpolate(min, max)
87
88 bboxes := make([][2]Vertex, len(cubes))
89
90 for i := range cubes {
91 bboxes[i] = [2]Vertex{
92 bbox(cubes[i][0]),
93 bbox(cubes[i][1]),
94 }
95 }
96
97 var quandrants [8][]int32
98
99 for _, tri := range triangles {
100 triangle := tb.t.Triangles[tri]
101 v0 := tb.t.Vertices[triangle[0]]
102 v1 := tb.t.Vertices[triangle[1]]
103 v2 := tb.t.Vertices[triangle[2]]
104
105 l := v0
106 l.Minimize(v1)
107 l.Minimize(v2)
108
109 h := v0
110 h.Maximize(v1)
111 h.Maximize(v2)
112
113 for i := range bboxes {
114 if !(h.Less(bboxes[i][0]) || bboxes[i][1].Less(l)) {
115 quandrants[i] = append(quandrants[i], tri)
116 }
117 }
118 }
119
120 for i := range quandrants {
121 if len(quandrants[i]) > 0 {
122 child := tb.buildRecursive(
123 quandrants[i],
124 bboxes[i][0], bboxes[i][1],
125 depth+1)
126 tb.index[pos+i] = child
127 }
128 }
129 tb.nodes++
130 return int32(pos)
131 }
132
133 func (tb *Builder) Serialize(w io.Writer) error {
134 var buf [binary.MaxVarintLen32]byte
135
136 if err := binary.Write(w, binary.LittleEndian, tb.index[0]); err != nil {
137 return err
138 }
139
140 var last int32
141 var written int
142
143 for _, x := range tb.index[1:] {
144 delta := x - last
145 n := binary.PutVarint(buf[:], int64(delta))
146 for p := buf[:n]; len(p) > 0; p = p[n:] {
147 var err error
148 if n, err = w.Write(p); err != nil {
149 return err
150 }
151 written += n
152 }
153
154 last = x
155 }
156 log.Printf("compressed octree index in bytes: %d (%d)\n",
157 written, 4*len(tb.index))
158
159 return nil
160 }
161
162 func (tb *Builder) WriteTo(w io.Writer) error {
163 out := snappy.NewBufferedWriter(w)
164 if err := tb.t.Serialize(out); err != nil {
165 return err
166 }
167 if err := tb.Serialize(out); err != nil {
168 return err
169 }
170 return out.Flush()
171 }