Partially redrawing an OpenGL scene in response to exposure events and state changes

Most OpenGL applications redraw the entire scene every time a refresh has to be performed. There are exceptions, however. For example, to maintain responsiveness and conserve CPU time, an UI toolkit should only redraw the gadgets which need redrawing, either as a result of exposure events or gadget state changes.

It seems that partial redraws together with double buffering are not well-documented or understood by OpenGL programmers. Since partial redraws are very important to the Factor UI, I'll document what I've learned so far in this blog entry.

Factor's UI always sets the viewport dimensions to the entire window, however a scissor rectable is set using glScissor() to clip rendering to the region being redrawn. Gadgets are always rendered to the back buffer. Once the exposed region has been redrawn, the problem is now to bring it into the front buffer.

The GLX spec does not state whether glXSwapBuffers() takes the scissor rectangle into account.

On some OpenGL implementations, for example the NVidia drivers on Windows, Mac OS X and Linux, the current scissor rectangle is taken into account, and so the Factor UI can just request that buffers be swapped, and this only copies the requested region to the front buffer.

On Windows machines with Intel 9xx graphics adapters, this does not work, and SwapBuffers() copies the entire back buffer to the front buffer. As I documented in yesterday's entry, there exists a special WGL API for copying a partial region of the back buffer to the front buffer. This appears to fix the problem.

On my Linux/PPC machine with an ATI Radeon 9200 card and the open source "radeon" driver built in to X.org, glXSwapBuffers() also ignores the back buffer. Now, the MESA OpenGL implementation used has an extension GLX_MESA_copy_sub_buffer() which adds a glXCopySubBufferMESA() function for copying part of the back buffer to the front buffer, however, this function is buggy! It works some of time, but other times makes the entire screen go black, or kills the X server altogether.

There is a general fallback routine for copying part of the back buffer, but this is sometimes slower than redrawing the entire scene, at least on the Linux/PPC box described above. You can use glCopyPixels() to copy pixels from the back buffer to the front buffer, after setting the destination with glRasterPos():

: gl-raster-pos ( loc -- )
    first2 [ >fixnum ] 2apply glRasterPos2i ;

: gl-copy-pixels ( loc dim buffer -- )
    >r fix-coordinates r> glCopyPixels ;

: swap-buffers-slow ( -- )
    GL_BACK glReadBuffer
    GL_FRONT glDrawBuffer
    GL_SCISSOR_TEST glDisable
    GL_ONE GL_ZERO glBlendFunc
    clip get rect-bounds { 0 1 } v* v+ gl-raster-pos
    clip get flip-rect GL_COLOR gl-copy-pixels
    GL_BACK glDrawBuffer
    glFlush ;

Note the fidgety calculations to convert Factor UI co-ordinates ((0,0) is top left corner) to OpenGL window co-ordinates ((0,0) is lower left corner).

I'm still unsure if SwapBuffers() respects the scissor region on other platforms and OpenGL implementations, and if not, what is the correct way to copy part of the back buffer to the front buffer in the fastest possible way.

One other solution I need to look into is finding a way to be notified when the back buffer becomes invalid. If we redraw only part of the back buffer, then call SwapBuffers() to flip the entire back buffer with the front buffer, then in many cases, the previous content in the back buffer is still valid. It becomes corrupt when the video card needs to reclaim 3D memory for other applications, though. If there was a notification when volatile image buffers become out of date, I could force a full redraw on the next refresh, even if only a few gadgets need to be redrawn.

C/C++

Every time you say "C/C++" and lump two very different languages together as one, you're telling the world that you don't know either language. Idiomatic C code is very different from idiomatic C++. Good C++ code has very little that is actually C. Even the problem domains they are used in are different. Usually "C/C++" comes up in Java apologist rants ("Java is unmaintainable you say? Well I spent 10 years chasing memory leaks in "C/C++", it was far worse!") however sometimes you see informed people saying "C/C++". Please, don't.

OpenGL redraw bug on Windows

A while ago, "glguy" reported an issue with Factor 0.89: the UI was not being redrawn properly on Windows. I borrowed a Windows laptop and reproduced the exact same issue, and it turns out both me and glguy have the same graphics adapter: an Intel Express GM915.

I found a workaround: if I disable double buffering and don't call SwapBuffers after redrawing the window, then the issue disappears, and furthermore, it appears as if double buffering is still performed!

This is really strange, and I don't think this workaround will work elsewhere, unless WGL always double buffers, and uses hardware page flipping if you explicitly ask for it, or something.

If anybody has UI redraw issues and they're not using this adapter, or not running Windows at all, let me know!

Update: I found the right fix. On Windows, the glSwapHintRectWIN function must be called before SwapBuffers when doing a partial redraw. Turns out this function is not necessary with most drivers, but Intel drivers are picky when it comes to this. Good to resolve this one, finally. The fix is in the darcs repository.

Units and reversable computation

Since we don't want space probes written in Factor to crash because of calculations on mismatching units, Doug Coleman wrote a units library:

10 feet 30 inches d+ 56 s d/

It can add, multiply and divide dimensioned quantities while converting on the fly and making sure all the units make sense (10 miles 30 teaspoons d+ is a runtime error).

There was one problem with this library though, and it was that converting a dimensioned quantity back to a scalar required some boilerplate; for example, we have the following code:

: inches ( n -- dimensioned ) 2.54 * cm ;
: inches> ( dimensioned -- n )
    dup 0 { m } { }  =dimensions?*
    dimensioned-value 100 * 2.54 / ;

The inches word converts a number of inches to centimeters; cm in turn converts it to meters, which is the canonical representation of distances, then creates a dimensioned quantity. However the inches> word is ugly, and it is all boilerplate since the defintion of inches has all the required information.

Let's take a look at cm:

: cm centi m ;

And its auxilliary words:

: centi 100 / ;
: m ( n -- dimensioned ) { m } { } <dimensioned> ;

As you can see, <dimensioned> is the canonical constructor.

Now, enter Daniel Ehrenberg's inverse library. While Dan originally intended to use it for pattern matching, this library is a perfect fit for auto-generating words for converting dimensioned quantities back to scalars.

Indeed, out of the box, it cannot invert <dimensioned>, because it calls natural-sort which is not an invertible operation. However, we can explicitly define an inverse for <dimensioned> (not an inverse in the mathematical sense, since the original function is not one-to-one; strictly speaking, this is a section, that is, a function which satisfies only one of the two conditions of an inverse).

And now, everything works; here, undo is Dan's inversion combinator:

  100 cm [ inches ] undo .
5000/127

So 100 cm constructs a dimensioned object, after converting the dimension to canonical form (meters in the case of distance):

  100 cm .
T{ dimensioned f 1 { m } { } }

And [ inches ] undo takes a dimensioned quantity, and works backwards in order to obtain a number, which when passed to inches, would give the original quantity:

  [ inches ] undo .
5000/127

Lets take a look at the code generated by [ inches ] undo:

  [ inches ] [undo] .    
[ >dimensioned< { } =/fail { m } =/fail 100 * 127/50 / ]

It takes the dimensioned quantity apart, makes sure it is a distance (and not a time, etc), then multiplies the quantity itself by a conversion factor.

So we can convert a scalar represented by unit to any other unit in this way; we can also do stuff like:

  10 miles 30 km d+ [ yards ] undo .
19205600/381

What is shorter, a quarter of a mile or 400 meters?

  1/4 miles 400 m d< .
f

We also support compound units, such as miles per second, miles per second squared, etc. How many teaspoons in a liter plus a tablespoon?

  1 L 1 tablespoons d+ [ teaspoons ] undo .
77937/379

For volume units, the canonical representation is meters cubed:

  15 teaspoons .
T{ dimensioned f 379/5120000 { m m m } { } }

Here is a unit with a denominator:

  20 knots .
T{ dimensioned f 463/45 { m } { s } }

The inverse library automatically guards against invalid conversions:

  30 km 10 s d/ [ teaspoons ] undo .
Unification failed

This is seriously cool stuff. The implementation of units is very simple and elegant, too; only half of the code has to be written, because we can use inverse!

The inverse library depends on two things; the simple mapping between syntax and semantics (the composition of two functions is their concatenation, therefore the inverse of a concatenation of two functions is a concatenation of their inverses!) and it also depends on quotations being sequences rather than opaque code blocks. Two qualities which are unique to Joy dialects such as Factor.

HTTP server on factorcode.org

The Factor HTTP server on factorcode.org has been running non-stop since May 7th; that's almost 4 months. This site doesn't get a whole lot of traffic, but it seems that the I/O code and garbage collector are in good shape these days.

Back from Austin

I'm back in Ottawa. Doug, Ed, and all of their friends are very cool and lots of fun to hang out with! Once again, my luggage has been delayed en route, and I'll only get it Tuesday at the earliest. I wonder if the baggage handling infrastructure runs on Java, implemented by the regulars from JavaLobby?

Factor 0.90 will be released before the end of the month. I only have two things left on my to do list! I need to test on all platforms, then I have to fix one last bug concerning UI redraw on certain Windows systems.

I think I will aim for shorter release cycles in the future; say, 2 or 3 weeks. I'll limit the amount of new functionality in each release, so that it doesn't take so long for things to settle down. In the long term, I might try to get rid of releases altogether, and instead have daily builds; a daily build will only be uploaded if all unit and integration tests pass, and if all contributed modules load, and maybe even if there are no major performance regressions in benchmarks. It would be cool to automate something like this.

When to use locals

Some people have wondered why I implemented the locals library, and if in fact I'm turning my back on stack-based programming and "selling out". In fact this is not the case.

First of all, Factor has already had named variables in the core for quite some time; these are found in the namespaces vocabulary, which implements very simple dynamically-scoped namespaces. There are many cases where dynamic scope is useful, and languages which lack it often end up with a lot of code which passes parameters down long function call chains, with only the leaf functions actually using the parameters. Examples of dynamic scope usage in Factor include the current stream, and various idioms for sequence and association construction. Here dynamic scope is the right thing to use, and it makes total sense, and it cleans up code when certain values are not passed around on the stack.

In a handful of places, we also used dynamic variables as temporaries in calculations. I think once the right abstraction is found, stack code is almost always simpler and cleaner than the equivalent applicative code using named temporaries. But sometimes you have a math formula which operates on 10 values at once, or something similar, and it simply makes more sense to name these intermediate values. In these cases, we used dynamic variables. There are a handful of examples of this so far, such as the MD5 algorithm, and a couple of routines in the calendar library.

However when one uses dynamic variables for temporaries, the dynamic scope semantics no longer help and in fact get in the way; anybody who has used a Lisp with all-dynamic scope can testify. So while most values which would be lexically-scoped in a Lisp program are passed on the stack in Factor, sometimes you still want to name temporaries, and named locals with lexical scope are useful here, because they allow you to create closures and safely pass them around without running into the "funarg problem" which had the Lispers stumped through the 60's.

I never opposed having named variables in Factor, because if I did, they wouldn't be there from day one. Until recently, I didn't feel the need for lexical scope much, though, and when asked about it, my standard reply would be that the stack is Factor's equivalent of lexical scope, and that if somebody coded it up, I'd be happy to add it as an extra library.

Eduardo eventually implemented somewhat inefficient lexical scope in his extra/rewrite-closures library, which still exists because unlike extra/locals, it has first-class environments. I decided to code extra/locals because I wanted to see if I could make locals as efficient as stack values, and the experiment was a success.

So to recap, Factor now has three main methods of passing values between words, and storing temporary values within words:

• The stack. Factor is and always will be a stack-based language; the whole point of the project is to explore stack-based programming. I encourage beginners to learn to think in terms of the stack before jumping into other abstractions, and for most code, the stack works really well. It is really interesting that in a stack language, function composition is expressed as concatenation, and compared to Lisp, Factor code has a lot less nesting and arbitrary introduction of temporaries. Especially now that Factor supports efficient partial function application, quotations can have internal state, and this brings much of the benefits of closures to the world of the stack.
• Dynamically scoped variables. These are useful for a set of issues totally orthogonal to temporaries: they're used to give words context-specific behavior, and when an algorithm spanning multiple words needs to operate on a common set of values.
• Lexically scoped variables. These are used to name temporary values inside calculations which otherwise would be hard to express with the stack. Hopefully this set will reduce over time, but for now, it includes any kind of hairy mathematical operation such as found in cryptography, numerical methods, and so on.

Having more abstractions to choose from when writing code is good, and I think a stack language can express the widest range of them in the most natural possible way.