Daarong, what you’re encountering is expected. When you optimize code for “speed” (or number of operations/instructions) as was done above, you frequently give up on robustness. I noted this with the comment “Also, if implemented as derived, the resulting code is not the greatest example of floating-point robustness […]” If robustness is your goal, you will have better results not performing any of the for-speed optimizations that I outlined in the article.

]]>For example if you make a test scheme that uses a 2d area 700×700 and randomly place triangle points in it, iterate through every pixel, each time “moving a circle” to that position, and if it intersects, draw black, otherwise draw white… when the triangle gets small enough you end up with same really crazy patterns.

This happened to me first in 3 dimensions in JavaScript… then I did the 2D test described above in C#. Both cases had the same instability.

As I said – any recommendations? I’m bypassing this instability by just replacing tiny triangles with appropriately sized tiny spheres, then doing sphere-sphere intersection. So I’m asking this not for myself, but more as a discussion provoking thing.

Thanks for this resource!!

]]>First of all let me praise you for this excellent book that is yours “Real-time collision detection”. I write to you in order to ask about a small clarification of something I found odd in a couple of your codes. On page 189, you give a code for detecting the interception between a line and a quadrilateral, which I assume to be in two-dimensional space. However, at some point, there is a line with a crossproduct yielding a new vector:

Vector m = Cross(pc, pq);

As far as I know, the cross-product of two 2D vectors returns a scalar value – or a 3D vector in case we add the zeros to the other two dimensions and use that scalar as the third dimension. I found it confusing: how should one proceed in that regard, since in that code line the object “m” seems to be a 2D vector? Notice that I am not the only soul lost in that: http://stackoverflow.com/questions/2333292/cross-product-of-2-2d-vectors

Many thanks for your time.

Best regards,

Andy E. Astro

]]>As you note, there’s also often overlap between the calculations for distance vs. separation. Some of this follows because in both types of test we have to perform the testing by cases that correspond to regions of space. Sometimes these regions are the same or at least sufficiently close that the math becomes the same or very similar.

I haven’t tried, nor really thought about it much, but to handle the moving-sphere case SAT-style, you would have to parameterize the sphere-axis movement and then track the projections onto this parameterized axis, same as you would for a stationary axis. Sounds messy.

For moving sphere vs. triangle, a distance-based approach intuitively sounds more appealing. Dave Eberly describes one such approach in Intersection of Moving Sphere and Triangle.

]]>Since this is a SAT, it should be possible to use the same axes in the “dynamic” version of SAT – the thing popularized by Ron Levine on GDA a long time ago -, to get a moving-sphere-vs-triangle test. Right? Except it doesn’t work, and I think it’s simply because contrary to what happens for, say, box-vs-box, here the axes change over time. For boxes the axes remain the same when a box gets translated. For spheres, the axes need recomputing.

But then, going back to how the axes are built, there is something not very satisfying there. For the “edge axes” (number 2, 3 and 4 in the article) we effectively already do some distance computations (Q = closest point from P to line AB). Ok, but if we can do that, why not simply compute Q = closest point from P to *segment* AB, which is basically the same computation, and it lets us drop the “sphere axes” (number 5, 6, 7) completely. And if we continue in that direction, computing Q = closest point from P to the triangle gives us, in a way, a single axis to test (at which point we don’t really have a SAT anymore of course, just a distance-based test).

I found it interesting to see how the SAT version can gradually turn into the distance test. I also wonder now what are the proper “rules” to choose the candidate axes. You wrote:

“it should be clear a sphere has only one feature, but it varies from test to test: the point on the sphere surface closest to each given triangle feature!”

and at the same time:

“a triangle has three kinds of features that are involved in testing: vertices (3), edges (3), and a face (1)”

But that’s edges right there, not lines. So why not computing the closest point from P to the edges indeed? Is it an arbitrary choice? A way to avoid the extra tests in the segment case, to make it more SIMD friendly?

And more importantly, how do we make this work for the moving-sphere case? Any idea? :)

]]>Well yeah, a later construction that appears in Gottschalk’s thesis, section 4.2:

http://www.mechcore.net/files/docs/alg/gottschalk00collision.pdf

But this is from 2000 apparently, I suppose somebody else may have used the term first, between 1995 and 2000. Oh well. Fascinating stuff anyway :)

]]>It is historically interesting to note (as I did in my book) that the whole idea was actually presented to Gottschalk by Mikki Larcombe on comp.graphics.algorithms in 1995. Google groups have the two postings archived (as do I in my personal archive of interesting posts from back then). It’s worth noting two things: 1) Larcombe clearly presents the whole idea behind separating-axis testing to Gottschalk, and 2) there’s no mentioning of “separating axis theorems” anywhere. That’s an unfortunate later construction.

Gottschalk 1995 comp.graphics.algorithms inquiry:

From: gotts…@cs.unc.edu (Stefan Gottschalk)

Subject: arbitrary bounding box intersection

Date: 1995/10/09

Message-ID: <45bup9$c9k@zworykin.cs.unc.edu>#1/1

X-Deja-AN: 117294500

organization: The University of North Carolina

newsgroups: comp.graphics.algorithmsI have two right rectangular prisms (I think that’s right – they’re

3d rectangles, anyway) arbitrarily positioned and oriented in

3-space, and I want to know if they touch or intersect. I don’t

need to know WHERE they touch, but only WHETHER they touch.Does anyone know an efficient way to do this?

Currently I test whether any of the edges of box A intersects any

of the faces of box B and vice versa, for a total of 144 edge-face

intersection tests. Yuck. I want to do better.-stefan

Mikki Larcombe 1995 comp.graphics.algorithms answer:

]]>From: Mikki.Larco…@dcs.warwick.ac.uk (Mikki Larcombe)

Subject: Re: arbitrary bounding box intersection

Date: 1995/10/11

Message-ID: <1995Oct11.130545.22985@dcs.warwick.ac.uk>#1/1

X-Deja-AN: 117385584

sender: mhel@granite (Mikki Larcombe)

x-nntp-posting-host: granite

references: <45bup9$c9k@zworykin.cs.unc.edu> <813274427snz@jjavp.demon.co.uk>

organization: Department of Computer Science, Warwick University, England

newsgroups: comp.graphics.algorithms

originator: Mikk@graniteGiven two convex polyhedra these are separable (i.e. have no point in

common) if there is some axis such that the points from each polygon project

onto this axis in two separable sets. This is equivalent to the notion of a

plane of separation but has the advantage of giving a direct measure for

comparison purposes: given the two convex polyhedra A and B and letting

these project onto some axis as p(A),p(B) then separability exists if

max p(a)<min p(B) or max p(B)<min p(A).This leaves us to choose the appropriate directions. There is a finite set of

such directions for polyhedra: the facet normals from both polyhedra and the

directions formed from the vector cross-products of an edge direction taken from

each polyhedra. For the rectangular boxes this gives 15 directions, but

the tests are rejective… it is sufficient to find separability in one of these

directions, intersection requires overlap of the projected sets in all of these

directions.In making these tests it is useful to have the formula for the extent of a

rectangular box in any direction to hand (extent is the range of the projected

points. Given a mid-point m, orthonormal

basis vectors b0,b1,b2, and semi-axis s0,s1,s2 the extent in a direction d

relative to a test point q is:

d.(m-q)+/-(s0|d.b0|+s1|d.b1|+s2|d.b2|)

where |d.b0| means the absolute value of the dot product.

—

Mikki Larcombe

—

Mikki Larcombe

QC = C * e1 + Q1

QA = A * e2 + Q2

QB = B * e3 + Q3

Should be:

QC = C * e1 – Q1

QA = A * e2 – Q2

QB = B * e3 – Q3

As for the separating axis theorem, I suppose we all have to blame Stefan Gottschalk, who was the first AFAIK to talk about it in his thesis. I don’t remember if he “proved it in print” though :)

]]>