Tag: crbn

Last day i was reading the wikipedia article about the Pioneer program. I don’t know how, but after following some links i ended on the Hayabusa mission article.
The Hayabusa space probe was launch in 2003 to study the Itokawa asteroid. The most ambitious part of the mission was about landing on the astoreid to collect samples. From what i understood, the samples would not have been collected by drilling the asteroid but from the debris made by the collision between the asteroid and a projectile launched from the space probe. Unfortunately, the attempts to land on the asteroid failed. Nevertheless, it seems that the Hayabusa managed to collect some samples.
The Hayabusa may be bak to earth around 2010.

Using the data collected, Robert Gaskell from the Planetary Science Institute generated 3D models of the Itokawa asteroid. The model is available in 3 formats (plate-vertex table, STL ASCII and triangle) and in 4 resolutions (from 49,152 to 3,145,728 triangles).
The plate-vertex table format is similar to ply2 format. So, i took the 3M triangles version. Translated it into ply2 and launched my crappy raytracer on it.
I was surprised by the rendering speed. A 256×256 image was rendered in less than 1 minute. Nevertheless, i had a nasty bug 🙁

As you may have noticed there’s a bug on the left part. Here’s a close up.

buggy	correct

The “correct” image was obtained after 3 hours of computation by disabling BVH. So the problem came from the BVH code. After almost rewriting the BVH building and intersection code, i still had the same bug. Some heavy code review later, i realized that the wrong ray intersection was returned. In fact it was the informations of the last intersection instead of the one from the closest intersection point. It’s a very stupid bug. Well at least i cleaned up the BVH code.
So for your pleasure here is a nice 512×512 image of the Itokawa asteroid.

And some stats:

• BVH building time : 0h 0min 38.943722 sec
• Rendering time : 0h 0min 7.411200 sec

As i said before, the code is greatly unoptimized but it manages to render a 3M triangles model in less than one minute. I’ll try to speed up the BVH building code, use a clever cost function and monitor memory usage (while running the top command, i noticed that more than 70% of the RAM (1go) was used.)

Bonus : dark side of the patatoid!

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.

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.

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.

I decided to render a larger model. So i took the happy buddah model from stanford repository. It contains 543652 points and 1087716 triangles. Rendering a 256×256 image took approximatively 2 hours. I really need surface partitioning.

The white dots on the picture represent the ray where a floating point error occured. As the mesh has really small triangles and low coordinates points, i had to replace the zero divider test using boundaries by the standard not equal to zero test. I really hate this floating point issues…

I quickly wrote some basic polygonal mesh raytracer in order to test some space partitioning algorithm like KD-trees or BIH. I’m actually using the maneki neko from this repository. It’s not really big compared to stanford bunny or happy buddha. As i don’t need any lighting, i decided to use point normal as color. Here’s the result :

It took 25 minutes to render this image on my amd64 3500+. The model contains 62385 points and 124677 triangles. Not that much… But it’s brute force raytracing for the moment.
I also discovered that XYZ-RGB is offering free texture materials. Maybe i should use them for the displacement map.

On the 8bit side, the pcengine tracker is going well. The instrument routines may be finished next week. Next step is note/pattern handling.