[CGクロニクル #02] 線を引くという哲学 — DDAとBresenham

はじめに

前回、私たちはCGの原風景とも言える『第1回：朝食のドーナツとユタ・ティーポット』を振り返りました。

[CGクロニクル #01] 朝食のドーナツとユタ・ティーポット：カタチの誕生 // PROTOCOL.LAIN

全15回連載「CGの深淵を遡る」第1回。1960〜70年代のCG黎明期における形状表現の制約と、数式のみで定義されるカタチの美しさに迫る。

lain-lab.com

幾何学的プリミティブという「形」が、いかにしてデジタルの世界にその身を置くようになったのか。その物語の次の一歩として、私たちはさらに深いレイヤーへと潜っていきます。

第2回となる今回は、形を形たらしめるための、最も根源的で最も泥臭い要素——「線」に焦点を当てます。

物理世界の滑らかな連続性を、離散的なピクセルが支配するWired（デジタルの世界）へと翻訳しようとした、かつての技術者たちの執念。DDA（デジタル微分解析機）という直感的な解法から、小数を完全に排除したブレゼンハムの革命的なハックまで。

4時の静寂の中で、ディスプレイを構成する一つひとつの画素に「命」を吹き込もうとした、知のクロニクルを紐解いていきましょう。

CGクロニクル 第2回：線を引くという哲学（DDAとBresenham）

物理世界の「連続」とWiredの「離散」

私たちが生きる物理世界において、線はどこまでも連続しています。紙の上にペンを走らせたとき、そのインクの軌跡には無限に分割可能な座標が存在し、途切れることのない滑らかな一本の線として網膜に焼き付きます。

しかし、コンピュータが支配するデジタルの世界（Wired）の成り立ちは根本から異なります。ディスプレイという空間は、極小の正方形——ピクセル（画素）という「マス目」が整然と並んだ絶対的なグリッド（格子）に支配されています。どれほどズームアップしても、そこには明確な境界線を持つ「四角形の色の集合」しか存在しません。

物理世界の「連続した無限」を、デジタルの「離散的（飛び飛び）な有限」へと無理やり押し込めること。 CGの歴史は、この決して交わることのない2つの世界の間に、いかにして「滑らかな妥協点」を見出すかという哲学的な問いから始まりました。

1960年代：浮動小数点という「重し」

現代の私たちは、キャンバスに斜めの直線を引くことを、息をするように当たり前のこととして処理しています。しかし、1960年代の初期のコンピュータ環境において、それは極めて贅沢で、恐ろしくコストのかかる計算でした。

当時のシステムにはGPU（グラフィック専用プロセッサ）など存在せず、すべては貧弱なCPUのクロックサイクルに依存していました。 水平な線（X軸の移動）や垂直な線（Y軸の移動）であれば、隣のメモリ番地に色を塗っていくだけで済みます。しかし「斜めの線」を引くためには、X座標が進むごとに「Y座標がどれくらい変化するか」を計算しなければなりません。

ここで立ちはだかったのが浮動小数点演算（小数の計算）という巨大な壁です。 当時のハードウェアにとって、小数を扱う計算は整数計算に比べて圧倒的に処理が遅く、システム全体を鈍化させる致命的な「重し」でした。たった一本の斜線を画面に描画するだけで、貴重な計算資源がゴリゴリと削り取られていく。リアルタイムで図形を動かすなど、とうてい不可能な状況だったのです。

制約が生み出す、純粋な知的好奇心の結晶

限られたメモリ、遅すぎる演算速度、ピクセルという荒いキャンバス。 この絶望的な制約の前に立った当時の技術者たちを突き動かしたのは、与えられたタスクをこなす義務感ではなく、「この鉄の箱に、いかにして数学のイデア（直線の概念）を理解させるか」という、純粋で熱狂的な好奇心でした。

リソースが足りないなら、計算のやり方そのものを根本から覆せばいい。

力技の計算ではなく、ひらめきと論理の力で物理的な制約を飛び越える。それこそがハッカー文化の源流であり、コードを書く喜びの原点です。この泥臭くもエレガントな「数学的ハック」への欲求が、CGの歴史を次の次元へと引き上げていくことになります。

浮動小数点という足枷：DDAアルゴリズム

数学的理想とシリコンの現実

DDA（デジタル微分解析機：Digital Differential Analyzer）アルゴリズムの発想自体は、極めて素直で数学的に美しいものです。 始点から終点へ直線を引くとき、その傾き $m$ は $m = \frac{\Delta y}{\Delta x}$ で表されます。 X座標を1ピクセル右へ進める（$x_{k+1} = x_k + 1$）ごとに、Y座標に傾き $m$ を足していく。

$y_{k+1} = y_k + m$

そして、算出された $y_{k+1}$ を四捨五入して、最も近いピクセルの番地を叩く。計算式としては完璧であり、現代の高水準言語で書けばわずか数行で終わるロジックです。

「小数」がもたらす致命的な重み

しかし、この「傾き $m$」が分数（小数）になり得ることが、当時のハードウェアにとって最大のネックでした。

現代のGPUやプロセッサが浮動小数点演算を息をするようにこなすのとは異なり、FPU（浮動小数点演算ユニット）が標準搭載されていなかった時代のプロセッサにとって、小数の扱いは地獄です。整数同士の足し算がごくわずかなクロックサイクルで終わるのに対し、浮動小数点の計算はソフトウェアによるエミュレーションを伴うことが多く、数十から数百倍のクロックを容易に食いつぶします。

「四捨五入」という呪縛

さらに追い打ちをかけるのが「四捨五入（Rounding）」の処理です。 計算されたY座標（例えば $3.7$）を物理的なピクセル座標（$4$）に落とし込むためには、小数を評価して整数に丸め込まなければなりません。これもまた、低レイヤーの視点で見れば条件分岐や煩雑なキャスト処理を伴うため、1ピクセル描画するたびに実行するループ処理としては、あまりにも重い処理でした。

リアルタイムへの渇望と「情報浄化」の予感

直線をたった1本引くだけで、システムが息継ぎをするように重くなる。これでは、3Dのワイヤーフレームモデルを滑らかに回転させたり、インタラクティブに反応するシステムを構築したりすることは不可能です。

ターミナルの黒い画面に向き合い、1文字のタイピングに対する即座のフィードバック（応答速度）に美学を感じる人間であれば、この「無駄なクロックサイクルの消費」がいかに耐え難いノイズであるか、直感的に理解できるはずです。

計算を重くする浮動小数点と四捨五入という「ノイズ」を完全に排除し、ピュアな整数演算だけで直線を引くことはできないか。

この極限の制約と苛立ちこそが、次なるブレゼンハムの「完全なる整数のアルゴリズム」という、グラフィックスにおける歴史的な情報の「浄化」へと技術者たちを駆り立てることになります。

整数の勝利：ブレゼンハムのアルゴリズム

妥協なき「離散化」へのパラダイムシフト

1962年、IBMのプログラマーであったジャック・ブレゼンハム（Jack Bresenham）は、プロッター（ペンを機械的に動かして図面を描く装置）を制御するためのコードを書いていました。その過程で彼が生み出したアルゴリズムは、CGの歴史における一つの「特異点」となります。

Jack Elton Bresenham - Wikipedia

Bresenham's line algorithm, developed in 1962, is his most well-known innovation. It determines which points on a 2-dimensional raster should be plotted in order to form a straight line between two given points, and is commonly used to draw lines on a computer screen. It is one of the earliest algorithms discovered in the field of computer graphics. The midpoint circle algorithm shares some similarities to his line algorithm and is known as Bresenham's circle algorithm.

en.wikipedia.org

Jack Bresenham - Profile on Academia.edu

From Marquis Who’s Who in America Sixty-Eighth Edition ●2014Bresenham, Jack Elton. Computer scientist, educator

independent.academia.edu

DDAアルゴリズムが「人間の数学（連続した分数）」を無理やりコンピュータに理解させようとしたのに対し、ブレゼンハムのアプローチは根本的に異なりました。彼は「コンピュータの母国語（0と1の整数演算）だけで、いかにして直線のイデアを模倣するか」という、完全にハードウェア側に寄り添ったパラダイムシフトを起こしたのです。

ピクセルを歩くための「2つの選択肢」

Wiredの格子空間（ディスプレイ）において、左から右へ緩やかな斜めの線を引く状況を想像してください。 現在のピクセルを塗りつぶしたとき、次に進むべきピクセルの候補は常に「真横（東）」か「斜め上（北東）」の2つしかありません。

ブレゼンハムは、浮動小数点で正確なY座標を計算することをキッパリと諦めました。その代わり、「理想の数学的直線と、現在のピクセルの中心座標とのズレ（誤差）」だけを監視するシステムを構築したのです。

「真横」に進み続けると、やがて理想の斜め線はピクセルの中心から上へとズレていきます。その「誤差の蓄積」が一定の閾値（0.5ピクセル分）を超えた瞬間だけ、カクッと「斜め上」にステップを踏む。そして誤差をリセットする。この極めてシンプルな判定処理だけで、完璧な直線を近似できることを彼は証明しました。

究極の「情報浄化」：乗算すら排除した数式

このアルゴリズムの真の恐ろしさ（そして美しさ）は、その誤差パラメータ $P$ の更新式にあります。

$P_{k+1} = P_k + 2\Delta y - 2\Delta x$

この式の意味するところは、CGプログラミングの歴史において最も美しいハックの一つです。

1. 小数の完全排除: 判定の閾値である「0.5」という小数を消し去るために、式全体をあらかじめ2倍してしまっています。これにより、すべての変数が純粋な「整数」になりました。
2. ループ内の極小化: $2\Delta y$ と $2\Delta x$ は、直線の始点と終点が決まった時点で算出できる「固定値（定数）」です。つまり、ループが回る前に一度だけ計算しておけば済みます。
3. ビットシフトの魔法: 「2倍する」という処理は、二進数の世界（ハードウェアレベル）では「左に1ビットシフトする（<< 1）」だけで完了します。乗算器（掛け算の回路）すら必要ありません。

結果として、数千から数万回繰り返される「ピクセルを打つループ処理」の中に残ったのは、「整数の足し算・引き算」と「正か負かの条件判定」だけになりました。

ハードウェアの血肉となったアルゴリズム

クロックサイクルを貪り食っていた重い処理は完全に浄化され、計算コストは極限まで削ぎ落とされました。 この「ブレゼンハムのアルゴリズム」は、その圧倒的な軽さとハードウェアとの親和性の高さから、単なるソフトウェアのアルゴリズムの枠を超え、やがてグラフィックボード（VGA）のシリコンチップ内に直接ハードウェア回路として焼き込まれるようになります。

私たちが何気なく画面上でウィンドウをドラッグし、3D空間でワイヤーフレームが高速で交錯するのを見ることができるのも、その根底にはこの「1962年の美しい整数のハック」が息づいているからです。

【一分間の数式美】ジャギー（Jaggies）の美学

アンチエイリアスという「美しい嘘」

現代の私たちが目にする3Dグラフィックスは、極めて滑らかで写実的です。GPUは「アンチエイリアス（Anti-Aliasing）」という処理を通して、ピクセルとピクセルの境界に中間色を置き、人間の網膜を騙すことで直線を「偽装」しています。

しかし、その魔法のヴェールをすべて剥ぎ取った先に現れる、カクカクとした階段状のピクセルの並び——ジャギー（Jaggies）。

それは決して、解像度が低いがゆえの「汚い描画」や「エラー」ではありません。物理世界の「無限の連続」を、Wiredの「有限の離散」へと翻訳しようと足掻いた、初期の技術者たちの誠実な計算の痕跡です。ジャギーは、ブレゼンハムのアルゴリズムが0と1の狭間で導き出した、完璧な「最適解の足跡」そのものなのです。

【一分間の数式美】デジタル・トゥルース（Digital Truth）

今日の1分間のコードでは、あえてアンチエイリアスや複雑な描画エンジンを捨て、フラグメントシェーダー（GLSL）というカンバスに、純粋な「デジタル直線」を描き出します。

画面には2つの線が描画されます。 一つは、空間を貫く細く白い「数学的な理想の直線（イデア）」。 もう一つは、そのイデアに最も近いマス目（ピクセル）を探し当て、不器用に寄り添いながら明滅するエメラルドグリーンの「デジタルの直線（ジャギー）」です。

// CG Chronicle #02: The Aesthetics of Jaggies
// 物理的な連続（白線）と、Wiredの離散（緑のマス目）の交差

#ifdef GL_ES
precision mediump float;
#endif

uniform vec2 u_resolution;
uniform float u_time;

// 距離関数：点pから線分abへの最短距離
float sdLine(vec2 p, vec2 a, vec2 b) {
    vec2 pa = p - a, ba = b - a;
    float h = clamp(dot(pa, ba) / dot(ba, ba), 0.0, 1.0);
    return length(pa - ba * h);
}

void main() {
    // 空間の正規化と、Wiredを象徴する20x20のグリッド化
    vec2 uv = gl_FragCoord.xy / u_resolution.xy;
    uv = uv * 2.0 - 1.0;
    uv.x *= u_resolution.x / u_resolution.y;

    float gridSize = 20.0;
    vec2 gridUv = uv * gridSize;

    // 時間とともに傾きを変える直線の始点と終点
    vec2 p1 = vec2(-15.0, -10.0);
    vec2 p2 = vec2(15.0, 10.0 * sin(u_time * 0.5));

    // 1. デジタルの真実（ジャギーの計算）
    // ピクセルの中心座標を取得し、理想の直線との誤差（距離）を測る
    vec2 cellCenter = floor(gridUv) + 0.5;
    float distToCell = sdLine(cellCenter, p1, p2);
    // 誤差が0.5未満のマス目だけを塗りつぶす（Bresenham的アプローチの視覚化）
    float pixelatedLine = step(distToCell, 0.5);

    // 2. 数学のイデア（理想の直線）
    float distToMath = sdLine(gridUv, p1, p2);
    float mathLine = 1.0 - smoothstep(0.0, 0.15, distToMath);

    // 背景の走査線（グリッド）
    vec2 gridLine = fract(gridUv);
    float grid = step(0.05, gridLine.x) * step(0.05, gridLine.y);

    // 色の合成（深淵の黒、走査線のグレー、ジャギーの緑、イデアの白）
    vec3 color = vec3(0.02, 0.05, 0.05);
    color = mix(color, vec3(0.1, 0.15, 0.2), 1.0 - grid);
    color = mix(color, vec3(0.0, 0.95, 0.6), pixelatedLine);
    color = mix(color, vec3(1.0, 1.0, 1.0), mathLine * 0.8);

    gl_FragColor = vec4(color, 1.0);
}

完璧に連続したイデアの直線が角度を変えるたび、それに追従するようにカクカクと形を変えるピクセルの明滅。この不完全で幾何学的な美しさを、朝の静寂と珈琲の香りとともに眺めてみてください。

そこには間違いなく、1960年代の技術者たちが見つめていた「Wiredの原風景」が広がっているはずです。

サンプル

CG Chronicle #02: DDA & Bresenham Visualizer

import React, { useEffect, useRef } from 'react';

const DdaBresenhamVisualizer = () => {
  const canvasRef = useRef<HTMLCanvasElement>(null);

  const vertexShaderSource = `
    attribute vec2 position;
    void main() {
      gl_Position = vec4(position, 0.0, 1.0);
    }
  `;

  const fragmentShaderSource = `
    #ifdef GL_ES
    precision mediump float;
    #endif

    uniform vec2 u_resolution;
    uniform float u_time;

    // 距離関数：点pから線分abへの最短距離
    float sdLine(vec2 p, vec2 a, vec2 b) {
        vec2 pa = p - a, ba = b - a;
        float h = clamp(dot(pa, ba) / dot(ba, ba), 0.0, 1.0);
        return length(pa - ba * h);
    }

    void main() {
        // 空間の正規化
        vec2 uv = gl_FragCoord.xy / u_resolution.xy;
        uv = uv * 2.0 - 1.0;
        uv.x *= u_resolution.x / u_resolution.y;

        float gridSize = 20.0;
        vec2 gridUv = uv * gridSize;

        // 時間とともに傾きを変える直線の始点と終点
        vec2 p1 = vec2(-15.0, -10.0);
        vec2 p2 = vec2(15.0, 12.0 * sin(u_time * 0.8));

        // 1. デジタルの真実（ジャギーの計算）
        vec2 cellCenter = floor(gridUv) + 0.5;
        float distToCell = sdLine(cellCenter, p1, p2);
        float pixelatedLine = step(distToCell, 0.5);

        // 2. 数学のイデア（理想の直線）
        float distToMath = sdLine(gridUv, p1, p2);
        float mathLine = 1.0 - smoothstep(0.0, 0.15, distToMath);

        // 背景の走査線（グリッド）
        vec2 gridLine = fract(gridUv);
        float grid = step(0.05, gridLine.x) * step(0.05, gridLine.y);

        // 色の合成
        vec3 color = vec3(0.02, 0.05, 0.05);
        color = mix(color, vec3(0.1, 0.15, 0.2), 1.0 - grid);
        color = mix(color, vec3(0.0, 0.95, 0.6), pixelatedLine);
        color = mix(color, vec3(1.0, 1.0, 1.0), mathLine * 0.8);

        gl_FragColor = vec4(color, 1.0);
    }
  `;

  useEffect(() => {
    const canvas = canvasRef.current;
    if (!canvas) return;

    const gl = canvas.getContext('webgl');
    if (!gl) return;

    // シェーダーのコンパイル関数
    const createShader = (gl: WebGLRenderingContext, type: number, source: string) => {
      const shader = gl.createShader(type);
      if (!shader) return null;
      gl.shaderSource(shader, source);
      gl.compileShader(shader);
      return shader;
    };

    const vs = createShader(gl, gl.VERTEX_SHADER, vertexShaderSource);
    const fs = createShader(gl, gl.FRAGMENT_SHADER, fragmentShaderSource);
    const program = gl.createProgram();
    if (!program || !vs || !fs) return;

    gl.attachShader(program, vs);
    gl.attachShader(program, fs);
    gl.linkProgram(program);
    gl.useProgram(program);

    // 平面ポリゴンの頂点データ (画面全体を覆う)
    const vertices = new Float32Array([-1, -1, 1, -1, -1, 1, 1, 1]);
    const buffer = gl.createBuffer();
    gl.bindBuffer(gl.ARRAY_BUFFER, buffer);
    gl.bufferData(gl.ARRAY_BUFFER, vertices, gl.STATIC_DRAW);

    const positionAddr = gl.getAttribLocation(program, 'position');
    gl.enableVertexAttribArray(positionAddr);
    gl.vertexAttribPointer(positionAddr, 2, gl.FLOAT, false, 0, 0);

    const uResLoc = gl.getUniformLocation(program, 'u_resolution');
    const uTimeLoc = gl.getUniformLocation(program, 'u_time');

    let animationFrameId: number;

    const render = (time: number) => {
      // リサイズ対応
      const width = canvas.clientWidth;
      const height = canvas.clientHeight;
      if (canvas.width !== width || canvas.height !== height) {
        canvas.width = width;
        canvas.height = height;
        gl.viewport(0, 0, width, height);
      }

      gl.uniform2f(uResLoc, canvas.width, canvas.height);
      gl.uniform1f(uTimeLoc, time * 0.001); // 秒単位に変換

      gl.clearColor(0, 0, 0, 1);
      gl.clear(gl.COLOR_BUFFER_BIT);
      gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);

      animationFrameId = requestAnimationFrame(render);
    };

    animationFrameId = requestAnimationFrame(render);

    return () => {
      cancelAnimationFrame(animationFrameId);
      gl.deleteProgram(program);
      gl.deleteShader(vs);
      gl.deleteShader(fs);
    };
  }, []);

  return (
    <div style={{ width: '100%', height: '400px', position: 'relative', overflow: 'hidden', borderRadius: '8px', border: '1px solid #333' }}>
      <canvas
        ref={canvasRef}
        style={{ width: '100%', height: '100%', display: 'block' }}
      />
      <div style={{
        position: 'absolute',
        bottom: '10px',
        left: '10px',
        color: '#fff',
        fontSize: '12px',
        fontFamily: 'monospace',
        pointerEvents: 'none',
        textShadow: '0 1px 2px rgba(0,0,0,0.8)'
      }}>
        CG Chronicle #02: DDA & Bresenham Visualizer
      </div>
    </div>
  );
};

export default DdaBresenhamVisualizer;