Advise needed to approach problem

Hello everyone,

In the application I am working on, I will need to know if certain objects (some of which move) can be reached by EM waves originating off some source point. The waves can find an object via two methods, either by line of sight, or by reflections (for example up to two reflections maximum). As you can imagine, this will mean I will need to create several rays off the source point that can detect collisions, and I will need to do that in real time. A simple but perhaps very ineffective way to this problem would be to create several CollisionRays.

Does anyone have any better ideas regarding how to approach this problem? Would it be possible to use a Shader/ Compute Shader and utilize the GPU more? If so, how?

Thanks in advance,

How many rays are you talking about? Modern character controllers already use something like a dozen ray casts, so I would just try something with ray casting and see if you run into performance problems.

Some notes to help with performance:

  • Bullet may be able to handle more ray tests than Panda’s builtin collision system
  • Try to use basic shapes like spheres, boxes, and capsules as these have the quickest ray collision checks
  • Avoid doing ray casts against polygons if you can help it (these are the slowest)

Is Bullet the most effective way of detecting these ray to object collisions? For my situation every object in the scene is modeled using a collision box. However I do not speak of just a few dozen rays, I expect the number to be in the thousands. I will therefore need my collision detection system to be as effective as possible. If I am not mistaken most collision detection algorithms are based off vector math which GPUs excel at, so perhaps (I could be wrong) a GPU collision detection system would be the best way to approach such problem. But is it even possible? It is certainly not a common thing to ask.

Hmm… I’m not confident in the following, so take it with some salt. But that said, some thoughts:

When you speak of having thousands of rays, is that because you intend to have thousands of objects or EM sources, or because you’re simulating the emission of radiation in all directions from the sources?

In addition, how complex is your environment? And do you intend to model any sort of scattering?

If you have only a few objects and sources, are using a fairly simple environment, and don’t intend to model scattering, and given that you intend only a few reflections per ray, then I wonder whether there might not be a simplified approach. Perhaps you could calculate, for each object, EM source, and surface what reflections would be required to get from source to object in each of one or two bounces, and only test rays along those? (After testing direct line-of-sight as a potential early-out, that is.)

(This might also go well with some form of spatial partitioning to cull away objects that can be assumed to be unreachable from a given EM source–if there are five rooms all with closed doors between a given object and a given EM source, then it’s probably safe to assume that a ray won’t get from the latter to the former, after all.)

Thousands does sound like more of a problem. This could be done with the GPU using compute shaders, but it isn’t exactly straight-forward. I do see some docs here (I haven’t read over them yet). The general steps would be:

  • Store ray sources and collision objects in a buffer that you upload to the GPU
  • Run a compute shader for each source and check against all collisions objects; store the result in another buffer
  • Download the buffer back to the CPU and analyze results

You could also do this with a vertex shader (model each source as a vertex) with raster discard. This would avoid the need for computer shaders, but would still likely rely on image load/store, which is still an OpenGL 4+ feature.

I thank both of you for the interesting suggestions.

As for what I am simulating, indeed it is the emission of radiation in most directions off a few/one source in an environment that is neither too complex but nor too simplistic (made of collision-boxes, although some of them are moving). Because of the high complexity of scattering, I do not believe I will attempt simulating it.

Just like baked lighting, perhaps I could calculate everything ahead of the real-time simulation, although this would mean potentially storing all the alternate paths of rays in relation to where they pass through (such as a dictionary made of integer locations and a list of all the paths that lead to it). However this too poses problems, as we speak of 3-dimensional space coordinates off an environment that is fairly large (at least 100 by 100 by 40 units). And this would not just solve the problem entirely as I would then need to account for moving objects during run-time.

Having looked through the internet, GPU collision testing is not a fairly common approach but it has lead to some impressive results that one may argue are orders of magnitude better than using the CPU. I will attempt using the compute shaders although I am completely new to GPU programming so this may take a long while.

If anyone in these forums has attempted anything similar or knows of a better alternative, help would be greatly appreciated.