B-Spline عمومی، NURBS، رندر منحنیها و سطحهای جبری
شکل ۱۰.۲۵ — تابع پایهٔ اسپلاین.
شکل ۱۰.۲۶ — تابع تقریبزننده روی یک بازه.
شکل ۱۰.۲۷ — وصلهٔ سطح اسپلاین.
برای یک وصلهٔ سطح B-Spline داریم:
p(u,v)=\sum_{i=0}^{3}\sum_{j=0}^{3} b_i(u)b_j(v)p_{ij}.
این عبارت همان فرم کلی وصلههای سطحی دیگر ما را دارد، اما همانطور که در شکل ۱۰.۲۷ دیده میشود، از وصله فقط در ناحیهٔ مرکزی استفاده میکنیم و در مقایسه با وصلهٔ Bézier باید تقریباً نه برابر کار انجام دهیم. با این حال، به دلیل بهارثبردن ویژگی پوستهٔ محدب و پیوستگی بیشتر لبهها از منحنیهای B-Spline، وصلهٔ B-Spline بهمراتب نرمتر از وصلهٔ Bézier ساختهشده از همان دادههاست.
۱۰.۸ B-Splineهای عمومی
فرض کنید مجموعهای از نقاط کنترل (p_0,\ldots,p_m) داریم. مسئلهٔ عمومی تقریب، یافتن تابع
p(u)=[x(u)\;y(u)\;z(u)]^T
است که روی بازهای تعریف شده، نرم باشد و به معنایی مناسب به نقاط کنترل نزدیک بماند.
فرض کنید مجموعهای از مقادیر ({u_k}) داشته باشیم که گره (knot) نامیده میشوند و
u_{\min}=u_0\le u_1\le\cdots\le u_n=u_{\max}.
دنبالهٔ (u_0,u_1,\ldots,u_n) را آرایهٔ گرهها مینامیم. در اسپلاینها، تابع (p(u)) میان هر دو گره یک چندجملهای درجهٔ (d) است:
p(u)=\sum_{j=0}^{d}c_{jk}u^j,\qquad u_k<u<u_{k+1}.
پس برای مشخصکردن یک اسپلاین درجهٔ (d)، باید (n(d+1)) ضریب سهبعدی (c_{jk}) را تعیین کنیم. شرطهای لازم از اعمال الزامهای مختلف پیوستگی در گرهها و شرطهای درونیابی در نقاط کنترل بهدست میآیند.
برای مثال، اگر (d=3) باشد، در هر بازه یک چندجملهای مکعبی داریم و برای (n) بازه باید (4n) شرط مشخص شود. (n-1) گرهٔ داخلی وجود دارد. اگر در گرهها پیوستگی (C^2) بخواهیم، (3n-3) شرط بهدست میآید. اگر افزون بر آن بخواهیم (n+1) نقطهٔ کنترل درونیابی شوند، در مجموع (4n-2) شرط داریم. دو شرط باقیمانده را میتوان به روشهای مختلف انتخاب کرد؛ مثلاً شیب دو انتهای منحنی را ثابت کرد. با این حال، چنین اسپلاینی سراسری است: باید دستگاهی از (4n) معادله با (4n) مجهول حل شود و هر ضریب به همهٔ نقاط کنترل وابسته خواهد بود. بنابراین، هرچند منحنی حاصل نرم است و نقاط کنترل را درونیابی میکند، برای گرافیک رایانهای و CAD انتخاب مناسبی نیست.
۱۰.۸.۱ B-Splineهای تعریفشده بهصورت بازگشتی
در B-Spline، اسپلاین بر حسب مجموعهای از تابعهای پایه یا آمیختن تعریف میشود که هرکدام فقط روی ناحیهای محدود، شامل چند گره، ناصفر هستند. بنابراین مینویسیم:
p(u)=\sum_{i=0}^{m}B_i^d(u)p_i,
که در آن هر (B_i^d(u))، بهجز در گرهها، چندجملهای درجهٔ (d) است و بیرون از بازهٔ پشتیبانی خود صفر میشود. نام B-Spline از عبارت basis spline یا «اسپلاین پایه» گرفته شده است، زیرا مجموعهٔ تابعهای ({B_i^d(u)}) برای دنبالهٔ گرهها و درجهٔ انتخابشده یک پایه تشکیل میدهد.
از میان روشهای متعدد تعریف اسپلاینهای پایه، بازگشت Cox-de Boor اهمیت ویژهای دارد:
B_k^0(u)=
\begin{cases}
1,&u_k\le u\le u_{k+1},\0,&\text{در غیر این صورت.}
\end{cases}
پاورقی ۹. بیشتر پژوهشگران این دنباله را knot vector مینامند، اما در این کتاب واژهٔ «بردار» فقط برای پارهخطهای جهتدار بهکار میرود؛ ازاینرو اصطلاح «آرایهٔ گرهها» استفاده شده است.
پاورقی ۱۰. این فرمول با نام بازگشت de Casteljau نیز شناخته میشود.
شکل ۱۰.۲۸ — سه تابع پایهٔ نخست.
رابطهٔ بازگشتی برای درجههای بالاتر چنین است:
B_k^d(u)=
\frac{u-u_k}{u_{k+d}-u_k}B_k^{d-1}(u)
+
\frac{u_{k+d}-u}{u_{k+d+1}-u_{k+1}}B_{k+1}^{d-1}(u).
هر تابع مجموعهٔ نخست، (B_k^0)، در یک بازه ثابت و در همهٔ جاهای دیگر صفر است؛ هر تابع مجموعهٔ دوم، (B_k^1)، در دو بازه خطی و در خارج آنها صفر است؛ هر (B_k^2) روی سه بازه یک تابع درجهٔ دوم است و همین الگو ادامه مییابد (شکل ۱۰.۲۸). بهطور کلی (B_k^d) روی (d+1) بازهٔ میان (u_k) و (u_{k+d+1}) ناصفر است و در هر یک از این بازهها چندجملهای درجهٔ (d) است. در گرهها پیوستگی (C^{d-1}) داریم.
ویژگی پوستهٔ محدب برقرار است، زیرا
\sum_{i=0}^{m}B_{i,d}(u)=1
و
1\ge B_i^d(u)\ge 0
در بازهٔ (u_{\min}\le u\le u_{\max}). از آنجا که هر (B_i^d) تنها در (d+1) بازه ناصفر است، هر نقطهٔ کنترل نیز فقط بر (d+1) بازه اثر میگذارد و هر نقطه از منحنی حاصل داخل پوستهٔ محدبی قرار میگیرد که همین (d+1) نقطهٔ کنترل تعریف کردهاند.
با بررسی دقیق فرمول Cox-de Boor میبینیم که هر مرحلهٔ بازگشت، یک درونیابی خطی میان تابعهای تولیدشده در مرحلهٔ قبل است. درونیابی خطی چندجملهایهای درجهٔ (k)، چندجملهایهای درجهٔ (k+1) تولید میکند.
مجموعهای از تابعهای پایهٔ اسپلاین با درجهٔ مطلوب و آرایهٔ گرهها تعریف میشود. برای مشخصکردن اسپلاین ظاهراً به (d-1) مقدار گرهٔ «اضافی» نیاز داریم، زیرا بازگشت برای تعریف اسپلاینهای بازهٔ (u_0) تا (u_{n+1}) به مقادیر (u_0) تا (u_{n+d}) نیاز دارد. این مقادیر اضافه با شرطهای ابتدا و انتهای کل اسپلاین تعیین میشوند.
تا اینجا بهجز (u_k\le u_{k+1}) هیچ شرط دیگری برای مقدار گرهها نگذاشتهایم. اگر هر عبارت (0/0) که هنگام ارزیابی بازگشت پدید میآید را برابر ۱ تعریف کنیم، میتوانیم گرههای تکراری یا چندگانه داشته باشیم. اگر گرهها با فاصلههای مساوی قرار گیرند، اسپلاین یکنواخت است. انعطاف بیشتر زمانی حاصل میشود که هم فاصلههای غیریکنواخت و هم گرههای تکراری ((u_k=u_{k+1})) مجاز باشند. در ادامه چند حالت را بررسی میکنیم.
شکل ۱۰.۲۹ — B-Spline یکنواخت.
۱۰.۸.۲ اسپلاینهای یکنواخت
دنبالهٔ یکنواخت گرهها ({0,1,2,\ldots,n}) را در نظر بگیرید. B-Spline مکعبی بخش ۱۰.۷ را میتوان از فرمول Cox-de Boor با گرههای همفاصله بهدست آورد. با شمارهگذاری همان بخش ــ که نسبت به اندیسگذاری Cox-de Boor جابهجا شده است ــ میان گرههای (k) و (k+1) از نقاط کنترل (p_{k-1},p_k,p_{k+1},p_{k+2}) استفاده میکنیم. در نتیجه، منحنی فقط روی بازهٔ (u=1) تا (u=n-1) تعریف میشود. برای دادههای شکل ۱۰.۲۹، منحنی تعریفشده کل گرهها را پوشش نمیدهد.
شکل ۱۰.۳۰ — B-Spline یکنواخت دورهای.
در بعضی وضعیتها، مانند شکل ۱۰.۳۰، میتوان از ماهیت دورهای دادههای نقاط کنترل استفاده کرد و اسپلاین را روی کل دنبالهٔ گرهها تعریف کرد. در B-Splineهای یکنواخت دورهای، هر تابع پایهٔ اسپلاین نسخهای انتقالیافته از یک تابع واحد است.
۱۰.۸.۳ B-Splineهای غیریکنواخت
گرههای تکراری باعث میشوند اسپلاین به نقطهٔ کنترل متناظر با گره نزدیکتر شود. اگر یک گرهٔ انتهایی دارای تکرارپذیری (d+1) باشد، B-Spline درجهٔ (d) ناچار است آن نقطه را درونیابی کند. بنابراین، یک راه حل برای مشکل کمبود دادهٔ کافی در دو انتها آن است که گرههای انتهایی تکرار شوند تا درونیابی انتهاها اجباری شود و در بخشهای دیگر از گرههای یکنواخت استفاده کنیم. چنین اسپلاینهایی اسپلاین باز نامیده میشوند.
برای B-Splineهای مکعبی معمولاً دنبالهٔ
\{0,0,0,0,1,2,\ldots,n-1,n,n,n,n\}
بهکار میرود. دنبالهٔ
\{0,0,0,0,1,1,1,1\}
از این نظر جالب است که B-Spline مکعبی در این حالت دقیقاً به منحنی Bézier مکعبی تبدیل میشود. در حالت کلی میتوان گرههای داخلی را نیز تکرار کرد و فاصلهٔ میان گرهها را به هر شکل دلخواه انتخاب کرد.
۱۰.۸.۴ NURBS
در توسعهٔ B-Splineها فرض کردیم (p(u)) آرایهٔ ([x(u);y(u);z(u)]^T) است. در دو بعد میتوانستیم بهسادگی ([x(u);y(u)]^T) را جایگزین کنیم و همهٔ معادلات بدون تغییر باقی میماندند. در واقع، همین معادلات برای B-Splineهای چهاربعدی نیز برقرارند. نقطهٔ کنترل سهبعدی
p_i=[x_i\;y_i\;z_i]
را در نظر بگیرید.
نمایش مختصات همگن وزندار این نقطه برابر است با
q_i=w_i
\begin{bmatrix}
x_i\\y_i\\z_i\\1
\end{bmatrix}.
ایده آن است که با وزنهای (w_i) اهمیت یک نقطهٔ کنترل خاص را افزایش یا کاهش دهیم. میتوان از این نقاط وزندار برای تشکیل یک B-Spline چهاربعدی استفاده کرد. سه مؤلفهٔ نخست اسپلاین حاصل همان نمایش B-Spline نقاط وزندار هستند:
q(u)=
\begin{bmatrix}
x(u)\\y(u)\\z(u)
\end{bmatrix}
=
\sum_{i=0}^{n}B_{i,d}(u)w_i p_i.
مؤلفهٔ (w)، چندجملهای اسکالر B-Spline حاصل از مجموعهٔ وزنهاست:
w(u)=\sum_{i=0}^{n}B_{i,d}(u)w_i.
در مختصات همگن، مؤلفهٔ (w) لزوماً برابر ۱ نیست؛ بنابراین برای بهدستآوردن نقاط سهبعدی باید تقسیم پرسپکتیو انجام دهیم:
p(u)=\frac{1}{w(u)}q(u)=
\frac{\sum_{i=0}^{n}B_{i,d}(u)w_i p_i}
{\sum_{i=0}^{n}B_{i,d}(u)w_i}.
اکنون هر مؤلفهٔ (p(u)) تابعی گویا از (u) است و چون هیچ محدودیتی بر گرهها نگذاشتهایم، به یک منحنی NURBS (B-Spline گویای غیریکنواخت) رسیدهایم.
منحنیهای NURBS همهٔ ویژگیهای B-Splineهای سهبعدی، از جمله پوستهٔ محدب و پیوستگی، را حفظ میکنند. دو ویژگی دیگر نیز دارند که آنها را برای گرافیک رایانهای و CAD بسیار مهم میکند.
اگر یک تبدیل آفین را روی منحنی یا سطح B-Spline اعمال کنیم، همان تابعی را بهدست میآوریم که از ساخت B-Spline نقاط کنترلِ تبدیلشده حاصل میشود. از آنجا که تبدیلهای پرسپکتیو آفین نیستند، بیشتر اسپلاینها در مشاهدهٔ پرسپکتیو بهدرستی رفتار نمیکنند. اما تقسیم پرسپکتیوِ تعبیهشده در ساخت NURBS تضمین میکند که منحنی NURBS در نماهای پرسپکتیو بهدرستی تبدیل شود.
سطحهای درجهٔ دوم (quadric) معمولاً با فرمهای جبری ضمنی مشخص میشوند. اگر از اسپلاینهای غیرگویا استفاده کنیم، تنها میتوان این سطحها را تقریب زد. با این حال، میتوان نشان داد که quadricها حالت خاصی از منحنیهای NURBS درجهٔ دوم هستند؛ بنابراین میتوان یک روش مدلسازی واحد ــ یعنی NURBS ــ را برای بسیاری از منحنیها و سطحهای پرکاربرد بهکار برد (تمرینهای ۱۰.۱۴ و ۱۰.۱۵ را ببینید). لوح رنگی ۵ مشی را نشان میدهد که از یک سطح NURBS تولید شده است.
سطحی که شیء لوح رنگی ۱ را میسازد با همین روش مدلسازی شده و OpenGL در نهایت مش حاصل را با چندضلعیها رندر میکند.
۱۰.۸.۵ اسپلاینهای Catmull-Rom
اگر شرط قرارگرفتن منحنیها و سطحها در پوستهٔ محدب دادهها را کنار بگذاریم، میتوان از دادهها برای ساخت انواع دیگری از اسپلاین استفاده کرد. یکی از پرکاربردترین آنها اسپلاین Catmull-Rom است.
چهار نقطهٔ کنترل (p_0,p_1,p_2,p_3) را که در استخراج منحنی Bézier استفاده کردیم دوباره در نظر بگیرید. این بار بهجای ساخت یک چندجملهای مکعبی که (p_0) و (p_1) را درونیابی کند، دو نقطهٔ میانی (p_1) و (p_2) را درونیابی میکنیم:
p(0)=p_1,
\qquad
p(1)=p_2.
بنابراین، همانند B-Spline، چندجملهای روی بازهای کوتاهتر تعریف میشود و هر بار که یک نقطهٔ کنترل جدید اضافه کنیم، منحنی جدیدی پیدا میکنیم.
شکل ۱۰.۳۱ — ساخت اسپلاین Catmull-Rom.
از نقاط (p_0) و (p_3) برای تقریب مماسها در دو انتهای قطعه استفاده میکنیم:
p'(0)\approx\frac{p_2-p_0}{2},
\qquad
p'(1)\approx\frac{p_3-p_1}{2}.
اکنون برای منحنی
p(u)=c_0+c_1u+c_2u^2+c_3u^3
چهار شرط داریم و معادلات زیر بهدست میآیند:
p_1=c_0,
p_2=c_0+c_1+c_2+c_3,
\frac{p_2-p_0}{2}=c_1,
\frac{p_3-p_1}{2}=c_1+2c_2+3c_3.
توجه کنید که وقتی (u) از ۰ تا ۱ تغییر میکند فقط از (p_1) به (p_2) میرویم؛ در نتیجه (p_0) و (p_2) در فضای پارامتر دو واحد از هم فاصله دارند و همین موضوع برای (p_1) و (p_3) نیز برقرار است. این چهار شرط تضمین میکنند که منحنیهای حاصل در نقاط کنترل هم خودشان و هم مشتق اولشان پیوسته باشند، هرچند دیگر ویژگی پوستهٔ محدب را نداریم.
حل چهار معادله میدهد:
p(u)=u^T M_R p,
که در آن (M_R) ماتریس هندسی Catmull-Rom است:
M_R=\frac12
\begin{bmatrix}
-1&3&-3&1\2&-5&4&-1\-1&0&1&0\0&2&0&0
\end{bmatrix}.
۱۰.۹ رندر منحنیها و سطحها
پس از مشخصکردن صحنهای شامل منحنیها و سطحها، باید روشی برای رندر آن پیدا کنیم. بسته به نوع نمایش، چند رویکرد وجود دارد. برای منحنیها و سطحهای صریح و پارامتری میتوان تابع را در تعداد کافی نقطه ارزیابی کرد و سپس با اشیای تخت استاندارد خود آن را تقریب زد. در این بخش تمرکز ما بر همین روش برای منحنیها و سطحهای چندجملهای پارامتری است.
برای سطحهای ضمنی میتوان نقاطی از شیء را محاسبه کرد که محل تقاطع پرتوهای عبوری از مرکز تصویرسازی و پیکسلها با شیء هستند. سپس از این نقاط برای تعریف قطعههای منحنی یا مشهایی استفاده کرد که مستقیماً قابل رندرند. با این حال، بهجز سطحهای درجهٔ دوم یا quadricها (بخش ۱۰.۱۱)، محاسبهٔ تقاطع مستلزم حل معادلات غیرخطی با درجهای چنان بالا است که برای محاسبهٔ بلادرنگ عملی نیست.
چندجملهای Bézier مکعبی را در نظر بگیرید:
b(u)=(1-u)^3p_0+3(1-u)^2up_1+3(1-u)u^2p_2+u^3p_3.
اگر بخواهیم آن را در (N) مقدار همفاصلهٔ (u) ارزیابی کنیم و نتایج را مانند مثالهای قبل در آرایهٔ points قرار دهیم، کد یک نمونهٔ دوبعدی میتواند به سادگی زیر باشد:
float d = 1.0/(N-1.0);
float u, uu;
for(int i=0; i<N; i++)
{
u = i*d;
uu = 1.0 - u;
for(int j=0; j<2; j++) points[i][j] = p[0][j]*uu*uu*uu
+ 3.0*p[1][j]*uu*uu*u
+ 3.0*p[2][j]*uu*u*u
+ p[3][j]*u*u*u;
}
دادهٔ نقاط کنترل در آرایهٔ p قرار دارد.
۱۰.۹.۱ روشهای ارزیابی چندجملهای
فرض کنید روی بازهٔ استاندارد خود نمایش زیر را داشته باشیم:
p(u)=\sum_{i=0}^{n}c_i u^i,
\qquad 0\le u\le1.
میتوان (p(u)) را در مجموعهای از مقادیر ({u_k}) ارزیابی کرد و با یک چندخطی یا GL_LINE_STRIP منحنی را تقریب زد. بهجای آنکه هر توان (u^k) را جداگانه محاسبه کنیم، جملهها را چنین گروهبندی میکنیم:
p(u)=c_0+u(c_1+u(c_2+u(\ldots+c_nu))).
این گروهبندی نشان میدهد برای ارزیابی هر (p(u_k)) فقط به (n) ضرب نیاز داریم. این الگوریتم روش Horner نامیده میشود. برای چندجملهای مکعبی معمول:
p(u)=c_0+u(c_1+u(c_2+uc_3)).
اگر نقاط ({u_i}) با فاصلهٔ یکنواخت قرار گرفته باشند، میتوان با روش تفاضلهای پیشرو مقدار (p(u_k)) را با (O(n)) جمع و بدون هیچ ضربی محاسبه کرد. تفاضلهای پیشرو بهطور بازگشتی تعریف میشوند:
\Delta^{(0)}p(u_k)=p(u_k),
\Delta^{(1)}p(u_k)=p(u_{k+1})-p(u_k),
\Delta^{(m+1)}p(u_k)=\Delta^{(m)}p(u_{k+1})-\Delta^{(m)}p(u_k).
اگر (u_{k+1}-u_k=h) ثابت باشد، میتوان نشان داد که اگر (p(u)) چندجملهای درجهٔ (n) باشد، (\Delta^{(n)}p(u_k)) برای همهٔ (k) ثابت است. این نتیجه راهبرد شکل ۱۰.۳۲ را برای چندجملهای مکعبی اسکالر
p(u)=1+3u+2u^2+u^3
پیشنهاد میکند.
شکل ۱۰.۳۲ — ساخت جدول تفاضل پیشرو.
جدول مقادیر نمونه:
| (t) |
0 |
1 |
2 |
3 |
4 |
5 |
| (p) |
1 |
7 |
23 |
55 |
109 |
191 |
| (\Delta^{(1)}p) |
6 |
16 |
32 |
54 |
82 |
— |
| (\Delta^{(2)}p) |
10 |
16 |
22 |
28 |
— |
— |
| (\Delta^{(3)}p) |
6 |
6 |
6 |
— |
— |
— |
شکل ۱۰.۳۳ — استفاده از جدول تفاضل پیشرو.
برای یافتن (\Delta^{(n)}p(u_0))، به نخستین (n+1) مقدار (p(u_k)) نیاز داریم. اما پس از بهدستآوردن (\Delta^{(n)}p(u_0))، میتوانیم این مقدار را در طول سطر کپی کنیم و، مطابق شکل ۱۰.۳۳، از پایین به بالا پیش برویم تا مقادیر متوالی (p(u_k)) را با رابطهٔ بازآراییشدهٔ زیر محاسبه کنیم:
\Delta^{(m-1)}p(u_{k+1})=
\Delta^{(m)}p(u_k)+\Delta^{(m-1)}p(u_k).
این روش کارآمد است، اما محدودیتهایی نیز دارد: فقط برای شبکهٔ یکنواخت قابل استفاده است و در برابر انباشتهشدن خطاهای عددی حساس است.
۱۰.۹.۲ تقسیمبندی بازگشتی چندجملهایهای Bézier
ظریفترین روش رندر، تقسیمبندی بازگشتی منحنی Bézier است. این روش بر ویژگی پوستهٔ محدب تکیه دارد و هرگز به ارزیابی صریح چندجملهای نیاز ندارد. فرض کنید یک چندجملهای Bézier مکعبی داریم؛ همین روش برای منحنیهای Bézier با درجهٔ بالاتر نیز قابل استفاده است. میدانیم منحنی باید داخل پوستهٔ محدب نقاط کنترل قرار گیرد.
میتوان منحنی را به دو چندجملهای جداگانهٔ (l(u)) و (r(u)) تقسیم کرد که هرکدام روی نیمی از بازهٔ اصلی معتبرند. چون چندجملهای اصلی مکعبی است، هر دو چندجملهای جدید نیز مکعبیاند. هرکدام روی نصف بازهٔ اصلی استفاده میشوند، بنابراین پارامتر (u) را برای (l) و (r) مقیاس میکنیم تا وقتی (u) در بازهٔ ((0,1)) تغییر میکند، (l(u)) نیمهٔ چپ (p(u)) و (r(u)) نیمهٔ راست آن را طی کند.
هر چندجملهای جدید چهار نقطهٔ کنترل دارد که هم چندجملهای را مشخص میکنند و هم پوستهٔ محدب آن را میسازند. این دو مجموعه را ({l_0,l_1,l_2,l_3}) و ({r_0,r_1,r_2,r_3}) و نقاط کنترل اصلی را ({p_0,p_1,p_2,p_3}) مینامیم. شکل ۱۰.۳۴ این نقاط و دو پوستهٔ محدب را نشان میدهد. پوستههای محدب (l) و (r) باید داخل پوستهٔ محدب (p) قرار گیرند؛ این نتیجه با نام ویژگی کاهش تغییرات (variation-diminishing property) منحنی Bézier شناخته میشود.
برای چندجملهای سمت چپ، میتوان تختبودن پوستهٔ محدب را با اندازهگیری فاصلهٔ (l_1) و (l_2) از پارهخط بین (l_0) و (l_3) آزمود. اگر این نقاط نزدیک به خط باشند، بهجای منحنی همان پارهخط را رسم میکنیم. اگر نزدیک نباشند، (l) را به دو نیمه تقسیم میکنیم و تختبودن دو پوستهٔ محدب جدید را میآزماییم. بنابراین یک الگوریتم بازگشتی داریم که هیچگاه نیازمند ارزیابی نقاط روی چندجملهای نیست. فقط باید مشخص کنیم ({l_0,l_1,l_2,l_3}) و ({r_0,r_1,r_2,r_3}) چگونه محاسبه میشوند. در ادامه پوستهٔ (l(u)) را پیدا میکنیم؛ محاسبه برای (r(u)) متقارن است.
شکل ۱۰.۳۴ — پوستههای محدب و نقاط کنترل.
از نمایش
p(u)=u^TM_B
\begin{bmatrix}
p_0\\p_1\\p_2\\p_3
\end{bmatrix}
با ماتریس
M_B=
\begin{bmatrix}
1&0&0&0\-3&3&0&0\3&-6&3&0\-1&3&-3&1
\end{bmatrix}
آغاز میکنیم.
چندجملهای (l(u)) باید (p(0)) و (p(1/2)) را درونیابی کند؛ بنابراین
l(0)=l_0=p_0,
l(1)=l_3=p\!\left(\frac12\right)
=\frac18(p_0+3p_1+3p_2+p_3).
در (u=0)، شیب (l) باید با شیب (p) منطبق باشد. اما چون پارامتر (p) فقط بازهٔ ((0,1/2)) را پوشش میدهد و (u) برای (l) در ((0,1)) تغییر میکند، بهطور ضمنی جایگذاری (\bar u=2u) انجام دادهایم. در نتیجه مشتقها با (d\bar u=2du) مرتبطاند و
l'(0)=3(l_1-l_0)=\frac32(p_1-p_0).
به همین ترتیب در نقطهٔ میانی:
l'(1)=3(l_3-l_2)
=\frac38(-p_0-p_1+p_2+p_3).
این چهار معادله را میتوان جبری حل کرد. راه دیگر آن است که با کمک شکل ۱۰.۳۵، پاسخ را بهصورت هندسی بسازیم. در آنجا پوستههای هر دو نیمهٔ منحنی ساخته میشوند.
شکل ۱۰.۳۵ — ساخت منحنیهای حاصل از تقسیمبندی.
مجموعههای نقاط کنترل سمت چپ و راست را همزمان میسازیم. ابتدا از شرط درونیابی داریم:
l_0=p_0,
\qquad
r_3=p_3.
با جایگذاری در چهار معادله میتوان بررسی کرد که شرط شیب در دو طرف میدهد:
l_1=\frac12(p_0+p_1),
r_2=\frac12(p_2+p_3).
نقاط داخلی از روابط زیر بهدست میآیند:
l_2=\frac12\left(l_1+\frac12(p_1+p_2)\right),
r_1=\frac12\left(r_2+\frac12(p_1+p_2)\right).
در نهایت، نقطهٔ میانی مشترک برابر است با
l_3=r_0=\frac12(l_2+r_1).
مزیت این صورتبندی آن است که هر دو مجموعهٔ نقاط کنترل را فقط با عملهای انتقال بیت ــ برای تقسیم بر ۲ ــ و جمع میتوان تعیین کرد. با این حال، یکی از مزایای رویکرد تقسیمبندی این است که میتواند تطبیقی باشد و در یک مرحلهٔ خاص رندر شاید فقط یکی از دو نیمه به تقسیم بیشتر نیاز داشته باشد. همچنین چون رندر منحنی لازم نیست تا مرحلهٔ رسترسازی خط لوله انجام شود و میتواند در مختصات صفحه یا پنجره صورت گیرد، تفکیکپذیری محدود نمایشگر سقفی طبیعی برای تعداد دفعات تقسیم پوستهٔ محدب ایجاد میکند (تمرین ۱۰.۱۸).
۱۰.۹.۳ رندر سایر منحنیهای چندجملهای با تقسیمبندی
همانطور که هر چندجملهای را میتوان یک چندجملهای Bézier دانست، با انتخاب مناسب نقاط کنترل میتوان همان چندجملهای را به صورت چندجملهای درونیاب، چندجملهای B-Spline یا هر فرم چندجملهای دیگری نیز نمایش داد. الگوریتم تقسیمبندی Bézier چنان کارآمد است که معمولاً بهتر است فرمهای دیگر منحنی را ابتدا به فرم Bézier تبدیل کنیم و سپس الگوریتم تقسیمبندی را بهکار ببریم.¹¹
الگوریتم تبدیل مستقیماً از صورتبندی منحنیها بهدست میآید. یک منحنی Bézier مکعبی را در نظر بگیرید. میتوان آن را با ماتریس Bézier، یعنی (M_B)، چنین نوشت:
p(u)=u^TM_Bp,
که در آن (p) ماتریس هندسی نقاط کنترل است. همان چندجملهای را میتوان به صورت
p(u)=u^TMq
نوشت که (M) ماتریس نوع دیگری از چندجملهای و (q) ماتریس نقاط کنترل آن نوع است. فرض میکنیم هر دو چندجملهای روی یک بازه تعریف شدهاند. اگر انتخاب کنیم
q=M^{-1}M_Bp,
دو چندجملهای یکسان خواهند بود.
برای تبدیل فرم درونیاب به Bézier، ماتریس کنترلکننده برابر است با
M_B^{-1}M_I=
\begin{bmatrix}
1&0&0&0\-\frac56&3&-\frac23&\frac13\\frac13&-\frac23&3&-\frac56\0&0&0&1
\end{bmatrix}.
برای تبدیل میان B-Spline مکعبی و منحنی Bézier مکعبی:
M_B^{-1}M_S=\frac16
\begin{bmatrix}
1&4&1&0\0&4&2&0\0&2&4&0\0&1&4&1
\end{bmatrix}.
شکل ۱۰.۳۶ چهار نقطهٔ کنترل و سه چندجملهای مکعبی ــ Bézier، درونیاب و اسپلاین ــ را نشان میدهد. فرمهای درونیاب و اسپلاین به صورت منحنی Bézier و با نقاط کنترل جدیدی تولید شدهاند که از ماتریسهای بالا حاصل میشوند.
پاورقی ۱۱. حتی سامانههایی که با تقسیمبندی رندر نمیکنند، اغلب برای رندر منحنی Bézier با روشهای دیگر بهینه شدهاند. بنابراین باز هم ممکن است تبدیل هر نوع منحنی یا سطح چندجملهای به فرم Bézier سودمند باشد.
شکل ۱۰.۳۶ — چندجملهایهای مکعبی تولیدشده به صورت منحنی Bézier با تبدیل نقاط کنترل: (الف) چندجملهای Bézier، (ب) چندجملهای درونیاب، (ج) چندجملهای B-Spline.
هر سه منحنی با تقسیمبندی بازگشتی منحنیهای Bézier تولید شدهاند. در حالت اسپلاین، توجه کنید که منحنی حاصل فقط میان نقطهٔ کنترل دوم و سوم نقاط کنترل اصلی ایجاد میشود.
۱۰.۹.۴ تقسیمبندی سطحهای Bézier
میتوان الگوریتم تقسیمبندی را به سطحهای Bézier نیز گسترش داد. سطح مکعبی شکل ۱۰.۳۷ را با ۱۶ نقطهٔ کنترل نشاندادهشده در نظر بگیرید.
شکل ۱۰.۳۷ — سطح Bézier مکعبی.
هر چهار نقطه در یک سطر یا ستون یک منحنی Bézier را تعیین میکنند که قابل تقسیم است. با این حال، الگوریتم تقسیمبندی سطح باید وصله را به چهار وصله تقسیم کند و در مرکز وصله نقطهٔ کنترل نداریم. این کار را در دو مرحله انجام میدهیم.
ابتدا تکنیک تقسیم منحنی را روی چهار منحنیای اعمال میکنیم که ۱۶ نقطهٔ کنترل در جهت (v) تعریف کردهاند. بنابراین برای هر یک از (u=0,1/3,2/3,1)، دو گروه چهارتایی نقطهٔ کنترل میسازیم که نقطهٔ میانی در هر دو گروه مشترک است. در نتیجه روی هر منحنی اصلی هفت نقطهٔ متفاوت داریم؛ این نقاط در شکل ۱۰.۳۸ با دایره نشان داده شدهاند. سه نوع نقطه وجود دارد: نقاط کنترل اصلی که پس از تقسیم باقی میمانند (خاکستری)، نقاط کنترل اصلی که پس از تقسیم کنار گذاشته میشوند (سفید)، و نقاط جدیدی که تقسیمبندی ایجاد میکند (سیاه).
سپس با استفاده از این نقاط در جهت (u) تقسیم میکنیم. سطرهای (v) ثابت را برای مقادیر (v=0,1/3,2/3,1) در نظر بگیرید. هفت گروه چهارتایی نقطه داریم. هر گروه یک منحنی Bézier با (v) ثابت تعریف میکند. در جهت (u) تقسیمبندی انجام میدهیم و هر بار دو گروه چهارتایی نقطه با یک نقطهٔ میانی مشترک میسازیم. نقاط حاصل در شکل ۱۰.۳۹ آمدهاند. اگر این نقاط را به چهار گروه ۱۶تایی تقسیم کنیم و نقاط روی لبهها مشترک باشند (شکل ۱۰.۴۰)، هر ربع شامل ۱۶ نقطهای است که نقاط کنترل یک سطح Bézier تقسیمشده را تشکیل میدهند.
شکل ۱۰.۳۸ — نخستین تقسیمبندی سطح.
راهنمای شکل: نقاط جدید ایجادشده در تقسیمبندی؛ نقاط قدیمی حذفشده پس از تقسیم؛ و نقاط قدیمی حفظشده پس از تقسیم.
شکل ۱۰.۳۹ — نقاط پس از تقسیمبندی دوم.
شکل ۱۰.۴۰ — یک ربع تقسیمشده.
در مقایسه با منحنیها، آزمون اینکه پوستهٔ محدب جدید بهاندازهٔ کافی تخت شده است تا فرایند تقسیم متوقف شود دشوارتر است. بسیاری از رندرکنندهها تعداد ثابتی از تقسیمها را بهکار میبرند و اغلب اجازه میدهند کاربر این تعداد را انتخاب کند. اگر رندر با کیفیت بالا لازم باشد، میتوان تقسیم را تا زمانی ادامه داد که اندازهٔ تصویرشدهٔ پوستهٔ محدب کمتر از اندازهٔ یک پیکسل شود.
۱۰.۱۰ قوری یوتا
بحث سطحهای پارامتری را با مثالی از تقسیمبندی بازگشتی مجموعهای از وصلههای Bézier مکعبی پایان میدهیم. شیء این مثال به نام قوری یوتا (Utah teapot) شناخته میشود. دادههای قوری را Mike Newell در دانشگاه Utah برای آزمایش الگوریتمهای گوناگون رندر ایجاد کرد.
این دادهها بیش از ۳۰ سال در جامعهٔ گرافیک مورد استفاده بودهاند. دادههای قوری شامل نقاط کنترل ۳۲ وصلهٔ Bézier دومکعبی هستند و در قالب ۳۰۶ رأس ارائه میشوند. ۱۲ وصلهٔ نخست بدنهٔ قوری، چهار وصلهٔ بعدی دسته، چهار وصلهٔ بعدی لوله، هشت وصلهٔ بعدی درپوش و چهار وصلهٔ نهایی کف قوری را تعریف میکنند. این دادهها بهطور گسترده در دسترساند.
برای توضیح، فرض کنید میخواهیم هر وصله را (n) بار تقسیم کنیم و پس از این تقسیمها، رأسهای نهایی را با پارهخط یا چندضلعیهایی که از چهار گوشهٔ هر وصله عبور میکنند رندر کنیم. بنابراین رسم نهایی برای پارهخطها با تابع زیر قابل انجام است. این تابع چهار نقطهٔ گوشه ــ که باید سطح را درونیابی کنند ــ را به آرایهای میافزاید که بعداً با خط یا مثلثهای پرشده رندر میشود:
void draw_patch(point4 p[4][4])
{
points[n] = p[0][0];
n++;
points[n] = p[3][0];
n++;
points[n] = p[3][3];
n++;
points[n] = p[0][3];
n++;
}
تقسیمکنندهٔ وصله را بر پایهٔ تقسیمکنندهٔ یک منحنی مکعبی c و با نوع point4 میسازیم:
void divide_curve(point4 c[4], point4 r[4], point4 l[4])
{
/* division of convex hull of Bezier curve */
int i;
point4 t;
for(i=0;i<3;i++)
l[0][i]=c[0][i];
r[3][i]=c[3][i];
l[1][i]=(c[1][i]+c[0][i])/2;
r[2][i]=(c[2][i]+c[3][i])/2;
t[i]=(l[1][i]+r[2][i])/2;
l[2][i]=(t[i]+l[1][i])/2;
r[1][i]=(t[i]+r[2][i])/2;
l[3][i]=r[0][i]=(l[2][i]+r[1][i])/2;
for(i=0; i<4; i++) l[i][3] = r[i][3] = 1.0;
}
مطابق قاعدهٔ حفظ کد، متن داخل بلوک کد بدون ترجمه یا تغییر هویتی منتقل شده است.
اگر فرض کنیم تابع ترانهادهسازی ماتریس transpose4 را داریم، تقسیمکنندهٔ وصله سادهتر ــ هرچند اندکی کمبازدهتر ــ نوشته میشود:
void divide_patch(point4 p[4][4], int n)
{
point4 q[4][4], r[4][4], s[4][4], t[4][4];
point4 a[4][4], b[4][4];
int k;
if(n==0) draw_patch(p); /* draw patch if recursion done */
/* subdivide curves in u direction, transpose results, divide
in u direction again (equivalent to subdivision in v) */
else
{
for(k=0; k<4; k++) divide_curve(p[k], a[k], b[k]);
transpose4(a);
transpose4(b);
for(k=0; k<4; k++)
{
divide_curve(a[k], q[k], r[k]);
divide_curve(b[k], s[k], t[k]);
}
/* recursive division of 4 resulting patches */
divide_patch(q, n-1);
divide_patch(r, n-1);
divide_patch(s, n-1);
divide_patch(t, n-1);
}
}
یک برنامهٔ کامل رندر قوری با چندضلعیهای سایهخورده در ضمیمهٔ A آمده است و دادههای خود قوری نیز در همان برنامه قرار دارند.
شکل ۱۰.۴۱ قوری را یکبار به صورت قاب سیمی و یکبار با سایهزنی ثابت نشان میدهد. وصلههای مختلف دارای انحنا و اندازههای متفاوتاند؛ در نتیجه اگر همهٔ تقسیمبندیها را تا عمق یکسان ادامه دهیم، تعداد زیادی چندضلعی کوچک و غیرضروری ساخته میشود.
شکل ۱۰.۴۱ — قوریهای رندرشده.
۱۰.۱۱ سطحهای جبری
اگرچه quadricها را میتوان حالت خاصی از منحنیهای NURBS تولید کرد، این رده از اشیای جبری آنقدر مهم است که بررسی مستقلی میطلبد. quadricها مهمترین حالت سطحهای جبری معرفیشده در بخش ۱۰.۱ هستند.
۱۰.۱۱.۱ سطحهای درجهٔ دوم
سطحهای quadric با معادلات جبری ضمنی توصیف میشوند که هر جملهٔ آنها چندجملهایای از فرم (x^iy^jz^k) با شرط (i+j+k\le2) است. هر quadric را میتوان به صورت
q(x,y,z)=a_{11}x^2+2a_{12}xy+a_{22}y^2+a_{33}z^2+2a_{23}yz+2a_{13}xz
+b_1x+b_2y+b_3z+c=0
نوشت. این رده شامل بیضویها، سهمویوارها و هذلولیوارهاست.
اگر ماتریس ستونی سهبعدی
p=[x\;y\;z]^T
را بهکار ببریم، معادلهٔ عمومی به شکل فرم درجهٔ دوم زیر نوشته میشود:
p^TAp+b^Tp+c=0,
که در آن
A=
\begin{bmatrix}
a_{11}&a_{12}&a_{13}\a_{12}&a_{22}&a_{23}\a_{13}&a_{23}&a_{33}
\end{bmatrix},
\qquad
b=
\begin{bmatrix}
b_1\\b_2\\b_3
\end{bmatrix}.
ده ضریب مستقل در (A)، (b) و (c) یک quadric مشخص را تعیین میکنند. با این حال برای طبقهبندی، میتوان دنبالهای از چرخشها و انتقالها را اعمال کرد که بدون تغییر نوع سطح، quadric را به یک فرم استاندارد میبرد. در سه بعد چنین تبدیلی را میتوان نوشت:
p'=Mp+d.
این جایگذاری فرم درجهٔ دوم دیگری تولید میکند که در آن (A) با ماتریس (M^TAM) جایگزین میشود. همیشه میتوان (M) را یک ماتریس چرخش انتخاب کرد بهگونهای که
D=M^TAM
قطری شود. عناصر قطری (D) نوع quadric را مشخص میکنند. برای مثال اگر معادله مربوط به یک بیضوی باشد، فرم درجهٔ دوم حاصل را میتوان به صورت
a'_{11}x'^2+a'_{22}y'^2+a'_{33}z'^2-c'=0
درآورد که همهٔ ضرایب آن مثبتاند. چون با یک تبدیل آفین میتوان به فرم استاندارد رسید، quadricها تحت تبدیلهای آفین حفظ میشوند و در کنار primitiveهای استاندارد دیگر ما بهخوبی قرار میگیرند.
۱۰.۱۱.۲ رندر سطحها با Ray Casting (پرتوافکنی)
رندر quadricها ساده است، زیرا تقاطع یک quadric با یک پرتو با حل یک معادلهٔ اسکالر درجهٔ دوم پیدا میشود. پرتو آغازشده از (p_0) در جهت (d) را به صورت پارامتری نمایش میدهیم:
p=p_0+\alpha d.
با جایگذاری در معادلهٔ quadric، معادلهٔ اسکالر زیر برای (\alpha) بهدست میآید:
\alpha^2d^TAd+
\alpha d^T(b+2Ap_0)+
p_0^TAp_0+b^Tp_0+c=0.
مانند هر معادلهٔ درجهٔ دوم، ممکن است صفر، یک یا دو جواب حقیقی داشته باشیم. از این نتیجه میتوان برای رندر quadric در frame buffer یا بهعنوان بخشی از محاسبات ray tracing استفاده کرد. همچنین مدل سایهزنی استاندارد را میتوان در هر نقطهٔ quadric اعمال کرد، زیرا نرمال از مشتقها محاسبه میشود:
n=
\begin{bmatrix}
\partial q/\partial x\\partial q/\partial y\\partial q/\partial z
\end{bmatrix}
=2Ap-b.
این روش رندر را میتوان به هر سطح جبری گسترش داد. فرض کنید سطح جبری
q(p)=q(x,y,z)=0
داریم. در بخشی از خط لولهٔ رندر، از مرکز تصویرسازی از میان هر پیکسل یک پرتو میفرستیم. هر پرتو را میتوان به صورت
p(\alpha)=p_0+\alpha d
نوشت. با جایگذاری این عبارت در (q)، یک معادلهٔ چندجملهای ضمنی بر حسب (\alpha) حاصل میشود:
q(p(\alpha))=0.
نقاط تقاطع را میتوان با روشهای عددی یافت؛ برای quadricها نیز فرمول درجهٔ دوم کافی است. اگر جملههایی تا مرتبهٔ (x^iy^jz^k) داشته باشیم، ممکن است تا (i+j+k) نقطهٔ تقاطع پدید آید و رندر سطح زمان قابل توجهی نیاز داشته باشد.
۱۰.۱۲ منحنیها و سطحهای تقسیمبندیشونده
فرمول تقسیمبندی بخش ۱۰.۹.۲ را از دیدگاهی اندکی متفاوت دوباره بررسی میکنیم. با چهار نقطهٔ (p_0,p_1,p_2,p_3) آغاز میکنیم و در پایان هفت نقطه داریم. این نقاط جدید را (s_0,\ldots,s_6) مینامیم. هر یک از این مجموعه نقاط را میتوان تعریفکنندهٔ یک منحنی خطیِ قطعهای دانست؛ شکل ۱۰.۴۲ این دیدگاه را نشان میدهد.