<p>I can simplify the problem for you, but I'm not sure it's possible to do what you want in the general case. When it works, this solution will tell you which circle the ray intersects first; finding the exact intersection point is then simple.</p>
<p>First, let's say that the ray starts at a point where <span class="math-container">$-1 &lt; x \le 0$</span> and is traveling in the positive x and y direction, with direction vector parallel to <span class="math-container">$(1,m)$</span>, with <span class="math-container">$0 &lt; m \le 1$</span>. (This can be arranged for any input by various translations and reflections.)</p>
<p>Second, note that you don't strictly need to consider intersections with circles, just with line segments parallel to the y-axis. If the circles have radius <span class="math-container">$r$</span>, then clearly any ray that intersects the segment <span class="math-container">$(a,b-r)-(a,b+r)$</span> (where <span class="math-container">$a$</span> and <span class="math-container">$b$</span> are integers) intersects the sphere at <span class="math-container">$(a,b)$</span>. If the ray is traveling up and to the right, then there is only one situation where it can intersect the circle but not the segment:</p>
<p><a href="https://i.sstatic.net/QcGLQ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/QcGLQ.png" alt="Image of a ray osculating a circle of radius r. The circle's center is at point C; the ray touches the circle at point O and intersects the vertical line through C at P. Q is the projection of O on the line PC." /></a></p>
<p>We can compute the extra distance <span class="math-container">$v$</span> by simple trigonometry. Note that the three triangles <span class="math-container">$OPC$</span>, <span class="math-container">$QPO$</span>, and <span class="math-container">$QOC$</span> are similar. The value <span class="math-container">$m$</span> is the slope of the ray: <span class="math-container">$PQ / OQ$</span>, or, by similarity, <span class="math-container">$m = \ell/r$</span>. By Pythagoras, we know that <span class="math-container">$\ell^2 + r^2 = (r+v)^2$</span>. Substituting, we get a quadratic equation for <span class="math-container">$v$</span>
<span class="math-container">$$ v^2 + 2rv - m^2r^2 = 0, $$</span>
which has a single positive (if <span class="math-container">$r &gt; 0$</span>) solution
<span class="math-container">$$ v = r \left(\sqrt{1 + m^2} - 1\right). $$</span></p>
<p>The ray will intersect the circle of radius <span class="math-container">$r$</span> at <span class="math-container">$(a,b)$</span> exactly when it intersects the line <span class="math-container">$x = a$</span> between <span class="math-container">$y = b - r$</span> and <span class="math-container">$y = b + r + v$</span>. We can simplify this even further by shifting everything up by <span class="math-container">$r$</span>; then the interval becomes <span class="math-container">$[b, b + 2r + v]$</span> and the ray intersects a circle at <span class="math-container">$a$</span> exactly when
<span class="math-container">$$ (y_0 + r) + a m \le 2r + v \mod 1, $$</span>
where <span class="math-container">$y_0$</span> is the intersection point with the y-axis (the first vertical line it reaches, per our simplification).</p>
<p>Then the circle intersected can (often) be found quite simply. If <span class="math-container">$y_0 + r \mod 1 &lt; 2r + v$</span>, then it is the first circle reached, i.e. <span class="math-container">$a = 0$</span>. If <span class="math-container">$m &lt; 2r + v$</span>, then we can just divide the y-distance yet to be traveled by <span class="math-container">$m$</span>, i.e.
<span class="math-container">$$a = \left\lceil \frac{1 - (y_0 + r)}{m} \right\rceil.$$</span></p>
<p>Unfortunately, the problem comes with <span class="math-container">$m &gt; 2r+v = r\left(\sqrt{1 + m^2} + 1\right)$</span>. In this regime, it's possible for the y-intersection point to skip over the critical interval, and even to miss it entirely. In general, I'm not sure it's possible to find when the iteration hits the critical interval without some iteration of the value. Maybe there's some GCD-esque iteration that will get you the value?</p>

CC BY-SA 4.0
2021-09-28T08:24:01.537Z
I've just realized that, of course, the interval has to include $v$ on the bottom as well, to account for intersections on the back side of the circle. The criterion then becomes $y_0 + (r + v) + am \le 2(r+v)$, but the rest still stands, I think.
gilgamec
CC BY-SA 4.0
2021-09-27T12:26:50.073Z
2021-09-27T12:26:50.073Z
gilgamec
<p>My actual problem is considerably more complex, but can be solved if there is a cheap way to compute the intersection of a ray with a regular grid of circles. If I had a circle centered at every integer (x,y) pair, and a ray in xy space, what's the fastest way to determine where the ray first intersects the surface of a circtle? My ray origin will not be inside one of the circles.</p>
<p>The grid will be at least 256x256, so a signed distance function would be far too expensive, as I'd have to allow too many iterations to get the answer I need. I'm hoping that there's a mathematical solution to my problem so I can get this over in a dozen or two floating point operations. If a solution exists, I would assume that it will test against an infinite grid. I can happily cull intersections outside of the finite space in which I am working.</p>
<p>Thanks...</p>

CC BY-SA 4.0
2021-09-25T09:04:14.537Z
Not a direct answer but the link contains almost all the useful references about static and dynamic object intersection methods, I am sure it can help: https://www.realtimerendering.com/intersections.html
Kaan E.
CC BY-SA 4.0
2021-09-25T09:23:44.753Z
Filter out all circles that are definitely outside of the way of the ray (can be done through a modification of Bresenham) and intersect the ones on its way in order (you'll likely stop after the first few steps).
lightxbulb
CC BY-SA 4.0
2021-09-25T20:00:03.073Z
Bresenham is iterative and therefore, far too costly for the job.
Sniggerfardimungus
CC BY-SA 4.0
2021-09-27T12:55:41.557Z
Are you talking about circles or spheres because these are different things, and by regular grid do you mean they are all in a single plane with equal spacing and equal size?
pmw1234
CC BY-SA 4.0
2021-10-03T15:38:43.793Z
How does the radius of the circles relate to the grid spacing?  Are all circles the same radius?  Are they all tangent to each other? Or may their diameter be larger or smaller than the grid spacing?
Wyck
<raytracing>
Is there a mathematical (as opposed to iterative/SDF) test for ray intersection with a grid of circles?
Sniggerfardimungus
# Is there a mathematical (as opposed to iterative/SDF) test for ray intersection with a grid of circles?

(Asked by: username_0 on 2021-09-25)

My actual problem is considerably more complex, but can be solved if there is a cheap way to compute the intersection of a ray with a regular grid of circles. If I had a circle centered at every integer (x,y) pair, and a ray in xy space, what's the fastest way to determine where the ray first intersects the surface of a circtle? My ray origin will not be inside one of the circles.

The grid will be at least 256x256, so a signed distance function would be far too expensive, as I'd have to allow too many iterations to get the answer I need. I'm hoping that there's a mathematical solution to my problem so I can get this over in a dozen or two floating point operations. If a solution exists, I would assume that it will test against an infinite grid. I can happily cull intersections outside of the finite space in which I am working.

Thanks...

**Tags:** raytracing

> **Comments:**
> **username_1**: Not a direct answer but the link contains almost all the useful references about static and dynamic object intersection methods, I am sure it can help: https://www.realtimerendering.com/intersections.html  
> **username_2**: Filter out all circles that are definitely outside of the way of the ray (can be done through a modification of Bresenham) and intersect the ones on its way in order (you'll likely stop after the first few steps).  
> **username_0**: Bresenham is iterative and therefore, far too costly for the job.  
> **username_3**: Are you talking about circles or spheres because these are different things, and by regular grid do you mean they are all in a single plane with equal spacing and equal size?  
> **username_4**: How does the radius of the circles relate to the grid spacing?  Are all circles the same radius?  Are they all tangent to each other? Or may their diameter be larger or smaller than the grid spacing?  

---

## 1 answers

### Answer by username_5 on 2021-09-27. Score: 2

I can simplify the problem for you, but I'm not sure it's possible to do what you want in the general case. When it works, this solution will tell you which circle the ray intersects first; finding the exact intersection point is then simple.

First, let's say that the ray starts at a point where $-1 < x \le 0$ and is traveling in the positive x and y direction, with direction vector parallel to $(1,m)$, with $0 < m \le 1$. (This can be arranged for any input by various translations and reflections.)

Second, note that you don't strictly need to consider intersections with circles, just with line segments parallel to the y-axis. If the circles have radius $r$, then clearly any ray that intersects the segment $(a,b-r)-(a,b+r)$ (where $a$ and $b$ are integers) intersects the sphere at $(a,b)$. If the ray is traveling up and to the right, then there is only one situation where it can intersect the circle but not the segment:

[![Image of a ray osculating a circle of radius r. The circle's center is at point C; the ray touches the circle at point O and intersects the vertical line through C at P. Q is the projection of O on the line PC.](https://i.sstatic.net/QcGLQ.png)](https://i.sstatic.net/QcGLQ.png)

We can compute the extra distance $v$ by simple trigonometry. Note that the three triangles $OPC$, $QPO$, and $QOC$ are similar. The value $m$ is the slope of the ray: $PQ / OQ$, or, by similarity, $m = \ell/r$. By Pythagoras, we know that $\ell^2 + r^2 = (r+v)^2$. Substituting, we get a quadratic equation for $v$
$$ v^2 + 2rv - m^2r^2 = 0, $$
which has a single positive (if $r > 0$) solution
$$ v = r \left(\sqrt{1 + m^2} - 1\right). $$

The ray will intersect the circle of radius $r$ at $(a,b)$ exactly when it intersects the line $x = a$ between $y = b - r$ and $y = b + r + v$. We can simplify this even further by shifting everything up by $r$; then the interval becomes $[b, b + 2r + v]$ and the ray intersects a circle at $a$ exactly when
$$ (y\_0 + r) + a m \le 2r + v \mod 1, $$
where $y\_0$ is the intersection point with the y-axis (the first vertical line it reaches, per our simplification).

Then the circle intersected can (often) be found quite simply. If $y\_0 + r \mod 1 < 2r + v$, then it is the first circle reached, i.e. $a = 0$. If $m < 2r + v$, then we can just divide the y-distance yet to be traveled by $m$, i.e.
$$a = \left\lceil \frac{1 - (y\_0 + r)}{m} \right\rceil.$$

Unfortunately, the problem comes with $m > 2r+v = r\left(\sqrt{1 + m^2} + 1\right)$. In this regime, it's possible for the y-intersection point to skip over the critical interval, and even to miss it entirely. In general, I'm not sure it's possible to find when the iteration hits the critical interval without some iteration of the value. Maybe there's some GCD-esque iteration that will get you the value?

> **Comments:**
> **username_5**: I've just realized that, of course, the interval has to include $v$ on the bottom as well, to account for intersections on the back side of the circle. The criterion then becomes $y_0 + (r + v) + am \le 2(r+v)$, but the rest still stands, I think.  

---

