Daniel's Musings

A little “color spiral” I made for an art class:

It was generated by a little Java code… who needs image editors?

Just for fun, I made a completely monogreen template. You wouldn’t want to use this for a website with lots of reading! It displays correctly on all the browsers I’ve tried. Here’s a screenshot:

Binary: ijava.class (4k)
Source: ijava.java (2.5k)

This REPL evaluates Java expressions interactively, as illustrated:

C:\Users\daniel>ijava
>>> 2 + 3
5
>>> Math.cos(Math.PI)
-1.0
>>> Integer.MIN_VALUE * -1 // underflow
-2147483648
>>> new Integer(42).hashCode()
42
>>> System.getProperty("java.vm.name")
Java HotSpot(TM) Client VM

How does the shell work? It’s a bit of a hack, to say the least! Essentially, it

• reads an expression from standard input
• surrounds the expression with some template code
• writes the code to a temporary file
• runs javac on that file
• dynamically loads the class
• invokes a method in the new class using reflection
• prints the object returned by this method

David Wheeler’s sloccount tool is nice for counting lines of code in a project, but it won’t run on Windows. The option of running it through Cygwin didn’t appeal to me, so I wrote a similar tool in Java.

Binary: SLOC.class
Source: SLOC.java

Starting Java programs from a console can be a bit of an annoyance, so I use this in conjunction with a tiny DOS script:

@echo off
java -cp C:\Users\daniel\bin SLOC 2> NUL

Now I can count lines of code in my current directory just like this:

C:\Users\daniel>sloc
.hs: 10625 physical lines, 8822 nonblank
.cpp: 625 physical lines, 559 nonblank
[...]

(See: Nim.)

import java.util.*;
import static java.lang.System.*;

public class Nim {
	static int[] heaps = {3, 4, 5};
	static Scanner sc = new Scanner(in);
	static Random rnd = new Random();

	static void playerMove() {
		int h, n;
		do {
			out.print("Heap to remove from: "); h = sc.nextInt();
			out.print("Number of pieces to remove: "); n = sc.nextInt();
		} while (h < 0 || h >= 3 || n <= 0 || n > heaps[h]);
		heaps[h] -= n;
	}

	static void compMove() {
		int sum = heaps[0] ^ heaps[1] ^ heaps[2], heap = -1, amount = 0, i;
		for (i = 0; i < 3; ++i)
			if ((heaps[i] ^ sum) < heaps[i])
				amount = heaps[heap = i] - (heaps[i] ^ sum);
		while (heap == -1)
			if (heaps[i = rnd.nextInt(3)] > 0)
				amount = 1 + (heaps[heap = i] > 1? rnd.nextInt(heaps[heap = i] - 1) : 0);
		out.printf("Computer removes %d pieces from heap %d\n", amount, heap);
		heaps[heap] -= amount;
	}

	public static void main(String[] _) {
		boolean move;
		for (move = true; heaps[0] + heaps[1] + heaps[2] > 0; move = !move) {
			out.printf("heaps: %s\n", Arrays.toString(heaps));
			if (move) playerMove(); else compMove();
		}
		out.println(move? "You lost!" : "You won!");
	}
}

Download: hq9c.jar

Source: hq9c.java (depends on org.objectweb.asm)

Usage:

echo hq9hq > myProgram
java -jar hq9c.jar myProgram
java myProgram

Have fun!

After trying a few approaches, I came up with a method for rendering infinite terrain which I’m pretty satisfied with.

In a nutshell,

• I use the floating point variation of Perlin noise for the heightmap. Originally I had tried using a variation on the diamond-square algorithm which mapped any pair of integers to a height by viewing the bits of each integer as branches in a quadtree. The terrain looked great, but the speed just wasn’t there, unless I used a lot of smoothing to mask low underlying resolution.
• I precompute a large binary triangle tree at the start. All of the triangle coordinates are relative to the camera position, so I have enough information to do my LOD tests and remove triangles which lie beyond the far clipping plane upon initialization. Not having to deal with LOD at runtime is very helpful.
• I ended up using no caching at all. There are several reasons for this –
  • I wanted to be able to move the camera very rapidly, or teleport to a completely new location, with no performance degradation. If the heightmap only performed well after warming the cache, I would lose that flexibility.
  • A nice feature of floating point Perlin noise is that its precision is infinite (well, bounded only by the numerical precision of the floats). If you bring the camera very close to a feature of the terrain, you can see very precise curves. This is difficult
  • Besides, the noise function is fast enough that caching is not that  helpful. I tried adding a quick LRU cache implementation and was not that pleased by the speedup.

The major drawbacks are

• With no caching, it is difficult to apply even crude erosion algorithms without slowing down the program considerably.
• There is no opportunity to precompute the normals of the heightmap. They could be cached, but not with the infinite precision that runtime computation offers. Finding the normals at runtime can take a fair bit of CPU time, depending on the desired accuracy. I should probably use GLSL for this (but I want to rely on GPU performance as little as possible).

In summary, this approach is quite a bit slower than traditional texture-based heightmap rendering, but it is extremely flexible, and the performance is acceptable for most purposes.

A little animation I wrote a while ago, just for fun.

Download it here.

For the past few months I’ve been reading Physically Based Rendering, which describes a rather impressive ray tracer in just over a thousand pages. Could a tracer with comparable realism be described in 200 pages? That’s my hope. For now, here are some boxes and spheres.

For those renders, I combined a strong directional light with a weak ambient light. The radiometry isn’t accurate — I’ll get around to fixing it sooner or later — but I think the geometry is sound.