Как оптимизировать определение границ произвольной фигуры ?

[Alex2013]

Во-первых сравнение с фотошопом почти комплимент .. (который я пока не заслужил ) во вторых даже тот "самый фотошоп" тоже реально когда-то был когда-то алфа и бета версии …
(Я кстати, ещё с альфа версий не спрыгнул проект довольно объёмистый выходит
viewtopic.php?f=9&t=10941
Всему толкаемому мной в одиночку проекту "Веб-2" " чуть меньше года, а редактор с перерывами в разработке и того меньше где-то с апреля мая пошлого года... )

Но для тех кто "на танке" (или " рацию на бронепоезде забыл") :

1 Такого функционала я обнаружил не у одного «давно пройденного пакета» .
2 Редактор часть проекта разработки инструментария для создания веб приложений
3 Пакет пишется основном ДЛЯ СЕБЯ (чтобы облегчить разработку конкретно мне )
4 Кроме того имеет место самообучение тонкостям веб-программирования
(Готовый пакет мне и близко не позволит добиться нужного уровня понимания )


Зы
 Тессаляция — штука интересная но «не в тему» . Разбивать на полигоны мне ничего пока не нужно . (Ты бы ещё например тру-форминг вспомнил https://ru.wikipedia.org/wiki/TruForm)
Но если уж записал себя в «не проходимые первопроходцы» что посоветуешь «из не пройденного »? Нет кроме, шуток вдруг что-то действительно интересное предложишь ...
Зы Зы
Часть функционала традиционно закладываемого похожие редакторы у меня просто про пропущена по причине того, что основные задач у проекта совсем ДРУГИЕ чем у «просто редактора» Глянь тему проекта внимательней , там не все так примитивно как может показаться .

[Лекс Айрин]

Может OpenGL?

Может... я их постоянно путаю(((

перестань изобретать то, что уже давно пройдено..

А как еще написать что-то лучше пройденного? Если бы не это, то мы до сих пор бегали бы с камнем в руках.

[vitaly_l]

Тессаляция — штука интересная но «не в тему» . Разбивать на полигоны мне ничего пока ненужно . (Ты бы ещё например тру-форминг вспомнил https://ru.wikipedia.org/wiki/TruForm)

Человек Вам от чистого сердца - верное решение предложил, но раз Вам такие решения не по душе, то попробуйте поискать ScanLine, т.к. такие масштабные переборы в Bitmap делаются с помощью ScanLine. И он(ScanLine) в Лазарусе работает только при подключении внешних библиотек.

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

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



.

[Лекс Айрин]

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

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

[olegy123]

1 Такого функционала я обнаружил не у одного «давно проеденного пакета» .

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

Тессаляция — штука интересная но «не в тему» . Разбивать на полигоны мне ничего пока ненужно .

Очень в тему: разбивается сложная фигура до примитивов. и потом их переберают "for to do" применяя математический аппарат(нахождения точек в плоскости, принадлежность к линии, и т.п. что уже давно изучено доказано еще в 17х веках великими математиками).. все просто.. Иначе иначе если что то напишите то с кучами ветвлений с кучами циклами .. и все это будет работать относительно к конкретно частному случаю..

[Лекс Айрин]

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

Скорее, в механизм отрисовки окон. где-то в районе функций SetWindowRgn и т.п.

[olegy123]

Кстати, разбиение на треугольники - давно уже плохой тон.

Треугольники это "три точки на плоскости".. по ним выясняется пересечения плоскости с лучом.. чистая математика.. нахождения плоскости по четырем точкам - этого мы не проходили..

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

Из не пройденного могу посоветовать переписать написанные либлы под новое железо.. AGG(Anti-Grain Geometry) - он же AggPas(пакет входит в поставку lazarus-а) под CUDA или OpenCL. Там ты не только славы поимеешь, но и бабла могут подсыпать от капиталистов-эксплуататоров.. много бабла, потому что это для них тоже тяжкий труд.

Добавлено спустя 14 минут 43 секунды:
Re: Как оптимизировать определение границ произвольной фигуры ?
Могу сообщить, что нет нормального легкого опенсоурс SVG рендеринга..

Добавлено спустя 9 минут 9 секунд:
Re: Как оптимизировать определение границ произвольной фигуры ?

корее, в механизм отрисовки окон. где-то в районе функций SetWindowRgn и т.п.

Вся векторная графика представлена.. даже векторные шрифты рисуются.. градиенты с тенями...

[vitaly_l]

Треугольники это "три точки на плоскости".. по ним выясняется пересечения плоскости с лучом.. чистая математика.. нахождения плоскости по четырем точкам - этого мы не проходили..

Излагаю, геометрия 2222 летней давности: вначале находим плоскость по трём точкам (раз уж Вы заговорили о 3D) и потом смотрим: "а пересекает ли луч плоскость в границах треугольника?" <== верно? Если мы плоскость уже нашли, то при прямоугольниках, чтобы найти пересечение во втором, треугольнике, мы уже в каждой итерации - экономим на поиске плоскости. <== Ферштейн? Или не бельмеса?

Но это ещё не полная оптимизация, т.к. если после нахождения плоскости, искать принадлежность сразу в прямоугольнике (а не в двух треугольниках), то это уже ДВОЙНАЯ оптимизация на каждую итерацию и ОЧЕНЬ значительная прибавка в скорости 3D движка. Тоже самое касается и 2D.

И чему Вас только учили в этих школах и институтах?

.

[olegy123]

Ферштейн? Или не бельмеса?

Nicht ferstein.. Походу дела вы путаете плоскость с прямоугольником..
Любую фигуру проще выразить через треугольник чем через квадрат. Сам квадрат может показан быть через два треугольника.. а треугольник через квадрат?

[Alex2013]

Человек Вам от чистого сердца - верное решение предложил, но раз Вам такие решения не по душе, то попробуйте поискать ScanLine, т.к. такие масштабные переборы в Bitmap делаются с помощью ScanLine. И он(ScanLine) в Лазарусе работает только при подключении внешних библиотек.

Уже сам догадался ... Кстати работает реально быстрее даже на глаз заметно
(Что в LCL такого в канвас напихали что ПРОСТОЙ ДОСТУП К ПИКСЕЛЮ взывает настолько дикий тормоз ?)

Код: Выделить всё

/ Номер команды по клику
// и определение границ текущей фигуры

Function GetCMDOnClik(X,Y:Longint):Longint;
Type
  AB=Array  [0..1] of byte;
Var
B:TBitmap;
i,YF,Y1,X1:longint;
R:TRect;
PLine:^AB;
BP:Byte;
begin
....


Код определения номера команды по клику
(Есть в этой теме )

Код: Выделить всё

....
  if b.Canvas.Pixels[X,Y]<>$f2 then
  begin
    //Дополнительно определение границ
    // текущей фигуры
    {*********************************}

   R.Left:=b.Width;R.Top:=b.Height;
   r.Right:=0;r.Bottom:=0;
    YF:=0;
      for Y1:=Y to b.Height-1 do begin
       if YF <>0 then YF:=2;
       PLine :=b.ScanLine[Y1];
        for X1:=0 to b.Width-1 do
          if PLine^[X1*3+2]<>$f2 then
           begin
            YF:=1;
            If Y1<R.Top then R.Top:=Y1;
            If X1<R.Left then R.Left:=x1;
            If X1>R.Right then R.Right:=x1;
            If Y1>R.Bottom then R.Bottom:=Y1;
           end;
          If YF>1 then break;
        end;
     YF:=0;
      for Y1:=Y downto 0 do begin
      if YF <>0 then YF:=2;
      PLine :=b.ScanLine[Y1];
        for X1:=b.Width-1 downto 0 do
          if PLine^[X1*3+2]<>$f2 then
            begin
               YF:=1;
                 If Y1<R.Top then R.Top:=Y1;
                 If X1<R.Left then R.Left:=x1;
                 If X1>R.Right then R.Right:=x1;
                 //If Y1>R.Bottom then R.Bottom:=Y1;
                 end;
                If YF>1 then break;
           end;
        CurRec:=R;
        fCurRec:=True;
        Result:=I;
        break;
       end;


Зы
Насчет "от чистого сердца" извините есть сомнения ... (И "куль-нуль- хакер" или бото-диот опять на форуме похоже завелся со "стандартными дуростьями" типа поменять ссылку на тему на ссылку на картинку ярлыка темы ( возможно сейчас это мой ляп (у меня их вообще "традиционно " много ) но когда-то ранее было открыто два окна и в том что не обновил было все ок.. так что работа "дур машины" отслежена на 100% )

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

[vitaly_l]

Nicht ferstein.. Походу дела вы путаете плоскость с прямоугольником..
Любую фигуру проще выразить через треугольник чем через квадрат. Сам квадрат может показан быть через два треугольника.. а треугольник через квадрат?

Треугольники (в такой системе) - априори запрещены. Это просто система позволяющая делать - очень-очень, быстрые 3D движки, т.к. 50-75% снижает нагрузку на процессор. Теперь Ферштейн в умной оптимизации? Или всё ещё ни бельмеса, в итерациях?

Уже сам догадался ... PLine :=b.ScanLine[Y1];

Ну вот уже что-то похожее на истину. Но всё равно непонятно, почему вы не используете array of TRect?
array of TRect <== будет работать быстрее, тем более что, в WEB - все элементы прямоугольные.

Добавлено спустя 11 минут 11 секунд:
Re: Как оптимизировать определение границ произвольной фигуры ?
Да и ещё, у WEB-фигур есть положение по оси Z.
Иначе, как Вы будете работать с фигурами которые пересекают друг друга?


.

[Alex2013]

Уже сам догадался ... PLine :=b.ScanLine[Y1];

Ну вот уже что-то похожее на истину. Но всё равно непонятно, почему вы не используете array of TRect?
array of TRect <== будет работать быстрее, тем более что, в WEB - все элементы прямоугольные.

Добавлено спустя 11 минут 11 секунд:
Re: Как оптимизировать определение границ произвольной фигуры ?
Да и ещё, у WEB-фигур есть положение по оси Z.
Иначе, как Вы будете работать с фигурами которые пересекают друг друга?


.

1 WEB - все элементы прямоугольные. ? Кто вам это сказал ? Отнюдь не все !
Даже у меня в редакторе уже есть например полилинии которые в коде-веб страницы задаются начальной точкой ...
И веб-код он у меня как истина "где-то там"( на выходе генерируется) а в редакторе есть свои внутренний представления данных (в виде списка команд например ) ...

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

3 "почему вы не используете array of TRect?" честно говоря для меня это новая идея ...
С трудом представляю как ее можно реализовать тем более в моем случае потому что
1 У меня нет фиксированного формата данных
2 Элемент может быть какой угодно формы и без заранее определенного прямоугольника (то есть есть набор неких данных по которым скрипт что-то может нарисовать (в том числе и вообще рандомно перерисовывать с каждой прорисовкой, например снег идущий фоном ) )
То есть нужно определить размер блока в который вписано некое " облако неопределенной формы " именно в момент клика по нему мышкой .

[Лекс Айрин]

olegy123, совет, не спорьте с ним.

Это просто система позволяющая делать - очень-очень, быстрые 3D движки, т.к. 50-75% снижает нагрузку на процессор. Теперь Ферштейн в умной оптимизации?

Интересная оптимизация... сначала находим треугольник, строим плоскость, а потом ее выражаем через квадрат? Я тебе очень странную вещь скажу... не надо так делать. 3D-полигональная модель, чего-то сложнее параллелепипеда, всегда строилась из треугольников, Иногда, используется квадратная сетка в перспективных преобразованиях на плоскости, теоретически, можно сделать кубическую сетку и для пространства . Можно, в принципе, объединять треугольники в одну фигуру, но это уже более поздние и не обязательные оптимизации модели.

тем более что, в WEB - все элементы прямоугольные.

Не все. Особенно для веб 2.0.

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

[vitaly_l]

vitaly_l писал(а):
тем более что, в WEB - все элементы прямоугольные.
Не все. Особенно для веб 2.0.

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

Интересная оптимизация... сначала находим треугольник, строим плоскость, а потом ее выражаем через квадрат? Я тебе очень странную вещь скажу... не надо так делать. 3D-полигональная модель, чего-то сложнее параллелепипеда, всегда строилась из треугольников, Иногда, используется квадратная сетка в перспективных преобразованиях на плоскости, теоретически, можно сделать кубическую сетку и для пространства . Можно, в принципе, объединять треугольники в одну фигуру, но это уже более поздние и не обязательные оптимизации модели.

Эту туфту, даже обсуждать не буду - времени жаль.

И веб-код он у меня как истина "где-то там"( на выходе генерируется) а в редакторе есть свои внутренний представления данных (в виде списка команд например ) ...

Это уже более понятно, но раз Вы пишите для WEB, то быть может array of TRect вам пригодится, т.к. с ним проще.
Вам решать - это Ваша программа.

.

[Лекс Айрин]

Вы хоть один WEB-ресурс видели в своей жизни?

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

Пример непрямоугольного элемента DOM

Легко! Обычный абзац текста. Он же не обязан быть прямоугольным, он даже в ворде так себя ведет. А на веб-странице он вообще по поведению напоминает жидкость и заполняет все, если не применять особые ухищрения. При правильном дизайне (samlib.ru, стоит обратить внимание на список авторов на букву "А"), форма далеко не прямоугольная.


И, если уж на то пошло, DOM и WEB существуют в практически параллельных областях.

Эту туфту, даже обсуждать не буду - времени жаль.

Однако, предлагаете