millions of raycast

Hi all,
I have an application that requires obtaining distances of object meshes at high angular resolution from the player (like a laser scanner). This is in the order of 500k distance calculations at 20Hz.

- I can't raycast to a specific layer since I need to see everything
- I have approximated meshes in the scene using box colliders

The built-in recast system is not built for this. Assuming I have the best hardware out there, what technique do I use?

 

A new algorithm. I don't think there is any technology that can do a 500k raycasts in 50 ms.

If you must use this approach, here are some things to consider.

• Can you bake the raycasts
• Can you spread them out across multiple frames
• Can you use an approximation? Do you actually have 500k polys to collide against?
• Can you work backwards from your colliders

 

Hi,
- I am not familiar with baking
- Spreading them out in frames reduces frame rate
- I can average out rays in between and reduce total to 100k, but this is still large. Polys don't really make a difference. Even if I have 1 polygon, I need detailed information on where the rays hit on the polygon face.

I was hoping there would be a GPU solution to this. I'm not familiar with shaders, but operations like casting shadows probably need this information

 

Baking is the concept of doing all of doing your calculations ahead of time. Light maps, navmeshes, normal maps and the like are all pre calculated before the game is built. This allows your game to use the precalculated values, instead of needing to do expensive per frame calculations.

If you have multiple rays hitting a single polygon, then all of the data can be calculated based on a single ray and knowledge of the polygon.

What's your use case for this? A proper use case might help suggest a better algorithm.

 

btw. vote for this too,
physx raycast batching:
http://feedback.unity3d.com/suggestions/enable-physx-raycast-batching

 

@BoredMormon
My use case is simulation and generation of point clouds. For example, I want to generate something like this: http://www.tms.org/pubs/journals/JOM/0112/News/fig1a.gif

Think of it something like detailed distances from the player. This is to generate intelligent plans for navigation.

"If you have multiple rays hitting a single polygon, then all of the data can be calculated based on a single ray and knowledge of the polygon."
-- Could you elaborate more on this?

@mgear
Good to know about raycast batching

 

btw. If you already have that map, polygons (for that terrain, obstacles etc) then what actually do that many raycasts add to the navigation ? (I mean, even few raycasts would be enough to check distances, if its flying AI or such)

 

What are you navigating with that needs this level of precision? What's wrong with a simple navmesh? Or a height map if you prefer. Either way the picture doesn't look like it was intended to be generated at runtime.

 

+1

 

@BoredMormon Thank you for the suggestions. I cant use a nav-mesh since I have a restriction of using an external AI navigation library that requires a pointcloud infomation around the player. I understand this is not the unity way of doing things, but please humor me.

I guess real time retrieval of a baked height map say of 100m radius around the vehicle is what I'm looking for. I can then pass these 3d point values to the external library. Any suggestions on how I could do this? Again, using this external library is mandatory for my situation.

Something like this is perfect: http://www.pointclouds.org/blog/_images/Building-Side.png

 

That's probably doable. Is your terrain dynamic, or can you compute the entire point cloud in advance?

 

My world is not dynamic. What I have is a city (buildings+ road network) mesh which is static. The vehicle in this world is expected to always move though. So I need an efficient way of retrieving this data around the vehicle. To start off, how do I create a pointcloud of this static mesh in advance?

 

Disclaimer: I've never done this before, but it should work.

I would build an editor script that does the raycasts. For navigation the resolution doesn't need to be that fine, raycasts every meter if you are moving something like tanks around. Raycasts every 0.25 m should probably work for humanoids. If this resolution isn't enough, or gives you weird results, you could always try doing closer raycasts and then averaging the results.

Once you have the collision points from the ray casts you can store this data in a heightmap. A heightmap is just a greyscale image with the height represented by one of the channels.

At runtime you can load up all of the points into an array, then use them as required for your navigation.