Post by chrisd on Jun 4, 2019 5:11:37 GMT
If you're anything like me (and I know I am), you may have gotten tired of waiting for your PPM files to be written and then opening them in an image viewer or editor. To alleviate this problem, I went ahead and modified my renderer to render directly to the screen. There's a certain satisfaction watching the pixels fill out in the image.
However, many images don't have interesting stuff at the top of the image. Waiting until the lines of pixels get down to the interesting part can be slow. It would be nice to fill in pixels throughout the image, giving a progressively complete view of the image.
Note: This article assumes you have modified your renderer to render to the screen.
When I originally thought of this idea, I envisioned a low resolution image progressively becoming more and more fine and detailed. I came to the conclusion that this would be somewhat difficult to do, and the mere act of drawing all those pixels to the canvas would add additional overhead. After some experimentation, I determined that just drawing individual pixels throughout the image would be good enough. The renderer just needs an algorithm to choose the pixel order.
Converting From Loops To Iteration/Stream
The first order of business was to extract the logic that chose the order of pixels to be drawn. The original logic looked something like this:
for (int y = 0; y < vsize; y++)
{
for (int x = 0; x < hsize; x++)
{
renderPixel(x, y, image);
}
}
Instead of calculating x and y pixel locations (or PixelCoordinates) in a loop, I put the logic for coming up with the list of PixelCoordinates into a stream of PixelCoordinates, with the requirement that all PixelCoordinates of the image have to be chosen, though in any order. Depending on the language you are using, that could be an Enumeration or Iterator or a Stream. I am using Java, and I chose a Spliterator which can be converted into a Stream, which supports a more functional programming approach.
boolean parallel = false;
AbstractSpliterator<PixelCoordinate> traversal = new AcrossDownTraversal(hsize, vsize);
StreamSupport.stream(traversal, parallel).forEach(pixel -> {
renderPixel(pixel, image);
});
Now all the logic for choosing the order of the pixels is in that AcrossDownTraversal object, which could be swapped out for some other implementation of AbstractSpliterator<PixelCoordinate>. This object keeps track internally of the current x and current y values of the last PixelCoordinate it returned, and just increments the current x, and if it exceeds the width then resets it and increments current y. At any given time, the set of PixelCoordinates remaining to be rendered can be inferred to be all PixelCoordinates with (x > current x and y = current y) or (y > current y).
One other benefit ... notice the parallel flag. Since we are using Streams, by turning this to true, the Stream can be made multi-threaded. If this is turned on, the renderPixel method better be thread safe.
Creating A New Traversal
The next step is creating a new AbstractSpliterator<PixelCoordinate> that chooses pixels from various parts of the canvas to get a more progressive effect. This Spliterator has to keep track of which PixelCoordinates are still left to be rendered. Before starting, all pixels in the canvas need to be rendered. When the first PixelCoordinate is chosen, the Spliterator needs to data structures to know which PixelCoordinates are left to be rendered.
The approach I came up with was to keep a list of areas that are left to be rendered. Remove an area from the list, choose a PixelCoordinate near the center of that area, and then create up to four more areas (or quadrants) and put those on the list before returning the center PixelCoordinate. The picture below shows the layout of the PixelCoordinate in the center plus the four quadrants.
Once an area is small enough that the center pixel is against one or more of the borders, some of the resulting areas might be of 0 width or height, and not needed. Of course, if the area is only 1 pixel large, then no additional areas will be added.
From an aesthetic perspective, the image should not descend down into details of one quadrant. For example, if after the first division into 4 quadrants, after then splitting the first quadrant, this Traversal should not descend down and continue processing pixels in the first quadrant until it's all done. Rather, it should process pixels in quadrants 2, 3, and 4. Therefore, it is best to keep a separate list of quadrants that are currently being worked on and a list of newly split quadrants. Once the list of currently worked on areas is empty, then it can be swapped with the newly split quadrants so it will be processed next.
Notice you want to be able to efficiently add and remove items to the list, which is especially important for larger resolution images. I'll leave that as an exercise to the reader.
This is a huge advantage over the AcrossDownTraversal, because you can see pixels through various parts of the image and get a better idea of what it will look like earlier. The disadvantages of this approach are that the pattern of the quadrants will be noticeable, and there is a slight performance decrease.
Tweaking The Quadrant Traversal
To avoid the visible pattern of the quadrants, you can get a more randomized appearance by doing some randomization. When swapping the list of newly split quadrants to the list of quadrants currently being worked on, you can randomize the list. In Java, you can use Collections.shuffle(list, random).
What does this all look like?
I generated these Animated GIFs directly from updates to my Canvas using an Animated GIF encoder. There is some banding and flashing in the images, which probably means I did not have the correct optimization flags turned on.
AcrossDownTraversal
QuadrantsTraversal
RandomQuadrantsTraversal