Mercurial > gemma

comparison pkg/octree/tree.go @ 1879:9a2fbeaabd52 dev-pdf-generation

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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]