0
$\begingroup$

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...

$\endgroup$
5
  • $\begingroup$ 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: realtimerendering.com/intersections.html $\endgroup$
    – Kaan E.
    Sep 25 at 9:04
  • $\begingroup$ 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). $\endgroup$
    – lightxbulb
    Sep 25 at 9:23
  • $\begingroup$ Bresenham is iterative and therefore, far too costly for the job. $\endgroup$ Sep 25 at 20:00
  • $\begingroup$ 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? $\endgroup$
    – pmw1234
    Sep 27 at 12:55
  • $\begingroup$ 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? $\endgroup$
    – Wyck
    Oct 3 at 15:38
2
$\begingroup$

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.

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – gilgamec
    Sep 28 at 8:24

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.