تقسیمبندی مش، تولید مش از داده و تمرینهای فصل دهم
شکل ۱۰.۴۲ — (الف) منحنی خطیِ قطعهای تعیینشده با چهار نقطه. (ب) منحنی خطیِ قطعهای پس از یک مرحله تقسیمبندی.
میتوان از فرمولهای تقسیمبندی برای ارتباطدادن دو مجموعهٔ نقاط استفاده کرد:
s_0=p_0,
s_1=\frac12(p_0+p_1),
s_2=\frac14(p_0+2p_1+p_2),
s_3=\frac18(p_0+3p_1+3p_2+p_3),
s_4=\frac14(p_1+2p_2+p_3),
s_5=\frac12(p_2+p_3),
s_6=p_3.
گفته میشود منحنی دوم پالایش (refinement) منحنی نخست است. همانطور که در بخش ۱۰.۹.۲ دیدیم، میتوان فرایند را بهصورت تکراری ادامه داد و در حد به B-Spline همگرا شد. در عمل فقط آنقدر تکرار انجام میدهیم که منحنی خطیِ قطعهایِ حاصل، که نقاط جدید را به هم متصل میکند، نرم به نظر برسد. تعداد تکرار لازم به اندازهٔ تصویرشدهٔ پوستهٔ محدب بستگی دارد و این اندازه از مشخصات دوربین بهدست میآید. بنابراین روشی داریم که اجازه میدهد منحنیها را در سطوح مختلف جزئیات رندر کنیم.
این ایدهها و مزایایشان به B-Spline محدود نیستند. در سالهای اخیر روشهای گوناگونی برای تولید منحنیهای تقسیمبندیشونده ارائه شده است. بعضی از آنها نقاطی مانند (p_0) و (p_3) را درونیابی میکنند و بعضی هیچیک از نقاط اولیه را درونیابی نمیکنند؛ اما در همهٔ حالتها، منحنیهای پالایشیافته به یک منحنی نرم همگرا میشوند.
۱۰.۱۲.۱ تقسیمبندی مش
اکنون بررسی میکنیم چگونه همین ایدهها را روی سطحها اعمال کنیم. نظریهای برای سطحهای تقسیمبندیشونده شکل گرفته است که هم جنبههای نظری و هم جنبههای عملی این موضوع را پوشش میدهد. بهجای ساخت یک طرح عمومی تقسیمبندی، بر مشهای مثلثی و مشهای چهارضلعی تمرکز میکنیم. در عمل بسیاری از برنامههای مدلسازی یکی از این دو نوع مش، یا مشی متشکل از ترکیب مثلث و چهارضلعی، تولید میکنند.
شکل ۱۰.۴۳ — تقسیمبندی چندضلعی: (الف) مثلث، (ب) مستطیل، (ج) چندضلعی ستارهای.
اگر با یک مش عمومیتر آغاز کنیم، میتوان با tessellation مش اولیه را با مشی متشکل فقط از مثلثها یا چهارضلعیها جایگزین کرد.
با روش Catmull-Clark میتوان از یک مش دلخواه، مش چهارضلعی ساخت. هر یال را از وسط نصف میکنیم و در نقطهٔ میانی رأس جدیدی میسازیم. سپس در مرکز هندسی هر چندضلعی یک رأس اضافی ایجاد میکنیم؛ مرکز هندسی همان میانگین رأسهای سازندهٔ چندضلعی است. بعد با اتصال هر رأس اولیه به دو رأس جدید دو سوی آن و اتصال آن دو رأس جدید به مرکز هندسی، یک مش چهارضلعی تشکیل میدهیم. شکل ۱۰.۴۳ تقسیمبندی چند چندضلعی ساده را نشان میدهد. در هر حالت نتیجه یک مش چهارضلعی است.
پس از ساختهشدن مش چهارضلعی، روشن است که تقسیمبندیهای پیاپی مشهای چهارضلعی ریزتری تولید میکنند. اما هنوز کاری برای نرمترکردن سطح انجام ندادهایم. بهویژه میخواهیم تا حد امکان در رأسها پیوستگی ایجاد کنیم.
روش زیر را در نظر بگیرید. ابتدا موقعیت میانگین هر چندضلعی، یعنی مرکز هندسی آن، را محاسبه میکنیم. سپس هر رأس را با میانگین مرکزهای هندسی تمام چندضلعیهایی که آن رأس را دارند جایگزین میکنیم. در این مرحله سطح نرمتر است، اما در رأسهایی که valence یا ظرفیت اتصالشان ۴ نیست هنوز تغییر تند در نرمی دیده میشود. طرح Catmull-Clark با یک مرحلهٔ دیگر سطح نرمتری ایجاد میکند. برای هر رأسی که valence آن ۴ نیست، آن را با
p=\frac{4}{k}p_0+p_1
جایگزین میکنیم؛ در این رابطه (p_0) موقعیت رأس پیش از مرحلهٔ میانگینگیری، (p_1) موقعیت آن پس از گذر میانگینگیری و (k) valence رأس است. valence یک رأس تعداد چندضلعیهایی است که آن رأس را مشترک دارند. این روش معمولاً رأسهای یال در گوشهها را بیش از سایر رأسهای بیرونی جابهجا میکند.
شکل ۱۰.۴۴ دنبالهٔ عملیات را برای یک مستطیل نشان میدهد. در شکل ۱۰.۴۴(الف)، رأسهای اصلی سیاه و رأسهای نقاط میانی یالها سفیدند. مرکز هندسی چندضلعی اصلی رأس خاکستری وسط است و مرکزهای هندسی چندضلعیهای تقسیمشده با رأسهای رنگی نشان داده شدهاند. شکل ۱۰.۴۴(ب) جابهجایی رأسها بر اثر میانگینگیری را نشان میدهد.
شکل ۱۰.۴۴ — تقسیمبندی Catmull-Clark.
شکل ۱۰.۴۴(ج) تقسیمبندی نهایی Catmull-Clark را پس از اعمال ضریب اصلاح نشان میدهد.
این طرح برای مشهایی که از ابتدا همهٔ وجههایشان مثلث است به همان اندازه مناسب نیست، زیرا رأسهای داخلی valence بالایی دارند که با پالایش تغییر نمیکند. برای مشهای مثلثی روش سادهای به نام Loop subdivision (تقسیمبندی Loop) وجود دارد که میتوان آن را گونهای از طرح عمومی دانست.
با تقسیمبندی استاندارد هر مثلث آغاز میکنیم: نیمسازهای اضلاع را به هم وصل میکنیم تا چهار مثلث ساخته شود. سپس مانند قبل پیش میرویم، اما از مرکز هندسی وزندار رأسها استفاده میکنیم؛ وزن رأسی که جابهجا میشود (1/4) و وزن هر یک از دو رأس دیگر مثلث (3/8) است. برای نرمترشدن سطح، مانند طرح Catmull-Clark، میانگین وزنداری از موقعیت رأس پیش و پس از مرحلهٔ میانگینگیری میگیریم. روش Loop از وزن
\frac58-\frac38\left(\frac38+\frac14\cos\left(\frac{2\pi}{k}\right)\right)^2
استفاده میکند.
شکل ۱۰.۴۵ — تقسیمبندی Loop: (الف) مش مثلثی، (ب) مثلثها پس از یک تقسیمبندی.
شکلهای لوح رنگی ۲۹ با سطحهای تقسیمبندیشونده تولید شدهاند. شکل ۱۰.۴۶ دنبالهای از مشهای تولیدشده توسط یک الگوریتم سطح تقسیمبندیشونده و سطح رندرشده از مش با بالاترین تفکیک را نشان میدهد. مش اولیه چندضلعیهایی با تعداد ضلعهای مختلف و رأسهایی با valenceهای متفاوت دارد.
شکل ۱۰.۴۶ — تقسیمهای پیاپی یک مش چندضلعی و سطح رندرشده. (تصاویر با اجازهٔ Caltech Multi-Res Modeling Group)
با تقسیم بیشتر مش، هر مرحله سطح نرمتری تولید میکند.
برخی مسائل دشوار را پوشش ندادهایم؛ برای مثال ساختارهای دادهای لازم برای اینکه هنگام درج رأسها، یالهای مشترک نتیجهای سازگار داشته باشند. منابع بخش «مطالعهٔ پیشنهادی» میتوانند نقطهٔ شروع مناسبی برای بررسی این جزئیات باشند.
۱۰.۱۳ تولید مش از داده
در همهٔ مثالهای قبلی فرض کردیم موقعیت دادهها در گرههای یک شبکهٔ مستطیلی یا شاید در گرههای یک گراف عمومی داده شده است. اما در بسیاری از کاربردها، مجموعهای از مکانها در اختیار داریم که میدانیم از یک سطح آمدهاند، ولی خود مکانها فاقد ساختارند. بنابراین فهرستی از مکانها داریم، بدون اینکه بدانیم کدام نقاط به یکدیگر نزدیکاند.
شکل ۱۰.۴۷ — دادههای ارتفاع.
شکل ۱۰.۴۸ — دادههای ارتفاع تصویرشده روی صفحهٔ (y=0).
۱۰.۱۳.۱ بازنگری میدانهای ارتفاع
یک نمونهٔ شکلگیری چنین دادهای در توپوگرافی رخ میدهد؛ جایی که ممکن است از هواپیما یا ماهواره ارتفاع نقاط تصادفی روی زمین اندازهگیری شود. در فصل ۴ میدانهای ارتفاع را بررسی کردیم، اما در آنجا فرض میشد اندازهگیریها روی یک شبکهٔ منظم انجام شدهاند و (y=0) سطح زمین را نشان میدهد. در نتیجه دادههای ارتفاع به شکل (y_{ij}) بودند و همه را میشد در یک ماتریس ذخیره کرد.
در اینجا دادهها در مکانهای تصادفی و بدون ساختار بهدست میآیند؛ بنابراین نقطهٔ شروع مجموعهای از مقادیر ({x_i,y_i,z_i}) است. مثال توپوگرافی مقداری ساختار دارد: میدانیم همهٔ نقاط روی یک سطح واحد هستند و هیچ دو نقطهای نمیتوانند (x_i) و (z_i) یکسان داشته باشند.
شکل ۱۰.۴۷ مجموعهای از نقاط را نشان میدهد که همگی بالای صفحهٔ (y=0) قرار دارند. این نقاط را میتوان مانند شکل ۱۰.۴۸ روی صفحهٔ (y=0) تصویر کرد. به دنبال الگوریتمی هستیم که این نقاط را به یک مش مثلثی متصل کند، مانند شکل ۱۰.۴۹. سپس مش روی صفحه را میتوان دوباره به بالا تصویر کرد تا دادههای اصلی با مثلثها به هم متصل شوند. رندر این مثلثهای سهبعدی تقریبی از سطحی میدهد که دادهها از آن آمدهاند. شکل ۱۰.۵۰ این مش را نشان میدهد.
در بخش بعد بررسی میکنیم چگونه میتوان از مجموعهای از نقاط روی صفحه، یک مش مثلثی بهدست آورد.
۱۰.۱۳.۲ مثلثبندی Delaunay
برای یک مجموعه نقطه روی صفحه، روشهای بسیاری برای تشکیل مش مثلثی با استفاده از همهٔ نقاط بهعنوان رأس وجود دارد. حتی چهار رأسی که یک چهارضلعی محدب را مشخص میکنند، بسته به انتخاب قطر، به دو روش میتوانند یک مش دو-مثلثی بسازند.
شکل ۱۰.۴۹ — مش مثلثی.
شکل ۱۰.۵۰ — مش سهبعدی.
شکل ۱۰.۵۱ — دو روش تقسیم یک چهارضلعی.
برای مشی با (n) رأس، (n-2) مثلث خواهیم داشت، اما روشهای بسیاری برای مثلثبندی آن وجود دارد. از دید گرافیکی، همهٔ مشهایی که از یک مجموعه رأس ساخته میشوند همارز نیستند. دو روش مثلثبندی چهار نقطهٔ شکل ۱۰.۵۱ را در نظر بگیرید. چون میخواهیم هیچ یالی با یال دیگر تقاطع نداشته باشد، چهار یال سیاه باید در مش حضور داشته باشند؛ این یالها پوستهٔ محدب چهار نقطه را تشکیل میدهند. بنابراین تنها انتخاب ما قطر چهارضلعی است.
در شکل ۱۰.۵۱(الف)، قطر دو مثلث بلند و باریک میسازد، در حالی که قطر شکل ۱۰.۵۱(ب) دو مثلث متعادلتر تولید میکند. حالت دوم ترجیح داده میشود، زیرا مثلثهای بلند و باریک معمولاً بد رندر میشوند و در اثر درونیابی ویژگیهای رأسها آرتیفکت ایجاد میکنند.
بهطور کلی هرچه یک مثلث به مثلث متساویالاضلاع نزدیکتر باشد، برای رندر مناسبتر است. به زبان ریاضی، بهترین مثلثها بزرگترین کمینهٔ زاویهٔ داخلی را دارند. اگر دو مش مثلثی حاصل از یک مجموعه نقطه را مقایسه کنیم، مش بهتر آن است که کمینهٔ زاویهٔ داخلی در میان همهٔ مثلثهایش بزرگتر باشد. ممکن است یافتن چنین مشی برای تعداد زیاد مثلث دشوار به نظر برسد، اما میتوان مسئله را به روشی حل کرد که به بهترین کمینهٔ زاویه منجر شود.
شکل ۱۰.۵۲ — دایرههای تعیینشده توسط مثلثبندیهای ممکن.
چند رأس روی صفحه را که قرار است بخشی از مش باشند در نظر بگیرید (شکل ۱۰.۵۲). با تمرکز روی رأس (v)، به نظر میرسد یکی از دو مثلث (a,v,c) یا (v,c,b) باید در مش باشد. به یاد آورید که سه نقطه روی صفحه یک دایرهٔ یکتا را تعیین میکنند که از هر سه عبور میکند. دایرهٔ ساختهشده از (a,v,c) نقطهٔ دیگری را درون خود ندارد، در حالی که دایرهٔ (v,c,b) نقطهای دیگر را در بر میگیرد. همچنین مثلث (a,v,c) کمینهٔ زاویهای کوچکتر از مثلث (v,c,b) دارد. چون این دو مثلث یک یال مشترک دارند، تنها یکی از آنها را میتوان در مش بهکار برد.
این مشاهدات راهبردی به نام Delaunay triangulation (مثلثبندی دلانی) را پیشنهاد میکنند. برای مجموعهای از (n) نقطه روی صفحه، مثلثبندی Delaunay ویژگیهای زیر را دارد و هر یک از آنها بهتنهایی برای تعریف این مثلثبندی کافی است:
- برای هر مثلث در مثلثبندی Delaunay، دایرهای که از سه رأس آن میگذرد هیچ رأس دیگری را در داخل خود ندارد.
- برای هر یال در مثلثبندی Delaunay، هیچ دایرهای که از دو انتهای آن یال بگذرد و درون خود یک رأس دیگر داشته باشد وجود ندارد.
- اگر مجموعهٔ زاویههای همهٔ مثلثهای یک مثلثبندی را در نظر بگیریم، مثلثبندی Delaunay بزرگترین مقدار برای کوچکترین زاویه را دارد.
اثبات این ویژگیها در منابع پیشنهادی پایان فصل آمده است. ویژگی سوم تضمین میکند این مثلثبندی برای گرافیک رایانهای مناسب باشد. دو ویژگی نخست نیز مستقیماً از روش ساخت آن ناشی میشوند.
ابتدا سه رأس اضافه میکنیم بهگونهای که همهٔ نقاط مجموعه داخل مثلث حاصل از این سه رأس قرار گیرند، مانند شکل ۱۰.۵۳. در پایان میتوان این رأسهای اضافی و یالهایی را که آنها را به نقاط دیگر متصل میکنند حذف کرد. سپس یک رأس (v) را بهصورت تصادفی از دادهها انتخاب و به سه رأس افزودهشده متصل میکنیم؛ سه مثلث شکل ۱۰.۵۴ ساخته میشود. هنوز نیازی به آزمون نداریم، زیرا هیچ دایرهای که با سه رأس از این چهار رأس تعیین شود نمیتواند رأس چهارم را درون خود داشته باشد.
بعد یک رأس (u) را بهصورت تصادفی از رأسهای باقیمانده انتخاب میکنیم. شکل ۱۰.۵۵ نشان میدهد این رأس داخل مثلث (a,v,c) قرار دارد و سه مثلثی که ایجاد میکند در ابتدا مشکلی ندارند. با این حال، یال میان (a) و (v) قطری از چهارضلعی (a,u,v,b) است و دایرهای که از (a,u,v) میگذرد، (b) را درون خود دارد. پس استفاده از این یال معیار Delaunay را نقض میکند.
شکل ۱۰.۵۳ — آغاز یک مثلثبندی Delaunay.
شکل ۱۰.۵۴ — مثلثبندی پس از افزودن نخستین نقطهٔ داده.
راهحل ساده است: قطر دیگر چهارضلعی را انتخاب میکنیم و یال میان (a) و (v) را با یالی میان (u) و (b) جایگزین میکنیم. این عملیات flipping (برگرداندن یال) نام دارد. مش جزئی حاصل در شکل ۱۰.۵۶ نشان داده شده است. اکنون دایرهٔ عبوری از (u,v,b) هیچ رأس دیگری را درون خود ندارد و همین موضوع برای دایرههای متناظر با سایر مثلثها نیز برقرار است؛ بنابراین برای زیرمجموعهٔ فعلی نقاط یک مثلثبندی Delaunay داریم.
فرایند را با افزودن رأس تصادفی دیگری از مجموعهٔ اولیه و انجام flipping در صورت نیاز ادامه میدهیم. در حالت کلی فقط برگرداندن یک یال متناظر با رأسی که تازه اضافه شده کافی نیست. برگرداندن یک یال ممکن است نیاز به برگرداندن یالهای دیگری ایجاد کند؛ بنابراین بهتر است فرایند را بازگشتی توصیف کنیم. چون هر flipping بهبود ایجاد میکند، برای هر رأس افزودهشده فرایند خاتمه مییابد. وقتی همهٔ رأسها اضافه شدند، سه رأس اولیهٔ کمکی و همهٔ یالهای متصل به آنها را حذف میکنیم. پیچیدگی متوسط این مثلثبندی (O(n\log n)) است.
روش ما میتواند مشکلاتی داشته باشد، زیرا مش را روی یک صفحه میسازیم و سپس آن را به نقاط دادهٔ اصلی برمیگردانیم. مثلثی که روی صفحه زاویههای تقریباً برابر دارد ممکن است پس از اتصال رأسهای سهبعدی متناظر، دیگر چنین هندسهٔ مناسبی نداشته باشد.
شکل ۱۰.۵۵ — افزودن رأسی که به flipping نیاز دارد.
شکل ۱۰.۵۶ — مش پس از flipping.
یک راهحل احتمالی آن است که راهبرد مشابه را مستقیماً روی دادههای سهبعدی اعمال کنیم، نه اینکه ابتدا آنها را روی صفحه تصویر کنیم. هر چهار نقطه یک کرهٔ یکتا را تعیین میکنند که از هر چهار عبور میکند. بنابراین میتوان مثلثبندی Delaunay سهبعدی را به شکلی تعریف کرد که هیچ نقطهٔ دادهٔ دیگری داخل آن کره قرار نگیرد و از چهار نقطه برای تعریف یک چهاروجهی استفاده شود. متأسفانه تعیین چنین تقسیمبندی فضایی بهمراتب پرهزینهتر از مثلثبندی Delaunay روی صفحه است.
۱۰.۱۳.۳ ابرهای نقطهای
مثلثبندی Delaunay بر این فرض متکی بود که دادههای ما «دو و نیمبعدی» هستند؛ یعنی میدانستیم از یک سطح واحد آمدهاند و میتوان آنها را از تصویرشان روی یک صفحه بازیابی کرد.
در بسیاری از وضعیتها، دادهها کاملاً بدون ساختارند و اغلب مجموعهٔ داده بسیار بزرگ است. برای مثال اسکنرهای لیزری میتوانند در مدت کوتاهی دهها میلیون نقطه تولید کنند. چنین مجموعههایی point cloud (ابر نقطهای) نامیده میشوند. اغلب این دادهها مستقیماً با primitiveهای نقطهای نمایش داده میشوند. از آنجا که در OpenGL میتوان نقاط را همانند یک سطح سایهزنی کرد، تراکم بالای نقاط سایهخورده میتواند ساختار سهبعدی را بهخوبی نشان دهد؛ بهویژه اگر دوربین بهصورت تعاملی قابل حرکت باشد.
جمعبندی و نکتهها
یک بار دیگر تنها سطح موضوعی عمیق و مهم را خراشیدهایم. همچنان تمرکز ما روی کارهایی بوده است که با یک سامانهٔ گرافیکی و API استانداردی مانند OpenGL میتوان انجام داد. از این دیدگاه، منحنیها و سطحهای پارامتری Bézier مزایای بزرگی دارند. فرم پارامتری مقاوم و برای استفادهٔ تعاملی آسان است، زیرا دادههای موردنیاز نقاطی هستند که میتوان آنها را بهصورت تعاملی وارد و دستکاری کرد. الگوریتم تقسیمبندی منحنیها و سطحهای Bézier نیز اجازه میدهد اشیای حاصل را با هر دقت دلخواه رندر کنیم.
دیدیم که هرچند رندر سطحهای Bézier آسان است، اسپلاینها میتوانند نرمی و کنترل بیشتری فراهم کنند. منابع پیشنهادی پایان فصل گونههای متعدد اسپلاین مورد استفاده در جامعهٔ CAD را بررسی میکنند.
سطحهای quadric در ray tracerها بسیار پرکاربردند، زیرا یافتن نقطهٔ تقاطع پرتو و quadric فقط به حل یک معادلهٔ اسکالر درجهٔ دوم نیاز دارد. حتی تشخیص اینکه نقطهٔ برخورد یک پرتو با صفحهٔ یک چندضلعی تخت داخل خود چندضلعی قرار دارد یا نه، میتواند دشوارتر از حل تقاطع با quadric باشد. ازاینرو بسیاری از ray tracerها تنها صفحههای نامتناهی، quadricها و شاید چندضلعیهای محدب را مجاز میدانند.
سطحهای تقسیمبندیشونده به دو دلیل اهمیت روزافزونی پیدا کردهاند. نخست، چون سختافزارهای عمومی امروز چندضلعیها را با نرخ بسیار بالا رندر میکنند، اغلب میتوان با تعداد زیادی چندضلعی به نرمی دلخواه رسید و این روش حتی ممکن است از رندر تعداد کمتری وصلهٔ سطح سریعتر باشد. البته اگر در سختافزار آینده رندر سطحهای منحنی مستقیماً در rasterizer قرار گیرد، این مزیت میتواند تغییر کند. دوم، چون سطح تقسیمبندیشونده را میتوان در هر سطح جزئیات دلخواه رندر کرد، هنگامی که سطح در تصویر به ناحیهٔ کوچکی نگاشت میشود نیازی نیست نسخهٔ بسیار ریزتقسیمشدهٔ آن را رندر کنیم.
مطالعهٔ پیشنهادی
کتاب Farin [Far88] مقدمهای عالی بر منحنیها و سطحها ارائه میکند. پیشگفتار جالبی نیز دارد که در آن Bézier دربارهٔ کشف تقریباً همزمان سطحهایی که امروز نام او را دارند توسط خودش و de Casteljau صحبت میکند. متأسفانه کار de Casteljau در گزارشهای فنی منتشرنشده توصیف شده بود و به همین دلیل تا سالهای اخیر اعتبار شایستهٔ کارش را دریافت نکرد. کتابهایی مانند Rogers [Rog90]، Foley [Fol90]، Bartels [Bar87] و Watt [Wat00] نیز این حوزه را بررسی میکنند.
منابع یادشده بسیاری از فرمهای دیگر اسپلاین را نیز پوشش میدهند. برای مقدمهای بر NURBS به Rogers [Rog00] مراجعه کنید. اسپلاینهای Catmull-Rom در [Cat75] پیشنهاد شدند.
کتاب Faux [Fau80] رویکرد مستقل از دستگاه مختصات به منحنیها و سطحها و چارچوب Frenet را بررسی میکند.
اگرچه کتاب ویرایششده توسط Glassner [Gla89] عمدتاً به ray tracing میپردازد، بخش نوشتهشده توسط Haines مطالب قابل توجهی دربارهٔ کار با quadricها و سایر سطحهای جبری دارد.
در سالهای اخیر فعالیت پژوهشی زیادی روی منحنیها و سطحهای تقسیمبندیشونده انجام شده است. برای برخی کارهای بنیادی این حوزه به [Che95]، [Deb96]، [Gor96]، [Lev96]، [Sei96] و [Tor96] مراجعه کنید. توسعهٔ این فصل از [War04] پیروی میکند. تقسیمبندی Catmull-Clark در [Cat78] پیشنهاد شد؛ [War03] و [Sta03] را نیز ببینید. مثلثبندی Delaunay در بیشتر کتابهای هندسهٔ محاسباتی پوشش داده میشود؛ [deB08] را ببینید.
تمرینها
۱۰.۱ یک سطح جبری (f(x,y,z)=0) را در نظر بگیرید که هر جملهٔ (f) میتواند توانهایی از (x)، (y) و (z) تا درجهٔ (m) داشته باشد. (f) حداکثر چند جمله میتواند داشته باشد؟
۱۰.۲ معادلات صریح (y=f(x)) و (z=g(x)) را در نظر بگیرید. این معادلات چه نوع منحنیهایی را توصیف میکنند؟
۱۰.۳ فرض کنید چندجملهای
p(u)=\sum_{k=0}^{n}c_ku^k
را دارید. چندجملهای
q(v)=\sum_{k=0}^{n}d_kv^k
را پیدا کنید بهگونهای که برای هر نقطه از (p) در بازهٔ ((a,b))، نقطهای با (0\le v\le1) وجود داشته باشد که (p(u)=q(v)).
۱۰.۴ نشان دهید تا زمانی که چهار نقطهٔ کنترل منحنی درونیاب مکعبی در مقادیر یکتای پارامتر (u) تعریف شوند، ماتریس هندسی درونیابی همیشه وجود دارد.
۱۰.۵ نشان دهید در بازهٔ ((0,1))، چندجملهایهای Bernstein باید کوچکتر از ۱ باشند.
۱۰.۶ پیوستگی (C^2) اسپلاین مکعبی را بررسی و تأیید کنید.
۱۰.۷ در بخش ۱۰.۹ نشان دادیم میتوان با انتخاب مجموعهٔ مناسب نقاط کنترل ــ یا معادل آن، پوستهٔ محدب مناسب ــ یک چندجملهای مکعبی را بهصورت چندجملهای Bézier مکعبی نوشت. با استفاده از این حقیقت نشان دهید چگونه میتوان یک منحنی درونیاب را با رندرکنندهٔ Bézier فراهمشده توسط OpenGL رندر کرد.
۱۰.۸ یک نمایش مختصات همگن برای quadricها پیدا کنید.
۱۰.۹ فرض کنید وصلههای Bézier را با تقسیمبندی تطبیقی رندر میکنیم، بهگونهای که هر وصله بتواند تعداد متفاوتی بار تقسیم شود. آیا پیوستگی در امتداد لبهٔ وصلهها حفظ میشود؟ پاسخ را توضیح دهید.
۱۰.۱۰ برنامهای در OpenGL بنویسید که مجموعهای از نقاط کنترل را ورودی بگیرد و منحنیهای درونیاب، B-Spline و Bézier متناظر با این دادهها را تولید کند.
۱۰.۱۱ فرض کنید برای توصیف مسیر زمانی حرکت یک شیء در پویانمایی از مجموعهای منحنی اسپلاین استفاده میکنید. در این وضعیت تفاوت میان پیوستگی (G^1) و (C^1) را چگونه میتوان مشاهده کرد؟
۱۰.۱۲ برنامهای بنویسید که از تعداد دلخواهی نقطه که بهصورت تعاملی وارد میشوند، یک چندجملهای Bézier مکعبی تولید کند. کاربر باید بتواند نقاط کنترل را نیز بهصورت تعاملی دستکاری کند.
۱۰.۱۳ آزمونی ساده برای تختبودن یک وصلهٔ سطح Bézier استخراج کنید.
۱۰.۱۴ B-Spline گویای درجهٔ دومِ باز با گرههای ({0,0,0,0,1,1,1,1}) و وزنهای (w_0=w_2=1) و (w_1=w) را استخراج کنید.
۱۰.۱۵ با استفاده از نتیجهٔ تمرین ۱۰.۱۴ نشان دهید اگر
w=\frac{1-r}{r},\qquad 0\le r\le1,
باشد، همهٔ مقاطع مخروطی را بهدست میآورید. راهنما: حالتهای (r<1/2) و (r>1/2) را در نظر بگیرید.
۱۰.۱۶ صفرهای تابعهای blending هرمیت را پیدا کنید. چرا این صفرها نشان میدهند منحنی Hermite در بازهٔ ((0,1)) نرم است؟
۱۰.۱۷ چه رابطهای میان دادههای نقاط کنترل یک وصلهٔ Hermite و مشتقها در گوشههای وصله وجود دارد؟
۱۰.۱۸ برای صفحهنمایشی با وضوح (1024\times1280)، حداکثر چند تقسیمبندی برای رندر یک سطح چندجملهای مکعبی لازم است؟
۱۰.۱۹ فرض کنید سه نقطهٔ (P_0,P_1,P_2) دارید. ابتدا نقاط متوالی را با پارهخطهای پارامتری متصل کنید که برای هر پارهخط (u) از ۰ تا ۱ تغییر کند. سپس میان جفتهای متوالی پارهخطها بهصورت خطی درونیابی کنید؛ یعنی نقاط متناظر با مقدار یکسان (u) را با پارهخط به هم وصل کنید و همان مقدار (u) را برای بهدستآوردن نقطهای روی پارهخط جدید بهکار ببرید. منحنی حاصل از این فرایند را چگونه میتوان توصیف کرد؟
۱۰.۲۰ تمرین ۱۰.۱۹ را برای چهار نقطه گسترش دهید. ابتدا میان سه منحنی ساختهشده طبق آن تمرین بهصورت خطی درونیابی کنید و سپس میان دو منحنی جدید حاصل نیز درونیابی خطی انجام دهید. منحنی نهایی تعیینشده توسط چهار نقطه را توصیف کنید.
۱۰.۲۱ اگر در منحنی Bézier مکعبی مقادیر نقاط کنترل (P_0) و (P_1) یکسان باشند، چه اتفاقی میافتد؟
۱۰.۲۲ فرض کنید یک وصلهٔ سطح Bézier را ابتدا در جهت (u) تقسیم میکنیم. سپس در جهت (v)، فقط یکی از دو وصلهٔ ایجادشده را تقسیم میکنیم. نشان دهید چگونه این فرایند میتواند در سطح حاصل یک شکاف ایجاد کند. راهحلی ساده برای این مشکل پیدا کنید.
۱۰.۲۳ برنامهای برای انجام تقسیمبندی مشهای مثلثی یا چهارضلعی بنویسید. پس از آنکه تقسیمبندی بهدرستی کار کرد، مرحلهٔ میانگینگیری را اضافه کنید تا سطح نرمتری ساخته شود.
۱۰.۲۴ چندجملهایهای blending اسپلاین Catmull-Rom را پیدا کنید و صفرهای آنها را بهدست آورید.
۱۰.۲۵ ماتریسی را پیدا کنید که دادههای اسپلاین Catmull-Rom را به دادهٔ نقاط کنترل یک منحنی Bézier تبدیل کند، بهگونهای که هر دو نمایش همان منحنی را تولید کنند.