NavisworksTransport/doc/working/网格生成性能优化方案.md

自动路径规划网格生成性能优化方案

当前性能问题

• 1万个模型，网格大小0.25m时需要5秒
• 更大模型或更小网格时性能急剧下降

性能瓶颈分析

1. 空间索引构建阶段 (BuildSpatialHashIndex)

• 需要遍历所有模型项（1万个）计算边界框
• 每个模型项都要计算空间哈希键并添加到对应桶中
• 固定的空间哈希大小（10m）可能导致分布不均

2. 垂直扫描阶段 (ParallelScanHeightIntervals) - 最大瓶颈

• 对每个网格点（网格0.25m时，数量巨大）执行：
  • GetCandidateItemsFromSpatialHash: 查询9个相邻哈希桶
  • HeightFiltering: 高度范围筛选
  • PerformIntersectionTests: 对筛选后的每个模型项进行包围盒相交测试
• 虽然使用了包围盒快速检测而非射线法，但重复查询和测试量仍然巨大

3. 关键问题

• 空间哈希粒度固定（10m），对于0.25m的网格太粗糙，导致每个桶内模型项过多
• 每个网格点都要查询9个哈希桶，产生大量重复
• HashSet去重和ToList转换带来额外开销

优化方案

第一阶段：空间索引优化（预期提升40-60%）

1.1 自适应空间哈希大小

// 根据网格大小动态调整空间哈希大小
// 当前固定10m，改为根据网格大小动态计算
_spatialHashSize = Math.Max(gridSize * 4, 2.0); // 例如：0.25m网格用1m哈希桶

1.2 优化哈希键查询策略

• 对于小网格，减少查询的相邻桶数量（从9个减到4个或1个）
• 实现基于模型大小的智能查询范围

private List<string> GetSpatialHashKeysForPoint(Point3D point, double searchRadius)
{
    var keys = new List<string>();
    int centerX = (int)Math.Floor(point.X / _spatialHashSize);
    int centerY = (int)Math.Floor(point.Y / _spatialHashSize);
    
    // 根据搜索半径动态确定查询范围
    int range = (int)Math.Ceiling(searchRadius / _spatialHashSize);
    range = Math.Min(range, 1); // 限制最大查询范围
    
    for (int dx = -range; dx <= range; dx++)
    {
        for (int dy = -range; dy <= range; dy++)
        {
            keys.Add($"{centerX + dx},{centerY + dy}");
        }
    }
    return keys;
}

1.3 缓存优化

• 为相邻网格点缓存候选模型列表
• 实现LRU缓存减少重复查询

private readonly Dictionary<string, List<ModelItem>> _candidateCache = 
    new Dictionary<string, List<ModelItem>>();

private List<ModelItem> GetCandidateItemsFromSpatialHashWithCache(Point3D point)
{
    string cacheKey = $"{(int)(point.X/_spatialHashSize)},{(int)(point.Y/_spatialHashSize)}";
    
    if (_candidateCache.TryGetValue(cacheKey, out var cached))
        return cached;
    
    var candidates = GetCandidateItemsFromSpatialHash(point);
    _candidateCache[cacheKey] = candidates;
    return candidates;
}

第二阶段：数据结构优化（预期提升20-30%）

2.1 避免不必要的数据转换

// 直接返回IEnumerable而非ToList()
private IEnumerable<ModelItem> GetCandidateItemsFromSpatialHash(Point3D point)
{
    var hashKeys = GetSpatialHashKeysForPoint(point);
    
    foreach (var key in hashKeys)
    {
        if (_spatialHashMap.TryGetValue(key, out var items))
        {
            foreach (var item in items)
                yield return item;
        }
    }
}

2.2 使用对象池

// 为HashSet<ModelItem>实现对象池
private readonly ObjectPool<HashSet<ModelItem>> _hashSetPool = 
    new ObjectPool<HashSet<ModelItem>>(
        () => new HashSet<ModelItem>(),
        set => set.Clear());

2.3 批处理相邻点

// 将相邻的网格点分组处理，共享候选列表
private void ProcessGridPointBatch(List<Point3D> batch)
{
    // 计算批次的边界框
    var batchBounds = CalculateBounds(batch);
    
    // 一次性获取所有候选项
    var candidates = GetCandidatesForBounds(batchBounds);
    
    // 为批次中的每个点处理
    Parallel.ForEach(batch, point =>
    {
        ProcessPointWithCandidates(point, candidates);
    });
}

第三阶段：算法优化（预期提升15-25%）

3.1 分层扫描策略

// 先用粗网格（如1m）快速识别障碍物区域
var coarseGrid = GenerateCoarseGrid(1.0);
var obstacleRegions = IdentifyObstacleRegions(coarseGrid);

// 只在边界区域使用细网格（0.25m）
var fineGridPoints = GenerateFineGridPoints(obstacleRegions, 0.25);

3.2 早期终止优化

private List<ModelItem> HeightFiltering(List<ModelItem> items, double minZ, double maxZ)
{
    var filtered = new List<ModelItem>();
    int fullyBlockedCount = 0;
    
    foreach (var item in items)
    {
        var bbox = item.BoundingBox();
        
        // 如果完全覆盖扫描范围，标记并早期终止
        if (bbox.Min.Z <= minZ && bbox.Max.Z >= maxZ)
        {
            fullyBlockedCount++;
            if (fullyBlockedCount > 3) // 多个障碍物完全覆盖
            {
                return items; // 早期返回，无需继续筛选
            }
        }
        
        if (bbox.Max.Z >= minZ && bbox.Min.Z <= maxZ)
        {
            filtered.Add(item);
        }
    }
    
    return filtered;
}

3.3 空间局部性优化

// 按空间顺序处理网格点，提高缓存命中率
var sortedPoints = gridPoints
    .OrderBy(p => p.Y)
    .ThenBy(p => p.X)
    .ToList();

第四阶段：并行优化（预期提升10-20%）

4.1 优化并行粒度

// 使用Partitioner创建更均衡的工作负载
var partitioner = Partitioner.Create(pointsList, true);
Parallel.ForEach(partitioner, new ParallelOptions 
{ 
    MaxDegreeOfParallelism = _parallelDegree 
}, 
gridPoint =>
{
    // 处理逻辑
});

4.2 减少锁竞争

// 使用线程本地存储减少共享资源访问
ThreadLocal<List<IntersectionResult>> threadLocalResults = 
    new ThreadLocal<List<IntersectionResult>>(() => new List<IntersectionResult>());

实施计划

立即实施（1-2天）

1. 自适应空间哈希大小
2. 优化哈希键查询策略
3. 避免不必要的ToList()转换

短期实施（3-5天）

1. 实现缓存机制
2. 批处理相邻点
3. 优化并行粒度

中期实施（1-2周）

1. 分层扫描策略
2. 对象池实现
3. 早期终止优化

预期效果

场景	当前性能	优化后性能	提升比例
1万模型，0.25m网格	5秒	1.5-2秒	2.5-3倍
2万模型，0.25m网格	15-20秒	3-5秒	4-5倍
1万模型，0.1m网格	30秒+	5-8秒	4-6倍

关键代码修改文件

1. src/PathPlanning/VerticalScanProcessor.cs

   • 构造函数：添加网格大小参数
   • GetSpatialHashKeysForPoint：智能查询范围
   • GetCandidateItemsFromSpatialHash：缓存实现
   • ParallelScanHeightIntervals：批处理优化

2. src/PathPlanning/GridMapGenerator.cs

   • GenerateChannelBased2_5D：传递网格大小到VerticalScanProcessor

3. src/PathPlanning/ChannelBasedGridBuilder.cs

   • BuildChannelCoverage：优化通道识别流程

测试验证

1. 性能测试

   • 不同模型数量（1千、5千、1万、2万）
   • 不同网格大小（1m、0.5m、0.25m、0.1m）
   • 记录时间和内存使用

2. 正确性验证

   • 对比优化前后的网格生成结果
   • 确保路径规划结果一致

3. 稳定性测试

   • 长时间运行测试
   • 内存泄漏检测

风险评估

1. 缓存可能导致内存增加

   • 解决方案：实现LRU缓存，限制缓存大小

2. 并行度提高可能导致CPU占用过高

   • 解决方案：提供可配置的并行度参数

3. 空间哈希大小改变可能影响结果

   • 解决方案：充分测试，确保结果一致性