Algorithm to build a surface out of points

[Plyskeen]

Hello everyone,

I am just trying to build a surface out a set of points which are part of a 3D-grid, and I am trying to figure out how to build a surface around that set of points, so the user of the program can see what the boundary is.
Is there any kind of algorithm that makes that? I have been trying with some test but they fail to cover all the "surface" or just use too much polygons (or CPU time).

Thanks in advance!

[samv]

Can you be more specific about what you mean by a) "a surface around that set of points" and b) "points which are part of a 3D-grid"?

a) leaves unclear if you mean constructing a surface so that all points are on said surface, or constructing a convex hull of the points.

b) implies that you have some information about the structure of the points, which is pretty important in the choice of algorithm.

[Plyskeen]

Sorry, I knew that it will be difficut to explain.
The thing is:

I have a 3D grid, with a scalar value for each point in that mesh (For example, temperature in each point). Then, I set a threshold, because I want to focus in the points with that value or higher in their corresponding scalar values (that is, the points with that temperature or higher). Since drawing the "volume" of all the points will suppose too much polygons, I want to represent the surface (could be more than one) of the volume formed by the points of the desired threshold or higher. (For example "temperature higher than 60 degrees"). I suppose that I have to build a isosurface, and all the data that I have is:

- The points (both coordinates and the scalar value, I have already managed to "pick" only the points in the frontier of the "volume")
- The distance between the points (It's a fixed value in the grid)

The idea is that the points in the frontier will form part of the surface, but if there is an efficient and accurate "wrapping" "around" the points, that would be useful too, if it gives the user an idea about where the "temperature" is higher than the desired threshold.

Thanks again!

[Overmind]

If the points are layed out in a regular grid, you can use the "marching cubes" algorithm. It's a bit hard to describe, but I'm sure google will find a lot of tutorials...

[-NiCo-]

You could try this:

quadlist=empty
For each 3D pixel
    If pixelvalue >= Treshold
        For each direct neighbour of that pixel
            If neighbourvalue < Treshold
                Add shared cubeside of pixel and neighbour to quadlist
            End
        End
    End
End

Nico

[Plyskeen]

Oooops, I thought that the marching cubes algorithm was only functional if you know exactly what the surface was (and you were only drawing it). I will check it again.

And about the code, the problem is that I am trying to build a (hopefully) smooth surface. I have already tried using cubes (and rectangles perpendicular to the user, which supposed less polygons to draw), and I have not been satisfied with the results (too few frames per second and a pixelated-looking surface).

Thanks a lot!!

[-NiCo-]

The pixelated-looking effect can easily be remedied by assigning a normal to each vertex which is the average of the normals of the connected cubesides. Then apply some Gouraud or Phong lighting model when drawing.

What's the resolution of your 3D grid?

Nico

[Overmind]

The marching cubes algorithm is basically the same as Nicos code, but with the difference that the surface is not only drawn at the cube boundaries, but through the cube, at the location where the surface should be, based on the values at the cubes corners. This solves the "pixelated" looking effect.

For example, if you have a treshold of 1.0, and one corner of the cube has the value 0.7 and another one 1.1, the surface vertex should be placed at 3/4 of the edge (that's where the value of 1.0 is, assuming linear interpolation between the corners). The marching cubes algorithm is a generalisation of this to 3 dimensions.

[Plyskeen]

Right now I am working with a 161x161x183 grid with its points separated by a 0.05 distance; but the idea is applying later the same code to smaller grid, about 48x48x60, and with a distance of about 0.08-0.09.

And the tests that I tried, had been drawing one cube or rectangle in each of the frontier points, just to make an assesment of the frames per second / quality of the image. I will try Nico's code later!

[gumby]

You can volume render your data, using a transfer function to highlight the values you are interested in...