CS 888 Project: PQ, Conical and Circular meshes for Architectural Design
Murtaza Safri
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.
· 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.
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^{0} 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 nontrivial. 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
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
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 ngon 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.
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)
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.
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 ngons. 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 ngon faces.
1. Geometric Modeling with Conical Meshes and Developable Surfaces (Yang Liu, Helmut Pottmann, Johannes Wallner, YongLiang 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)