My previous fix was a hack and manually set the background of glyphs to transparent. I have known for some time that dvi_cairo_alloc_colors needed changing for transparency to properly fix the issue. dvi_cairo_alloc_colors created all the colors between the foreground and background and is used for smoothly transitioning between the two for anti-aliasing. Before adding transparency, it needed to take the background color into account. With transparency we don't care what the background is, we can just place progressively more transparent ink to fade into the background. Below is the relevant change in background/dvi/cairo-device.c

Before


color.red = frac * ((double)color_fg.red - color_bg.red) + color_bg.red;
color.green = frac * ((double)color_fg.green - color_bg.green) + color_bg.green;
color.blue = frac * ((double)color_fg.blue - color_bg.blue) + color_bg.blue;
pixels[i] = (color.red << 16) + (color.green << 8) + color.blue + 0xff000000;

After


color.red = frac * color_fg.red;
color.green = frac * color_fg.green;
color.blue = frac * color_fg.blue;
alpha = frac * 0xFF;
pixels[i] = (alpha << 24) + (color.red << 16) + (color.green << 8) + color.blue;

This is a simple fix and removes the special case for glyphs where I was setting the first color to fully transparent, this will now always be the case.

I also found a couple issues with draw_shrink_rule from backend/dvi/mdvi-lib/dviread.c. First, it had its parameters in the wrong order on the call to get_color_table, which points to the dvi_cairo_alloc_colors that we just discussed. The foreground and background parameters were swapped, this caused the wrong color to be placed. This function also chooses the darkness of the color based on how much the rule (or box) is scaled. This doesn't make sense to me, it should place the foreground color not a partially transparent version based on the scale.

First pass at fixing


static void draw_shrink_rule (DviContext *dvi, int x, int y, Uint w, Uint h, int f)
{
	int hs, vs, npixels;
	Ulong fg, bg;
	Ulong *pixels;
	hs = dvi->params.hshrink;
	vs = dvi->params.vshrink;
	fg = dvi->curr_fg;
	bg = dvi->curr_bg;
	if (MDVI_ENABLED(dvi, MDVI_PARAM_ANTIALIASED)) {
		npixels = vs * hs + 1;
                /* bg, and fg were out of order, it should be fg, bg */
		pixels = get_color_table(&amp;dvi->device, npixels, fg, bg,
					 dvi->params.gamma, dvi->params.density);
		if (pixels) {
		    int color;
		    /*  Lines with width 1 should be perfectly visible
		     *  in shrink about 15. That is the reason of constant
		     */
		    color = (pow (vs / h * hs, 2) + pow (hs / w * vs, 2)) / 225;
		    /*if (color < npixels) {
		        fg = pixels[color];
                        } else {	*/
			fg = pixels[npixels - 1];
                        //}
		}
        }
	mdvi_push_color (dvi, fg, bg);
	dvi->device.draw_rule(dvi, x, y, w, h, f);
	mdvi_pop_color (dvi);
	return;
}

Second pass at fixing


static void draw_shrink_rule (DviContext *dvi, int x, int y, Uint w, Uint h, int f)
{
	Ulong fg, bg;
	fg = dvi->curr_fg;
	bg = dvi->curr_bg;
	mdvi_push_color (dvi, fg, bg);
	dvi->device.draw_rule(dvi, x, y, w, h, f);
	mdvi_pop_color (dvi);
	return;
}

DVI is working much better for me now in my patched evince!

Update: 11/08/2010
The patch (slightly modified) has been accepted by the evince team!