Generating a Dynamic Grid Based of 4 Points

Given four points in space:
Vec3f vTopLeft, vTopRight, vBottomLeft, vBottomRight;
and a value for the cell density
unsigned int uiDensity;

We’re trying to generate a set of verticies in 3D space. These points are not limited in any way by being on the same plane.

The reason for this algorithm was originally quite simple and this solution was far from being necessary but it peaked my interest so I stuck with it.

The simple solution:

1. Define all 4 edges as new vectors
2. For every Edge we need to calculate the slope per axis
   1. vEdge[0] = vTopRight – vTopLeft;
      • slope.axis_x = vEdge[0].y / vEdge[0].x; // standard rise over run (in unit length)
      • slope.axis_x *= (vEdge[0].magnitude() / uiDensity); // scale to fit a square grid
   2. repeat for each edge

* the result is assumed to have equal number of points on each edge

3. Using opposite sides of the edges connect the dots, and generate additional edges that can be added to our list of existing 4. Don’t forget to do the same for the adjacent side
4. Using two nested for loops perform a line-segment on line-segment intersection tests to find the remaining points on the grid.

This algorithm is not very fast, but it should get the job done. I’m interested in other approaches since this was an on the fly solution at 1:00am.