我想用 java 从头开始构建一个 3D 渲染引擎。代码工作正常，我只是在以正确的顺序对三角形进行排序时遇到一些问题，这样它们就不会相互渲染。我已经实现了面剔除和快速排序，以按 3 个顶点的平均 z 值对三角形进行排序。
无论如何，现在它可以工作，但我发现一旦三角形的数量接近 100k，排序算法似乎会花费大量时间，因此程序无法使用。
这是我对三角形进行排序的代码。我遵循了这个方案:https://www.baeldung.com/java-quicksort 。我对其进行了一些更改，因为在我的情况下，我加载了一个 .obj 文件，其中面只是对顶点的引用(在另一个列表中)。所以这很令人困惑但它有效。
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;
}
在这里我计算位置和顶点等。
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();
.obj 文件遵循以下规则:
v x y z(v表示顶点) [...] f [顶点索引]/[纹理索引]/[法线索引] [顶点索引]/[纹理索引]/[法线索引] [顶点索引]/[纹理索引]/[法线索引](对于三角形)
所以当我有 v 0 0 1 v 0 1 0 v 1 0 0 f 1/1/1 2/2/2 3/3/3
我用( vector 数组列表的f数组列表)f.get(0).get(0).x f.get(0).get(1).y f.get(0)获取三角形顶点。获取(2)
我希望这是可以理解的
最佳答案
请注意，对三角形进行排序必然会对性能造成巨大影响，如果不需要(例如由于透明度)，引擎通常会依赖 z 缓冲区并接受 overdraw 。
一般来说，100k 个渲染的三角形对于纯软件渲染引擎来说已经很多了。因此，您可能不想尝试加快排序速度，而是尝试减少渲染的三角形数量:
- 计算相机视锥体内潜在可见的三角形集合 (pvs)
- 尝试使用更复杂的 pvs 机制来剔除墙后的物体等。
- 如果可能，尝试减小视锥体的大小(不要渲染太近或太远的对象)
- 尝试使用细节级别渲染 (LOD)，即对远处的模型使用较低的分辨率，甚至可能只是对最远的地方使用广告牌
- 在对三角形进行排序之前使用背面剔除来删除不可见的三角形
另请注意，您可能不必对每帧的所有三角形进行排序。如果相机或其他对象移动得不太快或突然出现或消失，您可以尝试在几帧中重复使用已排序的三角形列表 - 或者您可以尝试仅对部分元素进行排序。
此外，您可以尝试不按平均 z 排序，而是使用三角形(即顶点)的最小/最大 z。计算平均值 z 也会影响性能
关于java - 对三角形进行排序时快速排序太慢，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66877868/