Sky Improvements

I’ve been meaning to improve the sky rendering in Chunky for a long time, and finally I have started to work on this project. I had first just planned on adding support for sky maps with full 180° vertical resolution, as opposed to the current 90° sky maps:

Skymap Resolution

The increased vertical resolution means that the entire sky can be textured, without mirroring the sky map at the horizon. Most scenes do need to render the sky below the horizon specifically, however it is not uncommon some part of the render shows a bit of sky mirroring happening:

Distracting sky mirroring at horizon.

The mirroring is quite distracting, and detracts from the overall quality of the render. I think supporting full 360 by 180 degree sky maps is an important improvement.

While I was adding support for more sky maps I thought it would be cool if you could use spherical sky maps, or skyboxes as well. So, skyboxes and spherical sky maps can now also be used in Chunky. Spherical sky maps are pretty cool, because it’s quite easy to make one yourself, just take a picture of a shiny metal sphere and you have a ghetto spherical sky map.

We used spherical sky maps, or light probes as they are called if they use a high dynamic range format, in the rendering course I took last semester. I thought that it would be a shame if I did not add support for HDR formats as well, so I did. Now images using the PFM or RGBE (.hdr) formats can be loaded by Chunky. This means that Chunky is now capable of image-based lighting. Image-based lighting really gives renders a much more realistic appearance. I found several free HDR sky maps online, so I’ve been testing some out for rendering:

Desert Vista

While studying the RGBE HDR image format, I also read a bit about the RADIANCE rendering system and through some links I arrived at Mark Stock’s RADIANCE page and saw that he had also implemented the Preetham et. al. sky model. I was not really satisfied with my own implementation, the one used in Chunky for the default sky, because the sky appeared too pink. My results differed slightly from the images in the paper by Preetham et. al., A Practical Analytic Model for Daylight. When I saw Mark Stock’s results, they seemed much closer to the results in the original paper, so I decided to investigate why. He provides the sources for his implementation on his website. After comparing the implementations for a while I finally arrived at what I believe is the only functional difference: he uses a different matrix to transform from the XYZ color space to RGB! I switched to using the same transformation matrix and voila! The sky looks much better, in my opinion! Here is a comparison video I made (original on the left, corrected version on the right):

Sky Color Variations from Jesper Öqvist on Vimeo.

Color Picker

This post is a bit of a rant about the current state of color pickers in different applications. It also talks a bit about a color picker I created myself, and how I decided to make it different from most other color pickers.

The Terrible JColorChooser

The default color picker interface in the Java Swing API is terrible. I have been using it in Chunky because there was really no simple alternative. Here is a screenshot of the Swing color picker:

Swing JColorChooser

Out of the three tabs in the dialog, the first one is the second least useful. I won’t even show the unspeakably bad third one. I hate the above tab because the color swatches in the palette are too small – it would have been better if that palette was just a continuous gradient of colors. I also hate that the palette has a grid in it with some kind of bevel effect – if there is some grid between the colors in a palette it should just be one solid achromatic color. With the current small color swatches the grid muddies up the perception of the individual colors. It’s a real shame that the above tab is the default one, it makes the JColorChooser much shittier than it would have been if the second one was the default tab.

So, let’s look at the second tab:

Swing JColorChooser

This second tab is better, but still bad. Here are a few problems I have with it:

  • I can not click on the hue bar. To change hue I have to either use that stupid little text field or the shitty slider that is clipped for some reason. Oddly, though, the nice big color palette to the left of the hue slider does not update while dragging the slider – only after you let go of the slider thumb. That makes it very annoying to try to find the correct slider position, it would have been so much better if the color palette updated ASAP while tweaking the hue value.
  • The RGB display. I do not care what the RGB values for the current color are! Give me the hexadecimal number for the color instead!
  • The HSL text fields are pointless. I can not think of any situation where I’d want to input a color by hue, saturation, and lightness unless I want to copy a color from another application, in which case a hexadecimal input would have been much superior. What matters here are the colors, not the numbers.
  • The color preview area at the bottom is too cluttered with stuff. It should have just been one solid swatch of color. The idea of displaying the color side-by-side with black and white for comparing brightness is good, but here it just went overboard.

The Problem

I’ve been looking at other color pickers in different applications and most of the ones I’ve seen so far are awful. The main problem is usually that the interface is very fiddly, due to too small sliders or sliders that are otherwise difficult to adjust. There seems to be some weird idea that the components in a color picker should be small and compact, but the smaller they are the worse they are to use. As a user I want big palettes that can display a color gradient over a large area so I can get a better idea of the different nuances at a glance.

Another common problem is that color pickers lack a good color preview. The preview should be one large swatch of the color, uninterrupted by other crap.

The Fix

After being irritated that I had to use JColorChooser for far too long I finally decided I would invest the effort required to rid myself of JColorChooser for good. This is what I created:

color_picker

The interface is really simple, and it has only the features that I needed, but I think it is superior to most other color choosers I have tried. What makes it so good?

  1. The sliders are nice and large, and you can click anywhere in the sliders and the thumb jumps directly there. The saturation and lightness sliders update directly whenever any one of the other sliders is changed.
  2. The preview swatch is huge. It shows the current color in all its glory.
  3. There are some smaller swatches with previously selected colors, and a series of colors generated pseudo-randomly from the current color. These give some interesting alternative colors. Again, these swatches are much larger than they would be in other color pickers.
  4. Click the big swatch when you are satisfied to close the dialog. If the dialog loses focus it is closed automatically. These are nice features which make the “Cancel” and “Done” buttons obsolete, however the buttons are still there in case you forget.

Entities

I’ve started working on entity support for Chunky. This means that Chunky will be able to render a number of different things that it can currently not render because they did not fit inside a single voxel (a single block in the Minecraft world).

From the beginning Chunky would only render perfectly cuboid objects such as stone blocks, grass blocks etc. After a while I started adding support for non-cuboid things such as fence posts, stairs, torches, etc.

Fence and stair blocks

Most non-cuboid blocks still fit inside a voxel, like the stairs and fence in the above image, so I reused the same representation for both voxel-filling cuboid blocks and non-filling blocks. Without going into too much detail, this meant that although I could render things with more interesting shapes than pure cubes, they could not extend outsize a 1x1x1 meter area. This is a problem for things such as paintings, cows, player models, beacon effects, and a bunch of other miscellaneous blocks or effects that are currently not be rendered by Chunky.

Gallery

The above image was rendered using the current partial entity support I’ve been working on. Entities support is exciting because it allows rendering a lot of things that could not previously be rendered properly! Only paintings are fully handled right now, and there’s a bit more to do before this is ready for release. I hope to release it soon.

Improving the Chunky 2D map

The past couple of days I have been polishing the 2D map rendering in Chunky. The 2D map is a feature that has been mostly neglected since I started working on the 3D rendering.

Originally Chunky was only a 2D mapping program. I created Chunky to explore my own small Minecraft worlds and look for hidden treasures near my mineshafts. The default rendering mode was the “layer” mode, in which a single layer of blocks is rendered top-down. In order to allow quickly switching between layers I designed Chunky store most of the loaded chunk data and only throw it away when out of memory. This was done to avoid reading from the hard disk whenever a new layer was loaded.

The original layer mode

The original layer mode

Nowadays Chunky is used quite differently and the requirements for the 2D map have changed. The 2D map is now mostly a tool for selecting chunks to be rendered in 3D. This means that the layer mode is seldom used — the default “surface” mode is mainly used for chunk selection. In addition much larger views have to be rendered by the 2D map because when selecting a portion of the map to render you usually want a good overview of the entire area to be rendered.

Rendering a Minecraft map covering a large area is a significant challenge, especially for interactive applications. The number of chunks that need to be loaded is immense. If the map is zoomed out as far as possible (equivalent to one chunk per pixel) Chunky, at the default window size, will display about half a million chunks. Simply loading all those chunks takes significant time even if you are loading from a fast SSD drive. The memory requirements for storing the map are also massive. Just storing color values for each block in such a map would require 480 megabytes. There are additional overheads which bring it up to about one gigabyte of data stored for just the 2D map.

The red square is 32x32 chunks (each chunk is 16x16 Minecraft blocks)

The red square is 32×32 chunks (each chunk is 16×16 Minecraft blocks)

One thing I did to improve the efficiency of the 2D map was to remove caching of chunk data. The chunk data includes information about each block in a chunk, biome metadata, block metadata etc. The memory required for the complete chunk data set is much larger than just the 2D map rendering. Removing this caching may lead to many extra disk reads when creating a 3D scene, but it noticeably improved the loading speed for the 2D map.

I also removed pre-rendering of background maps such as the layer map, biome map (seen above), or cave map. Only the currently viewed map is stored by Chunky. This means that chunks need to be re-loaded if the map mode is changed, however this happens so seldom that the memory savings are likely worth more than the extra cost of switching to another map mode.

Surface map mode

Surface map mode

In addition to removing the caching of chunk data and background maps, I improved the way the map is updated. The 2D map is interactive, meaning that it is redrawn whenever a chunk is loaded for the first time or whenever a chunk is re-loaded because someone changed it on disk. It used to be that most of the map was redrawn if something changed but now it is supposed to redraw only the region or chunk that was updated, depending on the zoom level. To test the smarter redrawing I made the map renderer highlight each pixel that is drawn with a color indicating in which rendering pass it was drawn. It looked kinda funky:

Each chunk is colored based on when it was last redrawn

Each chunk is colored based on when it was last redrawn

During this process I was able to fix some tearing issues that were caused by bugs in the previous map redrawing code.

Another not so noticeable but important feature of the 2D map is that it loads some chunks outside of the current map view, this gives a margin of already-loaded chunks around the current view which makes panning behave a lot smoother than it otherwise would.

The 2D map should be more responsive in the next release. I have implemented several smaller usability improvements in addition to the above performance improvements.

Future Work

There are still improvements that could be made to the 2D map to make it even more responsive. These have not been implemented yet, but I might return to it in the future and add some of these features:

  • Cache each region at max zoom level on disk
  • Don’t load heightmap data at max zoom level
  • Use bloom filters instead of chunk sets
  • Fine tune surface rendering mode

Stochastic Progressive Photon Mapping

The last assignment in the rendering course was to create your own scene and implement some rendering technique not covered by the previous assignments. I chose to implement depth of field because it was the simplest thing I could think of doing. My scene was a pile of LEGO bricks in different colors. In order to make the depth of field work well with my photon mapper I also implemented stochastic progressive photon mapping:

LEGO

Since the stochastic variant of my renderer re-runs the eye pass for each photon pass I implemented a more efficient BVH construction algorithm using Morton codes. The BVH construction time was reduced by an order of magnitude with the more efficient implementation!

How Not to Sort

The common sorting algorithms which you may find implemented in many programming languages standard libraries usually require a comparator function to order the elements being sorted. A comparator function is a function taking two objects of the same kind and returning a signed integer indicating their ordering. If the returned integer is zero then both elements are equal, otherwise the sign indicates which is greater than (ordered after) the other.

For example, to sort integers in increasing order we can use this comparator:

/**
 * Return negative if a < b, positive if a > b, zero if a = b.
 */
int compare(int a, int b) {
    if (a<b) return -1;
    if (a>b) return 1;
    return 0;
}

If you’ve ever implemented a comparator function where the actual comparison of the objects used integer values you may have made this premature optimization:

int compare(int a, int b) {
    return a - b;
}

As with many things, the devil is in the details. The assumption is that a minus b is less than zero if a is less than b, greater than zero if a is greater than b, and equal to zero if a and b are equal. The math checks out on paper, however if we take integer overflow into account we get a different story. If a is a large positive number and b is a large negative number then the subtraction could very well overflow, and despite a being much larger than b, the return value would indicate the opposite.

The optimization works only if there are limitations on the possible input values. If the inputs can only be positive then the subtraction will never overflow. However, this is an easily forgotten constraint. Even if the inputs were initially only positive there is usually no guarantee that it will remain true as the code evolves.

I searched the web a bit to see if I could find examples of this error, and I found some instructional articles on the topic of sorting, that use the above hack, where the input values are implicitly assumed to be positive:

None of the above articles have any discussion about the limitation of valid input values, and although the input values may be assumed to always be positive there is no explicit mention of this. It’s like a perfect pitfall to stumble into. You learn a neat way to compare positive values without necessarily learning the important constraint that they must be positive, then later you end up using the hack incorrectly where the inputs may be negative.

Comparing without branching (in Java)

The lesson of this article should really be not to use hacks. If you do, make double sure they work as intended. Below is another hack, which I have made sure works for my inputs. Please don’t use it without making sure that it works for you. It may very well not work as intended!

I wanted to see if I could remove the conditional statements and compare two signed 32-bit integers using only arithmetic and bit twiddling. This is what I ended up with:

int compareHack(int a, int b) {
    long p = (long)a.value-b.value;
    return (int) ((p>>1) | (p&0x7FFFFFFF));
}

The above method works in Java but is not guaranteed to work in other languages. Use it at your own risk!!

The subtraction is done with 64-bit values to avoid overflow. If and only if the result is negative then the high 32 bits in p are all ones. If the 32nd bit (highest of the low 32) is set then it may be a value bit from the subtraction result. Shifting p right moves the highest value bit out of the sign position, then the bitwise OR makes sure that we set at least one value bit if the result was positive and nonzero. The shift also ensures that the sign bit is set only if the result was negative.