FaceVisibilityGraph Performance Benchmark Results (v0.2.0)

This document records the performance comparison between the legacy adjacency list implementation and the new CSR-style FaceVisibilityGraph implementation introduced in PR #12.

Test Environment

• Date: December 2024
• Julia Version: 1.11.5
• Machine: Apple M1/M2 (specify your machine)
• Commit: cae08e7 (feature/face-visibility-graph)

Benchmark Results

1. Small Model (Ryugu test shape - 5,932 faces)

Visibility Computation Time

Legacy implementation: 391.08 ms
FaceVisibilityGraph:   97.51 ms
Speed up: 4.01x

Memory Usage

Legacy (adjacency list): 11.7 MB
FaceVisibilityGraph:     5.9 MB
Memory reduction: 49.6%

2. Large Model (Ryugu 49k - 49,152 faces)

Visibility Computation Time

Legacy implementation: 29.064 seconds
FaceVisibilityGraph:   28.778 seconds
Speed up: 1.01x

Memory Usage

Legacy (adjacency list): 561.92 MB
FaceVisibilityGraph:     281.34 MB
Memory reduction: 49.9%

Query Performance (isilluminated - 1000 queries)

Legacy implementation: 52.88 μs
FaceVisibilityGraph:   49.67 μs
Speed ratio: 1.06x

Verification of Results

Computation Results Match

All tests confirm that both implementations produce identical results:

• ✅ Same number of visible face pairs
• ✅ Same view factors (floating point equality)
• ✅ Same distances
• ✅ Same direction vectors
• ✅ Same isilluminated results

Test Code for Verification

# From test/test_face_visibility_graph.jl (v0.2.1)
@testset "Legacy vs New Implementation" begin
    # Legacy implementation (v0.2.0)
    shape_legacy = ShapeModel(nodes, faces)
    find_visiblefacets!(shape_legacy, use_visibility_graph=false)
    
    # New implementation (v0.2.1)
    shape_new = ShapeModel(nodes, faces)
    find_visiblefacets!(shape_new, use_visibility_graph=true)
    
    for i in 1:length(faces)
        @test length(legacy_visible) == length(new_visible)
        @test sort(legacy_ids) == sort(new_ids)
        # View factors, distances, and directions also match
    end
end

Note: This comparison code was used in v0.2.1. In v0.3.0, the legacy implementation was completely removed.

Key Findings

1. Small models (< 10k faces): Significant speedup (4x) due to reduced overhead
2. Large models (> 40k faces): Similar computation time, but 50% memory savings
3. Consistent memory reduction: ~50% across all model sizes
4. Cache efficiency: Better sequential access patterns with CSR format

Reproducing These Benchmarks

To reproduce these benchmarks on future versions:

# Checkout the commit before FaceVisibilityGraph
git checkout e3529d2

# Run legacy benchmark
julia --project=. benchmark/compare_visibility.jl

# Checkout the commit with FaceVisibilityGraph
git checkout feature/face-visibility-graph

# Run comparison benchmark
julia --project=. benchmark/compare_visibility.jl
julia --project=. benchmark/benchmark_49k_shape.jl

Migration Notes

Changes in v0.3.0

The following breaking changes were made in v0.3.0:

• The use_visibility_graph parameter was removed (FaceVisibilityGraph is now always used)
• The visiblefacets field was removed from ShapeModel
• find_visiblefacets! was renamed to build_face_visibility_graph!
• visibility_graph was renamed to face_visibility_graph
• The find_visible_facets parameter in ShapeModel constructor was renamed to with_face_visibility
• Accessor functions were renamed:
  • get_visible_faces → get_visible_face_indices
  • (other accessors remain the same)

Current API (v0.3.0+)

# Create shape with face visibility
shape = ShapeModel(nodes, faces; with_face_visibility=true)

# Or load from OBJ file with visibility
shape = load_shape_obj("path/to/shape.obj"; scale=1000, with_face_visibility=true)

# Or build visibility graph later
build_face_visibility_graph!(shape)

# Access visibility data
visible_face_indices = get_visible_face_indices(shape.face_visibility_graph, face_id)
view_factors = get_view_factors(shape.face_visibility_graph, face_id)
distances = get_visible_face_distances(shape.face_visibility_graph, face_id)
directions = get_visible_face_directions(shape.face_visibility_graph, face_id)

# Get specific visible face data
vf_data = get_visible_face_data(shape.face_visibility_graph, face_id, visible_face_id)

# Count visible faces
n_visible = num_visible_faces(shape.face_visibility_graph, face_id)

These benchmark results serve as the baseline for future optimizations.