8.6 مقدمة نظرية عن الرسم ثلاثي الأبعاد كتاب لينكس الشامل >>

8.6 مقدمة نظرية عن الرسم ثلاثي الأبعاد

8.6.1 تمثيل النقطة

جميع طرق تمثيل الرسوم في الفراغ(العالم) ثلاثي الأبعاد هي طرق متجهية وليست نقطية Bitmap لأن المصفوف المكونة من صفوف وأعمدة لا يمكن أن تمثل صور ثلاثية الأبعاد، ولأن الشاشة هي صفوف وأعمدة فقط. تمثل النقاط ثلاثية الأبعاد بثلاث أرقام مرتبة تسمى إحداثيات وهي القياس عن ثلاث محاور(مساطر) متقاطعة في نقطة الأصل(الصفر) ومتعامدة تسمى X و Y و Z على الترتيب ، وليس مهما أن يكون X أفقياً أو عامودياً أو في العمق ، ولا غيره المهم أن يكون نظام الإحداثيات يحقق قاعدة اليد(أو القبضة) اليمنى أي إذا أمسكت المحور Z بقبضتك وكان الإبهام يشير إلى الإتجاه الموجب له فإن إتجاه انحناء الأصابع يشير إلى الإتجاه من X إلى Y.

tipتلميح

يوجد طرق تمثيل أخرى تستخدم في الغالب لتسهيل بعض التكاملات الرياضية، ولكنها خارج موضوع هذا الفصل.

لتسهيل الحسابات تمثل النقطة بمصفوفة عامودية بثلاث صفوف هي الإحداثيات X و Y و Zعلى الترتيب ، ولتسهيل الكتابة تكتب المصفوفة أحياناً على شكل صف وليس عامود ويوضع الرمز T ليدل أنها مقلوبة 90 درجة مثلاً [1 2 3]T يقصد بها النقطة التي احداثياتها 1 و 2 و 3 على الترتيب. ويتم تمثيل الأشكال المختلفة بتقسيمها إلى مضلعات(غالباً مثلثات أو رباعيات) رؤوسها نقاط ثلاثية الأبعاد.

تمثل الإتجهات في الفراغ ثلاثي الأبعاد والذي نسميه متجهاً بثلاث أرقام أيضاً، وهي ناتج طرح نقطة البداية من نقطة النهاية وينتج من الطرح ثلاث إحداثيات عند تمثيلها نراها وكأن المتجه تم نقله لنقطة الأصل(الصفر) ، هذا المتجه له طول يتحدد بجمع مربعات إحداثياته وأخذ جذرها الثاني. فإذا قسمنا المتجه على طوله نحصل على متجه طوله وحدة واحدة نسميه متجه وحدة. أهم متجهات الوحدة المعروفة هي متجهات الوحدة القياسية التي تشير للإتجاه الموجب للمحاور الثلاثة أي [1 0 0]T و [0 1 0]T و [0 0 1]T

tipتلميح

جمع أو طرح متجه مع آخر يكون بجمع أو الطرح الإحداثيات المتناظرة
[a b c]T+[d e f]T=[(a+d) (b+e) (c+f)]T وضربها أو قسمتها في/على عدد يكون بضرب أو قسمة كل إحداثي فيها. وهذا ينطبق على المصفوفات ككل وليس على المتجهات فقط

8.6.2 الإسقاط

حتى نتمكن من عرض الشكل على الشاشة فنحن بحاجة لإسقاطه وهناك أنواع من الإسقاط أولهما الإسقاط العامودي Orthogonal Projection ويكون ذلك فقط بحذف أحد الإحداثيات ويسمى المسقط باسم الإحداثين الباقيين مثلاً المسقط X-Y ويكون هذان الإحداثيين هما إحداثيان على الشاشة كمستوى ديكارتي ثنائي الأبعاد مركزه الزاوية اليسرى الدنيا. بتغيير الإحداثي الذي ستحذفه يكون لديك 3 مساقط عامودية تسمى أمامي وجانبي وعلوي. وهي طريقة سريعة تستخدم أثناء التصميم (حتى لا يضيع الكثير الوقت) وفي ألعاب RPG أو تلك التي يكون المشهد دائماً من نفس الزاوية (من أعلى مثلاً) ولا يظهر العمق فيها.

وبطريقة مشابهة بعض الألعاب تستخدم إسقاط زائف بالعلاقة (x,y,z) -> (x-y,y-z) لتكون صورة تظهر وكأنها ثلاثية الأبعاد. ويمكن هنا تحريك الكاميرا فإذا كانت الكاميرا على النقطة (X,Y,Z) فإن صورة أي نقطة تكون (x,y,z) -> (x-y-X+Y,y-z-Y+Z) هنا لا يمكننا تغيير زاوية النظر ولا يظهر العمق (الأشياء البعيدة لها نفس حجم القريبة) لكنها طريقة سريعة ويمكن بسهولة لصق صور معدة مسبقاً أي صور ثلاثية الأبعاد يتم رسمها وإسقاطها مسبقاً وتخزينها كصور ثنائية الأبعاد وعند الحاجة لعرضها يتم اسقاط إحداثيات طرفها وعررضها عند النقطة الناتجة لأنه كما قلنا لا يتغيّر شكلها بتغيّر مكانها أو عمقها ويتم إسقاط الأجسام بالترتيب الأسفل أولاً ثم الأعمق فالأيسر أولاً.

(start)->->->->
      ->->->->
     ->->->->
    ->->->->(end)
وتفيد هذه في ألعاب RPG والألعاب الاستراتيجية كما تستخدم في كتب الهندسة الإقليدية وكتب الرياضيات الأخرى لأن الخطوط المتوازية تبقى كذلك بعد اسقاطها.

fake 3D projection

الطريقة الإخرى في الإسقاط هي الإسقاط البعدي Perspective Projection الذي يشبه إسقاط المشهد على فيلم في كاميرا التصوير(الفيلم هو الشاشة). الفرق الأساسي هنا عن الإسقاط العامودي أن الأجسام الأبعد عن الكاميرا تصبح أصغر، ويتم عمل ذلك بتحديد نقطة وجود الكاميرا والإتجاه الذي تنظر إليه والإتجاه العامودي وزاوية الرؤيا وتصحيح نسبة الإحداثي العامودي إلى الأفقي لتفهم ذلك تخيل هرماّ مربع القاعدة رأسه الكاميرا ويتجه نحو المشهد (نحدد هذا الإتجاه بمتجهين الأول هو إلى داخل المشهد والآخر الإتجاه الرأسي) ما يقع داخل هذا الهرم هو ما يتم إسقاطه على الفيلم. قد تقسم بعض المكتبات هذه العملية إلى عمليتين بحيث تفترض مكان وإتجاه ثابتين للكاميرا فتكون العملية الأولى نقل المشهد إلى فراغ(عالم) الكاميرا (بدلاً من تحريك الكاميرا نحرك العالم) تتبعها عملية أخرى هي الإسقاط. هذا الفصل جاء فقط لتسهيل وتسريع عملية الإسقاط إذا افترضنا أن كاميرا موجودة على [0 0 0]T تنظر باتجاه [0 0 -1]T بحيث يكون الإتجه [0 1 0]T هو الإرتفاع العامودي وتكون زاوية الرؤيا 90 درجة فإن إسقاط النقطة [X Y Z]T إلى الشاشة ثنائية الأبعاد يعطى بالعلاقة [-X/Z -Y/Z]T (لاحظ أن النقطة الأبعد ستصبح أقصر وأقرب للوسط لأننا نقسم على Z) ونتوقع جواب يكون بين سالب واحد وموجب واحد ولتحويله إلى شاشة تبدأ من [صفر صفر] وتمتد إلى عرض W وطول H فإننا نجمع واحد ثم نضرب في نصف الطول أو العرض فتصبح العلاقة [(1-X/Z)*W/2 (1-Y/Z)*H/2]T تسمى عملية تحديد نقطة البداية وطول وعرض الشاشة setting view port كل هذا ونحن نفترض مكان وإتجاه محددين للكاميرا وزاوية رؤيا محددة فتخيل أنت العلاقة الكاملة دفعة واحدة.

الإسقاط الذي ذكرناه يكون لنقطة واحدة ولإسقاط جسم نسقط كل نقطة مكونة لمضلعاته ثم نرسم المضلعات. هنا تظهر مشكلة أخرى وهي كيف نخفي الجزء من المضلعات الذي يقع تحت مضلع آخر أحد الحلول هي بأن ترتب الأجسام حسب قربها من الكاميرا وترسم الأبعد أولاً فعند رسم شكل فوق آخر على الشاشة فإن ما يرسم أخيراً (الأقرب) هو الذي يظهر ويخفي ما تحته هذه الطريقة تسمى scanline sorting. هذا الحل ليس كاملاً لأن الأجسام التي تتقاطع أو التي يكون جزء منها أقرب وجزء أبعد لا تحل بهذه البساطة. الطريقة الأفضل هي طريقة z-buffer التي تقوم على حجز ذاكرة على شكل مصفوفة بنفس حجم(طول وعرض) الشاشة التي نسقط عليها أي حجمها WxH عناصر هذه المصفوفة هي أرقام يمثل الواحد منها العمق(في فراغ الكاميرا وليس العالم) لأقرب نقطة تم رسمها في ذلك المكان، فيصبح لدينا للنقطة [x y]T ما يقابله من لون RGB و Z الأخيرة في ال z-buffer والأُول في frame-buffer. وعند رسم مضلع يتم إسقاطه رؤوسه إلى الشاشة ثم رسم كل النقاط داخله التي يكون z فيها أقرب من تلك المخزنة في ال z-buffer ثم تحديث قيم z للتي تم رسمها. هذه التعقيدات تقوم بها المكتبة وكل ما عليك هو مسح ال z-buffer بقيم استهلالية بعيدة جداً قبل بداية الرسم.

8.6.3 العمليات الأساسية

العمليات الأساسية على النقاط أو المتجهات هي

الإزاحة translation
أي تحريك النقطة بمقدار متجه آخر(مثلاً p) وتتم بجمعهما معها. ونرمز لها T(p)
التحجيم Scaling
أي أطالة أو تقصير طور المتجه (بعد النقطة عن الأصل) وذلك بضرب احداثياته برقم ثابت نرمز له ب s.
اللف Rotation
أي لف(فتل/برم/تدوير) النقطة حول نقطة الأصل للقيام بها تضرب بالنقطة مصفوفة 3×3 تحتوي أعمدتها متجهات الوحدة القياسية ( [1 0 0]T و [0 1 0]T و [0 0 1]T ) بعد لفها بنفس الزاوية ولكن بعكس الإتجاه (مع عقارب الساعة أو عكسها) فإذا أسمينا المصفوفة A والنقطة p تكون العلاقة Axp
لتوضيح آخر عملية لنفترض أنك تريد مصفوفة تقوم باللف بزاوية مقدارها h بالإتجاه الموجب (عكس عقارب الساعة) حول محور z افترض أن H=-h أي أن H هي الزاوية بعكس الإتجاه نلاحظ أن متجه [0 0 1]T لن يتغير لأنه محور الدوران أما المتجه [1 0 0]T فسيصبح [cos(H) sin(H) 0]T أي [cos(-h) sin(-h) 0]T ومنه [cos(h) -sin(h) 0]T والمتجه الأخير [0 1 0]T سيصبح [-sin(H) cos(H) 0]T أي [sin(h) cos(h) 0]T بعد تدويرهما بمقدار H.أي أن المصفوفة هي
 /                 \
| +cos(h) -sin(h) 0 |
| +sin(h) +cos(h) 0 |
|   0       0     1 |
 \                 /

tipتلميح

يكون ضرب مصفوفتين معاً بضرب عناصر كل صف في الأولى بعناصر كل عمود من الثانية ثم جمع الناتج. أي أن العنصر Cij من ناتج ضرب AxB هو : sum[k=1 to m](Aik*Bkj)

وللقيام بعمليات أكثر تعقيداً نستخدم أربع احداثيات للنقطة كما يلي [X Y Z 1]T وقبل أن تسأل لماذا هذا الواحد، فاعلم أننا نستعمل مصفوفة 4×4 لنضربها بالنقطة لتقوم بالوظائف الثلاث السابقة كما يلي

 Translate    Scale     Rotate
 /       \  /       \  /       \
| 0 0 0 0 || s 0 0 0 || ix jx kx 0 |
| 0 0 0 0 || 0 s 0 0 || iy jy ky 0 |
| 0 0 0 0 || 0 0 s 0 || iz jz kz 0 |
| X Y Z 1 || 0 0 0 1 || 0 0 0 1 |
 \       /  \       /  \       /
فإذا أردنا القيام بعملية أكثر تعقيداً مكونة من سلسة من العمليات السابقة فإننا نحصل على المصوفة التي تقوم بذلك العمل بضرب المصفوفات التي تقوم بتلك العمليات مثلاً إذا كانت المصفوفة A تقوم بتدوير النقطة 30 درجة حول محور z والمصفوفة B تقوم بتدوير النقطة 60 درجة حول محور y فإن المصفوفة الناتجة من ضرب AxB تقوم بتدوير النقطة حول z 30 درجة ثم 60 درجة حول y. تكمن أهمية ذلك أنه بدلاً من ضرب كل النقاط في A ثم ضربها في B نضرب AxB ونخزن الناتج ونضرب كل النقاط في ذلك الناتج. تستطيع المصفوفة الرباعية القيام بعمليات أكثر تعقيدا من ذلك ولكن هذه أهمها.

tipتلميح

لتدوير نقطة حول نقطة مثل p غير نقطة الأصل يمكنك أن تقوم بإزاحة النقطة p إلى نقطة الأصل (من p إلى صفر يعني بمقدار -p) ثم تديرها حولها ثم تقوم بإزاحتها إلى النقطة p مرة أخرى أي ازاحة بمقدار p بالرموز T(-p)xAxT(p)

8.6.4 تمثيل المجسمات المعقدة

نمثل الشكل كما قلنا بتقسيمه إلى مضلعات تكون في الغالب كلها من نفس النوع كأن تكون كلها رباعيات. وحتى نفعل ذلك عليا أن نخزن الشكل على شكل سلسلة(منظومة في بعد واحد) من احداثيات الرؤوس، بحيث يتم رسم كل أربعة معاً فنحصل على الأشكال الرباعية التي تكون الشكل. مثلاً الإحداثيات التالية تشكل مكعب مركزه الأصل وطول حرفه(ضلعه) 40.

float box[][3]={
	{-20,-20,-20},{ 20,-20,-20},{ 20, 20,-20},{-20, 20,-20}, /* z=-20 */
	{-20,-20, 20},{ 20,-20, 20},{ 20, 20, 20},{-20, 20, 20}, /* z= 20 */
	{-20, 20, 20},{-20, 20,-20},{-20,-20,-20},{-20,-20, 20}, /* x=-20 */
	{ 20, 20, 20},{ 20, 20,-20},{ 20,-20,-20},{ 20,-20, 20}, /* x= 20 */
	{-20,-20, 20},{-20,-20,-20},{ 20,-20,-20},{ 20,-20, 20}, /* y=-20 */
	{-20, 20, 20},{-20, 20,-20},{ 20, 20,-20},{ 20, 20, 20}  /* y= 20 */
};
قد نحتاج أيضاً إلى تخزين لون كل رأس أو على الأقل لون لكل شكل رباعي، تخزن هذه المعلومات في منظومة موازية أي الأربع نقاط الأولى تعود للون الأول. لنفرض أنك تريد تشويه المكعب السابق قليلاً بشد إحدى النقاط بعيداً هنا عليك تحديث المعلومة في ثلاث أماكن؛ هي الرباعيات التي تحتوي هذه النقطة. هذا لن يكون عملياً عن التعديل في وجه أو حبة تفاح أن تذهب لكل الرباعيات التي تحتوي النقطة وتحدثها للمكان الجديد. لهذا نستخدم ما يسمى منظومة الرؤوس وهي منظومة تحتوي إحداثيات كل النقاط(الرؤوس) في الشكل، ومنظومة أخرى تحتوي أرقام الرؤوس في المنظومة الأولى التي تشكل المضلع (الرباعي في حالتنا) وقد تحتوي معلومات أخرى مثل اللون. تسمى هذه الأخيرة Indices array هذا مثال يوضح المكعب السابق
float vertices[][3]={ /* 8 are cube vertices */
	{-20,-20, 20},{20,-20, 20},{20,20, 20},{-20,20, 20},
	{-20,-20,-20},{20,-20,-20},{20,20,-20},{-20,20,-20}
}
// the indices to form the cube
unsigned int indeces[24]={ /* 24 = 4 points in 6 sides */
	0,1,2,3, /* the 1st side by connect 0-1-2-3-0 */
	1,5,6,2,
	4,5,6,7,
	4,0,3,7,
	3,2,6,7,
	0,1,5,4
}
لاحظ في المنظومة الثانية الأرقام 0،1،2،3 تعني النقاط التي تحمل تلك الأرقام في المنظومة الأولى أي أنها تعني وصل vertices[0] مع vertices[1] مع vertices[2] مع vertices[3] مع vertices[0] لتشكيل أول مضلع. وهكذا عند الرغبة بنقل موقع نقطة يكفي عمل ذلك في المنظومة الأولى.

8.6.5 الأسطح الملساء smooth

لزيادة دقة تمثيل الرسوم ثنائية الأبعاد نزيد الكثافة النقطة resolution، أما في الرسوم ثلاثية الأبعاد نزيد الدقة بزيادة الرؤوس (أي نزيد عدد الأضلاع في المضلعات) ويتم تحصيل النقاط الجديدة بعملية انقسام subdivision. وهي عملية استدعاء ذاتي recursion تأخذ الشكل قليل الرؤوس وتضيف المزيد من التفاصيل له ثم تكرر العملية عدة مرات على الشكل الناتج. مثلاً لنقرب شكل الكرة يوجد طريقة UVsphere حيث تقسّم الكرة إلى حلقات (الحلقات كل منها يقرب بمضلع منتظم بعدد كبير من الأضلاع) نوصل النقاط المتجاورة لتشكيل مربعات (كما خطوط الطول ودوائر/حلقات العرض في كتب الجغرافيا) طريقة أخرى لتقريب الكرة (مركزها نقطة الأصل ونصف قطرها واحد) على شكل عدد من المثلثات بواسطة هرمين قائمين مشتركين في قاعدة ثلاثية (مثلث متساوي الأضلاع)، بهذا نكون قد قرّبنا الكرة بست مثلثات (3 فوق و3 تحت) الآن لمزيد من الدقة نعمل على تقسيم كل مثلث إلى 4 مثلثات بتنصيف الأضلاع ووصلها (مثلثات باسكال كما في بند Fractals من الفصل السابق) ونكرر ذلك ونكرر العملية مع المثلثات الجديدة وأخيراً نرسل رؤوس هذه المثلثات إلى سطح الكرة بقسمة المتجه الذي يمثل النقطة على طوله.

8.6.6 مظهر حقيقي للمجسم

حتى يبدو المجسم حقيقياً يجب أن يحتوي على أكثر من مجرد مضلعات ملونة، أهم تلك الأشياء هي النسيج texture وهو عبارة عن صورة (غالباً حقيقية) يتم تلبيس المضلع بها، قد تكون تركيب لعدد من صورة المجسم الحقيقي من جهات مختلفة تم تركيبها معاً باستعمال برنامج مثل gimp في الغالب تشترط المكتبات أن تكون أبعاد الصورة على شكل 2n أي 8، 16، 32، 64 ...وهكذا ونحتاج لتخزين احداثيات مرافقة لكل رأس من رؤوس المضلعات التي تشكل المجسم نرمز لها عادةً u و v وهي احداثيات في مستوى صورة النسيج

8.6.7 الإضاءة

في البرامج التفاعلية(مثل الألعاب) ليس ضرورياً الحصول على إضاءة واقعية بقدر ما هو ضروري الحصول على إضاءة تبدو واقعية. مثلاً، في لعبة دووم الشهيرة ذات جدول ألوان ثابت ب256 لون من المؤكد أنك لاحظت أن الجسم الأقرب للكاميرا أكثر اضاءة والأبعد يقترب من السواء. يكون ذلك بتقسم جدول الألوان لعدة أقسام لنقل أربعة أول 64 منها مضيئة جداً والثانية أكثر اعتاماً وهكذا وعند رسم نقطة بلون رقم 32 ينظرر إلى إحداثي Z أي بعده عن مستوى الكاميرا فإذا كان قريباً نضع النقطة باللون 32 فإذا كان أبعد نضعها باللون رقم 32+64 فأبعد 32+(2*64) وهكذا.

الطريقة السابقة تعطي كل الأسطح على عمق ثابت Z نفس الدرجة من الإضاءة وإن اختلفت في زاويتها. ولكن هذا بعيد جداً عن الواقع تخيل كرة لامعة يفترض أن تكون الأسطح المواجهة للضوء لامعة وغير المواجهة تكون معتمة والمائلة بين هذه وتلك تكون بين هذه وتلك. لهذه الغاية نقوم بعملية احتساب المتجه عامودي على سطح المضلع normal vector عند كل رأس وتخزينها في منظومة . ويكون ذلك بوصل مركز المجسم بالرأس وأخذ متجه الوحدة (قسمته على طوله) هذه الطريقة ليست دقيقة لكنها تعمل. يتم حساب مركز الجسم بإيجاد أقرب وأبعد احداثيات فيه ثم أخذ وسطها الحسابي [(Xmin+Xmax)/2 (Ymin+Ymax)/2 (Zmin+Zmax)/2]T طبعاً السؤال هو ما هي علاقة المتجه العامودي بالإضاءة؟ إذا افترضنا أن الكاميرا مثبتة كما قلنا سابقاً عند الأصل متجه نحو الإتجاه السالب لمحور Z وأضفنا لهذا الافتراض أنها مصدر إضاءة نقطي عندها يمكننا أن نعتبر الإحداثي الثالث Z من المتجه العامودي هو مقدار الإضاءة أي نضربه باللون فنحصل على ما نريد.

هناك الكثير من الطرق الأكثر تعقيداً للرسوم الواقعية غير التفاعلية كأن تقوم بحساب مجال الضوء بقوانين التربيع العكسي أو بتكاملات تعتمد على نوع وشكل مصدر الضوء المستخدم ثم تضرب كل نقطة بذلك المجال مع أخذ بعين الإعتبار المادة التي يتشكل منها ذلك السطح وذلك بمعاملات ثلاث هي Ambient ومعامل التشتيت Diffuse و Specular ولكنها لا تصلح في البرامج التفاعلية لأنها معقدة جداً.

8.6.8 الظلال والإنعكاسات

يتم توليد الإنعكاسات والظلال في البرامج التفاعلية بطبع طورة مخزنة مسبقاً للظل فوق الصورة النهائية بطريقة ثنائية الإبعاد. أما في البرامج التي تحاكي الواقع فيتم توليد ذلك بطريقة الإستدعاء الذاتي ولمستوى تعقيد محدد تخيل مرآة وابرق شاي لامع هناك صورة لإبريق الشاي في المرآة وإبريق الشاي يعكس أيضاً صورة المرآة التي تحتوي إبريق يحتوي مرآة التي تحتوي إبريق ... وهكذا. الفكرة تكمن في رسم الصورة كاملة ثم رسم الصورة على اعتبار أن الكاميرا موجودة مكان المرآة والصورة الثنائية الناتجة عن الإسقاط (التي ستكون عبارة عن ابريق وربما لمعة مصدر الإضاءة) تمزج مع نسيج المرآة ثم تولد صورة أخرى على إعتبار أن الكاميرا موجودة في إبريق الشاي التي تكون مرآة بها إبريق(من الخطوة السابقة) لتكون هذه الصورة نسيجاً للإبريق وتعاد هذه الخطوات عدد معقول من المرات فنحصل في النهاية على الصورة التي نريد. قد يرافق كل خطوة من العمليات السابقة تخفيف للألوان حتى يكون اختفائها فجأة مبرراً. باختصار إن توليد الظلال و الإنعكاسات ليس أكثر من مجرد اسقاط المحيط على النسج يسمى هذ النسيج Environment Texture.

قد ترافق هذه العمليات عملية رسم ضباب ثنائي الأبعاد يزداد إعتاماً كلما ابتعدنا عن الكاميرا ويزداد شفافية كلما اقتربنا.

8.6.9 ربط المجسمات معاً

عند عمل نوذج معقد لرجل آلي مثلاً مكون من عدة مجسمات وأردنا تحريك ذراعه فإن علينا تحريك كفه ومفاصل أصابعه بطريقة مناسبة أيضاً فإذا أردنا أن تكون هذه العملية تلقائية أي حرك الذراع تحرك الكف بشكل مناسب. وإذا حنى ظهره تتحرك ذراعه ورقبته ورأسه بشكل مناسب حتى لا تبدو منفصلة. يكون ذلك بعمل شجرة يكون لكل مجسم فيها أباً وأبناء؛ فإذا دار الأب دارت معه الأبناء. نكوّن مكدس stack لمصفوفات العمليات المطلوبة. عند الرسم نبدأ من الجذر ثم ننتقل إلى الأبناء ويتم ضرب مصفوفتهم في المصفوفة الحالية وإرسالها إلى المكدس، عمليت الضرب هذه تضمن لنا تطبيق العمليات التي نفذت على الأب على الأبناء، وعند الإنتهاء من الإبن يتم سحب مصفوفته من المكدس لتعود المصفوفة الحالية إلى ما كانت عليه قبل الدخول في رسم الإبن.


<< السابق كتاب لينكس الشامل التالي >>