Mercurial > gemma

comparison pkg/octree/strtree.go @ 4646:89a72e0e2f9b stree-experiment

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add a method to serialize an STRTree.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Sun, 13 Oct 2019 15:45:39 +0200
parents a1a9b1eab57c
children 18331577a251
comparison
equal deleted inserted replaced
4643:a1a9b1eab57c 4646:89a72e0e2f9b
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de> 12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
13 13
14 package octree 14 package octree
15 15
16 import ( 16 import (
17 "bytes"
18 "encoding/binary"
19 "io"
20 "log"
17 "math" 21 "math"
18 "sort" 22 "sort"
23
24 "github.com/pierrec/lz4"
19 ) 25 )
20 26
21 const STRTreeDefaultEntries = 8 27 const STRTreeDefaultEntries = 8
22 28
23 type STRTree struct { 29 type STRTree struct {
42 n := s.index[top+1] 48 n := s.index[top+1]
43 stack = append(stack, s.index[top+2:top+2+n]...) 49 stack = append(stack, s.index[top+2:top+2+n]...)
44 } 50 }
45 } else { // leaf 51 } else { // leaf
46 top = -top - 1 52 top = -top - 1
53 if !s.bbox(top).Contains(x, y) {
54 continue
55 }
47 for i, n := int32(0), s.index[top+1]; i < n; i++ { 56 for i, n := int32(0), s.index[top+1]; i < n; i++ {
48 idx := s.index[top+2+i] 57 idx := s.index[top+2+i]
49 ti := s.tin.Triangles[idx] 58 ti := s.tin.Triangles[idx]
50 t := Triangle{ 59 t := Triangle{
51 vertices[ti[0]], 60 vertices[ti[0]],
148 } 157 }
149 158
150 return removed 159 return removed
151 } 160 }
152 161
162 func (s *STRTree) serializeIndex(w io.Writer) error {
163
164 if err := binary.Write(w, binary.LittleEndian, int32(len(s.index))); err != nil {
165 return err
166 }
167
168 if err := binary.Write(w, binary.LittleEndian, s.index[0]); err != nil {
169 return err
170 }
171
172 var buf [binary.MaxVarintLen32]byte
173
174 var last int32
175 var written int
176
177 for _, x := range s.index[1:] {
178 delta := x - last
179 n := binary.PutVarint(buf[:], int64(delta))
180 for p := buf[:n]; len(p) > 0; p = p[n:] {
181 var err error
182 if n, err = w.Write(p); err != nil {
183 return err
184 }
185 written += n
186 }
187
188 last = x
189 }
190 log.Printf("info: compressed index in bytes: %d %.2f (%d %.2f)\n",
191 written,
192 float64(written)/(1024*1024),
193 4*len(s.index),
194 float64(4*len(s.index))/(1024*1024),
195 )
196
197 return nil
198 }
199
200 func (s *STRTree) serializeBBoxes(w io.Writer) (rr error) {
201
202 if err := binary.Write(w, binary.LittleEndian, int32(len(s.bboxes))); err != nil {
203 return err
204 }
205
206 var err error
207
208 write := func(v float64) {
209 if err == nil {
210 err = binary.Write(w, binary.LittleEndian, math.Float64bits(v))
211 }
212 }
213 for _, box := range s.bboxes {
214 write(box.X1)
215 write(box.Y1)
216 write(box.X2)
217 write(box.Y2)
218 }
219
220 return err
221 }
222
223 func (s *STRTree) Bytes() ([]byte, error) {
224
225 var buf bytes.Buffer
226 w := lz4.NewWriter(&buf)
227
228 if err := s.tin.serialize(w); err != nil {
229 return nil, err
230 }
231
232 if err := binary.Write(w, binary.LittleEndian, uint8(s.Entries)); err != nil {
233 return nil, err
234 }
235
236 if err := s.serializeIndex(w); err != nil {
237 return nil, err
238 }
239
240 if err := s.serializeBBoxes(w); err != nil {
241 return nil, err
242 }
243
244 if err := w.Flush(); err != nil {
245 return nil, err
246 }
247
248 return buf.Bytes(), nil
249 }
250
153 func (s *STRTree) allTriangles(pos int32, tris map[int32]struct{}) { 251 func (s *STRTree) allTriangles(pos int32, tris map[int32]struct{}) {
154 stack := []int32{pos} 252 stack := []int32{pos}
155 for len(stack) > 0 { 253 for len(stack) > 0 {
156 top := stack[len(stack)-1] 254 top := stack[len(stack)-1]
157 stack = stack[:len(stack)-1] 255 stack = stack[:len(stack)-1]