All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Description

Finite Elements in Analysis and Design 41 (2005) 351 – 370
www.elsevier.com/locate/ﬁnel
Finite element mesh generation over intersecting curved surfaces by tracing of neighbours
S.H. Loa,∗ , W.X. Wangb
a Department of Civil Engineering, the University of Hong Kong, Pokfulam Road, Hong Kong b Intelligence Engineering Lab, Institute of Software, Chinese Academy of Science, Beijing, China
Received 15 January 2004; accepted 29 July 2004
Abstract The use of discrete data to represent engineering s

Tags

Transcript

Finite Elements inAnalysis and Design41 (2005) 351–370
www.elsevier.com/locate/ﬁnel
Finite element mesh generation over intersecting curved surfacesby tracing of neighbours
S.H. Lo
a
,
∗
, W.X. Wang
b
a
Department of Civil Engineering, the University of Hong Kong, Pokfulam Road, Hong Kong
b
Intelligence Engineering Lab, Institute of Software, Chinese Academy of Science, Beijing, China
Received 15 January 2004; accepted 29 July 2004
Abstract
The use of discrete data to represent engineering structures as derivatives from intersecting components requiresalgorithms to perform Boolean operations between groups of triangulated surfaces. In the intersection process,an accurate and efﬁcient method for the determination of intersection lines is a crucial step for large scale andcomplex surface intersections. Given the node numbers at the vertices of the triangles, the neighbour relationshipis ﬁrst established.A background grid is employed to limit the scope of searching for candidate triangles that mayintersect. This will drastically reduce the time of geometrical check for intersections between triangles, making thesurface intersection and mesh generation a quasi-linear process with respect to the number of elements involved.The intersection lines are determined by the robust algorithm based on tracing the neighbours of intersectingtriangles. In the determination of intersection between two triangles, four fundamental cases are identiﬁed andtreated systematically to enhance robustness and reliability.In this paper, the consistent treatment of mesh generation along intersection lines is emphasized. The procedureensures that all mesh generation operations are carried out on the surface concerned without leaving the surfaceso that elements generated will always be on the surface. Five examples on a great variety of surface and meshcharacteristics are given to illustrate the efﬁciency and robustness of the algorithm.
2004 Elsevier B.V.All rights reserved.
Keywords:
Triangular surface intersection; Neighbour tracing; Local meshing
∗
Corresponding author. Tel.: +852-2859-1977; fax: +852-2559-5337.
E-mail address:
hreclsh@hkucc.hku.hk (S.H. Lo).0168-874X/$-see front matter
2004 Elsevier B.V.All rights reserved.doi:10.1016/j.ﬁnel.2004.07.002
352
S.H. Lo, W.X. Wang / Finite Elements in Analysis and Design 41 (2005) 351–370
1. Introduction
There are, in general, two ways to represent a surface for the purpose of visualization and com-putation. One is to use analytical surface patches via functions such as Coon’s patches, B-Splinesor NURBS surfaces. Another is to use discrete data structure such as tessellate facets and triangularfacets[1].For engineering applications, surfaces deﬁned by discrete data are widely adopted, for in-
stance, in the presentation of complex molecules[2–5],engineering design[6],visualization[7]and
computational models for analysis by the ﬁnite element method[4–6,8],etc. There are at least three
ways for the construction of complex surface models of triangulated facets. The ﬁrst approach is toform triangles directly on the surface by well-known mesh generation techniques[9],such as the oc-
tree method[10],the advancing-front method[11–14],the paving method[15,16]and so on. The
second is parametric mapping approach[17–20]which mesh the parametric domain followed by amapping process of the resulting mesh onto the surface. The third approach is to construct modelsby using Boolean operations such as intersection[6,8]and union between groups of surfaces com-posed of triangular facets. A great variety of objects can be easily created by selectively putting to-gether various surface parts derived from surface intersections. This approach has been explored andapplied in the ﬁeld of ﬁnite element mesh generation[21,22],molecules model[6],engineering design
[23,24],etc.The intersection of triangulated surfaces consists of line segments from the intersection of triangles,which can be collected to form chains. These chains will help to deﬁne and will be part of the bound-aries of the surface parts as a result of surface intersection. For large scale and complex surfaces, anaccurate and efﬁcient method for the determination of intersection chains is a crucial step in the in-tersection process. The problem we have at hand is to ﬁnd out all the intersection segments whentwo or more surfaces of triangular facets come together. It would be very time consuming if we tryto detect intersections by examining all the triangular facets on two groups of surfaces a pair of tri-angles at a time. The process can be speeded up by using a bounding box technique[6,24]to ﬁlterout all triangles of the two groups of surfaces that are too far apart and cannot possibly have intersec-tion. Additional data structure can also be set up to further reduce searching for intersections[23,24].Moreover, the intersection line segments obtained, in general, do not follow any particular order. How-ever, in actual engineering applications, these line segments have to be re-ordered to form loops orchains before they could be included as boundaries of surface parts. In this process, undetermined andunresolved cases often arise when many line segments are very close to one other. A wrong connec-tion of line segments may result in forming incorrect chain/loop structures inconsistent with the actualintersection.The algorithm based on the idea of tracing the neighbours of intersecting triangles (TNOIT)[25]is employed in the construction of chains/loops in a progressive and consistent manner. The construc-tion process can be initialized with any intersection segments. As the neighbouring elements of eachtriangular facet are known, the triangular facet to which the intersection line will extend can be eas-ily identiﬁed. This process will be continued until a complete loop is formed or the intersection lineterminates on surface boundaries to form a chain. In this paper, the emphasis is placed on how in-tersection lines from the TNOIT process are incorporated into the intersecting surfaces in a consis-tent manner in such a way that all meshing operations are carried out on the surfaceconcerned.
S.H. Lo, W.X. Wang / Finite Elements in Analysis and Design 41 (2005) 351–370
353
2. The algorithm
Thetypesofsurfacesunderconsiderationaresurfacesalreadydiscretizedintotriangularfacets/elements.The intersection lines between surfaces are represented in terms of straight-line segment, which can bedetermined by considering a pair of triangular facets at a time. Intersection lines are represented in theform of loops and chains.This deﬁnition for surface intersection is broad enough to cover the intersectionof artiﬁcial surfaces that can be discretized into triangular facet and ﬁnite element meshes made up of surfaces of triangular elements.An intersection line will form progressively by connecting line segmentend to end. Two situations can be identiﬁed: (i) the line terminates on the boundary of the intersectionsurfaces to form a open chain and (ii) it goes back to the starting point to form a closed loop.An accurateand efﬁcient process for the determination of intersection chains and loops is of utmost importance to theintersection of discretized surfaces.A trace by neighbours technique is adopted, which greatly enhancesreliability and efﬁciency as neighbours for each triangle are known and connection of segment is doneby means of continuity. The following are the steps for the construction of intersection chains/loops bythe neighbour tracing technique.(1) Find out and record the neighbours of each triangle on the two surfaces.(2) Reduce the population of candidate triangles by means of background grid ﬁlter.(3) Identify an intersection segment from one of the partition cells.(4) Determine the associated chain/loop by continuity tracing neighbouring elements.
2.1. Determination of neighbours
The neighbours of each triangle are a useful topological information of the triangulated surfaces. Thesearching time can be much reduced by making use of the continuity as provided by the neighbourhoodrelationship. The following is a detailed description as how neighbours of the triangles can be identiﬁed.
2.1.1. Some concepts and thoughts
For a given surface composed of triangular facets, generally each triangle in the surface has threeadjacent triangles. If two triangles have a common edge then they are neighbour to each other. InFig. 1, the edge
mn
is a common edge and the triangle
I
is a neighbour of triangle
J
about
mn
. In case noneighbourcanbefoundononeoftheedges(seetriangle
K
inFig.1),therelatededgeisaboundaryedgeof
I J mnK
Fig. 1.A triangulated surface.
354
S.H. Lo, W.X. Wang / Finite Elements in Analysis and Design 41 (2005) 351–370
the surface. For a given triangular mesh, the average number of edges connected to a particular node isquite constant and is independent of the total number of elements present in the system. Based on thisidea, an efﬁcient algorithm can be deﬁned to determine the neighbourhood relationship by consideringelements and edges connected to a node.
2.1.2. The data structure
A simple data structure is adopted to hold the topological information of the triangular facets, and onlythe three vertices of each triangle are needed and stored.As for other connectivity information, it can bederived from this basic data structure.Structure
{
T
k
; //
k
th triangle on the list
v
k
1
; //the ﬁrst vertex of
T
k
v
k
2
; //the second vertex of
T
k
v
k
3
; //the third vertex of
T
k
n
k
1
; //the neighbour about edge
v
k
2
v
k
3
n
k
2
; //the neighbour about edge
v
k
3
v
k
1
n
k
3
; //the neighbour about edge
v
k
1
v
k
2
}
;
2.1.3. The algorithm of ﬁnding out neighbours
Let
N
t
be the number of triangular facet on a given surface
S
and
N
v
be the number of nodal points.Let
S
[
i
] be the set of triangles in
S
connected to node
i
(
1
i
N
v
)
.(a) Initialize
S
[
i
] as null set.(b) For each triangular facet
T
k
, 1
k
N
t
.Add the triangular facet
T
k
to the sets
S
[
v
k
1
]
,
S
[
v
k
2
]
and
S
[
v
k
3
]
respectively. Where
v
k
1
,v
k
2
,v
k
3
are thethree node numbers of triangular facet
T
k
.End(c) For each triangular facet
T
k
from 1 to
N
t
.Find out and record the neighbours of triangle
T
k
.A neighbour of the triangle
T
k
is another triangle present in both sets
S
[
v
k
1
]
and
S
[
v
k
2
]
, in which
v
k
1
and
v
k
2
are vertices of triangle
T
k
.End.This is a linear process as the steps taken for the determination of neighbours for each triangle is moreor less constant.
2.2. Using a background grid to ﬁlter away those triangles that do not intersect
A direct computation of intersection between two groups of surfaces by considering all the triangleson one group against all the triangles on the other group is not an economical process. As intersectionsonly happen in a few parts of the two groups of surfaces, it is necessary to ﬁlter out triangles that do notpossibly have any intersection.A background grid is introduced for this purpose, in which the search forintersection of a triangular facet can be made localized to within a small volume as given by a typical cell

Related Search

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks