Civil Engineering Reference
In-Depth Information
Q
1
= P
3
Q
2
θ
3
θ
2
θ
1
P
2
P
1
θ = min(θ
1
, θ
2
, θ
3
)
Figure 8.14
Angle
θ
between edge
Q
1
Q
2
and triangle P
1
P
2
P
3
.
Figure 8.15
Background grid.
8.1.5.3 Sharp angle
If either Q
1
or Q
2
is connected to a vertex of triangle P
1
P
2
P
3
, then calculate the angle between
the line segment and the triangle, as shown in Figure 8.14. The angle will be called a
sharp
angle
if it is smaller than, say, 1°.
8.1.5.4 Use of background grid
The geometrical check is the most time-consuming step. Suppose we have a boundary sur-
face consisting of N
B
facets and N
L
edges; the number of tests required n = N
B
N
L
, or order
N
2
. Usually, N
L
≈ 1.5N
B
; hence, in a system of 10
6
facets, n = 10
6
× 1.5 × 10
6
= 1.5 × 10
12
.
Further, suppose that there are 100 operations per test on the average; a machine of 1GIP ≈
250MFLOPs may take roughly 6000 s for checking intersections. This estimate shows that
an order
O
(N
2
) process is just too slow. To reduce the amount of computations in geometric
calculations, a background grid can be used to localise the searching process, as shown in
Figure 8.15, in which the cells intersected by the shaded triangle are shaded in light grey, and
the edges in the vicinity of the shaded triangle crossed by the cells are marked in red. For an
even distribution of elements, the time complexity for the geometrical check process can be
made linear, i.e. order N
B
. Background grids for the partition of nodes have been presented
in Sections 7.3.1 and 7.4.1 for 2D and 3D. Edges and triangles can be assigned to grid cells
according to the cell labels of their vertices.
8.1.6 Examples
The boundary surfaces of a number of engineering objects are analysed in this section. The
input data for these examples are randomly numbered and arbitrarily oriented triangular
