How to draw a Perspective-Correct Grid in 2D

Question

I have an application that defines a real world rectangle on top of an image/photograph, of course in 2D it may not be a rectangle because you are looking at it from an angle.

The problem is, say that the rectangle needs to have grid lines drawn on it, for example if it is 3x5 so I need to draw 2 lines from side 1 to side 3, and 4 lines from side 2 to side 4.

As of right now I am breaking up each line into equidistant parts, to get the start and end point of all the grid lines. However the more of an angle the rectangle is on, the more "incorrect" these lines become, as horizontal lines further from you should be closer together.

Does anyone know the name of the algorithm that I should be searching for?

Yes I know you can do this in 3D, however I am limited to 2D for this particular application.

Answer 1

The problem is that it's the transformation from 3D to 2D that's getting you.

Here's a tutorial on how it's done.

Answer 2

While my google-fu has failed to produce any rock solid mathematical solution, perhaps this drawing that I found could help a little.

http://studiochalkboard.evansville.edu/lp-diminish.html

I think it might actually be pretty difficult to come up with the correct math on your own, it's probably some sort of logarithmic or summation expression. Hopefully the drawing and terms at that link might provide something a little more searchable for you.

Answer 3

What you need to do is represent it in 3D (world) and then project it down to 2D (screen).

This will require you to use a 4D transformation matrix which does the projection on a 4D homogeneous down to a 3D homogeneous vector, which you can then convert down to a 2D screen space vector.

I couldn't find it in Google either, but a good computer graphics books will have the details.

Keywords are projection matrix, projection transformation, affine transformation, homogeneous vector, world space, screen space, perspective transformation, 3D transformation

And by the way, this usually takes a few lectures to explain all of that. So good luck.

Answer 4

Here's the solution: http://freespace.virgin.net/hugo.elias/graphics/x_persp.htm

The basic idea is you can find the perspective correct "center" of your rectangle by connecting the corners diagonally. The intersection of the two resulting lines is your perspective correct center. From there you subdivide your rectangle into four smaller rectangles, and you repeat the process. The number of times depends on how accurate you want it. You can subdivide to just below the size of a pixel for effectively perfect perspective.

Then in your subrectangles you just apply your standard uncorrected "textured" triangles, or rectangles or whatever.

You can perform this algorithm without going to the complex trouble of building a 'real' 3d world. it's also good for if you do have a real 3d world modeled, but your textriangles are not perspective corrected in hardware, or you need a performant way to get perspective correct planes without per pixel rendering trickery.

Answer 5

Using Breton's subdivision method (which is related to Mongo's extension method), will get you accurate arbitrary power-of-two divisions. To split into non-power-of-two divisions using those methods you will have to subdivide to sub-pixel spacing, which can be computationally expensive.

However, I believe you may be able to apply a variation of Haga's Theorem (which is used in origami to divide a side into Nths given a side divided into (N-1)ths) to the perspective-square subdivisions to produce arbitrary divisions from the closest power of 2 without having to continue subdividing.

Answer 6

In the special case when you look perpendicular to sides 1 and 3, you can divide those sides in equal parts. Then draw a diagonal, and draw parallels to side 1 through each intersection of the diagonal and the dividing lines drawn earlier.