Mercurial > gemma

annotate pkg/octree/tree.go @ 2478:930ca9c4e2a7 octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed concurrent octree builder. The iso line cuts are now in the same quantity order of line segments but still differ. Need to have a closer look once we serve the data.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Thu, 28 Feb 2019 12:34:47 +0100
parents a1e751c08c56
children c85b16db8a02
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
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
35 func (ot *Tree) Vertices() []Vertex {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
36 return ot.vertices
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
37 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
38
759
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
39 var scale = [4][4]float64{
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
40 {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
41 {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
42 {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
43 {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
44 }
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
45
2466
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
46 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
47
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
48 // out of bounding box
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
49 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
50 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
51 return 0, false
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
52 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
53
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
54 type frame struct {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
55 pos int32
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
56 Box2D
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
57 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
58
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
59 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
60
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
61 stack := []frame{{1, all}}
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
62
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
63 for len(stack) > 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
64 top := stack[len(stack)-1]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
65 stack = stack[:len(stack)-1]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
66
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
67 if top.pos > 0 { // node
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
68 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
69 for i := 0; i < 4; i++ {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
70 a := index[i]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
71 b := index[i+4]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
72 if a == 0 && b == 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
73 continue
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
74 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
75 dx := top.X2 - top.X1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
76 dy := top.Y2 - top.Y1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
77 nbox := Box2D{
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
78 dx*scale[i][0] + top.X1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
79 dy*scale[i][1] + top.Y1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
80 dx*scale[i][2] + top.X1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
81 dy*scale[i][3] + top.Y1,
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
82 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
83 if nbox.Contains(x, y) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
84 if a != 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
85 stack = append(stack, frame{a, nbox})
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
86 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
87 if b != 0 {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
88 stack = append(stack, frame{b, nbox})
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
89 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
90 break
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
91 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
92 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
93 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
94 } else { // leaf
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
95 pos := -top.pos - 1
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
96 n := ot.index[pos]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
97 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
98
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
99 for _, idx := range indices {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
100 tri := ot.triangles[idx]
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
101 t := Triangle{
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
102 ot.vertices[tri[0]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
103 ot.vertices[tri[1]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
104 ot.vertices[tri[2]],
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
105 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
106 if t.Contains(x, y) {
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
107 return t.Plane3D().Z(x, y), true
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
108 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
109 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
110 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
111 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
112
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
113 return 0, false
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
114 }
a1e751c08c56 Calculate difference on single core.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1790
diff changeset
115
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
116 // 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
117 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
118
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
119 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
120 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
121 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
122 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
123 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
124 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
125
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
126 // 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
127 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
128 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
129 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
130 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
131
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
132 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
133
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
134 type frame struct {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
135 pos int32
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
136 Box2D
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
137 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
138
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
139 dupes := map[int32]struct{}{}
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
140
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
141 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
142 //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
143 //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
144
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
145 stack := []frame{{1, all}}
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
146
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
147 for len(stack) > 0 {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
148 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
149 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
150
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
151 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
152 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
153 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
154 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
155 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
156 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
157 continue
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
158 }
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
159 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
160 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
161 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
162 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
163 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
164 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
165 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
166 }
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
167 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
168 if a != 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
169 stack = append(stack, frame{a, nbox})
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
170 }
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
171 if 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
172 stack = append(stack, frame{b, nbox})
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
173 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
174 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
175 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
176 }
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
177 } else { // leaf
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
178 pos := -top.pos - 1
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
179 n := ot.index[pos]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
180 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
181
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
182 for _, idx := range indices {
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
183 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
184 continue
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
185 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
186 tri := ot.triangles[idx]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
187 t := Triangle{
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
188 ot.vertices[tri[0]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
189 ot.vertices[tri[1]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
190 ot.vertices[tri[2]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
191 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
192
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
193 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
194 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
195 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
196
787
3d927e06b92c Triangle intersection. WIP. Currently interpolation is messed up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 778
diff changeset
197 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
198 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
199 fn(&t)
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
200 }
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
201 dupes[idx] = struct{}{}
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
202 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
203 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
204 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
205 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
206
1692
f4dcbe8941a1 Octree: Resolved the remaing golint issues with this package.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 1017
diff changeset
207 // 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
208 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
209
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
210 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
211 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
212 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
213
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
214 type frame struct {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
215 pos int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
216 min float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
217 max float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
218 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
219
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
220 dupes := map[int32]struct{}{}
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
221
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
222 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
223
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
224 for len(stack) > 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
225 top := stack[len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
226 stack = stack[:len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
227
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
228 pos := top.pos
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
229 if pos == 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
230 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
231 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
232 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
233
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
234 if pos > 0 { // node
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
235 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
236 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
237 min = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
238 } else {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
239 max = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
240 }
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
241 if index := ot.index[pos:]; len(index) > 3 {
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
242 stack = append(stack,
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
243 frame{index[0], min, max},
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
244 frame{index[1], min, max},
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
245 frame{index[2], min, max},
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 frame{index[3], min, max})
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
247 }
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
248 } else { // leaf
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
249 pos = -pos - 1
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
250 n := ot.index[pos]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
251 //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
252 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
253
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
254 for _, idx := range indices {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
255 if _, found := dupes[idx]; found {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
256 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
257 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
258 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
259 t := Triangle{
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
260 ot.vertices[tri[0]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
261 ot.vertices[tri[1]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
262 ot.vertices[tri[2]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
263 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
264
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
265 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
266 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
267 dupes[idx] = struct{}{}
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
268 fn(&t)
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
269 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
270 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
271 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
272 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
273 }