How can I draw an image inside a rectangle?

I am introducing myself in the manipulation of images for games, I have a window and inside there is a rectangle that deforms. I would like to fill the rectangle with an image, but I have no idea how to translate the coordinates of the image to the rectangle. I don't want a library function, I want to implement it myself.

enter image description here

the idea would be to have a function:

void fill_image_rectangle (img, b1, b2, b3, b4) {

// *

I use Java on Windows 7 CPU

  • 2
    \$\begingroup\$ What language or technology stack are you using? Are you looking for a GPU solution, or CPU? \$\endgroup\$ – DMGregory May 4 '20 at 16:08
  • \$\begingroup\$ hi molo32, welcome to gamedev! can you clarify what language/platform you're using? i dont know if we can answer this question without that information. \$\endgroup\$ – Gigazelle May 4 '20 at 18:14
  • \$\begingroup\$ below the example code it says so \$\endgroup\$ – molo32 May 4 '20 at 18:26
  • \$\begingroup\$ If CPU - google "non-affine transformation". \$\endgroup\$ – Engineer May 5 '20 at 7:54

You do it backwards.

You need a transformation that maps from the original image to the cuadrilateral. Well, actually, you need the inverse. In particular, you want a transformation matrix such that you multiply a position from the target canvas and it gives you a position in the original image.

To derive that matrix, you define that image_position = M * canvas_position, and knowing the coordinates of the corners, you solve the matrix equation.

I explain how to derive such transformation in another answer, in that want we want to fit a model to the image of a QR code, it is the same approach. You probably can work in 2D instead of 3D. Please refer to the demo code there.

Once you have that transformation, you can iterate over the pixels of the target canvas, for each one you query the pixel at the corresponding position of the image and pain it.

The iteration over the pixels is a bit tricky too… You will not iterate over the original image, instead you iterate over the target canvas (that is what I mean by doing it backwards). If you were to go over the original image and map each pixel to one pixel on the target you could end up leaving gaps in the target image (you might be interested in seeing some kind of interpolation there).

Thus, we iterate over the target canvas… You can, of course, go over each pixel, check if it is inside the target cuadrilateral and if it is proceed… however, that will have a lot of wasted effort.

Instead, think of iterating over one axis, and draw the shape segment by segment. That part is easy, you get the minimum and maximum coordinate on the main axis of the corners. Then for each segment You want to know where it starts and ends in the secondary axis.

One easy approach is to break the cuadrilateral at the main axis coordinate of each corner. That should give you a series of trapezoids (with two special cases: a rectangle, where the sides are parallel and a triangle where the sides meet at one end). Each trapezoid would be defined by a range in the main axis, and two line equation for the other sides… These line equations will be the secondary axis coordinate as a function of the main axis coordinate.

Alright, what main axis? It could be the vertical or the horizontal. Usually the images are stored such that the next and prior pixel in a row are contiguous in memory. Because of this, making the vertical the main axis will perform better. This means that the line equations for the sides of the trapezoids are going to be the horizontal as a function of the vertical, which is not how we usually see them. And I want to draw attention to that.

For clarity:

Target cuadrilateral divided in trapezoids

Thus, you will be iterating over the trapezoids (I remind you that the triangles are trapezoids where the sides meet at one end), for each trapezoid, you will iterate on its vertical range. For each row in the vertical range of the trapezoid, you compute the start and end column, and iterate over those pixels. For each pixel you find where it is in the image, and you query the pixel and draw.

Bonus: you might be interested in finding the neighbor pixels and interpolate them.

See also: Resizing Images - Computerphile and Bicubic Interpolation - Computerphile.

Yeah, this is going to have very bad performance in Java. If done on CPU, you want to manipulate the image memory directly (without the overhead of an API call to read and write each pixel) to have a decent performance. It is, of course, much better to solve the problem in GPU with a fragment shader, where each pixel gets resolved in parallel, with hardware optimized for that, and without taking CPU time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.