Mercurial > gemma

comparison cmd/octree2contour/loader.go @ 707:9db4ae29ded9 octree

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
octree: Moved octree traveral code to own file.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Fri, 21 Sep 2018 11:02:24 +0200
parents be90ab542aa7
children 5af9ab39e715
comparison
equal deleted inserted replaced
704:fe0889460e97 707:9db4ae29ded9
8 "math" 8 "math"
9 "os" 9 "os"
10 10
11 "github.com/golang/snappy" 11 "github.com/golang/snappy"
12 ) 12 )
13
14 type octree struct {
15 epsg uint32
16
17 vertices []vertex
18 triangles [][]int32
19 index []int32
20
21 min vertex
22 max vertex
23 }
24 13
25 func (v *vertex) read(r io.Reader) error { 14 func (v *vertex) read(r io.Reader) error {
26 var buf [8]byte 15 var buf [8]byte
27 b := buf[:] 16 b := buf[:]
28 if _, err := io.ReadFull(r, b); err != nil { 17 if _, err := io.ReadFull(r, b); err != nil {
127 } 116 }
128 117
129 return tree, nil 118 return tree, nil
130 } 119 }
131 120
132 func (ot *octree) horizontal(h float64, fn func(*triangle)) {
133
134 type frame struct {
135 pos int32
136 min float64
137 max float64
138 }
139
140 if h < ot.min.z || ot.max.z < h {
141 return
142 }
143
144 stack := []frame{{1, ot.min.z, ot.max.z}}
145
146 dupes := map[int32]struct{}{}
147
148 for len(stack) > 0 {
149 top := stack[len(stack)-1]
150 stack = stack[:len(stack)-1]
151
152 pos := top.pos
153 if pos == 0 {
154 continue
155 }
156 min, max := top.min, top.max
157
158 if pos > 0 { // node
159 if mid := (max-min)*0.5 + min; h >= mid {
160 pos += 4 // nodes with z-bit set
161 min = mid
162 } else {
163 max = mid
164 }
165 stack = append(stack,
166 frame{ot.index[pos+0], min, max},
167 frame{ot.index[pos+1], min, max},
168 frame{ot.index[pos+2], min, max},
169 frame{ot.index[pos+3], min, max})
170 } else { // leaf
171 pos = -pos - 1
172 n := ot.index[pos]
173 //log.Printf("%d %d %d\n", pos, n, len(ot.index))
174 indices := ot.index[pos+1 : pos+1+n]
175
176 for _, idx := range indices {
177 if _, found := dupes[idx]; found {
178 continue
179 }
180 tri := ot.triangles[idx]
181 t := triangle{
182 ot.vertices[tri[0]],
183 ot.vertices[tri[1]],
184 ot.vertices[tri[2]],
185 }
186
187 if !(math.Min(t[0].z, math.Min(t[1].z, t[2].z)) > h ||
188 math.Max(t[0].z, math.Max(t[1].z, t[2].z)) < h) {
189 dupes[idx] = struct{}{}
190 fn(&t)
191 }
192 }
193 }
194 }
195 }
196
197 func loadOctree(fname string) (*octree, error) { 121 func loadOctree(fname string) (*octree, error) {
198 122
199 f, err := os.Open(fname) 123 f, err := os.Open(fname)
200 if err != nil { 124 if err != nil {
201 return nil, err 125 return nil, err