Row Major Order vs Column Major Order in Computer Science

I was just reading this great article on Wikipedia about Row Major Order and Column Major Order and how they relate to Computer Science and storage of two-dimensional arrays. It was really enlightening for me so unless you know all about it, I would suggest giving it a read if you see anything you like here. I have been doing some stuff with GLSL and reading about it and I was surprised to read that it uses column major order when storing matrices (which are basically just 2D arrays).

When I took Linear Algebra at the University a while back we had talked a bit about the differences between doing things using either rows or columns and that you could do both. I did not quite understand this at the time, I knew that you could do the same things in different ways if you used rows or columns. But now I know that at least when it comes to computers there can be applications where either one could be better than the other.

Row-Major Order

I am going to talk for a bit about Row-Major Order, and anyone that is close with the C/C++ programming language will know that two dimensional arrays are stored in physical memory contiguously like so:

int A[3][4] =  {{19,22,31,42},
                 {50,61,32,83}, 
                 {93,47,15,66}};

This array would be stored in memory in Row-Major Order with rows one after the other stored in memory, with the array cells contiguously stored as shown below:

19

22

31

42

50

61

32

83

93

47

15

66

If you know that your array is in Row-Major Order and initialized with data of a certain type and size then you can calculate the linear offset in memory of a certain element from the beginning of the array. The figure I created below shows how to calculate such an offset.

'Two-Dimensional' Arrays in Java vs C++

This is also how two dimensional arrays are usually stored in assembly, but you have enough control at that level to store them however you want. It is important to know if you are using Java, that despite being similar in many ways to C++, it does not actually support two-dimensional arrays. Probably the biggest characteristic of an array whether one-dimensional or two-dimensional is that it is stored in contiguous memory, all of it together. In Java what we have are arrays of arrays. It might sound nit-picky but it is not quite the same thing as the two-dimensional arrays in C/C++.

In Java, they do it similar to Row-Major Order. If we take the above example again. If we declare an integer array in java int A[3][4] it would initialize an array that we could reference as simply A, where A.length would return 3. A can be referenced as an array of references or 'pointers' to 3 different integer arrays. In Java it is worth mentioning that because these are references Java's arrays are inherently jagged. You can have different number of elements in each array, and even a null row. We could set A[2] = null; and it would delete the reference putting the integer array and the 4 ints up for garbage collection.

In the above array int A[3][4] in Java each of our three rows would have elements that were stored in contiguous memory, but the rows themselves are not stored in adjacent memory addresses. You cannot count on them to be anywhere related in memory:

19

22

31

42

50

61

32

83

93

47

15

66

Here in Java the element that contains 42 would not be stored next to the element containing 50. 83 is not contiguous to 93.

Column-Major Order

There are several programming languages that store two-dimensional arrays in Column-Major Order rather than by row. This is popular for matrix operations so it can be found in the MATLAB computing language, Fortran the scientific computing language, and because of heavy matrix math in graphics operations, shading languages such as GLSL and HLSL use Column-Major Ordering.

Using Column-Major Order, columns instead of rows are stored in sequence. If we take our original array A,

int A[3][4] =  {{19,22,31,42},
                 {50,61,32,83}, 
                 {93,47,15,66}};

And we store the above array in Column Major order it becomes the following stored contiguously in adjacent cells of memory, with one column after the other as shown below:

19

50

93

22

61

47

31

32

15

42

83

66

If the array is stored like this, then the linear offset can be calculated as explained by the following figure I created with LaTeX below:

Graphics shader languages and the like use Column-Major Ordering because certain matrix operations require us to consider a matrix as sets of column vectors. This would be very slow if we had our matrices in storage in Row-Major Order. In fact the extra work needed if we have to consider a Row-Major Ordered array as a Column-Major Order array is that of transposing the matrix. This is relatively expensive and is hard to do in place for arrays with an unequal amount of rows and columns.

Column-Major Ordering in OpenGL Shader Language - GLSL
In the open graphics library OpenGL the shader language called GLSL has arrays in the form of vectors and two-dimensional arrays in the form of square matrices. There are mat2, mat3, and mat4 data types, which store 2x2, 3x3, or 4x4 matrices respectively (float by default). Initialization in GLSL is mostly handled through constructors and it has pretty good flexibility about this. You can assume always though that initialization will be handled in Column-Major order. The following illustrates my point:

vec2 a = vec2(3.0, 4.0); // stored column vec [3.0,4.0]
vec2 c = vec2(5.0, 6.0);

mat2 ac = mat2(a,c); // Stored in memory as [3.0,4.0,5.0,6.0] mat2 d = mat2(3.0,4.0,5.0,6.0); //two column same as ac

UV Texture Coordinates and Texture Mapping - OpenGL / DirectX

Because I am not in school right now, I have been getting pretty heavy into WebGL graphics trying to reinforce and learn new 3D and graphics concepts. At the moment I am trying to get a solid foundation on texture mapping before moving onto bump mapping, shadow mapping and the like, so I decided to write up a simple tutorial.

When I am trying to learn something new I think a great way to start off is to at least skim the associated wikipedia page, so why not pop over there either before or after reading this and check out the page on Texture Mapping. Did you know that texture mapping was first laid out in the Ph.D thesis of Dr. Edwin Catmull all the way back in 1974? No wonder the Atari and the like debuted just a few years later.

Texture coordinates are used in order to map a static image onto a 2D or 3D geometry in order to create a mesh. There are a few different ways that texture coordinates can be defined. In any case the standard is to specify them as an ordered pair (u, v) usually with values ranging from 0 to 1 floating point.

Basically the idea with any kind of texture coordinates is that we will use some of the coordinates to map to particular vertices of a geometry. The rest of the pixels are interpolated between the specified vertices. All kinds of 3D objects can be mapped to using a 2D texture, however the mapping will be different for differently shaped objects and obviously some objects will be harder to map than others.

I think that the typical workflow at most studios would involve a modeler first creating the geometry, then using tools to unfold it and draw a texture, by using these tools they can match the texture coordinates to the objects correct associated vertices. The mapping data would then be handed over to the programmer. I am not very experienced with the modeling side of things so I would love to hear from anyone who knows more about how this works. A lot of graphics libraries will handle this for you in some default way for simple geometries, whilst having some mechanism for the programmer to specify custom mapping of texture coordinates to the objects local coordinates.

With that being said, it makes sense that regardless of how the coordinate system is set up, it seems they are always specified as floating point values between 0 and 1. Basically, this means we are only specifying positions on our texture as percentages. This is because we need to interpolate between vertices and this makes it a lot easier.

Although, Cartesian coordinates are the ones we all learn in school and are probably the simplest, these are not however the coordinates that are usually used with textures. Instead, textures are mapped according to what we call UV Texture Coordinates. Basically UV coordinates are just a way of making the range of our coordinates can take be the same regardless of the width or height of the image.

Even though Cartesian coordinates are not used for mapping a texture to geometry, they are relevant however because a digital image is stored as a Cartesian grid. Where each single pixel is a square of the grid. An image is made up of individual quantifiable pixels starting at the first pixel 1x1 and going to the last pixel which will be (img_width)x(img_height).

Now if we have a range of possible values and we want to map all of these possible values to a floating point range between 0 and 1, how can we do this? Well basically all we have to do is divide each value by the maximum of its possible range. I could talk about math all day, but let me just lay it out more formally:

If we define the pixels of an image as a set of ordered pairs (x,y) on a Cartesian grid, then we can define it's texture coordinates as the range of ordered pairs (U,V) such that U = x / (img_width) and V = y / (img_height).

So for an example, let's say that we have a texture that has a width of 700 pixels and a height of 512 pixels. Pixels are perfect squares, all the same size, so we've got 700x512 different pixels. And let's say we need to know what the (U,V) texture coordinate is at the pixel 310x400. We could therefore come up with the texture coordinate (0.44286, 0.78125).

U = 0.44286 = 310/700 , V = 0.78125 = 400/512.

I am going to attempt to make this tutorial equally valid for both OpenGL and DirectX. So far the above really applies to both. It is really only where the origin begins that they do not agree. I think it is important for people to realize there is not always a "best" way to do things and that not always everyone is going to agree. You are going to have to learn more than one system of doing things in lots of cases. In the case of texture coordinates, the big difference between OpenGL and DirectX is:

In OpenGL the origin of our texture coordinates is in the bottom left corner of the texture and in DirectX it is in the upper left. This means that our first coordinate will always be the same in both systems. We have to flip the second coordinate to convert between the two. This simple illustrations on this page demonstrate the differences. We can do this by subtracting the second coordinate by one.

DirectX to OpenGL --- (U,V) --> (U, 1-V)
OpenGL to DirectX --- (W,X) --> (W, 1-X)

DirectX (U,V)=(0.4, 0.75) --- 40% from left, 75% from top
OpenGL (U,V)=(0.4, 0.75) --- 40% from left, 75% from bottom

DirectX (U,V)=(0.4, 0.25) --- 40% from the left, 25% from top / 75% from bottom
OpenGL (U,V)=(0.4, 0.25) --- 40% from the left, 25% from bottom / 75% from top