Реализация инструмента графического комментирования на виртуальной доске на графических потоковых процессорах

Андрей Юрьевич Сморкалов

аспирант, лаборатория систем мультимедиа

Поволожский Государственный Технический Университет,

пл. Ленина, 3, г. Йошкар-Ола, 420000, +7-836-2-686090

asmorkalov@mail.ru


Аннотация

В данной статье предлагается метод поддержки операций рисования для реализации образовательного инструмента графического комментирования на виртуальной доске в виртуальном мире c использованием вычислительных возможностей потоковых процессоров. Предлагаемый метод имеет минимальные требования к аппаратному обеспечению и обеспечивает высокую производительность по сравнению с реализацией инструмента на центральном процессоре, особенно при использовании инструмента в 3D-среде. Предложены три метода оптимизации, позволяющие значительно ускорить реализацию инструмента на потоковых процессорах. Подробно описаны подходы к синхронизации рисунка на виртуальной доске в многопользовательской образовательной среде, позволяющие сократить объем сетевых пакетов синхронизации.

This paper is devoted to method of drawing operations support via graphics stream processors for development of whiteboard educational tool for virtual blackboard in  virtual world. Suggested method has minimal system requirements and provides high performance in comparison with CPU-based version. Highest performance is provided if tool was developed for 3d-graphics environment. Three additional optimization methods were suggested for significant speedup of whiteboard tool working via stream processors. Ways of virtual blackboard drawing synchronization  in multiuser educational environment are widely described. Significant reduce of size of synchronization net packets is one of advantages of suggested method.

Ключевые слова

обработка изображений, образовательные инструменты, графические потоковые процессоры, виртуальные образовательные миры, операции рисования;

image processing, educational tools, graphics stream processors, virtual educational worlds, drawing operations.

Введение

Электронное обучение уже не один десяток лет является полноценным направлением в развитии образования. Оборот индустрии электронного обучения превысил 50 миллиардов долларов [1], а в ведущих исследовательских институтах даже разработаны докторские программы, рассчитанные на онлайн-обучение [2].

Из синхронных форм образовательной деятельности в электронном обучении наибольшее распространение получили вебинары и виртуальные миры. Вебинары (например, [3]) дают ограниченный набор функциональности и возможностей, однако при этом предъявляют относительно низкие требования к аппаратному и программному обеспечению учащихся, что и стало залогом их успеха в настоящее время.

Стремительно набирающие популярность образовательные виртуальные миры требуют более мощного аппаратного обеспечения, однако в свою очередь предлагают гораздо больше возможностей для взаимодействия преподавателя и учащихся, в некоторых случаях предоставляя даже такие формы обучения, которые крайне проблематично применить в ходе даже обычного «живого» занятия. Между тем, стоит отметить, что все образовательные инструменты вебинаров присутствуют или технически могут присутствовать в виртуальных мирах [4].

Whiteboard доска для комментирования в форме рисунка впервые появилась еще в 1996 году в программном продукте CoolTalk корпорации Netscape, предназначенном для личного голосового общения через сеть интернет. Примерно в это же время подобная доска была реализована в Microsoft NetMeeting программе, ориентированной на групповое голосовое общение через сетевое соединение. Эти программные продукты часто использовались как инструменты CSCW [5] (computer supported collaborative work).

Параллельно шло развитие такого направления, как CSCL [6] (computer supported collaborative learning), и спустя несколько лет, whiteboard начинает массово появляться в вебинарах как мощный и эффективный образовательный инструмент. Whiteboard дает возможность быстро и эффективно передавать знания, поэтому этот инструмент нашел свое применение в вебинарах.

Доска для рисования может эффективно использоваться и виртуальных образовательных мирах, однако стоит отметить, что если в вебинарах используется одна доска, то виртуальные аудитории могут содержать в себе десятки досок, которыми одновременно могут пользоваться учащиеся. Этот факт означает повышенные требования к производительности операций рисования на виртуальных досках, особенно с учетом того, что большие вычислительные ресурсы тратятся в виртуальном мире на отображение 3D-среды, синхронизацию мира, загрузку ресурсов с удаленного сервера и другие задачи.

В вебинарах реализация whiteboard традиционно использует центральный процессор для осуществления расчетов. Теоретическая основа поддержки рисования в системах обработки изображения, работающих на центральном процессоре, детально разработана, а их многочисленные реализации стали широко известны (например, [7]).

Однако, при использовании потоковых процессоров классические алгоритмы (например, алгоритм Брезентхема [8]) оказываются неприменимы из-за архитектурных ограничений, что требует разработки методов поддержки операций рисования специально для использования с применением потоковых процессоров. Таким образом становится актуальной разработка математической и программной модели, а также методов и алгоритмов, позволяющих адаптировать работу инструмента whiteboard для исполнения на графических потоковых процессорах.

Математическая модель

Составим необходимую для решения задачи реализации инструмента «whiteboard» математическую модель обработки изображений на потоковых процессорах. Будем рассматривать изображение в цветовой модели RGBA:

U(x, y) = {fR(x, y), fG(x, y), fB(x, y), fA(x, y)}                        (1),

где fR(x, y), fG(x, y), fB(x, y), fA(x, y) это дискретные функции, заданные табличным методом. fR(x, y) представляет красный канал изображения, fG(x, y) - зеленый, fB(x, y) - синий, fA(x, y) - альфа-канал. Значения этих функций лежат в диапазоне [0, 1].

Результатом преобразования G изображения А на основе изображения B будем называть

R = G(A, B, x, y)                                                        (2),

где А это исходное изображение, B растеризуемая фигура, G преобразующая функция.

Цветовой маской будем называть множество

M = {MR, MG, MB, MA}                                                (3),

где MR, MG, MB, MA могут принимать значения из множества {0, 1}. Результатом преобразования G изображения А на основе изображения B с учетом цветовой маски M будем называть

Rq = Gq(A, B, M, x, y) = Gq(A, B, x, y) * Mq + A * (1 Mq)                (4),

где q любой из цветовых каналов.

Геометрическая фигура

S = {Vi, Fj, {r, g, b, a}}                                                (5)

задается множеством двумерных векторов вершин Vi и множеством индексов вершин Fj, а также цветом фигуры {r, g, b, a}. Растеризация представляет собой преобразование, результатом которого является изображение:

U(x, y) = GR(GP(S, MP))                                                (6),

где GR растеризующее преобразование, MP матрица проецирования, GP проецирующее преобразование. В результате проецирующего преобразования GP получается спроецированная фигура

SP = GP(S, MP) = {P, F, {r, g, b, a}}                                        (7)

Спроецированная фигура SP задается множеством двумерных векторов спроецированных вершин P с количеством элементов N, множеством индексов вершин F c количеством элементов M, а также цветом фигуры {r, g, b, a}. Отметим, что в свою очередь, что спроецированная вершина может быть найдена по формуле:

Pi = Vi * MP                                                        (8)

Растеризующее преобразование также может быть записано в форме GR(x, y) = {{r, g, b, a}, если существует тройка (F3 * k, F3 * k + 1, F3 * k + 2), где k целое число от 0 до M / 3 1, такая, что (x, y) принадлежит треугольнику, образованному вершинами Pi1 , Pi2 , Pi3, где i1 = F3 * k, i2 = F3 * k + 1, i3 = F3 * k + 2,  {0.0, 0.0, 0.0, 0.0} в противном случае}.

Время выполнения преобразования (2) может быть вычислено по формуле:

T = TПР + Т1 * W * H                                                (9),

где TПР время подготовки к преобразованию,

Т1 время расчета цвета одного пикселя, т.е. расчета (2),

W, H высота и ширина рассчитываемого изображения.

Традиционно геометрические фигуры отрисовывались с помощью центрального процессора на основе одного из специфичных для фигуры алгоритмов. Примерами могут служить, алгоритмы рисования линии: алгоритм Брезентхема [8], алгоритм DDA-линии [9], алгоритм Ву [10]. Однако, эти алгоритмы не подходят для растеризации фигур на потоковых процессорах в силу их архитектурных ограничений. Также стоит отметить, что геометрическая фигура не может быть растеризована по её аналитическому описанию с помощью потоковых графических процессоров без применения шейдерных программ, так как потоковые процессоры умеют оперировать только с такими понятиями как вершина и треугольник.

Теоретически, геометрическая фигура может быть отрисована непосредственно по аналитическому описанию с применением шейдерных программ, что свело бы эту задачу к задачам фильтрации. Однако, эффективность такого подхода невелика, т.к. фактическая площадь отрисовываемой фигуры может быть на порядки меньше, чем площадь растеризовываемого триангулированного прямоугольника. Даже если в качестве данного прямоугольника брать ограничивающий объем фигуры (bounding box), неэффективность подхода остается значительной (см. рис. 1).

Рис. 1: Замер производительности поддержки операций рисования с помощью растеризации по аналитическому описанию и с помощью триангуляции.

Поэтому для более эффективной реализации необходимо триангулировать геометрические фигуры, т.е. представлять их в форме выражения (5). Для триангуляции каждой фигуры предлагается использовать частный, наиболее оптимальный для нее метод триангуляции, т.к. триангуляция в общем виде избыточно сложна.

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

Триангуляции линии с учетом наклона и толщины.

Хотя, в общем случае, задача триангуляции линии имеет известные решения, в данном случае требуется получить результаты триангуляции в подходящем для потоковых процессорах виде множестве индексов F и множестве вершин V. Выведем формулы, определяющие эти множества.

Пусть известны точки (x1, y1) и (x2, y2) начало и конец линии, а также известна w толщина линии. Тогда надо найти вершины двух треугольников, составляющих линию: (x0', y0'), (x1', y1'), (x2', y2'), (x3', y3'). Очевидно, что

(x0', y0') = (x1 - dx, y1 + dy)                                                 (10)

(x1', y1') = (x1 + dx, y1 dy)                                         (11)

(x2', y2') = (x2 - dx, y2 + dy)                                                 (12)

(x3', y3') = (x2 + dx, y2 dy)                                         (13),

где (dx, dy) вектор смещения, который отражает толщину линии и её наклон, тогда

dx = (w / 2) * sin ψ                                                (14)

dy = (w / 2) * cos ψ, где                                                (15)

ψ угол наклона линии. Синус и косинус этого угла можно найти по формулам:

cos ψ = (x1 x2) / L                                                (16)

sin ψ = (y1 y2) / L,                                                (17)

где L =                                (18)

Таким образом множество вершин и множество индексов триангулированной линии:

V = {(x0', y0'), (x1', y1'), (x2', y2'), (x3', y3')}                                (19)

F = {0, 1, 2, 1, 2, 3}                                                (20)

Цвет фигуры для триангуляции значения не имеет, таким образом, выражений (19) и (20) достаточно для определения множества геометрической фигуры линии при заданном цвете.

Триангуляция прямоугольника

Хотя, в общем случае, задача триангуляции прямоугольника имеет известные решения, в данном случае требуется получить результаты триангуляции в подходящем для потоковых процессорах виде множестве индексов F и  множестве вершин V. Выведем формулы, определяющие эти множества.

Для триангуляции контура прямоугольника можно воспользоваться триангуляцией четырех его составляющих линий, а внутренняя часть прямоугольника легко представляется как одна линия. Пусть известны точки (x1, y1) и (x2, y2) верхняя левая и нижняя правая вершины прямоугольника и w толщина контура. Тогда для триангуляции контура достаточно триангулировать четыре линии c толщиной w:

1) (x1, y1) - (x1, y2)

2) (x2, y1) - (x2, y2)

3) (x1 + w / 2, y1) - (x2 - w / 2, y1)

4) (x1 + w / 2, y2) - (x2 - w / 2, y2)

Пусть V1 множество вершин линии 1, V2 линии 2 и так далее. Тогда множество вершин контура прямоугольника можно задать как:

V = V1 U V2 U V3 U V4                                                 (21)

Для задания множества индексов определим преобразование смещения индексов. Результатом преобразование смещения индексов Gio множества индексов F на индекс di будет:

F' = Gio(F, di) = {F1 + di, …, FN-1 + di}                                (22),

где N это количество элементов в множестве F.

Пусть F1 множество индексов линии 1, F2 линии 2 и так далее. Тогда множество индексов контура прямоугольника:

F = F1 U Gio(F2, 6) U Gio(F3, 12) U Gio(F4, 18)                        (23)

А для триангуляции внутренней части прямоугольника достаточно триангулировать линию (x1 + w / 2, (y1 + y2) / 2) - (x2 - w / 2, (y1 + y2) / 2) с толщиной |y2 y1| - w. Множество вершин и множество индексов триангулированной линии будут совпадать с (19), (20).

Таким образом, выражений (22) и (23) достаточно для определения множества геометрической фигуры прямоугольника при заданном цвете.

Триангуляция эллипса

Хотя, в общем случае, задачи триангуляции эллипса и контура эллипса имеют известные решения, в данном случае требуется получить результаты триангуляции в подходящем для потоковых процессорах виде множестве индексов F и множестве вершин VВыведем формулы, определяющие эти множества.

Будем считать, что триангуляция производится для эллипса, центр которого располагается в точке (0, 0). Для того, чтобы применить к триангулированному эллипсу центр (xс, yс) достаточно будет сдвинуть на вектор (xс, yс) все вершины триангулированного эллипса.

Для триангуляции контура эллипса достаточно найти упорядоченное множество точек, располагающихся на центральной линии контура, отстоящих друг от друга на некоторый угол dA. Для упрощения расчетов требуется, чтобы существовало целое положительное число K, такое что

dA * K = 360º                                                        (24)

Чем меньше будет угол dA, тем больше будет точность триангуляции. После этого достаточно пройти по множеству, соединяя каждую точку со следующей (а последнюю с первой), чтобы получить набор линий, триангуляция которых уже описана. Пусть один из радиусов эллипса w, а другой h, тогда координаты точек находятся по формулам

x' = w * cos ψ                                                        (25)

y' = h * sin ψ                                                        (26),

где ψ = dA * i, i целое число >= 0, ψ принадлежит [0º, 360º)

Тогда если множества индексов линий 1-4, это F1, F2, F3, F4 соответственно, то множество индексов контура прямоугольника:

Vкэ = V1 U V2 U ... U VK                                                (27)

Fкэ = F1 + Gio(F2, 6) + Gio(F3, 12) + ... + Gio(FN, (N 1) * 6)                (28)


Рис. 2. Пример триангуляции внутренней части эллипса

Для триангуляции внутренней части эллипса (рис. 2), достаточно найти упорядоченное множество T точек, располагающихся на центральной линии контура, отстоящих друг от друга на угол dA, который был использован для триангуляции контура эллипса. Триангулированная фигура будет состоять из всех возможных треугольников, первая вершина которых (0, 0), а две другие являются соседними точками на центральной линии контура. Таким образом, для множества вершин внутренней части эллипса:

Vвэ = {(0, 0)} U T                                                        (29)

Fвэ = {0, 1, 2, 0, 2, 3, 0, 3, 4,....0, N 1, N}                                (30),

где N это число элементов множества T

Таким образом, выражений (27), (28), (29), (30) достаточно для определения множества геометрической фигуры эллипса при заданном цвете.

На основе приведенной программой модели и предложенных формул базируется программная модель и алгоритм работы инструмента whiteboard.

Программные модель и архитектура

Программная модель обработки изображений на ГПП на основе математической модели, анализа архитектуры и особенностей потоковых процессоров и возможностей OpenGL подробно описана в [11]. В основе модели лежат четыре основных объекта: Texture, Drawing Target, Filter и Filter Sequence.

Texture - это изображение в форме выражения (1), хранимое в памяти графического потокового процессора.  Drawing Target - это объект, который определяет изображение-результат и цветовую маску. Filter - задает преобразование изображения, соответствуя преобразованию (2), и в общем случае представляет собой функцию  с набором предопределенных и пользовательских параметров, возвращающую цвет точки для заданных координат. Filter Sequence - задает последовательность нескольких фильтров с их параметрами, в общем случае позволяя организовать конвейер обработки.

Для поддержки операций рисования данная программная модель была расширена. Для каждого изображения создается объект RenderTarget, а также объект палитры инструментов. RenderTarget представляет собой абстракцию поверхности доски. Он содержит в себе основную текстуру, временную текстура и буфер глубины (24 бит). Размер основной и временной текстуры совпадают. Во временную текстуру сохраняется изображение из основной текстуры перед очередным этапом работы любого из инструментов. До окончания этапа содержимое временной текстуры может быть скопировано в основную, а поверх растеризована актуальная рисуемая фигура. Под этапом понимается полный цикл рисования одной фигуры (линии, прямоугольника и т.д).

Рис. 3. Архитектура инструмента

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

Такая архитектура позволяет позволяет добавлять новые инструменты поддержки рисования без изменений в базовой архитектуре. Взаимосвязи объектов приведены на рис. 3.

Поддержка прозрачности

При поддержке прозрачности должны учитываться требования:

1) Смешивание RGB-каналов должно производиться с учетом значения альфа-канала растеризуемой фигуры.

2) При растеризации фигуры на абсолютно непрозрачную точку изображения, значение альфа-канала не должно измениться.

3) При растеризации фигуры на абсолютно прозрачную точку изображения, значение альфа-канала должно увеличиться.

Для поддержки прозрачности предлагается использовать двухпроходное преобразование. Первый проход выражается преобразованием

G(C, D, x, y) = min(C(x, y) + D(x, y), 1.0)                                (31),

где C и D представляют собой функции одного и того же канала изображения. Это преобразование применяется только к альфа-каналу с помощью маски (3). Оно соответствует поддерживаемому аппаратно преобразованию с параметрами source factor = GL_ONE, destination factor = GL_ONE, blend mode = GL_FUNC_ADD.

Второй проход выражается преобразованием

G(А,B,x,y)q = min(A(x,y)q * B(x,y)A + (1.0B(x,y)A)*B(x,y)q), 1.0)        (32)

Преобразование (32) осуществляется только к RGB-каналам изображения. Оно соответствует поддерживаемому аппаратно преобразованию с параметрами source factor = GL_SRC_ALPHA, destination factor = GL_ONE_MINUS_SRC_ALPHA, blend mode = GL_FUNC_ADD. Результат такого двухпроходного преобразования будет удовлетворять вышеперечисленным требованиям

Основные инструменты

Для реализации инструмента «карандаш» используется описанное двухпроходное преобразование. Пусть требуется отрисовать линию от карандаша от точки (x1, y1) до точки (x2, y2), а его толщина составляет w. Для этого потребуется нарисовать серии частично перекрывающихся триангулированных окружностей радиуса w, количество которых равно:

КО = max(|x2 - x1|, |y2 y1|)                                                (33)

Центр i-окружности находится с помощью линейной интерполяции

Сi = ((x2 x1) * i / KO + x1, (y2 y1) * i / KO + y1)                        (34)

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

Рис. 4. Неправильный учет прозрачности при реализации инструмента «карандаш»

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

Z1 < Z2                                                                (35)

Это позволяет избежать растеризации фрагмента окружности поверх уже растеризованного фрагмента другой окружности и при этом первый проход преобразования не мешает второму проходу преобразования, т.к. выполняется условие (35). Пример работы корректной реализации инструмента приведен на рис. 5.

Рис. 5. Корректная реализация инструмента:

а)  структура отрисовки пунктиром показываются части, скрытые благодаря  условию (35)

б) результат работы инструмента на некотором уже нарисованном изображении.

Для реализации прямоугольника и эллипса используется их триангуляция и описанное двухпроходное преобразование. Инструмент «ластик» аналогичен инструменту «карандаш» за одним исключением. Т.к. назначение инструмента состоит в уменьшении значения альфа-канала исходного изображения, то стандартное двухпроходное преобразование не используется. Вместо этого для альфа-канала изображения используется преобразование:

G(А, B, x, y)q = max(A(x,y)q * B(x,y)A - (1B(x, y)A) * B(x, y)q), 0.0)        (36),

где q любой из каналов изображения.

Преобразование (36) соответствует поддерживаемому потоковыми процессорами преобразованию смешивания с параметрами source factor = GL_SRC_ALPHA, destination factor = GL_ONE_MINUS_SRC_ALPHA, blend mode = GL_FUNC_REVERSE_SUBTRACT. Чтобы преобразование применялось только к альфа-каналу с помощью цветовой маски (3) запрещается запись в остальные цветовые каналы.

Текстовый инструмент

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

Каждой паре (шрифт, размер шрифта) соответствует своя текстура. Текстура заводится при первой необходимости использовать новый шрифт, а её общий размер зависит от размера шрифта (в целях оптимизации потребления видеопамяти). Как только необходимость использовать шрифт отпадает, шрифтовая текстура удаляется.

Растеризация буквы происходит средствами популярной библиотеки поддержки шрифтов FreeType [12], растеризации подлежает не все символы поддерживаемой кодировки, а только те, которые необходимы для вывода конкретного текста. Т.е. в шрифтовой текстуре постепенно накапливается множество символов, которое было когда-либо использовано с использованием этого шрифта, причем это множество расширяется в реальном времени, по мере необходимости. В таком случае не требуется тратить значительное время на растеризацию символов, которые никогда не будут использованы.

Буква шрифта растеризуется в оттенках серого и хранится в одноканальной текстуре, что с одной стороны позволяет существенно экономить видеопамять, а с другой позволяет примешивать любой цвет к буквам. Т.е. шрифты с одинаковыми именами и стилями, но разными цветами, будут использовать одну и ту же шрифтовую текстуру, что дает экономию видеопамяти. Буквы шрифта выводятся на основе преобразования (32) с примешиванием цвета шрифта и добавлением (в случае необходимости согласно выбранным стилям шрифта) подчеркивания как отдельной линии, координаты которой рассчитаны на основе свойств шрифта. Такая обработка подчеркивания также позволяет существенно экономить видеопамять, т.к. подчеркивание исключается из стилей шрифта, требующих заведения отдельной шрифтовой текстуры для своей поддержки.

Шрифтовые текстуры совместно используются при необходимости. Например, если на нескольких виртуальных досках несколько человек одновременно пишет текст одним и тем же шрифтом, с одними и теми же параметрами, то для этого используется только одна шрифтовая текстура.

Синхронизация рисунка на виртуальной доске

Модель синхронизации vAcademia [13] предусматривает синхронизацию отдельных свойств (простых типов) объектов. Рисунок на виртуальной доске не может быть представлен свойством простых типов, а представление его в виде синхронизируемого пути к файлу на серверу, в котором будет храниться текущее изображение, является неэффективным, т.к. бинарный объем изображения в растеризованном виде слишком большой для синхронизации процесса рисования в реальном времени.

Более оптимальным подходом является хранение описания фигур в том или ином виде и синхронизация этого описания. Чтобы синхронизировать произвольные данные, в систему синхронизации было введено понятие бинарного состояния. Бинарное состояние представляет собой бинарный массив, над которым определены только две операции: добавить данные в конец массива и очистить массив. Кроме того, бинарное состояние обладает целочисленной версией. После любого изменения бинарного состояния, его версия увеличивается на сервере на 1.

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

В бинарное состояние записываются все вызовы методов ToolPalette  (вместе с их параметрами), который являются уведомлением о действиях пользователя: начало рисования, смена инструмента, смена параметра инструмента, движение мыши в момент рисования и др. Это позволяет построить работу ToolPalette и всего связанного с ним кода инструмента в независимости от необходимости иметь поддержку синхронизации. Как в момент рисования на компьютере автора, так и в момент воспроизведения рисунка на другом компьютере, вызываются одни и те же методы с одними и теми же параметрами.

Оптимизация

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

При внимательном анализе подхода можно заметить, что основные фигуры можно триангулировать заранее и не тратить время на триангулирование во время работы инструмента рисования. Более того, OpenGL позволяет сохранить команды потокового процессора для отрисовки триангулированный фигуры в специальный список команд (display list), хранимый в наиболее оптимальном виде в памяти потокового процессора. Таким образом, для отрисовки фигуры необходимо будет инициировать процесс исполнения сохраненных команд, что существенно быстрее, чем передавать данные для исполнения по шине PCI-E.

Другим способом оптимизации является тот факт, что для достижения одного и того же визуального качества отрисовки графических примитивов разного размера требуется триангуляция с разной точностью. Таким образом, было решено заранее предпросчитать фигуры с 5 уровнями детализации и сохранить их в отдельные display list. При необходимости отрисовки фигуры вызывается display list, хранящий команды для отрисовки фигуры в детализации, зависящей от размера фигуры.

Третий примененный подход оптимизирует наиболее ресурсоемкую операцию: восстановление ранее нарисованного рисунка на доске при заходе в виртуальный мир, перемотке 3D-записи и т.д. и т.п. В этом случае операции рисования исполняются в большом количестве, друг за другом. Серьезный объем времени при этом занимает согласно выражению (9) время подготовки к преобразованию TПР, поэтому в целях оптимизации производится сборка фигур, отправляемых на отрисовку с одними и теми же настройками DrawingTarget, для отрисовки в качестве одной большой фигуры сложной формы.

Описанные подходы к оптимизации позволили значительно ускорить выполнение операций рисования и сократить вычислительные затраты.

Анализ и оценка разработки

Инструмент визуального графического комментирования на виртуальной доске был успешно реализован в виртуальном образовательном мире vAcademia (рис. 6). Интерфейс инструмента приведен на рис. 7.


Рис. 6: Инструмент графического комментирования материала

Рис. 7. Интерфейс инструмента whiteboard

Экспериментальные замеры производительности показали преимущество описанного в подхода в 10-50 раз в зависимости от аппаратных конфигураций и условий тестирования в базовом варианте (без оптимизаций). При реализации первого и второго метода оптимизаций средняя скорость работы инструментов рисования возросла на 19%. При реализации третьего способа оптимизации средняя производительность восстановления ранее нарисованного рисунка возросла на 22%. Замеры производились в ходе записи и просмотра группой тестирования около 250 записей виртуального занятия, в каждой из которых активно использовались инструменты рисования.

Замеры, проведенные на различных аппаратных конфигурациях, показали возможность одновременно использования инструмента рисования на 25 досках с общим падением производительности клиента виртуального мира не более 15%. Это говорит о возможности широкого использования инструмента для образовательной деятельности, т.к. позволяет проводить как лекции с использованием одиночной доски, так и массовые практические занятия, на которых каждый учащийся будет решать свою задачу на своей виртуальной доске.

Наибольшее ускорение наблюдается в трехмерных приложениях, т.к. содержимое виртуальной доски хранится в видеопамяти как текстура, чтобы отображать его в трехмерном пространстве. Это делает неэффективной работу инструмента на центральном процессоре из-за необходимости постоянной пересылки данных по шине данных AGP/PCI-E и соответственно дает преимущество описанному подходу.

Заключение

Описанные подходы были успешно апробированы в виртуальном образовательном мире vAcademia на примере реализации инструмента whiteboard для графического комментирования изображений на виртуальной доске. Использование графических потоковых процессоров и нескольких подходов к оптимизации позволили получить многократное ускорение работы инструмента относительно реализации на центральном процессоре. Предложен метод синхронизации рисунка на виртуальной доске в многопользовательской образовательной среде, позволяющий значительно сократить размер сетевых пакетов и сложность алгоритма синхронизации.

Литература

1. EC (2000). Communication from the Commission: E-Learning  Designing «Tejas at Niit» tomorrows education. Brussels: European Commission

2. Hebert, D. G. (2007). «Five Challenges and Solutions in Online Music Teacher Education». Research and Issues in Music Education 5 (1)

3. URL: http://www.wiziq.com (дата посещения: 26.08.2012 г)

4. Сморкалов А.Ю. Реализация образовательных инструментов в виртуальных 3D-средах с использованием потоковых процессоров. // Международный электронный журнал "Образовательные технологии и общество (Educational Technology & Society)" 2011. - V. 14. - № 3. - С. 409-425 . - ISSN 1436-4522. URL:
http://ifets.ieee.org/russian/periodical/journal.html

5. P. H. Carstensen and K. Schmidt: Computer Supported Cooperative Work: New Challenges to Systems Design, CTI Working Paper Series, report # 41, edited by Anders Henten, Center for Tele-Information, Technical University of Denmark, Lyngby, Denmark, 1999.

6. Gerry Stahl, Timothy Koschmann, and Dan Suthers. Computer-supported collaborative learning: An historical perspective. In "Cambridge handbook of the learning sciences". UK, Cambridge, Cambridge University Press, 2006, p. 409-426.

7. Tung, Teck-lee. MediaBoard: A Shared Whiteboard Application for the MBone  // UCB CS Masters Thesis. 1998.

8. Роджерс Д. Алгоритмические основы машинной графики. - М.: Мир, 1989. - С. 512.

9. Чириков С. В. Алгоритмы компьютерной графики (Методы растрирования кривых). Учебное пособие - СПб: СПбГИТМО(ТУ), 2001. - 120 с.

10. У Сяолинь. Эффективная техника сглаживания. Computer Graphics 25 (4): 143-152. ISBN 0-89791-436-8.

11. А.Ю. Сморкалов, М.Н. Морозов. Поддержка дискретных вейвлет-преобразований для компрессии в системе обработки изображений на потоковых графических процессорах. Сборник материалов Всероссийской научно-практической конференции с международным участием "Информационные технологии в профессиональной деятельности и научной работе". - Йошкар-Ола: МарГТУ,.- Йошкар-Ола: МарГТУ, 2010.- С. 91-96.

12. URL: http://www.freetype.org/ (дата посещения: 26.08.2012 г.)

13. Д. А. Быстров. Оптимизация сетевого трафика сообщений синхронизации объектов образовательного виртуального мира vAcademia. // Международный электронный журнал "Образовательные технологии и общество (Educational Technology & Society)" 2011. - V. 14. - № 3. - С. 439-456. - ISSN 1436-4522. URL:
http://ifets.ieee.org/russian/periodical/journal.html