کواترنیونها، جمعبندی و تمرینهای فصل سوم
3.14 کواترنیونها
با این حال، آنچه واقعاً برای ما اهمیت دارد دوران در یک فضای سهبعدی است. در سه بعد، مسئله دشوارتر میشود، زیرا برای مشخصکردن یک دوران حول مبدأ باید هم یک جهت (یک بردار) و هم مقدار دوران حول آن جهت (یک اسکالر) را تعیین کنیم. یک راهحل، استفاده از نمایشی است که هم یک بردار و هم یک اسکالر را در بر بگیرد. این نمایش معمولاً به صورت کواترنیون زیر نوشته میشود:
a=(q_0,q_1,q_2,q_3)=(q_0,\mathbf q),
که در آن (\mathbf q=(q_1,q_2,q_3)) است. عملیات میان کواترنیونها بر استفاده از سه عدد «مختلط» (i)، (j) و (k) با خواص زیر استوار است:
i^2=j^2=k^2=ijk=-1.
این اعداد مشابه بردارهای واحد در سه بعد هستند و میتوانیم (\mathbf q) را چنین بنویسیم:
\mathbf q=q_1i+q_2j+q_3k.
اکنون با استفاده از روابط میان (i)، (j) و (k) میتوان جمع و ضرب کواترنیونی را به دست آورد. اگر کواترنیون (b) به صورت
b=(p_0,\mathbf p)
داده شود، با استفاده از ضرب داخلی و ضرب برداری برای بردارها داریم:
a+b=(p_0+q_0,\mathbf p+\mathbf q),
ab=(p_0q_0-\mathbf q\cdot\mathbf p,\;q_0\mathbf p+p_0\mathbf q+\mathbf q\times\mathbf p).
همچنین میتوان اندازهٔ یک کواترنیون را به شیوهٔ معمول تعریف کرد:
|a|^2=q_0^2+q_1^2+q_2^2+q_3^2=q_0^2+\mathbf q\cdot\mathbf q.
کواترنیونها دارای همانی ضربی، یعنی کواترنیون ((1,\mathbf 0))، هستند و بهسادگی میتوان بررسی کرد که وارون یک کواترنیون از رابطهٔ زیر به دست میآید:
a^{-1}=\frac{1}{|a|^2}(q_0,-\mathbf q).
3.14.2 کواترنیونها و دوران
تا اینجا فقط یک شیء ریاضی جدید تعریف کردهایم. برای آنکه این شیء برای ما مفید باشد، باید آن را به موجودیتهای هندسی خود مرتبط کنیم و نشان دهیم چگونه میتوان از آن برای انجام عملیاتی مانند دوران استفاده کرد. فرض کنید از بخش برداری یک کواترنیون برای نمایش نقطهای در فضا استفاده کنیم:
p=(0,\mathbf p).
در این حالت، مؤلفههای (\mathbf p=(x,y,z)) مکان نقطه را مشخص میکنند. کواترنیون زیر را در نظر بگیرید:
r=\left(\cos\frac{\theta}{2},\;\sin\frac{\theta}{2}\mathbf v\right),
که در آن (\mathbf v) طول واحد دارد. آنگاه میتوان نشان داد که (r) یک کواترنیون واحد است، یعنی (|r|=1)، و بنابراین
r^{-1}=\left(\cos\frac{\theta}{2},\;-\sin\frac{\theta}{2}\mathbf v\right).
اگر حاصلضرب کواترنیونیِ کواترنیون (p)، که نمایندهٔ یک نقطه است، با (r) را در نظر بگیریم، کواترنیون زیر به دست میآید:
p'=rpr^{-1}.
این کواترنیون به شکل ((0,\mathbf p')) است که در آن
\mathbf p'=\cos^2\frac{\theta}{2}\,\mathbf p
+\sin^2\frac{\theta}{2}(\mathbf p\cdot\mathbf v)\mathbf v
+2\sin\frac{\theta}{2}\cos\frac{\theta}{2}(\mathbf v\times\mathbf p)
-\sin^2\frac{\theta}{2}(\mathbf v\times\mathbf p)\times\mathbf v.
پس (\mathbf p') نیز نمایش یک نقطه است. نکتهای که در نگاه نخست کمتر آشکار است این است که (\mathbf p') نتیجهٔ دوران نقطهٔ (\mathbf p) به اندازهٔ (\theta) حول بردار (\mathbf v) است. با مقایسهٔ جملههای (\mathbf p') با دوران عمومی میتوان درستی این نتیجه را بررسی کرد.
پیامد این نتیجه مهم است: چون همان نتیجهٔ هندسی را به دست میآوریم، حاصلضرب کواترنیونی ساختهشده از (r) و (p) میتواند جایگزین ماتریسهای تبدیل برای نمایش دوران حول یک محور دلخواه، با نقطهٔ ثابت در مبدأ، باشد. اگر تعداد عملیات را بشماریم، کواترنیونها سریعترند و در پیادهسازیهای سختافزاری و نرمافزاری نیز به کار گرفته شدهاند.
چند مثال را بررسی کنیم. دوران به اندازهٔ (\theta) حول محور (z)، با نقطهٔ ثابت در مبدأ، را در نظر بگیرید. بردار واحد مطلوب (\mathbf v=(0,0,1)) است و کواترنیون زیر را میدهد:
r=\cos\frac{\theta}{2}+\sin\frac{\theta}{2}(0,0,1).
دوران یک نقطهٔ دلخواه (\mathbf p=(x,y,z)) کواترنیون زیر را تولید میکند:
p'=rpr^{-1}=r(0,\mathbf p)r^{-1}=(0,\mathbf p'),
که در آن
\mathbf p'=(x\cos\theta-y\sin\theta,\;x\sin\theta+y\cos\theta,\;z).
بنابراین همان نتیجهٔ مورد انتظار را، با عملیات کمتر، به دست میآوریم. اگر دنبالهای از دورانها حول محورهای مختصات داشته باشیم که در نمایش ماتریسی ماتریس
R=R_x(\theta_x)R_y(\theta_y)R_z(\theta_z)
را میسازد، میتوانیم به جای آن حاصلضرب کواترنیونهای متناظر، یعنی (r_xr_yr_z)، را به کار ببریم.
اگر به دوران حول یک محور دلخواه بازگردیم، در بخش 3.10.4 ماتریسی به شکل زیر به دست آوردیم:
M=T(\mathbf p_0)R_x(-\theta_x)R_y(-\theta_y)R_z(\theta_z)R_y(\theta_y)R_x(\theta_x)T(-\mathbf p_0).
به علت وجود انتقالها در ابتدا و انتهای این زنجیره، نمیتوان از کواترنیونها برای کل عملیات استفاده کرد. با این حال، میتوان تشخیص داد که مؤلفههای (\mathbf p'=rpr^{-1}) برای یافتن مؤلفههای ماتریس دوران مختصات همگنِ نهفته در (M) قابل استفادهاند. پس اگر بار دیگر
r=\left(\cos\frac{\theta}{2},\sin\frac{\theta}{2}\mathbf v\right),
باشد، ماتریس دوران (R) از همان مؤلفههای کواترنیونی ساخته میشود. به صورت صریح، مؤلفههای ماتریس از ترکیبهای (v_x)، (v_y)، (v_z)، (\sin(\theta/2)) و (\cos(\theta/2)) به دست میآیند و سطر و ستون همگن چهارم به صورت معمول ([0;0;0;1]) باقی میماند.
این ماتریس را میتوان با استفاده از همانیهای مثلثاتی زیر به شکل آشناتری درآورد:
\cos\theta=\cos^2\frac{\theta}{2}-\sin^2\frac{\theta}{2}=1-2\sin^2\frac{\theta}{2},
\sin\theta=2\cos\frac{\theta}{2}\sin\frac{\theta}{2},
و با یادآوری اینکه (\mathbf v) یک بردار واحد است:
v_x^2+v_y^2+v_z^2=1.
بنابراین میتوان از حاصلضربهای کواترنیونی برای تشکیل (r) استفاده کرد، سپس با تطبیق جملههای (R) و (r)، بخش دورانی (M) را ساخت و در پایان با عملیات تبدیل معمول، اثر دو انتقال را نیز اضافه کرد.
راه دیگر این است که با نوع vec4، کواترنیونها را یا در برنامهٔ کاربردی (تمرین 3.26) یا در شیدرها (تمرین 3.30) ایجاد کنیم. در هر دو حالت میتوان دوران را مستقیماً، بدون تبدیل دوباره به ماتریس دوران، انجام داد.
علاوه بر کارایی بیشتر کواترنیونها نسبت به ماتریسهای دوران، میتوان میان کواترنیونها درونیابی کرد تا دنبالههای نرم و پیوستهای از دورانها برای پویانمایی به دست آید.
جمعبندی و یادداشتها
در این فصل دو دیدگاه متفاوت ــ اما در نهایت مکمل ــ دربارهٔ ریاضیات گرافیک رایانهای ارائه کردیم. دیدگاه نخست این است که اگر بخواهیم عملیاتی را که در برنامههای گرافیکی انجام میدهیم بهدرستی درک کنیم، انتزاع ریاضی اشیایی که با آنها کار میکنیم ضروری است. دیدگاه دوم این است که تبدیلها و روشهای اجرای آنها، از جمله مختصات همگن، پایهٔ پیادهسازی سامانههای گرافیکیاند.
ابزارهای ریاضی ما از تحلیل برداری و جبر خطی میآیند. با این حال، برای اهداف گرافیک رایانهای، ترتیب ارائهٔ این ابزارها را برعکس ترتیبی انتخاب کردیم که بیشتر دانشجویان معمولاً آنها را میآموزند. به طور معمول ابتدا جبر خطی مطالعه میشود و سپس مفاهیم فضای برداری به بررسی n-تاییها در (R^n) پیوند میخورند. در مقابل، مطالعهٔ ما دربارهٔ نمایش در فضاهای ریاضی، ما را به استفاده از جبر خطی به عنوان ابزاری برای پیادهسازی نوعهای انتزاعی رساند.
رویکرد مستقل از مختصات را به دو دلیل دنبال کردیم. نخست، میخواستیم نشان دهیم که همهٔ مفاهیم پایهٔ اشیای هندسی و تبدیلها مستقل از شیوهٔ نمایش آنها هستند. دوم، با فراگیرترشدن زبانهای شیءگرا، برنامهنویسان کاربردی بیش از پیش مستقیماً با خود اشیا کار خواهند کرد، نه صرفاً با نمایش عددی آنها. منابع بخش «مطالعهٔ پیشنهادی» نمونههایی از سامانههای برنامهنویسی هندسی را معرفی میکنند که ظرفیت این رویکرد را نشان میدهند.
مختصات همگن نمونهای درخشان از قدرت انتزاع ریاضی فراهم کرد. با رفتن به یک فضای ریاضی انتزاعی ــ فضای آفین ــ ابزاری یافتیم که مستقیماً به روشهای کارآمد نرمافزاری و سختافزاری انجامید.
در پایان، مجموعهٔ تبدیلهای آفین پشتیبانیشده در OpenGL را ارائه کردیم و توضیح دادیم چگونه میتوان با الحاق آنها همهٔ تبدیلهای آفین را ساخت. راهبرد ترکیب چند نوع سادهٔ ماتریس برای ساخت تبدیل مطلوب، راهبردی قدرتمند است و بهتر است آن را در تعدادی از تمرینهای پایان فصل به کار ببرید. در فصل ۴ بر همین تکنیکها بنا میکنیم تا مشاهده در گرافیک سهبعدی را توسعه دهیم؛ در فصل ۸ نیز از تبدیلها برای ساخت مدلهای سلسلهمراتبی استفاده خواهیم کرد.
مطالعهٔ پیشنهادی
کتابهای فراوانی دربارهٔ تحلیل برداری و جبر خطی وجود دارد، هرچند بیشتر آنها این دو موضوع را جداگانه بررسی میکنند. در جامعهٔ طراحی هندسی، رویکرد فضای برداری و توصیف مستقل از مختصاتِ منحنیها و سطوح محبوب بوده است؛ کتاب Faux و Pratt [Fau80] نمونهای از این دیدگاه است. برای مقدمهای بر برنامهنویسی هندسی به DeRose [DeR88, DeR89] مراجعه کنید. مختصات همگن ابتدا در هندسه پدیدار شد [Max51] و بعداً جامعهٔ گرافیک آن را دوباره کشف کرد [Rob63, Rie81]. استفادهٔ سختافزاری آن با Geometry Engine شرکت Silicon Graphics آغاز شد [Cla82]. معماریهای سختافزاری جدید از مدارهای مجتمع ویژهٔ کاربرد (ASIC) بهره میگیرند که تبدیلهای مختصات همگن را شامل میشوند.
کواترنیونها توسط Shoemake [Sho85] برای استفاده در پویانمایی وارد گرافیک رایانهای شدند. کتاب Kuipers [Kui99] مثالهای فراوانی از کاربرد ماتریسهای دوران و کواترنیونها ارائه میکند.
ابزارهای نرمافزاری مانند Mathematica [Wol91] و MATLAB [Mat95] نیز برای یادگیری و دستکاری ماتریسهای تبدیل بسیار سودمندند.
تمرینها
3.1 نشان دهید دنبالههای زیر جابجاپذیرند:
الف) یک دوران و یک مقیاسدهی یکنواخت؛ ب) دو دوران حول یک محور یکسان؛ ج) دو انتقال.
3.2 پیچش (Twist) شبیه دوران حول مبدأ است، با این تفاوت که مقدار دوران هرچه نقطه از مبدأ دورتر باشد با ضریب (f) افزایش مییابد. برنامهای بنویسید که واشر سیرپینسکی مبتنی بر مثلث را با مقدار (f) واردشده توسط کاربر بپیچاند. مشاهده کنید شکل واشر با تعداد تقسیمبندیها چگونه تغییر میکند.
3.3 کتابخانهای از توابع بنویسید که امکان برنامهنویسی هندسی را فراهم کند. کتابخانه باید توابعی برای دستکاری نوعهای هندسی پایه (نقطه، خط، بردار) و عملیات روی آنها، از جمله ضرب داخلی و ضرب برداری، داشته باشد. همچنین باید تغییر Frame را پشتیبانی کند. میتوانید توابعی برای ارتباط با OpenGL نیز بسازید تا نتیجهٔ محاسبات هندسی قابل نمایش باشد.
3.4 اگر فقط به گرافیک دوبعدی علاقهمند باشیم، میتوانیم از مختصات همگن سهبعدی استفاده کنیم و نقطه را به شکل (p=[x;y;1]^T) و بردار را به شکل (v=[a;b;0]^T) نمایش دهیم. ماتریسهای (3\times3) دوران، انتقال، مقیاسدهی و برش را بیابید. یک تبدیل آفین برای تبدیل نقاط دوبعدی چند درجهٔ آزادی دارد؟
3.5 میتوان یک تبدیل آفین را با درنظرگرفتن مکان تعداد کمی نقطه، پیش و پس از تبدیل، مشخص کرد. در سه بعد برای تعیین یکتای تبدیل به چند نقطه نیاز داریم؟ این تعداد در دو بعد چگونه تغییر میکند؟
3.6 اگر در یک دستگاه چپگرد کار کنیم و تعریف خود از دوران مثبت را حفظ کنیم، ماتریسهای دوران چگونه باید تغییر کنند؟
3.7 نشان دهید هر دنبالهای از دورانها و انتقالها را میتوان با یک دوران واحد حول مبدأ و سپس یک انتقال جایگزین کرد.
3.8 تبدیل برش را از تبدیلهای دوران، انتقال و مقیاسدهی استخراج کنید.
3.9 در دو بعد میتوان خط را با معادلهٔ (y=mx+h) مشخص کرد. یک تبدیل آفین برای بازتاب نقاط دوبعدی نسبت به این خط بیابید. نتیجه را برای بازتاب نسبت به یک صفحه در سه بعد گسترش دهید.
3.10 در بخش 3.10 نشان دادیم که یک ماتریس دوران دلخواه را میتوان از دورانهای متوالی حول سه محور ساخت. اگر فقط سه دوران ساده مجاز باشند، یک دوران مشخص را به چند روش میتوان ترکیب کرد؟ آیا هر سه ماتریس دوران ساده لازماند؟
3.11 برش را به تبدیل نمونه (instance transformation) اضافه کنید. نشان دهید چگونه میتوان با این تبدیل توسعهیافته، متوازیالسطوحها را از یک مکعب واحد تولید کرد.
3.12 یک نمایش مختصات همگن برای صفحه پیدا کنید.
3.13 ماتریس دوران برای دورانی به شکل (R_xR_yR_z) را تعیین کنید. فرض کنید نقطهٔ ثابت مبدأ و زاویهها (\theta_x)، (\theta_y) و (\theta_z) هستند.
3.14 حل معادلات دیفرانسیل خطی یا معادلات تفاضلی (روابط بازگشتی) با ضرایب ثابت را در نظر بگیرید. نشان دهید جوابهای معادلات همگن یک فضای برداری تشکیل میدهند. جواب یک معادلهٔ ناهمگن مشخص را به یک فضای آفین مرتبط کنید.
3.15 برنامهای برای تولید واشر سیرپینسکی به روش زیر بنویسید: با یک مثلث سفید آغاز کنید. در هر مرحله، با استفاده از تبدیلها سه مثلث مشابه تولید کنید که روی مثلث اصلی رسم شوند، بهطوریکه مرکز مثلث سفید و سه گوشه سیاه باقی بمانند.
3.16 با مکعبی که در مبدأ مرکز شده و با محورهای مختصات همراستا است شروع کنید. ماتریس دورانی را بیابید که مکعب را بهصورت متقارن، همانند شکل 3.63، جهتدهی کند.
شکل 3.63 ــ جهتگیری متقارن مکعب.
3.17 در سه بعد از رأسها برای تعریف اشیایی مانند چندضلعیهای سهبعدی استفاده کردیم. با داشتن مجموعهای از رأسها، آزمونی بیابید که مشخص کند چندضلعی تعیینشده توسط آنها همصفحه است یا نه.
3.18 سه رأس، در صورتی که روی یک خط نباشند، یک مثلث را تعیین میکنند. آزمونی برای همخطبودن سه رأس طراحی کنید.
3.19 تبدیل نمونه را به صورت حاصلضرب یک انتقال، یک دوران و یک مقیاسدهی تعریف کردیم. آیا با اعمال این سه نوع تبدیل در ترتیبی متفاوت میتوان همان اثر را به دست آورد؟
3.20 برنامهای بنویسید که با یک دکمهٔ ماوس بتوان مکعب را جهتدهی کرد، با دکمهٔ دوم آن را انتقال داد و با دکمهٔ سوم روی آن بزرگنمایی/کوچکنمایی انجام داد.
3.21 با داشتن دو بردار سهبعدی غیرموازی (\mathbf u) و (\mathbf v)، چگونه میتوان یک دستگاه مختصات متعامد ساخت که (\mathbf u) یکی از بردارهای پایهٔ آن باشد؟
3.22 یک دوران افزایشی حول محور (z) را میتوان با ماتریس زیر تقریب زد:
\begin{bmatrix}
1&-\theta&0&0\\theta&1&0&0\0&0&1&0\0&0&0&1
\end{bmatrix}.
اگر این ماتریس را برای تعداد زیادی گام استفاده کنیم چه پیامدهای منفیای خواهد داشت؟ آیا راهحلی پیشنهاد میکنید؟ راهنمایی: نقاطی با فاصلهٔ ۱ از مبدأ را در نظر بگیرید.
3.23 کواترنیونهای دوران ۹۰ درجه حول محورهای (x) و (y) را بیابید و حاصلضرب آنها را تعیین کنید.
3.24 ماتریس دوران (R=R(\theta_x)R(\theta_y)R(\theta_z)) را تعیین کنید. کواترنیون متناظر را بیابید.
3.25 برنامهٔ Trackball را با استفاده از کواترنیونها به جای ماتریسهای دوران بازنویسی کنید.
3.26 با استفاده از کلاس vec4 مجموعهای از عملیات کواترنیونی ایجاد کنید که در یک برنامهٔ کاربردی قابل اجرا باشند. برای مثال میتوانید با Prototypeهای زیر آغاز کنید:
typedef vec4 quaternion;
quaternion multq(const quaternion &, const quaternion &);
quaternion addq(const quaternion &, const quaternion &);
quaternion iverseq(const quaternion &);
point4 rotateq(float theta, const point4 &);
3.27 یک Vertex Shader بنویسید که یک زاویه و یک محور دوران را به عنوان ورودی بگیرد و رأسها را حول آن محور بچرخاند.
3.28 از نظر اصولی، یک سامانهٔ شیءگرا میتواند اسکالرها، بردارها و نقاط را به عنوان نوعهای پایه فراهم کند. هیچیک از APIهای رایج چنین کاری نمیکنند. چرا فکر میکنید چنین است؟
3.29 نشان دهید مجموع
P=\alpha_1P_1+\alpha_2P_2+\cdots+\alpha_nP_n
اگر و تنها اگر
\alpha_1+\alpha_2+\cdots+\alpha_n=1
باشد تعریفشده است. راهنمایی: از دو جملهٔ نخست شروع کنید و بنویسید:
P=\alpha_1P_1+\alpha_2P_2+\cdots
=\alpha_1P_1+(\alpha_2+\alpha_1-\alpha_1)P_2+\cdots
=\alpha_1(P_1-P_2)+(\alpha_1+\alpha_2)P_2+\cdots,
و سپس به صورت استقرایی ادامه دهید.
3.30 یک Vertex Shader بنویسید که ورودی آن یک کواترنیون باشد و رأس ورودی را با دوران کواترنیونی بچرخاند.
3.31 تابعی با امضای Rotate(float theta, vec3d) بنویسید که به اندازهٔ theta درجه حول محور d و با نقطهٔ ثابت در مبدأ دوران دهد.
این صفحه عمداً خالی گذاشته شده است.