فصل سوم مبناهای خروجی گرافیک )(Output Primitives مبناهای خروجی گرافیکی یا مبناها توابعی که در بسته های گرافیکی برای توصیف مؤلفه های تصویری گوناگون بکار برده می شوند، :رنگ قرار داده شده فعلی را در فریم بافر در مکان صحیح ) (x,yذخیره می کند :پااارام ر colorمقاادار صااحیتی متناااکر بااا کااد بی ااای RGBمرکااذ ذخیااره شااده برای پیکسل واقع در مکان ) (x,yدریافت می کند 5 4 3 2 1 0 4 3 2 1 0 بارای صااحنه هااای یااه بعاادی ،م تصااا صاافره بصااور مقااادنر یااه بعاادی کااه در ن بعااد یااو معاارمکان ای جسم نسبت به نک موقعیت دند ایت ،ذخیره می شوند. -برای صحنه ای دو بعدی ،همه مقادنر عمق برابر صفر هستند خط پا اااره خ ا ا در صا ااحنه با ااا موافا ااع م تصا ااا دو رکی ن عریا ااف ما اای شا ااود و ی ا ا نزدنک رنن موافع پیکسلی را در طول مسیر خطی بین دو رکی عیین کند ی سا ااتم گرافیکا اای خ به مجموعه ای از نقاط صحیح گسسته که تقریبی برای مسیر خ فعلی اند رقمی میش ود. عم اال گ اارد ک ااردن م تص ااا ب ااه اع ااداد ص ااحیح باعا ا م اای ش ااود ش ااکل پ ااه ای خط ااای ریا ا ر ب ااوی ه در ی ستم ای با تفکیک پذنری پانین مرسوی شود معادله خط y = mx + b موافع پیکسلی در طول مسیری خ ،از روی معادله دکار ی خ قابل مرایبه ایت. نقطه شروع نقطه پايان و در اين الگوريتم یاده براي حالتي که |m|>1اگر نقش xو yرا عوض کنيم خ با شکستگي کم ر و دقت بيش ر ریم خواهد شد. 6 5 4 3 2 1 0 4 3 2 1 5 4 3 2 1 0 4 0 y=4x >1 شديدتر ایت پ غيیرا رایتاي yانجا ميشود 3 1 2 0 y=(1/4)x |m|>1 نمونه برداري در <1 شديدتر ایت پ غيیرا رایتاي xانجا ميشود |m|<1 نمونه برداري در : |m|<1 متنای ااذ ب ااا ن ااک ولت ااا منر اار کنن ااده افق اای کو ااک قا ارار داد ميش ااود یا ا مرایبه ميشود عمودی متناکر ،با ولت ااا منر اار کننا اده : |m|>1 متنایااذ بااا نااک ولت ااا منراار کننااده عمااودی کو ااک ق ارار داد ميشااود ی ا مرایبه ميشود افقی متناکر ،با ولتااا منراار کنن اده الگوریتم DDA مشکال روش معادله خ : عمل فرب عمل ROUNDکردنمرایبا اعشاريبراي از بین بردن عمل فرب از معادال نموي ( )Incremental Equationایتفاده ميشود x k+1= xk+ 1 yk+1- yk x k+1- xk =m نقطه شروع یمت رایت و |m|<1 x k+1= xk- 1 نقطه شروع یمت باال و |m|>1 y k+1= yk- 1 نقطه شروع یمت پ و |m|<1 x k+1= xk+ 1 نقطه شروع یمت پايین و |m|>1 y k+1= yk+ 1 # define ROUND (a) ((int) (a+0.5)) Void lineDDA (int xa, int ya, int xb, int yb) { int dx = xb – xa, dy = yb – ya, steps, k; float xIncrement, yIncrement, x = xa, y = ya; if (abs (dx) > abs (dy)) steps = abs (dx); else steps = abs (dy); xIncrement = dx / (float) steps; yIncrement = dy / (float) steps; setPixel (ROUND (x), ROUND (y)); for (k=0; k<steps; k++) { x += xIncrement; y += yIncrement; setPixel (ROUND(x), ROUND(y)); } } مزايا و معايب الگوريتم )Digital Differential Analyzer( DDA عمل فرب بکار رفته در معادله خ حذ میشودانباشاته شادن خطاهااای گارد کاردن در جمع ااای متاوا ی نموهاا در مااد اعاداد اعشااری کااه باعا دور شاادنتدریجی موافع پیکسلی از خ واقعی برای پاره خط ای ب ند ميشود عمل گرد کردن-حساب در مد اعشاري الگوریتم خط برزنهام ()Bresenham`s Algorithm قابل کس رش برای نمایش دانره ها و دنگر منرنی های -مرایبا صحیح نمو ؟ ؟ ؟ ؟ در مث ااال بر ا ش ااده روش برزن ااا را با اراي خط ااا ی ب ااا ف ااریذ زاوی ااه مثب اات و ک ااو ک ر از ن ااک ()0<m<1درنظ اار میگیرنم انت اااب ش ااده در مرح ااه kا پيکس االح ا ااال باي ا ااد تص ا ااميم بگی ا ااريم در مرح ا ااه ، K+1 پيکسل بعدي : يا ايا ا ا اان انت ا ا ا اااب با ا ا ااه کما ا ا ااک يا ا ا ااک پا ا ا ااارام رتصميمگیري انجا ميشود ؟ y k+1 ؟ yk x k+1 xk يافتن پارامتر تصميمگيري Pkبراي الگوريتم برزنهام y k+1 dupper y k+1 y dlower yk yk x k+1 xk else If (dupper > dlower) مرایبا اعشاري وجود دارد =m و فرض ميکنيم همواره >0 ميباشد و بر عالمت dkاثر ندارد Pk=dk . بنابراين عالمت pkهمان عالمت dkایت Cثابت و مقدار ن به xkو ykبستگي ندارد و برابر ایت با : =c پيکسل منت ذ بعدي )Pk<0 dk<0 dupper>dlower (xk+1,yk پيکسل منت ذ بعدي )Pk>0 dk>0 dupper<dlower (xk+1,yk+1 محاسبات صحیح و نموی Pk ()1 از نجا ي که 0<m<1مي باشد و Pk<0 yk+1 = yk Pk>0 yk+1= yk + 1 ن ستین پارام ر با قرار دادن پیکسل شروع خ y=mx+bو ارزیابی mبصور بدیت مي يد در معادله ( )1و همچنین در معادله الگوریتم ترسیم خط برزنهام برای 0 < m < 1 .1 .2 .3 .4 ذخیره کن. رئوس پاره خط را وارد و رأس چپ را در را قگگرار گگده ینن گ نخ گتین رنگگف یگگریف گگایر گگرا پی گ نقطه را ر ف کن. را محا گگگ ه مگگگ کنگگگیف و مقگگگدار و ، ، ثا تهگگگا گگه شگگرور را گگرا پگگارامتر تهگگمیف گگه هگگور م آوریف. د در هگر در طگو خگط گا شگرور ا k = 0آ مگون یگر را انمگاف مگ دهیف: و ا اگر pk<0نقطة ند را تر یف در غیگگگگگگگگگر ایگگگگگگگگگن هگگگگگگگگگور نقطگگگگگگگگگة نگگگگگگگگگد وده و .1مرحلة 4را ار انماف م دهیف. گگگگگگگگگرا تر گگگگگگگگگیف Void lineBres (int xa, int ya, int xb, int yb) { int dx = abs (xa – xb), dy = abs (ya –yb); int p = 2 * dy – dx; int twoDy = 2 * dy, twoDyDx = 2 * (dy – dx); int x, y, xEnd; /* Determine which point to use as start, which as end */ if (xa > xb) { x = xb; y = yb; xEnd = xb; } else { x = xa; y = ya; } setPixel (x , y); while (x < xEnd) { x++; if (p < 0) p += twoDy; else { y++; p += twoDyDx; } setPixel (x , y); } } مثال :خ با رئوی ) (20,10و ) (30,18به کمک الگوريتم برزن ا مرح ه به مرح ه توليد کنيد =)(20,10 =)(30,18 پارام ر تصمیم اولیه: نموها برای مرایبة پارام رهای تصمیم متوا ی K k )(26,15 6 5 )(21,11 6 0 )(27,16 2 6 )(22,12 2 1 )(28,16 -2 7 )(23,12 -2 2 )(29,17 14 8 )(24,13 14 3 )(30,18 10 9 )(25,14 10 4 برای خطی با فریذ زاویه مثبت و بزرگ ر از نک ،نقش ای ج ای xو yرا عوض می کنیم. y k+1= yk+ 1و تصميمگیري بین xkو xk+1ها )(xk,yk+1 يا )(xk+1,yk+1 y k+1= yk+ 1 dleft dright ؟ ؟ y k+1 yk x k+1 x xk برای خطی با فریذ زاویه منفي يکي از ج تها افزايش و ديگري کاهش مييابد xk+1= xk+ 1و تصميمگیري بین ykو yk-1ها ؟ yk y k-1 ؟ x k+1 xk خ هاي و و مستقيما و بدون پردازش با الگوريتم برزن ا ریم ميشوند نمایش چند ضلعیها پیاااده یااازی پااردازه نااد ف ا عی بااا n-1بااار فراخااوانی الگااوریتم تریاایم خ ا ب ارای نمااایش خط ااای متصاال کننده nرکی انجا می شود الگوریتمهای موازی خط با کار گیری پردازش موازی ،ندنن موفع پیکسلی را در طول مسیر خ می توان بصور همزمان با تقسيم مرایبا بین پردازنده های گوناگون مرایبه کرد روش او ل :پردازنده تقسیم مسیر خ به افراز خطی با فریذ زاویه 0 < m < 1و با رکی پ فاص ه بین xهای شروع افرازهای مجاو ر را در ج ت مثبت مرور xها افراز می کنیم (تقسيم صحيح) xشروع برای افراز kا 2,1,0تا np-1 هر پردازنده موافع پیکسلی زیر بازه منسوب به خود را با ایتفاده از مقدار پارام رتصمیم شروع مزبور و نقطه شروع مرایبه می کند دایره مجموعه نقاطی که همگی در فاص ه داده شده rاز نقطه مرکز قرار دارند از انن معادله می توان برای مرایبه نقاط روی مری دانره با برداش ن گام ایی بطول و احد در روی مرور و مرایبه مقادنر yاز : تا xها از مرایبا زیادفواصل بین موافع پیکسلی ریم شده نکنواخت ن واهد بود( .انان مساه ه را مای تاوان باا عاوی نقشا ای xو ( yگااا برداشا ن در ج اات yهااا و مرایاابه مقااادنر بارای xهااا) زمااانی کااه فااریذ زاویااه دانااره ب شا ر از نااک ایت بر طر کرد ) استفاده از معادالت قطبی پارامتری مرایبه نقاط روی مرز دانره با ایتفاده ز م تصا قطبی rو ب ااا بک ااارگیری ان اادازه گ ااا زاوی ااه ای ثاب اات ،دان ااره ای ب ااا نق اااط متس اااوی الفاص ا ه ب اار روی مر اایخواهد شد. ن ری اام بارای کاااهش مرایاابا ماای تااوان از فاصا ه زاویااه ای بزرگ اار بااین نقاااط روی مراای دانااره ایااتفاده کاارد ون ا را بویی ه پاره خط ایی برای تقریذ مری دانره ب م وصل کرد(ریم ند ف عيهاي منتظم) برای مرزی پیویته تر در ی ستم ری ر ،اندازه گا زاویه را می توان برابر-مرایبا مث ثا ی بکار رفته هنوز هم وقت گیر هستند قرار داد = r .طول کمان خاصیت تقارنی دایره مرایبا را می توان با در نظر گرف ن خاص ت تقارنی دانره ها کاهش داد تمامی موافع پیکسلی بر روی مری دانره را می توان فق با مرایبه نقاط واقع در کمان از x = 0تا x = yتولید کرد الگوریتم نقطه میانی برای دایره ()MidPoint Circle Algorithm نمونااه گیااری در بااازه هااای واحااد انجااا ماای شااود و در هاار مرح ااه نزدنااک تاارین موفااع پیکساالی بااه مساایردانره عیین می شود الگوريتم را براي دايرهاي به مرکز ) (0,0و به شعاع rبدیت مي وريم و به راحتاي باراي داياره باه هارمرکز دلخواه قابل گس رش ایت با توجه به تقارن در دايره کمان دانره از x = 0تا x = yدر ربع اول توليد و یهفت اوکتانت دنگر را با ایتفاده از خاص ت تقارن بدیت می وریم x=0 -1<m<0 x=y m=-1 m=0 نقاط واقع در معيار تصميمگیري ?=Pk يا مرح ه k+1ا ()xk+1=xk+1 با ااه دریا ااتي انت ا اااب شا ااده ایا اات ميخا ااواهيم تصا ااميم بگیا ااريم در مرح ا ااه در مرح ا ااه kا پيکسا اال با ااه دايا ااره نزديک ا اار يا ااا k+1ا ( )xk+1=xk+1کا اادا يا ااک از دو پيکسا اال ایت؟ X2+y2=r2 fcircle(x,y) = X2+y2 - r2 اگر ) (x,yداخل دانره باشد اگر ) (x,yروی مرز دانره باشد اگر ) (x,yخارج دانره باشد پارام ر تصمیم برای انن کار ،تابع ، fcircleارزیابی شده در نقطه میانی انن دوپیکسل خواهد بود )(xk+1,ykبه مرز دايره نزديک ر ایت نقطه مياني داخل دايره Pk<0 )(xk+1,yk-1به مرز دايره نزديک ر ایت نقطه مياني خارج دايره Pk>0 y( yk+1مرح ه بعد) مرایبا Pkپيچياده ميباشاد باراي کام کاردن مرایابا Pk+1را باا ایاتفاده از معاادال نماوي بدیات) مي وريم ( )y =(yk-1مرح ه بعد Pk<0 yk+1 = yk Pk>0 yk+1 = yk-1 و ?= P0 (برای rصحیح) الگوریتم نقطة میانی برای دایره را وارد ماای کناایم یا -1شااعاع rو مرکااز دانااره م تصا را به صور زیر قرار می دهیم م تصااا بارای ن سااتین نقطااه باار روی مراای دانااره بااه مرکاز -2در هار موقعیات xkباا شاروع از k = 0زماون زیار را انجاا مای دهایم .اگار Pk<0نقطاه بعادی بار روی دانارهي باه مرکاز ایت و داريم ) (0,0برابر در غیر انن صور ،نقطة بعدی بر روی دانره برابر که در ن ایت و داریم و -3نقاط متقارن در هفت اوکتانت دنگر را عیین می کنیم -4ها اار پیکسا اال مرایا اابه شا ااد ) (x,yرا با ااه روی دانا اار با ااه مرکا ااز م تصا زیر را ریم می کنیم. -5مراحل 2تا 4را نقدر تکرار می کنیم تا شرط برقرار شد منتقا اال ما اای کنا اایم و مقا ااادنر Void circleMidpoint (int xCenter, int yCenter, int radius) { int x = 0; int y = radius; int p = 1 – radius; /* Plot first set of points */ circlePlotPoints (xCenter, yCenter, x, y); while (x < y) { x++; if (p < 0) p += 2 * x + 1; else { y--; p+= 2 * (x – y) + 1; } circlePlotPoints (xCenter, yCenter, x, y); } } Void circlePlotPoints (int xCenter, int yCenter, int x, int y) { setPixel (xCenter + x, yCenter + y); setPixel (xCenter - x, yCenter + y); setPixel (xCenter + x, yCenter - y); setPixel (xCenter - x, yCenter - y); setPixel (xCenter + y, yCenter + x); setPixel (xCenter - y, yCenter + x); setPixel (xCenter + y, yCenter - x); setPixel (xCenter - y, yCenter - x); } مثال :دايرهاي به شعاع r = 10 k 20 20 20 18 18 16 14 ) y =(yk-1مرح ه بعد 2 4 6 8 10 12 14 )(1,10 )(2,10 )(3,10 )(4,9 )(5,9 )(6,8 )(7,7 -9 -6 -1 6 -3 8 5 0 1 2 3 4 5 6 Pk<0 yk+1 = yk Pk>0 yk+1 = yk-1 بیض ی مکان هندس ي بيض ي :مجموع فواصل هر نقطه واقع در روي بيض ي از دو نقطه ثابت به نا مراکز کان وني ثابت ایت. a + b = constant http://www.mathopenref.com/ellipse.html )F1=(x1,y1 )F2=(x2,y2 معادله بيض ي ایتاندارد که مرورهاي ن موازي مرورهاي م تصا به مرکز ycو xcبه شعاعهاي rxو ry معادله بيض ي مرکز (: )0،0 اگر ب واهیم نک بیض ی را در موقعیت غیر ایتاندارد نمایش دهیم می توانیم با دوران ن حول مرکزش، قطرهای بزرگ و کو ک نرا در ج ای دلخواه قرار دهیم بيض ي در مختصات قطبی تقارنی در بيض ي برای کاهش مرایبا : الگوریتم نقطه میانی برای بیض ی ()MidPoint Ellipse Algorithm يک ار بيض ي را به کمک الگوريتم نقطه مياني شبيه نچه بري دايره بدیت ورديم توليد ميکنيم و باقي مانده به کمک تقارن توليد ميشود -1<m<0 =شرور نقطه -inf<m<-1 اگر ) (x,yداخل بیض ی باشد اگر ) (x,yروی بیض ی باشد اگر ) (x,yخارج بیض ی باشد ي) پارام ر تصميم(معيار تصميم گی ر در ناحيه 1بيض ي : معيار تصميمگیري ?=P1k يا مرح ه k+1ا ()xk+1=xk+1 در ناحيه 2بيض ي : معيار تصميمگیري ?=P2k يا مرح ه k+1ا ()yk+1=yk-1 آزمون تشخيص خروج از ناحيه =-1 (من اي مشتق نسبت به x = mتقسيم بر مشتق نسبت به )y شرط خروج از ناحيه ( 1ورود به ناحيه )2 در ناحيه 1بيض ي : معيار تصميمگیري ?= P1k يا مرح ه k+1ا ()xk+1=xk+1 )midpoint=(xk+1 , yk- 0.5 )(xk+1,ykبه مرز بيض ي نزديک ر ایت نقطه مياني داخل بيض ي P1k <0 )(xk+1,yk-1به مرز بيض ي نزديک ر ایت نقطه مياني خارج بيض ي P1k >0 کم کردن مرایبا با مرایبه : P1k +1 P1k <0 yk+1=yk P1k >0 yk+1=yk-1 در ناحيه 2بيض ي : معيار تصميمگیري ?=P2k يا مرح ه k+1ا ()yk+1=yk-1 )midpoint=(xk+0.5 , yk-1 )(xk+1,yk-1به مرز بيض ي نزديک ر ایت نقطه مياني داخل بيض ي P2k <0 )(xk,yk-1به مرز بيض ي نزديک ر ایت نقطه مياني خارج بيض ي P2k >0 کم کردن مرایبا با مرایبه : P2k +1 P2k <0 xk+1=xk+1 P2k >0 xk+1=xk ? = P2k ) = (x0,y0خرين موقعيت انت اب شده در ناحيه 1 براي یاده شدن مرایبا p20مي توان در ناحيه 2در خال گا در ج ت مثبت مرور yتا ریيدن به ناحيه 1 رخش عقربه یاعت و با شروع از ( )rx,0و # include “device.h” # define ROUND(a) {(int) (a+0.5)) Void ellipseMidpoint (int xCenter, int yCenter, int Rx, int Ry) { /* Region 2 */ int Rx2 = Rx*Rx; p = ROUND (Ry2 * (x+0.5) * (x+0.5) + Rx2 * (y-1) * (y-1) – Rx2 * Ry2); int Ry2 = Ry*Ry; while (y > 0) { int twoRy2 = 2*Ry2; y--; int p; py -= twoRx2; int x = 0; if (p > 0) int y = Ry; p += Rx2 – py; int px = 0; else { x++; int py = twoRx2 * y; px += twoRy2; /* Plot the first set of points */ p += Rx2 – py + px; ellipsePlotPoints (xCenter, yCenter, x, y); } /* Region 1 */ ellipsePlowPoints (xCenter, yCenter, x, y); P = ROUND (Ry2 – (Rx2 * Ry) + (0.25 * Rx2)); } While (px < py) { } X++; Void ellipsePlotPoints (int xCenter, int yCenter, int x, int y) Px += twoRy2; { if (p < 0) setPixel (xCenter + x, yCenter + y); p += Ry2 + px; setPixel (xCenter – x, yCenter + y); else { setPixel (xCenter + x, yCenter – y); y--; setPixel (xCenter – x, yCenter – y); py -= twoRx2; } p += Ry2 + px – py; } ellipsePlotPoints (xCenter, yCenter, x, y); } مثال :ترسیم بیض ی به روش نقطه میانی و و P1k <0 yk+1=yk P1k >0 yk+1=yk-1 برای ناحیة 1 768 768 768 640 640 512 384 حاال ون 72 144 216 288 360 432 504 )(1,6 )(2,6 )(3,6 )(4,5 )(5,5 )(6,4 )(7,3 از ناحیة 1خارج می شویم -332 -224 -44 208 -108 288 244 k 0 1 2 3 4 5 6 و پارامتر تهمیف شرور نی را ناحیة ،2نقطه شرور را ر P2k <0 xk+1=xk+1 P2k >0 xk+1=xk 256 128 --- 576 576 --- )(8,2 )(8,1 )(8,0 -151 233 745 k 0 1 2 منحنی های دیگر ()Other Curves روش ی یاده برای نمایش منرنی ،تقریذ ن توی پاره خط ایت در جاهااایی کااه قاادر مط ااق فااریذ زاویااه منرناای انت اب و مقادنر yرا در نموهای xمتساوی مرایبه می کنیم. کااو ک ر از نااک ایاات xرا بعنااوان متغیاار مسااتقل زمانی که قدر مط ق فریذ زاویه منرنی بزرگ تر از نک ایت برای بدیت وردن موافع متساوی الفاصا ه ،از ایا ااتفاده و مقا ااادنر xرا در گا ااا ها ااای متسا اااوی الفاص ا ا ه در روی مرا ااور yها ااا تا ااابع معکا ااوی مرایبه می کنیم اکثر توابع منرنی دارای خاص ت تقارنی اند که می توان از انن خاص ت برای کاهش مرایبا موافع م تصا بر روی مسیر منرنی ها ایتفاده کرد هذلولي از تقارن ایتفاده مي کنيم و نیز منرني را به دو ناحيه ( |m|<1 )1و ( |m|>1 )2تقسيم مي کنيم نویسه ها ق م (فونت) :طرح و یبک کلی برای مجموعه ای از کاراک رها را فونت نقش بیتی (نا فونت : )bitmappedقرار دادن الگویی از مقادنر دودویی در رانه ای مستطیلی فضاي ذخیره یازي بيش ر ،هر غيیري در اندازه و فونت بايد در يک حافظه به نا فونت پن ان ( font )cacheذخیره شود(براي دو برابر کردن اندازه نو سه عداد پيکس ا نقش بيتي دو برابر شود) B فونت برون خطی ( : )Outline fontشک ای نویسه ای توی قطعه خط ای مستقیم و قطعه منرنی ها فضاي ذخیره یازي کم ر ،براي غيیر اندازه نو سهها عاريف منرنيها دیتکاري ميشوند ،پردازش فونتها وقتگیرتر ایت فونتها -1با سرکش ( : )serifداراي خ هاي کو ک يا عالئم نقطه گذاري در ان اي نو سههاي اصلي ایت مانند Lotus, Times New Romanو . . . کاربرد :خواناتر هستند و در م نهاي طوالني تر راحت تر خوانده ميشوند -2بدون سرکش ( : )sans serifخ هاي کو ک در ان اي نو سههاي وجود ندارد مانند Tahoma کاربرد:ک ما انفرادي،عنوان و بر سذ گذاري ،قاب يت شنایا ي بيش ر Amin Zare [email protected] [email protected] 2011/04/19