مدلهای زبانی، فراکتالها، مجموعه ماندلبرو و نویز رویهای
۹.۷ مدلهای مبتنی بر زبان
یک دستگاه قواعد نهتنها میتواند رشتهها را تولید کند، بلکه میتواند رشتهای را بهعنوان ورودی بگیرد و بررسی کند که آیا آن رشته عضو معتبری از مجموعهٔ رشتههای حاصل از یک گرامر مشخص هست یا نه. بنابراین میتوان مجموعهای از قواعد برای تولید یک نوع شیء، مثلاً درخت یا بوته، داشت و برنامهای جداگانه نوشت که اشیای موجود در یک صحنه را بر پایهٔ گرامری که شکل آنها را تولید میکند شناسایی کند.
تفسیر نمادهای یک رشته، آن رشته را به یک شیء گرافیکی تبدیل میکند. راههای فراوانی برای ساخت قواعد و تفسیر رشتههای حاصل بهصورت اشیای گرافیکی وجود دارد. یکی از رویکردها از سامانهٔ گرافیک لاکپشتی (تمرین ۲.۴) آغاز میشود. در گرافیک لاکپشتی سه عمل پایه برای کنترل مکاننمای گرافیکی، یا «لاکپشت»، داریم: حرکت یک واحد به جلو، چرخش به راست و چرخش به چپ. اگر زاویهٔ چرخش ثابت باشد، این سه عمل را با F، R و L نشان میدهیم. هر رشته از این عملها تفسیر گرافیکی سادهای دارد. برای مثال، با زاویهٔ ۱۲۰ درجه، رشتهٔ FRFRFR یک مثلث متساویالاضلاع میسازد.
نمادهای ویژهٔ [ و ] برای push و pop کردن حالت لاکپشت ــ مکان و جهت آن ــ روی پشته بهکار میروند. قاعدهٔ تولید زیر را با زاویهٔ ۶۰ درجه در نظر بگیرید:
F \rightarrow FLFRRFLF
شکل ۹.۱۱ — قاعدهٔ منحنی کُخ.
اگر قاعده را دوباره و بهطور موازی بر همهٔ نمونههای F اعمال کنیم، منحنی کُخ بهدست میآید؛ و اگر آن را روی یک مثلث اجرا کنیم، دانهبرف کُخ ساخته میشود.
شکل ۹.۱۲ — منحنیهای کُخ: (الف) منحنی کُخ، (ب) دانهبرف کُخ.
اگر در هر اجرا منحنی را چنان مقیاس کنیم که رأسهای اولیه در مکان خود بمانند، در هر تکرار منحنی بلندتری ایجاد میشود ولی کل منحنی در همان جعبهٔ محدود جا میگیرد. در حد، منحنی طول بینهایت دارد، خود را قطع نمیکند، در جعبهای متناهی قرار میگیرد، پیوسته است و مشتق آن در همهجا ناپیوسته است.
نمونهٔ کلاسیک دیگر منحنی هیلبرت است. چهار الگوی پایه را (A_0)، (B_0)، (C_0) و (D_0) مینامیم. برای هر مرتبهٔ (N)، چهار منحنی (A_N)، (B_N)، (C_N) و (D_N) از ترکیب الگوهای مرتبهٔ (N-1) طبق قواعد زیر ساخته میشوند:
A_N = B_{N-1}\uparrow A_{N-1}\rightarrow A_{N-1}\downarrow C_{N-1}
B_N = A_{N-1}\rightarrow B_{N-1}\uparrow B_{N-1}\leftarrow D_{N-1}
C_N = D_{N-1}\leftarrow C_{N-1}\downarrow C_{N-1}\rightarrow A_{N-1}
D_N = C_{N-1}\downarrow D_{N-1}\leftarrow D_{N-1}\uparrow B_{N-1}
شکل ۹.۱۳ — الگوهای پایهٔ هیلبرت.
الگوی مرتبهٔ (N) با ترکیب چهار الگوی مرتبهٔ (N-1) در جهتهای مشخص ساخته میشود. در منحنی (A_1) باید برای اتصال الگوها پیوندهایی مطابق پیکانهای فرمول اضافه شود و هر الگو از گوشهای متفاوت شروع میکند. هنگام رسم نهایی، پیکانها و پیوندهای کمکی حذف میشوند.
شکل ۹.۱۴ — قاعدهٔ هیلبرت برای نوع A.
شکل ۹.۱۵ — منحنی هیلبرت مرتبهٔ دوم.
اگر در مرتبههای بالاتر طول پیوندها را مقیاس کنیم، منحنیهای هیلبرت همانند منحنیهای کُخ بلندتر میشوند، خود را قطع نمیکنند و در همان جعبه باقی میمانند. در حد، همهٔ نقاط جعبه را پُر میکنند و به همین دلیل منحنیهای فضاپُرکن نامیده میشوند.
عملگرهای push و pop اجازهٔ ایجاد شاخههای جانبی را میدهند. قاعدهٔ زیر را با زاویهٔ ۲۷ درجه در نظر بگیرید:
F \rightarrow F[RF]F[LF]F
شکل ۹.۱۶ — قاعدهٔ (F \rightarrow F[RF]F[LF]F).
رسم از پایین شروع میشود و زاویه انحراف راست یا چپ از جهت جلو است. با یک پارهخط آغاز میکنیم و سپس قاعده را روی هر F تکرار میکنیم. میتوان طول حرکت رو به جلو را در تکرارهای بعدی کاهش داد تا شاخهها کوچکتر شوند. حاصل شبیه بوته است، اما اعمال یک قاعدهٔ واحد بهصورت موازی همهٔ بوتهها را یکسان میکند.
شکل ۹.۱۷ — تکرار دوم قاعدهٔ شکل ۹.۱۶.
راهبرد جالبتر، اعمال تصادفی قاعده روی رخدادهای F است. با چند production دیگر و کنترل احتمال انتخاب آنها میتوان گونههای مختلف درخت ساخت و حتی در انتهای شاخهها برگ رسم کرد.
مزیت مهم این روش آن است که یک کلاس از اشیا با چند قاعده و چند پارامتر توصیف میشود. در روش مستقیم، هر درخت مجموعهٔ بزرگی از خطوط، چندضلعیها و منحنیهاست و در صحنهٔ پیچیده تعداد primitiveها بسیار زیاد میشود؛ بسیاری از آنها نیز به علت clipping یا فاصلهٔ زیاد اصلاً دیده نمیشوند. در روش رویهای هندسه فقط هنگام نیاز و فقط تا سطح جزئیات لازم تولید میشود.
شکل ۹.۱۸ — نتیجههای اعمال تصادفی قاعدهٔ شکل ۹.۱۶.
میتوان گرامر را مستقیماً بر حسب شکلها و تبدیلهای آفین تعریف کرد و گرامر شکل ساخت. برای واشر سیرپینسکی، یک مرحلهٔ تقسیم را میتوان با سه تبدیل آفین تعریف کرد؛ هر تبدیل مثلث اولیه را به نصف اندازه مقیاس میکند و نسخهٔ کوچک را در موقعیتی متفاوت میگذارد.
شکل ۹.۱۹ — سه قاعده برای واشر سیرپینسکی.
قواعد را میتوان تصادفی یا هر سه را موازی اعمال کرد؛ در هر دو حالت، در حد، واشر بهدست میآید. اکنون سه روش رویهای مرتبط داریم که میتوانند اشیای طبیعی یا اشیای ریاضی جالب تولید کنند. کُخ و سیرپینسکی جنبهٔ مهمی را نشان میدهند: روشی بازگشتی که هر بار جزئیاتی مشابه شکل اولیه میسازد. این پدیدهها با هندسهٔ فراکتالی بررسی میشوند.
۹.۸ روشهای بازگشتی و فراکتالها
مدلهای مبتنی بر زبان تنها یک راه ساخت اشیای پیچیده با برنامههای سادهاند. رویکرد دیگر بر هندسهٔ فراکتالی و خودشباهتی بسیاری از اشیای واقعی استوار است. ماندلبرو این شاخهٔ ریاضیات را توسعه داد تا بتوان پدیدههایی را بررسی کرد که هندسهٔ معمولی ابزار مناسبی برای آنها ندارد.
پژوهشگران گرافیک رایانهای از فراکتالها هم برای ساخت اشیای زیبا و پیچیده و هم برای مدلسازی پدیدههای واقعی دشوار استفاده کردهاند. اشیای گرافیکی حاصل از فراکتالها گاهی graftal نامیده شدهاند.
۹.۸.۱ خطکشها و طول
دو ستون هندسهٔ فراکتالی، وابستگی هندسه به مقیاس و خودشباهتی هستند. پرسش معروف «طول یک خط ساحلی چقدر است؟» هر دو را آشکار میکند. اگر خط ساحلی را روی نقشه با نخ اندازه بگیریم، طولی بهدست میآید. در نقشهای با بزرگنمایی بیشتر، خلیجچهها و برآمدگیهای بیشتری دیده میشوند و اندازهگیری طولانیتر میشود. اگر دقت را باز هم بیشتر کنیم، جزئیات جدید تا مقیاس سنگریزهها و در اصل تا مقیاس مولکولی ظاهر میشوند؛ هر بار تصویری مشابه با جزئیات بیشتر و طول بزرگتر خواهیم داشت.
برای داشتن اندازهای مفید باید وضوح را محدود کنیم یا کوچکترین واحد اندازهگیری را تعیین کنیم. در گرافیک پرسپکتیو نیز میزان جزئیات به فاصلهٔ بیننده از شیء بستگی دارد.
در منحنی کُخ هر پارهخط طول ۱ با چهار پارهخط طول (1/3) جایگزین میشود؛ پس هر مرحله، همان دو نقطهٔ انتهایی با مسیری به طول (4/3) طول قبل متصل میشوند. در حد، منحنی طول بینهایت و مشتق ناپیوسته در همهجا دارد، اما یک ناحیهٔ دوبعدی را پر نمیکند. این وضعیت با تعریف بُعد کسری توضیح داده میشود.
شکل ۹.۲۰ — افزایش طول منحنی کُخ.
شکل ۹.۲۱ — پارهخط، مربع و مکعب.
شکل ۹.۲۲ — تقسیم اشیا برای (h=1/3).
۹.۸.۲ بُعد فراکتالی
یک پارهخط واحد، مربع واحد و مکعب واحد بهترتیب یک، دو و سهبعدیاند. خطکشی با وضوح
h=\frac{1}{n}
در نظر بگیرید. پارهخط به (k=n) بخش، مربع به (k=n^2) مربع و مکعب به (k=n^3) مکعب کوچک تقسیم میشود. هر بار نسخههای مشابهی از شیء اصلی با مقیاس (h) میسازیم. اگر (d) بُعد شیء باشد، کل برابر مجموع اجزاست:
\frac{k}{n^d}=kn^{-d}=1.
بنابراین:
d=\frac{\ln k}{\ln n}.
در منحنی کُخ چهار نسخهٔ مشابه با مقیاس (1/3) داریم، پس:
d=\frac{\ln 4}{\ln 3}=1.26186.
برای واشر سیرپینسکی، هر بار که ضلع با ضریب ۲ تقسیم میشود، سه مثلث از چهار مثلث حاصل نگه داشته میشوند. در نتیجه:
d=\frac{\ln 3}{\ln 2}=1.58496.
شکل ۹.۲۳ — تقسیمبندی واشر سیرپینسکی.
هم در کُخ و هم در سیرپینسکی، شیء حاصل بیش از یک منحنی و کمتر از یک سطح پُر فضا اشغال میکند. نسخهٔ جامد واشر را میتوان در سه بعد از یک چهاروجهی ساخت: هر وجه تقسیم میشود، چهار چهاروجهی واقع در رأسهای اصلی نگه داشته و ناحیهٔ میانی حذف میشود.
شکل ۹.۲۴ — واشر جامد.
بُعد فراکتالی آن:
d=\frac{\ln 4}{\ln 2}=2
است، با آنکه شیء در صفحه قرار ندارد. در هر تقسیم، حجم کاهش و مساحت سطح افزایش مییابد.
اگر یک مکعب را در هر جهت به سه بخش تقسیم و بخش مرکزی و قطعات میانی هر وجه را حذف کنیم، از ۲۷ زیرمکعب اولیه ۲۰ زیرمکعب میماند:
d=\frac{\ln 20}{\ln 3}=2.72683.
شکل ۹.۲۵ — تقسیمبندی یک مکعب.
این ساختها از نظر گرافیکی جالب و در هر سطح بازگشت آساناند، اما بهتنهایی برای مدلسازی جهان واقعی چندان سودمند نیستند. افزودن تصادفیبودن آنها را به تکنیک مدلسازی قدرتمندی تبدیل میکند.
۹.۸.۳ تقسیم نقطهٔ میانی و حرکت براونی
منحنی فراکتالی دارای (1\le d<2) است. هرچه بُعد فراکتالی کمتر باشد منحنی نرمتر دیده میشود. برای سطحها نیز معمولاً (2\le d<3) است. در گرافیک رایانهای اغلب میخواهیم منحنی یا سطحی تصادفی اما با زبری قابل کنترل بسازیم؛ مثلاً خط افق کوهستان باید زبرتر از خط افق بیابان باشد و سطح زمین کوهستانی بُعد فراکتالی بیشتری از زمین کشاورزی داشته باشد.
همچنین تولید وابسته به وضوح مهم است. در شبیهساز پرواز، جزئیات بالا فقط برای نواحی نزدیک هواپیما لازم است.
حرکت تصادفی ذرات در سیال حرکت براونی نام دارد. مدل فیزیکی آن از توزیع تصادفی ویژهای استفاده میکند، اما در گرافیک بیشتر سرعت محاسبه و کنترل زبری اهمیت دارد؛ بنابراین اصطلاح حرکت براونی را به معنای گستردهتری به کار میبریم.
شکل ۹.۲۶ — جابهجایی نقطهٔ میانی: (الف) پارهخط اولیه، (ب) پس از تقسیم.
شکل ۹.۲۷ — منحنیهای فراکتالی با ۱، ۲، ۴، ۸ و ۱۶ پارهخط.
بهجای تولید مستقیم یک چندخطی براونی، میتوان از فرایند بازگشتی سادهتری استفاده کرد. نقطهٔ میانی یک پارهخط را پیدا میکنیم و آن را به فاصلهای تصادفی در راستای نرمال جابهجا میکنیم. با تکرار، منحنیهای فراکتالی ساخته میشوند.
چون پارهخطها در هر مرحله کوتاهتر میشوند، واریانس مولد عدد تصادفی یا میانگین جابهجایی نیز باید هر بار با ضریبی ــ معمولاً (1/2) ــ کاهش یابد. میتوان جابهجایی را در جهتی تصادفی انجام داد. اگر اعداد تصادفی همواره مثبت باشند، میتوان خط افق ایجاد کرد. اگر مولد گاوسی با میانگین صفر و واریانس متناسب با
l^{2(2-d)}
بهکار رود، که (l) طول پارهخط در حال تقسیم است، (d) بُعد فراکتالی منحنی حاصل خواهد بود. مقدار (d=1.5) متناظر با حرکت براونی واقعی است.
شکل ۹.۲۸ — تقسیم نقطهٔ میانی یک وجه چهاروجهی.
شکل ۹.۲۹ — زمین فراکتالی: (الف) مش، (ب) مش تقسیمشده با رأسهای جابهجاشده.
۹.۸.۴ کوههای فراکتالی
شناختهشدهترین کاربرد فراکتال در گرافیک رایانهای تولید کوه و terrain است. در فرایند تقسیم چهاروجهی، ابتدا نقاط میانی ضلعهای یک وجه را پیدا و هر نقطهٔ میانی را جابهجا میکنیم تا چهار مثلث تازه ساخته شود. با کنترل واریانس مولد عدد تصادفی، زبری شیء حاصل کنترل میشود. برای آنکه شیء از نظر توپولوژیک درست باشد و روی خودش تا نخورد باید در تولید اعداد تصادفی دقت کرد. حتی میتوان رأسهای اولیه را نیز جابهجا کرد.
این الگوریتم روی هر مش قابل اعمال است. میتوان از یک مش تخت مستطیلی در صفحهٔ (x,z) آغاز کرد، هر مستطیل را به چهار مستطیل کوچکتر تقسیم و رأسها را در جهت (y) به بالا جابهجا کرد. بخش ۹.۹ راه دیگری برای تولید terrain ارائه میکند.
شکل ۹.۳۰ — صفحهٔ مختلط.
۹.۸.۵ مجموعهٔ ماندلبرو
مجموعهٔ ماندلبرو نمونهای مشهور از هندسهٔ فراکتالی است که بهسادگی با قابلیت ترسیم پیکسلی OpenGL تولید میشود، اما الگوهایی با پیچیدگی نامتناهی دارد و نمونهٔ خوبی برای تولید تصویر و جدول نگاشت رنگ است.
نقطهای در صفحهٔ مختلط را مینویسیم:
z=x+iy
که (x) بخش حقیقی و (y) بخش موهومی است. برای دو عدد
z_1=x_1+iy_1,\qquad z_2=x_2+iy_2
داریم:
z_1+z_2=x_1+x_2+i(y_1+y_2),
z_1z_2=x_1x_2-y_1y_2+i(x_1y_2+x_2y_1).
همچنین (i^2=-1) و
|z|^2=x^2+y^2.
تابع
w=F(z)
نقاط مختلط را به نقاط مختلط نگاشت میکند و میتوان رابطهٔ بازگشتی
z_{k+1}=F(z_k)
را با (z_0=c) تعریف کرد. مسیرهای حاصل بسته به نقطهٔ شروع میتوانند رفتارهای متفاوتی داشته باشند.
شکل ۹.۳۱ — مسیرهای حاصل از رابطهٔ بازگشتی مختلط.
برای یک تابع (F)، برخی مقدارهای آغازین دنبالههایی واگرا به بینهایت میسازند، برخی دورهایاند و برخی به نقاطی به نام جاذب همگرا میشوند.
برای
z_{k+1}=z_k^2,\qquad z_0=c
اگر (c) بیرون دایرهٔ واحد باشد دنباله واگراست؛ اگر داخل آن باشد به مبدأ همگرا میشود؛ و اگر (|c|=1) باشد همهٔ نقاط روی دایرهٔ واحد میمانند.
نمونهٔ مهمتر:
z_{k+1}=z_k^2+c,\qquad z_0=0+i0.
نقطهٔ (c) عضو مجموعهٔ ماندلبرو است اگر و تنها اگر دنبالهٔ حاصل متناهی باقی بماند. بنابراین صفحهٔ مختلط به نقاط عضو و غیرعضو تقسیم میشود. میتوان یک ناحیهٔ مستطیلی را گرفت و اعضا را سیاه و غیرعضوها را سفید کرد. بیشترین پیچیدگی در لبههاست و معمولاً همان نواحی بزرگنمایی میشوند.
محاسبه زمانبر است. ناحیهٔ پیرامون (c=-0.5+i0.0) اهمیت زیادی دارد، هرچند اندازه و مرکز پنجره باید قابل تغییر باشد. اگر در تکرارها (|z_k|>4) شود، دنباله به واگرایی میرود و میتوان محاسبه را متوقف کرد. تشخیص همگرایی نزدیک مرز دشوارتر است. بنابراین تعداد بیشینهای برای تکرار تعیین میشود؛ نقاطی که واگرا شوند سفید و نقاطی که پس از آن تعداد تکرار هنوز زیر آستانه باشند سیاه در نظر گرفته میشوند.
شکل ۹.۳۲ — مجموعهٔ ماندلبرو: (الف) رنگآمیزی سیاهوسفید، (ب) جزئیات لبهها.
برای مقدارهای دیگر (|z_k|)، میتوان به پیکسل متناظر با (c) رنگ ویژهای داد. رنگ معمولاً از مقدار (|z_k|) پس از آخرین تکرار یا از سرعت همگرایی/واگرایی استخراج میشود.
برنامهٔ نمونه میتواند اندازه و مرکز مستطیل و تعداد تکرارها را از کاربر بگیرد. اندازهٔ (z_k) به بازهٔ ۰ تا ۱ clamp میشود و با پیمایش همهٔ پیکسلها، یک تصویر آرایهای (n\times m) تکبایتی ساخته میشود.
تصویر بهصورت texture روی مربعی متشکل از دو مثلث نگاشت میشود. رأسها و مختصات texture میتوانند چنین باشند:
point4 points[6] = {point4(0.0, 0.0, 0.0, 1.0), point4(0.0, 1.0, 0.0, 1.0),
point4(1.0, 1.0, 0.0, 1.0), point4(1.0, 1.0, 0.0, 1.0),
point4(1.0, 0.0, 0.0, 1.0), point4(0.0, 0.0, 0.0, 1.0)};
GLfloat tex_coord[6][2] = {{0.0, 0.0}, {0.0, 1.0}, {1.0, 1.0}, {1.0, 1.0},
{1.0, 0.0}, {0.0, 0.0}};
اگر رأسهای دوبعدی بخواهیم:
GLfloat points[6][2] = {{0.0, 0.0}, {0.0, 1.0}, {1.0, 1.0}, {1.0, 1.0},
{1.0, 0.0}, {0.0, 0.0}};
texture map مانند فصل ۷ تنظیم میشود. سادهترین تصویر luminance چنین آرایهای دارد:
پس از محاسبهٔ مقادیر مجموعه، تصویر به روش معمول نمایش داده میشود:
void display()
{
glClear(GL_COLOR_BUFFER_BIT);
glDrawArrays(GL_TRIANGLES, 0, 6);
glutSwapBuffers();
}
شکل ۹.۳۲(الف) با همین روش ساخته شده است. برای نمایش جزئیات بیشتر میتوان luminance را به RGB نگاشت کرد:
و برای مقدار روشنایی (v):
if(v>1.0) v=1.0; /* clamp if > 1 */
image[i][j][0] = v;
image[i][j][1] = 2.0*sin(v)-1.0;
image[i][j][2] = 1.0 - v;
کانال قرمز از صفر برای سیاه تا یک برای سفید بهصورت خطی تغییر میکند؛ کانال آبی برعکس آن است؛ و سبز بهصورت سینوسی تعیین میشود. این انتخاب سبز جزئیات نواحی با تغییر آهستهٔ شدت را تقویت میکند.
۹.۹ نویز رویهای
مولدهای عدد شبهتصادفی برای واشر سیرپینسکی، تقسیمبندی فراکتالی، texture و مدلسازی اشیای طبیعی مانند ابر و سیال کاربرد دارند، اما مولد ساده همیشه مناسب نیست.
نویز سفید را میتوان با نویز حرارتی مدارهای الکتریکی یا برفک تلویزیون بدون سیگنال مقایسه کرد. در نویز سفید ایدهآل، بین نمونههای متوالی هیچ همبستگی وجود ندارد و نمونهٔ بعدی از قبلیها قابل پیشبینی نیست. طیف توان آن تخت است؛ یعنی همهٔ فرکانسها با قدرت یکسان حضور دارند.
رایانه دنبالههای شبهتصادفی مانند خروجی rand تولید میکند. این دنبالهها عملاً نامرتبطاند، ولی چون پس از دورهای طولانی تکرار میشوند تصادفی حقیقی نیستند.
برای بیشتر کاربردها این موضوع مسئلهای نیست، اما اغلب نویز سفید چیزی نیست که لازم داریم. در تولید terrain برای بازی، اگر ارتفاع رأسهای مش با نویز سفید تعیین شود، به علت مؤلفههای فرکانس بالا سطح بسیار زبر خواهد شد. برای زمین هموارتر، ارتفاع رأسهای مجاور باید نزدیک باشد؛ یعنی فرکانسهای بالا حذف یا طیف «رنگی» شود.
مشکل دیگر فرکانسهای بالا aliasing است. نمونهبرداری فرکانسهای نزدیک نرخ نایکوئیست را alias میکند و artifactهای بصری آزاردهنده ایجاد میشود.
برای ساخت دنبالهٔ band-limited با فرکانسهای دلخواه میتوان مجموع سینوسهای کمفرکانس با دامنه و فاز تصادفی را نمونهبرداری کرد. این سنتز فوریه در اصل کار میکند اما محاسبهٔ توابع مثلثاتی برای هر نمونه پرهزینه است.
روش دیگر فیلتر دیجیتال نویز سفید است. فیلتر را میتوان برای عبور فرکانسهای مطلوب با دامنه و فاز موردنظر طراحی کرد. خروجی با طیف غیریکنواخت نویز رنگی نامیده میشود.
شکل ۹.۳۳ — تولید اعداد تصادفی همبسته: نویز سفید، فیلتر دیجیتال و نویز رنگی.
در یک روش رویهای علاوه بر هزینهٔ کم، تکرارپذیری و محلی بودن لازم است. pattern یا texture تصادفی باید در بازتولید شیء دقیقاً دوباره ساخته شود و مقدار هر ناحیه نیز ترجیحاً فقط از دادههای محلی بهدست آید.
روی شبکهٔ یک، دو یا سهبعدی با نقاط صحیح میتوان دنبالهٔ شبهتصادفی تولید کرد و مقدار نقاط غیرصحیح میان سلولها را درونیابی نمود. برای texture دوبعدی، یک آرایهٔ مستطیلی تصادفی میسازیم و برای هر مختصات ((s,t)) سلول را یافته و چهار گوشه را bilinear interpolation میکنیم.
این روش value noise است و نرمی آن با اندازهٔ بخشی از آرایه که استفاده میشود کنترل میشود.
اگر آرایهٔ تصادفی (256\times256) و texture نهایی (128\times128) باشد، استفاده از یک سلول و درونیابی همهٔ تصویر از چهار گوشه، تصویری بسیار نرم میدهد. استفاده از بخش (4\times4) تنوع بیشتری ایجاد میکند. استفادهٔ مستقیم از بخش (128\times128) بدون درونیابی، texture کاملاً نامرتبط میسازد.
مشکل bilinear interpolation آن است که مرز سلولها artifact قابل مشاهده ایجاد میکند. چندجملهایهای مکعبی با دادهٔ سلولهای مجاور نرمترند. یک چندجملهای مکعبی چهار ضریب و چهار داده میخواهد. در دو بعد ۱۶ نقطهٔ (4\times4) و در سه بعد ۶۴ نقطه لازم است؛ نتیجه نرمتر است اما هزینهٔ محاسبه و مدیریت داده زیاد میشود.
راهحل، gradient noise است. نویز سهبعدی را تابع پیوستهٔ (n(x,y,z)) بگیرید. نزدیک نقطهٔ شبکهٔ صحیح ((i,j,k)):
n(x,y,z)\approx n(i,j,k)+(x-i)\frac{\partial n}{\partial x}
+(y-j)\frac{\partial n}{\partial y}
+(z-k)\frac{\partial n}{\partial z}.
بردار
g=
\begin{bmatrix}g_x\\g_y\\g_z\end{bmatrix}
=
\begin{bmatrix}
\frac{\partial n}{\partial x}\\frac{\partial n}{\partial y}\\frac{\partial n}{\partial z}
\end{bmatrix}
گرادیان در نقطه است و (x-i)، (y-j)، (z-k) بخش کسری مکان داخل سلولاند.
در هر نقطهٔ شبکه یک گرادیان شبهتصادفی نرمالشده تولید میکنیم؛ میتوان آنها را از نقاط با توزیع یکنواخت روی کرهٔ واحد ساخت. مقدار خود نقاط شبکه را صفر میگذاریم: (n(i,j,k)=0). در سه بعد، هشت گرادیان گوشههای هر سلول با یک درونیابی فیلترشده و نرم برای محاسبهٔ نویز داخلی استفاده میشوند.
این روش به افتخار ابداعکنندهاش Perlin noise یا فقط noise نامیده میشود و در RenderMan و GLSL نیز وجود دارد. پیادهسازی معمول از hash table استفاده میکند تا بهجای تولید گرادیان برای کل شبکه، تنها ۲۵۶ یا ۵۱۲ عدد شبهتصادفی لازم باشد.
شکل ۹.۳۴ — تصاویر gradient noise: (الف) noise، (ب) 50*noise، (ج) 100*noise.
شکل ۹.۳۴ نویز گرادیانی دوبعدی را در سه فرکانس متفاوت نشان میدهد. هر کدام تصویر luminance به اندازهٔ (256\times256) است و همه از همان آرایهٔ اولیهٔ اعداد شبهتصادفی آغاز میشوند.
نویز رویهای کاربردهای گوناگونی دارد. افزودن نویز کوچک به موقعیت مفصلهای یک مدل پیکره میتواند حس واقعگرایی ایجاد کند. افزودن یک غیرخطیسازی مانند قدرمطلق به مولد نویز، دنبالههایی میسازد که برای مدلسازی آشفتگی جریان و تولید texture استفاده شدهاند. نویز رویهای برای مدلسازی اشیای «پفدار» مانند ابرهای شبیهسازیشده نیز به کار میرود.
جمعبندی و یادداشتها
روشهای رویهای اجازه میدهند تعداد primitiveهای تولیدی و زمان تولید آنها کنترل شود. مهمتر آنکه گرافیک رویهای رویکردی شیءگرا برای ساخت مدل فراهم میکند و انتظار میرود اهمیت آن بیشتر شود.
ترکیب فیزیک و گرافیک رایانهای مجموعهای از تکنیکها برای انیمیشنهای فیزیکی صحیحتر و روشهای جدید مدلسازی فراهم میکند. نمونههایی مانند استفاده از مدلسازی فیزیکی برای حرکت حدود ۱۰۰۰ بادکنک در فیلم Up از Pixar Animation Studios نشان میدهند حل دستگاههای پیچیدهٔ معادلات چگونه میتواند پایهٔ یک انیمیشن باشد.
سامانههای ذرهای تنها یک نمونه از مدلسازی فیزیکیاند، اما کاربرد بسیار گسترده دارند. ساختن یک سامانهٔ ذرهای در این مرحله تمرینی بسیار آموزنده است.
روشهای ذرهای در انیمیشن تجاری برای شبیهسازی آتش، ابر، آب متحرک و نیز تعیین موقعیت شخصیتها استفاده میشوند. آنها همچنین به روشی استاندارد برای شبیهسازی پدیدههای فیزیکی تبدیل شدهاند و گاه جای مدلهای پیچیدهٔ معادلات دیفرانسیل جزئی را میگیرند، حتی وقتی خروجی گرافیکی لازم نیست. در بازیها و شبیهسازیهای تعاملی میتوان برای هر ذره قواعد رفتاری پیچیده تعریف کرد؛ این ترکیب گرافیک و هوش مصنوعی مدلسازی مبتنی بر عامل نام دارد.
فراکتالها نیز با الگوریتمهای ساده اشیایی با پیچیدگی ظاهری بسیار زیاد تولید میکنند. نویز رویهای در قلب بیشتر روشهای مدلسازی رویهای قرار دارد و اغلب در ترکیب با روشهای دیگر بیشترین قدرت را نشان میدهد.
با افزایش توان محاسباتی و کاهش هزینهٔ دسترسی، همگرایی روشهای گرافیک با فیزیک، ریاضیات و علوم دیگر بیشتر خواهد شد. در گذشته به دلیل محدودیت توان پردازش، نمایشهایی که فقط «قابل قبول» به نظر میرسیدند پذیرفته میشدند، حتی اگر فیزیک آنها دقیق نبود. اکنون انتظار میرود مدلسازی فیزیکی صحیح در کاربردهای گرافیک رایانهای فراگیرتر شود.
منابع پیشنهادی
سامانههای ذرهای در گرافیک رایانهای توسط Reeves [Ree83] معرفی شدند و پس از آن برای دستهپروازی پرندگان [Rey87]، جریان سیال، آتش، مدلسازی چمن و نمایش سطحها [Wit94a] به کار رفتند. ذرات در فیزیک و ریاضیات نیز جایگزینی برای حل دستگاههای پیچیدهٔ معادلات دیفرانسیل جزئی در جریان سیال و مکانیک جامداتاند؛ برای نمونه [Gre88]. رویکرد این فصل از Witkin [Wit94b] پیروی میکند و نمونههای فراوان مدلسازی رویهای در [Ebe02] آمده است.
ادبیات فراکتال بسیار گسترده است. Fournier [Fou82] نخستین نمایش کوه فراکتالی را ارائه کرد. برای ریاضیات عمیقتر فراکتال میتوان به Mandelbrot [Man82] و Peitgen [Pei88] مراجعه کرد. گرامرهای گراف در [Pru90, Smi84, Lin68] بررسی شدهاند. Hill [Hil07] و Prusinkiewicz [Pru90] منحنیها و سطحهای فضاپُرکن را بررسی میکنند. سامانههای تابع تکرارشوندهٔ Barnsley [Bar93] نیز رویکرد دیگری برای خودشباهتیاند و در حوزههایی مانند فشردهسازی تصویر کاربرد دارند.
gradient noise به Perlin [Per85, Per89, Per02] برمیگردد. کاربردهای texture و تولید شیء و بحث value noise در [Ebe02] آمده است.
تمرینها
۹.۱ قواعدی برای تولید واشر سیرپینسکی با آغاز از یک مثلث متساویالاضلاع بیابید.
۹.۲ چگونه بُعد فراکتالی خط ساحلی را تعیین و فراکتالی بودن شکل آن را تأیید میکنید؟
۹.۳ برنامهٔ تقسیم چهاروجهی فصل ۵ را که برای تقریب کره بود، به برنامهٔ تولید کوه فراکتالی تبدیل کنید.
۹.۴ برنامهای در OpenGL بنویسید که توصیف یک درخت دودویی به شکل گرهها و اشارهگرهای فرزند را بگیرد و آن را گرافیکی نمایش دهد.
۹.۵ سامانهٔ سادهٔ جرم–فنر بسازید، آن را بهصورت مش چهارضلعی رندر کنید و تعاملی برای تعیین موقعیت اولیهٔ ذرات فراهم کنید.
۹.۶ به تمرین ۹.۵ نیروهای خارجی بیفزایید و پرچمی در حال وزش را تولید کنید.
۹.۷ برنامهای برای fractalize کردن یک مش بنویسید و برای موقعیت اولیه از دادهٔ ارتفاع واقعی استفاده کنید.
۹.۸ برنامهای بسازید که دو چندضلعی با تعداد رأس یکسان را گرفته و دنبالهای از تصاویر تبدیل یکی به دیگری تولید کند.
۹.۹ با ثابت گرفتن (c) در فرمول ماندلبرو و یافتن نقاط آغازینی که همگرا میشوند، مجموعهٔ Julia آن (c) حاصل میشود. برنامهای برای نمایش مجموعههای Julia بنویسید. راهنما: (c)های نزدیک لبهٔ مجموعهٔ ماندلبرو را امتحان کنید.
۹.۱۰ سامانهٔ ذرهای برای شبیهسازی جرقههای جوشکاری یا آتشبازی بنویسید.
۹.۱۱ تمرین ۹.۱۰ را برای شبیهسازی انفجار یک چندوجهی توسعه دهید.
۹.۱۲ alpha blending فصل ۷، تولید کره فصل ۵ و فراکتالها را برای ساخت ابر ترکیب کنید.
۹.۱۳ با فراکتالها سطح یک سیارهٔ مجازی دارای قاره و اقیانوس تولید کنید.
۹.۱۴ سامانهٔ Lennard-Jones را شبیهسازی کنید که در آن نیروی جاذبه متناسب با معکوس فاصله به توان ۱۲ و نیروی دافعه متناسب با معکوس فاصله به توان ۲۴ است. ذرهای که از یک سمت جعبه خارج میشود میتواند از سمت مقابل وارد شود.
۹.۱۵ فضا را به مکعبهای هماندازه تقسیم کنید و اجازه دهید هر ذره فقط با ذرات مکعب خود و مکعبهای مجاور تعامل داشته باشد.
۹.۱۶ سامانهای برای شخصیتهای متحرک بسازید که موقعیت آنها با ذرات تعیین شود و تصاویر دوبعدی شخصیتها روی چندضلعیها texture-map شوند. نیروهای هدایتکننده و دافعهٔ جلوگیری از برخورد را لحاظ کنید. روشی بیابید که چندضلعیها همیشه رو به دوربین باشند.
۹.۱۷ طول عمر ذره را اضافه کنید و سامانه را با linked list بهجای آرایه بازپیادهسازی کنید تا افزودن و حذف آسانتر شود.
۹.۱۸ ذرات را بهصورت تقریبهای سایهزنیشدهٔ کره رندر کنید.
۹.۱۹ با چهار نقطهٔ متصل در یک زنجیره و سامانهٔ جرم–فنر، یک تار مو یا تیغهٔ چمن را شبیهسازی کنید.
۹.۲۰ الگوریتمهای flocking گوناگون را آزمایش کنید؛ مثلاً حرکت به مرکز جرم کل ذرات یا حرکت هر ذره به سمت یک ذرهٔ «دوست».
۹.۲۱ نویز رویهای را به مدل پیکره اضافه کنید تا در حالت سکون نیز هر مفصل اندکی حرکت داشته باشد.
۹.۲۲ یک منظرهٔ فراکتالی با نویز رویهای پیادهسازی کنید و امکان حرکت بیننده و zoom in/out را اضافه کنید.