Thắc mắc về nội suy 3D???

[mtt333]

Mình muốn tìm các bài toán và thuật giải nội suy 3D???
Các bạn nếu biết hoặc nếu có nguồn tài liệu thì chỉ cho mình với nhé.

[poly]

nội suy 3D thì cũng là nội suy thôi mà. Cơ bản là giả sử 1 hàm nào đó, tìm thông số hàm đó rồi áp dụng cho 1 điểm trong miền.
Còn muốn cụ thể thì ít nhất phải biết bạn muốn dùng để làm gì chứ.

[whitepenguin]

KHông phải gọi là nội suy 3D mà gọi là nội duy tuyến tính (linear interpolate) , thường dùng để nội suy trong Spline và Vector pháp tuyến của các Revolution patch và nội suy màu trong quá trình đánh bóng

[mtt333]

KHông phải gọi là nội suy 3D mà gọi là nội duy tuyến tính (linear interpolate) , thường dùng để nội suy trong Spline và Vector pháp tuyến của các Revolution patch và nội suy màu trong quá trình đánh bóng

Bạn whitepenguincos thể nói cụ thể ra không chứ nói chung chung thế này thì khó biết quá.

Vẫn có thể gọi là nội suy 3D đối lập với bài toán nội suy 2D. Những cái bác nói ra là phương pháp hoặc ứng dụng.

Bài toán của mình được phát biểu như sau:
Trong không gian 3 chiều (x, y, z)
Giới hạn (Xmin <= x <= Xmax)(Ymin <= y <= Ymax)

Cho trước tập hữu hạn N điểm
(x1, y1, z1), (x2, y2, z2), .... (xN, yN, zN)

Cần phải xác định tại một điểm (x, y) bất kỳ trong giới hạn trên thì z là bao nhiêu???

Mình muốn tìm hiểu nhiều phương pháp khác nhau.

Hiện tại mình đã có hai phương pháp: trong đó có một phương pháp khá nổi tiếng là Gauroud Shading được sử dụng để đánh bóng màu.

Các bạn còn biết phương pháp nào nữa không???

[poly]

Hic, đã nói rồi. Nội suy trong 3D cũng như trong 2D hay trong cái gì khác thôi. Bác mtt33 học phương pháp tính chưa nhỉ? Nội suy là nội suy, mấy D cũng là nội suy. Nội suy tuyến tính (linear interpolate) hay nội suy bậc cao hơn cũng là nội suy.
Nội suy Gouraud bác nói ko phải là cái "tổng quát" như bác mô tả. Trường hợp này data input khá ít, cao nhất nội suy Gouraud dùng tuyến tính (linear- patch tam giác) hay cao lắm song tuyến tính (bilinear -patch quadrilateral) là hết. Mà cái bác mô tả trong bài trên cũng là nội suy 2D chớ 3D đâu, hix.
Tổng quát là khác. Có nhiều cách, nhưng cách nào cũng dùng 1 hàm test cả. Hàm test có thể là đa thức f(x,y,z), hoặc hàm dựa trên khoảng cách r (radial function).
Giả sử dùng hàm đa thức thì dễ rồi. Cho là N điểm đi, thế thì từ N điểm này, viết pt:
đi qua N điểm. Hàm đa thức sẽ chứa N ẩn. Giải hệ tuyến tính này là ra nhé. Ẩn là các tham số của đa thức.
Nhưng pp này có điểm bất lợi. Khi N lớn thì ma trận Vandermonde thường bị ill-condition. Thế nên người ta có pp khác là pp bình phương cực tiểu...
Dùng hàm đa thức thì thế, dùng hàm radial thì khỏe hơn...
Đại khái là thế, bác muốn nhiều pp để làm gì?

[mtt333]

Hic, đã nói rồi. Nội suy trong 3D cũng như trong 2D hay trong cái gì khác thôi. Bác mtt33 học phương pháp tính chưa nhỉ? Nội suy là nội suy, mấy D cũng là nội suy. Nội suy tuyến tính (linear interpolate) hay nội suy bậc cao hơn cũng là nội suy.
Nội suy Gouraud bác nói ko phải là cái "tổng quát" như bác mô tả. Trường hợp này data input khá ít, cao nhất nội suy Gouraud dùng tuyến tính (linear- patch tam giác) hay cao lắm song tuyến tính (bilinear -patch quadrilateral) là hết. Mà cái bác mô tả trong bài trên cũng là nội suy 2D chớ 3D đâu, hix.
Tổng quát là khác. Có nhiều cách, nhưng cách nào cũng dùng 1 hàm test cả. Hàm test có thể là đa thức f(x,y,z), hoặc hàm dựa trên khoảng cách r (radial function).
Giả sử dùng hàm đa thức thì dễ rồi. Cho là N điểm đi, thế thì từ N điểm này, viết pt:
đi qua N điểm. Hàm đa thức sẽ chứa N ẩn. Giải hệ tuyến tính này là ra nhé. Ẩn là các tham số của đa thức.
Nhưng pp này có điểm bất lợi. Khi N lớn thì ma trận Vandermonde thường bị ill-condition. Thế nên người ta có pp khác là pp bình phương cực tiểu...
Dùng hàm đa thức thì thế, dùng hàm radial thì khỏe hơn...
Đại khái là thế, bác muốn nhiều pp để làm gì?

Rất cám ơn ý kiến đóng góp của bác

Muốn biết nhiều để có chọn lựa và đánh giá thôi!!!

Thôi không tranh cãi với bác cái tên gọi nữa.
Em chỉ được học bài toán nội suy trong trường như thế này:
cho trước tập điểm (xi, yi) hỏi tại x bất kỳ thì y bằng bao nhiêu.
BÀi toán này thì quá kinh điển và có nhiều phương pháp khác nhau: tuyến tính, Lagrang, Spline, ...

Em muốn phát triển bài toán dưới dạng mở rộng trong không ain 3 chiều
là cho trước tập điểm (xi, yi, zi), hỏi tại (x, y) bất kỳ thì z bằng bao nhiêu.

Phương pháp giải đa thức N ấn qua N điểm thì okie, đã rõ, nhưng ngốn ngấu thời gian giải phương trình quá, nhất là khi dữ liệu có sự biến thiên liên tục: ví dụ như độ cao z của các điểm cho trước là biến thiên liên tục.

Bình phương cực tiểu thì cũng được đấy, nhưng cũng vướng mắc vấn đề như trên khi z biến thiên liên tục.

Tuyến tính hay Lagrang trong bài toán của em thì chưa hiểu phải như thế nào.

Dùng Spline thì đang đọc sách sẽ tranh cãi sau.

Dùng radial thì cũng tchuwa tìm hiểu, trình bày clearly hơn đi.

Cám ơn bác nhé

[poly]

Hì, để mình làm rõ vấn đề nhé.

Em muốn phát triển bài toán dưới dạng mở rộng trong không ain 3 chiều là cho trước tập điểm (xi, yi, zi), hỏi tại (x, y) bất kỳ thì z bằng bao nhiêu.
Bài toán của bạn là nội suy hàm z = f(x,y). Đây là bài toán 2 thông số, hay "2D".

Phương pháp giải đa thức N ấn qua N điểm thì okie, đã rõ, nhưng ngốn ngấu thời gian giải phương trình quá, nhất là khi dữ liệu có sự biến thiên liên tục: ví dụ như độ cao z của các điểm cho trước là biến thiên liên tục.
Đúng rồi, N nhỏ thỉ mới nội suy global. Nếu N lớn (chừng hơn vài chục thì nội suy đa thức chết ngắc) thì thực tế thì không ai nội suy điểm trong cả 1 vùng (global) mà dùng một lưới (patch) để nội suy cục bộ (local). Patch thường là lưới tam giác hay tứ giác. Cần nội suy điểm nào thì tìm phần tử chứa điểm này sau đó nội suy dựa trên phần tử chứa điểm này. Cách này là thông dụng nhất để nội suy data. Ko ai nội suy trực tiếp cả. Nhưn nó ko phải là pp nội suy mà là cách để nội suy. Bạn đừng nhầm nhé.

Bình phương cực tiểu thì cũng được đấy, nhưng cũng vướng mắc vấn đề như trên khi z biến thiên liên tục.
Bình phương cực tiểu thì khác. Cái này dùng trong thống kê hơn là nội suy "kỹ thuật". Mình đính chính lại là bình phương cực tiểu ko expensive vì nó ko liên quan đến inverse ma trận O(N^3) mà chỉ nhân thôi O(N^2). Giả sử bạn dùng để nội suy giá trị "đúng" thì ko dùng pp này. Bình phương cực tiểu chỉ dùng cho một số hàm test đơn giản nên ko chính xác đủ để dùng trong "kỹ thuật". Tuy nhiên trong một số trường hợp trong giải thuật Radiosity (Global Illumination) người ta dùng cái này trong giải thuật Monte-Carlo để ước lượng đó.

Tuyến tính hay Lagrang trong bài toán của em thì chưa hiểu phải như thế nào.
Hic hic, tuyến tính là một trường hợp nhỏ của nội suy đa thức. Dùng tuyến tính (linear) thì hàm test là z = f(x,y) = a + b*x + c*y. Thêm "d*x*y" là song tuyến tính(bilinear). Lagrange là một trường hợp tương tự đa thức, cách biểu diễn hàm đa thức hơi khác thôi. Cái này chi tiết bạn đọc sách nhé.

Dùng Spline thì đang đọc sách sẽ tranh cãi sau.
Dùng spline có thể tóm gọn là "đa thức bậc 3" dùng kỹ thuật patch mình nói ở trên (trong 1D thì nó là hàm local trên từng đoạn, OK?). Spline dùng cho trường hợp z = f(x,y) thì được rồi, nhưng nhiều ẩn hơn thì ko được.

Dùng radial thì cũng tchuwa tìm hiểu, trình bày clearly hơn đi.
Radial là vầy, thay vì dùng hàm test là hàm theo x,y thì dùng r (khoảng cách từ 1 điểm đến 1 điểm reference nào đó). Ví dụ hàm test dạng này: z = f(x,y)= sqrt(r^a+b^2), với r = sqrt((x-x_ref)^2+(y-y_ref)^2)
Sau đó thì cũng tương tự các pp khác. Tuy nhiên pp này không biết được mức độ chính xác trước (ko giống như nội suy Newton bạn biết chính xác accuracy), chính xác là biết nhưng về cơ sở toán khá rườm rà. Tuy nhiên trong một số trường hợp, nó khá tốt. Muốn biết thêm thì bạn google "radial basis function" nhé.

[mtt333]

Thế hồi trước em có làm bài toán nội suy như thế này, liệu đó có phải là "radial basis function":
Xét một điểm (x, y), nó chịu "tác động" (đây là từ chuyên môn của bài toán mà mình đã làm) của một điểm zi = (xi, yi) cho trước là f(di) với di là khoảng cách từ (x, y) đến (xi, yi).
Hàm f max là 1,000 tại d = 0, nghịch biến theo d và là đặc trưng vật lý của riêng bài toán.
Có tất cả N điểm cho trước gây "tác động" lên điểm (x, y) đó
Tính T = f(d1) + f(d2) + f(d3) + ... + f(dN)
Vậy z tại điểm (x, y) được tính như sau:
z = z1*f(d1)/T+ z2*f(d2)/T + z3*f(d3)/T+ ... + zN*f(dN)/T

[poly]

Hơ cái đó giống công thức chứ đâu phải nội suy gì đâu. Giống tính "cường độ điện trường" hay cái gì đó tương tự :D

[whitepenguin]

đang nội suy 3d tự nhiên đi sang hệ number analysym , điên ,ngoài đánh bóng gauroud thì còn có phong là hết roai