| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | August 15, 2014 |
| Latest Amendment Date: | September 14, 2015 |
| Award Number: | 1422019 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Rahul Shah
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2014 |
| End Date: | August 31, 2018 (Estimated) |
| Total Intended Award Amount: | $102,875.00 |
| Total Awarded Amount to Date: | $102,875.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
5600 CITY AVE PHILADELPHIA PA US 19131-1308 (215)879-7300 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
PA US 19131-1308 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
The representation and reconstruction of complex three-dimensional objects is critical in a wide range of applications in computing today. Polygonal meshes have become the industry standard for the representation of surfaces with highly complex geometry and arbitrary genus in computer graphics and geometry processing applications. While triangle meshes are the most popular type of mesh representation for surfaces, quadrilateral meshes are better suited than triangle meshes in several applications such as character animation, texture mapping, spline-based surface modeling, mesh compression, and some specific finite element analysis applications. Provably good algorithms for generating triangle meshes from surfaces given by parametric or implicit functions or as point point clouds are widely available. However, algorithms to generate quadrilateral meshes with provable quality guarantees for such surfaces are not as prevalent, in part because the problem of generating a quadrilateral mesh from a given surface is intrinsically harder than its triangular counterpart. The goal of this project is to develop algorithms for quadrilateral meshes for various surface representations with provable guarantees on element quality as measured by commonly used metrics such as angle bounds or aspect ratio, and mesh quality as measured by mesh size or anisotropy. Direct and indirect methods (which generate a quad mesh from a triangle mesh), as well as parameterization guided methods will be utilized. Techniques from computational geometry and graph theory will play a central role in the design and development of algorithms.
The automated generation of provably good quadrilateral meshes for surfaces is a fundamental problem that is of interest both in theory, as it raises several geometric, combinatorial, and graph-theoretic questions, as well as practice, where the computational pipeline from designing a model for the surface to the end stage of simulation or animation is frequently dominated by the meshing process. A formal understanding of these questions is critical not only for the theoretical underpinnings of automated mesh generation, but also for the sound practice of utilizing the meshes in a wide range of applications.
As a collaborative effort between PIs at three undergraduate institutions, involvement of undergraduate students in research projects is an integral part of this project. An important and particular goal for this project is the creation of a larger peer group for female and minority undergraduate Computer Science majors by providing opportunities for collaboration and joint research projects between students across all three institutions. Through early and active involvement of undergraduates in the project, the PIs also seek to create a pipeline of female and minority students bound for graduate school in Computer Science.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
Quadrilateral meshes (including those derived from triangles) are often used for computational analysis, graphical representation, and modeling. Figure 1 illustrates the progression from shape outline to triangulated and quadrilateral meshes. Robinson's Continuum-Region-Element method calculates stress and displacement values for each quad to evaluate its quality. The specific Shape Parameters that describe a quadrilateral are its aspect ratio, skew angle, and two tapers. These parameters may be calculated using two different approaches, (a) one that employs the Jacobian matrix, and (b) another that does not but employs an alternative approach using a systematic drawing procedure. Method (a) employs the Jacobian and expresses the parameters in terms of coefficients and polynomials. It has been observed, however, that the specific order of the four points that define a given quad greatly affects the calculated results and therefore may lead to a suboptimal network of shapes. For example, for a given set of points {p1,p2,p3,p4}, different results may be obtained when the measures are calculated in these orders: (p1,p2,p3,p4) vs. (p2,p3,p4,p1) vs. (p4,p3,p1,p2) vs. (p4,p3,p2,p1). Therefore, an algorithm that permutes the sequence of points to produce consistent results regardless of order is desirable. During this project, we created and implemented such an algorithm that can rearrange a given sequence of points in a consistent and predictable manner that yields results for these measures that are invariant regardless of input order.
Last Modified: 11/30/2018
Modified by: George J Grevera
Please report errors in award information by writing to: awardsearch@nsf.gov.
