Mercurial > gemma
changeset 758:0f3ba8bfa641
Simplified vertical traversal of octree.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Tue, 25 Sep 2018 04:38:40 +0200 |
parents | ef3dfe7037b3 |
children | 46fe2ae761e8 |
files | pkg/octree/tree.go |
diffstat | 1 files changed, 29 insertions(+), 39 deletions(-) [+] |
line wrap: on
line diff
--- a/pkg/octree/tree.go Tue Sep 25 03:59:39 2018 +0200 +++ b/pkg/octree/tree.go Tue Sep 25 04:38:40 2018 +0200 @@ -100,54 +100,42 @@ dupes := map[int32]struct{}{} - stack := []frame{{1, box2d{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y}}} + all := box2d{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y} + log.Printf("area: %f\n", (box.x2-box.x1)*(box.y2-box.y1)) + log.Printf("all: %f\n", (all.x2-all.x1)*(all.y2-all.y1)) + + stack := []frame{{1, all}} var lineRejected int + var dupeRejected int for len(stack) > 0 { top := stack[len(stack)-1] stack = stack[:len(stack)-1] if top.pos > 0 { // node - midx, midy := top.mid() - - var all uint - for i := 0; i < 2; i++ { - var xcode uint - if box.xi(i) > midx { - xcode = 1 - } - for j := 0; j < 2; j++ { - code := xcode - if box.yi(j) > midy { - code |= 2 - } - all |= 1 << code + for i := int32(0); i < 4; i++ { + a := ot.index[top.pos+i] + b := ot.index[top.pos+i+4] + if a == 0 && b == 0 { + continue } - } - - dx := top.x2 - top.x1 - dy := top.y2 - top.y1 - for i := int32(0); all != 0; i++ { - if all&1 == 1 { - a := ot.index[top.pos+i] - b := ot.index[top.pos+i+4] - if a != 0 || b != 0 { - nbox := box2d{ - dx*scale[i][0] + top.x1, - dy*scale[i][1] + top.y1, - dx*scale[i][2] + top.x1, - dy*scale[i][3] + top.y1, - } - if a != 0 { - stack = append(stack, frame{a, nbox}) - } - if b != 0 { - stack = append(stack, frame{b, nbox}) - } + dx := top.x2 - top.x1 + dy := top.y2 - top.y1 + nbox := box2d{ + dx*scale[i][0] + top.x1, + dy*scale[i][1] + top.y1, + dx*scale[i][2] + top.x1, + dy*scale[i][3] + top.y1, + } + if nbox.intersects(box) { + if a != 0 { + stack = append(stack, frame{a, nbox}) + } + if b != 0 { + stack = append(stack, frame{b, nbox}) } } - all >>= 1 } } else { // leaf pos := -top.pos - 1 @@ -156,6 +144,7 @@ for _, idx := range indices { if _, found := dupes[idx]; found { + dupeRejected++ continue } tri := ot.triangles[idx] @@ -184,17 +173,18 @@ math.Signbit(v0)), math.Signbit(v1)), math.Signbit(v2)) == 3 { - dupes[idx] = struct{}{} fn(&t) } else { lineRejected++ } + dupes[idx] = struct{}{} } } } // XXX: This value seems to high! - log.Printf("rejected by line test: %d\n", lineRejected) + log.Printf("rejected by line test: %d %d %d\n", + lineRejected, len(dupes), dupeRejected) } func (ot *Tree) Horizontal(h float64, fn func(*Triangle)) {