Алгоритмы и принципы создания canvas-виджетов

Доводилось как-то прорисовывать таблицу, кроме высоты/ширины строки/колонки я хранил нарастающий итог по координатам (начало коих было в 0,0, таблица росла в сторону +,+). Это позволяло двоичным поиском выкидывать все, что не попало во вьюпорт. Но там был естественный порядок строк/колонок.

Для произвольного канваса наверное подойдут 4 очереди из элементов (объект, координата), и чтобы каждый объект ссылался на свой элемент в каждой из них. При перемещении/ресайзе объекта просто сдвигаешь элементы так, чтобы очереди всегда оставались отсортированными. Сам вьюпорт тоже пусть будет таким объектом. Тогда вопрос «кто в кадре» сведется к перебору элементов очереди между концами вьюпорта, который тоже в ней. Думаю как-то так.

Кстати есть вот одна история успеха.

Отображить десятки миллионов объектов в кадре? какая тут может быть производительность? только если видно из этих миллионов несколько тысяч. А вообще - примитивы хранить в древовидной структуре, отсечение по пирамиде видимости, упрощеное отображение (или вообще не отображение) удаленных\мелких примитивов

Сам вьюпорт тоже пусть будет таким объектом. Тогда вопрос «кто в кадре» сведется к перебору элементов очереди между концами вьюпорта, который тоже в ней.

Как то больно просто. Я думал используется что-то вроде R-деревьев.

И как быть с сигналами. К примеру набор произвольных линий и окржностей. Пользователь кликает в определнном месте, как определить есть ли в этой точке каой-либо объект? Тыпой перебор тут уже будет не таким простым.

Отображить десятки миллионов объектов в кадре?

Ну к примеру пользователь решил отобразить весь рисунок.

А вообще - примитивы хранить в древовидной структуре

Деревьев много разных, в какой лучше?

Думаю на любом дереве отсев невидимых и определение объекта под мышкой будут бесплатными, по сравнению с «отобразить всё». Я использую простое двоичное дерево - тормозит не оно))

А я стараюсь не заморачиваться, пока во что-то не упираюсь :)

Хит-тест все равно надо делать сначала прямоугольный (чтобы на миллионах не проседать), а потом только смотреть в дырку ты попал или нет. Каждый тип объекта должен наверное сам предоставлять дырявые хит-тесты: для линий простые формулы, для фигур посложнее. Вообще тебе рисовальный движок может ответить на этот вопрос. Взять хотя бы cairo_in_fill().

R-деревья посмотрел, интересно конечно, но сомневаюсь, что пользователь полюбит тебя именно за них. К тому же в интерактивном режиме учитывай затраты на перестроение, оно наверняка недешевое.

Миллиард треугольников в секунду видеокарты рисуют (обещают даже 12 миллиардов для gf560). А алгоритмов отсечения много, зависит от возможного расположения элементов, структуры, размера, количества.

Статических объектов - может быть. В чертилках-рисовалках апетиты нужно поумерить

В тех же ваших максах, майах да блендеров интерактивных элементов можно много рисовать (с миллионом вершин справятся). Их можно выбирать, масштабировать, перемещать.

Поглядел, средний чертеж (можно сказать небольшой) ~1.8млн вершин. Не сказать что летает, но и не тормозит при выводе средствами OpenGl (glBegin\glEnd без современных наворотов). Основной вклад в кол-во вершин - векторные шрифты

glBegin намного хуже, чем VBO. А векторные шрифты можно кэшировать в текстуры.

Тут, правда, появится необходимость в сортировке выводимых объектов для минимизации переключения текстур.

Можно еще кэшировать целые области экрана и перерисовывать только изменившийся прямоугольник. Тогда производительность будет падать только на масштабировании.

glBegin намного хуже, чем VBO

Не спорю, но на каждую линию делать отдельный VBO? все может поменяться в любой момент.

А векторные шрифты можно кэшировать в текстуры.

я имею ввиду автокадовские shx шрифты, их текстурить смысла нет ИМХО. Также не представляю как с текстурой сделать «честное» выделение текста мышью - при попадании подмышку элемента буквы а не текстурного квадратика.

Не спорю, но на каждую линию делать отдельный VBO? все может поменяться в любой момент.

Раз в секунду пересылку миллиона вершин в видеопамять выдержит даже старая видеокарта. А VBO обновлять не так уж и затратно.

Про выделение текста непонятно — нужно вершины букв выделять?

Тут, правда, появится необходимость в сортировке выводимых объектов для минимизации переключения текстур.

Сортировка нужна во всём, даже переключения цвета кушают производительность. Оказалось что выгоднее отказаться от glLineStrip и везде юзать glLines размножая вершины когда надо - эти переключения тоже не хило отъедают времени

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

Еще камешек в сторону VBO - на входе редактора может оказаться очень не подготовленный чертеж. например баба Груня нарисовала пару разрезов размером 100x100 на удалении E+16 от начала координат. штатными средствами OpenGL такую геометрию без искажений не отобразить, получится чтото наподобии http://www.gamedev.ru/files/images/?id=53468

Это проблема точности float. С какой точностью хранятся эти координаты во входных данных?

хранятся double, и глю скармливаются в double, он их сам внутри floatит.

Решилась данная проблема «оптимизацией» опенглной modelview матрицы и вычитанием из выводимых координат некой точки. Если это пихнуть в ВБО, придется использовать шейдеры я так понимаю. В автокаде подобные чертежи летают на дохлейших видеокартах без всяких шейдеров, вбо и вообще без опенгл))

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

Можно сделать model + view. Модель — сырые исходные данные объектов, вид — набор VBO и аргументов для шейдеров. При изменении модели автоматически пересчитывать и обновлять VBO.

Кстати, не обязательно перерисовывать чертеж с частотой 60 кадров в секунду.

Кстати, не обязательно перерисовывать чертеж с частотой 60 кадров в секунду.

это понятно, я экран запоминаю в текстуры и перерисовываю только когда надо, в остальных случаях обновляю из текстур. Но основные операции при черчении zoom и pan требуют полной перерисовки видимых объектов. (хотя pan при паралельной перспективе в принципе можно оптимизировать двигая текстуры, но это геморойно)

Отрисовку в принципе можно, но всеравно теже данные для VBO нужны и на CPU. Например для выбора мышкой. Штатный GL_SELECT на ATI мягко говоря работает оочень медленно. И гдето я читал что вообще он стал deprecated, а чё, в играх ненужен и фиг сним))

Так а зачем для выбора пользоваться данными, подготовленными для отрисовки? Тут как раз подойдет какое-нибудь простое отсечение, структуру данных для которого быстро перестраивать в случае изменений.

Про «честный» выбор я писал выше - если мы имеем штрих-пунктирную линию, то и выбирать ее нужно за штрихи и пунктиры, а не тыками в «пустое» место. Такчто все координаты при текущем положении с GL_SELECT всеравно придется держать и на CPU и на GPU

Все координаты и так придется держать в основной памяти, opengl при смене контекста состояние, включая буферы, теряет.

А использовать GL для выбора вообще нельзя, только графика.

Чето темка заглохла. Жаль, очень интересная. Прчитал умных ссылок - разбиение которое я использую называется kd-tree. Подсобрал статистики на дохлых компах (древний ноут celeron1.7+ati) - более менее можно работать с ~300000 одновременно видимых вершин (при выводе примитивов посредством glBegin\glEnd), время рендера в районе 100мсек. Упомянутый выше чертеж с 1.8М до 300К вершин при «показать всё» упрощается практически без видимых искажений.