BSP-дерево и алгоритм художника: порядок отрисовки для любой точки зрения

Коротко

BSP-дерево (двоичное разбиение пространства) режет плоскость прямой одного из отрезков сцены на две половины, каждую - прямой другого отрезка, и так далее. Отрезок, который прямая пересекает, режется на два куска. Зачем: для любой точки зрения обход дерева «сначала дальняя половина, потом прямая узла, потом ближняя» даёт порядок отрисовки сзади вперёд - алгоритм художника без сортировки по расстоянию, которая на перекрывающихся объектах ошибается. Для n непересекающихся исходных отрезков случайный порядок разрезов даёт в ожидании O(n · log n) кусков; в худшем случае нужно Θ(n · log n / log log n).

Если ты знаешь, как строится BSP-дерево, почему его обход даёт порядок художника и сколько кусков получается при случайном порядке разрезов, листай до «Теперь сам».

Как думаешь, в каком порядке рисовать

Игра рисует стены лабиринта, и у видеокарты 1990-х нет буфера глубины: что нарисовано позже, то и видно. Значит, стены надо рисовать от дальних к ближним, как художник, который пишет сначала горы, потом деревья. Самое простое - отсортировать стены по расстоянию до зрителя.

Ответь себе до чтения: всегда ли это работает? Середина длинной стены может быть далеко, а ближний конец заслоняет короткую стену. На тридцати случайных стенах сортировка по расстоянию до середины даёт 15 нарушений порядка отрисовки; обход BSP - ни одного.

На что это похоже

Карточки в библиотеке можно раскладывать вопросами: «до или после буквы М?», затем «до или после Т?». Каждый вопрос делит текущую стопку. BSP-дерево задаёт вопросы про пространство: «по эту сторону стены или по ту?». Для любой точки зрения ответы определяют порядок отрисовки.

Механизм: разрезы прямыми отрезков и обход

Построение (авторазбиение). Взять отрезок, провести через него прямую. Остальные отрезки: целиком спереди - в переднее поддерево, целиком сзади - в заднее, пересекающие прямую - разрезать на два куска. На прямой - хранить в узле. «Спереди» - сторона, где поворот c, d, x положителен: слева от направления c → d. Повторить в каждой половине.

Порядок художника. Для зрителя v в узле с прямой l: если v спереди l, то любой луч из v сначала идёт по передней половине и лишь потом, перейдя l, по задней, - ничто сзади не может заслонить то, что спереди. Значит: нарисовать заднее поддерево, потом отрезки на l, потом переднее. Если v сзади - наоборот; на прямой - любой порядок верен. Обход стоит O(число кусков), а дерево строится один раз для всех точек зрения.

Прямая отрезка A режет плоскость на две половины и отрезок C на два куска. Для зрителя спереди A сначала рисуется задняя половина (D, C₂), потом A, потом передняя (B, C₁).

Сколько кусков. Пусть исходные отрезки не имеют общих внутренних точек. Плохой порядок разрезов может дать много кусков. Если разрезающие отрезки брать в случайном порядке, отрезок s режется прямой отрезка t, только если t выбран раньше всех отрезков, которые прямая t встречает между t и s: пройди по прямой от t до s - отрезок, пересечённый по дороге и выбранный раньше, отрежет s от неё. Вероятность этого - 1 / (число таких отрезков + 2), и сумма по всем парам даёт в ожидании не больше n + 2n · ln n кусков (де Берг и соавторы) - для отрезков без общих внутренних точек: решётка из пересекающихся отрезков даёт n² кусков при любом порядке. Нижняя граница для худшего входа - Ω(n · log n / log log n) (Тот), и она точная.

Правило

BSP-дерево режет плоскость прямыми отрезков сцены, разрезая пересекаемые отрезки. Обход «дальняя половина, узел, ближняя половина» даёт порядок отрисовки сзади вперёд для любой точки зрения. Случайный порядок разрезов даёт O(n · log n) кусков в ожидании для непересекающихся исходных отрезков на плоскости. Точность: кусок храни как исходный отрезок и интервал параметра - тогда при целых координатах сцены и зрителя все проверки сторон идут в целых.

Разбор: сколько кусков при случайном порядке

Короткие случайные отрезки, по пять перемешиваний на каждый размер. Кусок - номер исходного отрезка и дроби t0, t1: сторона конца куска относительно прямой - линейная функция t, и её знак считается в целых. Точка a + t(b − a) даёт поворот p0 + t · k, где p0 - поворот для a, а k - для направления b − a. На прямой он ноль - отсюда точка разреза t = −p0 / k. Отрезки опыта иногда пересекаются: это замер, не проверка оценки.

import random

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def storona(otr, j, kusok):
    # знаки концов куска относительно прямой отрезка j; кусок -
    # [i, t0, z0, t1, z1]: точка a + (t / z)(b - a) исходного отрезка i
    c, d = otr[j]
    a, b = otr[kusok[0]]
    p0 = povorot(c, d, a)
    k = (d[0] - c[0]) * (b[1] - a[1]) - (d[1] - c[1]) * (b[0] - a[0])
    s0 = kusok[2] * p0 + kusok[1] * k
    s1 = kusok[4] * p0 + kusok[3] * k
    return [s0, s1, p0, k]

def postroit(otr, kuski):
    # узел: [номер разрезающего, куски на его прямой, спереди, сзади]
    if len(kuski) == 0:
        return None
    j = kuski[0][0]
    na_pryamoj = [kuski[0]]
    speredi = []
    szadi = []
    for kusok in kuski[1:]:
        s0, s1, p0, k = storona(otr, j, kusok)
        if s0 == 0 and s1 == 0:
            na_pryamoj.append(kusok)
        elif s0 >= 0 and s1 >= 0:
            speredi.append(kusok)
        elif s0 <= 0 and s1 <= 0:
            szadi.append(kusok)
        else:
            # разрезать в точке t = -p0 / k
            tn = -p0
            tz = k
            if tz < 0:
                tn = -tn
                tz = -tz
            i = kusok[0]
            pervyj = [i, kusok[1], kusok[2], tn, tz]
            vtoroj = [i, tn, tz, kusok[3], kusok[4]]
            if s0 > 0:
                speredi.append(pervyj)
                szadi.append(vtoroj)
            else:
                szadi.append(pervyj)
                speredi.append(vtoroj)
    return [j, na_pryamoj, postroit(otr, speredi), postroit(otr, szadi)]

def kuskov(uzel):
    if uzel == None:
        return 0
    return len(uzel[1]) + kuskov(uzel[2]) + kuskov(uzel[3])

def nabor(n):
    # n коротких отрезков в квадрате 1000 × 1000
    otr = []
    for i in range(n):
        x = random.randint(0, 1000)
        y = random.randint(0, 1000)
        otr.append([[x, y], [x + random.randint(-100, 100),
                             y + random.randint(-100, 100)]])
    return otr
import math
random.seed(3)
for n in [25, 50, 100]:
    otr = nabor(n)
    poryadok = list(range(n))
    vsego = 0
    for t in range(5):
        random.shuffle(poryadok)
        kuski = []
        for i in poryadok:
            kuski.append([i, 0, 1, 1, 1])
        vsego = vsego + kuskov(postroit(otr, kuski))
    print(n, vsego / 5, round(vsego / 5 / n, 2), round(math.log2(n), 2))

25 28.8 1.15 4.64
50 77.2 1.54 5.64
100 176.6 1.77 6.64

Кусков на отрезок 1,15, 1,54, 1,77 - растёт медленно, как логарифм (последний столбец - log₂ n). Отрезки здесь короткие, прямые режут их редко, и множитель далёк от оценки 2 ln n: оценка - потолок.

Разбор: художник против сортировки по расстоянию

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

import random

def povorot(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def storona(otr, j, kusok):
    c, d = otr[j]
    a, b = otr[kusok[0]]
    p0 = povorot(c, d, a)
    k = (d[0] - c[0]) * (b[1] - a[1]) - (d[1] - c[1]) * (b[0] - a[0])
    s0 = kusok[2] * p0 + kusok[1] * k
    s1 = kusok[4] * p0 + kusok[3] * k
    return [s0, s1, p0, k]

def postroit(otr, kuski):
    if len(kuski) == 0:
        return None
    j = kuski[0][0]
    na_pryamoj = [kuski[0]]
    speredi = []
    szadi = []
    for kusok in kuski[1:]:
        s0, s1, p0, k = storona(otr, j, kusok)
        if s0 == 0 and s1 == 0:
            na_pryamoj.append(kusok)
        elif s0 >= 0 and s1 >= 0:
            speredi.append(kusok)
        elif s0 <= 0 and s1 <= 0:
            szadi.append(kusok)
        else:
            tn = -p0
            tz = k
            if tz < 0:
                tn = -tn
                tz = -tz
            i = kusok[0]
            pervyj = [i, kusok[1], kusok[2], tn, tz]
            vtoroj = [i, tn, tz, kusok[3], kusok[4]]
            if s0 > 0:
                speredi.append(pervyj)
                szadi.append(vtoroj)
            else:
                szadi.append(pervyj)
                speredi.append(vtoroj)
    return [j, na_pryamoj, postroit(otr, speredi), postroit(otr, szadi)]
import math

def obhod(otr, uzel, v, poryadok):
    # от дальнего к ближнему: сначала сторона, где зрителя нет
    if uzel == None:
        return
    c, d = otr[uzel[0]]
    if povorot(c, d, v) > 0:
        obhod(otr, uzel[3], v, poryadok)
        for kusok in uzel[1]:
            poryadok.append(kusok)
        obhod(otr, uzel[2], v, poryadok)
    else:
        obhod(otr, uzel[2], v, poryadok)
        for kusok in uzel[1]:
            poryadok.append(kusok)
        obhod(otr, uzel[3], v, poryadok)

def koncy(otr, kusok):
    a, b = otr[kusok[0]]
    t0 = kusok[1] / kusok[2]
    t1 = kusok[3] / kusok[4]
    p = [a[0] + t0 * (b[0] - a[0]), a[1] + t0 * (b[1] - a[1])]
    q = [a[0] + t1 * (b[0] - a[0]), a[1] + t1 * (b[1] - a[1])]
    return [p, q]

def narusheniya(otr, kuski, v, luchej):
    # лучи из зрителя: ближний кусок должен рисоваться позже дальнего
    plohih = 0
    for r in range(luchej):
        ugol = 2 * math.pi * r / luchej
        dx = math.cos(ugol)
        dy = math.sin(ugol)
        popadaniya = []
        for nomer in range(len(kuski)):
            p, q = koncy(otr, kuski[nomer])
            ex = q[0] - p[0]
            ey = q[1] - p[1]
            zn = dx * ey - dy * ex
            if zn == 0:
                continue
            wx = p[0] - v[0]
            wy = p[1] - v[1]
            t = (wx * ey - wy * ex) / zn
            u = (wx * dy - wy * dx) / zn
            if t > 0 and 0 <= u <= 1:
                popadaniya.append([t, nomer])
        popadaniya.sort()
        for k in range(len(popadaniya) - 1):
            if popadaniya[k][1] < popadaniya[k + 1][1]:
                plohih = plohih + 1
    return plohih

random.seed(11)
otr = []
for i in range(30):
    x = random.randint(0, 1000)
    y = random.randint(0, 1000)
    otr.append([[x, y], [x + random.randint(-300, 300),
                         y + random.randint(-300, 300)]])
v = [500, 500]
kuski = []
for i in range(len(otr)):
    kuski.append([i, 0, 1, 1, 1])
random.shuffle(kuski)
derevo = postroit(otr, kuski)
poryadok = []
obhod(otr, derevo, v, poryadok)
print(len(otr), len(poryadok), narusheniya(otr, poryadok, v, 90))
# наивно: целые отрезки по расстоянию до середины, дальние первыми
pary = []
for i in range(len(otr)):
    a, b = otr[i]
    mx = (a[0] + b[0]) / 2 - v[0]
    my = (a[1] + b[1]) / 2 - v[1]
    pary.append([-(mx * mx + my * my), [i, 0, 1, 1, 1]])
pary.sort()
naivno = []
for para in pary:
    naivno.append(para[1])
print(len(naivno), narusheniya(otr, naivno, v, 90))

30 61 0
30 15

BSP разрезал 30 стен на 61 кусок, и на 90 лучах ни одной ошибки порядка. Сортировка по расстоянию до середины - 15 нарушений (пар соседних попаданий на луче в неверном порядке): длинная стена, середина которой далеко, у своего ближнего конца заслоняет стену, середина которой ближе. Никакая сортировка по одному числу этого не исправит: бывают стены, заслоняющие друг друга по кругу, и их надо разрезать - ровно это BSP и делает.

Лучи считаются во float: это свидетель, а не предикат алгоритма - сам BSP строится и обходится в целых.

Что ломается без этого

Сортировка по расстоянию. Годится для мелких объектов, на длинных стенах ломается - второй разбор.

Разрезанные куски в float. Конец куска чуть сдвигается, и следующая прямая относит его не к той стороне - кусок попадает в чужое поддерево и рисуется не в свой момент. Параметр-дробь держит всё точно.

Фиксированный порядок разрезов (по длине, по номеру): для него есть сцены с квадратичным числом кусков.

Зачем это в работе

Doom (1993) рисовал уровни обходом заранее построенного BSP-дерева - отсюда скорость. Сегодня глубину решает видеокарта, а BSP остались в редакторах уровней, булевых операциях над многогранниками и проверке столкновений.

Теперь сам

Зритель сзади прямой корня. В каком порядке обойти поддеревья?
Отрезки (0, 0)-(4, 0) и (2, −1)-(2, 3). Первым разрезающим взят первый. Сколько кусков у второго?
Почему одно BSP-дерево годится для любой точки зрения?

Ответ. 1. Сначала переднее поддерево (оно дальше от зрителя), потом отрезки корня, потом заднее.

Два: прямая y = 0 пересекает отрезок x = 2 в точке (2, 0) - куски (2, −1)-(2, 0) и (2, 0)-(2, 3).
Дерево зависит только от сцены. Точка зрения выбирает в каждом узле, какую половину обойти первой, - это одна проверка стороны на узел, а само дерево не меняется.

Главное

BSP-дерево отвечает на вопрос «что дальше» для любой точки зрения, потому что задаёт его прямыми самой сцены и разрезает то, что нельзя упорядочить целиком. Случайный порядок разрезов держит размер около n · log n.