More knife tool cross-contour cutting work is needed

[eliheuer]

Knife Tool Cross-Contour Cutting Analysis

Problem Statement

The knife tool in Bezy works well for simple single-contour shapes (like rectangles) but fails on complex multi-contour glyphs like the letter 'a'. This document analyzes the approaches used by professional font editors and provides recommendations for implementing proper cross-contour cutting.

The Challenge

Multi-contour glyphs like 'a' have:

• Outer contour: Main letter shape (clockwise winding)
• Inner contour: Counter/hole (counter-clockwise winding, creates negative space)

The desired knife behavior:

• Cut from inner bowl to outer edge, merging two separate contours into one
• Handle winding rule changes properly
• Create "bridges" that connect inner and outer shapes
• Maintain proper topology after cutting

Research: Professional Font Editor Approaches

Fontra Approach: Explicit Multi-Path Processing

Source: https://github.com/fontra/fontra

Architecture:

// Fontra's slicePaths() - processes multiple paths explicitly
slicePaths(intersections, ...paths) {
    // Group intersections by path
    // Sort intersections within each path  
    // Create bridges between intersection points
    // Handle cross-contour connections explicitly
}

Key Files:

• /src-js/views-editor/src/edit-tools-knife.js - Main knife tool
• /src-js/fontra-core/src/path-functions.js - Core slicing algorithms
• /src/fontra/core/pathops.py - Python backend with Skia pathops

Characteristics:

• Multi-path aware: Explicitly designed for multiple contours from the start
• Bridge creation: Creates explicit bridges between intersection points on different contours
• Complex topology: Handles winding rules and path boolean operations via Python/Skia backend
• Two-tier architecture: JavaScript frontend + Python/Skia backend for complex operations

Advantages:
✅ Explicit control over cross-contour topology
✅ Sophisticated bridging algorithms
✅ Proven production use in browser-based font editing
✅ Python/Skia backend handles complex boolean operations
✅ Clear separation of concerns between UI and complex math

Disadvantages:
❌ Higher complexity - two-tier architecture
❌ Bridge logic complexity - explicit topology management
❌ Language barriers - JavaScript frontend, Python backend
❌ Dependency heavy - requires Skia/pathops integration

Runebender Approach: Unified Segment Iteration

Source: https://github.com/linebender/runebender

Architecture:

// Runebender's unified approach - treats all segments uniformly
let intersections = data.paths.iter()
    .flat_map(Path::iter_segments)  // KEY: All segments as one sequence
    .flat_map(|seg| seg.intersect_line(line))
    .collect();

Key Files:

• /runebender-lib/src/tools/knife.rs - Main knife tool implementation
• /runebender-lib/src/path.rs - Path manipulation utilities
• /runebender-lib/src/cubic_path.rs - Low-level path splitting operations
• /runebender-lib/src/edit_session.rs - Multi-contour editing operations

Core Algorithm:

fn update_intersections(&mut self, data: &EditSession) {
    let line = self.current_line_in_dspace()?;
    self.intersections.clear();

    let iter = data
        .paths
        .iter()
        .flat_map(Path::iter_segments)  // Treat all segments uniformly
        .flat_map(|seg| seg.intersect_line(line))
        .map(move |hit| DPoint::from_raw(line.eval(hit.line_t)));
    self.intersections.extend(iter);
}

Characteristics:

• Unified iteration: flat_map() treats all segments from all contours as one sequence
• Implicit multi-contour: Cross-contour operations emerge naturally from unified processing
• Single-tier architecture: Pure Rust with kurbo mathematics
• Emergent behavior: Complex behaviors arise from simple uniform rules

Advantages:
✅ Conceptual simplicity - uniform treatment of all segments
✅ Single language - pure Rust throughout
✅ Emergent cross-contour behavior from simple rules
✅ Lightweight dependencies - just kurbo for math
✅ Natural scaling - works with any number of contours

Disadvantages:
❌ Less explicit control over topology
❌ Potential edge cases in complex scenarios
❌ Early stage - less battle-tested than Fontra
❌ Simpler math - may miss sophisticated cases that Skia handles

FontForge Approach: Geometric Precision Focus

Source: https://github.com/fontforge/fontforge

Key Files:

• /fontforgeexe/cvknife.c - Main knife tool implementation
• /fontforge/splineoverlap.c - Spline intersection algorithms
• /fontforge/splineutil.c - Utility functions for spline manipulation

Characteristics:

• Focus on precise geometric intersection detection
• Individual contour processing with careful spline splitting
• C-based implementation with robust edge case handling
• Less emphasis on sophisticated cross-contour bridging

Current Bezy Implementation Status

What We've Tried

1. Complex Bridging Approach (Initially implemented)

   • Attempted to manually create bridges between contours
   • Complex topology reconstruction logic
   • Result: Too complex, hard to debug, didn't work reliably

2. Runebender-Style Unified Approach (Currently implemented)

   • Unified intersection collection across all contours
   • Global sorting of intersections along cutting line
   • Simplified processing without explicit bridging
   • Result: Compiles and runs, but still not working on 'a' glyph

Current Implementation

File: /src/ui/edit_mode_toolbar/knife.rs

Key Functions:

• perform_multi_contour_cut() - Main entry point using unified approach
• perform_unified_path_slicing() - Processes all contours with global intersection context
• UnifiedIntersection - Struct tracking intersections with source contour info

Current Issues:

• Still not working properly on complex glyphs like 'a'
• May need more sophisticated path reconstruction
• Missing proper handling of cross-contour connections

Fundamental Architectural Question

The core difference between approaches:

Fontra: "How do I explicitly connect these different contours?"
Runebender: "What if I just treat everything as one big sequence of segments?"

Recommendations for Bezy

Recommended Approach: Enhanced Runebender Style

Reasoning:

1. Fontra's explicit bridging proved complex and hard to get right
2. Runebender's unified approach is more aligned with Bezy's Rust/kurbo foundation
3. Simpler emergent behavior is easier to debug and maintain
4. Single-language consistency fits better with Bezy's architecture

Next Steps

1. Debug Current Implementation

   • Add more detailed logging to understand where the unified approach is failing
   • Test with simpler multi-contour shapes to isolate the issue
   • Verify intersection detection is working correctly

2. Study Runebender More Deeply

   • Examine their exact path reconstruction logic after intersection detection
   • Understand how they handle the transition from intersections back to complete paths
   • Look at their segment iteration implementation in detail

3. Consider Hybrid Approach

   • Use Runebender's unified segment iteration for intersection detection
   • Add minimal explicit bridging logic for specific cross-contour cases
   • Leverage kurbo's robust path mathematics

4. Alternative: Skia Integration

   • Consider integrating Skia's pathops for complex boolean operations
   • Could provide a backend similar to Fontra's approach
   • Would handle complex topology cases that pure kurbo might miss

Key Insight

Complex cross-contour behavior can emerge from simple uniform rules rather than requiring explicit bridging algorithms. The Runebender approach suggests that treating all segments uniformly, regardless of which contour they belong to, naturally handles cross-contour operations.

Implementation Files

Current implementation is in:

• /src/ui/edit_mode_toolbar/knife.rs - Main knife tool logic
• Related coordinate system fixes in /src/tools/pen.rs, /src/tools/shapes.rs

Testing

To test improvements:

1. Use the default 'a' glyph in Bezy
2. Select the knife tool (K key)
3. Draw a line from the inner bowl to the outer edge
4. Expected: The knife should create a cut that connects the inner and outer contours
5. Current: Nothing happens or incorrect results

References

• Fontra Font Editor
• Runebender Font Editor
• FontForge Font Editor
• Kurbo 2D Curves Library
• Skia Pathops Documentation