79807534

Date: 2025-11-03 04:32:42
Score: 1
Natty:
Report link

The problem here is with the something's in your question. Those somethings are kind of important. Is it a circle? a sphere? a cylinder? a triangle? an AABB? an OBB? a plane?

The basic principle is to start from two equations; one for a point on the ray, and one for the something.

Sometimes we can use simultaneous equations directly to say:

RayPos + RayDir * d   -   EquationForPointOnTheSomething == 0

Or, you use a distance test:

std::distance((RayPos + RayDir * d), (EquationForPointOnTheSomething)) == 0

In both cases, you need to solve for 'd' (Which hopefully will boil down to something nice to solve, like a quadratic equation). In some cases, you may find you need to solve a multivariate equation, e.g.

RayPos + RayDir * d   -   BezierPatchEquation(u, v) == 0

In this case, you'll need to solve for d, u, & v at the same time. Assuming that this is in 3D, that should work nicely using a JacobianMatrix.

RayCircle example

Equation for a circle at the origin: x^2 + y^2 = r^2 Equation for point on a ray: RayPos + RayDir * d

Combined: (RayPos.x + RayDir.x * d)^2 + (RayPos.y + RayDir.y * d)^2 = r^2

Now expand out the brackets:

RayPos.x^2 + 2*RayPos.x*RayDir.x*d + RayDir.x^2*d^2 + 
RayPos.y^2 + 2*RayPos.y*RayDir.y*d + RayDir.y^2*d^2 - r^2 = 0

Factoring out d^2, d, and the constants:

d^2 * (RayDir.x^2 + RayDir.y^2) + 
d   * (2*(RayPos.x*RayDir.x + RayPos.y*RayDir.y)) +
1   * (RayPos.x^2 + RayPos.y^2 - r^2)  = 0

We can simplify further, by noticing that these are dot products:

d^2 *   dot(RayDir, RayDir) + 
d   * 2*dot(RayDir, RayPos) +
1   *  (dot(RayPos, RayPos) - r^2)  = 0

So now we have a standard quadratic polynomial, of the form ax^2 + bx + c = 0, where a,b,c are:

a =   dot(RayDir, RayDir)
b = 2*dot(RayDir, RayPos)
c =   dot(RayPos, RayPos) - r^2

Pass into the quadratic formula, voila!

Interestingly, if you use the dot product form, this would also work for a Ray/Sphere test. If you want to ray test against a circle that is not at the origin, subtract the circle position from the ray position first.

Now for the complicated part....

Your game world will be constructed from a large soup of differing primitives: Spheres, Planes, Boxes, triangles, quads, etc.

To find the closest intersection, you need to test the Ray against ALL of those primitives, to find the one with the closest intersection. As your game world complexity increases, the computation time will typically rise exponentially.

How to fix that??

Typically you need to start with some form of spatial partitioning scheme. (E.g. BSP trees, Quad trees, Oct Trees, Kd Trees, AABB trees, Portals, and many many more!). With any luck, that spatial partitioning scheme should be able to reduce the amount of objects you need to test against, hopefully keeping you within a reasonable CPU budget.

With a lot of work, you can usually find a way to batch up similar ray test types, potentially optimize them with SIMD, or throw in batches at a GPU compute shader.

The other alternative, is to simply use an existing physics engine (e.g. Havok, PhysX, Bullet), because they've already done the hard work for you!

Reasons:
  • Blacklisted phrase (1.5): any luck
  • RegEx Blacklisted phrase (1.5): How to fix that??
  • Long answer (-1):
  • Has code block (-0.5):
  • Contains question mark (0.5):
  • High reputation (-1):
Posted by: robthebloke