Ray tracing issue

[ZenanH]

Hi! Thanks for providing this package, I think it can play a big role in my project. My question is about ray tracing. This feature is not registered yet, so I just added it by git URL (main).

I have a set of triangular faces forming a closed 3D entity A and need to determine if a large number of scattered points are inside it. I plan to use ray-casting, counting intersections of rays with triangles. To accelerate, BVH can filter potential intersecting triangles instead of checking all. I think the ray-tracing example provides this first step, returning possible intersecting triangles and ray IDs in Tuple. (Please correct me if I'm wrong.😅)

I prepared an example where A is a tetrahedron. All directions are fixed as [0, 0, 1] (z-direction).

using ImplicitBVH
using ImplicitBVH: BBox

vertices = [0.0 0.0 0.0; 1.0 0.0 0.0; 0.0 1.0 0.0; 0.0 0.0 1.0]
faces    = [1 2 3; 1 3 4; 1 2 4; 2 3 4]

bounding_boxes = [BBox{Float32}(vertices[faces[i, :], :]) for i in axes(faces, 1)]
bvh = BVH(bounding_boxes, BBox{Float32}, UInt32)

points = [
    0.8 0.2 0.5 0.1;
    0.8 0.2 0.5 0.1;
    0.8 0.2 0.5 0.1
]
directions = zeros(3, 4)
directions[3, :] .= 1.0
traversal = traverse_rays(bvh, points, directions)

julia> traversal.contacts
4-element view(::Vector{Tuple{Int32, Int32}}, 1:4) with eltype Tuple{Int32, Int32}:
 (4, 1)
 (4, 2)
 (4, 3)
 (4, 4)

I think the result here is reasonable. However, If I uniformly fill the test points within a space range of 1 with a step size of 0.1, the result is as follows:

# generate test points
range  = 0:0.1:1
x      = repeat(range, inner=length(range)^2)
y      = repeat(repeat(range, inner=length(range)), outer=length(range))
z      = repeat(range, outer=length(range)^2)
points = Array(hcat(x, y, z)')
directions = zeros(3, size(points, 2))
directions[3, :] .= 1.0
traversal = traverse_rays(bvh, points, directions)

julia> traversal.contacts
8-element view(::Vector{Tuple{Int32, Int32}}, 1:8) with eltype Tuple{Int32, Int32}:
 (1, 111)
 (2, 111)
 (3, 111)
 (4, 111)
 (3, 721)
 (4, 721)
 (1, 722)
 (2, 722)

Since there are 1331 test points uniformly distributed within a cube of side length 1, I believe the result should not consist of only eight tuples.

Do you think this result is reasonable? Is it a bug, or is there an issue with my understanding or code? Thanks!

[Jack-Grogan]

Hi! Thanks for raising the issue. I had made a mistake in the raytrace_cpu.jl parallelisation script. I have submitted a pull request that should fix this issue.

[ZenanH]

I tested it again and it works perfectly. 👍 Hope a new ImplicitBVH.jl version will be released soon, ray tracing function is useful.