VizWorld.com

At the upcoming ACM Symposium on Discrete Algorithms conference, a group of MIT researchers is presenting a new Fourier Transform algorithm that can improve on the now-standard “Fast Fourier Transform” (FFT) algorithm by a full order of magnitude.

In the SODA paper, they do this by repeatedly cutting the slice of spectrum into smaller pieces and keeping only those in which most of the signal power is concentrated. But in an as-yet-unpublished paper, they describe a much more efficient technique, which borrows a signal-processing strategy from 4G cellular networks. Frequencies are generally represented as up-and-down squiggles, but they can also be though of as oscillations; by sampling the same slice of bandwidth at different times, the researchers can determine where the dominant frequency is in its oscillatory cycle.

Their work is based on some previously found optimizations, but expands them to a significantly larger opportunity base.  The FFT is the foundation of many digital signal algorithms like MP3 and image compression codecs.  This new optimization could bring them to a whole new class of devices like mobiles and tablets, all while decreasing battery consumption.

via Faster-than-fast Fourier transform.

Science acm, algorithm, fft

CodingHorror isn’t typically a website to visit for visualization advice, but a new post over there details the many types of anti-aliasing algorithms, complete with lots of detail and examples and the original paper for the FXAA algorithm.

Pretty much all “modern” anti-aliasing is some variant of the MSAA hack, and even that costs a quarter of your framerate. That’s prohibitively expensive, unless you have so much performance you don’t even care, which will rarely be true for any recent game. While the crawling lines of aliasing do bother me, I don’t feel anti-aliasing alone is worth giving up a quarter of my framerate and/or turning down other details to pay for it.

But that was before I learned that there are some emerging alternatives to MSAA. And then, much to my surprise, these alternatives started showing up as actual graphics options in this season’s PC games — Battlefield 3, Skyrim, Batman: Arkham City, and so on. What is this FXAA thing, and how does it work?

via Coding Horror: Fast Approximate Anti-Aliasing (FXAA).

Graphics, Science algorithm, antialiasing

At SIGGRAPH Asia, researchers from Carnegie Mellon’s CS department are demonstrating an interesting new algorithm capable of matching not only similar images, but matching paintings and sketches against databases of images looking for matches.

The goal of this work is to find visually similar images even if they appear quite different at the raw pixel level. This task is particularly important for matching images across visual domains, such as photos taken over different seasons or lighting conditions, paintings, hand-drawn sketches, etc. We propose a surprisingly simple method that estimates the relative importance of different features in a query image based on the notion of “data-driven uniqueness”. We employ standard tools from discriminative object detection in a novel way, yielding a generic approach that does not depend on a particular image representation or a specific visual domain.

Impressive stuff, check out their demo video below.

via Data-driven Visual Similarity for Cross-domain Image Matching.

Science algorithm, siggraph

NVidia’s Cyril Crassin has a great post on their Developer Blog talking about his in-depth research into realistic lighting in computer rendering.  Discussing realtime vs offline, along with many algorithms and physics effects, it’s a great-read.

The key to our approach lies in a new algorithm and data structure that allow much faster computation. Instead of working on triangles (the traditional way of rendering graphics), we’re using voxels. Each voxel is one value in a 3D grid. The voxels are stored in an octree structure (a tree structure in which each node has eight children), with voxels as the nodes on the tree. Octree structures effectively compact the information stored in large amounts of graphics data. Octree structures use less memory, making them faster and more efficient at rendering tasks such as ray tracing.

via An Inside Look At New Research On CG Global Illumination « NVIDIA.

Science algorithm, nvidia

A new paper from the folks at Crytek and the Universidad de Zaragoza showcases a new antialiasing technique they call SMAA, or Subpixel Morphological Antialiasing.  The results are promising, as shown above.

We present a new image-based, post-processing antialiasing technique, that offers practical solutions to all the common problems of existing filter-based antialiasing algorithms. It yields better pattern detection to handle sharp geometric features and diagonal shapes. Our edge detection scheme exploits local contrast features, along with accelerated and more precise distance searches, which allows to better recognize the patterns to antialias. Our method is capable of reconstructing subpixel features, comparable to 4x multisampling, and is fully customizable, so that every feature can be turned on or off, adjusting to particular needs. We propose four different presets, from the basic level to adding spatial multisampling and temporal supersampling. Even this full-fledged version achieves performances that are on-par with the fastest approaches available, while yielding superior quality.

You can download a high-resolution video at the site below showcasing the effects of their new algorithm.  It’s impressive work, showing some beautiful results in their examples.

via SMAA: Enhanced Subpixel Morphological Antialiasing.

Graphics algorithm, antialiasing, crytek, paper

An amazing paper at SIGGRAPH2011 Asia from Kevin Karsch, Varsha Hedau, David Forsyth, Derek Hoiem shows some amazing algorithms they’ve developed for inserted rendered & artificial objects into photographs of real-scenes, all with a minimum of user input.

With a single image and a small amount of annotation, our method creates a physical model of the scene that is suitable for realistically rendering synthetic objects with diffuse, specular, and even glowing materials while accounting for lighting interactions between the objects and the scene. We demonstrate in a user study that synthetic images produced by our method are confusable with real scenes, even for people who believe they are good at telling the difference. Further, our study shows that our method is competitive with other insertion methods while requiring less scene information. We also collected new illumination and reflectance datasets; renderings produced by our system compare well to ground truth. Our system has applications in the movie and gaming industry, as well as home decorating and user content creation, among others.

There are some amazing applications of this technology, only the first of which is detailed in their abstract.  A little more automation and a nice simple web-driven/cloud-backed system and this could be the cornerstone of many technologies, not the least of which would be interior decorating.

Be sure to watch the video below.

Rendering Synthetic Objects into Legacy Photographs from Kevin Karsch on Vimeo.

via KevinKarsch.com

Science algorithm, siggraph

It was about a year ago when we first brought you the news of “Euclideon Geometry’s Unlimited Detail Real-time Rendering engine all based on Voxel-rendering.  Haven’t heard much from then but now they’re back with another video showcasing their engine and some information.

Hi everyone. We’ve been working very hard and we hope you like what we’ve made. This is just our 1 year report, after which we will probably go quiet again while we finish our work. This demo only shows what was ready at the time, we have a lot of really good stuff here but we are keeping it secret for now. (Yes grumpy forum people, we do have animation, but you’ll just have to be patient.)

I wouldn’t have paid much attention to it, until I saw Notch (Creator of MineCraft) discussing it.  He saw the same thing I originally noticed:

In the video, you can make up loads of repeated structured, all roughly the same size. Sparse voxel octrees work great for this, as you don’t need to have unique data in each leaf node, but can reference the same data repeatedly (at fixed intervals) with great speed and memory efficiency. This explains how they can have that much data, but it also shows one of the biggest weaknesses of their engine.

The technology is interesting yes, but I still think there is a lot of smoke-and-mirrors in their presentation.  They’re heavily constrained by memory limits so the bulk of their demonstrations rely on heavily tiled space making it nothing but referencing to a single memory block.  Trying to do this for anything unique is going to hit the memory wall really quick, as mentioned in this other post by Notch:

* One byte per voxel is way lower than the raw data you’d need. In reality, you’d probably want to track at least 24 bits of color and eight bits of normal vector data per voxel. That’s four times as much data. It’s quite possible you’d want to track even more data.
* If the data compresses down to 1%, it would still be 1 700 three-terrabyte hard drives of data at one byte of raw data per voxel.

All that said, watch the video and decide for yourself.  Fact, or Fiction?

‪Unlimited Detail Real-Time Rendering Technology Preview 2011 [HD]‬‏ – YouTube.

Science algorithm, euclideon, voxel

Click for Fullsize

InsideHPC dug up a nice paper from the ACM PLDI conference that discusses a prototype CPU-GPU Communication optimization tool called ‘CGCM’.  From their conclusions:

CGCM has two parts, a run-time library and an optimizing compiler.  The run-time library’s semantics allow the compiler to manage and optimize CPU-GPU communication without programmer annotations or heroic static analysis. The compiler breaks cyclic communication patterns by transferring data to the GPU early in the program and retrieving it only when necessary. CGCM outperforms inspector-executor systems on 24 programs and enables a whole program geomean speedup of 5.36x over best sequential CPU-only execution.

Impressive results to say the least.  Their examples seem based on CUDA code, not really OpenCL, although they do relate it to tools like OpenMP approaches and CUDA-lite.  It seems it becomes the programmer’s responsibility to mark data that’s to be shared between the GPU and CPU, and then some memory magic happens to move data between the two systems transparently.

It’s available as a PDF.

New Paper: Automatic CPU-GPU Communication Management and Optimization | insideHPC.com.

Science algorithm, cuda, gpgpu

Click for Fullsize

I just found this interesting example (with Source Code) of a new anti-aliasing technique called “GBAA”, or Geometry Buffer Anti Aliasing.  It uses a separate buffer to store geometry information as two-channel edge distance data , then uses a pixel buffer to select which pixel to show at rendertime.

The advantage of GBAA over GPAA is that it gets rid of the second geometry pass. It also does not require any line drawing, something that consumer level GPUs generally suck at. Additionally, having geometry information in a buffer allows us to anti-alias other edges than just geometric ones, most notably alpha-tested edges. The shader just needs to output the distance to the alpha-edge, something that’s easily approximated using gradient instructions. This is also demonstrated in the demo. On the down side it requires additional memory for the geometry buffer, but does not balloon up in the same way as MSAA does.

I’ve got to admit, the results are impressive.  You can get the Windows Executable and source code at the site.  DirectX10 required (Sorry XP’ers).

via Humus – 3D.

Science algorithm, directx

Gregor Aisch gave a recent sneak-peek of some OpenSpending visualization work that has resulted in a new visualization method he calls “radial bubble trees”.  Built entirely in web-friendly technologies like HTML5 and SVG, it’s a highly-interactive method of diving into the data.

We recently re-implemented the bubble visualisation from WDMMG to make it more re-usable for almost every dataset. Our main aim was to use it in the OpenSpending explorer which lets users explore and analyse government spending in a fun way. We now call the visualisation radial bubble tree, or just bubble tree, because that’s what it actually does: displays tree datasets in a radial layout with bubbles representing the individual nodes. For our purposes, each node represents a budget item.

via New Visualisations for OpenSpending | Open Knowledge Foundation Blog.

Science algorithm, financial, research