Cụm từ thông dụng trên không gian voxel

Question

Có cách nào mô tả một đối tượng một cách lỏng lẻo (thông qua mẫu phù hợp với automata hữu hạn) trong lưới 3d voxel giống như cách chúng ta có thể mô tả một cách lỏng lẻo các chuỗi một chiều với regexp không?

Giả sử tôi muốn mô tả một hình khối voxels "A" với mặt dưới bao gồm voxels "B" hoặc "C" với chiều cao 3 và chiều rộng 5 và khớp mô tả này với trường voxel để tìm ví dụ về mẫu. Tôi có thể làm một số tìm kiếm cho các mô hình chính xác (loại-of-như-Boyer-Moore-in-3D) nhưng tôi cần phải xác định kích thước biến cho một số đối tượng (như chiều dài biến cho cuboid nói trên).

Answer 1

Tôi không biết nhiều về 3D hoặc voxels, nhưng nếu bạn có thể chuyển đổi không gian 3D của mình thành biểu diễn một chiều bằng cách đánh dấu, thì bạn có thể sử dụng regex trên đó.

Giản dụ:

Đối với một khối lập phương với một khuôn mặt màu xanh, đỏ mặt, mặt xanh, và 3 người khác chúng ta không quan tâm đến:

<object> 
    <cube> 
     <faces> 
      <face orientation="up" color="blue"> 
       <border neighborOrient="west"> 
       <border neighborOrient="south"> 
      <face orientation="west" color="red"> 
      <face orientation="south" color="green"> 
      ... 
     </faces> 
    </cube> 
</object> 

regex của bạn có thể tìm kiếm những gương mặt trong cùng một khối lập phương có chung đường viền. Regexes làm việc tốt nhất với văn bản, vì vậy bước đầu tiên của bạn nên là tìm cách "làm phẳng" xuống văn bản.

Answer 2

Cụm từ thông dụng là cách nhỏ gọn để thể hiện cú pháp của một nhóm ngôn ngữ có giới hạn (và vẫn vô hạn). Với các biểu thức thông thường, bạn không cần phải biết nơi cần tìm biểu tượng tiếp theo, vì nó được biết rằng bạn đang làm việc trên một chuỗi và lặp qua các ký tự của nó để lấy chúng làm biểu tượng của ngôn ngữ ... nhưng trong 3D, bạn sẽ cần phải nói cách nào để đi.

Bạn có thể nghĩ về nó như một máy 3D Turing, đó là một máy Turing có trạng thái bên trong và có thể đọc các biểu tượng từ một "băng" 3D, vì chúng tôi chỉ xác minh chúng ta bỏ qua việc ghi vào băng. Sau đó, máy Turing này sẽ đi bộ 3D "băng" aka lưới voxel 3D và đọc voxels như biểu tượng, sau khi đọc từng biểu tượng trạng thái bên trong của máy Turing sẽ thay đổi theo luật nhất định. Khi việc thực hiện kết thúc trạng thái cuối cùng của máy, hãy cho bạn biết đó có phải là kết quả trùng khớp hay không. Bây giờ những luật này trong Kiến trúc Von Newman là một cách giải thích dữ liệu từ băng như hướng dẫn, nhưng chúng tôi muốn có kiến ​​trúc Harvard, đó là các hướng dẫn được tách ra khỏi dữ liệu. Bây giờ những gì bạn muốn là một cách để mô tả những hướng dẫn cho máy Turing. [Bạn có thể nghĩ đây là con rùa của Logo nhưng trong 3D].

Theo tinh thần của cụm từ thông dụng, chúng tôi muốn có ngôn ngữ giống với cấu trúc thực tế hơn. Nếu chúng ta làm cho nó văn bản dựa nó sẽ là một ngôn ngữ mô tả (vì là một mệnh lệnh là không tốt hơn so với Turing yêu thích của bạn hoàn thành một), nó sẽ phải nói ví dụ (bằng tiếng Anh):

There is a voxel type A and then moving (x1, y1, z1) from that there is a voxel of type B or C and then moving (x2, y2, z3) from that there is a voxel type D 

này mô tả những gì máy Turing đang tìm kiếm, với một thuật toán backtracking kiểm tra tất cả các trận đấu tiềm năng nó sẽ hoạt động như mong đợi.

Xin lưu ý rằng tôi không biết tập hợp các giá trị có thể có của voxels. Đó là, tôi không biết bảng chữ cái. Vì vậy, tôi đã chỉ nói loại A, loại B, loại C và loại D là ví dụ, một trong những người có thể là đại diện của không voxel, và những người khác có thể là màu sắc hoặc bất cứ điều gì bạn đang sử dụng. Có thể có nhiều loại voxels khi cần thiết. Nếu loại voxel phức tạp thì mô tả của nó sẽ được chèn vào đó.

Tôi đã nghĩ về cách sử dụng thực tế loại ngôn ngữ và một vấn đề phát sinh rất nhanh là xoay vòng, tôi phải quyết định rằng ba voxels loại A trên trục X được coi là giống nhau ba loại voxels A trên Trục Z, tốt hơn là cho phép mô tả bằng ngôn ngữ đó.

Bây giờ nó rất giống với mô tả đường dẫn nếu voxels là nút, tôi đã thực hiện ngôn ngữ để mô tả đường dẫn 2D như một phần của dự án riêng tư (để lưu trữ chúng trong cơ sở dữ liệu, xem hình ...), nó rất đơn giản, nó dự trữ một ký tự cho mọi hướng và sử dụng một số cho các bước, ví dụ: "2d5l1u". Làm tương tự cho 3D và thêm một cách để nhóm và kết hợp sẽ làm. Để giải quyết vấn đề xoay, nó sẽ là cần thiết để mở rộng hướng để cho phép disjunctions để thể hiện các cấu hình thay thế cho trận đấu. Điều này sẽ trở nên rõ ràng hơn trên một số ví dụ về cách nó có thể hoạt động mà tôi đã nghĩ đến (Tôi đã không làm việc một cú pháp chính thức trong EBNF hoặc tương tự):

Phù hợp với một dòng ba loại voxels A trên trục X:

(A1X){3} 

Ở đây tôi đang xen phù hợp với "A" với phong trào "1X", sử dụng dấu ngoặc đơn "(" và ")" cho nhóm và các dấu ngoặc nhọn "{" và "}" để định lượng. Đây unrolls này:

A1XA1XA1X 

cuối cùng "1X" không ảnh hưởng đến kết quả, vì vậy nó có thể cũng là:

A1XA1XA 

Và nó nói rõ: Phù hợp với một loại A voxel, di chuyển 1 trên X và khớp với loại A voxel, di chuyển 1 trên X và khớp với loại A voxel.

Matching một dòng của ba voxels loại A trên trục X hoặc trục Z:

(A1X){3}|(A1Z){3} 

Alternative:

(A1[X|Z]){3} 

Ở đây tôi sử dụng dấu ngoặc "[" và "]" để làm cho một 'lớp', vị trí của nó cho biết đó là về hướng và nó chỉ bao gồm trục có thể, không nhầm lẫn với:

[(A1X)|(A1Z)]{3} 

Điều này sẽ phù hợp với ba voxels loại A nhưng chúng có thể không nằm trên cùng một trục, chúng chỉ được tiếp giáp và chia sẻ trục X hoặc trục Z với hàng xóm.

Matching một bộ 3x3 kiểu voxels một trong những máy bay X, Y:

(((A1X){3})1Y){3} 

này phù hợp với dòng trên trục X và di chuyển 1 trên trục Y để phù hợp với nhau và vân vân. Nó ngụ ý rằng sau khi nhóm lại một sự lặp lại "([(A1X)] {16})", chúng ta quay lại nơi trận đấu bắt đầu thực hiện bước di chuyển sau "1Y". Để hủy đăng ký, sẽ là:

(A1XA1XA1X)1Y(A1XA1XA1X)1Y(A1XA1XA1X)1Y 

Xem dấu ngoặc đơn còn lại, những phương tiện đó để quay lại nơi bắt đầu trận đấu. Vì vậy, chương trình sẽ kiểm tra những gì bên trong của nhóm và khi nó được thực hiện nó sẽ quay trở lại nơi nó đã được trước khi vào nhóm và tiếp tục thực hiện sau khi nó.

Matching một cặp loại voxels Một cách nhau bởi một voxel loại bỏ qua (trên bất kỳ trục): ""

A1(X|Y|Z).1(X|Y|Z)A1(X|Y|Z) 

Bị ảnh hưởng bởi biểu thức thông thường chúng ta sử dụng dấu chấm để đại diện cho bất kỳ loại voxel nào.

Tôi vẫn không quyết định xem có nên sử dụng các giá trị âm tốt hơn là sử dụng các chữ cái khác cho trục khác hay không, tôi cũng cho rằng số 1 có thể là tùy chọn. Ngoài ra các phần khác của cú pháp của cụm từ thông dụng như "+", "*" và "?" trở nên cẩn thận hơn. Nó có thể là tốt để thực thi "{" và "}" cho bất kỳ định lượng nào cho đến khi được chứng minh rằng không có sự mơ hồ.

Như bạn có thể thấy nó sẽ không là một vấn đề để thêm một hướng chuyển động hoặc hoàn toàn khác trục, vì vậy cổng này rất tốt để nói bốn khía cạnh, như trong:

(A1[X|Y|Z|W]){3} 

Nó cũng có thể tốt để sử dụng dấu chấm "." để đại diện cho bất kỳ hướng:

(A1.){3} 

Có một vấn đề với giả định bất kỳ hướng khi không quy định và đó là ngôn ngữ này được định nghĩa để xác định một hướng là gì và phân biệt với các loại voxel dựa trên vị trí bên trong biểu hiện. Vì vậy, "(A1B1) {3}" sẽ không ánh xạ tới "(A1.B1.) {3}" bởi vì nó sẽ lấy "B" làm hướng di chuyển, có thể suy ra ý nghĩa của số thứ tự tại kết thúc, nhưng tôi không biết liệu nó có rõ ràng không.

Cuối cùng này sẽ phù hợp với bất kỳ mảnh Tetris hợp lệ trong mặt phẳng X, Y làm bằng voxels loại A:

(A1[X|Y]){4} 

Nếu chúng ta giả định rằng thế giới chỉ là hai chiều và chúng tôi cho phép bỏ qua các số một, nó giảm xuống còn:

(A.){4} 

Và tôi hài lòng với điều đó. Tuy nhiên, bạn nên xem xét một ký pháp phức tạp hơn, ít gọn hơn và dễ đọc hơn đối với các cấu trúc phức tạp.

Và đó là lý thuyết của tôi để khái quát biểu thức chính quy thành hai, ba hoặc nhiều thứ nguyên.

EDIT:

Nếu loại voxel là phức tạp hoặc gây ra sự mơ hồ Tôi đề nghị để viết nó với dấu ngoặc góc "<" và ">", ví dụ như vậy bạn có thể sử dụng giá trị hex của nguyên dữ liệu voxel:

(<0088FF>.){4}