I'm Jon Olick. I make shiny things. I simplify.

I presented Sparse Voxel Octrees at Siggraph 2008.

Sunday, August 7, 2011

Voxels vs Displacement Mapping

Voxels on the left. Displacement mapping on the right.

What is being shown here is a pyroclastic sphere primitive. Link

This is a good example of the difference between a voxel technology, and a displacement mapping technology that the GPU manufacturers are pushing.

The DM tech is pretty obviously just pushing out parts and pulling in parts of the surface, making things look more like a wave function on a sphere.

The Voxel tech looks like a much more natural expression of the function.

Disclaimer: To be fair, both pictures are using voxels in the source article. However the right picture could easily have been accomplished with DM and does IMO represent the difference between the two approaches.

Saturday, July 30, 2011

What a 128bit addressing space is useful for...

What if you had unlimited storage capacity and it was fully redundant... and what does this have to do with a 128bit addressing space?

To answer that question, you have to look into how to implement a P2P Cloud Storage solution.

To make a long story short, every file sector gets an address - a very big one. Some P2P services use up to 160bits. 128-bits is good enough for this new purpose though.

What if every file, every document ever made was in this P2P cloud storage. And it could be referred to as naturally as having a pointer in your code. The OS would page in part of this data from the internet on demand.

This is what I would think of as the ultimate computer storage solution -- blurring the line between computer and internet - to the point of being indistinguishable. This blur between internet and computer is where I believe computers are headed... I can't wait. :D

A shame 128-bit addressing is probably 20 years away... I'll be old by then (by my current standards anyway). It will be neat to watch the incremental progress towards this though as the years go by.

A few questions that keep crossing my mind is - If the internet could be applied to computing in general, to the extent of running something as simple as notepad.exe. How would it be done? How would it be secure? Is that possible with the internet of the future which has 10-100 times the bandwidth and 1/10th to 1/100th the ping? Which brings up more questions, such as what are the limits of internet related technologies? How fast is it advancing as to be able to make predictions about where it will be. etc...

Sunday, April 3, 2011

Designing to make ATM Skimmers impractical

I was curious about how thieves make these things. Turns out you can buy ATM skimmers on online auction sites for $3000. They make them by manufacturer. So this got me thinking about what ATMs could do to make a skimmer impractical.

My first thought is to have 1000 different ATM front plates from each manufacturer. That would make most skimmers very expensive, but not quite impractical yet as they can just make a universal fit -- we can do better. If the shape of the card receptacle was easily identifiable by a human and able to match easily with a picture, then you could take advantage of the fact that a skimmer, no matter how complex never hides the display. You can use that to show a picture and have people manually verify the shape of the receptacle. If it is different, then there is a skimmer on top. While it would not eliminate skimming, it would make doing it incredibly expensive and unpractical to do for most thieves. The maker of the device would often be directly involved.

While this sounds all well and good, manufacturers would not like making 1000 different versions of their ATMs just to stop skimming. Implementation of that approach is unlikely and it doesn't solve the problem for millions of existing ATMs. Is there any other way to solve those problems?

Holographic stickers. If they printed out 10,000 different holographic stickers and put a different one right over the face plate, and then had people do the manual verification with a picture (for example a bunny, a squirrel, etc... easily recognizable to humans and you can have many hundreds if not thousands of variations). That would also serve the make impractical purpose for the most part. Its not as good as the former solution, but its a whole lot cheaper and can work on existing ATM machines with just a software upgrade.

At a minimum, you might even be able to not have the manual verification part and instead just have the holographic sticker with some special certification message. If it doesn't say ATM verified something or other, than its a fake. Having a sticker in the first place is a deterrent. Only risk without is somebody could rip off the sticker off the ATM and then use it on their skimmer. So that wouldn't be full proof.

Perhaps you could have a sequence of numbers on the sticker that you would have to enter before using the ATM. I would hate that, personally. It would work as well though and only work for that single ATM.

Friday, March 18, 2011

Know your SPU transposes - part 2

In this part of the SPU transposes series, we will cover 2 element transposes. Same format as last time.

AOS to SOA, 2 elements

4 input vectors of the format:

in1 = in1.x, in1.y, ?, ?
in2 = in2.x, in2.y, ?, ?
in3 = in3.x, in3.y, ?, ?
in4 = in4.x, in4.y, ?, ?

2 output vectors of the format:

out1 = in1.x, in2.x, in3.x, in4.x
out2 = in1.y, in2.y, in3.y, in4.y

I'll start with the simplest way to do it - all on the odd pipe. Then show some ways to do things differently to trade odd instructions for even instructions.

0 even, 4 odd, 3 shuffle masks, 10 cycles

InstructionsIn English
shufb t1, in1, in2, s_AaBb t1 = in1.x, in2.x, in1.y, in2.y
shufb t2, in3, in4, s_AaBb t2 = in3.x, in4.x, in3.y, in4.y
shufb out1, t1, t2, s_ABab out1 = in1.x, in2.x, in3.x, in4.x
shufb out2, t1, t2, s_CDcd out2 = in1.y, in2.y, in3.y, in4.y

1 even, 3 odd, 4 shuffle masks, 9 cycles

InstructionsIn English
shufb t1, in1, in2, s_AaBb t1 = in1.x, in2.x, in1.y, in2.y
shufb t2, in3, in4, s_BbAa t2 = in3.y, in4.y, in3.x, in4.x
selb out1, t2, t1, m_FF00 out1 = in1.x, in2.x, in3.x, in4.x
shufb out2, t1, t2, s_CDab out2 = in1.y, in2.y, in3.y, in4.y

4 even, 2 odd, 4 shuffle masks, 10 cycles

InstructionsIn English
selb t1, in1, in2, m_F000 t1 = in2.x, in1.y, ?, ?
shufb t2, in3, in4, s_aABb t2 = in4.x, in3.x, in3.y, in4.y
shufb t3, t1, t2, s_BAba t3 = in1.y, in2.x, in3.x, in4.x
selb out2, t2, in2, m_FF00 out2 = in2.x, in2.y, in3.y, in4.y
selb out2, out2, t3, m_F000 out2 = in1.y, in2.y, in3.y, in4.y
selb out1, t3, in1, m_F000 out1 = in1.x, in2.x, in3.x, in4.x

SOA to AOS, 2 elements

2 input vectors of the format:

in1 = in1.x, in2.x, in3.x, in4.x
in2 = in1.y, in2.y, in3.y, in4.y

4 output vectors of the format:

out1 = in1.x, in1.y, ?, ?
out2 = in2.x, in2.y, ?, ?
out3 = in3.x, in3.y, ?, ?
out4 = in4.x, in4.y, ?, ?

Again, I'll start with the simplest way to do it - all on the odd pipe. Then show some ways to do things differently to trade odd instructions for even instructions.

0 even, 4 odd, 4 shuffle masks, 7 cycles

InstructionsIn English
shufb out1, in1, in2, s_Aa00 out1 = in1.x, in1.y, 0, 0
shufb out2, in1, in2, s_Bb00 out2 = in2.x, in2.y, 0, 0
shufb out3, in1, in2, s_Cc00 out3 = in3.x, in3.y, 0, 0
shufb out4, in1, in2, s_Dd00 out4 = in4.x, in4.y, 0, 0

0 even, 4 odd, 2 shuffle masks, 9 cycles

InstructionsIn English
shufb out1, in1, in2, s_AaBb out1 = in1.x, in1.y, in2.x, in2.y
shufb out3, in1, in2, s_CcDd out3 = in3.x, in3.y, in4.x, in4.y
shlqbyi out2, out1, 8 out2 = in2.x, in2.y, 0, 0
shlqbyi out4, out3, 8 out4 = in4.x, in4.y, 0, 0

2 even, 3 odd, 4 masks, 7 cycles

InstructionsIn English
shufb out2, in1, in2, s_Ba00 out2 = in2.x, in1.y, 0, 0
shufb out3, in1, in2, s_Cc00 out3 = in3.x, in3.y, 0, 0
shufb out4, in1, in2, s_Dd00 out4 = in4.x, in4.y, 0, 0
selb out1, in1, out2, m_0F00 out1 = in1.x, in1.y, 0, 0
selb out2, out2, in1, m_0F00 out2 = in2.x, in2.y, 0, 0

2 even, 3 odd, 3 masks, 8 cycles

InstructionsIn English
shufb out2, in1, in2, s_BaCc out2 = in2.x, in1.y, in3.x, in3.y
shufb out4, in1, in2, s_Dd00 out4 = in4.x, in4.y, 0, 0
shlqbyi out3, out2, 8 out3 = in3.x, in3.y, 0, 0
selb out1, in1, out2, m_0F00 out1 = in1.x, in1.y, 0, 0
selb out2, out2, in1, m_0F00 out2 = in2.x, in2.y, in3.x, in3.y

Next post...

... 3 elements

Thursday, March 17, 2011

Know your SPU transposes

It has come to my attention that this is some needed and useful information to have. Too useful to keep to one's self. At Naughty Dog, some years back, Cort Stratton and I compiled a pretty comprehensive list of transposes. Its unbelievably handy to have on the fly as you need it. I've reconstructed the transposes as best I can and put it up here for your general use. Enjoy!


There is more than one way to skin a cat. When converting from AOS to SOA and back there are many variations. How many instructions you have available to schedule in your even/odd pipes, how many spare registers you have to spend, and the latency of the combination of instructions used will dictate which you should use.

The goal is to first find all variations where you can trade even for odd or odd for even instructions -- and minimize the number of registers used in the process (including shuffle masks used).

Shuffle Masks
To specify shuffle masks, I'll use A-D,0 to specify the element 1 through 4 in the first parameter and a-d,0 to specify element 1 through 4 in the second parameter. '0' is special in that it means put a zero in the output for that element.

For example, s_ABab would take the first 2 elements in parameter 1 and the first 2 elements in parameter 2 and put them side by side into the output register.

Example - AOS to SOA, 1 element - 0 even, 3 odd, 1 shuffle mask, 9 cycles
Lets first consider the simple case of 4 input registers, where we are interested in combining the first element of each in(1-4) register into a single out register.

InstructionsIn English
shufb t1, in1, in2, s_ACac t1 = in1.x, ?, in2.x, ?
shufb t2, in3, in4, s_ACac t2 = in3.x, ?, in4.x, ?
shufb out, t1, t2, s_ACac out = in1.x, in2.x, in3.x, in4.x

Example - AOS to SOA, 1 element - 1 even, 2 odd, 2 shuffle masks, 7 cycles
This variation on the above splits up the even/odd pipe usage a bit at the cost of more masks.

InstructionsIn English
shufb t1, in1, in2, s_Aa00 t1 = in1.x, in2.x, 0, 0
shufb t2, in3, in4, s_00Aa t2 = 0, 0, in3.x, in4.x
or out, t1, t2 out = in1.x, in2.x, in3.x, in4.x

Example - SOA to AOS, 1 element - 0 even, 3 odd, 0 shuffle masks, 6 cycles
This example converts back from SOA to AOS. Still working on 1 element.

InstructionsIn English
shlqbyi out2, in, 4 out2 = in.y, in.z, in.w, in.x
shlqbyi out3, in, 8 out3 = in.z, in.w, in.x, in.y
shlqbyi out4, in, 12 out4 = in.w, in.x, in.y, in.z

Know a transpose that I didn't list? Find a better one? Post in the comments and I'll update the post.

Next post...
... will be on 2 element transposes.

Monday, February 28, 2011

Designers should Learn to Code, Even if Poorly

2,500 years ago, a Greek writer told us something about creating software: Thucydides wrote, "The society that separates its scholars from its warriors will have its thinking done by cowards and its fighting done by fools."

The same is true for companies that separate their designers from their engineers. The most important trait a team can have is empathy. Without it, the engineers will not care, and the designers will not be realistic. When companies complain of specs and code being "thrown out the window", a lack of empathy is to blame.

The best way to create empathy as a designer is to make a prototype. It meets the rest of the team half-way and gives you a sense of what's hard and what's easy to implement. Having thought through the edge-cases and being able to speak an engineer's language gives you street cred. You don't need to be a great coder, but you should at least be able to get your idea across in a scripting language.

To design is to inspire participation. To do that you need to be respected. For that you need to be a designer-coder.

Friday, February 4, 2011

High Resolution Textures -- The Field Guide

The options:

Static Texturing
No dynamic loading. Just use higher resolution static textures. Standard stuff.
- VRAM limited

Dynamic Texturing
Dynamically load mips (Unreal 3 style).
+ Allows for much higher resolution
- Still ultimately resolution limited.
- Sometimes implemented with a feedback pass to a low resolution buffer.

Virtual Texturing
Dynamically load parts of textures.
+ Use as high of resolution textures as your heart desires.
+ Static memory footprint
- Sampling the virtual texture is slightly slower than Static or Dynamic texturing.
- Bi-linear filtering. (Tri-linear is possible, but requires more work.)
- Requires an extra rendering pass with most implementations (for the feedback of what pages to load)
- Problems with transparent materials. *****
- Popping mips when the disk streaming doesn't keep up very well with the game. *

Unique Virtual Texturing (AKA Mega Textures)
For each mesh in the world, allocate a portion of virtual texture space for that mesh and then bake in any lighting and diffuse information.
+ Use as high of a resolution texture as your heart desires.
+ Static memory footprint
+ Infinitely complex lighting algorithms.
+ Can bake in decals to allow an infinite number of them. ****
- Bi-linear filtering. (Tri-linear is possible, but requires more work.)
- Requires an extra rendering pass with most implementations (for the feedback of what pages to load)
- Iteration time is very slow
- Popping mips when the disk streaming doesn't keep up very well with the game. *
- Lighting is mostly static. **
- Requires massive disk space. ***
- Some games may have a world that is too big for UVTs -- exceeding floating point precision.
- Problems with transparent materials. *****

* The popping can be mitigated through "blending" of tiles as they load. However this requires using RGBA uncompressed textures for your physical tiles -- making texture reads slower and increasing memory requirements.

** I toyed around with animating virtual textures, so that you could have looping or one off lighting animations. Is a lot of extra space, and streamer had a hard time keeping up with the animation. Not impossible to pull off though, so something to keep in mind.

*** The disk space is typically reduced by both compression, and not storing the higher mips for areas that are never seen in game. If you happen to predict incorrectly, they just see a blurry texture.

**** Watch out for problems with changing the meshes after the baking process. Causes headaches.

***** VT typically uses a feedback rendering pass to a low resolution buffer to tell what to load and what not to load. This is typically rendered opaquely. The common work around is to render transparent materials using Standard or Dynamic texturing.

Where is the sweet spot?

Standard texturing is the easiest to implement.

Unique virtual texturing offers the best results.

But -- Virtual Texturing takes the prize.

While Unique Virtual Texturing is great, it doesn't work for every game (your world size may be so large that it is unrealistic or you require a day-night cycle), and the bake times for lighting and texturing can be horrendous -- making fast iteration very hard.

Living Blog Post
I'll be updating this blog post from time to time as reference for myself and others. If you would like to see something added or corrected, send me a message or post in the comments.

-- Kind of wish this was a wiki or something. --

Monday, January 17, 2011

Business and Ethics

I've been reading a book called the Ten Day MBA

Its got a pretty interesting chapter on Ethics...


The proponents of relativism hold that we can't decide on matters of right and wrong, or good and evil. Things are rarely black or white. There are so many shades of gray. Relativism proposes that ethics are "relative" to the personal, social, and cultural circumstance in which one finds oneself. Relativists are not torn by ethical dilemmas since they do not believe that truth can be discovered through soul searching. Professors teach relativism so that students may guard against it. To understand relativism, you need to recognize its four forms.

Naive Relativism
Naive relativism holds that every person has his or her own standard that enables him or her to make choices. No one can make a moral judgment about another person's behavior. So many variables affect behavior that an outsider cannot possibly be privy to all the elements that went into making a decision. Therefore, an executive at Borden is not equipped to make a moral judgement regarding the actions of the CEO of Nestle, whose corporation is possibly selling harmful baby formula in developing countries.

Role Relativism
Role Relativism distinguishes between our private selves and our public roles. These public roles call for a "special" morality which we separate from the individual making the choices. The president of a fishing company may personally dislike the incidental killing of dolphins in his company's tuna nets, but as an executive, he must not let his feeling interfere with the best interest of the company.

Social Relativism
Social relativism is akin to naive relativism. People refer to social norms to render ethical judgments. "Industry Practices", "club rules", "professional codes of conduct", and "accepted practices" are the cop-outs of the social relativist. In the produce industry, it is "industry practice" to ignore child labor laws and employ small children to work in the field and miss school.

Cultural Relativism
Cultural relativism holds that there is no universal moral code by which to judge another society's moral and ethical standards. If a whole culture holds certain beliefs, how can an outsider sit in judgment? "When in rome..." The concept of cultural relativism becomes more important as companies compete globally. Multinational corporations often follow local laws and customs that may violate ethical standards in their home countries. Discussions about aparthied revolve around issues of cultural relativism. Adopting a cultural relativist philosophy, a multinational corporation might have justified its participation in South African gold and diamond mining activities despite the employment of "slave" labor in the mines.

In some instances US corporations and citizens are barred from adopting the host country's business practices. In some countries it is ordinary business practice to pay bribes to get favorable treatment from businesses and government. The Foreign Corrupt Practices Act of 1977 outlaws overseas bribery.

The relativism concepts provide MBAs with an awareness of and a way to guard against inaction on ethical and moral issues. They provide a framework to go beyond currently held beliefs and patterns of behaviors.

Natural Law
Natural law serves as a guide to some who believe that the "right" thing to do is revealed in nature or the bible.

Utilitarianism holds that an action is justified if it provides the greatest benefit for the greatest number of people.

Universalism propounds that any action is condonable if the motive behind the action is good, since the results of a person's actions are so often not in his or her control.

My Personal Take
What is ethics?
Ethics, in my opinion, is what you do when you think that nobody is watching.

People are easily corruptible. Money and more specifically the love of money, really is the root of all evil. To justify putting an additive into a baby formula because it saves you money when it actually hurts the people your giving it to.. is morally wrong. I don't care if you think that because it costs less you can sell it to more people, and thus less babies go hungry. Its evil and wrong to knowingly sell things that hurt other people. Find some other way to make more money. Sure the road is harder, but the payoff is that everyone is better -- Not just the company. Doing what is ethical is doing the right thing, and saying no to doing what is wrong just because it is easy.

Nobody is perfect. Everybody makes mistakes. Sometimes, you might find yourself doing something that you think you shouldn't be doing. Making the choices which correct those things after the fact takes courage. Courage to face yourself in a mirror. Do it though. For your self, your family, your community, and your world.

Saturday, January 8, 2011

This is why Facebook is Valuable

The data plot above is google.com, the data plot below is facebook.com. Google has a market cap of 250 billion. What the investors are betting on, is that with all that juicy information they get from users, they can make uber targeted ads that people can't help but click. Basically achieving the same click-through ratio that searching enjoys, about 1 in every 100 people (sometimes better). Now, I'm not really sure if they can achieve that ratio or not, but I do know one thing -- I hardly use facebook anymore, but I have been using google consistently for 11 years. I don't think I'm alone in that. Maybe that doesn't matter? Maybe they figure the can get enough of the world hooked on facebook, it doesn't matter that they don't get everyone hooked on facebook. Who knows. But anyway, yes it does look like a good investment. The stock will likely triple after the IPO. I would suggest to buy it until the honeymoon period wears off, then sell like crazy.

Friday, January 7, 2011

Facebook is worth 50 billion

You've got to be kidding me. This is obviously just investor valuation overload. Goldman paid 450 million for less than 1% of Facebook. Really....

So facebook has 500 million users. That means each user is valued at $100. And thats assuming that each user is an active user, which is not the case. The real valuation may be more like $250 - $500 per active user. That just doesn't make sense to me. Their primary revenue source is advertising. You get about $1 for every 1000 views in non-search advertising. If somebody visits their Facebook page once every day, then each user is worth $0.365 per year. To recoup the best case of $100 per user, that would take 300 years or so. As in, impossible. I don't know what those investors are smoking, but it must be Zuckerberg's !@#$.

In other news, Apple is worth more than Google. Seriously, and not by a trivial amount either.

Something is wrong with the world.

Sunday, January 2, 2011

Next generation graphics

While there are many directions for video games to improve in the future. Animation being a big one. People are looking for things to do for graphics. First, avoiding the uncanny valley in next gen games may be a big problem. In general high level though (probably mostly obvious)

- Higher resolution textures.
- Higher resolution geometry.
- More world clutter and detail.
- Enormous worlds with little to no loading.
- I'd like to see water reflections that are actually reflections and not just cube-maps.
- Some people think that many more dynamic lights (1000's in a scene) are the future of video games.
- Soft shadows via variance shadow mapping or the like.
- Hair on video game characters will get a huge upgrade. No longer will characters look like they haven't showered for 2 weeks.
- Smoke using fluid simulations (this would be awesome)
- Geometry LOD is going to be a serious problem (even more so)

If you were to stick with triangles, then you would probably do some kind of subdivision surfaces.

There are other options though like voxels which can give triangles a serious run for their money. When properly optimized, they can provide very consistent frame rates irrespective of world detail.

Voxels aren't all static either. Lattice skinning can be used for characters, as well as I've seen some research in the area of dynamic KD-tree generation. There has also been some research in completely dynamic voxels, such that the world is actually changeable real-time. Leaving a foot-print in the sand actually leaves a foot-print there. Possibly permanently depending on how you implement it.

You could also do interesting procedural stuff if you had the compute power, where grass could grow back over craters over time, etc... Other benefits of voxels are the sampling you can do to do motion blur, depth of field, etc stochastically.

You can guarantee a framerate by doing progressive rendering of the frame. Stopping at a certain ms. That gives a lot of freedom to the content people to make the world how they see it in their imagination and no longer be limited by what hardware can provide.

All very interesting stuff, and I'm sure its only the tip of the iceberg.

However... things are not without its challenges. The PS4 may make the life of voxels a little harder. You will likely have to write a custom ray-casting solution for the PS4.

I'm sure many people will continue to use triangles. Hell, even I might. I'm a reasonable guy and will likely measure both approaches and pick the best one for the task at hand. However, ignoring voxels as an option seems kind of silly to me. The game developing public needs a good example implementation of voxels in order for it to really take hold in any sort of realistic way. There is an open source one from NVidia which has lots of ideas pulled from my stuff, however their solution is not really prime-time ready. For example, it doesn't stream from disk so you can only do what you can fit in memory. I don't really have time to write a public implementation of voxels, or to really contribute anything significant to the nvidia one. I'm just too darn busy right now. Who knows though, maybe I'll have time in the future.

Ok, enough voxel talk.

Another big challenge is going to be doing things for 3D displays. I don't have a lot of experience with 3D conversions for games yet, but I will very soon. I'll write more when I know more. Doing so in a deferred renderer seems like it might be a bit troublesome.

I'm sure there is much more that I could chat about here with next gen graphics. Taking each of the previous things in detail. Maybe I'll do a dedicated post to each one.

Saturday, January 1, 2011

Playstation Brain

It would be very interesting for a next generation console (I'm looking at you Sony) to do a brain-wave controller. It would be different enough from both Nintendo and Microsoft to stand out. Of course the technology itself is incredibly primitive at the moment, but nothing a massive r&d push can't fix. :) How awesome would it be to play a game by not moving at all?