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)) {