changeset 759:46fe2ae761e8

Check bounding boxes against plane, too. WIP
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Tue, 25 Sep 2018 08:32:32 +0200
parents 0f3ba8bfa641
children 6f913badee5d
files pkg/octree/tree.go
diffstat 1 files changed, 42 insertions(+), 22 deletions(-) [+]
line wrap: on
line diff
--- a/pkg/octree/tree.go	Tue Sep 25 04:38:40 2018 +0200
+++ b/pkg/octree/tree.go	Tue Sep 25 08:32:32 2018 +0200
@@ -46,13 +46,6 @@
 	return a.y2
 }
 
-var scale = [4][4]float64{
-	{0.0, 0.0, 0.5, 0.5},
-	{0.5, 0.0, 1.0, 0.5},
-	{0.0, 0.5, 0.5, 1.0},
-	{0.5, 0.5, 1.0, 1.0},
-}
-
 type plane2d struct {
 	a float64
 	b float64
@@ -76,6 +69,45 @@
 	return p.a*x + p.b*y + p.c
 }
 
+const epsPlane = 1e-5
+
+func sides(s int, x float64) int {
+	if math.Signbit(x) {
+		return s | 2
+	}
+	return s | 1
+}
+
+const eps = 1e-05
+
+func (a box2d) intersectsPlane(p plane2d) bool {
+	var s int
+	for i := 0; i < 2; i++ {
+		x := a.xi(i)
+		for j := 0; j < 2; j++ {
+			y := a.yi(j)
+			v := p.eval(x, y)
+			if math.Abs(v) < epsPlane {
+				log.Printf("on line")
+				return true
+			}
+			if s = sides(s, x); s == 3 {
+				log.Printf("... on both sides (djt)")
+				return true
+			}
+		}
+	}
+	log.Printf("side: %d\n", s)
+	return false
+}
+
+var scale = [4][4]float64{
+	{0.0, 0.0, 0.5, 0.5},
+	{0.5, 0.0, 1.0, 0.5},
+	{0.0, 0.5, 0.5, 1.0},
+	{0.5, 0.5, 1.0, 1.0},
+}
+
 func (ot *Tree) Vertical(x1, y1, x2, y2 float64, fn func(*Triangle)) {
 
 	box := box2d{
@@ -128,7 +160,7 @@
 					dx*scale[i][2] + top.x1,
 					dy*scale[i][3] + top.y1,
 				}
-				if nbox.intersects(box) {
+				if nbox.intersects(box) && nbox.intersectsPlane(line) {
 					if a != 0 {
 						stack = append(stack, frame{a, nbox})
 					}
@@ -158,21 +190,9 @@
 				v1 := line.eval(t[1].X, t[1].Y)
 				v2 := line.eval(t[2].X, t[2].Y)
 
-				sides := func(s int, b bool) int {
-					if b {
-						return s | 2
-					}
-					return s | 1
-				}
-
-				const eps = 1e-05
-
 				if math.Abs(v0) < eps || math.Abs(v1) < eps ||
 					math.Abs(v2) < eps ||
-					sides(sides(sides(0,
-						math.Signbit(v0)),
-						math.Signbit(v1)),
-						math.Signbit(v2)) == 3 {
+					sides(sides(sides(0, v0), v1), v2) == 3 {
 					fn(&t)
 				} else {
 					lineRejected++
@@ -182,7 +202,7 @@
 		}
 	}
 
-	// XXX: This value seems to high!
+	// XXX: This value seems too high!
 	log.Printf("rejected by line test: %d %d %d\n",
 		lineRejected, len(dupes), dupeRejected)
 }