Mercurial > gemma

comparison pkg/octree/tree.go @ 758:0f3ba8bfa641

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Simplified vertical traversal of octree.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Tue, 25 Sep 2018 04:38:40 +0200
parents ef3dfe7037b3
children 46fe2ae761e8
comparison
equal deleted inserted replaced
757:ef3dfe7037b3 758:0f3ba8bfa641
98 box2d 98 box2d
99 } 99 }
100 100
101 dupes := map[int32]struct{}{} 101 dupes := map[int32]struct{}{}
102 102
103 stack := []frame{{1, box2d{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}}} 103 all := box2d{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}
104 log.Printf("area: %f\n", (box.x2-box.x1)*(box.y2-box.y1))
105 log.Printf("all: %f\n", (all.x2-all.x1)*(all.y2-all.y1))
106
107 stack := []frame{{1, all}}
104 108
105 var lineRejected int 109 var lineRejected int
110 var dupeRejected int
106 111
107 for len(stack) > 0 { 112 for len(stack) > 0 {
108 top := stack[len(stack)-1] 113 top := stack[len(stack)-1]
109 stack = stack[:len(stack)-1] 114 stack = stack[:len(stack)-1]
110 115
111 if top.pos > 0 { // node 116 if top.pos > 0 { // node
112 midx, midy := top.mid() 117 for i := int32(0); i < 4; i++ {
113 118 a := ot.index[top.pos+i]
114 var all uint 119 b := ot.index[top.pos+i+4]
115 for i := 0; i < 2; i++ { 120 if a == 0 && b == 0 {
116 var xcode uint 121 continue
117 if box.xi(i) > midx { 122 }
118 xcode = 1 123 dx := top.x2 - top.x1
119 } 124 dy := top.y2 - top.y1
120 for j := 0; j < 2; j++ { 125 nbox := box2d{
121 code := xcode 126 dx*scale[i][0] + top.x1,
122 if box.yi(j) > midy { 127 dy*scale[i][1] + top.y1,
123 code |= 2 128 dx*scale[i][2] + top.x1,
129 dy*scale[i][3] + top.y1,
130 }
131 if nbox.intersects(box) {
132 if a != 0 {
133 stack = append(stack, frame{a, nbox})
124 } 134 }
125 all |= 1 << code 135 if b != 0 {
126 } 136 stack = append(stack, frame{b, nbox})
127 }
128
129 dx := top.x2 - top.x1
130 dy := top.y2 - top.y1
131 for i := int32(0); all != 0; i++ {
132 if all&1 == 1 {
133 a := ot.index[top.pos+i]
134 b := ot.index[top.pos+i+4]
135 if a != 0 || b != 0 {
136 nbox := box2d{
137 dx*scale[i][0] + top.x1,
138 dy*scale[i][1] + top.y1,
139 dx*scale[i][2] + top.x1,
140 dy*scale[i][3] + top.y1,
141 }
142 if a != 0 {
143 stack = append(stack, frame{a, nbox})
144 }
145 if b != 0 {
146 stack = append(stack, frame{b, nbox})
147 }
148 } 137 }
149 } 138 }
150 all >>= 1
151 } 139 }
152 } else { // leaf 140 } else { // leaf
153 pos := -top.pos - 1 141 pos := -top.pos - 1
154 n := ot.index[pos] 142 n := ot.index[pos]
155 indices := ot.index[pos+1 : pos+1+n] 143 indices := ot.index[pos+1 : pos+1+n]
156 144
157 for _, idx := range indices { 145 for _, idx := range indices {
158 if _, found := dupes[idx]; found { 146 if _, found := dupes[idx]; found {
147 dupeRejected++
159 continue 148 continue
160 } 149 }
161 tri := ot.triangles[idx] 150 tri := ot.triangles[idx]
162 t := Triangle{ 151 t := Triangle{
163 ot.vertices[tri[0]], 152 ot.vertices[tri[0]],
182 math.Abs(v2) < eps || 171 math.Abs(v2) < eps ||
183 sides(sides(sides(0, 172 sides(sides(sides(0,
184 math.Signbit(v0)), 173 math.Signbit(v0)),
185 math.Signbit(v1)), 174 math.Signbit(v1)),
186 math.Signbit(v2)) == 3 { 175 math.Signbit(v2)) == 3 {
187 dupes[idx] = struct{}{}
188 fn(&t) 176 fn(&t)
189 } else { 177 } else {
190 lineRejected++ 178 lineRejected++
191 } 179 }
180 dupes[idx] = struct{}{}
192 } 181 }
193 } 182 }
194 } 183 }
195 184
196 // XXX: This value seems to high! 185 // XXX: This value seems to high!
197 log.Printf("rejected by line test: %d\n", lineRejected) 186 log.Printf("rejected by line test: %d %d %d\n",
187 lineRejected, len(dupes), dupeRejected)
198 } 188 }
199 189
200 func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) { 190 func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) {
201 191
202 if h < ot.Min.Z || ot.Max.Z < h { 192 if h < ot.Min.Z || ot.Max.Z < h {