From: erich@eye.com (Eric Haines)
Newsgroups: comp.graphics,comp.windows.x.pex,comp.graphics.opengl
Subject: Re: Row major or column major matrices? - SUMMARY POSTING
Date: Wed, 27 Jan 93 14:40:23 GMT
Organization: 3D/EYE, Inc.  Ithaca, NY

Once upon a time (like, last week) I wrote:

>Someone was telling me that OpenGL allows only post-concatenation of matrices.
>This seemed bass-ackwards, and after a few minutes reconfirming in my slow
>turtle brain that you'd normally want pre-concatenation of matrices, I read
>over the OpenGL manual page carefully.  Aha, they store matrices in
>column-major form:
>
>	a0   a4   a8   a12	a typical	1  0  0 -2
>	a1   a5   a9   a13	translation	0  1  0  5
>	a2   a6   a10  a14	matrix -->	0  0  1  3
>	a3   a7   a11  a15			0  0  0  1
>
>
>Just out of curiosity, I looked at a few computer graphics books and whatnot
>and how they presented 3D matrices.

I received a large amount of mail about this topic (thanks, everyone), with
much of it having unexpected angles on the question.  There were a fair number
of responses which said that column major is what mathematicians use (and that
computer graphics people are finally seeing the light), while others said they
learned row major order in mathematics, engineering, and physics classes.  Go
figure.  Actually, Ron Levine's answer has an authoritative sound to it, and
he says that the type of notation used depends on the field of mathematics.

As Ron also points out, a source of confusion arose from my propagation of the
term "column major", which is what OpenGL calls the form shown above.  My
question was meant to address the pencil-and-paper notation of matrices, not
the internal representation in the machine.  As Mark Segal (who designed
OpenGL) writes, there is _no_ difference between IRIS GL and OpenGL on the way
matrices are passed via the API's or used internally, so there should be no
porting problems (other than rearranging the neuro-electrical pathways in the
programmer's head!).  The data elements 0 through 15 are in the same order for
a "row major" matrix as for a "column major" matrix.  To beat it to death:
the OpenGL matrix stores translation values in elements 12,13,14, which is
exactly where they are stored in IRIS GL.  There may be other systems in which
the translation elements are stored in locations 3,7, and 11, but this is a
separate computer language issue (can you say "FORTRAN"?).  As Ron Levine
notes, postfix vs. prefix is probably a better way to talk about these
representations, though then we have to remember that "prefix == translation
vector in column".

Anyway, here's a new list of who uses what.  I started to list everyone who
replied and anyone they mentioned, but it got too long and pointless.  The
ratio seems to be 2:1 of row major (postfix) to column major (prefix) users.

Eric Haines  erich@eye.com


Row Major users:

	Foley & VD (1st edition), Newman & Sproull, Graphics Gems series,
	Rogers books, Watt, Burger & Gillies, the Thalmanns, HP Starbase,
	RenderMan, SGI's IRIS GL, Sun's XGL

Column Major users:

	Foley & VD & F & H (2nd edition), OpenGL, Phigs (and PEX, I assume),
	Dore'


Here are various quotes of interest.  If you have too much time on your hands,
write me and I'll send you the entire file of mail message replies.  Some
related "this way or that" issues that people mentioned:
	right handed vs. left handed coordinate systems
	upper left corner vs. lower left corner being the origin of the image

Interesting to us amateur psychologists, there seems to be an inferiority
complex in the computer graphics community, e.g.  "mathematicians use column
major, so we should, too".  Reading the replies over, there's a fair mix of
people who learned row major in their engineering and physics and even math
classes.  At this point most computer graphics people seem to use row major,
and I like Robin Forrest's reason of how this began.  So, I don't believe
there's currently a "right" way, but rather it's worth conforming to the usage
of whoever you're talking with (see Jon Leech's quote as a good example of
this).  It'll be interesting to see how this sorts itself out in a decade or
two.  I suspect Gavin Bell's quote is probably right, since the F&VD&F&H book,
OpenGL, Phigs, and PEX are major influences in our field.

I wish I could have found a relevant quote from Major Major Major Major in
_Catch-22_, but no such luck.  Anyway, here we go (in some vaguely structured
order):



"`Row-major' and `column-major', as I have understood the terms for years,
refer to how the matrices are stored in memory, not to how they are used to
represent transformations.  That is, the terms distinguish between the Fortran
convention, in which the first subscript varies most rapidly as memory address
increases, and the C convention, in which the second subscript varies most
rapidly as memory address increases.  Although your note refers to how
matrices are stored, I think you are really concerned with quite a different
distinction, namely, whether the matrix represents a linear transformation as
a left multiplier of column vectors or as a right multiplier of row vectors.
Mathematicians sometimes distinguish these two conventions as the `pre-fix'
and `post-fix' conventions.

Mathematicians have long been split into two camps, between pre-fix and
post-fix preferences.  Geometers and analysts have tended more to the pre-fix
convention--thus you learned in calculus that f(x) denotes the value of a
function f for a domain element x.  Then, if you compose two functions,
(gf)(x) means g(f(x)), that is, first apply f then apply g.  This corresponds
to interpreting a matrix as a left multiplier of column vectors.

But some schools of abstract algebraists logicians, and some authors of
computer graphics books, have insisted on the post-fix (x)f or xf.  I always
work in the pre-fix convention when I have a choice, but this is only because
in the past most of my math professors and books have used it and so it is a
little more natural to me.  I especially prefer it in computer graphics, which
is inspired more by geometry than by abstract algebra.

But the two conventions are completely equivalent, and one should have no
difficulty in using either.  Of course it is important to know which
convention is used by any particular system with which you are working.  And
of course, the matrices may be stored in row-major or column-major order for
either convention of writing functional expressions; that distinction tends to
depend on the programming language."
	- levine@netcom.com (Ron Levine)


"I plead guilty.  As an author of the OpenGL specification, I'm the one
responsible for this foolishness.  I explained it in a message in
comp.graphics.opengl a couple of months ago (you can probably find it if you
look through your archives), but since you seemed to have figured out the
salient points, I'll just explain my reasons.

I have always been irritated with computer graphics treatments using rows to
represent vectors, since this is at odds with what is done throughout the
mathematics world, where vectors are represented by columns (there are some
good reasons for this, but I'll spare you).  I wanted to do my part to remedy
this disturbing situation (it had nothing to do with Foley and van Dam; I
wasn't even aware until recently that they had adopted a new convention).  So
I wrote everything in the spec with vectors as columns, with matrices and
application order corresponding.  The only snag was compatibility with
existing GL programs, so I used the subterfuge of saying that the matrices are
stored in column major order.  This was kind of a dirty trick, but I didn't
think it would seriously bother anyone.

As you note, of course, there is no actual difference.  You can rewrite
everything the old way, and then your matrices are in row major order.  I'm
sure it's not much consolation, but many numerical analysts and FORTRAN
afficianados actually prefer column major order."
	- segal@spud.asd.sgi.com (Mark Segal)



"I have no strong preference for either, but it would make my life much easier
if real-world systems could *choose one and stick with it*!  I recently had
days of unnecessary skullsweat grafting OpenGL evaluator onto a utility
library that used the opposite ordering."
	- jbulf@balsa.Berkeley.EDU (Jeff Bulf, aka Dr. Memory)



"Funny thing you know, one of the other summer students here are the ACGC is
writing a matrix transformation library, and nicked some of his matrix
formulas from the new GL reference manual.  Guess what?  They did some really
bizarre things (especially the perspective :-) until I told him they in row
major form, not column major like we were used to!"
	- rcskb@minyos.xx.rmit.OZ.AU (Kendall Bennett)



"I was also shocked to learn that OpenGL decided to use post multiplication of
matrices.  Not because I learned pre-multiplication, but because it is
opposite of what IRIS GL uses.  [...]

I learned the 'NEW' way of using matrices.  The reason that Foley decided to
use post-multiplication of matrices in the second edition, is because it
allows the notation to be written in the same manner as that used by
mathematicians.

If you look in linear algebra books, they all use post-multiplication
notation, and if you show a math person the 'OLD' way they will look at you
like a leper...  At least this is the opinion I formed from my teacher (who
was Dr. Foley)."
	- wlw@cc.gatech.edu (Wayne Wooten)



"I learned Row Major at Computervision and have been confused by column major
ever since.  Now the only question I want answered is whether the X offset is
the fourth element of the data structure.

I'm always amused at people saying the everyone does it this way or that.
Matrices are a fairly recent invention (in the 40's?).  And different
disciplines use row & column matrices arbitrarily, at least in my limited
understanding.  It's so arbitrary."
	-Jan "YON" Hardenbergh (jch@oki.com)
	[Jan is one of the designers of PEX. - EAH]



"The translation-matrix for me looks like:

 1  0  0  0
-2  1  0  0
 5  0  1  0
 3  0  0  1 "
	- Christian Linhart <chris@cosy.sbg.ac.at>



"The question of row versus column vectors is historical.  Steve Coons used
row vectors for his influential early papers on transformations (University of
Michigan Summer Courses in the mid 60's).  I asked him why in 1967 and he said
it was because it was easier for the stenographer to type row vectors!

Regarding left and right hand co-ordinate systems, Larry Roberts who
introduced 4x4 matrix transforms to graphics used RH co-ordinates and anyone
brought up with his papers or Coons papers uses RH systems.  Ivan Sutherland,
on the other hand, believed that z should be positive into the screen and
hence used LH co-ordinates as did his pupils.  Sutherland's treatment of
perspective also diverged from that devised by Roberts, hence the two schools
of thought there."
	- Robin Forrest (forrest@uk.ac.uea.sys)



"Actually, I have no clear preference, and I'll explain why.  In all my
education (math and physics, B.S Physics UCLA 1986), only row-major matrices
were used, so I naturally think of that as the standard.  However, I have an
idea as to why so many people are switching to column-major notation.  It's
so that matrices can be post-multiplied instead of pre-multiplied!  Post-
multiplication notation accords better with the compound operators of C and
C++.  If you're writing a matrix class in C++, and you want to multiply one
matrix by another, it seems natural to define the operator `*=' as the
multiplication operator, such that:

    A *= B means A = A * B.

I was writing such a class for a simple 3-D graphics program, and I quickly
realised that the most common multiplication I wanted to do was PRE-
multiplication.  I therefore said `Screw convention', and defined `*=' so that

    A *= B means A = B * A.

So, my solution was to change the standard C relationship between `*=' and
`*'.  Apparently, others decided it was better to change the very operation
of matrix multiplication to imply a column-major order, so that `A *= B'
would still mean `A = A*B'."
	- jasper@einstein.com (John Scott Peter XXXIII)



"`I am the major model of a modern Row Major General'..... I just saw the
Pirates of Penzance last week.  Even Gilbert and Sullivan were Row Major
fanatics, if I got the quote correct 8-)"
	- Brian Corrie <Brian.Corrie@cs.anu.edu.au>



"I go for what you call "row major". My "pappy's knee" was

  CS374 -- R.F. Sproull -- Introduction to Computer Graphics, Fall 1976

at Caltech, straight from the (then new) book. Together with Sutherland about
the most lucid lectures I ever heard (only heard Feynman speak once, and to a
semi-technical audience). I later had the privilege of brief involvement with
N&S vol. II while at Xerox Pasadena (our laser printers produced all the
camera-ready copy)."
	- Alan Wm Paeth <awpaeth@watpix.uwaterloo.ca>



"I learned linear algebra before computer graphics.  The linear algebra
books normally write vectors as column vectors."
	- Kevin.Wu@Eng.Sun.COM (Kevin Wu)



"I personally prefer row major...  however, computer hardware that I've worked
on recently preferred column major.  The reason for this was the presence of an
auto-increment load/store assembly instruction which allowed the matrix
routines to work faster if the data was presented to them in column major
form."
	- reid.judd@East.Sun.COM (Reid Judd - Sun NC Development Center)

[This answer (and a few others received) discusses the storage of row vs.
column, not the presentation on paper of row vs. column, a different issue.
"Row major" is definitely an overloaded term.  - EAH]



"Avast there, ye scurvy scum!  Dore' uses column vectors and LIKES IT!!"
	- hollasch@kpc.com (Steve Hollasch)



"The reason/justification/excuse for the change in matrices is to switch to
the way the mathematicians have been doing it all along.  They have a far
longer history than we do in this affine transform jazz."
	- Sam Uselton (uselton@nas.nasa.gov)



"I'm a row major type person.  From my engineering and graphics background
that is all I usually see.  I learned my first matrix stuff in a
Linear Algebra class in college. [...]

I don't really see any difference between the two methods other than I wish
they would pick one and stick with it!!!  By the way, engineers, structural 
mechanics, fluids guys, and aerodynamicists use row major from what I've 
been taught and seen."
	- Mike Goza (goza@cheers.jsc.nasa.gov)



"Characterizing the matrices is not the clearest way IMO.  I prefer stating
that points are either row vectors or column vectors.

Jim Blinn taught me to use row vectors in 1982 and Al Barr taught me to use
column vectors in 1984.  I prefer column vectors these days, although I'll go
either way as needed.  In teaching an undergraduate graphics course last
semester I used row vectors, since I was handing out copies of Blinn papers
and didn't want to confuse them too much.

I'm less sanguine about left-handed coordinate systems, which are Tools of the
Devil (as anyone doing physically based modelling should think)."
	- Jon Leech <leech@cs.unc.edu>



"I got started using row-major matrices for transforms when we used
mimeographed copies of the manuscript for the 1st edition of Newman and
Sproull in Prof. Bert Herzog's class at the Univ. of Michigan!  That should
date me pretty well.  :-)

The system I work on now uses column-major matrices, and to make things more
interesting, homogeneous coordinates are expressed as (w,x,y,z) instead of
(x,y,z,w).  That mixes things up pretty well in those transform matrices and
keeps me on my toes...

I hate to try to classify people by their preferences to use row-major versus
column-major form.  Maybe engineers tend to use row-major, while
mathematicians tend to use the transpose; don't know about physicists.
Conventions do seem to tend to cluster around various subfields.  Computer
graphics, maybe because it is so cross-disciplinary, is definitely in a state
of flux on transform order conventions.

The row-major convention is good for thinking about transforms as operators.
Column-major form is best for thinking about transforms as functions, e.g.,

                    v' = T(v)

for a transform T that maps vector v to vector v'; then transform
concatenation is just function composition:

                    v' = T2(T1(v))

May you always compose your matrices in the "right" order..."
	- Ron Capelli <capelli@vnet.ibm.com>



"It's even more surprising since the current version of GL normally
pre-concatenates. I can imagine some hard to find bugs when people port old GL
code in which they generate their own matrices from scratch.  [not true - EAH]

I'm not too upset though, cause column vectors and post-concatenation is what
I learned as an engineer, and so it seems more natural to me.  Note, that
pre-concatenation with column vectors or post-concatenation with row vectors
is useful.  In this one instance I prefer PHIGS, which has a direct mechanism
for doing both pre- & post-concatenation of matrices ...  you can
post-concatenate in GL but only indirectly and inefficiently.

According to the GL manual, GL uses row vectors and pre-multiplication for
purely historical reasons related to the efficiency of early hardware."
	- ledwards@leland.Stanford.EDU (Laurence James Edwards)



"In 10 years we will probably remember the good old days when the translations
were at the bottom of the matrix..."
	- gavin@krypton.asd.sgi.com (Gavin Bell)