0
\$\begingroup\$

I understand in unity there is Phsyics.LineCast(Vector A, VectorB). What's the maths behind doing that, the only thing i can think of is going along the line at small intervals and seeing whether it collides with an object or setting the line as a cuboid with a small width and height but depth equal to vector1-vector2 but then that would be non-axis aligned cuboid collision which seems pretty expensive.

Could anyone help me on this?

EDIT: I just want to know how to draw a line between two objects and see whether another object obstructs that line. That's it. Yes this is in DirectX.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Have you searched previous questions here on various ray intersection formulas? (Ray vs sphere, ray vs box, ray vs triangle, ray vs voxel grid...) I bet those could give you some good clues. \$\endgroup\$ – DMGregory Jan 17 at 15:23
  • \$\begingroup\$ Help you with what? What kind of issue are you facing? \$\endgroup\$ – Vaillancourt Jan 17 at 17:43
  • 1
    \$\begingroup\$ Welcome to GDSE. Your question references the Unity LineCast method, but you've tagged the question with DirectX. If you're trying to figure out how can I find line intersections/collision using DirectX, it's better to directly ask that as your question. Unity isn't open source, doesn't document the implementation specifics of LineCast & asking us to speculate what they might have done isn't as likely to get an answer as telling us what you are trying to do. \$\endgroup\$ – Pikalek Jan 18 at 1:53
  • \$\begingroup\$ @Vaillancourt i need it because I want to cast a line between two objects and see if there's an object in the way. \$\endgroup\$ – user146777 Jan 18 at 15:45
1
\$\begingroup\$

The math behind Physics.LineCast(A, B) is what we call a ray intersection test.

We take A to be the origin of the ray, B-A to be the direction of the ray, and look for potential intersections along the line P(t) = A + (B-A)*t for 0 <=t <= 1 (or other equivalent formations that differ only in details)

For many shapes, we have a closed-form formula we can apply to find the specific t value where the ray hits it, if it does at all. If there's no such value of t, or the intersection happens at t < 0 or t > 1, then there's no intersection with our line segment.

Different shapes will use different formulas:

So this gives us a simple algorithm: loop over all the collision shapes in your scene, apply the corresponding ray intersection formula for each one, and keep the lowest value of t you find in the range 0...1.

This will give you correct results, but it's not fast. We waste a lot of time evaluating the formula on objects nowhere near the ray, or on distant objects likely to be occluded by something closer.

So we apply an acceleration structure to help us zero in on just the shapes worth checking, ideally in roughly front-to-back order. That lets us keep the correctness, while making the test much cheaper/faster.

There are a lot of forms this could take, depending on your needs:

  • We could divide your world into a grid of cells, and store collision shapes in each cell they overlap.

    Then we can march the ray through this grid (kind of like Bresenham's line algorithm), so that we visit each cell in front-to back order.

    For each cell we visit, we run the intersection formulas on just the shapes in that cell, skipping any cells our ray doesn't touch.

  • We could group objects into a bounding volume hierarchy, and test our ray only against the bounding volume of the root node of that tree. If we find a hit, we test against the bounding volume of its children, and recurse this way until we narrow in on the intersecting objects to run the fine-grained formula on.

    We usually use a very simple shape for the bounding volumes, so that test is fast, letting us quickly discard large swaths of the scene.

For all these approaches, it's important to know when to stop. The first hit you found isn't necessarily the nearest hit - it could be that the next object you check has a closer hit point. We can again use a bounding volume to estimate the closest possible hit on an object, and stop our search once the closest possible estimate is further away than the closest hit we've found, guaranteeing that we do indeed have the closest result now.

\$\endgroup\$
-1
\$\begingroup\$

Figured it out, thanks to everyone who actually tried to help instead of just asking me why i needed to do this.

Use z=mx+c. sub in the two objects positions to work out m and c. Then sub in z and x values to see if it collides with other objects in the scene.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.