Mercurial > gemma
diff pkg/octree/tree.go @ 2466:a1e751c08c56 octree-diff
Calculate difference on single core.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Mon, 25 Feb 2019 18:21:33 +0100 |
parents | fe1aa62195c2 |
children | c85b16db8a02 |
line wrap: on
line diff
--- a/pkg/octree/tree.go Mon Feb 25 17:02:33 2019 +0100 +++ b/pkg/octree/tree.go Mon Feb 25 18:21:33 2019 +0100 @@ -32,6 +32,10 @@ Max Vertex } +func (ot *Tree) Vertices() []Vertex { + return ot.vertices +} + var scale = [4][4]float64{ {0.0, 0.0, 0.5, 0.5}, {0.5, 0.0, 1.0, 0.5}, @@ -39,6 +43,76 @@ {0.5, 0.5, 1.0, 1.0}, } +func (ot *Tree) Value(x, y float64) (float64, bool) { + + // out of bounding box + if x < ot.Min.X || ot.Max.X < x || + y < ot.Min.Y || ot.Max.Y < y { + return 0, false + } + + type frame struct { + pos int32 + Box2D + } + + all := Box2D{ot.Min.X, ot.Min.Y, ot.Max.X, ot.Max.Y} + + stack := []frame{{1, all}} + + for len(stack) > 0 { + top := stack[len(stack)-1] + stack = stack[:len(stack)-1] + + if top.pos > 0 { // node + if index := ot.index[top.pos:]; len(index) > 7 { + for i := 0; i < 4; i++ { + a := index[i] + b := index[i+4] + if a == 0 && b == 0 { + continue + } + 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.Contains(x, y) { + if a != 0 { + stack = append(stack, frame{a, nbox}) + } + if b != 0 { + stack = append(stack, frame{b, nbox}) + } + break + } + } + } + } else { // leaf + pos := -top.pos - 1 + n := ot.index[pos] + indices := ot.index[pos+1 : pos+1+n] + + for _, idx := range indices { + tri := ot.triangles[idx] + t := Triangle{ + ot.vertices[tri[0]], + ot.vertices[tri[1]], + ot.vertices[tri[2]], + } + if t.Contains(x, y) { + return t.Plane3D().Z(x, y), true + } + } + } + } + + return 0, false +} + // Vertical does a vertical cross cut from (x1, y1) to (x2, y2). func (ot *Tree) Vertical(x1, y1, x2, y2 float64, fn func(*Triangle)) {