Mercurial > gemma

annotate pkg/octree/tree.go @ 2499:62adfe9cbbde octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Be more precise with clipping nodes.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 04 Mar 2019 14:58:22 +0100
parents 12ed6feefea5
children 5c3e63cfd50d
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 (
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
17 "log"
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 "math"
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19 )
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
21 // 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
22 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
23 // 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
24 EPSG uint32
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25
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
26 vertices []Vertex
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 triangles [][]int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28 index []int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
30 // 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
31 Min Vertex
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
32 // 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
33 Max Vertex
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35
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
36 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
37 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
38 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
39 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
40
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
41 func (ot *Tree) Vertices() []Vertex {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
42 return ot.vertices
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
43 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
44
759
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
45 var scale = [4][4]float64{
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
46 {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
47 {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
48 {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
49 {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
50 }
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
51
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
52 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
53
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
54 log.Printf("info: num triangles: %d\n", len(ot.triangles))
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
55
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
56 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
57
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 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
59
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 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
61
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
62 var triangleTests int
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
63 var nodeTests int
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
64 var nodesClipped int
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
65 var trianglesClipped int
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
66 var nodesAllInside int
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
67
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
68 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 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
70 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
71 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
72
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 if top.pos > 0 { // node
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
74 nodeTests++
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
75 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
76 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
77 // all inside so nothing to clip.
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
78 nodesAllInside++
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
79 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
80 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
81 // all outside -> clip from tree.
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
82 nodesClipped++
2499
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
83 index := ot.index[top.pos:]
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
84 if len(index) > 8 {
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
85 index = index[:8]
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
86 }
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
87 for i := range index {
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
88 index[i] = 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
89 }
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 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
91 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
92 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
93 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
94 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
95 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
96 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
97 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
98 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
99 }
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 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
101 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
102 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
103 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
104 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
105 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
106 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
107 }
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 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
109 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
110 // all inside so nothing to clip.
2499
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
111 nodesAllInside++
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
112 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
113 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
114 // all are ouside -> clip from tree.
2499
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
115 nodesClipped++
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
116 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
117 index[i+4] = 0
2499
62adfe9cbbde Be more precise with clipping nodes.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2496
diff changeset
118 continue children
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
119 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
120 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
121 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
122 }
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 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
124 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
125 }
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 }
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 }
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 }
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 } 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
131 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
132 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
133 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
134 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
135 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
136 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
137 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
138 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
139 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
140 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
141 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
142 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
143 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
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 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
146 triChecks[triIndex] = what
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
147 triangleTests++
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
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 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
150 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
151 // 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
152 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
153 default:
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
154 trianglesClipped++
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
155 // 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
156 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
157 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
158 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
159 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
160 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
161 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
162 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
163 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
164 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
165 }
2496
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
166 log.Printf("info: node tests: %d\n", nodeTests)
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
167 log.Printf("info: nodes clipped: %d\n", nodesClipped)
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
168 log.Printf("info: nodes all inside: %d\n", nodesAllInside)
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
169 log.Printf("info: triangle tests: %d\n", triangleTests)
12ed6feefea5 Use octree clipping. Not working, yet!
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2488
diff changeset
170 log.Printf("info: triangle clipped: %d\n", trianglesClipped)
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
171 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2479
diff changeset
172
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
173 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
174
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
175 // out of bounding box
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
176 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
177 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
178 return 0, false
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
179 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
180
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
181 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
182
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
183 stack := []boxFrame{{1, all}}
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
184
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
185 for len(stack) > 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
186 top := stack[len(stack)-1]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
187 stack = stack[:len(stack)-1]
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 if top.pos > 0 { // node
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
190 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
191 for i := 0; i < 4; i++ {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
192 a := index[i]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
193 b := index[i+4]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
194 if a == 0 && b == 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
195 continue
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
196 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
197 dx := top.X2 - top.X1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
198 dy := top.Y2 - top.Y1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
199 nbox := Box2D{
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
200 dx*scale[i][0] + top.X1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
201 dy*scale[i][1] + top.Y1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
202 dx*scale[i][2] + top.X1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
203 dy*scale[i][3] + top.Y1,
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 nbox.Contains(x, y) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
206 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
207 stack = append(stack, boxFrame{a, nbox})
2466
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 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
210 stack = append(stack, boxFrame{b, nbox})
2466
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 break
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 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
215 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
216 } else { // leaf
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
217 pos := -top.pos - 1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
218 n := ot.index[pos]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
219 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
220
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
221 for _, idx := range indices {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
222 tri := ot.triangles[idx]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
223 t := Triangle{
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
224 ot.vertices[tri[0]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
225 ot.vertices[tri[1]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
226 ot.vertices[tri[2]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
227 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
228 if t.Contains(x, y) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
229 return t.Plane3D().Z(x, y), true
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
230 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
231 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
232 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
233 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
234
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
235 return 0, false
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
236 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
237
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
238 // 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
239 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
240
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
241 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
242 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
243 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
244 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
245 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
246 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
247
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
248 // 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
249 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
250 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
251 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
252 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
253
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
254 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
255
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
256 dupes := map[int32]struct{}{}
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
257
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
258 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
259 //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
260 //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
261
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
262 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
263
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
264 for len(stack) > 0 {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
265 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
266 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
267
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
268 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
269 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
270 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
271 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
272 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
273 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
274 continue
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
275 }
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
276 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
277 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
278 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
279 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
280 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
281 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
282 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
283 }
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
284 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
285 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
286 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
287 }
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
288 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
289 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
290 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
291 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
292 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
293 }
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
294 } else { // leaf
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
295 pos := -top.pos - 1
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
296 n := ot.index[pos]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
297 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
298
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
299 for _, idx := range indices {
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
300 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
301 continue
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
302 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
303 tri := ot.triangles[idx]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
304 t := Triangle{
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
305 ot.vertices[tri[0]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
306 ot.vertices[tri[1]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
307 ot.vertices[tri[2]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
308 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
309
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
310 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
311 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
312 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
313
787
3d927e06b92c Triangle intersection. WIP. Currently interpolation is messed up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 778
diff changeset
314 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
315 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
316 fn(&t)
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
317 }
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
318 dupes[idx] = struct{}{}
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
319 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
320 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
321 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
322 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
323
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
324 // 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
325 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
326
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
327 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
328 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
329 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
330
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
331 type frame struct {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
332 pos int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
333 min float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
334 max float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
335 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
336
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
337 dupes := map[int32]struct{}{}
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
338
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
339 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
340
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
341 for len(stack) > 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
342 top := stack[len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
343 stack = stack[:len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
344
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
345 pos := top.pos
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
346 if pos == 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
347 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
348 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
349 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
350
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
351 if pos > 0 { // node
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
352 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
353 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
354 min = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
355 } else {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
356 max = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
357 }
2479
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
358 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
359 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
360 stack = append(stack,
c85b16db8a02 Calculate better triangulation and store it into database.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2466
diff changeset
361 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
362 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
363 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
364 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
365 }
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
366 }
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
367 } else { // leaf
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
368 pos = -pos - 1
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
369 n := ot.index[pos]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
370 //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
371 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
372
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
373 for _, idx := range indices {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
374 if _, found := dupes[idx]; found {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
375 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
376 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
377 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
378 t := Triangle{
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
379 ot.vertices[tri[0]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
380 ot.vertices[tri[1]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
381 ot.vertices[tri[2]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
382 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
383
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
384 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
385 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
386 dupes[idx] = struct{}{}
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
387 fn(&t)
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
388 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
389 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
390 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
391 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
392 }