3
\$\begingroup\$

The problem: A player entity wishes to throw a ball from a known position with a known initial velocity. The surrounding environment contains physical objects that can alter the trajectory of the ball. How can this trajectory be as accurately as possible be rendered?

One solution: perform small steps and simulate throwing the ball. During each small step, a raycast is performed against the world to find potential colliding bodies. In case a collision is reported, it must be handled accordingly. The intermediate positions of the ball will then be saved in an array and the trajectory should be described by the succession of these points.

While this solution works (it is tested and doesn't fail almost never :) ), are there any workarounds or possible optimizations that can be done to avoid performing the raycast queries too often? It would be nice if there were such a thing as a parabolic caster instead of a linear ray caster. Do you know of any existing solution that is better of the one I just described (that either avoids those many raycasts or performs a more clever kind of query to reduce the number of intermediate steps and replace the actual line segments with parabola segments)?

\$\endgroup\$

3 Answers 3

Reset to default
2
\$\begingroup\$

Well I think it's possible to solve parabola/shape intersection equations. But first the problem is; I think it would be tricky to solve for more complicated shape and the intersection algorithm performance I suspect won't be that good. (Actually this is very obvious in the link @IcyDefiance provided in the comments).

Secondly and the far more important problem is that parabolic casters can't take advantage of spatial data structure, traversing a spatial data structure is far simpler when you assume the ray is going in a straight line, bend that path and most the traversal assumptions don't hold anymore. For example the faster ray octree intersection algorithm actually does exploit the ray and octree analytical properties, for example it assumes if a ray was in a certain cell it can only go through some other neighbor cell. Add a parabolic shape and those assumptions will vanish.

My recommendation

Stick with the ray casting technique with a memory coherent spatial data structure.

It doesn't make sense to test for intersection for every object in the scene anyway, using a spatial data structure is a must. I also suspect that if the data structure was cache friendly then ray casting the scene will be far less demanding.

Final Note

Something I just thought about but never tested, is to use asynchronous casting. Meaning; instead of doing one step at a time you can do each 4-16 steps together asynchronously, to be honest I never tried this and don't know if the performance will be better or worse. You just need to generate the samples first, and then do asynchronous test, similar to what people do in ray tracing, the difference is that samples will be for a parabola rather than an image.

\$\endgroup\$
3
  • \$\begingroup\$ I didn't want to add it as an answer, but wikipedia has equations for that parabola thing here: [link]. You're right about its limited use, but the link may be useful to someone. \$\endgroup\$ Commented May 9, 2014 at 17:02
  • \$\begingroup\$ @concept3d the asynchronous casting sounds nice, although I can't use it (I don't have any other threads for this job at the moment). But if I had, how would you assure the spatial and temporal coherence by doing different casts simultaneously? \$\endgroup\$ Commented May 9, 2014 at 17:16
  • 1
    \$\begingroup\$ @teodron This specific point needs profiling and really hard to speculate, but what I would say that even up to Level3 cache is good, it doesn't need to be in one cache level. In the end you need to maximize cache hits and not make it 100%. Generally speaking the results will vary based on the scene and the samples structure. \$\endgroup\$ Commented May 9, 2014 at 17:45
2
\$\begingroup\$

Unless you are in a situation where you NEED to optimize, don't waste your time on it. Avoid unnecessary premature pessimism, and premature optimization.

For the sake of submitting some ideas I had though, here is what I have come up with.

Depending on how much control you have over your system, a more accurate version would be to simulate an object in a separate "compartment", and trace the path. This would require you to maintain a mirrored subset of objects that it could interact with, as well as simulate at a different time step.

PhysX has (last I knew) native support for compartment based simulation, though I am unaware of whether or not it allows separate timesteps for different compartments. This is definitely the most accurate way you could do this, but the overhead associated with it could be pretty unacceptable.

An alternative method would be to calculate the path that the projected object would take independent of the physics sim. This could get complex if you have forces other than gravity affecting the ball. After plotting this path, a minimal set of tangents could be pulled from the path to represent an efficient set of raycasts. This method would require iteration, and would likely incur a higher calculation penalty, while the previous method has a higher data penalty.

\$\endgroup\$
3
  • \$\begingroup\$ Sadly this is a mature optimization attempt, the solution I gave in the answer is good, but the raycasts are a killer. The alternative method you proposed is actually identical to what I'm doing, provided you could somehow propose the most efficient "minimal" set of tangents.. \$\endgroup\$ Commented May 9, 2014 at 17:14
  • \$\begingroup\$ To be more concise, I'm using Havok, so the compartment based simulation might be out of the question :(. Good to know about such a mechanism though! \$\endgroup\$ Commented May 9, 2014 at 17:18
  • 1
    \$\begingroup\$ I would say determining the acceptable number of tangents would be relative to a few things. Based on the derivative, you would have to make some sort of executive decision about how drastic this change is before you declare a new tangential point. Additionally, this could lead to wasted or overlapping rays in some situations. There would always have to be some level of acceptable error. \$\endgroup\$ Commented May 9, 2014 at 18:14
1
\$\begingroup\$

For a game, piecewise linear approximations of the parabolic path are fine, don't waste time going beyond that.

Also, use someone else's well-tested, well-optimized physics and collision engine.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.