# Writing my own pathtracer on mobile device

This topic is 1070 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello forum and graphic geeks  ,

i just registered myself on this wonderful site where kind of everything is posted i am interested in (games, graphics, programming). So the christmas holidays are imminent and i am currently searching for some programming stuff i could learn in the free days off from work.

Because i am really into android programming currently and i also really love the idea of pathtracing (i did a lot of CGI with Blender and LuxRender) i thought about writing a simple pathtracer for mobile devices (it don't have to be fast! )

Sadly i am a complete math idiot. Some months ago i started the first project "Try to write a pathtracer". After reading documents for hours and trying to understand the math calculations behind the letters i gave up. So in the next weeks i hope i have enough endurance to go through this second try and finally understand it (maybe it helps me in the future).

Currently i am working with Android Studio and a Galaxy Note 2 with Android 4.4.3 (Cyanogenmod).

There will probably be a lot of questions and i hope you will answer them

So here are some points i already understood of programming a pathtracer:

1. I need an abstract class from which the basic objects inherit (such as a Sphere and a Plane). Every object has its own definitions (radius, center point, etc.) and its own "checkIntersect" function

2. I need different classes, such as a Vector3D and a Ray (which has a origion Vector3D and a direction Vector3D)

3. Then i have to loop through the pixels of the image and generate a ray. Now i will loop through all basic objects and check if the ray intersects with one of these objects

4. if an object is in front of the intersected one (no idea how i could check this?) i skip this ray

5. if the ray hits the object i have to calculate the reflection and the resulting color depending on the object color (i will start with just a diffuse material). From that i have to calculate a second reflection ray which will also travel through the scene (sadly no idea how to calculate that second ray

6. If a given MAX_BOUNCE is reached, the ray disappears

These are the rough points i have in my mind for the topic "pathtracing".

So any tips you may have for me? I really appreciate all your answers

I will try to keep the latest progress updated.

Edited by IsItSharp

##### Share on other sites

Hi  Vilem Otte,

thank you very much for your detailed answer. Because everyone on the internet is talking about, how easy it is to write a pathtracer (climax is a pathtracer in 99 lines of C and i don't understand a single line of code) i first thought: well, it can't be that hard, even for me. But sadly, it is kind of complicated.

To the data storage topic:

do i really need a KD-Tree if i only use primitives such as spheres and planes?

Edited by IsItSharp

##### Share on other sites

do i really need a KD-Tree if i only use primitives such as spheres and planes?

If you only have a few, no. You can start out with a test scene of 5-6 spheres and won't need any special data structure to store the spheres. Once you get over a few hundred spheres (or triangles) though you quickly begin to realize how important it is for larger scenes!

##### Share on other sites

The key to usually anything is understanding the basics, without the basic mathematical knowledge and understanding behind path-tracing you are doomed to blind cut-paste/copy-paste  -> find tutorial/sample code and then back to copy and pasting again. All too often the same phrase have been mentioned, I want to do X but I do not comprehend the theory/principles underlying X. Then how are you going to implement something you don't understand, and what are you going to do when you run into issues during implementation. My advice, spend the time up front to understand the basics behind path-tracing, math and all and you will find that this will go a long way when you decide to start your implementation.

##### Share on other sites

[background=#fafbfc]I want to do X but I do not comprehend the theory/principles underlying X.[/size][/background]

Yes, that's the problem

[background=#fafbfc]Then how are you going to implement something you don't understand, and what are you going to do when you run into issues during implementation.[/size][/background]

As i wrote at my first post, i hoped you guys could help me out with some things?

[background=#fafbfc]My advice, spend the time up front to understand the basics behind path-tracing, math and all[/size][/background]

The best method to learn something is if you practice it a lot (e.g. writing a pathtracer). "Learning by doing"

So here comes my first understanding problem:

Based on this letter: http://www.csee.umbc.edu/~olano/435f02/ray-sphere i tried to calculate the intersection for the sphere.

So far tried to calculate a, b, c and the discriminant. As it says in the text:

if the discriminant is below zero, there is not intersection. If it is 0, there is one intersection. If it is 1 there are two intersection (entry and exit).

So do i have to calculate the length of the resulting discriminant vector (and then check the stuff) or should i check if the coordinates of the vector are below zero?

My code looks like this so far (based on
b2 - 4 a c
a = d * d
b = 2 d * (p0 - pc)
c = (p0 - pc) * (p0 - pc) - r2):
        public override float Intersect(Ray ray)
{
Vector3D a = ray.direction.multiply(ray.direction);
Vector3D twoDirection = ray.direction.multiply(new Vector3D { x = 2, y = 2, z = 2 });
Vector3D b = twoDirection.multiply(ray.origin.subtract(this.center));
Vector3D c = (ray.origin.subtract(this.center)).multiply(ray.origin.subtract(this.center)).subtract(
);
Vector3D discriminant = b.multiply(b).subtract(new Vector3D(4,4,4).multiply(a).multiply(c));

}

Edit:

Okay, i got it

Is this correct?

        public override float Intersect(Ray ray)
{
float a = ray.direction.Dotproduct(ray.direction);
float b = 2.0f * ray.direction.Dotproduct(ray.origin.subtract(this.center));

float discriminant = (b * b) - (4.0f * a * c);

if (discriminant < 0) //no hit
return -1.0f;
else if (discriminant == 0) //one hit
return (-b + (float)Math.Sqrt(discriminant)) / 2.0f * a;
else
{
float t1 = (-b - (float)Math.Sqrt(discriminant)) / 2.0f * a;
float t2 = (-b + (float)Math.Sqrt(discriminant)) / 2.0f * a;

return Math.Min(t1, t2); //get the smallest value
}
}

Edited by IsItSharp

##### Share on other sites

So any tips here?

##### Share on other sites

No one here who wants to check the last function?

##### Share on other sites
Probably you want to completely exclude results less than zero (i.e. if t1 is less than 0, return t2, and vice versa, and if they are both positive then return the smallest one). That will also handle cases where your ray starts inside the sphere, as well. Otherwise I haven't checked but the equation looks correct, it's just a standard quadratic. Also make sure your direction vectors are normalized.

Also since you seem to be using C# (correct me if I'm wrong) you would do yourself a favour to code proper arithmetic operators for your vector class rather than using .subtract, .add, etc... that'll make your code much easier to read and write.

##### Share on other sites

@Bacterius

Also since you seem to be using C# (correct me if I'm wrong) you would do yourself a favour to code proper arithmetic operators for your vector class rather than using .subtract, .add, etc... that'll make your code much easier to read and write.

It is C# yes. I want to write the pathtracer step by step in c# because i am more familiar with this language. After i finished a code block (e.g. the intersection for the sphere) i will transfer it to Java for Android.

I didn't over overwrite the arithmetic operators because it is not possible in java.

Probably you want to completely exclude results less than zero (i.e. if t1 is less than 0, return t2, and vice versa, and if they are both positive then return the smallest one). That will also handle cases where your ray starts inside the sphere, as well. Otherwise I haven't checked but the equation looks correct, it's just a standard quadratic[/size]

So like this?

    public float intersect(Ray ray){
Vector3D v = ray.origin.sub(this.center);

float a = ray.direction.dot(ray.direction);
float b = 2.0f * ray.direction.dot(v);

float discriminant = (b*b) - (4.0f * a * c);

if(discriminant > 0){
float x1 = (-b - (float)Math.sqrt(discriminant) / (2.0f * a));
float x2 = (-b + (float)Math.sqrt(discriminant) / (2.0f*a));

return Math.min(x1,x2);
}
else if(discriminant == 0)
return (-b + (float)Math.sqrt(discriminant) / (2.0f * a));
else
return -1.0f;
}


Also make sure your direction vectors are normalized.

So like this?

Ray ray = new Ray(new Vector3D(0.0f,0.0f,0.0f), new Vector3D(5.0f,5.0f,1.0f).normalize());


Normalize function:

    public Vector3D normalize(){
float magnitude = magnitude();
return new Vector3D(this.x / magnitude, this.y / magnitude, this.z / magnitude);
}


Magnitude function:

    public float magnitude(){
return (float)Math.sqrt(this.x * this.x + this.y * this.y + this.z * this.z);
}

Edited by IsItSharp

##### Share on other sites

So like this?

No, see here if x1 is negative and x2 is positive then your code will return x1, but the correct return value should be x2 as that is the first intersection along the ray. Something like:
if(discriminant > 0){
float x1 = (-b - (float)Math.sqrt(discriminant) / (2.0f * a));
float x2 = (-b + (float)Math.sqrt(discriminant) / (2.0f*a));

if (x1 < 0) return x2;
if (x2 < 0) return x1;
return Math.min(x1,x2);
}

You can check this will always return the smallest positive solution, and a negative value (not necessarily -1!) if there is no positive solution. It could probably be optimized, though.

So like this?

Yes, but I really meant to remember to make sure they actually are normalized before giving them to your intersect function, since it depends on the direction vector having unit length.

##### Share on other sites

Thanks again Bacterius for your help, i really appreciate it

So after i have implemented the Vector, Ray and Sphere classes i think i am ready to go to calculate my first image, am i?

                Sphere sphere = new Sphere(Color.BLUE, false, new Vector3D(10.0f, 10.0f, 0.0f), 1.5f);
Vector3D camera = new Vector3D(0.0f, 0.0f, 0.0f);

for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
Ray ray = new Ray(camera, new Vector3D((float)x, (float)y, 0.0f).normalize());
if(sphere.intersect(ray) > -1.0f)
this.canvas.drawPoint(x,y, paint);
}
}


So here is the code and the second point i am struggling with. I expected to see a blue round ball but instead i just see a blue line:

Edited by IsItSharp

##### Share on other sites

Uhm.....

Your ray generation code is a nonsense... for F.e. x = 0, y = 0 you create a vector (0, 0, 0) and normalize it - all of its components are divided by sqrt(0^2 + 0^2 + 0^2) ... afaik sqrt(0) = 0 (or technically +0 or -0, both are correct answers) ... nothing changes the fact that you're dividing by 0. (Fyi. in mathematics sqrt(0) depends on convention - there are multiple definitions - one of the conventions also specifies that 0^2 is undefined, thus also sqrt(0) is undefined).

You want your rays to go from left to right, where x=0 will be in the middle column of pixels, and y=0 in middle row of pixels - also your z determines your field of view angle. Technically you want something like this:

float xdir = (x / (float)width) * 2.0f - 1.0f; // Keep x direction in interval <-1; 1>
float ydir = ((y / (float)height) * 2.0f - 1.0f) * aspect; // Keep y direction in interval <-1; 1>, aspect is (height / width) in your case
float zdir = 1.0f / (float)tan(fov); // Where fov represents field-of-view angle (in radians)
Ray ray = new Ray(camera, new Vector3D(xdir, ydir, zdir).normalize());


I hope xdir and ydir makes sense (their computation), zdir can be calculated using trigonometry.

This will generate correctly your ray directions, assuming your intersection code is correct - you should see a sphere.

##### Share on other sites

Fyi. in mathematics sqrt(0) depends on convention - there are multiple definitions - one of the conventions also specifies that 0^2 is undefined, thus also sqrt(0) is undefined

o.O

I have never heard of such a convention. The square root of zero has always been, and always will be zero, and zero squared is most definitely zero. Are you confusing with 0^0?

That said, yes, dividing by zero is always a mistake, and indeed you need some positive z component to drive the camera rays in a particular direction - there are different camera types but the one given by Villem is probably the simplest and easiest (and most common). Edited by Bacterius

##### Share on other sites

Thanks for your little hint with the x, y and z coordinates @Vilem Otte.

I changed my loop to this:

                Sphere sphere = new Sphere(Color.BLUE, false, new Vector3D(0.0f, 1.0f, 10f), 2.8f);
Vector3D camera = new Vector3D(0.0f, 0.0f, 0.0f);
float aspect = (float)height / (float)width;

for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
float xdir = (x / (float)width) * 2.0f - 1.0f;
float ydir = ((y / (float)height) * 2.0f - 1.0f) * aspect;
float zdir = 1.0f / (float)Math.tan(255);
Ray ray = new Ray(camera, new Vector3D(xdir, ydir, zdir).normalize());
if(sphere.intersect(ray) > -1.0f)
this.canvas.drawPoint(x,y, paint);
}
}


But i have a strange "appearance". If i set the FOV-Value to 255 i get this image:

but if i set it just 1 point higher to 256 i get this:

Are there any problems in my calculation or is this completely normal?

Edited by IsItSharp

##### Share on other sites

Reading the docs helps, or what Vilem has written. Argument is in radians, not degrees. Even for degrees the value would be silly (> 180°).

##### Share on other sites

Shadertoy is really useful for simple and bruteforce examples. Like this small path tracer. https://www.shadertoy.com/view/4sfGDB

Its easy to just start to modify sources and learn what each lines do. And you can avoid all non relevant problems.

##### Share on other sites

Reading the docs helps, or what Vilem has written. Argument is in radians, not degrees. Even for degrees the value would be silly (> 180°).

Thanks, now it works fine:

        float fov = 35 * (float)Math.PI / 180;
float zdir = 1.0f / (float)Math.tan(fov);


Now i have to get to the really hard part: bouncing rays, diffuse material, calculating colors and light

Edit: So what is the next step now? Should i generate the reflection ray from the intersection? If so: how do i get the intersection point between the ray and the sphere? I just get a float value back from my function?

Edited by IsItSharp

##### Share on other sites

Okay so i did a little bit of research and implemented a recursive "Trace" function which takes a Ray and a depth counter as parameters. It looks like this:

        public Color Trace(Ray ray, int depth)
{
float distance = 5000.0f;
BaseObject hitObject = null;
Vector3D HitPoint = null;
foreach (BaseObject obj in this.scene.Objects)
{
float currentDistance = obj.Intersect(ray);
if (currentDistance < distance && currentDistance > 0)
{
distance = currentDistance;
hitObject = obj;
}

}

if (distance == 5000.0f) //Kein Object wurde getroffen
return Color.Black;
if (hitObject.isEmitter) //Eine Lichtquelle wurde getroffen
return hitObject.surfaceColor;
if (depth == MAX_DEPTH)
return Color.Black;

Vector3D normal = hitObject.Normal(HitPoint);

Ray reflectionRay = null;

if (hitObject.mat == Material.Diffuse)
{
reflectionRay = new Ray(HitPoint, Vector3D.getRandomVectorInHemisphere(1.0f));
}

Color returnColor = Trace(reflectionRay, depth + 1);

float r = hitObject.surfaceColor.R * returnColor.R;
float g = hitObject.surfaceColor.G * returnColor.G;
float b = hitObject.surfaceColor.B * returnColor.B;

r /= 255.0f;
g /= 255.0f;
b /= 255.0f;

return Color.FromArgb(255, (int)r, (int)g, (int)b);
}


And i call the function like this:

            float fov = 35 * (float)Math.PI / 180;
float zdir = 1.0f / (float)Math.Tan(fov);
float aspect = (float)height / (float)width;

//BWorker.RunWorkerAsync(new Tuple<int, int, Bitmap, float, float, float>(height, width, drawArea, fov, zdir, aspect));

for (int y = 0; y < pB_Result.Height; y++)
{
for (int x = 0; x < pB_Result.Width; x++)
{
float xdir = (x / (float)width) * 2.0f - 1.0f;
float ydir = ((y / (float)height) * 2.0f - 1.0f) * aspect;
Ray ray = new Ray(new Vector3D(0.0f, 0.0f, 0.0f), new Vector3D(xdir, ydir, zdir).normalize());

float r = 0, g = 0, b = 0;
for (int i = 0; i < 3; i++)
{

Color c = Trace(ray, 0);
r += c.R;
g += c.G;
b += c.B;
}

drawArea.SetPixel(x, y, Color.FromArgb(255, (int)r / 3, (int)g / 3, (int)b / 3));
}
}
pB_Result.Image = drawArea;


But i only get this (there is one sphere on the left side of the light and one sphere on the right):

I think it all depends on my "getRandomVectorInHemisphere" function.

Currently i am just generating a random Vector:

        public static Vector3D getRandomVectorInHemisphere(float radius)
{
float x = (float)new Random(DateTime.Now.Millisecond).NextDouble() * radius;
float y = (float)new Random(DateTime.Now.Millisecond).NextDouble() * radius;
float z = (float)new Random(DateTime.Now.Millisecond).NextDouble() * radius;

return new Vector3D(x, y, z).multiply((float)new Random(DateTime.Now.Millisecond).NextDouble());
}


So anyone here who can give me a hint how i can compute a random direction vector for the bouncing ray in the hemisphere the normal is pointing at?

Edit: If i do something like this:

            int abortCounter = 0;
while (abortCounter < 500)
{
Vector3D b = new Vector3D((float)new Random(523940).NextDouble() - 0.5f, (float)new Random(5231).NextDouble() - 0.5f, (float)new Random(25061).NextDouble() - 0.5f);
b.normalize();
if (b.Dotproduct(normal) > 0)
return b;
abortCounter++;
if (abortCounter == 499)
return b;
else
return b;
}
return null;


I get this:

Edited by IsItSharp

##### Share on other sites

Your random number generator and logic behind it is wrong. Sadly I have to go off from PC in few minutes so I won't be able to give full answer and some background why is that (I will do that later).

As for now - your random direction should be normalized (unless you normalize it in ray constructor - which I don't think you do). There are few rules about the "random" direction and generally random number generation behind - you should use different random number generators for different surfaces. As of now, go with:

// Initialization of RNG, try to do this only once for whole random direction generator object - SEED is some number (F.e. 123456 ... or current timestamp, or anything :) )
Random rng = new Random(SEED);

...

// Your random direction into sphere generation code

Vector3D v = new Vector3D();
v.x = rng().NextDouble() * 2.0 - 1.0;
v.y = rng().NextDouble() * 2.0 - 1.0;
v.z = rng().NextDouble() * 2.0 - 1.0;
v.normalize();

...

// Your random direction into hemisphere
Vector3D v = GenerateRandomDirectionIntoSphere();
if (v.dot(normal) < 0.0)
{
// Where negate does return new Vector3D(-v.x, -v.y, -v.z);
v = v.negate();
}


The process of "how" you generate random numbers determines how good is your path tracer (I will elaborate later ;) ).

##### Share on other sites

Salt'n Pepper ? Probably hitting the same object you bounced the ray off again. This can happen due to precision issues. Grant your Trace function a ignoreObject parameter, skip collision check for this and feed hitObject when you recurse.

##### Share on other sites

Salt'n Pepper ? Probably hitting the same object you bounced the ray off again. This can happen due to precision issues. Grant your Trace function a ignoreObject parameter, skip collision check for this and feed hitObject when you recurse.

Another quick'n'dirty way to fix it is to "nudge" your hitpoint slightly outside the object (or inside, in the case of refraction) to make sure it doesn't intersect it again. A bit ugly, though, and unreliable with floating-point arithmetic although it tends to work most of the time (I actually read a paper where the authors used fixed point arithmetic to make it reliable).

##### Share on other sites

Your random number generator and logic behind it is wrong. Sadly I have to go off from PC in few minutes so I won't be able to give full answer and some background why is that (I will do that later).

As for now - your random direction should be normalized (unless you normalize it in ray constructor - which I don't think you do). There are few rules about the "random" direction and generally random number generation behind - you should use different random number generators for different surfaces. As of now, go with:

// Initialization of RNG, try to do this only once for whole random direction generator object - SEED is some number (F.e. 123456 ... or current timestamp, or anything :) )
Random rng = new Random(SEED);

...

// Your random direction into sphere generation code

Vector3D v = new Vector3D();
v.x = rng().NextDouble() * 2.0 - 1.0;
v.y = rng().NextDouble() * 2.0 - 1.0;
v.z = rng().NextDouble() * 2.0 - 1.0;
v.normalize();

...

// Your random direction into hemisphere
Vector3D v = GenerateRandomDirectionIntoSphere();
if (v.dot(normal) < 0.0)
{
// Where negate does return new Vector3D(-v.x, -v.y, -v.z);
v = v.negate();
}


The process of "how" you generate random numbers determines how good is your path tracer (I will elaborate later ;) ).

Works somehow better

Another quick'n'dirty way to fix it is to "nudge" your hitpoint slightly outside the object (or inside, in the case of refraction) to make sure it doesn't intersect it again.

If i debug through the code i understand the problem. But how do i move the hitpoint in the right direction away from the object?

Grant your Trace function a ignoreObject parameter, skip collision check for this and feed hitObject when you recurse.

Hm if i set an additional parameter "ignoreObject" of the type "BaseObject" and set the hitObject to ignoreObject and ignore the loop if ignoreObject is not null i get just the light in my image:

        public Color Trace(Ray ray, int depth, BaseObject ignoreObject = null)
{
float distance = 5000.0f;
BaseObject hitObject = ignoreObject;
Vector3D HitPoint = null;

if (hitObject == null)
{
foreach (BaseObject obj in this.scene.Objects)
{
float currentDistance = obj.Intersect(ray);
if (currentDistance < distance && currentDistance > 0)
{
distance = currentDistance;
hitObject = obj;
}

}
}

if (distance == 5000.0f) //Kein Object wurde getroffen
return Color.Black;
if (hitObject.isEmitter) //Eine Lichtquelle wurde getroffen
return hitObject.surfaceColor;
if (depth == MAX_DEPTH)
return Color.Black;

Vector3D normal = hitObject.Normal(HitPoint);

Ray reflectionRay = null;

if (hitObject.mat == Material.Diffuse)
{
Vector3D randomVector = Vector3D.getRandomVectorInHemisphere();
if (randomVector.Dotproduct(normal) < 0.0)
randomVector = randomVector.negate();
reflectionRay = new Ray(HitPoint, randomVector);
}

Color returnColor = Trace(reflectionRay, depth + 1, hitObject);

float r = hitObject.surfaceColor.R * returnColor.R;
float g = hitObject.surfaceColor.G * returnColor.G;
float b = hitObject.surfaceColor.B * returnColor.B;

r /= 255.0f;
g /= 255.0f;
b /= 255.0f;

return Color.FromArgb(255, (int)r, (int)g, (int)b);
}

Edited by IsItSharp

##### Share on other sites

Ah i understood the idea now. I hope i did it right:

        public Color Trace(Ray ray, int depth, BaseObject missObject = null)
{
float distance = 5000.0f;
BaseObject hitObject = null;
Vector3D HitPoint = null;

foreach (BaseObject obj in this.scene.Objects)
{
if (obj == missObject)
continue;
float currentDistance = obj.Intersect(ray);
if (currentDistance < distance && currentDistance > 0)
{
distance = currentDistance;
hitObject = obj;
}
}

if (distance == 5000.0f) //Kein Object wurde getroffen
return Color.Black;
if (hitObject.isEmitter) //Eine Lichtquelle wurde getroffen
return hitObject.surfaceColor;
if (depth == MAX_DEPTH)
return Color.Black;

Vector3D normal = hitObject.Normal(HitPoint);

Ray reflectionRay = null;

if (hitObject.mat == Material.Diffuse)
{
Vector3D randomVector = Vector3D.getRandomVectorInHemisphere();
if (randomVector.Dotproduct(normal) < 0.0)
randomVector = randomVector.negate();
reflectionRay = new Ray(HitPoint, randomVector);
}

Color returnColor = Trace(reflectionRay, depth + 1, hitObject);

float r = hitObject.surfaceColor.R * returnColor.R;
float g = hitObject.surfaceColor.G * returnColor.G;
float b = hitObject.surfaceColor.B * returnColor.B;

r /= 255.0f;
g /= 255.0f;
b /= 255.0f;

return Color.FromArgb(255, (int)r, (int)g, (int)b);
}


But all i get is this:

There is still something wrong. Any ideas or hints where i have to search?

Edited by IsItSharp

##### Share on other sites

Hm no one?

I would really appreciate it if someone could solve the problem or give me a little hint :)

##### Share on other sites

This topic is 1070 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628714
• Total Posts
2984353

• 23
• 11
• 10
• 13
• 14