Mercurial > gemma

comparison pkg/octree/tree.go @ 755:1a1a8b5f2d02

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Vertical traversal of octree for cross sections. WIP.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 24 Sep 2018 18:41:29 +0200
parents e9d37300ce99
children 5e14000829d1
comparison
equal deleted inserted replaced
754:105c421f99b1 755:1a1a8b5f2d02
13 13
14 Min Vertex 14 Min Vertex
15 Max Vertex 15 Max Vertex
16 } 16 }
17 17
18 type box2d struct {
19 x1 float64
20 y1 float64
21 x2 float64
22 y2 float64
23 }
24
25 func (a box2d) intersects(b box2d) bool {
26 return !(a.x2 < a.x1 || a.x2 < b.x1 ||
27 a.y2 < a.y1 || a.y2 < b.y1)
28 }
29
30 func (a box2d) mid() (float64, float64) {
31 return (a.x2-a.x1)*0.5 + a.x1, (a.y2-a.y1)*0.5 + a.y1
32 }
33
34 func (a box2d) xi(i int) float64 {
35 if i == 0 {
36 return a.x1
37 }
38 return a.x2
39 }
40
41 func (a box2d) yi(i int) float64 {
42 if i == 0 {
43 return a.y1
44 }
45 return a.y2
46 }
47
48 var scale = [][]float64{
49 {0.0, 0.0, 0.5, 0.5},
50 {0.5, 0.0, 1.0, 0.5},
51 {0.0, 0.5, 0.5, 1.0},
52 {0.5, 0.5, 1.0, 1.0},
53 }
54
55 func (ot *Tree) Vertical(x1, y1, x2, y2 float64, fn func(*Triangle)) {
56
57 box := box2d{
58 x1: math.Min(x1, x2),
59 y1: math.Min(y1, y2),
60 x2: math.Max(x1, x2),
61 y2: math.Max(y1, y2),
62 }
63
64 // out of bounding box
65 if box.x2 < ot.Min.X || ot.Max.X < box.x1 ||
66 box.y2 < ot.Min.Y || ot.Max.Y < box.y1 {
67 return
68 }
69
70 type frame struct {
71 pos int32
72 box2d
73 }
74
75 stack := []frame{{1, box2d{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}}}
76
77 for len(stack) > 0 {
78 top := stack[len(stack)-1]
79 stack = stack[:len(stack)-1]
80
81 if top.pos > 0 { // node
82 midx, midy := top.mid()
83
84 var all uint
85 for i := 0; i < 2; i++ {
86 for j := 0; j < 2; j++ {
87 x, y := box.xi(i), box.yi(j)
88 var code uint
89 if x > midx {
90 code |= 1
91 }
92 if y > midy {
93 code |= 2
94 }
95 all |= 1 << code
96 }
97 }
98
99 dx := top.x2 - top.x1
100 dy := top.y2 - top.y1
101 for i := 0; all != 0; i++ {
102 if all&1 == 1 {
103 s := scale[i]
104 nbox := box2d{
105 dx*s[0] + top.x1,
106 dy*s[1] + top.y1,
107 dx*s[2] + top.x1,
108 dy*s[3] + top.y1,
109 }
110 // TODO: Push two frames to stack.
111 _ = nbox
112 }
113 all >>= 1
114 }
115
116 } else { // leaf
117 }
118 }
119 }
120
18 func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) { 121 func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) {
122
123 if h < ot.Min.Z || ot.Max.Z < h {
124 return
125 }
19 126
20 type frame struct { 127 type frame struct {
21 pos int32 128 pos int32
22 min float64 129 min float64
23 max float64 130 max float64
24 }
25
26 if h < ot.Min.Z || ot.Max.Z < h {
27 return
28 } 131 }
29 132
30 stack := []frame{{1, ot.Min.Z, ot.Max.Z}} 133 stack := []frame{{1, ot.Min.Z, ot.Max.Z}}
31 134
32 dupes := map[int32]struct{}{} 135 dupes := map[int32]struct{}{}