CS 888 Project: PQ, Conical and Circular meshes for Architectural Design

Murtaza Safri

Project Description

Planar Quadrilateral (PQ) meshes and their special cases of Conical and Circular meshes possess useful properties with respect to architectural design and modeling. The papers [1] and [2] discuss about these properties and this project is based on it. In architectural design planar surfaces are easier to manufacture as opposed to non planar ones and quadrilaterals are cost effective compared to triangular meshes. In particular, conical meshes possess face offsets and circular meshes possess vertex offset meshes that are useful in providing support structures for surfaces. This project investigates the techniques used by [1] and [2] to derive these meshes.

Implementation

· The project is written in Visual C++ and OpenGl is used for rendering. The viewer supports basic features like moving and rotating objects.

· The program is interfaced with Matlab engine to provide optimization for the Levenberg Marquardt algorithm.

· Test case meshes have been modeled using Maya trial edition. The output meshes shown here are rendered using Maya.

Results and Discussion

Planar quadrilaterals

A planar quadrilateral or PQ mesh is one in which all quads are planar. Such a mesh can be obtained by minimizing the objective function:

(1)

Where, for each perturbed vertex v_i,j

(2)

and foot point y_i,j

(3)

. The planarity condition is expressed for each quadrilateral Q_i,j with interior angles as

(4)

For each quadrilateral Q_i,j the unit vectors along the four sides e_i,j, e_i+1,j, f_i,j and f_i,j+1, f_det is computed as four individual terms

(5)

This term is useful for narrow polygons because it ensures planarity in the limit of the quad becoming a line.

One problem encountered was the calculation of the foot point which is the closest point on the surface which we want to model. Although the authors do not mention it explicitly, they refer to a paper (3) where the foot point is computed by intersecting the surface normal of the perturbed surface with the original surface. The method requires that the continuous surface representation. However, in my case I only have the discretized mesh information. There are a few ways to resolve this problem. If the given mesh is close to being PQ then we can use the point which originally corresponded with v_i,j as the foot point. If we want to allow more deformation then we can construct a continuous representation of the surface. The mesh faces themselves are C⁰ continuous and so can be used. The foot point can be obtained by computing the distance of v_i,j with the face planes of the original mesh and selecting the point on the face which is closest to v_i,j. For most of the experiments I did not use the term in (5) because most quadrilateral meshes don’t have sharp angled or narrow polygons.

There were also some minor typographical errors, like in (2) there was no 2 norm in the fairness term. This is not possible because a square of vector term (the points have 3 coordinates and so does their difference) cannot be computed. Also, (5) needs to be expressed as individual terms in the objective function, which is not mentioned. Triangles have also not been dealt with. This can become a problem with mesh computation. However, triangles can be removed by applying Catmull Clark subdivision which always gives quadrilaterals.

For optimization Levenberg Marquardt method was used which is based on Gauss Newton method and minimizes a functional composed of sums of squares of functions. However, it has been found that the optimization is very slow. Even for moderately sized meshes composed of 400 vertices the method took about 40 seconds to converge on a 2.5 Ghz Core 2 processor. This is a little surprising given the authors claim of computing a 6000 vertex mesh in 13 seconds on a 2.0 Ghz PIV. One possible explanation is that the authors use an analytically computed Jacobian matrix for the optimization, as opposed to approximating it with finite difference method. This can reduce computation time significantly. However obtaining the analytical form of the Jacobian is non-trivial. Still the difference seems to be quite large and perhaps other optimization improvements were used by the authors.

The dimensionality of the vector valued function to be optimized affects the speed of optimization search as well the dimensionality of the Jacobian matrix. It is preferable to have a smaller sized vector function. Keeping this in mind, if any of the weights () in (1) is zero the term associated with the zero weight is removed from the vector function. This can affect the computation speed considerably.

Figure showing result of PQ mesh planarization

Conical Meshes

The conical meshes can be computed by enforcing the condition for each vertex

(6)

where the angles are shown in Figure.

Figure: Vertex of conical mesh

For a vertex of valence greater than four, [1] just enforces the conical condition on any four incident faces. However, there is no justification given for such a step and I think there is some error in theory here.

Figure: Conical mesh generated from the non planar mesh

Circular Meshes

For circular meshes the condition is given by the four angles of a quad

(7)

The conditions (4) and (5) can be removed because (1) is sufficient to guarantee convexity and planarity.

Figure: Circular mesh generated from the non planar mesh

Liu et. al. [1] do not deal with polygons in the mesh with sides greater than 4. This is not a good idea in my opinion because without any condition the polygon might become narrow or sharp. This can be resolved by adding an extra condition for these polygons so that it possesses a circumcircle like the other quads. In general it is not possible to find a condition for an n-gon which ensures existence of a circumcircle. However, for the special case of a regular polygon where the sides are of equal length and the interior angles are all equal, the polygon will possess a circumcircle. These conditions can then be input to the optimization algorithm. A more general approach is to compute the minimum bounding sphere of the face and impose the condition for each vertex , where is the center of the sphere and is its radius. This condition allows for the polygon to be non regular but still possess a circumcircle.

Offset surfaces

For circular meshes generating the offsets is trivial. Each vertex of the mesh is offset in the direction of the vertex normal by a fixed distance. For a face offset, a translation is computed for each vertex separately by trigonometric operations.

Face offset of the Conical mesh generated before (In program and Rendered)

Vertex offset of the circular mesh generated before (In program and Rendered)

Offset generated off a cut sphere (In program and Rendered)

Conical to circular construction

In [2], Pottmann and Wallner list two ways of constructing circular meshes from conical meshes. The first method is direct construction as shown in Figure 2. It is done by selecting a point in any one face of the conical mesh and then reflecting that point in the bisector plane of the edges of the conical mesh. Another method is polar dual construction, where the conical mesh is first circumscribed to a sphere of radius 1. The tangent points of the face planes are connected to give a circular mesh. The polar dual construction is then offset to give the circular mesh in the face planes of the conical mesh.

Figure 2 Direct construction Conical to circular mesh (from [2])

I have used a different method for constructing the circular mesh from the conical mesh. First it is to be noted that the distance of each point m_i,j of the circular mesh from the conical vertex l_i,j is constant. This is because the four points of the circular mesh lie at a constant distance from the center of the circle of its quadrilateral. The axis of the circular quad is also coincident with the axis of the cone of the conical mesh. Also, the faces around the vertex of the conical mesh are tangent to a cone along lines which we call rulings. The vertices of the circular mesh therefore lie at constant distance along the rulings of the cone of the conical mesh. Using this idea, I first obtain the four unit ruling vectors. The distance of the seed vertex from the conical vertex is computed. Along the other three rulings a point is selected at the keeping the same distance as the seed vertex.

Figure 3 Conical to circular mesh conversion. The red shaded circular mesh is obtained from the blue shaded conical mesh.

Conical meshes can also be constructed from circular meshes. One interesting application of the construction method I found is that it can yield a faster approach to generate conical meshes. This is because for circular meshes fangle and fdet conditions are not needed and the dimensionality of the vector function for optimization is reduced. Thus the difference in dimensionality becomes (3*number of vertices + 5*number of faces) for conical mesh – (3*number of vertices + 2 * number of faces for circular mesh) = 3*number of faces.

Conclusion and future work

Liu et. al. [1] obtain the initial mesh from discretizing the principle curvature lines. This discretization leads to meshes that are planar, conical and circular meshes or close to it. This is because by definition principle curvature lines intersect at right angles. Most of the modeling tools give a good approximation to the principal curvature lines of the surface. The generated meshes are also planar and close to being conical or circular, unless highly deformed surfaces are modeled. These tools also compute the results in a reasonably short amount of time. The algorithms in these tools are likely much more optimized than the ones given in the paper. In my opinion, it would be better to use these tools than use a computationally expensive method like in [1]. It would be useful however in situations where the freeform surface has large deformations and face/vertex offset properties are desired as current modeling tools do not handle planarization well with such surfaces. Methods in [1] can be incorporated in the modeling tools directly as well.

One natural question to ask is, is there any conical for vertices of valence other than four or circular mesh for n-gons. The answer is that conical and circular meshes have been defined as the discretization of the conjugate curve networks. Such a network will always give a quadrilateral mesh, baring any singularities in the network. However, the vertex and face offset properties can exist for other types of meshes. In particular a recent publication [4] discusses that planar hexagonal meshes possess face offsets. In [5] vertex offset meshes have been explored for general polyhedral surfaces with n-gon faces.

References

1. Geometric Modeling with Conical Meshes and Developable Surfaces (Yang Liu, Helmut Pottmann, Johannes Wallner, Yong-Liang Yang, Wenping Wang, 2006)

2. The focal geometry of circular and conical meshes (Helmut Pottmann and Johannes Wallner, 2006)

3. Object modeling by registration of multiple range images (Y. Chen and G. Medioni, In Proc. IEEE Conf. on Robotics and Automation 1991)

4. Hexagonal Meshes with Planar Faces (Wenping Wang, Yang Liu, Dongming Yan, Bin Chan, Ruotian Ling, Feng Sun, HKU CS Technical Report, 2008)

5. On Vertex Offsets of Polyhedral Surfaces (Yang Liu and Wenping Wang, 2008)