It's summer break, and work hasn't started yet. For a normal person, that means some time to kick back and chill. But I'm not exactly normal. Instead I've spent my break so far trying to figure out how to find the point of intersection of a line with a quad inside of Blender. Now that I have figured it out and have it working, I'm going to explain where things started and walk to where they ended.
At first glance this appears to be a fairly simple problem: after all you can figure out fairly accurately where the two would intersect simply by looking at the line and the face. A computer is not able to do that though. Instead, a computer sees the coordinates of the geometry defining the shapes as vectors. Does the line given by the points [-1.1, 0.3, 0] and [-2.8, -1.2, -0.4] intersect with the quad defined by the points [1.5, -0.6, 0.2], [0.7, 0.4, 1.2], [1.2, 0.7, -0.4], [1.3, -0.3, -2.2]? If so, where do they intersect? The picture below provides a visual of what the line and point would look like:
[[posterous-content:pid___0]]
As you can clearly see, they don't intersect. But for a computer, there is no easy way to see that. So instead we define the problem in a way that a computer can think in. A computer requires defining the problem in terms of mathematical formulas that it can then put the coordinates into, calculate, and then get the answer from. So how do we define the line and the face as formulas? Enter linear algebra and vector math:
Linear algebra is the branch of mathematics concerning finite or countably infinite dimensional vector spaces, as well as linear mappings between such spaces. Such an investigation is initially motivated by a system of linear equations in several unknowns. Such equations are naturally represented using the formalism of matrices and vectors.
First, we shall treat the line as a vector. As some may recall from their high school algebra or geometry, a line is defined by two points. Skipping over some of the theory about adding vectors, we can think of the vector as being defined by two points also: its starting point, and its end point. To find the value of the vector, we are going to subtract the coordinates of the start point from the end point. If we say the starting point is called "a" and the end point is called "b", then this gives us the following base equation:[[posterous-content:pid___1]]There are two problems with this though: 1) a vector is assumed to start at the origin and 2) we have no control where on the line we are considering meaning we can't just look up any coordinates along the line. To solve the first problem, we add the vector defining the starting point. For the second we introduce a new variable, and call it "t". This will serve to scale the vector with scalar multiplication With simplification we get the following:[[posterous-content:pid___2]]This is called the "parametric equation" for a line in 3-space. When "t = 0", we get the starting point. When "t = 1" we get the end point. "t = 0.5" is the point half way in between the two, and so forth.
We now have to create a formula for the quad. After some investigation, it turns out that Blender has an interesting definition for a quad; Blender defines a quad as the set of all lines spanning two lines. We're first going to define the two lines:[[posterous-content:pid___3]]Now the definition says that for those lines, there are lines going between them. This means that the first point for our line will be on the first line and the second needed point will be on the second line. "t" is that same for both lines, but cannot be the same for the line we're creating. If it was the same, then we would end up with a diagonal line between the two lines. So we need another "t" for that. Putting it all together we get:[[posterous-content:pid___4]]Now defining our original point in terms of another "t" (because it cannot be the same one either used in defining the plane):[[posterous-content:pid___5]]Now since we are looking for the point of intersection, the two vectors should give use the same solution:[[posterous-content:pid___6]]All we have to is solve for the three different "t" variables and we have created a system of equations that we can put out points into and get useful information back from. If all three "t" variables are equal to or between 0 and 1, then they intersect. By putting the resulting "t" values into the original equations, we can look up the point of intersection. There happens to only be one small catch though: solving for the "t" values, it turns out, is no simple task. Enter a symbolic solver. In my case I used Mathematica, but there are alternate solutions out there. The input and output has been reproduced in the following PDF.[[posterous-content:pid___7]]
Because the goal is a solution that can be easily programed, there was some slight modifications to how I solved it. I first had it solve for the entire system of three equations, three unknowns. I then took the simplest and "calculated" the value; I assumed the simplest to be a known. Then I solved the system again, this time as two equations and two unknowns. Again, I assumed the simpler of the two as a constant and solved again as one equation, one unknown. This produced the equations to solve for the three using previously calculated values (and thus saving computation time).
From that, I created the following Python code for Blender:
Formulas generated by MathML Central using MathML and powered by Wolfram webMathematica 3. Code hosting provided by PasteAll.org.
