Mapping a Texture to a 2d Quadrilateral

I want to map a 2d picture onto an arbitrary 2d quadrilateral, for the purpose of particle system. To do that, I split the picture into two triangles, and then linearly interpolated u,v along the triangle edges, using the following code:

struct tlerp {
double x,i;
double u,v;
double ui,vi;
} tlerp;

void tlerp_init(tlerp *l
, double first_step, double steps
, double sx, double ex
, double su, double eu
, double sv, double ev) {
l->i  = (ex - sx) / steps;
l->ui = (eu - su) / steps;
l->vi = (ev - sv) / steps;
l->x = sx + first_step*l->i;
l->u = su + first_step*l->ui;
l->v = sv + first_step*l->vi;
}

l->x += l->i;
l->u += l->ui;
l->v += l->vi;
}


But the result is garbled. My guess is that linear interpolation can't be used here, because the space inside quadrilateral is obviously non-linear (on the attached picture it gets more compressed the closer it gets to the top). Is there some way to make it linear again?

As always, I'm not using an OpenGL/DirectX, so can't use any built-in solution.

• You can solve this with projective texture mapping, as described in this previous Q&A. There it's described with a shader, but you can implement the same math in your own code. – DMGregory Aug 22 '19 at 23:40
• I do four points to a perspective projection on My answer to Detect transform from detection of QR code?. – Theraot Aug 23 '19 at 3:18
• I know it can be fixed in 3d by diving by Z (i.e. projective mapping), but I don't have a 3d space, the polygons are purely 2d. And from what I understand, even in 3d they will be garbled, unless that trapezoid is actually just a tilted in 3d rect. I know Photoshop and GIMP somehow do it correctly (they allow even more advanced mapping with curve points inside quad), guess I should cheat by looking at GIMP's code. – SmugLispWeenie Aug 23 '19 at 7:41

I've solved the problem by following DMGregory's suggestion to introduce this imaginary Z, which I calculated based on distances between quad vertices. Here is a basic C code, because many people seems struggle getting it right, it is like most common pitfall of 2d and 3d graphics:

//usual euclidean distance
float distance(int ax, int ay, int bx, int by) {
int x = ax-bx;
int y = ay-by;
return sqrtf((float)(x*x + y*y));
}

void gfx_quad(gfx_t *dst //destination texture, we are rendering into
,gfx_t *src //source texture
)
{
float z = 20.0;
float top = distance(v[0],v[1],v[2],v[3]); //top
float bot = distance(v[4],v[5],v[6],v[7]); //bottom
float lft = distance(v[0],v[1],v[4],v[5]); //left
float rgt = distance(v[2],v[3],v[6],v[7]); //right

// By default all vertices lie on the screen plane
float az = 1.0;
float bz = 1.0;
float cz = 1.0;
float dz = 1.0;

// Move Z from screen, if based on distance ratios.
if (top<bot) {
az *= top/bot;
bz *= top/bot;
} else {
cz *= bot/top;
dz *= bot/top;
}

if (lft<rgt) {
az *= lft/rgt;
cz *= lft/rgt;
} else {
bz *= rgt/lft;
dz *= rgt/lft;
}

// draw our quad as two textured triangles
gfx_textured(dst, src
, v[0],v[1],az, v[2],v[3],bz, v[4],v[5],cz
, 0.0,0.0,      1.0,0.0,      0.0,1.0);
gfx_textured(dst, src
, v[2],v[3],bz, v[4],v[5],cz, v[6],v[7],dz
, 1.0,0.0,      0.0,1.0,      1.0,1.0);
}