Question How do I make physics raycasts hit mesh point clouds?

I have a mesh point cloud that's constantly changing, it's coming from a lidar camera.
How do I let it be hit by physics raycasts in real-time?

 

some options:
- if that view has depth texture https://github.com/staggartcreations/Graphics-Raycast
- manually calculate (look for: ray intersects point, get closest point on ray)
- update mesh collider every frame based on those points (could be pretty slow, but could probably skip every x point, or only collect points where it changes on depth)

which lidar that is? (does it send image as depth map, or actual point cloud points)

 

Some important additional information you need to supply:

Mesh Point Cloud: Is this to imply it comes with a mesh or merely that you have a point cloud that could at some point in the future be used to create a mesh?

How frequently is the data being updated. "Constantly changing" is not very informative. You should have a sample rate limit that the lidar can supply and you must also have a minimum rate at which you need to process the data. What is the limiting factor? How much can the scene feasibly change between samples (i.e. do you need to process each update). Until recently even fancy automotive systems were only running at about 10Hz.

Is the cloud created from a single source? i.e. can some points lie behind others, if your target was a box, do you have points on just the front of the box or also on the back? Are you ray casting from the same point that the point cloud was generated from (please say yes).

How many points?!

During a single cycle of processing the data, what is the maximum number of rays that you need to cast? This will determine how much effort to invest in optimising your data.

What are the consequences of error (this does not look like a game)?

Hardware limits, what is the minimum spec platform this needs to perform on? (typical steam setup or some sort of research box with a rack of 4090s in it?). Have you done any benchmarking, e.g. at a most basic level how long does it take you to measure the distance of each point to your cast vector without any optimisations (points per second you can process on the target platform)? You could also implement a fast surface mesher, e.g. Ball-Pivoting or some Delaunay variation. It depends how many casts you are doing per update to see if the cost of meshing is worth it.

Make sure you benchmark to get the fastest distance measure / mesh routine.

If measuring point distances from vectors, be aware of depth of field induced errors (sample points further away will be less densely packed, making closer point groups appear nearer the vector than distant point groups).

Have you considered using DOTS physics (https://forum.unity.com/forums/dots-physics.422/). Nearly all of the maths here works well in parallel.

 

I tried creating colliders, and the performance was very slow, takes around a second to make the collider.
And yes, I thought there'd be a method for it.

 

Said lidar for simplicity, it's actually an Intel Realsense D415, I have the option of either a depth map, or a mesh point topology
I'll look into graphics-raycast, seems promising
Manually calculating wouldn't work for me, since there's around 640 x 480 = 307200 points, and I'd like to do thousands of raycasts at 30 fps
I tried updating the mesh-collider but it's very slow and down-scaling isn't an option for me

 

why do you need that many raycasts?
*ok saw your reply below.

 

"Mesh Point Cloud: Is this to imply it comes with a mesh or merely that you have a point cloud that could at some point in the future be used to create a mesh?"
My Intel Realsense Camera supplies me with a depth map, and then I convert the depth map points to vertices, and then render a Mesh Point Topology.

"How frequently is the data being updated"
30 FPS

"What is the limiting factor?"
The limiting factor is my own code, I'd be fine with it running at 1 - 3 fps but it runs much slower

"How much can the scene feasibly change between samples?"
I'm making a tool in which the user specifies a 3d model, and then a projector projects colors on different spots of the users surface indicating where they should build in order to make the 3d model. Due to this, If I were to use mesh colliders, I'd have to update the mesh every time.

"Is the cloud created from a single source?"
Yes, it's relative to the camera which is centered at (0,0,0), but I allow the user to rotate the point cloud.

"Are you ray casting from the same point that the point cloud was generated from"
No, I raycast from the location of the projector, relative to the location of the camera

"How many points?"
640 x 480 = 307200

"During a single cycle of processing the data, what is the maximum number of rays that you need to cast?"
~30k

"What are the consequences of error?"
If it's slight, it's negligible, as even the camera's point cloud has approximation errors.

"Hardware limits, what is the minimum spec platform this needs to perform on?"
I have an RTX 3060, with an i7-4790k core, and 32GB of ram

"You could also implement a fast surface mesher, e.g. Ball-Pivoting or some Delaunay variation. It depends how many casts you are doing per update to see if the cost of meshing is worth it."
I tried generating a triangle mesh topology by using the depth map. If two vertices were adjacent on the depth map, I'd connect them, this turned out to be very slow.

"Have you considered using DOTS physics?"
I think that's what I'm using, I already have the code, but it requires raycasts to be able to hit the mesh point topology

 

If you're using DOTS then you need to post on that forum. It seems to me a big ask to process the amount of data you are talking about here in PhysX on a single thread, so that is probably a good choice. That said, if it was me, I would experiment with this route:

Efficiently sort the data points into searchable buckets/cells of data, e.g. look at octree / kd-tree type approaches (there are also others specifically aimed at cloud point data, so worth doing some research), because one thing is for sure - you don't want to check 30k casts against 300k points. You just want to check viable points.

I would then check each point in the local bucket for its perpendicular distance to the ray vector (make sure this is as cheap as possible), if the distance is within my tolerance then I add it to a list of viable ray hits, take the point from the list that is nearest the origin and that will be the hit for that ray.

Optimisations to consider:
You want to minimise the number of points that you actually do the ray distance check on, so picking the best bucket strategy is important - aim for equal numbers of points in each bucket. You need to balance the processing cost of setting up the buckets versus the processing save for the number of checks for each ray.

Don't run this from Update, use some strategy that allows you to do this at a controlled frequency and start by just doing it once so you can see how long one cycle takes.

I would look at moving this to a compute shader, as it seems like the type of problem well suited to one. Perhaps DOTS is also viable, but I don't know anything about that

 

Got it all working, I had to make an algorithm that doesn't use raycasts.
Basically, I map each point on the pointcloud to a ray that would hit it, then round that ray to one that corresponds to a projected pixel path ray ( which is O(1) ) instead of casting a ray and then iterating through every point to find the closest point to the ray.
This makes computation O(points) instead of O(points * amount of rays)
Computation became surprisingly quick after, and runs at >30 fps.