I want to build a 3d render engine from scratch in java. The code works fine, I only have some problems sorting the triangles in the right order, so that they won't get rendered over one another. I have implemented face culling and quicksort to sort the triangles by the average z value of the 3 vertices.
Anyway for now it works but I figured out once the amount of triangles comes closer to 100k the sorting algorithm seems to take extreme amounts of time so that the program is unusable.
Here is my code for sorting the triangles. I followed this scheme: https://www.baeldung.com/java-quicksort. I have changed it a bit because in my case I load a .obj file, where the faces are only the references to the vertices (in another list). So it's quite confusing but it works.
public static ArrayList<Vector> sortList(ArrayList<Vector> array,
Vector[] vectors, int begin, int end) {
if (begin < end) {
int partitionIndex = partition(array, vectors, begin, end);
sortList(array, vectors, begin, partitionIndex - 1);
sortList(array, vectors, partitionIndex + 1, end);
}
return array;
}
public static int partition(ArrayList<Vector> arr, Vector[] vectors,
int begin, int end) {
float pivot = vectors[(int) arr.get(end).x - 1].z;
pivot += vectors[(int) arr.get(end).y - 1].z;
pivot += vectors[(int) arr.get(end).z - 1].z;
pivot /= 3;
int i = (begin - 1);
for (int j = begin; j < end; j++) {
float check = vectors[(int) arr.get(j).x - 1].z;
check += vectors[(int) arr.get(j).y - 1].z;
check += vectors[(int) arr.get(j).z - 1].z;
check /= 3;
if (check <= pivot) {
i++;
Vector swapTemp = arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, swapTemp);
}
}
Vector swapTemp = arr.get(i+1);
arr.set(i+1, arr.get(end));
arr.set(end, swapTemp);
return i + 1;
}
and here I calculate the positions and vertices etc.
Vector[] vectors = new Vector[obj.vertices.size()];
Vector[] vectors3D = new Vector[obj.vertices.size()];
// transformation and rotation
for (int i = 0; i < obj.vertices.size(); i++) {
Vector vertex = obj.vertices.get(i);
vectors[i] = Calc.matmul(Calc.rotationY(rotY), vertex);
vectors[i] = Calc.matmul(Calc.rotationX(rotX), vectors[i]);
vectors[i] = Calc.matmul(Calc.rotationY(rotZ), vectors[i]);
vectors3D[i] = vectors[i];
// projection
float depth = 1 / (z + camera.z - vectors[i].z);
float[][] projection = { { depth, 0, 0 }, // Orthographic:
// depth instead
// of 1/camera.z
{ 0, depth, 0 } // Perspective: 1/camera.z isntead of
// depth
};
vectors[i] = Calc.matmul(projection, vectors[i]);
vectors[i].mult(size);
vectors[i].add(new Vector(x, y))
.add(new Vector(camera.x, camera.y));
}
// drawing
if (type.equals(Object.CORN)) {
for (int i = 0; i < vectors.length; i++) {
triangles.add(new ArrayList<Vector>());
triangles.get(triangles.size() - 1).add(
new Vector(vectors[i].x, vectors[i].y));
// point(vectors[i].x, vectors[i].y);
}
} else if (type.equals(Object.MESH)) {
for (int i = 0; i < obj.faces.size(); i++) {
Vector corner = obj.faces.get(i);
float x1 = vectors[(int) corner.x - 1].x;
float y1 = vectors[(int) corner.x - 1].y;
float x2 = vectors[(int) corner.y - 1].x;
float y2 = vectors[(int) corner.y - 1].y;
float x3 = vectors[(int) corner.z - 1].x;
float y3 = vectors[(int) corner.z - 1].y;
triangles.add(new ArrayList<Vector>());
triangles.get(triangles.size() - 1).add(new Vector(x1, y1));
triangles.get(triangles.size() - 1).add(new Vector(x2, y2));
triangles.get(triangles.size() - 1).add(new Vector(x3, y3));
}
} else if (type.equals(Object.FILL)) {
ArrayList<Vector> faces = obj.faces;
// sort back to front
faces = Calc.sortList(faces, vectors3D, 0, faces.size() - 1);
for (int i = 0; i < faces.size(); i++) {
Vector corner = faces.get(i);
float x1 = vectors3D[(int) corner.x - 1].x;
float y1 = vectors3D[(int) corner.x - 1].y;
float z1 = vectors3D[(int) corner.x - 1].z;
float x2 = vectors3D[(int) corner.y - 1].x;
float y2 = vectors3D[(int) corner.y - 1].y;
float z2 = vectors3D[(int) corner.y - 1].z;
float x3 = vectors3D[(int) corner.z - 1].x;
float y3 = vectors3D[(int) corner.z - 1].y;
float z3 = vectors3D[(int) corner.z - 1].z;
float nx = (y2 - y1) * (z3 - z1) - (z2 - z1) * (y3 - y1);
float ny = (z2 - z1) * (x3 - x1) - (x2 - x1) * (z3 - z1);
float nz = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
Vector lightVector = new Vector(light.x, light.y, light.z)
.normalize();
Vector normalVector = new Vector(nx, ny, nz).normalize();
// face culling
if (Calc.dotProduct(new Vector(0, 0, -1), normalVector) < 0) {
int col = (int) Calc.map(
Calc.dotProduct(lightVector, normalVector), -1, 1,
0, 255);
colors.add(new Color(col, col, col));
x1 = vectors[(int) corner.x - 1].x;
y1 = vectors[(int) corner.x - 1].y;
x2 = vectors[(int) corner.y - 1].x;
y2 = vectors[(int) corner.y - 1].y;
x3 = vectors[(int) corner.z - 1].x;
y3 = vectors[(int) corner.z - 1].y;
triangles.add(new ArrayList<Vector>());
triangles.get(triangles.size() - 1).add(new Vector(x1, y1));
triangles.get(triangles.size() - 1).add(new Vector(x2, y2));
triangles.get(triangles.size() - 1).add(new Vector(x3, y3));
}
}
}
this.repaint();
the .obj file follows these rules:
v x y z (v indicates vertex) [...] f [vertex index]/[texture index]/[normal index] [vertex index]/[texture index]/[normal index] [vertex index]/[texture index]/[normal index] (for a triangle)
so when i have v 0 0 1 v 0 1 0 v 1 0 0 f 1/1/1 2/2/2 3/3/3
i get the triangle vertices with (f arraylist of arraylist of vectors) f.get(0).get(0).x f.get(0).get(1).y f.get(0).get(2)
I hope that is understandable