Розроблення алгоритму згладжування кутів

Основа графічного редактора – малювання. І чим воно краще реалізовано, тим кращим буде враження від програми. Використовуючи класичний принцип малювання (рис. 2.6.1) при досить великих швидкостях малювання, а відповідно, і досить великою відстанню між точками – отримана лінія виходить помітно ламаною.

Рис. 2.6.1 Результат малювання використовуючи класичні принципи

Задача алгоритму згладжування – позбавити лінію від різких кутів та зробити її більш гладкою (рис. 2.6.2), яка б не сприймалась як лінія побудована за малою кількість точок.

Рис. 2.6.2 Очікуваний результат роботи алгоритму згладжування

Реалізувавши простий алгоритм, в якому лінія будується прямими відрізками від точки попереднього дотику до точки поточного дотику, можемо отримати результат, зображений на рис. 2.6.3. Також до лінії були додані кола, діаметр яких дорівнює товщині лінії та розміщуються вони в точці поєднання двох ліній. Таке вдосконалення дозволило не допустити розривів лінії при досить великих кутах з’єднання відрізків та разом з тим трішки згладити різкі кути, зробивши їх більш гладкими.

Рис. 2.6.3 Результат малювання без алгоритму згладжування

Розроблюючи алгоритм згладжування було прийнято рішення базуватись на алгоритмах побудови кривих Безьє [http://3d-orange.com.ua/bezier-curves-for-your-games-tutorial/]. Крива Безьє будується за 4-ма точками (рис. 2.6.4).

Рис. 2.6.4 Побудова кривої Безьє

Згладжування відбуватиметься за принципом побудови кривої з урахуванням попередньої та пост-попередньої точок в лінії, де початкова точка (Р0) – попередній дотик, кінцева точка (Р3) – поточний дотик. Контрольна точка 1 (Р1) направляє лінію від перед попереднього дотику так, щоб лінія починалась продовжуючи попередню лінію – точка, що продовжує лінію від перед попереднього дотику до попереднього дотику на довжину, що рівна 1/3 довжини відрізка від перед-попереднього дотику до попереднього. А контрольна точка 2 (Р2) розташована на 1/5 відрізка від контрольної точки 1 (Р1) до кінцевої точки (Р3). Ілюстрацію роботи такого алгоритму можна побачити на рис. 2.6.5.

Рис. 2.6.5 Ілюстрація роботи згладжування за допомогою кривих Безьє

Такий алгоритм (лістинг 2.6.1) суттєво покращив сприйняття лінії, зробив її більш гладкою та цільною (рис. 2.6.6), однак в ситуаціях, коли відстань між контрольними точками є нерівномірною, алгоритм допускає виникнення відхилень від лінії, порушуючи задуману користувачем форму лінії.

Рис. 2.6.6 Результат роботи алгоритму згладжування за допомогою кривих Безьє.

int coef = 6;

double ldx = historyProvider. getX(event.getPointerId(pointer), 1) - historyProvider. getX(event.getPointerId(pointer), 2);
double ldy = historyProvider. getY(event.getPointerId(pointer), 1) - historyProvider. getY(event.getPointerId(pointer), 2);

double vector1x = historyProvider. getX(event.getPointerId(pointer), 1) + (ldx / coef);
double vector1y = historyProvider. getY(event.getPointerId(pointer), 1) + (ldy / coef);

double kdx = event.getX(pointer) - historyProvider. getX(event.getPointerId(pointer), 0);
double kdy = event.getY(pointer) - historyProvider. getY(event.getPointerId(pointer), 0);

double vector2x = historyProvider. getX(event.getPointerId(pointer), 0) - (kdx / coef);
double vector2y = historyProvider. getY(event.getPointerId(pointer), 0) - (kdy / coef);

double fromX = historyProvider. getX(event.getPointerId(pointer), 1);
double fromY = historyProvider. getY(event.getPointerId(pointer), 1);

double toX = historyProvider. getX(event.getPointerId(pointer), 0);
double toY = historyProvider. getY(event.getPointerId(pointer), 0);

double beginX;
double beginY;
double endX = fromX;
double endY = fromY;
for (double t = 0.1; t < 1; t += 0.1) {
beginX = endX;
beginY = endY;
endX = (Math. pow ((1 - t), 3) * fromX + 3 * Math. pow ((1 - t), 2) * t * vector1x + 3 * (1 - t) * Math. pow (t, 2) * vector2x + Math. pow (t, 3) * toX);
endY = (Math. pow ((1 - t), 3) * fromY + 3 * Math. pow ((1 - t), 2) * t * vector1y + 3 * (1 - t) * Math. pow (t, 2) * vector2y + Math. pow (t, 3) * toY);

invalidateAreaCalculator. add(
(int) endX,
(int) endY,
(int) brushSize);
draw. canvas. drawLine(
(float) beginX,
(float) beginY,
(float) endX,
(float) endY,
paint);
draw. canvas. drawCircle(
(float) endX,
(float) endY,
size / 2,
paint);
draw. canvas. drawCircle(
(float) endX,
(float) endY,
size / 2,
paint);

Лістинг 2.6.1 Алгоритм згладжування за допомогою кривих Безьє

В рамках вдосконалення алгоритму Безьє вирішити цю проблему не вдавалось. Саме тому було прийнято рішення про розробку принципово нового алгоритму. В основу нового алгоритму взято формули розділу фізики «Кінематика», зокрема формули, подібні до формул гравітаційного притягання. Ідея алгоритму у тому, що лінія – це шлях по якому біжить уявна точка прямуючи до точки дотику (рис. 2.6.7).

private float cx = -1, cy = -1;
private float vx = 0, vy = 0;
private float m = 50;
private float rubbingCoefficient = 0.8f;

Лістинг 2.6.2 Набір змінних для згладжування

Для кожного об’єкта на екрані створюється набір змінних (лістинг 2.6.2), де сх та су – уявне положення точки. Коли користувач ставить палець на екран, ця точка встановлюється в місце дотику, а під час руху пальцем вона переміщується згідно з алгоритмом (лістинг 2.6.3), vx, vy – уявні швидкості точки, m – уявна маса точки, а коефіцієнт rubbingCoefficient – це коефіцієнт тертя точки об поверхню малюнка, що не дозволяє точці рухатись навколо пальця вічно.

Рис. 2.6.7 Ілюстрація роботи нового алгоритму

float lcx = cx, lcy = cy;
float iterations = 5;
for (float i = 0; i < iterations; i++) {
float Fx = x2- cx;
float Fy = y2- cy;
float ax = Fx / m;
float ay = Fy / m;
vx *= rubbingCoefficient;
vy *= rubbingCoefficient;
vx += ax;
vy += ay;
cx += vx;
cy += vy;
if (lcx!= cx && lcy!= cy){
float curSize = lastSize + (size - lastSize)*(i / iterations);
drawCircle(cx, cy, curSize);
drawLine(lcx, lcy, cx, cy, curSize);
}
lcx = cx;
lcy = cy;
}

Лістинг 2.6.3 Робота алгоритму згладжування під час переміщення пальця

Кожен маленький відрізочок лінії, намальованої користувачем, ділиться на 5 частин, що являють собою 5 кроків алгоритму, або ж відрізок t=5 з точки зору фізики. Для розрахунку кожної наступної точки розраховується сила, що діє на точку, враховуючи відстань до цільової точки, прискорення, яке отримує точка, враховуючи її уявну масу, швидкість точки з урахуванням тертя, та сумарна швидкість точки на цьому кроці. Згідно з цими даними, розраховується положення наступної точки. Якщо положення змінилось, лінія від попередньої точки до розрахованої точки відмальовується на екрані.

Після довгого підбору коефіцієнтів можна досягти такого згладжування, яке б дозволило зробити лінію плавною при будь-яких умовах з невеликим відхиленням від її траєкторії (рис. 2.6.8). Зокрема, якщо зменшити силу тертя, можна побачити, як лінія почне «кружляти» навколо пальця так, наче уявна точка попала до нього на орбіту (рис. 2.6.9). А якщо збільшити – отримана лінія виродиться в таку, яка б була намальована без згладжування, при цьому вона не встигатиме досягти пальця, тому буде сильно відхилятись від траєкторії (рис. 2.6.10).

Рис. 2.6.8 Зразок роботи кінематичного алгоритму згладжування з оптимальними коефіцієнтами

Рис. 2.6.9 Зразок роботи кінематичного алгоритму згладжування зі зменшеним коефіцієнтом тертя

Рис. 2.6.10 Зразок роботи кінематичного алгоритму згладжування зі збільшеним коефіцієнтом тертя

Остаточним варіантом алгоритму було залишено кінематичний алгоритм згладжування, зі зразком роботи якого можна ознайомитись на рис. 2.6.8. Поруч із алгоритмом на кривих Безьє він забезпечує кращий результат не допускаючи відхилень в напрямку руху лінії. Крім того, такий алгоритм обчислювально є набагато менш складним, так як взагалі не має в собі затратних операцій, таких як піднесення до квадрата, куба, або коренів. Також розраховуючи кожну наступну координату враховується положення усіх попередніх координат та разом з тим це не ускладнює формули і розрахунки можна виконувати «на льоту», не відкладаючи згладжування на момент, коли вся лінія буде домальована.

Дата добавления: 2015-08-09