Быстрая фрагментация треугольника. Как?

← →
@!!ex © (2008-07-25 14:55) [0]

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

← →
Сергей М. © (2008-07-25 15:05) [1]

А зачем это вообще надо ?
Какова предметная область задачи ?

← →
Ega23 © (2008-07-25 15:08) [2]

Решить систему линейных уравнений?

← →
@!!ex © (2008-07-25 15:09) [3]

Нужно нарисовать график на Canvasе.
График задан картой высот, хранится в bmpшке.
Сейчас рисуется с помощью Canvas.Polygon(), но это плохо подходит, поскольку полигон заливается весь одним цветом, а нужно сделать плавный цветовой переход в пределах одного примитика.

← →
Правильный$Вася (2008-07-25 15:34) [4]

PtInRegion
?
может, проще побить треугольник на несколько частей?

← →
Сергей М. © (2008-07-25 15:39) [5]

> @!!ex © (25.07.08 15:09) [3]

Так может тебе регионами воспользоваться ?

см. справку "Region Functions"

Вот нашел по фрагментации:
http://compgraphics.info/2D/triangle_rasterization.php

Пробую реализовать.

← →
Sapersky (2008-07-25 16:20) [7]

Нашёл у себя код. Писался он 8 лет назад, поэтому эффективностью не блещет, но вроде работает.

Type
TRealPoint = record
x,y : Real;
end;
TPoints3 = array[1..3] of TRealPoint;
TColors3 = array[1..3] of Byte;

function getlength(x1,y1, x2,y2 : Real):Real;
begin
Result:=sqrt(((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1)));
end;

procedure DrawTriangle(const points : TPoints3; const colors : TColors3);
Var iMin, iMax, iMid : Byte;
i,n : Integer;
arry : array[1..3] of Real;
d1,d2,d3 : Boolean;
dx1,dx2,dx3,x1,x2 : Extended;
p,l1,l2,l3,l,c1,c2 : Real;

procedure HLine(x1,x2:Real; y:Integer; i1,i2 : Real);
Var x,xn,xe,dx : Integer;
c,r,g,b : Byte;
l1,l2,l3,di,i : Real;
begin
xn:=Round(x1); xe:=Round(x2);
If xn=xe then Exit;
If xn>xe then begin dx:=xn; xn:=xe; xe:=dx; di:=i1; i1:=i2; i2:=di; end;
di:=(i2-i1)/(xe-xn);
i:=i1;
For x:=xn to xe do begin
c:=Round(i);
buffer.Canvas.Pixels[x,y]:=RGB(c,c,c);
i:=i+di;
end;
end;

begin
iMin:=1; iMax:=1; iMid:=0;
For i:=1 to 3 do
If points[i].y<points[iMin].y then iMin:=i;
For i:=1 to 3 do
If points[i].y>points[iMax].y then iMax:=i;
For i:=1 to 3 do
If (i<>iMin) and (i<>iMax) then
begin iMid:=i; Break; end;

l1:=(GetLength(points[iMin].x,points[iMin].y,points[iMax].x,points[iMax].y));

l2:=GetLength(points[iMin].x,points[iMin].y,points[iMid].x,points[iMid].y);
l3:=GetLength(points[iMax].x,points[iMax].y,points[iMid].x,points[iMid].y);
arry[1]:=points[iMax].y-points[iMin].y;
arry[2]:=points[iMid].y-points[iMin].y;
arry[3]:=points[iMax].y-points[iMid].y;
d1:=True; d2:=True; d3:=False;
If arry[1]=0 then begin d3:=True; end;
If arry[2]=0 then d1:=False;
If arry[3]=0 then begin d2:=False; end;
dx1:=0; dx2:=0; dx3:=0;
If not d3 then dx1:=(points[iMax].x-points[iMin].x)/arry[1];
If d1 then dx2:=(points[iMid].x-points[iMin].x)/arry[2];
If d2 then dx3:=(points[iMax].x-points[iMid].x)/arry[3];
x1:=points[iMin].x; x2:=x1;

If d1 then
For n:=Round(points[iMin].y) to Round(points[iMid].y)-1 do begin
l:=GetLength(x1,n,points[imin].x,points[iMin].y)/l2;
p:=GetLength(x2,n,points[imin].x,points[iMin].y)/l1;
c1:=(colors[iMin]*(1-l))+colors[iMid]*l;
c2:=(colors[iMin]*(1-p))+colors[iMax]*p;
HLine(x1,x2,n,c1,c2);
x1:=x1+dx2; x2:=x2+dx1;
end;
x1:=points[iMid].x;
If d2 then
For n:=Round(points[iMid].y) to Round(points[iMax].y)-1 do begin
l:=GetLength(x1,n,points[iMid].x,points[iMid].y)/l3;
p:=GetLength(x2,n,points[imin].x,points[iMin].y)/l1;
c1:=(colors[iMid]*(1-l))+colors[iMax]*l;
c2:=(colors[iMin]*(1-p))+colors[iMax]*p;
HLine(x1,x2,n,c1,c2);
x1:=x1+dx3; x2:=x2+dx1;
end;
end;

> Сейчас рисуется с помощью Canvas.Polygon(), но это плохо
> подходит, поскольку полигон заливается весь одним цветом,
> а нужно сделать плавный цветовой переход в пределах одного
> примитика.

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

Быстрая фрагментация треугольника. Как? Найти похожие ветки