Raycast in Softbodies vs Rigidbodies

[blito]

Hi all,

I'm trying to model ultrasound rays going through human organs. I figured I could use Bullet since it provides an easy to use raycast API and softbody physics, although I have almost no previous experience using it (or any other physics engine for that matter). I picked a kidney from this dataset, and shot a ray through it, recalculating its refraction direction using Snell's Law.

I followed this SoftBody from OBJ example and this Raytest example and created a new entry in the Examples Browser. Ended up with something like this:

.

Pretty good!
Blue spheres indicate when the ray gets into the kidney, red ones when it goes out. I aimed the ray at a spot where the mesh has a "valley", where the kidney gets concave.

You can see it in a more detailed fashion in this picture, using a much more detailed mesh:



I tried going up with the number of rays, no problem:



I was able to shoot 500 rays at 15fps, using an i7-4510U. Removing rays' rendering led to a little bit more than 30fps.

I figured having a rigidbody would improve performance, so I went ahead using the RigidBody from OBJ example. However, performance dropped to 2fps! Completely removing raycasting leads to 45fps, so raycasting + rigidbody is clearly the problem here.

So, to sum up:
- 1 Softbody + 500 rays = 15 fps
- 1 Softbody + 500 rays (but no ray rendering) = 30fps
- 1 Rigidbody + 500 rays = 2 fps
- 1 Rigidbody = 45 fps

Question 1: I was wondering if anyone could point me in the right direction as to why this is happening. My guess is that the raycasting algorithm checks for the rigidbody's bounding box, and tests against every triangle inside of it, so it ends up doing 500*number_of_triangles tests. I don't know why the softbody doesn't exhibit this behavior. From what I understand, this should be done in Broadphase, right? What can I try to fix this?

Question 2: Which is the right way of adding rigid and soft bodies in the same world? I'm thinking about adding ribs to my model (which are also in that dataset), but I'd rather make them completely rigid.

Question 3: I found the function call generateBendingConstraints (called here) takes a very long time with more complex meshes. Looking through Bullet's code I found a comment saying it's doing a Floyd's algorithm, which is O(v^3). Is there any way to have that precalculated? This is one of the main reasons pushing me to use only rigid bodies, although I can't until I figure out how to do raycasting properly.

My code is at https://github.com/Blito/bullet3/tree/softbody-raycast. It's added as an example in the Examples Browser. I'm using MinGW + C++11, but it should work on any C++11-enabled compiler. I didn't push the meshes I'm using, but you can probably make it work using one of the meshes provided in the other examples.

Thank you for your time!

[benelot]

Hello!

First of all, I am very happy you found the SoftBody and RigidBody from OBJ examples useful, they were made only recently and they seem to be useful and intuitive as I see (At least they helped you to implement your simulation ). Congratulations to your simulation, it looks very great.

1) I also would expect that they would take about the same time to perform the same amount of raycasts. The softbody behaves differently from a rigidbody, but at the time of a raytrace, it should be exactly the same (like an object's movement compared to the speed of light, it barely moves as the light comes in. A similar velocity ratio is between your simulated organ and the ray.) But I do not know the reason exactly, but I see that the kidney is not convex, but you are using a btConvexHullShape. That might cause issues with the collisions for one. Have a look at the other shapes here: http://www.bulletphysics.org/mediawiki- ... Primitives and see if you can use another shape. it says in the documentation that convexhull shape is the fastest, however, it also says that you should keep the number of vertices below 100 for some reason ("Make sure to reduce the number of vertices below say 100. Reducing the number of vertices can be done automatically using the btShapeHull vertex reduction utility."). Let us see what you can do with this.

2) The right way of adding rigid and soft bodies to the same world is to use addSoftBody() and addRigidBody(). They are both available on the btSoftRigidBodyWorld (If you do not store it in a btSoftRigidBodyWorld* but a btDiscrete...World, you might have to change the type or cast it when using it). Since your example inherits from CommonRigidBodyBase, it stores your world as I say and you really need the cast. This cast is already performed by using getSoftDynamicsWorld() in your example.

3) Unfortunately I do not know a lot about the softbody world implementation but from what I see in the example, it only performs this method within the add_softbody_from_obj method, so only on startup. Is that not precalculation as you want?

It seems that the btSoftRigidBodyWorld has its own castRay method, check that out as well, it might be faster.

Cool thing! I first thought you are just showing us your beautiful setup and wanted to point out to you that you should move this post to the showcase here http://www.bulletphysics.org/Bullet/php ... m.php?f=17.

[blito]

Thanks for your answer benelot. I got back to the problem yesterday and was able to produce some results.



This scene has 589878 triangles and 2500 rayTest calls (500 rays with to 5 refraction bounces each), and runs at ~6 fps.

1) I ended up using a btBvhTriangleMeshShape. Performance is pretty similar, ~3 fps faster than the soft body approach for a single mesh. I tried changing the broadphase algorithm from btDbvtBroadphase to btAxisSweep3, but I got no noticeable change in fps. Maybe I'm not setting aabb_min and aabb_max as efficiently as possible.

3) The issues I found with generateBendingConstraints seem to be also documented here. My times are definitely better than those reported, although some very complex meshes (150k vertices) take forever to calculate (I've waited 20 minutes and it wasn't finished). I definitely can't wait 20 minutes every time I load up the program, that's the kind of precalculation (and loading) that I was looking for. In any way, the most detailed meshes in this problem belong to bones and veins, which I think can be made rigid without hurting realism too much.

I still have to add materials to the different meshes so that rays will start refracting again. I'll try doing a hybrid scene too, so I'll probably come again with more questions.

Can you think of any performance bottleneck I should be watching? I'll add reflection bounces too, so performance will likely be hit a little bit more. I already have a few improvements in mind which are domain related (killing a ray when it reaches a certain energy threshold, for example), but there are probably others related to the use of Bullet.

Thanks for your help!

[Erwin Coumans]

That looks nice. Do you mind creating a pull request to add this example in the Bullet Example Browser? That would add a motivation to improve performance: https://github.com/bulletphysics/bullet3/pulls

I just created an issue to accelerate the btSoftBody::generateBendingConstraints
https://github.com/bulletphysics/bullet3/issues/845

For best performance, ray intersection against complex meshes is a good candidate for GPU acceleration, recovering the OpenCL pipeline of Bullet 3.x (mostly unused at the moment).

On CPU, ray intersections can be multi-threaded with a little bit of work, and you could use a 'batch' ray cast to reduce calling overhead.

[blito]

Hi Erwin. I'll try to do the pull request this week. I did it in MinGW using C++11, so I had to change a few things in Bullet's code for it to build (I didn't push those changes to my fork though). I'll make sure it works in gcc in C++98 at least.

I've been working these last days in taking the example I did in the browser to a standalone program [here]. I got rid of graphical output, so the only way I know I'm getting the same results is by checking the amount of positive ray tests (I have a completely rigid scene now). What caught my attention was the increase of fps. I was at ~15 fps using the examples browser, and at ~140 while running it in a console application. Now that I know that the rendering was taking up that much cpu, I may give softbodies another shot (for which I will need better performance at btSoftBody::generateBendingConstraints).

I'll post another screenshot on Monday when I get to work. I added acoustic properties to tissues and rays now reflect and refract accordingly, it looks pretty nice. I also added some pruning to avoid 2^(ray_collisions) raytests.

What did you mean by "recovering the OpenCL pipeline of Bullet 3.x"? I didn't try going that route since I didn't find any tutorials or examples at a first glance. Is it working at the moment?

I'll try to read more about generateBendingConstraints and btDbvt. I don't think I'll be able to come up with a fix, but I'll try to see if I understand the problem at least.

Thanks!

[benelot]

What he means by recovering is that the GPU pipeline was built some years ago, but did not work too well, mainly because OpenCL drivers were not ready and stable on most devices. A lot has happened in the GPU business since, so that might need some recovering and updating. The rendering for your model might indeed take a while and so it might improve your performance if you go without. For an example I was trying to make the browser run headless, and it worked quite well, so maybe we can get that into your example as soon as it is up.

[blito]

As promised, here it goes. Rays now bounce using Snell's Law, and have an associated intensity given by Fresnel equations and Beer-Lambert's law, which is used to prune the length of the ray tests.



I don't think I need to render it headless. It'd be a nice thing to have to debug I guess, but the thing I'm actually trying to render is the final ultrasound image, which is made from ray collisions.

Thanks for your help so far!