Mathematics
This chapter shows which mathematical methods are behind CaveRenderPro – from the survey calculation through the 3D rendering to the loop closure adjustment. You do not need to know any of this in order to use the program; anyone who wants to understand what happens in the background will find the methods here, with their sources.
Survey calculation
The first survey station of a cave is calculated from the cave data – from the latitude, longitude and elevation of the entrance:
All further survey stations follow from the data of the survey shots: length, azimuth and inclination, each relative to the reference point:
The individual views (plan, extended profile, projected profile, perspective) then only make use of the values calculated in this way:
See Calculation & quality → survey calculation.
Perspective rendering
With the help of a series of transformations, the cave coordinates are converted into screen coordinates:
Every transformation is defined in a 4×4 matrix, and these are multiplied into one transformation matrix:
All survey station vectors are multiplied by the transformation matrix. At this point no trigonometric calculations are needed any more:
Finally the perspective is applied by dividing by w, and the points can be shown on the screen:
See Visualization → view types.
Camera flight with cubic splines
Camera positions can be defined for a camera flight. The parameters (X, Y, Z, azimuth, inclination, distance) serve as the knots for the cubic splines:
Neighbouring splines intersect at the common knot and have the same slope and curvature there:
By solving a system of linear equations, the coefficients of the cubic equation can be determined and all values between the knots can be calculated:
Further information: Spline interpolation (Wikipedia)
See Visualization → animation.
Horizontal extension
To calculate the horizontal extension of a cave efficiently, the convex hull is determined with the Jarvis march algorithm (gift wrapping):
Source: Gift wrapping algorithm (Wikipedia)
The longest connection between the corner points of the convex hull gives the extension of the cave:
See Calculation & quality → data reduction.
Drawing curves
Lines drawn with the mouse or a tablet are stored efficiently as polygons and output as well-formed curves:
The lines that are entered are filtered and smoothed with the Ramer-Douglas-Peucker algorithm. This minimizes the amount of data to be stored:
Source: Ramer-Douglas-Peucker algorithm (Wikipedia)
From the polygons, the knots and control points for cubic Bézier curves are calculated. The curves are interpolated and output by the graphical interface:
Source: Bézier interpolation
See Drawings & plans → drawing elements.
Hatchings
In order to get the cave plan as a vector graphic, hatchings have to be depicted by individual hatching lines:
For this, all intersections between the outline lines (blue) and a family of lines (light blue) are calculated:
In this example the red line intersects the outline four times. Each pair of intersections forms one hatching line (in bold).
See Drawings & plans → water and water bodies.
Patterns
In order to get a cave plan as a vector graphic, patterns have to be depicted by symbols:
With the point-in-polygon test (ray casting) the number of intersections between a ray and the outline lines is determined:
If the number of intersections is odd, the symbol is included in the pattern.
Further information: Point in polygon (Wikipedia)
See Drawings & plans → patterns.
Loop closure adjustment
To calculate the loop closure adjustment, an overdetermined system of linear equations has to be solved in order to minimize the squared errors:
One equation is set up per reference point and survey shot (here for the x coordinates):
The coefficients of the equations are transferred into a matrix:
To calculate the new x coordinates, the system of linear equations is solved with a sparse QR decomposition (Givens rotations). Only the survey stations that are actually connected enter into the calculation, which keeps the effort low even for large networks. The further coordinates (y, z, l, p) are calculated in the same way.
Further information: Linear least squares (Wikipedia)
See Calculation & quality → adjustment.
Graph theory
If the cave network is understood as an undirected graph – survey stations as vertices, survey shots as edges – two methods can be applied:
Finding bridges
For the adjustment of the survey shots it determines those survey shots that are part of cycles or that lie on the route between the entrance and further reference points. A survey shot lies in a cycle exactly when it is not a bridge of the graph:
Further information: Cycle (Wikipedia)
Dijkstra's algorithm
For the distance measurement, the shortest path between two survey stations is calculated with Dijkstra's algorithm:
Origin, destination and distance are shown in the status bar – see Getting started → the status bar.
Further information: Dijkstra's algorithm (Wikipedia)
Map tiles
With OpenTopoMap the world map is provided as around 23 billion bitmaps of 256 × 256 pixels each on 18 levels – a so-called MIP map:
Source: Mipmap (Wikipedia)
The zoom level (z) is determined from the size of the area to be displayed:
From the longitude and latitude of the centre of the area, the number of the central map tile (x, y) is calculated. The numbers of the neighbouring tiles can be determined by addition:
See Visualization → map views.
Meridian convergence
The meridian convergence gives the angle between geographic north and the UTM grid:
Graphic from "Wissen wo – Orientierung im Gelände mit Karte und GPS", Springer-Verlag
Maps in the UTM grid are aligned to the central meridians (… 15°W, 9°W, 3°W, 3°E, 9°E, 15°E …). The meridian convergence can be calculated from the longitude and latitude of the cave entrance:
In order to show a cave that was surveyed relative to geographic north in the UTM grid, every survey station has to be rotated by the meridian convergence:
CaveRenderPro does this with Calculate → North → UTM Grid, and the convergence is calculated individually for every entrance.
The calculated value is shown in the Cave Data dialog in the field Meridian. For drawings spanning several caves, the north alignment has to be set to the UTM grid.