Sign in to follow this  

converting a polygon mesh to volume grid

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

As per my understanding a polygonal mesh is hollow inside ( no vertices and no edges inside). It has only vertices and edges at the surface . Where as volume grid contain vertices both inside and outside. But in one of the articles, related to LOD, mentioning techniques for converting a polygon mesh to volume grid. Is it possible to convert? If yes, what are they referring. How is it possible to convert to Volume grid. Regards Renganath Rajesh

Share this post


Link to post
Share on other sites
That would be pretty simple. Compute the bounding box of the mesh, pick some arbitrary grid resolution, and then iterate over all the points in that 3d volume (eg, voxels). For each point, check if the point is inside or outside the mesh; and, for optional added quality, compute the distance to the mesh..to use for 3d "aliasing". To determine if a given point is inside the mesh, off the top of my head, you could find the closest triangle to that point and see if it is not on the normal side of that triangle. That probably doesn't work in all cases but you get the idea.

Share this post


Link to post
Share on other sites
Quote:
Original post by yahastu
That would be pretty simple. Compute the bounding box of the mesh, pick some arbitrary grid resolution, and then iterate over all the points in that 3d volume (eg, voxels)..


I understood the bounding box concept. But how to create 3d volume. Because Bounding Box has min and max values of bounds. How to convert this Bounding Box into 3D Volume ( voxels).Could you please explain.


Quote:
]Original post by yahastu
For each point, check if the point is inside or outside the mesh;
..

The Checking concept I understood. Although the checking method is not simple to implement.

[quote]]Original post by yahastu
and, for optional added quality, compute the distance to the mesh..to use for 3d "aliasing".[quote].
What do you mean by 3d aliasing.

Thanks a lot for informing. I understood the basic concept of constructing a Volume Grid.

Regards
Renganath Rajesh


Share this post


Link to post
Share on other sites
NVidia gave a presentation at siggraph this year about using the GPU to performe voxelization, download it here.
Might be overkill to use GPU but could give you some hints.

Share this post


Link to post
Share on other sites
Quote:
Original post by rajesh_nest
I understood the bounding box concept. But how to create 3d volume. Because Bounding Box has min and max values of bounds. How to convert this Bounding Box into 3D Volume ( voxels).Could you please explain.


A volume shape is nothing more than a 3 dimensional matrix...so if you split your 3D region into small cubes, each cube is a voxel and represents a small area of space. The value of that voxel represents the "density of object" at that location, so 0 = not part of object, 1 = inside of object, and anything inbetween represents the percentage of the grid cell that overlaps the object.

Share this post


Link to post
Share on other sites
I would suggest another approach. Testing if each voxel lies inside or outside the polygon-mesh is not always trivial and may produce errors for non-closed geometry.

Its much simpler and more efficient to write a real 3D-rasterizer, which writes textured triangles to the volume data. Doing so, its not a problem dealing with a polygon soup - also the data is very compression friendly, as there will be lots of empty space.

If you want a solid object at the end, you can apply flood-fill.
Also I guess this method might be very fast, as you dont need any raycasting - you get the result instantly.

Share this post


Link to post
Share on other sites
Quote:
Its much simpler and more efficient to write a real 3D-rasterizer, which writes textured triangles to the volume data.

I've actually implemented this in the past and as you say it's really simple to raterize a triangle (if you're not to worried about performance).
The SIMPLEST way in my opinion is to use a recursive approach:

struct Vertex
{
Vertex(const Vec3& position, const Vec3& normal, const Vec2& uv) : m_position(position), m_normal(normal), m_uv(uv)
{
}
Vertex(const Vertex& v) : m_position(v.m_position), m_normal(v.m_normal), m_uv(v.m_uv)
{
}
Vertex(const Vertex& v0, const Vertex& v1) : m_position((v0.m_position + v1.m_position) * 0.5f), m_uv((v0.m_uv + v1.m_uv) * 0.5f)
{
m_normal = (((v0.m_normal + v1.m_normal) * 0.5f)).normal(); // Normalizes the normal at each subdivision step
}
Vec3 m_position;
Vec3 m_normal;
Vec2 m_uv;
};


class VolumeRenderer
{
public:
void rasterize(const Vertex& a, const Vertex& b, const Vertex& c)
{
const float lab = (a.m_position - b.m_position).sqrLen();
const float lac = (a.m_position - c.m_position).sqrLen();
if ((lab < 0.5f) && (lac < 0.5f)){ // TODO: Modify threshold to get better results?
plot(a); // a, b, c should map to the same voxel, but it might be a better idea to plot the center of a, b,c or the four points: a, b, c and center(a, b, c)
return;
}
const Vertex ab(a, b);
const Vertex ac(a, c);
const Vertex bc(b, c);
rasterize(a, ab, ac);
rasterize(b, bc, ab);
rasterize(c, ac, bc);
rasterize(ab, bc, ac);
}
virtual void plot(const Vertex& v) = 0; // TODO: Implement
};





As for flood filling the interior this isn't that simple actually.
A standard flood fill uses recursion and that could easily result in a stack overflow (especially with volume fills).
Secondly one must consider what color to use at each voxel, if you use a uniform color the risk is that the volume render "misses" the shell with correct color and you get noise.
Granted this is a problem caused by a bad volume renderer but could be hard to avoid (if your aiming at high performance for instance).
Another example where you need to consider fill color is if your application can "drill" i.e remove voxel data interactively.
There are ways to color the points based on an interpolation of the nearest filled voxels but it makes things a bit harder..

Disclaimer: I haven't actually tried the code above it's just there to serve as an example of how simple a ratserizer could be when there's no need for super speed.

Share this post


Link to post
Share on other sites
Just off the top of my head, wouldn't you get fine "rasterizing" results by starting with an "empty" cube, and then for each polygon, toggle the fill of all the voxels "behind" the polygon (use the normal vector).

Quick and dirty mental run of that seems to work for both convex and non-convex shapes... don't take my word for it without testing, though.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wyrframe
Just off the top of my head, wouldn't you get fine "rasterizing" results by starting with an "empty" cube, and then for each polygon, toggle the fill of all the voxels "behind" the polygon (use the normal vector).

Quick and dirty mental run of that seems to work for both convex and non-convex shapes... don't take my word for it without testing, though.


Yes, I also guess this might work. However, a problem that remains is how to avoid errors in case of a non-closed mesh..

Perhaps using 2 bits for each voxel helps, 1 bit for set/unset and one to state weather behind its in or ouside the object. (In one direction, lets say x).

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this