Why don't you just draw the lines using single-surface quads. You can make really good soft edged lines using this aproach and it's fast. Just use small gradient texsturemap with the quads and stretch/resize one to make a line. This way you can't blame the line drawing when your algo is too slow :)