StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POInfinite cone surface * AABB intersection testing
text
Body
copied!<p>I'm trying to discover a faster algorithm for testing whether an axis-aligned <a href="http://en.wikipedia.org/wiki/Conical_surface" rel="nofollow noreferrer">conical surface</a> intersects the volume of an axis-aligned bounding box.</p> <p>The current algorithm I developed is as follows:</p> <p><img src="https://i.stack.imgur.com/0Eq1k.png" alt="cone, AABB, lines along 4 parallel edges, and intersection points"></p> <ul> <li>x = 0</li> <li>For each of any 4 parallel edges of the AABB: <ul> <li>Intersect its line with the cone.</li> <li>If the intersection point is within the AABB: <ul> <li>Return true.</li> </ul></li> <li>If the intersection point is on a specific side of the AABB: <ul> <li>x += 1</li> </ul></li> </ul></li> <li>If x == 0 or x == 4 (all the intersections were on one side of the AABB): <ul> <li>Return false.</li> </ul></li> <li>Return true.</li> </ul> <p>Can anyone think of a more efficient one? This seems to do a lot of extra work by computing each line intersection.</p> <p>EDIT:</p> <p>Above algorithm is bad, for example:</p> <p><img src="https://i.stack.imgur.com/xRuv4.png" alt="cone hits untested axis of box"></p> <p>The cone can intersect only one edge of the box in a way that all the axis-line intersections are on one side, so the above algorithm doesn't work unless all edges are tested or the edges to be tested are intelligently chosen (maybe the edges closest to the cone?).</p> <p><strong>EDIT EDIT: See my own answer below for the solution I later discovered, which seems nearly optimal to me.</strong></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload