2
$\begingroup$

I have a mesh which represents a 0-genus model. My goal is to construct a homeomorphism from that mesh to its bounding sphere.

I'm trying to understand a paragraph in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.2762&rep=rep1&type=pdf :

The basic idea of [the algorithms to project a 0-genus mesh on the sphere, referred below] is to let the object grow towards its convex hull and then project it directly onto the sphere. [...]

In our implementation we use a variation of this principle. We first compute a voxelization of the given model. The gradient of the corresponding volumetric distance function is then used to guide the vertices of the given mesh towards a convex configuration. This process can be considered as some kind of ”inverse” deformable surface technique.

Here is the link to the article it cites: http://design.osu.edu/carlson/history/PDFs/shape-kent.pdf

Can someone please explain me:

  1. How to compute a voxelization of a given model ?
  2. What is the "corresponding volumetric distance function" ?
  3. How to use its gradient to "guide the vertices of the given mesh to a convex configuration" ?

Once we've got a "convex configuration", projection on the sphere is easy.

Any open source implementation is welcome.

$\endgroup$
3
$\begingroup$

Here are some elements of answers to the three questions and references to alternative methods for spherical parameterization:

1. How to compute a voxelization of a given model ?

What it means: It means embedding your surface into a 3D voxel grids, and determining which voxels have an intersection with some triangles of the surface.

How to do that: There are several methods to do that, the simplest one is for each triangle, iterating on the voxels inside the bounding box of the triangle, and testing for each voxel whether it has an intersection with the triangle. More sophisticated implementations can use the GPU, that is well suited to this kind of things [1]. It is also possible to use some variants of the Bresenham algorithm [2] to "rasterize" the triangles in 3D.

2. Computing the distance function

What it means: Starting from a voxel grid with voxels that are either empty or that have an intersection with the surface (obtained at step 1.), populate each empty voxel with the distance between its center and the surface.

How to do that: There is an efficient algorithm (see survey in [3]) that operates by several "sweepings" over the volume, it is quite easy to implement and very efficient.

3. Using the gradients to guide the vertices of the mesh to a convex configuration This means solving an evolution equation that will morph the initial surface to a convex surface. The evolution equation uses at each step the gradient of the distance to the initial surface.

Alternatives for spherical parameterization There are other methods that you may use. On the theory side, the approach in [5] is elegant (but probably difficult to implement). If you want a method that is as simple as possible, cut your mesh into two halves and parameterize each half using planar Tutte/Floater parameterization [6] then glue the halves. You can then further optimize the mapping to make the seam between the halves disappear. There is an implementation of this approach in my graphite software [7]

References:

[1] https://developer.nvidia.com/content/basics-gpu-voxelization

[2] https://stackoverflow.com/questions/21663613/triangle-rasterization-bresenhams-in-3d

[3] 3D distance fields: a survey of techniques and applications, Jones et.al, IEEE Trans. on Vis. and Computer Graphics, 2006

[4] math.nyu.edu/~bkleiner/mean_convex_flow.pdf

[5] Fundamentals of spherical parameterization, Gotsmann et.al, ACM Siggraph 2003

[6] Parameterization and smooth approximation of surface triangulations, Floater, 1996

[7] Implementation of spherical parameterization in Graphite ver. 2. https://gforge.inria.fr/frs/download.php/file/33290/Graphite-2-a6.tar.bz2, src/packages/OGF/parameterizer/algos/spherical_stretch_map_parameterizer.h,.cpp

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.