Mercurial > gemma

annotate pkg/octree/tree.go @ 2493:e3487fa9284d octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merged default into octree-diff branch.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 04 Mar 2019 11:56:07 +0100
parents cb55d7eaaa36
children 12ed6feefea5
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
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
51 func (ot *Tree) Clip(p *Polygon) {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
52
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
53 all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
54
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
55 stack := []boxFrame{{1, all}}
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
56
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
57 triChecks := make(map[int32]IntersectionType)
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
58
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
59 frames:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
60 for len(stack) > 0 {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
61 top := stack[len(stack)-1]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
62 stack = stack[:len(stack)-1]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
63
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
64 if top.pos > 0 { // node
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
65 switch p.IntersectionBox2D(top.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
66 case IntersectionInside:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
67 // all inside so nothing to clip.
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
68 continue frames
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
69 case IntersectionOutSide:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
70 // all outside -> clip from tree.
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
71 if index := ot.index[top.pos:]; len(index) > 7 {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
72 for i := range index {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
73 index[i] = 0
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
74 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
75 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
76 continue frames
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
77 default: // Overlaps
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
78 if index := ot.index[top.pos:]; len(index) > 7 {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
79 children:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
80 for i := 0; i < 4; i++ {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
81 a := index[i]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
82 b := index[i+4]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
83 if a == 0 && b == 0 {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
84 continue
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
85 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
86 dx := top.X2 - top.X1
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
87 dy := top.Y2 - top.Y1
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
88 nbox := 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
89 dx*scale[i][0] + top.X1,
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
90 dy*scale[i][1] + top.Y1,
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
91 dx*scale[i][2] + top.X1,
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
92 dy*scale[i][3] + top.Y1,
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
93 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
94 switch p.IntersectionBox2D(nbox) {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
95 case IntersectionInside:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
96 // all inside so nothing to clip.
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
97 continue children
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
98 case IntersectionOutSide:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
99 // all are ouside -> clip from tree.
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
100 index[i] = 0
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
101 index[i+4] = 0
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
102 continue
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
103 default: // Overlaps
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
104 if a != 0 {
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 = append(stack, boxFrame{a, nbox})
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
106 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
107 if b != 0 {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
108 stack = append(stack, boxFrame{b, nbox})
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
109 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
110 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
111 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
112 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
113 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
114 } else { // leaf
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
115 pos := -top.pos - 1
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
116 n := ot.index[pos]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
117 indices := ot.index[pos+1 : pos+1+n]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
118 tris:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
119 for i := len(indices) - 1; i >= 0; i-- {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
120 triIndex := indices[i]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
121 what, found := triChecks[triIndex]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
122 if !found {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
123 tri := ot.triangles[triIndex]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
124 t := Triangle{
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
125 ot.vertices[tri[0]],
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
126 ot.vertices[tri[1]],
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
127 ot.vertices[tri[2]],
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
128 }
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 what = p.IntersectionWithTriangle(&t)
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
130 triChecks[triIndex] = what
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
131 }
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 switch what {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
133 case IntersectionInside:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
134 // triangle inside -> stay.
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
135 continue tris
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
136 default:
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
137 // outside or not fully covered -> remove.
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
138 if i < len(indices)-1 {
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
139 copy(indices[i:], indices[i+1:])
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
140 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
141 indices[len(indices)-1] = 0
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
142 indices = indices[:len(indices)-1]
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
143 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
144 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
145 ot.index[pos] = int32(len(indices))
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
146 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
147 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
148 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
149
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
150 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
151
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
152 // out of bounding box
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
153 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
154 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
155 return 0, false
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
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
158 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
159
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
160 stack := []boxFrame{{1, all}}
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
161
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
162 for len(stack) > 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
163 top := stack[len(stack)-1]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
164 stack = stack[:len(stack)-1]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
165
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
166 if top.pos > 0 { // node
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
167 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
168 for i := 0; i < 4; i++ {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
169 a := index[i]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
170 b := index[i+4]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
171 if a == 0 && b == 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
172 continue
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
173 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
174 dx := top.X2 - top.X1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
175 dy := top.Y2 - top.Y1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
176 nbox := Box2D{
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
177 dx*scale[i][0] + top.X1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
178 dy*scale[i][1] + top.Y1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
179 dx*scale[i][2] + top.X1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
180 dy*scale[i][3] + top.Y1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
181 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
182 if nbox.Contains(x, y) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
183 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
184 stack = append(stack, boxFrame{a, nbox})
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
185 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
186 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
187 stack = append(stack, boxFrame{b, nbox})
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
188 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
189 break
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
190 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
191 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
192 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
193 } else { // leaf
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
194 pos := -top.pos - 1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
195 n := ot.index[pos]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
196 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
197
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
198 for _, idx := range indices {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
199 tri := ot.triangles[idx]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
200 t := Triangle{
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
201 ot.vertices[tri[0]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
202 ot.vertices[tri[1]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
203 ot.vertices[tri[2]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
204 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
205 if t.Contains(x, y) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
206 return t.Plane3D().Z(x, y), true
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
207 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
208 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
209 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
210 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
211
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
212 return 0, false
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
213 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
214
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
215 // 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
216 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
217
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
218 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
219 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
220 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
221 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
222 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
223 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
224
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
225 // 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
226 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
227 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
228 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
229 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
230
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
231 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
232
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
233 dupes := map[int32]struct{}{}
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
234
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
235 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
236 //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
237 //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
238
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
239 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
240
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
241 for len(stack) > 0 {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
242 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
243 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
244
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
245 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
246 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
247 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
248 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
249 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
250 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
251 continue
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
252 }
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
253 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
254 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
255 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
256 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
257 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
258 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
259 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
260 }
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
261 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
262 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
263 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
264 }
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
265 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
266 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
267 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
268 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
269 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
270 }
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
271 } else { // leaf
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
272 pos := -top.pos - 1
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
273 n := ot.index[pos]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
274 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
275
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
276 for _, idx := range indices {
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
277 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
278 continue
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
279 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
280 tri := ot.triangles[idx]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
281 t := Triangle{
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
282 ot.vertices[tri[0]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
283 ot.vertices[tri[1]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
284 ot.vertices[tri[2]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
285 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
286
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
287 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
288 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
289 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
290
787
3d927e06b92c Triangle intersection. WIP. Currently interpolation is messed up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 778
diff changeset
291 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
292 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
293 fn(&t)
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
294 }
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
295 dupes[idx] = struct{}{}
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
296 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
297 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
298 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
299 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
300
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
301 // 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
302 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
303
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
304 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
305 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
306 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
307
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
308 type frame struct {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
309 pos int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
310 min float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
311 max float64
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
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
314 dupes := map[int32]struct{}{}
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
315
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
316 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
317
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
318 for len(stack) > 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
319 top := stack[len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
320 stack = stack[:len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
321
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
322 pos := top.pos
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
323 if pos == 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
324 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
325 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
326 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
327
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
328 if pos > 0 { // node
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
329 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
330 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
331 min = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
332 } else {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
333 max = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
334 }
2479
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
335 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
336 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
337 stack = append(stack,
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
338 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
339 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
340 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
341 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
342 }
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
343 }
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
344 } else { // leaf
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
345 pos = -pos - 1
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
346 n := ot.index[pos]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
347 //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
348 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
349
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
350 for _, idx := range indices {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
351 if _, found := dupes[idx]; found {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
352 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
353 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
354 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
355 t := Triangle{
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
356 ot.vertices[tri[0]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
357 ot.vertices[tri[1]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
358 ot.vertices[tri[2]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
359 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
360
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
361 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
362 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
363 dupes[idx] = struct{}{}
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
364 fn(&t)
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
365 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
366 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
367 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
368 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
369 }