Mercurial > gemma

annotate cmd/octree2contour/octree.go @ 726:5af9ab39e715

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renamed a few types to uppercase names to prepare the move to the octree package.
author Sascha L. Teichmann <teichmann@intevation.de>
date Sat, 22 Sep 2018 21:34:12 +0200
parents 9db4ae29ded9
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 package main
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
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
7 type Octree struct {
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
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
18 func (ot *Octree) 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
19
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20 type frame struct {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21 pos int32
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22 min float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 max float64
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
24 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25
726
5af9ab39e715 Renamed a few types to uppercase names to prepare the move to the octree package.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 707
diff changeset
26 if h < ot.Min.z || ot.Max.z < h {
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 return
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29
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 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
31
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32 dupes := map[int32]struct{}{}
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 for len(stack) > 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 top := stack[len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36 stack = stack[:len(stack)-1]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38 pos := top.pos
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39 if pos == 0 {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42 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
43
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44 if pos > 0 { // node
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45 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
46 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
47 min = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
48 } else {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
49 max = mid
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
50 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
51 stack = append(stack,
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
52 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
53 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
54 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
55 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
56 } else { // leaf
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
57 pos = -pos - 1
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
58 n := ot.index[pos]
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
59 //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
60 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
61
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
62 for _, idx := range indices {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
63 if _, found := dupes[idx]; found {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
64 continue
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
65 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
66 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
67 t := Triangle{
707
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
68 ot.vertices[tri[0]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
69 ot.vertices[tri[1]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
70 ot.vertices[tri[2]],
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
71 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
72
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
73 if !(math.Min(t[0].z, math.Min(t[1].z, t[2].z)) > h ||
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
74 math.Max(t[0].z, math.Max(t[1].z, t[2].z)) < h) {
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
75 dupes[idx] = struct{}{}
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
76 fn(&t)
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
77 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
78 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
79 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
80 }
9db4ae29ded9 octree: Moved octree traveral code to own file.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
81 }