Mercurial > gemma
annotate pkg/octree/tree.go @ 789:d43e61044ad8
Fill in last remaining corner cases in vertical triangle interpolation.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Thu, 27 Sep 2018 08:24:23 +0200 |
parents | 3d927e06b92c |
children | a244b18cb916 |
rev | line source |
---|---|
727
41c8dc61f38f
Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
726
diff
changeset
|
1 package octree |
707
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
2 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
3 import ( |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
4 "math" |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
5 ) |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
6 |
727
41c8dc61f38f
Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
726
diff
changeset
|
7 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
|
8 EPSG uint32 |
707
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
9 |
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
|
10 vertices []Vertex |
707
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
11 triangles [][]int32 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
12 index []int32 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
13 |
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
|
14 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
|
15 Max Vertex |
707
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
16 } |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
17 |
759
46fe2ae761e8
Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
758
diff
changeset
|
18 var scale = [4][4]float64{ |
46fe2ae761e8
Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
758
diff
changeset
|
19 {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
|
20 {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
|
21 {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
|
22 {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
|
23 } |
46fe2ae761e8
Check bounding boxes against plane, too. WIP
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
758
diff
changeset
|
24 |
755
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
25 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
|
26 |
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
|
27 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
|
28 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
|
29 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
|
30 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
|
31 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
|
32 } |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
33 |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
34 // 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
|
35 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
|
36 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
|
37 return |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
38 } |
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 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
|
41 |
755
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
42 type frame struct { |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
43 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
|
44 Box2D |
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 |
756
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
47 dupes := map[int32]struct{}{} |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
48 |
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
|
49 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
|
50 //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
|
51 //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
|
52 |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
53 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
|
54 |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
55 for len(stack) > 0 { |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
56 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
|
57 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
|
58 |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
59 if top.pos > 0 { // node |
758
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
60 for i := int32(0); i < 4; i++ { |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
61 a := ot.index[top.pos+i] |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
62 b := ot.index[top.pos+i+4] |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
63 if a == 0 && b == 0 { |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
64 continue |
755
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
65 } |
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
|
66 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
|
67 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
|
68 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
|
69 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
|
70 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
|
71 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
|
72 dy*scale[i][3] + top.Y1, |
758
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
73 } |
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
|
74 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
|
75 if a != 0 { |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
76 stack = append(stack, frame{a, nbox}) |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
77 } |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
78 if b != 0 { |
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
79 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
|
80 } |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
81 } |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
82 } |
756
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
83 } else { // leaf |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
84 pos := -top.pos - 1 |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
85 n := ot.index[pos] |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
86 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
|
87 |
756
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
88 for _, idx := range indices { |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
89 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
|
90 continue |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
91 } |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
92 tri := ot.triangles[idx] |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
93 t := Triangle{ |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
94 ot.vertices[tri[0]], |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
95 ot.vertices[tri[1]], |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
96 ot.vertices[tri[2]], |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
97 } |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
98 |
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
|
99 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
|
100 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
|
101 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
|
102 |
787
3d927e06b92c
Triangle intersection. WIP. Currently interpolation is messed up.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
778
diff
changeset
|
103 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
|
104 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
|
105 fn(&t) |
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
106 } |
758
0f3ba8bfa641
Simplified vertical traversal of octree.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
757
diff
changeset
|
107 dupes[idx] = struct{}{} |
756
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
108 } |
755
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
109 } |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
110 } |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
111 } |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
112 |
727
41c8dc61f38f
Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
726
diff
changeset
|
113 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
|
114 |
755
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
115 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
|
116 return |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
117 } |
1a1a8b5f2d02
Vertical traversal of octree for cross sections. WIP.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
728
diff
changeset
|
118 |
707
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
119 type frame struct { |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
120 pos int32 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
121 min float64 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
122 max float64 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
123 } |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
124 |
756
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
125 dupes := map[int32]struct{}{} |
707
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
126 |
756
5e14000829d1
Complete vertical octree traversal. Seems not very selective.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
755
diff
changeset
|
127 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
|
128 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
129 for len(stack) > 0 { |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
130 top := stack[len(stack)-1] |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
131 stack = stack[:len(stack)-1] |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
132 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
133 pos := top.pos |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
134 if pos == 0 { |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
135 continue |
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 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
|
138 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
139 if pos > 0 { // node |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
140 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
|
141 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
|
142 min = mid |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
143 } else { |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
144 max = mid |
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 stack = append(stack, |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
147 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
|
148 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
|
149 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
|
150 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
|
151 } else { // leaf |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
152 pos = -pos - 1 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
153 n := ot.index[pos] |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
154 //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
|
155 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
|
156 |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
157 for _, idx := range indices { |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
158 if _, found := dupes[idx]; found { |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
159 continue |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
160 } |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
161 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
|
162 t := Triangle{ |
707
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
163 ot.vertices[tri[0]], |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
164 ot.vertices[tri[1]], |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
165 ot.vertices[tri[2]], |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
166 } |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
167 |
727
41c8dc61f38f
Moved octree loading stuff to octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
726
diff
changeset
|
168 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
|
169 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
|
170 dupes[idx] = struct{}{} |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
171 fn(&t) |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
172 } |
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 } |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
175 } |
9db4ae29ded9
octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff
changeset
|
176 } |