15

I need to paint a square image, mapped or transformed to an unknown-at-compile-time four-sided polygon. How can I do this?

Longer explanation

The specific problem is rendering a map tile with a non-rectangular map projection. Suppose I have the following tile:

Square tile

and I know the four corner points need to be here:

Four distorted corners

Given that, I would like to get the following output:

Distorted, image-mapped polygon

The square tile may be:

  • Rotated; and/or
  • Be narrower at one end than at the other.

I think the second item means this requires a non-affine transformation.

Random extra notes

Four-sided? It is plausible that to be completely correct, the tile should be mapped to a polygon with more than four points, but for our purposes and at the scale it is drawn, a square -> other four-cornered-polygon transformation should be enough.

Why preferably GDI only? All rendering so far is done using GDI, and I want to keep the code (a) fast and (b) requiring as few extra libraries as possible. I am aware of some support for transformations in GDI and have been experimenting with them today, but even after experimenting with them I'm not sure if they're flexible enough for this purpose. If they are, I haven't managed to figure it out, and so I'd really appreciate some sample code.

GDI+ is also ok since we use it elsewhere, but I know it can be slow, and speed is important here.

One other alternative is anything Delphi- / C++Builder-specific; this program is written mostly in C++ using the VCL, and the graphics in question are currently painted to a TCanvas with a mix of TCanvas methods and raw WinAPI/GDI calls.

Overlaying images: One final caveat is that one colour in the tile may be for color-key transparency: that is, all the white (say) squares in the above tile should be transparent when drawn over whatever is underneath. Currently, tiles are drawn to square or axis-aligned rectangular targets using TransparentBlt.

I'm sorry for all the extra caveats that make this question more complicated than 'what algorithm should I use?' But I will happily accept answers with only algorithmic information too.

NGLN
  • 43,011
  • 8
  • 105
  • 200
David
  • 13,360
  • 7
  • 66
  • 130
  • 1
    @NGLN: That looks perfect. I had either forgotten or never knew about that function! I will experiment with it tomorrow (it's late at night here.) Meanwhile, would you mind adding it as an answer, please? – David Mar 07 '12 at 20:48
  • 1
    Oops, sorry: PlgBlt can only result in a parallelogram. – NGLN Mar 07 '12 at 20:59
  • If speed is important you should probably abandon GDI and start making use of OpenGL. Delphi comes with the `OpenGL` unit so you can get started quickly. (GDI is probably fast *enough*, but since you mention the importance of speed...) – Andreas Rejbrand Mar 07 '12 at 22:02
  • @AndreasRejbrand, yes... OpenGL would be faster, certainly for this. I'm adding to an existing view though and don't want to have to rewrite the whole thing, so I'd prefer to integrate with the existing code. But thanks for the idea! We are actually [considering using OpenGL elsewhere in the program](http://stackoverflow.com/questions/9572887/3d-library-recommendations-for-interactive-spatial-data-visualisation) soon... – David Mar 07 '12 at 22:43
  • @AndreasRejbrand, its just a filler word. Everyone want it a priori fast :-) – OnTheFly Mar 07 '12 at 22:48
  • 2
    @DavidM, I really don't understand what more you want... you have the full sources, the project name, and the desired output. take a look at the excellent demo of `Graphics32`: Isn't that a "concrete examples of how a specific library solves the problem"? – kobik Mar 12 '12 at 13:23
  • @kobik: a detailed answer is better. (The highest-voted answer atm is a vector library which isn't even applicable to transforming raster images...) For Graphics32 though, the demo is simple and works well, but in a larger app it isn't integrating well - odd exceptions, for example. There is also no documentation for most parts of it, including the main class, `TBitmap32`. So, I'm seeking a specific answer above a library recommendation, logic being that an answer I have to spend ages investigating just to get it to work in a non-trivial app could be improved. A bounty sponsors improvement. – David Mar 12 '12 at 14:02
  • @DavidM, The highest-voted answer is actually mine. after iamjoosy posted the Graphics32 answer I have tested it (It worked super), and even commented that it was the best solution for raster image transformation. anyway, if anyone can give a *better* solution, I'll be all for it :) – kobik Mar 12 '12 at 14:08
  • Yeah... GR32 worked really well in the demo, and terribly in practice integrated into a bigger app, and I have posted to their newsgroups to find out why. I really would like something that works in a non-demo app too, I guess. Is that a better way of explaining why I added the bounty? – David Mar 12 '12 at 14:30

3 Answers3

6

Take a look at 3D Lab Vector graphics. (Specially "Football field" in the demo).

Another cool resource is AggPas with full source included (download)

AggPas is Open Source and free of charge 2D vector graphics library. It is an Object Pascal native port of the Anti-Grain Geometry library - AGG, originally written by Maxim Shemanarev in C++. AggPas doesn't depend on any graphic API or technology. Basically, you can think of AggPas as of a rendering engine that produces pixel images in memory from some vectorial data.

Here is how the perspective demo looks like:

enter image description here

After transformation:

enter image description here

kobik
  • 21,001
  • 4
  • 61
  • 121
6

You might also want to have a look at Graphics32. The screen shot bewlow shows how the transfrom demo in GR32 looks like

iamjoosy
  • 3,299
  • 20
  • 30
  • 1
    This works well in the demo app, but runs into issues integrated into a bigger pre-existing app (I posted on the GR32 forums, no need to clutter this, but the main issue is some methods on the TBitmap32 class aren't found by the linker, though they're in the generated .hpp file and I can't spot anything wrong.) Have you used it with C++ Builder and do you know what must be done to get anything beyond the demo to work? – David Mar 12 '12 at 14:34
  • 1
    @David, sorry, I am a Delphi only guy. But have a look at my response on the GR32 forum – iamjoosy Mar 12 '12 at 19:46
  • 1
    @David :) Thanks. In one of your comments you mentioned the lack of documentation. This is not true, but somewhat hidden. Have a look [here](http://graphics32.org/documentation/Docs/_Body.htm) – iamjoosy Mar 14 '12 at 11:05
5

The general technique is described in George Wolberg's "Digital Image Warping". It looks like this abstract contains the relevant math, as does this paper. You need to create a perspective matrix that maps from one quad to another. The above links show how to create the matrix. Once you have the matrix, you can scan your output buffer, perform the transformation (or possibly the inverse - depending on which they give you), and that will give you points in the original image that you can copy from.

It might be easier to use OpenGL to draw a textured quad between the 4 points, but that doesn't use GDI like you wanted.

David X
  • 3,998
  • 3
  • 29
  • 32
user1118321
  • 25,567
  • 4
  • 55
  • 86
  • So you implement a scan line algorithm, much like rendering a 3D polygon, using the matrix to look up pixel values in the original image? – David Mar 07 '12 at 22:44
  • I awarded the bounty to the above Graphics32 answer - it's a useful and fast library. But this is a good answer too, I appreciate knowing the algorithms and I'd give you more than one up vote if I could. – David Mar 14 '12 at 10:17