Sign in to follow this  
maxgpgpu

help: math too abstract for this lame-brain

Recommended Posts

maxgpgpu    206
[font="Book Antiqua"][size="2"]I invented and implemented a triangle-triangle intersection routine for my engine, but want to speed up the performance of this speed-critical routine. After a lot of research I found what appears to be the fastest known algorithm, but the paper that describes it is... well... over my head. I can usually beat myself up sufficiently to eventually understand such things, but this time I'm too far out of my league (ie, much too stupid). A friend took at shot at converting it to code, but his attempt isn't quite working right.

My brain went out the window when the very first equation in the paper had three variables that appeared out of nowhere and were never described or shown in the illustrations (alpha1, alpha2, Beta-sub-i). Maybe every self-respecting math whiz knows these are standard terminology for something or other, but that also explains why I'm stumped, because I always have to grunt and groan my way through math.

So I'm looking for a volunteer to either explain this to me and/or convert to code. I prefer both, of course, but I understand beggars can't be choosers. According to the article the algorithm is quite compact (my friend's function is short enough), so this appears to be more an issue of understanding the math than writing code. Specifically, the algorithm executes a total of 97 math opcodes (all being plus, minus, multiply and compares, (no divide, trig, abs, etc). Clearly some additional move/assign opcodes are required in the C code. Most of the math is just subtracting positions/vectors and performing cross-products (one line function calls), so this routine isn't many lines of C code.

Any takers?

You're welcome to look at the functions I already have (my way that apparently works, plus my friend's attempt at this paper algorithm). I can't post these functions on a public forum, but I'm happy to email them to anyone willing to help. Still, I doubt they'd help you, and in fact might lure you into the same confusions that foiled us.

The article is attached, so you can figure out in advance whether you understand the math and technique or not. My technique is totally brain-dead obvious and intuitive, but their "brilliant math-whiz way" is not at all intuitive to me. But my code executes a total of 6 divide opcodes and theirs executes none --- so I'm sure theirs beats mine in a speed comparison by a fair margin.

If nothing else, I hope I save somebody out there the effort of searching for hours and hours for the fastest triangle-triangle intersection algorithm.[/size][/font]

Share this post


Link to post
Share on other sites
Daan    122
To understand the equation you mentioned you need to know about the Barycentric coordinate system. The alpha_1, alpha_2, and beta_i variables are scalar values which are used to scale p1, p2 and q_i respectively. In this case the left part of the equation represents triangle B and the right part represents the three edges of triangle A.
For the left part of the equation you can see that if you choose values for alpha_1 and alpha_2 so that both are between zero and one and alpha_1 + alpha_2 < 1 you get a point that lies on B.
Similar, on the right part of the equation you can get a points on the three edges if you choose values for beta_i between zero and one.

Share this post


Link to post
Share on other sites
maxgpgpu    206
[quote name='Daan' timestamp='1313023491' post='4847428']
To understand the equation you mentioned you need to know about the Barycentric coordinate system. The alpha_1, alpha_2, and beta_i variables are scalar values which are used to scale p1, p2 and q_i respectively. In this case the left part of the equation represents triangle B and the right part represents the three edges of triangle A.

For the left part of the equation you can see that if you choose values for alpha_1 and alpha_2 so that both are between zero and one and alpha_1 + alpha_2 < 1 you get a point that lies on B.

Similar, on the right part of the equation you can get a points on the three edges if you choose values for beta_i between zero and one.
[/quote]
[font="Book Antiqua"]Thanks for getting me on the correct path. I wish I could say that gets me beyond my lack of understanding. I've read wikipedia and several other resources on barycentric coordinates, but somehow this doesn't make the rest of the article doesn't entirely fall into place for me. Any chance you (or someone else) could take this a bit further? I'm trying.[/font]

Share this post


Link to post
Share on other sites
haegarr    7372
First notice that there are point vectors P and Q[sub]i[/sub] in use, as well as difference vectors p[sub]1[/sub], p[sub]2[/sub], and q[sub]i[/sub]. The correspondence between point and difference vectors is that a difference vector is the difference of 2 point vectors. E.g.
d := D[sub]2[/sub] - D[sub]1[/sub]
what means that the difference vector d is the difference from point D[sub]1[/sub] to point D[sub]2[/sub]. One can obviously rewrite the above equation to yield in
D[sub]2[/sub] = D[sub]1[/sub] + d
what means that point D[sub]2[/sub] is reached when adding the difference vector d onto point D[sub]1[/sub].

But how to reach the point D[sub]3[/sub] exactly on the half way between D1 and D2? Well, we have to add the half of vector d:
D[sub]3[/sub] = D[sub]1[/sub] + 0.5 * d
In general we can add any elongation of d to D[sub]1[/sub] by weighting d with a scalar s.
D( s ) := D[sub]1[/sub] + s * d
with the special cases
D( s=0 ) = D[sub]1[/sub] + 0 * d = D[sub]1[/sub]
D( s=1 ) = D[sub]1[/sub] + 1 * d = D[sub]2[/sub]

The above are ray equations. They describe a directed line starting from D[sub]1[/sub] in direction of D[sub]2[/sub], where D can be any point on that line in dependence of s. That is exactly what the right side of the equation in the paper is (but using its own variable names).

Now, think of not moving on a 1-dimensional line but on a 2-dimensional plane. You can reach any point of a plane if you 1st wander along a ray as done above, and 2nd wander on another ray but now starting from the point you've reached during your previous wandering and, of course, wander into another direction. This would look like
D( s, t ) := D( s ) + t * d[sub]2[/sub] = D[sub]1[/sub] + s * d[sub]1[/sub] + t * d[sub]2[/sub]
and that is exactly what is written on the left side of the article's equation (but using its own variable names).

In summary, the equation means a point that is both (a) on the plane in which triangle A lies and is (b) on a ray in which the edge of a 2nd triangle B lies.

Share this post


Link to post
Share on other sites
maxgpgpu    206
[font="Book Antiqua"][size="2"]Thanks for the math lesson! It still took a lot of grinding to semi-decode that article, but "somehow" (after a LOT of fiddling) I got a function implemented that... works! Difficult to believe, and frankly, I wouldn't believe it except I have my program calling my original function then a new function based on this technique, and they always agree. Impossible but true.

Then I had a couple other strange ideas and wrote a third function... and it works too. Well, either that or they all produce the same wrong answers! Hahaha. I don't think so though, because I fiddled the engine to make all vertices white, then when each of these functions finds triangles in collision it makes the "red", "green" or "blue" vertices of the triangles about 1/3 intensity. So I can watch objects wander around the screen and collide, and along all the intersecting surfaces are nicely greyed-out triangles. So it looks like it works (plus I actually understand the first function I wrote).

Just for laughs, here is the number of CPU cycles each function takes (average after 1,000,000 calls to each function):
function #1: 1314 // the one I wrote and understand
function #2: 0901 // the one in the article
function #3: 0801 // the newest one

Somehow, I don't think I'm gonna do much better than this last one.

Thanks much for your help.[/size][/font]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this