In the previous session, we have learned what Mesh is and the various aspects upon which a mesh can be classified. Mesh generation requires expertise in the areas of meshing algorithms, geometric design, computational geometry, computational physics, numerical analysis, scientific visualization and software engineering to create a mesh tool.

Over the years, mesh generation technology has evolved shoulder to shoulder with increasing hardware capability. Even with the fully automatic mesh generators there are many cases where the solution time is less than the meshing time. Meshing can be used for wide array of applications, however the principal application of interest is the finite element method. Surface domains are divided into triangular or quadrilateral elements, while volume domain is divided mainly into tetrahedral or hexahedral elements. A meshing algorithm can ideally define the shape and distribution of the elements.

A key step of the finite element method for numerical computation is mesh generation algorithms. A given domain is to be partitioned it into simpler ‘elements’. There should be few elements, but some portions of the domain may need small elements so that the computation is more accurate there. All elements should be ‘well shaped’. Let us take a walkthrough of different meshing algorithms based of two common domains, namely quadrilateral/hexahedral mesh and triangle/tetrahedral mesh.

Algorithm methods for Quadrilateral or Hexahedral Mesh

Grid-Based Method

The grid based method involves the following steps:

• A user defined grid is fitted on 2D & 3D object. It generates quad/ hex elements on the interior of the object.
• Some patterns are defined for boundary elements followed by forming a boundary element by applying boundary intersection grid.
• This results in the generation of quadrilateral mesh model.

 

Medial Axis Method

Medial axis method involves an initial decomposition of the volumes. The method involves few steps as given below:

• Consider a 2D object with hole.
• A maximal circle is rolled through the model and the centre of circle traces the medial object.
• Medial object is used as a tool for automatically decomposing the model in to simple meshable region.
• Series of templates for the region are formed by the medial axis method to fill the area with quad element.

 

Plastering method

Plastering is the process in which elements are placed starting with the boundaries and advancing towards the centre of the volume. The steps of this method are as follows:

• A 3D object is taken.
• One hexahedral element is placed at boundary.
• Individual hexahedral elements are projected towards the interior of the volume to form hexahedral meshing, row by row and element by element.
• The process is repeated until mesh generation is completed.

 

Whisker Weaving Method

Whisker weaving is based on the concept of the spatial twist continuum (STC). The STC is the dual of the hexahedral mesh, represented by an arrangement of intersecting surfaces, which bisect hexahedral elements in each direction. The whisker weaving algorithm can be explained as in the following steps:

• The first step is to construct the STC or dual of the hex mesh.
• With a complete STC, the hex elements can then be fitted into the volume using the STC as a guide. The loops can be easily determined from an initial quad mesh of the surface.
• Hexes are then formed inside the volume, once a valid topological representation of the twist planes is achieved. One hex is formed wherever three twist planes converge.

 

Paving Method

The paving method has the following steps to generate a quadrilateral mesh:

• Initially a 2D object is taken.
• A node is inserted in the boundary and the boundary node is considered as loop.
• A quadrilateral element is inserted and a row of elements is formed.
• The row of element is placed around the boundary nodes.
• Again this same procedure adopt for next rows.
• Finally quad mesh model is formed.

 

Mapping Mesh Method

The Mapped method for quad mesh generation involves the following steps:

• A 2D object is taken.
• The 2D object is split into two parts.
• Each part is either a simple 2D rectangular or a square object.
• The simple shape object is unit meshed.
• The unit meshed simple shape object is mapped in its original form and then joined back to form actual object.

 

Algorithm methods for Triangular and Tetrahedral Mesh

Quadtree Mesh Method

With the quadtree mesh method, square containing the geometric model are recursively subdivided until the desired resolution is reached. The steps for two dimensional quadtree decomposition of a model are as follows:

• A 2D object is taken.
• The 2D object is divided into rectangular parts.
• A Detail tree of divided object is provided.
• The object is eventually converted into triangle mesh.

 

 

Delaunay Triangulation Method

A Delaunay triangulation for a set P of discrete points in the plane is a triangulation DT such that no points in P are inside the circum-circle of any triangles in DT. The steps of construction Delaunay triangulation are as follows:

• The first step is to consider some coordinate points or nodes in space.
• The condition of valid or invalid triangle is tested in every three points which finds some valid triangle to make a triangular element.
• Finally a triangular mesh model is obtained.

Delaunay Triangulation maximizes the minimum angle of all the angle of triangle and it tends to avoid skinny triangles.

 

Advancing Front Method

Another very popular family of triangular and tetrahedral mesh generation algorithms is the advancing front method, or moving front method. The mesh generation process is explained as following steps:

• A 2D object with a hole is taken.
• An inner and outer boundary node is inserted. The node spacing is determined by the user.
• An edge is inserted to connect the nodes.
• To start the meshing process, an edge AB is selected and a perpendicular is drawn from the midpoint of AB to point C (where C is node spacing determined by the user) in order to make a triangular element.
• After one element is generated, another edge is selected as AB and a point C is made, but if in case any other node lets point D within the defined radius, then ABC element is cancelled and instead, an element ABD is formed.
• This process is repeated until mesh is generated.

 

Spatial Decomposition Method

The steps for spatial decomposition method are as follows:

• Initially a 2D object is taken.
• The 2D object is divided into minute parts till we get the refined triangular mesh.

 

Sphere Packing Method

The sphere packing method follows the given steps:

• Before constructing a mesh, the domain is filled with circles.
• The circles are packed closely together, so that the gaps between them are surrounded by three or four tangent circles.
• These circles are then used as a framework to construct the mesh, by placing mesh vertices at circle centers, points of tangency, and within each gap while using generated points. Eventually, the triangular mesh is generated.

 

 

 

 Source

Singh, Dr. Lokesh, (2015). A Review on Mesh Generation Algorithms. Retrieved from http://www.ijrame.com

The quality of a mesh plays a significant role in the accuracy and stability of the numerical computation. Regardless of the type of mesh used in your domain, checking the quality of your mesh is a must. The ‘good meshes’ are the ones that produce results with fairly acceptable level of accuracy, considering that all other inputs to the model are accurate. While evaluating whether the quality of the mesh is sufficient for the problem under modeling, it is important to consider attributes such as mesh element distribution, cell shape, smoothness, and flow-field dependency.

Element Distribution

It is known that meshes are made of elements (vertices, edges and faces). The extent, to which the noticeable features such as shear layers, separated regions, shock waves, boundary layers, and mixing zones are resolved, relies on the density and distribution of mesh elements. In certain cases, critical regions with poor resolution can dramatically affect results. For example, the prediction of separation due to an adverse pressure gradient depends heavily on the resolution of the boundary layer upstream of the point of separation.

Cell Quality

The quality of a cell has a crucial impact on the accuracy of the entire mesh. The quality of cell is analyzed by the virtue of three aspects: Orthogonal quality, Aspect ratio and Skewness.

Orthogonal Quality: An important indicator of mesh quality is an entity referred to as the orthogonal quality. The worst cells will have an orthogonal quality close to 0 and the best cells will have an orthogonal quality closer to 1.

Aspect Ratio: Aspect ratio is an important indicator of mesh quality. It is a measure of stretching of the cell. It is computed as the ratio of the maximum value to the minimum value of any of the following distances: the normal distances between the cell centroid and face centroids and the distances between the cell centroid and nodes.

Skewness: Skewness can be defined as the difference between the shape of the cell and the shape of an equilateral cell of equivalent volume. Highly skewed cells can decrease accuracy and destabilize the solution.

Smoothness

Smoothness redirects to truncation error which is the difference between the partial derivatives in the equations and their discrete approximations. Rapid changes in cell volume between adjacent cells results in larger truncation errors. Smoothness can be improved by refining the mesh based on the change in cell volume or the gradient of cell volume.

Flow-Field Dependency

The entire effects of resolution, smoothness, and cell shape on the accuracy and stability of the solution process is dependent upon the flow field being simulated. For example, skewed cells can be acceptable in benign flow regions, but they can be very damaging in regions with strong flow gradients.

Correct Mesh Size

Mesh size stands out as one of the most common problems to an equation. The bigger elements yield bad results. On the other hand, smaller elements make computing so long that it takes a long amount of time to get any result. One might never really know where exactly is the mesh size is on the scale.

It is important to consider chosen analysis for different mesh sizes. As smaller mesh means a significant amount of computing time, it is important to strike a balance between computing time and accuracy. Too coarse mesh leads to erroneous results. In places where big deformations/stresses/instabilities take place, reducing element sizes allow for greatly increased accuracy without great expense in computing time.

Whether working on a renovation project or making an information data about an as-built situation, it is understandable that the amount of time and energy spent on analysis of the object/project in hand can be quite debilitating. Technical literatures over the years, has come up with several methods to make a precise approach. But inarguably, the most prominent method is the application of Point Clouds.

3D scanners gather point measurements from real-world objects or photos for a point cloud that can be translated to a 3D mesh or CAD model.

But what is a Point Cloud?

A common definition of point clouds would be — A point cloud is a collection of data points defined by a given coordinates system. In a 3D coordinates system, for example, a point cloud may define the shape of some real or created physical system.

Point clouds are used to create 3D meshes and other models used in 3D modeling for various fields including medical imaging, architecture, 3D printing, manufacturing, 3D gaming and various virtual reality (VR) applications. A point is identified by three coordinates that, correlate to a precise point in space relative to a point of origin, when taken together.
There are numerous ways of scanning an object or an area, with the help of laser scanners which vary based on project requirement. However, to give a generic overview of point cloud generation process, let us go through the following steps:

1. The generation of a point cloud, and thus the visualization of the data points, is an essential step in the creation of a 3D scan. Hence, 3D laser scanners are the tools for the task. While taking a scan, the laser scanner records a huge number of data points returned from the surfaces in the area being scanned.

2. Import the point cloud that the scanner creates into the point cloud modeling software. The software enables visualizing and modeling point cloud, which transforms it into a pixelated, digital version of the project. 

3. Export the point cloud from the software and import it into the CAD/BIM system, where the data points can converted to 3D objects.

Different 3D point cloud file formats

Scanning a space or an object and bringing it into designated software lets us to further manipulate the scans, stitch them together which can be exported to be converted into a 3D model. Now there are numerous file formats for 3D modeling. Different scanners yield raw data in different formats. One needs different processing software for such files and each & every software has its own exporting capabilities. Most software systems are designed to receive large number of file formats and have flexible export options. This section will walk you through some known and commonly used file formats. Securing the data in these common formats enables the usage of different software for processing without having to approach a third party converter.

Common point cloud file formats

OBJ: It is a simple data format that only represents 3D geometry, color and texture. And this format has been adopted by a wide range of 3D graphics applications. It is commonly ASCII (American Standard Code for Information Interchange).

PLY: The full form of PLY is the polygon file format. PLY was built to store 3D data. It uses lists of nominally flat polygons to represent objects. The aim is to store a greater number of physical elements. This makes the file format capable of representing transparency, color, texture, coordinates and data confidence values. It is found in ASCII and binary versions.

PTS, PTX & XYZ: These three formats are quite common and are compatible with most BIM software. It conveys data in lines of text. They can be easily converted and manipulated.

PCG, RCS & RCP: These three formats were developed by Autodesk to specifically meet the demands of their software suite. RCS and RCP are relatively newer.

E57: E57 is a compact and widely used vendor-neutral file format and it can also be used to store images and data produced by laser scanners and other 3D imaging systems.

Challenges with point cloud data

The laser scanning procedure has catapulted the technology of product design to new heights. 3D data capturing system has come a long way and we can see where it’s headed. As more and more professionals and end users are using new devices, the scanner market is rising in a quick pace. But along with a positive market change, handling and controlling the data available becomes a key issue.

Five key challenges professionals working with point cloud face are:

• Data Format: New devices out there in the market yields back data in a new form. Often, one needs to bring together data in different formats from different devices against a compatible software tool. This presents a not-so-easy situation

• Data Size: With the advent of new devices, scanning has become cheaper with greater outputs. It is possible to scan huge assets from a single scan. This has resulted in the creation of tens of thousands of data points. A huge data of points can be challenging to handle and share between project partners.

• Inter-operability: Integration between new technologies with the existing software can be quite arduous. Although, with careful investment of time and money, the goal can be achieved nonetheless.

• Access: All the professionals involved in the entire lifecycle of a product can benefit from having access to point cloud data. But multiple datasets in multiple formats usually makes it more of a hassle.

• Ownership: Who owns point cloud data? In the past, EPCs and the contractors who capture the data become custodians of the information.

• Rendering: Different formats can result in rendering problems for point clouds.

As we have seen during the introduction, the first step to reverse engineer a product is through scanning with the help of 3D scanners. Early eras have seen the painstaking task of obtaining dimensions of an existing product. These methods were time consuming and needed attention to details from the very first stage.

However, with the rapid development in the scanning technology, the inception of a product has caught speed and the chances of errors have reduced dramatically which has made 3D scanning and measurement an important part, starting from design stage to inspection stage.

3D laser scanning is the technology to capture a physical object’s exact size and shape using a laser beam to create a digital 3-dimensional representation of the same. 3D laser scanners create “point clouds” of data from the surface of an object.

We will go through point clouds in later sections.

3D Scanning Technology

3D laser scanning efficiently takes the measurements of contoured surfaces and complex geometries which require huge amounts of data for their accurate description because doing this with the use of traditional measurement methods is impractical and time consuming. It creates accurate point cloud data by acquiring measurements and dimensions of free-form shapes.

The basic working principle of a 3D scanner is to collect data of an entity. It can either be:

• an object
• an environment (such as a room)
• a person (3D body scanning)

In reverse engineering, laser scanner’s primary aim is to provide a lot of information about the design of an object which in the later stages gets converted to 3D CAD models, considering the compatibility of 3D scans and Computer Aided Design (CAD) software. 3D scans are even compatible with 3D printing which requires some specific computer software.

3D scanning technologies varies with different physical principles and can be classified as follows:

• Laser triangulation 3D scanning technology: In this category, the laser scanner projects a laser beam on a surface and measures the deformation of the laser ray.

• Structured light 3D scanning technology: This technology acquires the shape of a surface by measuring the deformation of a light pattern.

• Photogrammetric technology: It is also known as 3D scan from photography. It reconstructs an object from 2D to 3D and has specific computational geometrical algorithms for the task.

• Laser pulse 3D scanning technology: This unique process collects geometrical information by evaluating the time taken by a laser beam to travel between its emission and reception.

Contact based 3D scanning technology: This process requires contact between the probe and the object, where the probe is moved firmly over the surface to acquire data.

Types of scanners

Apart from scanning technologies, there are various types of 3D scanners. Some are built for short range scanning while others are ideal for medium or long range scanning. The built and usage of specific scanners hugely depend upon size of the object to be scanned. The scanners used for measuring small objects vastly differ from the ones that are used for large bodied objects, such as a ship.

Here is a brief summary of types of 3D laser Scanners:

1. Short Range 3D scanners: Short Range 3D scanners utilize either a Laser triangulation technology or Structured Light technology.

2. Laser based 3D scanners: Laser scanners work by projecting laser a beam or multiple laser beams on an object and capturing its reflection with sensors, which are located at a fixed distance from the scanners.

3. Structured light 3D scanners: These are also known as white light scanners. However, most structured scanners use blue or white LED light. The light pattern usually consists of a certain geometrical shape such as bar or block or any other shape, which is projected onto the object. The sensors consider the edge of the pattern to determine the 3D shape of the object. Blue or white light scanners are generally used to obtain outward dimension.

4. Medium and Long range scanners: Long range 3D scanners are used for large objects such as buildings, ships, aircrafts, and military vehicles. These scanners rotate and spin a mirror which reflects the laser outward towards the object or areas to be 3D scanned.

5. Arm based scanners: Arm based scanners are very useful when measuring small minor parts, as it can be maneuvered by attaching it to the arm and is generally portable.

Benefits of 3D Laser Scanners

3D scanners have contributed a lot over the years and needless to say, it comes up with many benefits. Some of them are as follows:

• Able to scan tough surfaces, such as shiny or dark finishes.
• This is strictly for the handheld or other portable scanners. But given their importance, it is safe to say that the portability of scanners has played a great role in easing up engineering.
• The scanning technology has made it possible to capture millions of point in a considerably less time.
• Scanners are less sensitive to changing light conditions and ambient light.
• Scanning of complex contours and geometrical figures have become more convenient with the invention of groundbreaking scanning technologies.
• Nowadays, laser scanners have become so diverse that they are produced depending upon variety of projects or the objects to be scanned.

Up until now, we believe our readers got a clear explanation of reverse engineering. Let us give walkthrough — Reverse engineering is the process of extracting design information after studying a physical product, with the intent to reproduce the product, or to create another object that can interact with it.

In the past, designers resorted to physical measurement of the product to redraw its geometry. Today, designers use 3D scanners to capture measurements. The scanned data is then imported to CAD where the design can be analyzed, processed, manipulated and refined. Two key aspects that fall in place when focusing on reverse engineering process are:

Parametric Model/Modeling

A parametric model captures all its information about the data within its parameters. All you need to know for predicting a future data value from the current state of the model is just its parameters.
The parameters are usually finite in dimensions. For a parametric model to predict new data, knowing just the parameters is enough. A parametric model is one where we assume the ‘shape’ of the data, and therefore only have to estimate the coefficients of the model.

Non-parametric Model/Modeling

A non parametric model can capture more subtle aspects of the data. It allows more information to pass from the current set of data that is attached to the model at the current state, to be able to predict any future data.
The parameters are usually said to be infinite in dimensions. Hence, it can express the characteristics in the data much better than parametric models. For a non parametric model, predicting future data is based on not just the parameters but also in the current state of data that has been observed. A non-parametric model is one where we do not assume the ‘shape’ of the data, and we have to estimate the most suitable form of the model, along with the coefficients.

The previous sections dealt with the initial and middle stages of reverse engineering. This section highlights a stage which is undoubtedly crucial for product development. After a meshed part is aligned, it goes through either—surface modeling in tools such as Polyworks, which generates a non-parametric model (IGES or STEP format) or parametric modeling where a sketch of the meshed part is created instead of putting it through surfacing (.PRT format). The resultant is generally called, 3D computer aided model or CAD model.

But, what is CAD?  

CAD is the acronym for Computer Aided Design. It covers different variety of design tools used by various professionals like artists, game designers, manufacturers and design engineers.

The technology of CAD systems has tremendously helped users by performing thousands of complex geometrical calculations in the background without anyone having to drop a sweat for it. CAD has its origin in early 2D drawings where one could draw objects using basic views: top, bottom, left, right, front, back, and the angled isometric view.  3D CAD programs allow users to take 2D views and convert them into a 3D object on the screen.  In simple definition, CAD design is converting basic design data into a more perceptible and more understandable design.

Each CAD system has its own algorithm for describing geometry, both mathematically and structurally.  

Different CAD models

Everything comes with its own varieties and CAD modeling is no stranger to it. As the technology evolved, CAD modeling came up in different styles. There are many methods of classifying them, but a broad general classification can be as follows:

• 2 dimensional or 2D CAD: The early version of CAD that most of us are aware of. These are 2-dimensional drawings on flat sheet with dimensions, layouts and other information needed to manufacture the object.
• 3 dimensional or 3D CAD: The purpose of both 2D and 3D models is the same. But what sets 3D models apart is its ability to present greater details about the individual component and/or assembly by projecting it as a full-scale 3-dimensional object. 3D models can be viewed and rotated in X, Y, or Z axes. It also shows how two objects can fit and operate which is not possible with 2D CAD.

3D models can be further classified into three categories:

• 3D Wire-frame Models: These models resemble an entire object made of just wires, with the background visible through the skeletal structure.
• Surface Models: Surface models are created by joining the 3D surfaces together and look like real-life objects.
• Solid Models: They are the best representation of real physical objects in a virtual environment. Unlike other models, solid models have properties like weight, volume and density. They are the most commonly used models and serve as prototypes for engineering projects.

Types of CAD formats

Different professionals use different software, owing to different reasons like cost, project requirements, features etc. Although, software comes with their own file formats, there are instances where one needs to share their project with someone else, either partners or clients, who are using different software. In such cases, it is necessary that both party software understand each other’s file formats. As a result of this situation, it is necessary to have file formats which can be accommodated in variety of software.

 CAD file formats can be broadly classified into two types:

• Native File Formats: Such CAD file formats are intended to be used only with the software it comes with. They cannot be shared with any other software which comes with their own CAD formats.
• Neutral File Formats: These file formats are created to be shared among different software. Thereby it increases interoperability, which is necessary.

 Although there are almost hundreds of file formats out there, the more popular CAD formats are as follows:

STEP: This is the most popular CAD file format of all. It is widely used and highly recommended as most software support STEP files. STEP is the acronym for Standard for the Exchange of Product Data.

IGES: IGES is the acronym for Initial Graphics Exchange Specification. It is an old CAD file format which is vendor-neutral. IGES has fallen out lately since it lacks many features which newer file formats have.

Parasolid: Parasolid was originally developed by ShapeData and is currently owned by Siemens PLM Software.

STL: STL stands for Stereolithography which is the format for 3D information created by 3D systems. STL finds its usage mostly in 3D printers. STL describes only the outer structure or surface geometry of a physical object but doesn’t give out color, texture and other attributes of an object.

VRML: VRML stands for Virtual Reality Modeling Language. Although it gives back more attributes than STL but it can be read by a handful of software.

X3D: X3D is an XML based file format for representing 3D computer graphics.

COLLADA: COLLADA stands for Collaborative Design Activity and is mostly used in gaming and 3D modeling.

DXF: DXF stands for Drawing Exchange Format which is a pure 2D file format native to Autocad.

Use of CAD

Computer-aided design or CAD has pushed the entire engineering process to the next level. One can actually mould or fold, modify or make a new part from scratch, all with the help of CAD modeling software. The many uses of CAD are as follows:

• CAD is used to generate design and layouts, design details and calculations, 3-D models.
• CAD transfers details of information about a product in a format that can be easily interpreted by a skilled professional, which therefore facilitates manufacturing process.
• The editing process in CAD is very fast as compared to manual process.
• CAD helps in speeding up manufacturing process by facilitating accurate simulation, hence reducing time taken to design.
• CAD can be assimilated with CAM (Computer Aided Manufacturing), which eases up product development.