Архитектура 'рисовальных' программ

если поле не слишком большое,
то можно использовать canvas - widget`ы 
практически из любой серъёзной библиотеки (Qt/Gtk/Tk),
они рисуют всё-что надо на виртуальном поле и отоображают только
ту часть которая влезает на видимую область.

для быстрого ваяния подобных вещей я лично использую Tk
и tkzinc (чуть более навернутые canvas)

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

Тыкнул юзер мышой в поле... и как определить попал он в линию или не попал. Попал и вередину или на конец.

вот как раз таких проблем не встречал ;-)
поэтому и говорил - используйте НОРМАЛЬНУЮ библиотеку с canvas
- там по определению все что вы добавляете - равноправный объект управления, для которого можно определять биндинги, посылать ему сообщения и прочее и прочее..
Tcl/Tk sample (highlight line under mouse cursor):
set myline [ $can add line -width 1 $x1 $y1 $x2 $y2 ]
bind $myline <Enter> [ list $myline configure -width 3 ]
bind $myline <Leave> [ list $myline configure -width 1 ]
bind $myline <Double-Button-1> [ list $can see $myline ]
# etc etc..

У qt и gtk возможностей больше, по пример просто невлезет в сообщение ;-)

пример написал 'с руки' поэтому содержит пару ошибок ;-)
вместо 'bind $myline' читать '$myline bind' ;-))

Пожалуй самый быстрый способ таков:

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

хехе. Объяснил путано, могу разжевать при необходимости.

> ... и как определить попал он в линию или не попал

На самом деле весь вопрос в количестве линий. Если их пара-тройка тысяч, то тупой перебор покатит. Когда под миллион-два придется подумать. Спроси гугля на предмет computational geometry.

Это все понятно. До такого я и сам додумался. Мне это почему-то показалось велосипедом :)

Бля. Сам прочитал свои бредни - ужаснулся. 

короче вот примерная организация данных в такой программе

Рисуемые объекты 

1 - Линия (0,0)-(10,0)
2-  Линия (10,0)-(10,10)
3-  Линия (10,10)-(0,10)
4-  Линия (0,10) - (0,0)

Буфер отрисовки будет примерно следующим

11111111111
1.........1
1.........1
1.........1
1.........1
1.........1
1.........1
1.........1
1.........1
11111111111

где '1'- например, белый цвет, а '.' - прозрачный (чОрный к примеру).

Буфер при помощи которого пользователь может определить какой объект 
нарисован в данной точке экрана

41111111112
4.........2
4.........2
4.........2
4.........2
4.........2
4.........2
4.........2
4.........2
43333333333

1,2,3,4 - номера соотвествующих линий
 
Когда юзер "выбирает линию" он тыкает в пиксел с кооринатами (например 
(0,5)), ты соовтественно смотришь во вотором буфере и видишь что этой 
точке соотвествует элемент со значением '4' => юзер ткнул в 4-ю линию

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

Имхо, это дельный велосипед

Ну-ну. 1280x1024 = 1310720 (1.3 Mb)

Теперь юзер схватил линию и двигает. Как это все обновлять быстро?

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

Потом, зачем быстро ? Когда отпустит - тогда и обнови.

GameMagister : предложенный Вами вариант, имеет право на существование,
но жрёт ресурсы как лошадь и сложно реализуем для overlapped (перекрывающихся) объектов. ;-)

ПРимер : изображение 800*600 pixels, на нём чертёжик в 300 объектов,
итого для второго буфера (map: pixel coords -> object pointer)
надо памяти : 800*600*sizeof(void *) = 320000 * 4 = 128K 
для чертежей a-la ACAD размеры в пикселах мягко говоря побольше ;(

Механизм определения - в какой-же объект ткнул пользователь -
реализуются (и реализованны) несколько подругому :-)

Вы уж определитесь что хотите делать - прикладную программу для рисования/черчения или свой вариант canvas.

Как по-другому?

> GameMagister : предложенный Вами вариант, имеет право на существование, но жрёт ресурсы как лошадь

Ничего он не жрет. На скорости почти не сказывается (добавляется лишь одна операция присваивания при отрисовке), а по памяти требования не такие серьезные для современнымх машин.

> и сложно реализуем для overlapped (перекрывающихся) объектов. ;-)

Реализуется элементарно - через список.

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

> ПРимер : изображение 800*600 pixels, на нём чертёжик в 300 объектов, итого для второго буфера (map: pixel coords -> object pointer) надо памяти : 800*600*sizeof(void *) = 320000 * 4 = 128K

> для чертежей a-la ACAD размеры в пикселах мягко говоря побольше ;(

Так речь идет об экраном буфере (т.е. только та часть, которая отрисовывается ), а не о всем чертеже. Тем более что чертеж в ACAD-е хранится в векторном виде...

> Механизм определения - в какой-же объект ткнул пользователь - реализуются (и реализованны) несколько подругому :-)

Расскажите плз.

ну какой-же Вы упрямый ;-)
рисуем на экране, разрешение экрана 1280*1024,
хрен с ним рисуем не на всём экране 1024*768,
итого : 1024*768*4 = 3Mb памяти отъели...
теперь блин её заполняем , hint - в графических приложениях объект 
'подсвечивается' (то есть выбирается) когда указатель мыши находится 
ВБЛИЗИ этого объекта.. короче - для того чтобы попасть мышом в вертикальную линию толщиной 1 пиксел не обязательно надо иметь прецизионную мышь и снайперскую точность. 
Будем рисовать все объекты во втором буфере с большей толщиной ?

А если область рисования у нас больше отображаемой в виджете ?
Вы будете делать большой второй буфер или ловкие алгоритмы
регенерации и скроллирования первого ??

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

Интересует реализация нормальных подходов ? 
посмотрите исходник к примеру Qt..

К сожалению, в QT-4 убрали canvas, точнее сказали что он depricated.... Столкнулся с такой же проблемой (хочу щас написать CASE средство и нужен аналог erwin в нём) - смотрел на diacanvas - советую посмотреть, в нём даже perl-bindings есть, но мне не очень пока понравилось... Возможно стоит самому написать... GTK вообще как я понял не очень подходит для векторной графики... Потому что у него есть только DrawingArea, а это pixmap и как говорится, "рисуйте сами что хотите", вот QT3canvas был интересен (он как раз под векторы хорошо заточен был) но как я уже писал выше - убрали.

Так что я сам тоже в поиске - буду читать тред, смотреть что предложили...

> итого : 1024*768*4 = 3Mb памяти отъели...

Ну и ... вы другие графические приложения не создают таких буферов для отрисовки ? В том же Qt все так и сделано.

> теперь блин её заполняем , hint - в графических приложениях объект 'подсвечивается' (то есть выбирается) когда указатель мыши находится ВБЛИЗИ этого объекта.. короче - для того чтобы попасть мышом в вертикальную линию толщиной 1 пиксел не обязательно надо иметь прецизионную мышь и снайперскую точность. Будем рисовать все объекты во втором буфере с большей толщиной ?

Зачем ? достаточно сканировать некоторую окрестность точки в которой находится мышь, например "крест на крест".

> А если область рисования у нас больше отображаемой в виджете ? Вы будете делать большой второй буфер или ловкие алгоритмы регенерации и скроллирования первого ??

Не мутите воду, буфер с указателями на объекты должен быть равен по размеру (геометрическому) буферу отрисовки. Все. Никаких ловких алгоритмов не потребуется.

> Интересует реализация нормальных подходов ? посмотрите исходник к примеру Qt..

Самое смешное, что там сделано именно так как я и говорю.

> Не мутите воду, буфер с указателями на объекты должен быть равен по размеру (геометрическому) буферу отрисовки. Все. Никаких ловких алгоритмов не потребуется.

Вот это меня кстати тоже интересует - а как прикажете в него рисовать-то? Так вроде, (ну например) я спихиваю отрисовку на q3canvas или ещё что, а потом должен сам вручную рисовать всё и вся алгоритмом г-на брезинхема на копии?

Алгоритм отрисовки разумеется таков:

1. Рисуем в буферах 2. Выводим буфер отрисовки на экран

Если вы делаете серьезную программу вроде библиотеки qt или acad-а, а не коленочное поделие из готовых "компонентиков", то реализовать несколько алгоритмов отрисовки основных примитивов в буферы вам особого труда не составит, в простивном случае - ищите готовые решения которые по сути повторяют этот подход.

> К сожалению, в QT-4 убрали canvas, точнее сказали что он depricated....

запустите штатную demo от Qt4. посмотрите, как весело и чудестно мышой растягивается сглаженный график закорючки. посмотрите, как это сделано в коде. aka в Qt3/4 это все уже есть в лучшем виде.

// wbr

Есть маза! Надо просто использовать OpenGL и рисовать в оффлайн разными цветами без подсветки... Там как раз и глубина есть и всё такое =)))

Ведь должны-же быть на эту тему какие-то более или менее научные труды?

Их-бы почитать. Или узнать как это сделано не в QT/GTK/etc, а В ACAD/QCAD/...CAD.

Не должно-же это быть столь секрктной информацией.

> Так вроде, (ну например) я спихиваю отрисовку на q3canvas или ещё что, а потом должен сам вручную рисовать всё и вся алгоритмом г-на брезинхема на копии?

Если вы сами сделаете алгоритмы отрисовки то никаких копий не
потребуется. Вот вам пример функции которая ставит "точку" в такой
системе

void plot(unsigned int x,
          unsigned int y,
          unsigned int color,
          object   *   ob,
          unsigned int * color_buf,
          object   **  object_buf
)
{
     (color_buf+y*BUF_SIZE_X+x)=color; // Ставим точку в буфере отрисовки
     (object_buf+y*BUF_SIZE_X+x)=ob; // Ставим точку в буфере объектов
}

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

> Если вы сами сделаете алгоритмы отрисовки то никаких копий не потребуется.

Угу, а теперь представь себе объем кода чтобы хотя бы залитые полигоны и круги рисовать... И не забудь - не должно быть ни одного умножения или деления...

О! Я совсем забыл ещё и про то что текст рендерить надо бы... Типа всякие подписи...

Глубина в OpenGL реализована такими же средствами. Про z-buffer слышал ?

Не только слышал, но и использовал - просто ты с лёгкой руки предлагаешь написать 2-4 мегабайта исходных кодов которые уже были кем-то где-то написаны (в частности повторить большой кусок openGL) :)

Ну с научными я загнул, но описания типа "Как это сделали мы" (от рабочего реального пректа) не помешали-бы.

Чорт, все алгоритмы описаны. Твое дело - забить их в компьютер. Разговор детский. Повторюсь: если речь идет о коленочном поделии, то проще использовать готовые решения. В противном случае - лучшге сделать самому, т.к. любое готовое решение рано или поздно перестанет удовлетворять твоим потребностям и все равно все придется переделывать нах.

> Чорт, все алгоритмы описаны. Твое дело - забить их в компьютер.

Такое ощущение, что тебе 15 лет или 45 лет и ты топ-менеджер отдела ни разу не видавший программного кода... Или прикалываешься...

Про 2-4 мегабайта ты загнул. 2-4 мегабайта осмысленного кода средней сложности год пишет коллектив из 5-6 человек. максимум - 100 кбайт при реализации средней грамотности.

Так обсуждается как раз как сделать самому.

А предлагается в качестве решения слямзить код c QT . :)

Блин. Я тебе говорю. Все зависит от твоих потребностей. Почему по твоему все более или менее серьезные элементы больших программных продуктов написаны с нуля без использования сторонних специализированных библиотек ? Просто потому что любое готовое решение имеет ограниченную область применимости. Откуда ты знаешь как поведет себя кутешный канвас в случае когда ему датут работать с миллионом объектов ?

постановка задачи по вычислительной геометрии :
 на плоскости заданны геометрические объекты,
которые могут полностью или частично перекрывать друг-друга
каждому объекту сопоставлен приориритет (z),
надо по двум координатам x,y выбрать объект с макимальным приоритетом находящийся не далее r от неё.
 Геометрический объект состоит из одной или более элементарных фигур 
для каждой из которых заданна функция enclosed(x,y,r) возвращающая 1 если точка достаточно близка к фигуре. Каждому объекту сопоставленна обрамлющая элементарная фигура внутри которой он полностью расположен.
Объекты могут группироваться с сохранением тех-же свойств

Вот собственно и весь canvas ;-)
за решением - google - computation geometry, 




 

Ты знаешь, я уже даже готов заплатить тебе деньги чтоб на это посмотреть: Условия: написать обсуждаемую библиотеку, чтоб она могла обслуживать 1) линии 2) Окружности (эллипсы) 3) Залитые круги 4) Залитые полигоны 5) Полые полигоны 6) Текст разного размера. 7) Чтоб это было с чёткими слоями 8) Ну и конечно чтоб можно было всё таскать. 9) Чтоб при таскании соединённые объекты таскались вместе, а соединённые линиями - например два таблицы с foreign key - одна тащилась, и изменялась линия. 10) Самое главное: чтоб не тормозило с кол-вом сущностей ~1000-10000 и размером экрана 1280x1024.

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

Хочешь убедится - посмотри код QCanvas

Ой-йёй - забыл -забыл!!!
Ещё bezier пожалуйста!
На самом деле, заплачу и много.
А если это будет всё в 100kb то ОЧЕНЬ МНОГО!

>в дюну, например, играл ?

В дюну я не только играл, но и писал аналоги в 15 лет (в 1995 году)
так что не надо мне на уши лапшу-то вешать, а?
Я вполне представляю объемы кода которые надо лопатить и вполне представляю уровень необходимой оптимизации для отрисовки таких вещей в 1280x1024.

Ага.

1. Перебор по всем объектам (если учитывать overlaped ) 2. Перебор по всем элементарным составным элементам объекта 3. Вычисление номали от точки до элементарной составляющей. 3. Вычисление расстояния вдоль нормали.

Типа быстро и не ресурсоемко.

Если ты действительно хочешь заплатить мне за реализацию, то прошу в асю 191581134.

> При отрисовке экрана необходимо заводить два буфера. Первый - для > отрисовки. Второй - содержит указатели на рисуемые объекты > производилась отрисовка.

Мозгов не напасёшься. Для больших-то изображений. А для мелких можно и координаты ручками перебрать, с разными вариациями (например, отсортировать для быстрого поиска).

> По скорости затраты у такого метода почти равны затратам на отрисовку объектов добавляется лишь еще одна операция присваивания.

Может проще, если известна организация так сказать области рисования или имеется возможность получения информации о цвете точки с заданными координатами, штатными средствами отрисовывать все эти линии разными цветами. Ну а сами линии пронумеровать. Для 65К или 16М хватит. Надеюсь понятно выразил мысль. Просто так быстрей будет. Movet bytx...

Так там только для видимой части, отрисоваемой.

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

Если нет особых требований к цвету объектов можно и так. Просто подбирать очень близкие по оттенкам цвета и фсе.

Но это очень грязный хак =)

Может по существу возразишь ? Я никого не презываю переделывать Qt или ACAD. Писать тонны кода если это не нужно. Вопрос был о методе решения поставленной задачи - я объяснил свое видение.

> Если нет особых требований к цвету объектов можно и так. Просто подбирать очень близкие по оттенкам цвета и фсе. > Но это очень грязный хак =)

Любой хак -- это решение. В данном случае никакое не грязное. Я предлагаю заводить ДВЕ КАРТИНКИ. Одну -- для показа юзеру. Другую -- для сопостовления координат объекту. Вот во второй номера объектов кодируются цветами. Отрисосываются ШТАТНЫМИ методами. Единственное но: нужно уметь получать информацию о цвете точки с заданными координатами. Ну и никаких градиентов, размыленности и прочих альфа-каналов.

А вообще бы я пользовал Tk, если устраивает, и не парился. Зачем писать давно написанное?

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