alice-sdf 6.0.0

//! Vertex cache optimization for GPU-friendly triangle ordering
//!
//! Implements the Tom Forsyth algorithm for optimal post-transform
//! vertex cache utilization. Reorders triangles to minimize cache misses,
//! improving GPU rendering performance by 10-30%.
//!
//! # References
//! - Tom Forsyth, "Linear-Speed Vertex Cache Optimisation" (2006)
//!
//! Author: Moroya Sakamoto

use crate::mesh::Mesh;

const CACHE_SIZE: usize = 32;
const CACHE_DECAY_POWER: f32 = 1.5;
const LAST_TRI_SCORE: f32 = 0.75;
const VALENCE_BOOST_SCALE: f32 = 2.0;
const VALENCE_BOOST_POWER: f32 = 0.5;

struct VertexData {
    score: f32,
    active_tri_count: u32,
    tri_indices: Vec<u32>,
    cache_pos: i32, // -1 = not in cache
}

/// Optimize triangle order for vertex cache efficiency (Tom Forsyth algorithm)
///
/// Reorders `mesh.indices` in-place to maximize post-transform vertex cache hits.
/// This typically improves GPU rendering performance by 10-30%.
pub fn optimize_vertex_cache(mesh: &mut Mesh) {
    let vert_count = mesh.vertices.len();
    let tri_count = mesh.indices.len() / 3;

    if tri_count <= 1 {
        return;
    }

    // Build per-vertex data
    let mut vdata: Vec<VertexData> = (0..vert_count)
        .map(|_| VertexData {
            score: 0.0,
            active_tri_count: 0,
            tri_indices: Vec::new(),
            cache_pos: -1,
        })
        .collect();

    // Count triangles per vertex and build adjacency
    for t in 0..tri_count {
        for k in 0..3 {
            let vi = mesh.indices[t * 3 + k] as usize;
            if vi < vert_count {
                vdata[vi].active_tri_count += 1;
                vdata[vi].tri_indices.push(t as u32);
            }
        }
    }

    // Initial vertex scores
    for v in &mut vdata {
        v.score = compute_vertex_score(v.cache_pos, v.active_tri_count);
    }

    // Triangle scores and emitted flags
    let mut tri_scores: Vec<f32> = (0..tri_count)
        .map(|t| {
            let a = mesh.indices[t * 3] as usize;
            let b = mesh.indices[t * 3 + 1] as usize;
            let c = mesh.indices[t * 3 + 2] as usize;
            vdata[a].score + vdata[b].score + vdata[c].score
        })
        .collect();
    let mut tri_emitted = vec![false; tri_count];

    // LRU cache
    let mut cache: Vec<u32> = Vec::with_capacity(CACHE_SIZE + 3);

    // Output indices
    let mut output = Vec::with_capacity(mesh.indices.len());

    // Find best starting triangle
    let mut best_tri = 0usize;
    let mut best_score = -1.0f32;
    #[allow(clippy::needless_range_loop)]
    for t in 0..tri_count {
        if tri_scores[t] > best_score {
            best_score = tri_scores[t];
            best_tri = t;
        }
    }

    for _ in 0..tri_count {
        if tri_emitted[best_tri] {
            // Find any unemitted triangle
            let mut found = false;
            #[allow(clippy::needless_range_loop)]
            for t in 0..tri_count {
                if !tri_emitted[t] {
                    best_tri = t;
                    found = true;
                    break;
                }
            }
            if !found {
                break;
            }
        }

        // Emit triangle
        tri_emitted[best_tri] = true;
        let tri_verts = [
            mesh.indices[best_tri * 3] as usize,
            mesh.indices[best_tri * 3 + 1] as usize,
            mesh.indices[best_tri * 3 + 2] as usize,
        ];

        output.push(tri_verts[0] as u32);
        output.push(tri_verts[1] as u32);
        output.push(tri_verts[2] as u32);

        // Decrement active tri count for these vertices
        for &vi in &tri_verts {
            if vi < vert_count {
                vdata[vi].active_tri_count = vdata[vi].active_tri_count.saturating_sub(1);
            }
        }

        // Update cache - push new vertices to front
        for &vi in &tri_verts {
            // Remove if already in cache
            if let Some(pos) = cache.iter().position(|&v| v == vi as u32) {
                cache.remove(pos);
            }
            cache.insert(0, vi as u32);
        }

        // Truncate cache
        if cache.len() > CACHE_SIZE {
            // Evicted vertices get cache_pos = -1
            for &evicted in cache.iter().skip(CACHE_SIZE) {
                let ei = evicted as usize;
                if ei < vert_count {
                    vdata[ei].cache_pos = -1;
                }
            }
            cache.truncate(CACHE_SIZE);
        }

        // Update cache positions
        for (pos, &vi) in cache.iter().enumerate() {
            let vi = vi as usize;
            if vi < vert_count {
                vdata[vi].cache_pos = pos as i32;
            }
        }

        // Recalculate scores for affected vertices and their triangles
        let mut dirty_tris = Vec::new();
        for &vi in &cache {
            let vi = vi as usize;
            if vi < vert_count {
                vdata[vi].score =
                    compute_vertex_score(vdata[vi].cache_pos, vdata[vi].active_tri_count);
                for &ti in &vdata[vi].tri_indices {
                    if !tri_emitted[ti as usize] {
                        dirty_tris.push(ti as usize);
                    }
                }
            }
        }

        // Update dirty triangle scores and find next best
        best_score = -1.0;
        let mut next_best = 0;
        for &t in &dirty_tris {
            let a = mesh.indices[t * 3] as usize;
            let b = mesh.indices[t * 3 + 1] as usize;
            let c = mesh.indices[t * 3 + 2] as usize;
            tri_scores[t] = vdata[a].score + vdata[b].score + vdata[c].score;
        }

        // Search candidates from dirty triangles first
        for &t in &dirty_tris {
            if !tri_emitted[t] && tri_scores[t] > best_score {
                best_score = tri_scores[t];
                next_best = t;
            }
        }

        if best_score < 0.0 {
            // Fallback: scan all
            for t in 0..tri_count {
                if !tri_emitted[t] && tri_scores[t] > best_score {
                    best_score = tri_scores[t];
                    next_best = t;
                }
            }
        }

        best_tri = next_best;
    }

    mesh.indices = output;
}

fn compute_vertex_score(cache_pos: i32, active_tri_count: u32) -> f32 {
    if active_tri_count == 0 {
        return -1.0;
    }

    let mut score = 0.0f32;

    if cache_pos >= 0 {
        if cache_pos < 3 {
            score = LAST_TRI_SCORE;
        } else {
            let scaler = 1.0 / (CACHE_SIZE as f32 - 3.0);
            score =
                alice_det_math::powf((cache_pos as f32 - 3.0) * -scaler + 1.0, CACHE_DECAY_POWER);
        }
    }

    // Valence boost
    let valence_boost = alice_det_math::powf(active_tri_count as f32, -VALENCE_BOOST_POWER);
    score += VALENCE_BOOST_SCALE * valence_boost;

    score
}

/// Calculate Average Cache Miss Ratio (ACMR)
///
/// Lower is better. A value of 0.5 means ~0.5 cache misses per triangle.
/// Unoptimized meshes typically have ACMR ~0.7-1.0, optimized ~0.5-0.7.
pub fn compute_acmr(mesh: &Mesh, cache_size: usize) -> f32 {
    let tri_count = mesh.indices.len() / 3;
    if tri_count == 0 {
        return 0.0;
    }

    let mut cache: Vec<u32> = Vec::with_capacity(cache_size);
    let mut misses = 0u32;

    for &idx in &mesh.indices {
        if !cache.contains(&idx) {
            misses += 1;
            cache.insert(0, idx);
            if cache.len() > cache_size {
                cache.pop();
            }
        } else {
            // Move to front (LRU)
            if let Some(pos) = cache.iter().position(|&v| v == idx) {
                cache.remove(pos);
                cache.insert(0, idx);
            }
        }
    }

    misses as f32 / tri_count as f32
}

/// Deduplicate vertices that share the same position, normal, and UV
///
/// Merges identical vertices and updates indices accordingly.
/// Reduces vertex buffer size and improves cache efficiency.
pub fn deduplicate_vertices(mesh: &mut Mesh) {
    use std::collections::HashMap;

    let mut vertex_map: HashMap<u64, u32> = HashMap::new();
    let mut new_vertices = Vec::new();
    let mut index_remap: Vec<u32> = Vec::with_capacity(mesh.vertices.len());

    for v in &mesh.vertices {
        // Hash key from quantized position + normal + uv
        let key = hash_vertex(v);

        if let Some(&new_idx) = vertex_map.get(&key) {
            index_remap.push(new_idx);
        } else {
            let new_idx = new_vertices.len() as u32;
            vertex_map.insert(key, new_idx);
            new_vertices.push(*v);
            index_remap.push(new_idx);
        }
    }

    // Remap indices
    for idx in &mut mesh.indices {
        *idx = index_remap[*idx as usize];
    }

    mesh.vertices = new_vertices;
    remove_degenerate_triangles(mesh);
}

/// Drop triangles that reference the same vertex twice.
///
/// Marching cubes emits them when a grid corner sits exactly on the
/// iso-level: the edge vertices on every edge leaving that corner collapse
/// onto the corner, and after deduplication the triangle has two equal
/// indices. Such a triangle has no area, but its `(a, a)` edge is counted
/// as a boundary by any edge-pairing check, so the mesh reads as open.
pub fn remove_degenerate_triangles(mesh: &mut Mesh) {
    let mut kept = Vec::with_capacity(mesh.indices.len());
    for t in mesh.indices.chunks_exact(3) {
        if t[0] != t[1] && t[1] != t[2] && t[0] != t[2] {
            kept.extend_from_slice(t);
        }
    }
    mesh.indices = kept;
}

// ============================================================================
// meshoptimizer 相当 §vfetchoptimizer 移植 (Vertex Fetch Optimization)
// ============================================================================

/// Vertex Fetch Optimization
///
/// `optimize_vertex_cache` (Tom Forsyth) の後に適用し、vertex buffer を
/// index buffer が参照する順序に並べ替えることで vertex fetch のキャッシュ
/// ライン利用効率を最大化する
///
/// # アルゴリズム (zeux/meshoptimizer §vfetchoptimizer.cpp 準拠)
///
/// 1. index buffer を先頭から走査
/// 2. 各 index について、新規なら "next output position" に割当
/// 3. remap table を用いて index buffer を書き換え
/// 4. vertex buffer を新順序に並べ替え
///
/// # 何が変わるか
///
/// - 三角形の順序 (index の並び) は変えないので、`compute_acmr` も
///   `compute_atvr` も変わらない どちらも「どの頂点を参照したか」の列だけで決まり、
///   頂点の番号の付け方には依存しない
/// - 変わるのは vertex buffer 上の **アドレスの局所性**: 最初に参照された順に
///   番号を振り直すので、index の列が参照する vertex buffer の位置がほぼ単調増加になり、
///   GPU の vertex fetch (cache line 単位の読み込み) が連続アクセスに近づく
/// - 参照されない頂点は削除される
///
/// # 呼び出し順序
///
/// ```text
/// deduplicate_vertices → optimize_vertex_cache → optimize_vertex_fetch
///                        (ACMR ↓)                 (vertex buffer の参照が連続に近づく)
/// ```
#[allow(clippy::cast_possible_truncation)]
pub fn optimize_vertex_fetch(mesh: &mut Mesh) {
    let n = mesh.vertices.len();
    if n == 0 || mesh.indices.is_empty() {
        return;
    }

    // sentinel value: u32::MAX = まだ割当てなし
    let sentinel = u32::MAX;
    let mut remap: Vec<u32> = vec![sentinel; n];
    let mut next_output = 0u32;

    // index を走査、初出頂点に順次 next_output を割当
    for idx in &mut mesh.indices {
        let old = *idx as usize;
        if old >= n {
            continue; // 破損 index は無視
        }
        if remap[old] == sentinel {
            remap[old] = next_output;
            next_output += 1;
        }
        *idx = remap[old];
    }

    // 新順序で vertex buffer を再構築
    // remap[old] = new_idx なので、新 buffer の new_idx 位置に old 頂点をコピー
    let mut new_vertices: Vec<crate::mesh::Vertex> = vec![mesh.vertices[0]; next_output as usize];
    for (old, &new_idx) in remap.iter().enumerate() {
        if new_idx != sentinel {
            new_vertices[new_idx as usize] = mesh.vertices[old];
        }
    }
    mesh.vertices = new_vertices;
}

/// Average Transformed Vertex Ratio (ATVR) 計測
///
/// `cache_size` entry の FIFO cache (hit では順序を更新しない) で index の列を走査し、
/// **miss 数 / 参照された相異なる頂点の数** を返す
///
/// - 下限は 1 (各頂点を 1 回だけ変換する)、cache が全頂点を保持できれば常に 1
/// - 空の mesh または `cache_size == 0` は 0
///
/// # 頂点の番号付けに依存しない
///
/// 値は index の列の「同じ頂点か違う頂点か」の並びだけで決まり、頂点の番号を
/// 付け替えても変わらない したがって `optimize_vertex_fetch` (頂点の番号の振り直し)
/// では変わらず、三角形の順序を変える `optimize_vertex_cache` などで変わる
/// vertex buffer 上のアドレスの局所性 (`optimize_vertex_fetch` が改善するもの) は
/// この指標では測れない
#[must_use]
#[allow(clippy::cast_precision_loss)]
pub fn compute_atvr(mesh: &Mesh, cache_size: usize) -> f32 {
    if mesh.indices.is_empty() || cache_size == 0 {
        return 0.0;
    }

    let mut cache: std::collections::VecDeque<u32> =
        std::collections::VecDeque::with_capacity(cache_size);
    let mut misses = 0u32;
    let mut unique_seen = std::collections::HashSet::new();

    for &idx in &mesh.indices {
        // 既知 vertex の cache line 上での連続性で hit 判定
        if cache.contains(&idx) {
            // hit: cache 順序は保持 (LRU 化しない、fetch は前方 window の連続性を測る)
        } else {
            unique_seen.insert(idx);
            misses += 1;
            cache.push_front(idx);
            if cache.len() > cache_size {
                cache.pop_back();
            }
        }
    }

    // ATVR = fetched unique vertices / total unique vertices seen
    // 完全 linear なら ATVR ≈ 1.0 (各 vertex を 1 度だけ fetch)
    // 完全 random なら ATVR ≈ misses / unique count (>1)
    misses as f32 / (unique_seen.len().max(1) as f32)
}

fn hash_vertex(v: &crate::mesh::Vertex) -> u64 {
    use std::hash::{Hash, Hasher};
    let mut hasher = std::collections::hash_map::DefaultHasher::new();

    // Quantize to avoid floating point issues
    let qp = [
        (v.position.x * 10000.0) as i32,
        (v.position.y * 10000.0) as i32,
        (v.position.z * 10000.0) as i32,
    ];
    let qn = [
        (v.normal.x * 1000.0) as i32,
        (v.normal.y * 1000.0) as i32,
        (v.normal.z * 1000.0) as i32,
    ];
    let quv = [(v.uv.x * 10000.0) as i32, (v.uv.y * 10000.0) as i32];

    qp.hash(&mut hasher);
    qn.hash(&mut hasher);
    quv.hash(&mut hasher);
    v.material_id.hash(&mut hasher);

    hasher.finish()
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::mesh::{sdf_to_mesh, MarchingCubesConfig};
    use crate::types::SdfNode;
    use glam::Vec3;

    #[test]
    fn test_vertex_cache_optimization() {
        let sphere = SdfNode::sphere(1.0);
        let config = MarchingCubesConfig {
            resolution: 16,
            iso_level: 0.0,
            compute_normals: true,
            ..Default::default()
        };
        let mut mesh = sdf_to_mesh(&sphere, Vec3::splat(-2.0), Vec3::splat(2.0), &config);

        let acmr_before = compute_acmr(&mesh, 32);
        optimize_vertex_cache(&mut mesh);
        let acmr_after = compute_acmr(&mesh, 32);

        // Optimized should be equal or better
        assert!(
            acmr_after <= acmr_before + 0.01,
            "ACMR should improve: before={}, after={}",
            acmr_before,
            acmr_after
        );
    }

    #[test]
    fn test_acmr() {
        let sphere = SdfNode::sphere(1.0);
        let config = MarchingCubesConfig {
            resolution: 8,
            iso_level: 0.0,
            compute_normals: true,
            ..Default::default()
        };
        let mesh = sdf_to_mesh(&sphere, Vec3::splat(-2.0), Vec3::splat(2.0), &config);

        let acmr = compute_acmr(&mesh, 32);
        assert!(acmr > 0.0);
        assert!(acmr <= 3.0); // Maximum 3 misses per triangle
    }

    #[test]
    fn test_deduplicate_vertices() {
        let sphere = SdfNode::sphere(1.0);
        let config = MarchingCubesConfig {
            resolution: 8,
            iso_level: 0.0,
            compute_normals: true,
            ..Default::default()
        };
        let mut mesh = sdf_to_mesh(&sphere, Vec3::splat(-2.0), Vec3::splat(2.0), &config);

        let vert_before = mesh.vertex_count();
        deduplicate_vertices(&mut mesh);
        let vert_after = mesh.vertex_count();

        // Should have same or fewer vertices
        assert!(vert_after <= vert_before);
        // Triangles should be unchanged
        assert!(mesh.triangle_count() > 0);
    }

    #[test]
    fn test_single_triangle() {
        // Edge case: single triangle
        let mut mesh = Mesh {
            vertices: vec![
                crate::mesh::Vertex::new(Vec3::ZERO, Vec3::Y),
                crate::mesh::Vertex::new(Vec3::X, Vec3::Y),
                crate::mesh::Vertex::new(Vec3::Z, Vec3::Y),
            ],
            indices: vec![0, 1, 2],
        };

        optimize_vertex_cache(&mut mesh);
        assert_eq!(mesh.indices.len(), 3);
    }

    // ------------------------------------------------------------------------
    // meshoptimizer §vfetchoptimizer 移植テスト
    // ------------------------------------------------------------------------

    #[test]
    fn test_vertex_fetch_empty_mesh() {
        let mut mesh = Mesh::new();
        optimize_vertex_fetch(&mut mesh);
        assert!(mesh.vertices.is_empty());
        assert!(mesh.indices.is_empty());
    }

    #[test]
    fn test_vertex_fetch_permuted_order() {
        // 4 頂点、index が (2, 0, 3, 1, 2, 3) = 逆順アクセス
        // optimize_vertex_fetch 後: index が (0, 1, 2, 3, 0, 2) に write されて
        // vertex buffer の [2, 0, 3, 1] が [0, 1, 2, 3] に並び直る
        let v0 = crate::mesh::Vertex::new(Vec3::new(0.0, 0.0, 0.0), Vec3::Y);
        let v1 = crate::mesh::Vertex::new(Vec3::new(1.0, 0.0, 0.0), Vec3::Y);
        let v2 = crate::mesh::Vertex::new(Vec3::new(2.0, 0.0, 0.0), Vec3::Y);
        let v3 = crate::mesh::Vertex::new(Vec3::new(3.0, 0.0, 0.0), Vec3::Y);
        let mut mesh = Mesh {
            vertices: vec![v0, v1, v2, v3],
            indices: vec![2, 0, 3, 1, 2, 3],
        };

        optimize_vertex_fetch(&mut mesh);

        // 4 頂点全て残る (すべて使用済み)
        assert_eq!(mesh.vertices.len(), 4);
        assert_eq!(mesh.indices.len(), 6);

        // 各 index 経由でアクセスした頂点の position が元と一致 (data 保存)
        // 元 index[0] = 2 → v2、新 index[0] は 0 で mesh.vertices[0] = 元 v2
        assert!((mesh.vertices[mesh.indices[0] as usize].position.x - 2.0).abs() < 1e-6);
        assert!((mesh.vertices[mesh.indices[1] as usize].position.x - 0.0).abs() < 1e-6);
        assert!((mesh.vertices[mesh.indices[2] as usize].position.x - 3.0).abs() < 1e-6);
        assert!((mesh.vertices[mesh.indices[3] as usize].position.x - 1.0).abs() < 1e-6);
    }

    #[test]
    fn test_vertex_fetch_removes_unused() {
        // 5 頂点あるが index が (0, 1, 2) のみ使う → 4, 3 は削除される
        let v = |x: f32| crate::mesh::Vertex::new(Vec3::new(x, 0.0, 0.0), Vec3::Y);
        let mut mesh = Mesh {
            vertices: vec![v(0.0), v(1.0), v(2.0), v(3.0), v(4.0)],
            indices: vec![0, 1, 2],
        };
        optimize_vertex_fetch(&mut mesh);
        // 使用頂点だけ残る
        assert_eq!(mesh.vertices.len(), 3);
    }

    #[test]
    fn test_vertex_fetch_atvr_improves() {
        // 実 mesh で fetch 最適化前後で ATVR 改善を確認
        let sphere = SdfNode::sphere(1.0);
        let config = MarchingCubesConfig {
            resolution: 16,
            iso_level: 0.0,
            compute_normals: true,
            ..Default::default()
        };
        let mut mesh = sdf_to_mesh(&sphere, Vec3::splat(-2.0), Vec3::splat(2.0), &config);

        // Random 順序に shuffle して vertex を離散化
        // (index を revert してから直接触る、単純 fisher-yates は割愛、reverse で十分)
        let mut new_verts = mesh.vertices.clone();
        new_verts.reverse();
        let n = mesh.vertices.len() as u32;
        for idx in &mut mesh.indices {
            *idx = n - 1 - *idx;
        }
        mesh.vertices = new_verts;

        let atvr_before = compute_atvr(&mesh, 8);
        optimize_vertex_fetch(&mut mesh);
        let atvr_after = compute_atvr(&mesh, 8);

        // ATVR は頂点の番号付けに依存しないので、番号を振り直すだけの
        // fetch 最適化では変わらない
        assert_eq!(
            atvr_after.to_bits(),
            atvr_before.to_bits(),
            "ATVR is invariant under renumbering: before={atvr_before}, after={atvr_after}"
        );
    }

    #[test]
    fn test_atvr_finite() {
        let sphere = SdfNode::sphere(1.0);
        let config = MarchingCubesConfig {
            resolution: 8,
            iso_level: 0.0,
            compute_normals: true,
            ..Default::default()
        };
        let mesh = sdf_to_mesh(&sphere, Vec3::splat(-2.0), Vec3::splat(2.0), &config);
        let atvr = compute_atvr(&mesh, 8);
        assert!(atvr > 0.0 && atvr < 10.0);
    }
}