Marching lattice
A method and system provide for extracting an isosurface. A set of three-dimensional (3D) asymmetric sampling grids are created based on a sampling resolution and a region of interest. The set of grids cover a 3D scalar field and are tiles made up of tetrahedrons. The 3D scalar field is evaluated based on the set of 3D asymmetric sampling grids to generate a value for each tile, convert the values to cells, and assign an index to each cell. For each cell, the index is utilized to identify, in a lookup table, an enumerated tetrahedron. For each identified enumerated tetrahedron that contains an isosurface crossing, an isosurface connection is estimated between new points of edges of the identified tetrahedron. A mesh is created to connect the new points and utilized as the extracted isosurface.
1. A computer-implemented method for extracting an isosurface, comprising:
(a) creating a set of three-dimensional (3D) asymmetric sampling grids based on a sampling resolution and a region of interest, wherein:
(i) the set of 3D asymmetric sampling grids cover a 3D scalar field; and
(ii) the 3D asymmetric sampling grids comprise one or more tiles, wherein each of the one or more tiles comprises one or more tetrahedrons;
(b) evaluating the 3D scalar field based on the set of 3D asymmetric sampling grids, wherein:
(i) the evaluating generates a value for each of the one or more tiles; and
(ii) the evaluating converts the values to cells;
(iii) the evaluating assigns an index to each cell;
(c) for each cell, utilizing the cell's index to identify, in a lookup table, an enumerated tetrahedron;
(d) for each identified enumerated tetrahedron that contains an isosurface crossing, estimating an isosurface connection between new points of an edge of the identified enumerated tetrahedron;
(e) creating a mesh to connect the new points; and
(f) utilizing the mesh as the extracted isosurface.
2. The computer-implemented method of claim 1 , wherein:
the set of 3D asymmetric sampling grids comprises four (4) sampled field data grids; and
the four sampled field data grids are merged while preserving the indices.
3. The computer-implemented method of claim 1 , wherein:
all vertices that form the one or more tiles are bounded within the set of 3D asymmetric sampling grids and the indices; and
the cells are positively indexed.
4. The computer-implemented method of claim 1 , wherein:
the lookup table comprises twenty-four (24) enumerated tetrahedrons; and
the identifying of the enumerated tetrahedron is done in parallel for each enumerated tetrahedron in the lookup table.
5. The computer-implemented method of claim 1 , wherein:
the identifying of the enumerated tetrahedron and estimating are iteratively performed over three or more dimensions.
6. The computer-implemented method of claim 1 , wherein:
the one or more tiles comprise hexagonal close pack (HCP) tetrahedrons.
7. The computer-implemented method of claim 6 , wherein:
the index is based on four (4) dimensions; and
a stride between sampled points in the one or more tiles varies by dimension.
8. The computer-implemented method of claim 1 , further comprising constructing a solid out of the set of 3D asymmetric sampling grids, wherein the solid:
is space filing or tileable;
is non-self intersecting; and
has a consistent winding direction.
9. The computer-implemented method of claim 8 , wherein the solid uses all vertices of the scalar field.
10. The computer-implemented method of claim 1 , wherein each index is connected out of two or more simplex shapes.
11. A computer-implemented system for extracting an isosurface, comprising:
(a) a computer having a memory;
(b) a processor executing on the computer;
(c) the memory storing a set of instructions, wherein the set of instructions, when executed by the processor cause the processor to perform operations comprising:
(i) creating a set of three-dimensional (3D) asymmetric sampling grids based on a sampling resolution and a region of interest, wherein:
(A) the set of 3D asymmetric sampling grids cover a 3D scalar field; and
(B) the 3D asymmetric sampling grids comprise one or more tiles, wherein each of the one or more tiles comprises one or more tetrahedrons;
(ii) evaluating the 3D scalar field based on the set of 3D asymmetric sampling grids, wherein:
(A) the evaluating generates a value for each of the one or more tiles; and
(B) the evaluating converts the values to cells;
(C) the evaluating assigns an index to each cell;
(iii) for each cell, utilizing the cell's index to identify, in a lookup table, an enumerated tetrahedron;
(iv) for each identified enumerated tetrahedron that contains an isosurface crossing, estimating an isosurface connection between new points of an edge of the identified enumerated tetrahedron;
(v) creating a mesh to connect the new points; and
(vi) utilizing the mesh as the extracted isosurface.
12. The computer-implemented system of claim 11 , wherein:
the set of 3D asymmetric sampling grids comprises four (4) sampled field data grids; and
the four sampled field data grids are merged while preserving the indices.
13. The computer-implemented system of claim 11 , wherein:
all vertices that form the one or more tiles are bounded within the set of 3D asymmetric sampling grids and the indices; and
the cells are positively indexed.
14. The computer-implemented system of claim 11 , wherein:
the lookup table comprises twenty-four (24) enumerated tetrahedrons; and
the identifying of the enumerated tetrahedron is done in parallel for each enumerated tetrahedron in the lookup table.
15. The computer-implemented system of claim 11 , wherein:
the identifying of the enumerated tetrahedron and estimating are iteratively performed over three or more dimensions.
16. The computer-implemented system of claim 11 , wherein:
the one or more tiles comprise hexagonal close pack (HCP) tetrahedrons.
17. The computer-implemented system of claim 16 , wherein:
the index is based on four (4) dimensions; and
a stride between sampled points in the one or more tiles varies by dimension.
18. The computer-implemented system of claim 11 , wherein the operations further comprise constructing a solid out of the set of 3D asymmetric sampling grids, wherein the solid:
is space filing or tileable;
is non-self intersecting; and
has a consistent winding direction.
19. The computer-implemented system of claim 18 , wherein the solid uses all vertices of the scalar field.
20. The computer-implemented system of claim 11 , wherein each index is connected out of two or more simplex shapes.