从零实现光线追踪：3D渲染器隐藏面消除问题求助

我开发了一款可解析ASCII格式.obj文件并投影至2D平面的3D渲染器，目前遇到的问题是：模型背面的不可见多边形会被渲染出来。查资料后知道这是**隐藏面消除（Hidden-surface determination）**问题，了解到可以用Z-Buffer或光线追踪解决。因为后续要添加光源，我倾向选择光线追踪，但对原理有疑问：从相机向屏幕每个像素发射射线时，怎么判断多边形可见性才不会导致形状失真或性能问题？

附上我的Processing代码：

// 12.11.2022
// Siehe Rotation Matrix in Wikipedia

// View Space: The world space vertex positions relative to the view of the camera

/* Die Verdeckungsberechnung ist zum korrekten Rendern einer 3D-Szene notwendig, weil Oberflächen,
   die für den Betrachter nicht sichtbar sind, auch nicht dargestellt werden sollten
*/

// ->  https://de.wikipedia.org/wiki/Sichtbarkeitsproblem


// TODO: Raytracing/Verdeckungsberechnung
// TODO: Texture Mapping

import java.util.Arrays;

import java.awt.Robot;


import java.nio.ByteBuffer;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.ArrayList;

byte b[];

int amount = 0;
String lines[];


PVector[][] vertices;
int[] faces;



float a = 0;


PVector cam, cam_angle, cam_move, cam_speed;

float angle = 0.0;


void setup() {
  size(800,600);
  frameRate(60);
  noCursor();

  cam  = new PVector(0, 100, -500);
  cam_angle = new PVector(0, 0, 0);
  cam_move = new PVector(0, 0, 0);
  cam_speed = new PVector(50, 50, 50);
  
  lines =  loadStrings("UM2_SkullPile28mm.obj"); 
 
  println("File loaded. Now scanning contents...");
  
  println();
  
  Pattern numbers = Pattern.compile("(-?\\d+)");
  
  
  ArrayList<PVector> vertices_ = new ArrayList<PVector>();
  ArrayList<ArrayList> faces_ = new ArrayList<ArrayList>();
  
  int parsed_lines = 0; 
  
  for(String i:lines) {
    switch(i.charAt(0)) {
      
      // Find faces
      case 'f':
        ArrayList<Integer> values = new ArrayList<Integer>();
        for(Matcher m = numbers.matcher(i); m.find(); values.add(Integer.parseInt(m.group())));
        faces_.add(values);
        break;
        
      // Find Vectors  
      case 'v':
        String s[] = i.trim().split("\\s+");
        vertices_.add(new PVector(Float.parseFloat(s[1])*20, Float.parseFloat(s[2])*20, Float.parseFloat(s[3])*20));
        break;
    };
    if(++parsed_lines % (lines.length/6) == 0 || parsed_lines == lines.length) println((int)(map(parsed_lines, 0, lines.length, 0, 100)), "%");
  }
  
  println();
  println("Done. Found", vertices_.size(), "Vertices and", faces_.size(), "faces");
  
  

  int i=0;  
  
  vertices = new PVector[faces_.size()][];
  
  for(ArrayList<Integer> f_:faces_) {   
    vertices[i] = new PVector[f_.size()]; 
    int j = 0;
    
    for(int f: f_) {
      PVector v = vertices_.get(f-1);
      vertices[i][j] = Rotate3d_x(v, -90); 
      j++;
    }
    
    i++;
  }
  
}


PVector Rotate2d(PVector p, float a) {
  // a = angle

  float[][] m2 = {
    {cos(a), -sin(a)},
    {sin(a), cos(a)}
  };

  float[][] rotated = matmul(m2, new float[][] {
    { p.x },
    { p.y }
    });

  return new PVector(rotated[0][0], rotated[1][0]);
}


PVector Rotate3d(PVector p, float[][] m2) {

  float[][] rotated = matmul(m2, new float[][] {
    { p.x },
    { p.y },
    { p.z }
    });

  return new PVector(rotated[0][0], rotated[1][0], rotated[2][0]);
}



PVector Rotate3d_x(PVector p, float a) {
  return Rotate3d(p,
    new float[][] {
    {1, 0, 0},
    {0, cos(a), -sin(a)},
    {0, sin(a), cos(a)}
    });
};

PVector Rotate3d_y(PVector p, float a) {
  return Rotate3d(p,
    new float[][] {
    {cos(a), 0, sin(a)},
    {0, 1, 0},
    {-sin(a), 0, cos(a)}
    });
}

PVector Rotate3d_z(PVector p, float a) {
  return Rotate3d(p,
    new float[][] {
    {cos(a), -sin(a), 0},
    {sin(a), cos(a), 0},
    {0, 0, 1}
    });
}

PVector Rotate3d(PVector p, PVector a) {
  return Rotate3d_z( Rotate3d_y(Rotate3d_x(p, a.x), a.y), a.z );
}



// Matrixmultiplikation
float[][] matmul(float[][] m1, float[][] m2) {

  int cols_m1 = m1.length,
    rows_m1 = m1[0].length;

  int cols_m2 = m2.length,
    rows_m2 = m2[0].length;

  try {
    if (rows_m1 != cols_m2) throw new Exception("Rows of m1 must match Columns of m2!");
  }
  catch(Exception e) {
    println(e);
  }


  float[][] res = new float[cols_m2][rows_m2];


  for (int c=0; c < cols_m1; c++) {

    for (int r2=0; r2 < rows_m2; r2++) {

      float sum = 0;
      float[] buf = new float[rows_m1];

      // Multiply rows of m1 with columns of m2 and store in buf
      for (int r=0; r < rows_m1; r++) {
        buf[r] = m1[c][r]* m2[r][r2];
      }

      // Add up all entries into sum
      for (float entry : buf) {
        sum += entry;
      }

      res[c][r2] = sum;
    }
  }

  return res;
}


PVector applyPerspective(PVector p) {
    PVector d = applyViewTransform(p);
    return applyPerspectiveTransform(d);
}

PVector applyViewTransform(PVector p) {
    // c = camera position
    // co = camera orientation / camera rotation
    PVector c = cam;
    PVector co = cam_angle;
 

    // dx, dy, dz     https://en.wikipedia.org/wiki/3D_projection   :   Mathematical Formula
    float[][] dxyz = matmul(
            matmul(new float[][]{ 
                    {1, 0, 0},
                    {0, cos(co.x), sin(co.x)},
                    {0, -sin(co.x), cos(co.x)}
            }, new float[][]{ 
                    {cos(co.y), 0, -sin(co.y)},
                    {0, 1, 0},
                    {sin(co.y), 0, cos(co.y)}
            }),

            matmul(new float[][]{ 
                    {cos(co.z), sin(co.z), 0},
                    {-sin(co.z), cos(co.z), 0},
                    {0, 0, 1}
            }, new float[][]{ 
                    {p.x - c.x},
                    {p.y - c.y},
                    {p.z - c.z},
            }));

    PVector d = new PVector(dxyz[0][0], dxyz[1][0], dxyz[2][0]);
    return d;
}


PVector applyPerspectiveTransform(PVector d) {
     // e = displays surface pos relative to camera pinhole c
    PVector e = new PVector(0, 0, 300);
    return new PVector((e.z / d.z) * d.x + e.x, (e.z / d.z) * d.y + e.y);
}


void draw() {
  background(255);
  translate(width/2, height/2);
  scale(1,-1); 
  noStroke();
  fill(0, 100, 0, 50);
  
 
  
  PVector[][] points_view = new PVector[vertices.length][];
  
  for(int i=0; i < vertices.length; i++) {
    points_view[i] = new PVector[vertices[i].length];
    for(int j=0; j < vertices[i].length; j++)
    points_view[i][j] = applyViewTransform(Rotate3d_y(vertices[i][j], angle));
  }


    // The following snippet I got from:  https://stackoverflow.com/questions/74443149/3d-projection-axis-inversion-problem-java-processing?noredirect=1#comment131433616_74443149
  
    float nearPlane = 1.0;   
    
    for (int c = 0; c < points_view.length; c++) {
      beginShape();
      
        for (int r = 0; r < points_view[c].length-1; r++) {
            // Alle Punkte verbinden
            //if (i == a) continue;
            
            PVector p0 = points_view[c][r];    
            PVector p1 = points_view[c][r+1];
             
            
             if(p0.z < nearPlane && p1.z < nearPlane){ continue; };
             
           
             if(p0.z >= nearPlane && p1.z < nearPlane)
             p1 = PVector.lerp(p0, p1, (p0.z - nearPlane) / (p0.z - p1.z));
              
             if(p0.z < nearPlane && p1.z >= nearPlane)
             p0 = PVector.lerp(p1, p0, (p1.z - nearPlane) / (p1.z - p0.z));
 
            
            // project
            p0 = applyPerspectiveTransform(p0);
            p1 = applyPerspectiveTransform(p1);
            vertex(p0.x, p0.y);
            vertex(p1.x, p1.y);

        }
        endShape();
    }
    
  


  
}

光线追踪实现隐藏面消除的核心思路与优化方案 #

1. 可见性判断逻辑 #

对每个像素的射线，执行以下步骤：

• 射线生成：以相机位置为起点，根据像素在屏幕上的坐标计算射线方向（需结合相机的朝向和投影参数）
• 相交检测：遍历场景中所有多边形，计算射线与多边形的交点：
  1. 先判断射线是否与多边形所在平面相交，计算交点的3D坐标
  2. 用重心坐标法或射线交叉计数法，验证交点是否落在多边形内部
• 最近交点筛选：记录所有有效交点中距离相机最近的那个，对应的多边形就是该像素可见的面，直接渲染该面的颜色即可

2. 避免形状失真的关键 #

• 射线方向精度：确保射线方向计算时考虑相机的旋转矩阵，精确映射屏幕像素到3D空间方向
• 相交检测精度：使用浮点运算时加入微小的epsilon（比如1e-6），避免因精度误差导致的交点误判
• 多边形拓扑正确性：确保.obj文件解析时正确读取多边形的顶点顺序，法向量计算准确

3. 性能优化建议 #

• 背面剔除：预先计算每个多边形的法向量，若法向量与射线方向的点积大于0（多边形背向相机），直接跳过该多边形的相交检测
• 空间划分：用BVH（边界体积层次）将场景多边形分组，射线先与包围盒相交，再检测盒内的多边形，减少检测数量
• 分层次渲染：先渲染低分辨率图像，再对边缘像素做抗锯齿采样，平衡性能与画质

针对代码的修改提示 #

第一步：添加多边形法向量计算函数

// 计算多边形的法向量，顶点需按顺时针或逆时针顺序排列
PVector calculateFaceNormal(PVector[] faceVertices) {
  PVector edge1 = PVector.sub(faceVertices[1], faceVertices[0]);
  PVector edge2 = PVector.sub(faceVertices[2], faceVertices[0]);
  PVector normal = edge1.cross(edge2);
  normal.normalize();
  return normal;
}

第二步：替换渲染逻辑为光线追踪框架

在draw()函数中，替换原有的多边形遍历渲染，改为逐像素射线检测：

void draw() {
  background(255);
  loadPixels();

  float fov = PI/3; // 视场角
  float aspect = (float)width/height;

  for (int x = 0; x < width; x++) {
    for (int y = 0; y < height; y++) {
      // 将屏幕坐标转换为NDC（归一化设备坐标）
      float nx = (2.0f * x / width) - 1.0f;
      float ny = 1.0f - (2.0f * y / height);
      ny *= aspect;

      // 计算射线方向（考虑相机旋转）
      PVector rayDir = new PVector(nx * tan(fov/2), ny * tan(fov/2), 1);
      rayDir = Rotate3d(rayDir, cam_angle);
      rayDir.normalize();

      float closestDist = Float.MAX_VALUE;
      int pixelColor = color(255);

      // 遍历所有多边形
      for (int faceIdx = 0; faceIdx < vertices.length; faceIdx++) {
        PVector[] face = vertices[faceIdx];
        // 背面剔除：计算法向量与射线方向的点积
        PVector normal = calculateFaceNormal(face);
        if (PVector.dot(normal, rayDir) > 0) continue;

        // 射线与多边形相交检测（此处简化实现，需完善）
        float dist = rayIntersectsPolygon(cam, rayDir, face);
        if (dist > 0 && dist < closestDist) {
          closestDist = dist;
          pixelColor = color(0, 100, 0, 255); // 可见面的颜色
        }
      }

      pixels[y * width + x] = pixelColor;
    }
  }

  updatePixels();
  angle += 0.01;
}

// 射线与多边形相交检测的简化实现
float rayIntersectsPolygon(PVector rayOrigin, PVector rayDir, PVector[] polygon) {
  // 先计算射线与平面的交点
  PVector normal = calculateFaceNormal(polygon);
  float denom = PVector.dot(normal, rayDir);
  if (abs(denom) < 1e-6) return -1; // 射线与平面平行

  float t = PVector.dot(PVector.sub(polygon[0], rayOrigin), normal) / denom;
  if (t < 0) return -1; // 交点在相机后方

  PVector hitPoint = PVector.add(rayOrigin, PVector.mult(rayDir, t));

  // 验证交点是否在多边形内部（此处用重心坐标法简化）
  // 注：完整实现需处理任意边数的多边形，此处假设为三角形
  if (polygon.length == 3) {
    PVector v0 = polygon[0];
    PVector v1 = polygon[1];
    PVector v2 = polygon[2];

    PVector v0v1 = PVector.sub(v1, v0);
    PVector v0v2 = PVector.sub(v2, v0);
    PVector v0p = PVector.sub(hitPoint, v0);

    float dot00 = PVector.dot(v0v1, v0v1);
    float dot01 = PVector.dot(v0v1, v0v2);
    float dot02 = PVector.dot(v0v1, v0p);
    float dot11 = PVector.dot(v0v2, v0v2);
    float dot12 = PVector.dot(v0v2, v0p);

    float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
    float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

    if (u >= 0 && v >= 0 && u + v <= 1) {
      return t;
    }
  }

  return -1;