Voxel Terrain: Vật lý
Trong bài viết trước, chúng ta đã thảo luận về các chi tiết cụ thể của định nghĩa và lưu trữ dữ liệu voxel cho địa hình voxel trên Roblox. Từ đó, nhiều hệ thống khác đọc và ghi dữ liệu từ bộ lưu trữ và giải thích nó theo những cách khác nhau. Việc triển khai cho từng hệ thống (hiển thị, mạng, vật lý) là hoàn toàn riêng biệt và không phụ thuộc vào bất kỳ quyết định nào của bộ lưu trữ hoặc các hệ thống khác, vì vậy chúng ta có thể nghiên cứu chúng một cách độc lập.
Mặc dù về mặt logic, sẽ hợp lý hơn nếu chúng ta xem xét mesher tiếp theo (đó là cách chúng ta gọi thành phần có khả năng lấy một hộp dữ liệu voxel và tạo ra dữ liệu tam giác đại diện cho bề mặt địa hình với các thuộc tính vật liệu), vì nó được sử dụng bởi cả hệ thống vật lý và hiển thị, nhưng thuật toán này khá phức tạp và có khá nhiều “phép thuật”, vì vậy chúng ta sẽ để nó lại cho một dịp khác và thay vào đó, hôm nay chúng ta sẽ xem xét hệ thống vật lý.
Mẫu thử nghiệm ban đầu
Hỗ trợ vật lý là yếu tố quan trọng đối với địa hình vì phần lớn nội dung trên Roblox phụ thuộc vào hành vi vật lý mạnh mẽ, cả trong trò chơi và trong trình chỉnh sửa. Đặc biệt đối với địa hình, việc hỗ trợ vật lý có nghĩa là triển khai tính năng phát hiện va chạm giữa địa hình và tất cả các hình dạng khác mà chúng tôi sử dụng, cũng như hỗ trợ raycast một cách hiệu quả. Chúng tôi quan tâm đến hiệu suất và mức tiêu thụ bộ nhớ, vì giả định rằng một số thế giới sẽ phụ thuộc rất nhiều vào địa hình và vật lý địa hình.
Mặc dù công cụ vật lý của chúng tôi là công cụ tùy chỉnh, nhưng chúng tôi sử dụng một số thành phần của Bullet Physics cho giai đoạn rộng/giai đoạn hẹp (cụ thể là cho các đối tượng lồi phức tạp và phân tách lồi, dựa trên triển khai GJK của Bullet và một số thuật toán khác), vì vậy việc bắt đầu bằng việc tạo mẫu thử nghiệm giải pháp dựa nhiều vào Bullet là điều hợp lý.
Tương tự như lưu trữ voxel, chúng tôi chia toàn bộ thế giới thành các khối và biểu diễn mỗi khối dưới dạng đối tượng va chạm; việc chia này rất quan trọng vì mỗi khối trở thành đơn vị cập nhật dữ liệu vật lý. Vì địa hình có thể thay đổi bất cứ lúc nào, kích thước khối là sự cân bằng giữa chi phí cập nhật (nếu khối quá lớn, mỗi lần cập nhật một voxel trong khối đó, chúng tôi sẽ phải chịu chi phí cao để cập nhật toàn bộ khối. Hiện tại, chúng tôi giả định rằng cập nhật theo từng phần quá phức tạp để triển khai vì sự thay đổi của voxel có thể dẫn đến thay đổi về cấu trúc lưới kết quả) và chi phí quản lý khối (nếu một khối có 2^3 voxel, thì chúng tôi sẽ phải tốn nhiều thời gian/bộ nhớ để quản lý các khối). Chúng tôi đã quyết định chọn 8^3 khối (nhắc lại, một nhân vật cao hơn một voxel một chút, điều này sẽ giúp bạn hình dung được quy mô) như một sự cân bằng giữa các yếu tố này.
Mặc dù chúng tôi có thể thử thực hiện va chạm trực tiếp bằng cách sử dụng biểu diễn voxel cơ bản, nhưng thuật toán tạo lưới mà chúng tôi sử dụng rất phức tạp và khiến việc dự đoán chính xác vị trí bề mặt trở nên khó khăn nếu không chạy thuật toán. Vì các voxel của chúng tôi khá lớn, chúng tôi muốn biểu diễn hiển thị và vật lý khớp chặt chẽ để loại bỏ các hiện tượng hình ảnh không mong muốn, do đó chúng tôi quyết định sử dụng biểu diễn đa giác cho va chạm.
Do đó, bản mẫu đã lấy từng khối, chạy mesher trên khối đó để tạo ra một lưới tam giác từ nó, sau đó tạo ra một đối tượng va chạm Bullet bằng cách sử dụng btBvhTriangleMeshShape. Các đối tượng kết quả được chèn vào cấu trúc broadphase chung cùng với các đối tượng khác trong thế giới. Bất cứ khi nào một đối tượng, ví dụ như một quả bóng, giao nhau với một trong các khối, chúng tôi sẽ tạo ra một đối tượng tiếp xúc và sau đó chạy các thuật toán của Bullet để xác định các điểm tiếp xúc.
Mặc dù nguyên mẫu này đã giúp chúng tôi bắt đầu, nhưng nó cũng chỉ ra một số lĩnh vực cần cải thiện quan trọng:
- Dữ liệu giai đoạn rộng (Broadphase) quá thiếu chính xác: mỗi khi một đối tượng giao cắt với một khối voxel 8^3, chúng ta phải chạy thuật toán giai đoạn hẹp (Narrowphase) trên điểm tiếp xúc; điều này dẫn đến nhiều điểm tiếp xúc dư thừa không tạo ra bất kỳ điểm tiếp xúc nào, đặc biệt trong các hang động nơi một đối tượng treo lơ lửng có thể chồng lên hộp giới hạn của một khối voxel tương đối lớn nhưng không bao giờ chạm vào bất kỳ hình học nào.
- Dữ liệu giai đoạn hẹp quá lớn: đối với mỗi khối, chúng tôi phải lưu trữ lưới tam giác, vốn kém gọn gàng hơn dữ liệu voxel (vì chúng tôi cần lưu trữ vị trí/chỉ số đỉnh), cùng với cấu trúc BVH của Bullet được sử dụng để tăng tốc va chạm, vốn cũng khá lớn.
- Dữ liệu giai đoạn hẹp quá chậm để tạo ra: mặc dù thuật toán tạo lưới của chúng tôi đã được tối ưu hóa rất nhiều, nhưng quá trình xử lý lưới kết quả của Bullet tương đối chậm (chậm hơn tới 3 lần so với việc tạo lưới).
Điều này cho thấy rằng chúng tôi cần thay đổi cách tiếp cận cho cả broadphase và narrowphase. Hãy xem chúng tôi đã làm gì ở đó.
Giai đoạn broadphase: xây dựng
Vì vấn đề chính của giai đoạn broadphase là độ chính xác, chúng tôi quyết định cho giai đoạn broadphase biết cấu trúc của từng đối tượng và thực hiện loại bỏ sớm dựa trên dữ liệu voxel thực tế. Mỗi khi một đối tượng di chuyển, thay vì tạo tiếp xúc với từng khối chồng chéo, chúng tôi sẽ kiểm tra dữ liệu voxel trong khối đó để xem liệu AABB của đối tượng có giao cắt với bất kỳ dữ liệu voxel nào hay không.
Mặc dù dữ liệu voxel của chúng tôi khá gọn nhẹ, chúng tôi vẫn muốn giảm thiểu tác động bộ nhớ của dữ liệu giai đoạn rộng. Ngoài ra, cách hoạt động của thuật toán tạo lưới của chúng tôi là hình học được tạo ra từ một voxel không nằm hoàn toàn trong voxel đó mà có thể tràn sang các voxel lân cận, do đó chúng tôi thực sự cần kiểm tra cả các voxel lân cận. Để mọi thứ hoạt động hiệu quả, chúng tôi quyết định rằng đối với mỗi khối, chúng tôi sẽ lưu trữ một bitmask (trong đó mỗi voxel tương ứng với một bit) để cho biết liệu mỗi voxel có hình học nào để va chạm hay không.
Điều quan trọng là phải tạo ra bitmask này mà không phụ thuộc vào thuật toán tạo lưới (vì việc chạy thuật toán tạo lưới trên toàn bộ địa hình quá tốn thời gian, và do cấu trúc mã của chúng tôi, dữ liệu giai đoạn rộng phải có sẵn cho toàn bộ thế giới), vì vậy chúng tôi xấp xỉ điều này bằng cách giả định rằng nếu một voxel là rắn, nó có thể lý thuyết tạo ra hình học bên trong bất kỳ voxel lân cận nào (bao gồm cả các voxel chéo, tổng cộng 3^3=27 voxel), và điền tất cả các voxel này bằng 1 trong bitmask; quá trình này được gọi là dilation. Điều này cũng yêu cầu chúng ta xem xét các voxel lân cận của khối, do đó đầu vào của chúng ta là một hộp voxel 10^3 và đầu ra là một mặt nạ bit 8^3.
Cuối cùng, chúng ta có hai loại tiếp xúc: rắn và nước (chúng ta sử dụng các tiếp xúc giữa các hình khối và nước để tính toán lực nổi), vì vậy chúng ta tạo ra hai mặt nạ bit. Quá trình này hoạt động đại khái như sau (lưu ý rằng để giải thích, các hình ảnh trong bài viết này giả định các khối có kích thước 4^3 thay vì 8^3):
Để làm cho quá trình này nhanh hơn, chúng ta mở rộng bằng các phép toán bit. Đầu tiên, chúng ta tạo ra mặt nạ bit 10^3 và lưu trữ nó trong một mảng gồm 10^2 số nguyên 16 bit, sau đó chúng ta mở rộng từng số nguyên theo chiều ngang như sau:
data[y][z] = (data[y][z] << <span style="color: #ff0000;">1</span>) | data[y][z] | (data[y][z] >> <span style="color: #ff0000;">1</span>);
Sau đó, chúng tôi mở rộng dọc theo hai trục còn lại trong hai lần lặp như sau:
temp[y][z] = data[y][z - <span style="color: #ff0000;">1</span>] | data[y][z] | (data[y][z + <span style="color: #ff0000;">1</span>];
Kết quả là, chúng tôi nhận được 10^2 mặt nạ bit mở rộng 10 bit. Sau đó, chúng ta trích xuất 8^2 mặt nạ bit 8-bit tương ứng với các voxel của khối (bỏ qua các voxel biên dư thừa) và lưu trữ chúng dưới dạng dữ liệu giai đoạn rộng. Trong quá trình này, chúng ta cũng loại bỏ các khối dư thừa. Nếu tất cả các voxel trong thể tích 10^3 đều chứa không khí, thì không có hình học ở đó; cũng như vậy, nếu tất cả các voxel trong khối 10^3 đều chứa vật liệu rắn hoặc nước, thì thuật toán tạo lưới của chúng ta sẽ không bao giờ tạo ra đa giác nào, nhưng chúng ta vẫn cần giữ khối này trong giai đoạn rộng (ví dụ: để xác định xem một đối tượng có bị ngập hoàn toàn trong nước hay không), vì vậy chúng ta đánh dấu nó theo cách đặc biệt.
Nhìn chung, điều này dẫn đến chi phí lưu trữ cực kỳ thấp. Trường hợp xấu nhất là 2 bit/voxel (1 bit cho mặt nạ rắn và 1 bit cho mặt nạ nước), nhưng nhiều khối bị loại bỏ vì chúng trống hoặc đầy. Và trong trường hợp này, chúng ta chỉ cần lưu trữ cấu trúc khối chứ không cần lưu trữ mặt nạ.
Giai đoạn rộng bit: kiểm tra chồng chéo
Bây giờ chúng ta đã tạo dữ liệu giai đoạn rộng (điều này được thực hiện khi cấp độ được tải và dữ liệu giai đoạn rộng của mỗi khối được tạo lại mỗi khi bất kỳ voxel nào trong khối thay đổi), chúng ta có thể xem cách sử dụng nó.
Mỗi khi đối tượng di chuyển, chúng ta lấy AABB của đối tượng với các biến đổi cũ và mới, tra cứu giai đoạn rộng để kiểm tra chồng chéo và thực hiện quản lý tiếp xúc. Nếu đối tượng có tiếp xúc rắn với một khối ở vị trí cũ nhưng không có tiếp xúc rắn với khối đó ở vị trí mới, chúng ta có thể loại bỏ tiếp xúc đó. Chúng ta theo dõi tối đa 1 tiếp xúc rắn và 1 tiếp xúc nước cho mỗi cặp đối tượng-khối, do đó một đối tượng rất lớn có thể có nhiều tiếp xúc với địa hình (và mỗi tiếp xúc có thể tạo ra nhiều điểm tiếp xúc do công việc giai đoạn hẹp mà chúng ta sẽ thảo luận sau).
Truy vấn gồm hai bước. Đầu tiên, chúng ta lấy AABB của đối tượng, mở rộng nó thêm 1 voxel để bao phủ các đối tượng chạm vào hình học do tràn sang voxel lân cận, chiếu nó vào không gian khối (bằng cách chia tọa độ cho 8 voxel), và chuyển đổi min/max thành số nguyên (sử dụng floor/ceil), điều này cho chúng ta phạm vi các khối. Sau đó, chúng ta lấy từng chunk và kiểm tra dữ liệu bit để xem liệu AABB của đối tượng có chạm vào bất kỳ bit nào được đánh dấu là rắn/nước hay không. Trong khi phần sau có thể được thực hiện theo cách đơn giản bằng cách truy vấn từng voxel trong AABB của đối tượng, chúng ta tận dụng dữ liệu bit như sau.
Nhớ rằng mỗi khối có 8^3 bit; chúng ta lưu trữ mỗi lát Y (Y hướng lên) của khối này trong một số nguyên 64 bit, với mỗi nhóm 8 bit liên tiếp xác định dữ liệu cho một hàng X. Mỗi mặt nạ do đó là một mảng đơn giản, và chúng ta lưu trữ một mặt nạ cho rắn và một mặt nạ cho nước:
<span style="color: #007788;">uint64_t</span> solid[<span style="color: #ff0000;">8</span>];
<span style="color: #007788;">uint64_t</span> water[<span style="color: #ff0000;">8</span>];
Bây giờ, chúng ta lấy AABB của đối tượng, chiếu nó vào không gian khối và xác định các giới hạn trong không gian voxel. Sau đó, chúng ta xem xét phạm vi XZ của đối tượng khi nó giao với khối và tạo ra một mặt nạ 64 bit có các giá trị 1 được đặt ở những nơi đối tượng giao với các voxel dọc theo mặt phẳng XZ:
Sau đó, chúng tôi lặp qua tất cả các lát cắt Y mà đối tượng bao phủ và thực hiện một phép kiểm tra bit đơn giản cho mỗi lát cắt:
<span style="color: #006699;">if</span> (chunk.solid[y] & mask)
touchesSolid = <span style="color: #336666;">true</span>;
Điều này cho phép chúng ta kiểm tra toàn bộ lát cắt XZ của một khối — lên đến 64 voxel! — để tìm sự chồng chéo bằng một lệnh đơn giản (trên kiến trúc 32-bit, kiểm tra này mất khoảng 3 lệnh), giúp thực hiện các truy vấn chính xác trên các đối tượng có kích thước khá lớn một cách rất hiệu quả. Để tối ưu hóa chi phí cho các đối tượng nhỏ, chúng tôi đảm bảo tạo mặt nạ cho các phạm vi XZ càng nhanh càng tốt. Mặc dù chúng tôi có thể thực hiện việc này bằng cách lặp qua các phạm vi XZ và đặt các bit, nhưng chúng tôi lưu ý rằng mặt nạ mà chúng tôi có thực sự là giao điểm của hai mặt nạ đại diện cho một dải dọc và một dải ngang; đối với mỗi hướng, chúng tôi lưu giữ một bảng tra cứu và kết hợp các kết quả tra cứu để có được mặt nạ kết quả:
<span style="color: #007788;">uint64_t <span style="color: #000000;">mask = masksVer[cmin.x][cmax.x] & masksHor[cmin.z][cmax.z];
</span></span>
Giai đoạn thu hẹp: phân tích & kế hoạch
Bây giờ khi dữ liệu giai đoạn rộng đã được chuẩn bị tốt, hãy cùng xem xét giai đoạn hẹp. Ở mức độ tổng quan, cách thức hoạt động của giai đoạn hẹp dựa trên Bullet như sau:
- Mỗi khối lưu trữ một mảng các đỉnh (mỗi đỉnh có 3 số float cho vị trí và 1 byte cho vật liệu), một mảng các chỉ số (mỗi tam giác có 3 chỉ số 16 bit) và một BVH (là cây AABB).
- Khi tạo cây, danh sách các tam giác sẽ được chia nhỏ lặp đi lặp lại thành các nút cho đến khi các nút lá chỉ còn một tam giác
- Khi thực hiện phát hiện va chạm, một tập hợp các tam giác được trích xuất từ cây bằng một truy vấn AABB đơn giản; mỗi tam giác được so sánh va chạm với đối tượng mục tiêu bằng cách sử dụng thuật toán chuyên biệt cho cặp này (như tam giác-hình cầu) hoặc thuật toán GJK/EPA chung. Các điểm kết quả từ các va chạm này được đưa vào một cấu trúc simplex lưu trữ tối đa 4 điểm tiếp xúc và cố gắng tối đa hóa diện tích tiếp xúc.
- Khi thực hiện raycast, một truy vấn cây ray-AABB đơn giản được chạy; mỗi nút lá khớp sẽ được giao với tia. Điểm gần nhất được giữ lại và trả về làm kết quả.
Chúng tôi quyết định giữ nguyên các thuật toán phát hiện va chạm và cấu trúc tổng thể, nhưng thay thế tất cả các thành phần khác bằng các phiên bản hoạt động tốt hơn cho trường hợp sử dụng của chúng tôi. Để giữ chi phí bộ nhớ ở mức thấp, chúng tôi bắt đầu thực hiện việc tạo đối tượng va chạm theo cách lười biếng. Chúng tôi chỉ tạo dữ liệu tam giác/cây khi một điểm tiếp xúc được tạo ra hoặc một phép quét tia được thực hiện trên khối, và lưu trữ bộ nhớ đệm của các đối tượng kết quả để đảm bảo chi phí bộ nhớ vẫn ở mức có thể quản lý được.
Điều này đã cải thiện đáng kể mức tiêu thụ bộ nhớ trong giai đoạn hẹp, nhưng chi phí tạo ra vẫn quá đắt đỏ. Bullet có hai phiên bản cây lưới tam giác BVH: một phiên bản không lượng tử hóa và một phiên bản lượng tử hóa. Mỗi phiên bản đều duy trì một cây AABB nhưng lưu trữ chúng theo cách khác nhau (sử dụng số thực 32-bit trong một trường hợp và số nguyên 16-bit trong trường hợp khác). Vì mỗi tam giác có một nút lá và cây là nhị phân, bạn cần khoảng gấp đôi số nút so với số tam giác.
Chi phí bộ nhớ cơ bản cho một lưới thô là ~13 byte mỗi đỉnh (3 tọa độ số thực và 1 byte vật liệu) và ~6 byte mỗi tam giác (cho 3 chỉ số 16-bit), tổng cộng là ~12,5 byte/tam giác vì trung bình có gấp đôi số tam giác so với số đỉnh.
Cây BVH Bullet không lượng tử hóa chiếm 64 byte cho mỗi nút, tương đương ~128 byte/tam giác (cấu trúc nút chỉ cần 44 byte nhưng được bổ sung lên 64 byte), tức là ~10 lần chi phí bộ nhớ so với dữ liệu tam giác. Cây này cũng mất ~3 lần thời gian để tạo ra so với việc tạo lưới (sử dụng triển khai của chúng tôi chuyển đổi dữ liệu voxel thành dữ liệu tam giác).
Cây Bullet BVH đã lượng tử hóa chiếm 16 byte mỗi nút, tương đương ~32 byte/tam giác (tức là ~2,5 lần chi phí bộ nhớ của dữ liệu tam giác). Việc tạo ra nó chậm hơn so với phiên bản chưa lượng tử hóa; khoảng ~5 lần lâu hơn so với việc tạo lưới.
Cả hai tùy chọn này đều rất không thỏa đáng về mặt bộ nhớ và thời gian tạo dữ liệu (do tạo lười biếng, thời gian xây dựng rất quan trọng), vì vậy chúng tôi quyết định thay thế cấu trúc cây bằng cây kD tùy chỉnh với hai mặt phẳng cho mỗi nút.
Cây kD lỏng lẻo: xây dựng
Cây kD là một cây nhị phân, trong đó mỗi nút chia không gian theo một trục thành hai phần. Thông thường, cây kD chỉ có một mặt phẳng chia cắt cho mỗi nút, nhưng điều này khiến việc xử lý các tam giác không nằm hoàn toàn trong một trong hai nút con trở nên phức tạp (bạn phải cắt chúng bằng mặt phẳng chia cắt), vì vậy chúng tôi đã chọn sử dụng cây kD lỏng. Mỗi nút có hai mặt phẳng phân chia dọc theo cùng một trục, trong đó tất cả các nút con bên trái nằm trong một không gian con được xác định bởi một trong hai mặt phẳng đó, và tất cả các nút con bên phải nằm trong một không gian con được xác định bởi mặt phẳng còn lại. Các mặt phẳng này vừa khít với nội dung của các nút con, dẫn đến hai cấu hình mặt phẳng có thể có:
Mặc dù cây AABB có thể định vị không gian tốt hơn cây kD một chút, nhưng cây kD có thể được xây dựng nhanh hơn và bạn có thể khôi phục hầu hết thông tin trong quá trình duyệt đệ quy như chúng ta sẽ thảo luận sau. Lợi ích lớn là bạn chỉ cần lưu trữ 2 giá trị cho mỗi nút thay vì một AABB đầy đủ. Chúng tôi cũng quyết định lưu trữ nhiều hơn một tam giác cho mỗi nút lá — nói chung, việc lưu trữ 2 tam giác thay vì 1 không ảnh hưởng đáng kể đến chất lượng truy vấn — và kết quả là có được cấu trúc này:
<span style="color: #006bb8;">union</span> KDNode {
<span style="color: #006bb8;"> struct</span> {
<span style="color: #007788;"> float</span> splits[<span style="color: #ff0000;">2</span>];
<span style="color: #007788;"> unsigned int</span> axis: <span style="color: #ff0000;">2</span>; <span style="color: #999999;">// 0=X, 1=Y, 2=Z</span>
<span style="color: #007788;"> unsigned int</span> childIndex: <span style="color: #ff0000;">30</span>; <span style="color: #999999;">// children are at childIndex+0,1</span>
} branch;
<span style="color: #006bb8;">struct</span> {
<span style="color: #007788;"> unsigned int</span> triangles[<span style="color: #ff0000;">2</span>]; <span style="color: #999999;">// up to two triangles per leaf</span>
<span style="color: #007788;"> unsigned int</span> axis: <span style="color: #ff0000;">2</span>;<span style="color: #999999;"> // must be 3; same offset as branch.axis </span>
<span style="color: #007788;"> unsigned int</span> triangleCount: <span style="color: #ff0000;">30</span>;
} leaf;
};
Cấu trúc cây tương đối đơn giản; tất cả các nút được lưu trữ trong một mảng lớn để chúng ta có thể truy cập các nút thông qua chỉ số. Giá trị thứ 4 của chỉ số trục được sử dụng làm thẻ để phân biệt các nút lá, và chỉ lưu trữ một chỉ số con vì mỗi nút nhánh luôn có cả hai con. Chúng tôi lưu trữ tối đa 2 tam giác trong mỗi nút lá; chúng tôi dễ dàng có đủ không gian cho 4 tam giác, nhưng việc lưu trữ 4 tam giác thay vì 2 làm cho quá trình xử lý va chạm chậm hơn một chút, vì vậy chúng tôi đã chọn 2.
Lưu ý rằng mỗi nút có kích thước 12 byte. Vì chúng ta lưu trữ 2 tam giác trong mỗi nút lá, chúng ta cần khoảng bằng số nút tổng cộng với số tam giác, do đó chi phí bộ nhớ cuối cùng là 12 byte/tam giác. Vẫn còn nhiều tiềm năng tối ưu hóa ở đây. Chúng ta có thể giảm chi phí bộ nhớ cho dữ liệu đỉnh bằng cách nén tọa độ sử dụng số nguyên 16-bit và tối ưu hóa nút cây kD theo cách tương tự, đạt được ~6b mỗi nút kD, dẫn đến tổng tác động của tam giác là 3.5b đỉnh + 6b chỉ số + 6b cây = 15.5b, nhưng kết quả hiện tại là ~24.5b/tam giác đã đủ tốt để triển khai.
Quá trình xây dựng cây tương đối tiêu chuẩn. Chúng tôi bắt đầu với một mảng các tam giác và chia nhỏ nó một cách đệ quy, tạo ra các nút nhánh trong quá trình này (và dừng đệ quy khi đạt đến 2 tam giác mỗi nút hoặc ít hơn). Đối với mỗi lần chia, chúng tôi chọn trục bằng cách lấy trục dài nhất của AABB hiện tại, đặt điểm chia tại trung bình của các điểm giữa tam giác dọc theo trục này, lọc các tam giác bên trái/phải của mặt phẳng đó bằng cách sử dụng các điểm giữa làm yếu tố quyết định, và sau đó tính lại các mặt phẳng chia trái và phải bằng cách sử dụng tất cả 3 đỉnh tam giác. Nếu phân phối kết quả quá lệch về số lượng tam giác (hiện được định nghĩa là <25% tam giác nằm trong một trong hai nút), chúng ta sẽ phân chia lại và đặt một nửa số tam giác vào một nhánh con và một nửa vào nhánh con khác (từ danh sách được sắp xếp theo điểm giữa). Điều này duy trì sự cân bằng giữa tính nhất quán không gian và độ sâu của cây, giới hạn độ sâu của cây và đảm bảo quá trình kết thúc.
Quá trình xây dựng cuối cùng trở nên đơn giản hơn một chút và được mã hóa hiệu quả hơn so với Bullet, do đó nhanh hơn khoảng 3-4 lần so với thuật toán xây dựng cây nhanh nhất của Bullet. Điều này dẫn đến dữ liệu lưới và cây có kích thước gần như tương đương và thời gian tạo ra cũng gần như tương đương, đây là một sự cân bằng tốt (hay nói cách khác, điều này có nghĩa là để cải thiện đáng kể quá trình tổng thể, bạn cần tối ưu hóa cả hai một cách đáng kể :D).
Cây kD lỏng lẻo: truy vấn
Như đã đề cập trước đó, chúng ta chỉ cần hai loại truy vấn: truy vấn AABB (nơi chúng ta cần thu thập tất cả các tam giác nằm trong một AABB cho trước, được sử dụng cho giai đoạn hẹp) và truy vấn tia (nơi chúng ta cần thu thập tất cả các tam giác giao cắt với một tia, hoặc chỉ tam giác có điểm giao cắt gần nhất). Cả hai loại truy vấn này đều được thực hiện bằng cách duyệt không dùng stack. Vì độ sâu của cây có giới hạn, việc tính trước độ sâu của cây và phân bổ không gian tạm thời cho quá trình duyệt là khá đơn giản. Duyệt không dùng stack không nhất thiết tiết kiệm nhiều không gian hoặc thời gian, nhưng nó giúp hiểu kết quả phân tích hiệu suất vì tất cả chi phí từ quá trình duyệt ở cả nhánh và lá đều được tập trung vào một hàm, khiến việc xử lý trở nên dễ dàng hơn một chút.
Cây kD không có thông tin đầy đủ về phạm vi của các nút trong từng nút, như cây AABB, nhưng chúng ta có thể khôi phục thông tin này trong quá trình duyệt. Đối với truy vấn AABB, khi gặp nút nhánh, chúng ta chỉ đi xuống các nhánh có AABB nằm trong nửa không gian bên phải. Do cơ chế duyệt phân cấp, điều này dẫn đến việc chỉ duyệt các nút có thể tích trùng lặp với AABB:
<span style="color: #006699;">if</span> (node.branch.splits[<span style="color: #ff0000;">1</span>] <= aabbMax[axis])
buffer[offset++] = childIndex + <span style="color: #ff0000;">1</span>; <span style="color: #999999;">// push right child</span>
<span style="color: #006699;">if</span> (node.branch.splits[<span style="color: #ff0000;">0</span>] >= aabbMin[axis])
buffer[offset++] = childIndex + <span style="color: #ff0000;">0</span>; <span style="color: #999999;">// push left child
</span>Điều này có thể kém hiệu quả nếu AABB được truy vấn nằm ngoài giới hạn của cây kD, vì vậy chúng ta lưu trữ một AABB cho mỗi cây kD để loại bỏ sớm.
Đối với truy vấn tia, chúng ta chọn thực hiện quá trình duyệt cây phân đoạn, trong đó phân đoạn được xác định bởi điểm xuất phát/hướng của tia và hai giới hạn cho tham số t (tmin và tmax), chứa tất cả các điểm trong không gian con được xác định bởi mỗi nút. Khi gặp một nhánh, chúng ta cần giao cắt các mặt phẳng chia tách với tia (điều này đơn giản và nhanh chóng vì các mặt phẳng song song với trục), và điều chỉnh giới hạn t cho quá trình duyệt tiếp theo:
<span style="color: #007788;">float</span> sa = raySource[axis];
<span style="color: #007788;">float</span> da = rayDir[axis];
<span style="color: #007788;">float</span> t0 = (node.branch.splits[i0] - sa) / da;
<span style="color: #007788;">float</span> t1 = (node.branch.splits[i1] - sa) / da;
<span style="color: #006699;">if</span> (t1 <= rn.tmax)
buffer[offset++] = { childIndex + i1, max(t1, rn.tmin), rn.tmax };
<span style="color: #006699;">if</span> (t0 >= rn.tmin)
buffer[offset++] = { childIndex + i0, rn.tmin, min(t0, rn.tmax) };
Tương tự như các truy vấn AABB, nếu tia không giao với toàn bộ giới hạn cây kD, quá trình duyệt có thể kém hiệu quả, vì vậy chúng tôi tính toán các giới hạn đoạn ban đầu bằng cách giao tia với AABB được lưu trữ.
Ngoài ra, để tăng tốc các truy vấn tia chỉ cần điểm đầu tiên, chúng tôi sắp xếp quá trình duyệt để trước tiên truy cập nhánh xác định một không gian con xuất hiện sớm hơn dọc theo hướng của tia (điều này ảnh hưởng đến các chỉ số i0/i1 trong đoạn mã trên). Nếu chúng tôi tìm thấy một điểm giao nhau nằm trước trên tia so với giá trị t nhỏ nhất của một đoạn cho trước, thì chúng tôi có thể kết thúc quá trình duyệt. Tuy nhiên, do các vấn đề về độ chính xác của số thập phân, chúng tôi cần mở rộng nhẹ đoạn trên mỗi nhánh.
Với cách này, chúng ta có được các truy vấn cây hiệu quả cho cả AABB và raycast. Hiệu suất truy vấn AABB ngang bằng với triển khai Bullet, nhưng truy vấn raycast nhanh hơn; cả vì chúng ta thực hiện ít công việc hơn cho mỗi nhánh (chỉ giao nhau hai mặt phẳng với một tia) và vì chúng ta có thể kết thúc quá trình duyệt sớm nếu tìm thấy một điểm giao nhau phù hợp.
Công việc trong tương lai
Mặc dù các thuật toán mà chúng tôi đã xây dựng hoạt động khá tốt, nhưng chắc chắn chúng vẫn có thể được cải thiện hơn nữa. Tiêu thụ bộ nhớ của giai đoạn hẹp (narrowphase) có thể được cải thiện; ngoài ra, hiện tại chúng ta lưu trữ các tam giác trong cây kD. Christer Ericson đề xuất rằng nếu lưu trữ các hình chữ nhật (quads) như một nguyên thủy cấp cao, các truy vấn tia có thể hiệu quả gấp 2 lần vì thuật toán Möller-Trumbore có thể xử lý các hình chữ nhật với ít tính toán bổ sung (địa hình của chúng ta được xây dựng bằng các hình chữ nhật và một số trong số chúng là phẳng, nên điều này có thể khả thi).
Một lĩnh vực mà chúng tôi chưa khám phá là các phần của giai đoạn hẹp (narrowphase) mà chúng tôi vẫn sử dụng từ Bullet. Có thể sử dụng các thuật toán tốt hơn để thực hiện va chạm tam giác-lồi hoặc để giảm bớt tập hợp điểm tiếp xúc; ngoài ra, hiện tại chúng tôi sử dụng một số thủ thuật để xử lý va chạm cạnh bên trong trong khi có thể tạo dữ liệu về việc mỗi cạnh là bên ngoài hay bên trong và sử dụng điều này khi tạo điểm va chạm/vectơ pháp tuyến.
Cuối cùng, một điều mà chúng tôi đã khám phá trong giai đoạn tạo mẫu nhưng chưa đưa vào sản xuất là các vùng địa hình không liên kết. Bất cứ khi nào bạn sửa đổi dữ liệu voxel, nguyên mẫu của chúng tôi sẽ thực hiện phân tích kết nối cơ bản và chuyển đổi tất cả các vùng voxel không liên kết thành một đối tượng di chuyển tự do. Việc tính toán va chạm cho điều này trong thời gian thực rất có thể liên quan đến việc xấp xỉ hình dạng bằng vỏ lồi, mặc dù có thể có các tùy chọn khác và chúng tôi có thể sẽ khám phá điều này vào một ngày nào đó.
