Civil Engineering Reference
In-Depth Information
Let N
1
and N
2
be, respectively, the number of elements in the two surfaces. For even ele-
ment distribution in a grid of N cells, the average number of elements in a cell is given by
k
1
= N
1
/N for surface 1 and k
2
= N
2
/N for surface 2. The number of combinations for the
intersection between elements within a cell is k = k
1
k
2
= N
1
N
2
/N
2
.
If we have to look into all the cells for intersections, the total number of operations is
NN
N
NN
N
N
Total
=
12
2
N
=
12
Assuming N
1
= N
2
= M and N is of the same order of M, i.e. N = λM, then
2
M
Total
==
M
N
N
λ
Thus, N
Total
is of the same order as M, that is, if the elements are evenly distributed or
made into such a distribution by means of advanced spatial partition schemes, the search
for intersection is of linear time complexity. However, other measures could be and have
been taken to speed up the element intersection process in general and in the worst scenario.
i. The min/max comparison will be applied between elements before rigorous intersec-
tion tests are performed.
ii. Intersection chain/loop is recovered by neighbour tracing, and all intersected elements
are flagged and deleted from the list of candidate elements, which reduces in number
as more intersection lines are retrieved. In fact, each intersection line (chain or loop)
can be recovered by just locating one intersection point as the seed starting point.
For the examples of different characteristics, the time taken for searching for neighbours,
construction of a background grid and surface intersection are more or less the same, indi-
cating a linear time complexity of all these processes. Moreover, the algorithm can deal with
generalised surfaces consisting of several disjoint patches of triangles, and the number of
surface components in a surface group will have little influence on the computational cost,
as this information is never used, and individual surface patches need not be extracted or
identified in the intersection process.
The main additional memory requirement is for the construction of the background grid.
An efficient scheme for recording the list of elements for each cell is to make use of a pointer,
as described in Section 2.5.3. Suppose the background grid consists of N cells; then a single
vector
M
is needed to store the information of elements in each cell. For i = 1,N, elements in
cell i = {
M
(j), j = P
i
+ 1, P
i+1
}. Auxiliary pointer P is of size N + 1, and the size of
M
equals the
total number of intersections between elements and cells. For instance, if each element inter-
sects with three cells on average, then the size of
M
equals three times the number of elements.
4.5.6 Mesh generation along intersection lines
The intersection lines have to be incorporated into each of two triangulated surfaces. Based
on Lo (1995), by keeping the features of the intersection lines, the nodes on the intersection
lines are repositioned according to the local element size. Elements cut by the intersection
lines are removed, and the void as a result of element removal is meshed by proper connection
of nodes between the intersection line and the surface boundary (Hartmann 1998). While
this method is simple, due care is needed to maintain the original geometry of the surface
