Mini Tutorial: What is Deferred Shading

Over at Imagination Technology, the PowerVR, found in Intel chip sets for set top boxes is described in this way:

POWERVR graphics technology is based on a concept called Tile Based Deferred Rendering (TBDR). In contrast to Immediate Mode Rendering (IMR) used by most graphics engines in the PC and games console worlds, TBDR focuses on minimising the processing required to render an image as early in the processing of a scene as possible, so that only the pixels that actually will be seen by the end user consume processing resources. This approach minimises memory and power while improving processing throughput but it is more complex. Imagination Technologies has refined this challenging technology to the point where it dominates the mobile markets for 3D graphics rendering, backed up by an extensive patent portfolio.

Tile based rendering was covered in a previous tutorial. There I described the normal graphics process as having two distinct phases, a geometric transformation one and a drawing one:

for each triangle

• transform it and light it
  
• project to 2d
• clip it to the window

for each pixel in the triangle

• check visibility (usually done with z-buffer hardware) and if its visible
  
• interpolate lighting
• fetch textures to draw on it
• write the pixel with alpha blending if necessary

Notice that every pixel in every triangle is drawn. The problem with this technique comes from the fact that some pixels which are drawn are later overwritten by other pixels from other triangles which are closer to the viewer and thuis obscure the previously calculated pixel. The more triangles overlap in the scene, the more wasted effort occurs. This is explained in the image below:



This is a significant factor in the DTV world. We have relatively few triangles and huge numbers of pixels to deal with. This "overdraw" - calculating a pixels colour more than once - is a major performance factor for us.

Deferred rendering/shading rewrites the graphics pipeline like this:

for each triangle

• transform it and light it
  
• project to 2d
• clip it to the window

For each pixel in the triangle

• check visibility (including overlap) and store reference if necessary

next triangle

for each pixel on the screen

• interpolate lighting
• fetch textures to draw on it

In other words deferred rendering attempts to only shade each pixel in the resulting image once by first identifying how triangles overlap and only storing and shading the closest one at each pixel in the screen. The overlap can be detected very quickly using a z-buffer, present on most graphics architectures. As there are many more pixels than triangles, shading each pixel as few times as possible is a huge win.

The biggest problem for deferred shaders is alpha - transparency. When a triangle is transparent, the triangle behind it is also visible, negating the benefits of the technique and forcing the rendering pipeline to store several copies of pixels, one from each triangle, during the triangle transform stage. It gets even more complex when you think about the fact that we could receive a transparent triangle, then another on top, then an opaque one on top of them - forcing the architecture to remove the first two entries and replace with one reference to the opaque triangle for efficiency. In other words a collapsable stack, performing at incredibly high speeds is required in hardware. An area rich in patents no doubt.

One last point. Deferred shading does not require a tile based architecture such as PowerVR. Indeed, many modern games used deferred shading and it is key to high rendering performance at high resolutions.

ARM Mali Explained and Future Direction of DTV Graphics

Over at ARM there is a "confidential" presentation, freely available. It makes very interesting reading about the current generation of ARM Mali processors, their target performances, availability and future roadmap.

For me there are two very interesting slides. The first is this one, you can click on it to enlarge it:
This slide shows that mali-200 will cope with FLASH lite at low resolutions (SD I guess), but will struggle with FLASH 10 at lower HD resolution. Only Mali-400 will cope with FLASH 10 easily. Its noticeable as well that video post processing - something shaders should be good at - will only be good with the Mali-400. This makes me wonder what the chip manufacturers will ship in 2010? 400 or 200? Even an HD TV GUI is borderline according to ARM. Perhaps its ARM upselling the 400 but the diagram is a little worrying. Anyone from ARM care to comment?

The second slide is only academically interesting at this stage:
There is a real mixture here. Power comsumption is mostly for mobile devices. Composition is of most interest to DTV and comes as a software layer it seems, whilst geometry shaders and OpenCL would be of main interest to gamers with advanced rendering engines and physics.

Love the gal with the crystal ball.

To 3D, or not to 3D, that is the question. ..

Shakespeare may well have written:

To 3D, or not to 3D, that is the question:
Whether 'tis nobler in the set top to suffer
The spins and zooms of outrageous interfaces,
Or to take arms against a sea of dimensions
And by opposing end them.

The first consumer PC graphics cards were introduced in 1995. Previous to that for a good ten years, 3D was available on workstations such as those from IBM, SUN or best known at the time, Silicon Graphics. By 1995 OpenGL was well established (being based on the existing IrisGL from SGI) and with the exception of shaders, little has changed in the graphics world since.

Yet, 15 years later the user interface of Windows from Microsoft and, more telling perhaps, the user interface from Apple remain solidly 2D and we remain with interfaces like the one below:



In the early days of 3D, of course, there were many attempts to bring 3D interfaces to the desktop. PC shows looked very similar to set top box shows of today with a dozen 3D metaphors for licensing/sale. I particularly liked the messy bedroom metaphor. The idea was that your interface was a bedroom (or a house) and you left files, well, wherever, under the bed, next to the cat, on the TV. The claim was that you could more easily remember leaving your notes next to the cat than you could remember leaving them in /usr/ct/home/private/expenses/trips/florida. It never caught on.

One arguably successful user interface in 3D was seen briefly in the film Jurassic Park, running on an SGI. The young Lex sits down, pulls up FSN (File System Navigator) and declares that she knows this system, its Unix. Here is a shot of FSN, which was shipped with every SGI machine (not every Unix machine ;-) ).



It was a file searching utility and genuinely useful. The user saw a landscape of files and could easily find large files or large collections of files or new files (colour) or combinations. It presents far more information than a traditional windowing system can and removes the need to navigate the tree of files, allowing the user to jump to interesting directories simply by clicking on something in the distance.

Useful it may be, but pretty, it isn't.

Another successful 3D interface in the sea of unsuccessful ones is CoolIris. Though many would claim it is barely 3D at all, it presents a wall of images which can be examined and scrolled quickly. The user can very quickly find through visual queues an image in the distance that would otherwise take many clicks to find in a 2D paged scheme. Here is an image:



Again, like FSN, the interface presents information in the distance that a 2D windowed interface would fail to present at all. Again its not generally useful but useful for a specific type of data. However, it is well designed. A video is available on the website or you can download it and install in Firefox.

This is key I think, for the first time in history, with FLASH 10, designers of user interfaces have access to 3D technology and can experiment freely without recourse to programming. So perhaps the technology has not changed much but the useability has. The power is coming into the right hands (after 15 years).

We will see some experimentation at first. Whitevoid, who created Liquid user interface for Rovi, have an interesting 3D portfolio at their website. Meanwhile over at EcoZoo, it gets wilder. Ecozoo illustrates that a 3D interface based on a 3d world metaphor can work but also that it is much slower to navigate and less intuitive. Such interfaces will fail because they do not add to the user experience but subtract from it. Again I'm reminded of the early 3D world for PCs and workstations. The real question is can designers help create a generation of 3D interfaces that are genuinely useful?

Here are some golden rules that I made up for 3D interfaces to succeed. Thornborrows golden rules of 3D interfaces:

1. Use 3d only when it presents more information more quickly than 2d
2. Simplify the 3D as much as possible without breaking rule 1
3. Relevant (focused) information should be "close" to the user
   
4. Present textual information in 2D, not 3D
   
5. Only have supporting visuals such as images and visual cues in 3D
6. Never force the user to navigate freely a 3D world but instead use 2D control metaphors
   
7. Short highlight effects and transitions are ideal for 3D
8. Make it as fast as possible: the performance of 3D needed for a good experience is high

Tutorial: Drawing Trapezoids with a Blitter (and more)

3D without a 3D chip? At HD resolution? at 25 fps? Yes it is possible.

EGG from Osmosys and STMicroelectronics graphics library for the blitter can both draw rotated images. Specifically images rotated about the Y axis and the X axis (not Z). This results in trapezoidal shapes like those below:

These trapezoids can be useful for user interfaces such as in the example below:

However, a blitter, on which they both rely, can only copy a block of memory and can only draw a scaled, flat, square image (not quite true but for simplification I will assume it). How is it possible to get 3D effects from a blitter? The trick is simple: use more than one blit to draw the angled surface and vary the scaling. For example in the case of a surface rotated about the Y-axis (as above), a number of thin vertical blits can be used to draw the resulting image. The scaling power of the blitter is used to simulate the decrease in size of the image as it gets further away. Thus a series of blits can be used to draw a single off angle surface in perspective.

The blitter on modern chips however is very efficient at drawing pixels but quite slow at setting up individual blits. The key then to performance is to reduce the number of the blits needed to draw such a surface.

So how many blits are required? The obvious (and patented technique at the time we created EGG) was one blit per line of the resulting image. This means drawing lots of one line wide blits. The scaling is calculated for each line and passed to the blitter. The drawing below illustrates this:



Incidentally, the part of the source image that fits into this destination line must also be calculated (to maintain correct perspective). However, the bottleneck is setting up the blitter and issuing a blit command. It should be obvious that reducing the number of blits is critical.

Osmosys have patented a more efficient technique, which is now public so I can blog about it.
Instead of blitting every verticla line with a new scaling factor, the technique idetifies the maximum size block of pixels with the same scaling factor that can be rendered using a single blit. In other words, the technique finds a series of rectangles in the destination image, often wider than one line. A diagram helps to explain this:


In the example above, the Osmosys technique uses 9 blits to draw the trapezoid, whereas the original technique uses 26. Thats 3x more efficient in this case. At smaller angles and big images the technique really wins as only a few blits are needed even for a large trapezoid, compared with many hundreds for the traditional technique. The worst case is the same with respect to the number of blits. Therefore the technique is of the order of a magnitude faster in the general case.
There are further optimisations possible but I'm not free to talk about those.

Of course, rotating about the X axis is similar but the blits are drawn horizontally, not vertically.

The technique could be taken further to draw triangles and allow true 3D shapes in their libraries or to rotate images about the Z axis. However, the number of blits could be very large and therefore probably not worth the effort. Its still remarkable however that a blitter, when used correctly can draw many 3D surfaces in HD resolution at frame rates of 20fps or more.

The biggest problem with the technique is aliasing. The edge of the image is very clear and presents so-called "jaggies". At IBC this year Sagem used the ST library to have a 3D interface. To cover up the jaggies, the background was a very strange grey-black grid of lines - highly unsuited to the TV screen but a clever way to hide the problems.

Incidentally, even though the technique developed at Osmosys is I believe optimal, the patent appears to be badly written (ie not by a graphics expert) and thus easy to work around but then again, I'm no lawyer.

Ekioh SVG Engine

Ekioh provide an SVG engine. Described as :

(the) most advanced user interface engine, available for any embedded device such as a television, Set Top Box (STB), mobile phone or portable media player. Utilising the latest Web 2.0 standards from the W3C, the Ekioh UI Engine can provide a user experience second to none, with a completely customisable user interface and comprehensive integration with media controls.

Some details can be found at Ekiohs website. It appears to be the engine I saw in action on Dreamparks stand at IPTV world forum 2009 and blogged about previously. Ekioh is a small company formed by ex employees of ANT but with some good momentum judging by their press releases.

SVG, technically, plays to the same space as FLASH and Abobe creative tools can output SVG in some form. The hype surrounding SVG right now may die down once set tops have FLASH 10 and can play many of the games now available on the internet. In the mean time there is little to chose between FLASH and SVG. They are both vector formats that have been bent to make use of images through blitting and will also exploit OpenVG/GL-ES as it becomes mainstream.

Guessing right now you would have to say that FLASH has the edge in terms of momentum, future usefulness (games) and trained designers. It has heavyweight marketing and resources on its side and the chip vendors are supplying FLASH but have not been clear yet on SVG. SVG is more lightweight and seems to run a little faster.

The future has a way of eluding prediction, but the logic suggests SVG and FLASH may both have a place. SVG could be used with low end solutions, useful for the user interface but little else. FLASH meanwhile could be used at the higher end, faster platforms with higher performane 3D. The content available on the internet for FLASH would then be available on the higher end platforms. The picture probably will not clear up until we reach FLASH 10 for set tops...2011?

3D TV is not 3D Set Top Box

It was hard to find a killer theme at IBC this year but if there was one it was "3D". The hype surrounding 3D movies and television was there even if, in most cases, the products weren't. In many cases companies hi-jacked the hype and announced 3D Television - only to produce a psuedo3D GUI. Over at ITVT there is rather an amusing article on this...

However, though we didn't join the hype pool, Alticast did show something interesting. Alticast presented a 3D Video on Demand user interface running at high frame rates and full HD resolution. It was powered by a Broadcom chipset (7400) but the important point is that it was a Java 3D application, to be precise a GEM application using JSR 239.

JSR 239, also known as JOGL by some, is simply Java bindings for OpenGL-ES. This means that the C level calls of the OGL-ES drivers are duplicated at Java level. This standard sits alongside GEM and allows for GEM/MHP/tru2way/BluRay/ACAP applications to use any 3D graphics chips.

"Harry Potter" and Dolphin Remote Control for TVs

I'm growing more and more convinced that novel input devices take a side by side place with
advanced graphics in the digital TV world. 3D is not good unless you can navigate it. A run-jump game needs well, running and jumping or two key presses simultaneously. Shooting games work
much better with a pointer device. Simply put, the traditional RCU is not enough for next generation user interfaces. To this end I'll include remote control devices to go alongside the graphics on this blog.


The first device of interest is the Dolphin: a point and click device. It is based on the hardware development kit from Hillcrest Labs (see this blog entry) and gives a very positive mid air feel (unlike some devices in this category). The Dolphin can be used as a air mouse or can have gesture recognition. There is a longer article here. The device will apparently ship with Kodak picture viewer in the near future and shipping in huge numbers is likely to make the device costs come down.



A second and incredibly fun device is the Kymera Magic Wand from the Magic Wand Company. It comes in a real dragon skin box (I am told) and allows the young at heart to control an IR device in the home using a flick and swish. Infact the device can recgnise 13 different inputs (tap, tap side, rotate right, flick, rotate left, quick flick left or right, pull back push forward and so on). The device is programmable with the input from your cumbersome remote control and can send any IR signal for any gesture, allowing such feats as rewinding, power on from standby and volume control all with Hermione Granger grace.

It works and can even control lights in the house (infinite fun) but does cost a whopping 50 uk pounds from the Magic Wand Company. I know I'm buying one for my little Hermione.