#
Raycasting Length Does Not Matter; Localized Scene Geometry Complexity Does

A lot of people here do not know what they are talking about. And that is fine! *This is a very complex topic.* Let’s clear up some confusion!

As this is also a fairly complex topic so I’m going to skip over quite a bit of math here – it would be out of scope to explain affine geometry, barycentric coordinates, and linear algebra.

##
The Complexity of Raycasting: How Many Operations Do We Need?

A scene in computer graphics is made up of lots (usually in the order of millions) of triangles. Triangles are a useful structure from which to construct 3D geometry because they have some nice mathematical properties that make them easy to project, calculate intersections against, or otherwise manipulate.

Specifically, a ray-triangle intersection involves solving a series of linear equations to find a point in barycentric coordinates, then conducting a simple comparison to see if that point actually lies within the triangle.

The following slides are from a computer graphics course taught by Professor Albert Chern at UC San Diego. If you are interested in this stuff, I recommend you take a deeper dive there.

To perform your typical raycasting operation, you need to conduct a ray-triangle intersection against every triangle in the path of the ray.

**A naive implementation would be to solve a ray-triangle intersection against every triangle in the scene.** This would be very slow; your typical part in Roblox has 12 triangles (2 triangles per face on 6 faces), so if you had 1000+ parts in a scene, you would be performing a large number of operations.

However, we know that a ray has a specific path in the scene. Consider the 2D example below. For most rays, we also know there exist at least a handful of triangles in most cases that will never intersect the ray.

If we come up with some clever scheme to sort the triangles in our scene, then we can skip calculating triangle-ray intersections against triangles we know we will never hit.

And that is what Roblox (as well as most computer graphics applications of raycasting) does!

##
Spatial Partitioning

Under the hood, Roblox implements some form of Spatial Partitioning to make Raycasting faster.

Spatial partitioning the organization of a geometric scene into smaller “partitions.” The idea is that if we organize our scene into smaller parts in a certain mathematical way, that will give us certain mathematical properties. From those properties, we can easily know which partitions contain our ray, and which partitions do not contain our ray. If a partition does not contain our ray, then it is impossible for a ray-triangle intersection to take place against any triangle in that partition, so we can just ignore those triangles in our calculation.

There are different spatial partitioning algorithms out there that are better in certain cases; BST trees, k-d trees to name a few. We don’t know which type Roblox uses unless they tell us, but the overall idea is the same: Roblox, under the hood, is using spatial partitioning to make raycast operations faster by ignoring triangles the ray will definitely not hit.

##
Takeaways

Overall, I don’t think you should worry about Raycast length, or raycast performance for that matter. Under the hood, your scene will be partitioned, so most raycasts will be very fast.

If you do care about performance, then the real thing to minimize is not raycast length, but **scene triangle count**. The more triangles there are in the scene, the more complex the spatial partition will be to traverse under the hood, which will mean longer raycast times.