Month: November 2006

One Comment

Color blasting

  By code

The last 3 days (nights…), I played with octree color quantization. It’s another use of hierarchical data structure for computer graphics.

We first contruct the octree (a tree where each node as at most 8 children) by inserting each image color in it. Let’s assume that the color is encoded in 24 bits (8bits per component). The octree has then 8 levels. So, we first take the
most significant bit of each component and merge them to obtain the child index.

shift = 7 - level;
child = (((red >> shift) <<  2) & 0x04) | (((green >> shift) <<  1) & 0x02) | ((blue >> shift) & 1);

A leaf is contructed when we reach the first bit. The current color is added to the leaf color and a reference counter is incremented (it’s basically counting the color occurence in the image).

Then the leaves are successively merged until we reach the desire color count.

node = node to be merged
for(i=0; i<8; ++i) {
    if(node->child[i]) {
        node->rgb += node->child[i]->rgb;
        node->reference += node->child[i]->reference;
        delete(node->child[i]);
    }
}

The original paper stated that the nodes with the least number of pixels (the lowest reference count) must be merged first. Actually, I’m keeping an array containing the node list (newly created node is inserted at the head) for each level. Then i backward traverse this tree from the bitCount-1 (here 7th, as the 8th entry contains the leaves list) and merge each node in the list until i reach the desired color count. This is clearly unoptimal.
Thereafter, the palette entries are built by taking each leaf color and dividing it by its reference count. The indexed image is then built by taking each color and traverse the octree. The index of the pixel color is the one of the leaf color we reach.

Here’re some results! The following table show the quantization of a 24bpp rgb color wheel.

RGB Color Wheel
RGB Color Wheel (256 colors) RGB Color Wheel (128 colors)
256 128
RGB Color Wheel (32 colors) RGB Color Wheel (16 colors)
32 16

The artifact generated by the current merge criteria (merge the last created node for the current level) is clearly visible. I should make some kind of priority queue and then merge the node with the lowest priority (this reminds me the ROAM algorithm for terrain rendering).The following image is a sample of a Sorcerian wallpaper reduced to 16 colors. Here the lazy merge criteria flattens the colors.
Piece of sorcerian wallpaper in 16 colors

Here’s the same image reduced to 16 colors using GIMP (without dithering). It seems that GIMP uses the median cut method.
Sorcerian wallpaper 16 colors (gimp)
I will fix the merge criteria right now. I think i’ll implement color quantization using Kohonen neural networks first.
Meanwhile, here’s the source code.

No comments

Plückermeister

  By code, crbn

I replaced the Möller ray/triangle intersection test by the one using Plücker coordinates. It’s faster and more robust. The results is looking better (smoother normals). But, the holes didn’t disapear. After some investigations, i discovered that the problem came from point normals (I’m using them as point color). I read the objects from ply2 files which only store points and polygon indexes. Here’s how i’m computing point normals:

v is the mesh vertex list
n is the mest point normal list
foreach triangle t
    t.n = normalize(cross(v[t.p1]-v[t.po],v[t.p2]-v[t.po]))
    n[t.p0] += t.n
    n[t.p1] += t.n
    n[t.p2] += t.n
normalize each n

There’s a huge problem here. We are assuming that each polygon (triangle in this case) are ordered so that its normal is pointing away from the object. Unfortunately, this isn’t guaranteed by ply2 format. The following figure illustrates this.

Mesh normal problem

Imagine if t0 and t1 are coplanar. If we are in the worst case, the normals of t0 and t1 are pointing in the opposite directions. As the normal at p is the sum of those two normals, it’ll be equal to the null vector. That explains the black holes. But that’s not all… The normal at the intersection point between the ray and the triangle is interpolated from the point normals of the triangle using barycentric coordinates. One of these 3 normals may be wrong or/and, like the figure, they may be pointing in opposite directions… Arg!

There’s no exact way to determine if a polygon normal is pointing away from the surface. So, unless the file format provides polygon (or in the best case) points normals, i’ll not interpolate point normals.

No comments

Enter the dragon

  By code, crbn

I backported the BVH i wrote for CRBN to the little and ugly raytracer test. Even if it’s not the most efficient space partioning method for raytracing, the improvment is quite impressive.

Here’re some results with the Maneki Neko model rendered on a Athlon XP 1.4GHz with 1GB of RAM. The model contains 62385 points and 124677 triangles. The code was compiled only with the -O flag and the target image was 256×256.

BVH:
  • real 0m8.325s
  • user 0m6.461s
  • sys 0m1.505s
  • 174 MB
Without:
  • real 25m57.370s
  • user 24m25.249s
  • sys 0m5.714s
  • 52MB

Nice heh? So i decided to render something a little bit bigger. I chose the dragon hi-res model. It contains 437645 vertices and 871414 triangles. I haven’t tried rendering it without BVH. The 512×512 image took 2minutes to render. Unfortunately, i still have some floating point issues. You can notice holes here and there… I’ll made some tests using Plüecker coordinates as it’s supposed to be more robust.
Dragon (small)