Marching Cubes
Marching Cubes
 |
 |
 |
 |
 |
This program uses brute force to analyze a .vol file and display the results based on a "weight factor". First thing a little
back ground, this technique is used to visualize medical data such as CT, X-Ray, MRI, ect. The files are so huge that they
require a special format just store the data. The reason they are so huge is because distance between the points sampled
is microscopic. The object in the screen shots above is called a "bucky ball" (I'm not sure why) but it's a nickname for the
carbon 64 atom. Yep, atom. So, we are talking about millions of points.
Ok, a little bit about the algorithm. I have to assume everyone knows a little about interpolation. If not I will go over the
concept real quick. It starts with two points. We know everything about these two points because they are discrete. Since,
the distance between any two points is not discrete, we need to a way to get a close approximation with out storing a lot
of extra data. The way we approximation the distance is ...
linear interpolation ( [(1 - t) * pt1 + t * pt2] where 0 <= t <= 1)
the closer t is to 0 the smaller the distance from pt1. Marching Cubes starts with this basic case but now we need to find
the distance to a certain point between the original points.
Marching Cubes depends on a value set by us. This value is treated like a density, where we want to see everything that is
higher or equal to our value. The first thing we do is compare the eight points next to each other that form a cube and see
which points are with in the "density" we are looking for. Once, we know which points are in side and which points are out
side we interpolate to find the point were the “density” crosses between two points. The “density” will only cross between
a point in and a point out. By connecting these interpolated points we form triangles. Based on this there are 15 different
base combinations of points in a cube. There are another 15 by inflection of the points in and out of the density. Three
points in will produce the same configuration as 7 points in. Also, there are two trivial cases all points are in and all points
are out. This gives us a grand total of 32 base combinations of points in and out of a surface. All 32 combinations must be
accounted for in the Marching Cubes implementation. Beyond the base configuration I have identified a couple more unique
cases. When all the cases are accounted we are more likely to get a "closed" surface, as long as the sampled surface
was closed.
back ground, this technique is used to visualize medical data such as CT, X-Ray, MRI, ect. The files are so huge that they
require a special format just store the data. The reason they are so huge is because distance between the points sampled
is microscopic. The object in the screen shots above is called a "bucky ball" (I'm not sure why) but it's a nickname for the
carbon 64 atom. Yep, atom. So, we are talking about millions of points.
Ok, a little bit about the algorithm. I have to assume everyone knows a little about interpolation. If not I will go over the
concept real quick. It starts with two points. We know everything about these two points because they are discrete. Since,
the distance between any two points is not discrete, we need to a way to get a close approximation with out storing a lot
of extra data. The way we approximation the distance is ...
linear interpolation ( [(1 - t) * pt1 + t * pt2] where 0 <= t <= 1)
the closer t is to 0 the smaller the distance from pt1. Marching Cubes starts with this basic case but now we need to find
the distance to a certain point between the original points.
Marching Cubes depends on a value set by us. This value is treated like a density, where we want to see everything that is
higher or equal to our value. The first thing we do is compare the eight points next to each other that form a cube and see
which points are with in the "density" we are looking for. Once, we know which points are in side and which points are out
side we interpolate to find the point were the “density” crosses between two points. The “density” will only cross between
a point in and a point out. By connecting these interpolated points we form triangles. Based on this there are 15 different
base combinations of points in a cube. There are another 15 by inflection of the points in and out of the density. Three
points in will produce the same configuration as 7 points in. Also, there are two trivial cases all points are in and all points
are out. This gives us a grand total of 32 base combinations of points in and out of a surface. All 32 combinations must be
accounted for in the Marching Cubes implementation. Beyond the base configuration I have identified a couple more unique
cases. When all the cases are accounted we are more likely to get a "closed" surface, as long as the sampled surface
was closed.
| Features |
- User defined "Weight Factor"
- Number of Faces displayed
- Toggle Axis
- Toggle wire frame
- Loading .vol files
- Camera: left button rotates, right button zooms
| Future revisions |
- Adding a data structure
- Adding Gouraud shading
- Adding saving to Off file format
This project was done for a presentation on the Marching Cubes algorithm. I decided to leave out a data structure because I
wanted it to run as fast as possible. Since, I am not using a data structure I can not calculate the vertexes star which I need
for Gouraud shading.
I used MFC as a framework to handle the system events and provide nice windows based features. The project uses the
standard single view/doc architecture. I used openGL as the graphics API.
wanted it to run as fast as possible. Since, I am not using a data structure I can not calculate the vertexes star which I need
for Gouraud shading.
I used MFC as a framework to handle the system events and provide nice windows based features. The project uses the
standard single view/doc architecture. I used openGL as the graphics API.
| Comments |