Mercurial > gemma

annotate cmd/tin2octree/builder.go @ 674:120a82bd9953 octree

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
octree: Added loading frame for contour generation.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Wed, 19 Sep 2018 13:26:30 +0200
parents 010cc30fdf48
children 1cb565d244cf
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
661
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 package main
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
2
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
3 import (
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
4 "encoding/binary"
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
5 "io"
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
6 "log"
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
7 )
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
8
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
9 type treeBuilder struct {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10 t *tin
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 nodes int
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
12 leaves int
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
13 index []int32
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
14 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
16 var cubes = [8][2]vertex{
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17 {{0.0, 0.0, 0.0}, {0.5, 0.5, 0.5}},
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 {{0.5, 0.0, 0.0}, {1.0, 0.5, 0.5}},
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19 {{0.0, 0.0, 0.5}, {0.5, 0.5, 1.0}},
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20 {{0.0, 0.5, 0.5}, {0.5, 1.0, 1.0}},
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21 {{0.5, 0.0, 0.0}, {1.0, 0.5, 0.5}},
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22 {{0.5, 0.5, 0.0}, {1.0, 1.0, 0.5}},
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23 {{0.5, 0.0, 0.5}, {1.0, 0.5, 1.0}},
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
24 {{0.5, 0.5, 0.5}, {1.0, 1.0, 1.0}},
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27 func (tb *treeBuilder) build() {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29 triangles := make([]int32, len(tb.t.triangles))
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30 for i := range triangles {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
31 triangles[i] = int32(i)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
33
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34 tb.index = append(tb.index, 0)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36 tb.buildRecursive(triangles, tb.t.min, tb.t.max, 0)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 tb.index[0] = int32(len(tb.index))
674
120a82bd9953 octree: Added loading frame for contour generation.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 671
diff changeset
38 log.Printf("num nodes: %d\n", tb.index[0])
661
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40 log.Printf("nodes: %d leaves: %d index %d\n",
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41 tb.nodes, tb.leaves, tb.index[0])
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44 func (tb *treeBuilder) buildRecursive(
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45 triangles []int32,
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
46 min, max vertex,
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
47 depth int,
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
48 ) int32 {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
49 if len(triangles) <= 16 || depth > 8 {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
50 pos := len(tb.index)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
51 tb.index = append(tb.index, int32(len(tb.index)))
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
52 tb.index = append(tb.index, triangles...)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
53 //log.Printf("leaf entries: %d (%d)\n", len(triangles), depth)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
54 tb.leaves++
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
55 return int32(-(pos + 1))
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
56 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
57
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
58 pos := len(tb.index)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
59 tb.index = append(tb.index, 0, 0, 0, 0)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
60
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
61 bbox := interpolate(min, max)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
62
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
63 bboxes := make([][2]vertex, len(cubes))
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
64
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
65 for i := range cubes {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
66 bboxes[i] = [2]vertex{
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
67 bbox(cubes[i][0]),
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
68 bbox(cubes[i][1]),
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
69 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
70 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
71
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
72 var quandrants [8][]int32
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
73
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
74 for _, tri := range triangles {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
75 triangle := tb.t.triangles[tri]
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
76 v0 := tb.t.vertices[triangle[0]]
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
77 v1 := tb.t.vertices[triangle[1]]
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
78 v2 := tb.t.vertices[triangle[2]]
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
79
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
80 l := v0
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
81 l.minimize(v1)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
82 l.minimize(v2)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
83
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
84 h := v0
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
85 h.maximize(v1)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
86 h.maximize(v2)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
87
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
88 for i := range bboxes {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
89 if !(h.less(bboxes[i][0]) || bboxes[i][1].less(l)) {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
90 quandrants[i] = append(quandrants[i], tri)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
91 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
92 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
93 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
94
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
95 for i := range quandrants {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
96 if len(quandrants[i]) > 0 {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
97 child := tb.buildRecursive(
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
98 quandrants[i],
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
99 bboxes[i][0], bboxes[i][1],
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
100 depth+1)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
101 tb.index[pos+i] = child
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
102 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
103 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
104 tb.nodes++
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
105 return int32(pos)
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
106 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
107
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
108 func (tb *treeBuilder) Serialize(w io.Writer) error {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
109 var buf [binary.MaxVarintLen32]byte
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
110
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
111 if err := binary.Write(w, binary.LittleEndian, tb.index[0]); err != nil {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
112 return err
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
113 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
114
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
115 var last int32
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
116 var written int
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
117
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
118 for _, x := range tb.index[1:] {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
119 delta := x - last
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
120 n := binary.PutVarint(buf[:], int64(delta))
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
121 for p := buf[:n]; len(p) > 0; p = p[n:] {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
122 var err error
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
123 if n, err = w.Write(p); err != nil {
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
124 return err
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
125 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
126 written += n
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
127 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
128
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
129 last = x
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
130 }
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
131 log.Printf("compressed octree index in bytes: %d (%d)\n",
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
132 written, 4*len(tb.index))
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
133
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
134 return nil
af1d4d44a88a Experimental tin octree indexer.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
135 }