Okg Clipping

Екранно отсичане (clipping)


страницата се нуждае от дописване/преглеждане


Увод

Както е споменато по-рано тук доста важен е въпросът за това, кое се вижда на екрана, и кое е покрито или извън екрана (и съответно - не се вижда). Ще разгледаме два елементарни алгоритъма, чрез които намираме каква част от отсечка или многоъгълник се намират в друг многоъгълник (отсичащ).

Отсичане на отсечка

Ще използваме алгоритъма на Cyrus-Beck. Честно казано - тези двамата не са измислили нищо особено - алгоритъмът е от прост по-прост. Да видим първо какво е дадено

  • отсечка с крайща $p_1p_2 = p$
  • изпъкнал многоъгълник $W = \{ f_1, f_2, \cdots, f_k \}$

Целта е в края на алгоритъма да получим нова отсечка $p'_1p'_2$ която е изцяло вътре в многоъгълника $W$. Разбира се допустимо е накрая да остане … нищо, защото отсечката е вън от многоъгълника.

Алгоритъмът

Ще разгледаме поотделно всички страни на многоъгълника и ще отсечем последователно отсечката със всяка от тях. Както виждате задачата се свежда до отсичане на една отсечка (дадената) със друга отсечка (страна от многоъгълника), като разбира се от дадената отсечка остава тази част, която е във вътрешността на многоъгълника. Да разгледаме малко картинки:

line-segment-clipping-casesline-intersect-point

Аналитично задаване на отсечка

Първо ще покажем един начин за аналитично задаване на отсечката $p_1p_2$ чрез функция на един аргумент:

(1)
\begin{align} p(t) = p_1 + \overrightarrow{p_1p_2}t = p_1 + \overrightarrow{p}t \quad t \in [0, 1] \end{align}

Аргумента $t$ всъщност показва колко далече сме от началото на отсечката и в каква посока. Например $p(\frac{1}{2})$ е точно средата на отсечката, докато $p(-1)$ е централно симетричната на $p_2$ относно $p_1$. Точно заради това при $t \in [0, 1]$ функцията описва точно всички точки от отсечката.

Намиране на пресечна точка на две отсечки

Сигурно сте се досетили, че ще търсим пресечната точка на отсечката $p_1p_2$ със страните на многоъгълника $f_if_{i+1}$. Нека за всяка страна $f_if_{i+1}$ изберем нормалният вектор който сочи към вътрешността на многоъгълника - $n_i$. Сега ще изразим аналитично чрез $p(t)$ пресечната точка на $f_if_{i+1}$ и $p_1p_2$, като използваме факта, че скаларното произведени на 2 перпендикулярни вектора (именно $n_i$ и вектора образуван от $f_i$ и пресечната точка $p(t)$) е 0:

(2)
\begin{eqnarray} \overrightarrow{f_ip(t)}\overrightarrow{n_i} &=& 0 \\ (p(t) - f_i)\overrightarrow{n_i} &=& 0 \\ (p_1 + \overrightarrow{p}t - f_i)\overrightarrow{n_i} &=& 0 \\ (p_1 - f_i)\overrightarrow{n_i} + \overrightarrow{p}t\overrightarrow{n_i} &=& 0 \\ t &=& -\frac{(p_1 - f_i)\overrightarrow{n_i}}{\overrightarrow{p}\overrightarrow{n_i}} \\ \end{eqnarray}

Сега да видим каква информация събрахме до момента:

$t \in (-\infty, 0)$ пресечната точка е извън отсечката (преди началото)
$t \in [0, 1]$ пресечната точка е върху отсечката
$t \in (1, +\infty)$ пресечната точка е извън отсечката (след нея)

Освен това имаме и информация за това каква е ориентацията на отсечката спрямо страната - т.е дали $p_1$ е по-близо (по ъгъл) до вътрешността или $p_2$. Знака на знаменателя определя косинуса между векторите $\overrightarrow{p}$ и $\overrightarrow{n_i}$.

$\overrightarrow{p}\overrightarrow{n_i} < 0$ ъгълът е $> 90^\circ$, т.е $p_1$ е по към вътрешността
$\overrightarrow{p}\overrightarrow{n_i} = 0$ ъгълът е $90^\circ$, т.е $\overrightarrow{p} \| \overrightarrow{f_if_{i+1}}$. В този случай не трябва да търсим $t$ иначе ще делим на 0
$\overrightarrow{p}\overrightarrow{n_i} > 0$ ъгълът е $< 90^\circ$, т.е $p_2$ е по към вътрешността

Следната таблица обединява горните две за да се види в кой точно случай се намираме:

$\overrightarrow{p}\overrightarrow{n_i} < 0$ $\overrightarrow{p}\overrightarrow{n_i} > 0$
$t \in (-\infty, 0)$ 3 4
$t \in [0, 1]$ 2 1
$t \in (1, +\infty)$ 4 3

След като разбрахме в кой случай се намираме, остава да отрежем отсечката по подходящ начин и да продължим нататък. За да си улесним живота, ще пазим просто горна и долна граница на $t$, когато отсичаме. Примерно ако се окаже, че отсечката е отсечена през средата и остава частта със $p_2$, то записваме, че отсечката започва минимум от $t = \frac{1}{2}$, защото по-малките $t$ са извън многоъгълника. Съответно ако остава частта съдържаща $p_1$ то отбелязваме, че отсечката стига максимум до $t = \frac{1}{2}$, защото по-големите $t$ са извън многоъгълника. Ето табличен израз на последното:

случай \ начални стойности $t_{min} = 0 \quad t_{max} = 1$
1 $t_{max} = \min\{ t_{max}, t \}$ при нов кандидат за максимум избираме по-малкия, защото точките по-големи от кой да е от тях са извън отсечката
2 $t_{min} = \max\{ t_{min}, t \}$ при нов кандидат за минимум избираме по-големия, защото точките по-малки от кой да е от тях са извън отсечката
3 $t_{min} = 1$ по този начин ефективно затриваме цялата отсечка
4 $t_{max} = 0$ по този начин ефективно затриваме цялата отсечка

Отсичане на многоъгълник

Алгоритъмът

За всяка отсечка от отсичащия многоъгълник и всяка отсечка от отсичания многоъгълник правим горния алгоритъм. После това което остане от всички отсечки го сглобяваме и полученият франкещайн е отсечения многоъгълник.

Естествено, има и други начини (пр. Sutherland-Hodgman clipping algorithm, Weiler-Atherton clipping algorithm и др.). Ако някой желае, да се чувства свободен да ги сподели.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License