Matrix handling (atom.transform)

Page: 1 2
ID:1353302
 
Aug 14 2013, 11:57 am
Resolved
The new atom.transform var lets you scale and rotate icons easily. A new datum, /matrix, can be used to work with transformations.
Applies to:DM Language
Status: Resolved (500.1205)
This issue has been resolved.
It's time to get input on another planned feature.

I want to add a new var called atom.transform (also to images; this will apply to all Appearances). This will be a matrix stored as a simple 6-element list, or null when using the default. Tom and I agreed this makes more sense than doing separate rotate/scale/etc., but we should have helper functions for it.

Originally I was thinking of doing something like this:

// create a rotation matrix
transform = matrix(45, MATRIX_ROTATE)
// scale the transform matrix by 2x2
transform = matrix(transform, 2, 2, MATRIX_SCALE)


This is a very Blend()-like syntax, but as Tom pointed out, while it's flexible it's not necessarily intuitive. I do want KISS here, so I'd preferably at least want a way to multiply matrices, rotate, scale, and possibly translate. (My original stable of choices included multiply, add, subtract, invert, rotate, scale, translate, and I was thinking interpolate might also be useful.) I suppose there's no reason the original format couldn't be used, with aliases referring to the common operations, but it'd be nice to get input on what people would find useful and how they'd like to work with it.

This is the way a matrix would lay out:

transform = list(a, b, c, d, e, f)

a b c     x     x'
d e f  ×  y  =  y'
0 0 1     1     1

x' = ax + by + c
y' = dx + ey + f


A clockwise rotation by angle A, where s=sin(A) and c=cos(A), would be in the form list(c,s,0,-s,c,0). Obviously that's not something we want users to have to calculate, hence the need for helper functions.

I realize we already have pixel offsets for translation, but it seemed reasonable to include something in the matrix itself.
Aug 14 2013, 7:29 pm
If they're just /lists, I would prefer the matrix type/operation constant be first, just since the other parameters don't have any meaning until you know it:
// orbit (column-major?)
var/transform = matrix(MATRIX_MULTIPLY, \
                       matrix(MATRIX_ROTATE, 45), \
                       matrix(MATRIX_TRANS, 16, 0))


If we could get an actual /matrix type, then we could use the * operator, and have procs like matrix.Inverse(), matrix.Scale(2,2), matrix.Translate(), ect.

Also, what do you mean by an interpolate operator?
Aug 15 2013, 7:05 am
I was thinking along the lines of something like matrix(m1, m2, 0.5, MATRIX_INTERPOLATE), the idea being it'd take two matrices and a blend factor and try to interpolate from one to the other. (More generally, the idea will be to isolate translation and rotation so they can be done separately, since interpolating rotation means you'll want to interpolate the angle.) Such code will be needed for animation purposes anyway. Given the way such things work, it could extrapolate as well.

However, Tom is of the opinion that the Blend-like operator syntax is too kludgy, and I see his point. It feels more like something a programmer would do than what a user would be happy using. So at the very least I think we'd probably want some helper functions with simple names, even if they're aliases to a single function. I'm not even averse to leaving said function undocumented.

No matter what, I think this is a good syntax:

matrix_rotate(45) // create a rotation matrix
matrix_rotate(m, 45) // m * matrix(45)

I see it being very likely that users will want to modify existing matrices as much as create new ones on the fly, so it makes sense to build in multiplication.
Aug 19 2013, 6:09 pm
Are matrices limited to 3x2, or is that just a limitation of the transform variable?
Also, why not support 3D rotations with larger matrices?
Aug 19 2013, 8:40 pm
In response to Kaiochao
Kaiochao wrote:
Are matrices limited to 3x2, or is that just a limitation of the transform variable?
Also, why not support 3D rotations with larger matrices?

The matrices are essentially 3x3, but with one of the rows taken out. Or rather, a column. After reconsideration I've made the matrices like so:
          a d 0
x y 1  *  b e 0  =  x' y' 1
          c f 1
The reason for this approach is that then matrix multiplication makes more sense, as it's in a left-to-right order as new transforms are added.

3D transforms wouldn't really be useful, since we're only transforming a 2D image. There's no z dimension to transform.
Aug 20 2013, 11:26 am
In response to Lummox JR
For the scope of atom.transform, it's probably reasonable for it to take a 3x3/3x2 matrix. However, I think that the third column should be left in, if only as an option. Using skew, people can create cool 3D hacks even if there is no z depth.

However, in general, why not support 4x4 matrices? If the effort is being put for native matrix functions, may as well get the benefit.

I'm also personally more of a fan of row-major matrices, just because more literature is written on it, and you see software like OpenGL/glm/GLSL use row-major matrixes. I can understand the benefit of doing it this way though, so it's not too big of a deal for me.
Aug 20 2013, 11:34 am
I also think that having a sort-of equivalent client.transform would be awesome. Scaling/rotating/translating the screen would be a great addition.
Aug 20 2013, 1:13 pm
In response to Unknown Person
Unknown Person wrote:
For the scope of atom.transform, it's probably reasonable for it to take a 3x3/3x2 matrix. However, I think that the third column should be left in, if only as an option. Using skew, people can create cool 3D hacks even if there is no z depth.

You can skew with a 3x3 matrix just fine. transform(1,1,0,0,1,0) is a horizontal skew slanting the icon to the right. A 4x4 matrix would only be required for 3D transforms, when there's a z coordinate. The third column of the 3x3 doesn't really come into play; the only reason there's a third row is to support translation.

However, in general, why not support 4x4 matrices? If the effort is being put for native matrix functions, may as well get the benefit.

But to what purpose? BYOND users wouldn't have a need for 3D matrices.

I'm also personally more of a fan of row-major matrices, just because more literature is written on it, and you see software like OpenGL/glm/GLSL use row-major matrixes. I can understand the benefit of doing it this way though, so it's not too big of a deal for me.

I too am more of a fan of the row-major approach, per my initial post. I prefer to look at matrices that way. However, then the only way multiplication makes sense is if you do the newest operations before the oldest. I think for left-to-right thinking this is easier to grasp.

The only time the row/column order really matters though is when it comes to multiplication of two matrices. For any other time you can always think of them in a row-major order.

I also think that having a sort-of equivalent client.transform would be awesome. Scaling/rotating/translating the screen would be a great addition.

That would be pretty ugly to blit. There might be a few effects to be gained from it, but not enough to make it worth it IMO.
Aug 20 2013, 2:07 pm
In response to Lummox JR
Lummox JR wrote:
You can skew with a 3x3 matrix just fine. transform(1,1,0,0,1,0) is a horizontal skew slanting the icon to the right.

Sorry, I didn't mean skew, but rather a perspective projection, to produce a visual effect like this: https://www.svgopen.org/2008/papers/ 86-Achieving_3D_Effects_with_SVG/ figure_3_example_of_perspective_projection.png

A matrix of this form (row major) might do the trick (if the origin exists at the center of the icon).

1 0 0
0 1 0
0 1 0

A 4x4 matrix would only be required for 3D transforms, when there's a z coordinate. The third column of the 3x3 doesn't really come into play; the only reason there's a third row is to support translation.

But to what purpose? BYOND users wouldn't have a need for 3D matrices.

Probably not in anything with respect to rendering graphics on the screen, but I think it's pretty feasible for a developer to model 3d space with 4x4 matrices, even if it doesn't come out as true "3D". Or even to use a 4x4 matrix to model color transformations.

It's feasible enough for someone to write their own matrix library to do this, so I guess my question would be this: what kind of performance improvements would BYOND get from a native implementation? If there are speed benefits, it may be worthwhile to support larger matrices for these feasible use cases. If not, then perhaps this would be better done by a 3rd party library.

That would be pretty ugly to blit. There might be a few effects to be gained from it, but not enough to make it worth it IMO.

I think with sufficient anti-aliasing, it shouldn't be bad, but I guess you tell me, since I don't really know the display stack.
Aug 20 2013, 4:12 pm
In response to Unknown Person
Unknown Person wrote:
Sorry, I didn't mean skew, but rather a perspective projection, to produce a visual effect like this: https://www.svgopen.org/2008/papers/ 86-Achieving_3D_Effects_with_SVG/ figure_3_example_of_perspective_projection.png

A matrix of this form (row major) might do the trick (if the origin exists at the center of the icon).

1 0 0
0 1 0
0 1 0

A row-major matrix will basically ignore the third row, so that would be lost.

A vanishing perspective transform is basically impossible to achieve with affine transforms, though, unless a hidden z dimension is added and the display makes the adjustment. With a standard perspective projection, you basically have an infinite frustrum with no far plane. If the near plane is z=1 and everything beyond is z>1, then the x and y coordinates, relative to the center, get divided by z.

DirectX could probably handle that okay, since it can understand perspective projection. GDI can't, though, since it's drawing transforms with PlgBlt(). (I looked into switching us to SDL, but apparently it doesn't do affine transforms for sprites. I was shocked. Apparently you need another library for that, and it does all its transforms in software which is unacceptable.)

That would be pretty ugly to blit. There might be a few effects to be gained from it, but not enough to make it worth it IMO.

I think with sufficient anti-aliasing, it shouldn't be bad, but I guess you tell me, since I don't really know the display stack.

It's not the aliasing I'm worried about so much as the actual blit. We're already drawing everything to a buffer and then blitting that to the screen. To support client.transform we'd need an intermediary buffer. Performance would get downright ugly in software mode.
Aug 20 2013, 5:02 pm
 
// create a rotation matrix
transform = matrix(45, MATRIX_ROTATE)
// scale the transform matrix by 2x2
transform = matrix(transform, 2, 2, MATRIX_SCALE)

Frankly, I don't see the reason for using this kind of syntax over separate procs for scaling, rotating, et cetera. It's only slightly more flexible (e.g. in terms of acting on parameters), but as long as devs can access the matrix super flexibility shouldn't be a concern.

If we could get an actual /matrix type, then we could use the * operator, and have procs like matrix.Inverse(), matrix.Scale(2,2), matrix.Translate(), etc.

I like this syntax over making the transform var a list. Being able to multiply matrices with the * operator seems very convenient.
Aug 20 2013, 5:08 pm
I would prefer row-major, as I think the left-to-right transformation order is much more intuitive. The OpenGL documentation/spec is written with respect to column-major (and DirectX uses row-major, I think), but that shouldn't really matter because the nuts and bolts will be hidden from the average user.
Aug 20 2013, 5:14 pm
In response to DarkCampainger
DarkCampainger wrote:
I would prefer row-major, as I think the left-to-right transformation order is much more intuitive. The OpenGL documentation/spec is written with respect to column-major (and DirectX uses row-major, I think), but that shouldn't really matter because the nuts and bolts will be hidden from the average user.

But left-to-right transformation order is what you get by using column-major; that's the only reason I'm doing it that way. In other words:

point * transform1 * transform2 = point'

In row-major order, it has to be this way:

transform2 * transform1 * point = point'
Aug 20 2013, 5:23 pm
In response to Lummox JR
I think you've got 'em flipped:
http://www.scratchapixel.com/lessons/3d-basic-lessons/ lesson-4-geometry/conventions-again-row-major-vs-column-majo r-vector/
(scroll down to the first table)

I had to learn both at the same time (game dev classes used row-major, graphics dev classes used column-major), but I strongly remember row-major being left-to-right:
orbitTransform = transMat * rotMat
Aug 20 2013, 5:24 pm
In response to Toadfish
Toadfish wrote:
// create a rotation matrix
transform = matrix(45, MATRIX_ROTATE)
// scale the transform matrix by 2x2
transform = matrix(transform, 2, 2, MATRIX_SCALE)

Frankly, I don't see the reason for using this kind of syntax over separate procs for scaling, rotating, et cetera. It's only slightly more flexible (e.g. in terms of acting on parameters), but as long as devs can access the matrix super flexibility shouldn't be a concern.

I've decided on a best-of-both-worlds approach, keeping my original concept intact but adding:

matrix_rotate()
matrix_scale()
matrix_translate()
matrix_multiply()

Those are the options users will want most.

If we could get an actual /matrix type, then we could use the * operator, and have procs like matrix.Inverse(), matrix.Scale(2,2), matrix.Translate(), etc.

I like this syntax over making the transform var a list. Being able to multiply matrices with the * operator seems very convenient.

I quite agree. Tom mentioned something along these lines recently, that it would be really nice to have more of an object-oriented layer on tom of standard DM (maybe something defined in stddef.dm) that could do this. There are two problems with this method at present:

1) The DM language doesn't support operator overloading. Although this could be managed with a specialty datum flag, that's kind of hacky and not very expandable; in principle it makes sense to come up with a more general solution. (I'm wide open to suggestions as to how we could do that--operator overloading has been much requested! If there isn't a thread for it already, a new one could be made.)

2) If matrix features aren't used, it doesn't make a lot of sense to lock the code into requiring build 500. Defining this in stddef.dm would mean that the matrix() calls would be compiled in no matter what (forcing the .dmb to require build 500), even if this datum is never used.

In spite of those obstacles I think it'd be a good thing to come up with a way to solve them both, so that we could move toward some nicer object-oriented code.
Aug 20 2013, 5:31 pm
In response to DarkCampainger
DarkCampainger wrote:
I think you've got 'em flipped:
http://www.scratchapixel.com/lessons/3d-basic-lessons/ lesson-4-geometry/conventions-again-row-major-vs-column-majo r-vector/
(scroll down to the first table)

I had to learn both at the same time (game dev classes used row-major, graphics dev classes used column-major), but I strongly remember row-major being left-to-right:
orbitTransform = transMat * rotMat

Yeah, it looks like I got confused on the terminology (as did Unknown Person). The row-major format is actually what I'm going with:
          a d 0
x y 1  *  b e 0  =  x' y' 1
          c f 1
Column-major would be the other way, which is what I originally had in mind. I think that looks prettier but it means you have to do all the transforms right to left, which is annoying.
Aug 20 2013, 6:12 pm
We have a thread for operator overloading: http://www.byond.com/forum/?post=107902, from 2011 (which I found through forum search, but in which it looks like more than one of us were participants!). I think it has some pretty good suggestions, but I don't know if it satisfies. If you'd bump the thread with your current thoughts about this (foreseeable issues, etc.), Lummox, perhaps we can get the discussion going again?
Aug 26 2013, 9:05 pm
Just throwing an update on this thread, this is what's in place right now:

There's a new /matrix datum with vars a through f, and the following procs:

Add()
Subtract()
Multiply()
Invert()
Turn()
Scale()
Translate()
Interpolate()

All of these will modify the src matrix except for Interpolate().

The matrix() proc will create a new matrix: either a default, a copy of another matrix, or one with all six vars given. (It also is the powerhouse behind the other operations, but I'm leaving that undocumented as it's really too complex to go into.) You can feed it a list, too; it isn't fussy. In fact most of the binary operators will take a list or null as the second operand; likewise you can assign a list or null to atom.transform.

The following operators are supported:

+
-
*
/
~ (invert)
+=
-=
*=
/=

The turn() proc is supported as well, as it is for icons; as with icons, it produces a copy rather than modifying the original.

Reading from atom.transform gives you a new datum that's a copy of the original. Modifying this datum will not (in the current implementation) alter the atom until you assign it back to atom.transform. I suspect this is not really a severe limitation, as most users will either be assigning directly to it or using operators. The assignment operators, like atom.transform *= 2, should work as expected, which I'll be testing.

Examples of use in atom.transform:

// turn 45° clockwise
usr.transform = turn(atom.transform, 45)
// scale by 2
usr.transform *= 2

// take a 32x32 icon and make it look like a 64x32 isometric tile
var/matrix/M = new
M.Turn(45)
M.Scale(1, 0.5)
usr.loc.transform = M
Aug 27 2013, 4:28 am
Looks great, definitely an improvement over using lists. Using a-f to represent the values in a matrix doesn't seem very descriptive, though. Would it make more sense to use a naming convention similar to XNA's matrix object?
Aug 27 2013, 6:14 am
I was wondering about that myself. DirectX uses something similar, an _ij var such as _11, _21, _31, etc. I'm not sure what users would find most intuitive. There's still time for the a-f notation to be changed so I'm way open to suggestions.
Page: 1 2