バックフェースカリング

draft CG

面が隙間なく閉じた不透明な物体では、裏を向いた面は必ず手前側の面に隠れます。
視点からは見えない、物体の裏面はそもそも表示されないため、わざわざレンダリングする必要はありません。このような不可視となる裏面(back face)をあらかじめ除外する処理がバックフェースカリングです。

- (保留中)

隠面消去 では、重なり合う面のどちらが手前にあるかを確かめて、隠れる面を落としていきます。稜線を対象にする陰線消去も同じで、扱う面や線が増えるほど、この判定は重くなります。

裏面の判別
CG

インライン数式の前後には空白を空ける

面が裏を向いているかどうかは、面に垂直な向きと、その面から視点を見た向きを比べればわかります。

面に垂直で表側を向くベクトルが、その面の法線です。この法線ベクトルを 、面から視点へ向かう視点方向ベクトルを とします。

法線とは何かについてNote形式で補足

面が視点側を向いているなら、 と は同じ側を指すため、なす角は鋭角(直角より小さい角)になります。逆に、裏を向いた面では、なす角が鈍角(直角より大きい角)になります。

Action

次の点に着目して、デモを観察してみよう

  • 注目する面を切り替えると、同じ視点に対してでも、面によってなす角を示す扇が鋭角と鈍角に分かれること
  • 鈍角になる面では、視点方向ベクトルが立体の内部を貫くこと
  • 裏面を外すを切り替えると、閉じた物体からどれだけの面が取り除かれているか
! demo (Three.js)

モバイルだとベクトルが太すぎ、ラベルが小さすぎて読めないので、調整

Three.jsによる実装概要
/** 法線ベクトルの矢印の長さ。立方体の外へ十分に伸ばして、面から立つ向きを読みやすくする */
const NORMAL_LENGTH = 1.35

/** 矢印の軸の太さ(ピクセル)と、先端(円錐)の大きさ */
const LINE_WIDTH = 4
const ARROW_RADIUS = 0.09
const ARROW_HEIGHT = 0.28

/** なす角を示す扇の半径と分割数。法線ベクトルの矢印より内側に収める */
const SECTOR_RADIUS = 0.45
const SECTOR_SEGMENTS = 36

/** 面の不透明度。立体の内部を貫く視点方向ベクトルが透けて見える程度に薄くする */
const FACE_OPACITY = 0.5

/** 扇の不透明度。扇と法線ベクトルの矢印は同じ色なので、わずかに透かして見分けられるようにする */
const SECTOR_OPACITY = 0.72

/**
 * 半透明なものの描画順。数が小さいほど先に描かれ、あとから描いたものが上に重なる。
 * 稜線と矢印は不透明なので、半透明なものより先に描かれる。
 * 扇は既定の 0 のままなので面より先に描かれ、立体の内部に入り込んだ部分も面越しに透ける
 */
const FACE_ORDER = 1

/** ConeGeometry が既定で向いている方向 */
const CONE_UP = new Vector3(0, 1, 0)

// 始点から終点へ向かう矢印。表裏で色を変えるので、色をあとから差し替えられるようにする
const createArrow = (color: string) => {
  // 線の太さをピクセルで指定できるようにする。素の Line では太さが常に 1 px になる
  const shaftPositions = new Float32Array(6)
  const shaftGeometry = new LineSegmentsGeometry()
  const shaftMaterial = new LineMaterial({ color, alphaToCoverage: true })
  shaftMaterial.linewidth = LINE_WIDTH
  const shaft = new LineSegments2(shaftGeometry, shaftMaterial)

  const headGeometry = new ConeGeometry(ARROW_RADIUS, ARROW_HEIGHT, 16)
  const headMaterial = new MeshBasicMaterial({ color })
  const head = new Mesh(headGeometry, headMaterial)

  const group = new Group()
  group.add(shaft, head)

  const direction = new Vector3()
  const shaftEnd = new Vector3()

  return {
    object: group,
    setEnds: (from: Vector3, to: Vector3) => {
      direction.copy(to).sub(from).normalize()

      // 円錐の底面が線の先端に来るよう、矢印の高さのぶん手前で線を止める
      shaftEnd.copy(to).addScaledVector(direction, -ARROW_HEIGHT)
      shaftPositions.set([from.x, from.y, from.z, shaftEnd.x, shaftEnd.y, shaftEnd.z])
      shaftGeometry.setPositions(shaftPositions)

      // ConeGeometry の原点は円錐の中心なので、半分ぶん戻した位置に置く
      head.position.copy(to).addScaledVector(direction, -ARROW_HEIGHT / 2)
      head.quaternion.setFromUnitVectors(CONE_UP, direction)
    },
    setColor: (next: string) => {
      shaftMaterial.color.set(next)
      headMaterial.color.set(next)
    }
  }
}

// 2 つの向きがなす角を、塗りつぶした扇で示す。
// 角の大小がそのまま扇の広さになるので、鋭角か鈍角かを面積で読み取れる
const createSector = (color: string) => {
  // 要(かなめ)と弧の両端で 1 枚の三角形。それを分割数だけ並べて扇にする
  const position = new Float32BufferAttribute(new Float32Array(SECTOR_SEGMENTS * 3 * 3), 3)
  const geometry = new BufferGeometry().setAttribute("position", position)
  const material = new MeshBasicMaterial({
    color,
    side: DoubleSide,
    transparent: true,
    opacity: SECTOR_OPACITY,
    // 扇の縁は法線ベクトルの矢印と重なる。扇をわずかに奥へずらして z ファイティングを避ける
    polygonOffset: true,
    polygonOffsetFactor: 1,
    polygonOffsetUnits: 1
  })
  const mesh = new Mesh(geometry, material)

  const axis = new Vector3()
  const current = new Vector3()
  const next = new Vector3()

  return {
    object: mesh,
    // from・to は単位ベクトル。from を to まで回した範囲が扇になる
    setAngle: (center: Vector3, from: Vector3, to: Vector3) => {
      // 2 つの向きが張る平面に垂直な向きが回転軸
      axis.crossVectors(from, to).normalize()
      const angle = Math.acos(MathUtils.clamp(from.dot(to), -1, 1))

      for (let index = 0; index < SECTOR_SEGMENTS; index++) {
        current
          .copy(from)
          .applyAxisAngle(axis, (angle * index) / SECTOR_SEGMENTS)
          .multiplyScalar(SECTOR_RADIUS)
          .add(center)
        next
          .copy(from)
          .applyAxisAngle(axis, (angle * (index + 1)) / SECTOR_SEGMENTS)
          .multiplyScalar(SECTOR_RADIUS)
          .add(center)

        position.setXYZ(index * 3, center.x, center.y, center.z)
        position.setXYZ(index * 3 + 1, current.x, current.y, current.z)
        position.setXYZ(index * 3 + 2, next.x, next.y, next.z)
      }
      position.needsUpdate = true
    },
    setColor: (nextColor: string) => material.color.set(nextColor)
  }
}

// 面を囲む頂点から、面の中心と、外を向く法線ベクトル n を求める
const measureFace = (vertices: Vector3[]) => {
  const center = new Vector3()
  for (const vertex of vertices) center.add(vertex)
  center.divideScalar(vertices.length)

  // 隣り合う 2 辺の外積は面に垂直になる。頂点を外から見て反時計回りに並べてあるので、
  // 得られる向きは物体の外側、つまり面の表側を指す
  const normal = new Vector3()
    .subVectors(vertices[1], vertices[0])
    .cross(new Vector3().subVectors(vertices[2], vertices[1]))
    .normalize()

  return { center, normal }
}

// 立方体の 6 面を、外から見て反時計回りに並べた頂点として得る。先頭は +z の面
const faceVertices = createCubeFaces()

// 面ごとに 1 つの Mesh を作る。表裏で色を変え、外した面だけを消すため、面ごとに独立させる。
// 深度を書かない半透明にして、立体の内部を通るベクトルが透けて見えるようにする
const faces = faceVertices.map((vertices) => {
  const geometry = new BufferGeometry()
  geometry.setAttribute("position", new Float32BufferAttribute(createFacePositions(vertices), 3))
  const material = new MeshBasicMaterial({
    side: DoubleSide,
    transparent: true,
    opacity: FACE_OPACITY,
    depthWrite: false
  })
  const mesh = new Mesh(geometry, material)
  mesh.renderOrder = FACE_ORDER
  scene.add(mesh)

  return { ...measureFace(vertices), material, mesh }
})

// 面を外しても立方体の形が読めるよう、稜線は常に残す
const boxGeometry = new BoxGeometry(CUBE_HALF * 2, CUBE_HALF * 2, CUBE_HALF * 2)
const edgeGeometry = new EdgesGeometry(boxGeometry)
boxGeometry.dispose()
scene.add(new LineSegments(edgeGeometry, new LineBasicMaterial({ color: EDGE_COLOR })))

// 表裏を判定する視点。観察するカメラとは別の点で、6 面が表 3 枚・裏 3 枚に分かれる位置に固定する
const EYE = new Vector3(
  EYE_DISTANCE * Math.sin(EYE_AZIMUTH),
  EYE_HEIGHT,
  EYE_DISTANCE * Math.cos(EYE_AZIMUTH)
)

// 注目する 1 面にだけ、法線ベクトル n・視点方向ベクトル e・なす角の扇を添える
const normalArrow = createArrow(FRONT_ACCENT)
const eyeArrow = createArrow(EYE_COLOR)
const sector = createSector(FRONT_ACCENT)
scene.add(normalArrow.object, eyeArrow.object, sector.object)

const toEye = new Vector3()
for (const face of faces) {
  // 面から視点へ向かう視点方向ベクトル e
  toEye.subVectors(EYE, face.center)

  // n と e の内積。負なら、なす角が鈍角=裏を向いた面
  const isBack = face.normal.dot(toEye) < 0

  face.material.color.set(isBack ? BACK_FACE_COLOR : FRONT_FACE_COLOR)
  // 裏面を外すと、裏を向いた面だけが消える
  face.mesh.visible = !(isBack && cullBackFaces)
}

// 注目する面のなす角。裏を向いた面では e が立体の内部を貫く
const target = faces[targetFace]
toEye.subVectors(EYE, target.center)
const accent = target.normal.dot(toEye) < 0 ? BACK_ACCENT : FRONT_ACCENT

const normalEnd = target.center.clone().addScaledVector(target.normal, NORMAL_LENGTH)
normalArrow.setEnds(target.center, normalEnd)
normalArrow.setColor(accent)

const eyeDirection = toEye.clone().normalize()
eyeArrow.setEnds(target.center, EYE)
sector.setAngle(target.center, target.normal, eyeDirection)
sector.setColor(accent)

なす角が鈍角かどうかは、 と の内積の符号で調べられます。裏面が満たす判別式は次の通りです。

この式が成り立つ面を不可視として外し、残った面だけを次の処理へ渡します。

内積に関するNote内で、余弦とは何かについても触れる

内積は、2つのベクトルの長さと、なす角の余弦をかけ合わせた値です。長さは負にならないため、値の符号を決めているのは余弦だけで、なす角が直角を超えたところで負に転じます。

このような判定を面上の任意の点で行う場合は、面を構成する頂点を 、視点を とすると、次の判別式が使える:

凸形状と凹形状

- (保留中)

裏面を外した後に何が残るかは、物体の形で変わります。

どこにもへこみのない凸形状なら、表を向いた面どうしが重なることはありません。バックフェースカリングを終えた時点で残っているのはすべて見えている面で、隠面消去 はこれで完了します。

一方、へこんだ部分をもつ凹形状では、表を向いた面どうしでも一方が他方に隠れます。
つまり、バックフェースカリングだけでは、見えない面をすべて隠しきれないのです。

凸形状と凹形状で、バックフェースカリングの後に残る隠れを比べる図。同じ視点から見た凸形状と凹形状を並べ、裏を向いた面を取り除いた状態を描いて、凸形状では残った面が互いに隠れず、凹形状では表を向いた面どうしに隠れが残ることを示す

物体が2つ以上ある場面も同様に、別の物体に隠される面が残ってしまいます。

このように、バックフェースカリングだけで隠面消去が完了するとは限りませんが、隠面消去の前に面の数を減らす下ごしらえとしては使えます。たとえば閉じた物体では面のおよそ半分が裏を向いているため、バックフェースカリングを適用すると、面のデータは半分ほどまで減ります。

- (保留中)

残った面どうしの前後関係を決めるのが、隠面消去法の仕事です。

隠面消去法の分類
CG

隠面消去法はいくつもありますが、どの面が見えているかという可視性を、どの空間で判定するかで整理できます。
3次元の形状をそのまま扱うのが物体空間アルゴリズム、投影を終えた平面の上で扱うのが画像空間アルゴリズムです。
この2つの中間にあたるのが優先順位アルゴリズムです。

物体空間アルゴリズム

物体空間アルゴリズムは、投影する前の3次元空間で、面と面のどちらが手前にあるかを幾何的に計算する手法です。

求まるのは面の見えている範囲そのものなので、結果は画面の解像度に左右されません。解像度を変えても、可視性の計算はそのまま使えます。

そのかわり、面どうしの隠れ方を組み合わせごとに調べることになるため、計算量は面の数の2乗に比例して増えます。

稜線の見えている区間を求める陰線消去も、この空間での計算に向いています。

画像空間アルゴリズム

画像空間アルゴリズムは、投影を終えたあとの平面上で、位置ごとにそこで見える面を決める手法です。この平面は投影された像が並ぶ投影面 で、CGではスクリーンとも呼ばれます。

判定の単位になるのは、スクリーンを構成する画素(ピクセル)1つずつか、水平に並ぶ画素の列、つまりスキャンライン(走査線)1本ずつです。スキャンライン法 は走査線ごとに、Zバッファ法 とレイトレーシング法 は画素ごとに、可視性を決めていきます。

計算量は面の数と画素数の積に比例するため、面が増えても2乗のようには膨らみません。ただし解像度を上げればその分だけ計算量が増え、得られる結果も解像度に縛られます。

物体空間と画像空間の、可視性を判定する場所の違いを対比する図。2枚の面が重なって見える同じ場面を2通りに描き、物体空間では3次元空間で面どうしの前後関係を求めること、画像空間ではスクリーン上の画素やスキャンラインごとに見える面を決めることを示す

優先順位アルゴリズム

優先順位アルゴリズム は、面を奥から順に並べ替えてから、その順に描き重ねていく手法です。

並べ替えで前後関係を決めるところは3次元空間の計算ですが、どちらが見えるかは、後から描いた面が先の面を塗り替えることで決まります。面の順序は物体空間で決め、見える面はスクリーン上で決まるという、2つの空間にまたがった手法だといえます。