Mercurial > gemma

comparison pkg/octree/tree.go @ 728:e9d37300ce99

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renamed octree.go in octree package to tree.go.
author Sascha L. Teichmann <teichmann@intevation.de>
date Sat, 22 Sep 2018 21:58:15 +0200
parents pkg/octree/octree.go@41c8dc61f38f
children 1a1a8b5f2d02
comparison
equal deleted inserted replaced
727:41c8dc61f38f 728:e9d37300ce99
1 package octree
2
3 import (
4 "math"
5 )
6
7 type Tree struct {
8 EPSG uint32
9
10 vertices []Vertex
11 triangles [][]int32
12 index []int32
13
14 Min Vertex
15 Max Vertex
16 }
17
18 func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) {
19
20 type frame struct {
21 pos int32
22 min float64
23 max float64
24 }
25
26 if h < ot.Min.Z || ot.Max.Z < h {
27 return
28 }
29
30 stack := []frame{{1, ot.Min.Z, ot.Max.Z}}
31
32 dupes := map[int32]struct{}{}
33
34 for len(stack) > 0 {
35 top := stack[len(stack)-1]
36 stack = stack[:len(stack)-1]
37
38 pos := top.pos
39 if pos == 0 {
40 continue
41 }
42 min, max := top.min, top.max
43
44 if pos > 0 { // node
45 if mid := (max-min)*0.5 + min; h >= mid {
46 pos += 4 // nodes with z-bit set
47 min = mid
48 } else {
49 max = mid
50 }
51 stack = append(stack,
52 frame{ot.index[pos+0], min, max},
53 frame{ot.index[pos+1], min, max},
54 frame{ot.index[pos+2], min, max},
55 frame{ot.index[pos+3], min, max})
56 } else { // leaf
57 pos = -pos - 1
58 n := ot.index[pos]
59 //log.Printf("%d %d %d\n", pos, n, len(ot.index))
60 indices := ot.index[pos+1 : pos+1+n]
61
62 for _, idx := range indices {
63 if _, found := dupes[idx]; found {
64 continue
65 }
66 tri := ot.triangles[idx]
67 t := Triangle{
68 ot.vertices[tri[0]],
69 ot.vertices[tri[1]],
70 ot.vertices[tri[2]],
71 }
72
73 if !(math.Min(t[0].Z, math.Min(t[1].Z, t[2].Z)) > h ||
74 math.Max(t[0].Z, math.Max(t[1].Z, t[2].Z)) < h) {
75 dupes[idx] = struct{}{}
76 fn(&t)
77 }
78 }
79 }
80 }
81 }