Chaman Singh VermaDepartment of Computer Sciences,
University of Wisconsin-Madison
Madison, WI 53706.
E-mail(1) : email@example.com
E-mail(2) : firstname.lastname@example.org
Phone : 608-698-4729
projects and Publications
I am currently a Ph.D. candidate in the department of
computer science at UW-Madison. My primary advisor is Prof.
Suresh Krishnan (Mechanical Engineering) and co-advisors are
Prof. Vadim Shapiro (Computer Science) and Prof. Micheal
Gleicher (Computer Science). I am expecting to graduate in
For many years, I have been passionately exploring various sequential and parallel programming languages, reusable components, robust and reliable computations in computational geometry algorithms. The following four very large projects are being single-handedly developed by me.
An All-Hex Meshing Strategy for Bifurcation
Geometries in Vascular Flow Simulation
Chaman Singh Verma, Paul Fischer, Seung E. Lee, and F. Loth
14th International Meshing Roundtable, San Diego, 2006
Automatic hexahedral mesh generation is a notoriously hard problem. Currently, high-quality hex meshing is largely heuristic and require a customized solution. In this project, we provide an automatic hex generation in bifurcation geometries. We have used this method to generate hex meshes for Carotid arteries.
Jaal: Engineering a High-Quality All-Quadrilateral
Chaman Singh Verma, Tim Tautges
20th International Meshing Roundtable Conference, Paris, France, 2011
In this paper, we describe the implementation of an open source code (Jaal) for producing a high-quality, isotropic all-quadrilateral mesh for an arbitrary complex surface geometry. Two basic steps in this process are: (1) Triangle to quad mesh conversion using Suneeta Ramaswamy’s tree matching algorithm and (2) Global mesh cleanup operation using Guy Bunin’s one-defect remeshing to reduce irregular nodes in the mesh.These algorithms are fairly deterministic, very simple, require no input parameters, and fully automated yet produce an extremely high quality all-quadrilateral mesh (with very few 3 and 5 valence irregular nodes) for a large class of problems.
||Towards FEA over Tangled Quads
Chaman Singh Verma, Krishnan Suresh
23th International Meshing Roundtable Conference, London, UK, 2014
In finite element analysis (FEA), a mesh is said to be tangled if it contains an element with negative Jacobin-determinant. Tangling can occur during mesh optimization and mesh morphing. Modern FEA, unfortunately, cannot handle such tangled meshes, i.e., it will lead to erroneous results. While significant progress has been made on untangling, there are no definitive untangling algorithms. Danczyk and Suresh recently proposed a theoretical extension to FEA such that one could accurately solve boundary value problems over such tangled meshes. However, their investigation was limited to simplicial meshes. In this paper, we consider the extension of the above framework to tangled quad meshes that pose additional challenges compared to simplicial meshes. These challenges are identified, and a tangling-framework is developed to address explicit quad tangling where quads are allowed to overlap but are required to be geometrically convex. Numerical examples illustrate the correctness of the proposed framework, opening new opportunities for meshing algorithms.
||A robust Combinatorial Approach to
Reduce Singularities in Quadrilateral Meshes:
Chaman Singh Verma, Krishnan Suresh,
24th International Meshing Roundtable, Austin, Texas, 2015
Journal Paper: Special Issue on Mesh Generation, CAD
Abstract: There many automatic quadrilateral mesh generators that can produce high-quality mesh with low distortion. However, they typically generate a large number of singularities that could be detrimental to downstream applications. This paper introduces Minimum Singularity Templates (MST) to reduce the number of singularities in an existing pure quad mesh. These templates are easy to encode with high-level grammar rules for complete automation, or interactive control. The MST exploits two important properties of quadrilateral meshes: (1) every submesh has even number of quad edges on its boundary, and (2) every submesh with 3, 4 or 5 topological convex corners on its boundary has at most two interior singularities. The MST (1) does not change the boundary edges of the patch, (2) avoids corner picking on a patch and solving NP-hard internal matching algorithm to select divisions, (3) is extremely fast with time complexity of O(1) in template creation, and (4) has low memory footprint and is robust. To illustrate the concepts, we consider quadrilateral meshes generated using Abaqus, Gmsh, and Cubit, and reduce the singularities within these meshes.
|| CQMG: An Indirect Approach to Low
Singularities and Bounded Distortion Quad Meshing:
Chaman Singh Verma, Krishnan Suresh
In the literature, many automatic quadrilateral mesh generation algorithms have been proposed and most of them produce a mesh with very high geometric qualities. However, very few algorithms control the number of singularities. In this paper, we are proposing a new indirect approach to quadrangulate a 2D domain with improved topological quality and bounded elements geometric distortions. In this method, we first transform a given triangle mesh into a low-quality quadrilateral mesh (which is trivial using 1-3 subdivision algorithm) and the apply three operations (1) Pillowing, which inserts new quadrilateral elements at the boundaries and (2) Dicing, which refine a chord in the quadrilateral mesh. If the chord is a boundary chord, or the dicing is partial, then four additional singularities are inserted into the mesh. (3) MST operations, reduce the singularities in the mesh. Usually, a few iterations of these steps results in a mesh with high topological and geometric qualities.
Download Paper : Waiting for approval from the publisher.
|| Alpha-MST: A Robust Unified
Algorithm for Quadrilateral Mesh Adaptation:
Chaman Singh Verma, Krishnan Suresh,
25th International Meshing Roundtable, Austin, Texas, 2016
Mesh adaptation plays a critical role in balancing computational eciency and numerical accuracy. Three types of mesh adaptation techniques exist today, namely, mesh improvement, mesh refinement and mesh simplification, and for each of these, several strategies have been proposed. Most of these strategies yield acceptable geometric mesh quality but provide limited control over topological quality.
In this paper, we introduce a unified algorithm for all three types of mesh adaptation for quadrilateral meshes. The algorithm builds upon the Minimum Singularity Templates (MST) idea proposed by the authors for improving the topological quality of a quadrilateral mesh. The MST is extended here to define the concept of an MST where a single parameter controls mesh adaptation: = 1 for mesh improvement, > 1 for mesh refinement, and < 1 for mesh simplification.The proposed algorithm generates mesh with high geometric and topological qualities. Further, it is non-hierarchical and stateless, and yet it provides an arbitrary level of mesh adaptation. Finally, since cyclic chords can play an important role in quadrilateral mesh adaptation, we provide a simple constructive algorithm to insert such chords using the MST. Several examples are presented that demonstrate the robustness, effectiveness, and versatility of the proposed concept and algorithm.
Download paper: Waiting for approval from the publisher.
Very often during mesh generation and mesh deformation mesh elements near the concave corners can get inverted i.e. the Jacobian of the element becomes negative. Such inversion can serious repercussions in graphics and FEM calculations. In the past, many non-linear optimization schemes were proposed to recover and/or avoid such inversions. However, most of these methods are computationally expensive and provide no guarantees on the convergence of the numerical methods.
In this project, we exploited two fundamental results from the theory (1) Any 2D curve can be deformed into a circular using curve shortening flow (Gregson' theorem) and (2) The harmonic map on a convex shape can be made inversion free.
Using these result, we have implemented a very simple mesh untangling algorithm. In the first phase of the algorithm, the boundary undergoes curve shortening flow until all the elements are inversion-free and in the second phase, a deformed shape in deformed back to the original mesh using the Locally-Injective-Mapping algorithm.
IMR24 Poster Document C++ Software DataSet Gallery
|| OpenGL Compass:
While interactively modifying a shape precisely, we need to have some mechanism to provide the angle. Although it can be done using dialog box but it is elegant and simple if we can place a digital compass over the model. This software implements an OpenGL based digital compass which can be placed anywhere on the screen. To provide interaction, a user needs to place the mouse near the tip of the neddle.
|Approximate shortest distance
calculation in tangled meshes.
Classical Dijkstra's algorithm correctly calculates exact and approximate distances in a mesh only if the mesh in untangled. When the mesh contains even a few inverted elements, results are unpredictable. However, a slight modification in the FEM code, the limitation of using untangled mesh can be relaxed.
Document C++ Software
Speculative Parallelization in Quadrilateral Mesh Clean-up Operations:
Singularities removal is essential to produce high-quality quadrilateral meshes. We had proposed Minimum Singularity Templates methods to reduce singularities using small topological convex patches. Very often, the input mesh has a large number of singularities and applying MST on smaller patches can be expensive. However, we can exploit the parallelism that exists among patches. If the patches do not overlap, many steps of MST can be performed in parallel. If patches overlap, then only one will be allowed to commit the changes and the remaining threads work is discarded.
in Parallel Delaunay Triangulation:
The sequential algorithm of Delaunay Triangulation is simple. It involves inserting vertices incrementally in the mesh. When a new vertex is inserted, the "Empty CircumCircle" property gets violated in a few triangles surrounding the vertex. Therefore, all such triangle which violates the Delaunay properties form a convex hole which must be remeshed. In large meshes such holes could be sparsely located which, indirectly, hide parallelism which could be efficiently allowing refilling holes.
||Large Scale Radial Basis functions and
Many radial basis functions generate dense matrices with a large condition number, therefore, is direct methods for solving the system of linear equations is the only way. However, solving dense large matrices can be prohibitively expensive both in terms of memory and execution time. To limit the size of the dense matrix, the geometric model must be sparsely sampled. How to choose such points which produce the least distance from the given point is often a non-trivial problem.
In this work, I implemented the idea of "Geodesic Farthest Point Sampling (GFP)". In this approach, we start with fixed number of points sampled using GFS and incrementally insert new points which produce the maximum deviation from the original point cloud set. After each selection, we solve the system of equations, extract the geometric surface from the RBF, and from the surface identify the points which are at the maximum distance. The whole process is computationally very expensive, but often it has to be done only once for a given model.
This application provides huge opportunities for parallelization on both shared and distributed memory machines. We use heterogeneous computational model using TBB and GPU to solve the problem in reasonable time.
||Experimental studies on large-scale
combinatorial multi-grid Laplace solvers:
||2D mesh deformations:
||Changing Chords Directions in a
A theorem from Juvan, Malnic and Mohar says:
Let $F$ be a family of non-null homotopic closed curves on a surface $\sigma$ with $b \ge 0$ boundary components which are pairwise non-homotopic and pairwise disjoint. Then
$\|F \| \le max( 1, 2(g_\sigma-1) + 2b$
We provide a constructive algorithm to produce such curves which exploit chords in a quadrilateral mesh over the manifold. If two different chords intersect each other we apply Schwartz template to separate them. We iteratively apply this template until it becomes impossible to avoid intersections. Thereafter, we can choose different curves passing through the chords.
Curve Shortening Flows (CSF):
Two remarkable results of Gage-Hamilton-Grayson theorem are:
1. A non-intersecting planar curve will converge to a
finite "round point".
Although the mathematical proofs are difficult to
understand, but we can visualize the result and
understand the results quickly. I have implemented the
Mokhtarian and Mackworth algorithm (may not be
precise, but the final results are as per
expectations) in C++.
CSF ( or Mean Curvature flow in 3D) can be used to
solve one practical problem in "Mesh Untangling".
Catmull-Clark subdivision without modifying boundary.
The Catmull-Clark subdivision scheme is widely used
in geometric modelling. It is also used to transform a
quad-dominant mesh into an all-quad mesh. However, if
there are boundary segments in the model then
this subdivision will subdivide the boundary segments
also. Sometimes, we neither want to subdivide the
boundary and still want to have an quadmesh. This is
possible if we allow singularities in the mesh.
In this work, we first subdivide all the internal
elements according to the standard Catmull-Clark
scheme leaving elements adjacent to the boundary
segments. This will create a quad-dominant mesh with
non-quad elements will be adjacent to the boundary. In
the second step, we have to find pairs of non-quad
elements and create quad elements by collapsing them.
The major challenge is to minimize the changes in the
quad elements formed in the first stage because an
arbitrary pairing could modify the global structure of
the quad mesh.
Disk Reorganization and File System Layout Visualization:
Local Transformations in Hexahedral Meshing: A brief literature survey.
In the left Figure, a famous problem of "Schneider
Problem" is shown. It is a simple pyramid with a
square base and four triangular sides.
It is conjectured that the "holy-grail" of hexahedral
mesh generation can be resolved if we can find the
solution to this simple problem. In the past, many
attempts have been made to create geometric
valid hexahedral elements in this model, however, all
known algorithms fail. Download 1529 elements solution and
check yourself why hexahedral mesh generation is still
an open problem even for toy examples.