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

[zub]

Alex2013
>>Десять смотря отчего ...
Мерить скорость отрисовки 10 примитивов не имеет смысла, тут либо твой замер это одна погрешность либо твоя процедура отрисовки настолько медленна что...
Я бы на твоем месте сделал стрессовый "файл" тысяч на 10 примитивов, и на нем бы смотрел что да как.

Хотя давно ясно (мне и это мое ИМХО) что как и отрисовка "скриптами", так и "растровое" "выделение" примитивов - тормозилки неприминимые в реальных задачах. Оптимизировать тут нечего, надо переделывать.

>>Вся проблема в том, что замечена очень сильная зависимость от размеров рабочего поля ... Непропорциональная !
ну наконецто замечена)) тебе про нее сразу говорили

[Alex2013]

Alex2013
>>Десять смотря отчего ...
Мерить скорость отрисовки 10 примитивов не имеет смысла, тут либо твой замер это одна погрешность либо твоя процедура отрисовки настолько медленна что...
Я бы на твоем месте сделал стрессовый "файл" тысяч на 10 примитивов, и на нем бы смотрел что да как.

Zub про принцип "разумной достаточности" ты явно не слышал ...
Планируемый безусловный разумный максимум 1000 элементов в макете (Можно даже явно прописать ограничение "бо нефиг" ибо уже сейчас никто не мешает разделить страницу на несколько блоков генерация идет через замену "Певдо тега " ... кстати идея! можно вообще добывать элемент "псевдо фрейм"(суть не в названии) по типу панели в Хайасм (там чтобы редактировать панель в редакторе форм нужно в нее "зайти" и это отсекает все элементы "выше") картинку для показа можно получать отдельно один раз при загрузке или изменении ) ...

Если нужно больше по любому нужно как-то упрощать изображение искать второстепенные детали выводить только видимое то есть делать полноценный 2.5д движок.(что в рамках задачи в явно избыточно )
Попробуй кстати загрузить реально сложный эскиз в профессиональную "колку дров" (Корел Драв )... и прослезись .... ибо тормоз будет ирреальный и невероятный !
Там даже в оптимизированных примерах встречается ТАКОЕ что просто "ужос летящий на крылья ночи " поминать приходится!

Alex2013

Хотя давно ясно (мне и это мое ИМХО) что как и отрисовка "скриптами", так и "растровое" "выделение" примитивов - тормозилки неприминимые в реальных задачах. Оптимизировать тут нечего, надо переделывать.

"Отрисовка скриптами" уже по сути не применяется (только при загрузке а при изменении добавлении отдельного элемента через скрипт перерисовывается только один элемент )

>>Вся проблема в том, что замечена очень сильная зависимость от размеров рабочего поля ... Непропорциональная !
ну наконецто замечена)) тебе про нее сразу говорили

Это только при определение границ при перерисовке все "тип топ" . (Ну почти "тип топ" ... бо "совершенству нет предела" )

Зы
Объяснил ведь ! Сейчас все упирается в две "фишки" очистку фона после создания маски и собственно определение границ
(Если ускорить очистку можно будет оставить ОГ как есть и вызвать один раз после нахождения .
Если ускорить ОГ можно примять ее всегда и адресно чистить только рект фигуры при каждой итерации поиска )...

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

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

...
Type
  TLine=Array  [0..sizeOf(Longint)] of byte;
Const
C_B=$F2;
C_C=$F2F2F2;
...
Var
B:TBitmap;
LineSize,Y1,X1:longint;
PLine,ELine:^TLine;
BP:Byte;
PB:^Byte;
...

LineSize:=B.RawImage.Description.BytesPerLine;
...
// Создаю эталон для сравнеия ("Чистый вакуум")
Getmem(ELine,LineSize);FillChar(ELine^,LineSize,C_B);
...
      PB:=b.RawImage.Data;
      Y1:=IndexByte(PB^,b.RawImage.DataSize,$FF);
      If Y1<>-1 then begin
      Y1:=(Y1 div LineSize);

    Try
       b.BeginUpdate;
      for Y1:=Y1 to b.Height-1 do
      begin
       PLine :=b.ScanLine[Y1];
       If CompareByte(PLine^,ELine^, LineSize)<>0 then
        FillByte(PLine^, LineSize,C_B)
      else
         if IndexByte(PLine^,(b.Height-Y1)* LineSize,$FF)=-1 then break;
      end;
      finally
       b.EndUpdate;
      end
    end;
...


По идее код должен быстро вытирать белый контур на темном фоне Но "опять двойка" ... уже на стадии Y1:=(Y1 div LineSize); лезет какая -то чушь ...

[zub]

>>Zub про принцип "разумной достаточности" ты явно не слышал ...
)) просто я занимаюсь подобными вещами, многое пробовал на своей шкуре и представляю чего нужно ожидать в смысле скорости от разных методов.
Бывают подходы к задаче "в лоб", бывают "по науке" - как оно надо.
У тебя даже не "в лоб" у тебя "в лоб, но через зад". Без обид, имхо.

>>Можно даже явно прописать ограничение "бо нефиг"
Ограничения изза какойто детской упертости автора... это ерунда какаято...
Сколько времени ты потратил на "оптимизацию", давно бы уже имел написаную в правлильном ключе программу которую действительно имеет смысл оптимизировать.

Добавлено спустя 8 минут 12 секунд:
Re: Как оптимизировать определение границ произвольной фигуры ?
>>Попробуй кстати загрузить реально сложный эскиз в профессиональную "колку дров" (Корел Драв )... и прослезись .... ибо тормоз будет ирреальный и невероятный !
Сказки. всё в порядке у корела с производительностью. тебе такого ине снилось))

[Alex2013]

>>Zub про принцип "разумной достаточности" ты явно не слышал ...
)) просто я занимаюсь подобными вещами, многое пробовал на своей шкуре и представляю чего нужно ожидать в смысле скорости от разных методов.
Бывают подходы к задаче "в лоб", бывают "по науке" - как оно надо.
У тебя даже не "в лоб" у тебя "в лоб, но через зад". Без обид, имхо.

Хуже.. у меня "по лбу" ...
Но если кажется что еще вот-то вот и "дрогнут шведы" ... то понятное дело появляется "упрямство достойное лучшего применения" ...
Наверное для надежного вычисления границ по хорошему нужно добавить возможность подключить (опционально !) к каждому элементу дополнительный скрипт по их определению .
(Это чтобы купировать "жуткие случаи" ) и действовать по уже поверенной двухуровневой схеме (тем более что основа уже есть )
..ну и как резервный оставить вариант растрового поиска "на самый крайний случай" но опять же при "первой прорисовке" а не при каждом клике ...
Зы
Вообщем видимо пока попробую делать "гибрид" "верного" и "неверного" способа. ( если скорость устроит пока оставлю так но буду иметь ввиду и чисто "геометрический способ" "имени Ника Римера" ...)

В общем "война закончена , всем спасибо" !

[zub]

По науке - прослойка между канвасом и скриптом.

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

MyCanvas.DrawLine(p1,p2:TPoint)
begin
  EntityBoundingRect:=ConcatRectAndPoint(EntityBoundingRect,p1);
  EntityBoundingRect:=ConcatRectAndPoint(EntityBoundingRect,p2);
  Canvas.DrawLine(p1,p2:point);
end;

Абсолютно "копипастная" прослойка которая перед передачей управления реальному канвасу будет считать "оболочку" на основе переданых данных

[Alex2013]

"Железнодорожник из мятых карманов
Поношенной формы достанет на свет
Помятую трешку, железную ложку,
И на отъехавший поезд билет..." (С)Нау...

Вчера уже начал делать более "другой способ" определения границ и номера элемента под курсором по клику...

Но решил все же разобраться и довести до приемлемого по надежности уровня текущий вариант ( Все равно процедура растрового поиска пока будет частью "хорошо забытого нового" способа )
Проверили несколько вариантов насмотрелся на кучу непонятных глюков (Как уже писал особенно доставляет если код явно содержащий ошибку
(на которой уже большими буквами в комментарии написано "ОШИБКА ТУТ!") неким "мистическим образом " как-то умудряется работать ... )
Но вообще обычно это означает , что в поведении используемых объектов есть что-то на само деле оказывается "не тем чем казалось мне наивному" ( или в более редких случаях например "ОС внезапно оказывается не тем чем её считали разработчики библиотеки... " )

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

...То есть все мои "CurCanvas.Pen,mode := pmWhite; " для создания маски идут лесом полем и дальними хатками бобров ...
Беда была в том эта "тайная битмпа" на которой рисуется "типа маска" в нормальном случае никогда нигде не показывается ...
Угу ... "в темной темной комнате ... темные темные негры ... грузят темный темный уголь... "

Повозившись сделал чрез "двойной фон " (то есть вывожу фигуру на один фон, потом на другой дабы "магические" числа не мешали )
Что разуется не блещет в плане "ускорения и перестройки" ... Но зато работает без "ШМАГИ ЦИФЕР" ...

Так чем может быть дело ? Как заставить прорисовку метафайлов использовать свойства кисти канваса ?
(даже без привязки к текущему проекту мало ли где может понадобится сделать вывод МФ например с инверсией растра )

[zub]

Чем подкреплена уверенность что в emf запоминается только геометрия, без "атрибутивной" информации?
Попробуй делать 2 emf - один в цвете для рисования, другой без цвета для выделения

[Pavia]

Это непросто. Мето файл хранит информацию о кисте и карандвше для каждого объекта.
Проще всего попросить того кто его создал пересоздать с нужным TPen и TBrush.
Есть и трудный путь отрисовать с получением контура GetPath. И после отрисовать контур нужными кистями и карандашами.
http://www.delphimaster.ru/cgi-bin/foru ... 688889&n=7
По моему я это уже вам советовал.

[olegy123]

Кстати мысль: а что если "раскрыть циклы" и после изменения фигуры потихоньку считать границы в фоновом режиме

А осилишь фоновый режим?
там мыслить надо очень правильно.. а не "пробовать натянуть gui на свои фантазии".

[Alex2013]

"Жить стало лучше жить стало веселей!"
Сподобился я сделать список Ректов ...
Результате скорость определения границ по клику... отсутствует ...
За ненадобностью !
Вот все что осталось от некогда развесистого кода .

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


Function GetCMDOnClik(X,Y:Longint):Longint;
Var
i,Y1,X1:longint;
R:TRect;
begin
Result:=-1;
// Стандартная проверка списка команд
If drawlist= Nil  then exit;
If drawlist.Count=0  then exit;

If Frectlist= Nil  then exit;
If FRectlist.Count=0  then exit;

// Проверка попадания в рект
// по списку...
For I:=DrawList.Count-1 downto 0 DO
    begin
    R:=Trect(FRectlist[i]^);

    If  not  IsRectEmpty(R) and
      PtInRect(  R, Point(X,Y))
     then
    begin
         // Получаю результат ...
           CurRec:=R;
           fCurRec:=True;
           Result:=I;
           break;
    end
  end
end;


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

Но внезапно появилась новая проблема !Имя ей ПРОЗРАЧНОСТЬ ...
Точнее полное "отсутствие наличия" этой самой прозрачности для всех фигур "в горошек" и "сырные дыры".
Так что геометрия, примененная "в лоб" решает - увы! - далеко не все ...
Зы
Идеи разумеется есть ... но все какие-то сложно реализуемые
( вроде разбивки на более мелкие полигоны )

[Pavia]

Добавь проверку прозрачности.
If DrawList[i].GetPixel(X,Y).Alpha<10 then continue;

[Alex2013]

Добавь проверку прозрачности.
If DrawList[i].GetPixel(X,Y).Alpha<10 then continue;

Спасибо ! Идея неплоха ... (Хотя все чуток сложнее ... DrawList имеет тип TStringLst .. так что сам понимаешь никаких GetPixel(X,Y) там нет Но есть другой список MetaDrawList типа Tlist который содержит данные типа TMetafile ... то есть рисую как-то так CurCanvas.Draw(0,0,TMetafile ( MetaDrawList[i] ) ); вот там может что-то получится ... хотя есть ли доступ к по сути "виртуальным пикселям" у TMetafile это еще вопрос )

[vitaly_l]

есть ли доступ к по сути "виртуальным пикселям" у TMetafile это еще вопрос

А чем TMetafile, круче Tbitmap? В чём подвох, замены Tbitmap на TMetafile?

[Alex2013]

Alex2013 писал(а):
есть ли доступ к по сути "виртуальным пикселям" у TMetafile это еще вопрос

А чем TMetafile, круче Tbitmap? В чём подвох, замены Tbitmap на TMetafile?

vitaly_l я разумеется изрядный лопух (чему только что заимел очередное подтверждение и до сих пор мысленно прибываю в состоянии "рука лицо" ... о сути очередного программного " эпик фейла" расскажу ниже... ) но все-же не везде... Так что TMetafile юзаю не из любви к эпической героине Гари Гарисона по имени Мета или просто красивому названию ...

1 Tbitmap требует памяти "квнтум статис" - TMetafile нет .
2 Tbitmap требует сложной процедуры быстрой очистки и наложения "квнтум статис" - TMetafile нет .
3 Размеры фигур изначально не определены (и могут меняться при каждой перерисовке ) то есть по умолчанию нужен размер во все рабочие поле
Улавливаешь , что за "массивчик" получится ? Ага ... (Да после определения границ можно мелкие фигуры повырезать но что делать если нужны фигуры достаточно большого размера ? Это ведь никак не обойти даже при плотностью "геометрическом определении границ " )
и т. д..

Ну ладно это просто бурчание ...

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

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

Function GetCMDOnClik(X,Y:Longint):Longint;
Var
CTime,CTime1:TDateTime;
AL,SPS,CC,Lbs,i,Y1,X1:longint;
R:TRect;
TS:string;
M:TMetafile;
MC:TMetafileCanvas;
SaveCanvas:TCanvas;

B:TBitmap;
begin
Result:=-1;
// Стандартная проверка списка команд
If drawlist= Nil  then exit;
If drawlist.Count=0  then exit;

If Frectlist= Nil  then exit;
If FRectlist.Count=0  then exit;

// Если BufBMP не создан ...
If BufBMP=nil then begin
    BufBMP:=TBitmap.Create;
    BufBMP.SetSize(rf1.PaintBox1.Width,rf1.PaintBox1.Height);
   end;

For I:=DrawList.Count-1 downto 0 DO
    begin
    R:=Trect(FRectlist[i]^);
   If  not  IsRectEmpty(R) and
     PtInRect(  R, Point(X,Y))
     then
    begin
// Проверка прозрачности ...
    SaveCanvas:=CurCanvas;
    CurCanvas:=BufBMP.Canvas;
   //Проход 1
    BufBMP.Canvas.Pixels[x,y]:=$f2;
    rf1.FastDrawFig(I,1);
    If BufBMP.Canvas.Pixels[x,y]=$f2 then
    begin
     //Проход 2
     BufBMP.Canvas.Pixels[x,y]:=$f1;
     rf1.FastDrawFig(I,1);
     CurCanvas:=SaveCanvas;// Востанавливаю Canvas...
       If BufBMP.Canvas.Pixels[x,y]=$f1 then   continue;
     end
      else
        CurCanvas:=SaveCanvas;// Востанавливаю Canvas...
     //==================================

       rf1.StatusBar1.SimpleText:=
       format('Границы %d %d - %d %d',[r.Left,r.Top,r.Right,r.Bottom]);


         // Получаю результат ...
           CurRec:=R;
           fCurRec:=True;
           Result:=I;
           break;
    end
  end
end;



Пришлось сделать упрощенный вариант "растрового определения" для выяснения прозрачности но поскольку оно нужно только при попадании в уже определенные границы скорость попятное дело не проседает ....

А теперь об обещанном "эпик фейле" ...
Вместо "шибко вумных" процедур очистки на которые я потратил кучу времени можно было сразу написать что-то вроде "сакраментального" BufBMP.Canvas.Pixels[x,y]:=$f2; перед рисованием тестируемой фигуры ...
ОДНУ СТРОЧКУ ! Нет слов ...
Пусть бы это сработало только для определения номера фигуры , а не границ но скорость точно была бы на уровне перерисовки ...
Ну ладно поезд уехал цирк закрыли ....

[vitaly_l]

до сих пор мысленно прибываю в состоянии "рука лицо"

Векторная графика, конкретно для решения этой задачи ненужна. ТРектами - сократили количество фигур, а дальше по старинке, раз уж, метафайл не позволяет узнать принадлежность точки рисунку. Геометричекси это вычислить нереально сложно, разве что - разбить на треугольники, как подсказывали выше. И ещё, нужен порядок по оси Z, вначале тестируются ближние и только если false, то следующие. Описываю, подробно на случай если ВДРУГ заглянут крутые математико-геометры, только они могут это вычислить цифрами.