Phương pháp hiệu quả xác định kết quả tiêu diệt mục tiêu thời gian thực trong không gian mô phỏng - Dương Hồng Trường

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 143 PHƯƠNG PHÁP HIỆU QUẢ XÁC ĐỊNH KẾT QUẢ TIÊU DIỆT MỤC TIÊU THỜI GIAN THỰC TRONG KHÔNG GIAN MÔ PHỎNG Dương Hồng Trường*, Đoàn Văn Hòa, Bạch Hồng Quyết Tóm tắt: Trong lĩnh vực công nghệ mô phỏng đặc biệt là mô phỏng huấn luyện trong quân sự, khi một ứng dụng mô phỏng thời gian thực được thực hiện, máy tính phải xử lý một khối lượng các công việc và phép tính cực lớn bao gồm tính toán và kết xuất hình ảnh 3D, tạo ra các hiệu ứng thời tiết mây- mưa-sóng-gió, hiệu ứng chiến trường-cháy nổ, hiệu ứng âm thanh sinh động. Ngoài ra, nó còn phải song song thực hiện các công việc khác như đồng bộ các máy sinh ảnh, xử lý giao tiếp người - máy, giao tiếp với các thiết bị ngoại vi, tính toán bài toán va chạm đường đạn, tiêu diệt mục tiêu... Để xử lý được một khối lượng công việc khổng lồ như thế trong khi vẫn phải đáp ứng được về tốc độ thực thi và độ chính xác cao thì trong từng khâu, từng hàm, từng mô đun xử lý đều phải được tối ưu nhất có thể. Bài báo trình bày một phương pháp hiệu quả bằng cách chia vật thể có cấu trúc hình học phức tạp thành các hình khối cơ bản để từ đó dùng các thuật toán xử lý để vẫn đảm bảo được độ chính xác đánh trúng mục tiêu và giảm đáng kể số lượng các phép toán, đảm bảo được việc thực thi của máy tính. Từ khóa: Không gian mô phỏng, Thời gian thực, Tiêu diệt mục tiêu, Đối tượng 3D. 1. MỞ ĐẦU Trong khuôn khổ bài báo, nhóm tác giả sẽ trình bày một phương pháp hiệu quả để tính toán xác định kết quả tiêu diệt mục tiêu thời gian thực trong không gian mô phỏng. Một đối tượng chiến đấu 3D như tàu chiến, máy bay, xe quân sự... được tạo thành từ tập hợp các mặt đa giác, mỗi đa giác được tạo nên từ ít nhất 3 điểm trở lên, mỗi điểm là một tập giá trị tọa độ theo 3 trục Ox, Oy, Oz trong không gian. Số lượng điểm và đa giác càng lớn thì đối tượng càng chi tiết, càng đẹp và giống thật hơn. Thông thường để xác định đường đạn có chạm vào mục tiêu hay không người ta sẽ phải tính xem tọa độ tức thời của đạn có giao với một trong các mặt đa giác đó hay không. Khi mà số lượng các mặt đa giác của đối tượng là hàng nghìn thậm chí hàng vạn thì số phép tính phải tính toán tức thời lên đến hàng triệu đến mức mà máy tính thông thường không thể xử lý kịp, dẫn đến tình trạng máy tính bị treo. Để cân bằng giữa các yếu tố về độ chính xác và hiệu năng tính toán, bài báo đề xuất giải pháp là sẽ chia một đối tượng 3D thành một số khối hình học cơ bản như: hình nón cụt, hình elip đặc, hình hộp, hình đa giác. Thay vì phải tính toán va chạm cho tất cả các mặt theo cách truyền thống thì ta chỉ tính toán va chạm với từng khối nhỏ tạo nên đối tượng rồi tổng hợp kết quả lại. Với mỗi loại hình khối cơ bản ở trên, nhóm tác giả đều đã nghiên cứu và xây dựng các thuật toán tối ưu tương ứng. Với hướng tiếp cận này sẽ đảm bảo hài hòa được yếu tố hiệu năng, tốc độ thực thi của ứng dụng mô phỏng và độ chính xác chấp nhận được. 2. CÁC PHƯƠNG PHÁP, THUẬT TOÁN XÁC ĐỊNH MỘT ĐIỂM NẰM TRONG HAY NGOÀI CÁC KHỐI HÌNH HỌC CƠ BẢN 2.1. Phương pháp chiếu tia Phương pháp chiếu tia (Ray casting) [1, 3, 4] là một trong những phương pháp thường dùng để xác định 1 điểm nằm trong hay ngoài 1 khối hình học trong Công nghệ thông tin D. H. Trường, Đ. V. Hòa, B. H. Quyết, “Phương pháp hiệu quả không gian mô phỏng.” 144 không gian 2 chiều (2D) hoặc 3 chiều (3D). Phương pháp này có độ chính xác cao, tuy nhiên không phải mọi trường hợp đều có thể áp dụng được vì trong một số ứng dụng mô phỏng không có phương trình cụ thể để miêu tả hết bề mặt bao của vật thể. Nguyên tắc xác định một điểm nằm trong đa giác (2D): Một điểm nằm trong đa giác (lồi hoặc lõm) khi và chỉ khi số giao điểm từ một tia bất kỳ xuất phát từ điểm đó với các cạnh của đa giác phải là một số lẻ. Ngược lại, nếu số giao điểm là chẵn thì điểm nằm ngoài đa giác [4]. Tia xuất phát có thể sang phải hay sang trái, lên hoặc xuống bất kỳ hướng nào nhưng phải giao với đa giác. Lưu ý, tại các đỉnh cực trị thì một giao điểm cần xem xét cụ thể đối tượng hình học cụ thể để có thuật toán phù hợp. Xét đa giác lồi 7 cạnh với 7 đỉnh là P0, P1, ....., P6 trong hình sau (hình 1). Hình 1. Phương pháp chiếu tia áp dụng cho đa giác lồi. Với 2 điểm P, Q trong hình trên, chiếu tia xuất phát từ các điểm này giao với đa giác. Ta thấy tia đi từ P cắt đa giác ở 2 điểm nên nó nằm ngoài đa giác, tia đi từ Q cắt đa giác ở 1 điểm nên nó nằm trong đa giác. Nếu tia đi qua điểm không cắt với đa giác ở điểm nào thì hiển nhiên là điểm đó nằm ngoài đa giác. Trường hợp đa giác lõm thì phương pháp chiếu tia vẫn cho kết quả chính xác như hình dưới đây (hình 2). Hình 2. Phương pháp chiếu tia áp dụng cho đa giác lõm. Tia xuất phát từ điểm P giao ở 4 điểm nên nó nằm ngoài đa giác, tia xuất phát từ điểm Q giao ở 3 điểm nên nó ở trong đa giác. P Q P0 P1 P2 P3 P4 P5 P6 P Q P0 P1 P2 P3 P4 P5 P6 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 145 Nguyên tắc xác định một điểm nằm trong đa diện (3D): Từ phương pháp xác định 1 điểm nằm trong hay ngoài đa giác trong mặt phẳng 2D ở trên ta có thể phát triển lên để áp dụng cho không gian 3D: 1 điểm nằm trong 1 đa diện khi và chỉ khi số giao điểm từ một tia bất kỳ đi qua nó giao với các mặt của đa diện là số lẻ. Ngược lại, nếu số giao điểm là chẵn thì điểm đó sẽ nằm ngoài đa diện. Phương pháp này cũng đúng cho cả trường hợp đa diện lồi hay lõm. Trường hợp ngoại lệ khi tia đi qua điểm cực trị thì xem xét phân tích cụ thể đặc thù cũng như thuộc tính của các điểm đó để có thuật toán phù hợp. 2.2. Phương pháp diện tích Phương pháp diện tích dùng để xác định 1 điểm nằm trong hay ngoài 1 khối hình học trong không gian 2D hoặc 3D là một phương pháp rất cơ bản, độ chính xác cao và khá hiệu quả. Nhược điểm là phương pháp này chỉ áp dụng được cho đa giác lồi hoặc đa diện lồi. Phương pháp diện tích dùng những kiến thức phổ thông về cách tính diện tích để giải quyết bài toán. Trước hết, ta đi vào trường hợp đơn giản nhất với việc xác định 1 điểm nằm trong hay ngoài 1 tam giác trong mặt phẳng 2D (hình 3). Hình 3. Phương pháp diện tích áp dụng cho tam giác trong mặt phẳng 2D. Với 1 tam giác bất kỳ thì diện tích của nó được tính theo công thức Heron: (1) Trong đó: a, b, c là độ dài các cạnh, p = (a+b+c)/2 là nửa chu vi tam giác. Xét tam giác ABC và điểm P như hình trên. Tổng diện tích 3 tam giác con tạo ra từ P với các cạnh của tam giác ABC là SPAB + SPAC + SPBC. Nếu tổng này lớn hơn SABC thì P nằm ngoài tam giác ABC và ngược lại. Trong trường hợp tổng quát với đa giác có n đỉnh P0, P1, Pn và 1 điểm P bất kỳ Diện tích của đa giác là: (2) Tổng diện tích các tam giác con tạo ra bởi P và các cạnh của đa giác (3) Nếu SP > Sdg thì P nằm ngoài đa giác, ngược lại P nằm trong đa giác [2]. A B C P Công nghệ thông tin D. H. Trường, Đ. V. Hòa, B. H. Quyết, “Phương pháp hiệu quả không gian mô phỏng.” 146 Trong hình dưới đây minh họa cho trường hợp điểm P nằm trong và Q nằm ngoài đa giác lồi có 7 đỉnh P0, P1, ..P6 (hình 4). Hình 4. Phương pháp diện tích áp dụng cho đa giác lồi trong mặt phẳng 2D. Phương pháp diện tích dùng để xác định 1 điểm nằm trong hay ngoài 1 khối đa diện lồi trong không gian 3D: - Tính tổng diện tích các mặt xung quanh của khối đa diện bằng cách chia nhỏ các mặt của khối đa diện thành các tam giác con. - Nối điểm cần xác định với tất cả các cặp cạnh của đa diện được tập các tam giác con và tính tổng diện tích của chúng. - So sánh 2 tổng diện tích và kết luận được điểm nằm trong hay ngoài khối đa diện. 2.3. Thuật toán xác định 1 điểm nằm trong hay ngoài hình nón cụt Hình nón cụt là một dạng khối hình nón 3D nhưng bị cắt cụt ở phần chóp, đây cũng là dạng tổng quát của hình nón cơ bản. Các tham số đặc trưng của hình nón là: bán kính đáy lớn R, bán kính đáy nhỏ r, chiều cao nón cụt h như hình sau: Hình 5. Hình nón cụt.  Thuật toán: 1. Tìm tọa độ tâm C của đáy lớn và c đáy nhỏ. 2. Tìm tọa độ hình chiếu H của điểm P lên đường thẳng đi qua 2 tâm C và c. P0 P1 P2 P3 P4 P5 P6 Q P0 P1 P2 P3 P4 P5 P6 P Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 147 Hình 6. Hình minh họa 1 điểm nằm trong và ngoài hình nón cụt. 3. Nếu H không thuộc đoạn thẳng Cc thì điểm P nằm ngoài hình nón cụt. 4. Nếu H thuộc đoạn thẳng Cc, tính bán kính tròn tại tâm H của nón cụt theo công thức: RH = dis(HC) / h * r + dis(Hc) / h * R (4) Trong đó: dis(HC) - Độ dài đoạn HC; dis(Hc) - Độ dài đoạn Hc. 5. Nếu khoảng cách PH > RH thì điểm P nằm ngoài nón cụt, ngược lại P nằm trong nón cụt [5-8]. 2.4. Thuật toán xác định một điểm nằm trong hay ngoài hình hộp chữ nhật Hình hộp chữ nhật là một khối hình học cơ bản thường gặp trong thực tế. Các tham số cơ bản của nó là tọa độ các đỉnh, chiều dài, chiều rộng, chiều cao. Xét 1 hình hộp chữ nhật gồm 8 đỉnh P0, P1, P2, P3, P4, P5, P6, P7 (hình 7) đặt , , . Hình 7. Hình hộp chữ nhật. Thuật toán: Một điểm P trong không gian 3D với hệ trục tọa độ Oxyz được xác định nằm bên trong một hình hộp chữ nhật nếu nó thỏa mãn đồng thời các điều kiện sau [9,10]: 1. Tích vô hướng nằm giữa và . 2. Tích vô hướng nằm giữa và . .P P0 P1 P2 P3 P4 P5 P6 P7 Công nghệ thông tin D. H. Trường, Đ. V. Hòa, B. H. Quyết, “Phương pháp hiệu quả không gian mô phỏng.” 148 3. Tích vô hướng nằm giữa và . 2.5. Phương pháp xác định một điểm nằm trong hay ngoài hình elip đặc Hình elip đặc là 1 dạng khối hình học 3D với các tham số cơ bản là tọa độ tâm và độ dài 3 bán trục. Hình cầu chính là trường hợp đặc biệt của hình elip đặc với 3 bán trục đều bằng nhau. Hình 8. Hình elip đặc. Phương trình của đường elip đặc trong không gian 3D như sau: (5) Trong đó: a, b, c là các bán trục của elip đặc Phương trình trên là phương trình chuẩn với tâm elip đặc trùng với gốc tọa độ O và các bán trục nằm trên các trục Ox, Oy, Oz. Trong thực tế, hình elip đặc có tâm với tọa độ bất kỳ và các bán trục còn có thể quay theo các trục tọa độ. Giả sử tâm elip đặc là C(xc, yc, zc) thì phương trình elip đặc trở thành: (6) Từ phương trình (6) ta đưa ra được phương pháp xác định 1 điểm P nằm trong elip đặc nếu tọa độ của nó thỏa mãn [9]: (7) Trong trường hợp tổng quát hình elip đặc còn có thể quay theo 1 hay nhiều trục tọa độ với các góc quay khác nhau. Lúc này việc xác định 1 điểm nằm trong elip đặc như ở phương trình (7) không còn đúng nữa mà lúc này cần phải có các phép hiệu chỉnh cần thiêt. Ví dụ: Giả sử elip đặc quay quanh trục Z một góc  theo chiều ngược kim đồng hồ. Lúc này ta phải sử dụng phép biến đổi quay hình trong kỹ thuật đồ họa, Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 149 hệ tọa độ xyz sẽ được ánh xạ sang hệ trục tọa độ mới XYZ với các công thức biến đổi sau: (8) 3. PHÂN TÍCH, THỰC NGHIỆM Trong phần này , bài báo sẽ thực nghiệm chia 1 đối tượng máy bay chiến đấu thành nhiều khối nhỏ với 1 trong các hình dạng: hình nón cụt, hình hộp chữ nhật, hình elip đặc, hình đa giác. Áp dụng các phương pháp, thuật toán xác định 1 điểm nằm trong hay ngoài khối hình học đã nghiên cứu ở trên ta sẽ xác định được viên đạn có bắn trúng từng phần nhỏ của đối tượng hay không. Nếu có ít nhất 1 khối con bao lấy tọa độ tức thời của đạn thì đối tượng đã bị trúng đạn và không cần thiết phải xem xét đến các khối còn lại, ngược lại nếu không có 1 khối nào thỏa mãn điều kiện thì trắc thủ đã bắn trượt mục tiêu. Đối tượng máy bay chiến đấu được xét đến là máy bay tiêm kích F-5 Tiger II của không quân Mỹ [11]. Hình 9. Hình dạng máy bay tiêm kích F-5E Tiger II. Các thông số về kích thước và kết cấu của đối tượng như sau: Bảng 1. Thông số máy bay tiêm kích F-5E Tiger II. Chiều dài (m) Chiều rộng (m) Chiều cao (m) Số đỉnh Số mặt Số tam giác 14,45 7,79 4,06 121183 25804 69575 Từ bảng thông số ta thấy cần 69575 mặt tam giác để dựng lên máy bay, đây là con số quá lớn, nếu tính toán va chạm cho tất cả các tam giác này thì không thể đáp ứng được yêu cầu về tốc độ của ứng dụng. Do đó, ta phải chia đối tượng thành các phần nhỏ dựa vào kết cấu hình học của nó. Cách chia đối tượng phải đảm bảo sao cho tập bao hợp bởi tất cả các khối được chia ra nhỏ hơn hoặc bằng máy bay thật, hay nói cách khác là tập bao này nằm bên trong máy bay thật. Phương pháp chia nhỏ đối tượng thành các khối hình học cơ bản mục đích là làm giảm đáng kể số lượng phép tính phải thực hiện nhưng vẫn đáp ứng được yêu cầu đạt độ chính xác cao trong việc giải bài toán xác định kết quả tiêu diệt mục tiêu. Thực tế, nếu trắc thủ bắn trúng tập bao thì cũng có nghĩa là đường đạn càng tập trung vào tâm đối tượng hơn và càng giúp nâng cao kỹ năng, trình độ bắn của trắc thủ. Công nghệ thông tin D. H. Trường, Đ. V. Hòa, B. H. Quyết, “Phương pháp hiệu quả không gian mô phỏng.” 150 Từ cấu trúc hình học và thiết kế của máy bay tiêm kích F-5 Tiger II ở trên ta nhận thấy 2 cánh lớn, 2 cánh nhỏ và đuôi máy bay có độ dày nhỏ và nhỏ hơn rất nhiều nếu so với bề rộng của nó nên trong bài toán mô phỏng có thể quy thành các đa giác phẳng. Phần thân máy bay có nhiều tính chất đối xứng, trụ, tròn xoay nên có thể chia thành các khối hình nón cụt, elip đặc, thậm chí có thể chia thành hình hộp. Kết quả việc chia nhỏ đối tượng bằng phần mềm MultiGen Creator như sau (hình 10): Hình 10. Chia nhỏ đối tượng F-5 Tiger II thành các khối hình học cơ bản. Từ các thông số ban đầu của máy bay F-5 Tiger II ta qua quá trình chia tách thu được cấu trúc hình học chỉ còn là các khối hình học như bảng sau (bảng 2). Tổng cộng có 13 khối hình học cơ bản: 5 đa giác, 3 hình chóp cụt, 3 hình elip đặc và 2 hình hộp chữ nhật. Giảm đến hơn 5000 lần số lượng các khối hình học cơ bản và thuật toán đã đảm bảo được việc thực thi mô phỏng thời gian thực đánh trúng mục tiêu. Bảng 2. Bảng thống kê các khối hình học tạo thành đối tượng. Bộ phận Hình đa giác Hình chóp cụt Hình elip đặc Hình hộp chữ nhật Đầu máy bay 0 1 1 1 Giữa máy bay 0 0 2 1 Cuối máy bay 0 2 0 0 Đuôi, cánh 5 0 0 0 Tổng cộng (13) 5 3 3 2 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 151 4. KẾT LUẬN Bài báo đã đề xuất phương pháp chia nhỏ một đối tượng 3D trong không gian mô phỏng với rất nhiều các đỉnh và mặt thành số lượng nhỏ các khối hình học cơ bản bao gồm: hình đa giác, hình nón cụt, hình elip đặc, hình hộp chữ nhật. Với mỗi loại khối, bài báo đưa ra những phương pháp, thuật toán chính xác và phù hợp nhất để xác định 1 điểm bất kỳ trong không gian nằm trong hay ngoài khối hình học đó. Từ việc phân rã đối tượng thành nhiều phần nhỏ như thế, việc xác định kết quả tiêu diệt mục tiêu trở nên nhẹ nhàng hơn rất nhiều. Với sự ước tính bằng lý thuyết và bằng việc thực thi ứng dụng trực tiếp bằng phương pháp này, nhóm tác giả thấy rằng số lượng phép tính phải thực hiện đã được giảm xuống vài trăm đến hàng nghìn lần. Do đó, hiệu quả của phương pháp chia nhỏ đối tượng mang lại là rất rõ rệt, giúp tăng tốc độ, hiệu năng của ứng dụng mô phỏng. Tuy nhiên, những nghiên cứu trên đây cũng mới chỉ là những kết quả bước đầu. Hướng phát triển trong thời gian tới của nhóm tác giả là sẽ mở rộng thuật toán cho 1 số đối tượng hình học đặc biệt khác như: hình lăng trụ, hình vành xuyến, hình ống .., đồng thời, cũng cải tiến, nâng cao độ chính xác các thuật toán đã có. Những kết quả nghiên cứu này sẽ giúp ích rất nhiều trong việc lập trình, xây dựng các ứng dụng mô phỏng thời gian thực sau này. TÀI LIỆU THAM KHẢO [1]. John F. Hughes, Andries van Dam, Morgan McGuire, David F. Sklar, James D. Foley, Steven K. Feiner, Kurt Akeley, “Computer Graphics: Principles and Practice”, 3rd Edition, Pearson Education Inc, 2014. [2]. James D. Foley, Andries van Dam, Steven K. Feiner, John F. Hughes, “Computer Graphics: Principles and Practice”, 2nd Edition, Addison-Wesley, 1995. [3]. John Vince, “Mathematics for Computer Graphics”, 4th Edition, Springer, 2014. [4]. Ths Võ Phương Bình, Giáo trình “ĐỒ HỌA MÁY TÍNH“, Đại học Đà Lạt 2010. [5]. J. D Foley, A. Van Dam, S. K Feiner, J. F Hughes, “Computer graphics: principles and practice”, Addison-Wesley 1991. [6]. F. S. Hill Jr. Computer Graphics, Macmillan Publishing Company, New York 1990. [7]. John Vince, “Calculus for Computer Graphics”, Springer, 2013. [8]. John Vince, “Matrix Transforms for Computer Games and Animation”, Springer, 2012. [9]. John Vince, “Rotation Transforms for Computer Graphics”, Springer, 2011. [10]. John Vince, “Quaternions for Computer Graphics”, Springer, 2011. [11]. https://vi.wikipedia.org/wiki/Northrop_F-5. Công nghệ thông tin D. H. Trường, Đ. V. Hòa, B. H. Quyết, “Phương pháp hiệu quả không gian mô phỏng.” 152 ABSTRACT AN EFFICIENT SOLUTION DETERMINES RESULT OF DESTROY THE TARGET REALTIME IN SIMULATION SPACE In the field of simulation technology, especially military training simulators, when a real-time simulation application is run, the computer must handle a tremendous amount of workload and calculation including computation. And render 3D images, create weather effects clouds-rain- wave-wind, battlefield effects-fire explosion, sound effects vivid. In addition, it also has to perform other tasks such as synchronization of cameras, human-machine interface, interface with peripherals,... To handle such a huge workload while still having to meet the speed of execution and high accuracy, in each step, each function, each module must be processed, optimal as possible. The paper presents an effective method by dividing complex geometric objects into basic shapes so that they can use the processing algorithms to ensure accuracy hits the target and decreases Significant number of operations, ensuring the performance of the computer. Keywords: Space simulation, Real-time simulation, Destroy target, 3D objects. Nhận bài ngày 16 tháng 8 năm 2017 Hoàn thiện ngày 26 tháng 11 năm 2017 Chấp nhận đăng ngày 28 tháng 11 năm 2017 Địa chỉ: Viện CNTT, Viện KH&CN quân sự. * Email: kvtt2511@gmail.com.