# How to subdivide a quad?

I'm working with OpenGL and I'm importing from a file coordinates for quads in the following format:

 0.0 1.0 0.0 //normal vector
20.0 -5.0  20.0 10.0 10.0 //x y z u v
20.0 -5.0 -20.0 10.0 0.0
-20.0 -5.0 -20.0 0.0 0.0
-20.0 -5.0  20.0 0.0 10.0


I want to tessellate the quad so I'm starting with this:

------------
|          |
|          |
|          |
------------


And I should get this:

-------------
|___|___|___|
|___|___|___|
|   |   |   |
-------------


Can you guys help me creating the subdivide function? I'm struggling with it...

• Are you asking about tessellation programmatically by yourself, or about tessellation made by GPU automatically? That is a big difference.. – Kromster Jun 10 '13 at 13:28

To subdivide your quad in n*n sub-quads, you create n*n sub-quads inside it. There are several ways of doing this, so there is not such thing as the subdivide function.

Things get messy if you want to handle the most general case, i.e. a quad that is not necessarily a perfect square. Your illustration does not really tell us what you want. There is a whole lot of different kinds of quads (and this is only for "proper" quads, lying on a plane).

So I'm giving you one solution for gentle quads that are not too weird (so, convex quads), but don't expect it to work in every case. You can create line segments that start and end at regular intervals on each of your original quad's edges, and use these as edges for your new quads. E.g. with n=3:

In pseudo-code:

function naiveSubdivide(quad, n)
assert that n > 0
for i from 0 to n-1
// the P1-P2 line segment
P1 = A + i * (D - A) / 3
P2 = B + i * (C - B) / 3
// its sibling to the "right", Q1-Q2
Q1 = A + (i + 1) * (D - A) / 3
Q2 = B + (i + 1) * (C - B) / 3
// create n sub quads along the line segments
for j from 0 to n-1
A' = P1 + j * (P2 - P1) / 3
B' = P1 + (j + 1) * (P2 - P1) / 3
C' = Q1 + (j + 1) * (Q2 - Q1) / 3
D' = Q1 + j * (Q2 - Q1) / 3
create a new quad with vertices A', B', C' and D'
end for
end for
end function


For the general case, it's probably possible to write an entire book about it, but my guess is that working with triangles instead of quads would already be a good start.

Create 2 variables, hdivs and vdivs. In this example, hdivs=7, vdivs=5.

Now what you have to do is, compute all the points on the perimeter of quad ABCD. That means there are 20 points (including the corners) to be precomputed and stored.

You then need the 7 horizontal and 5 vertical lines (including the end lines). These are the lines along which the subdivided quads will be drawn. They are shown in red in the diagram above.

So then you just have to spin quads out of these 12 vectors. I will refer to the bottom line (AD) as the "1st horizontal line (1H)", and the left line (AB) as the "1st vertical line (1V)".