I''ve got a 3x3 bezier patch, and a line segement in 3d space (a vector + a start point). I need to find out if there is a collision between the two. I figured the way to do it would be to find the U and V coordinates of the intersection with the patch, and to find the scaling factor for the vector (so that if the scaling factor is less than one, there''s a collision, and if it''s greater than one, then there''s no collision because the intersection is beyond the endpoint of the segment). So that''s 3 unknowns. Now, I''ve worked out functions for X, Y, and Z coordinates of points on the patch (parametric to U and V - call them pX(u,v), pY(u,v), and pZ(u,v)). I can also express the points on the linesegment as (start + k*vec, where k is my scaling factor); so I figured the best way to do it is to just equate the two: (start + k*vec).x = pX(u,v), etc. However, after trying to work this for a little while, the expressions become very large and unworkable. I was wondering if this had already been solved, and if someone could point me to it, or if I just have to slog through it all? TiA... Superpig - saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.

I''m not sure, but I think bezier patch intersections are usually done by subdividing into polygons. I think it''s possible, but extremely innefficient to solve the equations directly.

I realised that, but I don't want to subdivide into polygons. So it may be academic.. but I won't know till I try. And you never know, maybe I'll solve the problem and obtain infinite wealth and riches.

I figured I'd post more of what I've got so far.

Given my control points A-I, I've formed a function which takes (U,V) and gives the point on the surface (in vector format).

I noticed that every combination of U and V raised to powers 0 through 2 are in there (that is, I can build a 3x3 table of terms, where term [1][2] is (u^1)*(v^2), and so on), and that the coefficients (in vector form, call them a-i) for those terms are constants for any given patch.

So, I can form an equation in the form:

startPoint + K * line = a*u*u*v*v + b*u*u*v + c*u*v*v + d*u*u + e*v*v + f*u + g*v + h*u*v + i

and split that into three (one for each XYZ).

So from that equation, I need to isolate each of the terms K, u, and v. K is easy, but u and v are more difficult. How can I isolate each of them in turn?

Superpig
- saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery.

[edited by - Superpig on April 20, 2003 6:46:32 PM]

Good question. Does that mean you''re using bi-quadratic patches? So you need only nine points per patch...

I can see if my TI-89 can solve it... just to make sure, you are trying to solve Auuvv+Buuv+Cuvv+Duv+Euu+Fvv+Gu+Hv+I=K*t+L for each of three dimensions, right? Actually, I don''t think my calculator will solve that... I know you can get u in terms of v or vice-versa by completing the square, but I don''t know about anything farther than that. I never thought about using bi-quadratic patches in ray-tracing, I didn''t realize that there were like half as many terms in the equation... Now I''m very interested in this, I think I will try to solve for u and v tomorrow in school. Right now, though, I can''t help you there.

I assume you''ve already realised that using that function for a large mesh would be insane. I guess if you''re doing ray-tracing, it doesn''t really matter.

Yeah, it''s bi-quadratic. Sorry, that''s what I meant by ''3x3'' (as in, a 3x3 grid of points).

I figured that by getting U in terms of V and K, and V in terms of U and K, I''d just be able to substitute one into the other and get each of U and V in terms of K. That would be a start, at least.

A large mesh? Well, assuming that we stick with a bi-quadratic patch (because that formula only works with bi-quadratic patches), what''s the problem? Given that we''ve got an absolute position for every point on the patch, then surely it would actually be *more* accurate than diving into polygons (and thus potentially losing masses of accuracy) and colliding with them?

I need a decent calculator.

Superpig
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.

There is a theorem that states that every parameterized polynomial path is a subset of an algebraic curve. It can be extended to higher dimensions. In other words for (x,y,z) = f(u,v) polynomial in u and v, you can create another polynomial g such that g(f(u,v)) = 0 for all u,v.

Once you have this form, substitute f(u,v) = e + d*t to get g(e + d*t) = 0, which is a polynomial in only t. The catch here is generating g. For a bicubic patch you have to invert an 800x800 matrix (ouch) but for biquadratic it might be considerably less (I used to have exact numbers, but no longer). Also, there may be a more reasonable computational way of doing it, though I haven''t found one. The upside is, you can generate g once before rendering and reuse it for every intersection query.

I can post more details later if you''re interested.

"Math is hard" -Barbie

What I gather from that is: There is a closed form solution for this problem. Am I right?
A little recap, mostly for my own benefit...
For ray tracing, solving for the intersection reduces to this problem:

x = x0+j*t = auuvv+buuv+cuvv+duv+euu+fvv+gu+hv+i

where x0 and a-j are all known coefficients. x0 and j have to do with your camera or light, and a-i can be found in terms of your control points (I just did all the algebra for those coefficients... damn! The solutions are so incredibly concise, but it took me like two hours to find them. I could probably just search on google, but I like doing things for myself.)

You need to find u, v, t, and x in terms of x0 and a-j. Of course, some of these are easy, so the real problem is finding:

u(a,b,c,d,e,f,g,h,i,j,x0) and
v(a,b,c,d,e,f,g,h,i,j,x0)

Now, according to you, Pragma, it is possible to find these functions.

Okay. Now I''m ready to start doing the REAL work. I think I have an idea of where to start...

Yeah, I found coefficients a-i as well It surprised me that there didn''t seem to be any definitive pattern to them. Some of them add up to zero (assuming all control points are equal), but some of them don''t. Strange.

I don''t think it''s possible to get u in terms of just constants - I think we can get u in terms of v and t, and v in terms of u and t; thus, we can substitute the first (using the X-dimension) into the second (using the Y-dimension) and get v in terms of t. Then, we get t in terms of u and v, substitute the first equation in and get t in terms of v (in the Z-dimension), and finally substitute in the second equation to get t in terms of constants.

Once we''ve got t, we can pretty much forget about u and v - t will give us the point of intersection, and the u, v coordinates once we''ve got that are unimportant, although they could easily be found.

There is, of course, a much more elegant solution to the problem, but I don''t know what that elegant solution is, because I''m 16 and officially studing 2D vector addition. *sigh*

Superpig
- saving pigs from untimely fates, and when he''s not doing that, runs The Binary Refinery.

It seems like there should be a way to do it without solving all three dimensions simultaneously, which is what I want to know. I guess I'd settle for a simultaneous solution though. I spent a few hours today reviewing splines and spline surfaces, and redoing all that algebra that I did a long time ago... now I'm ready to ignore my teachers tomorrow and try to figure it out. I'll try solving the three equations simultaneously, but I wouldn't keep my hopes up if I were you.
Of course! How did I forget? I just remembered, you need three independent equations to solve for three independent variables. That means that there should definitely be a closed-form expression. I guess you realized that a while ago...sorry for being so slow. Anyway, I can't wait to try this out tomorrow.

Edit: Don't just forget about the u and v values; they can be used for textures if you need them. I plan to incorporate them into my functions just in case I want them in the future.

Wait... it seems like you know exactly what to do. Are you having trouble with the algebra? Because I'm almost certain that I can solve those equations.

[edited by - vanillacoke on April 21, 2003 11:17:45 PM]

I think you''ve slightly misunderstood what I''m saying.

Rather than expressing u and v as functions of the other variables, you change the parametric representation to an implicit representation by eliminating u and v from the equations.

The disadvantage is that u and v have been lost, so you can''t use them as texture co-ordinates. But you can recover the normal, since it is parallel to the gradient of the implicit function.

"Math is hard" -Barbie