Mercurial > gemma
comparison pkg/octree/tree.go @ 1879:9a2fbeaabd52 dev-pdf-generation
merging in from branch default
author | Bernhard Reiter <bernhard@intevation.de> |
---|---|
date | Tue, 15 Jan 2019 10:07:10 +0100 |
parents | fe1aa62195c2 |
children | a1e751c08c56 |
comparison
equal
deleted
inserted
replaced
1878:f030182f82f1 | 1879:9a2fbeaabd52 |
---|---|
15 | 15 |
16 import ( | 16 import ( |
17 "math" | 17 "math" |
18 ) | 18 ) |
19 | 19 |
20 // Tree is an Octree holding triangles. | |
20 type Tree struct { | 21 type Tree struct { |
22 // EPSG is the projection. | |
21 EPSG uint32 | 23 EPSG uint32 |
22 | 24 |
23 vertices []Vertex | 25 vertices []Vertex |
24 triangles [][]int32 | 26 triangles [][]int32 |
25 index []int32 | 27 index []int32 |
26 | 28 |
29 // Min is the lower left corner of the bbox. | |
27 Min Vertex | 30 Min Vertex |
31 // Max is the upper right corner of the bbox. | |
28 Max Vertex | 32 Max Vertex |
29 } | 33 } |
30 | 34 |
31 var scale = [4][4]float64{ | 35 var scale = [4][4]float64{ |
32 {0.0, 0.0, 0.5, 0.5}, | 36 {0.0, 0.0, 0.5, 0.5}, |
33 {0.5, 0.0, 1.0, 0.5}, | 37 {0.5, 0.0, 1.0, 0.5}, |
34 {0.0, 0.5, 0.5, 1.0}, | 38 {0.0, 0.5, 0.5, 1.0}, |
35 {0.5, 0.5, 1.0, 1.0}, | 39 {0.5, 0.5, 1.0, 1.0}, |
36 } | 40 } |
37 | 41 |
42 // Vertical does a vertical cross cut from (x1, y1) to (x2, y2). | |
38 func (ot *Tree) Vertical(x1, y1, x2, y2 float64, fn func(*Triangle)) { | 43 func (ot *Tree) Vertical(x1, y1, x2, y2 float64, fn func(*Triangle)) { |
39 | 44 |
40 box := Box2D{ | 45 box := Box2D{ |
41 X1: math.Min(x1, x2), | 46 X1: math.Min(x1, x2), |
42 Y1: math.Min(y1, y2), | 47 Y1: math.Min(y1, y2), |
68 for len(stack) > 0 { | 73 for len(stack) > 0 { |
69 top := stack[len(stack)-1] | 74 top := stack[len(stack)-1] |
70 stack = stack[:len(stack)-1] | 75 stack = stack[:len(stack)-1] |
71 | 76 |
72 if top.pos > 0 { // node | 77 if top.pos > 0 { // node |
73 for i := int32(0); i < 4; i++ { | 78 if index := ot.index[top.pos:]; len(index) > 7 { |
74 a := ot.index[top.pos+i] | 79 for i := 0; i < 4; i++ { |
75 b := ot.index[top.pos+i+4] | 80 a := index[i] |
76 if a == 0 && b == 0 { | 81 b := index[i+4] |
77 continue | 82 if a == 0 && b == 0 { |
78 } | 83 continue |
79 dx := top.X2 - top.X1 | |
80 dy := top.Y2 - top.Y1 | |
81 nbox := Box2D{ | |
82 dx*scale[i][0] + top.X1, | |
83 dy*scale[i][1] + top.Y1, | |
84 dx*scale[i][2] + top.X1, | |
85 dy*scale[i][3] + top.Y1, | |
86 } | |
87 if nbox.Intersects(box) && nbox.IntersectsPlane(line) { | |
88 if a != 0 { | |
89 stack = append(stack, frame{a, nbox}) | |
90 } | 84 } |
91 if b != 0 { | 85 dx := top.X2 - top.X1 |
92 stack = append(stack, frame{b, nbox}) | 86 dy := top.Y2 - top.Y1 |
87 nbox := Box2D{ | |
88 dx*scale[i][0] + top.X1, | |
89 dy*scale[i][1] + top.Y1, | |
90 dx*scale[i][2] + top.X1, | |
91 dy*scale[i][3] + top.Y1, | |
92 } | |
93 if nbox.Intersects(box) && nbox.IntersectsPlane(line) { | |
94 if a != 0 { | |
95 stack = append(stack, frame{a, nbox}) | |
96 } | |
97 if b != 0 { | |
98 stack = append(stack, frame{b, nbox}) | |
99 } | |
93 } | 100 } |
94 } | 101 } |
95 } | 102 } |
96 } else { // leaf | 103 } else { // leaf |
97 pos := -top.pos - 1 | 104 pos := -top.pos - 1 |
121 } | 128 } |
122 } | 129 } |
123 } | 130 } |
124 } | 131 } |
125 | 132 |
133 // Horizontal does a horizontal cross cut. | |
126 func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) { | 134 func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) { |
127 | 135 |
128 if h < ot.Min.Z || ot.Max.Z < h { | 136 if h < ot.Min.Z || ot.Max.Z < h { |
129 return | 137 return |
130 } | 138 } |
154 pos += 4 // nodes with z-bit set | 162 pos += 4 // nodes with z-bit set |
155 min = mid | 163 min = mid |
156 } else { | 164 } else { |
157 max = mid | 165 max = mid |
158 } | 166 } |
159 stack = append(stack, | 167 if index := ot.index[pos:]; len(index) > 3 { |
160 frame{ot.index[pos+0], min, max}, | 168 stack = append(stack, |
161 frame{ot.index[pos+1], min, max}, | 169 frame{index[0], min, max}, |
162 frame{ot.index[pos+2], min, max}, | 170 frame{index[1], min, max}, |
163 frame{ot.index[pos+3], min, max}) | 171 frame{index[2], min, max}, |
172 frame{index[3], min, max}) | |
173 } | |
164 } else { // leaf | 174 } else { // leaf |
165 pos = -pos - 1 | 175 pos = -pos - 1 |
166 n := ot.index[pos] | 176 n := ot.index[pos] |
167 //log.Printf("%d %d %d\n", pos, n, len(ot.index)) | 177 //log.Printf("%d %d %d\n", pos, n, len(ot.index)) |
168 indices := ot.index[pos+1 : pos+1+n] | 178 indices := ot.index[pos+1 : pos+1+n] |