Mercurial > gemma
diff pkg/octree/builder.go @ 3953:4233570de212
Building octrees: Don't cause havok by building ain overly large tree if the points are not really 3D.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Mon, 15 Jul 2019 17:49:50 +0200 |
parents | 1ec4c5633eb6 |
children |
line wrap: on
line diff
--- a/pkg/octree/builder.go Mon Jul 15 17:09:59 2019 +0200 +++ b/pkg/octree/builder.go Mon Jul 15 17:49:50 2019 +0200 @@ -37,7 +37,7 @@ type buildStep func(chan buildStep) -var cubes = [8][2]Vertex{ +var cubes = [8]Box{ makeCube(0), makeCube(1), makeCube(2), @@ -48,7 +48,7 @@ makeCube(7), } -func makeCube(i int) [2]Vertex { +func makeCube(i int) Box { var d Vertex if i&1 == 1 { d.X = 0.5 @@ -59,12 +59,19 @@ if i&4 == 4 { d.Z = 0.5 } - return [2]Vertex{ + return Box{ Vertex{0.0, 0.0, 0.0}.Add(d), Vertex{0.5, 0.5, 0.5}.Add(d), } } +func twoElseOne(b bool) int { + if b { + return 2 + } + return 1 +} + // NewBuilder creates a new Builder for a TIN. func NewBuilder(t *Tin) *Builder { return &Builder{t: t} @@ -143,15 +150,28 @@ parent(tb.buildRecursive(triangles, min, max, depth)) return } + box := Box{min, max} - bbox := Interpolate(min, max) + xLimit := twoElseOne(box.HasX()) + yLimit := twoElseOne(box.HasY()) + zLimit := twoElseOne(box.HasZ()) - bboxes := make([][2]Vertex, len(cubes)) + indices := make([]byte, 0, 8) + + bbox := box.Interpolate() - for i := range cubes { - bboxes[i] = [2]Vertex{ - bbox(cubes[i][0]), - bbox(cubes[i][1]), + var bboxes [8]Box + + for x := 0; x < xLimit; x++ { + for y := 0; y < yLimit; y++ { + for z := 0; z < zLimit; z++ { + idx := byte(z<<2 | y<<1 | x) + bboxes[idx] = Box{ + bbox(cubes[idx][0]), + bbox(cubes[idx][1]), + } + indices = append(indices, idx) + } } } @@ -171,7 +191,7 @@ h.Maximize(v1) h.Maximize(v2) - for i := range bboxes { + for _, i := range indices { if !(h.Less(bboxes[i][0]) || bboxes[i][1].Less(l)) { quandrants[i] = append(quandrants[i], tri) } @@ -179,7 +199,7 @@ } used := new(int32) - for i := range quandrants { + for _, i := range indices { if len(quandrants[i]) > 0 { *used++ } @@ -187,7 +207,12 @@ pos := tb.allocNode() - for i := range quandrants { + if *used == 0 { + parent(pos) + return + } + + for _, i := range indices { if len(quandrants[i]) > 0 { j := int32(i) parent := func(v int32) { @@ -239,14 +264,28 @@ return int32(-(pos + 1)) } - bbox := Interpolate(min, max) + box := Box{min, max} - bboxes := make([][2]Vertex, len(cubes)) + xLimit := twoElseOne(box.HasX()) + yLimit := twoElseOne(box.HasY()) + zLimit := twoElseOne(box.HasZ()) + + indices := make([]byte, 0, 8) + + bbox := box.Interpolate() - for i := range cubes { - bboxes[i] = [2]Vertex{ - bbox(cubes[i][0]), - bbox(cubes[i][1]), + var bboxes [8]Box + + for x := 0; x < xLimit; x++ { + for y := 0; y < yLimit; y++ { + for z := 0; z < zLimit; z++ { + idx := byte(z<<2 | y<<1 | x) + bboxes[idx] = Box{ + bbox(cubes[idx][0]), + bbox(cubes[idx][1]), + } + indices = append(indices, idx) + } } } @@ -266,7 +305,7 @@ h.Maximize(v1) h.Maximize(v2) - for i := range bboxes { + for _, i := range indices { if !(h.Less(bboxes[i][0]) || bboxes[i][1].Less(l)) { quandrants[i] = append(quandrants[i], tri) } @@ -275,7 +314,7 @@ pos := tb.allocNode() - for i := range quandrants { + for _, i := range indices { if len(quandrants[i]) > 0 { child := tb.buildRecursive( quandrants[i],