Перевод кода Cи → Asm

@Sophos · Регистрация: 04.01.2010

Студворк — интернет-сервис помощи студентам

День добрый!
Возникла такая ситуация - необходимо проверить около миллиона точек на вхождение каждой в многоугольник. Если написать на языке высокого уровня, то, я так полагаю, время выполнения увеличится часа на два. А вот если сделать асм-вставку...

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

Вот исходный код:

C
1
2
3
4
5
6
7
8
9
10
11
 int pnpoly(int npol, float * xp, float * yp, float x, float y)
 {
   int c = 0;
   for (int i = 0, j = npol - 1; i < npol; j = i++) 
   {
     if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
       (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
         c = !c;
   }
   return c;
 }

И базис для вставки:

Delphi
1
2
3
4
Function InPoly(Veobject, Layer, X, Y : Integer) : Boolean; 
Asm  
... 
End;

, где массив находится в

Delphi
1
Warehouse.Veobject[Veobject].Polies[Layer].Poly {Poly  : Array of TPoint;}

Очень надеюсь на вашу помощь.

@vital792 · 12.03.2011, 13:41

Сообщение от Sophos

Если написать на языке высокого уровня, то, я так полагаю, время выполнения увеличится часа на два. А вот если сделать асм-вставку...

современные компиляторы генерят вполне оптимальный код, и улучшить его работу асм-вставкой удается редко. Посмотри дизассемблерный листинг твоей функции, выданный хотя бы visual studio. Ускорить его работу практически невозможно, если только на чуть-чуть, но не на 2 часа)

murderer · 12.03.2011, 13:46

Я так понял, что тебе на дельфи переписать надо. Вот посмотри это. Если хочешь можно ещё ускорить раза в 2-3. Если переписать на SSE2 и использовать 2-байтовые слова для хранения координат, то можно обрабатывать по 4 грани многоугольника за одну итерацию.

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs;
 
type
  TForm1 = class(TForm)
    procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X,Y: Integer);
  end;
 
var
  Form1:  TForm1;
  poly:   array[0..4] of TPoint=((X:20;Y:20),(X:50;Y:30),(X:40;Y:50),(X:10;Y:30),(X:20;Y:20));
 
implementation
 
{$R *.dfm}
 
Function InPoly(var Veobject; count,x,y : Integer): Boolean;assembler;stdcall;
asm
mov  edx,[Veobject]
movq mm0,qword[x]
mov  ecx,[count]
@a:movq     mm1,[edx+ecx*8-8]
   movq     mm2,[edx+ecx*8]
   psubd    mm2,mm1
   psubd    mm1,mm0
   packssdw mm2,mm2
   packssdw mm1,mm1
   pmaddwd  mm1,mm2
   movd     eax,mm1
   sar      eax,31
loopne @a
emms
end;
 
procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,Y: Integer);
begin
  Form1.Canvas.Pen.Width:=3;
  Form1.Canvas.Pen.Color:=dword(InPoly(poly,4,X,Y)) and 255;
  Form1.Canvas.Polyline(poly);
end;
 
end.

@Sophos · 12.03.2011, 16:23 **[ТС]**

Огромное спасибо! Наконец-таки с мертвой точки съеду.

Одно маленькое уточнение - если я беру адрес массива не сразу по переменной:

Delphi
1
var Veobject

А через глобальную структуру:

Delphi
1
Warehouse.Veobject[Veobject].Polies[Layer].Poly

Мне нужно в квадратные скобки брать все или только Poly?

murderer · 12.03.2011, 16:33

Передавай эту строку в качестве параметра

Delphi
1
InPoly(Warehouse.Veobject[Veobject].Polies[Layer].Poly,<количество граней>,x,y,);

Обрати внимание на то, что многоугольник должен быть замкнутым (poly[0]=poly[n])

@Sophos · 12.03.2011, 19:07 **[ТС]**

Обрати внимание на то, что многоугольник должен быть замкнутым (poly[0]=poly[n])

Оу... Придется добавлять точку в конец...

murderer · 13.03.2011, 14:57

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

@Kastaneda · 13.03.2011, 16:29

Сообщение от vital792

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

Зависит от компилятора, на отдельных участках можно значительно ускорить)

@Sophos · 13.03.2011, 19:42 **[ТС]**

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

Эм... Да, для произвольных.

murderer · 13.03.2011, 22:04

Вот для произвольных. Что-то я сомневаюсь, что ассемблерный вариант быстрее. Сравни производительность.

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs;
 
type
  TForm1 = class(TForm)
    procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X,Y: Integer);
  end;
 
var
  Form1:  TForm1;
  poly:   array[0..9] of TPoint=((X:20;Y:20),(X:300;Y:100),(X:330;Y:150),(X:200;Y:130),(X:170;Y:160),(X:130;Y:160),(X:120;Y:110),(X:50;Y:50),(X:70;Y:40),(X:20;Y:20));
 
implementation
 
{$R *.dfm}
 
{Function InPoly(var Veobject; count,x,y : Integer): Boolean;stdcall;
var
  i,j: dword;
  _x,_y: integer;
begin
  j:=0;
  for i:=0 to count-1 do
  begin
    _x:=poly[i+1].y-poly[i].y;
    _y:=poly[i].x-poly[i+1].x;
    j:=j+((((_x*(x-poly[i].x)+_y*(y-poly[i].y)) xor _x)and((y-poly[i].y)xor(y-poly[i+1].y))) shr 31);
  end;
  result:=boolean(j and 1);
end; }
 
Function InPoly(var Veobject; count,x,y : Integer): Boolean;stdcall;assembler;
asm
  push esi
  mov      esi,[Veobject]
  movq     mm0,qword[x]
  packssdw mm0,mm0
  mov      ecx,[count]
  xor      eax,eax
  @a:movq     mm1,[esi+ecx*8-8]
     packssdw mm1,[esi+ecx*8]
     pshufw   mm2,mm1,00110011b
     pshufw   mm3,mm1,10011001b
     psubw    mm3,mm2
     psubw    mm1,mm0
     pshufw   mm2,mm1,1110b
     pxor     mm2,mm1
     pmaddwd  mm1,mm3
     pslld    mm3,16
     pxor     mm3,mm1
     pand     mm3,mm2
     movd     edx,mm3
     shr      edx,31
     add      eax,edx
  loop @a
  emms
  and eax,1
  pop esi
end;
 
procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,Y: Integer);
begin
  Form1.Canvas.Pen.Width:=3;
  Form1.Canvas.Pen.Color:=dword(InPoly(poly,9,X,Y))*255;
  Form1.Canvas.Polyline(poly);
end;
 
end.

@Sophos · 14.03.2011, 08:56 **[ТС]**

Вот для произвольных.

Спасибо огромное!! Кстати, а вы их сами пишете или берете где? А то может будет быстрее мне не через посредника обращаться?

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

murderer · 15.03.2011, 13:57

Это моя реализация стандартного алгоритма
1) Подсчитываем количество пересечений луча, исходящего из данной точки в направлении горизонтальной оси, со сторонами многоугольника.
2) Если это количество нечётное, то точка лежит внутри многоугольника

Немного оптимизировал

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Function InPoly(var Veobject; count,x,y : Integer): Boolean;stdcall;assembler;
asm
  mov      eax,[Veobject]
  movq     mm0,qword[x]
  packssdw mm0,mm0
  mov      ecx,[count]
  pxor     mm4,mm4
  @a:movq     mm1,[eax+ecx*8-8]
     packssdw mm1,[eax+ecx*8]
     dec      ecx
     pshufw   mm2,mm1,00110011b
     pshufw   mm3,mm1,10011001b
     psubw    mm3,mm2
     psubw    mm1,mm0
     pshufw   mm2,mm1,1110b
     pxor     mm2,mm1
     pmaddwd  mm1,mm3
     pslld    mm3,16
     pxor     mm3,mm1
     pand     mm3,mm2
     pxor     mm4,mm3
  jnz @a
  movd     eax,mm4
  emms
  shr      eax,31
end;

@Sophos · 21.03.2011, 20:23 **[ТС]**

Один вопрос - в коде в посте #3 вы писали:

Code
1
Form1.Canvas.Pen.Color:=dword(InPoly(poly,4,X,Y)) and 255;

Фигурирует цифра 4. Но длина массива - 5. Почему 4?

murderer · 22.03.2011, 14:52

Количество вершин (длина массива) - 5, количество граней - 4.

Новые блоги и статьи Все статьи Все блоги /
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

murderer 4190 / 1838 / 221 Регистрация: 06.10.2010 Сообщений: 4,125
	13.03.2011, 14:57
	Тебе наверное надо для произвольного многоугольника? Тот код подходит только для выпуклых. 0

murderer 4190 / 1838 / 221 Регистрация: 06.10.2010 Сообщений: 4,125
	22.03.2011, 14:52
	Количество вершин (длина массива) - 5, количество граней - 4. 0