Distance Between Points on a “Toroidal Disk”

Life update: I’m now doing applied graphics research at EA SEED and really digging it. Really great people, great work to be done, and lots of freedom to do it. I’m really stoked, to be honest.

In a previous post, I wrote about how to calculate the distance between two points in a rectangle, where the rectangle edges wrapped around. That is, if you leave the rectangle by going past the right edge, you’d end up coming out of the left edge. If you go past the top edge, you’d come out of the bottom edge.

Calculating the Distance Between Points in “Wrap Around” (Toroidal) Space
https://blog.demofox.org/2017/10/01/calculating-the-distance-between-points-in-wrap-around-toroidal-space/

This weird space can be thought of as a toroid, or a doughnut. If you start at a point on a doughnut and go “upwards” on the surface, you’ll circle around back to where you started. Similarly, going left, you’ll circle around the doughnut and come back to where you started. More technically, this space is a “flat toroid” though, so isn’t quite the same thing as a doughnut. Video games have used this space for their game worlds, such as the classic “Asteroids”.

How was collision detection done on the Asteroids arcade game? -  Retrocomputing Stack Exchange
Asteroids: One of the first of many games to take place on the surface of a doughnut

I was recently experimenting with something (the experiment failed unfortunately ☹️) that involved working in a disk where going to the edge of the disk would teleport you to the center of the disk, and going to the center of the disk would teleport you to the edge of the disk. It’s like if you squished a doughnut flat to make the center hole infinitely small, and you removed the back side of the doughnut.

As part of this work, I needed to be able to calculate the distance between two points in this strange space.

It was a fun problem, so maybe you want to give it a shot before i explain how I did it. I’d love to hear what you come up with, either here as a comment on this post, or on twitter at https://twitter.com/Atrix256.

My Solution

Ok so I knew that there would be a few ways to get from a point A to a point B in this toroidal disk, and that we’d want to take the shortest of these paths as the length between them.

One path would be the line in the circle between the points.

Another path would be from point A to the edge of the circle, to get to the center, and from the center to point B. It’s interesting to note that these lines don’t have to be parallel!

Another path would be from point A to the center of the circle to get to the edge, and from the edge to point B.

Now for some stranger cases…

You could go from point A to the edge, to the center of the circle, then back to the edge at a different location and to point B.

You could also go form point A to the center, change direction and go to point B. This last case could only be as short as the “interior” path at minimum, so isn’t really a case we have to consider, but I’m including it for completeness.

Ok so we could turn this into code with a bunch of if statements to handle each case, but we can simplify this logic quite a bit.

First up, we do have to calculate the distance between the points in the circle the normal way, there’s no avoiding that. We’ll call that the “interior distance”.

Next, think about the paths point A can take to point B that aren’t through the disk. It can either go to the edge or the center, and we’ll want to keep whichever is shorter as the distance for the first part of the “exterior distance”. Since we want to take the shortest path to the center or the edge, we can just use the point’s radius as the distance form the center and 1.0 – radius as the distance from the edge (assuming a radius 1 circle). We’ll take the minimum distance between those two as the first part of the exterior distance path.

Next, it doesn’t matter if point A went to the center or the edge, the path can come out of either the center or edge and continue to point B. So, we again want the minimum of the distances: point B to the edge of the disk, or point B to the center of the disk. once again it’s the minimum of the radius and 1.0 – radius.

Adding those two distances together we get the “exterior distance”

The “Exterior Distance” Is min(A1, A2) + min(B1, B2)

The final answer we return as the distance between point A and B is whichever is smaller: the interior or exterior distance.

A fun thing is that while we have been working in 2 dimensions, this actually works for any dimension.

Here is some C++ code to calculate the distance:

// walking past the end of the circle brings you back to the center, and vice versa
// Assumes your points are in [0,1)^N with a disk center of (0.5, 0.5, ...)
template <size_t N>
float DistanceUnitDiskTorroidal(const std::array<float, N>& v1, const std::array<float, N>& v2)
{
    // Calculate the distance between the points going through the disk.
    // This is the "internal" distance.
    float distanceInternal = Distance(v1, v2);

    // The external distance is the distance between the points if going through the center
    // or past the edges.
    // This is the sum of the distance between each point and either the circle edge or the
    // circle center, whichever is closer.
    float distanceExternal1 = Length(v1 - 0.5f);
    distanceExternal1 = std::min(distanceExternal1, 0.5f - distanceExternal1);

    float distanceExternal2 = Length(v2 - 0.5f);
    distanceExternal2 = std::min(distanceExternal2, 0.5f - distanceExternal2);

    float distanceExternal = distanceExternal1 + distanceExternal2;

    // return whichever is less, between the internal and external distance.
    return std::min(distanceInternal, distanceExternal);
}

Again, I’d love to hear your thoughts, or any alternative methods you may have come up with, either here or on twitter at https://twitter.com/Atrix256. Thanks for reading!

Update

On twitter, https://twitter.com/Mal_loc mentioned that it would be nice to see the distance from one point to the rest of them visualized, to get a better sense of how this distance function worked. That was a great idea so i made an interactive shadertoy: https://www.shadertoy.com/view/NsBcDD

Here are a few images. The blue dot is the point that the distances are calculated from. Red is no distance, Green is full distance.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s