Octree gives various clojure.lang level errors

[charlieb]

First let me apologise for the poor title of this issue and then apologise again for not having narrowed down the exact cases that cause these problems.

I have this piece of code

(defn new-rand-point [xyz-range]
  (vec3 (- (rand xyz-range) (/ xyz-range 2))
        (- (rand xyz-range) (/ xyz-range 2))
        (- (rand xyz-range) (/ xyz-range 2))))
(defn dla-points
  "I don't do a whole lot."
  [npoints start-range]
  (let [tree (st/octree 0 0 0 100 100 100)]
    (g/add-point tree (vec3 0 0 0) (vec3 0 0 0))
    (loop [tree tree
           i npoints
           p (new-rand-point start-range)]
      (println i p)
      (cond (zero? i)
            (st/select-with-sphere tree (vec3 0 0 0) 50)

            (st/points-in-sphere? tree p 5) 
            (recur (g/add-point tree p p)
                   (dec i)
                   (new-rand-point start-range))

            (not (st/points-in-sphere? tree p 10))
            (recur tree i (new-rand-point start-range))

            :otherwise 
            (recur tree i (.+ p (new-rand-point 1.)))))))

(dla-points 100 50)

Which when run sometimes succeeds, sometimes gets to the last point and fails with

StackOverflowError   clojure.lang.Symbol.hashCode (Symbol.java:84)

and sometimes freezes, waits and then gives this:

OutOfMemoryError Java heap space  clojure.lang.PersistentVector.assocN (PersistentVector.java:181)

I'm probably breaking some (unwritten) rules in the way I'm using this but please let me know.

[charlieb]

 (reduce #(g/add-point % %2 %2)
          (st/octree 0 0 0 100 100 100)
          [[0 0 0] 
           [-1.9446942785288333 -4.311887733904416 -0.5723572012550799]
           [-0.2643569452823872 0.8996130544133574 4.885296326158475]
           ;  [-0.4272646031 3795933 -0.8410052835626067 -4.894709960433672]]
           ]))

StackOverflowError   clojure.lang.PersistentHashMap$BitmapIndexedNode.index (PersistentHashMap.java:677)

but remove a minus sign from the third number in the second vec and all is well:

 (reduce #(g/add-point % %2 %2)
          (st/octree 0 0 0 100 100 100)
          [[0 0 0] 
           [-1.9446942785288333 -4.311887733904416 0.5723572012550799]
           [-0.2643569452823872 0.8996130544133574 4.885296326158475]
           ;  [-0.4272646031 3795933 -0.8410052835626067 -4.894709960433672]]
           ]))

#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [100.0 100.0 100.0]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [50.0 50.0 50.0]} :children [#thi.ng.geom.sp
atialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [25.0 25.0 25.0]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [12.5 12.5 12.5]} :children [#thi.ng.geom.spatialtree.MutableO
ctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [6.25 6.25 6.25]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [3.125 3.125 3.125]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:boun
ds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [1.5625 1.5625 1.5625]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [0.78125 0.78125 0.78125]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds 
#thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [0.390625 0.390625 0.390625]} :children nil :p [0 0 0] :d [0 0 0]} nil nil nil #thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.390625], :size [0.390625 0.390625 0.390625]} :children nil
 :p [-1.9446942785288333 -4.311887733904416 0.5723572012550799] :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil] :p nil :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil nil nil nil nil] :p nil :d [0 0 0]} nil nil nil ni
l nil nil nil] :p nil :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil #thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 3.125], :size [3.125 3.125 3.125]} :children nil :p [-0.2643569452823872 0.89961305441335
74 4.885296326158475] :d [-0.2643569452823872 0.8996130544133574 4.885296326158475]} nil nil nil] :p nil :d [0 0 0]} nil nil nil nil nil nil nil] :p nil :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil nil nil nil nil] :p nil :d [0 0 0]} nil nil n
il nil nil nil nil] :p nil :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil nil nil nil nil] :p nil :d [0 0 0]}
#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [100.0 100.0 100.0]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [50.0 50.0 50.0]} :children [#thi.ng.geom.sp
atialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [25.0 25.0 25.0]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [12.5 12.5 12.5]} :children [#thi.ng.geom.spatialtree.MutableO
ctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [6.25 6.25 6.25]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [3.125 3.125 3.125]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:boun
ds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [1.5625 1.5625 1.5625]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [0.78125 0.78125 0.78125]} :children [#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds 
#thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [0.390625 0.390625 0.390625]} :children nil :p [0 0 0] :d [0 0 0]} nil nil nil #thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.390625], :size [0.390625 0.390625 0.390625]} :children nil
 :p [-1.9446942785288333 -4.311887733904416 0.5723572012550799] :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil] :p nil :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil nil nil nil nil] :p nil :d [0 0 0]} nil nil nil ni
l nil nil nil] :p nil :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil #thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 3.125], :size [3.125 3.125 3.125]} :children nil :p [-0.2643569452823872 0.89961305441335
74 4.885296326158475] :d [-0.2643569452823872 0.8996130544133574 4.885296326158475]} nil nil nil] :p nil :d [0 0 0]} nil nil nil nil nil nil nil] :p nil :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil nil nil nil nil] :p nil :d [0 0 0]} nil nil n
il nil nil nil nil] :p nil :d [-1.9446942785288333 -4.311887733904416 0.5723572012550799]} nil nil nil nil nil nil nil] :p nil :d [0 0 0]}

[postspectacular]

@charlieb i will take a closer look at this over the weekend. my first hunch is that the large selection sphere is in the wrong place. the octree (as defined by you) is between (0,0,0) -> (100,100,100), so the sphere should be centered around (50,50,50), not (0,0,0)...

[postspectacular]

the other thing is that i can't recall right now how points outside the octree volume are handled (if at all). i think this might cause some issues, so please try to clamp them to the indexable region...

[charlieb]

That was my hunch as well but I wasn't able to get behaviour that was consistent with that hypothesis. It wasn't clear from the comments whether the second argument was only in one direction or whether it defined a region offset by a maximum from the center. I assumed the second.
For my project I've gone with a kd-tree from another library so it's not urgent for me.

[postspectacular]

yeah, sorry - that part of the library is very much under-documented :( In general, for use cases like this (unknown/growing regions to be indexed), a k-D tree is definitely the better solution, especially if it supports rebalancing...

[charlieb]

No need to apologise, thank you for all your work on this!

[dimovich]

That was my hunch as well but I wasn't able to get behaviour that was consistent with that hypothesis. It wasn't clear from the comments whether the second argument was only in one direction or whether it defined a region offset by a maximum from the center. I assumed the second.
For my project I've gone with a kd-tree from another library so it's not urgent for me.

@charlieb
I remember also bumping into this issue while experimenting with https://dimovich.github.io/art and updating the agents positions. Sometimes it would work, but sometimes it would go into infinite loop for some specific points. Nice that you found a simple test case.

@postspectacular Why is it required to center the selection sphere? If I pick a point and would like to see the neighboring points shouldn't it be possible to place the selection sphere at any point within the octree?

[postspectacular]

So I can confirm that, as predicted earlier, the error/hang has to do with inserting points outside the defined octree volume, which really is a kind of user error, since conceptually these points are not indexable with an octree. So all you'd need to do is pre-clamping points before inserting, e.g. via: (m/min (m/max p (v/vec3)) (v/vec3 100))

(require
  '[thi.ng.geom.spatialtree :as st]
  '[thi.ng.geom.vector :as v]
  '[thi.ng.geom.core :as g])

(def tree (st/octree (v/vec3) (v/vec3 100)))

;; first outside point succeeds
(g/add-point tree (v/vec3 -1) nil)
#thi.ng.geom.spatialtree.MutableOctreeNode{:bounds #thi.ng.geom.types.AABB{:p [0.0 0.0 0.0], :size [100.0 100.0 100.0]} :children nil :p [-1.0 -1.0 -1.0] :d nil}

;; next outside point fails
(g/add-point tree (v/vec3 -2) nil)
;; hangs

@dimovich pls ignore my comment about centered sphere :) of course you should be able to position it anywhere in the indexed space, but it was my first (and wrong) hunch, which i then replaced straight after with the other (outlier points) prediction...

[postspectacular]

Btw. Fixing this would make a nice & easy PR. Just need to decide how to deal with the case of trying to index an outside point, e.g. return nil. The bounds check should only be needed in these 2 locations to also fix the same issue for the quadtree:

• https://github.com/thi-ng/geom/blob/feature/no-org/src/thi/ng/geom/spatialtree.cljc#L153
• https://github.com/thi-ng/geom/blob/feature/no-org/src/thi/ng/geom/spatialtree.cljc#L231

Tree nodes implement g/bounds so add-point could just become (untested, but should work):

(add-point [_ p d]
  (when (g/contains-point? (g/bounds _) p)
    (add-point* _ p d) _))

[dimovich]

Tree nodes implement g/bounds so add-point could just become (untested, but should work):

(add-point [_ p d]
  (when (g/contains-point? (g/bounds _) p)
    (add-point* _ p d) _))

@postspectacular Yes, this works! Btw, shouldn't the tree always be returned?

(add-point [_ p d]
    (when (g/contains-point? (g/bounds _) p)
      (add-point* _ p d)) _)

[postspectacular]

@dimovich great - and re: always returning the tree, that's what I meant with: "Just need to decide how to deal with the case of trying to index an outside point". Using nil as result here allows us to indicate to the caller that indexing that given point failed... Also, for performance reasons both the quad and octree impls are mutable structures, so in theory we'd never need to return a result tree...