We consider surfaces that are parametrized over a polygonal domain $\Omega$ in $\R^2$. To generate a progressive approximation of such a surface we use continuous piecewise linear functions subordinate to a sequence of nested triangulations of the parametric domain. We start from some initial (coarse) triangulation $P_0$ of $\Omega$ and refine it locally using a specific rule to receive finer triangulations on which better approximations to the surface are to be found. There are different rules of refinement that are in use but here we shall consider only the rule of {\it newest vertex bisection} that gives us the advantage of using {\it tree approximation} to find the near best among all the approximations over the refinements of $P_0$ with $n$ triangles.

After the sequence of approximations $\{S_j\}$ of the surface is found, a progressive encoding of the surface is generated usually by storing the information about the initial approximation $S_0$ and the differences $S_j-S_{j-1}$. The most common approach for the latter is to use a subdivision scheme to compute from $S_{j-1}$ a good preliminary approximation to the next level $S_j$ and then to store only the differences. This process depends on the way $S_j$ is represented. In a typical setting it is done by storing the values of $S_j$ at the vertices of the corresponding triangulation $P_j$. Here we propose to use the values of certain functionals over triangles from $P_j$.

Given a triangulation $P_j$ the approximation $S_j$ is defined as a quasi-interpolant of the original surface. Thus the value $S_j(v)$ at a vertex $v$ of $P_j$ is calculated as a linear combination of some functionals over the surrounding triangles from $P_j$. There are three different functionals for each triangle $\Delta\in P_j$ and that suggests using a subdivision scheme based on these triplets. The proposed method gives the possibility to work with almost regular meshes (generated by newest vertex bisection rule) even for surfaces given by scattered data points. The data it produces has a tree structure and very good local properties.