Я пробую алгоритм на бумаге, чтобы треугольник имел точки (0; 0), (1; 0), (1, 1/2), но получил ответ, который я считаю неправильным (расчет приведен ниже):
http://faculty.cs.tamu.edu/schaefer/research/wavelet_rasterization.pdf
Основная идея заключается в том, что этот алгоритм вычисляет покрытия полигонов области фракции внутри квадратной области с помощью вейвлетов Хаара, если полигон охватывает всю область, а значение равно 1, если половина 1/2 и т. Д. Затем алгоритм подразделяет эту квадратную область (квадрант) и вычисляет коррекция для следующего уровня более высокого разрешения. Размер области всегда равен двум и перестает делиться, когда размер области становится 1 х 1 пикселем. Нужно только подразделять квадранты этой квадратной области, если внутри этого квадранта есть ребро многоугольника (я думаю, квадрант имеет значение меньше 1 или больше 0).
Для расчета вейвлет-коэффициентов c_xx алгоритм всегда нормализует ребра многоугольника с координатами 0 ≤ x ≤ 1; 0 ≤ y ≤. После вейвлет-коэффициентов можно использовать это уравнение (если я правильно понял):
g (p) = (++ c_00) • Ψ_00 + (++ c_10) • Ψ_10 + (++ c_01) • Ψ_01 + (++ c_11) • Ψ_11
для расчета стоимости в каждом квадранте. Я предполагаю, что g (p) - квадрант покрытия полигонов области фракции.
Ψ_00; Ψ_10, Ψ_01, Ψ_11 - вейвлет-функции Хаара на рисунке 2.
Для применения алгоритма первая сумма (++ c_00) использует ребра многоугольника внутри всей квадратной области
c_00 + = 1/2 • det (v_0; v_1)
v_0; v_1 - конечные точки одного ребра многоугольника, нормализуйте координаты относительно квадратной области (0 ≤ v_0; v_1 ≤ 1).
Для вычисления трех других сумм ++ c_10, ++ c_01, ++ c_11, подразделите ребра многоугольника в каждом квадранте и нормализуйте в каждом квадранте. Обозначение статьи для 4 квадрантов:
Q_00: левый нижний субрегион
Q_10: правый нижний субрегион
Q_01: левый верхний субрегион
Q_11: правый верхний субрегион
Уравнения для расчета сумм для c_10, c_01 и c11 в приложении A к бумаге (я не хочу их вводить здесь).
РАСЧЕТ
Для эксперимента я использую этот треугольник с ребрами (уже нормализовано)
(0; 0) - (1; 0)
(1; 0) - (1, 1/2)
(1, 1/2) - (0; 0)
Треугольник и квадранты. Координата ребер в квадранте Q00 и Q10, нормализованных в каждом квадранте
рассчитать c_00
Край (0; 0) - (1; 0)
c_00 = 1/2 • (0 • 0 - 1 • 0) = 0
Край (1; 0) до (1, 1/2)
c_00 = 1/2 • (1 • 1/2 - 1 • 0) = 1/4
Край
c_00 = 1/2 • (1 • 0 - 0 • 1/2) = 0
Сумма c_00 для всех 3 ребер:
++ c_00 = 0 + 1/4 + 0 = 1/4 (треугольник покрывает 1/4 площади квадратной области, это число выглядит правильно)
рассчитать c_10, c_01, c_11
Край (0; 0) - (1; 0) в двух кандрантах Q_00 и Q_10
Q_00: от (0; 0) до (1/2; 0) нормализуются становятся -> (0; 0) до (1; 0)
Q_10: от (1/2; 0) до (1; 0) нормализуются -> (0; 0) до (1; 0)
Lx_00 = 1/8 • (0 - 0) • (0 + 1) = 0
Ly_00 = 1/8 • (1 - 0) • (0 + 0) = 0
Kx_10 = 1/4 • (0 - 0) = 0
Lx_10 = 1/8 • (0 - 0) (0 + 1) = 0
Ly_10 = 1/8 • (1 - 0) (0 + 0) = 0
c_10 = 0
c_01 = 0
c_11 = 0
Край (1; 0) - (1; 1/2) только в квадранте Q_10
Q_10: от (1: 0) до (1; 1/2) нормализуются -> (1; 0) до (1; 1)
Kx_10 = 1/4 • (0 - 1) = -1/4
Lx_10 = 1/8 • (0 - 1) (1 + 1) = -1/4
Ly_10 = 1/8 • (0 - 0) (1 + 0) = 0
c_10 = 0 + 0 + -1/4 - (-1/4) + 0 + 0 = 0
c_01 = 0 + 0 + 0 - 0 + 0 - 0 = 0
c_11 = 0 - 0 + -1/4 - (-1/4) - 0 + 0 = 0
Край (1; 1/2) - (0; 0) в двух квадрантах Q_00 и Q_10
Q_00: от (1/2; 1/4) до (0; 0) нормализуются от -> (0; 0) до (1; 1/2)
Q_10: от (1; 1/2) до (1/2; 1/4) нормализуются становятся -> (1; 1) до (0; 1/2)
Lx_00 = 1/8 • (1/2 - 0) • (0 + 1) = 1/16
Ly_00 = 1/8 • (0 - 1) • (0 + 1/2) = -1/16
Kx_10 = 1/4 • (1 - 1/2) = 1/8
Lx_10 = 1/8 • (1 - 1/2) (0 + 1) = 1/16
Ly_10 = 1/8 • (0 - 1) (1 + 1/2) = -1 / 8 * (3/2) = -3/16
c_10 = 1/16 + 0 + 1/8 - (1/16) + 0 - 0 = 1/8
c_01 = -1/16 + -3/16 + 0 - 0 + 0 + 0 = -1/4
c_11 = 1/16 - 0 + 1/8 - (1/16) -0 + 0 = 1/8
++ c_00 = 1/4
++ c_10 = 1/8
++ c_01 = -1/4
++ c_11 = 1/8
Рассчитать окончательный результат:
g00 = c00 + c10 + c01 + c11 = 1/4 + 1/8 + (-1/4) + 1/8 = 1/4
g10 = c00 - c10 + c01 - c11 = 1/4 - 1/8 + (-1/4) - 1/8 = -1/4
g01 = c00 + c10 - c01 - c11 = 1/4 + 1/8 - (-1/4) - 1/8 = 1/2
g11 = c00 - c10 - c01 + c11 = 1/4 - 1/8 - (-1/4) + 1/8) = 1/2
Но я думаю, правильный результат должен рассчитать:
g00 = 1/4
g10 = 3/4
g01 = 0
g11 = 0