Mercurial > gemma

annotate pkg/octree/tree.go @ 4658:4bbfe3dd2ab5 stree-experiment

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Completed usage of STRTrees.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 14 Oct 2019 14:58:04 +0200
parents 3eda5a7215ab
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1017
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
1 // This is Free Software under GNU Affero General Public License v >= 3.0
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
2 // without warranty, see README.md and license for details.
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
3 //
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
4 // SPDX-License-Identifier: AGPL-3.0-or-later
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
5 // License-Filename: LICENSES/AGPL-3.0.txt
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
6 //
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
7 // Copyright (C) 2018 by via donau
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
8 // – Österreichische Wasserstraßen-Gesellschaft mbH
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
9 // Software engineering by Intevation GmbH
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
10 //
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
11 // Author(s):
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
a244b18cb916 Added GNU Affero General Public License.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 787
diff changeset
13
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
14 package octree
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
16 import (
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17 "math"
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 )
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
20 // Tree is an Octree holding triangles.
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
21 type Tree struct {
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
22 // EPSG is the projection.
726
5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 707
diff changeset
23 EPSG uint32
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
24
726
5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 707
diff changeset
25 vertices []Vertex
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26 triangles [][]int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 index []int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
29 // Min is the lower left corner of the bbox.
726
5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 707
diff changeset
30 Min Vertex
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
31 // Max is the upper right corner of the bbox.
726
5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 707
diff changeset
32 Max Vertex
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
33 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
35 type boxFrame struct {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
36 pos int32
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
37 Box2D
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
38 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
39
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
40 func (ot *Tree) Vertices() []Vertex {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
41 return ot.vertices
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
42 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
43
759
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
44 var scale = [4][4]float64{
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
45 {0.0, 0.0, 0.5, 0.5},
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
46 {0.5, 0.0, 1.0, 0.5},
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
47 {0.0, 0.5, 0.5, 1.0},
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
48 {0.5, 0.5, 1.0, 1.0},
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
49 }
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
50
4649
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
51 func (ot *Tree) Tin() *Tin {
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
52 return &Tin{
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
53 EPSG: ot.EPSG,
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
54 Vertices: ot.vertices,
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
55 Triangles: ot.triangles,
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
56 Min: ot.Min,
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
57 Max: ot.Max,
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
58 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
59 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
60
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
61 func (ot *Tree) FindUnused() map[int32]struct{} {
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
62
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
63 used := make(map[int32]struct{}, len(ot.triangles))
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
64 for i := int32(0); i < int32(len(ot.triangles)); i++ {
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
65 used[i] = struct{}{}
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
66 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
67
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
68 stack := []int32{1}
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
69
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
70 for len(stack) > 0 {
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
71 top := stack[len(stack)-1]
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
72 stack = stack[:len(stack)-1]
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
73
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
74 if top > 0 { // node
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
75 if index := ot.index[top:]; len(index) > 7 {
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
76 for _, idx := range index[:8] {
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
77 if idx != 0 {
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
78 stack = append(stack, idx)
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
79 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
80 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
81 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
82 } else { // leaf
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
83 pos := -top - 1
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
84 n := ot.index[pos]
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
85 indices := ot.index[pos+1 : pos+1+n]
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
86 for _, idx := range indices {
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
87 delete(used, idx)
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
88 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
89 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
90 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
91
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
92 return used
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
93 }
8f745c353784 Finished first version of conversion tool.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 4151
diff changeset
94
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
95 func (ot *Tree) Value(x, y float64) (float64, bool) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
96
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
97 // out of bounding box
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
98 if x < ot.Min.X || ot.Max.X < x ||
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
99 y < ot.Min.Y || ot.Max.Y < y {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
100 return 0, false
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
101 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
102
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
103 all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
104
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
105 stack := []boxFrame{{1, all}}
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
106
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
107 for len(stack) > 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
108 top := stack[len(stack)-1]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
109 stack = stack[:len(stack)-1]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
110
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
111 if top.pos > 0 { // node
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
112 if index := ot.index[top.pos:]; len(index) > 7 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
113 for i := 0; i < 4; i++ {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
114 a := index[i]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
115 b := index[i+4]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
116 if a == 0 && b == 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
117 continue
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
118 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
119 dx := top.X2 - top.X1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
120 dy := top.Y2 - top.Y1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
121 nbox := Box2D{
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
122 dx*scale[i][0] + top.X1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
123 dy*scale[i][1] + top.Y1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
124 dx*scale[i][2] + top.X1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
125 dy*scale[i][3] + top.Y1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
126 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
127 if nbox.Contains(x, y) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
128 if a != 0 {
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
129 stack = append(stack, boxFrame{a, nbox})
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
130 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
131 if b != 0 {
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
132 stack = append(stack, boxFrame{b, nbox})
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
133 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
134 break
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
135 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
136 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
137 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
138 } else { // leaf
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
139 pos := -top.pos - 1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
140 n := ot.index[pos]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
141 indices := ot.index[pos+1 : pos+1+n]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
142
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
143 for _, idx := range indices {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
144 tri := ot.triangles[idx]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
145 t := Triangle{
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
146 ot.vertices[tri[0]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
147 ot.vertices[tri[1]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
148 ot.vertices[tri[2]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
149 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
150 if t.Contains(x, y) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
151 return t.Plane3D().Z(x, y), true
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
152 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
153 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
154 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
155 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
156
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
157 return 0, false
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
158 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
159
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
160 // Vertical does a vertical cross cut from (x1, y1) to (x2, y2).
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
161 func (ot *Tree) Vertical(x1, y1, x2, y2 float64, fn func(*Triangle)) {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
162
774
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
163 box := Box2D{
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
164 X1: math.Min(x1, x2),
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
165 Y1: math.Min(y1, y2),
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
166 X2: math.Max(x1, x2),
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
167 Y2: math.Max(y1, y2),
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
168 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
169
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
170 // out of bounding box
774
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
171 if box.X2 < ot.Min.X || ot.Max.X < box.X1 ||
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
172 box.Y2 < ot.Min.Y || ot.Max.Y < box.Y1 {
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
173 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
174 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
175
774
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
176 line := NewPlane2D(x1, y1, x2, y2)
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
177
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
178 dupes := map[int32]struct{}{}
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
179
774
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
180 all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}
761
033975d49c90 Removed a bit debug output on vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 760
diff changeset
181 //log.Printf("area: %f\n", (box.x2-box.x1)*(box.y2-box.y1))
033975d49c90 Removed a bit debug output on vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 760
diff changeset
182 //log.Printf("all: %f\n", (all.x2-all.x1)*(all.y2-all.y1))
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
183
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
184 stack := []boxFrame{{1, all}}
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
185
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
186 for len(stack) > 0 {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
187 top := stack[len(stack)-1]
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
188 stack = stack[:len(stack)-1]
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
189
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
190 if top.pos > 0 { // node
1790
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
191 if index := ot.index[top.pos:]; len(index) > 7 {
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
192 for i := 0; i < 4; i++ {
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
193 a := index[i]
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
194 b := index[i+4]
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
195 if a == 0 && b == 0 {
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
196 continue
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
197 }
1790
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
198 dx := top.X2 - top.X1
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
199 dy := top.Y2 - top.Y1
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
200 nbox := Box2D{
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
201 dx*scale[i][0] + top.X1,
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
202 dy*scale[i][1] + top.Y1,
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
203 dx*scale[i][2] + top.X1,
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
204 dy*scale[i][3] + top.Y1,
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
205 }
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
206 if nbox.Intersects(box) && nbox.IntersectsPlane(line) {
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
207 if a != 0 {
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
208 stack = append(stack, boxFrame{a, nbox})
1790
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
209 }
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
210 if b != 0 {
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
211 stack = append(stack, boxFrame{b, nbox})
1790
fe1aa62195c2 Octree: Same emtry tree fix for horizontal as for vertical traversal. Re-worked both to be BCE friendly.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1788
diff changeset
212 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
213 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
214 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
215 }
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
216 } else { // leaf
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
217 pos := -top.pos - 1
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
218 n := ot.index[pos]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
219 indices := ot.index[pos+1 : pos+1+n]
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
220
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
221 for _, idx := range indices {
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
222 if _, found := dupes[idx]; found {
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
223 continue
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
224 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
225 tri := ot.triangles[idx]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
226 t := Triangle{
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
227 ot.vertices[tri[0]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
228 ot.vertices[tri[1]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
229 ot.vertices[tri[2]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
230 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
231
774
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
232 v0 := line.Eval(t[0].X, t[0].Y)
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
233 v1 := line.Eval(t[1].X, t[1].Y)
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
234 v2 := line.Eval(t[2].X, t[2].Y)
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
235
787
3d927e06b92c Triangle intersection. WIP. Currently interpolation is messed up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 778
diff changeset
236 if onPlane(v0) || onPlane(v1) || onPlane(v2) ||
759
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
237 sides(sides(sides(0, v0), v1), v2) == 3 {
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
238 fn(&t)
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
239 }
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
240 dupes[idx] = struct{}{}
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
241 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
242 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
243 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
244 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
245
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
246 // Horizontal does a horizontal cross cut.
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
247 func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) {
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
248
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
249 if h < ot.Min.Z || ot.Max.Z < h {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
250 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
251 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
252
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
253 type frame struct {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
254 pos int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
255 min float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
256 max float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
257 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
258
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
259 dupes := map[int32]struct{}{}
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
260
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
261 stack := []frame{{1, ot.Min.Z, ot.Max.Z}}
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
262
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
263 for len(stack) > 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
264 top := stack[len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
265 stack = stack[:len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
266
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
267 pos := top.pos
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
268 if pos == 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
269 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
270 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
271 min, max := top.min, top.max
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
272
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
273 if pos > 0 { // node
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
274 if mid := (max-min)*0.5 + min; h >= mid {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
275 pos += 4 // nodes with z-bit set
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
276 min = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
277 } else {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
278 max = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
279 }
2479
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
280 if pos < int32(len(ot.index)) {
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
281 if index := ot.index[pos:]; len(index) > 3 {
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
282 stack = append(stack,
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
283 frame{index[0], min, max},
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
284 frame{index[1], min, max},
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
285 frame{index[2], min, max},
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
286 frame{index[3], min, max})
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
287 }
1788
00f34a00e6d5 Octree: Don't crash in horizontal traversal if the tree is empty.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1692
diff changeset
288 }
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
289 } else { // leaf
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
290 pos = -pos - 1
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
291 n := ot.index[pos]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
292 //log.Printf("%d %d %d\n", pos, n, len(ot.index))
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
293 indices := ot.index[pos+1 : pos+1+n]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
294
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
295 for _, idx := range indices {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
296 if _, found := dupes[idx]; found {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
297 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
298 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
299 tri := ot.triangles[idx]
726
5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 707
diff changeset
300 t := Triangle{
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
301 ot.vertices[tri[0]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
302 ot.vertices[tri[1]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
303 ot.vertices[tri[2]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
304 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
305
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
306 if !(math.Min(t[0].Z, math.Min(t[1].Z, t[2].Z)) > h ||
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
307 math.Max(t[0].Z, math.Max(t[1].Z, t[2].Z)) < h) {
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
308 dupes[idx] = struct{}{}
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
309 fn(&t)
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
310 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
311 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
312 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
313 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
314 }