for an arbitrary vector V, and its reflection V' into a specific octant, how do I find the reflection matrix R such that V' = R.V?

Question

I'm working on a tiled 2D game, and trying to implement a more complicated version of a fairly standard line-of-sight algorithm. When checking for occlusions, I need to be able to take neighbouring cells into account, but exactly which neighbours (and which of their edges) are important will depend on which octant the line-of-sight vector is in.

I feel like, if I can reflect the original vector into the ENE octant (+x, +y, θ <= 45°), perform my calculations, and then perform the inverse reflection to get back to the original coordinate space, then that would make things quite easy (i.e. I wouldn't need 8 distinct implementations).

The information I've been able to find so far about performing reflections mostly assumes I have a known reflection (e.g. "over the x axis", "over the y=mx axis"), and that I'm trying to calculate the result of applying that reflection. But I'm trying to do the inverse: I know where I want the vector to land, I'm trying to find a reflection that will put it there (and its inverse, to put it back after).

As a programmer, getting the arbitary vector v into the desired octant is easy:

new.x = abs(v.x)
new.y = abs(v.y)
if (new.y > new.x) swap(new.x, new.y)

but that leaves me no crumb to find my way back to the original coordinate space.

Intuitively, it seems like I might be able to build my reflection matrix using combinations of sign(v.x), sign(v.y), abs(v.x), abs(v.y), etc? But I would just be taking shots in the dark, and if I got the result I wanted, I couldn't say for certain whether it was correct, or just a one-time coincidence. I kinda know what a reflection matrix looks like, but I don't understand how to construct one.

Background: I'm not fluent in mathematical notation or terminology, and I have no formal education in linear algebra. I understand the basic operations, in an "occasional dabbler that learned from the internet and has to look it up and learn it all again each time" capacity, but not well enough to recognise which operations might be useful here.

Further background: my real input is two points (A and B), and I'm glossing over V=B-A to translate to the origin, and then the inverse again after, because I understand that aspect.

Edit: It seems like there's only 8 possible reflection axes I would need to consider (including the case where it's already in the desired octant), so I guess I could take a brute force approach of just looping over those and trying them in turn, until I find the one that puts the input vector into the desired octant. But I wouldn't learn anything from doing that...

Edit 2: I already have other code that uses a similar octant-based divide-and-conquer strategy, which means I can already reflect easily from the ENE octant back into real grid coords iff I have a matrix representing that reflection to use -- which is why I'm thinking about how to represent this as a matrix. The existing code is used by my player-field-of-view calculation, which loops over all 8 octants, so its reflection matrices are already known -- which is why I have reflection matrices already, yet don't know how to derive one arbitrarily :)

Edit 3: I've been experimenting with the "householder transformation" to turn a reflection axis (l = v + v') into a reflection matrix:

$$ A = \frac{1}{\lVert \vec{l} \rVert ^2} \begin{bmatrix} l_x^2 - l_y^2 & 2l_xl_y \\ 2l_xl_y & l_y^2 - l_x^2 \\ \end{bmatrix} $$

This works well (i.e. produces reflection matrices that look like what I expect) for 4 of the 8 octants. Three of the others end up non-diagonal, with fractional values; the fourth, where v and v' are directly opposite each other and thus their resultant is (0, 0), is all NaNs.

I'm about to try a different strategy, using the 3 bits of information that @indnwkybrd observes as a lookup into the 8-slot array of precalculated reflection matrices that I already had anyway...

Answer 1

From what I can tell, I'm not sure that a reflection matrix (at least, in the mathematical sense) is really what you're looking for. A reflection matrix will just mirror your vector about some line through the origin. For example, a reflection matrix which represents a reflection about the horizontal axis, will map a vector -v to v, but it will also map v to -v, which isn't what you want.

You would end up needing different reflection matrices, depending on the starting octant of your vector. Or you could compose separate reflection matrices about the two axes and the 45° line conditionally with if-statements. But why complicate matters by worrying about matrices in the first place, if you have to use if-statements anyway?

I think you're already onto the answer - you need some sort of "crumb" to find your way back to the original octant.

Conceptually, when you take the absolute value of v.x and v.y to bring the "new" vector into the positive quadrant, in a sense you "destroy" the information about their original signs. To get them back to where they started, you have to preserve that information somewhere else. The functions sign(v.x) and sign(v.y) achieve this purpose, by simply going back to your original vector v, and grabbing the information.

When you swap the x and y coordinates of new, but only in the case where new.y > new.x, you similarly destroy the information about whether your vector started out above or below the 45° line. Just as with the signs, you need some way to preserve this information elsewhere, if you hope to send the vector back to where it came from. The "crumb" in this case is the Boolean value of your if-statement. If it's true, you know you have to do a 45° reflection; if it's false, then none is necessary.

There's really no way around this. A more concrete way to see it is with an example. Suppose you have, say, u.x = 1 and u.y = 2 on one hand, versus v.x = 2 and v.y = 1 on the other. Without some external "crumb" of information, both u and v will be sent to the same new. You will have no way to distinguish one from the other.

In practical terms, you could try something like this. Not sure what language you're programming in here, so let's just use pseudocode. (I'm assuming here that sign(x) returns $1$ if $x > 0$, and $-1$ if $x < 0$).

define function stuff(x, y):
    -> do whatever you need to do on the transformed vector, within a single octant

u.x = abs(v.x)
u.y = abs(v.y)
if (u.x >= u.y) then
    w = stuff(u.x, u.y)
    new.x = w.x * sign(v.x)
    new.y = w.y * sign(v.y)
if (u.x < u.y) then
    w = stuff(u.y, u.x)
    new.x = w.y * sign(v.y)
    new.y = w.x * sign(v.x)

Notice within the context of the stuff function, there is no info about what octant the arguments x and y started in. We destroyed the info about the starting quadrant by taking abs( ), and we destroyed the info about above/below the 45° line between our if-statements and swapping the arguments to stuff( ) in one case. But we reapply the info about the quadrant at the end with sign( ), and we reapply the info about above/below the 45° line when we un-swap the values into new.

---

Edit: if you do really want to use reflection matrices, then the approach isn't that different. If you're going to destroy 3 bits of information (the $x$-sign, the $y$-sign, whether $y>x$) before doing stuff with your vector, you still have to track 3 bits as your "crumbs" to send it back. Then you'd use these matrices:

If v.x < 0: apply reflection about y-axis. $$ \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} $$

If v.y < 0: apply reflection about x-axis. $$ \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} $$

If v.y > v.x: apply reflection about 45° line. $$ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} $$

Now do your stuff to the vector.

Now undo the reflections:

• If v.y > v.x: reapply the 45°-line reflection matrix.
• If v.y < 0: reapply the horizontal reflection matrix.
• If v.x < 0: reapply the vertical reflection matrix.

However, this is all just the linear-algebra-ish way of saying the exact same things about shuffling signs around and swapping coordinates. Useful I guess if you're programming in a very math-oriented language? But otherwise, it's a lot of complexity, with the exact same end game.

---

Edit 2: On a totally separate note, don't forget, if v is really close to (some multiple of) $(0, 0)$ or $(1, 1)$, i.e. if the angle of v is really close to 0° or 45°, you may "see" squares to the right or left respectively, and still end up needing to look outside your octant, anyway... so maybe you might want to consider rotation matrices, instead of reflections? If v = (v.x, v.y) is your original vector, in any quadrant, then you can get a vector rot_cc which is v rotated by theta degrees in a counterclockwise direction, as:

rot_cc.x = v.x * cos(theta) - v.y * sin(theta)
rot_cc.y = v.x * sin(theta) + v.y * cos(theta)

To rotate clockwise you just rotate counterclockwise by -theta. Or you just use this, plus the identities, $\cos(-\theta) = \cos(\theta)$, and $\sin(-\theta) = -\sin(\theta)$, and get a clockwise-rotated vector rot_c as:

rot_c.x = v.x * cos(theta) + v.y * sin(theta)
rot_c.y = -v.x * sin(theta) + v.y * cos(theta)

Answer 2

Posting up what I did, because it solved my real problem (and I am no longer thinking about it). But it's a programming solution, not a mathematical solution, and the original question remains only partially solved (by "Edit 3", using the householder transformation). So I won't accept this as "the" answer.

@indnwkybrd observes the three bits of information that are needed to track the transformation into the desired octant and back:

• whether x is negative
• whether y is negative
• whether the absolute value of y is greater than that of x

3 bits means 8 possible values, which exactly matches the number of octants. So I can just bit-twiddle those conditions together to produce a number between 0-7,

  (abs(vy) > abs(vx)) << 0
| ((vx) < 0) << 1
| ((vy) < 1) << 2

use that to index into a lookup table to find the "nth" octant,

const unsigned octant_lookup[] = { 0, 1, 3, 2, 7, 6, 4, 5 };
#define vector_octant(vx,vy)                            \
            octant_lookup[   (abs(vy) > abs(vx)) << 0   \
                           | ((vx) < 0) << 1            \
                           | ((vy) < 1) << 2            \
                         ]

which I can use as an index into an array of precomputed reflection matrices (in anticlockwise order) that I already had lying around,

static const int octanttx[][4] = {
    {  1,  0,  0,  1 },
    {  0,  1,  1,  0 },
    {  0, -1,  1,  0 },
    { -1,  0,  0,  1 },
    { -1,  0,  0, -1 },
    {  0, -1, -1,  0 },
    {  0,  1, -1,  0 },
    {  1,  0,  0, -1 },
};

and, finally, I can call my function:

int vx = x2 - x1;
int vy = y2 - y1;
unsigned octant = vector_octant(vx, vy);

do_stuff(x1, y1, x2, y2, octanttx[octant]);

Where do_stuff() is implemented in terms of the most convenient octant to think about, but having the correct reflection matrix, it also knows how to transform back and forth between convenient coordinates and real coordinates.

[I could skip a level of indirection by storing the array of matrices in the order produced by the bit twiddling, but I use this array elsewhere too, and it's easier to reason about when it's sorted around the circle like this.]

I still don't know how to calculate the 8 reflections mathematically; I got these by noticing the pattern and then fiddling with +1, 0 and -1 until it worked.