Contacts
صفحه اصلی پورتال | صفحه اصلی تالار | ثبت نام | اعضاء | گروه ها | جستجو | پرسش و پاسخ | فروشگاه الکترونیکی | خرید پستی بازی های کامپیوتری





صفحه اول انجمنها -> اصول اولیه در طراحی بازیهای کامپیوتری -> Rasterize a triangle
 

ارسال يك موضوع جديد   پاسخ به يك موضوع ديدن موضوع قبلي :: ديدن موضوع بعدي

Rasterize a triangle
نويسنده
پيغام
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
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ديدن وب سايت كاربر نام كاربري در پيغامگير Yahoo
 

نويسنده
پيغام
sajad83
کاربر جدید
کاربر جدید


تاريخ عضويت: 2 شنبه 2 آذر 1388
تعداد ارسالها: 6


5 شنبه 5 آذر 1388 - 03:11
پاسخ بصورت نقل قول
اين را هم ببينيد:

http://seganx.com/Engine/2009/11/triangle-cash.html

_________________
Conflict Of Dimensions
ارسال  بازگشت به بالا
ديدن مشخصات كاربر ارسال پيغام خصوصي ديدن وب سايت كاربر نام كاربري در پيغامگير Yahoo
 

نمايش نامه هاي ارسال شده قبلي:   
ارسال يك موضوع جديد   پاسخ به يك موضوع    صفحه 1 از 1 تمام ساعات و تاريخها بر حسب 3.5+ ساعت گرينويچ مي باشد


 
پرش به:  


شما نمي توانيد در اين انجمن نامه ارسال كنيد.
شما نمي توانيد به موضوعات اين انجمن پاسخ دهيد
شما نمي توانيد نامه هاي ارسالي خود را در اين انجمن ويرايش كنيد
شما نمي توانيد نامه هاي ارسالي خود را در اين انجمن حذف كنيد
شما نمي توانيد در نظر سنجي هاي اين انجمن شركت كنيد


unity3d

بازگردانی به فارسی : علی کسایی @ توسعه مجازی کادوس 2004-2011
Powered by phpBB © 2001, 2011 phpBB Group
| Home | عضويت | ليست اعضا | گروه هاي كاربران | جستجو | راهنماي اين انجمن | Log In |