Phương pháp chia lưới Delaunay Triangulation
Giới thiệu
Phương pháp Delaunay Triangulation là một kỹ thuật chia lưới không cấu trúc được phát triển từ sớm, dựa trên tiêu chuẩn Delaunay, hay còn gọi là tiêu chuẩn vòng tròn ngoại tiếp Tiêu chuẩn này yêu cầu rằng trong không gian n - chiều, không có điểm nút nào khác nằm trong mặt cầu do bốn đỉnh của một tứ diện xác định Trong không gian hai chiều, hệ tam giác thu được từ tiêu chuẩn Delaunay được gọi là hệ tam giác Delaunay Hệ tam giác này rất phổ biến trong thực hành nhờ vào các đặc điểm tối ưu mà nó mang lại.
• Các tam giác Delaunay là các tam giác xấp xỉ đều;
• Góc lớn nhất của tam giác được cực tiểu hóa;
• Góc nhỏ nhất của tam giác được cực đại hóa.
Hệ tam giác Delaunay với các đặc điểm nhất định sẽ không bị biến dạng hoặc méo mó quá mức Tuy nhiên, tiêu chuẩn Delaunay không cung cấp hướng dẫn cụ thể về cách định nghĩa và kết nối các điểm lưới Một hạn chế đáng chú ý là tiêu chuẩn này có thể không áp dụng trên toàn bộ miền tính toán với các tam giác biên đã xác định Để khắc phục, có hai phương pháp chia lưới tam giác: phương pháp đầu tiên bỏ qua tiêu chuẩn Delaunay gần biên để giữ nguyên các liên kết biên, trong khi phương pháp thứ hai áp dụng tiêu chuẩn Delaunay trên toàn miền và khôi phục biên ban đầu bằng cách loại bỏ các đơn hình ngoài miền tính toán.
Có nhiều thuật toán tạo lưới không cấu trúc dựa trên tiêu chuẩn Delaunay, trong đó một số sử dụng phương pháp chia lưới có cấu trúc để phân bố các điểm nút lưới, sau đó kết nối chúng thành các tam giác thỏa mãn tiêu chuẩn hình học Thuật toán Bowyer-Watson là một trong những thuật toán phổ biến, có khả năng áp dụng cho không gian n-chiều Thuật toán này bắt đầu từ một hệ tam giác của một vài điểm, và tại mỗi bước, các điểm mới được thêm vào hệ tam giác hiện tại, đồng thời tái thiết lập hệ tam giác một cách địa phương Quá trình này giúp cải thiện chất lượng lưới trong khuôn khổ tiêu chuẩn Delaunay, với điểm khác biệt là vị trí các điểm và các liên kết được tính toán đồng thời.
Cơ sở hình học
Một ô lồi n - chiều S là một bao lồi của n + k điểm P 1 , , P n+k (k>1) mà các điểm này không cùng nằm trong một mặt phẳng (n −
1) - chiều Như vậy S bao gồm các điểm x n+k ∈ R n thỏa mãn x = ∑ α i P i , i=1 n+k ∑ α i = 1, 1 α i 0. i=1
Tất cả các điểm P l thuộc tập P i, với i = 1, , n + k, nằm trên biên của S được gọi là các đỉnh của ô lồi S Một mặt m - chiều của ô lồi n - chiều S (với n > m) được xác định là bao lồi của m + 1 đỉnh P l, và bao lồi này không chứa bất kỳ một đỉnh nào khác của S.
< n Ta nói ô S là lồi mạnh nếu nó không có hai mặt bất kỳ cùng nằm trongNếu P là một điểm nằm trong ô lồi mạnh S với các đỉnh P 1, ,
Hình 1.1: Ô lồi (bên trái) và ô tứ diện lồi mạnh (bên phải)
Đơn hình và các ô đơn hình toán học được gọi là ô n-chiều, bao gồm n + 1 điểm x1, , xn+1 mà không nằm trong cùng một mặt phẳng (n-1)-chiều Những ô này là phần tử đơn giản nhất n-chiều, thường được sử dụng để rời rạc hóa miền tính toán, được gọi là các đơn hình Một đơn hình được hình thành từ các điểm x ∈ Rn thỏa mãn x n+.
Đơn hình là một ô lồi mạnh với các đỉnh x1, x2, , xn+1, trong đó một đơn hình ba chiều là tứ diện với các đỉnh x1, x2, x3, x4 Đơn hình m-chiều được xác định qua m + 1 đỉnh, và một điểm x được coi là nằm trong đơn hình nếu αi > 0 với mọi i = 1, , n + 1 Trong thực hành, để rời rạc hóa miền tính toán, chúng ta thường sử dụng các ô lồi m-chiều.
Gọi N i , i = 1,., n, là số mặt đơn hình i - chiều của S, và N 0 là số đỉnh của có các mặt biên là các đơn hình Những ô như vậy được gọilà các ô đơn hình.
• Tính nhất quán của lưới
Bằng một phép rời rạc phù hợp chúng ta thu được một tập hợp các điểm
V R n và một tập các ô lồi mạnh T thỏa mãn các điều kiện sau:
1 Tập hợp các đỉnh của các ô của T trùng với V;
2 Nếu hai ô khác nhau S 1 và S 2 giao nhau, thì miền giao nhau đó là mặt chung của cả hai ô.
Hình 1.2: Các ô giao nhau chấp nhận được (a) và không chấp nhận được (b, c, d)
Tập hợp các ô của một phép rời rạc phù hợp tạo thành một miền kết nối đơn giản n - chiều.
Gọi N i , i > 0 là số lượng các mặt biên i - chiều của miền rời rạc,
N 0 là số đỉnh của biên, theo định lý Euler ta có: n 1
(−1) n−1 biểu thức trên được sử dụng để xác định tính nhất quán của lưới.
Xét một tập hợp các điểm P_i, với i = 1, 2, , N trong một miền xác định n chiều Đối với mỗi điểm P_i, chúng ta xác định miền V(P_i) trong R^n, bao gồm những điểm có khoảng cách đến P_i nhỏ hơn so với khoảng cách đến các điểm P_j khác.
Khoảng cách giữa hai điểm a và b được ký hiệu là d(a, b) Các miền V_i được gọi là khối đa diện Voronoi Những khối đa diện này là giao của các bán không gian của hai Voronoi tương ứng với hai điểm V(P_i) và V(P_j), tạo thành một đa giác (n - 1)-chiều Chúng là các đa diện lồi nhưng không nhất thiết phải bị chặn Mặt biên chung của cặp điểm P_i và P_j được gọi là cặp cấu hình trong lưới Voronoi Trong lưới này, tập hợp n + 1 điểm kề với một điểm khác sẽ tạo thành một mặt chung Kết nối các điểm kề nhau sẽ tạo thành một đơn hình n-chiều, và tâm của bất kỳ đơn hình nào cũng sẽ được xác định.
Mỗi đỉnh của sơ đồ Voronoi tương ứng với một siêu cầu, trong đó siêu cầu này phải rỗng, nghĩa là không có điểm nào nằm bên trong siêu cầu Nếu có điểm nằm trong siêu cầu, điểm đó sẽ gần tâm hơn so với các điểm khác, dẫn đến việc cấu trúc không còn chính xác Do đó, các đơn hình được tạo ra từ lưới tổ ong Dirichlet theo cách này hình thành một lưới tổ ong mới, đáp ứng tiêu chuẩn Delaunay Biên của hệ tam giác Delaunay được xây dựng dựa trên sơ đồ Voronoi chính là các bao lồi của tập hợp các điểm P i.
Phép đặt tam giác Delaunay và lưới tổ ong Dirichlet có thể được xem là đối ngẫu với nhau, trong đó mỗi đỉnh P i của lưới tổ ong tương ứng với một miền Voronoi V(P j ) Điều này thể hiện sự đối ngẫu hình học giữa các đơn hình trong không gian.
Sẽ có (n − 1) phân đoạn tương ứng của lưới tổ ong, với mỗi đỉnh P j thuộc hệ tam giác Hơn nữa, mỗi cạnh trong hệ tam giác này cũng sẽ được xem xét.
Thiết lập hệ tam giác ban đầu
Lưới ban đầu thường thô và có ít nút, với các tam giác lớn trong không gian hai chiều Để tạo ra lưới này, ta chia một hình vuông trong miền tính toán thành hai tam giác, sau đó thêm các điểm bên trong và biên để xây dựng các tam giác liên tiếp cho đến khi đạt yêu cầu Một yêu cầu quan trọng là hệ tam giác ban đầu phải bảo toàn biên, tức là tất cả các cạnh biên phải được bao gồm Để đảm bảo điều này, có thể quy định trước các điểm nút trên biên thông qua thuật toán Bowyer - Watson, nhưng không đảm bảo rằng hệ tam giác Delaunay sẽ bảo toàn biên Để khắc phục, ta có thể lặp lại việc chèn điểm lưới mới tại trung điểm của các cạnh biên thiếu hoặc loại bỏ các điểm có thể phá vỡ liên kết biên.
Thuật toán Bowyer - Watson
Có nhiều thuật toán để phân chia tam giác Delaunay, nhưng thuật toán Bowyer - Watson là phổ biến nhất Thuật toán này thực hiện việc thêm các điểm vào hệ tam giác Delaunay hiện có, thường bắt đầu từ một tam giác lớn bao quanh tất cả các điểm cần thiết Gọi T i là tập hợp các tam giác và B i là tập hợp các đường tròn ngoại tiếp các tam giác đó Khi một điểm mới x i+1 được thêm vào, quá trình cập nhật hệ thống sẽ diễn ra.
Delaunay xảy ra các trường hợp sau: x i+1 ∈ T i ; x i+1 ∈/ T i và x i+1 ∈ B i ; trường hợp cuối cùng là x i+1 ∈/ B i Sau đây ta sẽ xét lần lượt từng trường hợp một.
Trong trường hợp 1, để tìm tập S tròn ngoại i+1, ta cần xác định tập hợp các tam giác thuộc T i T i, có đường tiếp xúc chứa điểm x i+1 Hệ tam giác mới được tạo ra bằng cách loại bỏ các cạnh bên trong của các tam giác trong S và kết nối điểm x i+1 với tất cả các đỉnh của S Ví dụ, với năm điểm x 1, x 2, x 3, x 4, x 5, điểm mới x 6 nằm bên trong một tam giác và cũng nằm trong hai đường tròn ngoại tiếp Trong trường hợp này, S là tứ diện x 2, x 3, x 4, x 5 Ta sẽ xóa cạnh trong x 2 x 4 của S và nối x 6 với bốn đỉnh của S.
Trong trường hợp 2, khi x i+1 không thuộc T i và nằm trong B i chứa điểm x i+1, ta chỉ cần xóa các cạnh của Sgần Tập hợp S bao gồm các tam giác có đường tròn ngoại tiếp lớn nhất với điểm x i+1, và có thể nhìn thấy từ điểm này Hệ tam giác mới sẽ được hình thành bằng cách nối điểm x i+1 với tất cả các đỉnh của các tam giác trong S, cũng như với bất kỳ đỉnh nào của T i mà có thể nhìn thấy từ x i+1 Ví dụ, trong hình vẽ, điểm x i+1 không nằm trong đường tròn ngoại tiếp của tam giác x 1 x 2 x 5, trong đó tập S chỉ có một tam giác, và cạnh x 1 x 2 có thể nhìn thấy.
∈ thấy được từ x 6 , vì vậy cạnh này bị xóa đi và hệ tam giác mới thu được bằng cách nối x 6 với các đỉnh của x 1 , x 2 , x 5 và x 3
Chúng ta không cần loại bỏ bất kỳ cạnh nào của T i, mà chỉ cần xác định các cạnh ngoài của T i có thể nhìn thấy từ điểm x i+1 Hệ tam giác mới sẽ được tạo ra bằng cách nối điểm x i+1 với từng đỉnh của các cạnh ngoài này.
Điểm mới x6 không nằm trong đường tròn ngoại tiếp của bất kỳ tam giác nào trong hình vẽ Các cạnh x1x2 và x2x3 có thể được nhìn thấy từ x6, do đó hình thành hệ tam giác mới kết nối x6 với các đỉnh x1, x2 và x3 Đường tròn ngoại tiếp của các tam giác x1x2x6 và x2x3x6 không chứa ba điểm nút còn lại, đảm bảo tính chất của đường tròn ngoại tiếp được thỏa mãn Khi thêm một điểm mới vào hệ tam giác Delaunay, hệ tam giác mới sẽ được đánh giá dựa trên nhiều tiêu chuẩn hình học và vật lý.
Tiêu chuẩn hình học: Các tam giác phải trơn, nhẵn và có kích thước, hình dạng tương tự nhau.
Tiêu chuẩn vật lý: Mật độ điểm lưới trong miền tính toán phải ít hơn mật độ điểm lưới là nghiệm của phương trình vi phân từng phần.
Các phương pháp chèn điểm mới
Hệ tam giác Delaunay được xây dựng từ việc chọn lựa các điểm biên và sử dụng thuật toán Bowyer-Watson để chèn các điểm mới vào miền tính toán một cách tuần tự, đồng thời tái cấu trúc hệ tam giác với các điểm vừa thêm vào Bài viết này sẽ giới thiệu hai phương pháp khác nhau để thực hiện việc chèn điểm vào miền tính toán.
• Thêm điểm mới vào tâm đường tròn ngoại tiếp tam giác.
Các điểm mới sẽ được thêm vào tại vị trí tâm của các đường tròn ngoại tiếp tam giác, với điều kiện không quá gần các điểm nút đã tồn tại Điểm mới phải cách đều ba đỉnh của tam giác Trước khi thêm điểm mới, cần sắp xếp các tam giác theo chất lượng, bắt đầu từ những tam giác có chất lượng xấu nhất Tam giác được coi là có chất lượng xấu nếu nó gầy, mỏng hoặc có góc tù, và điều này được xác định qua tỉ lệ khía cạnh.
Tỉ lệ khía cạnh A.R của tam giác ABC được xác định bằng công thức R/2r, trong đó R là bán kính đường tròn ngoại tiếp và r là bán kính đường tròn nội tiếp của tam giác Diện tích của tam giác ABC có thể được tính theo công thức cụ thể.
Nếu tam giác là tam giác đều, thì A.R = 1 Khi ba đỉnh của tam giác gần như nằm trên một đường thẳng, giá trị p sẽ gần bằng a, b hoặc c, dẫn đến tỉ lệ khía cạnh lớn hơn Tỉ lệ khía cạnh được sử dụng để đo độ gầy của tam giác Do đó, chúng ta có thể lập danh sách các tam giác có chất lượng kém dựa trên tỉ lệ khía cạnh này.
Thêm vào danh sách các tam giác có diện tích vượt quá 1.5 lần diện tích của tam giác đều, với cạnh lớn nhất là cạnh của tam giác đó Quy trình này sẽ loại bỏ tất cả các tam giác có diện tích lớn.
Hình 1.3: Đường tròn ngoại tiếp và đường tròn nội tiếp của tam giác ABC
Danh sách các tam giác có bán kính đường tròn ngoại tiếp lớn và tỉ lệ khía cạnh cao sẽ được mở rộng Điều này có nghĩa là những tam giác nhỏ với tỉ lệ khía cạnh cao nằm gần biên sẽ được giữ lại.
Tiêu chuẩn đánh giá tỷ lệ khía cạnh cao thường dựa vào kinh nghiệm, với tỷ lệ khía cạnh tiêu chuẩn là 1.5 Tỷ lệ này được áp dụng cho tam giác cân có góc ở đỉnh nằm trong khoảng 24 độ.
Sử dụng ý tưởng trên thuật toán thêm điểm mới vào tâm đường tròn ngoại tiếp tam giác được tiến hành theo các bước sau đây:
(i) Thiết lập hệ tam giác ban đầu sử dụng các điểm biên dữ liệu và thuật toán Bowyer - Watson.
Xếp hạng các tam giác dựa trên chất lượng của chúng, từ đó lập danh sách các tam giác có chất lượng kém, bắt đầu từ tam giác có chất lượng thấp nhất.
(iii) Lấy tam giác đầu tiên trong danh sách và thêm một điểm mới vào vị trí tâm đường tròn ngoại tiếp
(iv) Chia lại sử dụng thuật toán Bowyer - Watson.
(v) Thêm các tam giác mới vào danh sách chất lượng xấu nếu chúng không đủ tốt.
Khi áp dụng thuật toán chèn điểm mới vào tâm đường tròn ngoại tiếp của tam giác đã chọn, cần lưu ý hai trường hợp cần loại bỏ.
• Tâm của tam giác được lựa chọn không nằm bên trong miền tính toán.
• Tâm của tam giác được lựa chọn qua gần biên của miền tính toán.
Một hạn chế của phương pháp này là mật độ lưới của hệ tam giác mới tạo ra trên toàn miền bị ảnh hưởng bởi mật độ lưới dọc theo biên Điều này có thể dẫn đến kích thước của các tam giác ở xa biên, ảnh hưởng đến độ chính xác của nghiệm số.
Để giải quyết vấn đề xác định bán kính của các phương trình vi phân trong miền không đều, chúng ta sử dụng hàm chỉ vị trí f(x) Hàm này cho phép nội suy các giá trị nút trên lưới nền thích hợp, từ đó xác định bán kính của đường tròn ngoại tiếp tại vị trí x Chúng ta định nghĩa tham số α = R/f(X) và thêm điểm mới vào tam giác có tâm và bán kính đường tròn ngoại tiếp lớn nhất Qua một số vòng lặp, tất cả các tam giác trong hệ thống đạt được giá trị α = 1, cho thấy chúng đã đạt được kích thước mong muốn.
• Thêm điểm mới vào đoạn thẳng Voronoi.
Thay vì thêm điểm mới vào tâm đường tròn ngoại tiếp của các tam giác, chúng ta sẽ chèn điểm mới dọc theo một cạnh của đa giác Voronoi Vị trí của điểm mới sẽ được xác định trước, và kích thước của ô lưới cần đạt được sẽ được điều chỉnh qua vài vòng lặp Kỹ thuật này có khả năng tạo ra một hoặc nhiều tam giác mới với kích thước phù hợp, từ đó, sau khi chèn điểm mới, chúng ta sẽ thu được các tam giác xấp xỉ đều trên toàn miền tính toán.
Công thức của thuật toán:
Hệ tam giác Delaunay được phân chia thành tam giác ngoài và tam giác trong, trong đó tam giác ngoài có ít nhất một cạnh biên, còn tam giác trong không có Tam giác trong được chia thành hai loại: loại đã được chấp nhận với bán kính đường tròn ngoại tiếp nhỏ hơn 1.5 f (X), và loại chưa được chấp nhận Thuật toán bắt đầu bằng cách xem xét các tam giác chưa được chấp nhận, có một cạnh chung với tam giác đã được chấp nhận, và chọn tam giác có bán kính đường tròn ngoại tiếp lớn nhất.
Trong hình vẽ trên ta có tam giác ABD là tam giác chưa được chấp nhận với bán kính đường tròn ngoại tiếp là R ABD và tam giác
Tam giác ABC đã được chấp nhận với cạnh chung AB được gọi là cạnh hoạt động Đoạn thẳng EF ngoại tiếp tam giác ABD và ABC, trong đó EF AB = M Voronoi của hai tam giác này là đoạn EF, với E và F lần lượt là tâm đường tròn của ABD Khi đó, tam giác ABD sẽ được thay thế bằng tam giác được chấp nhận ABX Chúng ta sẽ thêm điểm X vào một vị trí nào đó trên đoạn EF sao cho phù hợp.
Kí hiệu f M là giá trị của f (X) tại M Đặt AM = p, MF = q.
Bán kính của đường tròn ngoại tiếp tam giác ABX được tính bằng công thức (p² + q²)/2q, với điều kiện rằng X nằm ngoài đoạn thẳng AB Khi đó, bán kính nhỏ nhất của bất kỳ đường tròn nào đi qua hai điểm A và B sẽ là p, trong đó M là tâm của đường tròn.
+) Nếu f M p, chọn X sao cho bán kính đường tròn ngoại tiếp R ABX của tam giác ABX bằng p Điều này xảy ra khi MX = p và A^XB = 90 o
Hình 1.4: Các tam giác chấp nhận được và không chấp nhận được
+) Nếu f M > p chọn vị trí của X sao cho
R ABX = min( f M , (p 2 + q 2 )/2q) Điều này xảy ra khi X nằm giữa F và vị trí của X ở trường hợp trên khi đó
MX = R ABX + Trong cả hai trường hợp ta đều có: (R ABX ) 2 − p 2
+) Nếu f M < p < 1.5 f M và q > p thì điểm X sẽ được chọn sao cho
A^XB = 90 o , khi đó tam giác AXB là tam giác được chấp nhận Các cạnh
XA, XB sẽ là các cạnh hoạt động tiếp theo.
Hạn chế hình dạng của hệ tam giác Delaunay
Để bảo vệ tính nguyên vẹn của các tam giác biên khi tái kết nối hệ tam giác Delaunay với điểm mới, cần sử dụng phiên bản hạn chế hình dạng của hệ này mà không làm ảnh hưởng đến các liên kết gần biên Khi chèn một điểm mới P, ta có thể xác định tập hợp các tam giác có đường tròn ngoại tiếp chứa điểm P, ký hiệu là Γ(P), được gọi là hố Delaunay Cần lưu ý rằng P là điểm duy nhất nằm trong Γ(P) và nếu A là một đỉnh của ít nhất một tam giác trong Γ(P), thì sẽ có một tam giác S không thuộc Γ(P) có A là một đỉnh.
Điểm A không phải là điểm trong của Γ(P), vì vậy cần chứng minh sự tồn tại của một tam giác ngoại tiếp tương ứng với tam giác S_i Tam giác S_i Γ(P) chỉ tồn tại khi điểm mới được chèn vào nằm bên trong C_i Một đỉnh A được coi là điểm trong của Γ(P) nếu các điểm P thuộc tập hợp S_i, trong khi C_i là đường tròn bên trong ∩C_i Nếu A là một điểm trong của Γ(P), thì miền bên trong sẽ được xác định rõ ràng.
Hình 1.6 minh họa rằng thành phần chính trong của C i là rỗng, do đó, điểm A chỉ có thể nằm trên tất cả các đường tròn của S i Điều này dẫn đến việc ít nhất một tam giác của S i không nằm bên trong Γ(P), cho thấy A không phải là điểm trong của Γ(P).
Trong trường hợp tổng quát, hố Delaunay không chỉ là các kết nối đơn giản Để tái kết nối các tam giác, chúng ta xem xét miền kết nối đơn giản lớn nhất của hố Delaunay chứa điểm P, được gọi là thành phần chủ yếu và ký hiệu là Γ P.
Rõ ràng là tất cả các cạnh biên của Γ P đều có thể nhìn thấy được từ P.
Vì Γ P không rỗng, nên tồn tại ít nhất một tam giác chứa điểm P thuộc Γ P Giả sử tam giác đó là ABC, và tam giác BCD nằm bên trong Γ P, thì điểm P phải nằm trong đường tròn ngoại tiếp tam giác BCD Do đó, các điểm P, B, C, D tạo thành bốn đỉnh của một tứ diện lồi, với tất cả các cạnh của tứ diện này đều có thể nhìn thấy từ các đỉnh.
P Tiếp tục quá trình này đối với tất cả các tam giác của Γ P , rõ ràng là tất cả các cạnh của Γ P đều có thể nhìn thấy từ P (hình 1.6).
• Xây dựng hệ tam giác bị hạn chế
Chúng ta giả định rằng một số tam giác trong hệ tam giác Delaunay là cố định, đặc biệt là các tam giác nằm cạnh biên, được ký hiệu là T¯ Các tam giác thuộc tập hợp T¯ không tham gia vào quá trình xây dựng các hố.
Delaunay đề cập đến việc hình thành hố khi một điểm mới được thêm vào, có thể tạo ra một hoặc nhiều tam giác cố định Kí hiệu Υ(P) đại diện cho phần hố tương ứng, với Υ(P) = Γ(P) T¯ Υ P là miền kết nối đơn giản lớn nhất của Υ(P) có chứa tam giác cố định, và quá trình tái kết nối chỉ diễn ra trong phần hố không chứa P Υ P, thành phần chủ yếu của Υ(P), chỉ tồn tại khi điểm P không nằm trong bất kỳ tam giác nào của T¯ Tất cả các cạnh biên của Υ P đều có thể nhìn thấy từ P, và các đỉnh của Υ P đều được kết nối với P, từ đó xây dựng hệ tam giác hạn chế mà vẫn giữ nguyên các tam giác cố định của T¯.
• Bảo toàn biên của hệ tam giác
Trong quá trình tạo lưới, việc bảo toàn biên của miền tính toàn là yêu cầu quan trọng Hệ tam giác hạn chế giúp giữ lại một tập hợp con các tam giác biên từ các cạnh biên đã tạo thành Các tam giác biên này có thể được hình thành thông qua nhiều quá trình phù hợp khác nhau Do đó, hệ tam giác thu được không chỉ bảo toàn biên mà còn đảm bảo các tam giác bên trong đáp ứng tiêu chuẩn Delaunay.
Weatherill và Hassan đã phát triển một phương pháp mới bằng cách áp dụng tiêu chuẩn Delaunay để tạo ra lưới có biên phù hợp Phương pháp này bao gồm việc khôi phục các cạnh biên trong quá trình chia lưới Delaunay, sau đó loại bỏ tất cả các tam giác nằm ngoài miền tính toán.
Phép chia lưới Delaunay triangulation trong không gian
Trong không gian ba chiều, lưới Delaunay không cấu trúc được hình thành bằng cách kết nối các đỉnh của các khối đa diện Voronoi có mặt chung Mỗi đỉnh của khối đa diện Voronoi đại diện cho tâm của khối cầu đi qua bốn đỉnh tạo thành tứ diện, với điều kiện không có điểm nào khác nằm bên trong khối cầu đó Thuật toán phổ biến để chia lưới Delaunay trong không gian ba chiều là thuật toán Bowyer, dựa trên quá trình tuần tự.
Thuật toán Bowyer-Watson bắt đầu bằng cách tạo một hệ tam giác Delaunay từ một siêu tứ diện hoặc siêu lập phương, sau đó phân chia thành năm tứ diện chứa tất cả các điểm Khi các điểm mới xuất hiện trong quá trình hình thành lưới, chúng sẽ được thêm vào lần lượt Sau khi mỗi điểm được đưa vào, thuật toán sẽ áp dụng để tạo ra các hố Delaunay, từ đó tái kết nối và thu được hệ tam giác Delaunay mới Các bước của thuật toán tương tự như trong không gian hai chiều, giúp duy trì tính chất của hệ tam giác Delaunay.
Thuật toán hiện tại không bảo toàn bề mặt biên của miền tính toán, do đó cần đưa ra các hạn chế cho hệ tam giác Delaunay Trong không gian ba chiều, các hạn chế này tương tự như trong không gian hai chiều Cách tiếp cận thứ nhất giữ nguyên các tứ diện có mặt hợp thành bề mặt biên trong quá trình tái kết nối, với các tứ diện biên được thiết lập từ hệ tam giác Delaunay ban đầu Sau đó, điểm mới được chèn vào, xác định hố hình sao chứa điểm đó và tái kết nối các cạnh, đảm bảo lưới thu được bảo toàn biên và các tam giác nhỏ bên trong đáp ứng tiêu chuẩn Delaunay Cách tiếp cận thứ hai bắt đầu bằng việc xác định các điểm nút trên biên và kết nối chúng để tạo ra bề mặt của hệ tam giác.
Để khôi phục lại biên, trước tiên, chúng ta xây dựng hệ tam giác Delaunay mới bằng cách chèn các điểm bên trong và áp dụng thuật toán Bowyer-Watson Sau đó, các tứ diện cắt bề mặt biên sẽ được biến đổi Nếu một mặt biên không có trong phép đặt tam giác Delaunay mới, điều này xảy ra do các cạnh và mặt của tứ diện cắt mặt biên Để khôi phục một mặt, cần khôi phục ba cạnh của nó trước Quá trình này bắt đầu bằng việc tìm các tứ diện giao với các cạnh của mặt, sau đó thiết lập tiêu chuẩn giao nhau để thực hiện các phép biến đổi trực tiếp Các tứ diện sẽ được biến đổi một cách địa phương thành các tứ diện mới, đảm bảo sự hiện diện của các cạnh cần thiết Tương tự, quá trình khôi phục các mặt biên cũng được thực hiện.
Phương pháp tịnh tiến biên (Advancing Front)
Giới thiệu
Phương pháp Delaunay Triangulation, mặc dù phổ biến, không luôn đảm bảo tạo ra lưới thỏa mãn trong một số bài toán như xác định dòng chảy nhớt, nơi yêu cầu các phần tử tam giác có bán kính tỉ lệ cao ở vùng lớp biên Việc sử dụng phương pháp này có thể dẫn đến tình trạng các nút biên trở thành đỉnh của hệ tam giác cuối cùng, gây ra vấn đề về tính nguyên vẹn của biên Để khắc phục, phương pháp tịnh tiến biên (AFT) do George giới thiệu vào năm 1971 được áp dụng, cho phép tạo ra lưới không cấu trúc mà vẫn bảo toàn tính nguyên vẹn của biên Phương pháp này phân chia các đường biên thành các đoạn thẳng, tạo thành một 'front' di chuyển vào trong miền tính toán khi các điểm nút và cạnh mới được hình thành, từ đó tạo ra các phần tử tam giác Quá trình này tiếp tục cho đến khi không còn cạnh nào trong front, đảm bảo rằng việc lựa chọn các điểm nút trên đường cong biên phải phù hợp với kích thước ô lưới yêu cầu.
Điều khiển lưới
Khi áp dụng phương pháp chia lưới, kích thước và hình dạng của ô lưới là yếu tố quan trọng cần xem xét Đối với phương pháp tịnh tiến biên trong không gian 2 chiều, để tạo ra các ô lưới đạt yêu cầu, chúng ta cần thực hiện hai bước liên tiếp.
• Định nghĩa các đặc điểm yêu cầu của ô lưới;
Để tạo ra một lưới nền ban đầu với các đặc điểm yêu cầu, cần xác định sự phân bố không gian của các tham số lưới phù hợp Kích thước, hình dạng và hướng của ô lưới tam giác được mô tả bởi ba tham số độc lập.
Hình 1.7: Các tham số mô tả của phần tử tam giác
Tham số định hướng Φ liên quan đến hai véctơ trực giao ˙s và ˙n, trong đó để định nghĩa một ô lưới, cần nhập bốn tham số đầu vào (δ, s, n x, n y), với n x, n y là hình chiếu vuông góc của ˙n trên các trục ox, oy Các giá trị này cần được xác định tại mỗi nút của lưới nền, thường do người sử dụng tạo ra và có thể không mịn, đặc biệt cho các miền tính toán phức tạp Lưới nền có thể chỉ gồm một hoặc hai phần tử tam giác nhưng phải đảm bảo sự biến đổi tuyến tính của các tham số trong miền tính toán Nếu không có lưới nền cung cấp, một lưới mặc định sẽ được tạo ra dựa trên quy tắc thực nghiệm với hai phần tử tam giác và mật độ lưới đồng nhất Tham số kích thước δ được xác định bằng 5% chiều dài đường chéo của lưới nền, và lưới đầu tiên sẽ là cơ sở cho các lưới tiếp theo Để cải thiện phương pháp cho miền có biên phức tạp, cần chỉ rõ tham số lưới ở các khu vực biên thông qua sự phân bố của các nguồn, ví dụ như ở đầu và đuôi của máy bay Phân bố kích thước không gian của ô lưới được xác định dựa trên khoảng cách từ một điểm đến nguồn, và là đẳng hướng nếu chỉ phụ thuộc vào khoảng cách x từ bất kỳ hướng nào tới nguồn.
Hàm nguồn đẳng hướng tại điểm nguồn S được xác định như sau:
Để điều khiển sự biến đổi kích thước tam giác δ tại S, các tham số δ, D và x c được đưa vào công thức Σ D x − − xxc c Σ ln 2 x0 c < x ≥ x 0, l 2 > 0 nhưng l 3 < 0.
Nếu cho một điểm P nằm ngoài tam giác 123, thì sẽ tồn tại ít nhất một điểm (x P, y P) mà tại đó, chúng ta sẽ xác định được một tam giác có diện tích âm.
Khi tam giác cuối cùng được tạo ra trong lưới nền, chúng ta sẽ tính toán các diện tích tọa độ của điểm P tương ứng với tam giác đó Nếu phát hiện diện tích tọa độ âm, quá trình tìm kiếm sẽ chuyển sang tam giác tiếp theo Ví dụ, trong hình (1.10), do l3 < 0, chúng ta sẽ kiểm tra tam giác đối diện với đỉnh 3, có chung cạnh 12 Quá trình này sẽ tiếp tục cho đến khi tìm được tam giác mà tất cả các diện tích tọa độ đều dương.
Thuật toán AFT
Thuật toán AFT nổi bật với việc sinh ra đồng thời các nút lưới và ô lưới tam giác Mỗi tam giác mới được tạo ra sẽ được kiểm tra một cách địa phương ngay lập tức Dưới đây là các bước thực hiện của thuật toán AFT.
1 Thiết lập một ’front’ lưới ban đầu và một tập hợp các đoạn thẳng định hướng liên kết các điểm đã được chọn trên biên Nội suy các tham số lưới cho tất cả các nút trên front Tất cả các nút trên front hiện tại được gọi là các nút hoạt động.
2 Lựa chọn mặt ngắn nhất của front với chiều dài l Giá trị của δ là trung bình các giá trị nội suy của δ tương ứng với hai nút.
3 Xác định vị trí của điểm lý tưởng K ideal trên đoạn thẳng trực giao của mặt này sao cho một tam giác đều được tạo thành với
4 Dựng đường tròn tâm K ideal , bán kính r được lấy theo kinh nghiệm r 0.8∗ δ ′ , trong đó
Công thức 2.0 ∗ l δ > 2.0 ∗ l và δ giúp xác định giá trị địa phương, ngăn chặn việc hình thành các tam giác méo mó và đảm bảo tính tương thích hình học.
5 Tìm các nút hoạt động nằm bên trong đường tròn này và tính khoảng cách của các nút tới K ideal Điểm nào gần K ideal nhất được chọn là đỉnh thứ ba của tam giác tiếp theo.
6 Nếu không có các nút hoạt động thì tam giác đều có một đỉnh là K ideal cần phải được kiểm tra theo các yêu cầu sau:
Điểm K lý tưởng không nằm trong bất kỳ phần tử tam giác nào khác, và các mặt của tam giác mới không giao cắt với bất kỳ mặt nào đã tồn tại trong front hoạt động.
Nếu tam giác không thỏa mãn các điều kiện trên, ta tìm một nút hoạt động cho một tam giác có hình dạng tốt nhất.
7 Nếu bước 6 thất bại, xắp xếp lại trật tự của front, lấy mặt hoạt động ngắn thứ hai và quay trở lại bước 3.
8 Nếu bước 5 và 6 thành công, một tam giác mới được sinh ra và làm mới lại front (mặt ngắn nhất được chọn đã bị xóa bỏ) Trong trường hợp bước 6 thành công với K ideal là một đỉnh (đồng thời K ideal cũng trở thành một nút hoạt động của front mới) Nội suy tham số lưới tổng quát cho điểm mới này.
9 Sau khi làm mới front, quay trở lại bước 3 và lặp lại quá trình, tiếp tục cho đến khi không có cạnh nào còn lại trong front Khi đó tất cả các cạnh đều trở thành không hoạt động và miền tính toán đã tạo thành hệ tam giác đầy đủ.
Chúng ta xem xét một ví dụ trong không gian hai chiều với miền tính toán là hình vuông ABCD, bị khuyết một nửa đường tròn với các thông số δ = 1, s = 1, n x = 1, n y = 0 tại các nút A, B, C, D Tiếp theo, chúng ta sẽ tạo lưới nền gồm hai tam giác ACD và ABD, trình bày các bước đơn giản trong quá trình tạo lưới Các nút được chọn từ 1 đến 8 và mặt phẳng ban đầu được xác định như hình vẽ Một trong hai cạnh ngắn nhất (1-2) sẽ được chọn để dựng đường tròn tâm.
Điểm K id có bán kính δ′ và đường tròn này không chứa điểm nút nào bên trong Tam giác đều K id 12 được chấp nhận, do đó điểm K id được chọn là điểm mới Front sẽ được làm mới lại.
• Các nút không hoạt động: Không
• Các mặt không hoạt động: 1-2
• Tổng số phần tử được tạo ra: 1
• Tổng số điểm nút còn lại: 9
Sau khi chọn mặt 2-3, chúng ta tiếp tục thực hiện các bước tương tự như trước Điểm K lý tưởng được chấp nhận và trở thành nút mới, đồng thời front sẽ được cập nhật như hình minh họa dưới đây.
• Các nút không hoạt động: Không
• Các mặt không hoạt động: 1-2, 2-3
• Tổng số phần tử được tạo ra: 2
Tổng số điểm nút còn lại là 10 Khi chọn mặt 10-3, điểm K id không nằm trong miền tính toán, dẫn đến việc tam giác đều không được chấp nhận Do đó, điểm K id không thỏa mãn điều kiện.
Chúng ta sử dụng nút hoạt động đã tồn tại là nút 4 và chọn mặt 10-4 là mặt mới front được làm mới lại và có các đặc điểm sau:
• Các nút không hoạt động: 3
• Các mặt không hoạt động: 1-2, 2-
• Tổng số phần tử được tạo ra: 3
• Tổng số điểm nút còn lại: 9
Sau khi chọn mặt 2-10, nút 9 trong đường tròn tâm K id được xác định là đỉnh của phần tử tiếp theo Front đã được làm mới với các đặc điểm mới.
• Các nút không hoạt động: 2, 3
• Tổng số phần tử được tạo ra: 4
• Tổng số điểm nút còn lại: 8
Tiếp theo, mặt 1-9 được chọn Thực hiện tương tự như quá trình chọn mặt 10-3 Kết quả front được làm mới lại và có các đặc điểm sau:
• Các nút không hoạt động: 1, 2, 3
• Các mặt không hoạt động: 8-1, 1-2, 2-3, 3-4
• Tổng số phần tử được tạo ra: 5
• Tổng số điểm nút còn lại: 7
Chúng ta tiếp tục với mặt 8-9 Lần này, điểm K id nằm ngoài miền tính toán và bị loại bỏ do một cạnh của tam giác mới tạo thành cắt biên Đường tròn có tâm K id chứa nút 7, vì vậy nút 7 được chọn và front được làm mới với các đặc điểm mới.
• Các nút không hoạt động: 8, 1, 2, 3
• Các mặt không hoạt động: 7-8, 8-1, 1-2, 2-3, 3-4
• Tổng số phần tử được tạo ra: 6
• Tổng số điểm nút còn lại: 6
Tiếp theo mặt 7-9 được chọn, tam giác đều mới được chấp nhận
Vì vậy điểm K id trở thành điểm mới
Front được làm mới lại:
• Các nút không hoạt động: 8, 1, 2, 3
• Các mặt không hoạt động: 7-8, 8-1, 1-2, 2-3, 3-4
• Tổng số phần tử được tạo ra: 7
• Tổng số điểm nút còn lại: 7
Tiếp theo mặt 11-9 được chọn Tam giác đều vừa được xây dựng cắt mặt 9-10 của front, vì vậy điểm K id không được thỏa mãn.
Thay vào đó, nút hoạt động gần nhất là nút 10 được chọn, và front được làm mới lại với các đặc điểm:
• Các nút không hoạt động: 8, 1, 2, 3
• Các mặt không hoạt động: 7-8, 8-1, 1-2, 2-3, 3-4
• Tổng số phần tử được tạo ra: 8
• Tổng số điểm nút còn lại: 6
Thực hiện thêm 4 bước trong thuật toán, tại mỗi bước, mặt ngắn nhất được chọn, dẫn đến việc hình thành hệ tam giác như hình bên dưới Kết quả cuối cùng của quá trình này sẽ có những đặc điểm riêng biệt.
• Các nút hoạt động: Không
• Các mặt hoạt động: Không
• Các nút không hoạt động: 1, 2, 3, 4, 5, 6, 7, 8
• Các mặt không hoạt động: 1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-8, 8-1
• Tổng số phần tử được tạo ra: 12
• Tổng số điểm nút còn lại: Không
Khi một điểm mới được phát hiện gần một nút hoạt động trên front, điểm đó sẽ được thay thế bởi nút này, giúp loại bỏ các tam giác có cạnh nhỏ.
Sự thích nghi và không gian tham số
Khi tham số kéo dãn s tại một điểm trong miền tính toán bằng 1, lưới xung quanh điểm đó sẽ tạo thành các tam giác xấp xỉ đều Tuy nhiên, các ô lưới gần biên thường cần có bán kính tỉ lệ cao, đòi hỏi tham số s phải lớn Để khắc phục vấn đề này, ta có thể lấy các điểm mới trên đường thẳng trực giao của các đoạn biên ban đầu, cho phép các tam giác được mở rộng vào bên trong miền tính toán Sau khi các lớp gần biên được phủ bằng các tam giác đã được kéo dãn với bán kính tỉ lệ cao, phần còn lại của miền tính toán có thể được phủ theo thuật toán AFT đã được mô tả.
Chúng ta có thể tạo ra các tam giác kéo dãn thông qua các phép biến đổi toán học Đầu tiên, một lưới gồm các tam giác xấp xỉ đều được xây dựng trong không gian tham số Sau đó, chúng ta áp dụng phép biến đổi toán học để chuyển đổi các tam giác này thành các tam giác kéo dãn trong không gian vật lý Quá trình biến đổi từ không gian vật lý sang không gian tham số liên quan đến tính luân phiên và tính kéo dãn của một phần tử Một điểm trong không gian vật lý, tương ứng với véctơ vị trí ˙x, sẽ được biến đổi thành điểm ˙x˜.
(1.2.1) n x n y các thành phần của ˙s là (s x , s y ) = (cosΦ, sinΦ), các thành phần của ˙n là
(n x , n y ) = (−cosΦ, sinΦ) Chúng ta cũng có ˙ x˜ = ∼ x
Phép biến đổi được minh họa trong hình dưới đây cho phép chúng ta thu được các tam giác được kéo dãn trong không gian vật lý bằng cách áp dụng phép biến đổi ngược của (1.2.1).
Cải thiện chất lượng lưới
Sau khi tạo ra lưới không cấu trúc, chúng ta có thể áp dụng hai quy trình để nâng cao chất lượng lưới mà không làm thay đổi số lượng tam giác và nút.
Quá trình trao đổi đường chéo giữa các tam giác không làm thay đổi vị trí của các nút, mà chỉ thay đổi liên kết giữa chúng Chúng ta sẽ thực hiện trao đổi đường chéo cho tất cả các tam giác ngoại trừ các phần tử trên biên Ví dụ, cạnh AC là cạnh chung của hai tam giác ABC và ACD; chúng ta sẽ xem xét việc thay thế đường chéo AC bằng BD Việc trao đổi này chỉ được thực hiện nếu hình dạng của hai tam giác ABD và BCD đáp ứng tốt hơn một số tiêu chuẩn nhất định, chẳng hạn như góc nhỏ nhất của hai tam giác sau khi trao đổi phải lớn hơn góc nhỏ nhất của hai tam giác ban đầu Nếu các tam giác ban đầu tạo thành các tứ giác không lồi, thì không cần thực hiện trao đổi đường chéo.
Hình 1.11: Trao đổi đường chéo
Hình 1.12: không trao đổi đường chéo trong trường hợp này
Quá trình này thay đổi vị trí các nút bên trong mà không làm thay đổi liên kết giữa chúng, với ý tưởng coi các mặt của tam giác như lò xo tuyến tính có độ cứng đồng nhất và sức căng tỉ lệ với chiều dài lò xo Chúng ta xây dựng các vòng lặp để tìm kiếm vị trí cân bằng tổng thể của các nút, trong đó các nút bên trong được di chuyển đến vị trí trọng tâm của ba nút liên kết Thông thường, lưới sẽ đạt được độ nhẵn yêu cầu sau 3 đến 5 vòng lặp.
Phương pháp tạo lưới không cấu trúc sử dụng thuật toán chèn điểm tự động và tái kết nối địa phương
Giới thiệu
Các phương pháp tạo lưới không cấu trúc cho phần tử tam giác và tứ diện phổ biến bao gồm Delaunay Triangulation và tịnh tiến biên Delaunay Triangulation nổi bật với tính hiệu quả và nền tảng toán học vững chắc, trong khi phương pháp tịnh tiến biên mang lại các phần tử chất lượng cao và bảo tồn tính nguyên vẹn của biên Nghiên cứu gần đây cho thấy sự kết hợp giữa hai phương pháp này có thể tạo ra lưới với chất lượng tương đương như tịnh tiến biên, đồng thời vẫn giữ được cơ sở toán học của Delaunay Triangulation.
Thay thế các phương pháp đã được phát triển (sử dụng thuật toán chèn điểm tự động và kết nối tối ưu hóa), Maram và Weatherill
Phương pháp AFLR (advancing-front/local-reconnection) được giới thiệu vào năm 1955, kết hợp thuật toán chèn điểm của phương pháp tịnh tiến biên và sơ đồ tái kết nối địa phương của Delaunay Triangulation, với tiêu chí tối ưu hóa góc lớn nhất của phần tử Trong phương pháp này, quá trình chèn điểm và kết nối được thực hiện độc lập, với việc sử dụng thuật toán tái kết nối địa phương thay vì thuật toán trao đổi cạnh, nhằm đạt được kết nối tối ưu Tái kết nối địa phương được thực hiện lặp đi lặp lại để đáp ứng các tiêu chuẩn mong muốn AFLR rất hiệu quả cho các phần tử tam giác và tứ diện, và còn được mở rộng để tạo ra các phần tử lưới có bán kính tỉ lệ cao cùng các phần tử có góc vuông Phương pháp này đã được áp dụng thành công trong việc tạo ra các phần tử chất lượng cao cho các miền tính toán hai chiều có hình dạng phức tạp.
Phương pháp chia lưới AFLR
AFLR là phương pháp kết hợp thuật toán chèn điểm với tịnh tiến biên và sơ đồ tái kết nối địa phương Trong quá trình chia lưới, các phần tử thỏa mãn được giữ nguyên, tạo thành cấu trúc dữ liệu hiệu quả cho các phép toán tìm kiếm địa phương Hàm phân phối vị trí điểm được áp dụng toàn miền tính toán, bắt đầu từ các điểm xa biên đến các điểm trên biên Các điểm mới được tạo ra thông qua các phương pháp sắp xếp khác nhau, bao gồm sắp xếp theo mặt tiến cho phần tử đẳng hướng, sắp xếp theo điểm phía trước cho phần tử đẳng hướng có góc vuông, và tịnh tiến dọc pháp tuyến cho phần tử có bán kính tỉ lệ cao.
Để đạt được sự liên kết của các điểm mới, trước tiên cần chia nhỏ các phần tử chứa chúng Sau đó, các liên kết này sẽ được tối ưu hóa thông qua quá trình tái kết nối địa phương, nhằm tối thiểu hóa góc lớn nhất theo tiêu chuẩn min - max Quá trình này được thực hiện trên toàn miền tính toán và lặp lại cho đến khi lưới hoàn chỉnh được tạo ra.
Các bước cơ bản của phương pháp chia lưới AFLR là:
1 Xác định vị trí các điểm ở trên bề mặt biên.
2 Tạo một lưới bề mặt biên.
3 Tạo ra một hệ tam giác ban đầu hợp lệ của các điểm trên bề mặt biên và khôi phục lại toàn bộ bề mặt biên Ta lấy ví dụ sau đây để minh họa
Hình 1.13: Hệ tam giác ban đầu
4 Gán một hàm phân bố điểm với mỗi điểm biên dựa trên khoảng cách điểm địa phương, đồng thời gán tỉ lệ phát triển hình học của bề mặt biên một cách tùy ý.
5 Đối với các phần tử đẳng hướng, tạo ra các điểm sử dụng phương pháp sắp xếp điểm theo cạnh (mặt) tiến lên phía trước Các điểm được tạo ra bằng cách tịnh tiến từ cạnh (mặt) thỏa mãn hàm phân bố điểm của các phần tử cũng chỉ thỏa mãn hàm phân bố điểm trên một cạnh (một mặt)
Hình 1.14: Phương pháp sắp xếp điểm cho các phần tử đều, đẳng hướng
Đối với các phần tử có góc vuông, hãy sử dụng phương pháp sắp xếp điểm theo điểm phía trước để tạo ra các điểm mới Các điểm này được tạo ra bằng cách tịnh tiến tương tự như ở bước 5, nhưng với hai điểm được tịnh tiến theo cạnh (mặt) pháp tuyến từ hai (ba) điểm thuộc cạnh (mặt) đó.
Hình 1.15: Phương pháp sắp xếp điểm cho các phần tử đều, đẳng hướng
Đối với các phần tử có bán kính tỉ lệ cao, việc tạo ra các điểm sử dụng phương pháp sắp xếp tịnh tiến theo pháp tuyến là cần thiết Các điểm này được tạo ra từng lớp một từ các biên, thông qua việc tịnh tiến dọc theo các pháp tuyến dựa trên đặc điểm hình học của biên.
Hình 1.16: Phương pháp sắp xếp điểm tịnh tiến theo pháp tuyến cho các phần tử có góc vuông và bán kính tỉ lệ cao
Tại các vị trí có bề mặt biên bị gián đoạn, việc sử dụng nhiều pháp tuyến là cần thiết Các pháp tuyến này đóng vai trò quan trọng trong quá trình tối ưu hóa chất lượng lưới.
Hình 1.17: Các phần tử có bán kính tỉ lệ cao sử dụng nhiều pháp tuyến
8 Nội suy hàm phân bố điểm cho các điểm mới từ các phần tử chứa các điểm đó Nếu sự phát triển hình học đã được quy định cụ thể thì hàm phân bố phụ thuộc vào một khoảng cách gần đúng tới biên gần nhất và sự phát triển hình học đã được quy định với biên đó.
9 Loại bỏ các điểm mới quá gần với các điểm mới khác.
10 Chèn các điểm mới chấp nhận được bằng cách chia trực tiếp các phần tử có chứa chúng Ta thu được hệ tam giác sau:
Hình 1.18: Hệ tam giác sau khi chèn điểm trực tiếp ở vòng lặp thứ 3
11 Tối ưu hóa liên kết các điểm sử dụng tái kết nối địa phương Với mỗi cặp phần tử so sánh tiêu chuẩn tái kết nối với tất cả các liên kết có thể và tái kết nối sử dụng liên kết tối ưu nhất lặp lại quá trình này cho đến khi không còn phần tử nào được tái kết nối nữa.Trong quá trình tái kết nối địa phương ta sử dụng kết hợp hai tiêu chuẩn: Tiêu chuẩn Delaunay và tiêu chuẩn min-max Chất lượng lưới sẽ được cải thiện trên toàn miền và khắc phục được hầu hết các vấn đề có liên quan đến tính tối ưu địa phương mà ảnh hưởng đến tính tối ưu tổng thể. Hình vẽ dưới đây là hệ tam giác thu được sau quá trình tái kết nối địa phương.
Hình 1.19: Hệ tam giác sau khi tái kết nối địa phương ở vòng lặp thứ 3
12 Lặp lại quá trình sinh điểm và tái kết nối từ bước 5 đến bước 11 cho đến khi không có điểm mới nào được sinh ra nữa.
13 Kết nối các phần tử một cách tối ưu bằng cách tịnh tiến từ các bề mặt biên, việc lựa chọn kết nối dựa trên các tiêu chuẩn và chất lượng lưới.
14 Làm nhẵn các tọa độ của lưới.
15 Tối ưu hóa kết nối sử dụng quá trình tái kết nối địa phương (bước 11).
• Sự hình thành bề mặt lưới ba chiều.
Hệ thống hình học CAD được sử dụng để định nghĩa và đánh giá bề mặt hình học, trong đó quá trình hình thành cạnh và bề mặt lưới yêu cầu quy tắc đánh giá hình học và truy cập cơ sở dữ liệu hình học Cấu trúc liên kết bề mặt được tách ra từ cơ sở dữ liệu CAD, sử dụng cấu trúc dữ liệu riêng cho việc hình thành lưới Quá trình hình thành lưới được thiết kế riêng với truy cập đánh giá hình học, tạo ra giao diện mượt mà giữa lưới và hệ thống hình học, đồng thời giúp dễ dàng sử dụng các hệ thống CAD khác mà không cần sửa đổi nhiều Các quy tắc liên quan đến CAD chỉ cần thiết cho các cạnh hiện tại và sự hình thành bề mặt lưới, với tọa độ không gian vật lý x, y, z được ánh xạ sang không gian tọa độ u, v, được ký hiệu là xyz − from − uv.
Các cạnh lưới được hình thành từ phiên bản một chiều của quá trình tạo lưới chuẩn, đảm bảo sự phân bố điểm và tốc độ phát triển hình học phù hợp với chất lượng lưới tối ưu Khoảng cách giữa các điểm được xác định tại hai đầu của mỗi cạnh hoặc đoạn, từ đó xác định sự phân bố điểm như trong hình minh họa.
Các bước cơ bản của quá trình hình thành lưới:
1 Tạo ra một bảng nội suy cho các ánh xạ không gian tọa độ so với chiều dài tự nhiên sử dụng quy tắc đánh giá hình học xyz f rom
2 uv Đưa ra từ mỗi đầu của đoạn cạnh trong không gian chiều dài tự nhiên và tạo ra hai điểm mới Các khoảng cách điểm cho các điểm này được nội suy từ các điểm cuối tiếp xúc bên trong của mỗi cạnh.
3 Loại bỏ một điểm mới nếu nó quá gần điểm mới khác.
4 Lặp lại các bước 2 và 3 cho đến khi không còn điểm mới được tạo ra nữa.
5 Làm nhẵn các tọa độ chiều dài tự nhiên của các cạnh lưới.
6 Nội suy các ánh xạ không gian tọa độ u, v tại các tọa độ chiều dài tự nhiên phát sinh.