Whenever a strictly convex quadrangle consisting of two adjacent triangles is encountered, it can
be checked, whether interchanging the diagonals (Fig. 3.1) improves the ASD measure-of-fit
within the quadrangle. The sequence in which the adjustments are carried out matters. In the NIST
implementation, the diagonal interchanges with the biggest improvements are carried out first.

The triangle adjustment option was included in Experiment 2 reported below.

a. Does not retain valley line b. Retains valley line

Figure 3.1. Adjusting triangles crossing valley.

3.4. FILTERING AND SCREENING

TIN methods are also useful for data editing such as removal of “outliers”, that is, data points
whose elevations drastically exceed the elevation of neighboring data points. In order to achieve
such a removal, “filtering” and “screening” methods have been implemented at NIST. In any such
method, the elevation z; of a data point P; = (x; , yi, z)) is compared to the median of the
neighboring data elevations, that is, to the elevations of data points whose footprints are connected
to the footprint p;= (x; , y) of data point P; by an edge in a TIN triangulation. Typically, full
triangulations are used for that purpose. An outlier is then identified as a data point whose
elevation differs from the median of the neighboring elevations by more than a specified tolerance.

A screening method, as exemplified by the NIST routine, T/Nscreen , simply deletes outliers from
the point cloud. The NIST routine, T/Nfi/ter, on the other hand, adjusts the elevation of the outlier
by replacing it with the value of the median. These routines represent instances of what is usually
referred to as a “median filter”.

TINfilter has been used as an option in Experiment 3 to be reported in Chapter 5.

13


59.4 NA 3999745 -60 NIA 5709339 1.7096 0.62
64.4 NA 3740679 -65 NIA 5450296 1.7096 0.62
-69.4 NA 3484990 -70 NIA 5194479 1.7095 0.62
“14.4 NA 3232722 -78 NIA 4941982 1.7093 0.60
Method 2
284.4 8221805 NIA -285 6525009 NIA 1.6968 -0.13,
-289.4 8492938 NIA -290 6796411 NIA 1.6965 -0.15
-294.4 8764071 NIA -295 7067813 NIA 1.6963 -0.16
-299.4 9035204 NIA -300 7339216 NIA 1.6960 -0.18
-304.4 9306337 NIA -305 7610618 NIA 1.6957 -0.19
Box 04 No Box -04
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m’) (%)
(cm’) (cm’) (cm’) (cm’)
Method 1
54.4 NIA 4271003 -55 NIA 5962810 1.6918 -0.42
59.4 N/A 4008232 -60 NIA 5701292 1,6931 -0.35
64.4 N/A 3748770 -65 NIA 5442930 1,6942 -0.28
-69.4 N/A 3492708 -10 NIA 5187886 1,6952 -0.22
“14.4 N/A 3239950 -75 N/A 4936043 1.6961 -0.17
Method 2
284.4 8231735 NIA -285 6499401 NIA 1.7323 1.96
289.4 8503279 NA -290 6770059 NIA 1.7332 2.01
294.4 8774822 NA -295 7040717 NA 1.7341 2.07
-299.4 9046365 NA -300 7311375 NIA 1.7350 2.12
3304.4 9317908 NA -305 7582033 NIA 1.7359 217
Box 05 No Box — 05
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume | Fill Volume: (em) Cut Volume | Fill Volume: (m') (%)
(cm') (cm') (cm') (cm')
Method 1
“54.4 NA 4262402 “58 NIA 5964827 1.7024 0.20
“59.4 NA 3999957 -60 NIA 5702856 1.7029 0.23,
64.4 NA 3740782 -65 NIA 5444052 1.7033 0.25
69.4 NA 3484965 -70 NIA 5188648 1.7037 0.28
“14.4 NA 3232431 -78 NIA 4936540 1.7041 0.30
Method 2
-284.4 8226717 NIA -285 6513255 NIA 1.7135 0.85
-289.4 8497966 NIA -290 6784261 NIA 1.7137 0.87
-294.4 8769215 NIA -295 7055268 NIA 1.7139 0.88
-299.4 9040464 NIA -300 7326275 NIA 1.7142 0.89
-304.4 9311713 NIA -305 7597281 NIA 1.7144 0.91
Box 06 No Box - 06
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m') (%)
(em) (em) (em) (em)
Method 1
“54.4 NA 4260361 -55 NIA 5961267 1.7009 O11
59.4 N/A 3998168 -60 NIA 5699518 1.7013 0.14
64.4 N/A 3739259 -65 NIA 5441135 1.7019 0.17
69.4 N/A 3483790 -10 NIA 5186043 1.7023 0.19
“14.4 N/A 3231740 -75 NIA 4934184 1.7024 0.20
Method 2
284.4 8215414 NIA -285 6505609 NIA 1.7098 0.64
289.4. 8486372 NA -290 6776368 NA 1.7100 0.65,
294.4 8757330 NA -295 7047127 NIA 1.7102 0.66
-299.4 9028289 NA -300 7317886, NA 1.7104 0.67
304.4 9299247 NA -305 7588644 NIA 1.7106 0.68

34



Fill Fill

7-Level / z-Level
¥
a. Method 1
Cut Cut
7-Level 7-Level
b. Method 2

Figure 5.5. Schematic illustration of two methods for determining the volume of a box.

The second method, Method 2, uses floor levels which are located beyond the scanned objects as
viewed from the instrument and indicated by zero fill volumes. The difference of the cut
volumes with and without the box is then considered to be the volume of the box. A schematic
illustration of this second approach is provided in Fig. 5.5b.

All relevant triangles together define the footprint area of the meshed TIN surface. It was
observed that the screen with the box occupies a slightly larger footprint area than the screen
without the box (5.446 m vs. 5.442 m). Since the footprint area represents the silhouette of the
screen as seen by the instrument, this area should be the same before and after the removal of the
box. The discrepancy in the footprint areas may thus suggest that a slight movement of the
screen occurred after the box was removed. Another indication is the existence of a shift in the
sequence of cut volumes in the region between the box and the instrument. In this region, only
the screen contributes to cut volumes, and these cut volumes should therefore agree for identical
floor levels unless the scene was perturbed. Table 5.6 shows corresponding portions of the two
sequences, where z-levels are varied in steps of 0.2 cm between -30 cm and -80 cm. These two
sequences will be used to determine an offset between them.

30


Box — 10 No Box —10
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m') (%)
(cm’) (cm’) (cm’) (cm’)
Method 1
NIA 4261363 -355 N/A 5965047 1.7037 0.28
NIA 3999034 -60 N/A 5703179 1.7041 0.30
N/A 3739911 -65 N/A 5444506 1.7046 0.33
N/A 3484071 -70 N/A 5189127 1.7051 0.36
N/A 3231613 -15 N/A 4936995 1.7054 0.38
Method 2
-284.4 8228488 N/A -285 6514594 NIA 1.7139 0.88
-289.4 8499748 NIA -290 6785626 NIA 17141 0.89
294.4 8771007 N/A -295 7056658 N/A 1.7143 0.90
-299.4 9042266 N/A -300 7327690 NIA 1.7146 0.92
304.4 9313525 N/A -305 7598723 NIA 1.7148 0.93
250% 250%
200% 2.00%
1.50% so 1.50%
= = oS
: 4.00% : St 00%
g Se ne 8 g ee 050%
3 —— = pp
; 000%
4s s 230 = 20 280 2
950%
490%

Floor Level (em)

a. Method 1

Floor Level (em)

b. Method 2

Figure 5.6. Experiment 4 without RMS adjustments: Volume error for full data set and 10
subsets.

39


“full triangulation”

is used as opposed to

“partial triangulation”,
where a selected subset of the data footprints is triangulated.
In general, the TIN surface from a full triangulation “interpolates” the point cloud, that is, it
passes through every one of its points. Exceptions occur if there are different data points with
the same footprints, that is, duplicate points as mentioned at the beginning of this chapter. In that
case, only one of these points can be selected as a vertex of a TIN surface, and it is not possible
to pass a TIN surface through all points of the point cloud.
The TIN surface from a partial triangulation provides approximation only, that is, many points of
the point cloud are not part of the TIN surface. The quality of the approximation can sometimes
be checked by means of visualization. In general, however, there is a need for a numerical

“measure-of-fit,”

that is, a single number “grading” the quality of an approximation. For a point P; = (xj, yi, 2)
in the point cloud, let Z denote the elevation of the approximating TIN surface at the footprint
Pi = (Xi, yi). The

“residual” 1; =z; - 2

then measures the deviation in the z-direction of the data point P; from the TIN surface. The

“Root-Mean-Square (RMS): , Lye
n

“Average-size-deviation (ASD)”: L >
n

and the

n|

of the residuals are the most commonly used measures-of-fit for approximation by an elevated
surface. They will be used in this work, too.

2.4 THE INSERTION METHOD FOR DELAUNAY TINS

The method implemented in this work for constructing TIN surfaces is based on the so-called

“insertion method”


REFERENCES

Cheok, G. S., Lipman, R. R., Witzgall, C., Bernal, J., and Stone, W. C. [2000], “NIST
Construction Automation Program Report No. 4: Non-Intrusive Scanning Technology for
Construction Status Determination,’ N/STIR 6457, National Institute of Standards and
Technology, Gaithersburg, MD, January.

Delaunay, C. [1934], “Sur la sphere vide,” Bull. Acad. Sci. USSR (VID, Classe Sci. Mat., pp.
793-800.

Edelsbrunner, H., D. G. Kirkpatrick, and R. Seidel [1983], “On the Shape of a Set of Points
in the Plane,” JEEE Trans. Inform. Theory, 29, pp. 551-559.

Lawson, C.L. [1977], “Software for C! surface interpolation,” Mathematical Software III, J.R.
Rice (Ed.), Academic Press, New York, pp. 161-194.

Peucker, T. K., R. J. Fowler, J. J. Little, and D. M. Mark [1976], “Digital Representation of
Three Dimensional Surfaces by Triangulated Irregular Networks (TIN)” Technical Report
10, Office of Naval Research, Geography Programs.

Peucker, T. K., R. J. Fowler, J. J. Little, and D. M. Mark [1978], “The Triangulated Irregular
Network.” Proceedings of the Digital Terrain Model Symposium, St. Louis, MO, pp. 516-
532.

Witzgall, C., and Cheok, G. S. [2001], “Registering 3D Point Clouds: An Experimental
Evaluation”, NISTIR 6743, National Institute of Standards and Technology, Gaithersburg,
MD, May.

Witzgall, C., Bernal, J., and Cheok, G. S. [2004], “TIN Techniques for Data Analysis and

Surface Construction”, NISTIR 7078, National Institute of Standards and Technology,
Gaithersburg, MD, January.

45


p' and p",
respectively.
In the first case, only a portion forming a quadrangular prismoid over a quadrangular footprint, say
(D> Pi,» P's P")

contributes to the overall volume. Once this footprint quadrangle has been determined, any of its
two decompositions into triangles f; and ¢/, for instance,

t =(P,>Pi,>P') and t)=(p,,p',p"),
will produce two triangular prismoids with the obvious height adjustments.

In the second case, a reduced prismoid results, whose footprint is a triangular portion ¢, of the full
footprint of the triangle 7;, say

, =(P,> P's P")-

It is obvious that the level volume of a TIN surface depends critically on the definition of the
footprint region as discussed in Section 3.1.

4.2 FLOOR DETERMINATION

In certain applications, the volume of an object situated on a flat floor is to be found. In this case, it
is crucial to determine the elevation of the floor. More generally, there is a need to know when a
varying elevation level first meets or leaves an object of interest.

This task is not straightforward because of data noise. The method developed in [Cheok et al.,
2000, Witzgall and Cheok, 2001] is to vary the elevation level zo in equal increments of, say, 1 cm
or 0.5 cm, determine cut/fill volumes at these elevations, and then form the first and second
differences. As the level plane starts to intersect the portion of the point cloud representing the
object, and similarly if the level plane leaves that region, these events are then signaled by a spike
in the second differences.

17


Box 07 No Box 07
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m’) (%)
(cm’) (cm’) (cm’) (cm’)
Method 1
“54.4 N/A 4271016 “55 NIA 5965571 1.6946 -0.26
“59.4 N/A 4008232 -60 NIA 5703799 1.6956 -0.20
64.4 N/A 3748786 65 NIA 5445413 1.6966 -0.14
-69.4 N/A 3492744 -70 NIA 5190335 1.6976 -0.08
“74.4 N/A 3239954 -15 N/A 4938413 1.6985 -0.03
Method 2
284.4 8227652 NA -285 6500777 NIA 1.7269 1.64
-289.4. 8499110 NA -290 6771523 NIA 1.7276 1.68
294.4 8770568 NA -295 7042268 NIA 1.7283 1.72
-299.4 9042025 NIA -300 7313014 NIA 1.7290 1.77
304.4 9313483 N/A -305 7583759 NIA 1.7297 181
Box 08 No Box — 08
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume | Fill Volume: (em) Cut Volume | Fill Volume: (m') (%)
(cm) (em) (cm) (em)
Method 1
“54.4 N/A 4267298 “55 NIA 5960378 1.6931 -0.35
“59.4 NIA 4004670 -60 NIA 5698832 1.6942 -0.28
64.4 NIA 3745263 65 NIA 5440587 1.6953 0.22
69.4 NIA 3489318 -70 NIA 5185529 1.6962 -0.16
144 NA 3236614 -15 NIA 4933681 1.6971 -0.11
Method 2
-284.4 8228771 NIA -285 6501552 NIA 1.7272 1.66
-289.4 8500168 NIA -290 6772204 NIA 1.7280 1.70
294.4 8771564 NIA -295 7042855 NIA 1.7287 1.75
-299.4 9042961 NIA -300 7313506 NIA 1.7295 1.79
-304.4 9314357 NIA -305 7584157. NIA 1.7302 1.84
Box 09 No Box — 09
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m') (A)
(cm’) (cm’) (cm’) (cm’)
Method 1
“54.4 N/A 4267094 “55 NIA 5960493 1.6934 -0.33
“59.4 N/A 4004413 -60 NIA 5699025 1.6946 -0.26
64.4 N/A 3745021 65 NIA 5440726 1.6957 -0.19
69.4 N/A 3489039 -10 NIA 5185678 1.6966 0.14
74.4 N/A 3236376 -15 N/A 4933842 1.6975 -0.09
Method 2
284.4 8230516 NA -285 6498934 NIA 1.7316 1,92
-289.4 8501946 NA -290 6769537 NIA 1.7324 197
294.4 8773375 NA -295 7040141 NIA 1.7332 2.01
-299.4 9044805 NIA -300 7310745 NIA 1.7341 2.06
304.4 9316235 N/A -305 7581348 NIA. 1.7349 21
Box 10 No Box — 10
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume | Fill Volume: (em) Cut Volume | Fill Volume: (m’) (%)
(cm') (cm') (cm') (cm')
Method 1
“54.4 N/A 4262054 “55 NIA 5966361 1.7043 0.31
“59.4 NA 3999659 ~60 NIA 5704390 1.7047 0.34
64.4 NA 3740525 ~65 NIA 5445632 1.7051 0.36
69.4 NA 3484706 -70 NIA 5190226 1.7055 0.38
144 NA 3232200 -15 NIA 4938112 1.7059 0.41
Method 2
-284.4 8227650 NIA -285 6513124 NIA 1.7145 0.91

35





In addition, RMS and ASD approximation errors are tabulated for each surface pair (Table 5.3b)
except for the surface pair arising from a full triangulation. These errors do not refer to the direct
accuracy as based on deviations of the generated TIN surfaces from the known surface of the
box, but rather to the accuracy based on residual deviations of the data points from the TIN
surface derived from a subset of the data points. Table 5.3b shows that increased accuracy of
approximation, as measured by either RMS or ASD errors, does not necessarily correlate with
increased accuracy of volume calculation, which represents a direct accuracy measurement.

Again, representative values are derived for the five point clouds based on the approximate
vertex to data ratio of 1/3. For each density level, the four volume measurements are used to
derive the range and the midpoint as shown in Table 5.4.

Table 5.4. Experiment 2: Volumes.

Density Volume (m*) Mid-Range Volume (m’)
1 1.697 1,696 1.697 1.696 1,6964 + 0.00700
2 1.671 1.673 | 1.671 1673 1,6721 + 0.00105
3 1.695 1,696 1.696 1.697 1.6959 + 0.00125
4 1.678 1.677 1.676 1.676 1.6768 + 0.00100
5 1.635 1.628 1.626 1.633 1.6303 + 0.00425
5-Full set 1.615 NA NA NA NA

Note that the observed volume ranges do not include the “true” value 1.6990 m*. As mentioned
before, the reasons for this bias are unknown.

5.3. EXPERIMENT 3

This experiment aims at deriving statistical error measures for volume calculation. From each of
the two densest scans — screen with and without box — ten reduced files were created by
randomly selecting 50 % of the data points, respectively. For each of the ten pairs of data sets,
volumes were calculated. This procedure made it possible to determine an expected value and a
standard deviation from the ten volumes obtained. All surfaces were constructed with or without
employing the median filter T/Nfilter in order to smooth the surface (Section 3.4).

28


4, CALCULATING VOLUMES

Given the elevation level zy, consider the spatial region bounded below by zo, bounded above by
an elevated surface, and bounded either laterally by vertical walls along the boundary of the
footprint region or at the intersection of the surface with the elevation level (Fig. 4.1). The volume
of that spatial region is called the

“cut volume” Vou (Zo)
for the elevation level zp. The corresponding

“fill volume” Vu (Zi)
is defined as the volume of the region bounded above by the elevation level zp , and bounded
below by the surface. Lateral cut-off is again vertically either along the boundary of the footprint
region or at the intersection of surface and elevation level. The projections of the cut and fill
volumes ioto the x,y-plane cover precisely the footprint area, and meet only along the projections

of the lines along which the surface intersects the elevation level. The following discussion is
restricted to cut volumes since everything is analogous for fill volumes.

Cut plane

VA

a. Original surface
Cut b. Original surface and cut plane

Fill

c. Cut volume = volume bounded above by original surface and below by cut plane
Fill volume = volume bounded above by cut plane and below by original surface

Figure 4.1 Schematic illustration of cut and fill volumes.


Table 5.1. Sizes of data files after cropping.

Density Without Box With Box
setting Filename No. of points Filename [ No. of points
1 PtC_no_bx_la.dat 15 903 PtC_scr_la.dat 15912
2 PtC_no_bx_2.dat 10221 PtC_scr_2.dat 10 199
3 PtC_no_bx_3.dat 7104 PtC_scr_3.dat 7116
4 PtC_no_bx_4.dat 3.990 PtC_scr_4.dat 3.995
5 PtC_no_bx_5.dat 2548 PtC_scr_Sa.dat 2557

An uncropped footprint triangulation of the point cloud from scanning the box with screen at the
highest density setting is displayed in Fig. 5.1. It displays strips of high density marking the
location of the screen and two vertical walls of the box. Indeed, the signal returns from vertical
walls will generate data footprints that accumulate the “base” of those walls. Because of the higher
angle of incidence, data density is higher on the floor than on top of the box. In Fig. 5.1, — the
effects of beam spread can be observed at the bottom portion of the screen to the left. Such
“phantom points” and “mixed pixels” are a well recognized phenomenon capable of introducing
errors in surface modeling.

To exclude signal returns beyond the location of the screens, all ten point clouds were cropped
along the left screen in Fig. 5.1 as indicated in Fig. 5.2.

Phantom points

Figure 5.1. Triangulation of uncropped data sets.

20


with vertices
P= (Vi 02, 5 P= Vin o2, > P= Oy, Vig oi,

fully above the stipulated elevation level zp. In this case, the triangle 7; by itself, together with
its footprint triangle

t =(Pi+ Pi» Pi,»
with
Bi, =(%, NV, )> Ph =O, 0) Pi =O, NY, )
defines one of those prismoids, where

h,=2,—2) 20, h,=2,-2) 20, h,=z,-—z, 20.

Should a triangle 7; lie completely below the stipulated elevation level zo , then it does not
contribute a prismoid.

There are, however, two intermediate cases as shown in Fig. 4.3. In the first case (Fig. 4.3a), two
vertices of triangle 7; lie strictly above the elevation level zp , whereas the remaining vertex lies
strictly below. In the second case (Fig. 4.3 b), one vertex lies strictly above, another vertex lies
strictly below, with the third one at or below the elevation level Zo .

Figure 4.3. The triangular prismoid on the right has exactly one vertex above the plane.
The one on the left has two.

In both cases, two edges of the triangle 7; intersect the level plane at points

16


Table 5.5. Volume and statistics for Experiment 3.

Volume (m*)
No Filter Filter
File Number w/ RMS wio RMS w/ RMS w/o RMS
adjustment adjustment adjustment adjustment
1 1.691 1.693 1.686 1.677
2 1.678 1.672 1.669 1.664
3 1.686 1.687 1.669 1,669
4 1.665 1,669 1.659 1.659
5 1.674 1.674 1.662 1.653
6 1.681 1.682 1.669 1.667
7 1.673 1.689 1.674 1.676
8 1.685 1.689 1.678 1.680
9 1.664 1.668 1.661 1.658
10 1.678 1.688 1.664 1.663
Average Volume (m*) 1.678 1.681 1.669 1.667
Std. dev. (m’) 0.0086 0.0094 0.0085 0.0089
Volume Error (m’) -0.021 -0.018 -0.030 -0.032
Vol. Error (%) -1.26 -1.05 1.79 -1.91

Note that the directly measured “true” volume of the box differs by more than two standard
deviations from the expected value based on the ten volume measurements in Table 5.5. The
reasons for that apparent bias remain unclear. As in Experiment 2, the “true” volume is
consistently underestimated. Unexpectedly, the underestimation is even larger when the point
cloud has been pre-cleaned using the median filter.

5.4 EXPERIMENT 4

This experiment also uses the same ten random samples of 50 % of the data from the densest
scans as Experiment 3, and calculates volumes for the resulting ten pairs of data sets as well as
for the full data set. However, meshing is now carried out in a different coordinate system,
where the z-axis points in the opposite direction of an estimated general scan direction. The
scan direction estimate was obtained from a graphic display of the footprint triangulation. Note
that increasing the z-level for the volume calculation moves the floor towards the instrument.
Cut volumes are oriented towards the instrument, fill volumes away from it.

Two methods for calculating volumes were employed, based on comparing cut and fill volumes,
respectively. The first method, “Method 1”, determines floor levels that — when applied to the
scans with the box — are close to the box but separate it from the instrument. The volume of the
box is then recovered as the difference of the fill volume without the box and the fill volume
with the box. Fig. 5.5a schematically illustrates this approach in 2D.

29


3. POST-PROCESSING PROCEDURES

In general, once the insertion procedure has been completed, the resulting
“complete triangulation”

requires further editing and adjustment. Such procedures, in particular, the adjustments of vertex
elevations and changes in the triangulation are discussed in this chapter. Note that these two
adjustments apply only to partial triangulations since these adjustments rely on information
provided also by data points which have not been included in the TIN. Filtering and screening
options, also described in the chapter, are generally based on full triangulations.

3.1 RELEVANT TRIANGLES

The complete triangulation covers the entire map, including “no data” areas of the point cloud such
as occlusions or shadows cast by objects in the path of the scan. Among its vertices, the complete
triangulation will also contain artificial points such as map corners. In many applications, triangles
which contain such artificial vertices or which cover no data areas need to be identified, so that a
meaningful

“footprint region”
may be delineated. The approach taken here is to distinguish
“relevant triangles”

among the footprint triangles % of the TIN. All other triangles are then removed by marking
them a irrelevant, leaving the set of relevant triangles as an instance of a footprint region.

In general, triangles connected to map corners are not relevant. Also, triangles which cover
shadows are typically characterized by very long edges or, alternatively, by circumcircles of large
diameters. The following choices are therefore offered for designating relevant triangles or,
equivalently, deleting irrelevant ones:

all triangles are relevant, including those with artificial vertices such as map corners

only triangles meeting map corners and other artificial points are removed

triangles meeting artificial points or with edges longer than a specified length are removed
triangles meeting artificial points or with circumcircles larger than a specified diameter are
removed. This option relates to the concept of “@ -shapes” [Edelsbrunner, Kirkpatrick, and
Seidel 1983].

The relevant triangles determine an area of relevance for a given point cloud. Typically, however,
the boundary of such an area tends to be very irregular. Options for boundary editing are described
in [Witzgall et al. 2004].

11


2. THE MESHING PROCESS

A LADAR device gathers 3D data in the form of a
“point cloud”,

a collection of 3D locations represented in some coordinate system or “frame.” The immediate
output will typically be in instrument-centered “polar” coordinates, given by

“angle, angle, distance” (g , 0,1),

where the angles gy, @ represent instrument settings, and the distance or “range” r_ is measured.
The polar coordinates are commonly converted to “Cartesian” coordinates (x, y, z) centered at
the instrument. The coordinate z of such a point is interpreted as its elevation, and the
projection (x, y) as its location or

“footprint”.
In this report, the data points P; are assumed to be given in such coordinates,
Pi = (is Vis Zi) 5

with footprints p;=(x;, yi) .

In many applications, and often intuitively, the z-coordinate of the Cartesian coordinate system
is considered as the vertical elevation above a horizontal footprint plane. It is important to
realize that the x, y, z-coordinate system need not be chosen in this fashion. For instance, the
footprint plane may be perpendicular to a scanning direction. In that case, the z-coordinate

approximates distance from the instrument.

The purpose of meshing is to represent a point cloud by a surface. The surfaces considered in
this report (e.g., the surface depicted in Fig. 2.2) satisfy the following

Single Elevation Property: Any footprint is the projection of a single surface
point. In other words, no two different surface points have the same footprint.

This condition excludes surfaces with undercuts. A surface with this single elevation property is
commonly referred to as an

“elevated surface”, “parametric surface”, or “2.5 D surface”.

In typical applications, point clouds are either approximated or interpolated by elevated surfaces.
Because of the single elevation property, however, interpolation, that is, the passing of an
elevated surface through all data points P; will not be possible if the point cloud contains what
here will be called


5.2 EXPERIMENT 2

In this experiment all five pairs of scans — each pair taken with different point densities — were
analyzed. TIN surfaces were constructed by adaptively selecting approximately 1/3 of the data
points as vertices. For each density, the volumes associated with these TIN surfaces are
calculated in four different ways, depending on whether elevation adjustment (Section 3.2) and
or triangulation adjustment (Section 3.3) are employed:

No adjustment

RMS elevation adjustment only

Triangulation adjustment

RMS elevation adjustment followed by triangulation adjustment

A volume was also calculated using all points of the point cloud from the lowest density setting.
For such full triangulations, adjustments are not applicable since there are essentially no data
points available for adjustments as essentially all the points are incorporated as vertices into the
respective surfaces. The volume errors are plotted (Fig. 5.4) and tabulated (Table 5.3a). It is not
understood why the experimental volumes consistently underestimate the “true” value. Even
more puzzling is the fact that the errors don’t consistently increase with decreasing data density.

0.0%
0.5%
1.0%
15%

2.0%

No Adjustments No RMS
No Adjustments RMS
‘DAdjustments No RMS
Adjustments RMS

2.5%

3.0%

Volume Error (%)

3.5%

4.0%

4.5%

5.0%

Figure 5.4. Experiment 2: Error plot for volumes for scan sets | to 5.

26


defined by the number of vertices and, consequently, triangles, does not yield the most accurate
result. That result is achieved when the number of vertices is approximately 1/3 of the number of
data points. This may well be a general phenomenon, although much more evidence needs to be
collected.

The RMS elevation adjustment does not appear to improve the results significantly. Since the
adjustment is based mainly on those data points which have not been selected as vertices, its effect
will be progressively diminished as there are fewer such data points.

In subsequent experiments, volume calculations will be based on the vertex ratio of 1/3, although
there is little evidence as whether this parameter choice is optimal. Assuming this vertex ratio, this
translates into specifying 5000 vertices for the TIN surfaces to be used for volume calculation for
this experiment. The volumes reported in Table 5.2 for the corresponding six bin size
specifications range from 1.6974 m°® to 1.7021 m° with mid point 1.69975 m° with RMS
adjustment, and from 1.7029 m° to 1.6986 m° with midpoint 1.70075 m° without RMS adjustment.
The following volume result may thus be associated with Experiment | and compared to the “true”
value of 1.6990 m’ :

1.6997 m? + 0.00235 m°> (with RMS adjustment)
1.7007 m? + 0.00215 m> (without RMS adjustment)

The uncertainties based on the observed range of values for 5000 vertices are thus on the order of
0.14 % and 0.13 % , respectively.

23




ABSTRACT..

CONTENTS

CONTENTS 0.0. eeecceccesecessesecseseesesesecseseesesesessescseessseesescseessseseassesesasseeassesesassesesasseeasecsecaeseeaeaeseeee® v

1.

2.

6.

INTRODUCTION ...0..ccccccescesseseesseseseeseeseeseeseeseeseesssssssessssessecsecseeseesesseeseeesssessssessessesseeseeseeee 1

THE MESHING PROCESS .........ccceeceeseceeseseeeeseseeseseeeeseseensseseasseessseseeassesssasseeaeseseeeeeeeneeeeee
2.1 Triangulated Irregular Networks (TINs)
2.2 Delaunay Triangulations ..........
2.3 Interpolation and Approximation
2.4 The Insertion Method For Delaunay TINs

2.4.1 Vertex Selection for Approximation

2.4.2 Inserting a Vertex

POST-PROCESSING PROCEDURES .
3.1 Relevant Triangles
3.2 Elevation Adjustment
3.3 Triangulation Adjustment.
3.4 Filtering and Screening

CALCULATING VOLUMES
4.1 Decomposition into Triangular Prismoids
4.2 Floor Determination

EXPERIMENTAL VOLUME DETERMINATION
5.1 Experiment 1 ...
5.2 Experiment 2 ...
5.3 Experiment 3...
5.4 Experiment 4...

SUMMARY AND CONCLUSIONS. ...0.0..ceccscesssceseeesescseseesesesssseseescseseseseeseeesneaeseeseeeenes 43

REFERENCES ......scssesssssessessessessesescsseseesecseesessssscsusssssecsecsesseesessessseessussussessecsesseeseesesseesseessesaness 4S


3.2. ELEVATION ADJUSTMENT

Once a partial triangulation has been completed and its footprint region delineated, it may be
desired to improve the RMS measure-of-fit of the approximation of the given point cloud by the
corresponding TIN surface. This is done by adjusting vertex elevations while keeping the
triangulation fixed. This procedure -- which was examined in all experiments reported here -- is
referred to as

“RMS elevation adjustment.”

(An ASD elevation adjustment is under development). It is important to realize that it is the
approximating TIN surface and not the underlying point cloud that is adjusted by changing the
elevations at the vertices of the TIN surface. Any original data point, which was originally selected
as a vertex of the TIN surface, remains a member of the point cloud with its given elevation
unchanged, regardless of subsequent adjustments to the surface. It thus contributes, like any other
data point, to the calculation of the measure-of-fit upon which the approximation is based.

The RMS adjustment amounts to solving a standard “least squares problem” for which many highly
developed algorithms are available. The current implementation relies on the following simple
iterative scheme. Note that a change of elevation at a vertex v of the TIN surface affects the
surface only above the area formed by the triangles adjacent to vertex v. This suggests adjusting
the elevation at this vertex so that the resulting surface change minimizes the RMS above that area.
Carrying out such adjustments in turn for every vertex constitutes an iteration step. For infinitely
many steps, the vertex elevations will converge to limits which define the unique “best” TIN
surface over the given fixed triangulation and with respect to the RMS norm of vertical residuals.
For practical purposes, the process is terminated after (i) a preset number of iterations have been
reached, or (ii) all individual elevation adjustments during an iteration step have remained below a
specified tolerance.

3.3. TRIANGULATION ADJUSTMENT

There are situations in which deviations from the Delaunay principle may be called for. This
occurs, for instance, if — in terrain parlance — an edge of a Delaunay triangle crosses a valley or
tunnels through a ridge (Fig. 3.1). Such situations can be detected if there are sufficiently many
data points in the region of the affected triangles. For such cases, the following

“ASD triangulation adjustment”

procedure for adjusting the triangulation has been developed. (The analogous RMS triangulation
adjustment has not yet been considred.)

12


A previous report [Witzgall and Cheok 2001] provided a first analysis of scans of the same box
taken from four separate locations so as to cover areas occluded by individual scans. In addition
to meshing, those experiments required registration, that is, rigid transformation of separate
coordinate frames to a common frame. Since the experiments in this report aim to assess the
accuracy of meshing techniques, and since registration introduces additional errors, the data
collection for the experiments was designed to avoid the need for registration.

The following Chapter 2 provides an overview of the TIN meshing process. For more details,
the reader is referred to the report by [Witzgall et al., 2004]. Post-processing procedures, such as
elevation and triangulation adjustments are discussed in Chapter 3, and the numerical basis for
the volume calculations is presented in Chapter 4. The experiments are reported in Chapter 5.




NISTIR 7142

Triangular Meshing And Volume Determination

Building and Fire Research Laboratory
Gaithersburg, MD 20899

NIST

United States Department of Commerce
Technology Administration
National Institute of Standards and Technology



Table 5.9. Summary of Experiment 4 results.

Volume (m*)
Data Sub-Set No RMS RMS
Method 1 | Method 2 Method 1 Method 2

1 1,704 1.723 1.704 1,723
2 1,699 1.720 1,698 1,719
3 1.710 1,698 1.709 1.697
4 1.697 1.733 1.696 1,732
5 1,706 1715 1.704 1713
6 1,702 1.709 1.702 1,710
7 1,701 1.729 1,698 1,727
8 1.697 1.728 1.697 1,727
9 1.697 1731 1.697 1,732
10 1,705 1714 1.706 1715
Average (m') 1,702 1.720 1.701 1.719
Std. Dev. (m*) 0.0045 0.011 0.0045, 0.011
Volume Error (m')| 0.003 0.021 0.002 0.020
Vol. Error (%) 017 1.24 0.14 121

4l



to the 3D triangle 7; with the corresponding vertices
(Pus Fn)> Oy Dees Za do O65 3,2 25:
These elevated triangles then meet along common edges and form a surface in space called a
“TIN surface”

(see Fig. 2.2). The triangulation of the footprints qg, = (x, , 3.) determines an entire class of
TIN surfaces, each of which is defined by the choice of the elevations z, at the footprints q,.
The image of “tent poles” of height z, , supporting the surface at the locations q,, is appropriate.
It also suggests the idea of “raising” and “lowering” those “tent poles” so as to best represent the
points in the point cloud — a procedure to be discussed in Section 3.2.

Figure 2.2. A triangulation of data footprints (TIN) and its
corresponding TIN surface.

2.2. DELAUNAY TRIANGULATIONS

There are many ways of triangulating a set of planar points and, consequently, there are many
TIN surfaces through the corresponding sets of 3D vertices. It would therefore be highly
desirable to identify a triangulation concept that, given a set of vertices, defines triangulations
that are essentially unique, and that would come close to reproducing the intuitive triangulation
an analyst would choose. For instance, the occurrence of very long edges and of associated
“skinny” triangles will, in general, be reduced. Obviously, such triangles would distort the
appearance of any corresponding TIN surface. Such a suitable triangulation concept exists. It is
based on the following:


“duplicate points”,

that is, points with identical footprints but different elevations.

21 TRIANGULATED IRREGULAR NETWORKS (TINS)

The computational procedures used in this work are based on a particular kind of
“triangular mesh”,
referred to [Peucker et al., 1976, 1978] as a
“triangulated irregular network” or “TIN”.

Here elevated surfaces are constructed with reference to a

“triangulation”

in the footprint plane (Fig. 2.1).

Figure 2.1 A triangulation in a plane perpendicular to the scan direction.

A triangulation is the covering of a 2D region by triangles which do not overlap, that is, have no
common points other than vertices and along edges where two triangles join. If elevations z,
are specified at the vertices q, = (x,, yy) of triangles of the TIN, then a TIN surface is created
that passes through the corresponding 3D points Q, = (x, , yy, Z,) by elevating each planar
triangle ¢ with vertices

(095 )> Oo. %) ba re)


-294.4 8766045 N/A -295 7068814 NIA 1.6972 -0.10
-299.4 9037178 N/A -300 7340217 NIA 1.6970 -0.12
-304.4 9308311 N/A -305 7611619 N/A 1.6967 -0.14

Box - 04 No Box ~ 04
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) ‘Cut Volume | Fill Volume (cm) Cut Volume Fill Volume (m’y (%)
(cm’) (cm') (cm’) (cm’)

Method 1
-54.4 NIA 4269038 -55 N/A 5961613 1.6926 -0.38
“50.4 NIA 4006325 -60 N/A 5700140 1.6938 -031
64.4 N/A 3746882 -65 N/A 5441815 1.6949 -0.24
-69.4 NIA 3490847 -10 N/A 5186813 1.6960 -0.18
“14.4 N/A 3238087 “15 N/A 4934977 1.6970 -0.12

Method 2
-284.4 8233785 N/A -285 6500719 NIA 1.7331 2.01
-289.4 8505328 N/A -290 6771377 NIA 1.7340 2.06
-294.4 8776871 N/A -295 7042035 NIA 1.7348 211
-299.4 9048414 N/A -300 7312693 NIA 1.7357 2.16
304.4 9319957 N/A -305 7583351 NIA 1.7366 2.21

Box — 05 No Box — 05
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m’) (%)
(cem') (cm') (cm') (cm')

Method 1
-54.4 NIA 4260880 “55 N/A 5965368 1.7045 0.32
“59.4 NIA 3998463 -60 N/A 5703432 1.7050 0.35
64.4 NIA 3739316 ~65 N/A 5444635 1.7053 0.37
-69.4 NIA 3483545 -10 N/A 5189291 1.7087 0.40
“14.4 NIA 3231086 “15 N/A 4937214 1.7061 0.42

Method 2
-284.4 8228148 N/A -285 6512812 NIA 1.7153 0.96
-289.4 8499397 N/A -290 6783818 NIA 1.7156 0.98
-294.4 8770646 N/A -295 7054825 NIA 1.7158 0.99
-299.4 9041894 N/A -300 7325832 NIA 1.7161 1.00
304.4 9313143 N/A -305 7596838 NIA 1.7163 1.02

Box — 06 No Box — 06
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(em) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m‘) (%)
(cm’) (cm') (cm’) (cm’)

Method 1
-54.4 NIA 4259753 -55 N/A 5960251 1.7005 0.09
“50.4 NIA 3997557 -60 N/A 5698502 1.7009 O11
64.4 N/A 3738646 -65 N/A 5440078 1.7014 0.14
-69.4 NIA 3483114 -70 N/A 5184958 1.7018 0.17
“14.4 N/A 3231027 “15 N/A 4933064 1.7020 0.18

Method 2
-284.4 8216055 N/A -285 6506632 NIA 1.7094 0.61
-289.4 8487013 N/A -290 6777390 NIA 1.7096 0.63,
-294.4 8757971 N/A -295 7048149 NIA 1.7098 0.64
-299.4 9028929 N/A -300 7318908 NIA 1.7100 0.65
304.4 9299887 N/A -305 7589667 NIA 1.7102 0.66



4.7060

4.7040

4.7020

4.7000

Volume (m*3)

1.6980

1.6960

4.6940

4.6920

1.7060

1.7040

1.7020

1.7000

Volume (m*3)

1.6980

1.6960

1.6940

1.6920

3K,rms 4K,rms5K,rms—6K,rms_—7K,rms—8K,rms_—9K, rms
Data Points

a. With RMS Adjustment

10K,rms 13K,rms 18K, rms

True Volume

3k 4k 8K 6K 7K 8K 9K
Data Points

b. Without RMS Adjustment

15 bin
20 bin
1025 bin

a i oe ae oe 10130 bin

1240 bin
19100 bin
200 bin

10K 13K 18K

Figure 5.3. Plot of volume vs. number of points in sub-sample and number of bins.
(a)With and (b)Without RMS Adjustment.

25




Table 5.2. Results of Experiment 1.

# Points —%" of Volume (m') % Exror in Volume
Total
InMesh Pts. __1Sbin___20bin__25bin__30bin 40 bin 100 bin __200bin | _1Sbin ___20bin__-25bin__-30bin 40 in__—100bin__200 bin.
With RMS Adjustment With RMS Adjustment
3K, rms 19 17044 1.7043 1.7085 1.7015 1.7035 03178 0311903826 0.1471 0.2689)
4K,rms 25 1.7026 1.7007 —-1.7010-—‘1.6988 1.7013 02119 0.1001 0.1177 0.0118 0.1354
SKjrms 31 1.7021 1.6998 1.7008 1.7002 1.6995 1.6974 0.1825 0.0471 0,1059 0.0706 -——0,0294 0.0942.
OK,rms 37 1.7003 1.6982__1.6982___ 1.6980 1.6980__1.7002 0.0765 0.0471 0.0471 -0.0589 _-0,0589 0.0706
TkKrms 44 16975 1.6976 1.6967 1.6971 1.6966 1.6955 0.0883 0.0824 0.1354 O.11I8 0.1413 -0.2060
8K,rms 50 1.6968 1.6973 1.6961 1.6964 1.6965 1.6961 1.6947 | -0.1295 0.1001 0.1707 0.1530 0.1471 0.1707 0.2531
9OK,rms 56 16974 1.6977 1.6962 1.6974 1.6964 1.6952 1.6957 | -0.0942 0.0765 0.1648 0.0942 0.1530 -0.2237 0.1942
1OK,rms 62 1.6960 1.6964 1.6962 1.6971 1.6962 1.6954 1.6952 | 0.1766 0.1530 0.1648 -O.1118 0.1648 0.2119 -0,2237
I3K,rms_ 81 1.6949 1.6949 1.6945 1.6949 1.6948 1.6950 1.6045 | 0.2413 0.2413 0.2649 0.2413 0.2472 0.2354
IoK,rms 100 1.6946 (1.6947 1.6945 1.6946 1.6946 1.6946 1.6945 | -0.2590 0.2531 0.2649 _——-0.2590_-0.2590__-0.2590__-0.2649
Without RMS Adjustment Without RMS Adjustment
3K 19 17058 | 1.7059 | 1.7046 | 1.7021 1.7019 04002 | 04061 | 03296 | 0.1825 | 0.1707
4K 25 1.7024 1.7022 1.7004 1.7023 1.6999 02001 0.1883 0.0824 0.1942 0.0530
Exe 31 1.7029 1.6986 1.7005 1.7018 1.6993 1.6988 02295 0.0235 0.0883 0.1471 00177-00118.
OK 37 1.7007 1.6973 1.6982 1.6980 1.6976 1.7007 0.1001 0.1001 -0.0471-0.0589 -0.0824 0.1001
1K 4 1.6984 1.6977 1.6973 1.6975 1.6958 1.6970 ~0.0353 0.0765 -0.1001_- 0.0883 -0.1883 | -0.1177
8k 50 1.6964 1.6956 | 1.6954 1.6958 1.6049 | 1.6953 | 1.6930 | -0.1530 | -0.2001 | -02119 | 0.1883 | 0.2413 0.2178 | -0,3002
9K 56 16971 1.6968 1.6961 1.6971 1.6955 | 16948 | 1.6954 | -O.1118 | -0.1295 | -0.1707 | 0.1118 | -0.2060 | -0.2472 | -0.2119
10K 2 1.6953 1.6953 1.6957 1.6967 | 1.6949 | 1.6948 | 1.6950 | 0.2178 | 0.2178 | -0.1942 | -0.1354 | -0.2413 0.2472 0.2354
BK 81 16944 1.6941 1.6941 | 1.6947 1.6935 | 1.6942 | 1.6936 | -0.2707 | 0.2884 | -0.2884 | 0.2531 | 03237 | 0.2825 | -03178
16K 100 1.6941 1.6939 1.6941 1.6944 1.6935 | 1.6939 | 1.6937 | -0.2884 | -0.3002 | -0.2884 | -0.2707 | -0.3237 | -0.3002 | -0.3119

‘a, Rounded to nearest integer

24



1. INTRODUCTION

NIST is investigating the utility and accuracy of LADAR (LAser Detection And Ranging)
scanning devices for surface recovery with particular emphasis on applications by the
construction industry [Cheok et al., 2000]. NIST is also involved in planning a performance
evaluation facility for LADAR instruments and associated data processing methods.

As a step towards accuracy assessment, LADAR scans of a plywood box were collected in a
laboratory environment. The resulting point clouds were meshed using Triangulated Irregular
Network (TIN) techniques as part of the volume calculation. Comparison of that calculated
value with a separately measured volume of the box provides an indication of the accuracy of the
instrument as well as various methods of data analysis. Of particular interest are the sensitivities
of the results to alternate data representations such as choices of the coordinate system and
cropping, as well as parameter settings and procedural options included in the meshing
algorithm. The volume so calculated was then used to gauge the accuracy of the scanning
instrument as well as of the meshing algorithm by comparing it to the separately measured
volume. The NIST prototype routine

“TINvolume”
was used for both meshing and volume calculations.

The experiment set-up included a screen of two perpendicular rectangular plywood sheets,
positioned flush against the faces of the box not visible from instrument position (Fig. 1.1).
Scans were taken from the same instrument position and without changing instrument orientation
of (i) the screen by itself without the box, and (ii) the screen with the box. Those two kinds of
measurements were then used to determine the volume of the box from the difference between
corresponding surfaces.

Screen

\ \

Scan Direction Scan Direction

a. Scan with screen only. b. Scan with box and screen.

Figure 1.1. Experiment Set-up.


4.1 DECOMPOSITION INTO TRIANGULAR PRISMOIDS

The cut volume V..; (zo) is readily computed if the bounding elevated surface is a TIN surface.
For in this case, the enclosed space is the union of triangular prismoids. As shown in Fig. 4.2,

Figure 4.2. A triangular prismoid.

such a “prismoid” is spanned by a usually tilted triangle on top and its footprint at elevation z) on
the bottom. It is bounded at three sides by trapezoids spanned by edges of the top triangle and their
respective footprints below. Let

hy, hz, h3,

denote the lengths of the lateral edges of the trapezoids, that is, the elevations of the top vertices

above zp. Let also
Ajoor = area of the footprint triangle,
Vorism = Volume of the prism.
Then the volume of the prismoid is given by

_h, +h, +h,

Vprism = x Afoot .

The decomposition of the volume into triangular prismoids is readily identified. The straight-
forward case is that of a surface triangle


of 5.0 cm — that serve as reference for their computation. Note that for Method 1, the floor level
of -74.4 cm for the scan with the box corresponds to the floor level of -75.0 cm for the scan
without. These floor levels have been selected so as to be close to the box without intersecting it.
Similarly, for Method 2, the floor level of -284.4 cm corresponds to the floor level of -285 cm
for the other scan of the pair. These floor levels have been chosen for zero fill volumes. For
both methods, the volumes are sensitive to the choice of the reference floor level: the relationship
is not noisy, but exhibits a linear trend. The reason for this is unclear. The results of Method 2
appear to be less accurate. This might be due to the fact that the footprint area of the scan
without the box is slightly smaller than the footprint area with the box: the cut volume of the
scan without the box is thus reduced and, as this value is subtracted to arrive at the volume, the
volume is correspondingly increased.

Table 5.7a. Volume computation with RMS adjustments for the full data set.

Box —unsampled No Box — unsampled

Floor Level 6000 points meshed Floor Level 6000 points meshed Box Vol. Error
(cm) Cut Volume | Fill Volume (cm) Cut Volume | Fill Volume (m’) (%)

(cm') (cm’) (cm’) (cm')

Method 1
54.4 N/A 4280545 “55 NIA 5981733 1.7012 0.13
59.4 N/A 4017048 ~60 NIA 5718737 1.7017 0.16
64.4 N/A 3756907 ~65 NIA 5459025 1.7021 0.18
69.4 N/A 3500145 -70 NIA 5202554 1.7024 0.20
-74.4 N/A 3246716 “15 NIA 4949387 1.7027 0.22

Method 2
284.4 8257297 N/A -285 6548046 NIA 1.7093 0.60
-289.4 8529598 N/A -290 6820171 NIA 1.7094 0.61
-294.4 8801899 NIA -295 7092297 NIA 1.7096 0.62
-299.4 9074201 NIA -300 7364422 NIA 1.7098 0.63

Table 5.7b. Volume computation without RMS adjustments for the full data set.

Box — unsampled No Box ~ unsampled
Floor Level 6000 points meshed Floor Level 6000 points meshed Box Vol. Error
(em) Cut Volume | Fill Volume (cm) Cut Volume | Fill Volume (my (%)
(cm’) (cm’) (cm’) (cm’)
[Method 1
“54.4 NIA 4276612 “55 NIA 5981594 1.7050 0.35
“59.4 NIA 4013304 -60 N/A 5718545 1.7052 037
64.4 NIA 3753258 -65 NIA 5458852 1.7056 0.39
69.4 NA 3496743 -70 N/A 5202352 1.7056 039
“14.4 NIA 3243454 -15 N/A 4949128 1.7057 0.39

32


Method 2
-284.4 8252630 NIA -285 6548311 NIA 1.7043 0.31
-289.4 8524744 N/A -290 6820436 N/A 1.7043 0.31
-294.4 8796857 N/A -295 7092562 N/A 1.7043 0.31
-299.4 9068971 N/A -300 7364687 N/A 1.7043 0.31
-304.4 9341084 N/A -305 7636813 N/A 1.7043 0.31

The analogous computations for the ten subsets of the full scan yield similar results as shown in
Table 5.8a and 5.8b with and without RMS adjustments, respectively. Here, 3 000 points were
adaptively selected as vertices for the meshing. The same offset of 0.6 cm is used to match floor
levels. The error trends for the five reference levels are again almost exactly linear, but with
different slopes and signs, which was unexpected. Another counterintuitive result is that for data
set #3, Method 2 performs considerably better than Method 1, whereas the opposite is true in all
other cases. The results presented in Tables 5.7 and 5.8 are plotted in Fig. 5.6 and Fig. 5.7.

Table 5.8a. Processing samples with RMS adjustments for 10 subsets of data.

Box 01 No Box —01
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume | Fill Volume (em) Cut Volume | Fill Volume (m’) (%)
(cm) (cm) (cm) (cm)
Method 1
“54.4 NA 4261532 “35 NA 5962846 1.7013 0.14
“59.4 NA 3999156 ~60 NA 5701305 1.7021 0.19
64.4 NA 3740032 ~65 NA 5442911 1.7029 0.23
69.4 NA 3484269 -10 NA 5187829 1.7036 0.27
“14.4 NA 3231784 “15 NA 4935985 1.7042 031
Method 2
-284.4 8220953 NA 285 6497933 NA 1.7230 141
-289.4 8492063 NA -290 6768563 NA 1.7235 1.44
294.4 8763173 NIA -295 7039194 NIA 1.7240 147
-299.4 9034283 NIA -300 7309825 NIA 1.7245 1.50
304.4 9305393 NIA 305 7580455 NIA 1.7249 1.53
Box 02 No Box — 02
Floor Level 3000 points meshed Floor Level 3000 points mes! Box Vol. Error
(cm) Cut Volume Fill Volume (em) Cut Volume (m') (%)
(cm') (cm') (cm')
Method 1
“54.4 NIA 4273449 “35 NA 5968685 1.6952 0.22
“59.4 N/A 4010479 -60 NA 5706515 1.6960 0.17
64.4 N/A 3750721 65 NA 5447601 1.6969 0.12
69.4 N/A 3494477 -10 NA 5191963 1.6975 -0.09
“14.4 N/A 3241553 -15 NIA 4939610 1.6981 -0.06
Method 2
“284.4 8240311 NA “285 6521041 NA 1.7193 1.19
-289.4 8512090 NIA -290 6792302 NIA 1.7198 1.22
294.4 8783870 N/A -295 7063564 N/A 1.7203 1.25
“299.4 9055649 NA -300 7334825 NA 1.7208 1.28
-304.4 9327429 N/A -305 7606086 N/A 1.7213 1.32
Box 03 No Box — 03
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume | Fill Volume (em) Cut Volume | Fill Volume\ (m’) (%)
(cm) (em) (cm) (em)
Method 1
“54.4 NA 4262099 | -55 NIA 5971634 | 1.7095 | 0.62

33



Figure 5.2. Cropped data sets displayed as footprint triangulations.

In each experiment, a pair of point clouds arising from corresponding scans with and without the
box, respectively, was meshed as part of the volume calculation. Then the volumes above a
common horizontal, below-the-floor, level were calculated for each of the two resulting TIN
surfaces. The difference between those two separate volume measurements should then account
for the volume of the box.

As described in Chapter 4, volume calculations are geared to specified elevation levels
characterized by specified values of the coordinate z. The cut volumes are, therefore, above the
specified z-level and below the given TIN surface, fill volumes are below the specified z-level and
above the given TIN surface. The volume routine repeatedly prompts for specific z-levels for
which it then provides both cut and fill volumes. In the first three experiments described below,
any two volumes, whose difference is taken as the volume of the box, are cut volumes with respect
to the same z-level, which is chosen sufficiently low to yield a fill volume of zero.

Suppose two elevation levels z; and z;> z, are such that the fill volume at these levels vanishes.
Then the difference between the corresponding cut volumes VeuZ7) > Veu(Z2) is given by the area
of the footprint region of the TIN surface multiplied by the difference in those elevation levels:

VeulZ1) - VeutZ2) = AF CA copings X (Zp — 21)

In the case of TIN surfaces representing the screen by itself and the screen with the box, the foot-
print areas differ slightly. There is therefore a slight dependence of the volume difference on the
choice of a common z-level with zero fill volume. In view of this dependence, the common z-
level was generally chosen as high as possible while the fill volume remained at zero. In one of
two methods used in Experiment 4, a different approach was taken. Here the volume difference

21


ABSTRACT

Parametric studies are reported which investigate the feasibility and accuracy of calculating
volumes from LADAR (laser detection and ranging) scans of artifacts. The Triangulated
Irregular Network (TIN) technique was employed to construct the surfaces on which the volume
calculation was based. The artifact used was a plywood box of known size and volume. Scans
were taken of a tight fitting background screen, with and without the box placed against it. The
volume of the box was then recovered as the difference between respective cut or, alternatively,
fill volumes. A procedure for determining such cut and fill volumes is described. The
representation of point clouds by triangulated surfaces offers several algorithmic options as well
as choices of parameters. The sensitivity and accuracy of volume calculations was examined
for several alternative algorithmic options and parameter settings.

Keywords: approximation, Delaunay, experiments, LADAR, meshing, surface, TIN,
triangulation, volume.

iii


Volume Error (%)

Volume Error (%)

Floor Level (em) Floor Level (em)

a. Method 1 b. Method 2

Figure 5.7. Experiment 4 with RMS adjustments: Volume error for full data set and 10 subsets.

A summary of the results for Experiment 4 is given in Table 5.9. In this table, the mean and the
standard deviation for volume computations were associated with reference level pair -74.4 cm,
75.0 cm is selected as the result of Method 1, and the volume associated with the floor pair
-284.4 cm, 285.0 cm as the result of Method 2. In conjunction with either method, the RMS
adjustment did not result in a significant improvement. In fact, for the full data set, the RMS
adjustment increased the volume error for all floor levels chosen for Method 1, while yielding
improvements for all levels for Method 2. With and without RMS adjustments, the volume error
using Method | remained below the standard deviation. For Method 2, the volume error is about
double the standard deviation. In nine out of ten instances, the values provided by Method 2
overestimate the “true” volume of 1.6990 m’, indicating an unresolved bias error.

40


Box —07 No Box —07
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m*3) (%)
(cm’) (cm’) (cm’) (cm’)
Method 1
“54.4 NIA 4270027 -355 N/A 5967066 1.6970 -0.12
59.4 NIA 4007149 -60 N/A 5705331 1.6982 -0.05
~64.4 N/A 3747619 -65 N/A 5446837 1.6992 0.01
69.4 N/A 3491559 -70 N/A 5191587 1.7000 0.06
“744 N/A 3238763 -15 N/A 4939506 1.7007 0.10
Method 2
-284.4 8228700 N/A -285 6499495 NIA 1.7292 1.78
-289.4 8500158 NIA -290 6770240 NIA 1.7299 1.82
294.4 8771616 N/A -295 7040986 N/A 1.7306 1.86
-299.4 9043074 N/A -300 7311731 NIA 1.7313 1.90
304.4 9314531 N/A -305 7582476 NIA 1.7321 1.95
Box — 08 No Box — 08
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume | Fill Volume (em) Cut Volume Fill Volume (m’) (%)
(cm’) (cm’) (cm’) (cm’)
[Method 1
-54.4 NIA 4266799 “55 N/A 5960564 1,6938 -0.31
“59.4 NIA 4004200 -60 N/A 5699036 1.6948 -0.25
64.4 N/A 3744766 -65 N/A 5440759 1.6960 0.18
69.4 NIA 3488822 -70 N/A 5185617 1.6968 0.13
“74.4 N/A 3236154 -15 N/A 4933635 1.6975 -0.09
Method 2
-284.4 8229390 N/A -285 6501323 NIA 1.7281 171
-289.4 8500787 NIA -290 6771974 NIA 1.7288 1.75
294.4 8772183 NIA -295 7042625 NIA 1.7296 1.80
-299.4 9043580 N/A -300 7313276 N/A 1.7303 1.84
304.4 9314976 N/A -305 7583927 NIA 1.7310 1.89
Box - 09 No Box — 09
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(em) Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m’) (%)
(cm’) (cm') (cm’) (cm’)
[Method 1
-54.4 NIA 4266962 -55 N/A 5960031 1.6931 -0.35
“50.4 NIA 4004213 -60 N/A 5698588 1.6944
64.4 N/A 3744720 -65 N/A 5440279 1.6956 -0.20
69.4 N/A 3488715 -70 N/A 5185259 1.6965 0.14
“74.4 N/A 3236064 -15 N/A 4933476 1.6974 0.09
Method 2
-284.4 8230733 N/A -285 6499629 N/A 17311 1.89
-289.4 8502163 NIA -290 6770233 NIA 1.7319 1.94
294.4 8773593 N/A -295 7040837 N/A 1.7328 1.99
-299.4 9045023 N/A -300 7311440 N/A 1.7336 2.04
304.4 9316452 N/A -305 7582044 NIA 1.7344 2.08



(Lawson [1977]) in that it sequentially inserts data points as vertices, constructing an
intermediate TIN surface each time a new vertex has been added. Thus each additional vertex
triggers the update of a previously constructed TIN surface. The process terminates when a
specified number of vertices has been reached. After terminating the insertion procedure, it will
often be desired to further adjust the resulting TIN surface. Such adjustments are described in
Chapter 3.

As a first step, all data footprints are enclosed in a rectangular
“map” {(x.y)! Xpig SSX pax Vann SYS Pre bs

and after including its four corners, the entire map will be covered by the triangulation. If there
are no data points at those corners, arbitrary “no data values” will be assigned.

After specifying the map, and possibly cropping to it, the insertion method is applied in two
phases. The first phase of the procedure is to construct an

“initial Delaunay triangulation”.
The second phase terminates with the
“specified Delaunay triangulation”,

which now has the specified number of vertices. This triangulation should not be confused with
the full triangulation, which includes all possible vertices. During that second phase, each vertex
to be inserted next is selected according to an optimization criterion taking into account the
current shape of the respective TIN surface.

The simplest way of specifying an initial triangulation is to split the map into two triangles along
one of its diagonals. This triangulation is a Delaunay triangulation, which theoretically could
serve as an initial triangulation for the second phase. In practice, however, a richer triangulation
is recommended for two reasons:

= the NIST method for selecting the vertices to be inserted in phase two is slow if it
starts with a small portion of the triangles

= the quality of the vertex selection depends on how well the intermediate TIN surface
approximates the point cloud

The NIST meshing procedure uses the insertion method also for phase one, starting with splitting
the map into two triangles. Thus the insertion method is used in both phases, the only difference
being that during the second phase the vertices are selected for insertion using an adaptive
optimization criterion (Section 2.4.1) based on the current surface, whereas during the first phase
the insertion sequence is determined independently. In particular, NIST uses the following
procedure for constructing the initial Delaunay triangulation:


Figure 2.4. Adjustment to achieve a Delaunay triangulation.

10




Table 5.6. Cut volume comparison for data with and without box.

w/ Box w/o Box
Floor Level (em) Cut Volume (em*3) Cut Volume (em*3)
-30 70 53
-30.2 80 58
30.4 87 65
-30.6 94 B
105 80
114 89
124 97
138 107
148 116
159 126
172 139
187 151
200 165
214 175
231 189
246 205
° °
° .
. .
“78.2 84954 81639
“18.4 85906 82549
-78.6 86872 83466
18.8 87845 84380
-79 88825 85300
-79.2 89808 86230
-79.4 90818 87162
-79.6 91813 88096
-79.8 92823 89043
-80 93844 89983
Offset (em) Sum of Squares of Differences (cm*)
0.4 9652.648
0.6 3336.779
08 6552.81
10 13630.473

The two sequences of cut volumes shown in Table 5.6 appear to be offset by 0.6 cm. To verify
this, the square roots of the sum of squares of differences was calculated for the four offsets of
0.4 cm, 0.6 cm, 0.8 cm, respectively, and are displayed at the bottom of Table 5.6. They confirm
that the offset of 0.6 cm provides a better match than the other three choices in the sense of least
squares. That offset needs to be taken into account when cut volumes of the screen with and
without box are compared. Thus, in both methods for volume determination as implemented in
this work, floor levels that correspond to each other differ by 0.6 cm.

Tables 5.7a and 5.7b present volume results for the full data set, with and without RMS
adjustment, respectively. 6 000 points — roughly one third of the data points — were adaptively
selected as vertices of the TIN surface. Cut and fill volumes for both the scans with and without
the box are listed. These volumes are given for five pairs of corresponding floor levels — in steps

31


5. EXPERIMENTAL VOLUME DETERMINATION

In this chapter, volume determinations from LADAR scans taken inside an NIST building are
reported. These determinations are based on two series of LADAR scans of a plywood box, taken
from the same instrument location and orientation. The box was built to the following nominal
specifications

0.9144 mx 1.2192 mx 1.5240 m (3 ftx 4 ft x 5 ft),
and those dimensions were verified to within
0.0016 m (1/16 in).

Based on those specifications, a volume of 1.6990 m? is inferred for the box. It will be convenient,
to refer to this value as the “true” volume of the box, realizing full well that this value is still
subject to error. Assuming the above error limit of 0.0016 m (1/16 in ) for the linear dimensions of
the box, a worst case error estimate places the actual volume between the bounds:

1.6990 m? + 0.0059 m’ or 1.6990 (1 + 0.35 %) m°.

The LADAR instrument used for the experiment provided coordinate data at the millimeter level,
that is, three significant digits after the period if the measurement is reported in meters. A
uncertainty of 2 cm or 20 mm is specified by the manufacturer. However, this is the uncertainty for
a single measurement which is not the intended function of a LADAR. A LADAR collects
millions of points from a scene and these points are then used to generate a surface. This is akin to
averaging when the measurements are used, for instance, for the calculations of volumes. As a
result, these calculations are more accurate than might be expected in view of the single
measurement uncertainty. It was also felt that the standard deviations of the volume results need to
be determined without rounding the measurements based on the manufacturer’s specifications. For
these reasons, three digits after the period, when expressed in meters, were retained, and for the
reports of the experiments, the calculated volumes, averages, and standard deviations were reported
up to four digits after the period.

In one series of the experimental scans, a free-standing screen of plywood sheets was placed
against those two faces of the box that remained obscured when scanned from the instrument
location. In a parallel series, the box had been removed so that only the screen remained in its
original position (Fig. 1.1). Five different point density settings were used when generating the two
series of scans.

Using the same window for cropping the ten original data sets — five scans of the screen by itself

and five scans of the screen with the box — the data sets of the following sizes were obtained (Table
5.1).

19


NISTIR 7142

Triangular Meshing And Volume Determination

Christoph Witzgall
Geraldine S. Cheok

July 2004

Building and Fire Research Laboratory
National Institute of Standards and Technology
Gaithersburg, MD 20899

U. S. Department of Commerce
Donald L. Evans, Secretary
Technology Administration

Phillip J. Bond, Under Secretary
Technology Administration

National Institute of Standards and Technology
Ardent L. Bement, Director


6. SUMMARY AND CONCLUSIONS

This report describes experiments conducted to examine the performance and accuracy of TIN
techniques for volume determination. The TIN technique is a technique for meshing 3D point
clouds in order to represent them by surfaces.

Five pairs of LADAR scans were taken at five specified data densities. For each such density
setting, a plywood screen (Fig. 1.1) was scanned with and without a plywood box of known
dimensions. The volume of the box was then derived by several alternate procedures as the
difference of volumes associated with each pair of scans, respectively. Four experimental
procedures for volume determination were examined. Within each such experiment, alternate
options and parameter settings were explored.

Experiment 1 was based on the two scans of highest density only. The key parameter to be
varied was the number of data points specified to be automatically selected as vertices of the TIN
surfaces representing the two point clouds, respectively. This parameter determines the
coarseness or resolution of the resulting TIN surface. Varying the number of bins used for
constructing an initial triangulation provided a means for examining alternate TIN surfaces.
Experiment | produced an unexpected result in the volume calculations: for small numbers of
vertices and, therefore, coarser TIN surfaces, volumes tend to be overestimated. As the number
of vertices increases, the volumes decrease in a regular fashion. The most accurate volumes
were thus found when only about 1/3 of the data points were incorporated as vertices. There is
yet no evidence whether this observation holds true in general. Nevertheless, for the subsequent
experiments, the vertex ratio has been fixed at 1/3.

In Experiment 2, volume calculations for different densities were compared. As expected, the
volumes calculated for the highest density setting were the most accurate, and the ones based on
the lowest density setting the least accurate. Inexplicably, however, the third highest density
setting performed better than the second highest density setting. This phenomenon persisted
after triangulation adjustments were used to improve the RMS and ASD measures-of-fit of the
point clouds by the respective surfaces.

Experiment 3 was designed to estimate standard errors. The “true” box volume of 1.6990 m
was reproduced roughly within three standard deviations with volume errors less than 2 %. In all
cases, the true volume was underestimated, suggesting bias inherent in the experimental set-up.
The underestimation was increased rather than mitigated by the application of a median filter.

Experiment 4 was also designed to estimate standard errors. The objective of Experiment 4 was
to examine the effect of defining TIN surfaces in the direction of the scan rather than with
reference to a horizontal footprint plane — the procedure used in the previous experiments. In
addition, a difference scheme was employed to determine reference elevation levels. Two
methods, Method | and Method 2, were implemented; the first based on determining fill
volumes, the second on cut volumes. Method 1 provided the most exact volume measurements,
with errors below 0.2 % and within the standard deviation of 0.004 m°. Method 2 overestimated
the “true” volume for all but one of the ten data subsets. The reason for this apparent bias is not

43


Table 5.3a. Experiment 2: Volume Errors
Volume Error (%)
Fil #pts in #pts. used % of total No Triangulation Triangulation
Mename orig. file in mesh points Adjustments Adjustments
No RMS RMS No RMS RMS

PtC_scr_la.dat 15912

Ser am am am 0.2
PiC_no_bx_la.dat 15903 5000 / 5000 31 0.11 0.15 0.14 0.20
PtC_scr_2.dat / 10199

Ser - “1.52 - -
PiC_no bx 2.dat 10221 3500 / 3500 34 1.64 1.52 1.64 1.53
PtC_scr_3.dat / « <
PiC_no bx 3.dat 116/7104 2500/2500 35 -0.25 -0.19 -0.16 -0.11
PtC_ser_4.dat /
PiC_no bx 4.dat 3995/3990 1500/1500 38 -1.25 -1.28 -1.37 1.34
PtC_scr_Sa.dat

Scr 2 ~ - - -
PiC_no bx 5.dat 2557/2548 800/800 31 3.79 417 4.29 3.91
PtC_scr_Sadat/ | ,
PiC_no bx 5.dat 2557/2548 | 2557 / 2548 100 4.97 N/A N/A N/A

Table 5.3b. Experiment 2: ASD and RMS Errors

ASD Errors (em) RMS Errors (cm)
Filename No Triangulation Triangulation No Triangulation Triangulation
Adjustments Adjustments Adjustments Adjustments
No RMS RMS No RMS RMS No RMS RMS No RMS RMS
PtC_scr_la.dat 11.882 10.263 11.796 10.226 23.227 16.622 23.186 16.601
PtC_no_bx_la.dat 12.146 10.544 12.041 10.512 24.187 17.319 24.139 17.301
PtC_scr_2.dat 10.891 9.802 10.726 9.742 21.961 16.104 21.844 16.067
PtC_no_bx_2.dat 10.578 9.642 10.374 9.554 21.842 16.118 21.674 16.056
PtC_scr_3.dat 10.645 9.797 10.460 9.713 21.620 16.136 21.473 16.076
PtC_no_bx_3.dat 10.537 9.730 10.201 9.588 21.873 16.143 21.551 16.045
PtC_ser_4.dat 10.194 9.413 9.783 9.289 20.955 15.663 20.528 15.574
PtC_no_bx_4.dat 9.780 9.124 9.358 8.948 20.588 15.307 20.134 15.161
PtC_scr_Sa.dat 12.158 11.002 11.532 10.859 23,503 17.488 22.854 17.384
PtC_no_bx_5.dat 11.297 10.374 10.495 10.171 22.418 16.978 21.334 16.799
PtC_scr_Sa.dat! N/A N/A N/A N/A N/A N/A N/A N/A
PtC_no_bx_5.dat! N/A N/A N/A N/A N/A N/A N/A N/A

' These values are not meaningful when all the data points are used in the mesh.

27



-289.4 8498909 NIA -290 6784156 NIA 1.7148 0.93
294.4 8770168 NIA -295 7055189 NIA 1.7150 0.94
-299.4 9041427 NIA -300 7326221 NIA 1.7152 0.95
304.4 9312687 NIA 305 7597253 N/A 17154 0.97
Table 5.8b. Processing samples without RMS adjustments for 10 subsets of data.
Box—01 No Box—01
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(em) ‘Cut Volume Fill Volume (cm) Cut Volume Fill Volume (m’) (%)
(cm’) (cm') (cm’) (cm’)
[Method 1
NIA 4261449 “55 N/A 5962442 1.7010 0.12
N/A 3999093 -60 N/A 5701024 1.7019 0.17
NIA 3739939 -65 NIA 5442765 1.7028 0.23
NA 3484207 -70 NA 5187792 1.7036 0.27
NA 3231730 “15 NA 4936000 1.7043 031
Method 2
“284.4 8221086 NIA -285 6498465 NIA 1,7226 139
-289.4 8492196 NIA -290 6769096 NIA 1.7231 1.42
294.4 8763306 N/A -295 7039727 NA 1.7236 1.45
-299.4 9034416 N/A -300 7310357 NA 1.7241 147
-304.4 9305526 N/A -305 7580988 N/A 1.7245 1.50
Box — 02 No Box — 02
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume ] Fill Volume (em) Cut Volume | Fill Volume (m’) (%)
(cm’) (cm’) (cm*) (cm*)
[Method 1
“54.4 NIA 4272766 55 NA 5968602 1.6958 “0.19
“59.4 NA 4009853 ~60 NA 5706461 1.6966 0.14
64.4 N/A 3750145 ~65 NA 5447641 1.6975 0.09
-69.4 N/A 3493943 -70 N/A 5192063 1.6981 ~0.05
“144 NIA 3241044 -15 NA 4939805 1.6988 0.01
[Method 2
“284.4 8241248 NA -285 6521232 NIA 1.7200 1.24
-289.4 8513028 N/A -290 6792494 NIA 1.7205 127
-294.4 8784807 N/A -295 7063755 NIA 17211 130
-299.4 9056587 NIA -300 7335016 NIA 1.7216 1.33
304.4 9328366 N/A -305 7606277 NA 1.7221 1.36
Box — 03 No Box — 03
Floor Level 3000 points meshed Floor Level 3000 points meshed Box Vol. Error
(cm) Cut Volume | Fill Volume (em) Cut Volume | Fill Volume (m’) (%)
(cm’) (cm') (cm’) (cm’)
[Method 1
“54.4 NA 4260361 55 NA 5970773 1.7104 0.67
“59.4 N/A 3997963 ~60 NA 5708439 1.7105 0.68
64.4 NIA 3738837 -65 N/A 5449374 1.7105 0.68
69.4 N/A 3483089 -70 N/A 5193539 1.7105 0.67
“144 NIA 3230873 -15 NIA __4941089 1.7102 0.66
[Method 2
“284.4 8223780 NA -285 6526010 NIA 1.6978 -0.07
-289.4 8494913 NIA -290 6797412 NIA 1.6975 -0,09

36



was formed from fill volumes as the z-levels were reduced, moving away from the instrument, as
described below, slightly different z-levels were determined for the two fill volumes.

5.1 EXPERIMENT 1

In this experiment, only the pair of scans of the highest density setting has been considered. As
explained in the previous sections, the meshing process employed here offers various options and
requires choices of several process parameters. The first experiment to be described here aims to
explore the sensitivity of the volume calculations with respect to two parameters,

e bin size for pre-binning (Section 2.4),
¢ number of vertices in the final triangulation,

and to the option of choosing
e RMS elevation adjustments (Section 3.2).
The results of Experiment | are listed in Table 5.2 and graphically displayed in Fig. 5.3.

The bin size chosen for the pre-binning mechanism determines the set of data points entering the
initial triangulation and, therefore, its size and shape. Since a data point is chosen from each non-
empty bin, small bin size or, equivalently, a large number of bins per row, leads to a dense initial
triangulation. In this case, a smaller percentage of the specified number of vertices is chosen
adaptively, that is, based on the respective state of the surface. Conversely, few bins per row result
in a sparse initial triangulation, and a larger portion of the vertices chosen adaptively. In the
following Table 5.2, entries for large numbers of bins — resulting in small individual bin sizes —
cannot be obtained if they exceed the specified number of vertices. This is because selecting a
vertex in each non-empty bin for an initial triangulation may already exceed the specified limit. In
this experiment, the volume computations do not appear very sensitive to variations in bin size and
the resulting perturbations of the TIN triangulation.

The number of data points to be selected as vertices of the TIN surface is a more significant
parameter than the bin size. The reader might be under the impression that not using a full
triangulation would be tantamount to ignoring a part of the scan information. It should be kept in
mind, however, that to restrict the number of vertices of the TIN surface is not to restrict the
number of data points considered. In effect, the number of vertices specified for the TIN surface
defines the resolution of the mesh which represents the point cloud. During the adaptive vertex
selection process every data point plays a role in that selection. The full data information is
therefore already reflected in the shape of any TIN surface which has been based on an adaptively
selected vertex sample. Finally, error statistics are based on the full data sets. For these reasons,
information from data points not included as vertices in the TIN is indeed utilized.

An unexpected trend was observed: as the specified number of vertices increases, the resulting

volume estimates decrease. It is not yet known whether this trend represents a general
phenomenon. The data set also provides an example where the highest surface resolution, as

22


Empty Circle Criterion: No triangulation vertex (x,, yy) lies in the interior of the
circumcircle of any triangle of the triangulation [Delaunay 1934].

Such triangulations (Fig. 2.3) are widely considered standard, employing the terms
“Delaunay triangulation” or “Delaunay TIN”,
and for the corresponding TIN surface, the term
“Delaunay surface”.

In fact, the term “TIN” is often used synonymously with “Delaunay TIN”. A Delaunay
triangulation is, in general, uniquely determined by the empty circle criterion, the exception
being the case in which the circumcircle of one of the triangles contains more than three vertices
on its periphery. In that exceptional case, the vertices on the periphery of such a triangle

determine a convex polygon, which can be subdivided by diagonals in different ways into
triangles, and each of these subdivisions is acceptable within a Delaunay triangulation.

Figure 2.3. Two triangulations of the same set of points. The one on the left is Delaunay.

2.3. INTERPOLATION AND APPROXIMATION

So far no assumption has been made about how the footprint points g, = (x, ) and their
corresponding surface vertices Q, = (x) , yy , Z)) , which describe the TIN surface, are to be
chosen. The typical TIN approach, which is also adopted here, is to assume that — with minor
exceptions —

triangulations are constructed from footprints pi = (xi , yi) of data points
Pi= (Xi, Vi5Zi)-

If all possible data points are included in the triangulation, then the term


understood. The most meaningful comparison is with Experiment 3, in which the same
procedure for estimating standard errors was followed. For Method 1, a definite improvement of
volume accuracy was observed, while the results of Method 2 were comparable.

Several procedures for post-processing the TIN surfaces were explored. Minimizing the RMS
error of the surface representations — the “elevation adjustment” — was used as an option in all
experiments. The option described as “triangulation adjustment” was examined in Experiment 2.
Both of these post-processing adjustments improved the accuracy of representation as gauged by
specified measures-of-fit; however, these improvements only sporadically translated into
improvements of volume accuracy.

The noise level of the scans is estimated to correspond to a standard deviation of roughly 2 cm.
A statistical analysis of what accuracy can be realistically expected given this level of noise is
planned.

To provide an idea as to the kind of accuracies and uncertainties to expect for volume
determinations from LADAR scans, representative volume figures are shown in Table 6.1. They
reflect an arbitrary decision to choose approximately 1/3 of the data points as vertices of TIN
surfaces for which cut/fill volumes are determined, from which a box volume is subsequently
derived. The values and “uncertainties” listed for Experiments | and 2 are simply the values
over which the available measurements were ranging, expressed by their respective midpoints
and maximum deviations. The latter have no statistical meaning. In Experiments 3 and 4,
expected values and standard deviations have been calculated for random subsets of the data.

Table 6.1. Summary of Volumes and Uncertainties.

A _ Volume (m*)
Experiment Description Definition w/ RMS wlo RMS
1 Density 1 (Highest) Mid, range val. + range limit | 1.6997 + 0.0023 1,701 + 0.00215
Density 1 (Highest) Mid. range val. + range limit | _ 1.69640 + 0.0070 NA
Density 2 Mid. range val. + range limit | 1.67215 + 0.00105 NA
2 Density 3 Mid. range val. + range limit | 1.69595 + 0.00125 NA
Density 4 Mid. range val. + range limit | _ 1.67680 + 0.0010 NA
Density 5 (Lowest) Mid. range val. + range limit | _ 1.63035 + 0.00425 NA
3 Density 1, no filter Avg. val. + std. dev. 1.678 + 0.0086 1.681 + 0.0094
4 Density 1, Method 1 Avg. val. + std. dev. 1.701 + 0.0045 1,702 + 0.0045
“True” Volume 1.6990

44



Initial Binning: Divide the map into an almost square grid of bins. In each bin
of the grid select the data point P; whose footprint p; = (xi, yi) lies closest to the
center of the bin and interpolate this subset of data points by a Delaunay surface.

Unless empty, each bin contributes a vertex to the initial Delaunay triangulation, and these
vertices are inserted by column, first, and by row, second. When using the 7/Nvolume routine,
the bin size is set by specifying the number of bins per row. The number of bins per column is
then automatically chosen so as to make the individual bins as square as possible. The choice of
the bin size reflects a balance between two opposite effects: a small bin size leads to a dense
initial triangulation and reduces the role of the adaptive vertex selection during the second phase.
On the other hand, a large bin size leads to a sparse initial triangulation, increases the role of the
second phase, and also tends to increase the overall computational effort. Of course, if a full
triangulation is to be determined, the choice of the initial transformation will, in general, not
matter.

2.4.1 Vertex Selection for Approximation

Phase two of the meshing process applies only to the task of approximation, since for
interpolation all data points are considered, and selection of a sample of the data points as
vertices of a TIN surface is, therefore, moot. Vertex selection is typically connected with partial
triangulation. NIST routines offer two selection criteria. As the next vertex to be inserted, select
the data point whose

¢ vertical distance from the current TIN surface (= size of “residual”) is maximum

e product of the vertical distance with the area of the triangle in which its footprint is
contained is maximum.

The second option leads to triangulations with more homogeneous triangle size and appears
better suited for volume computation. It is, therefore, exclusively used in this work.

2.4.2 Inserting a Vertex

The basic procedure is the insertion of a vertex P; = (x;, yi, zi) into a current TIN surface or,
equivalently, the insertion of a footprint p; = (x; , i) into the underlying triangulation,
proceeding as follows. A triangle % containing p; is determined. Exceptional cases aside, p;
lies in the interior of this triangle #, a new triangulation is then created by connecting p; to the
comers of f , so that there are now three triangles where previously was just triangle %. The
new triangulation will, in general, no longer be Delaunay, and has to be adjusted. Each
adjustment step is an interchange of diagonals in a quadrangle composed of two triangles with a
common edge (Fig. 2.4). For details, consult [Witzgall et al., 2004].