of 20
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.
Finite Elements in Analysis and Design 41 (2005) 351 – 370 www.elsevier.com/locate/finel 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
  Finite Elements inAnalysis and Design41 (2005) 351–370 www.elsevier.com/locate/finel 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 efficient 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 first 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 identified 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 efficiency 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.finel.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 defined 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 finite element method[4–6,8],etc. There are at least three ways for the construction of complex surface models of triangulated facets. The first 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 field of finite 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 define 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 efficient method for the determination of intersection chains is a crucial step in the in-tersection process. The problem we have at hand is to find 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 filterout 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 identified. 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 definition for surface intersection is broad enough to cover the intersectionof artificial surfaces that can be discretized into triangular facet and finite 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 identified: (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 efficient 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 efficiency 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 filter.(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 identified. 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 efficient algorithm can be defined 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 first 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 finding 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 filter 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 filter 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
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