Tag Archive: rendering

K-d Tree Build

The first version of K-d tree I wrote was a trivial median-split build, and it ran quite slow. Then I found out a technique called Surface Area Heuristic (SAH). Basically, the method works under the assumption that the time of intersecting a ray with a voxel is based on its surface area and the number of triangles inside that voxel. And to find the split plane, it will check all the bounding face of every triangles in the scene. A benefit to this approach is axis-align (or planar) triangles will be preferred, making the algorithm perfect for scene in which there are many flat, parallel surfaces.

So I spent most of my last 2 weeks reading and implementing that build. Although the build is now O(NlogN), the code is till very poorly optimized.

The code is made available at:

My implementation is based on this paper:
On building fast kd-Trees for Ray Tracing, and on doing that in O(NlogN)

The SAH is described by Vlastimir Havran in his dissertation which is considered a bible for K-d tree
Heuristic ray shooting algorithm

It took me almost 3 days to understand the method, because I’m rather new to this acceleration scheme. I think I will write down some of my thoughts on this wonderful paper when I have time.


Point light usually mimics the illuminance of light bulb in which light is emitted in all direction from source.
As the name suggests, Computer Graphics often treat the light source as a single point in space. And by this way, the shadow generated by point light is always hard-edged. But sometimes, we want point light to give soft-edge shadow like in Arealight. This article will explain a trick to implement a basic point light that gives soft-edge shadow.

Here is how the render process happens
1. Primary ray is shoot from camera through each pixel’s coordinate of the view plane.
2. The renderer compute the intersection point of the ray with objects in the scene and return a ShadeRec (shading record) in which the information of the hit point (location, normal, material pointer,…) is stored.
3. From the hit point, a shadow ray is shoot to each light in the scene to determine whether that point is in shadow. If not, compute the incoming radiance from that light and add it to the final color

Let’s start the implementation by first looking at the Point light in Maya
Maya's Pointlight
The most important attributes are intensity, color, and shadow. Every kind of light must have all these 3 attributes. Under shadow, look for “raytrace shadow”, expand it and you will notice 3 sub attributes, i.e. shadow radius, # shadow rays, and # shadow depth. In this tutorial, I will implement the most 2 important (according to me) attributes which are shadow radius and number of shadow rays. Shadow depth is less important and will be 1 by default.

First, we need to define the Light class:

class Light {	
		virtual Vector3D	get_direction(const ShadeRec& sr) = 0;				
		virtual RGBColor	L(const ShadeRec& sr);		
		virtual bool in_shadow (const Ray& ray, const ShadeRec& sr) const; //shadow test

		void set_num_shadow_rays (int num_sr);
		int get_num_shadow_rays () const;

		bool isArea;   // check if this light is arealight
		int num_shadow_rays; // number of shadow rays being sampled

And PointLight class, which is a sub class of Light

class PointLight : public Light
	void set_ls (float _ls);
	void set_shadow_radius (float _sr);
	virtual Vector3D get_direction (const ShadeRec& sr);
	virtual RGBColor L (const ShadeRec& sr);
	virtual bool in_shadow (const Ray& ray, const ShadeRec& sr) const;

	float ls,shadow_radius;
	RGBColor color;
	Vector3D source;

The most important method that contribute to the shadow generated by point light is get_direction ()

Vector3D PointLight::get_direction (const ShadeRec& sr) {
	return ((sr.hit_point - source).hat()); // normalize the vector

By default, this implementation will generate, hard-edge shadow. The reason for this is because the light source is fixed. To fix this, we just need to jitter the source’s location. The shadow_radius control the spreading of the penumbra and is the same as “light radius” attribute in Maya

Vector3D PointLight::get_direction (const ShadeRec& sr) {
	Point3D sample_source;

	sample_source.x = source.x + pow (-1,(float) (rand ()%2))*shadow_radius*rand_float ();
	sample_source.y = source.y + pow (-1,(float) (rand ()%2))*shadow_radius*rand_float ();
	sample_source.z = source.z + pow (-1,(float) (rand ()%2))*shadow_radius*rand_float ();
	Vector3D temp = sr.hit_point - sample_source;
	return (temp.hat());

Now, when you jitter the light source’s location, a point near the edge of the old shadow, may make it to the light without hitting any object, and therefore is not in shadow. This will give us the below image. Look at the edge, there are noises indicating that many shadow rays did not hit anything because of the variant light source. To eliminate the noise, we just need to increase the number of samples per pixel. The image below is rendered with 1024 samples per pixel

Pointlight 1024samples

By default, we use Monte Carlo integration to estimate the color at each pixel. This is done through sampling the rays and calculate the average color return by each ray. However, this may be costly to reduce noise to acceptable level. Instead of firing many rays at the beginning, we can also shoot ray at each hit point which result in same result but lesser computation since the ray shooting process is pushed inside the pixel loop. The “Shadow Rays” attribute in Maya does exactly the same function.

This image below is rendered with 16 pixel samples and 16 shadow rays.

16 pixel samples, 16 shadow rays