Làm thế nào tôi có thể polygonise một bool [,,]

Question

Nếu bất cứ ai quan tâm, tôi đang sử dụng WPF ....

Bắt đầu của câu chuyện:

tôi có một loạt các hình ảnh màu xám quy mô (lát của một mô hình). Người dùng nhập "phạm vi" các giá trị thang màu xám để tạo mô hình 3D. Vì vậy, tôi đã tạo một mảng 3D bool để làm cho việc xây dựng mô hình 3D dễ dàng hơn. Mảng này đại diện cho một hộp pixel, cho biết mỗi pixel có nên được tạo/tạo/lấp đầy hay không.

---

Các tie:

Sử dụng một bool[,,], tôi muốn lấy một List<Point3D[]> nơi mỗi Point3D[] có chiều dài 3 và đại diện cho một hình tam giác trong không gian 3D.

---

Thông tin thêm:

Mô hình được tạo ra sẽ được in 3D. Trong số bool[,,], true cho biết sự hiện diện của vật chất, trong khi false cho biết sự vắng mặt của vật chất. Tôi cần phải tránh các mô hình khối, trong đó mỗi pixel được thay thế bằng một khối lập phương (Điều đó sẽ vô dụng theo mục đích của tôi). Mô hình nên càng trơn tru càng tốt và càng chính xác càng tốt.

---

Những gì tôi đã cố gắng để làm:

1- Tôi thực hiện các thuật toán khối diễu hành, nhưng nó chỉ đơn giản dường như không phải được tạo ra để chấp nhận một "phạm vi" các giá trị.

2- Tôi tiếp tục đấu tranh trong một vài ngày cố gắng tạo thuật toán của riêng mình, nhưng tôi đã thất bại một phần. (Nó thật phức tạp Nếu bạn muốn biết thêm về nó, xin vui lòng thông.)

---

Một số giải pháp dự kiến ​​rằng tôi không có ý tưởng làm thế nào để thực hiện:

1- Sửa đổi các thuật toán khối Marching để làm cho nó hoạt sử dụng một bool[,,]

2- Sửa đổi các thuật toán khối Marching để làm cho nó hoạt sử dụng một tác phẩm sử dụng một "tầm" của isolevel giá trị

3- Hiển thị cách triển khai thuật toán khác phù hợp với mục đích của tôi (Có thể thuật toán Ray-Casting) trong WPF.

4- Yêu cầu nguồn của thuật toán mà tôi đã cố thực hiện sau đó chỉ cho tôi cách giải quyết. (Nó đã được thực hiện để đa giác một bool[,,] ở nơi đầu tiên)

5- Một số giải pháp kỳ diệu khác.

Xin cảm ơn trước.

---

EDIT:

Bằng cách nói

Sử dụng một bool[,,], tôi muốn lấy một List<Point3D[]> nơi mỗi Point3D[] có chiều dài 3 và đại diện cho một hình tam giác trong không gian 3D.

Tôi có nghĩa là tôi muốn truy xuất một nhóm Hình tam giác. Mỗi tam giác phải được thể hiện bằng 3 Point3D s. Nếu bạn không biết Point3D là gì, nó là struct chứa 3 đôi (X, Y và Z) được sử dụng để đại diện cho một vị trí trong không gian 3D.

Vấn đề với thuật toán hình khối diễu hành là nó khá mơ hồ. Ý tôi là, bạn hiểu gì khi làm điều đó?

cubeindex = 0; 
if (grid.val[0] < isolevel) cubeindex |= 1; 
if (grid.val[1] < isolevel) cubeindex |= 2; 
if (grid.val[2] < isolevel) cubeindex |= 4; 
if (grid.val[3] < isolevel) cubeindex |= 8; 
if (grid.val[4] < isolevel) cubeindex |= 16; 
if (grid.val[5] < isolevel) cubeindex |= 32; 
if (grid.val[6] < isolevel) cubeindex |= 64; 
if (grid.val[7] < isolevel) cubeindex |= 128; 

Vì vậy, tôi chỉ đơn giản là không biết bắt đầu sửa đổi nó ở đâu.

---

Một EDIT:

Sau một số thử nghiệm với các thuật toán khối diễu hành, tôi nhận thấy rằng polygonising một bool[,,] sẽ không dẫn đến việc mô hình 3D mượt mà tôi mong muốn, vì vậy tôi giải pháp dự kiến ​​đầu tiên và giải pháp dự kiến ​​thứ tư của tôi đều không được phát. Sau rất nhiều nghiên cứu, tôi đã biết về phương pháp Ray-Casting về hiển thị khối lượng. Nó có vẻ thực sự mát mẻ, nhưng tôi không thực sự chắc chắn nếu nó phù hợp với nhu cầu của tôi. Tôi thực sự không thể hiểu cách nó được triển khai như thế nào mặc dù tôi biết cách hoạt động.

---

Thêm một EDIT: TriTable.LookupTable và EdgeTable.LookupTable là bảng hiện here

Đây là lớp MarchingCubes:

public class MarchingCubes 
{ 
    public static Point3D VertexInterp(double isolevel, Point3D p1, Point3D p2, double valp1, double valp2) 
    { 
     double mu; 
     Point3D p = new Point3D(); 

     if (Math.Abs(isolevel - valp1) < 0.00001) 
      return (p1); 

     if (Math.Abs(isolevel - valp2) < 0.00001) 
      return (p2); 

     if (Math.Abs(valp1 - valp2) < 0.00001) 
      return (p1); 

     mu = (isolevel - valp1)/(valp2 - valp1); 

     p.X = p1.X + mu * (p2.X - p1.X); 
     p.Y = p1.Y + mu * (p2.Y - p1.Y); 
     p.Z = p1.Z + mu * (p2.Z - p1.Z); 

     return (p); 
    } 

    public static void Polygonise (ref List<Point3D[]> Triangles, int isolevel, GridCell gridcell) 
    { 
     int cubeindex = 0; 
     if (grid.val[0] < isolevel) cubeindex |= 1; 
     if (grid.val[1] < isolevel) cubeindex |= 2; 
     if (grid.val[2] < isolevel) cubeindex |= 4; 
     if (grid.val[3] < isolevel) cubeindex |= 8; 
     if (grid.val[4] < isolevel) cubeindex |= 16; 
     if (grid.val[5] < isolevel) cubeindex |= 32; 
     if (grid.val[6] < isolevel) cubeindex |= 64; 
     if (grid.val[7] < isolevel) cubeindex |= 128; 

     // Cube is entirely in/out of the surface 
     if (EdgeTable.LookupTable[cubeindex] == 0) 
      return; 

     Point3D[] vertlist = new Point3D[12]; 

     // Find the vertices where the surface intersects the cube 
     if ((EdgeTable.LookupTable[cubeindex] & 1) > 0) 
      vertlist[0] = VertexInterp(isolevel, grid.p[0], grid.p[1], grid.val[0], grid.val[1]); 

     if ((EdgeTable.LookupTable[cubeindex] & 2) > 0) 
      vertlist[1] = VertexInterp(isolevel, grid.p[1], grid.p[2], grid.val[1], grid.val[2]); 

     if ((EdgeTable.LookupTable[cubeindex] & 4) > 0) 
      vertlist[2] = VertexInterp(isolevel, grid.p[2], grid.p[3], grid.val[2], grid.val[3]); 

     if ((EdgeTable.LookupTable[cubeindex] & 8) > 0) 
      vertlist[3] = VertexInterp(isolevel, grid.p[3], grid.p[0], grid.val[3], grid.val[0]); 

     if ((EdgeTable.LookupTable[cubeindex] & 16) > 0) 
      vertlist[4] = VertexInterp(isolevel, grid.p[4], grid.p[5], grid.val[4], grid.val[5]); 

     if ((EdgeTable.LookupTable[cubeindex] & 32) > 0) 
      vertlist[5] = VertexInterp(isolevel, grid.p[5], grid.p[6], grid.val[5], grid.val[6]); 

     if ((EdgeTable.LookupTable[cubeindex] & 64) > 0) 
      vertlist[6] = VertexInterp(isolevel, grid.p[6], grid.p[7], grid.val[6], grid.val[7]); 

     if ((EdgeTable.LookupTable[cubeindex] & 128) > 0) 
      vertlist[7] = VertexInterp(isolevel, grid.p[7], grid.p[4], grid.val[7], grid.val[4]); 

     if ((EdgeTable.LookupTable[cubeindex] & 256) > 0) 
      vertlist[8] = VertexInterp(isolevel, grid.p[0], grid.p[4], grid.val[0], grid.val[4]); 

     if ((EdgeTable.LookupTable[cubeindex] & 512) > 0) 
      vertlist[9] = VertexInterp(isolevel, grid.p[1], grid.p[5], grid.val[1], grid.val[5]); 

     if ((EdgeTable.LookupTable[cubeindex] & 1024) > 0) 
      vertlist[10] = VertexInterp(isolevel, grid.p[2], grid.p[6], grid.val[2], grid.val[6]); 

     if ((EdgeTable.LookupTable[cubeindex] & 2048) > 0) 
      vertlist[11] = VertexInterp(isolevel, grid.p[3], grid.p[7], grid.val[3], grid.val[7]); 

     // Create the triangle 
     for (int i = 0; TriTable.LookupTable[cubeindex, i] != -1; i += 3) 
     { 
      Point3D[] aTriangle = new Point3D[3]; 

      aTriangle[0] = vertlist[TriTable.LookupTable[cubeindex, i]]; 
      aTriangle[1] = vertlist[TriTable.LookupTable[cubeindex, i + 1]]; 
      aTriangle[2] = vertlist[TriTable.LookupTable[cubeindex, i + 2]]; 

      theTriangleList.Add(aTriangle); 
     } 
    } 
} 

Đây là lớp GridCell:

public class GridCell 
{ 
    public Point3D[] p = new Point3D[8]; 
    public Int32[] val = new Int32[8]; 
} 

Ok, đó là những gì tôi đang làm:

List<int[][]> Slices = new List<int[][]>(); //Each slice is a 2D jagged array. This is a list of slices, each slice is a value between about -1000 to 2300 

public static void Main() 
{ 
    List <Point3D[]> Triangles = new List<Point3D[]>(); 
    int RowCount;//That is my row count 
    int ColumnCount;//That is my column count 
    //Here I fill the List with my values 
    //Now I'll polygonise each GridCell 
    for (int i = 0; i < Slices.Count - 1; i++) 
    { 
     int[][] Slice1 = Slices[i]; 
     int[][] Slice2 = Slices[i + 1]; 
     for (int j = 0; j < RowCount - 1; j++) 
     { 
      for (int k = 0; k < ColumnCount - 1; k++) 
      { 
       GridCell currentCell = GetCurrentCell (Slice1, Slice2, j, k); 
       Polygonise (ref Triangles, int isoLevel, GridCell currentCell); 
      } 
     } 
    } 
    //I got the "Triangles" :D 
} 

//What this simply does is that it returns in 3D space from RI and CI 
public static GridCell GetCurrentCell (int[][] CTSliceFront, int[][] CTSliceBack, int RI, int CI)//RI is RowIndex and CI is ColumnIndex 
{ 
    //Those are preset indicating X,Y or Z coordinates of points/edges 
    double X_Left_Front; 
    double X_Right_Front; 
    double X_Left_Back; 
    double X_Right_Back; 
    double Y_Top_Front; 
    double Y_Botton_Front; 
    double Y_Top_Back; 
    double Y_Botton_Back; 
    double Z_Front; 
    double Z_Back; 

    GridCell currentCell = new GridCell(); 
    currentCell.p[0] = new Point3D(X_Left_Back, Y_Botton_Back, Z_Back); 
    currentCell.p[1] = new Point3D(X_Right_Back, Y_Botton_Back, Z_Back); 
    currentCell.p[2] = new Point3D(X_Right_Front, Y_Botton_Front, Z_Front); 
    currentCell.p[3] = new Point3D(X_Left_Front, Y_Botton_Front, Z_Front); 
    currentCell.p[4] = new Point3D(X_Left_Back, Y_Top_Back, Z_Back); 
    currentCell.p[5] = new Point3D(X_Right_Back, Y_Top_Back, Z_Back); 
    currentCell.p[6] = new Point3D(X_Right_Front, Y_Top_Front, Z_Front); 
    currentCell.p[7] = new Point3D(X_Left_Front, Y_Top_Front, Z_Front); 

    currentCell.val[] = CTSliceBack[theRowIndex + 1][theColumnIndex]; 
    currentCell.val[] = CTSliceBack[theRowIndex + 1][theColumnIndex + 1]; 
    currentCell.val[] = CTSliceFront[theRowIndex + 1][theColumnIndex + 1]; 
    currentCell.val[] = CTSliceFront[theRowIndex][theColumnIndex]; 
    currentCell.val[] = CTSliceBack[theRowIndex][theColumnIndex + 1]; 
    currentCell.val[] = CTSliceFront[theRowIndex][theColumnIndex + 1]; 
    currentCell.val[] = CTSliceFront[theRowIndex][theColumnIndex]; 

    return currentCell; 
} 

tôi đã thực hiện điều đó ngay từ stack-Overflow, vì vậy xin vui lòng chỉ ra bất kỳ lỗi chính tả. Đó là làm việc, Điều này dẫn đến một vỏ của một mô hình. Tôi muốn thay thế biến số isolevel trong hàm Polygonise với 2 số nguyên: isolevelMin và isolevelMax. Không chỉ 1 int mà còn là một dải ô.

---

EDIT: Guys, xin vui lòng giúp đỡ. 50 đại diện gần 1/2 danh tiếng của tôi. Tôi hy vọng tôi có thể thay đổi kỳ vọng của mình.Bây giờ tôi chỉ muốn bất kỳ ý tưởng làm thế nào tôi có thể thực hiện những gì tôi muốn, bất kỳ đoạn nào về cách làm điều đó hoặc nếu ai đó đưa ra một số từ khóa mà tôi có thể google mà tôi sử dụng để giải quyết vấn đề của tôi, ông sẽ nhận được đại diện. Tôi chỉ cần một ít ánh sáng - tất cả đều tối ở đây.

---

chỉnh sửa là tuyệt vời: Sau thậm chí nhiều hơn, nghiên cứu nhiều hơn và nhiều hơn nữa, tôi phát hiện ra rằng các thuật toán ray-diễu hành thể tích không thực sự tạo ra bề mặt. Vì tôi cần in mô hình 3D được tạo ra, tôi chỉ có một lối thoát ngay bây giờ. Tôi phải làm cho thuật toán hình khối diễu hành tạo ra một mô hình rỗng từ các giá trị cách ly tối đa và tối thiểu.

Answer 1

Một trong những giả định của thuật toán Marching Cube được rằng mỗi hình khối là một thực thể riêng biệt và không phụ thuộc vào các khối khác (điều này không hoàn toàn đúng nhưng chúng ta hãy gắn bó với điều này bây giờ).

Cho rằng, bạn có thể chia toàn bộ lưới thành hình khối và giải quyết từng phần riêng biệt. Bạn cũng có thể nhận thấy rằng mặc dù lưới cuối cùng phụ thuộc vào các giá trị chính xác của trường vô hướng 3D của bạn, cấu trúc liên kết của lưới chỉ phụ thuộc vào thực tế nếu một số góc lập phương là bên trong của lưới hoặc bên ngoài.

Ví dụ: Giả sử isolevel của bạn được đặt thành 0 và trường 3D của bạn có số dương và âm.Nếu bây giờ bạn thay đổi một số giá trị từ 0.1 thành 1.0 thì bạn sẽ chỉ thay đổi tỷ lệ của một số hình tam giác chứ không thay đổi số và/hoặc cấu trúc liên kết của chúng. Mặt khác, nếu bạn thay đổi một số giá trị từ 0.1 thành -0.1 thì hình tam giác của bạn có thể chuyển sang sắp xếp khác và số của chúng có thể thay đổi.

Nhờ vậy chúng ta có thể sử dụng một số tối ưu hóa thông minh - cho mỗi người trong số 8 góc bạn kiểm tra xem góc là bên hoặc ngoài của một lưới, bạn sử dụng những 8 bit để xây dựng một số - mà sẽ trở thành một chỉ số để bàn precomputed của bạn của các giải pháp cube có thể, hãy gọi cho họ Variants.

Mỗi Cube Variant là danh sách các hình tam giác cho cấu hình cụ thể của các góc này. Hình tam giác trong Marching Cubes luôn nằm giữa các cạnh khối lập phương, vì vậy chúng tôi sử dụng các chỉ số cạnh để mô tả nó. Các chỉ số đó là dữ liệu chính xác mà bạn thấy trong các bảng 'ma thuật' đó trong mã Paul Bourke :).

Nhưng đây chưa phải là lưới cuối cùng. Các hình tam giác bạn nhận được ở đây chỉ dựa trên một thực tế nếu một số góc bên trong hoặc bên ngoài của một lưới, nhưng bao xa là nó từ bề mặt? Nó có ảnh hưởng gì đến kết quả không? Ở đây có giá trị lưới của bạn một lần nữa - khi bạn đã chọn Variant, có danh sách các hình tam giác và 3 cạnh cho mỗi hình tam giác, sau đó bạn nhận được các giá trị ở đầu của cạnh và nội suy chúng để tìm giá trị 0 (chúng tôi ' đã đặt nó là isolevel, hãy nhớ?). Những cuối cùng, interpolated đỉnh nên được sử dụng cho lưới của bạn.

Điều đó đã trở thành một phần giới thiệu dài, tôi hy vọng bạn hiểu những gì tôi đã viết.

Đề nghị của tôi: Sự thay đổi đơn giản nhất là với các góc, thay vì làm điều này:

if (grid.val[0] < isolevel) cubeindex |= 1; 

Cố gắng thay đổi nó theo cách này:

if (grid.val[0] > isolevelMin && grid.val[0] < isolevelMax) cubeindex |= 1; 
// And the same for other lines... 

suy cuối cùng là một chút phức tạp hơn và Tôi không có cách nào để thử nghiệm nhưng hãy thử:

• Sửa đổi của bạn VertexInterp để vượt qua hai isolevels - min và max
• Bên VertexInterp séc isolevel là giữa valp1 và valp2 giá trị
• suy như trong mã hiện tại, nhưng sử dụng isolevel chọn (tối thiểu hoặc tối đa)

Và cho tôi biết nếu nó hoạt động :) hoặc nếu bạn có bất kỳ câu hỏi nào.

Answer 2

tuyên bố từ chối trách nhiệm: đó không phải là câu trả lời đầy đủ vì tôi không có thời gian để đặt câu trả lời ngay bây giờ, tôi không vội vã trả tiền thưởng.

Tôi sẽ bắt đầu một ý tưởng cho một cách để thực hiện dò tia, điều này sẽ tạo ra một danh sách các điểm có thể nhìn thấy ở bên ngoài hình dạng của bạn.

về cơ bản cho chiếu tia, bạn theo dõi một tia từ mỗi điểm của mỗi khuôn mặt (và có thể là đường chéo), đây không phải là cách tốt nhất, nhưng điều đó sẽ xuất ra một thứ gì đó.

tia là một vector, trong trường hợp này nếu bạn đi từ x, y máy bay về bên này sang bên khác, nó sẽ có một cái gì đó như thế này [giả]

bool[,,] points = getpoints(); 
bool[,,] outsidepoints = new bool[width,height,depth]; 
//this is traceray from x,y,0 to x,y,depth 
for(int x=0;x<width;x++){ 
    for(int y=0;y<height;y++){ 
    for(int z=0;z<depth;z++){ 
     if (points[x,y,z]==true){ 
     outsidepoints[x,y,z]=true 
     z=depth;//we break the last for 
     } 
    } 
    } 
} 

làm tương tự cho tất cả 6 kết hợp trong vòng lặp cuối cùng (x = 0..width, x = width..0, y = 0..height etc ...)

sẽ hoạt động tốt nếu bạn không có phần nhô ra (ví dụ: một đĩa đơn hình dạng lồi), nếu bạn có thể bị cắt.

một khi bạn có điểm bên ngoài của bạn, bạn chỉ cần một thuật toán để làm cho họ vào hình tam giác (một cái gì đó giống như làm lát kết nối trong mỗi mặt phẳng dọc theo một trục, sau đó may cho 2 kết nối cuối cùng.)

ps: nếu những gì bạn muốn chỉ hiển thị, bạn có thể sử dụng raytracing bằng cách lấy giá trị của điểm đầu tiên kết nối với tia cho mỗi điểm hiển thị của bạn (mong đợi một hình ảnh mỗi vài giây tùy thuộc vào phần cứng và kích thước hình ảnh của bạn.) cho điều này bạn có thể sử dụng thuật toán vẽ Line (kiểm tra wikipedia, có một mẫu, trong 2d) điều tốt nhất về nó là bạn có thể trực tiếp lấy màu từ ảnh của bạn (chỉ cần thiết lập một ngưỡng mà tại đó pixel bị vô hiệu (tia đi qua))

chỉnh sửa khác: nếu bạn cần bất kỳ chính xác, chiều tôi, hoặc nhận xét xuống đây

sử dụng đi qua tia:

bool lastwasempty=true; 
for(int x=0;x<width;x++){ 
    for(int y=0;y<height;y++){ 
    for(int z=0;z<depth;z++){ 
     if (points[x,y,z]==true){ 
     if(lastwasempty){ 
      outsidepoints[x,y,z]=true 
     } 
     lastwasempty=false; 
     }else{ 
     lastwasempty=true; 
     } 
    } 
    } 
}