7 ms·
How video games use lookup tables
- LuciBb 3y ago[dead]
- reactordev 3y agoOff the top of my head, my uses of LUTs have been: - Atmospheric scattering. - Tinting Sprites. - Nightvision Scopes. - FLIR scopes. - B&W “video feed” effect. - Glitch effects. - Heightmap Shading. - Alpha dot factor for spaceship exhaust plumes. - Heatmap of website visitors mouse dwellings. - Crystalline Effects. - And finally, post processing colorization in raw color space. LUTs are a visualization of an array of values known to you, and it’s amazingly useful.
- deleted 3y ago[deleted]
- corysama 3y ago> Tinting Sprites Kids these days have forgotten all about palettized sprites! Where do ya think the term “palette swap” comes from? ;) http://www.effectgames.com/demos/canvascycle/ http://www.effectgames.com/demos/canvascycle/ It fell out of favor because OG Xbox was bad at it and Photoshop doesn’t support it. But, modern hardware can totally handle palette swaps make in AESprite.
- charcircuit 3y ago>It fell out of favor because OG Xbox was bad at it It fell out of favor because hardware no longer needed to use palettes as they had enough memory to store the actual color.
- bregma 3y agoIt fell out of favour when the move to 16-bit systems meant no more hardware sprites.
- reactordev 3y agoIt fell out of favor when we could just store 1000x more sprites. It was memory, not instruction-set. Tinting then happened as a pre-build step until finally shaders replaced the practice entirely.
- corysama 3y agoInstead of “fell out of favor” I shoulda said “artists stopped being informed of its existence and occasionally invented poor approximations to it from first principles”. Such as tinting sprites to approximate palette swaps of the retro style they are referencing. You can do so much more than tint with palettes. The animations in the link I posted each a composed of a single 8-bit image and a function to rotate specific sections of the palette.
- reactordev 3y agoI’m intimately familiar with palette animations. You’re right though, it’s a technique that was lost due to hardware no longer limiting the artists. I still find it to be far superior to sprite tile replacement animations.
- corysama 3y agoThe SNES and Genesis definitely had hardware sprites. The PS1 and PS2 worked with palettized textures 99% of the time and had hardware quads. The N64 could do palettized textures and quads. The same for the OG Xbox, but it was a big speed hit vs DXTC. With the Xbox360 and PS3 you could implement palettized textures as a shader. But, only the most special cases bothered.
- smolder 3y agoI assume you mean the move to 16 bit color framebuffers, not systems with 16 bit CPUs? That was about the point where palettes and sprite and tile based 2D acceleration stopped being relevant.
- qiller 3y agoAlso: https://news.ycombinator.com/item?id=37823805 https://news.ycombinator.com/item?id=37823805 (You probably shouldn't use a lookup table (2022))
- pvg 3y agoThat's about a different, less specific meaning of 'look up table' (vs. 'LUT')
- pclmulqdq 3y agoI was the author of that piece. This blog is about graphics LUTs, which fall into point (4) of the "when to use lookup tables" section. GPUs have dedicated constant memories that were specifically made for holding lookup tables so that they can be accessed quickly and deterministically. Graphics LUTs are a really powerful tool because of that, and have none of the performance shortcomings.
- Anotheroneagain 3y agoWhy can't CPUs be told what to cache? Is it because the instruction sets are obsolete, or is there a technical reason why they can't be added?
- djmips 3y agoIt could be added and it was a feature on the Gamecube CPU for example - you were able to lock the cache and then, IIRC, half the cache was used as normal and half was at your disposal for very fast access to look up tables or data you were using over and over again. Some code to deform 3D meshes when animating them using a skeleton used the locked cache to speed up that operation greatly by having the bone matrices at hand. A problem I imagine on modern processors is the cache might be shared amongst several cores and interrupts etc. Back in the nineties, 3DFX made a speed of light rendering demo for the Voodoo1 where they took over the entire machine and through intimate knowledge of cache behaviour effectively set aside an area in the L1 cache that would contain some data they could stream in and speed up their triangle setup.
- Cloudef 3y agoHere is video how wind waker uses many luts to do its unique look (BoTW and ToTK use the same techniques) https://www.youtube.com/watch?v=mnxs6CR6Zrk https://www.youtube.com/watch?v=mnxs6CR6Zrk
- gxs 3y agoEven in boring old business process land, it’s surprising how useful this is. Often you can simplify a code base full of conditional statements with a tidy lookup table. I think the reason this isn’t always thought of is because a lookup table might end up with 50k rows even for something that might seem simple. This might some like a lot to end users, but thankfully the computer doesn’t mind. Also, the look up tables are so repetitive that the tables are usually pretty easy to manage, and still worth it even when they aren’t. On top of that, they can be configured by end users without code changes. All in all, a really useful concept, especially for a lot of scenarios that always pop up when coding business logic.
- chii 3y ago> On top of that, they can be configured by end users without code changes. and that is how you end up with a DSL.
- gxs 3y agoHere we go, knew someone would jump in here with their opinions on why this is bad etc. You’re reading way too much into this, this simply solves a particular set of problems well in this context and that’s that. Anything you use can get turned into something ugly given enough time and lack of supervision.
- chii 3y ago> their opinions on why this is bad etc. where did i say it's bad? DSLs aren't inherently bad (or good for that matter). > You’re reading way too much into this i think you're projecting your own ideas onto me!
- gxs 3y agoHa, sorry, guess I was a bit defensive. Forget sometimes not everyone is a jerk by default online.
- oakwhiz 3y ago
- bemmu 3y agoThe first look-up table effect that really impressed me was to use them for making a textured tunnel. You have a look-up table such that for each pixel on the screen, you know its angle and distance from the center of the screen. With this you can pick which texel to put at each pixel location. It looks as if you are moving in a tunnel with 3D geometry, but it's so cheap you can even do it on pico: https://www.lexaloffle.com/bbs/?pid=63818 https://www.lexaloffle.com/bbs/?pid=63818 At first I thought the game Stardust must have used this effect, but reading up on it just now they actually just play a repeating 6 frame animation for the background! https://codetapper.com/amiga/sprite-tricks/stardust/ https://codetapper.com/amiga/sprite-tricks/stardust/
- taeric 3y agoIf you view color palette as a lookup table, palette cycling was very common and feels very related.
- dividuum 3y agoColor palette definitely counts. I remember the lookup table Quake used to map its 256 color VGA palette to itself to implement light levels: https://quakewiki.org/wiki/Quake_palette#Colormap https://quakewiki.org/wiki/Quake_palette#Colormap You now basically have a two step lookup: palette_rgb[colormap[color, light]]
- indy 3y agoMark J. Ferrari was incredible at utilising palette cycling: http://www.effectgames.com/demos/canvascycle/ http://www.effectgames.com/demos/canvascycle/
- chongli 3y agoHe gave one of my favourite GDC talks of all time [1]! I recommend this talk to anyone who is interested in the details and history of working on limited colour palette games! [1] https://youtu.be/aMcJ1Jvtef0 https://youtu.be/aMcJ1Jvtef0
- wilg 3y agoIf you work with LUTs a lot, I work on a Mac app that handles all kinds of advanced color science and conversion tasks: https://videovillage.com/lattice https://videovillage.com/lattice
- KingOfCoders 3y agoBack in the days assemblers (patched Seka) had tools to generate sin wave lookup tables.
- OnlyMortal 3y agoHandy for vector graphics if you include a table for TAN.
- 082349872349872 3y ago"They came to TAN / I taught them how to SIN" (COS my slipstick brings all the girls to the yard): https://img-9gag-fun.9cache.com/photo/a5bbB2r_700bwp.webp https://img-9gag-fun.9cache.com/photo/a5bbB2r_700bwp.webp
- luismedel 3y agoThey are extra useful to precalculate other visual effects. In the past, following a magazine tutorial, I coded a very cheap raytraced "lens effect" on a 286. I recently (5 years ago!) ported it to js [0]. That magazine got me into fractals and raytracing, BTW. [0] https://github.com/luismedel/jslens https://github.com/luismedel/jslens
- pubby 3y agoRetro games used a ton of tables. Back then memory speeds were blazing fast, but processors were sluggish, so it made sense to pack as much computation as possible into tables. The more clever you were about it, the fancier games you could make.
- alpaca128 3y agoNot always, though it might depend on what platform you mean with retro. Kaze Emanuar on YT does a lot of development for the N64 and it feels like half the time he talks about how the memory bus affects all kinds of optimizations. In Mario 64 he replaced the original lookup table for the sine function because an approximation was faster and accurate enough (or rather two approximations for two different purposes). I love that channel, he reworked the entire Mario 64 code [0] to make it run at stable 60FPS...because he wanted his mods to run faster. [0] https://www.youtube.com/watch?v=t_rzYnXEQlE https://www.youtube.com/watch?v=t_rzYnXEQlE
- djmips 3y agoThe speedup from the approximation wasn't that much if anything. He made his real improvements elswhere. But your point stands that memory speed really has moved the goalposts on what is feasible to speed up through using precalculation tables and if you can do it with math then that is often much faster.
- sumtechguy 3y agoBack when I started I thought I would make games. I used a lookup table for cos/sin kept as an integer. I only needed enough precision for rotation on 320x240. It was something like 20-30 cycles faster per pixel. Even more if you didn't have a FP co-processor.
- TacticalCoder 3y agoBy retro platform GP meant Atari ST and Commodore Amiga and the like: LUT were the name of the game for everything back then. Games, intros/cracktros/demos. Heck even sprites movements often weren't done using math but using precomputed tables: storing movements in "pixels per frame". It worked particularly well on some platforms because they had relatively big RAM amounts compared to the slow CPU and RAM access weren't as taxing as today (these CPUs didn't have L1/L2/L3 caches). The N64 is already a more modern machine.
- cromulent 3y agoA Podcast Of Unnecessary Detail just did an episode talking about the SNES Doom port and how it used LUTs for trigonometry as the SNES didn't have a graphics processor. https://festivalofthespokennerd.com/podcast/series-3-episode-4/ https://festivalofthespokennerd.com/podcast/series-3-episode... https://github.com/RandalLinden/DOOM-FX https://github.com/RandalLinden/DOOM-FX
- nicetryguy 3y ago> the SNES didn't have a graphics processor It absolutely did! Even the NES had one. In addition to the (cloned) Motorola 65c816 SNES CPU, the PPU (picture processing unit) was a custom chip that offered several different layouts for spitting out tile based backgrounds and sprites as each scanline physically drew across the CRT TV. It was even capable of fancy things like background rotation and scaling (Mode 7, think Mario Kart) and hardware transparences which you can see in many games. Furthermore, in the case of Doom (and games like Starfox) the cart was baked in with the "Super FX" chip that handled the 3d calculations. So you were actually dealing with two graphics processors for that specific title, heh. Here's a wonderfully (and painfully) detailed series about the SNES hardware by Retro Game Mechanics Explained: https://www.youtube.com/watch?v=57ibhDU2SAI&list=PLHQ0utQyFw5KCcj1ljIhExH_lvGwfn6GV&index=1 https://www.youtube.com/watch?v=57ibhDU2SAI&list=PLHQ0utQyFw...
- zeta0134 3y agoLookup tables are the only reason I was able to get this effect working at all: https://twitter.com/zeta0134/status/1756988843851383181 https://twitter.com/zeta0134/status/1756988843851383181 The clever bit is that it's two lookup tables here: the big one stores the lighting details for a circle with a configurable radius around the player (that's one full lookup table per radius), but the second one is a pseudo-random ordering for the background rows. I only have time to actually update 1/20th of the screen each time the torchlight routine is called, but by randomizing the order a little bit, I can give it a sortof "soft edge" and hide the raster scan that you'd otherwise see. I use a table because the random order is a grab bag (to ensure rows aren't starved of updates) and that bit is too slow to calculate in realtime.
- sourthyme 3y agoThe 1/20 update works well because it gives the illusion of tiles popping into view naturally as the lamp moves. This is a cool effect to get away with.
- ecshafer 3y agoThat looks pretty awesome, and the graphics are way better than any NES game I can remember, it looks more like an SNES level graphics. Since you are running on an emulator there, does the emulator lock you to NES level performance?
- zeta0134 3y agoYes, though full disclaimer, the cartridge is a tiny bit more powerful than your average NES game, and that is definitely contributing. The capabilities of the cartridge I'm using are something like Nintendo's MMC5 (used for Castlevania 3) but with a slightly more useful ExRAM implementation. The main benefit for this effect is that I can write to the nametable outside of vblank, and that helps with the double-buffer setup. The NES CPU isn't fast enough to process all of the enemies at once, so I batch the changes over time, and then present the updated board when the musical beat advances. This should run on real hardware, I'm just waiting on a dev board from my cart supplier before I'll be able to test that properly. Mesen is what I use in the meantime. It is pretty darn accurate, and I haven't overclocked it or cheated any of the console's constraints away.
- lulznews 3y agoTLDR?
- deleted 3y ago[deleted]
- vjfms 3y agoAwesome demonstration!
- hinkley 3y agoIf I had a dollar for every time someone who had 30 seconds of accumulated knowledge about Dynamic Programming tried to argue with me that caching and memoization are the same thing, I'd have enough for a nerf bat to hit them with. (Briefly: memoization is local shared state, caches are global shared state, which is a whole other set of problems. And caching is hoping you'll need something eventually, where as memoization is knowing you will need it immediately.) A couple years ago I watched a very long video on Dynamic Programming and learned a new term: Tabulation. If memoization is encountering a common sub-problem and holding onto it, tabulation is seeking them out, answering the sub-problems before they can come up organically. It's much harder to derive the tabulation answer, but I find it's usually easier to reason about after the fact. Which is enormously helpful when you go back to add new features or fix old bugs. Look-Up Tables are fixed-size tabulations. The space complexity of tabulation is often ≥ O(n), while LUT are a fixed size, but big enough to reduce the computation time by a constant factor, like 10 or 100.
- sakras 3y agoIt sounds like your distinction of tabulation vs memoization is similar to the concept of bottom-up vs top-down DP. Bottom-up: build the table up eagerly, top-down: recurse down and fill in the table lazily.
- hinkley 3y agoYeah I'm not sure how widespread his nomenclature was. I was just glad to have more vocabulary for people who have trivialized the entire discipline down to 'caching'.
- sircastor 3y agoA little while back I got into the NES homebrew scene, and I recall seeing a game, (Bobl) that had incredible water physics - way more than system would have been capable of calculating. It turns out that it was a Lookup table and it really opened my eyes as to what you can accomplish with them and how simple tools can look like very complex processes. https://morphcatgames.itch.io/bobl https://morphcatgames.itch.io/bobl
- Intralexical 3y ago> (Bobl) that had incredible water physics - way more than system would have been capable of calculating. I'm not denying the effect is impressive, but assuming you're referring to the surface ripples/capillary waves, would a 1D cellular automaton be beyond the abilities of the NES to calculate in real time?
- sylefeb 3y agoLookup tables are great to produce impressive graphics effects under strict compute limits. I use them in many FPGA projects. On FPGA there is a balance between limited memory (often BRAM) and limited compute, but they can be used to great effect: Tunnel effect (exactly as user bemmu described below): - see it live: https://htmlpreview.github.io/?https://github.com/sylefeb/gfxcat/blob/main/runtime/gfxcat_tunnel.html https://htmlpreview.github.io/?https://github.com/sylefeb/gf... - lookup table: https://github.com/sylefeb/gfxcat/blob/main/tunnel/tunnel.h https://github.com/sylefeb/gfxcat/blob/main/tunnel/tunnel.h - how it is computed: https://github.com/sylefeb/Silice/blob/master/projects/ice-v/src/pre_tunnel.cc https://github.com/sylefeb/Silice/blob/master/projects/ice-v... Julia fractal, with a table to do integer multiply! (2.a.b = (a+b)^2 - a^2 - b^2, so just precompute all x^2 in a table! ) - see it live: https://htmlpreview.github.io/?https://github.com/sylefeb/gfxcat/blob/main/runtime/gfxcat_julia.html https://htmlpreview.github.io/?https://github.com/sylefeb/gf... - code (see 'sq' table): https://github.com/sylefeb/gfxcat/blob/main/julia/julia.c https://github.com/sylefeb/gfxcat/blob/main/julia/julia.c - credits (mul trick): http://cowlark.com/2018-05-26-bogomandel/index.html http://cowlark.com/2018-05-26-bogomandel/index.html In-hardware lookup division for perspective correct texturing! - doom-chip on-ice (rC3 2021 talk): https://www.youtube.com/watch?v=2ZAIIDXoBis https://www.youtube.com/watch?v=2ZAIIDXoBis - detailed write up: https://github.com/sylefeb/tinygpus?tab=readme-ov-file#precomputing-the-per-pixel-division https://github.com/sylefeb/tinygpus?tab=readme-ov-file#preco... - actual lookup table generation: https://github.com/sylefeb/tinygpus/blob/498be1b803d0950328ae5f0138ce4e97805ca4cb/hardware/GPUs/dmc-1/dmc-1.si#L195 https://github.com/sylefeb/tinygpus/blob/498be1b803d0950328a... Sine tables are also very typical, for animating things on screen or plain trigonometry, for instance my small fixed integer raytracer uses a sine table to animate the spheres (and the cos is easy to get from the sin, especially if the table has a power of two size ;) ): - see it live: https://htmlpreview.github.io/?https://github.com/sylefeb/gfxcat/blob/main/runtime/gfxcat_raytrace.html https://htmlpreview.github.io/?https://github.com/sylefeb/gf... - source code: https://github.com/sylefeb/gfxcat/blob/main/raytrace/raytrace.c https://github.com/sylefeb/gfxcat/blob/main/raytrace/raytrac... And of course procedural textures!! Perlin noise is made of lookup tables, and often multiple lookups are combined to then lookup a clolormap (https://redirect.cs.umbc.edu/~ebert/691/Au00/Notes/procedural.html https://redirect.cs.umbc.edu/~ebert/691/Au00/Notes/procedura...) There are so many other examples. Also, FPGAs are quite literally made of LookUp Tables, or LUTs: - https://github.com/sylefeb/Silice/tree/master/learn-silice#fpga-hardware-design-101 https://github.com/sylefeb/Silice/tree/master/learn-silice#f... - https://github.com/sylefeb/silixel https://github.com/sylefeb/silixel (edit: formatting)
- FrostKiwi 3y agoMany thanks for submitting <3 Author here, in case of any questions.
- fbdab103 3y agoThere was a typo that was melting my brain until I confirmed that this was not some alternate plotting library. "Here is every single colormap that matlibplot supports,..."
- FrostKiwi 3y agoOhh, that's funny. I just realized, I always read it the wrong way around in my brain up until now! Corrected the typo.
- vsuperpower2020 3y agoAll these animated gifs are annoying and distracting, and I can do without the unfunny boomer memes from 2010. It's just annoying to try and read text with all these colorful gifs being spammed.
- johnnyanmac 3y agoMay I suggest reader view as a solution if you use Firefox? But this is a technical topic in a visual concept. I appreciate visualizations and absolutely praise shaders in contexts like these.
- alpaca128 3y agoUsually I'd agree but I can only see embedded videos which respect the disabled autoplay setting. Edit: nevermind, once started it's impossible to pause the videos, they always continue playing after scrolling.
- FrostKiwi 3y agoI was not sure how to handle that. Battery optimization disables the top video element of a muted video once you scroll past it, which stops the WebGL samples from playing. Landing in the middle of the article from another page also prevents the WebGL samples from working with video, which is supposed to illustrate the realtime processing aspect. But unmuted cannot be auto played. I'll rethink how I approach this for my next article. Maybe a pause button under every WebGL sample?
- joegibbs 3y agoThis is brilliant - I've used plenty of LUTs for post-processing but it never occurred to me to use them for recolouring assets as well.
- wsc981 3y agoDoom used a lookup table for random numbers: https://doom.fandom.com/wiki/Pseudorandom_number_generator https://doom.fandom.com/wiki/Pseudorandom_number_generator
- 0cf8612b2e1e 3y agoDoes this mean the engine is fully deterministic?
- unleaded 3y agoYes, if you make the exact same inputs you will get the exact same outcome. Demos and multiplayer rely on this, they just record player inputs, nothing about enemy movement or anything like that. This is also why you can leave a multiplayer game in the middle of a match, but you can't join one in the middle https://www.youtube.com/watch?v=pq3x1Jy8pYM https://www.youtube.com/watch?v=pq3x1Jy8pYM
- bombcar 3y agoYes, and that speed runs can be “seed runs” where you do things to make the right LUT number come up at the right time. The DooM Engine Black Book goes into details. https://fabiensanglard.net/doom_fire_psx/ https://fabiensanglard.net/doom_fire_psx/ also Other games use seeded random number generators to be entirely deterministic even though random; Factorio does this to allow multiplayer without having to sync the entire game state all the time.
- stevenwoo 3y agoThis reminds me, we used a command line tool (originally made for Warcraft 2?) to take full color art assets and find a palette of 200 or so colors (the rest reserved for UI elements and the player characters) for the different areas in Diablo 2, and then remapped all the art assets to these small palettes, and then reuse the monster art with other colors within these palettes for varieties of monsters. I don't remember spending more than a day on putting this in our art pipeline, the guy who wrote the tool did all the hard work.
- 082349872349872 3y agoIf you try to program just about anything non-trivial in sed(1), LUTs are the way to go.
- kragen 3y agoindeed! though you've had more success with that than i have i'd add: or fpgas, or eproms, or m6
- dredmorbius 3y agoI'm both fascinated and horrified to ask what non-trivial sed programming you might be doing, and why ;-)
- 082349872349872 3y agowhat: the most complicated thing (that I've actually used in other projects) was a data-driven precedence-climbing parser (which, since sed is usually lousy at dealing with place-value numerics, required sussing out sed-friendly representations of the core data types). why: because given a "weird machine" that is nearly omnipresent (in the back end, anyway) and is also a Perlis language, who among us would not wish to program it? (and who among us would willingly admit that 1959's https://en.wikipedia.org/wiki/IBM_1620#Model_I https://en.wikipedia.org/wiki/IBM_1620#Model_I programmers had had better code-fu?) I must go down to the sed(1) again, to the pattern space and the hold, And all I ask is a t branch and a s/ub/st/ to map and fold; And the Jolt’s kick and the keys' clack and the write lines breaking, And a green glint in mirror shades, and a grey* dawn waking. * "the color of television, tuned to a dead channel"; no Ἠὼς Ῥοδοδάκτυλος here!