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:

Calculation of the first survey station

All further survey stations follow from the data of the survey shots: length, azimuth and inclination, each relative to the reference point:

Calculation of the further survey stations

The individual views (plan, extended profile, projected profile, perspective) then only make use of the values calculated in this way:

Use of the calculated values in the views

See Calculation & quality → survey calculation.

Perspective rendering

With the help of a series of transformations, the cave coordinates are converted into screen coordinates:

Chain of transformations from cave to screen coordinates

Every transformation is defined in a 4×4 matrix, and these are multiplied into one transformation matrix:

4x4 transformation matrices

All survey station vectors are multiplied by the transformation matrix. At this point no trigonometric calculations are needed any more:

Multiplication of the survey station vectors

Finally the perspective is applied by dividing by w, and the points can be shown on the screen:

Perspective division by w

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:

Camera parameters as knots

Neighbouring splines intersect at the common knot and have the same slope and curvature there:

Conditions at the knots

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:

Coefficients of the cubic equation

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):

Convex hull by Jarvis march

Source: Gift wrapping algorithm (Wikipedia)

The longest connection between the corner points of the convex hull gives the extension of the cave:

Longest connection between the corner points

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:

Drawn line as a polygon

The lines that are entered are filtered and smoothed with the Ramer-Douglas-Peucker algorithm. This minimizes the amount of data to be stored:

Filtering by Ramer-Douglas-Peucker

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:

Knots and control points of the Bézier curves

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:

Hatching as individual lines

For this, all intersections between the outline lines (blue) and a family of lines (light blue) are calculated:

Intersections between the outline and the family of lines

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:

Pattern made of individual symbols

With the point-in-polygon test (ray casting) the number of intersections between a ray and the outline lines is determined:

Ray and intersections with the outline

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:

Overdetermined system of linear equations

One equation is set up per reference point and survey shot (here for the x coordinates):

Equation per reference point and survey shot

The coefficients of the equations are transferred into a matrix:

Coefficient 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:

Cycles in the cave network

Further information: Cycle (Wikipedia)

Dijkstra's algorithm

For the distance measurement, the shortest path between two survey stations is calculated with Dijkstra's algorithm:

Shortest path by Dijkstra

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:

MIP map with 18 zoom levels

Source: Mipmap (Wikipedia)

The zoom level (z) is determined from the size of the area to be displayed:

Calculation of the zoom level

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:

Calculation of the tile numbers

See Visualization → map views.

Meridian convergence

The meridian convergence gives the angle between geographic north and the UTM grid:

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:

Calculation of the meridian convergence

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:

Rotation of the survey stations 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.

See Calculation & quality → north alignment.