YUV-based Delaunay Triangulation Image Upscaling

A successful implementation of resolution-independent image representation using triangular meshes with separate YUV channel densities.

FracPack encodes images into a triangular mesh representation that can be decoded at any scale. It uses YUV color space with Delaunay triangulation, creating denser meshes for luminance (Y) and coarser meshes for chrominance (U, V) - similar to how JPEG handles color.

Key Features:

• ✅ Resolution-independent rendering (decode at any scale)
• ✅ Smooth triangular interpolation (barycentric coordinates)
• ✅ 35+ dB PSNR quality (Very Good+)
• ✅ Fast performance on mobile (Pixel 8 tested)
• ✅ Distinctive triangular mesh aesthetic
• ✅ No compression artifacts or banding

Not Designed For:

• File size compression (model is ~same size as original)
• AI-enhanced detail (doesn't hallucinate features)
• Perfectly smooth gradients (has triangular faceting)

FracZoom Android app - 1350×1688 source image upscaled 3× in 1098ms

Zoomed to 759% - triangular mesh aesthetic clearly visible

1. Convert RGB → YUV (BT.601 standard) to separate luminance from chrominance
2. Build separate Delaunay meshes for each channel:
   • Y channel: Fine 4px grid + edge detection vertices → 232k triangles
   • U channel: Coarse 12px grid → 26k triangles
   • V channel: Coarse 12px grid → 26k triangles
3. Store mesh (vertices, triangles, channel values)
4. Decode by rasterizing triangles with barycentric interpolation
5. Convert YUV → RGB for display

Test Image: 1529×1216 face photo

Small images perform excellently:

• 512×512 test pattern: 22ms decode @ 2× ✓
• 400×311 photo: 10ms decode @ 2× ✓

// Default: Good quality/speed balance
FractalEncoder::new()                    // 4px Y, 12px UV

// Fast: Lower quality, faster
FractalEncoder::new_fast()               // 8px Y, 16px UV

// Quality: Excellent quality, slower
FractalEncoder::new_quality()            // 3px Y, 8px UV

// Ultra: Maximum quality, very slow
FractalEncoder::new_ultra()              // 2px Y, 6px UV

• image - Image loading and manipulation
• delaunator - Fast Delaunay triangulation
• imageproc - Canny edge detection for feature-aware meshing
• jni - Java Native Interface bindings
• android_logger - Proper Android logging
• lazy_static - Global state management

• Kotlin + Jetpack Compose
• Material Design 3
• Smart scaling (prevents crashes on huge images)
• 16KB page alignment (Android 15+ compatible)
• Pan/zoom with gesture support

fracpack/
├── src/
│   ├── lib.rs          # YUV Delaunay encoder/decoder
│   └── android.rs      # JNI bindings for Android
├── examples/
│   ├── encode_decode.rs       # Desktop testing
│   ├── test_quality.rs        # Quality preset comparison
│   ├── calculate_psnr.rs      # Image quality metrics
│   ├── test_yuv_roundtrip.rs  # YUV conversion accuracy
│   └── compare_brightness.rs  # Brightness analysis
└── Cargo.toml

FracZoom/
└── app/
    └── src/main/
        ├── java/com/billybobbain/fraczoom/
        │   ├── FracPack.kt        # JNI interface
        │   └── MainActivity.kt    # Android UI with smart scaling
        └── jniLibs/
            └── arm64-v8a/
                └── libfracpack.so

cd fracpack

# Basic encode/decode test
cargo run --release --example encode_decode path/to/image.jpg

# Compare quality presets
cargo run --release --example test_quality before.jpeg

# Calculate PSNR
cargo run --release --example calculate_psnr original.jpg decoded.png

# Test YUV conversion accuracy
cargo run --release --example test_yuv_roundtrip

Requires cargo-ndk:

cargo install cargo-ndk

Build for Android:

# ARM64 (phones/tablets)
cargo ndk --target aarch64-linux-android --platform 24 -- build --release --features android

# Copy to app
cp target/aarch64-linux-android/release/libfracpack.so \
   FracZoom/app/src/main/jniLibs/arm64-v8a/

Open FracZoom in Android Studio and build, or:

cd FracZoom
./gradlew assembleDebug

// 1. Convert RGB to YUV
let (y_img, u_img, v_img) = split_yuv(image);

// 2. Build mesh for Y channel (fine detail)
let y_mesh = build_channel_mesh(
    &y_img,
    y_grid_spacing: 4,      // 4px grid
    use_edge_detection: true // Add vertices on edges
);

// 3. Build meshes for U/V channels (coarse)
let u_mesh = build_channel_mesh(&u_img, uv_grid_spacing: 12, false);
let v_mesh = build_channel_mesh(&v_img, uv_grid_spacing: 12, false);

// 4. Store model
FractalModel { width, height, y_mesh, u_mesh, v_mesh }

fn build_channel_mesh(channel, grid_spacing, use_edges) {
    let mut points = Vec::new();

    // 1. Add regular grid points
    for y in (0..height).step_by(grid_spacing) {
        for x in (0..width).step_by(grid_spacing) {
            points.push([x, y]);
        }
    }

    // 2. Add edge points (Y channel only)
    if use_edges {
        let edges = canny(channel, 50.0, 100.0);
        for y in (0..height).step_by(grid_spacing) {
            for x in (0..width).step_by(grid_spacing) {
                if edges[x, y] > 128 {
                    points.push([x, y]);
                }
            }
        }
    }

    // 3. Delaunay triangulation
    let triangulation = delaunator::triangulate(&points);

    // 4. Sample channel values at vertices
    let values = points.map(|p| channel.get_pixel(p.x, p.y));

    ChannelMesh { vertices: points, triangles, values }
}

fn render_channel(mesh, output_buffer, scale) {
    for triangle in mesh.triangles {
        let v0 = mesh.vertices[triangle.indices[0]] * scale;
        let v1 = mesh.vertices[triangle.indices[1]] * scale;
        let v2 = mesh.vertices[triangle.indices[2]] * scale;

        let val0 = mesh.values[triangle.indices[0]];
        let val1 = mesh.values[triangle.indices[1]];
        let val2 = mesh.values[triangle.indices[2]];

        // Rasterize triangle
        for pixel in bounding_box(v0, v1, v2) {
            if let Some((w0, w1, w2)) = barycentric(pixel, v0, v1, v2) {
                // Interpolate value
                let value = w0 * val0 + w1 * val1 + w2 * val2;
                output_buffer.put_pixel(pixel, value);
            }
        }
    }
}

FracZoom automatically limits decode scale to prevent crashes on huge images:

val pixels = bitmap.width * bitmap.height
val decodeScale = when {
    pixels > 20_000_000 -> 1  // Huge (>20MP): 1× only
    pixels > 8_000_000  -> 2  // Large (>8MP): max 2×
    pixels > 2_000_000  -> 3  // Medium (>2MP): max 3×
    else                -> 8  // Small: up to 8×
}

This prevents Android's "bitmap too large" crash while still allowing impressive upscaling on smaller images.

• ❌ Severe horizontal banding artifacts
• ❌ "X inside X" geometric patterns
• ❌ Unusable for upscaling
• 📚 Learned: Regular grids + Delaunay = artifacts

• ✅ Fast (48ms encode, 19ms decode)
• ✅ Clean, no artifacts
• ❌ Blocky mosaic aesthetic
• 📚 Learned: Simple algorithms can be very fast

• ✅ Smooth triangular interpolation
• ✅ No banding (YUV separation solved it!)
• ✅ 35.19 dB PSNR quality
• ✅ Works on Android
• 📚 Learned: Separate channel densities are key

1. YUV color space is crucial - Separating luminance from chrominance allows different mesh densities (like JPEG chroma subsampling)

2. Edge detection improves quality - Adding vertices on high-contrast edges preserves features

3. Per-channel optimization works - Fine Y mesh (4px) + coarse UV meshes (12px) balances quality and performance

4. Triangle count matters - 284k triangles is manageable but slower; quality presets allow trade-offs

5. The aesthetic is unique - Triangular faceting creates a distinctive look (feature, not bug!)

1. Resolution-independent images - Store once, render at any scale
2. Artistic effects - Triangular mesh aesthetic for creative use
3. Rust/Android JNI example - Complete working implementation
4. Image processing learning - YUV, Delaunay, barycentric interpolation
5. Mobile-optimized native code - Real-world performance considerations

When you modify the fracpack Rust code and need to update the Android app:

1. Make changes to Rust code in src/lib.rs or other files

2. Test on desktop to verify the changes work:

   cd fracpack
   cargo run --release --example encode_decode path/to/test-image.jpg

3. Rebuild the Android native library:

   cargo ndk --target aarch64-linux-android --platform 24 -- build --release --features android

4. Copy the new .so file to Android app:

   cp target/aarch64-linux-android/release/libfracpack.so \
      FracZoom/app/src/main/jniLibs/arm64-v8a/

5. Test on Android device/emulator - Open FracZoom in Android Studio and run

6. Commit both changes:

   git add src/ FracZoom/app/src/main/jniLibs/arm64-v8a/libfracpack.so
   git commit -m "Update fracpack algorithm and rebuild native library"

7. Bump version in FracZoom/app/build.gradle if releasing:

   defaultConfig {
       versionCode 2
       versionName "1.1.0"
   }

8. Push to GitHub - GitHub Actions will build the APK with the updated .so file

The compiled libfracpack.so is checked into git so that:

• APK builds work without requiring Rust toolchain
• CI/CD can build Android apps quickly
• Contributors can build the Android app without Rust installed
• You control exactly when native updates are integrated

MIT OR Apache-2.0

FracPack concept and implementation: Billy

• Original FracPack (1990s): Fractal compression suite written in C during graduate school
• Modern implementation (2024): Rust + Android with assistance from Claude Code

A 30-year journey revisiting fractal compression with modern tools. Built while learning about YUV color spaces, Delaunay triangulation, and Android native development. Success after multiple iterations!

"Not all who wander are lost, but some of us took the scenic route through RGB banding hell to reach YUV paradise." 🎨📐