July 26, 2013

Graphics 5-6: Anti-this, pro-that

Good evening our loyal supporters. Welcome back to the same spiderchannel, at the same spidertime.

This biweek's plan was MLAA and SSAO. In addition, some remaining issues with lighting were squashed, and some unplanned effects were added, business as usual.



Selective bloom, requested by artists, was added. Now you can mark objects as causing bloom, even if their native brightness is not enough to catch them in the normal siphoning.


The test object in this picture is not the best one; you will likely see this effect used in the green crystals of the mine, and the windows of the mansion. The aforementioned windows may get something else too, but that's a secret, so don't tell anyone.

This is done by keeping a list of all such marked objects, and rendering that list with color and depth writes off, only writing the stencil. This results in 4x-8x drawing speed, as most graphics cards have that path optimized for uses such as Z-prepass.

This stencil is then used to copy the affected pixels from the picture to the bloom texture.

The bloom threshold was made configurable per-track. As you can see in the picture, the left version is clearly not bloom over-use.


The right is the default threshold, left was altered a bit to show how glorious a bit of bloom looks like.



Lightmaps were enabled in the new system. Before, after, the map.




This is a splash of older tech, and quite laborous for the artists too. However four tracks currently have it, so it should be used there.



MLAA, or Morphological Anti-Aliasing, is a shader-based AA technique. This means it can run in situations where traditional MSAA cannot, or catch edges such as those inside transparent textures better. It can usually reach better quality at the same speed; the quoted numbers for this particular technique are MSAA 8x quality at MSAA 2x speed, but the exact specifics obviously depend on the scene.

While no longer the state of the art, Jimenez's MLAA was used due to the author's familiarity with the technique, and the very decent results it still achieves. The most common competitor, FXAA, is a bit faster, but results in inferior quality - it blurs textures noticeably, which should not happen.


A short overview of the technique follows. First, any jagged edges are detected and marked for processing using the stencil. This greatly improves the performance of the technique, since the heavy shader for the following pass is only run on the needed pixels.

In the second pass, each edge is classified according to a pre-generated map of edges. This map tells the following pass where to fetch information from - essentially, which pixels to combine and the weights for them.

The final pass simply overlays the combined pixels on the picture. Before - after:




Dear reader, meet JJ.


Have no fear though, the glistering brightness that fills you with awe is a bit toned-up in this picture; sadly, the version to make it in the game will be more subtle. This comes as a disappointment to fans everywhere, and there have already been mass protests of over a thousand people outside my residence.



Levels can now choose to have cloud shadows. This completely fake system only fits some levels with a bright, daytime sky with clouds, but there are a few of such levels, and it improves them quite a bit.




It's a fairly subtle effect, and so hard to catch from a still picture, but when moving in the wind it's quite nice.

Itching to hear more I bet? This very fake effect is done inside the sun light, as that's the only thing that should be affected by it. A straight planar top-down mapping is created based on the pixel's world-space position; it's offset by the wind, and then used for a look-up in a specially made texture.

The effect is quite cheap. It does come with the downside that as currently there is no shadow mapping, the cloud shadows (just like sunlight) are visible inside buildings, caves and such. This may limit the levels where this can be used a bit for now, but with the overworld and hacienda, those areas are few and having it there is not distracting.



Finally, SSAO, or Screen-Space Ambient Occlusion.



"Mama, I want contact shadows and dark creases" "Sure thing, hon"

Another fake effect with no real-world equivalent, SSAO usually enhances scenes quite a bit. It approximates global light bouncing by making approximate ray traces around a pixel, checking if those points can possibly occlude some light from reaching this pixel.

Like you can probably imagine, it is expensive. Several tradeoffs were made in order to get it to run on the majority of the user base; it should still look acceptable, while the FPS hit is much less than the usual implementation.

Low - high:
The high variant merely runs at full resolution, and no tuning has been done for that one, as the majority will run on low or off.

The low option runs on a quarter resolution, taking only a single sample per step, without randomness, or an edge-aware blur.

Each of the listed parts lessen its quality somewhat, while increasing speed. First of all, the lower resolution prevents small creases from being detected, limiting the effect only to contact shadows. The upside is that it's 16 times less area, directly resulting in a 16x speedup over the high version.

Second, being able to only take a single sample per step, the information we have to work with is the normal plus a linearized, 8-bit depth. This results in some false occlusions in case the occluder is outside the hemisphere; the alternative however, making positions available, would double the cost of this effect.

The randomness in SSAO is usually implemented via a small normal texture. Its cost (beyond flicker that always results from randomness) is that it changes the step's texture read to a dependent one - named using great wit since the coordinates depend on another texture read.

A dependent texture read is a costly operation, since it prevents caches from pre-fetching the actual read. The exact cost cannot be calculated in a highly parallel pipelined system, but assuming it delays each read by 300 instructions (a typical cache miss), a core clock of 400MHz, and 16 steps, each pixel is delayed by about 12 microseconds. The delay is highly variable due to inter-dependencies, so take that cost estimation with a pinch of salt.

The first couple programmable desktop GPUs could only prefetch textures based on coordinates from a varying (that is, export from the vertex shader) or a hardcoded value. This is still the case for many mobile GPUs, but any desktop GPU from about 2004 onwards supports a set of math operations, such as additions and multiplication, making our set of vectors completely pre-fetchable. Should the target be a mobile GPU, this limitation could be circumvented by making the calculation of those vectors in the vertex shader and passing them as varyings.

As for using a normal gaussian blur over an edge-aware one, it results in some of the occlusions bleeding over a bit, but is about 4x the speed of the alternative. A 2x component comes from the fact that the edge-aware blur cannot take advantage of the bilinear hardware, requiring it to do twice as many samples, and the other 2x from requiring a branch for each sample.


With this, we end today's infotainment. Tune back next time!

July 10, 2013

Graphics 3-4: light me up

Evening, our loyal followers. This bulletin comes a few days early, as no new tech is expected for the rest of the week, just testing and tuning.

These weeks were about lighting, and now we have a running light prepass system. It could be described as more of a hybrid, read on to find out the butler did it.



So what is light prepass?

In traditional forward lighting, you draw every mesh, and each mesh runs a loop over all lights to see if they happen to touch it. As you can imagine, this is inefficient the moment you have more than one light.

The first good solution to this, deferred rendering, draws the mesh data to a set of temp buffers containing the position, normal, and other values. Lights are additively blended to the main image based on the values in the temp buffers.

It works, but it's inflexible in the amount of material variation it can do. Light prepass was designed to be both scalable and flexible.

In light prepass, less mesh data is saved: normal and depth only. The lights are additively blended to a light buffer, then the meshes are drawn, and they decide what to do with the gathered amount of light.



Our new system is light prepass, but by default it avoids the double draw of each mesh, blending the lights with a standard screen quad.

The moment the flexibility is needed, a mesh can draw itself and interpret the light data as it sees fit; but by default, there is only one draw call, as most meshes use the light data in a standard way.




Here we have the first step, ambient light, working. Yours truly has a fascination with the color red; he thinks nothing more of it, perhaps he should.


It's a normal world. This is a new debug view, showing what a normal world looks like, on a normal day. It has already revealed issues with two karts, which would have made them react badly to light (think badgers and mushrooms).


The next frontier after ambient light, point lights. The picture is from a new old map, red light district, with kindly visualized lights.



The other topic for this biweekly session was rim lighting for the karts.


First, one needed to identify the karts, and paint them in this spring's fashionable colors. It may look like red to the untrained eye, but in reality it's a mix of Indian red, crimson, and salmon, with just a hint of blueberry and salvia.


Rim lighting in the graphical world is a trick with normals. You compare the surface's normal with the direction to the camera, and visualize the difference with suitable colors, giving each kart a bit of shiny edges.


That's it folks, a short post this time.

July 8, 2013

GSoC project: The network for you to play online !

Hello world ! my name is Robin Nicollet, alias hilnius, and I'm a GSoC student working on your favorite open-source game ;) I'm going to present you why I'm here and what I'll try to add to SuperTuxKart.

Abstract

First of all, I'd like to thank STK's mentors for choosing me, it's a great honor to work on that project, and I'll do everything possible to make this game as good as possible. I'd also like to say that the community that I found here is amazing, I feel that everybody is welcome here and that's great to have such a good atmosphere.

Presentation

Me

I'm a french student from Télécom-Bretagne, I just finished my first year in this school (2 more and i'll have a master). I've been programming in C then C++ for about 5 years. I know more programming languages but that's not really relevant for this project.

My project

My project is to bring to this game the main features that allow people to play together online. To be quick, that means:
  • Connecting people in LAN (Local Area Networks) or WAN (Wide Area Networks : all over the world).
  • Starting games and playing together.
One of the main features to play on WAN is the lag compensation, which I won't tackle here for timing reasons :) .

If you just wanted to know what i'll do, you're down at this stage.
In the next sections, I'll detail how the connection between people will work and explain some things about network that are necessary to understand my solution. I will talk about playing together later in the summer when that will be implemented and working ;)

Connecting people

Situation

You may or may not know, but SuperTuxKart do not own a private server and cannot deploy a proper and classic client-server architecture. That's why we will ask SuperTuxKart's player to host their own games. As a result, we will provide inside the game an accessible interface that will allow you to start a server on your own computer to host races.

NAT issues

In this part i'll explain details about how NAT (Network Address Translation) works so that you will have a better understanding of IP networks and how connection will work.
I will use NAT to name the devices that does the Network Address Translation.

Your local configuration

Your local configuration at home probably looks like this:

You are in the Local Network. You are behind a first NAT (it is probably a box that you either borrowed or bought to your ISP (Internet Service Provider). Then, your ISP has his own network, with a lot of devices. Then he has his own NAT.

You may wonder: what is Network Address Translation ?

Network Address Translation

(If you want a fully detailed answer, you can read the wikipedia article)
Network Address Translation is a process used first to extend the number of available IPv4 addresses. Your three computers probably have IPv4 addresses matching the formats 10.xxx.xxx.xxx, 172.16-31.xxx.xxx or 192.168.xxx.xxx.
This does not identify you uniquely over the internet, thousands of people have the same address. It identifies you uniquely only in the Local Network. You should also know that each interface of a connected device has its own IP. For example, your NAT has at least two interfaces : one in the LAN network, and one in the ISP network. Each one of them has its own IP address.
What your NAT does, is that each time you send a message on internet (get a web page, connect to a server, anything...), it changes the IPv4 address in that message to its own. A quick drawing will help me explain that :

Request

Your computer sends a message (get the google.fr webpage) and puts his own local address. Then all NAT that stands on the way of the message will "translate" this address. That means they will memorize the IP of the sender, and replace it by their own.
So for example, when the message is in the ISP network, the IP address of the sender written inside the message is the one of your Router/NAT. And when the message travels in the public internet, the IP address of the sender written in the message is the one of the ISP NAT.

Response

When the google server receives that request, it answers to the IP written in the request (the one of your ISP NAT).
But the ISP NAT knows who sent that message in the first place (10.2.3.4). So the ISP NAT will send the response to 10.2.3.4. Same for your NAT/Router, which knows that it's you who made the request (and then doesn't send the response to your computers 1 and 3).

Conclusion ?

You can now understand that if google sends a message to your public address (that is the one of your ISP NAT), that ISP NAT won't know that you're the one who should receive the message, and then cannot route the message.
As a result, if you try to send a message to anybody who is not directly in the "public internet", he won't receive your message.
The solution to that is the STUN protocol and will be detailed in the next section

The STUN Protocol

This protocol carries well its name, because STUN means Simple Traversal of UDP through NATs. Our goal is indeed to establish a connection between two users, let's say Alice and Bob, each of who are behind their local NAT and their ISP NAT. You can find a complete RFC of the protocol here.

How stun works

STUN is very simple : there are STUN servers in the public internet. You send a STUN request to one of those servers, and it will send you a STUN response telling you your public address. If you understood well how address translation works, you'll notice that when the STUN server receives your request, the sender's IP address is your ISP NAT's one. In the response, that server will tell you : "you have a public IP address that is A and a public port which is P.".

If you're asking yourself what is a port, you can see it as how the NATs identify you. If you send a message to the STUN server, the ISP NAT will give you a port number and put it in the message. Then the STUN server will respond to the couple (sender's ip, sender's port). The ISP NAT will know that the port has been allocated to you and will send the response to your local NAT.

As you see, NATs use "NAT tables" to have ip:port bindings and know where they have to forward packets.
You can see that the STUN response received by your computer contains the ISP NAT's IP address and port number.
A detail worth mentioning: some NAT, called symmetric NATs, allocate a specific port for each connection, and do not allow this protocol to work. It's basically a security feature. So I'm sad to tell that it's very likely that you won't be able to play SuperTuxKart online in a company environment (symmetric NATs are used usually by companies).

Imagine now, Alice and Bob want to communicate. Alice and Bob obtain their own public address (which is their ISP's NAT IP address). Now Alice calls bob with her phone and says "hi bob, my public address is A-A and the associated port is P-A". Bob answers and says "Hey Alice, my public address is A-B and the associated port is P-B". Then if Alice sends a message to the address A-B on the port P-B, Bob will receive the message, because his ISP NAT will know that this IP:port couple is bind to Bob's local NAT/Router. And Bob's local NAT/Router will know that the message he's receiving from the ISP NAT is meant to be delivered to Bob's computer.
So Bob and Alice can now talk :)

The only difference in the way STK will work is that instead of using phone calls to exchange public IP addresses / ports, we'll use a SQL database.

The connection protocol in SuperTuxKart

So when you'll want to play online, you'll query a STUN server, obtain your public IP address/port, then you will publish that in a SQL database. After that, you will put in that database which server you want to join. You also get the server's public IP address/port from the database and start sending messages to it.
This server will check regularly in the database who wants to join him. When he knows that you want to join him, he will get your public IP address/port, and send messages to it. After both you and the server have sent at least one message to each other, NATs will have the good entries in their NAT tables to allow a UDP exchange between you and the server.

After that setup, you will be connected to the server and you will be able to play races with other players that are connected to this server.

Conclusion

I hope it wasn't too long, and that you have now a good understanding of why this is necessary to work this way, and why people cannot connect directly to each other.
The networking part is designed to allow people to setup game servers on real servers, so I'm glad to announce you that at the end of summer you will probably be able to run your own SuperTuxKart server !!

Bye and see you online ;) !

June 28, 2013

First graphical two weeks - very progressive, aye?

So, this will be long. Your humble coder will try to make it more interesting by interleaving pictures of cats among the overly technical chitchat.

The roadmap said one should do groundwork, glow/bloom, and a smoothed minimap. All this was done, and in addition, the weather system insulted my pet octopus, so now we have updated rain, snow, and grass (and full wind simulation).

Let's start with the rain. Just as any lvl 30 mage worth their bath salt, the mere presence of me triggered interesting gravitational effects:

The previous rain was done with five cylinders, encircling our player like a Russian matryoshka doll. Each cylinder was set to display both sides, and to use a scrolling rain texture.

While working, this method came with two downsides: it was repetitive (streaks always fell at the same spot), and it was a fillrate killer (ticket 892, among others).

Drawing every pixel on the screen five times, with alpha blending on (= 2x the cost, by having to do a read + write instead of mere write), really hit the weaker, bandwidth-low cards. Integrated ones especially bad, as system memory tends to be slower than dedicated VRAM.

So, for a 1024x768 window, 10 fullscreen draws equals 30mb of traffic. Using an integrated system with DDR2-400 RAM as an example, the system RAM can move 3.2 GB (3.05GiB)/s. If everything were optimally placed (we wish), it would take 9.8ms to draw the rain for one frame. 59% of the 16.6ms allowed budget, if the memory placement were optimal (add 10-20% of overhead to that for a more realistic number). This is also not counting the rain texture read.

Ah, we have a question from the audience: "But it's mostly see-through transparent pixels. Surely those are lighter than colorful pixels in the rain streaks?" - no, they aren't. Even if caught by the alpha test, that would only save the final write, the texture read would still occur, the fragment pipeline would still run. So lighter, but not by that much.

Before - after:

So, what was done? Instead of having five scrolling screens, we now model every raindrop, and it upped the average fps from 30 to 45 on a test setup. Yes, you read that right, every drop. There are about 2500 drops. The simulation is fully done on the GPU, and where each drop falls varies as time passes.

By drawing each drop with a point sprite, we send only one vertex per drop, and overdraw is minimal compared to the previous solution. Updating the rain texture from 512x512 to 32x32 (from covering a wall of rain to a single drop) also did its part, now the texture fits entirely into cache.

The average overdraw should be close to one now. Instead of the previous 10 fullscreen moves, we now move about 2.

The observant reader will note that point sprites are squares, not rectangles, and so there is still half of the space wasted in fully transparent area. This is true, a 16x32 texture with a rectangle billboard would be more efficient fragment-wise. However, it would have four times the vertex load, due to having to send each corner instead of just the center point.




Moving to the next topic, snow. Snow was handled as cpu-side particles, but they fell straight down, and always faced the player, giving them an artificial look.


So what was done with these? Nothing more than fixing the two lacking points. Each flake was made affected by the wind (more on it in the grass section), and to spin around randomly.


Making the flakes spin was an effort a little more involved. Irrlicht's particle system only does billboards, that is, squares that always face the player.  They don't rotate, period.

This left yours truly stumped for a few hours, pondering how to work around the limitation. The solution came in the form of texture magic, brought to you by the symmetric nature of the snow flake. By flipping the texture in-place by various amounts, it gives the appearance of actually spinning snowflakes.


The improvement was profound. You'll need to see it in action, the still screenshots don't fully do it justice.



The grass, which was made to wave in the as-of-yet-unreleased-level Lighthouse, had some limitations. First, there was no wind simulation, it was a sine wave, very repetitive to the eyes. Second, the wind was applied on one axis only, adding to the repetitiveness.

As the first stop towards summoning Jupiter, a proper wind simulation was implemented, via the scroll of 2D Simplex Noise. It blew in all directions, at all strengths, bringing a.. uhm.. wind-like quality to the uhm.. wind.

Then, the new wind was applied to the grass (and trees, and vines, and...) with a nicer shader. Nothing more to report on this topic, for pictures of Lighthouse see the previous post by Samuncle.





Turning our attention to the minimap in the lower-left corner, we notice a certain quality of jagginess. Assuming the player had MSAA enabled, it would look nicer, but with the target group of more casual userbase, not many have the hardware power to do so. Of course, smooth maps are as close to a constitutional right as any, so something had to be done.

After a few rounds of prototyping, the final formula ended up being so: render the minimap at double the original resolution, blur it with a Gaussian blur with a radius of 3 pixels, and make sure it has trilinear filtering enabled.

These steps eliminate most of the jaggies, while keeping the edges sharp enough, giving a nicer look in total.




At this point, the remaining items on the checklist were glow and bloom. However, our resident master artist had a request: mipmap level visualization, so that artists can determine which textures are of too low resolution, and which are too high.


The formula and colors are those from Unity, publicized by Aras P. A big set of thanks to him!

The blue means too low resolution, and red means too high. Original color means just perfect. Of course the measurement varies by the user's resolution, and how far is one looking at the object from. Therefore any decisions based on this should be done after looking at multiple resolutions, and getting as close & far as possible from the item in question.

The analysis on Hacienda showed that the rope had a far too high resolution - memory could be saved there - while the ground and the wheels of most karts were of too low resolution.

The implementation differs a bit from that of Aras; it is not done by texture, but entirely in the shader, giving more freedom and making it easier to apply. If we were happy with a DX10 requirement, even the textureSize uniform could be skipped (GL 3.0 introduced a function to query a texture's size inside the shader), but as we have to override the shader anyway to show this, sending the uniform is little additional effort, and enables it to run on GL 2 hardware.

Obviously there is a speed hit caused by calculating the mipmap level in the shader compared to letting the texture hardware handle that, but seeing as this is a debug option for artists, extreme speed is not needed. Ease of implementation, by not requiring the extra texture, was worth more in this case.




Next up, bloom. No, not her. The technique.


This one is fairly standard fare; a post-processing light bleed effect. We start by capturing the bright areas of the rendered scene. This bloom picture is then progressively minified to 1/8th the size (1/64 the area) halving the resolution at each step, losing no information.

Indeed, such a progressively minified image is of greatly better quality than if we had rendered the captured bloom to the same size directly. The cost of minification is very small in the total effect.

At the small resolution, we then blur it with a Gaussian blur of radius 6. Blurring at a lower resolution comes with the usual benefit that it looks like a much larger blur applied to the full image, at several times faster speed.

This blurred image is then additively blended on top of the scene. There are some artifacts from bilinear sampling, but they are invisible to the human eye in practise, due to the brightness's effect on the eye.




For the final item on today's list, we have glow. There's been some confusion with these terms, so let it be known how I define them: Bloom is a post-processing effect, applied to the whole image, to bleed bright light over, improving the look of sunsets, lava, explosions, and many other parts.
Glow is the object emitting light that is visible without a media - so more of an aura, or a light outline. Glow does not appear on top of the object, but only outside it.


I'm especially happy about the dynamic pink in that last picture. Certainly gives the final finish to any barrel of wheat! (don't be alarmed, the colors are intentionally bad as mentioned in the forum, gently encouraging the more artistic among us to change them ;)

I'm sure everyone is itching to hear how this works under the hood. No? I'll tell you anyway.

At each frame, we build a list of glowing objects and their glow colors. Each object is then drawn to a temporary texture, fully clothed with their given color, updating the stencil along the way for free.

This colorful pastel buffer is then progressively minified, this time to 1/4th resolution. A 6-radius Gaussian blur is applied to spread the glow around the object itself. This glow texture is then given to the list of glowing nodes built earlier.

In order for these glow nodes to behave properly in the scene's depth order, they are drawn by container geometry in the transparent pass. At first I tried to use the objects themselves, scaled to a larger size, but that failed soon enough, as no object was modeled around the origin (!). So the next best thing was used, a small sphere (~20 polys) placed at the object's real origin, not the placed origin.

Why does it not overlay the whole objects then, nobody asked. I'm glad you didn't ask, as this is where the stencil magic comes in. Having marked the stencil earlier for "these spots do not glow", we now ask the stencil to block our drawing to those parts, just for the container nodes.

Altogether, it provides a very nice effect, answering the issue that nitros and other objects were not easily visible in darker levels, such as the sand/egypt track.


Phew, if you made it this far, you're probably too tired to leave a comment. That's ok, I'm too tired to read them until Monday. Have a nice weekend!

June 15, 2013

"Next gen tracks" sneak preview


Hello my name is Jean-Manuel Clemençon (aka samuncle)
I'm the lead graphics artist.
I have been a contributor for a while but this is my first post.

Graphics is an important aspect in our game and since the last version I worked hard to improve graphics.
I made a new track that shows what I'm planning for the future of supertuxkart and two major improvements.

Old (new) mine

I cleaned up the mesh but the most visible improvement is the new lighting system with several lightmaps (and some dynamic lights). It's also more interactive with a Minecart that can knock the player if he forgot to check the traffic light.






Lighthouse

Lighthouse is a next gen track with around 70 000 poly (the average for a track is 20 000). It's the first track that uses our new vegetation shader for grass animation.

The track has also several animated objects like floating buoys in the sea and a dynamic skybox.

Zen Garden

When I made Zen garden in 2010 supertuxkart didn't support lightmaps. So I added some lights and a sunset. Caves are less empty with little blue fireflies.




 I'm not saying any more, you can discover by yourself ;)