# A question regarding depth sorting in raytracers

How do properly depth sort in raytracers

So this is more or less a debugging kind of problem, which im unable to solve. My problem is that the rays for some reason dont return the color of the closest intersection, alldough i have an sorting algorithm.

That sorting algorithm just checks if the currently closest intersection is further, than the newly computed one:

``````    float minDist = 1e10f; // set minDist to something reeaaaaaalllllly big
PVector surfClr = backgroundclr;

if(spheres.size() > 0) {

for(int i = 0; i < spheres.size(); i++) { // spheres

sphere curS = spheres.get(i); // create copy of data

float d = RaySphere(curS, r); // get intersection data of the current sphere

if(!(d < 0)) { // intersection occurs

if(minDist > d) { // check if intersection distance is smaller than the current

minDist = d; // update data
surfClr = curS.clr;

}

}

}

}
``````

(Only the loop for spheres)
â€śRaySphereâ€ť function tests for an intersection between a Ray and sphere, it will return -1 if no intersection occurs)

As already said, i cannot find the problem and i hope some of you guys may have a solution
Ill leave you with the source code of my raytracer.

main
``````Camera viewer; // the camera

public float deltaTime; // stuff for benchmarking
private long oldTime;
private float FPS;

PVector backgroundclr = new PVector(0, 0, 0);

public void setup() {

size(600, 400); // specify window dimensions

viewer = new Camera(); // create camera

createMemberContainers(); // create membery objects and arrays

}

public void draw() {

if (focused) {

oldTime = millis(); // cache the time

viewer.update(); // update camera (process user inputs etc...)

renderScreen(viewer); // render the screen (send out rays, update pixel array ...)

deltaTime = (millis() - oldTime) * 0.001; // calculate the delta time
FPS = 1f / deltaTime; // calculate FPS

}

}
``````
Camera
``````class Camera {

public Boolean openIn;
public float sensitivity;
public float movementSpeed;
public PVector position;
public PVector up;
public float FocalLength;
public Boolean processKey;
public Boolean processMouse;

private PVector cosR;
private PVector sinR;
private PVector rot;

Camera() {

openIn = true;
sensitivity = 0.1f;
movementSpeed = 50f;
position = new PVector(0f, 0f, 0f);
up = new PVector(0f, 1f, 0f);
rot = new PVector(90f, 0f);
FocalLength = 300f;
processKey = false;
processMouse = false;
cosR = new PVector(cos(rot.x),
cos(rot.y));

sinR = new PVector(sin(rot.x),
sin(rot.y));

}

public void update() {

if (!openIn || !focused) return; // check if the camera input stream is open and if the window is focussed

if (processMouse) {

rot.x += (mouseX - pmouseX) * (sensitivity * deltaTime); // update rotation
rot.y += (pmouseY - mouseY) * (sensitivity * deltaTime);

rot.y = constrain(rot.y, -89.9, 89.9); // clamp y rotation

cosR = new PVector(cos(rot.x),   // update the sin & cos values of the cameras rotation
cos(rot.y));

sinR = new PVector(sin(rot.x),
sin(rot.y));

}

if (processKey) {

float speed = movementSpeed * deltaTime; // calculate Speed

if(kw) position.add(new PVector(sinR.x * speed, 0, cosR.x * speed)); // process keyboard user inputs
else if(ks) position.sub(new PVector(sinR.x * speed, 0, cosR.x * speed));

if(ka) position.add(new PVector(cosR.x * (-1 * speed), 0, sinR.x * speed));
else if(kd) position.add(new PVector(cosR.x * speed, 0, sinR.x * (-1 * speed)));

if(kspace) position.y += speed;
else if(kshift) position.y -= speed;

}

}

public void directRay(ray r, PVector px) {

PVector Npx = new PVector(0,0); // create empty vector for new screen coordinates

if (px.x < (int)(pixelWidth/2)) Npx.x = -1 * ((int)(pixelWidth/2) - px.x); // map screen coordinates to a new origin (0,0 = the middle of the window)
else Npx.x = px.x - (int)(pixelWidth/2);

if (px.y > (int)(pixelHeight/2)) Npx.y = -1 * (px.y - (int)(pixelHeight/2));
else Npx.y = (int)(pixelHeight/2) - px.y;

PVector tmp = new PVector(Npx.x, Npx.y, FocalLength);  // create temporary vector with the pixel coordinates as xy and the focalLength as z
tmp.normalize(); // normalize the newly created vector

float savedZ = tmp.z; // save the z

tmp.z = cosR.y * savedZ - sinR.y * tmp.y; // calculate the y direction
tmp.y = sinR.y * savedZ + cosR.y * tmp.y;

savedZ = tmp.z; // save the z

tmp.z = cosR.x * savedZ - sinR.x * tmp.x; // calculate final z direction and the x direction
tmp.x = sinR.x * savedZ + cosR.x * tmp.x;

tmp.normalize(); // normalize again just for savety :)

r.origin = position; // pass created data to the ray
r.direction = tmp;

}

}
``````
helperFunctions
``````ray screenRays[][];
float depthBuffer[][];

public void loadHelperArrays() { // iniate the Helper arrays

screenRays = new ray[pixelWidth][pixelHeight];
depthBuffer = new float[pixelWidth][pixelHeight];

}

void tracePixel(ray r, PVector px, Camera c) {

c.directRay(r, px); // direct ray to the pixel

r.getIntersection(r); // get the intersection data

depthBuffer[(int)px.x][(int)px.y] = r.IntersectionTime * r.direction.z; // update the depth Buffer

pixels[getPixelIndex(px)] = color(r.returnClr.x, r.returnClr.y, r.returnClr.z); // updatee the pixel

}

int getPixelIndex(PVector px) { // neat function to convert from a 2D index to a 1D index

return ((int)px.y * pixelWidth) + (int)px.x;

}

public void renderScreen(Camera c) {

for(int i = 0; i < pixelHeight; i++) {

for(int i1 = 0; i1 < pixelWidth; i1++) {

screenRays[i1][i] = new ray(new PVector(), new PVector()); // create empty ray

tracePixel(screenRays[i1][i], new PVector(i1, i), c); // trace the pixel

}

}

updatePixels(); // update all the pixels

}
``````
intersectionFunctions
``````public float RayTriangle(triangle t, ray r) {

PVector e1 = PVector.sub(t.v2.position, t.v1.position);
PVector e2 = PVector.sub(t.v3.position, t.v1.position);

PVector rde2 = r.direction.cross(e2);

float d = e1.dot(rde2);

if (abs(d) < 0) return -1f;

else {

float invd = 1 / d;
PVector h = PVector.sub(r.origin, t.v1.position);

float u = h.magSq() * invd;

if (u < 0 || u > 1) return -1f;

else {

PVector he1 = h.cross(e1);

float v = r.direction.dot(he1) * invd;

if (v < 0 || v + u > 1) return -1f;
else return e2.dot(he1) * invd;

}

}

}

public float RaySphere(sphere s, ray r) {

PVector e1 = PVector.sub(s.position, r.origin);

float d = r.direction.dot(e1);

if (d > 0) {

PVector v = r.direction.cross(e1);
float vm = v.mag();

if (vm < s.rad) return vm;
else return -1f;

} else return -1f;

}
``````
userInputs
``````/*

To-Do:
- Put all the bools into an array

*/

Boolean kw = false, ks = false, ka = false, kd = false, kspace = false, kshift = false;

public void keyPressed() { // switch through the key variable to set the booleans accordingly

viewer.processKey = true;

switch(key) {

case 'w':

kw = true;
break;

case 's':

ks = true;
break;

case 'a':

ka = true;
break;

case 'd':

kd = true;
break;

case ' ':

kspace = true;
break;

case 'e':

kshift = true;

}

}

public void keyReleased() { // switch through the key variable to set the booleans accordingly

viewer.processKey = false;

switch(key) {

case 'w':

kw = false;
break;

case 's':

ks = false;
break;

case 'a':

ka = false;
break;

case 'd':

kd = false;
break;

case ' ':

kspace = false;
break;

case 'e':

kshift = false;
break;

}

}

public void mousePressed() { // just here to only update the cameras rotation if an actual input has been given

viewer.processMouse = true;

}

public void mouseReleased() { // just here to stop updating the camera

viewer.processMouse = false;

}
``````
worldMembers
``````ArrayList<sphere> spheres; // iniate world containers
ArrayList<triangle> triangles;
ArrayList<vertex> vertecies;

/*-----------------------------------------------------*/
/* Global functions, associated with the world members */
/*-----------------------------------------------------*/

public void createMemberContainers() {

spheres = new ArrayList<sphere>();
triangles = new ArrayList<triangle>();
vertecies = new ArrayList<vertex>();

}

2f,
new PVector(150, 0, 0)
));

2f,
new PVector(0, 150, 0)
));

2f,
new PVector(0, 0, 150)
));

}

/*----------------*/
/* member Classes */
/*----------------*/

class sphere {

public PVector position;
public PVector clr;

sphere (PVector p, float r, PVector c) {

position = p;
clr = c;

}

}

class triangle {

vertex v1;
vertex v2;
vertex v3;
public PVector clr;

triangle (vertex one, vertex two,vertex three, PVector c) {

v1 = one;
v2 = two;
v3 = three;
clr = c;

}

}

class vertex {

public PVector position;

vertex(PVector pos) {

position = pos;

}

}

/*----------------------------------------------------*/
/* Ray class (extra "chapter" because a lot more code) */
/*----------------------------------------------------*/

class ray {

public PVector origin;
public PVector direction;
public PVector IntersectionAngle;
public float IntersectionTime;
public PVector returnClr;

ray (PVector ro, PVector rd) {

origin = ro;
direction = rd;

}

public void getIntersection(ray r) {

float minDist = 1e10f; // set minDist to something reeaaaaaalllllly big
PVector surfClr = backgroundclr;

if(spheres.size() > 0) {

for(int i = 0; i < spheres.size(); i++) { // spheres

sphere curS = spheres.get(i); // create copy of data

float d = RaySphere(curS, r); // get intersection data of the current sphere

if(!(d < 0)) { // intersection occurs

if(minDist > d) { // check if intersection distance is smaller than the current

minDist = d; // update data
surfClr = curS.clr;

}

}

}

}

if(triangles.size() > 0) {

for(int i = 0; i < spheres.size(); i++) { // triangle

triangle curT = triangles.get(i); // create copy of data

float d = RayTriangle(curT, r); // get intersection data of the current triangle

if(!(d < 0)) { // intersection occurs

if(minDist > d) { // check if intersection distance is smaller than the current

minDist = d; // update data
surfClr = curT.clr;

}

}

}

}

IntersectionTime = minDist;
returnClr = surfClr;

}

}
``````

Excuse my english and all the mistakes that come with it

1 Like