To subdivide geometry (without any kind of smoothing), you generate new vertices by linearly interpolating each edge. The simplest case is subdividing by a factor of two, i.e. each new vertex is just the midpoint (average) of two other vertices. To divide an edge into N equal parts, the new vertices are (i*v[sub]1[/sub] + (N-i)*v[sub]2[/sub])/N for 0<i<N (i.e. i between 1 and N-1 inclusive). When N=2, this is just (v[sub]1[/sub] + v[sub]2[/sub])/2.
For a triangle, you find the midpoint of each edge. Now you have 6 vertices which are connected like so to form 4 triangles.
o
|\
| \
| \
o---o
|\ |\
| \ | \
| \| \
o---o---o
To subdivide a quadrilateral (4 vertices and 4 edges) into smaller quadrilaterals, you find the midpoint of each edge, plus a centroid which is the average of the 4 initial vertices. This gives you 9 vertices (3x3) which you use to create the smaller quadrilaterals.
o---o---o
| | |
| | |
o---o---o
| | |
| | |
o---o---o
Or you could split it into two triangles then use the above scheme, or treat it as a polygon using the following scheme.
For a polygon with 4 or more sides, you’d typically start by finding the centroid (the average of all of the vertices) and tessellating the polygon into triangles:
o-----o
/ \ / \
/ \ / \
o-----o-----o
\ / \ /
\ / \ /
o-----o
Thereafter, you’d use the triangle scheme above.
When you’re dealing with meshes made from connected polygons (i.e. which share edges), you’d typically want the smaller polygons to also share edges. Probably the simplest way to achieve this is to use an associative array (dictionary, hash table, …) whose key is a pair of vertex indices and whose value is the index of the new vertex formed from subdividing the edge between the first two vertices. So before subdividing an edge, you check if it’s already been done, and if it has you use the existing vertex rather than creating a new one.