sajad83 کاربر جدید
تاريخ عضويت: 2 شنبه 2 آذر 1388 تعداد ارسالها: 6
2 شنبه 2 آذر 1388 - 15:55 |
|
|
الگوریتم هایی که برای رسم مثلث پیدا کردم خیلی جالب نبودن. حتی چند الگوریتمی که مورد استقبال هم قرار گرفته بودند دارای نکات منفی زیادی بودند. از جمله الگوریتم هایی که با استفاده از حدود مثلث، یک مستطیل به دور مثلث در نظر می گیرند و پیکسل ها رو با "half-space" چک می کنند تا مشخص شود پیکسل مورد نظر داخل مثلث قرار دارد یا نه. بعد برای بهینه تر شدنش هم از بلاک های چهارتایی یا هشتایی برای پیمایش استفاده می کند.
من می خواستم هرطور شده الگوریتمی طراحی کنم که دقیقا پیکسلهای داخل مثلث را شمارش کند که حاصل کار در ادامه آمده است.
در این الگوریتم سه نقطه مثلث را به ترتیب Y از بالا به پایین مرتب می کنیم. با استفاده از قواعد شرطی می توان این کار را خیلی سریع و راحت انجام داد. قصد بر این است که از بالاترین تقطه مثلث ( می تواند پایینترین باشد ) پیمایش را آغاز کرده و با تغییر Y محدوده X را مشخص کنیم. برای مشخص شدن محدوده X معادله های خطوط بین نقاط را محاسبه می کنیم. در این اینجا ابتدا معادله خط بین دو نقطه 1 و 3 ( بالاترین و پایینترین ) را محاسبه می کنیم ( اگر dy=y3-y1=0 آنگاه مثلث حتی خط هم نیست و رسم نمی شود. ) در ادامه مثلث را در دو مرحله رسم می کنیم. ابتدا از نقطه 1 به 2 و سپس از نقطه 2 به 3 که در هر مرحله معادله خط بین نقاط برای پیدا کردن محدوده X به راحتی قابل محاسبه است. با چک کردن dy در هر مرحله نیز می توان از محاسبات اضافی جلوگیری کرد.
مزییت های این الگوریتم نسبت به الگوریتم های رایج این است که پیکسل های بیرون از مثلث پیمایش نمی شوند و دیگر آنکه متغییرهای کمی مورد استفاده قرار گرفته اند و دیگر آنکه از توابع ریاضی سنگین ( مثل توابع مثلثاتی، power، sqrt و ... ) در آن استفاده نشده است و ...
همچنان سعی می کنم الگوریتم را ساده تر کنم. امیدوارم دیگران نیز کمک کنند.
در حال حاضر برای نمایش هر پیکسل از یک کلاس ساده بوم ( canvas ) استفاده کردم که بعدا باید surface مخصوصی را هم برای دسترسی سریعتر طراحی کنم.
پ.ن
امیدوارم کسی پیدا بشه و این کد رو با اسمبلی بازنویسی کنه.
كد: |
procedure iTriagle(Canvas: TCanvas; vx1, vy1, vx2, vy2, vx3, vy3, col: Integer); inline;
var
x1, y1, x2, y2, x3, y3: Integer;
X, Y, dx, dy, xfrom, xto, tmp: Integer;
g13, g12, g23: Single;
begin
// quick rearrange vertices from top to bottom //
if (vy1>vy2) and (vy1>vy3) then begin
x1:= vx1;
y1:= vy1;
if (vy2>vy3) then begin
x2:= vx2; y2:= vy2;
x3:= vx3; y3:= vy3;
end else begin
x2:= vx3; y2:= vy3;
x3:= vx2; y3:= vy2;
end;
end else if (vy2>vy1) and (vy2>vy3) then begin
x1:= vx2;
y1:= vy2;
if (vy1>vy3) then begin
x2:= vx1; y2:= vy1;
x3:= vx3; y3:= vy3;
end else begin
x2:= vx3; y2:= vy3;
x3:= vx1; y3:= vy1;
end;
end else begin
x1:= vx3;
y1:= vy3;
if (vy1>vy2) then begin
x2:= vx1; y2:= vy1;
x3:= vx2; y3:= vy2;
end else begin
x2:= vx2; y2:= vy2;
x3:= vx1; y3:= vy1;
end;
end;
// Step 1 : calculate line equation from v1 to v3 //
dx:= x3-x1;
dy:= y3-y1;
if dy<>0 then begin
g13:= dx / dy;
// Step 2 : calculate line equation form v1 to v2 //
dx:= x2-x1;
dy:= y2-y1;
if dy<>0 then begin
g12:= dx / dy;
for Y := y1 downto y2 do begin
xfrom:= iround( g12 * (Y - y1) + x1 );
xto:= iround( g13 * (Y - y1) + x1 );
if xfrom>xto then begin
tmp:= xfrom;
xfrom:= xto;
xto:= tmp;
end;
for X := xfrom to xto do
Canvas.Pixels[X, Y]:= col;
end;
end;
// Step 3 : calculate line equation form v2 to v3 //
dx:= x3-x2;
dy:= y3-y2;
if dy<>0 then begin
g23:= dx / dy;
for Y := y2-1 downto y3 do begin
xfrom:= iround( g23 * (Y - y2) + x2 );
xto:= iround( g13 * (Y - y1) + x1 );
if xfrom>xto then begin
tmp:= xfrom;
xfrom:= xto;
xto:= tmp;
end;
for X := xfrom to xto do
Canvas.Pixels[X, Y]:= col;
end;
end;
end;
end;
|
|
_________________ Conflict Of Dimensions |
|