VoxelSpace: อัลกอริทึมเรนเดอร์ภูมิประเทศที่เขียนด้วยโค้ดไม่ถึง 20 บรรทัด (2020)

 (github.com/s-macke)
4 คะแนน โดย GN⁺ 2025-01-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Voxel Space เป็นเทคนิคเรนเดอร์ภูมิประเทศแบบ 2.5D ที่ใช้ใน Comanche ของ NovaLogic เมื่อปี 1992 ซึ่งสามารถแสดงภูเขาและหุบเขาที่มีพื้นผิวได้ด้วย CPU เพียงอย่างเดียว ในยุคที่การเร่งความเร็วด้วย GPU ยังไม่มีหรือมีราคาแพง
  • ภูมิประเทศถูกแทนด้วย height map และ color map โดย Comanche ใช้ height map ขนาด 1024×1024 แบบ 1 ไบต์ และ color map ขนาด 1024×1024 แบบ 1 ไบต์
  • ใน color map มี แสงเงาและเงาทอด อยู่แล้ว จึงไม่ต้องคำนวณแสงระหว่างการเรนเดอร์ แต่แต่ละตำแหน่งบนแผนที่มีความสูงได้เพียงค่าเดียว ทำให้แสดงโครงสร้างเรขาคณิตที่ซับซ้อนอย่างอาคารหรือต้นไม้ได้ยาก
  • การเรนเดอร์พื้นฐานใช้วิธี rasterize เส้นบนแผนที่จากหลังมาหน้า แล้วอ่านความสูงและสีในแต่ละคอลัมน์ของหน้าจอเพื่อวาด เส้นแนวตั้ง โดยสามารถทำมุมมอง 90° และการฉายภาพแบบ perspective ได้ด้วยโค้ดไม่กี่บรรทัด
  • การปรับปรุงประสิทธิภาพทำได้ด้วยการวาดจากหน้าไปหลัง ใช้ y-buffer แยกตามคอลัมน์เพื่อข้ามส่วนที่ถูกบัง และลดรายละเอียดในระยะไกล

บริบทที่ Voxel Space ปรากฏขึ้น

  • ในปี 1992 CPU ช้ากว่าปัจจุบันประมาณ 1000 เท่า และการเร่งความเร็วด้วย GPU ยังไม่เป็นที่รู้จักหรือมีค่าใช้จ่ายสูงเกินรับไหว
  • เกม 3D คำนวณด้วย CPU เพียงอย่างเดียว และเอนจินเรนเดอร์โดยทั่วไปใช้วิธีวาดโพลีกอนที่เติมสีทึบ
  • NovaLogic เปิดตัว Comanche ในปี 1992 และการแสดงพื้นผิว แสงเงา และเงาของภูเขาและหุบเขาทำให้กราฟิกของเกมนี้แตกต่างจากเกมอื่นในยุคนั้น
  • README มี Web Demo of the Voxel Space Engine ให้ทดลอง

การแทนภูมิประเทศ: height map และ color map

  • วิธีที่ง่ายที่สุดในการแทนภูมิประเทศใน Voxel Space คือใช้ height map และ color map
  • Comanche ใช้แผนที่สองชนิดต่อไปนี้
    • height map แบบ 1 ไบต์ ขนาด 1024×1024
    • color map แบบ 1 ไบต์ ขนาด 1024×1024
  • แผนที่เหล่านี้มีลักษณะวนซ้ำแบบ periodic
  • แต่ละตำแหน่งบนแผนที่มีความสูงได้เพียงค่าเดียว
    • ไม่สามารถแสดงโครงสร้างเรขาคณิตที่ซับซ้อน เช่น อาคารหรือต้นไม้ได้
    • แต่ color map มีแสงเงาและเงาทอดรวมอยู่แล้ว จึงไม่จำเป็นต้องคำนวณแสงระหว่างขั้นตอนเรนเดอร์

อัลกอริทึมเรนเดอร์พื้นฐาน

  • เอนจิน Voxel Space เรนเดอร์ภูมิประเทศด้วยการ rasterize height map และ color map แล้ววาด เส้นแนวตั้ง บนหน้าจอ
  • ขั้นตอนพื้นฐานมีดังนี้
    • ล้างหน้าจอ
    • วาดจากหลังมาหน้าเพื่อรับประกันการจัดการการบัง
    • หาเส้นบนแผนที่ที่มีระยะเชิงแสงเท่ากันจากผู้สังเกต
    • คำนึงถึงมุมมองและ การฉายภาพแบบ perspective
    • แบ่งเส้นนั้นให้พอดีกับจำนวนคอลัมน์ของหน้าจอ
    • อ่านความสูงและสีจากแผนที่ 2D ที่ตำแหน่งของแต่ละช่วงเส้น
    • ใช้การฉายภาพแบบ perspective กับพิกัดความสูง
    • วาดเส้นแนวตั้งด้วยความสูงที่ฉายแล้วและสีจาก color map
  • ลูปหลักในรูปแบบ Python ที่ง่ายที่สุดจะลดค่า z จากระยะไกลเข้ามาใกล้ และเรียก DrawVerticalLine สำหรับแต่ละคอลัมน์ของหน้าจอ
  • ตัวอย่างการเรียกส่งตำแหน่ง ความสูงของกล้อง ตำแหน่งเส้นขอบฟ้า สเกลความสูง ระยะสูงสุด ความกว้างและความสูงของหน้าจอเข้าไป

เพิ่มการหมุน

  • อัลกอริทึมพื้นฐานมองได้เฉพาะทางทิศเหนือเท่านั้น
  • หากต้องการมองทิศทางอื่น ต้องเพิ่มโค้ดสำหรับหมุนพิกัด
  • เวอร์ชันที่รองรับการหมุนรับ phi เป็นมุมมอง และคำนวณ sin(phi) กับ cos(phi) ไว้ล่วงหน้า
  • นำพิกัดที่หมุนแล้วไปใช้คำนวณจุดขอบเขตมุมมองด้านซ้ายและขวา และเพิ่มค่า x กับ y ไปพร้อมกันตามแต่ละคอลัมน์ของหน้าจอ
  • โครงสร้างหลักของการเรนเดอร์ยังคงเดิม
    • คำนวณช่วงเส้นตามระยะ
    • rasterize ให้พอดีกับคอลัมน์ของหน้าจอ
    • อ่าน height map และ color map
    • วาดเส้นแนวตั้งหลังการฉายภาพแบบ perspective

วิธีปรับปรุงประสิทธิภาพ

  • แทนที่จะวาดจากหลังมาหน้า หากวาด จากหน้าไปหลัง จะช่วยลดพื้นที่ที่จะถูกบังได้
  • วิธีนี้ต้องใช้ y-buffer ที่เก็บตำแหน่ง y สูงสุดสำหรับแต่ละคอลัมน์ของหน้าจอ
    • ค่าเริ่มต้นของ y-buffer ตั้งเป็นความสูงของหน้าจอ
    • วาดเฉพาะส่วนที่มองเห็น เมื่อ height_on_screen ที่คำนวณใหม่อยู่สูงกว่า y-buffer เดิม
    • หลังจากวาดแล้ว อัปเดต y-buffer ไปยังตำแหน่งที่สูงกว่า
  • ระยะ z จะเพิ่มจากระยะใกล้ไปไกล
  • หากค่อย ๆ เพิ่ม dz จะสามารถสุ่มตัวอย่างด้วยช่วงที่ใหญ่ขึ้นในระยะไกล จึงได้เอฟเฟกต์ Level of Detail
  • เป็นวิธีเรนเดอร์ให้บริเวณใกล้มีรายละเอียดมากกว่า และบริเวณไกลมีรายละเอียดน้อยกว่า

ทรัพยากรที่ให้มาและไลเซนส์

  • ใน repository มีคู่ของ color map และ height map หลายชุด
  • ส่วนซอฟต์แวร์อยู่ภายใต้ MIT License
  • เทคโนโลยี Voxel Space อาจยังมีสิทธิบัตรคงเหลือในบางประเทศ
  • color map และ height map เป็นข้อมูลที่ reverse engineering มาจากเกม Comanche จึงไม่รวมอยู่ในไลเซนส์
  • มีลิงก์เนื้อหาที่เกี่ยวข้องคือ Voxel terrain engine - an introduction

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-01-05
ความเห็นจาก Hacker News

  • เจ๋งมาก คิดถึงยุคที่ อัลกอริทึมใหม่ ๆ ที่สง่างาม แบบนี้สร้างประสบการณ์เหมือนเวทมนตร์ให้เราได้
    อาจเป็นเพราะอายุมากขึ้นถึงรู้สึกแบบนั้นก็ได้ แต่ผมว่ากเกมในยุคที่ทรัพยากรฮาร์ดแวร์จำกัดมีความเป็นเวทมนตร์มากกว่าตอนนี้ ในยุค 80, 90 และต้นยุค 2000 แทบทุกปี อย่างน้อยก็ทุกเจเนอเรชัน เกมจะผลักดันตัวสื่อเองไปข้างหน้า และนักพัฒนาก็รีดประสิทธิภาพฮาร์ดแวร์จนสุดด้วยเทคนิคใหม่ ๆ และการปรับแต่งที่เหมือนเวทมนตร์ล้วน ๆ
    ทุกวันนี้แพลตฟอร์มแฟนตาซีอย่าง PICO-8 น่าสนใจกว่าเกมภาคต่อซ้ำ ๆ จากสตูดิโอ AAA มาก และก็ไม่ค่อยเข้าใจว่าทำไมเกมที่แทบจะแค่เปลี่ยนแอสเซ็ตถึงประสบความสำเร็จได้ทุกปีแบบนั้น

    • เกม AAA สมัยใหม่ก็ยังมีเทคโนโลยีที่เหมือนเวทมนตร์อยู่มาก จริง ๆ แล้วอุตสาหกรรมเกมเป็นหนึ่งในไม่กี่วงการที่ให้ความสำคัญกับ ประสิทธิภาพ อย่างจริงจัง และบางครั้งก็ให้ความสำคัญกับประสิทธิภาพมากกว่าความปลอดภัยหรือความถูกต้องด้วยซ้ำ
      เพียงแต่ตอนนี้มันซับซ้อนกว่ามากและไม่สะดุดตาเท่าเดิม เมื่อก่อนเราเห็นพัฒนาการจากสามเหลี่ยมแบน ๆ ไปสู่เท็กซ์เจอร์ได้ด้วยทริกคณิตศาสตร์ฉลาด ๆ แต่ตอนนี้พัฒนาการเป็นทำนองทำให้เงาในมุมห้องดูดีขึ้น การปรับปรุงเท็กซ์เจอร์ใคร ๆ ก็ดูออกทันที แต่เงาตรงมุมห้อง ถ้าไม่ใช่คนในวงการก็คงชี้ชัดได้ยาก ถึงอย่างนั้นองค์ประกอบเหล่านี้ก็สะสมกันจนทำให้กราฟิกโดยรวมดีขึ้น เพียงแต่ไม่ประทับใจเท่าเมื่อก่อน
      อุตสาหกรรมเกม AAA เป็นธุรกิจขนาดใหญ่ ต้นทุนสร้างเกมมหาศาล และนักลงทุนก็ต้องการผลตอบแทน ดังนั้นโดยทั่วไปจึงสำรวจตลาด ดูว่าอะไรขายดี แล้วทำไปในทิศทางคล้าย ๆ กัน ความเป็นต้นฉบับลดลง แต่ความเสี่ยงก็ต่ำลง
      ในทางกลับกัน อุตสาหกรรมเกมอินดี้มีสตูดิโอหลายพันแห่ง และเพราะสู้ AAA ในด้านปริมาณคอนเทนต์หรือความเนี้ยบไม่ได้ จึงต้องมีอาวุธอื่นอย่างไอเดียแปลกใหม่เพื่อให้โดดเด่นออกจากฝูง แต่ตอนนี้หลายครั้งแรงขับหลักไม่ได้อยู่ที่การเอาชนะข้อจำกัดทางเทคนิคแล้ว เพราะข้อจำกัดไม่ได้มีมากเท่าสมัยก่อน กลับกัน มักจะไม่ได้ผลักดันด้านเทคนิคเท่างาน AAA เพราะต้นทุนไม่เอื้อ
      ผมไม่ค่อยรู้จักซีนของ PICO-8 แต่ก็สงสัยว่าในนั้นมีสัดส่วนแค่ไหนที่เป็นการเอาชนะข้อจำกัดทางเทคนิคที่ตั้งขึ้นเอง และแค่ไหนที่เป็นการใช้แพลตฟอร์มตามวิธีที่มันตั้งใจไว้ พร้อมโฟกัสที่เกมเพลย์
    • นี่เหมือนการรำลึกอดีตผ่าน แว่นเชื่อมสีชมพูขนาด 1/4 นิ้ว มากกว่า เกม AAA สมัยใหม่ก็มีช่วงเวลาที่ดีจนทำให้มึนงงได้เหมือนกัน และแม้จะมีโรคภาคต่อซ้ำซาก แต่ก็มีผลงานที่เป็นต้นฉบับด้วย และเทคโนโลยีก็เป็นสิ่งที่ทำให้เรื่องนั้นเป็นไปได้อย่างชัดเจน
      อีกอย่าง จำได้ว่าเมื่อก่อนก็มีเกมที่แย่มาก ๆ ๆ อยู่เยอะจริง ๆ
    • ผมเคยใช้ อัลกอริทึมนี้ทำ 3D Mario Kart บนเครื่องคิดเลขอยู่ เครื่องคิดเลขนั้นปกติแม้แต่กราฟิก 2D ก็แทบจะประมวลผลไม่ไหวแล้ว เลยน่าสนุกดี แต่สุดท้ายก็ทำไม่เสร็จ
      หนึ่งในโปรโตไทป์คืออันนี้: https://youtu.be/9Z8Bm8ZmWKI
    • ผมเคยใช้ อัลกอริทึมนี้ทำ 3D Mario Kart บนเครื่องคิดเลขอยู่ เครื่องคิดเลขนั้นปกติแม้แต่กราฟิก 2D ก็แทบจะประมวลผลไม่ไหวแล้ว เลยน่าสนุกดี แต่สุดท้ายก็ทำไม่เสร็จ
      หนึ่งในโปรโตไทป์คืออันนี้: https://media.discordapp.net/attachments/953383695908216843/...
    • ในเทคโนโลยีเกมยังมีนวัตกรรมเจ๋ง ๆ อยู่มาก ลองดูเกมอย่าง Noita, Dreams, Teardown และเกมที่ใหม่กว่านั้นอย่าง Tiny Glade ก็ได้
      พรีเซนต์ด้านเทคนิคล่าสุดของ Tiny Glade เต็มไปด้วยเรื่องที่เหมือนเวทมนตร์: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      แม้แต่ในเอนจินและเฟรมเวิร์กระดับพื้นฐานกว่านั้นก็มีเทคโนโลยีเจ๋ง ๆ ออกมาเช่นกัน เช่น Nanite/Lumen/MegaLights ของ UE5

  • ลิงก์ที่เกี่ยวข้อง มีอย่างอื่นอีกไหม?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - ตุลาคม 2023, 2 ความเห็น
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - มีนาคม 2021, 71 ความเห็น
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - มกราคม 2020, 116 ความเห็น
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - พฤศจิกายน 2017, 93 ความเห็น
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - กันยายน 2017, 2 ความเห็น

  • นึกถึง mars.com ขึ้นมาทันที ไม่ใช่โดเมน แต่เป็นโปรแกรม วิดีโอ: https://www.youtube.com/watch?v=_zSjpIyMt0k
    เพิ่มเติม: มีอยู่บน Pouet ด้วย: https://www.pouet.net/prod.php?which=4662

    • เจอ อิมพลีเมนต์ด้วย JavaScript ของเดโมนี้ด้วย: http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • ความทรงจำเก่า ๆ ผุดขึ้นมาเลย ตอนที่มันถูกส่งต่อมาถึงผมราวปี 1998 มันอยู่ใน ไฟล์ Microsoft Word และควบคุมด้วยเมาส์
      ตอนนั้นคิดว่ามันเจ๋ง แต่เพราะยังเป็นเด็กที่ไม่รู้อะไรเกี่ยวกับเดโมซีนหรือการเขียนโปรแกรมเลย ก็เลยผิดหวังที่มันไม่ใช่เกมเต็ม ๆ พอมองย้อนกลับไป ผมคิดแค่ว่ามันเป็นเดโม DirectX กาก ๆ ที่ส่งต่อกันทางอีเมล ไม่รู้เลยว่ามันเป็นของที่มีอยู่จริง
    • พูดให้ถูกคือ mars.com รันได้ลื่นแม้บน 286 8MHz
    • เจ็บเลย ยังจำได้ว่าลองรันบน 286 แล้วทึ่งมาก ขณะเดียวกันก็ผิดหวังที่ Wing Commander 3 รันบนเครื่องเดียวกันไม่ได้

  • วิธีเรนเดอร์ดูสะอาดดี แต่ไม่แน่ใจว่าจะเรียกสิ่งนี้ว่า voxel ได้ไหม มันเรนเดอร์ปริมาตรแบบใดก็ได้ไม่ได้ และวิธีเก็บข้อมูลก็มีตำแหน่งได้แค่ค่าเดียวสำหรับ x,y ที่กำหนด
    มันก็แค่อิมพลีเมนต์เท่ ๆ ของ heightmap renderer ไม่ใช่เหรอ?

    • ผมคิดว่ามองเป็น voxel engine ได้แน่นอน heightmap ไม่รองรับส่วนยื่นเหมือน octree แต่สุดท้ายความสูงก็คือสแต็กของ voxel
      octree ที่ไม่มีส่วนยื่นก็จะมีรูปทรงเหมือนสิ่งนี้เป๊ะ
    • เท่าที่ผมรู้ voxel หมายถึงอะไรประมาณ volume element คล้ายกับที่ pixel มาจาก picture element และ x ก็น่าจะเป็นตัวอักษรที่ใส่มาให้ดูเท่มากกว่า
      ในวิธีเรนเดอร์แบบนี้ แต่ละคอลัมน์คือกล่อง 3D ดังนั้นเรียกว่า เมทริกซ์ voxel 2x2 ก็ไม่น่ามีปัญหาอะไร
    • heightmap renderer แบบนี้ในยุคนั้นถูกเรียกว่า “voxel” แน่นอน
    • ใช่ ชื่อที่ตั้งให้อัลกอริทึมนี้ทำให้เข้าใจผิด

  • มีความทรงจำที่ดีมาก ตอนเรียนตรีโกณมิติที่จำเป็นในโรงเรียนมัธยมช่วงทศวรรษ 1990 พร้อม ๆ กับที่ทำ terrain viewer แบบนี้ ตอนแรกทำด้วย Pascal แล้วต่อด้วย C และ Assembly
    ตอนนั้นถ้าอยากให้มันรันได้ ต้องใช้การปรับแต่งระดับต่ำสารพัด
    การหาวิธีอิมพลีเมนต์และปรับแต่งให้เร็วโดยไม่มีหนังสือหรืออินเทอร์เน็ตให้อ้างอิง เป็นหนึ่งในสิ่งที่คุ้มค่าที่สุดสำหรับผมเป็นการส่วนตัว

  • ผมทำเกมด้วยเทคนิคนี้: https://eri0o.itch.io/i-rented-a-boat
    ทำด้วย Adventure Game Studio และสร้างบนเอนจินเวอร์ชันก่อนหน้าที่ยังไม่ได้ optimize ผมขี้เกียจอัปเดตหน้า itch เลยปล่อยไว้อย่างนั้น แต่สักวันจะทำ
    ผมเขียนไว้ตรงนั้นว่าทำอย่างไร และในฟอรัม AGS มีรายละเอียดมากกว่านั้น

    • น่าประทับใจที่ทำแบบนี้ใน AGS ได้

  • น่าจะใส่ [2020] ในชื่อเรื่องได้ และดูจากคอมเมนต์อื่น ๆ ในลิงก์กระทู้ด้านล่าง [2017] ก็น่าจะเป็นไปได้
    ยังมีกระทู้ปี 2021 เกี่ยวกับ repo เดียวกันด้วย: https://news.ycombinator.com/item?id=26631995
    ในเธรดนั้นก็มีลิงก์ต่อไปยังการอภิปรายอื่น ๆ ด้วย
    แม้จะไม่เหมือนกันเสียทีเดียว แต่ผมจำได้ว่าตอนเริ่มเรียนเขียนโปรแกรม ผมเคยเขียนโปรแกรมที่สร้าง heightmap ของภูมิประเทศ แล้วเรนเดอร์สไตล์ isometric ด้วยเทคนิคคล้าย ๆ กัน ทำด้วย QBasic รันบนเครื่อง DOS ยุค 386 ของโรงเรียนมัธยมต้น และใช้หน่วยความจำกราฟิกเป็นพื้นที่ทำงานชั่วคราว
    มันช้ามาก แต่ผมหลงใหลผลลัพธ์ที่ได้ และเป็นหนึ่งในเหตุผลที่ทำให้ผมเขียนโปรแกรมต่อมา

  • จำได้ว่าเคยอ่านเรื่องนี้ที่ไหนสักแห่งมาก่อน ครั้งนี้เลยคอมเมนต์ไว้เพื่อจะได้ไม่ทำหายอีก
    ในฐานะแฟน flight simulator ผมยังจำแรงกระแทกตอนเล่น Comanche ครั้งแรกได้ มันเหมือนมาจากอนาคตหรือจากหนัง และทำให้รู้สึกจริง ๆ ว่าเราอยู่ในยุคคอมพิวเตอร์

    • Novalogic ใช้เทคนิคนี้กับการเรนเดอร์ภูมิประเทศอยู่นานพอสมควร และเกมที่ผมชอบที่สุดคือ Delta Force ภาคแรก
      ดูเหมือนว่าใน Comanche 4 และ Black Hawk Down ต้นฉบับ พวกเขาเลิกใช้วิธีนี้แล้วเปลี่ยนไปเป็น polygon engine: https://en.wikipedia.org/wiki/Comanche_4#Reception
    • จำ Comanche ได้ ทำให้นึกถึงตอนที่ทึ่งกับ procedural generation ใน Rescue on Fractalus[0] บน Atari 8-bit ซึ่งชื่อก่อนวางจำหน่ายคือ Behind Jaggi Lines
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg ฉากลงจอดบนโลกอยู่ที่ 1:00

  • เจ๋งจริง ๆ
    ในเกมสมัยใหม่ส่วนใหญ่ บางครั้งจะเห็นได้ว่าภูเขาเป็น โครงสร้างกลวง เพราะมุมกล้องแปลก ๆ หรือปัญหา clipping
    แต่ในวิธีนี้ ภูเขาอัดแน่นตันอยู่ข้างใน >:)

  • ขอแนะนำอย่างยิ่งให้ลองทำ software renderer แบบนี้เล่น ๆ ray tracer เป็นโปรเจกต์ที่พบได้บ่อย แต่โค้ดเรนเดอร์เรียลไทม์สไตล์เรโทรแบบนี้ก็เหมาะเป็นโปรเจกต์สุดสัปดาห์เหมือนกัน
    นานมาแล้วผมเคยอิมพลีเมนต์อัลกอริทึมที่แทบเหมือนกันนี้ พูดให้ถูกคือพอร์ตโค้ด SDL มาเป็นแบบฝึกหัดเพื่อเรียน canvas2d: http://namuol.github.io/earf-html5/
    แน่นอนว่าอิมพลีเมนต์ที่ลิงก์ไว้นั้นเร็วกว่าและเรียบง่ายกว่าของผมมาก ดังนั้นถ้ากำลังหาเอกสารอ้างอิง ผมไม่แนะนำโค้ด CoffeeScript เก่า ๆ ของผม…