[Haskell-cafe] Where am I going wrong with my bounding box function?

20 Jun 2016

      I am writing a bounding box module for the octree
https://github.com/BioHaskell/octree/tree/master library. You can find my
branch here https://github.com/mlitchard/octree/tree/MBB. In the function
below, I try to make explicit the implicit bounding boxes of an Octree. The
problem is, not all bounding boxes are valid.

This is the function in question, followed by a way to replicate the
problem in ghci.

explicateMBB :: (BBox3, Octree a) -> [BBox3]
explicateMBB (mbb, (Leaf _)) = [mbb]
explicateMBB (mbb, (Node { split = split',
                           nwu   = nwu',
                           nwd   = nwd',
                           neu   = neu',
                           ned   = ned',
                           swu   = swu',
                           swd   = swd',
                           seu   = seu',
                           sed   = sed'
             })) =
   mbb:concatMap explicateMBB octList
  where
    octList = zip boxList children
    boxList = [swdBox, sedBox, nwdBox, nedBox, swuBox, seuBox, nwuBox, neuBox]
    children = [swd',sed',nwd',ned',swu',seu',nwu',neu']
    swdBox = bound_corners swdCorner neuCorner
      where
        swdCorner = Vector3 (minX mbb) (minY mbb) (minZ mbb)
        neuCorner = Vector3 (v3x split') (v3y split') (v3z split')
    sedBox = bound_corners swdCorner neuCorner
      where
        swdCorner = Vector3 (v3x split') (minY mbb) (minZ mbb)
        neuCorner = Vector3 (maxX mbb) (v3y split') (minZ mbb)
    nwdBox = bound_corners swdCorner neuCorner
      where
        swdCorner = Vector3 (minX mbb) (v3y split') (minZ mbb)
        neuCorner = Vector3 (v3x split') (maxY mbb) (v3z split')
    nedBox = bound_corners swdCorner neuCorner
      where
        swdCorner = Vector3 (v3x split') (v3y split') (minZ mbb)
        neuCorner = Vector3 (maxX mbb) (maxY mbb) (v3z split')
    swuBox = bound_corners swdCorner neuCorner
      where
        swdCorner = Vector3 (minX mbb) (minY mbb) (v3z split')
        neuCorner = Vector3 (v3x split') (v3y split') (maxZ mbb)
    seuBox = bound_corners swdCorner neuCorner
      where
        swdCorner = Vector3 (v3x split') (minY mbb) (v3z split')
        neuCorner = Vector3 (maxX mbb) (v3y split') (maxZ mbb)
    nwuBox = bound_corners swdCorner neuCorner
      where
        swdCorner = Vector3 (minX mbb) (v3y split') (v3z split')
        neuCorner = Vector3 (v3x split') (maxY mbb) (maxZ mbb)
    neuBox = bound_corners swdCorner neuCorner
      where
        swdCorner = Vector3 (v3x split') (v3y split') (v3z split')
        neuCorner = Vector3 (maxX mbb) (maxY mbb) (maxZ mbb)

To replicate problem:

git clone https://github.com/mlitchard/octree.git

git checkout MBB

stack ghci

In ghci, do the following :

:m + Data.List Data.Vector.Class System.Random System.Random.Shuffle
Data.BoundingBox.B3

let infinity = (read "Infinity") :: Double

let swdCorner = Vector3 (-infinity) (-infinity) (-infinity)

let neuCorner = Vector3 (infinity) (infinity) (infinity)

let rbb = bound_corners swdCorner neuCorner

xGen <- getStdGen

yGen <- newStdGen

zGen <- newStdGen

let xPoints = shuffle' [-256 .. 256] 513 xGen

let yPoints = shuffle' [-256 .. 256] 513 yGen

let zPoints = shuffle' [-256 .. 256] 513 zGen

let xPoints' = map fromInteger xPoints :: [Double]

let yPoints' = map fromInteger yPoints :: [Double]

let zPoints' = map fromInteger zPoints :: [Double]

let tup513 = zip3 xPoints' yPoints' zPoints'

let construct_vect = (\(x,y,z) -> Vector3 x y z)

let vect513 = map construct_vect tup513

let pre_oct513 = zip vect513 [1 .. 513]

let octree513 = fromList pre_oct513

length $ filter (== False) $ map isValidMBB $ explicateMBB (rbb,octree513)

The answer will be 9, but should be 0.

I feel like one of the fooBox where clauses is wrong, but I have gone over
each one several times, and I am not seeing which one it is.

If you needed a visual aid like I did, I found this pic
https://geidav.files.wordpress.com/2014/08/full_octree.png?w=820 to be
helpful. My sample does 2 subdivisions.

Any insight into what is going wrong would be appreciated.

[Haskell-cafe] Where am I going wrong with my bounding box function?

Michael Litchard