Khóa luận Xây dựng game engine đa nền tảng quản lý khung cảnh

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Trương Đức Phương XÂY DỰNG GAME ENGINE ĐA NỀN TẢNG QUẢN LÝ KHUNG CẢNH KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Trương Đức Phương XÂY DỰNG GAME ENGINE ĐA NỀN TẢNG QUẢN LÝ KHUNG CẢNH KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Nguyễn Việt Hà Cán bộ đồng hướng dẫn : ThS. Vũ Quang Dũng HÀ NỘI - 2009 Lời cảm ơn Tôi xin chân thành cảm ơn Tiến sĩ Nguyễn Việt Hà, Thạc sĩ Vũ Quang Dũng là người trực tiếp, nhiệt tình hướng dẫn tôi hoàn thành khóa luận tốt nghiệp này. Tôi xin gửi lời cảm ơn phòng thí nghiệm Toshiba-Coltech đã tạo môi trường làm việc để nhóm chúng tôi tập trung cùng nhau nghiên cứu. Tôi xin gửi lời cảm ơn tới toàn thể các thầy giáo, cô giáo tại Trường Đại học Công Nghệ - Đai học Quốc gia Hà Nội những người đã hết lòng dạy cho tôi những kiến thức hết sức bổ ích trong 4 năm học qua. Xin cảm ơn gia đình và những người bạn đã dành cho tôi tình thương yêu và sự hỗ trợ tốt nhất. Hà nội, ngày 22 tháng 05 năm 2009 Sinh viên Trương Đức Phương Tóm tắt nội dung Khái niệm Game Engine xuất hiện ở giữa thập kỉ 90 và ngày này đã trở thành một thành phần quan trọng trong quy trình phát triển trò chơi điện tử. Sự ra đời và phát triển của Game Engine đã mang đến cho các game hiện đại những bước tiến nhảy vọt về mọi mặt : đồ họa, khả năng tương tác, độ chân thực… Khóa luận này đề cập đến phương pháp triển khai module “Quản lý khung cảnh” trong dự án “Xây dựng Game Engine đa nền tảng” của chúng tôi. Cụ thể, chương 1 và chương 2 mang đến cho người đọc một các nhìn tổng thể về kiến trúc của cả hệ thống Game Engine. Sau đó, chương 3 trình bày chi tiết về module “Quản l‎ý khung cảnh”, đi sâu vào cách tổ chức khung cảnh và các giai đoạn trong quá trình render khung cảnh. Cuối cùng là thông tin kiểm thử thực nghiệm về hiệu năng của các kỹ thuật được triển khai và hướng phát triển trong tương lai. Mục lục Bảng các thuật ngữ Thuật ngữ Ý nghĩa Axis aligned bounding box Là một loại bounding volume có dạng hình hộp, các cạnh dọc theo 3 trục xyz. Bounding Sphere Là một loại bounding volume có dạng hình cầu. Bounding Volume Là danh từ chung chỉ các loại hình học đơn giản được sử dụng để mô tả một không gian bao bọc hoàn toàn một vật thể nào đó. Event Đơn vị truyền thông liên tiến trình được gửi đến bởi Hệ điều hành. Game Engine Middleware cung cấp một giao diện đơn giản hơn để phát triển game . Mesh Là một mạng lưới các đa giác dùng để mô tả hình dạng của vật thể trong không gian 3 chiều. OpenGL Một chuẩn 3d graphic API . Render Là việc từ các dữ liệu về khung cảnh, đối tượng 3D, ta thực hiện các phép biến đổi, các tính toán để đưa ra hình ảnh 2D thu được tại vị trí nhìn ( giống nhau quá trình mắt người hay các camera thu hình ảnh 2D từ môi trường ). Texture Là một hoặc một loạt các bức ảnh dùng để tăng độ chi tiết cho các đối tượng. View Frustum Hình chóp cụt xác định khung nhìn của camera. Danh mục hình vẽ Hình 1: Kiến trúc phân tầng của GEM. 2 Hình 2: Kiến trúc tổng thể. 4 Hình 3: Biểu đồ lớp của thành phần Các kiểu dữ liệu cơ bản. 5 Hình 4: Quá trình điều phối event. 7 Hình 5: Kiến trúc phân tầng của Render Engine. 8 Hình 6: Biểu đồ gói của Render Engine. 9 Hình 7: Axis Aligned Bounding Box và Bounding Sphere trong GEM. 12 Hình 8: Ví dụ cây khung cảnh và BHVs tương ứng. 12 Hình 9: Biều đồ lớp của module Quản lý khung cảnh. 13 Hình 10: Lớp SceneNode. 14 Hình 11: Lớp SolidMeshSceneNode. 16 Hình 12: Hình ảnh Bàn cờ và các quân cờ dùng SolidMeshNode. 17 Hình 13: Lớp CameraSceneNode. 18 Hình 14: Lớp SkyboxSceneNode. 19 Hình 15: Skybox. 20 Hình 16: Lớp SceneGraphManager. 20 Hình 17: Lớp RenderList và RenderContext. 21 Hình 18: Biều đồ hoạt động của giai đoạn prepare-render. 23 Hình 19: Biều đồ hoạt động của giai đoạn Tính lại BVHs. 25 Hình 20: Ví dụ minh họa khung hình. 27 Hình 21: Biều đồ hoạt động giai đoạn view frustum culling. 28 Hình 22: Ví dụ một Bounding Sphere có d > R. 29 Hình 23: Biều đồ hoạt động của giai đoạn render từng render-list. 32 Hình 24: Ví dụ minh họa một vật thể bị chắn hoàn toàn. 33 Chương 1. Đặt vấn đề 1.1. Bối cảnh nghiên cứu Ngành công nghiệp phát triển game trên thế giới đang phát triển như vũ bão. Cách đây 20 năm, game rất đơn giản và chỉ cần một người hoặc một nhóm nhỏ người phát triển nhưng ngày nay, các game hiện đại với đồ họa và khả năng tương tác ấn tượng thường được phát triển bởi một đội ngũ đông đảo người thiết kế game, lập trình viên, nghệ sĩ… trong thời gian ròng rã từ một đến ba năm. Chính việc game ngày càng trở nên phức tạp như vậy nên hiện nay, các game thương mại không còn phát triển từ nguyên thủy nữa mà được phát triển lên từ game engine. Game engine hỗ trợ việc xây dựng game một cách nhanh chóng, đơn giản hơn đồng thời cung cấp khả năng tái sử dụng code cao do có thể phát triển nhiều game từ một game engine. Ở Việt Nam, Game online mới chỉ thực sự thâm nhập vào thị trường cách đây 6 năm nhưng chỉ trong khoảng thời gian ít ỏi đó, chúng ta đã có một số lượng nhà phát hành game lên tới con số hàng chục, số game được phát hành cũng tương ứng với số lượng đó. Nhưng theo như chúng tôi được biết, gần như tất cả các game online đang được phát hành ở Việt Nam là được nhập khẩu từ nước ngoài, chủ yếu là Trung Quốc và Hàn Quốc ( trừ một số game nhỏ chơi trên web như đánh bài, đánh cờ ..) Một câu hỏi mà có lẽ tất cả những người chơi game đều trăn trở là “bao giờ mới được chơi game Việt Nam?”. Chúng tôi chọn đề tài này làm khóa luận tốt nghiệp không phải với một tham vọng quá lớn, chỉ là muốn đi những bước chân chập chững đầu tiên vào thế giới phát triển game rộng lớn, để thu lượm kiến thức về lĩnh vực khó khăn nhưng đầy thú vị này và hi vọng ở một tương lai không xa, chúng tôi có thể góp một phần sức lực giái đáp trăn trở của cộng đồng người chơi game Việt Nam. 1.2. Mục tiêu Xây dựng một Game Engine đa nền có thể chạy trên nhiều hệ điều hành khác nhau, hướng đến phân khúc phát triên game nhập vai trực tuyến (MMORPG). Game Engine này được đặt tên là GEM. Đây là mục tiêu dài hạn, còn hiện tại, do thời gian làm luận văn chỉ khoảng 5 tháng nên nhóm chúng tôi chỉ tập trung hoàn thiện thành phần Render Engine trong Game Engine ( Xem chi tiết ở chương 2). 1.3. Giới thiệu chung Như đã giới thiệu ở trên, Game Engine là một lớp trung gian giữa game và nền tảng bên dưới, các thư viện lập trình cấp thấp. GEM là một game engine nên dĩ nhiên nó cũng tuân thủ theo nguyên tắc này Hình 1: Kiến trúc phân tầng của GEM. Đặt điểm đầu tiên của GEM là khả năng chạy đa nền.Để đặt được điều đó, GEM sử dụng các bản build trên các nền tảng khác nhau ( chứ không phải sử dụng thông dịch ). Các đoạn code phụ thuộc nền tảng sẽ được phân chia bằng việc sử dụng các cờ tiền biên dịch, hạn chế tối đa việc sử dụng các lớp abstract – vì việc này sẽ làm giảm hiệu suất chương trình đáng kể [1]. Cũng vì lí đo chạy đa nền nên chúng tôi lựa chọn openGL làm giao diện lập trình đồ họa 3D cấp thấp cho GEM, do chuẩn openGL là chuẩn mở và không bị phụ thuộc vào hệ điều hành. GEM được thiết kế hướng đối tượng và yêu cầu về hiệu năng chạy cao nên chúng tôi sử dụng ngôn ngữ C++ - ngôn ngữ đáp ứng hoàn hảo các điều kiện trên. Đa số các Game Engine trên thế giới hiện nay đều được phát triển bằng ngôn ngữ C++. Chúng tôi thiết kế GEM nhắm đến phân khúc phát triển game nhập vai trực tuyến, nên khả năng tương thích với một phạm vi rộng cấu hình phần cứng là một điều kiện quan trọng, dự kiến sẽ support các card đồ họa hỗ trợ openGL 1.4 và shader 1.0 trở lên. Bảng cấu hình tối thiểu dự kiến : Hãng sãn xuất Dòng card hỗ trợ nVidia Từ GeForce4 Ti trở lên ATI Từ Radeon 9500 trở lên Intel ( card tích hợp ) Từ Intel® GMA 3100 ( chipset G31,Q33) trở lên Chương 2. Kiến trúc tổng thể GEM là được chia thành nhiều thành phần để tiện cho việc phát triển và bảo trì. Cụ thể GEM gồm các thành phần như sau : Hình 2: Kiến trúc tổng thể. Ghi chú : Do thời gian làm luận văn có hạn, chúng tôi mới chỉ hoàn thành những thành phần sau : Giao tiếp với hệ điều hành, Các kiểu dữ liệu cơ bản, Render Engine. Những thành phần này đủ để hỗ trợ người sử dụng tạo ra các khung cảnh 3D và tương tác với chúng. 2.1. Thành phần Các kiểu dữ liệu cơ bản Các kiểu dữ liệu cơ bản là thành phần bao gồm các cấu trúc dữ liệu cơ bản như mảng động, vector, ma trận…, các phép toán trên các kiểu dữ liệu đó cung cấp cho thành phần khác sử dụng Hình 3: Biểu đồ lớp của thành phần Các kiểu dữ liệu cơ bản. Các kiểu dữ liệu này có thể chia thành 2 nhóm chính : - Các yếu tố trong không gian 3D : + Vector2, Vector, Vector4 : các loại vector biểu diễn tọa độ 2 chiều, 3 chiều và tọa độ đồng nhất + Aabb ( Axis aligned bounding box ) : hình hộp chữ nhật có các cạnh dọc theo 3 trục xyz, được mô tả bằng 2 điểm (xmin, ymin, zmin ), ( xmax, ymax, zmax ) + Sphere : hình cầu, được mô tả bởi tọa độ tầm và bán kính. + LineSequent, Line, Ray : đoạn thẳng, đường thẳng, tia. + Matrix : ma trận sử dụng để biểu diễn các phép biến đổi : dịch, xoay, co giãn trong không gian 3 chiều. + Plane : mặt phẳng được mô tả bằng các hệ số của phương trình : ax + by + cz + d = 0. + Frustum : là hình chóp cụt biểu diễn khung nhìn của camera, được mô tả bằng 6 mặt phẳng tạo nên nó. - Các kiểu đối tượng lưu trữ : + String. + Array : mảng động với hệ số mở rộng có thể tùy biến. + GemAllocator : sử dụng bởi các lớp khác để thực thi việc cấp phát và giải phóng bộ nhớ. + List : linked list 2 chiều. + Stack. 2.2. Thành phần Giao tiếp với hệ điều hành Giao tiếp với hệ điều hành là thành phần thực thi các công việc cần giao tiếp với hệ điều hành như điều phối event, đọc ghi file, lấy thời gian hệ thống… Trong đó quan trọng nhất là quá trình điều phối event : Hình 4: Quá trình điều phối event. GEM lấy event từ Message System của hệ điều hành, từ đó lấy các thông tin cần thiết tạo ra GemEvent - lý do cần tạo ra GemEvent là để tránh bị phụ thuộc vào hệ điều hành. Sau đó, GemEvent sẽ được gửi lần lượt đến các thành phần có khả năng nhận và xử lý event. 2.3. Thành phần Render Engine 2.3.1. Khái quát về Render Engine Render Engine là thành phần cốt lõi của một Game Engine. Nó hỗ trợ người dùng các công việc thiết yếu để tạo ra một khung cảnh 3D. Người dùng sẽ không cần biết nhiều đến những công việc tầng thấp như quá trình đọc file tài nguyên, sử dụng 3D Graphic API, quá trình tạo các effect… mà chỉ cần dùng giao diện do Render Engine cung cấp. Render Engine là thành phần duy nhất trong Game Engine giao tiếp với các thư viện đồ họa cấp thấp ( cụ thể ở đây là openGL và Cg ) Hình 5: Kiến trúc phân tầng của Render Engine. 2.3.2. Kiến trúc của Render Engine Render engine được chia thành các module sau : Hình 6: Biểu đồ gói của Render Engine. - Graphic Driver là module duy nhất trực tiếp sử dụng 3D Graphic API (openGL), cung cấp cho các module khác một giao diện đơn giản hơn để tương tác với card đồ họa. - Quản lý tài nguyên là module quản lý các tài nguyên cần thiết để xây dựng một khung cảnh 3D như mesh, animated mesh, texture 2D, cubemap…Module này được bạn Hoàng Tuấn Hưng trình bày trong khóa luận  “Xây dựng Game Engine đa nền tảng – Quản lý tài nguyền và chuyển động đối tượng ”. - Quản lý khung cảnh là module thực hiện việc tổ chức và kiểm soát các đối tượng tồn tại trong một khung cảnh 3D, từ đó thực hiện quá trình render toàn bộ khung cảnh đó tạo nên hình ảnh 2D tại vị trí nhìn. Module này được trình bày chi tiết trong các chương sau của tài liệu này. -Hiệu ứng ánh sáng và vật liệu là module mở rộng các thành phần của Quản lý khung cảnh để tạo các hiệu ứng về ánh sáng, vật liệu, và đổ bóng. Module này được bạn Bùi Hoàng Khánh trình bày trong khóa luận “Xây dựng Game Engine đa nền tảng – Hiệu ứng ánh sáng và vật liệu”. -Mô phỏng tự nhiên là module mở rộng các thành phần của Quản lý khung cảnh để mô phỏng các yếu tố tự nhiên cần có trong game như nước, địa hình, lửa, khói… Module này được bạn Trần Thái Dương trình bày trong khóa luận “Xây dựng Game Engine đa nền tảng –Mô phỏng tự nhiên”. - Chuyển động của đối tượng là module mở rộng các thành phần của Quản lý hung cảnh, thực hiện quá trình nội suy trong các mô hình chuyển động ( thường là các nhân vật trong game ) thông qua hai kĩ thuật thông dụng là keyframe và skinning. Module này được bạn Hoàng Tuấn Hưng trình bày trong khóa luận  “Xây dựng Game Engine đa nền tảng – Quản lý tài nguyền và chuyển động đối tượng”. 2.4. Các thành phần còn lại. Các thành phần Mạng, Trí tuệ nhân tạo, Tính toán vật lí, Âm thanh chưa được triển khai nên chúng tôi không đề cập đến trong tài liệu này. Chương 3. Quản lý khung cảnh 3.1. Khái niệm khung cảnh và cách tổ chức khung cảnh Khung cảnh có thể hiểu giống như một trường quay phim. Nó bao gồm tất cả các đối tượng tham gia vào quá trình tạo nên hình ảnh, ví dụ như các camera, các nhân vật, các vật thể, các nguồn chiếu sáng… Dĩ nhiên trong một chương trình máy tính, khung cảnh được dữ liệu hóa và chúng tôi định nghĩa nó là tổng hợp tất cả dữ liệu mô tả các đối tượng trong một không gian 3D. Khung cảnh là rất nhiều dữ liệu, vì vậy một yêu cầu bắt buộc phải tổ chức nó một cách hợp l‎ý để tiện sử dụng trong quá trình render. Ở đây, chúng tôi tổ chức nó thành một cây quan hệ về không gian và đồng thời là Bounding Volume Hierachies (BVHs). 3.1.1. Cây quan hệ về không gian Cây quan hệ về không gian là một cây mà trong đó, node con nằm trong không gian của node cha. Nghĩa là khi không gian của node cha thay đổi sẽ làm node con thay đổi theo. Việc tổ chức khung cảnh thành cây quan hệ về không gian sẽ giúp mô tả mối quan hệ giữa các đối tượng một cách dễ dàng. Ví dụ như trong khung cảnh có một chiếc ôtô và 2 nhân vật ngồi trong đó, khi đó 2 nhân vật sẽ là 2 node con của node cha ôtô, khi ôtô di chuyển, do bị ràng buộc về không gian nên 2 nhân vật cũng sẽ di chuyển theo. 3.1.2. Bounding Volume Hierachies. a. Khái niệm Bounding Volume: Để đơn giản hóa một số giai đoạn tính toán trong quá trình render SceneGraph, chúng ta sử dụng một số hình đơn giản hơn bao bọc quanh các đối tượng.Các hình đó được gọi là bounding volume. Ở đây chúng tôi sử dụng 2 loại bounding volume là : + Axis Aligned Bounding Box. + Bounding Sphere. Hình 7: Axis Aligned Bounding Box và Bounding Sphere trong GEM. b. Khái niệm Bounding Volume Hierachies (BVHs): BVHs có thể hiểu là một cây bounding volume, trong đó bounding volume của node cha sẽ chứa tất cả bounding volume của node con. Việc sử dụng BVHs giúp giảm độ phức tạp của quá trình cắt theo khung hình (View Frustum Culling) Hình 8: Ví dụ cây khung cảnh và BHVs tương ứng. Trong hình trên, sơ đồ bên phải là cây khung cảnh, bên trái là ví trí các node trong không gian và bounding volume của nó. Ta có thể thấy bounding volume của node A là tổng bounding volume của 2 node con, bounding volume của root là tổng bounding volume của tất cả các node con. 3.2. Thiết kế cấu trúc Hình 9: Biều đồ lớp của module Quản lý khung cảnh. SceneGraphManager : lớp đóng vai trò là gốc của cây khung cảnh, chứa các phương thức thực thi quá trình render cây khung cảnh. SceneNode : là lớp cơ sở để tạo thành cây khung cảnh. SceneNode bao gồm các dữ liệu mà mọi đối tượng trong không gian 3D đều cần phải có. Các loại node khác sẽ thừa kế từ lớp này. CameraSceneNode, SolidMeshSceneNode, SkyBoxSceneNode ... : là các loại node được triển khai từ lớp cơ sở SceneNode, một loại node ứng với một loại đối tượng cụ thể. RenderList : là tập hợp các node có chung một tập các trạng thái render. Các node trong cây khung cảnh sẽ được đưa về các render list rồi sau đó mới thực hiện việc render các render list. Việc làm này sẽ hạn chế tối đa việc chuyển các trạng thái render, năng hiệu suất của hệ thống. RenderContext : Là tập hợp các trạng thái render. Animation : Là lớp cơ sở cho mọi loại animation. Một SceneNode sẽ có một list các animation và thực hiện tất cả các animation đó ở đầu mỗi khung hình. ValueAnimation, DestroyAnimation .. : Là các loại animation cụ thể được triển khai từ lớp cơ sở Animation. 3.2.1. Lớp SceneNode Hình 10: Lớp SceneNode. Các thuộc tính chính : - position, scale, rotation,angle : các phép biến đổi dịch, co dãn,xoay và góc xoay của không gian node này so với không gian của node cha. - modelMatrix : ma trận biến đổi không gian của node này sang không gian thế giới ( lưu ma trận này để tăng tốc quá trình render – nếu không, bất kì khung hình nào cũng phải tính lại nó mặc dù không gian của node có thể không biến đổi ) - chidren : danh sách các node con của node. - parent : node cha của node này - boundingBox : aabb của node này trong không gian địa phương của nó. - boundingBoxInWorld : aabb của node này trong không gian trong không gian thế giới. - treeBoundingBox : tổng hợp boundingBoxInWord của node này và treeBoundingBox của các node. - boundingSphere, boundingSphereInWorld, treeBoundingSphere : như trên nhưng thay aabb bằng bounding sphere. - animationList : danh sách các animation tác động lên node này Các phương thức chính : - updateModelMatrix() : phương thức này sẽ kiểm tra các trạng thái của node ( không gian của nó có biển đổi không, không gian của node cha có biến đổi không.. ) và tính lại ma trận modelMatrix nếu cần thiết. -viewFrustumCulling(Frustum& frustum) : phương thức đệ quy thực thi quá trình view frustum culling. - prepareRender() : phương thức đệ quy thực thi quá trình prepareRender. - render : phương thức được gọi khi render node này, các loại node sẽ triển khai phương thức này cách render loại node đó. - animate : thực thi tất cả các animation này trong animationList của node này. 3.2.2. Một số loại node khác a. SolidMeshSceneNode : SolidMeshSceneNode loại node dành cho các đối tượng có mô hình cố định (thường là các đồ vật ). Mỗi SolidMeshSceneNode sẽ sử dụng mesh trong mesh bank và texture trong texture bank, khi node này được render, hệ thống sẽ render mesh đó với ma trận biến đổi thích hợp ( có hỗ trợ tính năng Level of Detail – LOD – xem chi tiết về LOD trong phần 3.1.Các thuật ngữ ) Biểu đồ lớp : Hình 11: Lớp SolidMeshSceneNode. Các thuộc tính chính : - activeMeshID : mesh hiện tại đang sử dụng - meshLOD : tập hợp tất cả các mesh mà node này sử dụng để hỗ trợ tính năng static LOD - colorSamplerID : texture sử dụng để làm kênh color Minh họa : Hình 12: Hình ảnh Bàn cờ và các quân cờ dùng SolidMeshNode. b. CameraSceneNode CameraSceneNode là loại node chứa các thông tin camera: vị trí, hướng quay và góc quay.v.v., đồng thời nó cũng là 1 event receiver để xử lí các event của người dùng ( ví dụ như di chuột thì camera xoay .v.v. ) Biểu đồ lớp : Hình 13: Lớp CameraSceneNode. Các thuộc tính chính : - m_Up : Vector up của camera. - m_Center : Vector center của camera ( điểm nhìn ) - m_Far, m_Left, m_Right, m_Top, m_Bottom, m_Fovy, m_Aspect : các thuộc tính xác định khung nhìn của camera. Các phương thức chính : - look() : tính các ma trận biến đổi cần thiết với vị trì đặt camera là position, vị trí nhìn là m_Center, vector up là m_Up. - calculationFrustum() : tính khung nhìn hiện tại của camera ( Xem chi tiết trong phần 2.3.2.2.Render SceneGraph ) - onEvent(Event& event) : xử lí event nhận được đo quá trình dispatch event gửi đến. c.SkyboxSceneNode SkyboxSceneNode là loại node dùng để tạo cảnh vật ở xa vô cực, thường là bầu trời, cảnh núi mây ở rất xa vị trí nhìn. Để làm điều này, SkyboxSceneNode sử dụng hình lập phương rồi dán texture chứa hình ảnh ở rất xa vào, camera sẽ luôn nằm ở vị trí trung tâm của khối lập phương. Biểu đồ lớp : Hình 14: Lớp SkyboxSceneNode. Các thuộc tính chính : - xzTexture, yPositiveTexture,yNegativeTexture : Các texture chứa hình ảnh ở rất xa. Minh họa : Hình 15: Skybox. 3.2.3. Lớp SceneGraphManager Hình 16: Lớp SceneGraphManager. Các thuộc tính chính : - activeCamera : camera được sử dụng để nhìn toàn bộ khung cảnh. - renderList : 16 render-list. - renderOrder : mảng xác định thứ tự render các render-list. Các phương thức chính : - registerRenderList(..) : đăng kí một node vào một render-list. - unregisterRenderList(..) : loại bỏ một node ra khỏi một render-list. - drawSceneGraph() : render toàn bộ khung cảnh. - setRenderOrder(..) : xác định thứ tự render của các render-list. 3.2.4. Lớp RenderList và RenderContext Hình 17: Lớp RenderList và RenderContext. Một RenderList bao gồm một danh sách các node node_list và một RenderContext rc. Các node nằm trong node_list sẽ được render với các trạng thái đặt trong rc. RenderContext : Các thuộc tính : - RenderContext bao gồm rất nhiều trạng thái render trong đó có hể chia làm 2 nhóm : nhóm các trạng thái của openGL và các trạng thái của GEM. Các phương thức : - pushState() : đặt tất cả các trạng thái render. - popState() : phục hồi lại tất cả các trạng thái render như trước khi gọi pushState() 3.3. Thiết kế chức năng Chức năng chính của module này là render toàn bộ cây khung cảnh. Quá trình render trải qua những bước sau : - Bước 1 – prepare-render : duyệt cây theo chiều sâu, tại mỗi node, thực hiện tất cả các animation, kiểm tra trạng thái của node để xác định xem có cần tính lại các ma trận biến đổi không. - Bước 2 – Tính lại BVHs : Duyệt cây theo thứ tự sau (postfix) ,kiểm tra cờ trạng thái, tính lại tree bounding volume của node nếu cần thiết. - Bước 3 – Tính lại các ma trận biến đổi của Camera và tính khung nhìn. - Bước 4 – view frustum culling : phát hiện các node nằm bên ngoài khung nhìn và loại chúng ra khỏi quá trình render. - Bước 5 - Render từng render-list : tùy vào các trạng thái render nằm trong render context, các node trong render-list có thể sẽ được sắp xếp theo khoảng cách đến camera, thực hiện occlusion culling mới được render. 3.3.1. Prepare-render Hình 18: Biều đồ hoạt động của giai đoạn prepare-render. Quá trình prepare-render trải qua các bước như sau : - Bước 1 : Đi đến node tiếp theo theo chiều sâu. - Bước 2 : Gọi hàm animated() của node. Hàm này sẽ thực thi tất cả các animation có trong animationList của node này. - Bước 3 : Kiểm tra các cờ trạng thái liên quan đến ma trận biến đổi và tính lại các ma trận nếu cần thiết. Trong đó : + UPDATE_SCALE_MATRIX : khi cờ này được bật, nghĩa là node này bị thay đổi về độ phóng to ( hoặc thu nhỏ ) so với khung hình trước, do đó sẽ phải tính lại ma trận phóng của node. + UPDATE_ROTATION_MATRIX : khi cờ này được bật, nghĩa là node này bị thay đổi về góc quay ( hoặc độ quay ) so với khung hình trước, do đó phải tính lại ma trận quay của node. + UPDATE_TRANSLATE_MATRIX : khi cờ này được bật, nghĩa là node này bị dịch chuyển vị trí so với khung hình trước, do đó phải tính lại ma trận dịch của node. + PARENT_MATRIX_CHANGE : khi cờ này được bật nghĩa là ma trận biến đổi của node cha bị thay đổi, hay chính là không gian của node cha bị thay đổi. Nếu một trong các cờ trên được bật, thì node sẽ phải tính lại modelMatrix theo công thức như trong hình vẽ. modelMatrix là ma trận biến đổi không gian của node sang không gian thế giới, được sử dụng trong quá trình render vật thể. - Bước 4 : Nếu node này phải tính lại modelMatrix ( nghĩa là không gian của nó bị thay đổi so với khung hình trước ) ta phải bật một số cờ ở các node con và node tổ tiên ( node cha, node ông.. ) của node này. Cụ thể : + Bật cờ PARENT_MATRIX_CHANGE ở các node con ( thông báo không gian của node cha bị thay đổi ) + Bật cờ UPDATE_TREE_BOUNDING_VOLUME ở các node tổ tiên, thông báo các node đó sẽ phải tính lại tree bounding volume trong quá trình Tính lại BVHs ( xem chi tiết trong phần b của chương này ). 3.3.2. Tính lại BVHs Hình 19: Biều đồ hoạt động của giai đoạn Tính lại BVHs. Quá trình tính lại BVHs như sau : duyệt cây Scene Graph theo thứ tự sau ( do phải có tree bounding volume của node con mới tính được tree bounding volume của node cha ) : - Tại mỗi node, kiểm tra cờ UPDATE_TREE_BOUNDING_VOLUME. Cờ này được bật khi một trong những node con bị biến đổi về không gian hoặc khi thêm bớt node con ( so với khung hình trước ). - Nếu cờ được bật, tính lại tree bounding volume của node theo công thức : tree BV = tổng ( tree BV của tất cả các node con ) + BV của node này. 3.3.3. Tính lại các ma trận biến đổi của Camera và tính khung nhìn a.Các ma trận biến đổi của camera Camera là đối tượng mô phỏng mắt người trong Scene Graph. Tức là chúng ta sẽ thu hình ảnh ở vị trí đặt camera. Camera sẽ lưu trữ và tính toán 2 ma trận biến đổi  view matrix và project matrix : + View matrix : là ma trận biến đổi không gian thế giới sang không gian nhìn. + Project matrix : là ma trận biến đổi từ không gian nhìn sang không gian chiếu. b.Quá trình tính lại view matrix và project matrix Trước tiên, ta kiểm tra các cờ trạng thái của active camera để xác định xem có cần tính lại các ma trận biến đổi hay không : + Nếu cờ UPDATE_VIEW_MATRIX hoặc PARENT_MATRIX_CHANGE được bật : tính lại view matrix từ vị trí đặt, vector up và hướng nhìn của camera. + Nếu cờ UPDATE_PROJECTION_MATRIX được bật : tính lại projection matrix từ các thuộc tính m_Near,m_Far, m_Bottom, m_Top, m_Right, m_Left của camera ( Xem lại lớp Camera trong 4.2.1.d.Các loại node cơ bản ). c.Tính khung nhìn Khái niệm khung nhìn : là không gian mà chỉ những đối tượng nằm trong ( hoặc một phần nằm trong ) mới được nhìn thấy bởi camera. Ở đây camera hoạt động theo phép chiếu phối cảnh nên khung nhìn là một hình chop cụt do 6 mặt phẳng ghép lại : near, far, top, bottom, right, left. Hình 20: Ví dụ minh họa khung hình. Chúng tôi sử dụng phương pháp tính 6 mặt phẳng tạo nên khung nhìn từ view matrix và projection matrix theo [2]. 3.3.4. View frustum culling a. Khái niệm view frustum culling Ta đã biết chỉ các vật thể nằm trong ( hoặc một phần nằm trong ) khung nhìn mới được nhìn thấy. Như vậy, nếu xác định được node nào nằm bên ngoài view frustum, ta có thể loại nó ra khỏi quá trình render. Để đơn giản hóa việc kiểm tra xem một node có nằm ngoài khung nhìn hay không, ta sử dụng Bounding Volume của nó để kiểm tra ( do Bounding Volume có hình dạng rất đơn giản hơn nhiều so với bản thân vật thể). View frustum culling là việc phát hiện các node nằm bên ngoài frustum đựa vào BVHs là loại chúng ra khỏi quá trình render. b. Quá trình thực hiện view frustum culling Hình 21: Biều đồ hoạt động giai đoạn view frustum culling. Thực hiện view frustum culling như sau : Duyệt cây khung cảnh theo chiều sâu - Tại mỗi node, kiểm tra vị trí của tree bounding sphere so với khung nhìn ( tree bounding sphere là một trong hai loại tree BV của mỗi SceneNode ) : + Nếu nằm trong : toàn bộ nhánh cây với gốc là node này nằm trong khung nhìn, không cần duyệt các node thuộc nhánh này nữa. + Nếu nằm ngoài : toàn bộ nhánh cây với gốc là node này nằm ngoài khung nhìn, toàn bộ node trong nhánh nằm bị bật cờ trạng thái FRUSTUM_CULLED ( đánh dấu đã bị cắt ) và không cần duyệt đến các node thuộc nhánh này nữa. + Nếu giao : kiểm tra vị trí của tree bounding box so với khung nhìn ( vì bounding box bó sát vật thể hơn nhiều so với bounding sphere ). # Nằm trong : toàn bộ nhánh cây với gốc là node này nằm trong khung nhìn, không cần duyệt các node thuộc nhánh này nữa. # Nằm ngoài : toàn bộ nhánh cây với gốc là node này nằm ngoài khung nhìn, toàn bộ node trong nhánh nằm bị bật cờ trạng thái FRUSTUM_CULLED ( đánh dấu đã bị cắt ) và không cần duyệt đến các node thuộc nhánh này nữa. # Giao : không kết luận gì, đi đến node tiếp theo. c. Thuật toán kiểm tra vị trí của bounding sphere so với khung nhìn Để kiểm tra ví trị của một bounding sphere so với frustum, ta thực hiện như sau : Với từng mặt phẳng của Frustum : + Tính khoảng cách d từ tâm đến mặt phẳng + Nếu d < -R. Kết luận: bounding sphere nằm bên ngoài frustum + Nếu R > d > -R. Kết luận: bounding sphere giao với frustum Ngược lại, kết luận bounding sphere nằm bên ngoài Frustum ( R là bán kính của bounding sphere ) Hình 22: Ví dụ một Bounding Sphere có d > R. d. Thuật toán kiểm tra vị trí của bounding box với khung nhìn Thuật toán cơ bản để kiểm tra ví trí của bounding box với frustum là kiểm tra vị trí của 8 đỉnh của bounding box so với khung nhìn : - Nếu tất cả các đỉnh đều nằm trong thì kết luận bounding box nằm trong. - Nếu tất cả các đỉnh nằm ngoài thì kết luận bounding box nằm ngoài. - Các trường hợp còn lại kết luận bounding box giao với khung nhìn. Có nhiều tối ưu cho thuật toán trên và chúng tôi đã triển khai các tối ưu trong [3] 3.3.5. Render các render-list a. Khái niệm render-list Một render-list là tập hợp các Scene Node có chung các trạng thái render. Các trạng thái render ở đây là các trạng thái của openGL và một số trạng thái khác của GEM. Việc tập trung các Scene Node thành các render list sẽ hạn chế tối đa việc chuyển các trạng thái render, giúp tăng hiệu suất hệ thống. Một Scene Node có thể cùng lúc ở nhiều render-list. b. Các render list của GEM Trong GEM có 16 render list sau : - ERL_SKY_BOX : Render list đặc biệt dành cho SkyboxSceneNode, do loại node này phải đặt một số trạng thái render đặc biệt. - ERL_LIGHT : Render list đặc biệt dành cho các nguồn chiếu sáng (LightSceneNode và DLightSceneNode ). - ERL_SOLID : Render list mặc định dành cho các loại node có dạng đặc ( không nhìn xuyên qua được ). - ERL_TRANLUCENT : Render list mặc định dành cho các loại node có dạng trong suốt ( hình xuyên qua được ). - ERL_USER_DEFINE0 -> 9 : 10 Render list dành sẵn cho người sử dụng tùy biến. - ERL_SHADOW_VOLUME : Render list đặc biệt dành để render bóng của vật thể. - ERL_OCCLUSION_TEST : Render list dùng trong quá trình occlusion culling. c. Biểu đồ hoạt động Hình 23: Biều đồ hoạt động của giai đoạn render từng render-list. Quá trình render các render list như sau : - Bước 1: Đi đến list tiếp theo - Bước 2 : bật các trạng thái render cần thiết được lưu trong render context của list ( gọi hàm pushState() của RenderContext ) - Bước 3: Sắp xếp list theo khoảng cách đến camera theo thứ tự từ xa đến gần hoặc ngược lại ( nếu trong render context có trạng thái yêu cầu sắp xếp các node ). - Bước 4 : Loại bỏ các node có cờ FRUSTUM_CULLED được bật ( do các node nằm ngoài khung nhìn ). - Bước 5 : Kiểm tra xem list có thực hiện occlusion culling hay không : + Nếu không : render toàn bộ các node trong list. + Nếu có : thực hiện thuật toán occlusion culling/ + Bước 6 : Phục hồi toàn bộ các trạng thái render được bật trong bước 2 ( gọi hàm popState() của RenderContext ) e.Occlusion culling Occlusion culling là việc phát hiện các vật thể bị chắn hoàn toàn bởi các vật thể khác và loại chúng ra khỏi quá trinh render. Hình 24: Ví dụ minh họa một vật thể bị chắn hoàn toàn. Chúng tôi triển khai thuật toán occlusion culling được trình bày trong [4]. Chương 4. Tổng kết 4.1. Kết quả Chúng tôi đã xây dựng được module quản lý khung cảnh hoạt động một cách hiệu quả và chính xác. Cụ thể chung tôi đã thu được kết quả thực thi các giai đoạn trong quá trình render cây khung cảnh như sau : Cấu hình máy thử nghiệm : CPU : T7100 (1.8GHz x 2) RAM : 2 GB Card đồ họa : NVIDIA GeForce 8400M GS OS : Window Vista Home Premium Bảng đánh giá thời gian thực thi giai đoạn prepare-render : Số lượng SceneNode Trường hợp Thời gian thực thi prepare-render ( millisecond) 1000 Tất cả các node đứng yên không biến đổi (TH1) ~0.4 Tất cả các node biến đổi về cả : dịch chuyển, xoay, co giãn. ( TH2) ~1.4 2000 TH1 ~0.5 TH2 ~2.2 10000 TH1 ~2.2 TH2 ~8.3 Bảng đánh giá thời gian thực thi giai đoạn Tính lại BVHs Số lượng SceneNode Trường hợp Thời gian thực thi Tính lại BVHs ( millisecond) 1000 TH1 ~0.0 TH2 ~0.4 2000 TH1 ~0.0 TH2 ~0.7 10000 TH1 ~0.0 TH2 ~4.2 Thời gian thực thi giai đoạn Tính lại các ma trận biến đổi của Camera và tính khung nhìn gần như là cố định do luôn luôn chỉ có 1 active camera, thời gian này rất nhỏ ~0ms. Bảng đánh giá thời gian thực thi giai đoạn View frustum culling : Số lượng SceneNode Trường hợp Thời gian thực thi View frustum culling ( millisecond) 1000 Tất cả các node đều là con của root ( nên chúng độc lập với nhau ) ( TH1vfc) ~0.5 - Node thứ 10*n là con của root - Node thứ 10*n+1..9 là con của node 10*n n >= 0 ( TH2vfc ) ~0.4 2000 TH1vfc ~0.8 TH2vfc ~0.5 10000 TH1vfc ~1.4 TH2vfc ~0.9 Thời gian thực thi giai đoạn Render từng render-list phụ thuộc chủ yếu vào thời gian render từng loại node nên chúng tôi không đưa ra đánh giá ở đây. Hình ảnh một khung cảnh trong nhà : Hình 25: Khung cảnh trong nhà được render bởi GEM. 4.2. Hướng phát triển Như đã nêu ở những phần trên, chúng tôi sử dụng 16 render-list tập trung các node có chung trạng thái render, hạn chế tối đa việc chuyển trạng thái. Việc làm này giúp tăng hiệu suất nhưng lại làm giảm tính mềm dẻo của hệ thống. Một hướng phát triển là tìm kiếm phương pháp mới đặt hiệu suất tương đương nhưng mang lại cho người sử dụng nhiều tự do hơn. Ngoài ra, một vấn đề nghiên cứu khác là việc sử dụng thêm cấu trúc phân chia không gian (spatial partitioning) như oct-tree hay quad-tree, cấu trúc này sẽ giúp tăng tốc quá trình view-frustum-culling cho các đối tượng tĩnh. Còn về cả hệ thống Game Engine, vẫn còn nhiều thành phần : âm thanh, kết nối mạng, tính toán vật lí… cần được triển khai để nó trở thành một hệ thống hoàn chỉnh đáp ứng các yêu cầu của người phát triển game. Phụ lục Bảng các kí hiệu UML Kí hiệu Tên Ý nghĩa Activity Thể hiện một hành động Aggregation Thể hiện quan hệ kết tập Choice Điểm rẽ nhánh có điều kiện Class Thể hiện một lớp Composition Thể hiện quan hệ hợp thành Control Flow Thể hiện luồng điều khiển Dependency Thể hiện quan hệ phụ thuộc Final state Điểm kết thúc. Genaralization Thể hiện quan hệ tổng quát hóa. Initial state Điểm bắt đầu. Class Thể hiện một lớp Package Thể hiện một gói Tài liệu tham khảo Tiếng Anh : Karel Driesen and Urs Hölzle, The Direct Cost of Virtual Function Calls in C++, 1995 ACM. Gribb, Hartmann , Fast Extraction of Viewing Frustum Planes from the World-View-Projection Matrix, June 2001. Ulf Assarsson and Tomas M¨oller, Optimized View Frustum Culling Algorithms for Bounding Boxes, February 2000 Dean Sekulic, Croteam. Chapter 29.”Efficient Occlusion Culling” in GPU Gems, Addison-Wesley Professional (April 1, 2004)