Create a grid in perspective from 4 corners

Question

I'm trying to generate a grid of points from its 4 corners. As this corners can be freely placed, it will look as the grid has a perspective.

I've written the following code in Processing, where corners are in clockwise order (starting at top-left)

PVector[][] setGrid(PVector[] corners, int cols, int rows) {
    PVector[][] grid = new PVector[rows][cols];
    for(int y = 0; y < rows; y++) {
        float fY = (float)y / (rows - 1);
        PVector p1 = PVector.lerp(corners[0], corners[3], fY);
        PVector p2 = PVector.lerp(corners[1], corners[2], fY);
        for(int x = 0; x < cols; x++) {
            grid[y][x] = PVector.lerp(p1, p2, (float)x / (cols-1));
        }
    }
    return grid;
}

This generates a grid with interpolated points, but it doesn't correspond to a perspective grid. All in-line points are equidistant, while in perspective closest points should be more separated than farthest.

I would appreciate some orientation, if possible, in Java/Processing

EDIT

To clarify my answer. I define 4 random corner points, I want to get all the points that create a perspective deformed grid. Note that because of perspective dX1 != dX2 as well as dY1 != dY2 . The code I wrote does not this effect (I know this, but I don't know how to do what I require) as points are interpolated resulting dX1 = dX2 = ... = dXi and dY1 = dY2 = ... = dYi

I've read about perspective transform, but I don't need to transform an image, I just need to get the grid points coordinates.

Answer 1

In your example image the perspective effect is achieved by holding the number of lines invariant along edges of different length. That's what your implementation does, so I'm honestly not seeing the problem.

Here is a sketch calling your setGrid():

PVector[] corners;

void setup(){
  size(150,100);
  corners = new PVector[4];
  corners[0] = new PVector(35,20);
  corners[1] = new PVector(15,height-30);
  corners[2] = new PVector(width-10,height-10);
  corners[3] = new PVector(width-30,10);
  noLoop();
}
void draw(){
  background(255);
  PVector[][] results = setGrid(corners, 9, 9);
  for(PVector[] pvs : results){
    for(PVector pv : pvs){
      ellipse(pv.x,pv.y,5,5);
    }
  }
}

PVector[][] setGrid(PVector[] corners, int cols, int rows) {
    PVector[][] grid = new PVector[rows][cols];
    for(int y = 0; y < rows; y++) {
        float fY = (float)y / (rows - 1);
        PVector p1 = PVector.lerp(corners[0], corners[3], fY);
        PVector p2 = PVector.lerp(corners[1], corners[2], fY);
        for(int x = 0; x < cols; x++) {
            grid[y][x] = PVector.lerp(p1, p2, (float)x / (cols-1));
        }
    }
    return grid;
}

...and the result looks almost exactly like your target image. If you are seeing something different, perhaps you are creating grids with very similar edge lengths?

If you want to project perspective on a regular trapezoid -- like a sidewalk receding into the distance -- then consider this approach instead:

• https://math.stackexchange.com/questions/337056/a-controlled-trapezoid-transformation-with-perspective-projecton

Answer 2

I've solved it taking a geometric approach: identifying grid vanishing points from corners, and interpolating from the translated horizon line. I've created a class for this GridPerspective.

There are just 2 requirements:

1. Corners must be in clockwise order.

2. Grid sides cannot be parallel (vanishing point to infinite).

Processing code:

GridPerspective grid;

void setup() {
    size(600, 600, P2D);
    grid = new GridPerspective(10, 10);
}


void draw() {
    background(0);
    grid.draw();
}

void mouseClicked() {
    grid.addCorner(new PVector(mouseX, mouseY));
}

public class GridPerspective {

    int cols, rows;
    PVector[] corners = new PVector[4];
    int selC;
    PVector[][] points;

    public GridPerspective(int cols, int rows) {
        this.cols = cols;
        this.rows = rows;
    }

    public void addCorner(PVector corner) {
        if(selC < 4) {
            corners[selC++] = corner;
            if(selC == 4) update();
        }
    }

    public void update() {
        if(corners[0] == null || corners[1] == null || corners[2] == null || corners[3] == null) return;
        PVector[] vanishing = new PVector[] {
            linesIntersection(corners[0], corners[3], corners[1], corners[2]),
            linesIntersection(corners[0], corners[1], corners[3], corners[2])
        };
        PVector topHorizon = PVector.sub(vanishing[1], vanishing[0]);
        PVector bottomHorizon = PVector.add(corners[3], topHorizon);
        PVector[] bottomLimits = new PVector[] {
            linesIntersection(corners[3], bottomHorizon, vanishing[0], corners[1]),
            linesIntersection(corners[3], bottomHorizon, vanishing[1], corners[1])
    };
        points = new PVector[rows][cols];
        for(int r = 0; r < rows; r++) {
            PVector bpr = PVector.lerp(corners[3], bottomLimits[0], (float)r / (rows-1));
            for(int c = 0; c < cols; c++) {
                PVector bpc = PVector.lerp(corners[3], bottomLimits[1], (float)c / (cols-1));
            points[r][c] = linesIntersection(bpr, vanishing[0], bpc, vanishing[1]);
            }
        }
    }

    public void draw() {
        if(points != null) {    
            fill(255);
            for(int r = 0; r < rows; r++) {
                for(int c = 0; c < cols; c++) {
                    ellipse(points[r][c].x, points[r][c].y, 4, 4);
                }
            }   
        }
    }

    private PVector linesIntersection(PVector p1, PVector p2, PVector p3, PVector p4) {
        float d = (p2.x-p1.x) * (p4.y - p3.y) - (p2.y-p1.y) * (p4.x - p3.x);
        if(d == 0) return null;
        return new PVector(p1.x+(((p3.x - p1.x) * (p4.y - p3.y) - (p3.y - p1.y) * (p4.x - p3.x)) / d)*(p2.x-p1.x), p1.y+(((p3.x - p1.x) * (p4.y - p3.y) - (p3.y - p1.y) * (p4.x - p3.x)) / d)*(p2.y-p1.y));
    }

}