Euclidean Subdivision

Playing around with Proposition I two mornings ago, I constructed a curious diagram.  On nice paper it looks like this:

Euclidean SubD - Quad

The only thing given is finite segment AB.    There are two closed shapes: the square ABCD, and the shaded figure in the middle (mouse over).  Let's call the square the base geometry, and the curvy figure in the middle the subdivided geometry.  That's more or less what 3D programs call them.  The construction here is simple, but I'll list a few key details that might not be obvious:

 In Euclid's Proposition I , we draw two circles, and from these the square can be built.  For example,  AD is the radius of once circle, and tangent to the other.

   The sides of the subdivided figure are the points of equilateral triangles.

   To get the corners, I drew new circles around the four new points.

   The  point at the center and the segments connecting it are part of the new surface.  It thus has 9 points: 8 around the perimeter, and one at the center.

I have taken some liberties with Proposition  I.  For example, I have used the tangents of circles at points to construct the square.  I was doodling. 

The significance?

I think every 3D modeler recognizes this shape.   It is a smoothly subdivided surface.  Drop a Sub-D modifier onto your stack, and this is what happens to your model.  I have had subdivision on my mind for awhile, and I did not know where to start, so I started here.  I even made a plan for going through the Elements, and turning Propositions into algebra, vector equations, and algorithms.  But this is exactly what I wanted, and it only took the first Proposition!

I still need to make it an appealing and functional subdivision routine.  Several modifications should correct most of the problems:

1) As shown, none of the new points lie on the base geometry, which is too aggressive.  Next, I will split each edge at its midpoint, and leave these points on the base geometry.  Only the 'corners' will pull inside the original perimeter (or push out).  If the geometry is subdivided again, all points may lie off the original edges.

Splitting the edges at midpoints is also faster to compute.

2) The math does not need to be exact; it just has to look nice.  I used 30-60-90 triangles, so the distance to a new point is a term in √3.  I can choose friendlier numbers.  An even better solution is to build a template which gives the new topology like a stencil, tessellated across the whole mesh.

3) Triangles!  Arbitrary polygons can be divided into triangles. I need a subdivided triangle.  

Fig. 2: Euclidean Sub-D: Tri

4) Topologically, all triangles can be seen as the same, all four-sided shapes the same....and so on.  I am not yet considering polygons with more than four sides, so Figures 1 and 2 cover all cases.

5)  Order of construction:

Edges first, then vertices.

The midpoint of any edge can be found, independent of the surrounding topology.  So I will begin there.

   i) Add midpoints to each edge.  For example, in the new version of Fig 2,  m₁ will fall directly on the edge AB,  m₂ on  BC,  and  m₃  on AC.

  ii) When all edges of any polygon are split, add the center point.  This is easiest to see with Fig. 2.   If we complete the segments Am₂, Bm₃, Cm₁,  they intersect at a common point in the center.

  A segment joining a vertex to the midpoint of the opposite side is called a median.  In a triangle, the three medians always intersect at a common point inside the triangle.  This point of intersection is the geometric center (or centroid).  So I will use it.

   iii) This leaves A',  B' and C'.   They may be connected to other polygons, or they may be free edges.  The same general rule can be applied to both cases.  Say C joins four polygons.  When all four of these polygons have a geometric center,  balance C' between these centers.

      The rule is then, when all adjacent polygons to a vertex have centers, balance the new vertex between them.

   Balance:    The geometric center of a polygon is its balance point.  Then the obvious approach is to balance A', B'.... the same way.  This is (I believe) a tensor.  Say all the lines connected to C are flexible.  Where does C fall if the tension on these lines is balanced?  Or relaxed?  This question results in a system of linear equations which are most easily handled as vectors.

6) The third dimension: I plan to ignore it.  A surface is is two dimensional.  For example, you can attach an image to any surface.  However much it curves in space, you can always paste (map) a flat image to it.  Every polygon either lies in a plane, or there is a plane that is closest to it.  Viewed in this plane, a polygon will appear to subdivide as if it were perfectly flat.  The amount any vertex moves out of this plane will be completely determined by the geometry of the model.  The more rapidly the base geometry is changing perpendicular (normal) to the plane, the less the subdivided surface will be able to follow it.  Sharp angles smooth to a more gradual change.

7) The distance function is two-dimensional.  The math is fine, but how will it look?  3D models are surfaces, but they represent 3-D shapes objects.  A 2D distance function might be too tight. Consider some distances:

    From the origin (zero)  to 1 on the number line:

           1 - 0     =  1  

    From the origin (0, 0) to the point (1, 1), in the x-y plane:

           √(1² + 1²) =  √2.     (Pythagorean theorem)
     From the origin (0, 0, 0) to the point (1, 1, 1) in x-y-z space:

           √(1² + 1² + 1²) = √3.         (same)

 If AB in Fig. 1 has length of 2, then my unit subdivision length is √3.  I will keep this metric while developing the algorithm, and make the number under the root a variable.  I hope scaling the dimension of the subdivision length independently will make the algorithm both flexible and intuitive.  Scaling between "k=1.414" and "k= 1.732" on a linear slider may cover the same range of values as k = √2 , k = √3, but the relationship is unclear in the first case, and the scaling wrong.

I seek an adaptable subdivision method.  Once I have a working algorithm, I will revisit questions which I have glossed over.    #s 6 and 7  are such questions.  In general, "adaptable" implies greater sensitivity to rapid changes of direction in the base geometry (like corners).  Derivatives of higher order could be useful for a project involving assets designed from the ground up to be aggressively tessellated, and categorized by material type.

For example, how can a sub-D routine be tailored to hard surfaces?  And terrain? (...and types?)  Any spatial characteristics of the base mesh could be important factors.  One could also surely model using different subdivision templates throughout the mesh.  This would be labor-intensive for the artist, but it could also prove very efficient and intuitive, especially for hard surfaces, modeling for games.  Given by templates means a pool of scaled normal map files could potentially be used to speed normal map generation for complex surfaces, and to allow the low- and hi-poly meshes to be the same.  But that's just pretend for now;   this part of my project is not pressing.  It may be some time before I revisit subdivision and construct a basic algorithm.

Regardless, I think this provides sufficient generalization to tailor the algorithm to taste, and any problems which arise can be adjusted.  It's all made up of course, so maybe it'll be a disaster.  That's fine.  Now I have something to fix.

Make Your Own

I am happy to give the full construction of each diagram, and of my subdivision method when it is complete. It was more important to me to show how a subdivision routine can be constructed by anyone with a compass and straightedge.  The specific steps I have taken are personal preference.  I was playing a game with a compass.  Any way to break up a shape is a way to subdivide, and whatever people might want you to think, a bunch of special vocabulary is unnecessary.  It gets in the way.  If you follow that link, the authors will spend half a page describing a square with a diagonal drawn in it.  They will give it a special name.  Subdivision will appear mysterious, loaded with unforeseen complexities.*  It is not. 

Tell Me, or Ask A Question

If I have written about a problem, I have the time to go through every step.    Just ask.  I don't know what's missing from the explanation until someone tells me.  On the other hand, additional details make the broader picture harder to see.  There is a choice when writing about math: where to draw this line?

Ideally, the text should be both concise and complete.   This will take me quite some time to achieve, but that is my goal.  I tend to overcomplicate.  All suggestions about how ts can be more clearly presented are welcome.

I will add new diagrams in my next pass through subdivision.  This will provide additional clarity.

{* I had enough after a few pages.  I don't have the patience for this.}