‫فصل سوم‬
‫مبناهای خروجی گرافیک‬
‫)‪(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‬‬
‫‪aminzare@cse.shirazu.ac.ir‬‬
‫‪Amin_zare@pnu.ac.ir‬‬
‫‪2011/04/19‬‬