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
loadHelperArrays(); // load helper arrays (depth buffer ...)
createMemberContainers(); // create membery objects and arrays
loadMembers();
}
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) {
loadPixels(); // load pixels array
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>();
}
public void loadMembers() {
spheres.add(new sphere(new PVector(0, 0, 20),
2f,
new PVector(150, 0, 0)
));
spheres.add(new sphere(new PVector(20, 0, 20),
2f,
new PVector(0, 150, 0)
));
spheres.add(new sphere(new PVector(-20, 0, 20),
2f,
new PVector(0, 0, 150)
));
}
/*----------------*/
/* member Classes */
/*----------------*/
class sphere {
public PVector position;
public float rad;
public PVector clr;
sphere (PVector p, float r, PVector c) {
position = p;
rad = r;
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