<div dir="ltr">I am writing a bounding box module for the <a href="https://github.com/BioHaskell/octree/tree/master" rel="nofollow">octree</a> library. You can find my branch <a href="https://github.com/mlitchard/octree/tree/MBB" rel="nofollow">here</a>. In the function below, I try to make explicit the implicit bounding boxes of an <code>Octree</code>. The problem is, not all bounding boxes are valid.<br><br>This is the function in question, followed by a way to replicate the problem in <code>ghci</code>.<br><br><pre style="" class=""><code><span class="">explicateMBB </span><span class="">::</span><span class=""> </span><span class="">(</span><span class="">BBox3</span><span class="">,</span><span class=""> Octree a</span><span class="">)</span><span class=""> </span><span class="">-></span><span class=""> </span><span class="">[</span><span class="">BBox3</span><span class="">]</span><span class="">
explicateMBB </span><span class="">(</span><span class="">mbb</span><span class="">,</span><span class=""> </span><span class="">(</span><span class="">Leaf </span><span class="">_</span><span class="">))</span><span class=""> </span><span class="">=</span><span class=""> </span><span class="">[</span><span class="">mbb</span><span class="">]</span><span class="">
explicateMBB </span><span class="">(</span><span class="">mbb</span><span class="">,</span><span class=""> </span><span class="">(</span><span class="">Node </span><span class="">{</span><span class=""> split </span><span class="">=</span><span class=""> split'</span><span class="">,</span><span class="">
nwu </span><span class="">=</span><span class=""> nwu'</span><span class="">,</span><span class="">
nwd </span><span class="">=</span><span class=""> nwd'</span><span class="">,</span><span class="">
neu </span><span class="">=</span><span class=""> neu'</span><span class="">,</span><span class="">
ned </span><span class="">=</span><span class=""> ned'</span><span class="">,</span><span class="">
swu </span><span class="">=</span><span class=""> swu'</span><span class="">,</span><span class="">
swd </span><span class="">=</span><span class=""> swd'</span><span class="">,</span><span class="">
seu </span><span class="">=</span><span class=""> seu'</span><span class="">,</span><span class="">
sed </span><span class="">=</span><span class=""> sed'
</span><span class="">}))</span><span class=""> </span><span class="">=</span><span class="">
mbb</span><span class="">:</span><span class="">concatMap explicateMBB octList
</span><span class="">where</span><span class="">
octList </span><span class="">=</span><span class=""> zip boxList children
boxList </span><span class="">=</span><span class=""> </span><span class="">[</span><span class="">swdBox</span><span class="">,</span><span class=""> sedBox</span><span class="">,</span><span class=""> nwdBox</span><span class="">,</span><span class=""> nedBox</span><span class="">,</span><span class=""> swuBox</span><span class="">,</span><span class=""> seuBox</span><span class="">,</span><span class=""> nwuBox</span><span class="">,</span><span class=""> neuBox</span><span class="">]</span><span class="">
children </span><span class="">=</span><span class=""> </span><span class="">[</span><span class="">swd'</span><span class="">,</span><span class="">sed'</span><span class="">,</span><span class="">nwd'</span><span class="">,</span><span class="">ned'</span><span class="">,</span><span class="">swu'</span><span class="">,</span><span class="">seu'</span><span class="">,</span><span class="">nwu'</span><span class="">,</span><span class="">neu'</span><span class="">]</span><span class="">
swdBox </span><span class="">=</span><span class=""> bound_corners swdCorner neuCorner
</span><span class="">where</span><span class="">
swdCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">minX mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minY mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minZ mbb</span><span class="">)</span><span class="">
neuCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">v3x split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3y split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3z split'</span><span class="">)</span><span class="">
sedBox </span><span class="">=</span><span class=""> bound_corners swdCorner neuCorner
</span><span class="">where</span><span class="">
swdCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">v3x split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minY mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minZ mbb</span><span class="">)</span><span class="">
neuCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">maxX mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3y split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minZ mbb</span><span class="">)</span><span class="">
nwdBox </span><span class="">=</span><span class=""> bound_corners swdCorner neuCorner
</span><span class="">where</span><span class="">
swdCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">minX mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3y split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minZ mbb</span><span class="">)</span><span class="">
neuCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">v3x split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">maxY mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3z split'</span><span class="">)</span><span class="">
nedBox </span><span class="">=</span><span class=""> bound_corners swdCorner neuCorner
</span><span class="">where</span><span class="">
swdCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">v3x split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3y split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minZ mbb</span><span class="">)</span><span class="">
neuCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">maxX mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">maxY mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3z split'</span><span class="">)</span><span class="">
swuBox </span><span class="">=</span><span class=""> bound_corners swdCorner neuCorner
</span><span class="">where</span><span class="">
swdCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">minX mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minY mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3z split'</span><span class="">)</span><span class="">
neuCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">v3x split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3y split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">maxZ mbb</span><span class="">)</span><span class="">
seuBox </span><span class="">=</span><span class=""> bound_corners swdCorner neuCorner
</span><span class="">where</span><span class="">
swdCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">v3x split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">minY mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3z split'</span><span class="">)</span><span class="">
neuCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">maxX mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3y split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">maxZ mbb</span><span class="">)</span><span class="">
nwuBox </span><span class="">=</span><span class=""> bound_corners swdCorner neuCorner
</span><span class="">where</span><span class="">
swdCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">minX mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3y split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3z split'</span><span class="">)</span><span class="">
neuCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">v3x split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">maxY mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">maxZ mbb</span><span class="">)</span><span class="">
neuBox </span><span class="">=</span><span class=""> bound_corners swdCorner neuCorner
</span><span class="">where</span><span class="">
swdCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">v3x split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3y split'</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">v3z split'</span><span class="">)</span><span class="">
neuCorner </span><span class="">=</span><span class=""> Vector3 </span><span class="">(</span><span class="">maxX mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">maxY mbb</span><span class="">)</span><span class=""> </span><span class="">(</span><span class="">maxZ mbb</span><span class="">)</span></code></pre><br><p>To replicate problem:</p>
<p><code>git clone <a href="https://github.com/mlitchard/octree.git">https://github.com/mlitchard/octree.git</a></code></p>
<p><code>git checkout MBB</code></p>
<p><code>stack ghci</code></p>
<p>In <code>ghci</code>, do the following :</p>
<p><code>:m + Data.List Data.Vector.Class System.Random System.Random.Shuffle Data.BoundingBox.B3</code></p>
<p><code>let infinity = (read "Infinity") :: Double</code></p>
<p><code>let swdCorner = Vector3 (-infinity) (-infinity) (-infinity)</code></p>
<p><code>let neuCorner = Vector3 (infinity) (infinity) (infinity)</code></p>
<p><code>let rbb = bound_corners swdCorner neuCorner</code></p>
<p><code>xGen <- getStdGen</code></p>
<p><code>yGen <- newStdGen</code></p>
<p><code>zGen <- newStdGen</code></p>
<p><code>let xPoints = shuffle' [-256 .. 256] 513 xGen</code></p>
<p><code>let yPoints = shuffle' [-256 .. 256] 513 yGen</code></p>
<p><code>let zPoints = shuffle' [-256 .. 256] 513 zGen</code></p>
<p><code>let xPoints' = map fromInteger xPoints :: [Double]</code></p>
<p><code>let yPoints' = map fromInteger yPoints :: [Double]</code></p>
<p><code>let zPoints' = map fromInteger zPoints :: [Double]</code></p>
<p><code>let tup513 = zip3 xPoints' yPoints' zPoints'</code></p>
<p><code>let construct_vect = (\(x,y,z) -> Vector3 x y z)</code></p>
<p><code>let vect513 = map construct_vect tup513</code></p>
<p><code>let pre_oct513 = zip vect513 [1 .. 513]</code></p>
<p><code>let octree513 = fromList pre_oct513</code></p>
<p><code>length $ filter (== False) $ map isValidMBB $ explicateMBB (rbb,octree513)</code></p><p><br><code></code></p><p><br></p><p>The answer will be 9, but should be 0.</p>
<p>I feel like one of the <code>fooBox</code> <code>where</code> clauses is wrong, but I have gone over each one several times, and I am not seeing which one it is.</p>
<p>If you needed a visual aid like I did, I found <a href="https://geidav.files.wordpress.com/2014/08/full_octree.png?w=820" rel="nofollow">this pic</a> to be helpful. My sample does 2 subdivisions.</p>
<p>Any insight into what is going wrong would be appreciated.</p><br></div>