Does GKOctree have bugs?

Question

Created Dec ’20

Replies 3

Boosts 0

Views 1.3k

Participants 3

Hi, I'm newbie of swift, iOS and this forum.
Although I've just already same reply in the following issue, my reply doesn't appear. So please let me ask here.

https://developer.apple.com/forums/thread/127384

GKOctree doesn't work at all. There seems to be many problems.
Here is reproduction code.

Code Block swiftimport GameplayKit
class point: NSObject {
  var vec: simd_float3
  init(x: Float, y: Float, z: Float) {
    self.vec = simd_float3(x,y,z)
  }
}
func test () {
  let points = [
    point(x: 1, y: 1, z: 2),
    point(x: 2, y: 2, z: 1),
    point(x: 2, y: 1, z: 1)
  ]
  let min = point(x:0, y: 0, z: 0)
  let max = point(x:3, y: 3, z: 3)
  let box = GKBox(boxMin: min.vec, boxMax: max.vec)
  let tree = GKOctree<point>(boundingBox: box, minimumCellSize: 0.01)
  print("=== registering ===")
  for p in points {
    let node = tree.add(p, at: p.vec)
    print("at:", p.vec, "box:", node.box)
  }
  // All
  print("=== list in elements(at:) ===")
  for p in tree.elements(at: points[0].vec) {
    print(p.vec)
  }
  print("=== elements(in:) ===")
  for p in tree.elements(in: box) {
    print(p.vec)
  }
}

It generates these results in the following.

Code Block swift=== registering ===
at: SIMD3<Float>(1.0, 1.0, 2.0) box: GKBox(boxMin: SIMD3<Float>(0.4921875, 0.99609375, 1.9921875), boxMax: SIMD3<Float>(0.50390625, 1.0078125, 2.0039062))
at: SIMD3<Float>(2.0, 2.0, 1.0) box: GKBox(boxMin: SIMD3<Float>(0.99609375, 1.9921875, 0.99609375), boxMax: SIMD3<Float>(1.0078125, 2.0039062, 1.0078125))
at: SIMD3<Float>(2.0, 1.0, 1.0) box: GKBox(boxMin: SIMD3<Float>(2.4960938, 0.99609375, 0.4921875), boxMax: SIMD3<Float>(2.5078125, 1.0078125, 0.50390625))
=== list in elements(at:) ===
SIMD3<Float>(1.0, 1.0, 2.0)
=== elements(in:) ===

Results report that each point which added to GKOctree are not in each GTKOctreeNode.box.
And when code specifies box to get elements, it doesn't return any elements at all.

Would there be any wrong in above code?
I think It may be bugs.

Platform: iOS 14.2, Playground

Boost

Answer 1

ytakio OP

Dec ’20

Here is expected results.
It would not be correct in detail, because these are just written down by hand.
Of course, it depends on implementation, but these would be almost right, I think. (Maybe...)

Code Block swift=== registering ===
at: SIMD3<Float>(1.0, 1.0, 2.0) box: GKBox(boxMin: SIMD3<Float>(0.0, 0.0, 1.5), boxMax: SIMD3<Float>(1.5, 1.5, 3.0))
at: SIMD3<Float>(2.0, 2.0, 1.0) box: GKBox(boxMin: SIMD3<Float>(1.5, 1.5, 0.0), boxMax: SIMD3<Float>(3.0, 3.0, 1.5))
at: SIMD3<Float>(2.0, 1.0, 1.0) box: GKBox(boxMin: SIMD3<Float>(1.5, 0.0, 0.0), boxMax: SIMD3<Float>(3.0, 1.5, 1.5))
=== list in elements(at:) ===
SIMD3<Float>(1.0, 1.0, 2.0)
=== elements(in:) ===
SIMD3<Float>(1.0, 1.0, 2.0)
SIMD3<Float>(2.0, 2.0, 1.0)
SIMD3<Float>(2.0, 1.0, 1.0)

1

Answer 2

dcooley OP

Feb ’21

There's a very similar question on StackOverflow with no answers. This does seem like a bug doesn't it.

Code Block swiftimport GameplayKit
let tree = GKOctree(boundingBox: GKBox(
 boxMin: vector_float3(x: -10, y: -10, z: -10),
 boxMax: vector_float3(x: 10, y: 10, z: 10)
), minimumCellSize: 0.1)
tree.add(NSObject(), at: vector_float3(x: 0, y: 0, z: 0))
tree.elements(at: vector_float3(x: 0, y: 0, z: 0)).count // 1, fine
tree.elements(in: GKBox(
 boxMin: vector_float3(x: -1, y: -1, z: -1),
 boxMax: vector_float3(x: 1, y: 1, z: 1)
)).count // 0, ??
tree.elements(in: GKBox(
 boxMin: vector_float3(x: 1, y: 1, z: 1),
 boxMax: vector_float3(x: -1, y: -1, z: -1)
)).count // 0, well I tried
// The original defining bounding box
tree.elements(in: GKBox(
  boxMin: vector_float3(x: -10, y: -10, z: -10),
  boxMax: vector_float3(x: 10, y: 10, z: 10)
)).count // 0, ***

1

Answer 3

mabi99 OP

May ’25

Yes, it seems GKOctree is buggy and basically not usable– a shame, Apple does not at all respond to such "minor" bug reports for so many years :(

I resorted to using an own Octree class, which I based on the work by the Swift Algorithm Club (https://github.com/kodecocodes/swift-algorithm-club/).

I have fixed a couple of glitches with their code, refined it, and added missing features like elements covering a whole region (instead of just a point), just as the Apple GKOctree does. It further now respects the minimumCellSize parameter, and it auto-prunes when you remove elements. Feel free to use this instead of GameplayKits buggy version:

https://github.com/mabi99/swift-algorithm-club (note: this is a LOT of algorithms in this, you can simply copy the Octree.swift file and use it!

0