trace failed when ray origin is inside of normalization range

[Burningdust21]

Hi, thanks for a great work.

I have a point cloud that is normalized to [-1, 1], as described in documentation, and use it to generate a spc. When I apply spc tracing from ray whose origin is inside of the normalization field, that is all three axis of the ray's origin is in [-1, 1], there will be no intersection returned; but if the ray origin is outside of normalization field(by reducing normalization field), tracing can found correct intersections.

Is there a solution to this problem? I'm using kaolin 0.9.1.

[tovacinni]

Thanks for your interest in Kaolin.

One design decision we make (which we could update to accomodate the other case if it's useful to people) is that if you're tracing a ray whose origin is inside an AABB, it won't return that intersection. So if you have a SPC with just 1 voxel or something, it won't return an intersection.

If you're seeing that the rays are not hitting anything (even ones that the ray origin is not inside), then there might be a bug. Is this the case? (If so we can investigate)

[Burningdust21]

Thanks for the reply.

The spc I use has over 10000 points. and the ray origin is not inside of any aabb, but is inside of normalization range.

For example, if I generate a dense point cloud and use it to get a dense spc; then intersect the spc with direction (-1, 0, 0) and origin ranging from (0, 0, 0) to (2, 0, 0), theoretically all rays should have intersections. But rays that have origin from (0, 0, 0) to (1, 0, 0) will return empty intersection. Code and output as following:

from kaolin.ops import spc
import kaolin.render.spc as spc_render
import torch

# first, generste a dense point cloud
resolution = 16
_x = torch.linspace(-1, 1, resolution, device=0)
pc = torch.stack(torch.meshgrid(_x, _x, _x), dim=-1).reshape(-1, 3).float()

# second, create octree
level = 4
quantized_pc = spc.points.quantize_points(pc, level)
octree = spc.unbatched_points_to_octree(quantized_pc, level)

# octree to spc
lengths = torch.tensor([len(octree)], dtype=torch.int32)
_, pyramid, prefix = spc.scan_octrees(octree, lengths)
points = spc.generate_points(octree, pyramid, prefix)
pyramid = pyramid[0]

# finally, intersect with different origin with the same direction
num_tests = 10
rays_origins = torch.zeros((num_tests, 3), device=0, dtype=torch.float32) 
rays_origins[:, 0] = torch.linspace(0, 2, num_tests).cuda()
ray_dir = torch.ones((num_tests, 3), device=0, dtype=torch.float32) * 1e-4
ray_dir[:, 0] = -1

for i in range(num_tests):
    nugs = spc_render.unbatched_raytrace(octree, points, pyramid, prefix,
                                            rays_origins[i:i+1], ray_dir[i:i+1], level)
    depth, _, _ = spc_render.unbatched_ray_aabb(nugs, points, rays_origins[i:i+1], ray_dir[i:i+1], level)
    
    print(f"origin {rays_origins[i:i+1]} has {nugs.size()[0]} intersections, with depth {depth}")

output:

origin tensor([[0., 0., 0.]], device='cuda:0') has 0 intersections, with depth tensor([[0.]], device='cuda:0')
origin tensor([[0.2222, 0.0000, 0.0000]], device='cuda:0') has 0 intersections, with depth tensor([[0.]], device='cuda:0')
origin tensor([[0.4444, 0.0000, 0.0000]], device='cuda:0') has 0 intersections, with depth tensor([[0.]], device='cuda:0')
origin tensor([[0.6667, 0.0000, 0.0000]], device='cuda:0') has 0 intersections, with depth tensor([[0.]], device='cuda:0')
origin tensor([[0.8889, 0.0000, 0.0000]], device='cuda:0') has 0 intersections, with depth tensor([[0.]], device='cuda:0')
origin tensor([[1.1111, 0.0000, 0.0000]], device='cuda:0') has 16 intersections, with depth tensor([[0.1111]], device='cuda:0')
origin tensor([[1.3333, 0.0000, 0.0000]], device='cuda:0') has 16 intersections, with depth tensor([[0.3333]], device='cuda:0')
origin tensor([[1.5556, 0.0000, 0.0000]], device='cuda:0') has 16 intersections, with depth tensor([[0.5556]], device='cuda:0')
origin tensor([[1.7778, 0.0000, 0.0000]], device='cuda:0') has 16 intersections, with depth tensor([[0.7778]], device='cuda:0')
origin tensor([[2., 0., 0.]], device='cuda:0') has 16 intersections, with depth tensor([[1.]], device='cuda:0')

By the way, I found that if any of the axis in direction is 0, aabb will also return empty intersection, I add 1e-4 to make it work.

[tovacinni]

Thanks for the detailed outputs.

I'll perform some more tests with the script you sent, but in the case the direction is 0 in some axis, likely what is happening is that the rays are tracing exactly between the voxels and thus won't return any intersections.

In the origin case though, it should return intersections & your tests with the origin is good evidence. I'll take a look at this, thanks for the report!

[anuveshkumar]

I had the same problem. The way I solved it was to calculate intersection depth of rays with a bounding box [-1, 1].

After obtaining the near and far values, in cases where the near values were negative (as in intersection happened before the ray origin) I would shift my ray origin to near the surface of the bbox like so:
rays_o_modified = rays_o + (near - 1e-10) * rays_d

This will given different camera origins (behind the camera point) for different rays. But by doing so the camera origin don't fall inside the normalization range, and I was able to use this function as it is.

[ventusff]

I had the same issue;
Intersections when ray_o inside AABBs is needed and useful:

1. consider dealing with a large wild scene (e.g. streets of cities) with an observer (e.g. cars in streets), it is very likely that the camera will be inside voxels at certain levels (especially levels that are close to the root level).
2. consider dealing with an inside-out scene (e.g. indoors) with an observer (e.g. robots in indoor scenes), this is also the case. And in this case, even when ray origins are indeed inside voxels of the last level, a meaningful exit depth might still be needed. For example, if the last level of voxels represents many different rooms of a large building, one could still use the exit depth of intersections.

[LiXinghui-666]

I had the same issue; Intersections when ray_o inside AABBs is needed and useful:

1. consider dealing with a large wild scene (e.g. streets of cities) with an observer (e.g. cars in streets), it is very likely that the camera will be inside voxels at certain levels (especially levels that are close to the root level).
2. consider dealing with an inside-out scene (e.g. indoors) with an observer (e.g. robots in indoor scenes), this is also the case. And in this case, even when ray origins are indeed inside voxels of the last level, a meaningful exit depth might still be needed. For example, if the last level of voxels represents many different rooms of a large building, one could still use the exit depth of intersections.

I would like to ask if there is any other way to deal with the indoor scene？

[Caenorst]

Hi @LiXinghui-666 @ventusff , we are working on a fix, should be merged this week

[LiXinghui-666]

Hi @LiXinghui-666 @ventusff , we are working on a fix, should be merged this week

Thanks a lot!

[LiXinghui-666]

Hi @LiXinghui-666 @ventusff , we are working on a fix, should be merged this week

Hello, I'm sorry to bother you again. Has this problem been fixed? Will a new version be released after the fix? Thanks.

[Caenorst]

Hi @LiXinghui-666 @ventusff we just merged a fix, it even came with a little 10% speedup :)

[ventusff]

Hi @Caenorst ,
Cooool! I've done some testing, In most of the case, it works; also, the time consumed by unbatched_raytrace dropped from 7.1 ms to 6.1 ms in my test, with 2M rays and level=8.

However, I found two things that might need fix or discussion:

1. Firstly, when rays_o are exactly on the border planes or corners of the voxels, the results are sometimes incorrect.

Initialize a dense level=1 / level=2 octree and intersect:

from kaolin.rep.spc import Spc
from kaolin.render.spc import unbatched_raytrace
from kaolin.ops.spc import unbatched_points_to_octree
device = torch.device('cuda')
#----------------------------------------------------------------------
#------------------- level = 1
level = 1
octree = torch.tensor([255], dtype=torch.uint8, device=device)
spc = Spc(octree, torch.tensor([len(octree)], dtype=torch.int32))
spc._apply_scan_octrees()
spc._apply_generate_points()

# [failed]  expected: has intersection; result: no intersection.
rays_o = torch.tensor([[0., -1., 0.]], dtype=torch.float, device=device)
rays_d = torch.tensor([[0.,  1., 0.]], dtype=torch.float, device=device)
ridx, pidx, depth = unbatched_raytrace(octree, spc.point_hierarchies, spc.pyramids[0], spc.exsum, rays_o, rays_d, level=level, with_exit=True, return_depth=True)

# [passed]  expected: has intersection; result: has intersection.
rays_o = torch.tensor([[0., -1.+1e-3, 0.]], dtype=torch.float, device=device)
rays_d = torch.tensor([[0.,  1., 0.]], dtype=torch.float, device=device)
ridx, pidx, depth = unbatched_raytrace(octree, spc.point_hierarchies, spc.pyramids[0], spc.exsum, rays_o, rays_d, level=level, with_exit=True, return_depth=True)

#----------------------------------------------------------------------
#------------------- level = 2
level = 2
occ_grid = torch.ones([2**level]*3, device=device, dtype=torch.bool)
coords = occ_grid.nonzero().short()
octree = unbatched_points_to_octree(coords, level=level)
spc = Spc(octree, torch.tensor([len(octree)], dtype=torch.int32))
spc._apply_scan_octrees()
spc._apply_generate_points()

# [failed]  expected: has intersection; result: no intersection.
rays_o = torch.tensor([[0.,  0.,  0.]], dtype=torch.float, device=device)
rays_d = torch.tensor([[0,   1,   0]], dtype=torch.float, device=device)
ridx, pidx, depth = unbatched_raytrace(octree, spc.point_hierarchies, spc.pyramids[0], spc.exsum, rays_o, rays_d, level=level, with_exit=True, return_depth=True)

# [failed]  expected: has intersection; result: no intersection.
rays_o = torch.tensor([[0.,  1.0e-3,  0.]], dtype=torch.float, device=device)
rays_d = torch.tensor([[0,   1,          0]], dtype=torch.float, device=device)
ridx, pidx, depth = unbatched_raytrace(octree, spc.point_hierarchies, spc.pyramids[0], spc.exsum, rays_o, rays_d, level=level, with_exit=True, return_depth=True)

# [passed]  expected: has intersection; result: has intersection.
rays_o = torch.tensor([[1.0e-3, 1.0e-3, 1.0e-3]], dtype=torch.float, device=device)
rays_d = torch.tensor([[0,      1,      0]], dtype=torch.float, device=device)
ridx, pidx, depth = unbatched_raytrace(octree, spc.point_hierarchies, spc.pyramids[0], spc.exsum, rays_o, rays_d, level=level, with_exit=True, return_depth=True)

2. Secondly, it seems that the intersection with the exact voxel's where rays_o resides is ignored.
   However, this intersection still has a meaningful exit depth, with a zero entry depth.

Take the level=1 dense octree for example:
when rays_o=[[0.1, -0.1, 0.1]] and rays_d=[[0, 1, 0]], there are only 1 intersection with depth=[[0.1, 1.1]];
but sometimes (e.g. in my use case) the intersection with the current voxel (depth=[[0, 0.1]]) is also needed.

[Caenorst]

Hi @ventusff , it looks like both issues are related.

Will be a looking for a fix for 2)

[github-actions]

Stale issue, please reopen if still relevant