Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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...

share|improve this question
3  
Are you asking about tessellation programmatically by yourself, or about tessellation made by GPU automatically? That is a big difference.. –  Krom Stern Jun 10 '13 at 13:28

2 Answers 2

up vote 5 down vote accepted

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:

Naive subdivide

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.

share|improve this answer

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

enter image description here

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)".

Your first quad will be made of (winding clockwise here):

  • Left side: A to A+(1/6 1V)
  • Top side: A+(1/6 1V) to A+(1/6 2V)+(1/4 2H)
  • Right side: A+(1/6 2V)+(1/4 2H) to A+(1/4 1H)
  • Bottom side: (A+1/4 1H) to A

Using arrays and a for loop will make this process very automatic.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.