VoxelSpace: Thuật toán dựng hình địa hình được triển khai với chưa đến 20 dòng mã (2020)

 (github.com/s-macke)
4 điểm bởi GN⁺ 2025-01-05 | 1 bình luận | Chia sẻ qua WhatsApp
  • Voxel Space là kỹ thuật dựng hình địa hình 2.5D được dùng trong Comanche của NovaLogic năm 1992, thể hiện các ngọn núi và thung lũng có kết cấu chỉ bằng CPU trong thời kỳ chưa có tăng tốc GPU hoặc chi phí còn quá đắt
  • Địa hình được biểu diễn bằng height map và color map, và Comanche sử dụng height map 1 byte 1024×1024 cùng color map 1 byte 1024×1024
  • Trong color map đã có sẵn đổ bóng và bóng đổ, nên không cần tính toán chiếu sáng trong lúc dựng hình; tuy nhiên, mỗi vị trí trên map chỉ có thể có một độ cao nên khó biểu diễn các cấu trúc hình học phức tạp như tòa nhà hay cây cối
  • Dựng hình cơ bản hoạt động bằng cách raster hóa các đoạn đường trên map từ xa đến gần, rồi đọc độ cao và màu cho từng cột màn hình để vẽ đường thẳng đứng; góc nhìn 90° và phép chiếu phối cảnh được triển khai chỉ với vài dòng mã
  • Có thể cải thiện hiệu năng bằng cách vẽ từ gần ra xa rồi dùng y-buffer theo từng cột để bỏ qua phần bị che khuất, đồng thời giảm mức độ chi tiết ở khoảng cách xa

Bối cảnh ra đời của Voxel Space

  • Vào năm 1992, CPU khi đó chậm hơn 1000 lần so với hiện nay, còn tăng tốc GPU thì chưa phổ biến hoặc quá đắt đỏ
  • Game 3D được tính toán hoàn toàn bằng CPU, và engine dựng hình thường vẽ các đa giác tô màu đơn sắc
  • NovaLogic phát hành Comanche vào năm 1992, và cách thể hiện texture, đổ bóng, bóng đổ của núi và thung lũng đã tạo khác biệt với đồ họa game thời đó
  • README cung cấp Web Demo of the Voxel Space Engine

Biểu diễn địa hình: height map và color map

  • Cách đơn giản nhất để biểu diễn địa hình trong Voxel Space là dùng height map và color map
  • Comanche sử dụng hai map sau
    • height map 1 byte 1024×1024
    • color map 1 byte 1024×1024
  • Các map này lặp lại theo dạng tuần hoàn
  • Mỗi vị trí trên map chỉ có thể có một độ cao
    • Không thể biểu diễn các cấu trúc hình học phức tạp như tòa nhà hay cây cối
    • Bù lại, color map đã bao gồm sẵn đổ bóng và bóng đổ nên không cần tính toán chiếu sáng trong quá trình dựng hình

Thuật toán dựng hình cơ bản

  • Engine Voxel Space dựng hình địa hình bằng cách raster hóa height map và color map rồi vẽ đường thẳng đứng lên màn hình
  • Quy trình cơ bản như sau
    • Xóa màn hình
    • Vẽ từ xa đến gần để bảo đảm xử lý che khuất
    • Tìm các đường trên map tương ứng với cùng một khoảng cách quang học tới người quan sát
    • Tính đến góc nhìn và phép chiếu phối cảnh
    • Chia đường đó theo số cột của màn hình
    • Đọc độ cao và màu từ map 2D tại từng vị trí trên đoạn
    • Áp dụng phép chiếu phối cảnh cho tọa độ độ cao
    • Vẽ đường thẳng đứng bằng độ cao đã chiếu và màu từ color map
  • Vòng lặp lõi ở dạng Python đơn giản nhất sẽ giảm z từ khoảng cách xa về gần và gọi DrawVerticalLine cho từng cột màn hình
  • Lời gọi ví dụ truyền vào vị trí, chiều cao camera, vị trí đường chân trời, tỉ lệ chiều cao, khoảng cách tối đa, chiều rộng và chiều cao màn hình

Thêm phép quay

  • Thuật toán cơ bản chỉ có thể nhìn về hướng bắc
  • Muốn nhìn theo hướng khác thì cần thêm mã để xoay tọa độ
  • Phiên bản có quay nhận phi làm góc nhìn và tính trước sin(phi) cùng cos(phi)
  • Phép xoay tọa độ được áp dụng khi tính các điểm biên trái và phải của trường nhìn, và x cùng y được tăng đồng thời dọc theo từng cột màn hình
  • Cấu trúc cốt lõi của quá trình dựng hình vẫn giữ nguyên
    • Tính các đoạn theo khoảng cách
    • Raster hóa theo số cột màn hình
    • Tra cứu height map và color map
    • Vẽ đường thẳng đứng sau phép chiếu phối cảnh

Cách cải thiện hiệu năng

  • Thay vì vẽ từ xa đến gần, có thể vẽ từ gần ra xa để giảm vùng bị che khuất
  • Cách này cần một y-buffer lưu vị trí y cao nhất cho từng cột màn hình
    • Giá trị y-buffer ban đầu được đặt bằng chiều cao màn hình
    • Chỉ khi height_on_screen mới nằm cao hơn y-buffer hiện có thì phần đó mới được vẽ là nhìn thấy được
    • Sau khi vẽ, y-buffer được cập nhật lên vị trí cao hơn
  • Khoảng cách z tăng dần từ gần ra xa
  • Nếu tăng dz dần dần thì có thể lấy mẫu với khoảng cách lớn hơn ở xa, từ đó đạt hiệu ứng Level of Detail
  • Nghĩa là chỗ gần được dựng chi tiết hơn, còn chỗ xa thì ít chi tiết hơn

Tài liệu và giấy phép

  • Kho lưu trữ có kèm nhiều cặp color map và height map khác nhau
  • Phần mềm được phát hành theo giấy phép MIT
  • Công nghệ Voxel Space có thể vẫn còn bằng sáng chế ở một số quốc gia
  • Color map và height map bị loại khỏi giấy phép vì là dữ liệu được reverse engineering từ game Comanche
  • Tài liệu liên quan được cung cấp qua liên kết Voxel terrain engine - an introduction

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-01-05
Ý kiến trên Hacker News

  • Rất tuyệt. Tôi nhớ thời mà những thuật toán mới mẻ và thanh nhã như thế này tạo ra cảm giác như ma thuật
    Có thể là do tôi già đi nên cảm thấy vậy, nhưng tôi nghĩ các trò chơi thời tài nguyên phần cứng còn hạn chế có nhiều chất “ma thuật” hơn bây giờ. Trong thập niên 80, 90 và đầu những năm 2000, gần như mỗi năm, hoặc ít nhất mỗi thế hệ, game lại đẩy chính phương tiện này tiến lên, và các nhà phát triển vắt kiệt hiệu năng phần cứng bằng những kỹ thuật mới cùng các tối ưu hóa như phép màu thuần túy
    Ngày nay, các nền tảng giả tưởng như PICO-8 thú vị hơn nhiều so với các bản phát hành lặp lại của studio AAA, và thật ra tôi không hiểu vì sao những trò chơi gần như chỉ thay asset lại thành công đến vậy năm này qua năm khác

    • Trong game AAA hiện đại vẫn có rất nhiều công nghệ như ma thuật. Thực tế, ngành game là một trong số ít lĩnh vực thực sự quan tâm nghiêm túc đến hiệu năng, và đôi khi còn đặt hiệu năng lên trên độ an toàn hoặc độ chính xác
      Chỉ là giờ đây mọi thứ phức tạp hơn nhiều và ít dễ nhận thấy hơn. Trước đây, ta có thể thấy bước tiến từ các tam giác phẳng sang texture nhờ những mẹo toán học thông minh; còn bây giờ, bước tiến lại là làm bóng ở góc phòng đẹp hơn. Cải thiện texture thì ai cũng nhận ra ngay, còn bóng ở góc thì nếu không phải người trong ngành sẽ khó chỉ ra cụ thể. Dù vậy, những yếu tố này cộng dồn lại làm đồ họa tổng thể tốt hơn, chỉ là không gây ấn tượng như ngày xưa
      Ngành game AAA là một mảng kinh doanh lớn, chi phí làm game cực cao và nhà đầu tư muốn có lợi nhuận. Vì vậy họ thường nghiên cứu thị trường, xem thứ gì bán chạy rồi làm theo hướng tương tự. Tính độc đáo giảm đi, nhưng rủi ro cũng thấp hơn
      Ngược lại, ngành game indie có hàng nghìn studio, và vì không thể thắng AAA về lượng nội dung hay mức độ hoàn thiện, họ cần những vũ khí khác như ý tưởng độc đáo để nổi bật giữa đám đông. Tuy nhiên, giờ đây việc vượt qua giới hạn kỹ thuật thường không còn là động lực chính nữa, vì các giới hạn không nhiều như trước. Trái lại, do chi phí không kham nổi nên họ thường không đẩy kỹ thuật xa như các sản phẩm AAA
      Tôi không rành cảnh PICO-8, nhưng cũng tò mò trong đó có bao nhiêu phần là vượt qua các giới hạn kỹ thuật nhân tạo, và bao nhiêu phần là dùng nền tảng đúng theo cách nó được thiết kế rồi tập trung vào gameplay
    • Tôi nghĩ đây gần như là hồi tưởng qua kính hàn 1/4 inch màu hồng. Game AAA hiện đại vẫn có những khoảnh khắc hay đến choáng váng, và dù có bệnh phần tiếp theo lặp lại, vẫn có những tác phẩm độc đáo; công nghệ rõ ràng đã làm điều đó khả thi
      Cũng nên nhớ là ngày xưa cũng có rất, rất, rất nhiều game tệ hại
    • Tôi từng dùng thuật toán này để làm 3D Mario Kart trên máy tính bỏ túi. Chiếc máy đó bình thường còn xử lý đồ họa 2D khá chật vật, nên chuyện này khá thú vị, nhưng cuối cùng tôi không hoàn thành được
      Một trong các prototype là cái này: https://youtu.be/9Z8Bm8ZmWKI
    • Tôi từng dùng thuật toán này để làm 3D Mario Kart trên máy tính bỏ túi. Chiếc máy đó bình thường còn xử lý đồ họa 2D khá chật vật, nên chuyện này khá thú vị, nhưng cuối cùng tôi không hoàn thành được
      Một trong các prototype là cái này: https://media.discordapp.net/attachments/953383695908216843/...
    • Trong công nghệ game vẫn còn rất nhiều đổi mới thú vị. Hãy nhìn các game như Noita, Dreams, Teardown; gần đây hơn thì có Tiny Glade
      Bài thuyết trình kỹ thuật gần đây của Tiny Glade đầy những nội dung như ma thuật: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      Ở mức nền tảng hơn của engine và framework cũng đang có những công nghệ rất hay. Ví dụ như Nanite/Lumen/MegaLights của UE5

  • Đây là các liên kết liên quan. Còn gì khác không?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - tháng 10 năm 2023, 2 bình luận
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - tháng 3 năm 2021, 71 bình luận
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - tháng 1 năm 2020, 116 bình luận
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - tháng 11 năm 2017, 93 bình luận
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - tháng 9 năm 2017, 2 bình luận

  • Nghĩ ngay đến mars.com. Không phải tên miền, mà là một chương trình. Video: https://www.youtube.com/watch?v=_zSjpIyMt0k
    Bổ sung: Cũng có trên Pouet: https://www.pouet.net/prod.php?which=4662

    • Cũng tìm thấy bản triển khai JavaScript của demo này: http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • Ký ức ngày xưa ùa về. Khi nó đến tay tôi khoảng năm 1998, nó nằm trong một tệp Microsoft Word và điều khiển bằng chuột
      Khi đó tôi nghĩ nó rất ngầu, nhưng vì còn là một đứa trẻ hoàn toàn không biết gì về demoscene hay lập trình, tôi đã thất vọng vì nó không phải một trò chơi hoàn chỉnh. Nhìn lại thì tôi chỉ nghĩ đó là một demo DirectX tầm thường được chuyền qua email, không hề biết nó là một thứ thực sự từng tồn tại
    • Nói chính xác thì mars.com chạy mượt ngay cả trên 286 8MHz
    • Đau thật. Tôi vẫn nhớ cảm giác choáng ngợp khi chạy nó trên 286. Đồng thời cũng thất vọng vì Wing Commander 3 không chạy được trên cùng chiếc máy đó

  • Cách render thì gọn gàng, nhưng tôi không chắc có thể gọi đây là voxel không. Nó không render được thể tích tùy ý, và cách lưu dữ liệu cũng chỉ có thể có một vị trí cho mỗi x,y cho trước
    Chẳng phải đây chỉ là một triển khai hay của renderer heightmap sao?

    • Tôi nghĩ chắc chắn có thể xem là voxel engine. Heightmap không hỗ trợ phần nhô ra như octree, nhưng rốt cuộc chiều cao là một chồng voxel
      Một octree không có phần nhô ra sẽ có hình dạng đúng y như thế này
    • Theo tôi biết, voxel có nghĩa kiểu như phần tử thể tích (volume element). Tương tự như pixel bắt nguồn từ picture element, còn chữ x gần như chỉ để cho đẹp
      Trong cách render này, mỗi cột là một hộp 3D, nên tôi nghĩ gọi là ma trận voxel 2x2 cũng không có vấn đề gì
    • Những heightmap renderer như thế này hồi đó chắc chắn được gọi là “voxel”
    • Đúng vậy, cái tên đặt cho thuật toán này gây hiểu lầm

  • Tôi có những ký ức rất đẹp về việc làm các trình xem địa hình như thế này trong thập niên 1990, cùng lúc đang học lượng giác cần thiết ở trường trung học. Ban đầu tôi làm bằng Pascal, sau đó bằng C và Assembly
    Hồi đó để làm cho chạy được thì cần đủ loại tối ưu hóa cấp thấp
    Việc tự tìm ra cách triển khai và tối ưu mà không có sách tham khảo hay Internet là một trong những việc khiến cá nhân tôi thấy đáng giá nhất

  • Tôi đã làm một trò chơi bằng kỹ thuật này: https://eri0o.itch.io/i-rented-a-boat
    Nó được làm bằng Adventure Game Studio, trên một phiên bản engine cũ hơn lúc đó chưa được tối ưu. Tôi lười cập nhật trang itch nên vẫn để nguyên, nhưng một ngày nào đó sẽ làm
    Tôi đã viết ở đó về cách mình làm, và trên diễn đàn AGS còn có nội dung chi tiết hơn

    • Ấn tượng thật khi có thể làm được thứ này trong AGS

  • Có lẽ nên thêm [2020] vào tiêu đề, và xem các bình luận khác trong liên kết thảo luận bên dưới thì [2017] cũng có vẻ khả thi
    Cũng từng có một cuộc thảo luận năm 2021 về cùng kho lưu trữ: https://news.ycombinator.com/item?id=26631995
    Trong thread đó cũng có các liên kết dẫn tới những cuộc thảo luận khác
    Không hoàn toàn giống, nhưng tôi nhớ hồi mới học lập trình mình từng viết một chương trình tạo heightmap địa hình và render kiểu isometric bằng kỹ thuật tương tự. Tôi làm bằng QBasic, chạy trên máy DOS 386 ở trường cấp hai, và dùng bộ nhớ đồ họa làm vùng làm việc tạm
    Nó cực kỳ chậm, nhưng tôi bị mê hoặc bởi kết quả xuất ra, và đó là một trong những lý do khiến tôi tiếp tục lập trình

  • Tôi nhớ trước đây đã đọc nội dung này ở đâu đó, lần này để khỏi đánh mất nên để lại bình luận
    Là một fan của trình mô phỏng bay, tôi vẫn nhớ cú sốc khi lần đầu chơi Comanche. Nó như đến từ tương lai hay từ phim ảnh, và khiến tôi thực sự cảm thấy mình đang sống trong thời đại máy tính

    • Novalogic đã dùng kỹ thuật này để render địa hình khá lâu, và thứ tôi thích nhất là bản Delta Force đầu tiên
      Có vẻ họ đã bỏ cách này và chuyển sang engine polygon trong Comanche 4 và Black Hawk Down bản gốc: https://en.wikipedia.org/wiki/Comanche_4#Reception
    • Tôi nhớ Comanche. Nó làm tôi nhớ lại lúc kinh ngạc trước việc sinh thủ tục trong Rescue on Fractalus[0] trên Atari 8-bit, tên trước khi phát hành là Behind Jaggi Lines
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg cảnh hạ cánh xuống Trái Đất xuất hiện ở 1:00

  • Thật sự rất tuyệt
    Trong hầu hết game hiện đại, đôi khi bạn có thể thấy núi là cấu trúc rỗng bên trong vì góc camera kỳ quặc hoặc vấn đề clipping
    Nhưng với cách này, núi được lấp đầy đặc kín >:)

  • Rất khuyến khích thử làm các software renderer kiểu này cho vui. Ray tracer là dự án phổ biến, nhưng mã render thời gian thực phong cách retro như thế này cũng rất hợp làm dự án cuối tuần
    Rất lâu trước đây tôi từng triển khai một thuật toán gần như giống hệt. Chính xác hơn là tôi port mã SDL như một bài tập để học canvas2d: http://namuol.github.io/earf-html5/
    Tất nhiên bản triển khai được liên kết nhanh hơn và đơn giản hơn của tôi rất nhiều, nên nếu đang tìm tài liệu tham khảo thì tôi không khuyên dùng đoạn CoffeeScript cũ của mình…