It is extremely important to be able to protect our work from being stolen, and against low effort near reproductions being made and claimed to belong to someone else. The law is not protecting us as it should be, and we are left to fend for ourselves. I agree this is a problem, and this is the problem that data poisoning aims to address. How then could the concept of data poisoners annoy me? Certainly I should be a fan, and even more, perhaps I should use my graphics programming / computer science / research knowledge to help advance the technology?
Absolutely not, and I will tell you why: It makes people believe their work is safe, when it isn’t. That makes it dangerous, and it is not fixable, unfortunately.
For data poisoning to work, there needs to be some mechanism of perception where a machine would fail, but a human would succeed.
Data poisoners work by finding instances of this being true in specific models. That doesn’t protect from other models though, or from future models – and the future goes on for a long while (for better or worse).
Captchas are similarly doomed to ultimately fail, but the difference there is we can keep updating them in an arms race to keep up (essentially captchas being the adversary part of a GAN). With data poisoning, as soon as you need an iteration on the poisoning tool, this is a sign that the previous poisoning is no longer effective against the current models, which means all “protected” data is now unprotected.
If we want lasting protection, we need to find some perceptual mechanism that a human has but a machine does not have, and could never have. We can think about where something like that could come from. Anything that is biology based, chemistry based, or physics based can essentially be done by a machine.
Beyond that only lies concepts like the soul and free will. These things are untestable, and thus have no actual effect that us engineers can exploit to separate humans from nonhumans, or biology from machines. This is why I say the problem is ultimately unfixable.
Yeah sure, we can try to make things have prohibitive cost or difficulty to deal with – this is the age old battle in security after all – but even if we get that, the real problem is that poisoned data is not universally poisoned and does not stay poisoned. That is a shame, but that’s reality.
Also, here’s a paper on arxiv about the weaknesses of a specific type of data poisoning, even for models it was meant to poison. https://arxiv.org/abs/2406.12027
UPDATE 10/26
I’ve had a few comments from people that they use poisoning not to protect their work, but to instead hope that their work causes some damage to the training process which tries to consume it. Effective or not, this seems like a noble goal. This may have reversed my opinion on poisoning, I’ll have to think it over for a while!
While it doesn’t solve all the needs I called out in my original blog post, it solves many of them, and features can be added by myself or others at time goes on. I made it with the features that I needed for my current personal game project, but also spent the extra effort needed to make it usable by others. “I’m not just the president, I’m also a client”.
This blog post shows some of the technical decisions I made and why I made them. In particular, I like the solution I came up with for serializing static vs dynamic sized data, so we are going to start with that.
Serializing Fixed Sized Data vs Variable Sized Data.
If you have an array of objects, where the object type only contains simple data types and no pointers, writing them to a binary file is pretty easy: you write how many there are (as a uint32 perhaps) and then you write each object, one after the other.
When you read this data later, you can read the count, and then getting to each object is a easy calculation. The offset is index * sizeof(object). If you keep the file contents in memory, you can make a pointer of type object* to that location in memory and index it like a normal array.
That would be the end of the discussion if we were only dealing with fixed size data. That is almost every data type a person could ask for except for variable sized arrays, and strings which can be thought of as variable sized arrays of characters. These exceptions are important so we have to increase the complexity a bit.
One way to deal with dynamic sized objects would be to write the size of each object before the object. Unfortunately, if we wanted to get to a specific object by index, we would need to scan through the entire list of objects until we got to the one we wanted.
We lose the ability to just index into an array and get any object in O(1) time. Constant time access is really important for performance so let’s find a way to bring it back.
Variable Sized Data
A common way to deal with strings is instead of writing the whole string as part of an object, you put the string somewhere else in the file (like, at the end) and write the offset of where that string is as part of the object.
That makes an object with a string be a fixed size. This is also how strings work in memory: your object has a char* in it, but the actual string itself lives somewhere else. The size of an object containing a string doesn’t grow as the string grows.
When loading binary data that includes a string, you can use the offset to get the actual string itself. If you loaded your entire binary file into memory, you can add the starting memory address to the string offset to get an actual pointer to the string. This “pointer fixup” is a common thing in binary serialization, and is really nice for efficiently loading and using binary data files.
With strings solved, we can do the same for variable sized arrays. Instead of writing a variable sized array out as part of an object, we instead write the variable sized array data somewhere else in the file, and just write the item count and offset to the dynamic array as part of the object. Once again this is how variable sized arrays work in memory. Your object has a T* in it, but the actual data itself lives somewhere else. String length is determined by a null character, so strings don’t need to serialize the size, but dynamic arrays are not null terminated, so they do need a size serialized.
You can do the same pointer fixup on load to turn the dynamic array offset back into an actual pointer.
One way to implement this separation of fixed sized and dynamic sized data could be to have two std::vector<char>’s. The first one is where fixed sized data is written to, and the second one is where dynamic data is written to.
While you are filling out the binary data, you don’t know the offset of where a specific string is going to live in the file, since that offset is going to be the size of the entire fixed size data, plus the string’s offset in the dynamic sized data.
A way to deal with this is to defer writing the actual dynamic data offset until you are done making all the binary data. I do this by keeping a table where each entry has two numbers: The location of the offset in the fixed size data, and the dynamic data offset to be written there. After you are done making the binary data, you can loop through this table and write all the necessary offsets into the fixed data, pointing at the dynamic data. The dynamic data offset just has the static data size added to it, to make the offset to write into the static data area.
Fractal Complexity Tamed With A Data Stack
This sounds great, but what happens if we have a variable sized array of an object that includes strings? If you are in the middle of writing a dynamic array of objects into the dynamic data, and then you hit the string, you can’t write the string in the middle of the dynamic object. We’ll lose our ability to random access our dynamic array objects by index if they are different sizes. We hit the same problem again!
The solution I came up with was to generalize the solution from the previous section. Instead of having only two vectors where one is for fixed sized data and the other is for variable sized data, the strategy changes a bit. There is a stack of vectors that is arbitrarily deep. Whenever you are writing fixed size data, you write it to the current data stack index. When you write variable sized data, you write it to the data stack index + 1, and write the offset to it at data stack index.
At every level of the stack, there is fixed data which has O(1) random access by index, but it can support arbitrarily nested fixed and dynamic sized data.
To actually set the offsets, we keep a table like we did in the last section. Instead of only storing the fixed sized data location, and the dynamic sized data location it wants an offset to, it instead stores the stack index and offset of where it wants an offset written, and it stores the stack index and offset that it wants to get the offset of.
After all the data stacks have been written, it’s trivial to calculate and write the offsets, then dump the data to disk.
Null Pointers
When writing offsets, the offset of “stack 0, offset 0” has a special meaning. It calculates to a file offset of 0, and when the binary data file is read in, file offsets of 0 are translated into null pointers (left alone as null pointers), instead of having the base address added to them. The fourcc is at offset 0 in the file, and no data has a valid reason for pointing at it.
The ability to have offsets which translate to null pointers means that you can have optional data fields, which is a nice feature to have, and comes without too much effort or complexity.
With fixed / dynamic sized binary serialization solved, let’s talk about some of the other things.
Basic Functionality of df_game_data
In df_game data, you:
Describe a schema in a .def file using C/C++ style type definitions for structs, unions and enums.
Make and edit data records of the root data type you specified.
Compile the data to generate a .bin file, and also a .h file which is a “header only library” which loads the .bin file. Currently you can choose C or C++ for the language of the generated header.
Before writing my own schema language and binary serialization / deserialization, I looked into a couple different existing technologies like protobuffers and flatbuffers. Flatbuffers were very close to what I needed, but I felt chafed by what I felt were strange limitations – like dynamic arrays only being allowed to be in tables, and static arrays only being allowed to be in structs. I was nearly at the finish line when I made the call to take out flatbuffers and roll my own. I’m a lot happier with the result, so no regrets.
The Data Model
Whether we are talking about loading a .dbroot file in the editor, or loading a binary file off disk, the conceptual root object of the data is “The Database”.
The database is made up of one or more tables.
A table contains an array of named entries, where each entry in a table is the same struct type.
union – a data type that allows a field to be one of a specific list of types. Can be null (none of the fields).
link – a link to a table entry. Can be null.
Each struct field can also be a static or dynamic sized array of any of the above.
No special rules about what can go in what.
Loading The .bin Binary Data File
The file format has 4 main sections:
Fourcc
Version
Schema Hash
Data
Fourcc
The first four bytes in the file are a fourcc (four character code) “DFGD”. This is used to identify that the file type is a valid file, but also because if we read that in as a uint32 and it comes in backwards as “DGFD”, we know that means we need to do endian swapping.
Some machines store bytes of multi byte types in different order than others. The machine you are using is likely little endian, and modern consoles are as well, but some machines are big endian. The code doesn’t need to know if it’s running on a big endian machine or a little endian machine – it just needs to know if it’s the opposite endian. If so, it needs to reverse the byte order in multi byte types. This used to be a bigger topic in game dev than it is now.
Note there is also a cursed middle endian, but we’re ignoring that for now.
Version
The version is written as 3 bytes: Major.Minor.Patch.
The version doesn’t currently do anything, but in every piece of software that works with custom file formats, a day will come when you need to do special logic based on version number. It’s there in the file, ready to be used when it’s needed.
Schema Hash
After the fourcc is a uint64 hash which is a hash of the schema. The generated header file checks that this hash matches what it expects. If it doesn’t match, it won’t load the data and will return failure.
It would have been easy to hash the .def file (and any file it includes, recursively) for this hash, but a kindness I made for myself and other users was that it hashes the in memory representation of the schema instead. This way, if you add comments to the .def file or similar, it won’t invalidate / update the .bin and .h files you already have generated. This also lets me exclude field default values from the hash, since those don’t affect either the .bin file or the generated .h file. Default values are essentially an editor only feature.
Some compilation settings are also included in that hash though. You can opt into or out of various features, such as hot reloading, or being able to look up records by name, or whether the data is obfuscated. The features that affect the contents of the .h or .bin are included in the hash.
Data
After that comes the data. The data on disk is the same size / layout as the data in memory once loaded, but all pointers are uint64_t offsets into the file. They are written as uint64s because when running a 64 bit program, pointers are 64 bits in size. When running a 32 bit program, they are 32 bits in size, and they can just ignore the top 32 bits. Writing 64 bits allows us to have space for either a 32 or 64 bit pointer, depending on what flavor the loading program is running in. In the generated loading code, I make unions between the correct pointer type, and a uint64 to be able to enforce type safety of pointer types, while also making sure there is room for 64 bit pointers in the serialized data.
A pass is done through all the data fields recursively to first do endian swapping if needed, and then do pointer fixup.
Endian swapping is just reversing the order of bytes in multi byte data types like I said before.
Pointer fixup is converting the uint64 file offsets into pointers in memory. This is done by knowing the address of where the file data start in memory, and adding that to each offset. An offset of 0 is left at 0 though, so we can have null pointers.
Data Record Objects And Hot Reloading (C++)
When you get a record from a table in the database, it gives back a “Record” object, which internally stores a pointer to where that data lives. You can call .Get() on the record object to get a const reference to the object. The type is templated to know what struct type to give back.
If you have a record object which doesn’t point at a valid record, calling .Get() gives you a const reference to a default constructed static object of that type. You can also call .Valid() to see if a record is valid. A record is just a thin wrapper around a single pointer though, so it’s very light weight and fast to interact with.
When hot reloading support is on, it makes record objects a bit heavier weight by adding a dynamic allocation to store the name of the record they point at, a pointer to the database they are from, and an integer specifying what generation of database they are from.
If the database does hot reloading, it increments a generation integer. When you call .Get() on a record, the record will compare the generation integer it has versus the generation integer of the database. If they don’t match, the record will look up its record again in the database using the name it stored. If it can’t find that record, it becomes an invalid record.
So, when hot reloading support is on, record objects get heavier weight.
Calling Tick() on the database will cause it to look at the .bin file on disk and see if the modification time stamp has changed. If it has changed, it reloads the file and increments the generation integer.
Hot Reloading (C)
In C, hot reloading works differently. You still call a Tick() function which reloads the file when needed, and returns true when it does, but there are no concepts of records in the generated C code.
In C, when Tick() returns true, that is your notification that you need to update any data you have cached off from the database, if any.
Compilation Settings & Multiple Compilation Target Support
Different games have different needs, so there are few compilation options you can set.
The main ones right now are:
Record lookup by name support
Hot reloading support
Obfuscation
Looking up records by name can be useful (It uses a binary search), but it also means that the record names are plain text in the file, pointing at where the data for that record is. It makes it easier for players to edit data files. Turning this feature off makes those names not be emitted, and it makes the header file not have the ability to look up records by name.
Hot reloading support is useful if you want to do hot reloading, but it requires the record lookup by name to be on, and it also makes Record heavier weight like we talked about in the last section.
Because of this, it may be that a game wants to build a debug version of the data and header file which has hot reloading support on, but also a release version which has hot reloading and name lookup turned off. The editor lets you specify multiple compilation settings, and every time you compile data, it will compile all targets.
Obfuscation is an anti cheat option that was developed in part by Manoj MJ, who identified the need in the utility. When obfuscation is on, a pseudo random number generator will generate the same number of bytes as your data, and xor the data against it. This is a simple non cryptographic stream cipher. This feature just makes it a bit harder for people to read or modify the game data while it is on disk. Once it is deobfuscated in memory, they have full read/write access to it though.
Record lookup by name support can be useful, but you can do just fine without it too.
A common approach to this is to have one data table be a “singleton” with only one entry, and have this be the “configuration” object which points at the root of the most interesting objects. From there, you follow the links outwards to find the data you want.
For instance, in an RTS game, the singleton may have an array of links to building types, and each building type internally has an array of links to requirements for unlocking the building. If there is a special building, such as “What is the building that when destroyed means game over?”, you can make a singular link there in the settings that points at that building.
No need for magic strings (or indices, or hashes of names) there in the code. It all goes through data, starting from the singleton settings object.
Some games rely heavily on looking up data records by name though. In these situations, instead of doing a binary search in a sorted array of strings, these strings are either mapped to unique IDs for faster lookups, or they are hashed. A fun alternative is to use “minimal perfect hashing”, where you start with a known list of strings, and get a hash function that will turn those N strings into unique integers [0, N). If that need comes up, that would be a fun feature to add.
Enums, Links, Unions
All enums are serialized and defined as uint16s. Many enums could instead be serialized and defined as uint8s when they have 256 items or less. A future version may use “the smallest unsigned int needed to represent the enum” but for now they are all just uint16.
Links (Link<T> types) allow you to link to entries in tables. In the data, they become pointers to whatever entry you’ve linked to. If no link is specified in the source data, these become null pointers in the loaded data.
Unions work similarly to links. In C++, a union uses as much memory as it’s largest field. In fb_game data, we know at data compile time what type is used, and since the data is read only, we know that the type can’t change. So, we store an enum (uint16) for which field is the active field, and we store a pointer to the actual value, in dynamic memory, which is only as big as actually needed. Unions can also be null, so when a union is “none”, there would just be a null pointer in static memory, and nothing in dynamic memory.
Anti Cheat
When a game is running on a player’s computer, the game’s code has to be able to load that data. The player has full control over their own machine, and can read/write values in memory, and can even look at the machine code / assembly / disassembled C++ of the game to see what it’s doing. This means we can’t actually protect the data from reading and writing beyond cursory protection.
It would be easy to say the problem is that df_game_data is open sourced, but that isn’t the problem. Every game faces this issue and the only thing we can do is try to make it more effort than is worth while.
Right now the only things we have in the realm of “anti cheat” are:
The file needs to begin with the fourcc “DFGD” (or the endian swapped “DGFD”).
The next uint64 schema hash needs to be the expected value found in the header file.
You can opt out of having record names in the bin file, which could help a person understand what data was where in the file.
You can obfuscate the data on disk, which XORs it against a PRNG one time pad. (Added in part by Manoj MJ).
Aside from that, there is no validation that the data hasn’t been tampered with, and there is no attempt to obfuscate the game data.
However, more features can be added!
An option to compress the bin file could be added. This compression should happen before obfuscation if they are both on, since the one time pad obfuscation should turn the file into incompressible white noise. The main point of compression isn’t for obfuscation, it’s for reducing file size, but it would have a secondary benefit of obfuscating the data a bit more.
There could be a hash of the contents of the file after the schema hash field. When loading the file, this hash could be performed and compared to the contents hash stored in the file itself. If they don’t match, refuse to load the file. This would help protect the bin files from being written to while on disk. But again, it doesn’t protect them from being written to once they are in memory.
Any other ideas? File an issue, or better yet a pull request!
df_game_data Vs. a Real Game Engine
I’ve worked on a lot of games, most using custom engines, such as Starcraft 2, Heroes of the Storm, and Diablo 4.
Having game data solutions is very common, and there is a lot of variety in how they function.
I designed df_game_data to be standalone, low drama (easy to use, stays out of your way), and useful not only for myself, but for others as well.
Normally though, game data solutions are deeply integrated into the game, and not a modular component. For instance, in the Starcraft 2 engine, there were serialization functions for all serializable object types, and they would be called to save data to disk, to load data from disk, to send and recieve data over the network, to hash data, and probably some other things as well.
df_game_data is meant to be a standalone solution which has no knowledge of your game. This changes some things about it, but not in any real meaningful way IMO.
You may have to write your own serialization routines if you want to re-use structures for network messages or similar, but you could also add a feature to df_game_data which called a provided templated lambda on each data field in a struct, recursively.
In short, this is basically how game data systems work in most games, if you squint a bit.
Other Misc Things
When reading binary files into structs, you have to be careful of automatic struct padding. By default, padding will be added between fields to make them line up at a multiple of their size. A struct will also be padded to be a multiple of the largest sized member. See the struct definition below to see how a struct that looks like it should be 6 bites big is actually 12 bytes:
structMyStruct
{
chara; // 1 byte
//char padding[3]; // 3 bytes of invisible padding so that b can start on a 4 byte boundary
intb; // 4 bytes
charc; // 1 byte
//char padding[3]; // 3 more bytes of invisible padding so the struct size is a multiple of the largest size: 4
};
A way to get around the padding is to put #pragma pack(push, 1) before the struct, and #pragma pack(pop) after the struct to force packing to be 1 byte aligned, and thus add no padding.
You might be wondering how the loading headers are generated. I’m not doing anything very fancy, it’s just string replacement. If you look at the file output_cpp.h you can find the template for the c++ code generation. https://github.com/Atrix256/df_game_data/blob/main/loader/output_cpp_h.h.
In that file are tokens such as /*$Dtor$*/ which is where the object destruction logic goes, and /*$ClassName$*/ which is where the name of the class goes. The code generator generates strings to go where these tokens are, and it just does a find and replace to do that.
Adding backwards/forward compatibility of the data files could be nice to add. That and some other nice to have features are filed as issues in the repo.
Lastly, there is automated testing. I made the examples double as automated tests. A batch file runs each example and ensures that it exits with a code of 0. I have a batch file to run all tests and report the results. I also have a yaml file which makes github run that batch file, and requires it to return 0, for the build (& PRs) to be considered good.
This post has been a bit of a shotgun blast of binary serialization topics, but hopefully you found it useful!
First up, who the heck am *I* to have an opinion on this?
Well, I am a computer scientist specializing in deterministic sequences used in randomized algorithms.
Read my peer reviewed published papers on blue noise, read my blog posts on irrational numbers and the benefit of using them as pseudorandom number sources, read what I’ve written about using light weight cryptography to shuffle and group objects in constant time, with random access and inverse lookups using the Chinese remainder theorem. Watch my YouTube videos of the same. I find these things fascinating, so if you are interested, here are some of my favorites:
Ok so i know about determinism, but do I know about AI and ML? I stick to the bare metal of ML and don’t like to go into the highly abstracted levels that most modern ML people do, but yes. I know backprop, dual numbers (forward mode AD), ADAM, and other random things. During the AI winter, I kept myself warm implementing neural networks in excel (when I wasn’t working on game dev).
I also have an ML patent (pending) I won’t describe here, that is pretty interesting. Unfortunately, I fear it would help something like terminator’s skynet to exist. I tried to park the patent at a game company, thinking that would be safe, but now the American Fascist Party’s very own Jared Kushner and the Saudi prince who ordered the murder and dismemberment of Jamal Khashoggi own EA, and my patent, so RIP to humanity i guess.
Funny thing – a core feature of that patent is deterministic ML.
So yes, I do lift, bro.
The Determinism Argument
Ok so it annoys me that people complain that LLMs aren’t deterministic. I am annoyed because it isn’t that they want it to be deterministic, it’s that they want it to be RIGHT, and they don’t even realize it.
Let’s look at a 2×2 permutation matrix.
Considering each square, “When asked the same question multiple times”… :
#1 – it gives random answers and is wrong.
#2 – It gives the same answer every time and is wrong.
#3 – It gives random answers, but they are correct.
#4 – It gives the same answer every time, and is correct.
The argument that determinism is the problem with LLMs says that you want option #2 or #4 and are fine with either. You are saying “I don’t care if it’s right, I just want it to do the same thing every time”. If you are thinking this, good job: you are now breathing manually. (Note this feeling: This is what it feels like to be wrong. Do you feel it often?)
What people really want is #3 and #4. They don’t care if it’s random or not, they just want it to be CORRECT.
Any “random variation” within being correct doesn’t make it any less correct. If it did, you wouldn’t consider it correct, and it wouldn’t be part of box #3.
Yes i even am talking about LLMs generating code or executing some set of steps that a python script is probably better suited to. If you are in box #4, you are 100% happy. If you are in box #3, you are still fully happy because what it is doing is CORRECT. If you say “yeah but i need zero variation in the code generation or the utility execution”, ok so that’s part of your definition of CORRECT and you get that. If you don’t get what you consider correct, it is in a different box.
Another Way of Looking At It
You can run an LLM deterministically – both during training, and during inference. Set the seed of all pseudorandom number generators used, make sure nothing runs on CPU or GPU threads in a way that is non deterministic. This is fully possible and not even a big stretch. If you only know vibe coding you might think this is magic, but unfortunately it’s mundane as heck.
Would that make you happy? Of course not. It puts you into box 2 or 4 for every question you ask, but you don’t get to choose which box you end up in. The only variation in the network output comes from your input.
(Oh no, did i forget rounding modes? Go learn how an RTS works before you have an opinion about the feasibility of program determinism across different machines and compilers.)
Yet Another Way of Looking At It
I can hear you saying it:
“But bro – you are mixing up terms. The network represents a distribution in high dimensional space and the output is a single sample. You taking one sample using a a single pseudorandom value as input doesn’t make it deterministic.”
Bro, you are so correct.
Think about square number 3 in my lovely MS Paint ™ diagram. It gives random but correct answers when asked the same question repeatedly. How is that possible? BECAUSE IT’S A PROBABILITY DISTRIBUTION WITH WIDER SUPPORT.
Square #4 has a ~dirac delta as a distribution. That is the only difference.
Yes, I know it’s a distribution, so what.
Yet Another Way of Looking At It
There’s a debate about whether the universe is deterministic or not.
As best as we can tell, it is absolutely deterministic, except perhaps at the quantum level, which somehow seems to get laundered into determinism at large scales. Maybe through the central limit theorem, for all we know.
If that’s true, it is deterministic already so you can relax. Everything is exactly as you say you want it to be. Still not happy? THAT’S BECAUSE YOU DON’T CARE ABOUT DETERMINISM, YOU WANT IT TO BE RIGHT.
Also, maybe take a couple steps back from the kool-aid bowl. That stuff is bad for your health.
When programming high performance applications, such as video games, you learn neat tricks for writing fast code that makes the most of limited resources.
Memory allocation is a huge topic for performance critical code that needs a variable amount of memory.
When you hear “stack allocator” you might think of “alloca” which lets you allocate memory from the actual program stack. That is super useful in a pinch, but that is not what today’s post is about. Another name for the type of stack allocator we are talking about today is “bump allocator”.
The Stack Allocator
Around 2010 I was working at Surreal Software (Midway Seattle) on an open world game “This is Vegas” which unfortunately was cancelled when Midway went out of business.
On that project, one of my duties was animation programming. Animation worked by having a state machine for sets of bones, where each state was a tree of animation blends. When states changed, they would blend out from the old state into the new state to preserve continuity.
There was a lot of blending going on, and it used a large number of dynamic memory allocations for these animations to be evaluated and blended on the CPU. These allocations were all transient though and only needed to exist for part of the frame. Furthermore, these allocations had to happen per frame, as things could change drastically from one frame to the next, as to which characters were being animated that frame – based on the camera frustum for example. The allocator showed up as a hot spot in profiling this section of code.
To solve this problem, we implemented a “stack allocator” where allocation is just an integer add, and deallocation is even cheaper.
To do this, you allocate and keep some amount of memory that is the maximum amount you will need, like say 1MB. This is your stack. You also keep an integer “tos” variable to know where the top of the stack is.
When you want to allocate memory, your memory is the memory at the top of the stack, and you add the number of bytes you want to allocate to the tos variable so that the next allocation comes after yours:
In a real implementation, you would also want to know how big the memory was, so that you could handle the tos hitting the end of the memory – by returning null, or asserting, or something else.
When you are done with the memory, you just set the tos variable to 0.
tos = 0; // deallocate all stack allocations
In our case, we set the tos to 0 after animation blending was finished and we had copied the results into the buffers that were heading to the vertex shader for skinning. If you were using a stack allocator more generally for all transient memory allocations during a game’s frame, you may set it back to 0 when the frame starts.
The result was night and day. Allocation no longer took any measurable time in the profiler, because allocation was an integer addition, and freeing all memory was a single integer assigment. It doesn’t get faster than that.
One thing to note is that as written, this allocator does not call destructors or destructors. Using placement new for constructors would be easy enough. Calling destructors would be harder, as it would have to be a manual process, which is error prone. You might be able to use some RAII pattern, but stack allocators work best for simpler types.
Another great thing about stack allocators is that they can work in multi threaded environments. If the tos variable uses atomic addition, multiple threads can allocate from the same stack allocator. This can be nice in a fork/join situation on the CPU, or for a complex algorithm running on the GPU.
You can also do “partial deallocations” with stack allocators. For instance, if you had some recursive process where each level needed dynamic allocation, you could remember where the tos was when that level started, and set it back to that value when that level of processing finished.
The Double Headed Stack Allocator
A few years later, I found myself at Blizzard on the StarCraft 2 team. My boss James Anhalt was (and still is) a really smart dude who introduced me to shader toy, and shared a bunch of really cool techniques that have been previous blog posts. He told me about double headed stack allocators as a solution to a memory fragmentation problem he had hit in the past.
Imagine that you had a streaming world game where as the player ran around the world, old level geometry would deallocate, and new level geometry would allocate and stream in from disk.
At the same time, imagine the player character could shape shift into different forms – and each time they changed forms, the old form was deallocated, and the new form was allocated and streamed in from disk.
A challenge is, when you have these two systems allocating and deallocating random amounts of memory, on their own timelines, your memory is going to get fragmented.
Lets walk through a simple example. Let’s say you have 100 MB total memory for the level (red) and the character (green). The level allocates 20MB, then the character allocates 30MB, then the level allocates 20MB and the character allocates the final 30MB.
Level data (red) allocations interleaved with character allocations (green).
Now let’s say that the player runs to a new section, so the old level data memory is freed. The new level data only needs to make a single 30MB allocation. We do have 40MB memory free, but it isn’t in one chunk! We only have two blocks of 20MB. So even though the new level data is smaller, we can’t allocate space for it. This is memory fragmentation, and it’s a big problem in memory constrained environments.
Level data freed, leaving only character allocations. No room for a 30MB (3 block) allocation for new level data, despite having 40MB free!
So, James told me what they did in this type of situation was to have a chunk of memory like a normal stack allocator, but the level data had a tos which grew upwards from 0, and the character data had a tos which grew downward from the end of the memory. You knew you were out of memory when they crossed over each other and the level tos was greater than the character tos.
Let’s see how that works:
Level data (red) allocations and character allocations (green).Level data freed, leaving only character allocations.Level data is able to allocate the 30MB it needs by keeping a separate stack allocator in the same memory block. No memory fragmentation.
This made it so when the level data needed to change, it could reset the level tos back to 0, and reallocate the memory it needed, without any fragmentation whatsoever. Similarly, when the character freed its memory, it would reset its tos back to the end of memory, and could then reallocate the memory it needed, also without any fragmentation.
Once again, these allocators work fine in multithreaded environments, even when each thread might allocate from either side. Atomic add to the tos indices is all you need.
You might ask “why not have two stack allocators instead of a double headed one?” The main benefit is when you are memory constrained and know that the size of one stack allocator is enough to serve two systems, but the proportion of memory that goes to one side vs the other is flexible. In a game situation like described above, that means some levels could use more memory, but in those situations, the character would need to have reduced memory usage. A bit of a contrived example but hopefully you get what I mean.
Storing Variable Sized Objects In A Finite Region
There is a variation of this when you are trying to store a number of variable sized objects in a fixed amount of memory, but you want random access by index. An example may be that you want to send network packets of a specific size for efficiency reason, and you want to that memory to encode a variable number of variable sized network commands in it. You want to be able to easily iterate through the messages, but you want to support them having variable sizes too.
What you do is have a double headed stack allocator where one stack is for the dynamic allocations, and the other stack is for an array of integers that are an offset in the memory to the dynamic allocations.
Let me show you what I mean with an example. Starting with an empty double headed stack allocator:
You want to allocate 24 bytes. Stack 0 has a tos of 0, so that is where you write your 24 byte object. You add 24 to stack 0’s tos and it is now 24, where the next free region of memory is. You also allocate an integer from stack 1 and write 0 there, as the offset for where this first item lives.
Next you want to allocate 14 bytes. Stack 0 has a tos of 24, so that is where you write your 12 byte object. You add 12 to stack 0’s tos and it is now 38. You also allocate an integer from stack 1 and write 24 there, as the offset for where this second item lives.
and so on…
you also have to somehow keep track of how many objects there are. You could have a separate integer keeping count of how many offsets there are in the offset table, or maybe you could have a sentinel value in the offset table to indicate where the end of the offsets are. Perhaps ~0 (all 1s in binary) could be the sentinel value.
Just like the other stack allocators we talked about, this one can also work in a multi threaded environment. You might be tempted to make the two updates transactional – like with a compare and swap loop – but it isn’t needed.
Lastly, this configuration allows you to remove items, or move them around in memory, which is another way of reducing fragmentation – you just need to update the offset table to match reality when you do so.
I get asked fairly often what people need to know to be hireable as a graphics programmer. I figured it was time to make a page to link instead of re-typing it each time.
We are in a strange time with LLMs. I think ML as it is right now won’t live up to the hype, and the pendulum will swing away from ML a bit over the next couple years. I think the grifters will move onto quantum computing next or find some other thing to pump and dump. However, ML itself does have a place in the computer science tool box, so learning about the fitting and optimization techniques it offers is valuable IMO. I made a video you can watch to learn about the bare metal bits, but it’s up to you if you think it’s worth while to learn or not.
Learning the CPU side – Learning DirectX12, Vulkan, Metal, or similar modern “explicit” APIs and the engine programming to support loading assets and other supporting tasks.
Learning the GPU side – the mathematics of modern lighting and shading, rendering techniques like shadows, ambient occlusion, and post processing effects. Also understanding what is fast and what is slow on the GPU, to know how to make things that run better in real time.
It’s very difficult to learn both things at once. If you want to focus on #2, then you could use a simpler thing for #1, such as opengl, webgl, DirectX11, an engine, or similar. If you want to focus on #1, you should work until you get a first triangle up on the screen, then get a mesh on screen, and so on, but don’t worry about it being very pretty.
Part of #2 is writing a path tracer. Path tracing is how movies do rendering, and it is what we try to approximate with modern real time rendering techniques. A great place to start with a path tracer is this free book online “Ray Tracing in One Weekend”. A lot of people have used it. It’s really approachable and shows you how to make photo realistic renderings. https://raytracing.github.io/books/RayTracingInOneWeekend.html
Another part of #2 is learning “Physically based rendering” or PBR, which is a way of applying lighting (mainly specular, when it comes down to it). PBR is “principled,” meaning if you stick to the rules, you get good results. Before PBR, people wrote random equations for lighting with all sorts of random tweaks and hacks. It made it so you could make an asset that looked good in one situation, but changing the lighting would make it look too dark or would look like it was glowing. People had to make different versions of the assets for different lighting conditions, which was a lot of time and effort.
PBR lets your assets look better in all lighting conditions by default, and saves the time and effort of having to make different versions. It was a big win for our industry. Even so, asset creation time, money and effort is still a big bottleneck in game development.
If at some point you outgrow that and want to go deeper, reading the Filament documentation is a good next step. lots of calculus and statistics as you go deeper into PBR: https://google.github.io/filament/Filament.md.html
Beyond that is the famous PBRT book “Physically Based Rendering: From Theory To Implementation” which is also free online: https://pbrt.org/
Ideally you’ll end up with some source code you can share with prospective employers (like on github, linked to on your resume) to show as proof that you know these things. Something like:
Something that looks vaguely like an engine in that it loads assets (models, textures) and renders them on the screen in real time, with lighting and a couple effects (shadows, depth of field, area lights, tone mapping, ray traced shadows, whatever). Preferably lit using PBR, with a user controllable camera, and is written using DX12, vulkan or similar, and in C++.
A path tracer that generates a photo realistic image. Preferably in C++, but it could be a program without a window that just writes a png as output, it doesn’t have to be real time.
Bonus points if the path tracer is just a separate mode of your “engine-like renderer” and you use it to help verify that your real time PBR rendering is correct, by showing that it matches path traced results. Extra bonus points if you point out where the two renderings don’t match, you can explain why they don’t match, and have thoughts on what you could implement in your real time renderer to make them match more closely while still staying real time.
You might wonder what math you need to know. If you do the above items, you will encounter the math you need to know but basically linear algebra (matrix multiplication, cross product, dot product), basic trigonometry, and a little bit of calculus is really all you NEED. The fun thing about graphics (and game development in general), is that while the amount of math you need is fairly minimal, the amount of math you can use is essentially unbounded.
The same is true algorithmically. You should know the basic abstract data types and algorithms such as linked lists, hash tables, sorting and searching. Often times, the fastest algorithms are the simplest. An array is far faster than a linked list. However, knowing more advanced algorithmic concepts can help you when you really do need something novel and custom.
In game development, C++ is the language to learn. Some people use rust, and it’s hard to tell if rust use is growing or not, but it does have a slice of the pie, while not being the standard language that people expect you to know. WebGPU has a lot of capabilities that WebGL did not have, and it’s becoming more of a serious platform, which lets you work in javascript to do the CPU side of the work. I haven’t seen a lot of WebGPU jobs posted though, and I don’t see a lot of WebGPU content on the web. Knowing C++ seems to be the thing to learn, by far, for CPU side programming.
For shader languages, hlsl seems most common, but some people work in glsl. The shaders are often transpiled to other shader languages in multi platform games.
You might wonder if you have to be good at art to be a graphics programmer. Luckily not. You’ll be collaborating with artists who are good at art, as well as technical artists, who sit between programmers and artists and help bridge the gap in understanding between the two disciplines. That said, if you do know something about art, or photography, or similar, it does help. Not required, though.
I’ll keep this page updated as things change or as people ask questions not covered here.
Extended ML Commentary Regarding Agents: I don’t believe current ML technology is “up to task” for most of the things they are selling it’s use on. I do get use out of it by talking to Claude about math, papers, or unfamiliar algorithms. It’s easy to see if it’s making things up or not in those situations, and it’s easy to check other sources for sanity checks. I do not find it very useful for programming however because even when it does what it’s supposed to do, I don’t understand the code without taking the time to understand it. At that point, I should have just written it. There are some smaller things I find useful, such as “do you see any bugs in this file?” which either returns yes and i can investigate, or returns no, and it cost me nothing to ask. These technical things aside, I do believe that at some point humanity will figure out how to make actual human level artificial intelligence and then go beyond that. I don’t know if that will happen in my lifetime, but I do believe it will happen some day, unless we destroy ourselves first. In that way, this age of LLMs is sort of like a dress rehearsal for when “the real stuff” comes later on. I hope we learn the right lessons and are more prepared when it comes.
My name is Alan Wolfe, and I’m a game and engine programmer with over 25 years of experience. I’m also a graphics researcher with patents, published papers, book chapters, and conference presentations. Lastly, I am the creator of the open-source rapid graphics R&D platform, Gigi (https://github.com/electronicarts/gigi), which demonstrates the future of real time render pipelines by enabling graphics programming at the speed of thought.
I’m currently exploring new opportunities and looking for the following roles:
A Game or Game Engine Team – making a specific title. (Gameplay, engine, graphics, … )
A Shared Engine Team – supporting multiple titles or commercial customers.
Game Dev or Graphics Research – or research in similar topics.
Continuing Gigi Development – towards aligned business goals.
Related Technology – working on technology that enables game development or graphics practitioners.
The ideal position is remote, as I’m not looking to relocate, but Orange County, CA roles could work as well. My resume is at https://demofox.org/Resume.pdf
I am motivated by:
The creativity of making games, and the technical challenges that come with making them work.
Searching for creative solutions to unsolved problems and pushing forward human knowledge, while also sharing rarely known but useful bits of knowledge with others and helping them understand and apply it.
Enabling others to achieve more with less time and effort.
The three sections below go into the details of each area of specialty.
Game, Engine & Real Time Rendering Programmer
I originally started programming to turn creative writing into interactive experiences, but found game development itself to be a very wide and deep field, with many wide and deep sub-fields. Over the years I’ve been a generalist, and have also been a specialist in several areas. The fields I’ve specialized in are:
Rendering – I was one of two rendering engineers while on Diablo 4, I did some graphics work on Starcraft 2 and Heroes of the Storm. At Blizzard I was tasked with making a rendering solution for a company wide shared engine which could support any game genre on any platform. That led to Gigi. While at NVIDIA, I made the RTXGI UE plugin. I have also been a graphics researcher for the last 5 years and am known in the industry as “the blue noise guy”. My graphics research has ended up in several games withing and outside of EA, and is also found in the Unreal Engine, including as part of Lumen, where you can see them showcase it as part of the explanation of how their technology works.
Audio Programming – One of my duties on Starcraft 2 and Heroes of the Storm was audio programming. This involved both gameplay level audio features, but also lower level debugging, and writing custom DSPs. A limiter and compressor I wrote that works in dB space and has quick attack times was adopted widely across the company for other games as well. Audio (and making music!) is my second love behind graphics, but it doesn’t get as much time dedicated to it.
Skeletal Animation – I was the animation programmer on a canceled open world Midway game “This is Vegas”, and also on the shipped monolith game “Gotham City Impostors”
Online Engineering – Having games talk to web services / databases for things like community challenges and user generated content. I have written the servers for these on a few occasions, and I have also done some basic network programming. I’m comfortable writing TCP/IP servers and clients, and can do UDP if pressed!
As a generalist, I’ve of course done extensive work debugging, profiling and optimizing, and in crafting “right sized” systems for problems, innovating algorithmically when appropriate, and keeping it dead simple when that was the best solution. I can read and write assembly, though reading is easier.
I’ve found that every game genre has a “secret sauce” and have worked on FPSs, RTSs, MOBAs, open world streaming games, physics based games, dungeon crawlers, metroidvanias, web games, mobile “idle” games, and games with user generated content. I find peer to peer deterministic simulation to be extremely interesting, and enjoyed working in that environment while working on Stracraft 2 and Heroes of the Storm.
I tend to enjoy small teams over big ones because it’s easier to move faster and “do the right things” without getting caught up in meetings or process. No one can do everything on their own, though, and reasonable timeframes necessitate parallelizing work, so there is a balance. I’ve also been the lead of small teams, and can lead when it makes sense, but prefer to be hands on and doing work, rather than being focused on management duties. I am also happy to mentor people and over the last 5 years at EA have mentored ~10 people in graphics, while also mentoring a couple people outside of work as well.
Machine learning is the topic du jour, and I do have knowledge in this area:
Automatic differentiation with dual numbers (forward mode AD)
Back propagation (backward mode AD)
Gradient descent, Adam.
MLPs and CNNs. I’d love to get more practice with them, and also to learn VAEs.
MCP servers to let agents interface with software more easily.
I have a video entitled “Machine Learning For Game Developers” where I go through the details of the bare metal parts of machine learning: https://www.youtube.com/watch?v=sTAqWRsEiy0
You can also interact with numerical digit recognition machine learning implementations I made in Gigi and then code generated to WebGPU. There is a version that uses a MLP, and another that uses a CNN, and runs in compute shaders on the GPU: https://electronicarts.github.io/gigi/
You can see a large number of technical game dev related topics that I’ve written up over the years on the root of this blog: https://blog.demofox.org/
Graphics Researcher
My main area of research relates to rendering noise, sampling, and stochastic rendering algorithms. There is more to do, including combining what I’ve done with learning algorithms. An overview of the basics my video “Beyond White Noise for Real-Time Rendering”. The first half explains the basic ideas, and the second half shows how to apply it to rendering: https://www.youtube.com/watch?v=tethAU66xaA
I started my blog in 2012 as a way to show an idea I had which combined the concepts of “dirty rectangles”, gbuffers, and ray tracing. The idea was to enable real time raytracing by only having to re-render small parts of the screen each frame. I didn’t know it at the time, but that is the point my research path began.
I continued to blog over the years, which built up my research skills. I wrote whenever I had ideas I wanted to share, sometimes thinking they were novel when they weren’t (I thought I invented interpolation search!). Also, whenever I learned a rare piece of knowledge, or something that was challenging to learn, I would write up the explanation I wish already existed, and would make a working implementation in the simplest, plainest code I could make to help others understand it better. It also helped me understand things better and the blog became an “external memory” where I could quickly come back up to speed on a topic I had learned years prior.
At some point I became fascinated by low discrepancy sequences, and blue noise. Blue noise fascination was largely driven by the game “INSIDE” by playdead, which used blue noise to make very pretty scenes with minimal computation. They made a great youtube video here where you can learn about it: https://www.youtube.com/watch?v=RdN06E6Xn9E
My fascination became action while working on Diablo 4 and the game needing a way to do stochastic transparency. This was to allow objects to fade out while using the richer deferred lighting, instead of having to switch to forward lighting which was a very obvious transition and a lot uglier lighting. I used the alpha value of objects to threshold a 2d blue noise texture to make arbitrary density blue noise points which had the correct density for the given alpha value. I then added the golden ratio each frame to the blue noise texture to make it not only blue over space, but also low discrepancy over time. This made it look very nice under temporal anti aliasing and if you play the game, you might not even notice that the fade is stochastic. In many cases it looks like true transparency.
I later left Blizzard and joined NVIDIA, working in dev tech, and some researchers there asked if I might know how to have screen space points follow a blue noise distribution for arbitrary densities, while also having good temporal properties for integration. This is exactly what my stochastic transparency solution in Diablo 4 did. However, I had some more time to think about the Diablo 4 solution and realized that the golden ratio addition over time damaged the blue noise over space, and actually made the cutoff frequency “significantly strobe” higher and lower over time, which wasn’t great.
To try and make a better spatiotemporal blue noise mask, I adapted the void and cluster algorithm (which is used to make blue noise textures) to make noise which was not only blue over space, but also, each individual pixel should be blue over time – blue meaning “high frequency” and “isotropic” here, without worrying too much about specific frequency makeup beyond that. This worked well!
At around the same time, there was an excellent publication called “Blue Noise Dithered Sampling” which effectively showed how to make blue noise textures which had vector values per pixel, instead of only scalar, and showed how to use them to make amazing renderings at the lowest of sample counts: https://iliyan.com/publications/DitheredSampling/
I made a second technique for making spatiotemporal blue noise textures that involved simulated annealing, much like that paper, to randomly swap pixels to improve a scoring function.
We published that paper as “Spatiotemporal Blue Noise masks”.
I left NVIDIA and joined SEED at Electronic Arts as a graphics researcher, where I presented my work on spatiotemporal blue noise, and I nerd sniped a couple super smart, and very cool people to work in the problem space with me.
One of these people, William Donnelly, realized that my scoring function was not optimal, and he derived a better scoring function for both scalar and vector values, and also generalized the work to allow you to choose arbitrary spatial and temporal filters. This makes noise that is not only better perceptually, but can alternately be designed to just be more easily filtered by any specific denoising filter. We then published “FAST: Filter-Adapted Spatio-Temporal Sampling for Real-Time Rendering”.
From there, I did a small follow up paper explaining how to use blue noise point sets to make FAST noise textures which had importance sampled vectors in them. “Importance-Sampled Filter-Adapted Spatio-Temporal Sampling”.
There is work left to do with higher dimensional sampling, but the area is solved in a lot of ways and is waiting for the rest of the industry to catch up IMO. Our work has been cited by other research – when we presented FAST, the best paper award went to an NVIDIA paper which used STBN (what FAST improved on) – and our work is also used by games within EA, and also outside of EA. You can also see our work in Unreal Engine’s Lumen writeup. Go there and search for “blue noise” to see it: https://www.unrealengine.com/tech-blog/lumen-brings-real-time-global-illumination-to-fortnite-battle-royale-chapter-4
I believe next steps in these areas would be to either optimize noise and noise filters together (for specific situations), or to give blue noise point sets the same properties we gave to blue noise textures. I have the beginnings of a spatiotemporal blue noise point set working using optimal transport (would be useful for sparse rendering, and many other things), but it needs some more work.
There is an entirely different direction to pursue as well, in the same problem space.
Noise textures and sampling patterns aim to be the best they can be when working blind. In contrast to this are algorithms like restir, which learn the details of what is being sampled. A better version of restir would use good noise and sampling when it was unsure about the data it had, and would rely on the learned samples more when it was more confident. There is a continuum here where good noise is good for exploration, and learning is good for exploitation, and a good algorithm would use both appropriately.
Restir is just one of a family of many possible real time friendly rendering algorithms. There is a whole Pareto frontier of algorithms that live in this space, being able to trade speed for quality. In short: any place a random number is used in rendering, or COULD be used in rendering (like a stochastic filter), there is a place to drop in a sampling and learning algorithm. This algorithm could be neural, or it could be something like a Kalman filter, or a particle filter, or anything else.
There is no shortage of places where random scalars / points / vectors are used in rendering, or where they could be used. Each of these represents an opportunity for advancement.
Note: I have done other research along the way, but this blue noise work has been the main thread. I also have 2 patents.
The last paper I worked on was accepted and is in the process of being edited. A student from Pakistan asked me how to get into graphics research, and I suggested we write a paper together, with him being first author. We re-wrote a rejected paper I wrote in 2016 about abusing the texture interpolator to evaluate Bezier curves, and he found newer relevant research that doubled the contributions the paper adds. The ultimate result of the work is it shows how to offload compute onto the texture sampler, which can help in compute bound work loads. He did a great job, and it was a great collaboration. He is now working on another paper with another researcher, so it seems like our project was successful in jump starting his work.
Throughout the research at SEED, we used Gigi, a rapid graphics R&D platform I built, to make experimentation and development quicker and easier. I will be talking about that next.
Rapid Graphics R&D Render Pipeline – Gigi and Beyond
Gigi is version 3 of concepts that started while I was at Blizzard.
At Blizzard, each game team works almost like it’s own game company, using it’s own proprietary game engine (for the most part). This made it challenging for people to move between teams since the technology varied so much, and it also made it hard to know which engine to use when a new prototype game team would start up.
I was recruited internally for a “shared game engine” initiative, to make an engine which game teams could use to prorotype or develop future games on. I was tasked with making a rendering solution which could service any game genre Blizzard might want to make, on any platform.
I quickly decided that was far too many constraints to put on any render pipeline, and that the solution had to be that the render pipeline was loaded from disk as an asset. More specifically, the solution was to describe a render graph in data, instead of code. This way, each game could have its own right sized renderer, with the features they wanted, without a sea of complexity that dealt with functionality they didn’t want or need. Of course, nobody wants to start a render pipeline from scratch, so there needed to be a library of situationally appropriate renderers for games to start from, and modular rendering techniques they could plug into their render graph.
A nice side benefit of this is that the render graph is fully statically analyzable, which enabled some nice profiling and debugging features through reflection. For instance, you could view resources at any stage in the render pipeline in real time, as if you did a renderdoc capture, but without actually having to take a capture.
Another nice benefit is that you could change render pipelines at runtime by choosing a different one from a drop down menu. This would let you quickly and easily see how what you were looking at would look on the console or mobile version of the renderer.
Like many exploratory initiatives in game development, it was ultimately shut down due to shifting business priorities and cancelled prototype projects, though the technology influenced later work at the company.
Version 2 of this idea came up while I was at NVIDIA on the dev tech team.
In dev tech, there were a lot of effort to port research or implement technology features into various internal and external platforms. Internally this would mean things like Falcor or Omniverse, and externally this would mean things like DX12, Vulkan, Unreal Engine, Unity, and the myriad of proprietary engines that game partners used.
All this porting and implementation took a lot of time and effort, and each implementation ended up diverging from the rest because they were written by different people, and for different goals. That meant that if you wanted to update a technique across the board – to improve quality, perf, or do a bug fix – that this “small patch” would end up being almost as much work as the initial implementation.
While making the RTXGI (DDGI) plugin for Unreal, I realized that if you had a description of a render graph, you could generate the code to implement it. Not only that, the code generated could look like it was written by a human and pass a code review.
When working this way, doing an update for quality, perf or bug fixes meant just regenerating the code and dropping it in. Also, by necessity, the code ended up being a lot more modular than code a human would write. A human familiar with a system knows all sorts of short cuts to get at things more easily than a formal interface, and the temptation is too great sometimes to just get something done, even if done in an ugly way.
NVIDIA was exploring several solutions including cross-platform libraries and extending Slang. I focused on code generation because it solved a specific problem: game developers want to integrate techniques into their existing codebases without external dependencies. Generated code could be reviewed, modified, and maintained just like hand-written code.
My ideas worked well as a proof of concept and I used it in the RTXGI UE plugin.
Eventually I left NVIDIA and joined SEED at Electronic Arts where version 3 came to be.
At SEED, the challenge I was trying to solve was that it’s hard for many researchers to work against direct APIs like DX12 and Vulkan. Alternately, engines like Frostbite, Unreal, Unity can be a steep learning curve, they can be slow to iterate with. Also, when your work is part of a large rendering pipeline, it can be hard to know what else in the engine might be affecting the performance and quality of your results.
Gigi was born to be a place where people could do GPU work against real time graphics APIS, they could work at the speed of thought, be confident in their results, automate tasks with python, and when they were done, they could code generate their work to Unreal, Frostbite, DX12, WebGPU, and other platforms added as needed.
Electronic Arts was super kind and allowed me to open source this creation with a permissive license, so it can continue to exist in whatever form it takes in the future, by whoever continues development: https://github.com/electronicarts/gigi
You can also see a gallery of example techniques code generated to WebGPU here, which include machine learning applications: https://electronicarts.github.io/gigi/
Gigi has had contributions from inside EA and outside EA. There are of course bugs, and features that needed improvement, but I have only had positive feedback about the core concepts of how it works. Researchers like it because they can do what needs to be done without a lot of fuss. Graphics programmers like it because they can rapidly prototype ideas and find the wins before spending the effort to make it work in their engine. Graphics novices like it, because they can focus on just writing shaders, while getting access to the full power of the GPU.
There are a lot of “secret sauce” learnings from making Gigi, including things I wish I would have differently. The core of what Gigi is, though, is:
Editor – You describe a render graph as data in the editor
Viewer – You can load the render graph in the viewer to iterate (with hot reloading), profile and debug it. Change technique parameters, move the camera around, change what assets are used as inputs, using python to automate data gathering and similar.
Compiler – Code generate what you made to another platform. The code it emits looks as if a human wrote it with well-named variables, comments, proper indentation, and would pass a code review.
Gigi supports work graphs, ray tracing, compute shaders, rasterization, it is set up to support dx12’s tensor core access “linalg” when the driver support comes, it has an MCP server, it is python scriptable, it supports slang to let you write shaders that use automatic differentiation, and can run onnx through DirectML nodes. It’s set up to do modern R&D – both research and development, truly.
Gigi itself is great software, but I feel the real lesson is that engines can – and SHOULD – work how Gigi works.
Graphics programming is harder than ever. You need to be an expert engine programmer before you can see your first triangle, and then you need to know calculus, statistics, the physics of light, the rendering equation, microfacet theory, perception, PBR, path tracing, a multitude of rendering techniques, and so on..
The ideas behind Gigi remove the requirement of being an expert engine programmer and let people focus on the second part, which is already more than enough for any one person.
Gigi has a simple interface that lets people work quickly and easily. When you code generate the Gigi technique, it’s full of the required boilerplate complexity that things like DX12 and Vulkan (or even large engines!) need – and it generates that code CORRECTLY. To me, that is proof that the complexity isn’t needed. It hasn’t added any information.
Gigi simplifies graphics work through a few main avenues:
Subtractive Abstraction – Gigi uses the same abstractions you use when using a modern API or engine. It looks very familiar to those who already know graphics programming. Gigi finds ways to remove complexity without removing power. An easy example of that is that resource barriers are automatic in Gigi, and resource lifetime management is just specifying whether a resource is transient or persistent.
RHI Is The Wrong Abstraction Level – When people make renderers, one of the core pieces is an API abstraction that encapsulates modern and legacy graphics APIs. Making one that performs well and doesn’t leak implementation details is very hard. Impossible even. Gigi works at a higher level where nodes say “rasterize this mesh to these color and depth targets” or “run a compute shader” and similar. Working at the higher level, a platform is able to interpret the render graph actions however it wants, as long as it honors the read/write order and other constraints. That means a tiled renderer could combine raster and compute, if the resources involved were compatible with that. Working at a higher level gives a back end more freedom to do what it would like to do ideally for a given piece of rendering work, instead of an API that has to satisfy all platforms at once.
Render Graph As Data – Instead of making a single render graph to support all game types and platforms, you have the freedom to make a different render graph per platform and game. You can also share common work through sub graphs. This lets you get to a state where when you modify your rendering pipeline for your game on your platforms, you only have to think about your game, or the specific platform you are working on. You don’t have to consider everything else at the same time and try to come up with a compromise they are all happy with. Just make what you need for your specific situation and use it.
We can do better, graphics programming can be easier, and I’d love the chance to make that a reality for all of us. If you agree, drop me a line.
The video shows the link between probability and information entropy and a great takeaway from it is that you can use these concepts to decide what kind of experiments to do, to get as much information as possible. This could be useful if you are limited by time, computation, chemicals, or other resources. It seems like you could also mix this with “Fractional Factorial Experiment Design” somehow (https://blog.demofox.org/2023/10/17/fractional-factorial-experiment-design-when-there-are-too-many-experiments-to-do/).
Probability and Bits
Information theory links probability to bits of information using this formula:
where p is the probability of an event happening, and b is the number of bits generated by that event.
Using a fair coin as an example, there is a 50% (1/2) chance of heads and a 50% (1/2) chance of tails. In both cases, p=0.5. Let’s calculate how many bits flipping a head gives us:
So flipping a coin and getting heads would give us 1 bit, and so would getting tails, since it has the same probability. This makes some perverse sense, since we can literally generate random bits by flipping a coin and using Heads / Tails as 0 / 1.
What if we had a weighted coin that had a 75% (3/4) chance of heads, and a 25% (3/4) chance of tails?
So, flipping a heads gives us only 0.415 bits of information, but flipping tails gives us 2 bits of information. When something is lower probability, it’s more surprising when it happens, and it gives us more bits.
What if we had a two headed coin so that flipping heads was a 100% (1/1) chance, and tails was a 0% (0/1) chance?
The math says that flipping a 2 headed coin is a deterministic result and gives us no bits of information!
Submarine Game
The submarine game is a simplified and single player version of battleship where you have a grid of MxN cells, and one of the cells contains a submarine. The game is to guess a cell to attack, and it’s revealed whether the submarine was there or not. The game ends when the submarine is found.
At each step in the game, if there are U cells which are covered, there is a 1/U chance of shooting the submarine and a (U-1)/U chance of missing the submarine.
You can think of this a different way: The goal is to find the position of the submarine, and if you miss the submarine, you eliminate one of the possibilities, giving you some more information about where the submarine is by showing you where it isn’t and narrowing down the search. If you hit the submarine, you get all remaining information and the game ends.
If you had a 4×4 grid, there are 16 different places the submarine could be in, so you could store the position in 4 bits. Every time you miss the submarine, you gain a fraction of those bits. When you eventually hit the submarine you gain the remaining fraction of those bits!
Let’s see this in action with a smaller 4×1 grid. With only 4 cells, the submarine position can be encoded with 2 bits, so 2 bits is the total amount of information we are trying to get.
Turn 1
?
?
?
?
On the first turn we can choose from 4 cells to reveal. 3 cells are empty, and 1 cell is the submarine, so we have a 75% (3/4) chance of missing the submarine, and a 25% (1/4) chance of hitting it. Lets calculate how many bits of information each would give us:
This shows that if we find the submarine, we gain the full 2 bits of information all at once. Otherwise, we gain 0.415 bits of information.
Turn 2
Miss
?
?
?
If we got to the second turn, we missed on the first turn and have accumulated 0.415 bits of information. There are 3 cells to reveal. 2 cells are empty and 1 has the submarine. There is a 66% (2/3) chance to miss the submarine, and a 33% (1/3) chance to hit the submarine.
If we hit the submarine, we get 1.585 bits of information to add to the 0.415 bits of information we got in the first turn, which adds together to give us the full 2 bits of information needed to locate the submarine. Otherwise, we gain 0.585 more bits of information giving us 0.415+0.585=1 bits of info total, and continue on to turn 3.
Turn 3
Miss
Miss
?
?
On turn 3 there are 2 cells to reveal. 1 cell is empty and 1 has the submarine, so there is a 50% (1/2) chance for either missing or hitting the submarine. We also have accumulated 1 bit of information, which makes sense because we’ve eliminated half of the cells and have half the number of bits we need.
If we hit the submarine, it gives us the other bit we need, and if we miss the submarine, it also gives us the other bit we need. Either we hit the submarine and know where it is, or we revealed the final cell that doesn’t have the submarine in it, so we know the submarine is in the final unrevealed cell.
If we missed, let’s continue onto Turn 4, even though we have accumulated 2 bits of information already.
Turn 4
Miss
Miss
Miss
?
On turn 4 there is 1 cell to reveal. 0 cells are empty and 1 has the submarine, so there is a 100% (1/1) chance to hit the submarine, and 0% (0/1) chance to miss. We also already have 2 bits of information accumulated from the previous rounds, while only needing 2 bits of information total to know where the submarine is.
The math tells us that we got no new information from revealing the final cell. It was completely deterministic and we knew the outcome already. Turn 4 was not necessary.
Neat, isn’t it?
Miss
Miss
Miss
Hit
Expected Information Entropy
Besides being able to calculate the number of bits we’d get from a possible result, we can also look at all possibilities of an event simultaneously and get an expected number of bits to get from the event. You calculate this by calculating the bits for each possible event, multiplying by the probability, and summing them all up.
Fair Coin
Going back to the coin example, with a fair coin, there is a 50% (1/2) chance of landing heads, and a 50% (1/2) chance of being tails. Let’s calculate the number of bits that gives us again:
We then multiply them each by their probability of coming up and add them together. That is a weighted of the number of bits the events generate, weighted by their probability of happening.
So, the expected number of bits generated from a fair coin flip is 1 bit.
I’m using the notion to mean expected information entropy, but in other sources you’ll commonly see it as where is the event, and are the outcomes.
Unfair (Biased) Coin
How about the unfair coin that had a 75% (3/4) chance of heads, and a 25% (3/4) chance of tails?
Now let’s multiply each by their probability and add them together:
The biased coin gave us less information on average than the fair coin. The fair coin gave 1 bit, while this unfair coin only gave 0.811 bits. Interesting!
Fair Coin + Edge (Unfair 3 Sided Coin)
Let’s run the numbers for a coin where there’s a 49% chance to land heads, a 49% chance to land tails, and a 2% chance to land edge on.
Now let’s calculate the expected information entropy:
Equal Chance For Heads, Tails, Edge (Fair 3 Sided Coin)
Lastly, let’s do the math for a coin that has equal chances of landing heads, tails, or edge. All of them being a 33% (1/3) chance.
Tails and edge have the same probability so same number of bits. If we take the weighted average of that, since they are all the same, we get:
It looks to me that the expected bits are highest when the probabilities are equal. I asked Claude who said that is true, and gave a proof I could follow, as well as an intuitive explanation.
Using Expected Information Entropy To Choose Experiments
The video has a neat question they use “Expected Information Entropy” to solve:
Imagine you have 12 balls. 11 of them weigh the same, but 1 ball is either heavier or lighter than the others. You have a scale to help you figure out which ball is the “odd ball”. What is your strategy for finding it using the least number of weighings as possible?
Tangent: My 11 year old son Loki said the answer was 2 if you get lucky. Put one ball on each side of the scale, and if one of them is the odd ball, the scale will show an uneven weight. Replace one of the balls with another ball from the pile. If the scale goes flat, the ball that was removed was the “odd ball”, else it’s the ball that did not get removed. This answer relies on luck, but it is the minimum number of weighings possible.
For the “real” solution, the video wants you to instead think about the lowest number of EXPECTED weighings.
For the first weighing you have to decide how many balls to put on the left and right side of the scale.
We actually know that there are 3 possible outcomes of this are:
The left side of the scale goes down.
The right side of the scale goes down.
The scale is level.
If we decide how many balls to put on each side, we can calculate the probabilities of the outcomes.
1 Ball Each Side
For 1 ball on each side:
The left side of the scale goes down. 1/12 chance.
The right side of the scale goes down. Also a 1/12 chance.
The scale is level. a 10/12 chance.
If it doesn’t make sense to you how I came up with these probabilities, the next section explains it.
Since we know the outcomes and their probabilities, we can calculate the expected entropy information!
Putting 1 ball on each side for the first weighing gives us 0.817 bits of information on average.
2 Balls Each Side
The left side goes down: 2/12 chance
The right side goes down: 2/12 chance
The scale is level: 8/12 chance
Putting 2 balls on each side gives us 1.252 bits of information on average.
The Rest
We could calculate the rest of them, but I’ll show you the final chart and leave it up to you to calculate them all if you want to!
Balls On Each Side
Expected Information Entropy
1
0.82
2
1.25
3
1.50
4
1.58
5
1.48
6
1.0
As you can see, weighing 4 balls gives the most expected information entropy. On average, it’s the best thing to do for the first weighing. Something interesting is that when you put 4 balls on each side, there are 4 balls left on the table, so it is equal chance that the scale tilts left, lays flat, or tilts right. Just like we saw at the end of the last section, having 3 options with equally probable events gives the most expected information entropy.
A good heuristic to take away from all of this seems to be that if you are trying to decide what kind of measurement or experiment to do next, you should do whichever one has as close to even probabilities of all outcomes as possible.
I feel like this must relate to dimensionality reduction (like PCA or SVD), where you find a lower dimensional projection that has the most variance.
The video explains what to do after you do the first ball weighing, but it essentially comes down to calculating the expected information entropy for the next set of outcomes, and choosing the highest one. It turns out you can isolate the ball with 3 weighings total, when you work this way.
Bonus: Calculating Odds Of Scale Results
This is what makes sense to me. Your mileage may vary.
Let’s say we have 3 balls and label them A,B,C. A is the odd ball and is heavier than B and C. There are 6 ways to arrange these letters. ABC ACB BAC BCA CAB CBA
If we take the left letter of the strings above to be what is on the left side of the scale, the middle letter means what is on the right side of the scale, and the right letter means what is left on the table, we have our 6 possible ball configurations.
Out of those configurations, 2 out of 6 have A on the left of the scale, so the scale tilts to the left. 2 of the 6 have A on the right of the scale, so the scale tilts to the right. The last 2 of the 6 have A on the table, so the scale is flat. If A was light instead of heavy, you just reverse the tilt left and tilt right but everything else stays the same.
In the problem asked, there are 12 balls though, which are a lot more letters. In general, for N letters representing N balls, there are N! ways to arrange those letters. Each letter appears in each position an equal number of times, which is (N-1)! ways. So, the percentage of the time a letter is in a specific column is (N-1)! / (N!), or 1/N. Another way to get here is to just realize that every column has every letter in it the same number of times, so with N letters, each letter appears in the column 1/N percent of the time.
For 1 ball on each side, for our 3 cases we just count:
Tilt Left: The percentage of times the oddball “A” is in the first column (1/12).
Tilt Right: The percentage of times the oddball “A” is in the second column (1/12).
Flat: The remainder to make the percentages add up to 1 (12/12 – 1/12 – 1/12 = 10/12).
So for 12 balls, it’s 1/12 for each of the tilt directions, leaving 10/12 as the remainder, for the odd ball to be on the table.
For 2 balls on each side, we count:
Tilt Left: The percentage of times the oddball “A” is in the first column or second column (1/12 + 1/12 = 2/12).
Tilt Right: The percentage of times the oddball “A” is in the third column or fourth column (1/12 + 1/12 = 2/12).
Flat: the remainder (12/12 – 2/12 – 2/12 = 8/12).
So, it’s 2/12 for each of the tilt directions, and 8/12 for the remainder.
The pattern continues for higher ball counts being weighed.
Hopefully you found this post interesting. Thanks for reading!
This article explains how these four things fit together and shows some examples of what they are used for.
Derivatives
Derivatives are the most fundamental concept in calculus. If you have a function, a derivative tells you how much that function changes at each point.
If we start with the function , we can calculate the derivative as . Here are those two functions graphed.
One use of derivatives is for optimization – also known as finding the lowest part on a graph.
If you were at and wanted to know whether you should go left or right to get lower, the derivative can tell you. Plugging 1 into gives the value -4. A negative derivative means taking a step to the right will make the y value go down, so going right is down hill. We could take a step to the right and check the derivative again to see if we’ve walked far enough. As we are taking steps, if the derivative becomes positive, that means we went too far and need to turn around, and start going left. If we shrink our step size whenever we go too far in either direction, we can get arbitrarily close to the actual minimum point on the graph.
What I just described is an iterative optimization method that is similar to gradient descent. Gradient descent simulates a ball rolling down hill to find the lowest point that we can, adjusting step size, and even adding momentum to try and not get stuck in places that are not the true minimum.
We can make an observation though: The minimum of a function is flat, and has a derivative of 0. If not, that would mean it was on a hill, which means that going either left or right is lower, so it wouldn’t be the minimum.
Armed with this knowledge, another way to use derivatives to find the minimum is to find where the derivative is 0. We can do that by solving the equation and getting the value . Without iteration, we found that the minimum of the function is at and we can plug 3 into the original equation to find out that the minimum y value is 4.
Things get more complicated when the functions are higher order than quadratic. Higher order functions have both minimums and maximums, and both of those have 0 derivatives. Also, if the term of a quadratic is negative, then it only has a maximum, instead of a minimum.
Higher dimensional functions also get more complex, where for instance you could have a point on a two dimensional function that is a local minimum for x but a local maximum for y. The gradient will be zero in each direction, despite it not being a minimum, and the simulated ball will get stuck.
Gradients
Speaking of higher dimensional functions, that is where gradients come in.
If you have a function , a gradient is a vector of derivatives, where you consider changing only one variable at a time, leaving the other variables constant. The notation for a gradient looks like this:
Looking at a single entry in the vector, , that means “The derivative of w with respect to x”. Another way of saying that is “If you added 1 to x before plugging it into the function, this is how much w would change, if the function was a straight line”. These are called partial derivatives, because they are derivatives of one variable, in a function that takes multiple variables.
Let’s work through calculating the gradient of the function .
To calculate the derivative of w with regard to x (), we take the derivative of the function as usual, but we only treat x as a variable, and all other variables as constants. That gives us with .
Calculating the derivative of w with regard to y, we treat y as a variable and all others as constants to get: .
Lastly, to calculate the derivative of w with regard to z, we treat z as a variable and all others as constants. That gives us .
The full gradient of the function is: .
An interesting thing about gradients is that when you calculate them for a specific point, they give a vector that points in the direction of the biggest increase in the function, or equivalently, in the steepest uphill direction. The opposite direction of the gradient is the biggest decrease of the function, or the steepest downhill direction. This is why gradients are used in the optimization method “Gradient Descent”. The gradient (multiplied by a step size) is subtracted from a point to move it down hill.
Besides optimization, gradients can also be used in rendering. For instance, here it’s used for rendering anti aliased signed distance fields: https://iquilezles.org/articles/distance/
Jacobian Matrix
Let’s say you had a function that took in multiple values and gave out multiple values: .
We could calculate the gradient of this function for v, and we could calculate it for w. If we put those two gradient vectors together to make a matrix, we would get the Jacobian matrix! You can also think of a gradient vector as being the Jacobian matrix of a function that outputs a single scalar value, instead of a vector.
Here is the Jacobian for :
If that’s hard to read, the top row is the gradient for v, and the bottom row is the gradient for w.
When you evaluate the Jacobian matrix at a specific point in space (of whatever space the input parameters are in), it tells you how the space is warped in that location – like how much it is rotated and squished. You can also take the determinant of the Jacobian to see if things in that area get bigger (determinant greater than 1), smaller (determinant less than 1 but greater than 0), or if they get flipped inside out (determinant is negative). If the determinant is zero, it means it squishes everything into a single point (or line, etc. at least one dimension is scaled to 0), and also means that the operation can’t be reversed (the matrix can’t be inverted).
Here’s a great 10 minute video that goes into Jacobian Matrices a little more deeply and shows how they can be useful in machine learning: https://www.youtube.com/watch?v=AdV5w8CY3pw
Since Jacobians describe warping of space, they are also useful in computer graphics, where for instance, you might want to use alpha transparency to fade an object out over a specific number of pixels to perform anti aliasing, but the object may be described in polar coordinates, or be warped in way that makes it hard to know how many units to fade out over in that modified space. This has come up for me when doing 2D SDF rendering in shadertoy.
Hessian Matrix
If you take all partial derivatives (aka make a gradient) of a function , that will give you a vector with three partial derivatives out – one for x, one for y, one for z.
What if we wanted to get the 2nd derivatives? In other words, what if we wanted to take the derivative of the derivatives?
You could just take the derivative with respect to the same variables again, but to really understand the second derivatives of the function, we should take all three partial derivatives (one for x, one for y, one for z) of EACH of those three derivatives in the gradient.
That would give us 9 derivatives total, and that is exactly what the Hessian Matrix is.
If that is hard to read, each row is the gradient, but then the top row is differentiated with respect to x, the middle row is differentiated with respect to y, and the bottom row is differentiated with respect to z.
Another way to think about the Hessian is that it’s the transpose of the Jacobian matrix of the gradient. That’s a mouthful, but it hopefully helps you better see how these things fit together.
Taking the 2nd derivative of a function tells you how the function curves, which can be useful (again!) for optimization.
This 11 minute video talks about how the Hessian is used in optimization to get the answer faster, by knowing the curvature of the functions: https://www.youtube.com/watch?v=W7S94pq5Xuo
Where a derivative approximates a function locally with a line, a second order derivative approximates a function locally with a quadratic. So, a Hessian can let you model a function at a point as a quadratic type of function, and then do the neat trick from the derivative section of going straight to the minimum instead of having to iterate. That takes you to the minimum of the quadratic, not the minimum of the function you are trying to optimize, but that can be a great speed up for certain types of functions. You can also use the eigenvalues of the Hessian to know if it’s positive definite – aka if it’s a parabola pointing upwards and so actually has a minimum – vs if it’s pointing downwards, or is a saddle point. The eigenvectors can tell you the orientation of the paraboloid as well. Here is more information on analyzing a Hessian matrix: https://web.stanford.edu/group/sisl/k12/optimization/MO-unit4-pdfs/4.10applicationsofhessians.pdf
Calculating the Hessian can be quite costly both computationally and in regards to how much memory it uses, for machine learning problems that have millions of parameters or more. In those cases, there are quasi newton methods, which you can watch an 11 minute video about here: https://www.youtube.com/watch?v=UvGQRAA8Yms
Thanks for reading and hopefully this helps clear up some scary sounding words!
I stumbled on this when working on something else. I’m not sure of a use case for it, but I want to share it in case there is one I’m not thinking of, or in case it inspires other ideas.
Let’s say you want to do Monte Carlo integration on a function y=f(x) for x being between 0 and 10. You can do this by choosing random values for x between 0 and 10, and averaging the y values to get an “average height” of the function between those two points. This leaves you with a rectangle where you know the width (10) and you are estimating the height (the average y value). You just multiply the width by that estimated height to get an estimate of the integral. The more points you use, the more accurate your estimate is. You can use Monte Carlo integration to solve integrals that you can’t solve analytically.
We use Monte Carlo integration A LOT in rendering, and specifically real time rendering. This is especially true in the modern age of ray traced rendering. When a render is noisy, what you are seeing is the error from Monte Carlo integration not being accurate enough with the number of samples we can afford computationally. We then try to fix the noise using various methods, such as filtering and denoising, or by changing how we pick the x values to plug in (better sampling patterns). Here are some relevant resources:
Let’s say we want to integrate the function y=f(x) where x is a scalar value between 0 and 1. Three common ways to do this are:
Uniform White Noise – Use a standard random number generator (or hash function) to generate numbers between 0 and 1.
Golden Ratio – Starting with any value, add the golden ratio to it (1.6180339887…) and throw away the whole numbers (aka take the result mod 1) to get a random value (quasirandom technically). repeat to get more values.
Stratified – If you know you want to take N samples, break the 0 to 1 range into N equally sized bins, and put one uniform white noise value in each bucket. Like if you wanted to take two samples, you’d have a random number between 0 and 1/2, and another between 1/2 and 1. A problem with uniform white noise is that it tends to clump up and leave big holes. Stratification helps make the points more evenly spaced.
Here’s a log/log error graph using those 3 kinds of sampling strategies to integrate the function y=x from 0 to 1. The x axis is the number of samples, and the y axis is error.
White noise is terrible as usual. Friends don’t let friends use white noise. The golden ratio sequence is great, as per usual. Golden ratio for the win! Stratification is also quite good, but it doesn’t give very good results until the end.
Stratified sampling doesn’t do well in the middle because we are picking points in order. Like for 100 points, we sample between 0 and 1/100, then between 1/100 and 2/100, then between 2/100 and 3/100 and so on. By the end it fills in the space between 0 and 1, but it takes a while to get there.
The question is… can we make stratified sampling that is good all along the way, instead of only being good at the end? The answer is yes we can.
An observation is that we could visit those bins in a different order. But what order should we visit them in? We are going to get a bit meta and visit them in “golden ratio” order. If are taking N samples, we are going to pretend that N is 1.0, and we are going to do golden ratio sampling to pick the order of the buckets to do stratified sampling in. If we naively used the golden ratio sequence, multiplied by N and cast to integer to get the bucket index, we’d find we hit some of the buckets multiple times, and missed some of the buckets. But it turns out that we can find an integer coprime to N that is closest to the golden ratio. We can then start at any index, and repeatedly add that number to our index to get the next index – making sure to take the result modulo N. We will then visit each bucket exactly once before repeating the sequence.
Doing that, we get “StratifiedGR” below. It does nearly as well as the golden ratio sequence, but the final result is the same as if we did stratification in order.
Is this useful? Well, it’s hard to tell in general whether stratified sampling or golden ratio wins for taking N samples in Monte Carlo integration.
The golden ratio (orange) is usually lower error than the golden ratio shuffled stratifed sampling (red), but the ending error is 0.000017 for “StratifedGR” (same as Stratified), while it is 0.000023 for “GoldenRatio” (and 0.000843 for “WhiteNoise”), so stratification has lower error in the end.
A nice thing about the golden ratio sequence is that you can always add more points to the sequence, where for stratified sampling – and even golden ratio shuffled stratified sampling – you have to know the number of samples you want to take in advance and can’t naturally extend it and add more.
Stratifed sampling is randomized within the buckets, so we could repeat the sequence again to get new samples, but we are using the same buckets, and we are putting white noise values in them, so our sequence just sort of gets “white noise gains”, instead of the gains that a progressive, open, low discrepancy sequence gives. Below we repeat golden ratio shuffled stratification twice (purple) and 10 times (brown). You can see that golden ratio shuffled stratification loses quality when you repeat it. You really need to know how many samples you want at max, when doing golden ratio shuffled stratified sampling, but you are free to use less than than number.
By doing a golden ratio shuffle on stratified sampling, we did make it progressive (“good” at any number of samples), but we also made it progressive from any index (“good” starting from any index, for any number of samples). That is a pretty neat property, and comes from the fact that our golden ratio shuffle iterator is actually a rank 1 lattice, just like the actual golden ratio sequence, and this is a property of all rank 1 lattices.
However, by golden ratio shuffling stratification, we also made it TOROIDALLY progressive. What i mean by that is that the sampling sequence is finite, but that you can start at any index and have “good” sampling for any number of samples EVEN WHEN THE SEQUENCE FINISHES AND STARTS OVER. There is no “seam” when this sequence starts over. It just keeps going at the full level of quality. This is due to the fact that our “golden ratio shuffle iterator” rank 1 lattice uses a number that is coprime to N to visit all the indicies [0, N) exactly once before repeating.
This torodial progressiveness is useful if you have a lot of things doing integration at once, all using the same sampling sequence for the function, but individually, they may be (re)starting integration on different time intervals. That may sound strange and exotic, but that is exactly what is happening in temporal anti aliasing (TAA). We have a global sub pixel camera jitter, which is the x we plug into the y=f(x) as we integrate every pixel over its footprint, but each pixel individually uses neighborhood color clamping and other heuristics to decide when it should throw out the integration history and start over.
The only challenge is that if we wanted to use something like this for TAA, we would need a 2D sequence for the camera jitter instead of 1D. I do happen to have a blog post on a 2D version of the low discrepancy shuffler. I don’t think that will magically be the answer needed here, but perhaps you can smell what I’m cooking 😛
In the post so far, we’ve only looked at integrating the “triangle” function y=x. Below are the results for that again, and also for a step function, a sine function, and a Gaussian function. Different sampling sequences behave better or worse with different types of integrands sometimes.
Thresholding blue noise textures can be a decent way of getting blue noise points at runtime in real-time rendering. They aren’t the highest quality point sets, but they are fast to make and they can use a density map for the threshold value to make non uniform blue noise points, so they are very convenient.
At various times over the past year or so I’ve stumbled on evidence that seemed to show that thresholding FAST noise textures made lower quality blue noise point sets than when thresholding STBN noise textures.
STBN is “Spatiotemporal Blue Noise Masks”, which aims to have N slices of perfectly good blue noise textures, where each pixel individually is also blue over time. We published it in 2022, and it worked well. https://www.ea.com/seed/news/egsr-2022-blue-noise
FAST is “Filter Adapted Spatiotemporal Sampling”, which eclipses STBN by working for arbitrary spatial and temporal filters, while also increasing the quality of noise textures over STBN, particularly of the vector valued noise textures. We published it in 2024 and it was a nice improvement over STBN. https://www.ea.com/seed/news/spatio-temporal-sampling
So, it was a little bit confusing that thresholding FAST noise textures would be lower quality than STBN, when everything else seemed to show that FAST was better or equal to STBN in every single way.
This post is to finally do those threshold tests and share the results. First lets talk about all the noise types involved. Here they are along with their power spectrums (DFT magnitude).
You can click on the images in this post to view them full sized.
Note that all DFTs in this post are divided by the same value to make them be in the 0 to 1 range, so you can compare them to each other.
FAST S – A 128×128 spatial blue noise texture optimized by the FAST optimizer for a Gaussian low pass filter with a sigma of 1.0.
FAST ST – The first slice of a 128x128x32 FAST noise texture like FAST S, but optimized over time for a Gaussian filter with a sigma of 1.0 as well, with the filters “separate 0.5” (added) not “product” (multiplied).
STBN 1.0 S – A 128×128 spatial blue noise texture optimized by the STBN optimizer (a void and cluster variant) with a sigma of 1.0.
STBN 1.0 ST – The first slice of a 128x128x32 STBN texture also optimized for a gaussian filter over time with sigma 1.0.
STBN 1.9 S / ST – the same as STBN 1.0, but using a sigma of 1.9 instead.
VNC 1.0 S / 1.5 / 1.9 – 128×128 spatial blue noise made using the void and cluster algorithm made with sigmas 1.0, 1.5, and 1.9 respectively. The void and cluster paper recommends 1.5 and the “free blue noise textures” site uses 1.9. I’m including 1.0 as another data point.
Tellusim ST – The first slice of a 128x128x64 spatiotemporal blue noise texture, using a custom algorithm, from https://tellusim.com/improved-blue-noise/. This noise is actually 16 bit greyscale instead of 8 bit, which gives it many more unique values than the others. Up to 65,536 instead of 256.
Next up, let’s threshold these noise textures. The first row labeled “<= 1” means “if the pixel value is <= 1, write a black dot, else write a white dot”. The second row labeled “2” means “if the pixel value is <= 2, write a black dot, else write a white dot” and so on.
Here are power spectrums of those thresholded values.
Observations
We should start out by noting that thresholding is just one way to measure the quality of blue noise textures. If you are using a noise texture for stochastic transparency by testing alpha against the noise texture to see if you should discard a pixel or not, thresholding quality matters to your result. If you are dithering, the thresholding quality won’t matter for your result
This is important because in the first diagram that shows the power spectrum of the noise textures, the Fidussion texture shows itself to be very high quality blue noise – it has a very dark center circle showing very little low frequency content, and the circle is about as large as it can be within the square. When you use this noise, it pushes as much of the “rendering error” that it can into the highest frequencies, so that it’s more easily removed with a Gaussian low pass filter, and perhaps is higher perceptual quality as well.
However, when we look at the thresholding tests, Fidussion does the most poorly by far. I believe the noise is able to do better as a whole because it doesn’t try to satisfy the thresholding quality constraints. So, if thresholding quality matters to your usage case, you wouldn’t reach for the Fidussion noise, but otherwise, it might look pretty attractive! Basically “Quality is as quality does”.
Overall, none of the textures seem to do very well when extremely sparse, like when <= 1 or <= 254. That is 0.004 and 0.996 in floating point. They all do pretty ok between 10 and 245 though, which is 0.039 and 0.961 in floating point.
VNC 1.9 and Tellusim seem to do pretty ok at the extreme sparse values. VNC 1.9 is not spatiotemporal noise, but Tellusim is. Tellusim doesn’t show as nice DFT in the middle range though. You can see the circle of suppressed low frequencies is not as dark.
In the end, I don’t really see that STBN is better than FAST when thresholded. I think I saw FAST in the extremely sparse zone and didn’t recall ever seeing STBN in the same situation, so it seemed worse.
One other thing these diagrams show though is that if you add temporal constraints to spatial noise, the spatial properties of the noise seem to suffer. I am not certain, but I think that is probably unavoidable – the more constraints you put on something, you eventually reach a saturation point where the constraints can’t be solved, or can’t be solved as well. It would be great if I’m wrong though!
FAST does let you specify how much weight to give the spatial filter versus the temporal filter when doing “separate” mode like this instead of “product”. It defaults to 0.5 which is a balanced weighting between the two. Maybe playing with that could give better results in some situations.
I’d bet there’s a way to make blue noise (spatiotemporal or spatial only) that solved the thresholding constraint better, maybe at the cost of making the overall DFT of the noise texture worse. If you are only ever going to use the noise for thresholding, you don’t need it to have good qualities for other uses.
to mean expected information entropy, but in other sources you’ll commonly see it as 
where 
is the event, and 
are the outcomes.
, we can calculate the derivative as 
. Here are those two functions graphed.
and wanted to know whether you should go left or right to get lower, the derivative can tell you. Plugging 1 into 
gives the value -4. A negative derivative means taking a step to the right will make the y value go down, so going right is down hill. We could take a step to the right and check the derivative again to see if we’ve walked far enough. As we are taking steps, if the derivative becomes positive, that means we went too far and need to turn around, and start going left. If we shrink our step size whenever we go too far in either direction, we can get arbitrarily close to the actual minimum point on the graph.
and getting the value 
. Without iteration, we found that the minimum of the function is at 
term of a quadratic is negative, then it only has a maximum, instead of a minimum.
that is a local minimum for x but a local maximum for y. The gradient will be zero in each direction, despite it not being a minimum, and the simulated ball will get stuck.
, a gradient is a vector of derivatives, where you consider changing only one variable at a time, leaving the other variables constant. The notation for a gradient looks like this:
, that means “The derivative of w with respect to x”. Another way of saying that is “If you added 1 to x before plugging it into the function, this is how much w would change, if the function was a straight line”. These are called partial derivatives, because they are derivatives of one variable, in a function that takes multiple variables.
.
.
.
.
.
.
