Порталы 1D: соединяем сектора

Подключим к BSP-обходу порталы между секторами одинаковой высоты. В таком случае общий сегмент двух секторов больше не должен вести себя как непрозрачная стена: через него нужно видеть геометрию следующего сектора.

Поэтому портальный сегмент мы пропускаем при отрисовке стены и не добавляем его диапазон X в список закрытых участков. Он становится не препятствием, а проходом: BSP продолжает отдавать дальние подсекторы в правильном порядке, и они могут быть нарисованы в оставшемся видимом пространстве.

Здесь важна совместная работа двух идей. BSP задает порядок от ближнего к дальнему, а список закрытых диапазонов показывает, какие части экрана уже окончательно заполнены непрозрачной геометрией. Без BSP дальняя стена могла бы закрыть ближнюю; без диапазонов пришлось бы снова и снова проверять участки экрана, которые уже невозможно изменить.

Обычные стены по-прежнему закрывают экран от ближних к дальним. Порталы, наоборот, оставляют проем открытым. В результате BSP задает корректный глобальный порядок, а одномерный список диапазонов быстро отбрасывает только те части стен, которые уже скрыты непрозрачной геометрией.

Wall ranges

Wall range — это интервал экранных колонок от xStart до xEnd, который уже полностью закрыт непрозрачной стеной. Поскольку BSP отдает стены от ближних к дальним, содержимое такой колонки больше не изменится: вся следующая геометрия в ней находится за уже нарисованной стеной.

В начале кадра список содержит два служебных диапазона за левой и правой границами экрана. Они ограничивают рабочую область значениями от 0 до ширины экрана и позволяют обрабатывать крайние стены тем же алгоритмом, без отдельных проверок для краев.

Перед рисованием каждой колонки isWallVisible проверяет, не входит ли ее X-координата в закрытый диапазон. После отрисовки addSolidRange добавляет только еще не закрытые части проекции стены. Поэтому диапазоны не перекрывают друг друга, а уже обработанные участки экрана быстро пропускаются.

Такой одномерный клиппинг подходит для сплошной стены: в этом шаге она закрывает колонку целиком потолком, стеной и полом. Портал оставляет внутри колонки видимый проем, поэтому его диапазон нельзя добавлять в wall ranges. Пока соседние секторы имеют одинаковую высоту пола и потолка, этого достаточно: через портал просто виден следующий сектор. Для порталов с разной высотой потребуется отдельное вертикальное отсечение, которое появится на следующем шаге.

Немного кода

Первый фрагмент показывает пропуск портальных сегментов: они не рисуются как стены и не закрывают экран. Следующие фрагменты описывают список закрытых диапазонов и проверку каждой экранной колонки перед рисованием непрозрачной стены.

  function render25d(
    ctx: CanvasRenderingContext2D,
    settings: Settings,
  ) {
    const camera = settings.camera;
    const allSegments = settings.level.linedefs;
    const bspTree = buildBSPTree(allSegments);
    const solidWallRanges = createSolidWallRanges(camera);

    traverseBSPTree(bspTree, camera, (bspNode: BSPLeaf) => {
      for (const seg of bspNode.segs) {
        const sector = seg.frontSector!;

        const projection = projectSeg(camera, sector, seg);

        if (!projection) {
          continue;
        }

        if (!isPortal(seg)) {
          drawSolidWall(ctx, camera, seg, projection, solidWallRanges);
        }
      }
    });
  }

  interface SolidSegmentRange {
    xStart: number;
    xEnd: number;
  }

  function createSolidWallRanges(camera: Camera) {
    const ranges: SolidSegmentRange[] = [];

    ranges.push({ xStart: Number.MIN_SAFE_INTEGER, xEnd: -1 });
    ranges.push({ xStart: camera.screen.width, xEnd: Number.MAX_SAFE_INTEGER });

    return ranges;
  }

  function drawSolidWall(
    ctx: CanvasRenderingContext2D,
    camera:Camera, 
    // .. 
    solidWallRanges: SolidSegmentRange[]
  ) {
    // ..
    const xStart = projection.start.screenX;
    const xEnd = projection.end.screenX;
    const xFrom = Math.max(0, Math.floor(Math.min(xStart, xEnd)));
    const xTo = Math.min(camera.screen.width - 1, Math.ceil(Math.max(xStart, xEnd)));
    // ..
    for (let x = xFrom; x <= xTo; x++) {
      if (!isWallVisible(x, solidWallRanges)) {
        continue;
      }
  
      // рисуем стены
    }
  
    addSolidRange(camera, xStart, xEnd, solidWallRanges);
  }