path-tracing-reverse

パストレーシングのリバースエンジニアリング

概要

このスキルでは、高精度な出力の一致が求められるグラフィックスレンダリング用バイナリ（レイトレーサー、パストレーサー、レンダラー）をリバースエンジニアリングするための体系的なアプローチを紹介します。主な課題は、ピクセル単位またはそれに近い精度で再現すること（類似度 >99%）です。そのため、近似ではなく、アルゴリズム、定数、レンダリングパラメーターを正確に抽出する必要があります。

成功のための重要な要素

高い類似度（>99%）が求められる場合：

1. 定数の正確な抽出が必須です - 浮動小数点値を推測したり近似したりすると、うまくいきません
2. アルゴリズムを完全に再構築します - 理解が不完全だと、広範囲のピクセルにわたって系統的な誤差が生じます
3. コンポーネントを個別に切り分けます - 各レンダリングコンポーネント（空、地面、オブジェクト、ライティング）を個別に検証する必要があります
4. バイナリ比較の手法を用います - どのピクセルが異なるのかを正確に特定し、その差異を特定のアルゴリズムコンポーネントまで追跡します

体系的なアプローチ

フェーズ 1：初期分析と出力の特性把握

バイナリの内部を調べる前に、次の作業を行います。

1. プログラムを実行して出力を取得します - 画像の寸法、形式（PPM、PNG など）、全体的な内容を確認します
2. 出力画像を体系的に分析します：
   • 画像全体から一定間隔でピクセルをサンプリングします
   • 空、地面、オブジェクト、影などの領域を特定します
   • 色の分布と変化を記録します
   • レンダリングコンポーネント間のおおよその境界を図示します
3. 文字列情報を抽出します - strings を使って、アルゴリズムの手がかりとなる関数名、ファイルパス、埋め込みテキストを見つけます

フェーズ 2：定数の徹底的な抽出

コードを書く前に、すべての浮動小数点定数を抽出します。

1. rodata セクションをダンプします - objdump -s -j .rodata binary または readelf -x .rodata binary
2. 浮動小数点数のパターンを特定します - 適切な浮動小数点値（色なら 0.0～1.0、位置ならそれより大きな値）にデコードされる 4 バイトの並びを探します
3. 定数マップを作成します - 抽出した各定数をアドレスとともに記録します
4. 逆アセンブル結果と照合します - 各定数を使用する関数を特定します

定数の抽出方法の例：

# Dump rodata and decode floats
objdump -s -j .rodata binary | grep -E "^\s+[0-9a-f]+" | while read addr data; do
    # Parse and decode 4-byte float sequences
done

フェーズ 3：関数ごとのリバースエンジニアリング

各関数を特定し、完全にリバースエンジニアリングします。

1. すべての関数を列挙します - nm または objdump -t を使ってシンボルを特定します
2. 呼び出しグラフを作成します - どの関数がどの関数を呼び出すのかを把握します
3. レンダリング関数を優先します - 次のような関数に注目します。
   • sphere_intersect、ray_intersect（ジオメトリの交差判定）
   • vector_normalize、vector_dot、vector_cross（数学ユーティリティ）
   • shade、illuminate、reflect（ライティング計算）
   • trace、cast_ray（メインのレンダリングループ）
4. 各関数を擬似コードに変換します - 各関数を完全に理解するまでは、実装に進まないでください

フェーズ 4：コンポーネントごとの実装

各コンポーネントを個別に実装して検証します。

1. 最も単純なコンポーネントから始めます - 通常は空や背景のグラデーションです
2. 次のコンポーネントに進む前に、元の出力と照合して検証します
3. 交差判定ルーチンを個別にテストします - ジオメトリ計算を検証するテストケースを作成します
4. ライティングは最後に追加します - ライティングの誤差はジオメトリの誤差と重なります

フェーズ 5：バイナリ比較とデバッグ

出力が一致しない場合は、次の作業を行います。

1. ピクセルごとの差異を計算します - 正確な差異を示す差分マップを作成します
2. 系統的な誤差とランダムな誤差を特定します：
   • 1 つの領域における系統的な誤差 = そのコンポーネントのアルゴリズムの誤り
   • 1 つずれたパターン = 丸め処理または精度の違い
   • オブジェクト全体にかかる色合い = ライティングモデルの誤り
3. 誤差を特定の定数や数式まで追跡します - 定数が誤っていると、予測可能な誤差パターンが生じます

よくある落とし穴

落とし穴 1：試行錯誤による定数調整

問題：値が異なる理由を理解せず、見た目を比較しながら定数を少しずつ調整します（0.747 → 0.690）。

解決策：バイナリから正確な定数を抽出します。値が予想と一致しない場合は、推測するのではなく逆アセンブルを見直してください。

落とし穴 2：実装を急ぎすぎる

問題：アルゴリズムを十分に理解する前にコードを書き始めると、誤った前提が実装に組み込まれてしまいます。

解決策：実装コードを書く前に、フェーズ 3（関数全体のリバースエンジニアリング）を完了してください。

落とし穴 3：難しい要素を無視して簡単な要素に注力する

問題：球体の描画（複雑さ）がまったく正しくないまま、空のグラデーション（単純さ）の完成に労力を費やします。

解決策：早い段階ですべての要素を特定し、重要度に応じて労力を配分してください。空が完璧でも球体の描画に問題があれば、類似度のしきい値を満たせません。

落とし穴 4：単純な照明モデルを前提にする

問題：バイナリでより複雑なマテリアル（鏡面反射、反射、表面下散乱）が使われているにもかかわらず、拡散反射のみの照明だと想定します。

解決策：オブジェクトの色を注意深く分析してください。予想外の色かぶり（例：球体が予想されるグレーではなく赤みを帯びている：（51, 10, 10））は、考慮されていないマテリアル特性を示しています。

落とし穴 5：シーン分析が不完全

問題：分析が不十分なため、シーン内のオブジェクトを見落とします。色分布に複数のグレー値がある場合、球体が複数ある可能性があります。

解決策：出力画像全体を体系的に分析してください。異なるオブジェクト領域の数を数え、それぞれが考慮されていることを確認してください。

落とし穴 6：逆アセンブル分析を途中で放棄する

問題：重要な関数の逆アセンブルを始めても、完全に理解するまで続けません。

解決策：特定した各関数について、先に進む前に完全な疑似コードを作成してください。関数を「完全に理解済み」または「さらなる分析が必要」として記録します。

検証戦略

戦略 1：正解データのピクセルサンプリング

元の出力から特定のピクセルをサンプリングし、実装が同一の値を生成することを確認します。

# Test critical pixels across different components
test_pixels = [
    (0, 0),      # Corner - likely sky
    (400, 0),    # Top center - sky
    (400, 500),  # Bottom center - ground
    (400, 300),  # Center - likely object
]
for x, y in test_pixels:
    original = get_pixel(original_image, x, y)
    generated = get_pixel(generated_image, x, y)
    assert original == generated, f"Mismatch at ({x},{y}): {original} vs {generated}"

戦略 2：コンポーネント分離テスト

ほかのコンポーネントをマスクして、各描画コンポーネントを個別にテストします。

1. 空のみのテスト：オブジェクトのない領域のピクセルを確認します
2. 地面のみのテスト：オブジェクトのない市松模様または地面のパターンを確認します
3. オブジェクトのみのテスト：オブジェクトの境界内のピクセルを比較します

戦略 3：差分画像分析

視覚的な差分画像を生成して、エラーのパターンを特定します。

# Per-pixel absolute difference
diff_image = abs(original - generated)
# Highlight pixels exceeding threshold
error_mask = diff_image > threshold

戦略 4：統計的比較

複数の類似度指標を追跡します。

• 完全一致ピクセル率 - 成功には非常に高い値（>95%）が必要です
• 平均絶対誤差 - 平均的な偏差を特定します
• 最大誤差 - デバッグ対象となる最悪のピクセルを特定します
• コサイン類似度 - 全体的な構造の類似度を示します（ただし、局所的な誤差が隠れることがあります）

レイトレーシングに関する知識

一般的なレイトレーサーの構造

ほとんどの単純なレイトレーサーは、次のパターンに従います。

for each pixel (x, y):
    ray = generate_ray(camera, x, y)
    color = trace_ray(ray, scene, depth)
    write_pixel(x, y, color)

trace_ray(ray, scene, depth):
    hit = find_closest_intersection(ray, scene)
    if no hit:
        return background_color(ray)
    return shade(hit, ray, scene, depth)

抽出すべき主要な定数

• 画像の寸法：幅、高さ（多くの場合、rodata 内またはハードコードされています）
• カメラパラメーター：視野角、位置、注視方向
• オブジェクト定義：球体の中心、半径、色／マテリアル
• 光源の位置：点光源の位置、色、強度
• マテリアルの特性：拡散反射／鏡面反射係数、光沢度

浮動小数点精度

• バイナリでは float（32 ビット）または double（64 ビット）が使われている場合があります
• x86 の命令サフィックスを確認してください。movss／addss は float、movsd／addsd は double です
• 実装では元のプログラムと同じ精度を使用してください

ワークフローの概要

1. 出力の特性を把握する - 寸法、形式、視覚的な内容
2. すべての定数を抽出する - rodata を完全に分析する
3. すべての関数をマッピングする - 名前、目的、呼び出し関係
4. 各関数をリバースエンジニアリングする - 疑似コードを完全に翻訳する
5. コンポーネントごとに実装する - 各ステップで検証する
6. バイナリを比較する - 残っている不一致を特定して修正する
7. 反復する - 差分分析を使って修正を進める

避けること：性急なコーディング、定数の推測、関数分析の途中での打ち切り、複雑なコンポーネントの無視