2
\$\begingroup\$

I have a circle in 3D space, so we have center C with radius r, and the normal of plane the circle lies on, N. There is also a normalized vector V that I am modifying to go far past the circle's center, so I am multiplying it by a large float value such as 99999999.0f. I need to find the point on the edge of the circle that is closest to the end of this ray.

So far I have tried iterating around the circle parametrically from 0 to 2PI, and for each point I scalar project the vector from the origin to this point onto V, and store the largest value which is farthest along V. This seems to get close to the expected result but is off by 0.0006 or so in my current test, and I finding an acceptable step amount for this loop is tricky.

I have tried to derive another way of doing this without having to iterate over every point, which seems quite inefficient. I had an idea of forming a triangle with the origin, C, and the end of V, but given the arbitrary rotation of the circle I am lost on how to possibly do this. Might there be a simpler way to go about this?

\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

First, if we only care about the endpoint of the ray, then we can forget it came from a ray at all (or really, a line segment, since it has a definite, finite extent). Just think of it as an ordinary point. I'll call it endPoint.

Next, since we're limited to the plane of the circle, we can ignore the distance parallel to the normal — no matter how we try to move our eventual result point, we'll never get any closer or further away on that axis. So we can take the vector pointing from the circle center to endPoint and project it into the circle plane, then look for the closest point to that:

toTarget = endPoint - circleCenter

inPlane = toTarget - circleNormal * dot(toTarget, circleNormal)

(Here I'm assuming circleNormal has length one, but you can divide the normal term by the square of its length if not)

Now we have a vector in the plane of the circle, from its center to the point on the plane closest to our target. If that vector is the zero vector, then every point on the circle is equally close to endPoint, and we can choose one arbitrarily. Otherwise, we just snap to the circle radius in that direction:

onCircle = circleCenter + normalize(inPlane) * circleRadius
\$\endgroup\$
1
  • \$\begingroup\$ This seems to work well, thank you! \$\endgroup\$ Aug 18 at 4:07
1
\$\begingroup\$

I believe DMGregory approach is correct:

Wouldn't this just be the endpoint minus the circle center, projected onto the circle plane, and normalized to the circle radius?

We will break it down to simple operations.


I'm aware you have the circle center \$C\$. And you have a ray with \$V\$ direction. But you didn't provide nomenclature for the ray start and end. Since you are talking about the end of the ray, I'll forget this is about the ray and talk instead of a point which I'll call \$E\$ (for endpoint).

Also, I would expect the normal \$\vec{N}\$ to be already normalized (i.e. it is an unit vector). To normalize you scale it by the inverse of its length: \$\vec{N}*\frac{1}{|\vec{N}|}\$. Where scaling means multiplying each component by the scalar factor, and the length of the vector is the square root of the sum of the squares of the components of the vector.


First: the endpoint (\$E\$) minus the circle center (\$C\$).

We are talking about getting a vector that goes from \$C\$ to \$E\$. Which we do by vector difference:

$$\vec{d} = E - C$$

The vector difference is component-wise subtraction (i.e. it is making a new vector which components are the differences of matching components of the original vectors).

Yes, vectors do not have an inherent position. So when I say that a vector goes from a point to another, I mean that when I place the vector on the first it points to the other.

We need to do this difference because we want to project a point on a plane... Which will require to project a vector on the normal (I'll get to that). Since the normal \$\vec{N}\$ has meaning when placed on any point on the plane... In order for the projection to make sense, we want a vector that goes from some point on the plane to the point we want to project... And \$C\$ is a point on the plane. In fact \$C\$ is the only point we know on that plane, so it is our only option.


Second: \$\vec{d}\$ projected onto the circle plane.

I want you to think that there are two vectors \$\vec{a}\$ and \$\vec{b}\$ such that:

$$\vec{d} = \vec{a} + \vec{b}$$

And \$\vec{a}\$ is in the same direction as the normal \$\vec{N}\$, while \$\vec{b}\$ is perpendicular to it.

Thus:

  • \$\vec{a}\$ is the projection of \$\vec{d}\$ on the normal \$\vec{N}\$ vector.
  • \$\vec{b}\$ is the projection of \$\vec{d}\$ on a plane with the normal \$\vec{N}\$.

We want to get \$\vec{b}\$, but we do not get it directly, instead we get \$\vec{a}\$ and then find \$\vec{b}\$ like this:

$$\vec{b} = \vec{d} - \vec{a}$$

Since \$\vec{a}\$ has the same direction as the normal \$\vec{N}\$, it will be the that normal \$\vec{N}\$ scaled by some magnitude.

What is the magnitude of the projection along the vector? By trigonometry it is \$|\vec{d}|cos(ϴ)\$ where \$ϴ\$ is the angle between the vector we are projecting \$\vec{d}\$ and the vector we are projecting on \$\vec{N}\$.

Therefore:

$$\vec{a} = \vec{N}*\frac{|\vec{d}|*cos(ϴ)}{|\vec{N}|}$$

We are going to get \$cos(ϴ)\$ from the trigonometric identity of the dot product:

$$\vec{d}·\vec{N} = |\vec{d}|*|\vec{N}|*cos(ϴ)$$

Where the dot product is the sum of the components of the component-wise product of the vectors (i.e. we multiply matching components of the vectors and then sum the products we got).

Solving for \$cos(ϴ)\$ we have:

$$cos(ϴ) = \frac{\vec{d}·\vec{N}}{|\vec{d}|*|\vec{N}|}$$

Replacing in the prior formula we have:

$$\vec{a} = \vec{N}*\frac{|\vec{d}|}{|\vec{N}|}*\frac{\vec{d}·\vec{N}}{|\vec{d}|*|\vec{N}|}$$

Which simplifies to:

$$\vec{a} = \vec{N}*\frac{\vec{d}·\vec{N}}{{|\vec{N}|}^2}$$

And now we can get \$\vec{b}\$:

$$\vec{b} = \vec{d} - \vec{N}*\frac{\vec{d}·\vec{N}}{{|\vec{N}|}^2}$$

And assuming \$\vec{N}\$ is a unit vector:

$$\vec{b} = \vec{d} - \vec{N}*\vec{d}·\vec{N}$$

Yes, that is the projection formula you have seen before, barring variable names and notation.


Third: \$\vec{b}\$ normalized to the circle radius.

Since \$\vec{d}\$ was a vector that goes from \$C\$ to \$E\$, \$\vec{b}\$ is a vector that goes from \$C\$ to the projection of \$E\$ on to the circle plane... But not necessarily on the circle (edge).

Since the circle (edge) are all the points that are on the circle plane that are at a distance \$r\$ from the center \$C\$, all we need to do is make sure the length of \$\vec{b}\$ is \$r\$.

To do that we get a unit vector from it: \$\vec{b}*\frac{1}{|\vec{b}|}\$... And then we scale it by \$r\$: \$\vec{b}*\frac{r}{|\vec{b}|}\$. Let us call it \$\vec{l}\$:

$$\vec{l} = \vec{b}*\frac{r}{|\vec{b}|}$$


Fourth: ...

We have found a vector \$\vec{l}\$ that when placed on the center \$C\$ points to the point we want.

However, our points \$C\$ and \$E\$ are not defined respect to \$C\$. To fix that we will add \$C\$ to \$\vec{l}\$, and that is our solution:

$$S = \vec{l} + C$$

Vector addition, as you would expect is component-wise addition (i.e. it is making a new vector which components are the sum of matching components of the original vectors).

This is - effectively - the counterpart to the subtraction we did at the start. Since we subtracted \$C\$ as we needed it as common reference for the projection, we need to add it back so we get a point from the original reference (which is whatever origin you are working with).

You could also think of these subtraction and addition as a translation transformation and its inverse. Such that the transformation takes the vectors from the original coordinate space to another (which is displaced form the former by said translation), and the inverse transformation takes the vectors back to the original coordinate space.


Notes:

  • In general, since we work with floating point numbers, any non-finite number sneaking into the components of the vectors will yield unexpected results.

  • Similarly, I remind you that I assumed that the length of \$\vec{N}\$ is \$1\$. If that is not correct, make sure to normalize it. Be aware that \$\vec{N}\$ and thus the circle plane would be ill defined if \$\vec{N}\$ is a zero vector (in which case you have division by zero when trying to normalize it).

  • Speaking of division by zero, If \$|\vec{b}|\$ is \$0\$, we have division by zero when trying to scale \$\vec{b}\$ to \$r\$. This is the case where the projection of \$E\$ on the circle plane is on the center of the circle. In which case all the points on the circle (edge) are at the same distance to \$E\$.

  • We have the opportunity for floating point precision errors. In particular, if you compute the distance form the solution point \$S\$ to the center \$C\$ you might find that it is not exactly \$r\$.


In this answer we are getting the closest point on the circle to a point. If you actually wanted to find the closes point on the circle to a ray, you would get the closest point on the line of the ray to the center \$C\$, and then get the closest point on the circle to that point.

To get the closest point on the line of the ray to the center \$C\$, project the center \$C\$ on the line of the ray... In other words:

  • Get the vector that goes from the origin of the ray to center \$C\$. This is vector difference (which we need to do because we need the vectors to the points from the same point so projecting them makes sense).
  • If you need to, you might check that the dot product with the direction of the ray is positive (i.e. that the cosine of the angle is positive, i.e that the angle is less than a quarter turn). If it isn't, it would mean that the resulting point is behind the start of the ray.
  • Project it on the direction vector of the ray. This is vector projection.
  • And add the the origin of the ray to the result. This is vector addition (which we need to do because we starting by doing a vector difference).

What you get would a point on the line of the ray. And you would then proceed to get the closest point on the circle to that point (i.e. apply this answer).

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for the thorough explanation! I'm understanding it all much better now. \$\endgroup\$ Aug 18 at 4:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .