مدل‌سازی سلسله‌مراتبی، بازوی ربات، درخت‌ها و اشیای گرافیکی

فصل ۸ — مدل‌سازی و سلسله‌مراتب

Modelها انتزاعی از جهان‌اند؛ هم جهان واقعی و هم جهان‌های مجازی ساخته‌شده با رایانه. در علوم و مهندسی از Mathematical Model برای نمایش پدیده‌های فیزیکی با Equationها استفاده می‌کنیم. در Computer Science، Abstract Data Typeها سازمان اشیا را مدل می‌کنند و در Computer Graphics جهان با Geometric Objectها نمایش داده می‌شود.

همان‌طور که برای یک پدیدهٔ فیزیکی باید نوع Mathematics مناسب انتخاب شود، در Graphics نیز باید Primitiveهای مناسب و رابطهٔ میان آن‌ها انتخاب شوند. برای مثال Ordinary Differential Equation ممکن است برای سامانهٔ Spring-Mass مناسب باشد، در حالی که Turbulent Fluid Flow به Partial Differential Equation نیاز دارد. در Graphics نیز ممکن است چند Model متفاوت برای یک مسئله ممکن باشد؛ مدل مطلوب مدلی است که از قابلیت‌های Graphics System به‌خوبی بهره ببرد.

در این فصل چند رویکرد برای ساخت و کار با مدل‌های Geometric Object بررسی می‌شود. Building Blockها می‌توانند Primitiveهای خود Graphics System یا User-Defined Objectهای ساخته‌شده از آن‌ها باشند. Transformationهای فصل ۳ به روابط سلسله‌مراتبی میان اشیا تعمیم داده می‌شوند. این Techniqueها برای Robotics و Figure Animation مناسب‌اند، جایی که Dynamic Behavior اجزا به روابط میان بخش‌های Model وابسته است.

Hierarchy مفهومی قدرتمند و بخش مهم Object-Oriented Methodology است. مدل سلسله‌مراتبی اشیا را می‌توان به کل Scene شامل Camera، Light و Material Property تعمیم داد. چنین مدل‌هایی Graphics API را به سیستم‌های Object-Orientedتر نزدیک می‌کنند و برای Graphics روی Network و Distributed Environmentهایی مانند World Wide Web نیز مفیدند.

۸٫۱ Symbolها و Instanceها

نخستین مسئله این است که مدلی شامل تعداد زیادی Object پیچیده را چگونه ذخیره کنیم. دو پرسش فوری داریم: Objectهای پیچیده‌تر از Primitiveهای پایه چگونه تعریف شوند و مجموعه‌ای از این اشیا چگونه نمایش داده شود؟ بیشتر APIها در تعریف Primitiveها Minimalist هستند و فقط چند Primitive اصلی می‌دهند؛ ساخت Objectهای پیچیده‌تر بر عهدهٔ برنامه‌نویس یا Libraryهای سطح بالاتر است. فرض می‌کنیم مجموعه‌ای از Objectهای سه‌بعدی پایه در اختیار داریم.

می‌توان رویکردی غیرسلسله‌مراتبی داشت و هر Object را یک Symbol دانست و جهان را مجموعه‌ای از Symbolها مدل کرد. Symbol می‌تواند Geometric Object، Font یا مجموعه‌ای Application-Specific از Graphical Objectها باشد. هر Symbol معمولاً در اندازه و Orientation استاندارد و راحت تعریف می‌شود. برای مثال Cylinder اغلب موازی یکی از محورها، با Height و Radius واحد و کف آن در مبدأ تعریف می‌شود.

شکل ۸٫۱ — Symbol استوانه.

بیشتر APIها، از جمله OpenGL، میان Frame تعریف Symbol—که گاهی Model Frame نامیده می‌شود—و Object/World Frame تمایز می‌گذارند. این تفکیک به‌خصوص برای Shapeهایی بدون واحد فیزیکی، مانند Circuit Element در CAD، مفید است.

در OpenGL تبدیل از Frame خود Symbol به Object Coordinate Frame در برنامه تنظیم می‌شود. بنابراین Model-View Matrix یک Symbol ترکیبی از Instance Transformation است که Symbol را وارد Object Coordinates می‌کند و Matrix دیگری که آن را به Eye Frame می‌برد.

Instance Transformation فصل ۳ اجازه می‌دهد Instanceهای یک Symbol را با Size، Orientation و Location دلخواه در Model قرار دهیم. تبدیل

ترکیبی از Translation، Rotation و Scale—و در صورت نیاز Shear—است. الگوی رایج:

mat4 instance;
mat4 model_view;

instance = Translate(dx, dy, dz)*RotateZ(rz)*
           RotateY(ry)*RotateX(rx)*Scale(sx, sy, sz);

model_view = model_view*instance;
cylinder(); /* or some other symbol */

شکل ۸٫۲ — Instance Transformation: Scale، Rotate و Translate.

در این مثال Instance Matrix، Model-View Matrix را تغییر می‌دهد و Matrix نهایی با glUniform به Vertex Shader می‌رود. تابع cylinder رأس‌ها را تولید و مثلاً با glDrawArrays به Pipeline می‌فرستد. روش دیگر این است که Model-View Matrix در خود برنامه هنگام تولید Vertexها اعمال شود.

همین مدل را می‌توان به شکل Table نیز دید. هر Symbol یک Identifier عددی یکتا دارد و Table آن Identifier و پارامترهای لازم برای ساخت Instance Transformation Matrix را ذخیره می‌کند.

شکل ۸٫۳ — جدول Symbol–Instance Transformation.

این روش هیچ اطلاعاتی از رابطهٔ میان Objectها ندارد، اما برای Drawکردن همهٔ اشیا اطلاعات کافی فراهم می‌کند. می‌توان Table را برای یافتن Object جست‌وجو کرد، Instance Transformation آن را تغییر داد یا Object را اضافه/حذف کرد. بااین‌حال ساختار Flat محدودکننده است.

۸٫۲ Hierarchical Modelها

فرض کنید بخواهیم Automobileای قابل Animation مدل کنیم. Model می‌تواند از پنج قسمت—Chassis و چهار Wheel—ساخته شود که همه با Primitiveهای استاندارد قابل تعریف‌اند. دو Frame سادهٔ Animation در شکل ۸٫۵ نشان داده شده است.

شکل ۸٫۴ — مدل Automobile.

شکل ۸٫۵ — دو Frame از Animation.

اگر Radius هر Wheel برابر r باشد، Rotation کامل ۳۶۰ درجهٔ Wheel باید با Translation خودرو به اندازهٔ (2\pi r) متناظر باشد. می‌توان برای هر Wheel و Chassis تابع جدا نوشت و Speed و Direction را به همه داد:

{
    float s; /* speed */
    float d[3]; /* direction */
    float t; /* time */

    /* determine speed and direction at time t*/

    draw_right_front_wheel(s,d);
    draw_left_front_wheel(s,d);
    draw_right_rear_wheel(s,d);
    draw_left_rear_wheel(s,d);
    draw_chassis(s,d);
}

اما این دقیقاً نوع برنامه‌ای است که نمی‌خواهیم: Linear است و هیچ رابطهٔ ساختاری میان اجزای Automobile را نشان نمی‌دهد. دو نوع رابطه مهم وجود دارد. نخست، حرکت Chassis و Wheelها مستقل نیست؛ با حرکت خودرو Wheelها باید Rotate شوند. دوم، چهار Wheel یکسان‌اند و فقط Location و Orientation متفاوت دارند.

برای نمایش رابطهٔ میان اجزای Model می‌توان از Graph استفاده کرد. در Mathematics، Graph مجموعه‌ای از Node/Vertexها و Edgeهاست. Edgeها جفت Nodeها را متصل می‌کنند و ممکن است جهت داشته باشند. Graphهای مورد استفادهٔ ما Directed هستند؛ یعنی Edge از یک Node خارج و وارد Node دیگر می‌شود.

شکل ۸٫۶ — Tree Structure مدل Automobile.

مهم‌ترین نوع Graph برای ما Tree است. Tree متصل یک Directed Graph بدون Closed Path یا Loop است. به‌جز یک Node یعنی Root، هر Node دقیقاً یک Edge ورودی دارد. بنابراین هر Node غیر Root یک Parent دارد و می‌تواند یک یا چند Child داشته باشد. Node بدون Child، Terminal Node یا Leaf نام دارد.

در Tree خودرو، Chassis Root و چهار Wheel Childهای آن‌اند. در عمل Node و Edge فقط عناصر انتزاعی نیستند و می‌توانند Information اضافه ذخیره کنند. در مثال خودرو هر Node می‌تواند Geometry مربوط را نگه دارد و Position/Orientation Wheelها نیز می‌تواند در Node یا Edge اتصال به Parent ذخیره شود.

چون چهار Wheel معمولاً یکسان‌اند، ذخیرهٔ روش Drawکردن Wheel در چهار Node جدا ناکارآمد است. با مفهوم Instance Transformation می‌توان یک Prototype Wheel واحد داشت. در این حالت Tree به Directed Acyclic Graph (DAG) تبدیل می‌شود، مانند شکل ۸٫۷. در DAG ممکن است Loop هندسی در Graph دیده شود، اما هیچ مسیر Directed بسته‌ای وجود ندارد؛ دنبال‌کردن Directed Edgeها از هر Node سرانجام متوقف می‌شود. از نظر عملی کار با DAG تقریباً به سادگی Tree است.

شکل ۸٫۷ — مدل DAG یک Automobile.

در Model خودرو می‌توان اطلاعات Position هر Instance از Wheel Prototype را در Chassis Node، Wheel Node یا Edgeها نگه داشت. Tree و DAG هر دو روش Hierarchical برای بیان رابطهٔ Parent/Child میان بخش‌های مدل‌اند.

۸٫۳ بازوی ربات

Robotics نمونه‌های فراوانی برای Hierarchical Modeling فراهم می‌کند. بازوی سادهٔ شکل ۸٫۸(a) را می‌توان با سه Object ساده یا Symbol مدل کرد؛ مثلاً دو Parallelepiped و یک Cylinder. هر Symbol نیز از Primitiveهای پایه ساخته می‌شود.

شکل ۸٫۸ — بازوی Robot. (a) Model کامل. (b) Componentها.

بازوی Robot از سه بخش تشکیل شده است. Mechanism سه Degree of Freedom دارد: دو مورد با Joint Angle میان Componentها و سومین مورد با زاویهٔ Base نسبت به نقطه‌ای ثابت روی زمین توصیف می‌شود. در Model، هر Joint Angle تعیین می‌کند یک Component نسبت به Component متصل به آن چگونه Position شود؛ برای Base نیز زاویه، آن را نسبت به Environment تعیین می‌کند. هر Angle در Frame خود Component اندازه‌گیری می‌شود.

Base حول محور عمودی خود به اندازهٔ (\theta) Rotate می‌شود. Lower Arm با Jointی به Base متصل است و در صفحهٔ (z=0) در Frame خود به اندازهٔ (\phi) Rotate می‌شود. Upper Arm نیز با Joint مشابه به Lower Arm متصل است و در Frame خود به اندازهٔ (\psi) می‌چرخد. با تغییر این سه Angle می‌توان نوک Upper Arm را در سه بعد Position کرد.

برای Renderکردن Model بهتر است به‌جای تعریف مستقل Motion هر بخش، Transformationها را Incremental بسازیم. Base حول y با Matrix (R_y(\theta)) می‌چرخد.

Lower Arm باید ابتدا نسبت به Base تا Joint آن به اندازهٔ (T(0,h_1,0)) Translate شود و سپس در Frame خود با (R_z(\phi)) Rotate شود. چون Base نیز Rotate شده، Transformation کامل Lower Arm عبارت است از:

می‌توان (R_y(\theta)T(0,h_1,0)) را Positionکردن Frame Lower Arm نسبت به World و (R_z(\phi)) را Positionکردن آن نسبت به Base تعبیر کرد.

شکل ۸٫۹ — حرکت Componentها و Frameهای Robot.

برای Upper Arm نیز Translation (T(0,h_2,0)) نسبت به Lower Arm و سپس Rotation (R_z(\psi)) لازم است. بنابراین Matrix کامل:

Display Function با آرایهٔ theta[3] برای سه Angle نشان می‌دهد چگونه Model-View Matrix به‌صورت Incremental تغییر می‌کند:

void display()
{
    glClear(GL_COLOR_BUFFER_BIT);
    model_view = RotateY(theta[0]);
    base();
    model_view = model_view*Translate(0.0, BASE_HEIGHT, 0.0)
                           *RotateZ(theta[1]);
    lower_arm();
    model_view = model_view*Translate(0.0, LOWER_ARM_HEIGHT, 0.0)
                           *RotateZ(theta[2]);
    upper_arm();
    glutSwapBuffers();
}

Positioning بازو از جزئیات Geometry هر Part مستقل است. تا زمانی که Location Jointها تغییر نکند، می‌توان شکل Robot را فقط با تغییر Functionهای Draw سه بخش عوض کرد. این Separation اجازه می‌دهد تعریف Componentها و Animation جدا باشند.

شکل ۸٫۱۰ — Tree Structure بازوی Robot.

در برنامهٔ کامل می‌توان برای Base و Armها از سه Parallelepiped استفاده کرد. اگر Cube Code فصل ۳ و Instance Transformation به کار رود:

mat4 instance;
mat4 model_view;

void base()
{
   instance = Translate(0.0, 0.5*BASE_HEIGHT, 0.0)
              *Scale(BASE_WIDTH, BASE_HEIGHT, BASE_WIDTH);
   glUniformMatrix4fv(model_view_loc, 16, GL_TRUE, model_view*instance);
   glDrawArrays(GL_TRIANGLES, 0, N);
}

void upper_arm()
{
   instance = Translate(0.0, 0.5*UPPER_ARM_HEIGHT, 0.0)
              *Scale(UPPER_ARM_WIDTH, UPPER_ARM_HEIGHT, UPPER_ARM_WIDTH);

   glUniformMatrix4fv(model_view_loc, 16, GL_TRUE, model_view*instance);
   glDrawArrays(GL_TRIANGLES, 0, N);
}

void lower_arm()
{
   instance = Translate(0.0, 0.5*LOWER_ARM_HEIGHT, 0.0)
              *Scale(LOWER_ARM_WIDTH, LOWER_ARM_HEIGHT, LOWER_ARM_WIDTH);
   glUniformMatrix4fv(model_view_loc, 16, GL_TRUE, model_view*instance);
   glDrawArrays(GL_TRIANGLES, 0, N);
}

در هر بخش Cube با Scale به Size مطلوب می‌رسد و چون Vertexهای Cube حول Origin مرکز شده‌اند، با Translate بالا می‌رود تا کف آن روی (y=0) قرار گیرد. حاصل‌ضرب Model-View و Instance Transformation به Vertex Shader فرستاده می‌شود. چون Model-View برای هر بخش متفاوت است، هر Part پس از تنظیم Matrix خود Render می‌شود. چون همهٔ بخش‌ها Cube هستند، Vertex Data فقط یک بار به GPU ارسال می‌شود؛ اگر Symbolها متفاوت باشند، هر Drawing Function باید Draw Call مناسب خود را داشته باشد.

Tree شکل ۸٫۱۰ را می‌توان Data Structureای از Node و Edge دانست. اگر تمام Information در Node ذخیره شود، هر Node حداقل سه مورد دارد:

1. Pointer به Functionای که Object متناظر را Draw می‌کند؛
2. Homogeneous Matrix که Node و Childهایش را نسبت به Parent Position، Scale و Orient می‌کند؛
3. Pointerها به Childهای Node.

Node می‌تواند Attributeهای دیگری مانند Color، Texture و Material Property نیز داشته باشد.

شکل ۸٫۱۱ — نمایش Node شامل Draw، Matrix و Child Pointerها.

Drawکردن Object توصیف‌شده با چنین Treeای نیازمند Tree Traversal است. باید هر Node Visit شود، Matrix مؤثر بر Primitiveهای آن محاسبه و سپس Primitiveها نمایش داده شوند. برنامهٔ Robot نمونه‌ای Incremental از این Traversal است.

۸٫۴ Treeها و Traversal

شکل ۸٫۱۲ یک Humanoid ساده با ساختار Box-Like را نشان می‌دهد که برای Robot یا Virtual Reality مناسب است. اگر Torso را Root بگیریم، Figure با Tree شکل ۸٫۱۳ نمایش داده می‌شود. پس از Positionکردن Torso، Location و Orientation سایر Partها با Joint Angleها تعیین می‌شود؛ Animation نیز با تعریف Motion Jointها انجام می‌گیرد.

شکل ۸٫۱۲ — Figure انسان‌نما.

شکل ۸٫۱۳ — Tree Representation Figure انسان‌نما.

در Model ساده، Knee و Elbow ممکن است فقط یک Degree of Freedom داشته باشند، در حالی که Neck می‌تواند دو یا سه Degree of Freedom داشته باشد.

فرض کنید Functionهایی مانند head و left_upper_arm Partها را در Frame خود Draw می‌کنند. برای هر Node Matrixی می‌سازیم که Part را نسبت به Parent Position کند؛ درست مانند Robot Arm. اگر هر Body Part از قبل Size درست داشته باشد، این Matrix فقط Concatenation یک Translation و Rotation است.

در شکل ۸٫۱۴ Matrixها روی Edgeهای Tree نشان داده شده‌اند. هر Matrix تغییر Incremental از Parent به Child را بیان می‌کند.

شکل ۸٫۱۴ — Tree دارای Matrix روی Edgeها.

نکتهٔ مهم نحوهٔ Traversal Tree است. از نظر نظری می‌توان Depth-First یا Breadth-First Search به کار برد، اما برای مدل‌های گرافیکی استفاده از Algorithm ثابت مزیت دارد. در اینجا Treeها همیشه از چپ به راست و Depth-First پیمایش می‌شوند: از Left Branch تا عمیق‌ترین Node پایین می‌رویم، سپس بازمی‌گردیم و نخستین Right Branch را ادامه می‌دهیم. این ترتیب Pre-Order Traversal است.

Tree Traversal را می‌توان به دو روش نوشت. روش نخست Explicit است و Application با Stack، Matrixها و Attributeهای لازم را هنگام حرکت روی Tree ذخیره می‌کند. روش دوم Recursive است و Storage لازم به‌صورت Implicit توسط Call Stack انجام می‌شود. هر دو روش مفیدند و درک آن‌ها به طراحی Graphics System کمک می‌کند.

۸٫۴٫۱ Traversal مبتنی بر Stack

تابع figure ممکن است از Display Callback یا Mouse Callback برای Animation فراخوانی شود. Model-View Matrix اولیه M، Position Figure نسبت به Scene و Camera را تعیین می‌کند.

در Root، Torso با M Draw می‌شود. سپس Leftmost Branch تا Head طی می‌شود و Head با (MM_h) Render می‌گردد. بعد به Torso بازمی‌گردیم و Subtree دست چپ را طی می‌کنیم: Left Upper Arm با (MM_{lua}) و Left Lower Arm با (MM_{lua}M_{lla}). سپس Right Arm، Left Leg و Right Leg پردازش می‌شوند. هر بار که از یک Limb به Limb دیگر می‌رویم باید Matrix والد مناسب—اغلب M—بازیابی شود.

می‌توان این مسئله را با Current Transformation Matrix یعنی C دید. C ابتدا M است، برای Head به (MM_h) تغییر می‌کند و برای Nodeهای عمیق‌تر Matrixهای Incremental بیشتری در آن ضرب می‌شوند. چون هنگام بازگشت به Branch قبلی به Matrixهای قدیمی نیاز داریم، به‌جای Recomputeکردن آن‌ها از Stack استفاده می‌کنیم.

یک Matrix Stack ساده با ظرفیت ۵۰:

class matrix_stack
{
   public:
      static const int MAX = 50;
      matrix_stack() {index = 0;}
      void push(const mat4& matrix);
      mat4 pop();
   private:
      mat4 matrices[MAX];
      int index;
};

پیاده‌سازی Push/Pop:

void matrix_stack::push(const mat4& matrix)
{
   matrices[index] = matrix;
   index++;
}

mat4 matrix_stack::pop()
{
   index--;
   return matrices[index];
}

Traversal شامل Translation و Rotationهایی است که با Push و Pop کردن Model-View Matrix درهم‌آمیخته‌اند. ابتدای تابع figure می‌تواند چنین باشد:

mat4 model_view;
matrix_stack mvstack;
figure()
{
       mvstack.push(model_view);
       torso();
       model_view = model_view*Translate()*Rotate();
       head();

        model_view = mvstack.pop();
        mvstack.push(model_view);
        model_view = model_view*Translate()*Rotate();
        left_upper_arm();

        model_view = mvstack.pop();
        mvstack.push(model_view);
        model_view = Translate()*Rotate();
        left_lower_arm();

        model_view = mvstack.pop();
        mvstack.push(model_view);
        model_view = Translate()*Rotate();
        right_upper_arm();

        model_view = mvstack.pop();
        mvstack.push(model_view);
        .
        .
        .
}

اولین push یک کپی از Model-View Matrix جاری روی Stack می‌گذارد، بنابراین می‌توان Matrix جاری را آزادانه با Transformationهای بعدی تغییر داد و مطمئن بود نسخهٔ قبلی قابل بازیابی است. Translate و Rotate Matrix محلی Head یعنی (M_h) را ساخته و با Model-View اولیه Concatenate می‌کنند. پس از Drawکردن Head، pop Matrix اصلی را بازمی‌گرداند. Push دیگری لازم است تا نسخه‌ای از همان Matrix برای Branchهای بعدی نیز حفظ شود.

Functionهای Partها مشابه مثال Robot هستند. نمونهٔ torso:

void torso()
{
   mvstack.push(model_view);
   instance = Translate(0.0, 0.5*TORSO_HEIGHT,0.0)
                       *Scale(TORSO_WIDTH, TORSO_HEIGHT, TORSO_WIDTH);
   glUniformMatrix4fv(model_view_loc, 16, GL_TRUE, model_view*instance);
   colorcube();
   glDrawArrays(GL_TRIANGLES, 0, N);
   model_view = mvstack.pop();
}

Push در آغاز و Pop در پایان Function، State Changeهای داخلی را ایزوله می‌کند تا سایر بخش‌های Program تحت تأثیر قرار نگیرند. برنامهٔ کامل ضمیمهٔ A این Figure را با Menu برای تغییر Joint Angleها پیاده می‌کند و Partها را با Parallelepiped می‌سازد؛ کل Model را نیز می‌توان با روش فصل ۵ Shade کرد.

Attributeهایی مانند Color و Material Property نیز State Variable هستند: پس از Setشدن تا وقتی تغییر نکنند باقی می‌مانند. اگر torso Color را قرمز و head آن را آبی کند، بدون مدیریت State ممکن است همهٔ Nodeهای بعدی نیز آبی Render شوند و این State حتی پس از خروج از figure باقی بماند. در اینجا Traversal Order مستقیماً بر نتیجه اثر دارد.

راه‌حل، Stackهای مشابه برای Attributeهاست. Attributeها هنگام ورود به figure Push و هنگام خروج Pop می‌شوند تا State اصلی بازگردد. Push/Popهای اضافی در داخل Tree نیز می‌توانند Scope دقیق Attributeها را کنترل کنند.

در Model پیچیده‌تر همین ایده Recursive می‌شود. مثلاً Head می‌تواند خود یک Hierarchical Model شامل Eye، Ear، Nose و Mouth باشد و Function آن Stack Matrix/Attribute داخلی خودش را مدیریت کند.

اگر دو یا چند Node به Function یکسان اشاره کنند، Structure در واقع DAG است، اما Traversal DAG در این چارچوب دشواری تازه‌ای ایجاد نمی‌کند.

روش Explicit مبتنی بر Stack قابل استفاده است ولی محدودیت دارد: Application Programmer باید Push/Popها را دقیق و دستی بنویسد؛ Structure برای Example خاص Hard-Coded می‌شود و Dynamic Extension دشوار است. همچنین مرز روشن میان ساخت Model و Rendering Model وجود ندارد. اکنون به روشی عمومی‌تر بر پایهٔ Tree Data Structure می‌رویم.

۸٫۵ استفاده از Tree Data Structure

در روش دوم، Hierarchy با یک Tree Data Structure استاندارد نمایش داده می‌شود و Renderer با Traversal Algorithmی مستقل از Model آن را رسم می‌کند. ساختار مورد استفاده Left-Child, Right-Sibling است.

در نمایش شکل ۸٫۱۵، همهٔ Nodeهای یک Level از چپ به راست به‌صورت Sibling Link شده‌اند. Childهای یک Node نیز List دیگری از Leftmost Child تا Rightmost Child می‌سازند. این Structure Hierarchy را نشان می‌دهد، اما هنوز Graphical Information لازم را باید در Nodeها ذخیره کنیم.

شکل ۸٫۱۵ — (a) Tree. (b) نمایش Left-Child, Right-Sibling.

هر Node باید Function تعریف Object و Homogeneous Matrix Position آن نسبت به Parent را داشته باشد:

typedef struct treenode
{
   mat m;
   void (*f)();
   struct treenode *sibling;
   struct treenode *child;
} treenode;

آرایهٔ m یک Homogeneous Matrix (4\times4) ذخیره می‌کند. هنگام Render Node، ابتدا این Matrix در Model-View Matrix جاری ضرب می‌شود و سپس Function f که Primitiveها را ایجاد می‌کند اجرا می‌شود. Pointer به Sibling سمت راست و Leftmost Child نیز ذخیره می‌شود؛ اگر وجود نداشته باشند مقدار NULL استفاده می‌شود.

برای Figure انسان‌نما ۱۰ Node متناظر با ده Part تعریف می‌کنیم:

treenode torso_node, head_node, lua_node, rua_node, lll_node,
        rll_node, lla_node, rla_node, rul_node, lul_node;

Root یعنی Torso می‌تواند حول y Rotate شود:

torso_node.m = RotateY(theta[0]);
torso_node.f = torso;
torso_node.sibling = NULL;
torso_node.child = &head_node;

Drawing Function Torso با Cube:

void torso()
{
   mvstack.push(model_view);
   instance = Translate(0.0, 0.5*TORSO_HEIGHT, 0.0)
                      *Scale(TORSO_WIDTH, TORSO_HEIGHT, TORSO_WIDTH);
   glUniformMatrix4fv(model_view_loc, 16, GL_TRUE, model_view*instance);
   colorcube();
   glDrawArrays(GL_TRIANGLES, 0, N);
   model_view = mvstack.pop();
}

Instance Transformation ابتدا Cube را Scale و سپس Translate می‌کند تا کف آن روی (y=0) قرار گیرد.

برای Left Upper Arm:

lua_node.m = Translate(-(TORSO_WIDTH+UPPER_ARM_WIDTH),
                             0.9*TORSO_HEIGHT, 0.0)*RotateX(theta[3]);
lua_node.f = left_upper_arm;
lua_node.sibling = &rua_node;
lua_node.child = &lla_node;

Function آن:

void left_upper_arm()
{
   mvstack.push(model_view);
   instance = Translate(0.0, 0.5*UPPER_ARM_HEIGHT, 0.0)
                        *Scale(UPPER_ARM_WIDTH, UPPER_ARM_HEIGHT, UPPER_ARM_WIDTH);
   glUniformMatrix4fv(model_view_loc, 16, GL_TRUE, model_view*instance);
   colorcube();
   glDrawArrays(GL_TRIANGLES, 0, N);
   model_view = mvstack.pop();
}

Upper Arm باید نسبت به Torso و Width خودش Translate شود تا Center of Rotation درست قرار گیرد. Node آن هم Sibling یعنی Right Upper Arm و هم Child یعنی Left Lower Arm دارد. سایر Nodeها نیز مشابه تعریف می‌شوند.

Preorder Traversal Tree با Recursion بسیار کوتاه است:

void traverse(treenode* root)
{
   if (root == NULL) return;
   mvstack.push(model_view);
   model_view = model_view*root->m;
   root->f();
   if (root->child != NULL) traverse(root->child);
   model_view = mvstack.pop();
   if (root->sibling != NULL) traverse(root->sibling);
}

برای Render Node غیر NULL، State فعلی ذخیره می‌شود، Matrix محلی Node در Model-View ضرب می‌گردد، Function f Object را Draw می‌کند و سپس Childها با همین Matrix تغییرکرده Traversal می‌شوند. اما Sibling باید از Matrix Parent آغاز کند؛ بنابراین قبل از رفتن به Sibling، State با pop بازیابی می‌شود.

اگر Attributeها در Node تغییر کنند، می‌توان آن‌ها را داخل Rendering Function یا هم‌زمان با Model-View Matrix Push/Pop کرد. مزیت مهم این روش آن است که Traversal Function کاملاً از Tree خاص مستقل است و می‌توان یک Display Callback عمومی برای Modelهای مختلف داشت.

Display Callback عمومی می‌تواند بسیار ساده باشد:

void display(void)
{
  glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);
  traverse(&torso_node);
  glutSwapBuffers();
}

Animation همچنان با Joint Angleها انجام می‌شود. Angle از Menu انتخاب و با Mouse Button افزایش/کاهش می‌یابد. Mouse Callback Angle را عوض می‌کند، Matrix Node متناظر را دوباره می‌سازد و Redisplay درخواست می‌کند:

mymouse(int button, int state, int x, int y)
{
     if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN)
     {
         theta[angle] += 5.0;
         if (theta[angle] > 360.0 ) theta[angle] -= 360.0;
     }
     if (button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN)
     {
         theta[angle] -= 5.0;
         if (theta[angle] < 360.0 ) theta[angle] += 360.0;
     }

      mvstack.push(model_view);
      switch (angle)
      {
      case 0 :
           torso_node.m = RotateY(theta[0]);
           break;
      case 1 : case 2 :
           head_node.m = Translate(0.0, TORSO_HEIGHT+0.5*HEAD_HEIGHT, 0.0)
               *RotateX(theta[1])*RotateY(theta[2])
               *Translate(0.0, -0.5*HEAD_HEIGHT, 0.0);
           break;
       // rest of cases
       }
}

این روش قابلیت دیگری نیز دارد: به‌جای Nodeهای Static می‌توان هنگام اجرای Program، Nodeها را Dynamic ایجاد یا حذف کرد:

typedef treenode* tree_ptr;
tree_ptr torso_ptr = new treenode;

Nodeهای Dynamic مانند قبل مقداردهی می‌شوند و Traversal با Pointer Root انجام می‌شود:

lua_node->m = Translate(-(TORSO_WIDTH+UPPER_ARM_WIDTH),
                        0.9*TORSO_HEIGHT, 0.0)*RotateX(theta[3]);
lua_node->f = left_upper_arm;
lua_node->sibling = &rua_node;
lua_node->child = &lla_node;

traverse(torso_ptr);

برای Figure ثابت مزیت خاصی ندارد، اما در Application عمومی اجازه می‌دهد Structure به‌صورت Interactive تغییر کند؛ مثلاً Editorی برای افزودن و حذف Body Partها. همین ایده پایهٔ Scene Treeهایی است که بعداً بررسی می‌شوند.

Traversal Order در مثال‌ها ثابت است. Algorithm دیگری ممکن است در صورت وجود State Changeهایی مانند Transformation یا Attribute، Image متفاوتی بسازد. Push/Pop دقیق Matrix و Attribute در هر Node می‌تواند این وابستگی را کاهش دهد، البته با Performance Cost.

۸٫۶ Animation

Robot Arm و Figure ما Articulated Model هستند: مجموعه‌ای از Rigid Partها که با Joint متصل شده‌اند. با تغییر مجموعه‌ای کوچک از Parameterها می‌توان Position آن‌ها را در زمان عوض کرد و Animation ساخت. Hierarchical Model به‌طور طبیعی Compound Motion و رابطهٔ فیزیکی Partها را حفظ می‌کند. پرسش باقی‌مانده این است که Parameterها در زمان چگونه تغییر کنند تا Motion مطلوب حاصل شود.

در Robot، هدف را حرکت نوک Upper Arm از Positionی به Position دیگر فرض کنید. Model سه Degree of Freedom، یعنی سه Angle، دارد. هر مجموعه Angle یک Tip Position یکتا تولید می‌کند، اما عکس آن صادق نیست: برای یک Position هدف ممکن است هیچ Solution، یک Solution یا چند مجموعه Angle وجود داشته باشد.

مطالعهٔ Kinematics Position اجزای Model را فقط بر اساس Joint Angleها توصیف می‌کند. Hierarchical Model می‌تواند Position را عددی یا با Equation صریح محاسبه کند.

اگر (\theta) آرایهٔ Joint Angleها و p آرایهٔ Vertexهای Model باشد، Kinematic Model فرم کلی

دارد. اگر Joint Velocityها نیز داده شوند، Velocity نقاط Model را می‌توان به دست آورد.

Kinematic Model اثرهایی مانند Inertia و Friction را نادیده می‌گیرد. برای Dynamic Behavior بر حسب Forceهای اعمالی به Differential Equationهای پیچیده‌تر نیاز است؛ موضوعی مهم در Robotics.

Kinematics و Dynamics رفتار Forward را توصیف می‌کنند، اما در Animation اغلب با Inverse Kinematics و Inverse Dynamics روبه‌رو هستیم: Given State مطلوب، Joint Angleها چگونه تنظیم شوند؟

اول باید معلوم شود آیا Sequenceای از Angleها وجود دارد که State هدف را ایجاد کند. به‌طور کلی تابع تک‌مقداری

وجود ندارد. برای یک p ممکن است هیچ (\theta)، یک (\theta) یا چند Solution وجود داشته باشد. حتی اگر Sequence پیدا شود باید مطمئن شد در مسیر، Model با Obstacle برخورد نمی‌کند و Constraintهای فیزیکی نقض نمی‌شوند. برای Robot ساده شاید Equationهای Inverse قابل یافتن باشند، اما Figure با ۱۱ Degree of Freedom دشواری مسئله را نشان می‌دهد.

راه‌حل بنیادی از Traditional Hand Animation می‌آید: Key-Frame Animation. Animator Objectها را در زمان‌های انتخابی، یعنی Key Frameها، Position می‌کند و Frameهای میانی با In-Betweening ساخته می‌شوند. در Computer Graphics می‌توان Joint Angleها را میان Key Frameها Interpolate کرد یا Dynamic Equationهای سادهٔ تقریبی بین آن‌ها ساخت. GPUهای جدید بخشی از In-Betweening را در Pipeline خودکار می‌کنند. Spline Curveهای فصل ۱۰ نیز Transitionهای نرم میان Key Frameها فراهم می‌کنند. بااین‌حال انتخاب Key Frame و Pose مناسب همچنان به Animator ماهر یا Interactive Tool خوب نیاز دارد.

۸٫۷ Graphical Objectها

تا اینجا چند Graphics Paradigm معرفی کرده‌ایم، اما توسعهٔ اصلی بر Pipeline Implementation مدل Synthetic Camera متمرکز بوده است، زیرا هدف Applicationهای Interactive سه‌بعدی با Hardware/Software موجود است. در نتیجه معمولاً Geometric Data روی GPU قرار می‌گیرد و تقریباً بلافاصله Render می‌شود. هنوز از این قابلیت که Data پس از Upload می‌تواند بدون Regenerateشدن چند بار استفاده شود، کاملاً بهره نبرده‌ایم.

همچنین تمرکز بر Implementation Detail باعث شده سطح Abstraction پایین باقی بماند. اکنون دو مفهوم سطح بالاتر معرفی می‌شوند. نخست، مفهوم Object را از Geometric Objectهایی مانند Polygon و Vector به تقریباً همهٔ عناصر Graphics Program—Viewer، Light، Material Property و غیره—گسترش می‌دهیم. دوم، روی Objectهایی تمرکز می‌کنیم که پس از Drawشدن Image نیز وجود دارند، حتی اگر اصلاً Display نشوند.

می‌توان از Classهای C++ یا Structureهای C برای این Layer استفاده کرد. OpenGL مستقیماً Object-Oriented Model کامل ارائه نمی‌کند، اما همچنان Renderer زیرین است و Layer نرم‌افزاری بالاتری روی آن ساخته می‌شود.

۸٫۷٫۱ Method، Attribute و Message

Programها Data را Manipulate می‌کنند؛ از Number و String تا Geometric Entity. در Imperative Programming، Functionها Data را از طریق Parameter دریافت، تغییر و Result را برمی‌گردانند. برای Manipulateکردن Data، Function باید Structure داخلی آن را بداند.

Cube مثال‌های قبلی را می‌توان با Vertex Pointer، Edge List یا List رأس‌های Polygon نمایش داد. Application Programmer ممکن است نخواهد هیچ‌کدام از این Representation Detailها را بداند و Cube را یک Atomic Object ببیند. حتی ممکن است جزئیات Rendering مانند Shading Model یا Polygon Fill Algorithm نیز برای او مهم نباشد؛ Cube می‌تواند مفهومی «بداند چگونه خودش را Render کند».

OpenGL تا حدی با State این دیدگاه را پشتیبانی می‌کند: Color، Orientation و Lightهای مؤثر می‌توانند جزو Graphics State باشند و از Representation داخلی Cube مستقل بمانند.

اما برای یک Physical Cube، ویژگی‌هایی مانند Location، Color، Size و Orientation به خود Object وابسته‌اند. در OpenGL می‌توان بخشی از این رفتار را با Push/Pop Attribute و Matrix تقلید کرد، ولی Programming Model پایه برای آن طراحی نشده است. Function تبدیل Cube باید دقیقاً Representation آن را بشناسد؛ الگوی Imperative شکل ۸٫۱۶ همین است.

شکل ۸٫۱۶ — Paradigm برنامه‌نویسی Imperative: Application → Data/Function → Result.

Application Functionی می‌نویسد که Pointer به Cube Data و Transformation Parameterها را می‌گیرد، Data را Manipulate و Control را برمی‌گرداند.

Object-Oriented Design مسئله را متفاوت می‌بیند. زبان‌هایی مانند Smalltalk از ابتدا Computer Graphics را نمونه‌ای مناسب برای قدرت این رویکرد می‌دانستند. می‌توان Pipeline Orientation و Object Orientation را ترکیب کرد و Graphics Systemهایی هم Expressive و هم High-Performance ساخت.

در Object-Oriented Programming، Object Module سازندهٔ Program است. Module شامل Data تعریف‌کنندهٔ Object، Property/Attributeها و Function/Methodهایی است که Object و Attributeهایش را Manipulate می‌کنند. برای Invokeکردن Method، Message به Object فرستاده می‌شود.

شکل ۸٫۱۷ — Paradigm شی‌گرا: Application Message را به Object می‌فرستد و Object Method مناسب را اجرا می‌کند.

مزیت برای Application Programmer این است که لازم نیست Representation داخلی Cube را بداند؛ فقط Interface و Messageهایی را که Object پشتیبانی می‌کند می‌شناسد.

C struct بخشی از ویژگی‌های Object را دارد، اما C قدرت کامل Object-Oriented Approach را ندارد. در C++، class جایگاه اصلی برای تعریف Object است و قابلیت‌های مهم Encapsulation و Inheritance را فراهم می‌کند.

۸٫۷٫۲ یک Cube Object

فرض کنید بخواهیم در C یک Cube Object با Color Attribute و Homogeneous Transformation مرتبط بسازیم. می‌توان از struct استفاده کرد:

struct cube
{
   float color[3];
   float matrix[4][4];

/* implementation goes here */

}

بخش Implementation نحوهٔ Representation واقعی Cube را نگه می‌دارد. Application Programmer معمولاً لازم نیست آن را بداند و فقط Color یا Matrix مربوط به Cube را تغییر می‌دهد.

پس از تعریف Structure می‌توان Instanceها را مانند Typeهای پایه ساخت:

cube a, b;

Attributeها برای هر Instance مستقل‌اند. برای قرمزکردن Cube a:

a.color[0] = 1.0;
a.color[1] = a.color[2] = 0.0;

چنین Structی به‌سادگی در OpenGL قابل پیاده‌سازی است. اما Manipulate/Renderکردن Object هنوز محدود است. مثلاً برای Rendering:

render_cube(a);

و برای Rotation:

rotate_cube(a, theta, d);

که d محور Rotation است.

این روش عملی است اما برای هر Object Type به Functionهای مجزای Render و Rotate نیاز دارد و بخش Implementation برای Application قابل دسترسی است. C++ Class هر دو مشکل را کاهش می‌دهد. Memberها می‌توانند public، private یا protected باشند؛ Private Memberها از Functionهای بیرونی پنهان‌اند و Protected Memberها برای Classهای همان Hierarchy قابل دسترسی‌اند. friend نیز Access انتخابی می‌دهد.

تعریف Cube:

class cube
{
  public:
    vec4 color;
    mat4 model;
  private:

/* implementation goes here */

}

C++ اجازه می‌دهد Methodها نیز Member Class باشند. برای مثال:

void render();
void translate(float x, float y, float z);
void rotate(float theta, float axis_x, float axis_y,
             float axis_z);

Application:

cube a;
a.rotate(45.0, 1.0, 0.0, 0.0);
a.translate(1.0, 2.0, 3.0);
a.render();

از دید Object-Oriented، Cube «می‌داند» چگونه خودش را Rotate و Render کند و a.rotate Messageای به Object برای اجرای Method مربوط است. Rotate/Translate Method می‌توانند Matrix Member را با Functionهای Transformation خودمان تغییر دهند.

a.render باید Object پایدار را از State خود Object Render کند، نه صرفاً Graphics State جاری. Object و Attributeهایش در System باقی می‌مانند و Methodها آن‌ها را تغییر می‌دهند.

Render Method دادهٔ لازم را به GPU می‌فرستد؛ Vertex Attributeها از Private Implementation Object می‌آیند و Draw Call مانند glDrawArrays Object را نمایش می‌دهد.

۸٫۷٫۳ پیاده‌سازی Cube Object

یک Implementation پایه می‌تواند مشابه Rotating Cube قبلی باشد: شش Face، هر Face دو Triangle. Private Data:

private:
      vec4 points[36];
      vec4 colors[36];

این ساختار Color متفاوت برای هر Vertex را نیز مجاز می‌کند. Constructor می‌تواند points را با Unit Cube پیش‌فرض مقداردهی کند.

اما می‌توان Information بیشتری ذخیره کرد که Rendering را بهینه کند. OpenGL Hidden-Surface Removal را با z-Buffer درست انجام می‌دهد، ولی گاهی می‌توان Objectهای نامرئی را زودتر با Visibility Test حذف کرد. برای این کار می‌توان Bounding Volume ذخیره کرد؛ مثلاً Axis-Aligned Bounding Box با Min/Max مختصات x، y و z رأس‌ها پس از Transformation.

۸٫۷٫۴ Object و Hierarchy

مزیت مهم Object-Oriented Design، Code Reuse و ساخت Objectهای پیچیده از مجموعه‌ای کوچک از Objectهای ساده است. مانند بخش ۸٫۴ می‌توان Figure Object را از Cubeها ساخت و چند Instance از Figure داشت که هر کدام Color، Size، Location و Orientation مستقل دارند. Humanoid Class می‌تواند Arm/Leg Classها را در خود داشته باشد و Car Class از Wheel و Chassis ساخته شود؛ بنابراین Representationهای Tree-Like دوباره ظاهر می‌شوند.

در Treeهای Composition، رابطهٔ Parent/Child معمولاً has-a است: Figure «دو Arm و دو Leg دارد» و Car «چهار Wheel و یک Chassis دارد».

Hierarchy را می‌توان به‌شکل دیگری نیز دید که Simple Objectها بالای Hierarchy هستند و رابطه Parent/Child از نوع is-a است؛ همان الگوی Taxonomy. Mammal یک Animal است، Human یک Mammal است. در Projection نیز Parallel Projection یک Planar Geometric Projection و Oblique Projection نوعی Parallel Projection است.

Inheritance اجازه می‌دهد Subclass رفتار Base Class را استفاده و فقط بخش لازم را Refine کند. برای مثال اگر Code عمومی Parallel Projection نوشته شده باشد، Oblique Projection می‌تواند همان Code را Inherit و فقط قسمت‌های مخصوص خود را تغییر دهد. Geometric Objectهای پایه نیز می‌توانند Propertyهای پیش‌فرض مانند Color و Material داشته باشند که Subobjectها آن‌ها را استفاده یا Override کنند. C++ با Subclass و Inheritance از این مفهوم پشتیبانی می‌کند.

۸٫۷٫۵ Geometric Objectها

در ساخت یک Object-Oriented Graphics System، Point، Vector، Polygon، Rectangle و Triangle Candidateهای طبیعی Object هستند. اما دربارهٔ Attribute، Light Source و Viewer انتخاب‌های مختلفی وجود دارد. مثلاً Material Property می‌تواند مستقیماً Member Cube باشد یا خودش Object مستقلی تعریف شود.

Class ماده:

class material
{
  public:
    vec4 specular;
    float shininess;
    vec4 diffuse;
    vec4 ambient;
}

سپس Material به Geometric Object اختصاص می‌یابد:

cube a;
material b;
a.setMaterial(b);

Light Source نیز خود ویژگی‌های هندسی مانند Position و Orientation دارد و می‌تواند به‌صورت Object مستقل مدل شود. این گسترش، Model را از مجموعه‌ای صرفاً هندسی به Sceneای متشکل از Objectهای دارای State و Behavior تبدیل می‌کند.