Surface subdivision

Although surfaces refinement operations by mesh subdivision are intuitive and easy to describe locally, their formal and global specifications in a standard language are not trivial to implement. One may wonder how cellular complexes can be used as position space of topological collections and patches (an extension of standard transformation on cellular complexes) to program such structural modifications.

In this example, patches will be used to declaratively and locally describe a subdivision algorithm and keep a good expressiveness.

We focus here on one of the simplest algorithms of triangular meshes subdivision, the polyhedral one. It consists in dividing each triangle into four coplanar triangles.

The position of added vertices is computed along the process. Here, we insert new vertices in the middle of edges (i.e. its coordinates are the average edges ones). In other algorithms, the same topological modification is used, but positions of new and old vertices are different in respect with a specific mask. This difference is only geometrical without influence on the topological structure.

Description of the algorithm:

The previous figure shows that although the transformation is local, some effects appear on the sides of the triangle. Indeed, the neighbor triangles are topologically modified by the insertion of vertices. This effect makes the implementation be complicated. So we can't used a unique straightforward rewriting rule.

We avoid this problem by programming two different steps: in the first one, a vertex is inserted on each edge. In a second time, each hexagons (indeed, the first transformation make triangles become hexagons by inserting three new vertices) is divided by adding 3 new edges and 4 triangles.

We respectively associate the values `edge and `face to the edges and to the triangles. To make the difference between new and old vertices, an integer is associated to each vertex and corresponds to its generation number (like a birth date). A 3-dimensional embedding can also be associated:

record Point = { x:float , y:float , z:float , gen:int } ;;

Vertex insertion

This step consists in the selection of an edge in oder to insert a vertex on it.

The MGS code is the following:

patch insert_vertex[genNb] = {
  ~v1 < e:[dim=1] > ~v2 =>
    `v:[dim=0,cofaces=(`e1,`e2),{gen = genNb,
                                 x   = (v1.x + v2.x) / 2,
                                 y   = (v1.y + v2.y) / 2,
                                 z   = (v1.z + v2.z) / 2}]
} ;;

In this patch, v1 and v2 are not consumed (~ operator) to allow the matching of all edges that are incident to the same vertex.

Hexagons subdivision

Each hexagon of the mesh is substituted by 4 triangles:

patch build_triangles[genNb] = {
  f:[dim=2,(e1,e2,e3,e4,e5,e6) in faces]
  ~v1 < ~e1 > ~v2:[v2.gen == genNb] < ~e2 >
  ~v3 < ~e3 > ~v4:[v4.gen == genNb] < ~e4 >
  ~v5 < ~e5 > ~v6:[v6.gen == genNb] < ~e6 > ~v1 =>
} ;;

In this rule, only the hexagon f is matched
consumed. Its boundary is matched but not consumed to allow the building of triangles in the right hand side of the rule.

Iterating these two steps on a triangle produces the following animation:

Click on a picture to enlarge the view.

Here are some examples of subdivisions performing by MGS.

Click on a picture to enlarge the view.
Geometrical subdivisions. On top left, the initial mesh. On top right, the result after 4 iterations of the polyhedral algorithm. On bottom left, after 4 iterations of the same algorithm with another interpolation mask (Butterfly). On bottom right, the same thing with the modified butterfly mask to deal with vertices which have an incident number not equal to 6.

Back to top
MGS examples index
MGS home page

(currently under construction logo)
this site is under construction.
Pages started: May 2002. Last revision: 24 jully 2003.

Creative Commons License
Pictures, graphics and animations are licensed under a Creative Commons License.

English keywords for indexation: computer science, programming language, topological collections, transformation, declarative programming language, functional languages, simulation of biological processes, cell model, biological pathway, interaction network, gene regulation, signal transduction, morphogenesis, developmental biology, integrative simulation, biological organization, dynamical systems, dynamical structure, Gamma, CHAM, P system, L system, Paun, Lindenmayer, cellular automata, membrane computing, aqueous computing, artificial chemistry, GBF, Cayley graph, data fields, nested collections, rewriting, rule based programming, pattern-matching, intentional programming, compilation, interpretation, type, type inference, nested type, polytypism, catamorphism, static analysis, sequence, multiset, combinatorial algebraic topology, chain complex, chain group.