path-tracing-reverse（反向路径追踪）

Path Tracing Reverse Engineering

Overview

This skill provides a systematic approach to reverse engineering graphics rendering binaries (ray tracers, path tracers, renderers) with high-fidelity output matching requirements. The primary challenge is achieving pixel-perfect or near-pixel-perfect reproduction (>99% similarity), which requires precise extraction of algorithms, constants, and rendering parameters rather than approximation.

Critical Success Factors

When high similarity thresholds (>99%) are required:

1. Exact constant extraction is mandatory - Guessing or approximating floating-point values will fail
2. Complete algorithm reconstruction - Partial understanding leads to systematic errors across large pixel regions
3. Component isolation - Each rendering component (sky, ground, objects, lighting) must be verified independently
4. Binary comparison strategy - Identify exactly which pixels differ and trace differences to specific algorithm components

Systematic Approach

Phase 1: Initial Analysis and Output Characterization

Before examining the binary internals:

1. Run the program and capture output - Determine image dimensions, format (PPM, PNG, etc.), and general content
2. Analyze the output image systematically:

- Sample pixels at regular intervals across the entire image - Identify distinct regions (sky, ground, objects, shadows) - Note color distributions and transitions - Map out approximate boundaries between rendering components

1. Extract string information - Use strings to find function names, file paths, and embedded text that hints at the algorithm

Phase 2: Comprehensive Constant Extraction

Extract ALL floating-point constants before writing any code:

1. Dump the rodata section - objdump -s -j.rodata binary or readelf -x.rodata binary
2. Identify float patterns - Look for 4-byte sequences that decode to reasonable float values (0.0-1.0 for colors, larger values for positions)
3. Create a constant map - Document every extracted constant with its address
4. Cross-reference with disassembly - Determine which function uses each constant

Example extraction approach:

# 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

Phase 3: Function-by-Function Reverse Engineering

Identify and completely reverse engineer each function:

1. List all functions - Use nm or objdump -t to identify symbols
2. Map the call graph - Understand which functions call which
3. Prioritize rendering functions - Focus on functions like:

- sphere_intersect, ray_intersect (geometry intersection) - vector_normalize, vector_dot, vector_cross (math utilities) - shade, illuminate, reflect (lighting calculations) - trace, cast_ray (main rendering loop)

1. Translate each function to pseudocode - Do not skip to implementation until each function is fully understood

Phase 4: Component-by-Component Implementation

Implement and verify each component separately:

1. Start with the simplest component - Usually the sky/background gradient
2. Verify against the original output before moving to the next component
3. Test intersection routines independently - Create test cases that verify geometry calculations
4. Add lighting last - Lighting errors compound with geometry errors

Phase 5: Binary Comparison and Debugging

When output doesn't match:

1. Compute per-pixel differences - Create a difference map showing exact deviations
2. Identify systematic vs. random errors:

- Systematic errors in one region = algorithm error for that component - Off-by-one patterns = rounding or precision difference - Color tint across objects = lighting model error

1. Trace errors to specific constants or formulas - A wrong constant produces predictable error patterns

Common Pitfalls

Pitfall 1: Trial-and-Error Constant Adjustment

Problem: Making small adjustments to constants (0.747 → 0.690) based on visual comparison without understanding why values differ.

Solution: Extract exact constants from the binary. If a value doesn't match expectations, re-examine the disassembly rather than guessing.

Pitfall 2: Premature Implementation

Problem: Starting to write code before fully understanding the algorithm leads to incorrect assumptions being baked in.

Solution: Complete Phase 3 (full function reverse engineering) before writing implementation code.

Pitfall 3: Focusing on Easy Components While Ignoring Hard Ones

Problem: Spending effort perfecting the sky gradient (simple) while the sphere rendering (complex) remains completely wrong.

Solution: Identify all components early and allocate effort proportionally. A perfect sky with a broken sphere still fails similarity thresholds.

Pitfall 4: Assuming Simple Lighting Models

Problem: Assuming diffuse-only lighting when the binary uses more complex materials (specular, reflection, subsurface).

Solution: Analyze object colors carefully. Unexpected color tints (e.g., red tint on sphere: (51, 10, 10) vs expected gray) indicate material properties not accounted for.

Pitfall 5: Incomplete Scene Analysis

Problem: Missing objects in the scene due to incomplete analysis. Multiple gray values in color distribution may indicate multiple spheres.

Solution: Systematically analyze the entire output image. Count distinct object regions and verify each is accounted for.

Pitfall 6: Abandoning Disassembly Analysis

Problem: Starting disassembly of key functions but not following through to complete understanding.

Solution: For each identified function, create complete pseudocode before moving on. Mark functions as "fully understood" or "needs more analysis."

Verification Strategies

Strategy 1: Ground Truth Pixel Sampling

Sample specific pixels from the original output and verify the implementation produces identical values:

# 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}"

Strategy 2: Component Isolation Testing

Test each rendering component in isolation by masking other components:

1. Sky-only test: Verify pixels in regions with no objects
2. Ground-only test: Verify checkerboard or ground pattern without objects
3. Object-only test: Compare pixels within object boundaries

Strategy 3: Difference Image Analysis

Generate a visual difference image to identify error patterns:

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

Strategy 4: Statistical Comparison

Track multiple similarity metrics:

• Exact pixel match percentage - Should be very high (>95%) for success
• Mean absolute error - Identifies average deviation
• Max error - Identifies worst-case pixels for debugging
• Cosine similarity - Overall structural similarity (but can mask localized errors)

Ray Tracing Specific Knowledge

Common Ray Tracer Structure

Most simple ray tracers follow this pattern:

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)

Key Constants to Extract

• Image dimensions: Width, height (often in rodata or hardcoded)
• Camera parameters: FOV, position, look-at direction
• Object definitions: Sphere centers, radii, colors/materials
• Light positions: Point light locations, colors, intensities
• Material properties: Diffuse/specular coefficients, shininess

Floating-Point Precision

• Binary may use float (32-bit) or double (64-bit)
• Check instruction suffixes in x86: movss/addss for float, movsd/addsd for double
• Ensure implementation uses same precision as original

Workflow Summary

1. Characterize output - Dimensions, format, visual content
2. Extract all constants - Complete rodata analysis
3. Map all functions - Names, purposes, call relationships
4. Reverse each function - Full pseudocode translation
5. Implement by component - With verification at each step
6. Binary comparison - Identify and fix remaining discrepancies
7. Iterate - Use difference analysis to guide fixes

Avoid: Premature coding, constant guessing, partial function analysis, ignoring complex components.