Voxels and Cylinders...

This topic is 4062 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi, my problem is a quite large to explain.. i'll try :) I have a program that perform Volume Sculpting. I have a 3D matrix of voxels (or an octree). Now... My problem is this.. I have a cylinder that represent a mill. Let's suppose that at time t0 the mill intersects one or some voxels. I want understand if the cylinder intersects each voxel and how. The cylinder is represented by a normal, radius and a point (center of circonference) I have done a binary test of intersection like this: 2D example: (1 stays for voxel inside the volume, 0 for outside (cutted)) (dots are blank spaces) ............................... .....1-------1...<------ (direction of mill) .....|..........|....................... .....|..........|..|--------- (schematized mill) .....1-------1..| ....................|-------- ................................... result: .................................. ....1-------1.................... ....|..........|................... ....|.......|---------- ....1-----|-0 ............|------- My test is capable to understand if a voxel is inside/outside the cylinder and this is ok.. but i would like to know "where" the cylinder intersects each edge. The cylinder can intersect the cube with any angle of incidence. With my test i don't know the exact intersection points along the 2 edges. The only solution that comes to mind is a segment/cylinder intersection. (like ray-cylinder for raytracing). But it is quite hard to understand for me.. there could be any other solution? any suggestion?? Thank you in advice ^^

Share on other sites
One possible alternative would be to tessellate the cylinder into triangles (e.g., make a triangle mesh representation of the cylinder), then do ray/triangle intersections with the voxel edges. Its really not simpler than the segment/cylinder test....just an alternative. One way or another, to get the intersection points, you're going to have to do some segment/cylinder tests to get those points.

If your ultimate goal is to recreate a smooth surface with the trimmed voxel grid merely helping you to accelerate the intersections (which when using an octree is a great idea), then you potentially have to do more. If you want your final surface to reflect the exact trimmed cylinder shape (to simulate a woodworking router for example), then you must do more than simply look at edge/cylinder intersections. Those intersection points merely help you define trim curves. You'd have to chop a hole in the voxel, then copy a portion of the cylinder surface to fill the hole in the voxel. The intersected edges of the voxel define the trim curve around the cylinder portion, and the edge where the voxel itself has to be trimmed. To properly visualize the cylinder shape, you'd have to parameterize the trim curve in cylindrical coordinates...it'll become a polygon with curved edges...then discretize the parameterized trim curve into a faceted polygon, then triangulate that polygon in parameter space...then map the parameterized triangles back into 3D space to build the surface. If you want a smooth surface model rather than a faceted triangle mesh model, then its harder to do still. I know that is kind of a ramble of ideas, and may not be clear, but the message is that if you wish to really reproduce an accurate representation of the true cylinder cut surface, it can be quite complex and messy.

So, therefore, there is potentially a simpler approach that I would absolutely recommend to begin with, at least. If you are looking to reconstruct that surface, one way to do it is via isosurface extraction after you're done cutting. Let the cylinder kill voxels completelly...don't worry about a partially cut voxel, then when you're done cutting run a marching cubes or marching triangles algorithm to build up a surface for some nonzero voxel value. The marching triangles will build up a mesh that is smoother than the voxel grid. The mesh represents an isosurface along the boundary of the trimmed solid. Now...it will not precisely model the cylinder cuts...it'll be a visual approximation. And the approximation might not be super clean. You'd potentially want to post-process with some additional smoothing algorithm. But, to get something out that looks smoother than the trimmed voxel grid, this is more straightforward than the stuff in the prior paragraph.

I hope that helps, without confusing too much!

Share on other sites
thank you for fast answeing!

i forgot to say that i'm using a marching cubes algorithm right now. It improves smoothness over raw grid rendering but with my simple intersection test i don't know the real position of the intersection point along an edge.
This is the structure of my cube. Actually, i can't move the "e" vertices along the edges. They are in a fixed position at half the length of the edges.

Image

I wolud like to improve this algorithm moving the "e" vertices. But for doing this, i need a weight for the voxels. Now my weights are "0" or "1" without intermediate values. That's why i need a precise intersection test.

Two screens of my application :
Screen 1
Screen 2
In the first image artifacts are well visibles.

So, without a serious (and slow) edge/cylinder or cube/cylinder intersection test the only way to go is applying postprocess smoothing algorithms?

[edited by grhodes_at_work to convert URL links into gamedev friendly formats]

[Edited by - grhodes_at_work on November 1, 2007 11:57:11 AM]

Share on other sites
I see what you're trying to do now. And its a reasonable approach, with the marching cubes. So, how about this. Test each point of the voxel cube and see if it is inside the cylinder. A point that is inside receives a weight of 1, and a point that is outside receives a weight of 0. Add the 8 weights together and divide by 8. That'll give you potential voxel values of 0, 0.125, 0.25, 0.375, 0.5, 0.625, 0.75, 0.875, and 1.0. Now, this isn't perfect, since there are several cases where the same set of vertices of a voxel might be inside the cylinder while the cylinder moves around quite a bit. So, an enhancement would be that a vertex inside the cylinder receives a 1.0 only if the perpendicular distance from the the vertex to the cylinder centerline is zero...it is as far inside as it can be. And, if the vertex is inside but the perpendicular distance is equal to the radius of the cylinder (vertex is really on the surface), then it gets a weight of zero. This way, if the cylinder just barely contains one edge of the voxel, instead of jumping automatically to a voxel value of 0.25 since there are two vertices inside, you'd get a voxel value of near zero since the vertices on the contained edge are nearly touching the surface and have received a weight near zero.

I think that is a simple approach that should significantly enhance what you have.

Another approach, also simple but slower and that introduces more precision problems, would be to run a filter of some sort on the voxel grid before you run marching cubes...basically blur out the stair-stepping of the voxels after the fact.

Share on other sites
but with this technique 8 vertices gives weight to a single vertex. Right?
If i understood well there is a loss of precision.

How to figure marching cubes in the combination of this example?

example

Share on other sites
My understanding was that you are assigning to each voxel a value of exactly 0 or exactly 1, with no intermediate values until you ran marching cubes...the intermediate values were only occurring in the marching cubes. I was trying to describe a way that you could assign intermediate values to the voxel, and without having to explicitly compute the edge/cylinder intersections or something else more complex. 8 vertices gives a weight to a single voxel. So, in your example, the interior weight would be:

(1/8) * (.75 + .75 + 1 + 1 + .5 + .5 + 1 + .875) = 0.796875

Share on other sites
Yeah, i have only 0 or 1 values for voxels. Maybe the example is a bit confusing.. The cube on the right is composed by 8 smaller cubes with values = number written on the relative vertex (applying the sum described by you).

But after every voxel is weighted (by sum), i have 3 collections of voxels: those that are 0, 1 and 0<x<1.
The last group is composed by surface voxels. But during MC i must choose a value for isosurface extraction (by default is 0.5). What value i must choose beetwen 0 and 1? For example if i have an edge with 2 vertices, one at 0.7 and the other at 1, what point i select for extraction?

Sorry, maybe this question is rather trivial for you, but i'm rather new to solid modeling and volume sculpting :)

Share on other sites
Don't apologize! Its not actually a trivial question. Interpolation issues can be quite subtle indeed, even when you have vast experience (which I most certainly do not in this case!).

I think you should use just one isosurface extraction value throughout your MC run. If you try and vary the value, I believe you're going to end up with a million little special case...well, at least several, and it'll be impossible to get results that are generally good for different configurations.

Now, a value of 0.5 is probably going to give you the smoothest surface possible....for a case where the voxels can only be 0 or 1. Reason is this. If you choose an isosurface value of 1, you will get only triangles that belong to voxel==1 faces...stair-stepping. If you choose an isosurface value of 0, you will get only triangles that do not touch any voxel==1 face. Again, it'll be stair-stepping. So, 0.5 is the furthest thing you can get from two stair-stepping results. If I were you, I would try to assigned values to voxels that are not just 0 and 1. Perhaps using my approach, perhaps not.

For your example, if you have an edge where the vertices are 0.7 and 1, then if your isosurface value is 0.5, you simply do not produce a triangle that touches that edge.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• Forum Statistics

• Total Topics
633736
• Total Posts
3013598
×