Mercurial > gemma
changeset 678:7bb961d750b6 octree
octree: traverse horizontally over tree to find out which triangles to process.
| author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
|---|---|
| date | Wed, 19 Sep 2018 17:34:19 +0200 |
| parents | 1cb565d244cf |
| children | 899116318d58 |
| files | cmd/octree2contour/loader.go cmd/octree2contour/main.go cmd/tin2octree/builder.go |
| diffstat | 3 files changed, 73 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/cmd/octree2contour/loader.go Wed Sep 19 15:37:37 2018 +0200 +++ b/cmd/octree2contour/loader.go Wed Sep 19 17:34:19 2018 +0200 @@ -52,6 +52,8 @@ return nil, err } + log.Printf("EPSG: %d\n", tree.epsg) + if err := tree.min.read(r); err != nil { return nil, err } @@ -60,6 +62,10 @@ return nil, err } + log.Printf("BBOX: [[%f, %f, %f], [%f, %f, %f]]\n", + tree.min.x, tree.min.y, tree.min.z, + tree.max.x, tree.max.y, tree.max.z) + var numVertices uint32 if err := binary.Read(r, binary.LittleEndian, &numVertices); err != nil { return nil, err @@ -128,6 +134,64 @@ return tree, nil } +func (ot *octree) horizontal(h float64, fn func([]int32)) { + + type frame struct { + pos int32 + min float64 + max float64 + } + + if h < ot.min.z || h > ot.max.z { + return + } + + stack := []frame{{1, ot.min.z, ot.max.z}} + + for len(stack) > 0 { + top := stack[len(stack)-1] + stack = stack[:len(stack)-1] + + pos, min, max := top.pos, top.min, top.max + if pos == 0 { + continue + } + + if pos > 0 { // node + if mid := (max-min)*0.5 + min; h <= mid { + stack = append(stack, + frame{ot.index[pos+0], min, mid}, + frame{ot.index[pos+1], min, mid}, + frame{ot.index[pos+4], min, mid}, + frame{ot.index[pos+5], min, mid}) + } else { + stack = append(stack, + frame{ot.index[pos+2], mid, max}, + frame{ot.index[pos+3], mid, max}, + frame{ot.index[pos+6], mid, max}, + frame{ot.index[pos+7], mid, max}) + } + } else { // leaf + pos = -pos - 1 + n := ot.index[pos] + //log.Printf("%d %d %d\n", pos, n, len(ot.index)) + indices := ot.index[pos+1 : pos+1+n] + + for idx := range indices { + tri := ot.triangles[idx] + v0 := ot.vertices[tri[0]] + v1 := ot.vertices[tri[1]] + v2 := ot.vertices[tri[2]] + + if !(math.Min(v0.z, math.Min(v1.z, v2.z)) > h || + math.Max(v0.z, math.Max(v1.z, v2.z)) < h) { + fn(tri) + } + } + } + } +} + func loadOctree(fname string) (*octree, error) { f, err := os.Open(fname)
--- a/cmd/octree2contour/main.go Wed Sep 19 15:37:37 2018 +0200 +++ b/cmd/octree2contour/main.go Wed Sep 19 17:34:19 2018 +0200 @@ -13,7 +13,14 @@ ) func process(tree *octree) { - // TODO: Implement me! + if *one { + var triangles int + tree.horizontal(*step, func([]int32) { + triangles++ + }) + log.Printf("num triangles: %d\n", triangles) + } else { + } } func main() {
--- a/cmd/tin2octree/builder.go Wed Sep 19 15:37:37 2018 +0200 +++ b/cmd/tin2octree/builder.go Wed Sep 19 17:34:19 2018 +0200 @@ -48,7 +48,7 @@ ) int32 { if len(triangles) <= 16 || depth > 8 { pos := len(tb.index) - tb.index = append(tb.index, int32(len(tb.index))) + tb.index = append(tb.index, int32(len(triangles))) tb.index = append(tb.index, triangles...) //log.Printf("leaf entries: %d (%d)\n", len(triangles), depth) tb.leaves++