گراف صحنه، وب، WebGL و ساختارهای درختی

Light Source را نیز می‌توان Object تعریف کرد:

class light
{
  public:
     boolean type;
     boolean near;
     vec4 position;
     vec4 orientation;
     vec4 specular;
     vec4 diffuse;
     vec4 ambient;
}

پس از ساخت مجموعه‌ای از Geometric Objectها می‌توان از آن‌ها Scene ساخت. برای بهره‌برداری از Hierarchical Relationshipها، Structure جدیدی به نام Scene Graph معرفی می‌شود.

۸٫۸ Scene Graphها

Scene فقط از Primitive و Geometric Object تشکیل نشده است؛ Light، Camera و Attributeها نیز Objectهای Scene هستند. این Objectها نیز می‌توانند با Vertex و Vector تعریف شوند و Attributeهایی مانند Color داشته باشند. مجموع همهٔ آن‌ها Scene را می‌سازد و میان آن‌ها ممکن است رابطهٔ Hierarchical وجود داشته باشد.

برای مثال، هنگام تعریف یک Primitive، Camera Parameterهای همان لحظه در تشکیل Image نقش دارند. اگر بین تعریف دو Geometric Object، Lens دوربین تغییر کند، ممکن است هر Object با Camera Setting متفاوتی دیده شود؛ چیزی که Camera واقعی نمی‌تواند در یک Exposure واحد انجام دهد، اما Graphics System می‌تواند. Tree Data Structure را می‌توان برای بیان همین رابطه میان Geometry، Camera، Light و Attribute گسترش داد.

یک راه این است که در هر Node علاوه بر Instance Matrix و Drawing Function، Attributeهای بیشتری ذخیره کنیم. راه دیگر تعریف Node Typeهای تازه مانند Attribute-Definition Node و Matrix-Transformation Node است.

در Tree شکل ۸٫۱۸ Color و Model-View Matrix Nodeهای جدا دارند. Branch بالایی را می‌توان Group Node دانست که State موجود هنگام ورود را حفظ می‌کند و State Subtree خود را از بقیهٔ Tree ایزوله می‌سازد. Preorder Traversal متناظر به Codeای با Push/Pop State تبدیل می‌شود.

شکل ۸٫۱۸ — Scene Tree شامل Group، Color، Transformation و Object Nodeها.

pushAttrib
pushMatrix
   color
   translate
   rotate
   object1
   translate
   object2
popMatrix
pushMatrix
   translate
   rotate
   object3
popMatrix
popAttrib

Group Nodeها متناظر با Push/Pop در OpenGL هستند. Code هم Attribute و هم Model-View Matrix را پیش از خروج Restore می‌کند. Color Setشده به Branch مربوط اعمال می‌شود و Traversal مشابه Figure Hierarchy است.

می‌توان Viewing Condition را نیز روی Stack ذخیره کرد و Camera Node ساخت. معمولاً نمی‌خواهیم Objectهای یک Scene با Cameraهای متفاوت دیده شوند، اما ممکن است یک مجموعه Object را با چند Camera Render کنیم؛ مثلاً Orthographic Projectionهای چندنما و Isometric View در نقشه‌های مهندسی. Scene Graph با چند Camera به‌طور طبیعی چنین خروجی‌هایی می‌سازد.

Scene Graph توصیف‌شده از نظر رفتار معادل یک OpenGL Program است؛ می‌توان Tree را به‌صورت کاملاً مکانیکی Traversal و Graphics Callهای متناظر را تولید کرد. Open Inventor و سپس Open Scene Graph (OSG) همین رویکرد را به‌عنوان Object-Oriented API بالای OpenGL به کار گرفتند.

Open Inventor و OSG برنامه‌هایی هستند که Scene Graph را می‌سازند، Manipulate و Render می‌کنند. اجرای Program باعث Traversal Scene Graph می‌شود و Traversal در نهایت Graphics Functionهای پیاده‌سازی‌شده با OpenGL را اجرا می‌کند.

Scene Graph با Object-Oriented Paradigm بخش ۸٫۷ سازگار است. Primitive، Attribute و Transformation همگی Software Object می‌شوند و Classها آن‌ها را Manipulate می‌کنند. Encapsulation اجازه می‌دهد Sceneهای بسیار پیچیده با Programهای ساده و Objectهای ازپیش‌تعریف‌شده ساخته شوند. حتی Animation می‌تواند با Nodeهایی پیاده شود که Parameterها را تغییر داده و Redisplay ایجاد می‌کنند.

در Open Inventor، Scene Graph خود یک Database شامل همهٔ عناصر Scene است. OpenGL فقط Rendering Engine تبدیل Database به Image است و برای Specification Scene استفاده نمی‌شود. Game Engineها نیز Strategy مشابهی دارند: Game Play Scene Graph را تغییر می‌دهد و Graph با Interactive Rate Traversal/Render می‌شود.

معماری مدرن Graphics اغلب چند Layer دارد: Hardware در پایین، روی آن Hardware Abstraction Layer (HAL) به‌عنوان Virtual Machine، سپس OpenGL به‌عنوان Rendering Engine و بالاتر Object-Oriented Layer برای Scene Graph و Storage. Application بسته به نیاز می‌تواند روی هر Layer مناسب نوشته شود.

شکل ۸٫۱۹ — معماری مدرن Graphics: High-Level API → OpenGL → Virtual Machine/HAL → Hardware.

۸٫۹ Open Scene Graph

OSG یکی از رایج‌ترین Scene Graph APIهای کامل است و بسیاری از امکاناتی را دارد که Example سادهٔ ما فاقد آن بود. افزون بر Node Typeهای بیشتر، دو مفهوم کلیدی دارد.

نخست، Layer سطح بالاتر می‌تواند Workload را میان CPU و GPU متعادل کند. در OpenGL، Application Primitiveها را به‌صورت Vertex Set تولید می‌کند و تقریباً همهٔ Primitiveها حداقل بخشی از Pipeline را طی می‌کنند. Object خارج View Volume تازه در انتهای Vertex Processing Clip می‌شود و Objectی که کاملاً پشت یک Opaque Object پنهان است نیز تا Hidden-Surface Removal از Pipeline حذف نمی‌شود. در Sceneهای بسیار پیچیده حتی GPUهای پرسرعت ممکن است Frame Rate کافی نداشته باشند. OSG با Occlusion Culling و Level-of-Detail Rendering بار را کاهش می‌دهد.

شکل ۸٫۲۰ — Occlusion: Square داخل View Volume، Triangle پشت خود را می‌پوشاند.

Occlusion Culling می‌کوشد Objectهایی را که به علت Blockشدن توسط Object دیگر قابل دیدن نیستند پیش از ورود به Rendering Pipeline حذف کند. z-Buffer نتیجهٔ درست می‌دهد، اما OpenGL که Objectها را مستقل پردازش می‌کند خود به‌سادگی نمی‌تواند این Occlusion سطح Object را تشخیص دهد. OSG تمام Geometry و Viewer Information را در Scene Graph دارد و می‌تواند با Algorithmهای مناسب Graph را بررسی و Objectهای پنهان را Cull کند.

Strategy دوم مشابه منطق Mipmap است: اگر Object در Display بسیار کوچک Render شود، نیازی به Geometry پرجزئیات آن نیست. OSG دارای Level-of-Detail Node است که Childهای آن Versionهای مختلف یک Object با Geometric Complexity متفاوت‌اند. Application این Nodeها را می‌سازد و OSG هنگام Traversal Level مناسب را انتخاب می‌کند.

LOD فقط برای OSG مهم نیست؛ Real-Time Game Engineها نیز به‌شدت از آن استفاده می‌کنند. Game Engine Software بسیار بزرگ و پیچیده‌ای است که علاوه بر OpenGL/DirectX و Programmable Shaderها باید Game Play و Interaction چند Player را مدیریت کند. Scene Graph همهٔ Geometry، Texture Map و Stateهای لازم را نگه می‌دارد و LOD در Processing آن نقش مهم دارد.

مفهوم کلیدی دوم OSG نحوهٔ Processing Scene Graph در هر Frame است. برخلاف Example ساده با یک Traversal، OSG سه Traversal انجام می‌دهد تا List نهایی Geometry قابل Render را بسازد: Geometry با LOD مناسب، عبورکرده از Occlusion Culling، و Sortشده برای Rendering درست سطوح Translucent.

Traversal نخست Updateهای Scene Graph را اعمال می‌کند؛ مثلاً تغییرات ناشی از Callbackهای Interaction یا Geometry Update از Application. Traversal دوم List Geometry لازم برای Rendering را می‌سازد و Occlusion Culling، Translucency، LOD و Bounding Volumeها را در نظر می‌گیرد. Traversal سوم روی Geometry List حرکت کرده و OpenGL Callهای لازم برای Render را صادر می‌کند.

۸٫۱۰ Graphics و Internet

پیش از پایان Scene Graphها، مسئلهٔ انتقال Graphics روی Internet مطرح می‌شود. Multiplayer Game می‌تواند هزاران Participant هم‌زمان داشته باشد و هر Player بالقوه Scene Graph دیگران را تحت تأثیر قرار دهد. Modelهای بزرگ نیز ممکن است روی چند Site توزیع شده باشند.

Internet همهٔ Communication و Computer Applicationها را عمیقاً تغییر داده است. برای استفادهٔ مؤثر در Graphics باید Graphical Information را کارآمد منتقل کنیم، Applicationهایی بسازیم که از Locationهای مختلف قابل مشاهده باشند و Resourceهای توزیع‌شده را Access کنیم. OpenGL و Extensionهای آن بر توسعهٔ Applicationها و Standardهای سه‌بعدی Network-Based اثر زیادی داشته‌اند. Client–Server Model برای Rendering کارآمد و API-Independent Graphical Applicationها از موضوعات اصلی این بخش‌اند.

۸٫۱۰٫۱ Hypermedia و HTML

با رشد Internet، Protocolهای High-Level استاندارد برای Mail، File و Data Transfer رایج شدند. Systemهایی مانند X Window امکان بازکردن Window روی Remote System و انتقال Graphics پایه را می‌دادند. با افزایش Public Information، نیاز به روش‌های غنی‌تر برای اشتراک Resourceهای Distributed در Formatهای مختلف پدید آمد.

سه عنصر اصلی لازم بود: ۱) Addressing Scheme برای شناسایی Resource روی Network، ۲) Encoding Method فراتر از Text ساده برای Picture و Link، و ۳) روش Interactive برای Search Resource.

دو نیاز نخست توسط CERN و World Wide Web پاسخ داده شدند. Web اساساً یک Networked Hypertext System است. Resource/File با Uniform Resource Locator (URL) یکتا شناسایی می‌شود که سه جزء دارد: Protocol انتقال Document، Server میزبان و Location فایل روی Server.

یک URL نمونه از سه بخش تشکیل می‌شود: http که Protocol یعنی Hypertext Transfer Protocol را مشخص می‌کند؛ نام Server مانند www.cs.unm.edu؛ و Path Resource روی Server. اگر Document خاصی ذکر نشود، Default Document یا Home Page نمایش داده می‌شود.

دومین دستاورد CERN، Hypertext Markup Language (HTML) بود؛ روشی ساده برای توصیف Document شامل Text، Reference/Link به Documentهای دیگر و Image. HTML Document اساساً Text File است و در Encodingهای Character استاندارد ذخیره می‌شود.

ترکیب URL و HTML امکان Publishکردن Resourceها را فراهم کرد، اما یافتن و Searchکردن Resourceها تا ظهور Browser Mosaic در NCSA آسان نبود. Browser برنامه‌ای Interactive برای Search و Download Documentهای Web است. Mosaic و سپس Netscape Navigator مفهوم «Web Surfing» را عمومی کردند.

۸٫۱۰٫۲ Java و Appletها

یکی از مشکلات Interactive Graphics روی Internet، ناهمگونی Hardware و Operating Systemهاست. حتی با Standard APIای مانند OpenGL، Binary Application نوشته‌شده برای یک Machine الزاماً روی Machine دیگر اجرا نمی‌شود.

Java بخشی از این مسئله را با ایجاد یک Software Machine حل کرد. Java Program به Byte Code Compile می‌شود و روی هر Java Virtual Machine قابل اجراست، مستقل از Hardware زیرین. Client و Server می‌توانند Byte Code را از Web منتقل کنند. Programهای کوچک Byte Code، یعنی Applet، توسط Browserهای پشتیبان فهمیده می‌شدند و Dynamic Behavior زیادی به Web افزودند.

۸٫۱۰٫۳ Interactive Graphics و Web

HTML برای Structure و Layout Page مناسب بود، اما تا HTML5 Rendering Capability جدی نداشت. در آغاز Interactive Rendering در Browser غالباً با Java Applet انجام می‌شد؛ ولی نیاز به Download Applet و تفاوت Java VMها وعدهٔ Portability را، مخصوصاً برای 3D Graphics، محدود کرد.

با قدرتمندترشدن Browserها Technologyهای دیگری پدید آمدند. Flash با Plugin Interactive Content فراهم می‌کرد، ولی راه‌حل جامع 3D Graphics نبود و بیشتر روی Video و UI ساده تمرکز داشت. JavaScript نیز به‌عنوان Language اجراشونده در خود Browser رشد کرد و Integration بهتری با Page داشت، اما Rendering آن ابتدا عمدتاً دوبعدی بود و 3D اغلب با Software Rendererهای JavaScript پیاده می‌شد.

۸٫۱۰٫۴ WebGL

WebGL مشتقی از OpenGL—دقیق‌تر OpenGL ES 2.0—است که JavaScript Binding برای Functionهای OpenGL فراهم می‌کند و HTML Page را قادر می‌سازد از GPU Resourceهای Machine میزبان Browser برای Rendering استفاده کند.

WebGL توسط Khronos Group، همان Consortium توسعه‌دهندهٔ OpenGL، استانداردسازی شد و با Canvas در HTML5 یکپارچه است. مانند Modern OpenGL، Rendering با Vertex Shader و Fragment Shader کنترل می‌شود.

۸٫۱۱ سایر Tree Structureها

Tree و DAG برای توصیف Scene قدرتمندند، اما Tree در Graphics کاربردهای دیگری نیز دارد. سه نوع مهم بررسی می‌شوند: Expression Tree برای Hierarchy اشیای Solid، و دو Spatial Hierarchy برای افزایش Efficiency الگوریتم‌های Rendering.

۸٫۱۱٫۱ CSG Tree

Polygonal Representation مزایای زیادی دارد، اما ضعف اصلی آن این است که فقط Surface محصورکنندهٔ Interior یک Object سه‌بعدی را توصیف می‌کند، نه خود Volume را. در CAD، این محدودیت وقتی Property حجمی مانند Weight یا Moment of Inertia لازم است مشکل ایجاد می‌کند. همچنین Wireframe/Surface Display ممکن است مبهم باشد. Wireframe شکل ۸٫۲۱ می‌تواند Cube دارای Hole استوانه‌ای یا Cube جامد ساخته‌شده از دو Material متفاوت تعبیر شود.

Constructive Solid Geometry (CSG) این مشکل را با شروع از Solid Primitiveهای اتمی مانند Parallelepiped، Cylinder و Sphere حل می‌کند. Attribute می‌تواند Surface Property مانند Color/Reflectivity و Volumetric Property مانند Size/Density باشد. هر Object به‌عنوان Set of Points در Space دیده می‌شود و Objectهای جدید با Set Algebra ساخته می‌شوند.

شکل ۸٫۲۱ — Wireframe با دو تفسیر ممکن.

CSG سه Set Operation اصلی دارد:

• Union: (A\cup B)، همهٔ نقاطی که در A یا B هستند؛
• Intersection: (A\cap B)، نقاط مشترک A و B؛
• Difference: (A-B)، نقاط A که در B نیستند.

شکل ۸٫۲۲ — Set Operationهای Union، Intersection و Difference.

Object می‌تواند با Algebraic Expression توصیف شود؛ مثلاً

شکل ۸٫۲۳ Object متناظر را نشان می‌دهد.

Algebraic Expression معمولاً با Expression Tree ذخیره و Parse می‌شود: Internal Nodeها Operation و Terminal Nodeها Operand هستند. CSG Tree شکل ۸٫۲۴ Expression بالا را نمایش می‌دهد. Evaluation/Rendering با Postorder Traversal انجام می‌شود: نخست Left Subtree، سپس Right Subtree و در پایان Operation خود Node. CSG Rendering اغلب با گونه‌ای از Ray Tracing انجام می‌شود.

شکل ۸٫۲۳ — نمونه CSG Object.

شکل ۸٫۲۴ — CSG Tree.

۸٫۱۱٫۲ BSP Tree

Scene Graph و CSG Tree رابطهٔ Hierarchical میان Partهای Object را توصیف می‌کنند. Tree را می‌توان برای توصیف خود Object Space و Spatial Relationship میان گروه‌های Object نیز به کار برد. این روابط Visibility Test را سریع می‌کنند تا فقط Objectهایی که ممکن است توسط Camera دیده شوند پردازش شوند، به‌جای آنکه همهٔ Objectها تا z-Buffer پیش بروند. این Technique در Real-Time Game Animation اهمیت زیادی دارد.

یک Plane فضای سه‌بعدی را به دو Half-Space تقسیم می‌کند. Planeهای متوالی Space را به Partitionهای کوچک‌تر تقسیم می‌کنند. در دو بعد، Line نقش Plane را دارد.

Polygonهای شکل ۸٫۲۵ و Viewer را در نظر بگیرید. برای Painter’s Algorithm ترتیب مشخصی برای Drawکردن Polygonها وجود دارد. به‌جای Depth Sort در هر Frame، Relative Positionها را در Tree ذخیره می‌کنیم. Plane یکی از Polygonها برای جداکردن گروه Polygonهای جلو و عقب استفاده می‌شود.

برای توضیح ساده فرض کنید همهٔ Polygonها Parallel و Normalهایشان موازی z هستند. Top View در شکل ۸٫۲۶ دیده می‌شود.

شکل ۸٫۲۵ — مجموعه Polygonها و Viewer.

Plane مربوط به A Polygonها را به دو گروه تقسیم می‌کند: B,C جلو و D,E,F پشت. این Plane Root یک Binary Space Partitioning Tree (BSP Tree) می‌شود. در شکل ۸٫۲۷، A Root، B,C در Left Subtree و D,E,F در Right Subtree قرار دارند.

به‌صورت Recursive، C پشت Plane B است و Left Subtree کامل می‌شود. Plane D نیز E و F را جدا می‌کند و Right Subtree را می‌سازد.

شکل ۸٫۲۶ — Top View Polygonها.

شکل ۸٫۲۷ — BSP Tree.

برای یک Polygon Set چند BSP Tree ممکن است، زیرا ترتیب انتخاب Separating Planeها متفاوت است. در حالت عمومی اگر Separating Plane یک Polygon را قطع کند، Polygon به دو Polygon—یکی جلو و دیگری پشت Plane—تقسیم می‌شود، مشابه Splitکردن Polygonهای هم‌پوشان در Depth-Sort Algorithm فصل ۶.

شکل ۸٫۲۸ — جابه‌جایی Viewer به پشت Scene.

برای Paintکردن Polygonها با BSP Tree، اگر Viewer در سمت اولیه باشد می‌توان Backward In-Order Traversal انجام داد: نخست Right Subtree، سپس Root، سپس Left Subtree. مزیت BSP این است که با حرکت Viewer لازم نیست Tree را دوباره بسازیم؛ فقط Traversal Order تغییر می‌کند. اگر Viewer به پشت برود، مانند شکل ۸٫۲۸، Standard In-Order یعنی Left Subtree، Root، Right Subtree ترتیب صحیح را می‌دهد.

Algorithm را می‌توان در هر Levelی که Planeها Objectها را به Cluster تقسیم می‌کنند Recursive اعمال کرد. مثلاً Polygonها را در Polyhedral Object گروه‌بندی و Polyhedronها را در Clusterهای بزرگ‌تر قرار داد. سپس Visibility/Ordering ابتدا روی Cluster و درون Cluster تکرار می‌شود. در Flight Simulator که World Model ثابت و Viewer متحرک است، BSP Tree برای Visible-Surface Determination بسیار کارآمد است؛ Tree همهٔ Spatial Ordering را نگه می‌دارد و Viewer Position Traversal Order را تعیین می‌کند.

BSP تنها یک Spatial Hierarchy است. روش دیگر Bounding Volume Hierarchy، مثلاً Sphere، است. Root Sphere همهٔ Scene را دربر می‌گیرد و Subtreeها Groupهای Object درون Sphereهای کوچک‌ترند. Bounding Boxهای فصل ۶ نیز قابل استفاده‌اند. Sphere در Interactive Gameها مفید است چون Potential Visibility و Collision اولیه را بسیار سریع می‌توان آزمود.

۸٫۱۱٫۳ Quadtree و Octree

محدودیت BSP این است که Separating Planeها Orientation دلخواه دارند و ساخت Tree ممکن است پرهزینه باشد و Ordering/Splitting Polygon لازم داشته باشد. Quadtree و Octree این مسئله را با Plane/Lineهای موازی Coordinate Axisها ساده می‌کنند.

Image سیاه‌وسفید دوبعدی شکل ۸٫۲۹ را در نظر بگیرید. می‌توان آن را Binary Array ذخیره کرد، اما Image Coherence زیادی دارد: Pixelهای هم‌رنگ Cluster هستند.

شکل ۸٫۲۹ — فضای دوبعدی Pixelها.

دو Line Region را به چهار Quadrant تقسیم می‌کنند. اگر Quadrant کاملاً یک‌رنگ باشد فقط همان Color ذخیره می‌شود؛ Quadrantهای چندرنگ دوباره به چهار بخش تقسیم می‌شوند و این روند تا Uniformشدن Regionها ادامه می‌یابد. Information حاصل در Quadtree ذخیره می‌شود که هر Level یک Subdivision و هر Internal Node چهار Child دارد.

شکل ۸٫۳۰ — نخستین Subdivision فضا.

شکل ۸٫۳۱ — Quadtree متناظر.

چون Quadtree Space را با Lineهای Axis-Aligned تقسیم می‌کند، Construction و Traversal آن ساده‌تر از BSP است. مزیت مهم دیگر، کاهش Memory برای Imageهای دارای نواحی Uniform است.

Quadtree فقط برای Image نیست؛ Object Space دوبعدی را نیز می‌تواند Partition کند و بر اساس Viewer Position با Order مناسب Traversal شود. در سه بعد، Quadtree به Octree تعمیم می‌یابد. Planeهای موازی Axisها Space را در هر Step به هشت Octant تقسیم می‌کنند.

شکل ۸٫۳۲ — Octree.

Octree برای نمایش Volume Data Setهای متشکل از Voxel نیز به کار می‌رود.

شکل ۸٫۳۳ — Volume Data Set.

همین منطق Quadtree/Octree را می‌توان برای Spatial Partitioning خود Objectها، نه فقط Pixel/Voxel، به کار برد. برای مثال در Clipping، Space دوبعدی یا سه‌بعدی Recursive Subdivide می‌شود و Bounding Box هر Object با Rectangle/Cubeهای Subdivision مقایسه می‌گردد تا Region حضور Object تعیین شود.

جمع‌بندی و یادداشت‌ها

سرعت Rendering Hardware مدرن امکان Modeling Systemهای متنوع را فراهم کرده است. برای استفادهٔ کامل از Graphics System به مجموعهٔ بزرگی از Techniqueها نیاز داریم. Hierarchical Modeling یکی از آن‌هاست و می‌توان آن را با روش‌های دیگر ترکیب کرد.

یکی از Themeهای پایه، استفاده از Hierarchy برای ثبت Relationship میان Objectهای Scene است. Tree و DAG Data Structureهای طبیعی این روابط‌اند و Traversal آن‌ها بخشی از Rendering Process می‌شود. Scene Graph در OSG، VRML و Java3D اجازه می‌دهد Application از ترکیب Moduleهای Predefined و User-Defined، Sceneهای پیچیده و Animated بسازد.

Tree Structure در Shader Modelهای پیچیده نیز ظاهر می‌شود؛ جایی که Light Source، Material Property، Atmospheric Effect و Local Reflection Model با هم ترکیب می‌شوند و می‌توانند با RenderMan، Cg یا GLSL پیاده شوند.

Object-Oriented Approach در Applicationهای پیچیده و Network-Distributed استاندارد است، هرچند یک Object-Oriented API واحد مورد توافق همه نیست. Rendering در بسیاری از High-End Systemها همچنان در Level OpenGL انجام می‌شود، چون نزدیکی API به Hardware Efficiency بالایی می‌دهد. بنابراین Application Programmer و System Developer باید با چند سطح API آشنا باشند.

فصل ۹ رویکردی متفاوت ولی مکمل بر پایهٔ Procedural Methodها ارائه می‌کند.

منابع پیشنهادی

Hierarchical Transformation با Matrix Stack بیش از سه دهه پیش در Graphics Literature مطرح شد [New73] و PHIGS [ANSI88] نخستین API استانداردی بود که آن را وارد Package کرد. Watt [Wat92] مقدمه‌ای بر Articulated Figure در Animation و Lasseter [Las87] رابطهٔ Traditional Animation و Computer Animation را بررسی می‌کند.

BSP Tree نخست توسط Fuchs، Kedem و Naylor [Fuc80] برای Visibility Testing پیشنهاد شد و بعدها در CSG و Applicationهای دیگر به کار رفت. [Mol02] کاربردهای بیشتری را پوشش می‌دهد.

Scene Graph قلب Open Inventor [Wer94] است و Database Format آن مبنای VRML [Har96] شد. APIهای جدیدتر مانند Java3D [Swo00] و DirectX [Kov97] Object-Oriented هستند. منابع [Cha98] و [Arn96] Java/Applet را توضیح می‌دهند. Treeها در RenderMan Shading Language [Ups89] برای ساخت Shader استفاده می‌شوند. Modeling Systemهایی مانند Maya امکان Shader و Rendering Algorithm متفاوت برای Objectهای مختلف را می‌دهند. [Ma07] مقدمه‌ای بر Open Scene Graph است. Scene Graph در Game Engine Design نیز در [Ebe01] و Torque Engine در [Mau06] بحث شده است.

تمرین‌ها

۸٫۱ برای Robot Model ساده، مجموعهٔ نقاطی را که نوک Upper Arm می‌تواند به آن‌ها برسد توصیف کنید.

۸٫۲ Equationهای Position هر نقطه از Robot را بر حسب Joint Angleها پیدا کنید. آیا Joint Angleها را می‌توان از Position نوک Upper Arm به‌صورت یکتا تعیین کرد؟ توضیح دهید.

۸٫۳ برای دو نقطهٔ قابل دسترس Robot، Path میان آن‌ها را بر حسب Joint Angleها توصیف کنید.

۸٫۴ یک Circuit-Layout Program ساده با Symbol–Instance Transformation Table بنویسید. Symbolها می‌توانند Resistor، Capacitor، Inductor یا Logic Gateهای AND/OR/NOT باشند.

۸٫۵ یک Binary Tree توصیف‌شده با Node/Child Pointer را به‌صورت Graphical با OpenGL نمایش دهید.

۸٫۶ نمونه‌ای از Compound Motion—مانند Bicycle، Airplane با Propeller یا Merry-Go-Round—انتخاب و Graphics Program شبیه‌ساز آن را بنویسید.

۸٫۷ برای دو Polygon با تعداد Vertex یکسان، Sequenceای از Imageها تولید کنید که یکی را تدریجاً به دیگری تبدیل کند.

۸٫۸ به Tree Node بخش ۸٫۵ یک Attribute اضافه و Traversal Algorithm را متناسب اصلاح کنید.

۸٫۹ Scene Graph System ساده‌ای شامل Polygon، Material، Viewer و Light Source بسازید.

۸٫۱۰ چرا Ray Tracing/Ray Casting Strategy مناسبی برای Rendering Scene توصیف‌شده با CSG Tree است؟

۸٫۱۱ نشان دهید Quadtree چگونه Image را در Resolutionهای مختلف Draw می‌کند.

۸٫۱۲ برنامه‌ای بسازید که User بتواند از مجموعه‌ای کوچک Basic Shape، Articulated Figure بسازد، Jointها را Position کند و Figure حاصل را Animate نماید.

۸٫۱۳ آیا می‌توان Scene Graph Structureای طراحی کرد که از Traversal Algorithm مستقل باشد؟

۸٫۱۴ به Scene Graph این فصل قابلیت ذخیره در Text Format و Load از File اضافه کنید.

۸٫۱۵ قابلیت Animateکردن Objectها را به Scene Graph اضافه کنید.

۸٫۱۶ به Robot بخش ۸٫۳ یک Hand یا Gripper اضافه کنید.

۸٫۱۷ به همان Robot Wheel اضافه کنید تا روی سطح Flat حرکت کند.

۸٫۱۸ BSP Tree را به‌صورت Hierarchical با Clusterهای Object و Bounding Volume پیاده کنید؛ Visibility Check روی Clusterها انجام شود و آن را با Scene Graph Renderer ترکیب کنید.

این صفحه در نسخهٔ اصلی عمداً خالی است.