Sanders' blog

HDR dithering

2012-02-07T12:53:00.002+01:00

So I was just busy implementing HDR in my little experimental renderer, adding support to load wavefront .obj/.mtl files and started using the Crytek sponza scene. And at this point I was playing around with the lighting a bit and then I noticed this:

Original HDR screenshot (contrast increased in image to illustrate banding)

Loads of ugly bands in poorly lit areas. And at the moment I'm using really high precision buffers everywhere (16 bit floats), so the first thought that popped up in my head was .. how can I possibly be getting precision artifacts here? So I take a screenshot and start comparing pixels; turns out there's only a difference of 1 between the bands, so it's not a precision problem; my monitor is simply poorly calibrated! (I really thought I calibrated it properly! Interestingly enough it looks perfectly smooth on my other monitor) So my next thought was.. well most people out there will have poorly calibrated monitors, so is there a way to improve on this? Yes there is! Dithering! I remembered that in the good old days of 4, 16 and 256 color video modes people used to use dithering to simulate smooth crossovers from one color to another, and the higher the resolution, the better it worked. Long story short, I added some dithering to my shader and it worked like a charm:

HDR with dithering (contrast increased in image)

And finally here's the same screenshot without it's contrast increased:

HDR with dithering (original contrast)

Now when I turn contrast and brightness all the way to the highest levels on my monitor, it still looks nice and smooth.

Update

@renderwonk (Natty Hoffman) told me on twitter:

Pixar dither when quantizing. See "Mastering" section of "Color Pipelines..." course here instead of adding 0.5 and truncating to quantize, they add rand(0,1) and truncate

So I just tried using random noise instead of dithering, and it looks better, although obviously more noisy. (A screenshot wouldn't do it justice I'm afraid) When the noise changes over time it visually blends together. It makes the color transitions much smoother and all kinds of faint details, that where simply a single color before, end up being more visible.

Unlike Pixar I made the noise scale somewhat with the amount of light, this made the noise a bit more visible (especially on a monitor with a very high contrast & brightness, but not too much) but it also smoothed out the more brighter transitions. Interestingly enough the noise looks similar to the noise that you would see when you're in a poorly lit environment. Although the noise/dithering won't scale the extend of the contrast of your display device, it does extend the perceived color precision.

Physical Based Rendering

2012-01-29T10:42:00.001+01:00

Lately I've been playing around with Physical Based Rendering (yes, I'm late to the party). It took me a while to get it working because I kept getting weird results that looked more like caustics than surface roughness. I checked the math again and again, looked up as many source materials I could find to compare them to my implementation (just in case there where some errors in some articles), but couldn't see what could cause these weird artifacts. The thing is, when I rendered the light on a sphere it looked perfect, but when I rendered it from the inside of a box it looked completely wrong! So I started to check all my inputs and they all seemed fine ... until I discovered that my lighting position was inverted. Wut? How the hell? It turned out that the wrong light position caused my half way vector to be, well, something else entitely. And that combination made it all look plausible most of the time and completely threw me off course.

I'm currently using the GGX microfacet distribution, from the Microfacet Models for Refraction through Rough Surfaces paper. Here's what it looks like with some random textures and lightwave models borrowed from Doom 3 (don't sue me!) for testing purposes.

Some random thoughts about gloss / roughness maps & normal maps

While I was working on all this I realized that while roughness maps describe surface detail at the micro level, normal maps describe surface detail at the macro level. This made me think that, when generating normal map mip-maps, that lost normal details at lower resolution could be put in the gloss map instead. Of course this probably would work better with an anisotropic BRDF (directional-roughness) compared to an isotropic BRDF (uniform-roughness). Since both of them seem to be connected, it may imply that there might be a way to combine the two in a single thing. ("anisotropic normal maps"? lol)

This would probably work a lot better (especially with isotropic BRDF's) if you generate normal your maps from heightmaps, and create the gloss and normal maps mip maps from the mip-maps of the heightfield. The roughness would be calculated from all the height variation within a lower resolution mip pixel (compared to the highest resolution mip), while the normal would simply be calculated from the lower resolution mip directly. Maybe some sort of min-max mipmap approach could be used for the roughness. Of course you'd still have to take into account that the further away you are from a gloss map, the smoother it'll look. (disclaimer; I haven't actually tried any of this)

Just a quick update

2012-01-25T10:15:00.002+01:00

The last couple of months I was entangled in some stuff that I can't really talk about, so I didn't have time to post on my blog, or work on any of my tech experiments. (Not to mention that so many interesting tech stuff happened in those months, Rage was released, Doom 3 source code was released etc.) However now that's all behind me, it's now my intention to blog more regularly again now that I can.

In the meantime, here are some things that I've been messing around with lately.

I created a simple Minecraft renderer, which unfortunately slowed down to a crawl due to the recording software but which is silky smooth without it. (I really need to upgrade my aging machine!!) The light is simply interpolated between the tiles which creates an interesting GI kind of effect. It doesn't correctly take occlusion into account, so that's an area of improvement. Also it's very close to brute force at the moment, with chunks only frustum culling (and of course back-face culling) being used right now to decrease the number of polygons. Transparent blocks are sorted on a chunk level, but are currently incorrectly sorted within the center chunk. The only way to do that is to split the center chunk into 8 pieces and render those separately. In fact, all chunks that lie in a straight line with respect to the center chunk would need splitting. That said, I'm not so sure if I'm going to spend much more time on this though.

Of course like everybody else and their cat, I created my own Doom 3 source code branch, with GLSL shader support, where I'm busy replacing the Doom 3 lighting model. Right now it uses a physical correct lighting model, although the lighting isn't yet properly normalized. I also wrote a small C# library to load LWO files, which is still very rough in it's current form, but my intention is to improve on it as time goes by (any help improving this lib is appreciated!)

Deferred rendering with virtual texturing

2011-08-16T14:09:00.004+02:00

Just a random thought.

I had thought about a deferred rendering / virtual texturing approach before where instead of storing the normal, albedo etc. in a g-buffer you'd only store the texture coordinate + texture derivatives (+ z position & surface normal, unless you're storing normals in worldspace which is possible for static environments with virtual texturing). But I quickly dropped that idea back then because you'd store roughly the same amount of data so it wouldn't gain you much. But this morning I was thinking... If you have a lot of overdraw and/or if you render lots of small triangles (especially if a lot of them are smaller than 2x2 pixels) it might pay to have a really simple shader at the g-buffer phase, and then do the actual texture lookups later on, when you're just rendering a single full-screen triangle. It might work, it might make no difference, it might be worse. I should definitely try it some day.

Carmack Quakecon 2011 keynote

2011-08-06T13:45:00.005+02:00

So I saw the QuakeCon 2011 keynote by John Carmack..

... and I figured I'd jot down some notes:

80 degree field of view in Rage, pages might be loaded for entire 360 degree view?
Loading full pages that occupied 1 pixel on screen hurt a lot in Rage.

Single 4k x 4k texture wasn't enough.
Ended up using multiple 4kx4k textures on consoles.

Second buffer of cache, uses just about all memory on console, shared with audio.
Transcode pipeline comes after cache, so pages are not cached uncompressed.

Blu-ray is worse in latency than DVD.
Pages are cached on HD on consoles.

Carmack said better solution would've been split page cache in low-detail and high-detail pages.

1 thread reading from DVD
1 thread reading from HD
"additional threads (plural!) doing analysis of the feedback buffer"
"a bunch of threads doing transcoding"

HD-photo derivative compression, not using dct based compression.
30% better compression, requires twice the processing power.

Rage is running on intel hardware?!? (but not at 60hz)

Rage blurry close up, newer titles have more detail up close.

Biggest levels are 128kx128k, dynamic characters are 64kx64k.
Wasteland are 14 pieces, various sizes from 32kx32k to 128kx128k.

He mentions that "the wasteland doesn't fit into one 256 x 256",
Did he mean 256k x 256k?
Considering he specifically said that number I'm assuming that's some sort of maximum.
256k / 128 = 2k. GPU side page texture is 4k x 4k.
Are they using more page-tables?
Are they swapping page-tables (pieces) in and out according to the area/level you're in?
or maybe it's just not a hard limit, but rather a soft limit.

About 300 - 500mb per 'level'.

(My Q4 level conversion is 1.5gb, DXT compressed)

Source data giant 256000*256000 texture
64 gigatexels of source data.
Terrabyte of source art.

100 gigabytes of texture data (uncompressed) used in Rage.

Large ammount of profiling, removing pieces that aren't visible (roofs etc.)
(Clearly works better in outdoor levels, compared to my experiments with Q4)

This made me think of .. (not mentioned by carmack)

OnLive/Gaikai

The advantage of making a game purely for OnLive/Gakai is that the whole game runs on their servers and the images &amp; audio are send to the player over the network, the player only sends their controller inputs.
Obvious latency issues aside, which can be helped somewhat by putting servers all over the world, this has a lot of advantages for publishers and developers. Piracy and cheating being impossible being one example, not being constrained by disk space or hardware is another.

A game like rage could run with full detail, maybe even with dynamic lighting, if it had a good server using an OnLive/Gakai approach. In fact, gameplay could be run on separate severs compared to the actual rendering, which could be done in a more render-farm sort of way.

The render servers could hold a large chunk of the texture data in memory and keep the rest on SSD.
Oddly enough multi-player / MMO's become more attractive than single player games because if all players play in the same world lighting can be cached into the pages for all players, allowing the render farm to separate rendering lighting from rendering camera views. The same goes for anything else that's shared between the players, like physics etc.

Scary to think about scaling this up to world of warcraft like sizes though, from a technical POV.

Virtual texturing, brute force page VSD

2011-07-01T11:37:00.001+02:00

So I had a little bit of time between things to try out discovering which of my pages are potentially visible at any given time when moving around in my test scene (imported from quake 4).
At first I was amazed, my 1.5gb virtual texture file had reduced to about 50mb! I wanted to tell the world!

But no, that was a bug. Crap.
(Good thing I double checked!!)

When I got it working properly, it only removed 9 pages :(
It took about 5 minutes to process the entire Quake 4 level, 2 minutes to create the virtual texture file.

That said, in my current implementation I'm reusing the pages across surfaces, although they're still unique on the GPU side of things (so decals can still be added in the virtual texture), so it might be a bigger improvement when all pages are unique. Besides that I used the gathered information to sort all the pages according to locality and it helped reduce latency when loading the pages.

Considering that I'm reusing pages (hell, even the texture coordinates are created carefully as to maximize reusing the pages) I'm actually surprised that I only managed to get rid of 9 pages. I guess a lot of the 'reusing the pages' idea gets wasted when pages are combined into higher MIPs, which automatically makes them less unique. It would be better to store the lower resolution pages, that make up the lower resolution MIPs, separately. That way the virtual texture file could never be larger than the combined source textures. It would also allow more fine sorting (of sub-pages) and allow us to downscale higher resolution pages into a MIP, and hopefully removing the necessity to loading some pages. But it all gets awfully complicated real quick.
And I'm not sure how much that would help with true unique texturing.

The quake 4 levels are really worst cases for virtual texturing considering that the texture placement is made to minimize the number of textures in the level, not so much minimizing texture area and not worrying about the source of the texture. So many tiny pieces of geometry are rendered with unique pages, which could all be combined into single surfaces. So I really should try to either combine all the surfaces and re-project the textures onto them, or create geometry from scratch with a more virtual texture friendly texture layout.

Game Development Tools source code went up

2011-06-09T08:21:00.001+02:00

The source code for the book "Game Development Tools" went up,
and you can find all the source code, including my CSG article, here!

Winforms Graph library

2011-06-03T16:38:00.003+02:00

For some strange reason I was blocked on all projects I was working on, so I had a little time to work on something else. I've encountered many situations where a simple graph editor would've made my life a lot easier, yet I couldn't find any good and simple libraries to help me out. So I figured I'd make a simple graph library myself and make it open source to (hopefully) help whomever who needs similar tech in the future.

There are still a couple of things I want to add to this such as support for different colors of nodes/connections and maybe drop-down thingies. Anyone is welcome to contribute. Anything is open for discussion. I should mention, however, that I'm not interested in making this a super uber-leet library that includes everything including the kitchen sink. I'd rather keep it small, simple & flexible.

MIT license. Git repository can be found here.

Yes, I used my own image as an example.
It's just my weird sense of humor.

PS.
I should be getting a copy of the book soon, yay!
Hopefully that'll mean the CSG code will be online soon too.

Random thought

2011-05-24T09:16:00.000+02:00

This morning I suddenly was thinking, would it be possible to have some sort of hive mind server-client architecture working on top of a peer to peer network?
Meaning that the hive-mind (all or clumps of clients) would act as a sort of referee when it comes to gameplay. I can imagine that it would be pretty complicated, but it would remove the need for dedicated servers and possibly help avoid cheating ...

Just another one of my random thoughts ...

Busy busy busy

2011-05-02T13:21:00.003+02:00

For a long time me & Matthew have been working on an article on "real-time constructive solid geometry" (CSG) for the Game Development Tools book. We finished the article somewhere at the end of march, and last week we finished the demo. It's been a really interesting experience, writing an article, but it sure was a lot more work than I thought it would be! It really gives me a renewed respect for authors in general! Anyway, the source is going to be put on the book's website eventually, I'll post a link here when it's up, and eventually put it on git (when I can find time in my way too busy schedule). The article itself is basically a better written version of what I already wrote down on my blog, but with a couple of additional details, improvements and discoveries that we've made along the way!

While making the CSG demo I had a bug in my polygon splitting code (obviously fixed now), which looked kinda funny :)

Other than that I've been really busy with my regular projects, and a super secret IOS game which I've been working on with my friends at Limbic and Hidden Elephant. Can't wait to show some stuff from the game!

Unfortunately, all this means that I haven't had much time to work on my other experiments :(

VT progress

2011-02-14T20:15:00.002+01:00

Last weekend I spend a little more time on my VT experiment and added normal, specular and alpha channels to pages, all of which area only stored when they're actually used. I've also added alpha testing support, since id tech 4 makes heavy use of it, which made me split the geometry into two stages. I'm not entirely sure if it's a good idea to support alpha testing in a real world virtual texturing engine (especially when an engine is using deferred rendering), so I might remove it eventually.

My short term goal is to render this into a G-buffer and do some simple deferred rendering (just a naive, simple deferred rendering implementation will do for the time being).

I've also spend some time optimizing my import pipeline, and each stage (a separate executable) only takes about a minute (at most) except the stage that creates the virtual texture itself. That final stage doesn't scale very well and it can go from a minute to 30 minutes depending on the size of the virtual texture. This is mostly because of the part that creates the mipmaps for each page, this is mostly because I'm not using simple box filtering but using some more better quality solutions instead.

I'm considering just using pre-mipped source textures for this since it would bring back the vt creation time to basically the time it take to write it to disk, but it would snap all my pages to 128x128 coordinates, which could create a lot of additional wasted texels in the worst case.. It would also be a temporary solution since eventually I want to re-parameterize the geometry and render the textures into this newly created texture space. It won't allow me to re-use as many pages as I am now (which makes it possible to store a 6gb virtual texture in 500mb, uncompressed) but it causes less wasted texel space, simplify geometry and most importantly help with page locality (fewer pages visible at the same time), which would help latency wise.

Infinite virtual textures

2011-02-01T12:57:00.003+01:00

I've been playing with the thought that the page table of a virtual texture could itself have a higher level indirection table, allowing us to create much bigger virtual textures by dynamically allocating huge virtual texture blocks. This would make geometry streaming simpler with virtual texturing since you wouldn't need to have the entire worlds' page table in memory at once and can help avoid precision issues when page tables get too big.

The texturing on geometry would not be able to cross the edges of these higher level blocks, but that would be fine because the dimensions of these blocks would basically still be really big, much bigger than you'd ever want polygons to be. Also, we only really care about the actual texture pages that we store on disk and loading them quickly enough, if page tables have huge empty spaces, it doesn't matter because they don't actually take any space on disk, or any substantial space in memory. So if we have lots and lots of additional page table space, we gain a lot of freedom in how we built and update our virtual texture, and how we place our model/level textures within our virtual texture. We don't need to pack it as tightly anymore and we could consider using other metrics to place our textures in our virtual texture, for example proximity of the geometry on which the texture lies.

Obviously we do not want to have an extra indirection in our pixel/fragment shaders, which would be terribly wasteful, but we could easily use our vertex shaders for that, considering that geometry wouldn't be allowed to cross these higher level blocks. Another way could be that suppose you can load X page table blocks in memory at the same time, and each page table block would have a fixed position within the page table then you wouldn't have to use a vertex shader either. But you'd have to guarantee that no two page table blocks with the same position would ever be loaded, which might be fine if you have enough block positions.

On another note I've been looking at Assimp (I know what you're thinking, but no, that stands for Open Asset Import Library, you pervert) and it's pretty cool. I couldn't get the .net library to compile, which is a shame, but I've been using the C compiled command line tool to convert all the Lightwave files in quake 4 into an easily parsable XML format, which I then parse and use in my, oh so neglected, virtual texture experiment. It really makes everything feel more like an actual level, instead of random geometry with big gaping holes in it ;) Along the way I discovered that somehow my geometry was swizzled across an axis compared to quake 4, so I fixed that. In the process of getting all the geometry in the level I've had to parse all the skin, guide, mtt (material type), and def (entity definition) files (next to all the mtr (material), map and proc files that already was parsing before), which was a big adventure in figuring our how the id-tech 4 technology worked from a data point of view. Certainly gave me renewed respect for it's flexibility, despite the engine's age.

One of these days I'm going to put support for all the texture and door animations in my little demo (well, it's actually starting to become a little engine of sorts), and put in proper support for texture blending. And brute force page VSD as a pre-process (to determine if a page mip can actually ever be visible). And fast texture compression. And lighting obviously. And physics. And maybe it's not really an engine after all :)

Static analysis of gameplay

2010-12-21T10:37:00.001+01:00

Last night, couldn't really sleep, and my mind somehow landed at Fallout 3 and how complex a game like that is. It must've been an QA nightmare to test a game that has so many ways to play, so many different quests which may or may not be compatible with each other.

So I was thinking, what if game developers had a sort of editor, where they can see all the triggers in the game and their relationships between them, and have some sort of static analysis going on there to make sure you're not accidentally creating impossible situations.

In this editor, every trigger would have some 'hard' prerequisites, some of these would be added automatically from the trigger itself 'trigger will be triggered when you have object X and walk into region Y', and others would be implicit 'you can't get object X unless you finished quest Z', which would mean that all the prerequisites required to complete quest Z are automatically added to the trigger. Less quantifiable rules, I call them soft' prerequisites, could be added manually, for example 'Player must have strength X to reach this trigger'.

The difference between soft and hard prerequisites is that hard prerequisites would be checked at runtime (indirectly or directly) and soft prerequisites would only be used to check for situations where you don't want your average player to get stuck, but a good player might still be able to get through it. Each of these prerequisite rules would be either a boolean true/false 'do you own object X' or a simple comparison 'is your health > Y'.

Another idea I had is that the game's navigation meshes (which presumably are also the exact areas that the player can traverse) are divided into regions, and these regions are defined in such a way that you can get to anywhere from anywhere within a region without crossing a trigger, and the only way to leave a region is through a trigger. Triggers that have a location in the world are then associated with one or two regions (depending if it's a doorway or not).
Using this information we can then do some sort of flood fill where we start at the players' starting location, and while we go from region to region, we remember the prerequisites that are required to go from one region to the next and add them to the the triggers we encounter.
We actually have to do that for every possible path taken, skipping identical paths and avoiding loops. This can quickly become pretty complex, but it wouldn't have to be done in real-time or even all the time.

Regions can also be used to detect situations where a player jumps down from region A into region B, which he can't possibly get out anymore (nor finish the game from that location). (because, for example, the prerequisites of region A are in direct conflict with region B)

In the end we'll end up with basically a big expression tree, which can be simplified at every iteration. This expression tree can then be checked for conflicting expressions (for example, to trigger a certain trigger 'apple must be eaten' AND 'apple must've been thrown in bottomless pit'), and be shown to the game designer who can then check if it makes any sense ('you can only finish the game if science = 100'). The game designer could even do a sort of stack trace to see how the current expression tree was created.

I wonder if anyone out there has ever attempted to create something like this, it's basically a gameplay unit test of sorts..

Another virtual texturing thesis!

2010-11-09T10:17:00.001+01:00

I'm still recovering from an insane amount of deadlines, and in the process I neglected my blog. (so sorry! *cries*)

Anyway.

Some time ago I received an email from Julian Mayer about the thesis he wrote about Virtual Texturing, but until now I hadn't had any time to actually take a look at it. His thesis is a comprehensive list of all the (publicly known) virtual texturing implementations and their implementation details, combined with his own test implementation and performance testing and heuristics.
Considering it's size and the amount of details, Julian must've put an insane amount of time and effort into it!

It's well worth the read, if you're interested in virtual texturing you should definitely check it out!

The only criticism I have for his thesis is that he measured his timings in fps instead of ms, ironically he mentions in his thesis that ms is a better metric, which makes me wonder why he didn't just use ms instead ..

Also, he mentions that the borders of the pages need to be stored with the pages, which isn't true. As I mentioned before you can create the borders from the pages you already have in memory, at the cost of a little bit of extra bookkeeping and copying of textures fragments.

Another interesting thing he mentioned is the idea to have some sort of PVS for pages, something I've been thinking about as well (I may actually have mentioned something along those lines before). In J.M.P. van Waveren last presentation about virtual texturing he mentions that they do some brute force page visibility determinations to determine which MIP levels of which pages can possible be visible to the player, and which ones cannot.

I imagine they do this by rendering the scene in all directions from all points within the area where the player can walk, jump & fall, obviously with a minimum distance between the points. This way you basically know which pages are visible from each point in the map and theoretically, after massaging this data somewhat, you could create a system where you can figure out which pages you'll (potentially) need soon, and which pages can safely be discarded from the cache. For moving & dynamic objects the same concept can be used, except a distance metric should be used to determine which pages are required to properly render the object.

This information can also be used to group pages together in blocks on disk, so that they can be loaded together, decreasing latency. Obviously you'll need to be able to cache more pages because you'll always be loading more pages than you need, but because you can better predict which pages will potentially be visible soon, this doesn't have to be a problem.

MD3View online

2010-10-01T11:05:00.000+02:00

I've set up a repository on codeplex to hold the MD3View source.
So anyone who needs the source, you can find it here!

MD3view file hosting blues

2010-09-29T12:03:00.001+02:00

Sometime ago I wrote about MD3View, and old project which I was a part of, and hosted the file.
Unfortunately it seems that the download stopped working some time ago.
I received some emails about it, I am aware of it, I just haven't had any time to do anything about it. (Can you say attack of the multiple insane deadlines?)

My plan is to eventually put it up on sourceforge or github or something like that.

I haven't forgotten, its on my to-do list.
Sorry for the delay.

Mr Elusive strikes again!

2010-09-23T10:11:00.003+02:00

Mr Elusive, or I should say J.M.P. van Waveren from Id Software, has released a new presentation about virtual texturing called "Using Virtual Texturing to Handle Massive Texture Data".

Most of it has been covered in previous presentations, but there are a couple of interesting tidbits which give some hints on how Id Software's virtual texture implementation works.

Their "sparse texture quad tree" is implemented as a MIP mapped texture, just like everybody else. I wondered about this because they never explicitly mentioned it before, and only mentioned a quad tree.
The presentation mentions about feedback rendering that "factor 10 smaller is OK" and "~ .5 msec on CPU for 80 x 60" which surprises me, because it's definitely not okay in my quake 4 test levels. But I suppose if the artwork has been made to work with virtual texturing it might actually work.
It also mentions that

So 128x128x12 texels per page = 192kb per page.
192kb / 6 = 21.5x compression. (their worst case compression ratio)

(50 GB / 10 GB = 5x compression, which explains why that 50 GB must be DXT compressed)

It also mentions somewhere "lossy compression is perfectly acceptable", so I'm guessing there are probably a lot of artifacts in their textures, otherwise they won't be able to achieve such high compression ratios.

They also mention that decompressing costs "1 to 2 milliseconds per page on a single CPU core",
which I'm assuming for their entire 12 channel page.

My results are about 3ms per 4 channel texture, which would be 3*3=9ms.
Of course my compression stuff is rather unoptimized, I chose to focus on compression ratio and image quality, so I'm not at all surprised that they have far better results than my part-time experimental efforts.

Another thing is that they specifically mention read back buffers, so their implementation is not analytical after all.
Which makes me wonder about this screenshot ...

... which incidentally uses the exact same screenshot as the previous presentation, because the MIP boundaries always lie on the page boundaries, which is completely not how a normal MIP boundary would look like.
So I'm thinking it's probably just an artificial representation of the pages, not at all representative of their technology.

Afterwards it presents an high level overview of their decompression pipeline, which I haven't had any time yet to look in detail.

Now if you'll excuse me I have to go back to my 2 simultaneous (and impossible) deadlines, thank you.

Virtual texturing on iPhone

2010-08-16T11:37:00.001+02:00

Sorry for the lack of updates, I've been on vacation in Illinois for the last 3 weeks, visiting family in laws, and only now starting to recover from jet lag. Before I left me and Matthew Baranowski (start blogging already!) submitted a proposal to write an article for a book (not sure if I'm allowed to say anything more about it, so I won't, at least not yet), and while I was on vacation it got accepted! Yesterday (Sunday) was the deadline for the first draft, and I came back last Wednesday.
If I hadn't taken my laptop with me and worked on the article in my vacation, I would've only had a couple of days to write it! Pfew!

Today we submitted the draft and we should be getting comments on the article eventually.

Anyway.

While I was on vacation John Carmack showed a technical demo on the iPhone which used virtual texturing.
It's pretty cool, but I'm actually not surprised that it works. In fact it's something I wanted to try myself, but haven't had the time to do yet.

Why does it work so well on the iPhone? Well from what I've heard they've backed lighting into most surfaces in Rage, leaving only the specular channel to store and render.

IO latency and throughput are less of an issue on the iPhone because of flash memory for 'disk', and that pages don't need to be of as high a resolution compared to consoles.

So if you have pixel shaders, which the iphone does, then it's really not that hard.

The only thing that is more problematic on the iPhone is storage space which is alleviated somewhat by the lower resolution pages. Texture decompression would be more of a problem on the iPhone however, so they're probably not doing that.

I'm still wondering if Id software is subdividing it's geometry at the highest resolution page level though, in which case you wouldn't even need a pixel shader.

VSD implemented

2010-07-20T10:48:00.000+02:00

Last Friday I spend an hour or two in massaging my tools pipeline so that all the polygons would be stored on a per area basis, and passing along the id tech 4 portal information along to my test app.
This morning I implemented portal rendering.
I don't have any screenshots because it's hard to show what you couldn't see anyway ;)
I need to implement a multi-camera system first before I can show anything useful.

The next step will be to store area information with the pages as well, so I can try an analytical solution to page VSD.
The same data can also be used to determine which light potentially casts light on which page.

Bounds, Fragments and Updated tools

2010-07-15T11:19:00.000+02:00

Progress has been slow with my virtual texture experiments because I've come to a point where I can't simply work on things iteratively and need big chunks of time to work on some things.

I've managed to do some things however.

The first thing I did was rewrite the whole layout of my virtual texture file & the way they are loaded so that page definitions are separated from the texture pieces (which I named fragments) that form them.

This will make it possible to eventually support things like procedural and dynamic textures.
It will also allow me to share fragments between pages, which for the time being, speeds up my virtual page generation a lot, which is useful when I need to make more modifications in the future.
It also made it possible to define that a page consists out of more than just a diffuse layer, and my virtual texture file now also contains normal and specular maps, although I don't actually use them yet.

Another thing I've done is calculate the bounds of each page, by clipping the pages' geometry by the page boundaries, and then calculating it's extends.

Here you can see the bounds being rendered around their pages.
It shows how doom 3's texture usage is horrible for virtual texturing, and I really should be merging geometry and projecting the textures onto it.
But not now, because it's a nice worst case situation for testing.

What I really want to do first is start ordering pages in the virtual texture by how close they are together in worldspace, and I want to try to see how better or worse an analytical solution to page visibility would perform.

But before I can do that, I need to implement VSD.
Right now I'm rendering the entire level each frame, but I really should be using doom 3's portal/area information to do some simple portal rendering instead.

Another thing I should be doing is to do the page assignments in the virtual texture on a per area basis, because this will improve page locality at lower resolution mip map levels.
Right now a page on one end of the level could sit right next to a page on the other end of the level.

At a lower resolution mip level, the two page bounds would be combined and the bounds would enclose the entire level.
This is obviously bad because the bounds would become increasingly unusable at lower resolution mips, but it also makes us load a page where it's parts will never be used at the same time.

3rd person story telling

2010-07-08T14:03:00.000+02:00

Just had an interesting thought about game storytelling ...

First person story telling never seems to work very well, this is because you are in control and you can't be directed to play your part in someone else's story.
The more control someone tries to assert over you, the less freedom you have.

When you watch a movie, you sympathize with the characters you're seeing on the screen.
When you play a traditional first person game, you don't sympathize with yourself in the same way, because even though you control your character, you are never truly him or her.
You don't share that made up history with the character, you are just you put in the shoes of someone else and everybody pretending that you are that other person.

The first person games that have the best stories always have their stories revolve *around* the player, always trying to put the player into the center of the story in a somewhat fake way.
Half life does this the best because it lets most of it's story be told by other characters, and acted out by other characters.

So I was thinking, perhaps the story shouldn't centered around the player, but around other characters, and the player is simply there to, sort of, witness it.
Certainly the player would participate in the puzzles and obstacles, but when it comes to the story, the player wouldn't actually be the focal point.
The player wouldn't be the main character.

This would allow much more interesting characters in the story, or maybe even switching between multiple characters, like they do in series.
You would simply be the faceless guy/girl who goes along for the ride, so to speak.

Which explains why freeman never speaking in half life works so well.

3D TV and dynamic surface caching

2010-06-26T20:37:00.000+02:00

Just a thought I wanted to share about rendering lighting into a virtual texture (dynamic surface caching).

Compared to deferred rendering, it should be slower in the worst case.
But the worst case will always be bounded by the size of the page cache texture x the number of lights per page.
The best case is much better because lighting could theoretically be cached per page, as long as the lights that touch that page don't move or change.

However, unless you're moving *a lot* of lights around on screen, dynamic surface caching might always be faster than deferred rendering when rendering the scene multiple times.
Which is what you'd need to do when creating 3D for a 3D TV.

This is because when you're done with rendering the lighting into the page cache texture, you only need to render the scene as if you're rendering the geometry with only one texture, period.

Of course I'm simplifying this a little bit, because in the real world you also have post processing.

But it's still an interesting property ..

Borders? Borders? I don't need no stinkin' borders (on disk)

2010-06-25T10:20:00.000+02:00

Anyone who's read any paper about virtual texturing knows that you need to put borders around your pages, otherwise you get ugly seems because of bilinear interpolation.
This is because your page might be anywhere in your page texture, neighbouring other pages which have completely different colors, and when you sample an interpolated pixel near the border of the page, it interpolates between pixels of unrelated pages.

Usually the borders are build at preprocessing time, where the first 4 pixel horizontal or vertical lines are duplicated from a neighbouring page to serve as a border in the former page and visa versa.

Today I realized that the pages on disk don't need any borders at all, because you will always have all the information available to you to build those borders at upload time..

For example:

In this case, we've got a polygon crossing two pages, which are both visible, and both loaded from disk.
Here we can just copy the border pixels from both pages to the other one.

So what about this case?
Here we've got the same polygon crossing the same two pages, but one isn't loaded yet (or it's visible, in which case we really don't care), and we only have a lower resolution version of that page.
So what are we going to do now?
Well, we simply up-sample the lower resolution page, and then just copy border pixels from that page as before.

And when you think about it, this is actually more correct, because if we used a preprocessed border it would have been be a higher resolution border, and we'd actually get a (very subtle) seem here because the neighbouring page is different!

Bottom line:

Borders do not need to be stored, less disk space required.
The most correct resolution border is always in memory anyway.
Preprocessing is simplified.

Downsides:

More bookkeeping / work at runtime (but not much).
Borders of adjacent pages need to be updated when you load in a higher resolution page.

Virtual texture reflections, random thought

2010-06-19T10:29:00.006+02:00

A thought popped up in my head this morning..

I'm wondering if the following scheme would work.
For all reflecting static objects the world would be rendered around it, into a paraboloid environment map.

Actually, only the part of the world facing the camera, so the paraboloid environment map would be aligned with the camera in the opposite direction.
These maps would be relatively small, maybe virtual texture page sized (128 x 128), and rendered from a specified point within the reflected object.

Instead of storing the colors in the environment map, we store the virtual texture texel coordinates, which are always unique.

Using this, we can then bounce between the environment maps a couple of times using the surface normal of the texel and the destination texel in the environment maps.
If a texel doesn't have an environment map, it would just use that texel.
After x bounces, it would just use some default color.
Obviously the texel coordinates would be an approximation, so some blur would have to be applied afterwards, and more blur would be required at grazing angles..

Would this work/look good enough? I don't know.
Would it be fast? Probably not, but I think it would beat ray tracing.
Obviously there would be a lot of cost in the form of vsd, draw calls and fill-rate.

Update:
Whoops, because of reflections you'd be able to see the back of a reflected object, which would require a second environment map to be rendered in the direction of the reflection.
Damn you reflection angles! Damn you to heck.

However, it might be possible to make some sort of simplified reflection graph and figure out which environment maps you'd need to render.
Which one to use and when would be more complicated however.
And it certainly won't help with performance.

Update 2:
Maybe objects could be pre-split into several environment maps, and we could then perform back-face / frustum culling etc. on these maps.

Texture compression II

2010-06-17T17:04:00.003+02:00

I've made some more progress on the compression code.
I have >6000 128x128 pages, created from Quake 4 textures that I'm using for testing purposes.
Right now the average page size is roughly 2kb.
There's one page of 10kb, and two more that are almost 9kb, other than that none gets higher than 6kb.
I could get more compression out of this, but not without degrading quality beyond where I would like to go.
Average decompression time is 8ms, but I haven't made any attempt at optimizing.
I can compress all the pages combined to 31x their original size.

I'm wondering how id software do their compression though..
According to their latest presentation (id Tech 5 Challenges: From Texture Virtualization to Massive Parallelization) they compress each page to about 2-6kb, but that's diffuse, normal + specular.

But I'm only compressing diffuse here.

I know they're using DCT, they even have some papers published about older versions of their compression routines, but so far I haven't been able to get it down to these sizes without seriously degrading quality.

Perhaps, because of all the real-time lighting etc., it's perfectly fine to really compress textures all the way down to the point where the artefacts are really obvious, simply because they won't be as visible in a scene as it would be in a 2d picture.

Perhaps, I'm nitpicking too much when it comes to quality.

I'm also using SSIM for texture quality assessments now.
It's not perfect, but better than PSNR.

Texture compression

2010-06-14T10:16:00.004+02:00

So the last couple of days I've been playing around with texture compression again, just to see how far I could take it using wavelet compression.

I'm pretty pleased with the results. It's not very fast, but then again I haven't made any attempt to optimizing this yet.
I don't think I can get it as fast as DCT, but I can definitely get far more compression for the same quality.

Just to be able to measure my results more accurately I've created a tool which crawls through my page textures, compresses them, and measures the difference between the compressed/ and the original texture and determines the compressed size.

I should note that the third displayed bitmap in the tool is the exaggerated difference between the two textures.

The cool thing about wavelet compression is that it implicitly has it's mip-map encoded within it.
With virtual texturing you should always permanently cache your lowest resolution mip-maps, which means that if you use wavelet compression that you already have part of the compressed page in memory.

The idea is to use the mip maps that are already in memory to decompress the higher resolution mip maps, which helps decrease the amount of data that needs to be loaded from disk.
(Something I'm not yet doing right now)

Of course this will only be useful if the decompression can be made fast enough.

PS.
Texture page size is 128 x 128, 'diffuse' includes alpha channel here.

PPS.
Noticed that the textures that compress the worst are simple greyish textures with alpha.
It seems that these textures are using pre-multiplied alpha and as such have each color multiplied with their alpha.
This causes lots of variability in the color channels, even in the areas which you can't really see, which hurts compression.
The best solution would be to pre-multiply the alpha at load time, and not pre-multiply it on disk. For now I'm setting all the alpha==0 pixels to the average color, and this seem to work fairly well.

PPPS.
After interpolating the average color with the actual pixel color using the alpha as the interpolation factor, the compression ratio for the worst cases halved!
Obviously this shouldn't be done in production code, but it does show that non pre-multiplied alpha textures compress better than pre-multiplied alpha textures, which means that pre-multiplying the alpha should be done after decompression.

Also, can't help but notice that difference images kind of look like edge detection filters, which might mean sharpening the image with a filter might increase the overall quality of the images (maybe).

I could definitely use some better down/up scaling code for the Co/Cg channels.
(I'm using YCoCg internally as a color representation)

Some interesting links...

2010-06-02T20:26:00.003+02:00

I've got 2 interesting links to share, both are useful for virtual texturing.

The first one "Wavelet image compression - Iñigo Quilez" is a nice article about wavelet compression, which makes me think all the mip maps of a texture page could be compressed together.
This would mean that lower resolution mips would need to be build up dynamically from several pages, which is not necessarily a bad thing because a lower resolution mip's texture area might not be fully utilized anyway.
However, you don't want to require too many compressed pages to be in memory at the same time when you look at a very low resolution page, so there needs to be some sort of trade of.
The very lowest mips should be pre-cached in memory anyway, so that you always have something to display when you can't load in your pages fast enough.

The other link "Bump Mapping Unparametrized Surfaces on the GPU - Morten S. Mikkelsen" is very interesting.
Bryan McNett actually sums it up:

The guy who wrote this paper sits five feet away from me. The paper doesn't say so explicitly, but this finally makes normal maps obsolete for games. Implement the paper, and you can replace 2-channel normal maps with 1-channel height maps. You can also throw away all per-vertex tangent/binormal data. Cool stuff, if you ask me!

The primary flaw of the technique is that, since the derivative of the height map is taken with linear-filtering texture sampling hardware, when magnified it looks like "nearest neighbor" filtering. Fixing this requires adding bicubic-filtering to the hardware.

This can actually be used as a texture compression of sorts, by rendering the generated normal map into the normal page cache texture. The linear filtering won't be an issue there.
Of course this requires per pixel position & per pixel normal, something I would need to do lighting into the page cache anyway.

Realtime CSG - Optimizations

2010-05-28T11:50:00.000+02:00

The last time I blogged about realtime CSG, I mentioned that in my test scene if I performed CSG on the entire scene it would take about 80ms.
(And I should mention again that this algorithm is intended for fast updates, not necessarily doing this faster for the entire CSG tree. Even though that would be a nice bonus)

I also mentioned a couple of things that could be done to improve performance, and that there are a lot of ways to improve performance.

Today I had a simple idea to improve performance.
By checking the bounds for each left and right branch separately at a higher level, so that we know what operation we're performing, we can handle some common situations in a more simplified, and faster, way.

Here's the updated pseudo code for the CSGBranch.Categorize method.

void CSGBranch.
       Categorize( categorizationNode,
                   inputPolygons,
                   ..., 
                   inside, 
                   touchInside, 
                   touchOutside, 
                   outside)
{
  switch (Operator)
  {
    case CSGOperator.Addition:
    {
      // Check if the given polygons
      // are possibly touching the 
      // left branch
      if (boundsOfPolygons
            .IsOutside(Left.Bounds))
      {
        // Polygons are not touching 
        // the left branch.

        // Check if the given polygons
        // are possibly touching the
        // right branch
        if (boundsOfPolygons
              .IsOutside(Right.Bounds))
        {
          // Nope, all of them are
          // categorized as 'outside'
          outside.AddRange(
                    inputPolygons);
        } else
        {
          // We only need to check
          // with the right branch
          Right.
            Categorize(...);
        }
      } else
      // Polygons are touching 
      // the left branch.
      // Check if the given polygons
      // are possibly touching the
      // right branch
      if (boundsOfPolygons
            .IsOutside(Right.Bounds))
      {
        // We only need to check
        // with the left branch
        Left.
          Categorize(...);
      } else
      {
        // Polygons are touching
        // both branches 

        // same as before ...
        // (Left || Right)
        LogicalOr(categorizationNode,
                  inputPolygons,
                  ...,  
                  inside, touchInside, 
                  touchOutside, outside, 

                  false,
                  false
                  );
      }
      break;
    }
    case CSGOperator.Common:
    {
      // Check if polygons are outside
      // either left or right branch 
      if (boundsOfPolygons
            .IsOutside(Left.Bounds) ||
          boundsOfPolygons
              .IsOutside(Right.Bounds))
      {
        // Considering that in a
        // 'common' operation we need
        // to find the parts that are
        // shared with both branches, 
        // we know that if the polygons
        // are outside just one branch 
        // that they are categorized as
        // 'outside'
        outside.AddRange(
                  inputPolygons);
      } else
      {
        // Polygons are touching
        // both branches 

        // same as before ...
        // !(!Left || !Right)
        LogicalOr(categorizationNode,
                  inputPolygons,
                  ...,  
                  outside, touchOutside, 
                  touchInside, inside, 
                
                  true, // reverse Left
                  true  // reverse Right
                  );
      }
      break;
    }
    case CSGOperator.Subtraction:
    {
      // Check if the polygons are
      // touching the left branch
      if (boundsOfPolygons
            .IsOutside(Left.Bounds))
      {
        // The right branch removes
        // and the left branch keeps
        // whatever is inside it.
        // If all the polygons are
        // outside the left branch
        // then we know they're all
        // categorized as 'outside'
        // this branch.
        outside.AddRange(
                  inputPolygons);
      } else
      // Polygons are touching 
      // the left branch.
      // Check if the given polygons
      // are possibly touching the
      // right branch
      if (boundsOfPolygons
              .IsOutside(Right.Bounds))
      {
        // If we're only touching the 
        // left branch, we don't need
        // to do a more complicated
        // operation, and just
        // categorize the left branch.
        Left.
          Categorize(...); 
      } else
      {
        // Polygons are touching
        // both branches 

        // same as before ...
        // !(!Left || Right)
        LogicalOr(categorizationNode,
                  inputPolygons,
                  ...,  
                  outside, touchOutside, 
                  touchInside, inside, 

                  true, // reverse Left
                  false
                  );
      }
      break;
    }
  }
}

This alone increased the speed from about 80ms to 25-30ms for the entire test scene.

I'm going to use a much bigger scene in the future,
because it really is too small to properly test for scalability.

MD3View - A short trip down nostalgia lane

2010-05-26T19:55:00.010+02:00

A long time ago, about 10 years, Quake 3 Arena was released.
Within 24 hours Matthew Baranowski and I had reverse engineered the MD3 model format and created a model viewer that could display all the models in all it's Q3A shaded glory.

Well actually it could've been 24 hours after Q3Test, but anyway..

We named it MD3View and released it with the source, and because open source obviously equals GPL we slapped the GPL license on top of it. (at least that's we thought at the time, not that we gave it much thought)

Interestingly enough Raven software found our tool, expanded on it and used it on games such as Star Trek: Voyager - Elite force (We both got a special thanks in the credits because of this) and apparently Star Wars: Jedi Knight - Jedi Academy.

Not long after Matthew, me and Volker Schoenefeld went on an awesome road trip, starting at New York (well technically Volker & I flew to NY from Germany and the Netherlands) and we (well Matt) drove all the way to Siggraph 2000 in New Orleans (which was still in one piece at the time) and finally to Quakecon 2000.

I still remember being nervous as hell talking to a pretty cool Raven guy there, I mean there I was, this young geeky guy actually talking to someone from Raven Software!!
I politely told him, well mumbled, that MD3View was released under the GPL and that the modified source code should be released as well, or something or other.
Some time later we received an NDA through email, and then got a copy of the source code... and unfortunately my memory gets rather fuzzy beyond that.
But for no particular reason, certainly not because of Raven, the modified source code never got released.

I would've never given this any more thought if someone wouldn't, out of the blue, just asked me if I still had the source code.

Which I didn't.
I just couldn't find it.
Not the original (can anyone out there help me with that?) or the version from Raven.

So I figured, what the hell, I'll just politely ask Raven software for it, it's not like it's state of the art technology any more anyway.

Within hours I got an email back from Ste Cork:

Wow, you won't believe how hard it was to find this, 
we stopped using SourceSafe years ago (and that was
the only place this was ever stored), and it took a
while to even install the client (doesn't work on
Vista) and find all the databases and various INI 
files etc, then pick out the one this was in. 
Anyway, as you can see from the attachment our
IT guy finally managed it.

Whoops, sorry to put your IT guy through that! (so sorry!)
But thanks a lot for all the effort!

And after a couple of emails back and forth, making sure that the headers contained the proper legal information and converting it to a more modern version of visual studio: ~~here it is~~.
Update: Apparently the original hosted file disappeared, so I put it on Codeplex this time, you can find it here.

It's old, it's outdated, and it's yours, all yours.

Update: Matthew confirmed it, 24 hours after Q3Test, not Quake 3 Arena.
Update 2: He also said that we got a cease and desist from Id software and that we had to take it down, wait a couple of weeks until Quake 3 Arena was released before we could put it up again.
I honestly can't remember that... is that a grey hair?
Update 3: Wow, this article brought almost 5000 visitors to my blog in a day!?

Realtime CSG - Part 5

2010-05-21T12:23:00.006+02:00

In part 1 I explained the basics you'll need to know to understand how to perform real-time CSG.
In part 2 I described how to build a brush, which is the basic building block of the algorithm I'm describing.
In part 3 I wrote about CSG operations.
In part 4 I wrote about cutting a brush with another brush.

When I started on writing about real time CSG, I had my original real time CSG algorithm in mind.
It's a simple enough algorithm, but a very simplistic subset of CSG.
I foolishly thought I could just figure our how to generalize it as I went along, it turned out to be a little bit harder than that.

Eventually I managed to get an algorithm to work, but it was complicated and un-intuitive.
The additive and common operations seemed coherent all right, I could rationalize every piece of it.
But the subtractive operation, my god, it was frankenstein as code..
It just didn't make any sense!

I managed to make it work, but only through trial and error.
And even though it seemed to work in all my tests, I didn't really trust it.
It definitely didn't feel right to unleash that piece of code into the wild, imagine what kind of damage that could do in the wrong hands!

And then, as I blogged about before, I read a post at filmic games and it hit me; not only can CSG operations be seen as logical operations (which makes it so much easier to express), but the subtractive operation is actually a combination of operations!
That's why it was so hard to get it to work coherently, I was trying to doing multiple things at the same time!

After that figuring out the lean and mean version of my previous algorithm was fairly easy.

Categorization

As I mentioned before, the final solution of the entire CSG tree consists of all the polygons of all the brushes MINUS all the pieces of these polygons that we reject.

We don't add any new polygons, at all.
Ever.
We just remove parts.

So the heart of this CSG algorithm is the categorization code, this code takes the polygons of a brush, goes through the CSG tree and categorizes each piece of the polygon as being inside, outside, or touching the shape that the entire CSG tree (or sub-tree) represents.
Well actually we have two types of "touch" categories, inside-touching (plane aligned) and outside-touching (aligned with the reverse of the plane).

We essentially do this for every left / right branch and then swizzle the categorization depending on the CSG operation and the results from the left and right branch.

First the code for the branches in the tree (pseudo code)

void CSGBranch.
       Categorize( categorizationNode,
                   inputPolygons,
                   ..., 
                   inside, 
                   touchInside, 
                   touchOutside, 
                   outside)
{
  // Early out, check if the bounding box of
  // the categorizingBrush intersects with 
  // the bounding box of this branch. 
  // If it doesn't, don't bother going any further
  // (This effectively works as a, somewhat
  // unbalanced, bounding volume hierarchy)
  if (boundsOfPolygons
        .IsOutside(this.Bounds))
  {
    // ... add all input polygons to outside
    outside.AddRange(inputPolygons);
    return;
  }

  switch (Operator)
  {
    case CSGOperator.Addition:
    {
      // (Left || Right)
      LogicalOr(categorizationNode,
                inputPolygons,
                ...,  
                inside, touchInside, 
                touchOutside, outside, 

                false,
                false
                );
      break;
    }
    case CSGOperator.Common:
    {
      // !(!Left || !Right)
      LogicalOr(categorizationNode,
                inputPolygons,
                ...,  
                outside, touchOutside, 
                touchInside, inside, 
                
                true, // reverse Left
                true  // reverse Right
                );
      break;
    }
    case CSGOperator.Subtraction:
    {
      // !(!Left || Right)
      LogicalOr(categorizationNode,
                inputPolygons,
                ...,  
                outside, touchOutside, 
                touchInside, inside, 

                true, // reverse Left
                false
                );
      break;
    }
  }
}

Notice how elegant it is?
The LogicalOr method is basically the CSG Addition operator.
The inside, touchInside, touchOutside, outside parameters are lists to which the polygon pieces are added.
Notice how the 'not operator' is basically nothing more but a reversal of the parameters!
The last two parameters are used to tell the LogicalOr method if the left and/or right branch need to have their parameters reversed.

So here's the LogicalOr method:

void CSGBranch.
       LogicalOr( categorizationNode,
                  inputPolygons,
                  ..., 
                  inside, 
                  leftTouchInside, 
                  leftTouchOutside, 
                  leftOutside)
{
  //        right
  //        inside | touch-I | touch-O | outside
  // left          |         |         |
  // inside    I   |    I    |    I    |    I
  // touch-I   I   |   tI    |    I    |   tI
  // touch-O   I   |    I    |   tO    |   tO
  // outside   I   |   tI    |   tO    |    O

  ... create some temp lists ...

  // if anything is inside the left branch, 
  // we don't need to check it again for 
  // the right branch. Everything else is put
  // in temporary lists whose contents we'll
  // check against the right branch ...
  if (!inverseLeft)
    Left.
      Categorize(categorizationNode,
                 inputPolygons,
                 ..., 
                 inside, leftTouchInside, 
                 leftTouchOutside, leftOutside);
  else    
     // .. same as above but with parameters
     //    reversed

  if (!inverseRight)
  {
    //        right
    //        inside | touch-I | touch-O | outside
    // left          |         |         |
    // touch-I   I   |   tI    |    I    |   tI
    Right.
      Categorize(categorizationNode,
                 leftTouchInside,
                 ..., 
                 inside, touchInside, 
                 inside, touchInside);

    //        right
    //        inside | touch-I | touch-O | outside
    // left          |         |         |
    // touch-O   I   |    I    |   tO    |   tO
    Right.
      Categorize(categorizationNode,
                 leftTouchOutside,
                 ...,  
                 inside, inside,
                 touchOutside, touchOutside);

    //        right
    //        inside | touch-I | touch-O | outside
    // left          |         |         |
    // outside   I   |   tI    |   tO    |    O
    Right.
      Categorize(categorizationNode,
                 leftOutside,
                 ..., 
                 inside, touchInside, 
                 touchOutside, outside);
  } else
  {
     // .. same as above but with parameters
     //    reversed
  }
}

Note that if a polygon is touching-inside on one branch, and touching-outside on the other branch, then it means the two branches are touching each other there.
Which means that any polygon in that area is essentially inside both, and therefore 'inside'.

And here's the code that handles the leafs in the tree; the brushes themselves:

void CSGBrush.
       Categorize( categorizationNode,
                   inputPolygons,
                   ..., 
                   inside, 
                   touchInside, 
                   touchOutside, 
                   outside)
{
  // Early out, check if the polygons we're 
  // processing belong to the same brush as
  // we're currently checking against
  if (categorizingBrush == this)
  {
    // We're looking for the parts of 
    // 'categorizingBrush' that are visible
    // and at this position in the tree, these
    // polygons are definitely visible ...
    foreach (var polygon in inputPolygons)
      polygon.Visible = true;
    
    // We know all polygons are interesecting
    // with the brush they lie on
    touchInside.AddRange(inputPolygons);
    return;
  }

  // Early out, check if the bounding box of
  // the categorizingBrush intersects with 
  // the bounding box of this brush. 
  // If it doesn't, don't bother going any further
  if (boundsOfPolygons
        .IsOutside(this.Bounds))
  {
    // ... add all input polygons to outside
    outside.AddRange(inputPolygons);
    return;
  }

  ... create some temp lists ...

  this.Split(inputPolygons,
             ...,      
             inside,
             tempTouchingInside,
             tempTouchingOutside,
             outside);

  // We know that the current brush
  // is not the 'categorizingBrush'.
  // We also know that any polygon liying
  // on the surface of this brush cannot 
  // be lying on the surface of 
  // 'categorizingBrush' (well okay, it
  // can, but one overrides the other 
  // depending on order, which is exactly
  // what we want)
  // So we set all the polygons lying on 
  // the surface of this brush to invisible.
  // This solves overlapping polygon problems
  foreach (var polygon in tempTouchingInside)
    polygon.Visible = false;
  foreach (var polygon in tempTouchingOutside)
    polygon.Visible = false;

  touchInside.AddRange(tempTouchingInside);
  touchOutside.AddRange(tempTouchingOutside);
}

And finally here's what we do at the top level:

void CSGTree.
       ProcessBrush(categorizationNode,
                    inputPolygons)
{
  .. create temporary lists ...
 
  // Categorize the inputPolygons
  // depending on their location in 
  // the tree ...
  RootNode.
    Categorize(categorizationNode,
               inputPolygons,
               ...,
               // Store results in
               // temporary lists ..
               invisiblePolygons,
               visiblePolygons,
               reversedPolygons,
               invisiblePolygons);

  // We set all polygons that are outside
  // or inside the tree as being invisible ...
  foreach (var polygon in invisiblePolygons)
    polygon.Visible = false;

  // We reverse the order of all the polygons
  // that the tree categorized as having a
  // reversed orientation ...
  foreach (var polygon in reversedPolygons)
    ReverseVertexOrder(polygon);
}

And that's it!
After you've build all the geometry, when a brush moves, simply reprocess it and all the brushes it touches.

The result:

Points are vertices moved towards the center of the polygon
to make it easier to see where there are any t-junctions,
or where multiple vertices lie on the same line

Note that I didn't describe the CSGBrush.Split method, I'm going to retroactively modify the previous posts to add more pseudo code (it belongs there), and update the repository as well.
(but not today)
I'll post about it when I've done that.

Limitations and Future work

When I use this algorithm on my test level which has 234 brushes and 467 nodes, I can generate a mesh with it within about 80ms.

Keep in mind that this algorithm was designed with dynamically updating a handful of brushes in mind, not so much with updating everything all the time.

The resulting mesh has not been optimized yet, there are T-junctions and polygons that should be joined together, but that's a different topic and really deserves a series on it's own.
If the polygons are optimized per brush, T-junctions should be a rarity considering that the cutting plane that split an edge, would've cut any aligned edges on another brush as well.
(Of course, there might still be T-junctions because of floating point errors, so don't completely rely on this)

As for performance, there is much room for improvement here:

All brushes are processed independently, which makes them a prime candidate for parallelization.
(This is what I did in my editor)
This is the big elephant in the room; The algorithm should be rewritten with CPU cache usage in mind, this alone could make it an order of a magnitude faster. Half edges are the biggest problem here. The code would become more complex.
A higher level bounding volume hierarchy, hashed grid, or sweep & prune phase could theoretically speed things up. Although when I tried it, it only slowed things down.
I'm guessing that this is because we're already doing some sort of (unbalanced) hierarchical culling while going through the CSG-tree, so perhaps there's not too much to be gained. Perhaps this only becomes a problem when the tree grows very large.
I'm convinced that it should be possible to figure out some short cuts when going through the tree. Perhaps it's even possible to work from the bottom-up, by starting at the leafs.
Perhaps that would allow getting rid of all the temporary lists, which is not so much a problem in a language such as C# where allocation is very cheap, but a bigger problem in languages such as C++.
There are a lot of lower level optimizations that can help a lot with performance too.
I'm using a lot of methods and enumerations in the example code for clarity and readability, and these hurt performance.
Once you understand the code, you should consider copying all the planar/vector methods code directly into the methods where they're used.
Also, you should consider not converting planar side calculations into enums, but using the floating point values instead.
This should help a lot in the inner loops and could seriously improve performance.

That's it for now, let me know if I need to explain something in more detail or if you use or improve on my algorithm!

Andreas Neu's virtual texturing thesis online

2010-05-18T16:34:00.001+02:00

A while ago I mentioned a very interesting thesis written by Andreas Neu, but back then it wasn't online yet.

Today Andreas send me an email telling me that it's online now, and you can find it here.

Be sure to check it out if you're in any way interested in virtual texturing technology!

CSG operations update

2010-05-14T17:16:00.001+02:00

In my last post I mentioned that I suddenly realized that all popular CSG operations (Addition, Subtraction & common) can be expressed as logical operations.
Using that knowledge it was trivial to rewrite all operations as a mix of logical OR (the simplest of operations) and logical NOT operations.

To reiterate:

( A || B) = CSG Addition
!(!A || B) = CSG Subtraction
!(!A || !B) = CSG Union

Now the way my CSG code iterated over the CSG tree was basically to tell each child-node in which list to store the polygons that are inside, outside or touching (I actually have 2 categories of touching polygons, depending on the alignment of the plane that touches it).

Performing a logical NOT comes down to just swizzle the lists I'm passing on, so it's essentially free.
Leaving me with code for just 1 CSG operation that needed to work perfectly!

Although I got everything working with the more complicated code before, it had some really scary parts because of the CSG subtraction operation which was really hard to get right because I flipped the orientation of the polygons to get it working.
This caused a cascading effect which complicated all the other operations as well.

So when I rewrote it today I found a much more elegant solution which allows me to flip the orientation of the polygons at the very end, again simplifying everything even more.

It's pretty clean and easy to read now, I still need to test it.
I'm way more confident now about it working in all test cases compared to before because of it's reduced complexity.

CSG operations

2010-05-12T12:42:00.040+02:00

Lately I've been posting a lot of random thoughts, and this is one of them.
Today I read a post at filmic games about CSG, and for one reason or another a thought popped up in my head:

CSG operations can be expressed more intuitively as logical operations!

Technically, bitwise operations would work too, at least from a programming pov, but would make less sense (we're not working with bits here, aren't we).

A CSG complement operation would behave like a logical NOT operation (! in C languages), where the shape becomes "everything outside of the shape" (which is only useful as an intermediate step, not so much as an actual operation).
A CSG common (also known as 'intersection') operation behaves like a logical AND operation (&& in C languages) because only the parts that are kept are the ones shared between the two shapes.
A CSG addition (also known as 'union') operation behaves like a logical OR operation (|| in C languages) because all the parts of both shapes in this operation are kept afterwards.
A CSG subtraction operation would actually be a combination of AND and NOT (A&&!B).

The pictures have shamelessly been taken from wikipedia on the topic of logical operators which interestingly enough showed CSG like pictures!
(They're actually Venn diagrams)

Which shows that these things are, in fact, the very same thing!
(Hmm ... I wonder why I never noticed that before)

Note that logical OR (CSG union) operations can also be expressed as !(!A && !B), and that I've already shown that CSG subtraction can be expressed as (A && !B), meaning that all popular CSG operations can be implemented using only NOT and AND operations.

Now consider that a NOT operation would effectively not change the mesh at all, but would only invert the classification of triangles being inside or outside, there would effectively only be one kind of mesh modifying operation left..

Interesting!

More random thoughts

2010-05-11T11:10:00.012+02:00

Random thought 1: GJK / backface culling

So I was reading another chapter in my "Game Engine Architecture" book, written by Jason Gregory (which, incidentally, is a really good book), about Physics or more specifically, about the GJK algorithm.

I've seen the algorithm mentioned before but only glaced over it, not realizing how useful it is, but now I do!
It's very useful for doing intersection tests for my CSG algorithm.

Part of the GJK algorithm is finding a point furthest along a particular direction within a convex polytope (which is, basically, the same thing as a CSG brush).

Maybe they're already doing this in real life, but I couldn't help but wonder, why aren't they backface culling polygons (and all it's vertices) using this direction vector?

Update: Giving this some more thought makes me think that this won't work.
When you have relatively few points then all the back face culling operations would take more cycles compared to just going through all points. Yet if you have lots and lots of points you end up having more branching and CPU-cache misses. So ignore this idea.

I wonder if storing vertices into 8 octants, where each octant is a particular direction, and then using the signs of the x,y & z components of the direction vector to pick an octant would work.

Random thought 2: CPU Cache & Component entity systems

Couldn't help but think that component entity systems, data orientated design (optimize for CPU cache), block based memory allocations, splitting all the work into tasks (for easy multi-threading) would work really really well together, if all where designed together.

After all, component entity systems have lots of lists of similar components on which systems work.
This is exactly what you'd want to be doing with data based design because it's cache friendly, and it also allows you to break things up into small tasks within the system..

Of course entity systems are traditionally only used for the gameplay code, and usually written in a very flexible (and potentially very slow) way, but I'm wondering if the entire engine could be written around these principles..

Random thought 3: Each VT Page mip should decrease in size

In 'traditional' virtual texturing a lower resolution mip of a page contains several lower resolution versions of higher resolution pages, so that each page, no matter what mip, has the same size (for example, 128x128)

This is useful because you can more easily mix different pages of different mip levels within the GPU page cache, and this is fine.

I've been wondering though, should we really be doing the same on the disk side?

After all, we could just update the pieces of a lower resolution mip page in the GPU cache, instead of loading the entire mip, which would include an incrementally larger virtual texture area the lower resolution the mip level is.

This would all not be a problem if a virtual texture would just be a texture, but it isn't.
It's a texture management system, or a texture atlas at best.

There are a lots of seems within the virtual texture where individual mip pages contain pieces of texture that, within the level, can be very far apart.

Only loading the pieces of the mip pages that we need would reduce loading pixels that we're not going to use anyway.

It also makes it easier when compressing the pages, because we can more easily omit channels when they're not being used by a page.
Before, any used channel would travel up the mip map chain, because one of the higher resolution mips would be using it.

This is all, of course, not an issue for all the pre-cached pages.
And, in all fairness, the highest resolution pages are always the biggest problem, and this would only optimize loading the lower resolution pages.

All the above issues could also, potentially, be solved by grouping pages within the virtual texture in a more optimal way, but you'd probably end up with a lot of wasted space.

Also compressing pages in 8x8 blocks (or something) and omitting unused channels in those individual blocks would help to avoid the above problems too, and would probably be a good idea anyway.

Random thought 4: Compressing the mip map chain

I'm also wondering if there are good ways to compress an entire mip map chain together in context, considering that there isn't likely to be too much difference between two mip-map levels.

We're already pre-caching several mip map levels... so, can we leverage that information so that we can decrease the disk size of all the pages that we load on the fly?

Worldspace shadow-map / virtual texture - another random idea

2010-05-06T12:29:00.004+02:00

Just a new random, not even a nearly completely thought out idea of mine.
Which I blame on only having time to dream up these things, but not actually try them $@#!
Yes, I am frustrated ;)

Anyway.

Suppose we perform our lighting within our virtual texture cache (aka surface caching), which I've blogged about often, and we store our texel world-space coordinates in the cache, wouldn't we also be able to use this information to do shadow mapping?

The (HUGE) downside is that we'd need a place to store the texel coordinates even for pages that aren't visible (being able to analytically cull pages and lights would definitely help here... page bounding boxes? bounding volume hierarchies?)
Would lower resolution mips be enough for lighting? (sometimes?)
I suppose some sort of preprocessing could help here.. I can imagine that a lot of the geometry that uses a specific page would essentially be flat.

The upside is that we'd only have to render geometry exactly once per frame (or less, with caching), and perhaps we could be rendering the lighting directly into the cache..
In which case having the knowledge of all the transparent pages between your texel and the light-source would be interesting! (Probably slow as hell though, even IF you manage to get this to work somehow)

What about texel world coordinate mip maps?
Would we need to store min/max coordinates instead of 'just' coordinates?
Could that be used in a sort of hierarchical z-buffer type of setup somehow?
For (rough) culling on the CPU side perhaps?
For both the shadow map and camera?
That would require us to have the texel coordinates on the CPU side though.. (static geometry only?)
Preprocessed and stored with the pages? (geometry images?)
But bandwidth is already an issue...
Then again, it would probably be very compressible, most of the time.
At least, for the higher resolution mips..

Argh, too many angles, too many ideas!
Most of them look extremely impractical to begin with, but it's a lot of fun to think about ;)

Besides all that, this idea popped in my head:
If every texel coordinate is unique with virtual texturing, wouldn't we be able to use this, somehow, to eliminate shadow acne? (Assuming you're not using cascaded shadow maps already & this would really be complicated by page mip maps)

Propagation volumes

2010-05-04T08:43:00.005+02:00

I don't have much time to actually experiment with ideas these days, but I can still find a little time here and there to just let my thoughts go and see where they lead me.

Here's a thought I was playing with yesterday.

Suppose for a minute that we'd have the ultimate computer, memory is so large that it doesn't form any barriers, and CPU and memory speed is high enough to practically do anything we want.
So 'of course' all assets would consist out of a form of voxels,
but what about lighting?
Well all lighting would be performed within very high resolution propagation volumes of course!
Obviously, the propagation volumes would even handle light reflection, refraction, scattering and absorption.

This led me to the following, more interesting, idea.. what about audio?

Now I should mention that I'm nowhere near an expert on audio, so take this with a grain of salt, but audio is in the frequency domain, right?
Well, so are the spherical harmonics used in light propagation volumes!
Hmm.. doesn't that mean it should be possible to perform audio within a propagation volume-esque solution?

Just imagine being able to simulate how audio behaves within a scene, with reflections etc.!
I have no idea though which x-th order spherical harmonics, or what resolution of the volume would be "enough", nor do I have any idea how good this would sound.

But it sure sounds cool.
Err.. If you know what I mean.

Rendering into virtual texture using indirection table

2010-04-28T15:18:00.012+02:00

I mentioned an idea in the past where lighting would be performed into the GPU side cache of the virtual texture.

This would have some advantages, such as when you render to the scene, you basically only need to render a single texture, have perfect filtering and being able to render everything using standard anti-aliasing techniques (compared to, for example, deferred rendering).
Blur pages the right way and you can fake skin subsurface scattering..
Proper transparency with lighting would be a lot simpler too!

Of course there are downsides as well.. (Can you say post processing?)

One of the bigger fundamental problems with this approach is that you need to, somehow, know the positions of your pixels within your cache texture.

Before I was thinking along the lines of rendering into the cache texture using predefined batches of geometry per page.
Which requires a lot of preprocessing, costs a lot of memory or complicated schemes and would require you to either render the same batch to different mip levels, or have monolithic batches (where you'd basically be rendering EVERYTHING) for the highest mip levels (which would be ridiculous).

But now I realized it might be better to limit each triangle to a single page, and then to render the scene into the cache texture using the indirection table to transform the triangle to the right page with the right size!

It has some annoying issues though, it needs per vertex texture coordinates or a geometry shader, but it should work.
The caching of pixels-in-page-coordinates wouldn't be as straight forward either.

That said, I consider this surface caching idea just a (fun!) thought experiment.
For anything serious, I'd use a deferred renderer!

Virtual Texturing Thesis from Andreas Neu

2010-04-21T11:17:00.004+02:00

So last Friday I received an email from Andreas Neu who wrote his bachelor thesis about virtual texturing.
He was advised at the RWTH Aachen university by my good friend Volker Schoenefeld, and he told him I would probably be interested in his thesis, which I obviously was!
It cannot be found online (yet?), so I can't provide a link unfortunately.
Hopefully when or if it'll be placed online, I can provide a link to it here.

In his thesis he investigated which page priority heuristic would be better at choosing which page to load next, by measuring which would have the most positive visual impact.

He tried a couple of variations of what he calls "PixelSum", where he counts the number of visible pixels of a specific page (a technique I mentioned before on the blog), which performed surprisingly well.
He also provided some tweaks on "PixelSum" which improved it's performance when moving the camera, but which didn't have that much impact while rotating the camera, which is actually the worst case.

Another thing he tried was a "look ahead camera", which basically doubled the rotation and translations of the current frame compared to the previous frame, and used that new transformation for the readback buffer, which he calls a "needbuffer" in his thesis
This seemed to provide better or same performance in the worst cases, but sometimes slightly worse in the best cases.

The best idea, however, is what he calls "NoiseValues".
Here he compared his pages to it's lower mipmaps, using a rooted MSE on their luminance, and using that value as a weight to determine which pages would have the most visual difference between miplevels.
That same weight can then be used to determine which pages would have the biggest visual impact on the scene when loaded.

Personally I'd love to see more stuff like this, and I think there are a lot of interesting possibilities that continue on some of the ideas put forth by Andreas!

P.S. Still haven't found any time to continue on the whole CSG thing, but don't worry, I'll continue on it when I have some time! (Too much work, too many clients, where's the recession when you need it!)

Just a tiny update

2010-04-03T11:29:00.002+02:00

Finally had some time yesterday to put all the individual generic CSG components that I made together, write a simple 3d view test app, and test it.
And after fixing a couple of tiny issues, it worked like a charm!
Now I only need to do a couple of more tests, and then I can write the next part in the CSG series

CSG woes

2010-03-13T10:34:00.005+01:00

So, as I mentioned before, the algorithm I used in my editor used a simplified CSG implementation.
When I started blogging about CSG I thought, how hard could it be to turn this into a full implementation?
Easy, right?

Boy was I wrong.

My old implementation only supported subtractive and additive brushes and didn't supporting any grouping of brushes. This made it possible to put all the brushes in a single list and let the brushes BE the CSG operation themselves.
In a full implementation things get way more complicated, mainly because of the grouping of brushes and the tree like CSG structure which results out of that.

The cool thing about CSG is that, except the brush splitting method, it actually works exactly the same in 3D as it does in 2D.
So I made a tool to perform CSG in 2D to build an CSG implementation which I could then, once I've got it to work, transfer to a 3D implementation.
After all, 2D is much much easier to debug and visualize.

Anyway, my theory to get a full real-time CSG implementation working is like this.
First of all, each brush is processed separately so we can not only perform these operations in parallel, but also update individual brushes without needing to reprocess everything.

Since in any CSG implementation the resulting mesh would only included portions of the original polygons created from the original brushes, no new polygons would be created.
This means we can use our brushes and operations as a sort of query over the polygons of these same brushes.
We 'just' pass our polygons through our CSG tree and determine which pieces are visible and which ones are removed.

At a higher level the CSG tree could be simplified on a per brush basis and some space partitioning data structure could be used to avoid unneeded calculations, but I haven't got to that point yet.

Our brush splitting method will tell us which lines are inside/outside or touching and if we make sure that at every stage in our tree we correctly determine if the given polygons is inside/outside or touching then we should end up with the correct polygons.

The inside/outside part is relatively easy, it gets hard with the touching part though.

Take for instance the following simple situation with an additive operation and two brushes:

In the left situation we want to treat the parts of the polygons that touch as being "inside" this particular branch of the CSG tree, on the right we want to keep the touching polygons.

Well we actually want to remove it for the left brush and keep it for the right brush, but this can be solved by detecting if surfaces on the left and right brush overlap, and then only keeping the polygons that belong to the last brush that overlaps.

We can solve this by taking the relative orientation of the polygons into account;
If they're opposites, remove them, if they're aligned, keep them.

For subtractive operations it gets more complicated:

In the left situation I'm doing something which may be debatable.
When the subtractive brush touching another brush on the outside, I keep that polygon part because I want the subtractive brush to be able to override the underlying brush.

In the right situation not only do we keep all the polygons of the subtractive brush that are inside (we remove all the polygons that are outside), but we need to change the orientation of the polygons too!

This brings me to the biggest problem with CSG trees; the number of polygons increase, because of splits, as you go down the tree!
This works fine as long as you work with a single list of nodes, like in my old algorithm, but when you have a tree like data structure this causes lots of problems.

Suppose I first categorize my polygons in the left branch into inside/outside/touching-inside/touching-outside categories, what happens if I then try to categorize those same polygons in the right branch?
The original polygons could actually be split into lots of new pieces, and I have no easy way to match them together! (Certainly not in a hierarchy that's x-levels deep)

Even if I find a good way to handle this, imagine what happens a polygon's orientation is changed in the right branch, it would've been categorized wrongly in the left!
This probably means I have to determine the orientation of a touching polygon at the very last moment, but that would require me to pass along additional information like which plane it was touching.

Right now I 'solve' this by going through the CSG tree and splitting functions several times, but to say that this is inefficient would be an understatement..

I'm playing with some ideas, like building some sort of categorization tree, but they're not fully gestated just yet.

I'm close, but I'm not there just yet.

Edit:
It's funny how writing things down often helps you find an answer to a problem!
This is my solution:

Categorize(branch.Left, ... );

//for each category
foreach(var polygon in myCategory)
{
    Categorize(branch.Right, ... );

    // now, even if the polygon has been split, 
    // we know the category of all polygons
    // in both the left and right branch!
}

Ptex

2010-03-10T21:39:00.002+01:00

Through Google Buzz, Bryan McNett mentioned Ptex to me, which I missed somehow.

It's an interesting approach to texture a model without having to use any parameterization.
Now obviously this has been written with Renderman in mind, but I'm pretty sure it could be used in an art-pipeline which would triangulate the subdivision surfaces somewhere in the art pipeline (or use dx11), and put all the texturing into a virtual texture.
Obviously it would waste some texture space, but it would sure make the life of artists a lot easier.
It'll free up time for them to do what they do best; art!

Still working on the next part of my real-time CSG articles but I need my test code to work flawlessly on all my test cases (and there are oh so many of them), and debugging a full CSG implementation takes *a lot* of time I'm afraid.

Realtime CSG - Part 4

2010-03-02T11:29:00.003+01:00

In part 1 I explained the basics you'll need to know to understand how to perform real-time CSG.
In part 2 I described how to build a brush, which is the basic building block of the algorithm I'm describing.
In part 3 I wrote about CSG operations.

As I mentioned in my first post of the year; The most important thing to realize is that when you're performing CSG with multiple brushes, no matter which operations you perform, or how you group your brushes, the final mesh you'll end up with will always consist out of (parts of) the original polygons, which where made out of our brushes.
Only parts of these original polygons are removed, no new polygons need to be created, ever.

So in the end, we basically need to manage which parts will be visible or invisible depending on the situation.

At the end of part 3 I said that in the next blog post I would write about how to traverse the operations list.
Well, before I we get to that part I need to explain how to cut up a brush into the right pieces.

Cutting the brush

In part 1 I wrote about cutting polygons.
Cutting a brush is a natural extension to that.

The algorithm is pretty straight forward; for every brush you intersect with, cut each polygon of your brush with the planes of the intersecting brush.

All the pieces that are on the outside of the polygon are classified as "outside".
At the end, if there's anything left of the original polygon, then that's either "inside" or "touching-inside" or "touching-outside".

The polygon is "touching" when all the points of the polygon lie on one of the planes of the intersecting brush.
By comparing the normal of the polygon and the touching plane you can determine if it's "touching-inside" (normals are pointing in the same direction) or "touching-outside" (normals point in opposite directions).
You can use a dot product between the normals for this.
If the result of the dot product is positive, they're pointing in the same direction, if it's negative they're opposites.
Obviously if it's not touching, it's "inside".

Depending on the situation you'd need to discard your polygon pieces if it's inside/touching-inside/touching-outside or 'just' outside.

Next time

That's all I have time for today, the next time I'll go through the algorithm for general CSG.

"Efficient Irradiance Normal Mapping"

2010-02-04T10:09:00.000+01:00

Quote:
"Irradiance normal mapping is a method to combine two popular techniques, light mapping and normal mapping, and is used in games such as Half-Life 2 or Halo 3. This combination allows using low-resolution light caching on surfaces with only a few coefficients which are evaluated by normal maps to render spatial high-frequency changes in the lighting."

Now that sounds like it might work in combination with the virtual texturing surface caching idea!
Not sure about it's performance though, which is rather crucial.

You can find the paper here.

Random thought

2010-02-01T10:54:00.000+01:00

Just had a random thought concerning game component object systems.

If the system is optimized to quickly add and remove components, then an event system could be realized by adding and removing components.
So instead of having a complex event system to send events between components, you would add a specialized component that performs or represents the event.
The component would then be removed when the event is processed.
Not entirely sure how flexible it would be, but it would sure be easier to optimize for cache and multiple threads.

Yes, this blog has been neglected lately, I'm going to give it some attention again soon (I hope).
Real life has simply thrown several projects my way which is taking all my time at the moment.

615 bits should be enough for everyone

2010-01-18T09:56:00.000+01:00

Here's the proof.

First post of the year

2010-01-04T15:49:00.002+01:00

Happy new year!
Let's all hope this decade will lead us all towards a better path compared to the last one.

Lately most of my time, that I haven't spend with my family, has gone to my secret project™, but between all this I managed to sneak in some time for my other projects.

Real-time CSG

It's not full proof yet (there are some issues with duplicates), and only 2d (the basics are the same), but I've managed to come up with an algorithm that can perform CSG on each brush individually with a full CSG-tree implementation.

My old algorithm just added brushes together in a list.
Subtractive brushes where basically inverted and would work automatically.
The adding of subtractive brushes and additive brushes only differed when it came to brushes touching each other.

I'll explain the new algorithm it in detail eventually, when I finish it, but the basic thinking behind it is that with any CSG operation you perform on any mesh, that the resulting mesh will ALWAYS have the same polygons or with some pieces of these polygons removed.

This means that you never ever have to create new polygons, you just need to figure out which parts will need to be visible, and which polygons need their vertex order inverted.

If you consider a CSG-tree to be a sort of iterative query, where for every polygon you go trough the query and determine which parts of it are inside, outside or touching, then eventually you'll end up with all the parts that are visible.

Update: Figured out that if you give each node an index and pass the index of the node the current polygon belongs along with you while you traverse the CSG-tree.
Then you can compare this index with the current brush you're splitting with, which makes it possible to decide which overlapping polygon must be discarded, and which one must be kept!

Surface caching

Spherical harmonics won't work for storing specular highlights in a surface cache, I'm hoping the "half-life 2 basis" explained in the "half-life 2 shading paper" might do the trick.
I'm afraid it won't be accurate enough though.

There are also some really annoying inefficiencies in the whole virtual texture/surface cache idea, like having to render the geometry position into a buffer, which would require anything that moves to re-render it's position.
This could perhaps be done only once, when rigid bodies are concerned, by transforming the light instead of the world-positions of the texels.
This won't help when skinned characters are concerned though, they will need their positions rendered into the page cache and lighting re-calculated every frame.
I wonder if there's a way around this.

Just a quick update

2009-12-13T16:08:00.008+01:00

Deferred Virtual Texture Shading

I've blogged about this idea before, using a virtual texture cache as a sort of g-buffer, and this has some advantages (I'm not going to re-iterate these again, just read my older posts if you want to know more).

Frankly it's simply a dynamic form of surface caching, so I decided I'll start calling this idea "dynamic surface caching" instead of "deferred virtual texture shading", which is a horrible name for it anyway.

Anyway, today I read a blog post about an idea where a light pre-pass renderer is implemented using spherical harmonics.
This made me realize that with my dynamic surface caching idea, the lighting of the surfaces could be stored as SH coefficients as well, de-coupling it from the view direction, which would make the cache idea more useful.

Realtime CSG

When I implemented the realtime CSG algorithm I've been blogging about, I was mainly concerned with getting it to work, getting it stable and making it perform fast, not so much with code readability (it was a prototype anyway).
Since I needed to explain it in a coherent way (or at least I try to) I needed to figure out all the peculiar details I put in code a year ago, and figure out how to communicate all this in an effective way.

This actually gave me some new insights and ideas.
My original implementation only had additive and subtractive brushes, no 'common' brushes, and the CSG operation was tied with the brush, making a complete CSG hierarchy impossible.

It worked really well for it's purpose (seriously, you probably wouldn't want to directly expose this kind of functionality in an editor anyway), but I have some ideas on how to generalize it, possibly make it more efficient, and definitely make it more readable and accessible.
So I need to do some tests and get some code working before I can continue with the blog posts about it.

Unfortunately this is a very busy time for me at the moment.
Clients with lot's of deadlines (meaning I need to do some work at home as well), a top secret project I'm working on with some friends of mine, preparing for Christmas, wife wanting me to do all kinds of home improvement stuff, and my daughter obviously wanting some attention between all this as well ..

But I should have more time to code around Christmas itself!

Realtime CSG - Part 3

2009-12-07T10:49:00.008+01:00

In part 1 I explained the basics you'll need to know to understand how to perform real-time CSG.
In part 2 I described how to build a brush, which is the basic building block of the algorithm I'm describing.

This time I'll start explaining some parts of my CSG algorithm.

CSG Operations

Now that we've created our brushes, we want to build larger meshes with them.
We do that by performing certain operations between them, these are similar
to regular algebra because their order matters greatly and you really want
to be able to group them together.

Formally there are 3 types of CSG operations:

Addition, sometimes called 'Union' or 'Merge'.
Subtraction, sometimes called 'Difference'.
Common, sometimes called 'Intersection' or, confusingly 'Union'.

At each operation we determine which pieces of each mesh is inside, outside or is touches the other mesh. (Something I'll be blogging about eventually)
(A brush 'touches' another brush when one of it's polygons lies exactly on the plane of the other brush)
Depending on the type of operation these polygon pieces are either discarded or kept.

Since you almost never would want to perform a 'common' CSG operation on anything but a small number of brushes, you really need to group brushes together.
This is also, to a lesser degree, true for subtractive brushes.
This means you'll need some sort of tree structure so you can determine what operation to perform on and with which brushes.

Divide and conquer

So do we need to perform those operations on all brushes for each brush?
Fortunately not!

The trick is that for each brush, using some sort of bounding volume hierarchy, you determine which brushes intersect or touch your brush, and then put them into a list (let's call it an operations list) which is also sorted by the order in which they appear in your CSG tree.

So now that you have a list of operations to perform on each brush, on a per brush granularity.
This means that when a brush is added, deleted, moved or is modified, only that brush and the brushes it touches need to be rebuild, this is the part that makes this algorithm real-time.
This also makes it easier to perform each brush update in parallel, which will make this algorithm faster and faster the more cores a CPU has!

Early outs

Keep in mind that you can drastically shorten your operations list by having some intelligent early-outs.
For example, if the brush your working on is inside another additive brush, which is further on in your CSG-tree, then you know that you can just discard the entire brush (because anything you do will be deleted further on in the tree anyway).
In the reverse you can also just ignore the smaller brush when processing the larger brush because it'll never have any effect on this brush.
There are many cases like this, but be careful with this, I've tried a lot of early-outs which seemed to work most of the time but then broke down on a rare situation!

User interface limitations

In my editor I never implemented the CSG-grouping of brushes because it's really hard from an user-interface point of view.

In an editor you really want to group brushes semantically (for example all the brushes that form a 'door' or 'window') instead based on operation (artists aren't programmers after all, nor should we burden them with technicalities; they need to focus on their art, not their editor!).
If you try to implement this sort of functionality in an editor, you'll get an extra level of complexity which will really make your editor harder to use and understand.
That said, it shouldn't be too hard to implement because from the algorithms' point of view, it only effects the building of that operations list I was talking about earlier.

Nothing is stopping you from implementing a full implementation and not necessarily exposing all the functionality (all the time) in your editor, if you're building something which doesn't require an editor this is not so much of a problem obviously.

Processing a brush

To process each brush, we need to traverse the operations list.
Both parts of it.

The thing is, all the brushes that are ahead of our brush in the hierarchy, need to be handled differently than the brushes that come after it.

Which is exactly what I'll be blogging about next time!

Realtime CSG - Part 2

2009-12-02T09:55:00.017+01:00

This is part 2, you can find part 1 here.

Last time I told a bit about numerical stability, and the importance of consistency when dealing with geometry.
I also mentioned that in my CSG algorithm I represent my geometry in half-edges and described an algorithm that cuts a polygon using another plane.

Now I'm going to explain how to build the geometry of a brush, which is the most basic primitive in my CSG algorithm.

Brushes

A brush is a Convex Polytope, which is essentially a list of planes.
You create geometry from a brush by calculating all the intersections (which will be our vertices) of these planes, and creating our half-edges and polygons from these.

But before we begin, a word of advise.
You have to make sure that your data is clean otherwise you'll run into all kinds of wonderfully weird bugs.
What you really need to check for, and you should write some code to do this, that you don't have any duplicate planes, or planes that are -almost- the same.

So how do we build geometry and half-edges from this set of planes?
There are two methods that I know of.

The "standard" way

The first one is the most commonly used in game engines:

You create a big polygon by projecting an axis-aligned rectangle onto each plane, which is aligned by the most major axis of the normal of the plane.
You then cut this polygon up, using the polygon split method i described in my previous post, using all the other planes in your brush.
You then merge all the half-edges and turn it into a proper mesh.

Now the problem I have with this method is that first of all, it works the best when your brush is at the center in worldspace, the moment your brush is placed beyond the size of your axis-aligned rectangle it'll fall apart.
You can of course make that rectangle really large, but the problem with that is that when you mix numbers that are both very large and very small that your floating point errors will end up getting worse.
Another problem is that at the end you need to start to merge your vertices, which means comparing coordinates which is dangerous because floating point calculations are not exact, and you might end up either merging vertices that shouldn't be merged, or end up not merging vertices that should.

The "precise" way

The above method might very well be good enough for some applications, but I prefer a different, more complicated method.
It's a complicated SOB, so if I'm too fuzzy about some details, please let me know.
Keep in mind that you need to understand half-edges before you can comprehend this algorithm!

In the first step we calculate all the intersections of all the planes, and we make sure those intersections also lie on the inside or on all the other planes, because some planes also intersect somewhere outside the brush.

So at this moment you might be thinking "How can we possibly create polygons out of that??", "And how can that possibly be more accurate than the above method?" or "Maybe I should get some coffee..."
Now, I can't help you with the coffee, but bear with me, all will be revealed.
(Good thing I didn't accidentally write down "bare with me, all will be revealed"!)

Let's go over what information we have at every intersection:

We have the location of the intersection
We know which planes intersect at each vertex
We know that each plane will create 1 polygon
We know that where two planes intersect, we'll have an edge
We know that each edge will have two vertices

(Well actually a plane may actually only intersect at 0, 1 or 2 vertices, in which case you should just drop the plane.)

So now if you visualize this, you'll have multiple edges (defined by a pair of planes) ending at your vertex.
So, at this moment in time we only know one side of the edge.
Hmm... that sounds familiar.. that almost sounds like.. a half-edge!

Now look at this picture:

The green arrows are the half-edges we can build for every vertex.
The Red arrows are the half-edges that we know would be build for other vertices, but we don't know them yet.
However, we know that the edge formed by a pair of red/green arrows would share the same pair of planes (A/B , B/C and A/C in this case), so we can use that information to link both sides together!

The next issue is then, how to put the half-edges in order?
If you look at the picture, what do we know about our edges:

We now know both half-edges on each full-edge
We know that we'll have two full-edges on each plane (let's call them E & F)
We know that E will go to F -OR- F will go to E.
We know both full-edges on a plane share one vertex, but only one of these full-edges will be on that plane/polygon, so either E or F will not have this vertex.
We know that the order of half-edges or vertices in a polygons are consistent (clockwise or anti-clockwise)

So if we check the orientation of E going to F and F going to E, one of them will have the 'correct' orientation (which depends on how you define the order of your polygons).
After that it's a just matter of setting a pointer from one to the other.

Theoretically you could probably get away with only checking the orientation of 2 edges, and then using that information to iteratively build the edges around the edges with known orientation, it would probably be pretty complex and I haven't tried this.
It would, however, be more accurate.

Keep in mind that if you can't find 2 full-edges on the same plane, then you're dealing with a plane that only intersects at an edge and needs to be dropped.

Once you've done that, the mesh will be done.

In part 3 I'll start explaining the CSG algorithm itself.

Realtime CSG - Part 1

2009-12-01T08:12:00.022+01:00

Yesterday I got an email asking if I could explain my real-time CSG algorithm.
So I figured I might as well blog about it.

(CSG stands for Constructive Solid Geometry by the way)

I'm doing this from memory, so hopefully i'm not missing anything, please don't hesitate to tell me if something isn't clear to you.

About Numerical Stability

Before I begin, I need to stress that with these kinds of things you
really have to worry about floating point errors.
As you might know, floating point numbers have limited precision and
cannot possible hold a number with infinite precision.
If you divide 1 by 3, you won't get 0.3333333 with 3's into infinity,
instead you'll just get 0.333333343 (single precision).

Above all, consistency is more important than accuracy with geometry
on a computer. Otherwise you always end up with coordinates that are
almost the same, but never quite the same.
You'll need to use 'epsilon values', which is a small bias
(for example 0.01), when comparing coordinates or distances.
This is because you cannot assume that two calculations that are
equal from a mathematical sense, will produce the same result.

For example:
a/b does not (necessarily) give the same result as a * (1/b)
a*(b*c) does not (necessarily) give the same result as (a*b)*c
etc.

So, for example, when you determine the distance of a point to a plane you need to define for yourself that a point will be:

on the negative side of a plane when it's distance is < -epsilon.
on the positive side if it's distance is > epsilon.
on the plane itself if it's distance is between >= -epsilon and <= epsilon.

Make sure that you don't mix up, for example, > with >=, or you'll get all kinds of weird hard to track down bugs!
Be consistent!

Half-edges

I use a half-edge data structure to represent my geometry, you can find a basic explanation of the half-edge data structure here.

For my CSG algorithm you'll need a couple of basic methods.

First of all you'll need a method to create a pair of half-edges (with a new vertex) in between two other half-edges, which essentially splits a full edge in two and inserts the new vertex in between.

Polygon cutting

Another thing you'll need is a method to cut a polygon with a plane.

It works like this:
You cut a polygon by looping trough all your vertices, and for every vertex determine if it's on the positive side (outside), the negative side (inside) or -on- the plane you're currently cutting with. (using epsilon values like I mentioned before)

If all vertices are on the plane, then you've got a duplicate plane and you'll need to remove that plane (quite frankly, you should've detected that before you start cutting)
If all your vertices are on the 'outside' or are on the plane then you need to treat the entire polygon as being cut.
If all your vertices are on the 'inside' or are on the plane then your entire polygon wasn't cut by the plane.
In all other situations you'll need to cut your polygon into two pieces.

You do this by finding the two vertices where the polygon was intersected by the plane.
If the vertices you find just happen to lie on the cutting plane you won't need to calculate any intersection, but often you'll need to calculate the intersection point of an edge with the cutting plane, and then use the half-edge insert method I mentioned earlier.

The big advantage of half-edges here is that when you split the half-edge, you automatically do it for both polygons on both sides of the edge.
And since you won't be calculating an intersection when a point is already on the plane, you won't be splitting it twice and everything will be nice and consistent!

When you have an edge to split, you may have an edge that goes from the inside to the outside, or an edge that goes from the outside to the inside.
Now what is -really- important is that you always calculate the intersection point in the same direction.
What this means is that if you do:

myNewVertex = myCuttingPlane.Intersect(myInsideVertex, myOutsideVertex);

Then you don't mix it with:

myNewVertex = myCuttingPlane.Intersect(myOutsideVertex, myInsideVertex);

When you calculate your intersection point, stick with one direction!
Otherwise you'll end up with some vertices that are biased towards one side of the plane, and other vertices that are biased at the other side of the plane.
So make sure you're, once again, consistent here.

In the part 2 I'll explain how to build geometry from
brushes (convex polytopes), which are the building blocks of my CSG algorithm.

Update:
Created a repository for the code.

Adventures in virtual texture space, part 16

2009-11-25T09:35:00.000+01:00

The last couple of days I've been cleaning up some parts of my code and preparing for when I can add variable sized compressed pages, which may or may not include normal and specular maps.

Unfortunately my code wasn't build with that in mind, and now it'll take some serious refactoring work to make my mip generating code work with it.

What really annoys me is that if only one tiny sub-page in a higher mip page has a normal map, then the entire mip page will need a normal map too.
Sure, it'll compress nicely, but I can imagine that this will complicate rendering, that you may or may not have a normal map at a texel basis.
I suppose this will have to be handled either at a per mesh level, or just give everything a default normal map.
I'm probably going for option no. 2 because it'll be safer and simpler.

Besides, I need to reserve the texture for it anyway.

Also tweaked my algorithm to combine polygons a bit, and I'm now using fewer pages for the same geometry.

Adventures in virtual texture space, part 15

2009-11-18T08:17:00.000+01:00

For the last couple of weeks I've been working at a client in Utrecht, a city in the middle of the Netherlands, but I live in Capelle aan den Ijssel, which is a small city which has grown into the much larger city of Rotterdam.
The problem is that traffic between those two city is horrible.
If there wasn't any traffic it would take me 45 minutes, but it actually takes me 2 to 3 hours.
Well, it would take me 2 to 3 hours if I didn't get up at 6, eat my breakfast in the car, and drive like mad to avoid the rush!
So for the last couple of weeks I've been in a constant state of tiredness.

Anyway.
Since my last update I've written a idtech-4 shader parser so I can get more correct textures.
Before I would just take the name of the shader and let the importer kinda guess which textures it would need.
Fortunately most of the time the shaders and their textures had predictable names, but not always.
Parsing the shaders also allows me to get back the normal and specular maps, which should be useful when I start to implement lighting.

Other than that I downloaded the beta of Visual Studio 2010, and man, those profiling tools rock!
I haven't tried them on C++ code yet, so I'm not sure how or if they're any good there, but for managed code they're awesome!
Can't wait for it to come out of beta.

I also optimized my code a bit, and now it oscillates between 3-5ms per frame (300-200fps).
It takes about 2ms for the whole readback part, which is more than I would like.
(And I'm pretty sure this could be done a lot faster in C/C++ where you can do all kinds of smart pointer tricks etc.)
This makes me think that the analytical solution that I've been thinking about could be a lot faster.

Other than that it also takes about 2ms to render everything, but I expected that since I'm not doing anything remotely smart, at the moment, when it comes to rendering geometry.. I'm basically just drawing the entire level in one draw call right now.
The fact that the vertex count is way above 200k certainly doesn't help ;)

Adventures in virtual texture space, part 14

2009-11-09T14:18:00.002+01:00

This is just an update to show my progress.

Texture coordinates are now generated correctly, and popping of pages is extremely rare now and basically only happens if you travel trough a wall.

Note that I haven't put the texture compression code in yet, so IO performance will actually get better in the future.

Also, the frame rate in the video is rather chaotic, this is due to the screen recorder competing with the application for resources.

Adventures in virtual texture space, part 13

2009-11-06T09:10:00.001+01:00

Since my last post I've been working on cleaning up my tool set and breaking it up into several different pieces instead of one huge monolithic tool which did all the processing.
I really needed to do this because my processing time jumped up from 10 seconds per level to more than 20 minutes, which is clearly unacceptable.

Splitting it up into multiple pieces allows me to skip the processing steps that go before whichever part I'm modifying.
It also allows me to cache and pre process some content, such as the textures, for easy processing.
I'm not completely done with this yet, but hopefully it won't take much longer.

Other than that I've implemented my own disk cache code, and what a difference it makes!
Right now you wouldn't be able to tell if the level was textured normally or virtual textured, other than if you pass through a wall you have one or two frames of lower resolution pages.

I've pre cached all the smallest MIP-levels, so they're always in memory, this is to ensure that no matter what you always have at least a lower resolution version of your page in memory.
These cached pages cannot be unloaded as well.

All in all right now I'm allocating a whopping 500 Mb of page cache memory, but this should decrease a lot when I put the new texture compression code in which I mentioned in my previous posts, the idea is to store compressed textures in the cache and decompress them on demand.

After a while, hiccups appear in the application, and I'm not entirely sure what's causing them.
It might have to do with certain areas in the map which have lots and lots of different pages visible, which can probably only be fixed by improving my tool set.

I've also noticed that the TextPrinter I'm using from OpenTK has some pretty horrendous memory leaks, which makes my memory consumption grow rather rapidly.
I'm currently using an older version though, so this might already been fixed.

Adventures in virtual texture space, part 12

2009-10-28T10:32:00.019+01:00

So the last time I mentioned that I managed to compress my textures to about 6Kb, and theorizing that it's about the same compression ratio that Id software has.
Obviously Id software, next to simply being awesome, have many more resources compared to me to get their texture compression just perfect.
So I was quite happy with myself that, using their published papers, I was able to get it the same results.

Unfortunately, as Brian Karis mentioned in the comments, I was wrong.

6Kb wasn't per texture but for all the different material channels, diffuse/bump/specular, combined.

To get the same compression ratio I would need to get it down to 2Kb.

Of course I could just crank up the compression ratio, but I didn't really like the results if I did.
That being said, if I convert the results to dxt5 after decompression I'd lose some more quality anyway, so in the end cranking up the compression ratio might be acceptable.
But I really wanted to see how far I could go without decreasing the quality.

So I started to experiment with Burrows Wheeler transformations, which do some clever stuff to change the order of bytes so that when you perform RLE (Run Length Encoding) on them, the compression ratio ends up being better.
And look at that, it worked like a charm!

The file size got down to 2Kb.

But it's slow. REALLY slow.

The algorithm scales horribly, and on a 64Kb buffer it took seconds to finish.
Decompression took >10ms, which is a lot faster than compression, but still not good enough.

Sometime later, after trying all kinds of things, I tried doing RLE both before & after the transformation, just to see what would happen.
The reasoning was that if I first decrease the size of the buffer, by compressing it a little with RLE, then the Burrows Wheeler process would be faster.
After that I would then do another RLE over the resulting buffer to increase my compression ratio somewhat.
I expected this to be a little faster, and probably have somewhat worse compression overall.

To my surprise now the total compression process was MUCH FASTER only taking 14ms.
Decompression only took 3.2ms overall, and the file got about 100 bytes SMALLER, which is somewhat counter-intuitive.

Result: 1899 bytes for an 128x128 RGBA texture.
(the alpha channel is a solid color though)

Adventures in virtual texture space, part 11

2009-10-23T16:27:00.004+02:00

I've been working on implementing the texture compression ideas from the "Real-Time Texture Streaming & Decompression" paper in my virtual texture implementation.
I couldn't just use the code and port it this time because this paper only has the decompression code, and I figured it would probably be easier to write everything from scratch then to try to figure out how the compression side would look to perfectly work with the given decompression code.
It's not implemented into my VT demo (yet), but I have some results.

Right now I can decompress an 128x128 texture in 2.5ms, and it ends up about 5-6kb, and that includes an alpha channel.
I don't think i can get it much smaller, at least i don't know how to do that without seriously degrading performance, and the quality is already less than i would like.
Eventually i'll see how much of a difference it makes when i turn this into a YCoCg/DXT5 texture, in which case there might not be much difference in quality when comparing the original and the compressed one (since DXT5 already reduces the quality)
The speed can probably be increased several times considering this is written in plain vanilla C#. Languages like C or C++ are much better at this sort of thing because you can do all kinds of pointer tricks that you cannot do easily in a managed language, although i might try C++/CLI eventually.

Like the paper I'm converting my RGB(A) texture into YCoCg(A), separate the channels, and then downsample the Co and Cg channels (which actually makes no real visual impact).
I then splice the buffers up into 8x8 blocks and pass them trough an DCT converter and quantize it all.
Unlike the paper I'm not doing run-length and Huffman encoding on a block basis, but i'm doing this over all blocks. Eventually it might make sense to do the encoding on a block basis, to make it easier to multi thread the decompression, but I'm not so sure it's a good idea to have a Huffman header on a per block basis, I'm think it would be more efficient on a per texture basis.

In the "From Texture Virtualization to Massive Parallelization" paper they mention they have "diffuse, specular, bump and cover/alpha" channels for their tiles, and that they have "Typically 2-6kB input, 40kB output".
Which makes me wonder if they have this 2-6Kb input per 'texture', or for all those channels combined.
I can't imagine that it's for all the channels combined, because 40Kb is a 128x128 texture with 2.5 bytes per texel, and they use 128x128 tile sizes as an example in the same PDF.
So it seems to me they have 2-6Kb per tile, which is about the same I have right now.
The lower limit of 2Kb is probably for grey textures that only have 1 channel.

The birdmen cometh

2009-10-13T09:04:00.006+02:00

So yesterday my parents came back from France, from their second home i mentioned before in a previous post.

While they where in France my brother and his family visited them and he helped them cut down a couple of trees.

So my parents showed me a video of my brother perched up in a tree,
sawing off the branches.

A little while later his 3 year old son comes out of the house,
barely awake, just woken up.

He looks up, and sees his father sitting there in the tree,
which he obviously didn't expect to see.
Somewhat puzzled, he then says (roughly translated from dutch):
"Daddy, surely you're not a bird!?"

Classic.

Adventures in virtual texture space, part 10B

2009-10-12T21:43:00.011+02:00

Like I promised in my last post, here are some images.
On the left you can see the original texture, the other two are the result of YCoCg/DXT5 compression.
The middle one is with the simplification used in the
"Real-Time DXT Compression" paper I talked about, the right one is without it.

Here you can see that there's an orange border around

all the yellow edges. In the middle one there are also some

bright green blocks.

Everything is blocky after compression, has a

washed out red appearance, and in the middle

there are some purple smudges here and there.

In the middle image there's a red glow around the top of

the yellow stripes, while the black stripes have a redish glow.

The right one isn't that much better, but the glow is more yellow,

which makes more sense since there's no red in the original.

When you look at the yellow stripes from some distance,

the middle one looks green, unlike the left and right

one which remain yellow.

I'm pretty sure these artifacts would be far less visible on higher resolution textures, but here all these artifacts are rather visible.

Update: Updated images with higher resolution versions.

Adventures in virtual texture space, part 10

2009-10-12T13:51:00.012+02:00

Texture compression

Yesterday night I managed to spend some time on my virtual texture project.
I got sick of just fiddling around with all the stuff I already build, especially since it didn't really produce that much results.
So I figured it would be better to implement YCoCG/DXT5 compression.
Since time is a problem for me, I simply copied the code from the excellent
"Real-Time YCoCg/DXT5 Compression" paper and converted the C code into C# (since that's the programming language I'm using right now).

Conversion was pretty trivial, but unfortunately there seemed to be some inconsistencies between all the papers on this subject, so it took me more time than I would've liked to find the right combination of compression and decompression code.
It also turned out that somewhere in my image conversion chain my red and blue channels where reversed somehow? Still not sure exactly where it went wrong, didn't have much time, so i simply swapped them, which worked.

Unfortunately the quality was a big let down.
I'm guessing Id software simply uses higher resolution textures for Rage, so it's less obvious, but with some of the quake 4 textures the artifacts get really ugly.

I noticed that in the "Real-Time DXT Compression" paper (the prequel to the former paper) at the top of page 12 they mentioned that a line of code from 'EmitColorIndices' can be simplified from:

result = ( !b3 & b4 ) | ( b2 & b5 ) | 
         ( ( ( b0 & b3 ) | 
             ( b1 & b2 ) ) << 1 );

result = ( b2 & b5 ) | 
         ( ( ( b0 & b3 ) | 
             ( b1 & b2 ) ) << 1 );

mentioning that

Evaluating the above expression reveals that the sub expression ( !b3 & b4 ) can be omitted because it does not significantly contribute to the final result.

Well maybe it's just me, but I DO see significant differences, and replacing their 'improved' version with the 'unimproved' version increased quality a lot for me, especially with anything yellow. (I'll try to post some images later on)

(Don't get me wrong though, other than this little thing, it's an excellent paper and very valuable resource!)

Anyway, with YCoCg/DXT5 compression my page tiles shrunk 4x and performance increased a lot, so I'm quite happy about that.
I had a couple of frustratingly moments in the past where I thought I fixed my page loading performance, but it turned out the be caching, so I replaced everything with uncached memory mapping, and everything still ran rather smoothly.
Even though reducing the size of my pages on disk helps with locality and therefore latency, I honestly thought that throughput wasn't really part of my performance problems, at least not yet.
Apparently I was wrong.

I haven't tried the more advanced "Real-Time Texture Streaming & Decompression" stuff yet, but that should increase my performance even more.

Now that I've mentioned all these papers, I should also mention "Geospatial Texture Streaming From Slow Storage Devices" which is another paper written by Id Software, the latest one if I'm not mistaken.
Even though it's, oddly enough, about the older megatexture/clipmapping technology rather than virtual texture technology, which makes me wonder if they're mixing megatexure for terrain with virtual texturing for everything else, there is some rather interesting stuff in there, so well worth the read.

Possible analytical solution

Other than that, I have this vague idea concerning virtual texturing. I could have a hashed grid for each mip-level, and then store which pages are potentially visible from within each hashed-grid cell. I can then use this to sort my pages in my virtual texture file, and perhaps also use this at runtime to determine which pages are (potentially) visible when.

It would avoid having to do a read-back, and it would actually work with transparent textures.
Another thing would be that it would allow me to 'look ahead' to determine which pages might be visible in the future when i move in the direction i'm facing (or something similar).
I would need to load more pages though, most of which, i'm guessing should, be cached on the CPU side.. Hopefully this would be offset by the better (theoretical) locality of it all.

Somebody beat me to it!

2009-10-07T16:30:00.007+02:00

I was planning to, eventually, try to optimize some parts of virtual texturing using OpenCL.

But now it seems someone has done this pioneering work before me!
(using CUDA)

Check out this post from Charles-Fredrik Hollemeersch.
Perhaps some of you may recognize the name as the guy behind Tenebrae.

According to their Poster they seemed to have presented their results at the GPU Technology Conference in San Jose, California.

A chapter about this can be found in the upcoming book
"GPU Pro: Advanced Rendering Techniques"

Awesome.

Adventures in virtual texture space, part 9

2009-10-02T22:39:00.003+02:00

Awesome, I discovered that if I use bigger page sizes, my level would display much more smoothly.
Not because bigger page sizes are better, but because the code i was using to update my indirection table was god awfully slow!
(and the bigger the page size, the smaller the indirection table)

In the crytek paper they mention a trick where they basically render their page changes into the indirection table instead of uploading a texture.
Sounds like the next step for me!

Now if only I had some time to actually do this.. hmmm

Oh and defrag your harddisk when working on virtual texture tech!
It helps!
A LOT

Adventures in virtual texture space, part 8

2009-09-29T10:44:00.000+02:00

So yesterday I had a little bit of time to try a couple of small things.

I changed the page sorting, first sorting the pages from high mipmap level to low mipmap level, then from more to less visible (by counting how many samples I find for each page in the readback buffer).

I also decreased the amount of pages I store in my GPU side page-cache, because I suspect that OpenGL updates the entire texture even when I only update a small part of it, and a smaller texture would upload faster.

Next to that i fixed a small bug where a buffer wasn't reset properly.

Oh, and I defragmented my system :)

And lo and behold... my virtual texture app worked flawlessly!?
No popping at all!

So naturally I wanted to figure out which of my changes was responsible for this!
.. and then my wife pulled me away from my computer ;)

I guess I'll have to look at it next time I have time, but I'm really happy at the current results!

Adventures in virtual texture space, part 7

2009-09-28T09:58:00.004+02:00

Yesterday I spend a little time on my VT project, fiddled with priorities and got a good speedup by rewriting my threading code.
I wasn't lock-free data structures before, and now that I am things are much better.

That said, I did notice that in my profiler i'm now spending *a lot* of cycles in my lock-free data structure.
I'm assuming this is because the IO thread is often waiting for things to load.

I've now capped my IO thread queue to x items, assuming that before the thread would ever load the last texture in the queue it would've already been supplemented with new items anyway.
This way the response time is increased, and i don't run the risk of infinitely growing my queue.

This is still a part that i'm experimenting with, and i still need to try a lot of the stuff that's been suggested to me in the comment section of last couple of posts.

Once again, my test data is far from optimal.
In a perfect situation you'd have roughly 1:1 pixel to virtual page texel ratio, but i sometimes need 32x more than that.
This is because of lots of textures 'stamped' onto the geometry, and lots of tiny slivers of geometry that use their own unique textures.

This makes me believe that there are two ways to building virtual texture content.

One is that you build your virtual texture as a big texture-atlas, where although the textures themselves are only stored once (subdivided into pages), the pages themselves would actually be used many times in the indirection table.
UV coordinates would be calculated to take maximum advantage of this.
It might be somewhat tricky to do with multiple mip-levels, but it would speed up file IO and would remove some of the pressure on the page cache.
The UV coordinates would require more area, and the more uniquely textured area you have, the less efficient this would become.
This technique would be very close to regular, non virtual, texturing approaches, but would basically give you automatic texture management.

The other approach is to uv-unwrap all the geometry, avoiding overlapping unless the geometry truly lies on the same plane in world space.
The new UV coordinates would have to be aligned as much as possible with the original UV coordinate axis, to avoid the texturing looking different.
After this the original UV coordinates, and the textures belonging to each piece of geometry, would need to be rendered into the virtual texture.

This would more easily remove all the stamping problems I'm having, since the 'stamp' textures would be rendered on top of the original geometry (it would require some sorting though, somehow), and improve page locality.
Texel density would also be uniform across the geometry, which can also be a bad thing, lo-res textures could potentially use much more memory (like cube-maps which are processed as regular textures).
It would also be harder to re-use identical pages with this technique, since the chance that 2 pages are identical would probably be much smaller.

Also I tried rendering all my textures transparently, just to see how it looked, and I realized that using the readback approach to discover which pages has a serious defect: it can't look beyond the first surface, and since you might not have a page loaded yet, this won't even work with texture masks.
This is clearly a situation where an analytical approach would be superior.

Alas, I won't be able to spend as much time on virtual textures as the last couple of weeks.
I'm going to work at a client for the next two months, instead of at home, so the little time i can find will be fragmented at best.

Adventures in virtual texture space, part 6 B

2009-09-23T10:12:00.002+02:00

As promised in my last post, here's a video of what i got so far.

Random thought:
I'm wondering if it would be useful to have automatically generated page 'samples' spread around the level, each containing a list which pages are near it. That way it would be relatively simple to 'look ahead' and determine which pages could potentially be required in the near future.

The samples would contain all the pages for a specific miplevel in all directions and limited to the distance to the sample where a miplevel would be used.

Since this would only be possible for static pages / geometry, pages for dynamic objects would have to be handled differently.

Potentially, this could remove the need to do a readback completely..

But would this approach be faster? It could be more accurate though.

Maybe navigation meshes, if they're accurate enough, could be used to simplify the process of creating the samples.
The same information could be used to determine which pages could never be visible.
It would look pretty horrible when some pages are missing but turn out to be visible after all though.

Adventures in virtual texture space, part 6

2009-09-22T13:49:00.005+02:00

Yesterday I was working on my virtual texture code, and there's only one bug left (that i know of).

I haven't had much time to look at it, but it fails to load some pages when the page-cache is full for some reason, so it probably has to do with the code that kicks out unused pages when the cache is full.

That aside i'm having some problems with loading my pages from disk.

If I schedule pages to be loaded right when i discover i need them, and just keep adding them to the list, i end up with an ever increasing list if i move around fast enough, because the disk IO simply can't keep up.

So i tried a couple of things, one of them being counting how many times i have a reference to each page in my readback buffer, and giving the pages with the highest ammount of references the highest priority.

After all, the more visible it is, the more imporant it is to load!
That helped somewhat, but still caused a lot of pages to be loaded and uploaded which aren't visible, yet might actually kick out pages that would be more likely to be visible soon.

The next thing i tried was to remove all the pages from my scheduler that aren't visible in the current frame, but that caused pages to not get loaded at all while you move your camera.

A couple of things that i'm going to try:

A CPU side disk cache, i only have one on the GPU at the moment.
Compression, hoping that'll decrease all these problems simply because loading would be faster and the list wouldn't grow as quickly.
Using adjacency information. By pre-calculating a bounding box of all the texel area in world-space, i can sort all the pages by how close they are to each other, and perhaps do some analysis on what is likely to be visible soon, and what would be unlikely to be visible soon.
The source material I'm working with is pretty horrible because it has a lot of decal textures which take up extra pages on the screen, and there are simply too many different pages on the screen at the same time. Building my own CSG preprocessor would allow me to optimize this more easily, as apposed to trying to fix a relatively arbitrary list of triangles with all kinds of materials.

My good friend Volker suggested a couple of things i could try:

If you know if a page is to be loaded for the current frame, it may be wise to put the higher and lower mip levels of that page in the queue too. (but only if there is nothing else)
Kick out pages by random instead of last used or least frequently used caching schemes, apparently the worst case is better, so that's worth a shot.
(Obviously no pages should be kicked out that's visible in the current frame)
Using memory mapped IO.
Volker: "in my tests, mmap io made a difference from 10mb/s to 500mb/s. (using the disk cache)"
My biggest problem is latency though.

So does anyone out there have any good ideas on how to determine which pages should be loaded & which pages should be kicked out?

I'm going to see if I can upload a new video of my test level tonight.

Adventures in virtual texture space, part 5

2009-09-17T13:48:00.004+02:00

Today I've spend some time improving my tools and they're much simpler and faster than before, it only takes about 20 seconds to convert a quake4 level into a 16384x16384 virtual texture file and a separate geometry file. I'm quite happy with the tool as it is, there are only a handful of things i still want to do such as trying to rotate an allocated texture space to see if it'll fit better and forcing a texel density to some sane (maximum) limit.

Before i used 128x128 pages, and used texture-arrays (which are basically 3d textures where the z direction alway uses near filtering) with a depth of 512 layers.

This worked out pretty well because you never have any bleeding artifacts between pages.
It is possible to have visible seams between 2 pages that are rendered next to each other if they have a strong enough contrast right on the edge between them, the seam looks as if it's an aliased edge.
However i would consider it extremely rare, i only managed to see such a seam when i purposely made some handmade pages to see if it would happen at all, i couldn't find one when i looked at it in more real-life artwork.

So today i tried using smaller pages, but this caused some problems.
First of all, since i make the pages smaller (say 64x64 or 32x32) it uses less texture space, therefore i need more pages for the same amount of texels.
In theory, smaller pages should be able to match what i render on screen more precisely.
However, since my texture-array has a hard limit of 512 layers, even when the width/height is 4x smaller, i had no choice but to create a version of my texture cache that works with a giant 2d texture.
I haven't bothered to put borders around my pages (yet), so there are plenty of artifacts rendering it like that.

But when i started rendering lots of other artifacts started popping up, which apparently where more likely to happen with smaller pages somehow.
So i fixed a couple of these artifacts, some which helped improved performance, and i still have a couple of mysterious ones left.

Eventually i'll probably build something where i can record and replay a certain path trough my test level and i would use it to compare all the different parameters that can be used to build and render a virtual texture and see which ones are more efficient compared to the other.
This will also help to measure performance improvements, or the reverse, when i'll try to implement stuff like texture compression.

Unfortuneatly i probably won't have too much time working on this in the near future, so i'm kinda unsure if i should start on a CSG preprocessor for the level at this moment, because it'll take a couple of days to build and test.

On the upside I actually managed to get into NVIDIA's "GPU Computing Registered Developer Program"!
Which means i have access to OpenCL, which i would like to experiment with, to see if i can use it to optimize virtual texturing.
I can imagine that determining which pages are currently visible, could be done more efficiently trough OpenCL.
It could be done mostly on the GPU, saving CPU time, and would reduce the amount of data to be downloaded back to the CPU.
Another thing it could help with would be to improve texture decompression speed.

Virtual Texturing part 4; importing madness

2009-09-15T12:02:00.008+02:00

So after rewriting the code to load the pages in the background on a secondary thread, i started to write some code to import a Quake 4 level (.proc files) and modify the geometry so it could be displayed using a virtual texture, which would be automatically created from the textures in the level.

The red in the screenshot above are textures that i couldn't automatically discover without hacking. The black areas are supposed to be transparent, but i'm not handling that at the moment.

Here's a screenshot where every color is a different page, which shows that i have way too many different pages on screen at the same time:

There are a couple of things that I've learned about converting existing (Quake 4, but the same will apply to other sources as well) geometry to take advantage of virtual textures:

Quake 4 uses a z prepass to take care of occlusion, so it's geometry is optimized for number of triangles and not so much for using as little geometry area as possible, which means a lot of wasted texel space.
Quake 4 has a lot of transparent textures that are placed upon other textures, which again leads to wasted texel space, as you can see in my screenshots i'm actually not handling transparency.
Since Quake 4 has separate geometry for each type of shader, you might end up with lots of patches of geometry that each have completely different pages. If this was build with virtual textures in mind, it would've been continuous. This is bad because it means more pages need to be loaded into memory.
Sometimes large textures are assigned to a relatively small area. If you don't take that into account you'll be assigning large areas of texture space to something which is tiny.
Without parsing materials (which i'm not doing), discovering the right textures is sometimes impossible.

These problems are causing me some headaches with my test-scene because i'm loading waaaay more pages than i would need to in a scene that would've been build with virtual textures in mind.
I could solve this by building my own quake4 map CSG code, which i might do eventually as i already have some experience with CSG.

However, if you would be building geometry from scratch this would all be easier, as long as you try to keep texel density at a sane level and keep surface area to a minimum. (aka don't assign texel space to something which is never visible)
Sounds rather straightforward, i know, but if you don't think about this up front you might end up with some nasty surprises later on.

Also, allocated texture space should be aligned to page boundaries, if you don't you might end up loading 4 pages when 1 would've been sufficient.

One mistake i made trough this whole process was thinking about a virtual texture as a giant texture, and processing it as such.
The problem with this is that you cannot handle unused pages easily.

Update: scratch that, fixing existing geometry (automatically), to be able to be used with virtual texturing -efficiently-, is hard enough to be considered a dead-end.
I'm going to rebuild the geometry with my own CSG process instead.

Virtual Texturing part 3

2009-09-07T14:33:00.008+02:00

My virtual texture implementation now reads pages from disk.

I'm doing it the completely naive way, reading and uploading a page to the video card *just* before i need it, and i'm absolutely surprised how little performance penalty i'm seeing; only 0.1 - 0.2ms!

I'm guessing that this has to do, at least in part, because of disk caching since i'm using the regular .net disk functions at the moment (and i -just- generated my virtual texture disk file, so it's fresh in the cache).
Update: Confirmed, after a reboot i get horrible spikes of +/- 30ms when i move the camera around on the virtual texture!

Unfortunately .net won't get any memory mapped IO until .net 4.0 comes out, so i won't be able to try this unless i port everything over to C++.

I really should 'acquire' some more interesting test scenes.. a flat polygon is simply too ..erhm.. simple.

Virtual Texturing part 2

2009-08-19T19:33:00.012+02:00

A picture, or well in this case a movie, is worth more than a thousand words:

On top of the screen you can see (pages A/B) how many pages are used (A), and how many there are in memory (B).
The FPS / Ms should really be ignored..

Internally the OpenGL library for C# i'm working with (OpenTK, and i don't have the source-code) or a broken driver is forcing my app to sync to my monitor's refresh rate (60hz), and my recording software is seriously interfering with the timing of that syncing.

Update: putting a timer around the rendering code (and not relying on OpenTK's timer which is always synchronized to the monitors' refresh rate) showed that i was actually rendering around 4000-5000fps (0.2-0.3ms) instead of just 60fps ;)

Other than that there hasn't been any real performance optimalisations yet and i'm doing some things the quick & dirty way (readbacks are not async, page uploads are not async either, and should probably be spread out over multiple frames etc. etc.).
I'm basically just doing whatever i can to get things working like i want instead of trying to use the most optimal OpenGL api mechanisms at the moment.

Next to that there are still some artifacts there, i mean next to the usual video compression artifacts, which i'm trying to track down at the moment.
Just look at 0:30 to 0:32 in the bottom-left corner of the video.
It's weird that the page loading artifacts are there, because at the moment i'm uploading all the required pages before i use them.

The virtual texture is a mere 8192x8192 at the moment and completely in memory (no reading from disk at the moment).
Any larger texture would have to be loaded from disk, my system would probably not like loading a 16384x16384 texture in memory ;)

Filtering is trilinear, Bilinear would obviously be faster and would stress the system less as there are fewer pages to be required to be used per frame.
Seams between pages are more visible with bilinear filtering, but surprisingly hard to spot using trilinear filtering.. in fact, i haven't been able to spot a single one so far!

Next steps would be to fix all the artifacts, start reading back from disk, and optimizing everything.

Virtual Texturing part 1.

2009-08-14T16:06:00.012+02:00

Yay! I finally managed to liberate a little time for me to work on virtual texturing!

Thinking it would help me avoid worrying about additional borders i used a texture-array instead of a large texture for my physical page-cache texture.

(Edit: My test textures just happen to be a 'best case' and with alternating border colors between pages an aliased edge is actually visible, so additional page-borders are still necessary)

Each layer in the texture-array (255 max) is a single page, each page is 128x128, which would give me a cache of 255 x 128 x 128 pixels.

Right now the 'virtual texture' is small enough that it fits completely in video memory, so it's not exactly 'virtual', there's no readback yet either.

There's already a page lookup table however.

The next step would be to readback which pages are visible, upload them and update the page lookup table.

Here's a short video showing the blending between the pages

Yes Yes no fancy graphics or even interesting geometry, I'm on a tight time schedule here people! ;)

While working on this i did realize that the rage screenshot in my last post has something odd in it..

Before i only noticed that all the pages where just nice and square and that they had a nice locality to them.

What i failed to notice, and what i notice now, that it's just plain weird that there's just no blending or any transitions between what i assumed where mip-maps!?

Maybe they're showing pages at the highest resolution? And the ones in the back are bigger because some pages just happen to have a larger geometric area assigned to them? And it just, by chance, looks like some sort of weird rough mipmapping?

Rage

2009-08-07T09:24:00.008+02:00

I was just reading a new pdf about Rage, which i'm sure you know is the new game from id software, and i noticed something interesting in one of the screenshots:

Notice how the texturing is nicely aligned?

Seems to me that it would be possible to build a rough bounding volume tree with which you could determine which pages are potentially visible.
(Something I'm thinking about with my Deferred Virtual Texture Shading stuff)

Interestingly they're still reading back from the gpu which pages are visible at which LOD.
I wonder if that could be done more efficiently on the cpu avoiding the readback completely.

Time Allocation Failure Exception

2009-07-26T21:04:00.006+02:00

The plan was like this.

My parents have a second house in clermont-ferrand which they bought from the money they had left when they moved to a smaller home when my brother and i started living on our own.
I was going to spend two weeks there together with my parents, my wife and my daughter.
After those two weeks i would go home (i have a job after all), and my wife and daughter would stay there with my parents and go home with them another two weeks after that.
Two heavingly, having breakfast, lunch & diner behind your computer coding weeks. The week before we would go my wife was complaining that i was spending too much time behind my computer and suggested i would simply do some more work in those two weeks instead.
Perfect.
In theory..

Ofcourse i didn't get almost any time to program when i was there, and then the day before i was supposed to go home alone we got a call.
My aunt got a 'cerebral infarct' (mild one, but still very scary and serious stuff obviously).
So the next day we all went home.
Together.

Sigh.

Deferred Virtual Texture Shading 4

2009-06-30T09:46:00.005+02:00

Reading a post at gameangst made me realize yet some more advantages to my "Deferred Virtual Texture Shading" (*sigh* i really need to think of a better name for this!) idea:

It's possible to exclude/include objects from the influence of lights, this makes it easier to make sure that you won't have light bleeding through walls when a light doesn't actually cast any shadows.

Some time soon i'm going to try this idea out.

Deferred Virtual Texture Shading 3

2009-06-18T09:38:00.007+02:00

Just realized another good property of my "Deferred Virtual Texture Shading" idea:

Anti-aliasing is not a problem with this technique because all the shading occurs in texture space, and the rendering is 'simply' just rendering geometry with one (or two) textures ;)
Update: Also, if we render our lights in texture space, we can't use proxy meshes to only render light to the pixels that are visible to both the light and the camera. To reduce this disadvantage we could have some sort of octtree/hashed grid/whatever to determine which texture-pages are 'hit' by the light and only redraw those. If we also take page-mipping into account, and only redraw the part of the mip that holds the page we're touching we actually get the "the smaller the light is, the less pixels we process" advantage of deferred lighting back.
Update 2: Another interesting property is that smoothing the lighting over a surface to make it look as if it's more curved than it actually is would be much easier in texture-space..

I really need to allocate some time and try to implement this technique ...

Fluid dynamics experimentation

2009-06-17T09:33:00.003+02:00

Here is an experiment in fluid dynamics i'm working on:

Deferred Virtual Texture Shading 2

2009-06-10T10:11:00.007+02:00

I just read a post on EntherTheSingularity about some variations on a new technique that's roughly based on deferred rendering.

Basically they can work with transparent surfaces and can let you render the lighting at a lower resolution (saving fillrate), which works because lighting is usually rather low frequency anyway.

This made me realize a couple of things about my "Deferred Virtual Texture Shading" idea that i mentioned in a Previous post.

The good:

Since we're rendering in texture space we can render lighting at a lower resolution. We could still combine it with albedo at a higher resolution (probably at render time). Yay!

The bad:

Rendering in texture space can cause light leaks, which would be bad. So texturing geometry (or filtering) would have to take edges into account. Ouch ...

Behavior Tree & Navigation Meshes

2009-06-09T14:30:00.028+02:00

Behavior Tree

Today i've been busy implementing a behavior tree in C#, which was suprisingly easy!

(In case you don't know what a behavior tree is, read this NOW!)

Update: Apparently i the link i provided is in a part of that website which requires (free) registration..

However, the same article is also available (oddly enough) in the publicly accessible part of the website, but split in 3 parts (go figure).

Here are the links.

One of the more complicated parts of the tree is that you don't run the entire tree each frame (which is a good thing!), so it has to be split into small pieces.

I realized that i could probably abuse the whole enumerator/yield construction in C#, and came up with the following solution:

public class Sequence : IBehaviorTransform
{
public IEnumerable<BehaviorResult> Process()
{
   foreach (var node in Children)
   {
       foreach (BehaviorResult result 
                in node.Execute())
       {
           switch (result)
           {
               case BehaviorResult.Success:
                   // If child-node executes
                   // successfully, continue 
                   // to the next node
                   goto NextChild;

               case BehaviorResult.Failure:
                   // Notify parent that 
                   // we've failed ..
                   yield return 
                       BehaviorResult.Failure;
                   // Exit the function
                   yield break;

               case BehaviorResult.Running:
                   // Notify parent that
                   // we're still running
                   yield return 
                       BehaviorResult.Running;
                   // Continue the loop
                   continue;
           }
       }
       NextChild:
       ;
   }
   // Finally, if all nodes are processed
   // without failing we return success
   yield return BehaviorResult.Success;
}
}

Every IBehaviorTransform implementation would return an IEnumerable of BehaviourResult, and as i enumerate my enumerable once each frame, it'll just magically work ;)

Navigation Meshes

Another rough idea of mine is about navigation meshes (Look here if you don't know what those are).

I haven't played with them yet, but it seems to me that it should be possible to simply perform A* on the traversable edges (that are wide enough for the current entity) to find a path.

One problem with navigation algorithms is that they're relatively expensive and either need to be stored and/or re-calculated every x frames..

So you really want to only calculate a rough high level path, and use some more refined (maybe completely different) algorithm at a lower level.

Suddenly i realized that quite often you'd end up with long paths in any navigation mesh where several connected cells/nodes form a chain.

Which means that you could basically just skip the whole chain during the high level path finding, and only check the nodes/cells where you need to make a decision!

You'd probably need to store some basic stuff like the minimum portal size so you can tell in advance if an entity will actually fit through that chain. And you'd need to be able to update the chain in case it's obstructed.

Maybe information about obstructions could be stored at an entity level?

(probably too memory heavy though)

Entities would then expect a pathway to be clear, but when they arrive it's blocked (useful for planning an ambush?), and then will either try to remove the obstruction (if possible and doesn't require too much time and energy) or try another route instead...

Deferred Virtual Texture Shading

2009-06-08T16:11:00.020+02:00

For some time now i've had this, admittingly pretty vague, idea about a combination of deferred shading and virtual textures (aka "mega-texture").

It hit me that most of the attributes stored into a G-buffer during deferred shading are already present in a virtual-texture, so if you combine the two you'd only need to store the virtual-texture coordinates, which would require smaller G-buffers.

Ofcourse that's not entirely true, since a pixel in a G-buffer almost never exactly match a texel on a texture; that's what filtering is for.

But what if we would use our virtual-texture cache as the G-buffer itself?

The problems:

We'd need to fill some of the attributes of the virtual texture at runtime, like coordinates/normals of the texels. However, For static geometry this could be pre-baked, for dynamic geometry this could be cached. (Interestingly enough this sounds a lot like geometry images)
Another big problem is how can we (efficiently) render the lights into this "virtual G-buffer"?

I'm not sure how the last problem could easily be done without losing all the benefits of deferred shading. It would definitely help to have some sort of hierarchy where virtual texture pages are matched with chunks of geometry.

That way we'd only calculate the light for lights who's radius touches those chunks of geometry and their respective virtual texture pages.

It would also make it possible to move the paging algorithm completely to the cpu side, that way we won't need a nasty readback from the gpu to discover what virtual texture pages to upload.

But if (a BIG if) these problems would be solved, it would give us some interesting properties:

Lighting calculations can be cached.
A virtual texture would be able to contain a lot more data, at a much higher quality, compared to G-buffer (which would potentially create a disk space problem)
Rendering the geometry would simply be a matter of rendering the geometry with a single texture.
Transparent surfaces wouldn't need to be rendered in a separate pass. (depth peeling?)
All shadows and lighting would automatically be filtered. (so you'd better have a high-res virtual texture!)
Filters and blurs can be applied on lit surfaces (although there would be some difficulties at cache-page boundaries), which could be useful for subsurface scattering effects.
If you ignore all the caching, all the calculations would be relatively constant, scaling nicely with the amount of geometry and lights.

The questions are, is it possible? and, is it fast enough?

My 92 year old grandfather plays with Wii

2008-07-06T11:31:00.002+02:00

Yesterday my grandfather played Wii sports tennis, i kid you not. :)

My parents, both over 60, are considering buying one themselves.. my mother played hours on end!

Update: My parents actually bought one now ;)

Component Object Systems

2008-06-30T22:32:00.005+02:00

Lately I've been thinking a lot about component object systems. If you don't know what that is, read the following links:

Entity Systems are the future of MMOG development

Game Object Structure: Inheritance vs. Aggregation

A Data-Driven Game Object System

I've implemented the basics of this system in C#.

Still trying to figure out how to do messaging most effectively...

and wondering how to make this all work in a multi-threaded environment

(each component = job in worker thread?) and still keep everything predictable.

I just have this gut feeling that component object systems could be mixed with finite state machines, where an object would remove/deactivate or add/activate components based on which state they're in ...

But it would complicate the hell out of any user-interface around it...