OSDev

для всех
Текущее время: 23 июн 2018, 03:36

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Движок граффической библиотеки
СообщениеДобавлено: 05 май 2015, 10:31 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1088
По многочисленным просьбам решил завести тему. Разрабатываю архитектуру графической библиотеке, а вернее её движка.
Проблем не просто много, а очень много. Но сейчас я хочу обсудить следующий момент. Больно сложно всё получается.
Почему я решил заняться архитектурой? Ответ прост и дан в книге совершенный код.

Как известно наиболее дорогие ошибки, которые не выявлены в самом начале. Поэтому подход написал, не понравилось, выбросил в корзину, написал заново. Не понравилось, с ново выкинул и переписал – меня не устроил. Поэтому я решил заняться проработкой архитектурой, чтобы заложить основы, от которых можно будет отталкиваться в дальнейшем.
Вначале я себе представлял это просто. И думал, что за день или за несколько дней управлюсь. Тем более в этом деле я уже не новичок. Но уже скоро будет месяц. А пока только эскизы. В основном всё держу в голове. Мне так проще. Постепенно планирую всё задокументировать. Но чем дальше я планирую архитектуры, тем сложнее она становиться. И простой человек со стороны не сможет разобраться.
У меня уже используются такие понятия как пластилиновый конвейер, строитель конвейера, программная машина состояний, автомат, интератор, перечислитель. Понятие хранилища коллекции. Абстрактный вектор.
И это ещё я не прорабатывал пул для управления памятью и параллельность. При всём при этом я стараюсь минимизировать основной код, чтобы не писать лишнего.
А есть ещё предметные понятия: клякса, антилестница, линеаризация и тп.
И как человеку со стороны в этом всем разобраться? Если я не напишу как нужно делать? Дело в том, что у каждого этого понятия есть своя семантика, которая устанавливает порядок действия и работы с ним.

Прикладной программист прежде чем вызывать метод коллекции должен выделить память. А для этого нужен пул потоков, а ещё надо настроить программную машину состояний на работу с этой памятью. И только после этого я должен вызывать методы коллекции. При этом вызывать методы экземпляров в коллекции запрещается. А так как коллекция это всего лишь хранилище. И не предоставляет ни каких методов для обработки данных: вставки, удаления, поиск.
Опытный разработчик, зная потерны проектирования с легкостью может определить кто главенствует в архитектуре. Кто отвечает за создание, уничтожение и управления объектами. А кто просто является хранилищем или инструментом. Конечно я планирую задокументировать главенственность(иерархию) объектов.

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

Никак не получается разорвать треугольник.
1. Архитектура должна строиться так что-бы уменьшить число взаимных связей между объектами. В идеале каждый объект должен быть автономным.
2. Оптимизация должна заменять цепочки связей на один общий метод и группировать данные по однородному формату.
3. Основа движка, должна быть компактной простой, т.е с минимумом связей.

Основной виновник всего это как я вижу оптимизация. Но в графике без неё никуда.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 05 май 2015, 21:54 
Аватара пользователя

Зарегистрирован: 16 апр 2010, 10:10
Сообщения: 319
Откуда: Псковская обл.
За основу движок из гэймдева?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 05 май 2015, 22:48 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1088
Это не графический движок. А движок графической библиотеки.
Другими словами если графический движок использует OpenGL или DirectX. То я проектирую аналог Mesa3D которая является реализацией интерфейса OpenGL . И вопрос как спроектировать архитектуру реализации OpenGL.

Брал ли я что-то за основу со стороны? Согласно теории решения изобретательских задач для получения нового есть следующие пути:
1. взять существующие и попробовать скомбинировать
2. Взять существующие и изменить что-то в нём.
3. Использовать инвертирование.
4. Обобщение.

Безусловно я брал за основу наработки других людей. Как говорил Исаак Ньютон что-бы видеть дальше надо стоять на плечах других людей. Наибольшее вдохновение мне дала библиотека AGG. Возможно я всё ещё под впечатлением от прочтения книги банды четырёх про ООП. Но в качестве пути поиска изобретения я выбрал первый, комбинирования существующих знаний.

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

Прикладной интерфейс пока не проектировал, но думаю будет 2 вида.
1. Первый вид это функциональный близкий к OpenGL ES 2.0 для управления состоянием движка.
2. Второй вид это объектно ориентированный близкий к Delphi canvas, возможно какие-то элементы из Ogre.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 05 май 2015, 23:05 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
pavia писал(а):
2. Второй вид это объектно ориентированный близкий к Delphi canvas, возможно какие-то элементы из Ogre.

Тогда уж с Delphi FireMonkey, с архитектурой которой я советую ознакомиться. У самого пока не было времени, но по первым впечатлениям многое в ней сделано продуманней по сравнению с VCL.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 11 май 2015, 12:34 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1088
Работаем с промежутками(анг. Span).
Что такое промежуток? Это узкоспециализированный термин в графике. Он означает горизонтальные участки образовавшиеся после нарезки многоугольника на горизонтальные полоски.
Вовремя нарезки на одной линии могут образоваться несколько таких промежутков. Промежуток располагается между гранями и состоит из скосов и сплошных лент.

Введем два типа промежутков. Сжатые и несжатые. Каждый несжатые промежуток описывает скосы и содержит массив весовых коэффициентов. Весовой коэффициент соответствует проценту заполнения пикселя многоугольником. Где идет грань он же скос то там коэффициенты уменьшается или увеличивается. А где идет сплошная лента то там коэффициенты постоянные. Для таких и исполняется сжатие.

Небольшое отступление от темы:
Зачем нужно два типа? Дело в том что основной операция при рисовании является закраска пикселей. И тут важна оптимизация.
Можно выделить 3 функции закраски.
1) Простое присвоение
2) Присвоение при смешивание с постоянным коэффициентом
3) Присвоение со смешивание с разными коэффициентами.
Самая быстрая 1 потом 2 и самая медленная 3 функция. Скорость определяет число операций.
1) Запись.
2) Смешивание запись
3) Чтение смешивание запись.
Более детально я расскажу когда буду рассказывать про закраску и смешивание.

Вернемся к промежуткам.
Вначале я хотел сделать по простому 2 функции.
Код:
procedure AddСoSpan(Y, x0,x1:Integer);
begin
// Span Clipping
if X0<0 then X0:=0;
if X1<0 then X1:=0;
if X0>=Width then X0:=Width;
if X1>=Width then X1:=Width;
//
Span.Kind:=skCompressed;
Span.Y:=Y;
Span.X:=X0;
Span.N_1:=(X1-X0)-1;
Spans[SpansCount]:=Span;
Inc(SpansCount);
if SpansCount>=Length(Spans) then SetLength(Spans,SpansCount*2);
end;

procedure AddUSpan(Y, x0,x1:Integer; AAWeight:PByte);
begin
// Span Clipping
if X0<0 then X0:=0;
if X1<0 then X1:=0;
if X0>=Width then X0:=Width;
if X1>=Width then X1:=Width;
//
Span.Kind:=skUnCompressed;
Span.Y:=Y;
Span.X:=X0;
Span.N_1:=(X1-X0)-1;
Span.BufWeight:=AAWeight;
Spans[SpansCount]:=Span;
Inc(SpansCount);
if SpansCount>=Length(Spans) then SetLength(Spans,SpansCount*2);
end;


Но потом все таки решил отказаться от такого подхода. И разбить на 3 функции, как советуют Макконал в своей книге совершенный код. 1) Вернуться к предыдущему варианту я всегда успею. 2) Кадрирование требует перемещения указателя по весовому буферу. Что усложняет код. Да и по сути надо будет создать новый промежуток и заменить старый, а для этого нужен код для создания промежутка.
3) группировка однородных операций всегда работает быстрее. Поэтому отсечение лучше сделать отдельным проходом.

Код:
procedure AddSpan(const Span:PSpan);
begin
Spans[SpansCount]:=Span;
Inc(SpansCount);
if SpansCount>=Length(Spans) then SetLength(Spans,SpansCount*2);
end;

Отделение добавления промежутка в список промежутков позволяет скрыть информацию об реализации. В будущем это позволит изменять реализацию. Тем более управления памятью и структура коллекции ещё не проработана. А в таком случае изменения затронут минимум кода.

Код:
function CoSpan(Y, X, Width:Integer; Weight:Byte):TSpan;
begin
Result.Kind:=skCompressed;
Result.Y:=Y;
Result.X:=X;
Result.Width:=Width;
Result.UniformWeight:=Weight;
Result.WeightsCount:=0;
Result.Weights:=Nil;
end;

function USpan(Y, X, Width:Integer; PWeights:PByte):TSpan;
begin
Result.Kind:=skUnCompressed;
Result.Y:=Y;
Result.X:=X;
Result.Width:=Width;
Result.WeightsCount:=Width;
Result.Weights:=pointer(PWeights);
end;


По поводу выбора названий.
СoSpan сокращение от CompressedSpan.
USpan сокращение от UnCompressedSpan
N_1 длина минус один. Небольшой трюк для того что-бы втолковать оптимизатору что от него нужно.
Weight - почему ширина, а не x0,x1?
Дело в том что x0<x1, а может и наоборот x1<x0.
А длина бывает положительной и отрицательной. А вот ширина в большинстве случаев число положительное. При реализации закраски не хотелось бы иметь лишнего ветвления. А внутри функции сортировку тоже не хочется делать так как при разбиении на промежутки идет сортировка активных граней по Х. И повторная сортировка будет лишней. По этим причинам используется Weight. А вот тип знаковый, отрицательная ширина не рисуется.

UniformWeight - одинаковый, однородный вес. Используется в сжатом промежутке.
Weights - весовые коэффициенты.
PWeights - приставка P означает передачу указателя.

А вот с типом весового коэффициента пока не определился. Дело в том что для закраски нужна оптимизация надо использовать числа с фиксированной запятой. Но с другой стороны они могут быть и с плавающей запятой.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 24 май 2015, 22:59 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1088
Чем выше горка тем больше снежный ком. Продолжаю придумывать алгоритм. Приходится перебирать разные варианты. И не все из них подходят.
Для того чтобы добиться устранения ступенчатости надо вычислить процент заполнения пикселя многоугольником. Другими словами нам надо вычислить площадь многоугольника заключенная в границы пикселя. Так как пиксель имеет форму квадрата или прямоугольника, то очевидно что он также является многоугольником. А следовательно пересечение основного многоугольника и пискеля является многоугольником.
Из сходя из этого можно заключить что нужно 2 функции.
1) Вычисления площади многоугольника.
2) Нахождение пересечения многоугольников.

Операция пересечения относится к роду математической-морфологии. Также ещё распространено и второе название этой операции булево 'И' и класс операции булевая операция над многоугольниками.

Существует много методов для выполнения булевых операций над многоугольниками. Большой сборник для 2D можно найти в:
http://www.inf.tsu.ru/library/Publications/2004/46.pdf
Вопиющая ошибка в название. 'оверлеп' перепутан 'овелеям'. Да и не по русски. Так что приходится перепроверять весь текст.

Вначале мой выбор пал на метод Вейлера–Азертона. Но после прочтения метода Холверда. В голове сложился пазал.

Можно совместить первую функцию со второй. Это упростит расчёт пересечения многоугольников. Метод назовём протяжка линии. (Анг. Sweep line). Я не притендую на первенство так как видел такую же фразу в других движках.

Допустим что у нас уже есть многоугольник без самопересечения который мы нарезали на горизонтальные полоски шириной 1 пиксель. В результате у нас есть многоугольник Polygon_Tape.
Будем вести вертикальную линию по горизонтали. И как только линия встретит какую либо точку прямоугольника Polygon_Tape то будем генерировать сигнал для вычисления площади.
Делать мы будем это следующим образом. При каждом таком срабатывание будем делать разрез вдоль линии. Тем самым мы будем отрезать кусочки слева от Polygon_Tape . У нас будут образовываться примитивные многоугольники. Ба,да это же трапеции! У которых вертикальные линии параллельны. Для них есть очень простая формула площади S=1/2*(a+b).

Продолжение следует.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB