The Pixel Array
Along with drawing forms such as a
ellipse and so on in Processing, we can access each pixel in the sketch directly with
updatePixels. Each pixel is stored in a one-dimensional array of the
color data type; since a
color is actually a whole number, it is interchangeable with
Since our sketch is two dimensions while the pixel array is one dimension, we must convert from the coordinates (x, y) to an index,
i. In the code above we create a nested for-loop, where the outer loop goes through every row of pixels while the inner loop goes through every column. We increase the index
i for every iteration of the inner loop. This
i is also known as the stride of the array. There’s more than one way to convert from one- to two-dimensional space. For example, if the for-loop doesn’t update
i as above, we could say
If it is easier to use a single for-loop, we could figure out
y as we go.
If we wish, we can label for-loops. These labels can be used in conjunction with
All this clarifies the danger of an
ArrayIndexOutOfBoundsExceptionthat would bring our sketch to a halt. In the example above, 512 x 256 pixels = 131072 pixels. The index
i cannot equal -1 or less, nor can it equal 131072 or greater.
What would it mean to sort the colors we see on the screen, then? The first issue is one of naming and convention. When we speak of
pixels in everyday language, say “That dead pixel on my screen is so annoying”, we can mean the (x, y) coordinate, the color at that coordinate, or both.
A coordinate can be sorted by x major, y minor criteria — where (3, 10) precedes (5, 7) — by y major, x minor criteria — where (5, 7) precedes (3, 10) — or upon converting to a one-dimensional index — where 5 + 7 * 512 (3589) precedes 3 + 10 * 512 (5130). Keep in mind that this assumes a Cartesian coordinate system; we could also sort according to polar coordinates. Color may be sorted by red, green, blue and alpha channels; we could also sort by hue, saturation and brightness. (Though it’s a bit odd to say that an orange at 29 degrees hue is less than a magenta at 229 degrees.) That’s a total of 10 criteria… And the matter is complicated by the choice of ascending or descending order.
In this article, we’ll separate color and coordinate, then move from pixels in 2D space to vectors in 3D space. Let’s start with this example, in which we create and sort a color palette using Processing’s sort function. This code
will generate a sketch similar to
The top row of colors represent the randomized palette; the bottom row, the sorted. The console reports
This report offers a clue as to why
sort doesn’t work as expected. Processing packs channels of color into an integer using bitwise operations according to the pattern AARRGGBB. If we use
hex, we see the whole numbers created by these bitwise operations. Since -2074430010 is less than -1677522738, pale green precedes pale lavender.
To sort these colors by human sensibilities, we break each color down into its components, reversing the process initiated by the function
color. For this purpose, we can use the functions
blue. However, for the last four it is more efficient to use bitwise operations
float alpha = clr >> 24 & 0xff;,
float red = clr >> 16 & 0xff;,
float green = clr >> 8 & 0xff;,
float blue = clr & 0xff;. So how do we tell our sort function to take them into account?
A prior acquaintance with Object-Oriented Programming in Java, and with data structures (or, collections) greatly simplifies the task. By importing Java’s utility library at the top of our sketch,
import java.util.*;, we can access the sorting tools we need. We start by storing our colors not in an array, but in an array-list. A list can be a list of many kinds of objects, so we specify the kind we want between the angle brackets. Since a
color is an
int, we use the object equivalent,
Unlike the sort function, which makes a copy of the array, then uses
java.util.Arrays.sort and returns the copy,
Collections.sort sorts the input array in place. More importantly,
Collections.sort accepts another argument by which we can provide criteria for sorting. This argument must be a
Comparator of the same kind of data that is contained in the list (in our case, a comparator of integers). Suppose we wanted to sort by the redness of a color. We could create the following
Our sort needs assurance that the comparator it uses will behave as expected. For this reason, the class we’ve created
implements the interface
Comparator<Integer>, an interface being a contract which guarantees a behavior. Our sketch will not run until
RedSort upholds that guarantee by defining a function
compare. Within this function, we extract the red channel. If the red from color
a is greater than the red from
b, we return 1. If less than, -1. If the two are equal, 0. If we want descending order, we can set
false to flip the value. With this pattern in place, we can go down the line, implementing comparators for green, blue, etc. By revising the code above to
Collections.sort(palette, new RedSort());, we see results like so
This is okay, but not great. Pastel colors may contain a very high red value while never-the-less looking like a pale blue or green. What if we want to sort by multiple criteria, for example, by hue, then by saturation, then by brightness?
Collections.sort accepts only one extra argument, so we need to find a way to pack many comparators into one. A solution to this dilemma comes courtesy amon at Code Review Stack Exchange.
compare function loops through all of the comparators in its list, calling each of their
compare functions. The least desirable outcome of a sort function is to leave everything in place after every comparison returns 0. So as soon as a comparator in the list returns a value other than 0, then that is returned. The closer a comparator is to the start of the list, the higher in rank the criterion it represents will be, and the bigger impact it will make.
For now we are comparing colors, but in the future we’ll be comparing vectors and pixels. So, we keep our options open by using generics;
<? super T> mean that any class, or child of that parent class, can be used by our multi-sorter. Upon creation the constructor accepts a list of comparators. So as to not deal with all the angle brackets in our main sketch, we can make a child of the
MultiSort class using the keyword
In addition to concealing the generics, this also lets us create a default sort priority. All we need to specify is whether we want to use ascending (
true) or descending (
false) order. Since there are two color modes,
ColorSort constructor checks to see which mode is active (as stored in a
PGraphics object called
g) and creates the appropriate sorting objects: ARGB order for RGB mode, AHSB for HSB mode. To better see the visual impact of ordering sort criteria, let’s fill a sketch with random colors.
At first, our sketch looks like this
but on mouse click, depending on sort criteria and their order, we come up with the following
Above are colors sorted by Brightness-Saturation-Hue, Hue-Saturation-Brightness and Red-Green-Blue. With this infrastructure in place, we can move on to the pixel.
With color, we worked with a data type designed by others, but with pixels, we have an opportunity to create our own. In many respects, a pixel coordinate is similar to a
PVector, except that it uses
int rather than
float components. We can therefore use
PVector as a reference when deciding which behaviors to create (
sub, etc.). There is one quality in which a pixel differs, though: a vector can exist outside the screen, waiting to come into view of the camera; a pixel coordinate’s existence is confined to the sketch dimensions. What happens if a pixel goes beyond the left, right, top or bottom edge? In the design to follow we clamp the coordinates to the ranges 0 .. w, and 0 .. h.
hashCode are three functions easily overlooked, but when defining objects to be stored in collections, a lot of headaches can be avoided by taking care of these. Of interest at the moment is
set, which uses ternary operators to check whether the supplied (x, y) coordinates are in-bounds, then assigns an index. We can now author any number of functions which arrange pixels into a form, such as Bresenham’s line algorithm, the midpoint circle algorithm, bezierPoint, or the filled circle function below.
A key difference between the pixel array and collections of pixels generated by the above is that a pixel’s (x, y) coordinate no longer necessarily corresponds to its place in line, and hence, its draw order. Depending on the algorithm, a pixel at (256, 128) could precede a pixel at (32, 64) in the list
out. We can see the difference order makes by invoking shuffle:
When each pixel is moved to the right at a speed dependent on its place in the list, we see we see orderly stripes with the circle as created; when shuffled, we see a cloud of points.
While we can and will create comparators, we have another option: to implement an interface called
Comparable in the
Pixel class, which will mandate that we define the function
compareTo. We thus have a default sort should we not want to create a comparator.
Writing comparators for x and y is fairly straightforward. To facilitate radial comparison, we add a distance squared function to our pixel class. (We could create a
dist function as well, but we avoid calculating square roots when we don’t have to.)
Since pixels 10 units above, below, to the left and right of a center pixel would all evaluate to 0 in this radial comparison, as a backup we sort by a pixel’s index. If we modify the main sketch from earlier
we see results like
We may also find it advantageous in some cases for each pixel, in distinguishing itself from a coordinate, to store a color. As an example of patterns we create with color and pixel separated, we use a Brightness-Hue-Saturation comparator.
A Note In Passing On Pixel Sort & Glitch Aesthetic
Sorting pixels of a source image has gained popularity as one of the techniques used to simulate corruption, noise, malfunction, etc. of an image. To illustrate, below are some manipulations of Vermeer’s View of Delft which might pass for ‘glitch’ aesthetic. We won’t be addressing the topic in this article, but offer some preliminary thoughts below.
Up to this point, we’ve risked conflating comparison with sorting; to be more precise, a sort could be broken into smaller tasks, of which comparison is but one. Since we’ve delegated the task of sorting to Java’s utility library, we don’t have control over those steps.
Collections.sort performs a merge sort in one frame, without allowing us to observe or creatively intervene in the process. Custom implementations of each step would allow for that control. A swap is fairly straightforward (
Collections.swap is available should we want it), and we’ve already coded comparisons above; the last, and most important, would be the kind of sort we want to use.
Many sorting algorithms exist, and VisuAlgo is a great resource to better understand them by witnessing them in action. Although algorithmic efficiency may seem abstruse at first, especially since it is discussed in terms of Big-O notation, it is worth taking into account when choosing a sort for the
draw loop, where frame rate and speed of the animation are a concern.
The hazard if one is looking to recreate an aesthetic effect — whether it be smearing pixels or chromatic aberration — is that not all sorts yield interesting results, some effects are accomplished without sorting, and other effects require pixel sort in concert with other techniques of image processing and procedural generation. There are several practitioners and theorists worth looking into for those inclined to research the topic further, among them Rosa Menkman, Paul Hertz, Kim Asendorf, Evan Meaney, and Nick Briz.
Given what we’ve done before, comparing
PVectors in a collection is straightforward. We can define 3 comparators for the x, y and z components.
PVector doesn’t implement
Comparable, so there’s no default sort order. With comparators written, we can see how they operate in a sketch such as the following
For convenience, the lines connecting each randomly generated vertex are color coded by hue; the nodes are represented by boxes, which convert their spatial position to an RGB color. On mouse press, a radial sort, which depends on
dist function, provides effects similar to what we observed earlier in 2D.
For an example application of this, imagine we are preparing a 3D scene for export to a .pdf using the PDF library. In most cases — since a model generated by
loadShape is a group of faces— we find better performance in working the shape returned by
getTessellation, as we detailed here. However, a .pdf generated by Processing’s library does not account for the light in the scene. Nor does it support texture mapping. We therefore find advantage in the ability to recolor faces individually. We can then simulate naturalistic lighting, using
lerpColor or a multi-stop gradient, as covered in a prior tutorial.
There is an issue with the parent shape, however. Since a .pdf must convert a continuous z dimension in 3D space to a stack of discrete layers in 2D space, faces further away from the camera should be drawn before faces closer to the camera, and so fall on the bottom of the stack. If our camera is fixed and similar to the default camera, we can assume that lower z values are further away; if our camera is mobile, it would be better to do a radial comparison from the camera’s position, and to sort faces before we begin recording. Without sorting, the parent
PShape’s ordering produces a chaotic look. We use a bust of a bearded man to illustrate.
So how do we sort a face? Since a face may consist of 3+ vertices, we could sum these
PVectors and take the average.
We can then move on to the main sketch.
If we wanted to minimize concealed faces without delving into the OpenGL behind the 3D renderer, a hack for back-face culling would be to create a threshold for beginning the faces for-loop