clipping

我们之前一直在处理的限制：透视投影方程只适用于相机前面的点，由于我们现在可以围绕场景移动和旋转相机，就产生了一个问题：相机后面的点如何处理。

Pz作为除数是有问题的，会出现除以0的现象出现，此外相机后面的点Z的值为负，我们目前无法处理。即使是在相机前面但非常靠近相机的点，也会因为严重扭曲的物体表现形式而造成麻烦。

为了避免这些有问题的情况出现，我们选择不渲染投影平面z=d后面的任何物体。裁剪平面（clipping plane）让我们将任何点分类为裁剪体（clipping volume）的内部（inside）或外部（outside）。

相对于相机而言,由其可见部分组成的空间子集，在这种情况下，裁剪体是z=d前面的任何东西

。我们将只渲染裁剪体内部的这部分场景。

裁剪体

不仅仅是视口平面后面的不用渲染，还有就是靠近投影平面，但在相机右侧或左侧很远的物体的投影，会被投影到视口之外。

每个裁剪平面将空间分成两部分，称之为半空间 half-space。内部半空间是平面前面的所有东西，外部半空间是它后面的所有东西。我们定义的裁剪体的内部是每个裁剪平面定义的内部半空间的交集。

使用平面裁剪场景

首先，尝试一次性对整个物体进行分类。如果一个物体完全在裁剪体内部，则它被接受。如果一个物体完全在裁剪体外部，则将其丢弃。

如果一个物体不能被完全接受或丢弃，就进入下一阶段，对它的每个三角形进行独立的分类。如果三角形完全在裁剪体内部，它是被接受的。如果三角形完全在外部，则将其丢弃。

对于每个既没有被接受也没有被丢弃的三角形，我们需要裁剪三角形本身。将原来的三角形移除，并添加一个或两个新的三角形来覆盖裁剪体内部的三角形部分。

定义裁剪平面

这个方程是很特殊的，其中N恰好是平面的法线，-D是从原点到平面的有符号距离(signed distance)。NP就是求得P到原点距离。

剩余4个平面也是比较特殊，就是它们都经过原点，也就是说D=0。所以我们需要做的是确定它们的法线，为了简化数学计算，我们选择90度视野(FOV),意味着每个平面在45度。

裁剪整个物体

假设我们将每个模型放入能够容纳它的最小球体，称为这个球体为物体的边界球，计算这个球体要比想象得更困难，超出目前学习范围。但我们可以获得边界球得近似表示，首先通过计算模型中所有顶点的坐标平均值来获取球体的球心，然后将半径定义为从球心到它最远的顶点的距离。

这种情况，整个物体都被接受，不需要使用这个平面进行进一步的裁剪（但它仍然可能被另一个平面裁剪）

这种情况，整个物体将被丢弃，不需要进一步的裁剪（无论其他平面怎么样，物体的任何部分都不会在裁剪体内）

这并不能给我们足够的信息确定物体的任意部分是否在裁剪体内，它可能完全在里面，完全在外面，或者部分在里面。进行下一步处理，将模型的三角形逐个进行裁剪计算。

我们将任意点代入平面方程就能得到该点到平面的有符号距离。可以计算从边界球的球心到平面的有符号距离d。所以如果d>r,球体在平面的前面；如果d<-r,则球体在平面的后面，否则|d|<r,表示平面与球体相交。

裁剪三角形

如果球体-平面测试不足以确定一个物体是完全在裁剪平面的前面还是完全在裁剪平面的后面，那么我们必须对每个三角形进行裁剪。

可以查看三角形每个顶点到裁剪平面的有符号距离，以此来根据裁剪平面对三角形每个顶点进行分类。如果距离为0或者正值，则顶点在裁剪平面的前面，否则它在后面。

整个裁剪计算过程，也可以被称为裁剪管线，我们现在拥有了实现我们的裁剪管线所需的所有算法和方程。

裁剪过程的伪代码

ClipScene(scene, planes) {
    clipped_instances = []
    for I in scene.instances { // 遍历所以场景
        clipped_instance = ClipInstance(I, planes) // 对每个场景处理，返回处理后的数据
        if clipped_instance != NULL {
            clipped_instances.append(clipped_instance)
        }
    }
    clipped_scene = Copy(scene)
    clipped_scene.instances = clipped_instances
    return clipped_scene
}

ClipInstance(instance, planes) {
    for P in planes { // 每个面都对场景实例处理，很显然ClipInstanceAgainstPlane会修改instance数据
        instance = ClipInstanceAgainstPlane(instance, plane)
        if instance == NULL {
            return NULL
        }
    }
    return instance // 返回裁剪后的实例
}
ClipInstanceAgainstPlane(instance, plane) {
    // 计算场景球球心到平面的距离
    d = SignedDistance(plane, instance.bounding_sphere.center)

    if d > r {
        return instance // 场景内部
    } else if d < -r { // 场景外部
        return NULL
    } else { // 难以确定裁剪管线处理
        clipped_instance = Copy(instance)
        // 裁剪三角形
        clipped_instance.triangles =
            ClipTrianglesAgainstPlane(instance.triangles, plane)
        return clipped_instance
    }
}

SignedDistance(plane, vertex) {
    normal = plane.normal
    return (vertex.x * normal.x)
        + (vertex.y * normal.y)
        + (vertex.z * normal.z)
        + plane.D
}

ClipTrianglesAgainstPlane(triangles, plane) {
    clipped_triangles = []
    for T in triangles { // 都每个三角形基于平面 plane 都裁剪管线处理
        clipped_triangles.append(ClipTriangle(T, plane))
    }
    return clipped_triangles
}

ClipTriangle(triangle, plane) {
    // 计算三个顶点的有符号距离
    d0 = SignedDistance(plane, triangle.v0)
    d1 = SignedDistance(plane, triangle.v1)
    d2 = SignedDistance(plane, triangle.v2)

    // 所有都是正值则全部都在裁剪面内部
    if {d0, d1, d2} are all positive {
        return [triangle]
    // 所有都是负值全部都在裁剪面外部
    } else if {d0, d1, d2} are all negative {
        return []
    // 三者只有一个为正值
    } else if only one of {d0, d1, d2} is positive {
        let A be the vertex with a positive distance
        compute B' = Intersection(AB, plane)
        compute C' = Intersection(AC, plane)
        return [Triangle(A, B', C')]
    // 三者有一个为负值
    } else /* only one of {d0, d1, d2} is negative */ {
        let C be the vertex with a negative distance
        compute A' = Intersection(AC, plane)
        compute B' = Intersection(BC, plane)
        return [Triangle(A, B, A'), Triangle(A', B, B')]
    }
}

渲染管线中的裁剪过程

裁剪是一种3D操作，它获取场景中的3D物体并在场景中生成一组新的3D物体，或者更准确地说，它计算场景和裁剪体的交集。因此，必须在将物体放置在场景中之后（即使用模型和相机变换之后的顶点），且在透视投影之前进行裁剪。

代码实现


<!--
!!html_title Clipping demo - Computer Graphics from scratch
-->

# Clipping demo

This demo extends the [previous one](raster-08.html) by implementing instance and triangle clipping,
as described in the [Clipping](../11-clipping.html) chapter.

Although the output looks identical, there's a cube located directly behind the camera. Thanks to the
clipping algorithm, it's not visible in the rendered scene.

<div class="centered">
  <canvas id="canvas" width=600 height=600 style="border: 1px grey solid"></canvas>
</div>

<script>
"use strict";

// ======================================================================
//  Low-level canvas access.
// ======================================================================

let canvas = document.getElementById("canvas");
let canvas_context = canvas.getContext("2d");
let canvas_buffer = canvas_context.getImageData(0, 0, canvas.width, canvas.height);

// A color.
function Color(r, g, b) {
  return {
    r, g, b,
    mul: function(n) { return new Color(this.r*n, this.g*n, this.b*n); },
  };
}

// The PutPixel() function.
function PutPixel(x, y, color) {
  x = canvas.width/2 + (x | 0);
  y = canvas.height/2 - (y | 0) - 1;

  if (x < 0 || x >= canvas.width || y < 0 || y >= canvas.height) {
    return;
  }

  let offset = 4*(x + canvas_buffer.width*y);
  canvas_buffer.data[offset++] = color.r;
  canvas_buffer.data[offset++] = color.g;
  canvas_buffer.data[offset++] = color.b;
  canvas_buffer.data[offset++] = 255; // Alpha = 255 (full opacity)
}


// Displays the contents of the offscreen buffer into the canvas.
function UpdateCanvas() {
  canvas_context.putImageData(canvas_buffer, 0, 0);
}


// ======================================================================
//  Data model.
// ======================================================================

// A Point.
function Pt(x, y, h) {
  return {x, y, h};
}


// A 3D vertex.
function Vertex(x, y, z) {
  return {
    x, y, z,
    add: function(v) { return new Vertex(this.x + v.x, this.y + v.y, this.z + v.z); },
    mul: function(n) { return new Vertex(this.x*n, this.y*n, this.z*n); },
    dot: function(vec) { return this.x*vec.x + this.y*vec.y + this.z*vec.z; },
  }
}


// A 4D vertex (a 3D vertex in homogeneous coordinates).
function Vertex4(arg1, y, z, w) {
  if (y == undefined) {
    return { x: arg1.x, y: arg1.y, z: arg1.z, w: arg1.w | 1};
  } else {
    return { x: arg1, y, z, w };
  }
}


// A 4x4 matrix.
function Mat4x4(data) {
  return {data};
}


const Identity4x4 = new Mat4x4([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]);


// A Triangle.
function Triangle(v0, v1, v2, color) {
  return {v0, v1, v2, color};
}


// A Model.
function Model(vertices, triangles, bounds_center, bounds_radius) {
  return {vertices, triangles, bounds_center, bounds_radius};
}


// An Instance.
function Instance(model, position, orientation, scale) {
  this.model = model;
  this.position = position;
  this.orientation = orientation || Identity4x4;
  this.scale = scale || 1.0;
  this.transform = MultiplyMM4(MakeTranslationMatrix(this.position), MultiplyMM4(this.orientation, MakeScalingMatrix(this.scale)));
}


// The Camera.
function Camera(position, orientation) {
  this.position = position;
  this.orientation = orientation;
  this.clipping_planes = [];
}


// A Clipping Plane.
function Plane(normal, distance) {
  return {normal, distance};
}


// ======================================================================
//  Linear algebra and helpers.
// ======================================================================


// Makes a transform matrix for a rotation around the OY axis.
function MakeOYRotationMatrix(degrees) {
  let cos = Math.cos(degrees*Math.PI/180.0);
  let sin = Math.sin(degrees*Math.PI/180.0);

  return new Mat4x4([[cos, 0, -sin, 0],
                     [  0, 1,    0, 0],
                     [sin, 0,  cos, 0],
                     [  0, 0,    0, 1]])
}


// Makes a transform matrix for a translation.
function MakeTranslationMatrix(translation) {
  return new Mat4x4([[1, 0, 0, translation.x],
                     [0, 1, 0, translation.y],
                     [0, 0, 1, translation.z],
                     [0, 0, 0,             1]]);
}


// Makes a transform matrix for a scaling.
function MakeScalingMatrix(scale) {
  return new Mat4x4([[scale,     0,     0, 0],
                     [    0, scale,     0, 0],
                     [    0,     0, scale, 0],
                     [    0,     0,     0, 1]]);
}


// Multiplies a 4x4 matrix and a 4D vector.
function MultiplyMV(mat4x4, vec4) {
  let result = [0, 0, 0, 0];
  let vec = [vec4.x, vec4.y, vec4.z, vec4.w];

  for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++) {
      result[i] += mat4x4.data[i][j]*vec[j];
    }
  }

  return new Vertex4(result[0], result[1], result[2], result[3]);
}


// Multiplies two 4x4 matrices.
function MultiplyMM4(matA, matB) {
  let result = new Mat4x4([[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]);

  for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++) {
      for (let k = 0; k < 4; k++) {
        result.data[i][j] += matA.data[i][k]*matB.data[k][j];
      }
    }
  }

  return result;
}


// Transposes a 4x4 matrix.
function Transposed(mat) {
  let result = new Mat4x4([[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]);
  for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 4; j++) {
      result.data[i][j] = mat.data[j][i];
    }
  }
  return result;
}


// ======================================================================
//  Rasterization code.
// ======================================================================

// Scene setup.
let viewport_size = 1;
let projection_plane_z = 1;


function Interpolate(i0, d0, i1, d1) {
  if (i0 == i1) {
    return [d0];
  }

  let values = [];
  let a = (d1 - d0) / (i1 - i0);
  let d = d0;
  for (let i = i0; i <= i1; i++) {
    values.push(d);
    d += a;
  }

  return values;
}


function DrawLine(p0, p1, color) {
  let dx = p1.x - p0.x, dy = p1.y - p0.y;

  if (Math.abs(dx) > Math.abs(dy)) {
    // The line is horizontal-ish. Make sure it's left to right.
    if (dx < 0) { let swap = p0; p0 = p1; p1 = swap; }

    // Compute the Y values and draw.
    let ys = Interpolate(p0.x, p0.y, p1.x, p1.y);
    for (let x = p0.x; x <= p1.x; x++) {
      PutPixel(x, ys[(x - p0.x) | 0], color);
    }
  } else {
    // The line is verical-ish. Make sure it's bottom to top.
    if (dy < 0) { let swap = p0; p0 = p1; p1 = swap; }

    // Compute the X values and draw.
    let xs = Interpolate(p0.y, p0.x, p1.y, p1.x);
    for (let y = p0.y; y <= p1.y; y++) {
      PutPixel(xs[(y - p0.y) | 0], y, color);
    }
  }
}


function DrawWireframeTriangle(p0, p1, p2, color) {
  DrawLine(p0, p1, color);
  DrawLine(p1, p2, color);
  DrawLine(p0, p2, color);
}


// Converts 2D viewport coordinates to 2D canvas coordinates.
function ViewportToCanvas(p2d) {
  return new Pt(
    p2d.x * canvas.width / viewport_size,
    p2d.y * canvas.height / viewport_size);
}


function ProjectVertex(v) {
  return ViewportToCanvas(new Pt(
    v.x * projection_plane_z / v.z,
    v.y * projection_plane_z / v.z));
}


function RenderTriangle(triangle, projected) {
  DrawWireframeTriangle(
    projected[triangle.v0],
  projected[triangle.v1],
  projected[triangle.v2],
  triangle.color);
}


// Clips a triangle against a plane. Adds output to triangles and vertices.
function ClipTriangle(triangle, plane, triangles, vertices) {
  let v0 = vertices[triangle.v0];
  let v1 = vertices[triangle.v1];
  let v2 = vertices[triangle.v2];

  let in0 = plane.normal.dot(v0) + plane.distance > 0;
  let in1 = plane.normal.dot(v1) + plane.distance > 0;
  let in2 = plane.normal.dot(v2) + plane.distance > 0;

  let in_count = in0 + in1 + in2;
  if (in_count == 0) {
    // Nothing to do - the triangle is fully clipped out.
  } else if (in_count == 3) {
    // The triangle is fully in front of the plane.
    triangles.push(triangle);
  } else if (in_count == 1) {
    // The triangle has one vertex in. Output is one clipped triangle.
  } else if (in_count == 2) {
    // The triangle has two vertices in. Output is two clipped triangles.
  }
}


function TransformAndClip(clipping_planes, model, scale, transform) {
  // Transform the bounding sphere, and attempt early discard.
  let center = MultiplyMV(transform, new Vertex4(model.bounds_center));
  let radius = model.bounds_radius*scale;
  for (let p = 0; p < clipping_planes.length; p++) {
    let distance = clipping_planes[p].normal.dot(center) + clipping_planes[p].distance;
    if (distance < -radius) {
      return null;
    }
  }

  // Apply modelview transform.
  let vertices = [];
  for (let i = 0; i < model.vertices.length; i++) {
    vertices.push(MultiplyMV(transform, new Vertex4(model.vertices[i])));
  }

  // Clip the entire model against each successive plane.
  let triangles = model.triangles.slice();
  for (let p = 0; p < clipping_planes.length; p++) {
    let new_triangles = []
    for (let i = 0; i < triangles.length; i++) {
      ClipTriangle(triangles[i], clipping_planes[p], new_triangles, vertices);
    }
    triangles = new_triangles;
  }

  return Model(vertices, triangles, center, model.bounds_radius);
}


function RenderModel(model) {
  let projected = [];
  for (let i = 0; i < model.vertices.length; i++) {
    projected.push(ProjectVertex(new Vertex4(model.vertices[i])));
  }
  for (let i = 0; i < model.triangles.length; i++) {
    RenderTriangle(model.triangles[i], projected);
  }
}


function RenderScene(camera, instances) {
  let cameraMatrix = MultiplyMM4(Transposed(camera.orientation), MakeTranslationMatrix(camera.position.mul(-1)));

  for (let i = 0; i < instances.length; i++) {
    let transform = MultiplyMM4(cameraMatrix, instances[i].transform);
    let clipped = TransformAndClip(camera.clipping_planes, instances[i].model, instances[i].scale, transform);
    if (clipped != null) {
      RenderModel(clipped);
    }
  }
}


const vertices = [
  new Vertex(1, 1, 1),
  new Vertex(-1, 1, 1),
  new Vertex(-1, -1, 1),
  new Vertex(1, -1, 1),
  new Vertex(1, 1, -1),
  new Vertex(-1, 1, -1),
  new Vertex(-1, -1, -1),
  new Vertex(1, -1, -1)
];

const RED = new Color(255, 0, 0);
const GREEN = new Color(0, 255, 0);
const BLUE = new Color(0, 0, 255);
const YELLOW = new Color(255, 255, 0);
const PURPLE = new Color(255, 0, 255);
const CYAN = new Color(0, 255, 255);

const triangles = [
  new Triangle(0, 1, 2, RED),
  new Triangle(0, 2, 3, RED),
  new Triangle(4, 0, 3, GREEN),
  new Triangle(4, 3, 7, GREEN),
  new Triangle(5, 4, 7, BLUE),
  new Triangle(5, 7, 6, BLUE),
  new Triangle(1, 5, 6, YELLOW),
  new Triangle(1, 6, 2, YELLOW),
  new Triangle(4, 5, 1, PURPLE),
  new Triangle(4, 1, 0, PURPLE),
  new Triangle(2, 6, 7, CYAN),
  new Triangle(2, 7, 3, CYAN)
];

let cube = new Model(vertices, triangles, new Vertex(0, 0, 0), Math.sqrt(3));

let instances = [
  new Instance(cube, new Vertex(-1.5, 0, 7), Identity4x4, 0.75),
  new Instance(cube, new Vertex(1.25, 2.5, 7.5), MakeOYRotationMatrix(195)),
  new Instance(cube, new Vertex(0, 0, -10), MakeOYRotationMatrix(195)),
];

let camera = new Camera(new Vertex(-3, 1, 2), MakeOYRotationMatrix(-30));

let s2 = 1.0 / Math.sqrt(2);
camera.clipping_planes = [
  new Plane(new Vertex(  0,   0,  1), -1), // Near
  new Plane(new Vertex( s2,   0, s2),  0), // Left
  new Plane(new Vertex(-s2,   0, s2),  0), // Right
  new Plane(new Vertex(  0, -s2, s2),  0), // Top
  new Plane(new Vertex(  0,  s2, s2),  0), // Bottom
];

function Render() {
  RenderScene(camera, instances);
  UpdateCanvas();
}

Render();

</script>