merge_edge - Fixed, Sort of.

A while ago I wrote that you can't use CGAL's merge_edge if the two half-edges run in opposite X directions.  It turns out this isn't entirely true; as of CGAL 3.4 (yes, it's been a while since we went to latest) you can merge if you're very careful.

The issue is that CGAL caches the direction of a half-edge and doesn't invalidate the cache when you merge the edge.  Since it is replacing the curve of one of the two edges (the other is deleted) the cache could get out of sync with the curve, which causes chaos.

The work-around requires that you know which of two edges is going to be saved.  If you pass two halfedges h1 and h2 such that h1's target is h2's source (and that point is the vertex to be removed) then h1 and its twin are kept (and represent the merged edge) and h2 (and its twin) are deleted.

If h1 has the same direction as the new curve, you can simply merge h1,h2.  But if they run in opposite directions this means that h1 and h2 must not have the same direction (because two same-direction curves add up to the same direction curve).  If h1 does not match the curve then h2 does . If h2 matches the curve then h2's twin matches the curve's opposite.  Therefore the wokr-around when the curve and h1 don't match is to merge h2's twin, h1's twin with the curve reversed.

The Joys of Bezier Curves [NOT]

Someone please remind me why bezier curves are such a common parametric curve choice in the computer graphics world?  Some of their charming properties...

• No analytic solution for the curve's length.  The integral will make you cry.
• No analytic solution for the intersection of two curves.  Well, this guy found one, but he's not going to tell you what it is.
• No solution to find the closest point of encounter between two disjoint curves.
• No analytic solution to find the parametric value to split the bezier at a particular known length interval (e.g. into two halves of equal length).

You can subdivide a bezier curve into X or Y monotone regions analytically - to do this you intersect the X or Y parametric derivative with 0 and solve for t using the quadratic equation.

You can also intersect a bezier curve with a horizontal or vertical line - to do this you fill in the line coordinate and use the cubic equation (which does have a long but scary analytical solution) to find the roots.  (See here for code.)

Well, at least they're not riddled with patents.  Oh wait...

installer

A few tricks to get out of jail with OS X installs and updates...

If you have a package that just won't install due to bad voodoo (this can happen if you install a lot of seeds and the stars misalign) you can use this to force the install with this:
sudo CM_BUILD=CM_BUILD COMMAND_LINE_INSTALL=1 installer -verbose -pkg MacOSXUpd10.6.5.pkg -target /
If you need to install from an OS CD you can find the package to use for this trick in
/Volumes/volname/System/Installatoin/Packages/OSInstall.mpkg
One use for this is to force an install onto a partition that the OS doesn't understand.  I had my main drive triple-booted to OS X 10.5.8, Windows Vista (don't get me started) and Ubuntu 8.whatever.  Remaking this delicate balance without three OS reinstalls is virtually impossible, but the OS X Snow Leopard installer didn't want to install because it didn't understand the partition map.

The fix on the net is to resize the OS X partition, which causes Disk Utility to fondle the partition map in some useful way, but there's no way I want to risk my other OS installs.  Installing the OS from the command line with a forced install lets me simply dump the OS onto the drive, and then rEFIt just works because, well, it's rEFIt.

Why is Wordpress Slow?

I love WordPress, so it breaks my heart when our nice shiny WordPress pages take 9 seconds to load.  Here are the results of some investigations.  I don't do WP professionally, but WP is really easy to tinker with, so I'll blog this to avoid forgetting it.

The X-Plane blog uses WP Super Cache and a pile of social networking plugins.  Here's what I found for speed.

When we miss the cache, page load is really slow.  You can tell whether you missed the cache and why it's slow by looking at the last few lines of the page; WP super cache will list the time the cached page was last built, the render time in seconds, and it'll tell you if it's gzipping.  We see dynamic content times from 2 to 9 seconds!

Disabling Tweet This brought the time down to less than a second.  I don't know what Tweet This is doing (probably blocking on IO with Twitter on the server side while the page renders) but our first action will be to explore whether another plugin is faster.

So the number one issue is that when we miss the cache, run time costs are killing us.

When we hit the cache, Safari's timeline view of resources tells us what is causing the page to be slow to load.  We can see a few things:

• One plugin is putting its java script link at the end of the page, so we lose parallelism in loading.
• Some plugins are going to external sites with much higher latency than our server.
• We're "scattering" a bit to get our JS - consolidation might be a good idea, but in practice we don't have enough JS to care, plus the browser will cache.

We have some slow-loading stragglers from social media live content, but they don't block page load, so I guess we can live with that for now.

Finally the third and weirdest finding: if you have local browser cookies, WP Super Cache dutifully caches the customized version of the page you see with the forms filled out.  This means that you get your own private cache site.

This is a bit terrifying first because we could have a really huge build-up of files in the cache. But it's also bad news for cache hits.  When the site changes (e.g. a comment is posted) the first user to view the page eats the cache miss.  But if you have cookies, you always miss the cache since you have your own private cache.

In our case this is really bad: it means that users who have commented before (and thus have comment-name cookie in place) will always miss the cache once for every new article they see plus every comment posted.  Which is to say, the site will virtually always be "slow" (which in our case is "really slow" due to slow plugins).

I discovered this by putting WP Super Cache in debug mode, setting my IP as the debug URL and setting the debug level to 5.  Then when I first loaded a page in FireFox, I saw a whole pile of cache output due to cookies - when I viewed the cache meta data on the server, my own commenting name and email were clearly visible.

Fixing Wordpress Auto-Update Issues

There are a ton of posts from people having trouble auto-updating WordPress. 

This is the post that has the solution to the underlying problem.  I will try to explain why it works, since I totally misunderstood this the first time and without understanding it, it's hard to fix.

When WordPress auto-updates your blog, it doesn't do so as the "apache" user that usually runs httpd.  Instead it uses your ftp login to place files into the local file system as "you".

This is very clever because it means that you don't have to give apache cart blanche over your site, protecting you from web daemons run amock (or whatever it is that web developers worry about).

So the first key point is that you need to allow httpd to make FTP calls out to servers.  That's where
/usr/sbin/setsebool -P httpd_can_network_connect=1
comes in.  This gives httpd permission to make outgoing network connections so that it can call up your server via FTP as you. 

Without this you get the "Failed to connect to FTP server XXX" error (because httpd isn't allowed to make the outgoing connection - what's tricky here is that it is the client side of FTP that's failing, not your FTP server).

The second key point is that if you have multiple users administrating WP, things aren't going to go well.  The ownership of plugins will be 644 with the only person who has write permissions being you.  If another site admin tries to update, you get an error saying that WP couldn't remove the old version of the plugin.

I don't have a great solution for this yet.  I'll update this post when we fix the problem.

Guessing the Fine Print

One of the great things about OpenGL is that it can draw things really fast.

One of the great things about OpenGL is that it's really flexible.

But is it fast and flexible? No. There are "fast paths"; ask the GL to do something adequately byzantine and it's going to get the job done by a correct but not particularly optimized driver path.

I have had one or two occasions to peer over the shoulder of driver writers and see what a production driver looks like. Here's a taste. (Note: this is made up for illustration...no NDAs were harmed in the creation of this example.)

/* Figure out if we can push vertices through the fast path. */

#if X2913_GPU
#if USE_FAST_PATHS
if (
vbo->internal.struct_align % STRUCT_ALIGN_MOD == 0 &&
(vbo->source_mode == SOURCE_AGP || !vbo->resident) &&
#if FIX_STALL_BUG
vbo->current_day != AGP_YES_IT_IS_TUESDAY &&
#endif
vbo->internal.size > MIN_SIZE_FOR_FAST_PATH &&
vbo->internal.size < MAX_SIZE_FOR_FAST_PATH &&
IS_SIZE_WE_LIKE(vbo->internal.size) &&
#endif
FREE_SPACE(CMD_PACKET_BUF(OUR_CONTEXT)) > CMD_PACKET_ACCEL_SIZE)
{
/* do accelerated case *
} else
/* another 50,000 conditions have to be met. */
#endif
#if NEXT_GPU_THAT_IS_TOTALLY_DIFFERENT
...

What we have here might qualify as a leaky abstraction (at least with respect to performance): the fast path isn't obvious from the OpenGL API, but it matters.

Well, every now and then, you get to see yourself fall off the fast path. Ouch!

This is is a screenshot of an instruments 2.x trace (with the time profiler - 1.x won't give you this kind of info) of X-Plane with a fast path failure. In this case, we do a glCopyTexSubImage2D and...bad things happen! It's taking 67% of our frame time! In this case, we can sort of guess what the driver might be doing.

• 57% of the time goes into a gldFinish - I speculate that that's Apple asking nVidia to finish filling pixels on a surface. This of course goes through into Kernel space and spends a lot of time doing things that have "wait" in them.
• Another 8.2% is in glgProcessPixelsWithProcessor - that sounds a lot like Apple using the host to do some kind of pixel op.

Put it together and we realize: whatever we asked for, the driver can't do it in hw, so instead the OpenGL stack is stalling until the GPU completes, reading the data back to the host, and processing it.

Driver monitor confirms this - with non-zero "time spent waiting in user code" (meaning a call that might not block is blocking) and a non-zero texture page off bytes (meaning something in VRAM had to be copied back to the host). This is not what we want out of glCopyTexImage2D. Generally we never want to copy anything off of the GPU and we never want to wait in host.

What did it turn out to be? Well, the first surprise was that we were using glCopyTexImage2D at all (and not using an FBO). It turns out that we were reading back from an RGBA16F surface into an RGBA8 texture in a misguided attempt to cope with mismatching gamma. Of course, the driver could in theory build a custom shader to make that transformation, but it's very reasonable to expect a punt. Getting the two surfaces to the same format and using an FBO fixed the problem.

EXT vs ARB - The Fine Print

I thought I had found a driver bug: my ATI card on Linux rejecting a G-Buffer with a mix of RGBA8 and RG16F surfaces. I know the rules: DX10-class cards need the same bit plane width for all MRT surfaces.

I had good reason to think driver bug: the nappy old drivers I got from Ubuntu 10.04 showed absolutely no shadows at all, weird flicker, incorrect shadow map generation - and cleaning them out and grabbing the 11-5 Catalyst drivers fixed it.

Well, when the drivers don't work, there's always another explanation: an idiot app developer who doesn't know what his own app does. In that guy's defense, maybe the app is large and complex and has distinct modules that sometimes interact in surprising ways.

In my case, the ATI drivers follow the rules: the "EXT" variant of the framebuffer extension: an incomplete format error is returned if the color attachments aren't all of the same internal type. This was relaxed in the "ARB" variant, which gives you more MRT flexibility.

What amazes me is that the driver cares! The driver actually tracks which entry point I use and changes the rules for the FBO based on how I got in. Lord knows what would happen if I mixed and matched entry points. I feel bad for the poor driver writers for having to add the complexity to their code to manage this correctness.