Ok, you can follow the detail around this in the similarly named posts below.
Essentially I have a cube, on this cube I have a line which intersects
the faces (like a lazer pointer.) I have calculated the point in 3d
space where the intersection occurs, but would like to convert this
information into a 2d representation I have of the cube's faces.
http://pling.biz/popups/cube/cube.htm
is a working example of the cube and its intersections, (it looks
mashed to start with, just click one of the movement keys and it sorts
itself out.)
You can see on the cube faces, and their second representations, there
is a small red cross, this is what I am trying to move to the position
of the intersection (it does move at the moment, just not right.)
This time I am starting the price low - but I am prepared to tip
making it up to $30 (or reposting hte question once you have outlined
the solution)
Please comment if this isn't clear.

---

Clarification of Question by charltonian-ga on 28 May 2005 04:10 PDT

ok, I have followed manuka-ga's lead and implemented a gaussian
elimination process for trying to calculate the coefficient of unit
vectors specific to a plane.
The results are almost right, but not quite there. This may be a
problem with the method or the implementation and essentially I need
someone to look over the method to spot out where it's likely to have
gone wrong (I am fairly sure the gaussian elimation works properly -
but it does appear that the minimum sized array it can cope with is
four columns and 3 rows.)
The movement of the dot/data display is only implemented on face 5.

---

Clarification of Question by charltonian-ga on 29 May 2005 01:42 PDT

S U C C E S S!!

manuka-ga, your method did work, infortunately due to a carry over of
a previous method, the sign of some of the values were wrong (they
were -ve when they should have been +ve and vice versa.) I wish I'd
noticed before I could have saved a lot of heartache.

Thanks for the info - I'd never heard of gaussian elimination, and
even when I read up on it I wasn't sure if I could program it, but I
struggled through. (In fact your description was spot on, altho it is
a little difficult to follow unless you fully understand it.)

I am closing this thread (and I have to say that the sample cube is now removed.)

Please email me thru the site, and I will send you a link to the finished article.

Once again, thank you so much.

:) nice. OK. I hope you don't mind more of my comments?
May I guess that, perhaps, you're not likely to have the red dot on
any but one side? (or, if we agree that the line is a continuous line,
then either the laser line goes through opposite or adjoining faces
... what's weird to me is that you have the potential that the red dot
goes through 4 faces? Let's take a look.

BTW: it would have been very nice to have a full representation of the
line, regardless of the intersection.

Can you tell a little more about points 15 16 and 17; and I thought
they were static, regardless of how the cube rotated... Or do they
have anything to do with the red dot?

Coming in late to this one, but here we go anyway.

If you've calculated the point in 3D where the intersection occurs, as
well as (at least three of) the corners of the given face, it's really
not hard to do.

Suppose you have 3D coordinates for three corners A, B, C and the
intersection point X. Work out the vectors (A-B), (C-B) and (X-B).
Express (X-B) as a linear combination of (A-B) and (C-B); this will be
possible if you've calculated X correctly (i.e. X is in the plane of
ABC), and the solution will be unique unless X=B. In fact, most of
this is the same work you do to *find* the intersection point in the
first place.

These coefficients then map directly onto your square representation
of the face in question. Note that if either of the coefficients is
outside the range [0, 1] then X is not in the square defined by A, B,
C (i.e. the line does not intersect that particular face).

Here's an example. Suppose your square has corners A (0, 2, 2), B (0,
4, 0) and C (8/3, 14/3, 2/3). [A and B chosen at random, C chosen to
form a square with rational coefficients so I don't have to try
putting sqaure-root signs into this comment.] Suppose your line runs
from O along the vector (1,1,1). Then to find the intersection point
X, you let X = k(1, 1, 1) for some k and use the fact that X is in the
plane ABC:

(X-B) = c_1 (A-B) + c_2 (C-B)

where _1 and _2 are subscripts; we're sitting at B and saying that the
directions to A and to C define the plane ABC, so the vector to X must
be a combination of those.

Substituting in gives
(k, k-4, k) = c_1 (0, -2, 2) + c_2 (8/3, 2/3, -2/3)
The idea is to solve this for c_1 and c_2. Setting it up in matrix
form (with some reordering of the rows) gives
[  2  -2/3  |  k  ]
[  0   8/3  |  k  ]
[ -2   2/3  | k-4 ]
which can be reduced to
[  1  -1/3  |  k/2 ]
[  0    1   | 3k/8 ]
[  0    0   | 2k-4 ]
This is soluble if and only if 2k-4 = 0, i.e. k=2, so X = (2, 2, 2).
This is how we find X in the first place.

Now to map X into the square, all we need to do is complete the
solution by finding c_1 and c_2. Substituting k=2 into the last matrix
gives
[  1  -1/3  |  1  ]
[  0    1   | 3/4 ]
[  0    0   |  0  ]
which is interpreted as "c_1 - c_2/3 = 1; c_2 = 3/4"
giving the solution c_1 = 5/4, c_2 = 3/4.

Now suppose your square is mapped as below (how square this looks
probably depends on your browser settings, but just pretend):

 B.-------.C
  |       |
  |       |
  |       |
 A'-------'D

Then X is 5/4 of the way from B to A, and 3/4 of the way from B to C,
so it would be in the spot indicated:

 B.-------.C
  |       |
  |       |
  |       |
 A'-------'D
        .X

(I hope this is clear. If not, please let me know.)

crythias-ga

points 15 16 and 17 - represent the intersections on the visible
planes - the colour coding represents which of the three visible faces
the 'bubble' is for.
I will attempt to put a line in (tonight.)
The red dot, should move on the face to where the bubble 15, 16 or 17
(depending on the face) should be.

manuka-ga

I bizarrely had a very similar thought in the bath last night (a
'eureka moment' perhaps)
I'm reading over your response (and am nearly getting it) although I
think I'm a little confused as my square is

 A.-------.B
  |       |
  |       |
  |       |
 C'-------'D

but I guess that means
(X-A) = c_1 (C-A) + c_2 (B-A)
But I'm just not getting the last push, I'm sure it's obvious (and I
am a little foggy this morning)
I'll need to read through it properly, and substitite in my numbers,
and give it a go.

Ok, I've worked this through a little. And the point where I get stuck is:

"The idea is to solve this for c_1 and c_2. Setting it up in matrix
form (with some reordering of the rows) gives
[  2  -2/3  |  k  ]
[  0   8/3  |  k  ]
[ -2   2/3  | k-4 ]
which can be reduced to
[  1  -1/3  |  k/2 ]
[  0    1   | 3k/8 ]
[  0    0   | 2k-4 ]
This is soluble if and only if 2k-4 = 0, i.e. k=2, so X = (2, 2, 2).
This is how we find X in the first place. "

Now, I do understand what you are doing, but what I'm not sure of is
how I would convert it into something I can use at run-time. (As in
I'm not able to 'solve' something at run-time - it needs to be a fixed
formula.)

ok, there is now line.
crythias-ga
"Can you tell a little more about points 15 16 and 17, I thought
they were static"
Sorry this was a mis-explanation - possibly a little cleared up but
the line. 15 16 and 17 represent the point where the line and a plane
intersects (there are 3 as there are always 3 faces visible)

manuka-ga
Ok I have had a good attempt to work through your example, and I'm
still a bit unsure of things.
Essentially my confusion comes from:
I can get a value for k very simply, as you say X = kP where P is onw
end of the line which ends at the Origin, as I set P I know what its
values are, and I have calculated X. So k = X/P
Where, of course, this doesn't get me, is much further with the matrix
you have set up. I'm confused as to why you juggle the lines around.
And I'm unsure what to do with my newly found value k.
It would seem that I end up with some kind of simultaneous equation,
and I'm looking into methods for solving that at run-time...
Is this sounding right to you?

http://www.jtaylor1142001.net/calcjat/Solutions/VPlanes/VPtIntLPlane.htm
Point of Intersection of Line and Plane

Wow. amazing what you can find if you type in some things. I'm not
being mean. I was really surprised.
http://www.gotoandplay.it/_articles/2005/01/ppbr3d.php SWF

http://astronomy.swin.edu.au/~pbourke/geometry/linefacet/ source code!
http://members.tripod.com/~Paul_Kirby/vector/Vplanelineint.html
http://www.cs.unb.ca/profs/nickerson/courses/cs4735/Labs/L3_2004.htm

http://www.exaflop.org/docs/cgafaq/cga5.html

Subject 5.05: How do I find the intersection of a line and a plane?

If the plane is defined as:

a*x + b*y + c*z + d = 0

and the line is defined as:

x = x1 + (x2 - x1)*t = x1 + i*t
y = y1 + (y2 - y1)*t = y1 + j*t
z = z1 + (z2 - z1)*t = z1 + k*t

Then just substitute these into the plane equation. You end up with:

t = - (a*x1 + b*y1 + c*z1 + d)/(a*i + b*j + c*k)

When the denominator is zero, the line is contained in the plane if
the numerator is also zero (the point at t=0 satisfies the plane
equation), otherwise the line is parallel to the plane.

crythias-ga
I am actually amazed that you managed to find some stuff that I hadn't
seen before, but the flash example was particularly galling.
I have had a look through - and it obviously has an implementation of
what I need, but I find looking at other peoples code like staring
into the mouth of madness, and pulling it apart into a useful form for
my project could well prove to be a test in itself.
BUT- that is what I will be doing tomorrow. Thanks a lot for your help
and input. If you want to be kept up to date on what it becomes you
can find my email on the site.

You're pretty much right for the different square. Note that it's
normal practice to label the points in order as you go around, but for
our purposes it doesn't really matter - your proposed adjustments will
be fine, as long as you remember to carry them through to where you
plot X!

Now as for solving these equations at run-time, it's no harder than
finding the point of intersection in the first place. The matrix
notation may be making it look harder than it really is. (Also note
that there are many algorithms for doing Gaussian elimination all over
the place. I'll describe a simple one below.) Let's review the
situation:

We have calculated the 3D coordinates of points A, B, C, and we know X
is on a given line. We calculate vectors B-A and C-A. We want
coefficients of X-A as a combination of the other two.

I'm going to define a vector datatype with fields x, y and z; I'll use
. to indicate a field of a record (actual syntax depends on your
programming language). Define vector variables xa, xa_k, ba, ca. The
latter two will simply be B-A and C-A; the former two will be the
constant and vector portions of X-A. (So if A = (a1, a2, a3) and X is
on a line passing through point (p1, p2, p3) in the direction (n1, n2,
n3) then xa = (p1-a1, p2-a2, p3-a3) and xa_k = (n1, n2, n3).) Also
define a matrix type as a 3*4 array, or an array of 4 vectors, and
define a matrix variable M.

Mathematically we have c_1 (ba) + c_2 (ca) = xa + k (xa_k).

Populate M with the vectors ba, ca, xa and xa_k. I will assume M is
defined as M[0..2, 0..3].

 * If the first element M[0,0] of M is zero, find a non-zero element
in the first column (there will be one since ba is not the zero
vector) and swap the entire row containing this element with the
entire first row.
 * Divide every element of the first row by the first element of the
first row (store this in a variable, or work backwards to the first
element - you don't want to do something like "for i = 0 to 3: M[0,i]
= M[0,i] / M[0,0]" since this will only divide the first element by
itself).
 * For each lower row, subtract from each element the product of the
corresponding element in the first row and the first element of the
target row. In other words, do something like this:
  for i = 3 to 0 step -1  [C-style: for (i=3; i>=0; i--) ]
    M[1,i] = M[1,i] - M[1,1] * M[0,i]
    M[2,i] = M[2,i] - M[2,1] * M[0,i]
  next
 * At this stage we have sorted out the first row and column. We then
do essentially the same thing with the rest of the matrix. If the
second element of the second column M[1,1] is zero, swap the second
and third rows.
 * Then divide every element of the second row by the second element
of the second row.
 * Then subtract from every element of the third row the product of
the first element of the third row and the corresponding element in
the second row.

At this stage your matrix will look like this:
[ 1 a b c ]
[ 0 1 d e ]
[ 0 0 f g ]
Since the columns are respectively the coefficients of c_1, c_2, 1 and
k, the last row translates to "0 + 0 = f + g*k", so k = -f/g =
-M[2,2]/M[2,3].
The second last row translates to "0 + c_2 = d + e*k", so c_2 = M[1,2] + M[1,3]*k.
The first row translates to "c_1 + a*c_2 = b + c*k", so c_1 = M[0,2] +
M[0,3]*k - M[0,1]*c_2.

And there you have it. Once you have c_1 and c_2 you can plot X on the
projected square.

Note: An improvement to the above procedure is, instead of checking
for zero (or near-zero) values, find the value closest to 1 in
magnitude. This is on a logarithmic scale (i.e. 0.01 and 100 are the
same distance away for our purposes), so you want to find the row with
the lowest value of abs(log(abs(M[i,0]))) in the first step. Then swap
this row with the first row. Do a similar check when you're down to
just the second and third rows. This will give you more accurate
results (better protection against rounding errors).

Hi charltonian-ga,

Yes, we end up with a set of simultaneous equations. We're trying to
find two values: how far X is in the A-B direction, and how far in the
A-C direction.

We juggle the lines around basically to avoid dividing by zero. In my
example, I swapped the second and third rows when I set up the matrix.
If I hadn't, I'd have had to do it later because my second row would
have had the first two elements as 0. As my last comment indicates,
it's best when implementing this in a program to always look for the
best value to divide by to minimise rounding errors (do a search on
"Gaussian elimination" "partial pivoting" to find out much more).
Note: Most people prefer to find the largest-magnitude value and swap
that with the row being processed. I personally don't like that
approach, but by all means feel free to do it that way rather than the
more complicated one I proposed.

Hope this helps!

hello manuka-ga,
I think this will be the last question (cue sighs of releif far and wide)
I managed to find (on wikipedia) a pseudo code example of gaussian
elimination, and converted it into flash (no mean feat - honestly!)
So then I put it into my cube, and the results were... erratic. I'd
say this was due to some oversight on my part/programming, but I just
wanted to be sure I'd converted all the things you'd told me
correctly.

'So if A = (a1, a2, a3) and X is on a line passing through point (p1,
p2, p3) in the direction (n1, n2, n3) then xa = (p1-a1, p2-a2, p3-a3)
and xa_k = (n1, n2, n3).'

Now I'm just wondering where n has come from. The line goes from point
P to the origin so (and forgive the mixture of letters.) does n = P or
is n = |P|, and then from this I also wonder if xa_k = xa*k or
something else? Could you just clear that up

'Mathematically we have c_1 (ba) + c_2 (ca) = xa + k (xa_k).

Populate M with the vectors ba, ca, xa and xa_k. I will assume M is
defined as M[0..2, 0..3].'

from this I'm assuming my matrix is
[BAx, CAx, XAx, XAkx]
[BAy, CAy, XAy, XAky]
[BAy, CAy, XAy, XAky]
(i've changed some letters to caps for clarity)

Now, I've put the latest version of the cube up for all to see, this
currently has a fudged version of XAk, which equals the value of XA*k
(that I derived from k = X/P [X is point of intersection, P is one end
of the line)
The attempt to move the dot is only 'working' on face 5.
If you are in a position to answer this question (as in you are a
researcher), then do that rather than comment :)

I noticed the lastr line of my array was wrong, should obviously be
[BAz, CAz, XAz, XAkz]
Also should have mentioned I got rid of the 'bubble' for faces 5 and
3, just in case it obscured the  red dot.