Height field compressor

What is it about?
Adaptive coverage of a height_field
Block coverage, export to POV-Ray
Download <----------------------- If you're in a hurry, it's there!
Documentation
Screenshot
History

What is it about ?

Creating grass covered areas in POV-Ray meets one major problem: memory footprint. It is quite usual to use millions of grass blades to cover a not-so-wide area. Till now, two solutions have been available, that minimize the problem:

using a grass-looking texture. One of the best work in this area is probably Rune Johannson's. Despite its Van Gogh look, it gives acceptable results for uniform, undulating areas, which do not exhibit important crests, as long as a close view is not needed.
using a grass patch which is duplicated to cover a plane. This is the principle used in a set of macros written by Gilles Tran, which uses the fact that copying a mash only needs a very small amount of memory in POV-Ray. It gives very good results on flat areas, but might lead to long parsing times.

Adaptive coverage of a height_field

The principle used in this software is to extend the principle of Gille Tran's macros, to cover any height field. The original method cannot be directly used, since a bumped area cannot be precisely covered with big, flat patches. The height_field is divided into a set of small square blocks, which can be approximated by a reduced subset of bumped blocks, simply by applying symmetries, rotations and vertical translations. This method falls in the category of the "dictionary" data compression algorithms, the most famous element of which is the Lempel-Ziv-Welch algorithm, once pattented by Unisys, but which is now public domain, putting an end to the kind of complete messes software pattents can lead to ;-)

This software takes as input a greyscale image, in PNG (highly recommended), GIF (if needed) or JPEG (to be avoided) formats, in 8-bit depth. It also accepts 16-bit images encoded using red and green.

Image dimension is practically limited to a bit less than 1024x1024. It is possible to use bigger images, but it can be necessary to increase the memory available to the Java virtual machine, for instance using java -Xmx256m -jar hfc.jar, which extends the default 64 MB to 256. However, do not forget that the aim is to place grass leaves, not to draw an accurate HF. If HFC seems not to do anything when loading an image, you should probably guess that the image is too big. First try using a smaller scale version, and only increase the available memory if you really need it.

Two parameters are necessary to build the dictionnary: block size, and the threshold under which two blocks will be considered similar. Generally speaking:

The bigger the blocks, the lower the compression ratio, as it is likely that it will be more difficult to assimilate two blocks. The same is true if the threshold is too small, except on very flat lands.
Small blocks will often lead to a reduced dictionary, but might exhibit repetitive patterns.
Too high a threshold might lead to underground or flying grass blades. A compromise should be found between dictionary shrinking and realism.

Practically, 8x8 pixels often lead to good looking results, combined with a threshold around one quarter the height of the blades.

The result of this first step is internal, and features a dictionnary of the blocks needed to rebuild the HF, and a conversion table giving, for each block of the HF, the corresponding block in the dictionary, and the transformations to be performed to convert between each other.

The software reports the nomber of blocks of the main "grid", the dictionary size, and the amount of blocks used only once in the building process: if this number is too high, it can be useful to increase the threshold.

Block coverage, POV-Ray export

The second phase consists in covering each block of the dictionary, and copying this block wherever it is needed.

Several algorithms are available, and new ones can easilly be added using Java programming. One system allows basic export using a pair of crossed triangles for each blade. A second system uses the same ideas as Gille Tran's makeblade macro. Both generate POV-Ray files using the mesh2 syntax, thus reducing the parsing time to a minimum: a cliff covered with 3 million basic blades will be parsed in 7 seconds.

An estimation of the output file size is provided before exporting

Download

For portability and development speed reasons, this software is written in Java. Computing time is usually reasonnable, a few minutes being a maximum. You will need a full Java VM (version 1.4), and Java3D extension (any version). If you still use windows, it is strongly recommended to upgrade to a working JVM, such as Sun's one.

This is free software, available under the terms of the GNU General Public License, version 2 or higher at your option.

It's here: hfc.jar. Download the archive (~75 k), do not uncompress it, and double-click on its icon or type java -jar hfc.jar to run the software.

The source files are also available for those interested: hfc_src.zip

Screenshot (French)

Don't worry: the screenshot is in French, but the default GUI is in English. A Japanese version should follow soon.

Scrinechotte [16k]

History (extremely short)

0.1.0-0.1.7: Initial versions, only announced and shared between French speaking users
0.1.8: Initial international release.
0.1.9: Minor bugfixes, Dutch translation (thanks Thomas!).