isosurface tracking in high dimensions

Question

how to trace isosurface on a higher dimensional space efficiently

Answer 1

You have a scalar cost function in N dimensions,

f(y₀, y₁, .., y_N) ∊ ℝ,   y ∊ ℝ

but sampled only in a regular rectangular grid,

y_k = Ψ_k + ψ_k x_k,   constants Ψ_k ∊ ℝ and ψ_k ∊ ℝ, and grid coordinates x_k ∊ ℕ

and the problem is to locate the isosurface(s) i,

f(y₀, y₁, .., y_N) = C_i

The direct approach would be to just loop over each cell in the grid, and check if the current isosurface intersects the current cell, and if so, describe the part of the isosurface within the current cell. (Marching Cubes is one approach to describing how the isosurface intersects each grid cell.)

The restriction here is to use a neighborhood based search instead of examining every single cell.

OP had a previous question specifically for the 3D case, to which I posted a link to example code, grid.h and grid.c (at Pastebin.com, because they were too long to include inline).

That implementation is completely different to OP's slicing method. Mine is a direct, simple walk over the grid cells intersecting the current isosurface. It caches the grid samples, and uses a separate map (one char per grid cell) to keep track which grid cells have been cached, walked, and/or pushed to a stack to be walked later. This approach is easily extended to more than three dimensions. Although the code is written for exactly three dimensions, the approach itself is not specific to three dimensions at all; all you need to do is to adjust the data structures to accommodate any (sensible) number of dimensions.

The isosurface walk itself is trivial. You start from any grid cell the isosurface intersects, then examine all 2N nearest neighbor cells to see if the isosurface intersects those too. In practice, you use a stack of grid cell locations to be examined, and a map of grid cell flags to avoid re-examining already examined grid cells.

Because the number of grid point samples per grid cell is 2N, my example code is not optimal: a lot of nearby grid points end up being evaluated to see if the neighboring grid cells do intersect the isosurface. (Instead of examining only the grid points delimiting the isosurface, grid points belonging to any grid cells surrounding the isosurface are examined.) This extra work grows exponentially as N increases.

A better approach would be to consider each of the 2N possible (N-1)-faces separately, to avoid examining cells the isosurface does not intersect at all.

In an N-dimensional regular rectangular grid, each cell is an N-dimensional cuboid, defined by the 2^N grid points at the vertices (corners). The N-cuboid cells have N(N-1) two-dimensional faces, and 2N (N-1)-dimensional faces.

To examine each (N-1)-face, you need to examine the cost function at the 2^N-1 grid points defining that (N-1)-face. If the cost function at those points spans the isosurface value, then the isosurface intersects the (N-1)-face, and the isosurface intersects the next grid cell in that direction also.

There are two (N-1)-faces perpendicular to each axis. If the isosurface intersects the (N-1)-face closer to negative infinity, then the isosurface intersects the next grid cell along that axis towards negative infinity too. Similarly, if the isosurface intersects the (N-1)-face closer to positive infinity, then it also intersects the next grid cell along that axis towards positive infinity too. Thus, the (N-1)-faces are perfect for deciding which neighboring cells should be examined or not. This is true because the (N-1)-face is exactly the set of grid points the two cells share.

I'm very hesitant to provide example C code, because the example code of the same approach for the 3D case does not seem to have helped anyone thus far. I fear a longer explanation with 2- and 3-dimensional example images for illustration would be needed to describe the approach in easily understandable terms; and without a firm grasp of the logic, any example code would just look like gobbledygook.

Answer 2

You are better using a library for 2 dimension you can try the conrec algorithm from Prof. Paul Bourke. It's similar to a marching cube.