Triangulating Data¶
In Gemini Terrain we have four different triangulation methods for data in GMI layers:
The first method is used for constructed and surveyed models without overhangs, typically land-surveyed terrain models. With the second method, we can use a line to 3D triangulate point data. This method is most useful in connection with tunnel measurements where we have measured data along a centerline. The third method is a pure 3D triangulation and can be used for everything from scanned terrain models to constructions.
2D Triangulation (Delaunay)¶
To build the triangle network, the program uses a triangle method called Delaunay triangulation. This is a recognized method that also takes breaklines into account.
This method uses the following input data:
- Point, line, and polygon objects (polygons function as boundary contours)
- Point cloud objects
The function can be found under Tools in the context menu in the map window. It is called 2D Delaunay triangulation.
All lines in the input data are treated as breaklines. For breaklines, we can set an additional criterion. With the option Max. length of a breakline element, the program will split the breaklines according to the entered value.
Without max. length criterion
With max. length criterion
Another criterion we can set in the function is Max. length of triangle line. With this option, the program will remove triangle lines that are longer than the value for this criterion.
Without max. length criterion
With max. length criterion
We can also set a Minimum point distance. If the distance between points is less than this, the program considers the points identical.
Note
We cannot set 0 as the minimum point distance.
A common question is what the program does with arc elements in lines. The program will split these into many small line elements. Maximum arrow height is set to 5 mm.
The result of a triangulation is a triangle network object.
Triangle network object shown in horizontal list field
The illustration shows an example with many points, without breaklines and boundary contour, and the result from the triangulation
In cases where a boundary contour is not included in the selection, the program will create a boundary contour around the triangle network. Note that the boundary contour gets the same ID as the triangle network.
However, we see that the triangulation method has problems with concave shapes. This means that the program creates triangle lines where we have no data. Such cases can be solved in different ways:
- Digitize a boundary contour manually before triangulation
- Delete unwanted triangle lines in the triangle network
- Delete long edges
In the first case, we digitize a boundary contour by snapping to the outermost points. In this case, the program will use the digitized boundary contour during triangulation.
Triangulation within boundary contour
In the second case, we use the function Delete triangles or Delete long edges to delete triangle lines in the triangle network object. With these functions, we can delete triangle lines in the edge zone, that is, starting from the outside and going inward.
We can also define holes in a triangle network.
Hole in triangle network
Holes are solved by merging two polygons: main polygon and polygon that determines the hole (island). If we use the function to merge two polygons, we must ensure that the directions of the polygons are such that the main polygon has positive area and the island polygon has negative area.
Alternatively, we can use the function Create island in polygon in the context menu.
This copies the island polygon into the main polygon (retains the island polygon as an independent polygon), while ensuring that the directions are correct.
Note
We should not use line type Hole contour for the island polygon.
We can also extract the boundary contour from a triangle network. We find the option Extract boundary contour from triangle network in the context menu. If a boundary contour with the same ID as the triangle network exists, you will be asked to either: * Yes: Overwrite this * No: Create a new one * Cancel: Do nothing
Field Registration (Traditional Land Surveying)¶
Land surveying is often used for data capture for terrain models. For the model to be good, we must register data correctly. The most important thing in the registration is to include all break points and breaklines in the terrain. The breaklines in the terrain should be measured in context. The purpose is that triangles should not cross these lines during triangulation.
A* = Break points, B* = Breaklines
In the figure above, we have a model without breaklines and a model with breaklines. These models describe the terrain differently. If we place the models on top of each other, fill and cut will appear due to the terrain being defined differently. It is important to understand this since data capture is crucial for how accurately the model can reproduce the terrain shape.
If we look at the models in 3D we get a good visualization of this.
Without breakline
With breakline
Field Data Registration (Point Clouds)¶
Scanning and photogrammetry provide point clouds with high point density. With this type of data, it is normally not practical to use all points in the triangulation.
For this type of data, we can run an iterative triangulation. We must specify parameters for cell size and maximum deviation between result and original points as in the 3D triangulation described below. We will then automatically have unnecessary points removed in relation to the specified parameters. This will in practice mean fewer points in flat areas.
Triangulated point cloud
Triangulation Along Line¶
Triangulation along line is a method we can use if the input data describes overhangs, for example in tunnels. The method in Gemini Terrain can use the following input data:
- Individual points and line
- Point clouds and line
The line can either be a line in an application layer or a line in an SFI model. We can say that the method in Gemini Terrain is an indirect Delaunay triangulation. Based on the line, the points are unfolded to a mathematical plane, subjected to standard triangulation, and folded back.
The function Triangulate points along line... can be found under Tools in the context menu in the map window.
Simplified, we can say that the triangulation method in Gemini Terrain sees the same as the scanner. We can therefore enter approximate offset values for center point to scanner (profiles). We have negative side offset on the left side when looking forward in the line (increasing profile number).
A* = Profiles center point, B* = Line
Check Calculate normal to vertical curvature for data measured with instrument in plumb. This option requires horizontal and vertical curvature without breaks. The option is not active if we only have a 3D line.
Note
If we have a line with breaks (no rounding in the break points) in the horizontal plane, we will get the following message:
"Horizontal line contains one or more angle breaks! This may cause problems in the operation. Continue?"
The problems are related to the break points in the line. The program performs a mathematical "mapping" of the points before a 2D triangulation is performed. In this operation, the program calculates, among other things, profile number and distance. As we see from the figure below, we get a "blind zone" around the break points where the points will get the same profile number.
This can cause triangle lines to go crisscross in this area. In addition, on the opposite side you will get some points that belong to two different profile numbers and the same effect occurs here.
In tunnels, the use of scanning is dominant, but in some cases we also measure profiles with theodolite. Then problems will arise if the measured points in the profile do not lie approximately on a line. We will probably need to flip some of the triangles that the triangulation method gives directly. For such measurements, we have an option, Clean triangles for profiled measurement, which fixes this automatically. The figures below show how the function works.
Without the option Clean triangles for profiled measurement checked
With the option Clean triangles for profiled measurement checked
3D Triangulation¶
To reconstruct surfaces from point clouds, we can use a pure 3D triangulation method. The function can be found under Tools in the context menu in the map window.
It is important to pre-process the point clouds before we 3D triangulate them. Noise and other unwanted objects should be removed beforehand. Gemini Terrain has both manual methods for editing point clouds and automatic methods for removing noise.
The triangulation itself is normally performed in two or more iterations, but it is fully possible to run only 1 iteration if we only want a quick and rough triangulation.
Triangulation 1st Iteration¶
In the first iteration, we specify a cell size to reduce the number of points in the triangulation. Based on the cell size, the algorithm selects an arbitrary point to represent each cell. What cell size is natural to use? This will depend on the content in the scan. A rule of thumb can be half of two surfaces you want to separate. If you scan both sides of a wall that is 50 cm thick, the cell size should be 0.25 or smaller. If you have many different types of areas, it can be sensible to divide the point cloud to achieve the smallest possible triangle network.
In the first iteration, we have two additional options that can be useful. These are especially relevant for scan data with sharp edges, for example constructions.
The first option is a statistical method where the program picks out probable edge points. Not all types of scans are suitable for using this method. A rock cut is a typical example of scan data where the shape often makes us not recommend this method.
Another option is to include breaklines in the 3D triangulation. If the selection also contains 3D lines, the option for this becomes active in the dialog. The program simulates breaklines by generating densely spaced points along the lines (point distance equal to accuracy). The breaklines can be measured with traditional land surveying or digitized directly in the point cloud. Note that this method must be used with caution. It is easy to add "noise" with this option.
The points from these additional options are included in the point selection before the triangulation in 1st iteration is run.
Triangulation 2nd Iteration¶
In the second step, we set the accuracy we want on the triangle network. We do this by specifying a value for Maximum distance from original points. All points in the original point cloud with greater distance from the triangle network from 1st iteration will be included in the point selection for triangulation.
This process can be repeated multiple times. We do not specify the number of iterations, but enter a stop criterion. The criterion is a %-value for the number of points added compared to the original point set. In addition, the maximum number of iterations is set to 10.
The option to run multiple iterations is relevant when we have point clouds with little noise. Then we can get a model where no points are outside the accuracy requirement. If the model contains noise, many iterations will result in more and more noise points being included in the triangulation.
We can also check to fill holes. This process is run after the last iteration. The criteria for the option are Maximum perimeter and Maximum 3D area. First, the program checks the hole's perimeter against the specified criterion. If the perimeter is smaller, the next criterion is checked. If the 3D area is also smaller than the criterion, the hole is filled. Both criteria must be met for the hole to be filled. Two criteria are included since square and rectangular holes can have approximately the same area, but large differences in perimeter.
Result from Triangulation¶
The user determines where the result should be placed with the option for Result application layer. By default, the program suggests the active layer. Only application layers that are open for editing are listed in the dropdown menu.
In triangulation, properties are assigned to the triangle network:
| Attribute | Code | Description |
|---|---|---|
| S_JOBRESULT | S01 3D-triangulated | Code value indicating how the triangle network was created |
| 3DTri_Cellstart | Cell size for simplification of triangle network | |
| 3DTri_MaxDist | Max. distance from original points (required accuracy) |
Example of the effect some settings have on the result
Cell size: 0.1
Required accuracy: 0.025
With probable edge points
With breaklines
Triangulation of 3D Polygons¶
This triangulation tool also supports vertical polygons, as well as polygons with or without holes. We can also triangulate many polygons in one operation, and the function will merge the triangle networks into one object. If we also select an existing triangle network in the selection, a copy of this will be merged with the new ones.
The function can be found under Tools in the horizontal list window for polygons.
Example of triangulation of 3D polygons
A starting point with six polygons:
A starting point with six polygons
Gives a triangle network with volume:
Triangle network with volume