Edit: I rephrased the question to make it clearer, sorry!

I'm trying to solve for the intersection of two surfaces in three spatial dimensions and time. Consider each of these surfaces as some quadrilateral. For convenience, orient one corner "down". Any point on each surface is represented by bilinear interpolation:

$P_1(a_1,b_1) = x_1 + a_1*BL_1 + b_1*BR_1 + a_1*b_1*(TL_1 - BR_1)$ $P_2(a_2,b_2) = x_2 + a_2*BL_2 + b_2*BR_2 + a_2*b_2*(TL_2 - BR_2)$

Here, $x_1$ is the coordinate in x,y,z,t space of the bottom corner, $BL_1$ the bottom left edge, $BR$ the bottom right, and $TL$ the top left.

Then, an intersection is given by

$x_1 + a_1*BL_1 + b_1*BR_1 + a_1*b_1*(TL_1 - BR_1) = x_2 + a_2*BL_2 + b_2*BR_2 + a_2*b_2*(TL_2 - BR_2)$

How do I solve the system for the parameters $a1,a2,b1,b2$? I am looking for an analytic solution, if there is one.

Note: I ran a test using Mathematica for some arbitrary system, and found four roots - therefore, I think the system reduces to a quartic.


You can't "solve for $a1,a2,b1,b2$". At least, you won't find specific discrete values of $a1,a2,b1,b2$ at which an intersection occurs. You are intersecting two bilinear surfaces, so the result will be a curve (in general). The best you can hope for is to find an equation that relates $a1,a2,b1,b2$ at points along this curve.

One approach to this sort of problem as follows: find an implicit equation $G(x,y,z) = 0$ for one of the surfaces. Mathematica can probably do this for you. Let's leave the other surface in parametric form, say $P(u,v) = (x(u,v), y(u,v), z(u,v))$. Then, at points along the curve of intersection, $G((x(u,v), y(u,v), z(u,v)) = 0$. This is an implicit equation of the curve of intersection.

Bilinear surfaces are hyperbolic paraboloids, which tells you something about the compexity of the intersection curve.

  • $\begingroup$ I don't understand why this is true - the intersecting occurs in four dimensions, so there are four equations (three of space and one of time). Therefore, four equations, four unknowns? There should be discrete solutions. $\endgroup$ – Kurt Oct 14 '12 at 15:10
  • $\begingroup$ Sorry, I misread the question. I ignored the time dimension. $\endgroup$ – bubba Oct 14 '12 at 23:34
  • $\begingroup$ I'll take another shot later today. Even in 3D, my argument is wrong (again because I misread the question). $\endgroup$ – bubba Oct 14 '12 at 23:42

Another asnwer (a non-answer, really, but too long for a comment, I think).

First, I changed the notation. The main reason is to make it more clear (to me) which variables are real numbers and which ones are elements of $\mathbb{R}^4$. Also, I wanted something more succinct, and more in line with conventional parametric representations. So, I wrote the two objects as: $$H(u,v) = P + u*A + v*B + u*v*C$$ $$K(s,t) = Q - s*L - t*M - s*t*N$$ Here $P,A,B,C,Q,L,M,N \in \mathbb{R}^4$. Then, as you say, intersections occur for values of $u,v,s,t$ that satisfy: $$P + u*A + v*B + u*v*C = Q - s*L - t*M - s*t*N$$ If we write $R = P - Q$ and drop the * notation, then this becomes: $$R + uA + vB + sL + tM + uvC + stN = 0$$ Next, let's write this out component-wise, as four separate equations: $$R_i + A_iu + B_iv + L_is + M_it + C_iuv + N_ist = 0 \quad (i=1,2,3,4)$$ where $R=(R_1,R_2,R_3,R_4)$, and so on.

So, now we're in familar territory, at least. We have four polynomial equations of pretty low degree, with real coefficients, and we need to solve for $u,v,s,t$. I tried to solve in various ways using Mathematica (Groebner bases, elimination, and so on), but did not have any success at all. So, the only thing I've contributed is a tidier statement of the problem, which might encourage other people to take a look at it.


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.