VoxelSpace: 20 लाइनों से कम कोड में लागू किया गया terrain rendering algorithm (2020)

 (github.com/s-macke)
4 पॉइंट द्वारा GN⁺ 2025-01-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Voxel Space 1992 में NovaLogic के Comanche में इस्तेमाल हुई 2.5D terrain rendering technique है, जिसने उस दौर में जब GPU acceleration उपलब्ध नहीं था या महंगा था, सिर्फ CPU से textured पहाड़ों और घाटियों को दिखाया
  • terrain को height map और color map से व्यक्त किया जाता है, और Comanche ने 1024×1024 1-byte height map और 1024×1024 1-byte color map का उपयोग किया
  • color map में पहले से shading और shadows मौजूद होते हैं, इसलिए rendering के दौरान lighting calculation की जरूरत नहीं होती, लेकिन map की हर position केवल एक height रख सकती है, इसलिए इमारतों या पेड़ों जैसी complex geometric structures दिखाना मुश्किल है
  • basic rendering में पीछे से आगे की ओर map के line segments को rasterize किया जाता है, और हर screen column के लिए height और color पढ़कर vertical line खींची जाती है; 90° field of view और perspective projection को कुछ ही lines of code में लागू किया जाता है
  • performance improvements आगे से पीछे की ओर draw करते हुए column-wise y-buffer से छिपे हिस्सों को skip करके, और दूर की दूरी के लिए detail कम करके संभव हैं

Voxel Space के आने का संदर्भ

  • 1992 में CPU आज की तुलना में 1000 गुना धीमे थे, और GPU acceleration या तो जाना-पहचाना नहीं था या afford करना मुश्किल था
  • 3D games की calculation सिर्फ CPU से होती थी, और rendering engines में single-color filled polygons draw करना आम तरीका था
  • NovaLogic ने 1992 में Comanche release किया, और पहाड़ों व घाटियों की textures, shading, और shadow representation उस समय के game graphics से अलग दिखती थी
  • README Web Demo of the Voxel Space Engine प्रदान करता है

terrain representation: height map और color map

  • Voxel Space में terrain को represent करने का सबसे आसान तरीका height map और color map का इस्तेमाल है
  • Comanche निम्न दो maps का उपयोग करता है
    • 1024×1024 1-byte height map
    • 1024×1024 1-byte color map
  • ये maps periodic रूप से repeat होने वाले हैं
  • हर map position केवल एक height रख सकती है
    • इमारतों, पेड़ों जैसी complex geometric structures को represent नहीं किया जा सकता
    • इसके बदले color map में पहले से shading और shadows शामिल होते हैं, इसलिए rendering process में lighting calculate नहीं करनी पड़ती

basic rendering algorithm

  • Voxel Space engine height map और color map को rasterize करके और screen पर vertical lines draw करके terrain render करता है
  • basic procedure इस प्रकार है
    • screen clear करें
    • occlusion handling सुनिश्चित करने के लिए पीछे से आगे draw करें
    • observer से समान optical distance पर आने वाली map की line खोजें
    • field of view और perspective projection को ध्यान में रखें
    • उस line को screen columns की संख्या के अनुसार split करें
    • हर segment position पर 2D map से height और color पढ़ें
    • height coordinate पर perspective projection apply करें
    • projected height और color map के color से vertical line draw करें
  • सबसे सरल Python रूप का core loop z को दूर की distance से पास की distance की ओर घटाते हुए हर screen column पर DrawVerticalLine call करता है
  • example call में position, camera height, horizon position, height scale, max distance, screen width और height pass किए जाते हैं

rotation जोड़ना

  • basic algorithm केवल उत्तर दिशा देख सकता है
  • दूसरी दिशाएं देखने के लिए coordinates को rotate करने वाला code जोड़ा जाता है
  • rotated version phi को field of view के रूप में लेता है, और sin(phi) तथा cos(phi) को पहले से calculate करता है
  • left/right viewing boundary points की calculation में rotated coordinates apply किए जाते हैं, और हर screen column के साथ x और y को साथ-साथ increment किया जाता है
  • rendering की core structure वही रहती है
    • distance-wise line segment calculation
    • screen columns के अनुसार rasterization
    • height map और color map lookup
    • perspective projection के बाद vertical line draw करना

performance improvement methods

  • पीछे से आगे draw करने के बजाय आगे से पीछे draw करने पर occluded areas कम किए जा सकते हैं
  • इस तरीके में हर screen column के लिए सबसे ऊंची y position store करने वाला y-buffer चाहिए
    • initial y-buffer value screen height पर set होती है
    • newly calculated height_on_screen मौजूदा y-buffer से ऊपर होने पर ही visible part draw किया जाता है
    • draw करने के बाद y-buffer को अधिक ऊंची position पर update किया जाता है
  • distance z पास से दूर की ओर बढ़ती है
  • dz को धीरे-धीरे बढ़ाने पर दूर की distance पर बड़े intervals से sampling की जा सकती है, जिससे Level of Detail effect मिलता है
  • पास की जगहें अधिक detail में, और दूर की जगहें कम detail में render की जाती हैं

provided materials और license

  • repository में कई color map और height map pairs शामिल हैं
  • software वाला हिस्सा MIT license के तहत है
  • Voxel Space technology पर कुछ देशों में अभी भी patents बाकी हो सकते हैं
  • color maps और height maps Comanche game से reverse-engineered material हैं, इसलिए license से बाहर हैं
  • related material के रूप में Voxel terrain engine - an introduction link दिया गया है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-01-05
Hacker News की राय

  • बहुत शानदार। वह दौर याद आता है जब ऐसे नए और elegant algorithms किसी जादू जैसा अनुभव बना देते थे
    हो सकता है उम्र बढ़ने के कारण ऐसा लगता हो, लेकिन जब hardware resources सीमित थे, उस समय के games में आज की तुलना में ज्यादा जादू था। 80s, 90s और 2000s की शुरुआत में लगभग हर साल, या कम-से-कम हर generation में, games इस medium को आगे धकेलते थे, और developers नई techniques और सचमुच जादू जैसी optimizations से hardware performance की आखिरी बूंद तक निकाल लेते थे
    आजकल AAA studios की दोहराई जाने वाली releases की तुलना में PICO-8 जैसे fantasy platforms कहीं ज्यादा दिलचस्प लगते हैं, और मुझे सच में समझ नहीं आता कि असल में सिर्फ assets बदलकर बनाए गए games हर साल इतने सफल कैसे हो जाते हैं

    • आधुनिक AAA games में भी अब भी बहुत सारी जादू जैसी technology होती है। सच में, game industry उन गिने-चुने क्षेत्रों में से है जो performance को गंभीरता से लेती है, और कभी-कभी safety या correctness से भी ज्यादा performance को महत्व देती है
      बस अब यह कहीं ज्यादा complex और कम दिखाई देने वाली हो गई है। पहले कोई smart maths trick flat triangles से textures तक की प्रगति दिखा देती थी, जबकि अब प्रगति किसी कमरे के कोने की shading को बेहतर बनाने जैसी होती है। Texture improvement हर कोई तुरंत पहचान लेता है, लेकिन कोने की shadow को industry से बाहर का व्यक्ति शायद साफ़-साफ़ न बता पाए। फिर भी ऐसे elements मिलकर overall graphics को बेहतर बनाते हैं, बस पहले जितने प्रभावशाली नहीं लगते
      AAA game industry एक बड़ा business है, games बनाने की लागत बहुत भारी है, और investors returns चाहते हैं। इसलिए आमतौर पर market research की जाती है, जो बिकता है उसे देखा जाता है, और फिर उसी जैसी दिशा में बनाया जाता है। मौलिकता कम हो जाती है, लेकिन risk भी कम होता है
      इसके उलट indie game industry में हजारों studios हैं, और वे content की मात्रा या polish में AAA को नहीं हरा सकते, इसलिए भीड़ से अलग दिखने के लिए उन्हें original ideas जैसे दूसरे हथियार चाहिए होते हैं। हालांकि अब अक्सर मुख्य प्रेरणा technical limitations को पार करना नहीं होती। क्योंकि restrictions पहले जितनी ज्यादा नहीं रहीं। बल्कि cost के लिहाज से afford न कर पाने के कारण वे अक्सर AAA productions की तुलना में technical side को कम push करते हैं
      PICO-8 scene के बारे में मुझे ज्यादा नहीं पता, लेकिन यह जानने की उत्सुकता है कि उसमें कितना हिस्सा artificial technical constraints को पार करने में है, और कितना हिस्सा platform को intended तरीके से इस्तेमाल करते हुए gameplay पर focus करने में है
    • यह मुझे लगभग गुलाबी 1/4-inch welding goggles लगाकर की गई nostalgia जैसा लगता है। आधुनिक AAA games में भी दिमाग सुन्न कर देने वाले शानदार पल होते हैं, repetitive sequels की बीमारी भी है लेकिन original works भी हैं, और technology साफ़ तौर पर यह संभव बनाती है
      यह भी याद है कि पुराने समय में सचमुच, सचमुच, सचमुच बहुत खराब games भी बहुत थे
    • मैं इस algorithm से calculator पर 3D Mario Kart बना रहा था। वह calculator आम तौर पर 2D graphics भी मुश्किल से संभालता था, इसलिए यह काफी मजेदार था, लेकिन अंत तक पूरा नहीं कर पाया
      prototypes में से एक यह है: https://youtu.be/9Z8Bm8ZmWKI
    • मैं इस algorithm से calculator पर 3D Mario Kart बना रहा था। वह calculator आम तौर पर 2D graphics भी मुश्किल से संभालता था, इसलिए यह काफी मजेदार था, लेकिन अंत तक पूरा नहीं कर पाया
      prototypes में से एक यह है: https://media.discordapp.net/attachments/953383695908216843/...
    • game technology में अब भी बहुत सारे शानदार innovations हैं। Noita, Dreams, Teardown जैसे games देखिए, और हाल की game Tiny Glade भी है
      Tiny Glade की हालिया technical talk जादू जैसी चीजों से भरी है: https://youtu.be/jusWW2pPnA0?si=IE-6W0Z1VCBld0AT
      ज्यादा बुनियादी level के engines और frameworks में भी शानदार technology निकल रही है। उदाहरण के लिए UE5 के Nanite/Lumen/MegaLights हैं

  • संबंधित links हैं। कुछ और भी हैं क्या?
    VoxelSpace – Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=38051859 - अक्टूबर 2023, 2 comments
    Voxel Space: Comanche's terrain rendering in less than 20 lines of code (2020) - https://news.ycombinator.com/item?id=26631995 - मार्च 2021, 71 comments
    Terrain rendering algorithm in less than 20 lines of code - https://news.ycombinator.com/item?id=21944573 - जनवरी 2020, 116 comments
    Terrain rendering in fewer than 20 lines of code - https://news.ycombinator.com/item?id=15772065 - नवंबर 2017, 93 comments
    Show HN: Voxel Space – terrain rendering in less than 20 lines of code - https://news.ycombinator.com/item?id=15339016 - सितंबर 2017, 2 comments

  • mars.com तुरंत याद आया। यह domain नहीं, program है। वीडियो: https://www.youtube.com/watch?v=_zSjpIyMt0k
    अतिरिक्त: Pouet पर भी है: https://www.pouet.net/prod.php?which=4662

    • इस demo का JavaScript implementation भी मिला: http://web.archive.org/web/20140107070635/http://ppl-pilot.c...
    • पुरानी यादें एकदम ताजा हो गईं। करीब 1998 में जब यह मेरे पास पहुँचा था, तो यह एक Microsoft Word file के अंदर था और mouse से control होता था
      उस समय मुझे यह cool लगा था, लेकिन demosene या programming के बारे में कुछ नहीं जानने वाला बच्चा होने की वजह से मैं निराश हुआ कि यह पूरा game नहीं था। पीछे मुड़कर देखूँ तो मैंने इसे बस email पर घूमने वाला कोई साधारण-सा DirectX demo समझा था; यह नहीं पता था कि यह सच में मौजूद कोई चीज़ थी
    • सटीक कहें तो mars.com 8MHz 286 पर भी smooth चलता था
    • दर्द होता है। याद है कि 286 पर इसे चलाकर मैं अभिभूत हो गया था। साथ ही उसी machine पर Wing Commander 3 न चल पाने से निराश भी हुआ था

  • Rendering तरीका साफ-सुथरा है, लेकिन पता नहीं इसे voxel कहा जा सकता है या नहीं। यह arbitrary volume render नहीं कर सकता, और data storage तरीका भी दिए गए x,y के लिए सिर्फ एक ही position रख सकता है
    क्या यह बस heightmap renderer का शानदार implementation नहीं है?

    • मुझे तो लगता है कि इसे निश्चित रूप से voxel engine माना जा सकता है। heightmap, octree की तरह overhangs support नहीं करता, लेकिन आखिरकार height voxels का stack ही है
      बिना overhangs वाला octree ठीक इसी shape का होगा
    • मेरी जानकारी में voxel का मतलब volume element जैसा होता है। जैसे pixel, picture element से आया है, और x मुझे style के लिए जोड़ा गया अक्षर ज्यादा लगता है
      इस rendering तरीके में हर column एक 3D box है, इसलिए इसे 2x2 voxel matrix कहना भी कोई बड़ी समस्या नहीं लगती
    • ऐसे heightmap renderers को उस समय निश्चित रूप से “voxel” कहा जाता था
    • सही है, इस algorithm को दिया गया नाम भ्रम पैदा करता है

  • 1990s में high school में जरूरी trigonometry सीखते हुए, ऐसा terrain viewer बनाने की मेरी यादें बहुत अच्छी हैं। पहले Pascal में, फिर C और Assembly में बनाया था
    तब इसे चलाने लायक बनाने के लिए हर तरह की low-level optimizations चाहिए होती थीं
    बिना किसी reference book या internet के implementation तरीका निकालना और optimize करना मेरे लिए व्यक्तिगत रूप से सबसे संतोषजनक कामों में से एक था

  • मैंने इस technique से game बनाया था: https://eri0o.itch.io/i-rented-a-boat
    यह Adventure Game Studio में बनाया गया था, और engine के पुराने version पर बना था जिसे तब तक optimize नहीं किया गया था। itch page update करना झंझट लगता है, इसलिए वैसे ही छोड़ा हुआ है, लेकिन कभी न कभी करूँगा
    वहाँ मैंने इसे कैसे बनाया, इस पर लिखा है, और AGS forum में और ज्यादा details हैं

    • AGS में यह संभव है, यह impressive है

  • title में [2020] डालना भी ठीक लग सकता है, और नीचे discussion link की दूसरी comments देखें तो [2017] भी संभव लगता है
    इसी repository पर 2021 की discussion भी हुई थी: https://news.ycombinator.com/item?id=26631995
    उस thread में भी दूसरी discussions के links आगे जुड़े हैं
    बिल्कुल वही नहीं, लेकिन याद है कि जब मैं programming सीखना शुरू कर रहा था, तब terrain heightmap generate करने और ऐसी ही technique से isometric-style rendering करने वाला program लिखा था। QBasic में बनाया था, middle school के 386-era DOS machines पर चलाया था, और graphics memory को temporary workspace की तरह इस्तेमाल किया था
    यह बेहद slow था, लेकिन output ने मुझे मोहित कर दिया और programming जारी रखने की वजहों में से एक बना

  • याद है कि पहले कहीं यह पढ़ा था; इस बार खो न जाए इसलिए comment छोड़ रहा हूँ
    flight simulator fan के रूप में Comanche पहली बार खेलने का झटका मुझे अब भी याद है। ऐसा लगा जैसे यह भविष्य या किसी movie से आया हो, और सचमुच लगा कि मैं computer age में जी रहा हूँ

    • Novalogic ने terrain rendering के लिए इस technique को काफी लंबे समय तक इस्तेमाल किया, और मेरी पसंदीदा पहली Delta Force है
      लगता है Comanche 4 और मूल Black Hawk Down में उन्होंने यह तरीका छोड़कर polygon engine अपना लिया था: https://en.wikipedia.org/wiki/Comanche_4#Reception
    • Comanche याद है। 8-bit Atari पर Rescue on Fractalus[0], जिसका pre-release नाम Behind Jaggi Lines था, उसकी procedural generation देखकर चकित होने का समय याद आ गया
      [0] https://www.youtube.com/watch?v=FbZ-chrOgGg Earth landing scene 1:00 पर आता है

  • वाकई शानदार
    ज्यादातर modern games में अजीब camera angles या clipping issues की वजह से कभी-कभी दिख जाता है कि पहाड़ अंदर से खाली structure हैं
    लेकिन इस तरीके में पहाड़ solid भरे हुए हैं >:)

  • ऐसे software renderer को मजे के लिए बनाकर देखने की जोरदार सिफारिश करूँगा। ray tracer आम project है, लेकिन इस तरह का retro real-time rendering code भी weekend project के लिए अच्छा है
    बहुत पहले मैंने लगभग यही algorithm implement किया था। सटीक कहें तो canvas2d सीखने की practice के तौर पर SDL code port किया था: http://namuol.github.io/earf-html5/
    बेशक linked implementation मेरे वाले से कहीं तेज और कहीं सरल है, इसलिए अगर reference material ढूँढ रहे हों तो मेरे पुराने CoffeeScript code की recommendation नहीं करूँगा…