I have worked on this quite a while and is stuck with this bug.
We have build a ray-tracer in F# for a school project. (Link explaining Ray tracer: https://blog.frogslayer.com/kd-trees-for-faster-ray-tracing-with-triangles/)
We have a made hit function for triangles, boundingboxes, a KD tree to handle figures with thousands of triangles, such as the Stanford Bunny and a traverse algorithm for the KD tree.
We have debugged both the creation of the KD tree, made sure to add a epsilon value for float points and checked that duplicates between the boundingboxes are not removed. We are certain that we split the list of shapes in the scene corretly, but we get "holes" in the figure we try to render.
This is our KD tree implementation and I've attached pictures of the holes:
module TmKdtree
open Point
open Shapes
type BoundingBox = BasicShape.BoundingBox
type Shape = BasicShape.Shape
type TmKdtree =
| Leaf of BasicShape.Triangle list * BoundingBox
| Node of BasicShape.Triangle list * TmKdtree * TmKdtree * BoundingBox * (string*Point)
let epsilon = 0.001
//Making a boundingbox for the KD-tree, by finding max H point in the boundingboxlist and min l point in the boundingbox list.
let mkKdBbox (shapes : BasicShape.Triangle list) : BoundingBox =
let shapeX = List.map(fun x -> x:> Shape) shapes
let sbbox = List.map (fun (c:Shape) -> c.getBounding().Value) shapeX
let bL = List.map (fun (b:BasicShape.BoundingBox) -> b.getL) sbbox
let bH = List.map (fun (b:BasicShape.BoundingBox) -> b.getH) sbbox
let minX = List.minBy (fun x -> Point.getX x) bL
let minY = List.minBy (fun x -> Point.getY x) bL
let minZ = List.minBy (fun x -> Point.getZ x) bL
let maxX = List.maxBy (fun x -> Point.getX x) bH
let maxY = List.maxBy (fun x -> Point.getY x) bH
let maxZ = List.maxBy (fun x -> Point.getZ x) bH
{p1=(mkPoint (Point.getX minX - epsilon) (Point.getY minY - epsilon) (Point.getZ minZ - epsilon) )
; p2=(mkPoint (Point.getX maxX + epsilon) (Point.getY maxY + epsilon) (Point.getZ maxZ + epsilon) )}
//Splitting existing boundingbox according to left and right list of shapes
let BoundingBoxL (bbox:BoundingBox) axis midp : BoundingBox =
match axis with
| "x" -> {p1 = bbox.getL - epsilon; p2 = Point.mkPoint ((Point.getX midp)) ((Point.getY (bbox.getH))) ((Point.getZ (bbox.getH))) + epsilon}
| "y" -> {p1 = bbox.getL - epsilon; p2 = Point.mkPoint (Point.getX (bbox.getH)) ((Point.getY midp)+epsilon) ((Point.getZ (bbox.getH))) + epsilon }
| "z" -> {p1 = bbox.getL - epsilon; p2 = Point.mkPoint (Point.getX (bbox.getH)) (Point.getY (bbox.getH)) (Point.getZ midp) + epsilon}
let BoundingBoxR (bbox:BoundingBox) axis midp : BoundingBox =
match axis with
| "x" -> {p1 = (Point.mkPoint (Point.getX midp) (Point.getY (bbox.getL)) (Point.getZ (bbox.getL))) - epsilon; p2 = bbox.getH + epsilon}
| "y" -> {p1 = (Point.mkPoint (Point.getX (bbox.getL)) (Point.getY midp) (Point.getZ (bbox.getL))) - epsilon; p2 = bbox.getH + epsilon}
| "z" -> {p1 = (Point.mkPoint (Point.getX (bbox.getL)) (Point.getY (bbox.getL)) (Point.getZ midp)) - epsilon; p2 = bbox.getH + epsilon}
//Get left node
let getLeft s =
match s with
| Node(_,l,_,_,_) -> l
| Leaf(_,_) as leaf -> leaf
let getRight s =
match s with
| Node(_,_,r,_,_) -> r
| Leaf(_,_) as leaf -> leaf
//Get the triangle list
let getShapes s =
match s with
| Node(b,_,_,_,_) -> b
| Leaf(b,_) -> b
let getAxis s =
match s with
| Node(_,_,_,_,a) -> a
| Leaf(_,_) -> failwith "leaf ramt af axis"
//Get bounding box
let getBox s =
match s with
| Node(_,_,_,b,_) -> Some b
| Leaf(_,b) -> Some b
let closestHit (triList : BasicShape.Triangle list) ray =
let sndRects = List.map(fun x -> x:> Shape) triList
let min = List.map(fun (x:Shape) -> x.hit ray) sndRects |> List.choose id
match min with
|[] -> None
|_ -> Some(List.minBy (fun (di, nV, mat) -> di) min)
let searchLeaf leaf ray t' =
match leaf with
| Leaf(s,_) -> let hit = closestHit s ray
match hit with
|Some(f,_,_) -> if (f<t') then Some hit else None
|None -> None
| Node(_,_,_,_,_) -> failwith "Expected leaf"
let order(d, left, right) =
if d > 0.0
then (left, right)
else (right, left)
let rec search node ray t t' =
match node with
|Leaf(_,_) -> searchLeaf node ray t'
|Node(_,_,_,_,a') ->
let direction = Ray.getDirection ray (fst a')
let origin = Ray.getOrigin ray (fst a')
let nodeValue = Point.getFromAxis (snd a') (fst a')
if(direction) = 0.0 then
printfn("%s") "flatsite"
if(origin <= nodeValue) then search (getLeft node) ray t t'
else search (getRight node) ray t t'
else
let tHit = (nodeValue - origin) / direction
let (fst, snd) = order(direction,getLeft node, getRight node)
if tHit <= t || tHit < 0.0 then
search snd ray t t'
else if tHit >= t' then
search fst ray t t'
else
match search fst ray t tHit with
|Some hit -> Some hit
|_ -> search snd ray tHit t'
let traverse tree ray (bawx:BasicShape.BoundingBox) =
match(bawx).hit(ray) with
|Some(t,t') -> search tree ray t t'
|None -> None
//Finding the midpoint in the triangles in Shapes-list - we do this (recursively) to find out what axis to split
let rec mkTmKdtree (shapes : BasicShape.Triangle list) (box:BasicShape.BoundingBox) =
//Finding biggest dimension in the shapes list
let axis = snd (box.getLongestAxis)
let axisMidPoint =
let midPoint = List.fold (fun acc (ele:BasicShape.Triangle) -> (acc + ele.getMidPoint())) (Point.mkPoint 0.0 0.0 0.0) shapes
let avgMid = midPoint / float(shapes.Length)
avgMid
let rec largerThanSplit (xs:BasicShape.Triangle list) =
let results = List.choose(fun (elem:BasicShape.Triangle) ->
match axis with
|"x" -> if (Point.getX (elem.getMidPoint())) >= (Point.getX axisMidPoint) then Some elem else None
|"y" -> if (Point.getY (elem.getMidPoint())) >= (Point.getY axisMidPoint) then Some elem else None
|"z" -> if (Point.getZ (elem.getMidPoint())) >= (Point.getZ axisMidPoint) then Some elem else None) xs
results
let rec lessThanSplit (xs:BasicShape.Triangle list) =
let results = List.choose(fun (elem:BasicShape.Triangle) ->
match axis with
|"x" -> if ((Point.getX (elem.getMidPoint())) <= (Point.getX (axisMidPoint))) then Some elem else None
|"y" -> if ((Point.getY (elem.getMidPoint())) <= (Point.getY (axisMidPoint))) then Some elem else None
|"z" -> if ((Point.getZ (elem.getMidPoint())) <= (Point.getZ (axisMidPoint))) then Some elem else None) xs
results
//Creating the left and right list from the above
let rightTest = largerThanSplit shapes
let leftTest = lessThanSplit shapes
//If one of the trees are empty, we add make left and right equivelant.
let left = if(leftTest.IsEmpty && rightTest.Length > 0) then rightTest else leftTest
let right = if(rightTest.IsEmpty && leftTest.Length > 0) then leftTest else rightTest
//Check for duplicates among the lists.
if(((float(left.Length+right.Length-shapes.Length)/float(shapes.Length)) < 0.4) && left.Length <> shapes.Length && right.Length<>shapes.Length) then
let leftTree = mkTmKdtree left (BoundingBoxL box axis axisMidPoint)
let rightTree = mkTmKdtree right (BoundingBoxR box axis axisMidPoint)
Node(shapes,leftTree, rightTree, (box),(axis,axisMidPoint))
else Leaf(shapes, (box))
Thank you for the responses! I turned out that the bug was in our reflections of the figures, and had nothing to do with the data structure of the program.
But thank you anyway! :-)