Mercurial > gemma

comparison pkg/octree/tree.go @ 2496:12ed6feefea5 octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use octree clipping. Not working, yet!
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 04 Mar 2019 13:32:32 +0100
parents cb55d7eaaa36
children 62adfe9cbbde
comparison
equal deleted inserted replaced
2495:98bc023750cf 2496:12ed6feefea5
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de> 12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
13 13
14 package octree 14 package octree
15 15
16 import ( 16 import (
17 "log"
17 "math" 18 "math"
18 ) 19 )
19 20
20 // Tree is an Octree holding triangles. 21 // Tree is an Octree holding triangles.
21 type Tree struct { 22 type Tree struct {
48 {0.5, 0.5, 1.0, 1.0}, 49 {0.5, 0.5, 1.0, 1.0},
49 } 50 }
50 51
51 func (ot *Tree) Clip(p *Polygon) { 52 func (ot *Tree) Clip(p *Polygon) {
52 53
54 log.Printf("info: num triangles: %d\n", len(ot.triangles))
55
53 all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y} 56 all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}
54 57
55 stack := []boxFrame{{1, all}} 58 stack := []boxFrame{{1, all}}
56 59
57 triChecks := make(map[int32]IntersectionType) 60 triChecks := make(map[int32]IntersectionType)
61
62 var triangleTests int
63 var nodeTests int
64 var nodesClipped int
65 var trianglesClipped int
66 var nodesAllInside int
58 67
59 frames: 68 frames:
60 for len(stack) > 0 { 69 for len(stack) > 0 {
61 top := stack[len(stack)-1] 70 top := stack[len(stack)-1]
62 stack = stack[:len(stack)-1] 71 stack = stack[:len(stack)-1]
63 72
64 if top.pos > 0 { // node 73 if top.pos > 0 { // node
74 nodeTests++
65 switch p.IntersectionBox2D(top.Box2D) { 75 switch p.IntersectionBox2D(top.Box2D) {
66 case IntersectionInside: 76 case IntersectionInside:
67 // all inside so nothing to clip. 77 // all inside so nothing to clip.
78 nodesAllInside++
68 continue frames 79 continue frames
69 case IntersectionOutSide: 80 case IntersectionOutSide:
70 // all outside -> clip from tree. 81 // all outside -> clip from tree.
82 nodesClipped++
71 if index := ot.index[top.pos:]; len(index) > 7 { 83 if index := ot.index[top.pos:]; len(index) > 7 {
72 for i := range index { 84 for i := range index {
73 index[i] = 0 85 index[i] = 0
74 } 86 }
75 } 87 }
126 ot.vertices[tri[1]], 138 ot.vertices[tri[1]],
127 ot.vertices[tri[2]], 139 ot.vertices[tri[2]],
128 } 140 }
129 what = p.IntersectionWithTriangle(&t) 141 what = p.IntersectionWithTriangle(&t)
130 triChecks[triIndex] = what 142 triChecks[triIndex] = what
143 triangleTests++
131 } 144 }
132 switch what { 145 switch what {
133 case IntersectionInside: 146 case IntersectionInside:
134 // triangle inside -> stay. 147 // triangle inside -> stay.
135 continue tris 148 continue tris
136 default: 149 default:
150 trianglesClipped++
137 // outside or not fully covered -> remove. 151 // outside or not fully covered -> remove.
138 if i < len(indices)-1 { 152 if i < len(indices)-1 {
139 copy(indices[i:], indices[i+1:]) 153 copy(indices[i:], indices[i+1:])
140 } 154 }
141 indices[len(indices)-1] = 0 155 indices[len(indices)-1] = 0
143 } 157 }
144 } 158 }
145 ot.index[pos] = int32(len(indices)) 159 ot.index[pos] = int32(len(indices))
146 } 160 }
147 } 161 }
162 log.Printf("info: node tests: %d\n", nodeTests)
163 log.Printf("info: nodes clipped: %d\n", nodesClipped)
164 log.Printf("info: nodes all inside: %d\n", nodesAllInside)
165 log.Printf("info: triangle tests: %d\n", triangleTests)
166 log.Printf("info: triangle clipped: %d\n", trianglesClipped)
148 } 167 }
149 168
150 func (ot *Tree) Value(x, y float64) (float64, bool) { 169 func (ot *Tree) Value(x, y float64) (float64, bool) {
151 170
152 // out of bounding box 171 // out of bounding box