2D SVG楼层地图光线投射性能优化技术求助

我正在开发一项功能，在2D SVG楼层地图上执行光线投射（Raycasting）以可视化相机的视野（FoV）。SVG元素通过type="Wall"属性区分墙体与家具等可被光线穿透的对象。但当前代码在处理大型SVG时性能极差，几乎无法使用，仅在墙体极少的小型SVG上可正常运行。我曾尝试使用推荐的BSP和Quadtree数据结构来提升执行速度，但在实现过程中遇到了困难。

核心性能瓶颈分析 #

当前代码的时间复杂度为O(RWS)：

• R：光线数量（90）
• W：墙体数量（大型SVG可能上百）
• S：每个墙体的采样线段数（Path/Circle等最多10段）
  墙体数量增加时，计算量呈指数级增长，这是性能问题的根源。

解决方案1：预计算墙体线段（避免实时解析） #

将所有墙体元素提前转换为线段数组，避免每次光线投射时重复解析SVG元素：

代码修改：预处理墙体线段 #

// 在handleFileUpload中替换原setWalls逻辑
setTimeout(() => {
  const wallElements = Array.from(svgRef.current.querySelectorAll('[type="Wall"]'))
    .filter(element => element.getTotalLength);
  // 预转换所有墙体为线段数组
  const wallSegments = wallElements.flatMap(wall => {
    const points = getPointsFromElement(wall);
    const segments = [];
    for (let i = 0; i < points.length - 1; i++) {
      segments.push({
        x1: points[i][0], y1: points[i][1],
        x2: points[i+1][0], y2: points[i+1][1]
      });
    }
    return segments;
  });
  setWalls(wallSegments);
}, 100);

同时修改碰撞检测函数，直接接收线段参数：

const getIntersectionWithSegment = useCallback((ray, segment) => {
  return lineIntersection(
    ray.x1, ray.y1, ray.x2, ray.y2,
    segment.x1, segment.y1, segment.x2, segment.y2
  );
}, [lineIntersection]);

解决方案2：实现简化版Quadtree空间索引 #

Quadtree通过将空间划分为象限，只检查光线所在区域的墙体，大幅减少碰撞检测次数。以下是适配SVG场景的简化实现：

Quadtree类实现 #

class Quadtree {
  constructor(bounds, maxDepth = 4, maxSegments = 10) {
    this.bounds = bounds; // { x, y, width, height }
    this.maxDepth = maxDepth;
    this.maxSegments = maxSegments;
    this.segments = [];
    this.children = [];
  }

  insert(segment) {
    if (this.children.length > 0) {
      const child = this.getChildForSegment(segment);
      child ? child.insert(segment) : this.segments.push(segment);
      return;
    }

    this.segments.push(segment);
    if (this.segments.length > this.maxSegments && this.maxDepth > 0) {
      this.split();
      this.segments.forEach(seg => {
        const child = this.getChildForSegment(seg);
        child ? child.insert(seg) : this.segments.push(seg);
      });
      this.segments = [];
    }
  }

  split() {
    const { x, y, width, height } = this.bounds;
    const halfWidth = width / 2;
    const halfHeight = height / 2;

    this.children.push(
      new Quadtree({ x, y, width: halfWidth, height: halfHeight }, this.maxDepth - 1),
      new Quadtree({ x: x + halfWidth, y, width: halfWidth, height: halfHeight }, this.maxDepth - 1),
      new Quadtree({ x, y: y + halfHeight, width: halfWidth, height: halfHeight }, this.maxDepth - 1),
      new Quadtree({ x: x + halfWidth, y: y + halfHeight, width: halfWidth, height: halfHeight }, this.maxDepth - 1)
    );
  }

  getChildForSegment(segment) {
    const midX = (segment.x1 + segment.x2) / 2;
    const midY = (segment.y1 + segment.y2) / 2;
    const { x, y, width, height } = this.bounds;
    const halfWidth = width / 2;
    const halfHeight = height / 2;

    if (midX < x + halfWidth) {
      if (midY < y + halfHeight) return this.children[0];
      else if (midY < y + height) return this.children[2];
    } else if (midX < x + width) {
      if (midY < y + halfHeight) return this.children[1];
      else if (midY < y + height) return this.children[3];
    }
    return null;
  }

  queryRay(ray) {
    let candidates = [...this.segments];
    this.children.forEach(child => {
      if (this.rayIntersectsBounds(ray, child.bounds)) {
        candidates = candidates.concat(child.queryRay(ray));
      }
    });
    return candidates;
  }

  rayIntersectsBounds(ray, bounds) {
    const { x, y, width, height } = bounds;
    const minX = x, maxX = x + width;
    const minY = y, maxY = y + height;

    let tMin = (minX - ray.x1) / (ray.x2 - ray.x1);
    let tMax = (maxX - ray.x1) / (ray.x2 - ray.x1);
    if (tMin > tMax) [tMin, tMax] = [tMax, tMin];

    let tYMin = (minY - ray.y1) / (ray.y2 - ray.y1);
    let tYMax = (maxY - ray.y1) / (ray.y2 - ray.y1);
    if (tYMin > tYMax) [tYMin, tYMax] = [tYMax, tYMin];

    if (tMin > tYMax || tYMin > tMax) return false;
    const tNear = Math.max(tMin, tYMin);
    const tFar = Math.min(tMax, tYMax);
    return tFar >= 0 && tNear <= 1;
  }
}

在组件中集成Quadtree #

1. 新增状态存储Quadtree：

const [quadtree, setQuadtree] = useState(null);

2. 在文件上传后初始化Quadtree：

// 在handleFileUpload的setTimeout中：
const viewBoxValues = svgRef.current.viewBox.baseVal;
const bounds = {
  x: viewBoxValues.x,
  y: viewBoxValues.y,
  width: viewBoxValues.width,
  height: viewBoxValues.height
};
const tree = new Quadtree(bounds);
wallSegments.forEach(seg => tree.insert(seg));
setQuadtree(tree);

3. 修改光线投射逻辑，仅查询候选线段：

const castRays = useCallback((origin) => {
  if (!quadtree) return;

  const newRays = [];
  rayAngles.forEach(({ cos, sin }) => {
    const ray = {
      x1: origin.x,
      y1: origin.y,
      x2: origin.x + rayLength * cos,
      y2: origin.y + rayLength * sin
    };

    let closestIntersection = null;
    let minDistance = Infinity;

    // 只查询可能与光线相交的线段
    const candidateSegments = quadtree.queryRay(ray);
    candidateSegments.forEach(segment => {
      const intersection = getIntersectionWithSegment(ray, segment);
      if (intersection) {
        const distance = (intersection.x - ray.x1) ** 2 + (intersection.y - ray.y1) ** 2;
        if (distance < minDistance) {
          minDistance = distance;
          closestIntersection = intersection;
        }
      }
    });

    newRays.push(closestIntersection ? {
      x1: origin.x, y1: origin.y,
      x2: closestIntersection.x, y2: closestIntersection.y
    } : ray);
  });

  setRays(newRays);
}, [rayAngles, quadtree, getIntersectionWithSegment, rayLength]);

额外优化点 #

• 减少光线数量：根据实际FoV需求调整numRays，无需盲目追求高密度
• 渲染优化：给光线组添加CSS样式，避免缩放时线条变粗：

.rays line {
  vector-effect: non-scaling-stroke;
}

• 距离计算优化：保持使用距离平方比较，避免开根号的性能开销

内容的提问来源于stack exchange，提问作者Dixkxhith