3d 中三角形的 z 排序问题

Question

我们用 js 编写了一个旋转的 3d 形状。顶部三角形的渲染出现闪烁，我们认为这是因为 z 排序没有正常工作。我们如何解决这个问题？

这是一个jsfiddle。

这是 z 排序代码：

// z sorting

// dots_for_rendering.sort((a,b) => Math.sqrt((b.x)**2 + (b.y)**2) - Math.sqrt((a.x)**2 + (a.y)**2))

for (var i = 0; i < polygons.length; i++) {
  polygons[i].maxz = -Infinity;
  polygons[i].minz = Infinity;
  polygons[i].midz = 0;


for (var j = 0; j < polygons[i].verticies.length; j++) {
  var z = rotated_verticies[polygons[i].verticies[j]].vector[2];
  if (z > polygons[i].maxz) {
    polygons[i].maxz = z;
  }
  if (z < polygons[i].minz) {
    polygons[i].minz = z;
  }
  polygons[i].midz += z;
}
polygons[i].midz /= polygons[i].verticies.length;

}

polygons.sort((a, b) => b.midz - a.midz)
// polygons.sort((a,b) => Math.max(b.maxz - a.minz, b.minz - a.maxz))


// polygons.sort((a,b) => {
//   if (a.minz < b.maxz) {
//     return 0;
//   }
//   if (b.minz < a.maxz) {
//     return -1;
//   }
//   return 0;
// })

这是一个代码片段：

class Tensor {
  constructor(){
    var input = this.takeInput(...arguments);
    this.vector = input;
  }

  takeInput() {
    var a = true;
    for (var arg of arguments) {
      if (typeof arg !== "number"){
        a = false
      }
    }

     if (a && arguments[2] !== true){
       return new Array(...arguments);
     }
     else {
       if (arguments[0] instanceof Tensor){
         return arguments[0].vector;
       }
       else {
          if (typeof arguments[0] === "number" && typeof arguments[1] === "number" && arguments[2] === true) {
            var res = [];
            for (var i = 0; i < arguments[0]; i++) {
              res.push(arguments[1]);
            }
            return res;
          }
       }
     }
  }

  // used for + - * /
  change(f, input){
    for (var i in this.vector) {
      this.vector[i] = f(this.vector[i], input[i]);
    }
    return this;
  }

  copy() {
    return new Tensor(...this.vector);
  }

  dimentions() {
    return this.vector.length;
  }

  //-----------

  len() {
    var s = 0;
    for (var dim of this.vector) {
      s += dim ** 2;
    }
    return Math.sqrt(s);
  }

  norm() {
    return this.div(this.dimentions(), this.len(), true)
  }

  add() {
    var input = this.takeInput(...arguments);
    return this.change((x, y) => x + y, input);
  }

  sub() {
    var input = this.takeInput(...arguments);
    return this.change((x, y) => x - y, input);
  }

  mult() {
    var input = this.takeInput(...arguments);
    return this.change((x, y) => x * y, input);
  }

  div() {
    var input = this.takeInput(...arguments);
    return this.change((x, y) => x / y, input);
  }

  dot() {
    var input = this.takeInput(...arguments);
    var res = 0;
    for (var i in this.vector) {
      res += this.vector[i] * input[i]
    }
    return res;
  }

  rotate() {
    // WARNING: only for 3D currently!!!
    var input = this.takeInput(...arguments);

    var [x, y, z] = this.vector;

    // rotate Z
    var t_x = x * Math.cos(input[2]) - y * Math.sin(input[2])
    y = y * Math.cos(input[2]) + x * Math.sin(input[2])
    x = t_x

    // rotate X
    var t_y = y * Math.cos(input[0]) - z * Math.sin(input[0])
    z = z * Math.cos(input[0]) + y * Math.sin(input[0])
    y = t_y

    // rotate Y
    t_x = x * Math.cos(input[1]) + z * Math.sin(input[1])
    z = z * Math.cos(input[1]) - x * Math.sin(input[1])
    x = t_x

    this.vector = [x, y, z];

    return this;
  }
}



var canvas = document.getElementById('canvas')
var ctx = canvas.getContext("2d")


w = 300
h = 286

fov = 0.1
scale = 65;
offset = new Tensor(w / 2 - 5, h / 2 - 92, 0.1);
light = new Tensor(3.5, 0.5, 1).norm();

canvas.width = w;
canvas.height = h;

var verticies = [];
verticies.push(new Tensor(0.5, 1, 0))
verticies.push(new Tensor(0.5, -1, 0))
verticies.push(new Tensor(-1, 0, 0))
verticies.push(new Tensor(0, 0, 2))


var polygons = [];
polygons.push({
  verticies: [0, 3, 1],
  color: 'red',
  nf: 1
});
polygons.push({
  verticies: [2, 3, 0],
  color: 'blue',
  nf: 1
});
polygons.push({
  verticies: [2, 3, 1],
  color: 'green',
  nf: -1
});
polygons.push({
  verticies: [0, 1, 2],
  color: 'yellow',
  nf: -1
});


for (var i = 0; i < polygons.length; i++) {
  polygons[i].id = i;
}

theta = new Tensor(1.5 * Math.PI, 0, 1.5 * Math.PI);

function loop() {
  ctx.clearRect(0, 0, w, h);


  rotated_verticies = [];

  for (var i = 0; i < verticies.length; i++) {
    rotated_verticies.push(verticies[i].copy().rotate(theta));
  }

  // z sorting

  // dots_for_rendering.sort((a,b) => Math.sqrt((b.x)**2 + (b.y)**2) - Math.sqrt((a.x)**2 + (a.y)**2))

  for (var i = 0; i < polygons.length; i++) {
    polygons[i].maxz = -Infinity;
    polygons[i].minz = Infinity;
    polygons[i].midz = 0;


    for (var j = 0; j < polygons[i].verticies.length; j++) {
      var z = rotated_verticies[polygons[i].verticies[j]].vector[2];
      // z += 1 * (Math.random() * 2 - 1)
      if (z > polygons[i].maxz) {
        polygons[i].maxz = z;
      }
      if (z < polygons[i].minz) {
        polygons[i].minz = z;
      }
      polygons[i].midz += z;
    }
    polygons[i].midz /= polygons[i].verticies.length;

  }

  polygons.sort((a, b) => b.midz - a.midz)
  // polygons.sort((a,b) => Math.max(b.maxz - a.minz, b.minz - a.maxz))


  // polygons.sort((a,b) => {
  //   if (a.minz < b.maxz) {
  //     return 0;
  //   }
  //   if (b.minz < a.maxz) {
  //     return -1;
  //   }
  //   return 0;
  // })




  for (var i = 0; i < polygons.length; i++) {
    var polygon_2 = [];

    for (var j = 0; j < polygons[i].verticies.length; j++) {
      var v = rotated_verticies[polygons[i].verticies[j]]
      polygon_2.push(v.vector);
    }

    var norm = getNormal(polygon_2, polygons[i].nf);
    // var rotated_light = light.copy().rotate(theta);
    var brightness = Math.max(0, norm.dot(light))

    //ctx.fillStyle = "hsl(31, "+100+"%, "+(Math.min(9.0*brightness + 40, 100))+"%)";
    ctx.fillStyle = "hsl(190, "+100+"%, "+(Math.min(9.0*brightness + 40, 100))+"%)";
    // ctx.fillStyle = polygons[i].color
    ctx.beginPath();

    for (var j = 0; j < polygons[i].verticies.length; j++) {
      var vertex = rotated_verticies[polygons[i].verticies[j]].copy();
      vertex.mult(scale, scale, 1);
      vertex.add(offset);
      var n = 1 + vertex.vector[2] * fov;
      vertex.div(n, n, 1)

      // console.log(vertex.vector)
      if (j == 0) {
        ctx.moveTo(vertex.vector[0], vertex.vector[1]);
      } else {
        ctx.lineTo(vertex.vector[0], vertex.vector[1]);
      }
    }
    ctx.closePath();
    ctx.fill()
    // ctx.stroke()

    polygons[i].mid = new Tensor(3, 0, true);

    for (var k = 0; k < polygons[i].verticies.length; k++) {
      var vertex = rotated_verticies[polygons[i].verticies[k]].copy();

      vertex.mult(scale, scale, 1);
      vertex.add(offset);


      var n = 1 + vertex.vector[2] * fov;
      vertex.div(n, n, 1)

      polygons[i].mid.add(vertex);
    }

    polygons[i].mid.div(3, polygons[i].verticies.length, true);



    ctx.fillStyle = "red"
    ctx.font = '50px serif';

    // ctx.fillText(polygons[i].id + ", " + polygons[i].nf, polygons[i].mid.vector[0], polygons[i].mid.vector[1])
  }



  // theta.add(theta.vector[0] + (0.01*mouseY - theta.vector[0]) * 0.1, 0, theta.vector[2] + (-0.01*mouseX - theta.vector[2]) * 0.1)

  theta.add(0, -0.0375, 0);

  // fov = (mouseX - w/2) * 0.001
  requestAnimationFrame(loop);
}

loop();

// setInterval(loop, 1000 / 60)


function getNormal(polygon, nf) {

  var Ax = polygon[1][0] - polygon[0][0];
  var Ay = polygon[1][1] - polygon[0][1];
  var Az = polygon[1][2] - polygon[0][2];

  var Bx = polygon[2][0] - polygon[0][0];
  var By = polygon[2][1] - polygon[0][1];
  var Bz = polygon[2][2] - polygon[0][2];


  var Nx = Ay * Bz - Az * By
  var Ny = Az * Bx - Ax * Bz
  var Nz = Ax * By - Ay * Bx

  return new Tensor(nf * Nx, nf * Ny, nf * Nz);
}

function len(p1, p2) {
  return Math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2 + (p2[2] - p1[2]) ** 2);
}



mouseX = 0
mouseY = 0

onmousemove = (e) => {
  mouseX = e.clientX;
  mouseY = e.clientY;
}

<!DOCTYPE html>
<html>

<head>
    <meta charset="UTF-8">
    <meta name=”ad.size” content=”width=300,height=600”>
    <meta name="viewport" content="width=device-width, initial-scale=1">
    <title>...</title>

</head>
<body>

   <canvas id="canvas" width="300" height="238"></canvas>



</body>

</html>

** 编辑：

好的，我们已经对代码进行了大量编辑，请参阅此 fiddle 以及下面的代码片段。还是不能正常工作，我们认为这与这段代码的第一行有关，有什么想法吗？

    if (polygons[i].mid.copy().sub(camera).dot(norm) < 0) {
  var pathelem = document.createElementNS("http://www.w3.org/2000/svg", "path");
  pathelem.setAttribute("d", path);
  pathelem.setAttribute("fill", "hsl(31, "+100+"%, "+(Math.min(9.0*brightness + 40, 100))+"%)");
  svg.appendChild(pathelem);
}

class Tensor {
  constructor(){
    var input = this.takeInput(...arguments);
    this.vector = input;
  }

  takeInput() {
    var a = true;
    for (var arg of arguments) {
      if (typeof arg !== "number"){
        a = false
      }
    }

     if (a && arguments[2] !== true){
       return new Array(...arguments);
     }
     else {
       if (arguments[0] instanceof Tensor){
         return arguments[0].vector;
       }
       else {
          if (typeof arguments[0] === "number" && typeof arguments[1] === "number" && arguments[2] === true) {
            var res = [];
            for (var i = 0; i < arguments[0]; i++) {
              res.push(arguments[1]);
            }
            return res;
          }
       }
     }
  }

  // used for + - * /
  change(f, input){
    for (var i in this.vector) {
      this.vector[i] = f(this.vector[i], input[i]);
    }
    return this;
  }

  copy() {
    return new Tensor(...this.vector);
  }

  dimentions() {
    return this.vector.length;
  }

  //-----------

  len() {
    var s = 0;
    for (var dim of this.vector) {
      s += dim ** 2;
    }
    return Math.sqrt(s);
  }

  norm() {
    return this.div(this.dimentions(), this.len(), true)
  }

  add() {
    var input = this.takeInput(...arguments);
    return this.change((x, y) => x + y, input);
  }

  sub() {
    var input = this.takeInput(...arguments);
    return this.change((x, y) => x - y, input);
  }

  mult() {
    var input = this.takeInput(...arguments);
    return this.change((x, y) => x * y, input);
  }

  div() {
    var input = this.takeInput(...arguments);
    return this.change((x, y) => x / y, input);
  }

  dot() {
    var input = this.takeInput(...arguments);
    var res = 0;
    for (var i in this.vector) {
      res += this.vector[i] * input[i]
    }
    return res;
  }

  rotate() {
    // WARNING: only for 3D currently!!!
    var input = this.takeInput(...arguments);

    var [x, y, z] = this.vector;

    // rotate Z
    var t_x = x * Math.cos(input[2]) - y * Math.sin(input[2])
    y = y * Math.cos(input[2]) + x * Math.sin(input[2])
    x = t_x

    // rotate X
    var t_y = y * Math.cos(input[0]) - z * Math.sin(input[0])
    z = z * Math.cos(input[0]) + y * Math.sin(input[0])
    y = t_y

    // rotate Y
    t_x = x * Math.cos(input[1]) + z * Math.sin(input[1])
    z = z * Math.cos(input[1]) - x * Math.sin(input[1])
    x = t_x

    this.vector = [x, y, z];

    return this;
  }
}


var svg = document.getElementById('svg')


w = 300
h = 286

fov = 0.1
scale = 65;
camera = new Tensor(-w / 2 + 5, -h / 2 + 92, 0.1);
light = new Tensor(3.5, 0.5, 1).norm();

svg.setAttribute('width', w);
svg.setAttribute('height', h);

var vertices = [
  new Tensor(0.5, 1, 0),
  new Tensor(0.5, -1, 0),
  new Tensor(-1, 0, 0),
  new Tensor(0, 0, 2)
];

var polygons = [];
polygons.push({
  vertices: [0, 3, 1],
  color: 'red',
  nf: 1
});
polygons.push({
  vertices: [2, 3, 0],
  color: 'blue',
  nf: 1
});
polygons.push({
  vertices: [2, 3, 1],
  color: 'green',
  nf: -1
});
polygons.push({
  vertices: [0, 1, 2],
  color: 'yellow',
  nf: 1
});


for (var i = 0; i < polygons.length; i++) {
  polygons[i].id = i;
}

theta = new Tensor(1.5 * Math.PI, 0, 1.5 * Math.PI);

function loop() {
  // ctx.clearRect(0, 0, w, h);
  svg.innerHTML = "";


  rotated_vertices = [];

  for (var i = 0; i < vertices.length; i++) {
    rotated_vertices.push(vertices[i].copy().rotate(theta));
  }

  // z sorting

  // dots_for_rendering.sort((a,b) => Math.sqrt((b.x)**2 + (b.y)**2) - Math.sqrt((a.x)**2 + (a.y)**2))

  for (var i = 0; i < polygons.length; i++) {
    polygons[i].maxz = -Infinity;
    polygons[i].minz = Infinity;
    polygons[i].midz = 0;


    for (var j = 0; j < polygons[i].vertices.length; j++) {
      var z = rotated_vertices[polygons[i].vertices[j]].vector[2];
      // z += 1 * (Math.random() * 2 - 1)
      if (z > polygons[i].maxz) {
        polygons[i].maxz = z;
      }
      if (z < polygons[i].minz) {
        polygons[i].minz = z;
      }
      polygons[i].midz += z;
    }
    polygons[i].midz /= polygons[i].vertices.length;


    polygons[i].mid = new Tensor(3, 0, true);

    for (var k = 0; k < polygons[i].vertices.length; k++) {
      var vertex = rotated_vertices[polygons[i].vertices[k]].copy();

      vertex.mult(scale, scale, 1);
      vertex.sub(camera);


      var n = 1 + vertex.vector[2] * fov;
      vertex.div(n, n, 1)

      polygons[i].mid.add(vertex);
    }

    polygons[i].mid.div(3, polygons[i].vertices.length, true);

  }

  polygons.sort((a, b) => b.midz - a.midz)
  // polygons.sort((a,b) => Math.max(b.maxz - a.minz, b.minz - a.maxz))


  // polygons.sort((a,b) => {
  //   if (a.minz < b.maxz) {
  //     return 0;
  //   }
  //   if (b.minz < a.maxz) {
  //     return -1;
  //   }
  //   return 0;
  // })


  for (var i = 0; i < polygons.length; i++) {
    var polygons_embedded_point_coords = [];

    for (var j = 0; j < polygons[i].vertices.length; j++) {
      var v = rotated_vertices[polygons[i].vertices[j]]
      polygons_embedded_point_coords.push(v.vector);
    }

    var norm = getNormal(polygons_embedded_point_coords, polygons[i].nf);
    // var rotated_light = light.copy().rotate(theta);
    var brightness = Math.max(0, norm.dot(light))

    // ctx.fillStyle = "hsl(31, "+100+"%, "+(Math.min(9.0*brightness + 40, 100))+"%)";
    // ctx.fillStyle = polygons[i].color
    // ctx.beginPath();

    var path = [];

    for (var j = 0; j < polygons[i].vertices.length; j++) {
      var vertex = rotated_vertices[polygons[i].vertices[j]].copy();
      vertex.mult(scale, scale, 1);
      vertex.sub(camera);
      var n = 1 + vertex.vector[2] * fov;
      vertex.div(n, n, 1)

      // console.log(vertex.vector)
      if (j == 0) {
        // ctx.moveTo(vertex.vector[0], vertex.vector[1]);
        path.push("M "+vertex.vector[0]+" "+vertex.vector[1]);
      } else {
        path.push("L "+vertex.vector[0]+" "+vertex.vector[1]);
        // ctx.lineTo(vertex.vector[0], vertex.vector[1]);
      }
    }


    // that should work
    if (polygons[i].mid.copy().sub(camera).dot(norm) < 0) {
      var pathelem = document.createElementNS("http://www.w3.org/2000/svg", "path");
      pathelem.setAttribute("d", path);
      pathelem.setAttribute("fill", "hsl(31, "+100+"%, "+(Math.min(9.0*brightness + 40, 100))+"%)");
      svg.appendChild(pathelem);
    }


    // ctx.fillStyle = "red"
    // ctx.font = '15px serif';
    //
    // ctx.fillText(polygons[i].id + ", " + polygons[i].nf, polygons[i].mid.vector[0], polygons[i].mid.vector[1])
  }


  // theta.add(theta.vector[0] + (0.01*mouseY - theta.vector[0]) * 0.1, 0, theta.vector[2] + (-0.01*mouseX - theta.vector[2]) * 0.1)

  theta.add(0, -0.0375, 0);

  // fov = (mouseX - w/2) * 0.001
  requestAnimationFrame(loop);
}

loop();

// setInterval(loop, 1000 / 60)


function getNormal(vertices, nf) {

  var Ax = vertices[1][0] - vertices[0][0];
  var Ay = vertices[1][1] - vertices[0][1];
  var Az = vertices[1][2] - vertices[0][2];

  var Bx = vertices[2][0] - vertices[0][0];
  var By = vertices[2][1] - vertices[0][1];
  var Bz = vertices[2][2] - vertices[0][2];

  var Nx = Ay * Bz - Az * By
  var Ny = Az * Bx - Ax * Bz
  var Nz = Ax * By - Ay * Bx

  return new Tensor(nf * Nx, nf * Ny, nf * Nz);
}

function len(p1, p2) {
  return Math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2 + (p2[2] - p1[2]) ** 2);
}


mouseX = 0
mouseY = 0

onmousemove = (e) => {
  mouseX = e.clientX;
  mouseY = e.clientY;
}

<!DOCTYPE html>
<html lang="en" dir="ltr">

<head>
  <meta charset="utf-8">
  <title></title>
  <script src="Tensor.js"></script>
  <script src="script-tensors-svg.js" async defer></script>
</head>

<body>
  <!-- <canvas id="canvas"></canvas> -->
  <svg id="svg" xmlns="http://www.w3.org/2000/svg"></svg>

</body>

</html>

Answer 1

按平均 Z 排序并不能为您提供可靠的渲染顺序。但是，由于您的形状是凸形的，所以您根本不需要排序。

确保对每个三角形的顶点进行排序，以便始终获得指向外的表面法线。然后，不要渲染任何法线指向相机远离的三角形，即：

if (vector_from_camera_to_poly_midpoint \dot poly_normal < 0) {
   //render the poly
}

现在您将只渲染对象面向相机的一侧 -- none 多边形将重叠，因此您可以按任何顺序渲染它们。

3d 中三角形的 z 排序问题

z sorting issue with triangles in 3d

javascript

sorting

graphics

3d