Mercurial > gemma

annotate pkg/octree/tree.go @ 1328:d753ce6cf588

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
To make golint happier made context.Context to be the first argument in all calls.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Sun, 25 Nov 2018 16:26:41 +0100
parents a244b18cb916
children f4dcbe8941a1
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
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
20 type Tree struct {
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
21 EPSG uint32
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22
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 vertices []Vertex
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
24 triangles [][]int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25 index []int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26
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
27 Min Vertex
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
28 Max Vertex
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30
759
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
31 var scale = [4][4]float64{
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
32 {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
33 {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
34 {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
35 {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
36 }
46fe2ae761e8 Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 758
diff changeset
37
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
38 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
39
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
40 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
41 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
42 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
43 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
44 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
45 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
46
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
47 // 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
48 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
49 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
50 return
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
51 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
52
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
53 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
54
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
55 type frame struct {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
56 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
57 Box2D
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
58 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
59
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
60 dupes := map[int32]struct{}{}
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
61
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
62 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
63 //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
64 //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
65
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
66 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
67
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
68 for len(stack) > 0 {
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
69 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
70 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
71
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
72 if top.pos > 0 { // node
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
73 for i := int32(0); i < 4; i++ {
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
74 a := ot.index[top.pos+i]
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
75 b := ot.index[top.pos+i+4]
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
76 if a == 0 && b == 0 {
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
77 continue
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
78 }
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
79 dx := top.X2 - top.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
80 dy := top.Y2 - top.Y1
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
81 nbox := 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
82 dx*scale[i][0] + top.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
83 dy*scale[i][1] + top.Y1,
c55771b7c502 Moved Box2D and Plane2D into vertex.go and made to API public.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 761
diff changeset
84 dx*scale[i][2] + top.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
85 dy*scale[i][3] + top.Y1,
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
86 }
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
87 if nbox.Intersects(box) && nbox.IntersectsPlane(line) {
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
88 if a != 0 {
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
89 stack = append(stack, frame{a, nbox})
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
90 }
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
91 if b != 0 {
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
92 stack = append(stack, frame{b, nbox})
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
93 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
94 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
95 }
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
96 } else { // leaf
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
97 pos := -top.pos - 1
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
98 n := ot.index[pos]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
99 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
100
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
101 for _, idx := range indices {
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
102 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
103 continue
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
104 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
105 tri := ot.triangles[idx]
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
106 t := Triangle{
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
107 ot.vertices[tri[0]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
108 ot.vertices[tri[1]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
109 ot.vertices[tri[2]],
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
110 }
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
111
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
112 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
113 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
114 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
115
787
3d927e06b92c Triangle intersection. WIP. Currently interpolation is messed up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 778
diff changeset
116 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
117 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
118 fn(&t)
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
119 }
758
0f3ba8bfa641 Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 757
diff changeset
120 dupes[idx] = struct{}{}
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
121 }
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
122 }
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
123 }
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
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
126 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
127
755
1a1a8b5f2d02 Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 728
diff changeset
128 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
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
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
132 type frame struct {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
133 pos int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
134 min float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
135 max float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
136 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
137
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
138 dupes := map[int32]struct{}{}
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
139
756
5e14000829d1 Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 755
diff changeset
140 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
141
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
142 for len(stack) > 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
143 top := stack[len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
144 stack = stack[:len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
145
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
146 pos := top.pos
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
147 if pos == 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
148 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
149 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
150 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
151
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
152 if pos > 0 { // node
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
153 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
154 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
155 min = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
156 } else {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
157 max = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
158 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
159 stack = append(stack,
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
160 frame{ot.index[pos+0], min, max},
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
161 frame{ot.index[pos+1], min, max},
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
162 frame{ot.index[pos+2], min, max},
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
163 frame{ot.index[pos+3], min, max})
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
164 } else { // leaf
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
165 pos = -pos - 1
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
166 n := ot.index[pos]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
167 //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
168 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
169
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
170 for _, idx := range indices {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
171 if _, found := dupes[idx]; found {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
172 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
173 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
174 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
175 t := Triangle{
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
176 ot.vertices[tri[0]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
177 ot.vertices[tri[1]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
178 ot.vertices[tri[2]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
179 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
180
727
41c8dc61f38f Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 726
diff changeset
181 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
182 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
183 dupes[idx] = struct{}{}
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
184 fn(&t)
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
185 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
186 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
187 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
188 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
189 }