Has anyone tried Morse smale complex on triangular mesh.
I am trying to implement Quadrangulation algorithm described in the paper My link
This algorithm is based on Quadrangular patch construction based on Morse smale complex.
How difficult is to implement the algorithm on triangular meshes?
Morse smale complex
Hi!
Can you please elaborate a little more on what you’re planning to do? I'm not sure I understand your question.
You like to compute the morse smale complex on a triangular mesh, right? Do you have a scalar or vector field defined on the mesh?
I think this won't work for scalar fields… if you define a scalar field on a triangle mesh you won’t have isolated critical points, in fact you have critical ‘lines’.
Assume you have a triangle with the vertices v0, v1 and v2. At these vertices the scalar entries s0, s1 and s2 are defined. Wlog we set s0<0 and s1,s2>0. Now the edges s0,s1 and s0,s2 will both have somewhere the zero-crossing. Interpolation gives you now a critical line between those two zero-crossings. Single exception to that is the case, when a vertex has the scalar value of zero. Then you would have an isolated critical point.
Or are you working with two-dimensional velocity fields on the mesh (tangential flow so to say)? Then, of course, you can find up to one critical point in each triangle. The critical point can be found by barycentric interpolation.
Then, you have to classify the critical points by analyzing the eigenvalues of the Jacobian (when using velocity fields) or the Hessian (when using scalar fields).
Afterwards you integrate (the gradient field on scalar fields or simply the velocity field) starting from saddles and keep track of which sinks and sources you hit. For sources integrate forwards, for sinks integrate backwards. You should read on feature flow fields if you want to make this search stable.
Well, and then you can more or less read your morse smale complex, since it’s by definition a quadrangle of saddle, sink, saddle, source. But beware of degenerated cases, where you visit the same saddle twice.
I guess I need a little more information on what you’re planning to do, to help you out more…
Can you please elaborate a little more on what you’re planning to do? I'm not sure I understand your question.
You like to compute the morse smale complex on a triangular mesh, right? Do you have a scalar or vector field defined on the mesh?
I think this won't work for scalar fields… if you define a scalar field on a triangle mesh you won’t have isolated critical points, in fact you have critical ‘lines’.
Assume you have a triangle with the vertices v0, v1 and v2. At these vertices the scalar entries s0, s1 and s2 are defined. Wlog we set s0<0 and s1,s2>0. Now the edges s0,s1 and s0,s2 will both have somewhere the zero-crossing. Interpolation gives you now a critical line between those two zero-crossings. Single exception to that is the case, when a vertex has the scalar value of zero. Then you would have an isolated critical point.
Or are you working with two-dimensional velocity fields on the mesh (tangential flow so to say)? Then, of course, you can find up to one critical point in each triangle. The critical point can be found by barycentric interpolation.
Then, you have to classify the critical points by analyzing the eigenvalues of the Jacobian (when using velocity fields) or the Hessian (when using scalar fields).
Afterwards you integrate (the gradient field on scalar fields or simply the velocity field) starting from saddles and keep track of which sinks and sources you hit. For sources integrate forwards, for sinks integrate backwards. You should read on feature flow fields if you want to make this search stable.
Well, and then you can more or less read your morse smale complex, since it’s by definition a quadrangle of saddle, sink, saddle, source. But beware of degenerated cases, where you visit the same saddle twice.
I guess I need a little more information on what you’re planning to do, to help you out more…
Author
The paper I was referring is Spectral surface quadrangulation.
1. How do I compute saddles from a given triangular mesh, given scalar values at vertices.
2. From the saddles, how to determine the line starting from saddle and reachig a minimum/maximum.
3. What is degenarcy in this case?
Please help me.
1. How do I compute saddles from a given triangular mesh, given scalar values at vertices.
2. From the saddles, how to determine the line starting from saddle and reachig a minimum/maximum.
3. What is degenarcy in this case?
Please help me.
Hi!
Last time, I’ve been a little bit on a wrong track. I know the Morse-Smale Complex from topological analysis of scalar and vector fields. Our fields consist of some discrete values that are either measured or simulated, so we assume that our sample points are not necessarily the critical points we are looking for. Instead we must choose an interpolant that allows finding critical points in between our sample points (triangles won’t work here). For mesh processing it is sufficient to assume that critical points are the vertices. (That’s the big difference.)
So, first you need to find and classify the critical points. Bremer et al. described this very well. The paper you cited also builds up on this approach. What you’re basically doing is looking at the scalar values of adjacent vertices. If all are higher than the scalar in the center you have found a sink, if all are lower you found a source, if you iterate clockwise around the adjacent vertices and it goes up, down, up, down you found a saddle.
Practically the separatrices (connections from saddles to sources/sinks(/saddles) ) are found by integrating stream lines starting from your saddles. Figuratively speaking, you throw some particle into the gradient vector field of your scalar field and observe where it goes to.
A numerical integration goes like this: You start are at position x, find out in which direction to go: grad(s(x)), then do a tiny step x+=grad(s(x))*stepSize and repeat this until you reach a critical point (grad(s(x))=0). What I just showed you is the simplest way to go (it is called an explicit Euler integration). It is numerically very unstable. Defacto standard since at least 2 decades is the adaptive fourth-order Runge-Kutta integrator.
The start point is chosen based on the eigenvectors of the Hessian matrix at your critical point. For each saddle you have two eigenvectors: one with positive eigenvalue, one with negative. Take one step from the saddle center in direction of your eigenvectors and start your numerical integration. You must do a small step at the beginning, since you can't start at the saddle itself (it is a critical point after all). You do this for the positive and negative eigenvectors (e1, e2, -e1 and -e2) so in total four times (this gives you all four separatrices of a saddle). The stream lines coming up there will be the ridges and valleys at this saddle. Ridges will end up in sources, valleys in sinks. That’s what Bremer et al. called a steepest descent / ascent.
Integrating on the gradient field of a scalar field in general is like observing a rain drop on a height field. The “downward” movement of the rain drop equals the backward integration (toward sink) and the “upward” movement equals the forward integration (towards source). Former approaches restricted the movement to edges of the mesh, which led to problems (so a particle is only allowed to flow along edges). Bremer et al. inserted new edges if necessary which is improving the quality.
In this image from Edelsbrunner et al. you can see two degenerated Morse-Smale cells.
The maximum in the center which has only one separatrix belongs to a degenerated Morse-Smale cell. Each Morse-Smale cell is a quadrilateral of source, saddle, sink, saddle. If you start at the maximum (source) I mentioned, you can only go to one saddle. From there you have only one sink to go to. Now, you have to go back to the same saddle you just came from, otherwise you can’t move back to the source you started at. Visiting the same saddle twice yields not in nice quadrilaterals. According to Dong et al. this won’t be a big problem for you, since the eigenfunctions of the Laplacian produce a well-behaved scalar field that doesn’t show this configuration very often. (Nevertheless, I doubt that you can simply neglect this issue completely.)
Hope this helps!
Last time, I’ve been a little bit on a wrong track. I know the Morse-Smale Complex from topological analysis of scalar and vector fields. Our fields consist of some discrete values that are either measured or simulated, so we assume that our sample points are not necessarily the critical points we are looking for. Instead we must choose an interpolant that allows finding critical points in between our sample points (triangles won’t work here). For mesh processing it is sufficient to assume that critical points are the vertices. (That’s the big difference.)
1. How do I compute saddles from a given triangular mesh, given scalar values at vertices.
So, first you need to find and classify the critical points. Bremer et al. described this very well. The paper you cited also builds up on this approach. What you’re basically doing is looking at the scalar values of adjacent vertices. If all are higher than the scalar in the center you have found a sink, if all are lower you found a source, if you iterate clockwise around the adjacent vertices and it goes up, down, up, down you found a saddle.
2. From the saddles, how to determine the line starting from saddle and reachig a minimum/maximum.
Practically the separatrices (connections from saddles to sources/sinks(/saddles) ) are found by integrating stream lines starting from your saddles. Figuratively speaking, you throw some particle into the gradient vector field of your scalar field and observe where it goes to.
A numerical integration goes like this: You start are at position x, find out in which direction to go: grad(s(x)), then do a tiny step x+=grad(s(x))*stepSize and repeat this until you reach a critical point (grad(s(x))=0). What I just showed you is the simplest way to go (it is called an explicit Euler integration). It is numerically very unstable. Defacto standard since at least 2 decades is the adaptive fourth-order Runge-Kutta integrator.
The start point is chosen based on the eigenvectors of the Hessian matrix at your critical point. For each saddle you have two eigenvectors: one with positive eigenvalue, one with negative. Take one step from the saddle center in direction of your eigenvectors and start your numerical integration. You must do a small step at the beginning, since you can't start at the saddle itself (it is a critical point after all). You do this for the positive and negative eigenvectors (e1, e2, -e1 and -e2) so in total four times (this gives you all four separatrices of a saddle). The stream lines coming up there will be the ridges and valleys at this saddle. Ridges will end up in sources, valleys in sinks. That’s what Bremer et al. called a steepest descent / ascent.
Integrating on the gradient field of a scalar field in general is like observing a rain drop on a height field. The “downward” movement of the rain drop equals the backward integration (toward sink) and the “upward” movement equals the forward integration (towards source). Former approaches restricted the movement to edges of the mesh, which led to problems (so a particle is only allowed to flow along edges). Bremer et al. inserted new edges if necessary which is improving the quality.
3. What is degenarcy in this case?
In this image from Edelsbrunner et al. you can see two degenerated Morse-Smale cells.
The maximum in the center which has only one separatrix belongs to a degenerated Morse-Smale cell. Each Morse-Smale cell is a quadrilateral of source, saddle, sink, saddle. If you start at the maximum (source) I mentioned, you can only go to one saddle. From there you have only one sink to go to. Now, you have to go back to the same saddle you just came from, otherwise you can’t move back to the source you started at. Visiting the same saddle twice yields not in nice quadrilaterals. According to Dong et al. this won’t be a big problem for you, since the eigenfunctions of the Laplacian produce a well-behaved scalar field that doesn’t show this configuration very often. (Nevertheless, I doubt that you can simply neglect this issue completely.)
Hope this helps!
Author
[font="Book Antiqua"]Thanks a lot Tsus. It was very helpful [/font]
[font="Book Antiqua"]I have two more questions.[/font]
[font="Book Antiqua"]1. I am identifying saddles and min/max by comparing the scalar values of each vertices with one ring around that vertex .Now I got those critical points and the connecting paths and form patch. but how we can identify the vertices with in each patches? [/font]
[font="Book Antiqua"]2. Once you complete the Morse smale complex from Primal and Quassi dual and form Quadrangular patch, Is it necessary to implement Mesh parameterization? [/font]
[font="Book Antiqua"]3. Mesh parameterization mentioned in Dong et.al paper is not easy to understand. Specifically speaking Transistion function is not trivial to understand. [/font]
[font="Book Antiqua"]I have two more questions.[/font]
[font="Book Antiqua"]1. I am identifying saddles and min/max by comparing the scalar values of each vertices with one ring around that vertex .Now I got those critical points and the connecting paths and form patch. but how we can identify the vertices with in each patches? [/font]
[font="Book Antiqua"]2. Once you complete the Morse smale complex from Primal and Quassi dual and form Quadrangular patch, Is it necessary to implement Mesh parameterization? [/font]
[font="Book Antiqua"]3. Mesh parameterization mentioned in Dong et.al paper is not easy to understand. Specifically speaking Transistion function is not trivial to understand. [/font]
Hello again,
The idea behind the Morse Smale complex is to group regions of similar behavior. All vertices inside a group have one thing in common: They share the same sink and source. If you integrate forwards from any point in a certain cell you end up in the same source. Same thing is true for the backward integration, where you reach the same sink. So, for each vertex integrate once forward and backwards and then check which Morse Smale cell has those two critical points in its quadrilateral in which you ended up in.
This pretty much depends on what you’re trying to do, but in most cases you don’t want such a noisy subdivision of your mesh (it is mainly driven by the gradient flow and is thus probably not very natural). Dong et al. compute an initial parameterization and then iteratively start updating it to improve quality.
The idea behind the transition map is to transform the coordinates from one patch into the coordinates of another patch; so that you can compute distances between them in parameterization space (you additionally weight them according to shape properties and let the minimization via least squares do the rest). What the transition map is basically doing is to tile the patches in a regular grid. Actually each patch has uv coordinates in [0,1]x[0,1] but with the transition map they make them to
[0,1]x[1,2] -- [1,2]x[1,2] -- …
[0,1]x[0,1] -- [1,2]x[0,1] -- [1,3]x[0,1] …
etc.
Equation 6 in the paper is a slightly altered form of the original parameterization approach from Eck et al. They treated the edges of the mesh as springs with a given constant and summed up the spring energy E. They minimized it by least squares, so they found an approximation by setting grad(E)=0. (That’s why equation 6 of Dong et al. has this form.)
Pinkall and Polthier used another energy function, which led to the discrete harmonic weights (which are also often used for the discrete Laplacian).
Dong et al. built up on the work of Pinkall and Polthier.
By the way, Floater and Hormann wrote a nice survey on surface parameterization.
So, yes, I think you should consider implementing a parameterization. For the minimization I’d recommend to use BLAS/LAPACK or some wrapper for that like Armadillo.
Good luck with that!
[font="Book Antiqua"]1. I am identifying saddles and min/max by comparing the scalar values of each vertices with one ring around that vertex .Now I got those critical points and the connecting paths and form patch. but how we can identify the vertices with in each patches? [/font]
The idea behind the Morse Smale complex is to group regions of similar behavior. All vertices inside a group have one thing in common: They share the same sink and source. If you integrate forwards from any point in a certain cell you end up in the same source. Same thing is true for the backward integration, where you reach the same sink. So, for each vertex integrate once forward and backwards and then check which Morse Smale cell has those two critical points in its quadrilateral in which you ended up in.
[font="Book Antiqua"]2. Once you complete the Morse smale complex from Primal and Quassi dual and form Quadrangular patch, Is it necessary to implement Mesh parameterization? [/font]
This pretty much depends on what you’re trying to do, but in most cases you don’t want such a noisy subdivision of your mesh (it is mainly driven by the gradient flow and is thus probably not very natural). Dong et al. compute an initial parameterization and then iteratively start updating it to improve quality.
[font="Book Antiqua"]3. Mesh parameterization mentioned in Dong et.al paper is not easy to understand. Specifically speaking Transistion function is not trivial to understand. [/font]
The idea behind the transition map is to transform the coordinates from one patch into the coordinates of another patch; so that you can compute distances between them in parameterization space (you additionally weight them according to shape properties and let the minimization via least squares do the rest). What the transition map is basically doing is to tile the patches in a regular grid. Actually each patch has uv coordinates in [0,1]x[0,1] but with the transition map they make them to
[0,1]x[1,2] -- [1,2]x[1,2] -- …
[0,1]x[0,1] -- [1,2]x[0,1] -- [1,3]x[0,1] …
etc.
Equation 6 in the paper is a slightly altered form of the original parameterization approach from Eck et al. They treated the edges of the mesh as springs with a given constant and summed up the spring energy E. They minimized it by least squares, so they found an approximation by setting grad(E)=0. (That’s why equation 6 of Dong et al. has this form.)
Pinkall and Polthier used another energy function, which led to the discrete harmonic weights (which are also often used for the discrete Laplacian).
Dong et al. built up on the work of Pinkall and Polthier.
By the way, Floater and Hormann wrote a nice survey on surface parameterization.
So, yes, I think you should consider implementing a parameterization. For the minimization I’d recommend to use BLAS/LAPACK or some wrapper for that like Armadillo.
Good luck with that!
Author
Hi thanks. I have finished Primal dual construction.
But I am encountering monkey saddles. How to resolve them?
But I am encountering monkey saddles. How to resolve them?
Hi!
Monkey saddles are two-fold saddles. In the context of Morse-Smale complex extraction Bremer et al. suggested to unfold (split) them into two one-fold (simple) saddles (section 2.C: Piecewise linear functions). A quick google search showed that there are three ways to do so: Topology for Computing by Zomorodian
Hope it helps.
Monkey saddles are two-fold saddles. In the context of Morse-Smale complex extraction Bremer et al. suggested to unfold (split) them into two one-fold (simple) saddles (section 2.C: Piecewise linear functions). A quick google search showed that there are three ways to do so: Topology for Computing by Zomorodian
Hope it helps.
Author
Thanks a lot.
I could complete the initial parameterization (R3 to R2) and also the inverse mapping ( R2 - R3).
But now problem is there is enough shape loss after inverse mapping, Even though, I am getting quads.
I skipped Transition function ([font=arial, sans-serif][size=1]???) [/font]which maps from one patch ( say alpha) to another patch (say beta)
SSQ specifies to build a dual graph of all patches.
How to build this dual graph which maps from alpha to beta and also from alpha to gamma.
I am still not comfortable the concept of Transistion ([font=arial, sans-serif][size=1]???). [/font]
I could complete the initial parameterization (R3 to R2) and also the inverse mapping ( R2 - R3).
But now problem is there is enough shape loss after inverse mapping, Even though, I am getting quads.
I skipped Transition function ([font=arial, sans-serif][size=1]???) [/font]which maps from one patch ( say alpha) to another patch (say beta)
SSQ specifies to build a dual graph of all patches.
How to build this dual graph which maps from alpha to beta and also from alpha to gamma.
I am still not comfortable the concept of Transistion ([font=arial, sans-serif][size=1]???). [/font]
Hi!
The construction of the dual graph is shown in figure 7.
The vertices in the dual graph are all minima and maxima of the Morse-Smale complex.
Then, you look at each Morse Smale cell and create and edge which connects the minima and maxima of each cell. In case of monkey saddles you have to add further edges. I assume the shortest edge would then be a reasonable choice.
Once you got that graph you can start with the parameterization.
Within each cell of the dual graph we assume a parameterization in [0,1]x[0,1]. The corner which receives the origin (0,0) is chosen arbitrarily. The others are chosen so that right-hand coordinate systems are created. In the SSQ paper this mapping for a patch [formula]P_\alpha[/formula] is denoted as [formula]\phi_\alpha[/formula], which maps a coordinate in the patch [formula]P_\alpha[/formula] to its respective value in the parameterization domain [formula]D_\alpha[/formula].
[formula]\phi_\alpha: P_\alpha \rightarrow D_\alpha[/formula]
Good.
How do we describe a "good" parameterization? A “good” parameterization would have minimal path lengths in parameterization space when traveling from one vertex to another, right? If we look at two vertices inside the same patch the distance could be easily computed in the parameterization domain of the patch. The problem is we also like to compute the distance between two adjacent vertices that lie in different patches (thus are having a parameterization in a different reference frame)! Therefore we need to be able to transform the parameterization space from one patch to the other. This is what the transition map [formula]\phi_{\alpha\beta}[/formula] expresses. [formula]\phi_{\alpha\gamma}[/formula] does the same for a patch [formula]P_\gamma[/formula] being under a patch [formula]P_\alpha[/formula].
Now comes the interesting part. We’d like to have a parameterization coordinate [formula]u_i[/formula] for each vertex [formula]v_i[/formula] of the mesh. We will now look at each pair of adjacent vertices and assign a penalty for the parameterization. Or let’s rather say we create a condition for the system. This is what equation (6) does. It sums over all neighbors [formula]N_i[/formula] of vertex [formula]v_i[/formula] (enumerated with the index [formula]j[/formula], of which we know that they are in a certain patch [formula]\beta[/formula]). Note, that two adjacent vertices could as well be in the same patch, so [formula]\alpha[/formula] and [formula]\beta[/formula] can be equal. For each of these pairs the parameterization coordinate [formula]u_j[/formula] of the neighbor vertex is mapped via the transition map to the parameterization of [formula]v_i[/formula]. After doing so we can compute the distance between both coordinates ([formula]\phi_{\beta\alpha}(u_j) - u_i[/formula]). This distance is weighted by the discrete harmonic weight (some penalty for bad shapes, don't forget to normalize). With this we have crafted one condition for a vertex depending on its neighbor vertices.
When doing this for all vertices, we can place all these conditions in a big sparse linear system.
For vertices that belong to the corners of a Morse-Smale cell, we can (and should) pin the parameterization down to a certain value ( (0,0), (1,0), (0,1) or (1,1) ). Depending on the patch we are currently looking at this coordinate can vary. Since we don't need to compute them, those known values are moved to the right-hand side of the linear system (equation 7).
Now, use your favorite pre-conditioner and solve the thing.
Having this parameterization, the quad domain is iteratively repaired, but that’s another issue. (I haven’t yet read into it.)
Frankly, I’m not quite sure whether this was the point you were struggling with. Could you add some references to the sections in the paper to which you’d like to have further explanations? That would be nice.
I hope that helped anyway.
The construction of the dual graph is shown in figure 7.
The vertices in the dual graph are all minima and maxima of the Morse-Smale complex.
Then, you look at each Morse Smale cell and create and edge which connects the minima and maxima of each cell. In case of monkey saddles you have to add further edges. I assume the shortest edge would then be a reasonable choice.
Once you got that graph you can start with the parameterization.
Within each cell of the dual graph we assume a parameterization in [0,1]x[0,1]. The corner which receives the origin (0,0) is chosen arbitrarily. The others are chosen so that right-hand coordinate systems are created. In the SSQ paper this mapping for a patch [formula]P_\alpha[/formula] is denoted as [formula]\phi_\alpha[/formula], which maps a coordinate in the patch [formula]P_\alpha[/formula] to its respective value in the parameterization domain [formula]D_\alpha[/formula].
[formula]\phi_\alpha: P_\alpha \rightarrow D_\alpha[/formula]
Good.
How do we describe a "good" parameterization? A “good” parameterization would have minimal path lengths in parameterization space when traveling from one vertex to another, right? If we look at two vertices inside the same patch the distance could be easily computed in the parameterization domain of the patch. The problem is we also like to compute the distance between two adjacent vertices that lie in different patches (thus are having a parameterization in a different reference frame)! Therefore we need to be able to transform the parameterization space from one patch to the other. This is what the transition map [formula]\phi_{\alpha\beta}[/formula] expresses. [formula]\phi_{\alpha\gamma}[/formula] does the same for a patch [formula]P_\gamma[/formula] being under a patch [formula]P_\alpha[/formula].
Now comes the interesting part. We’d like to have a parameterization coordinate [formula]u_i[/formula] for each vertex [formula]v_i[/formula] of the mesh. We will now look at each pair of adjacent vertices and assign a penalty for the parameterization. Or let’s rather say we create a condition for the system.
This is what equation (6) does. It sums over all neighbors [formula]N_i[/formula] of vertex [formula]v_i[/formula] (enumerated with the index [formula]j[/formula], of which we know that they are in a certain patch [formula]\beta[/formula]). Note, that two adjacent vertices could as well be in the same patch, so [formula]\alpha[/formula] and [formula]\beta[/formula] can be equal. For each of these pairs the parameterization coordinate [formula]u_j[/formula] of the neighbor vertex is mapped via the transition map to the parameterization of [formula]v_i[/formula]. After doing so we can compute the distance between both coordinates ([formula]\phi_{\beta\alpha}(u_j) - u_i[/formula]). This distance is weighted by the discrete harmonic weight (some penalty for bad shapes, don't forget to normalize). With this we have crafted one condition for a vertex depending on its neighbor vertices.When doing this for all vertices, we can place all these conditions in a big sparse linear system.
For vertices that belong to the corners of a Morse-Smale cell, we can (and should) pin the parameterization down to a certain value ( (0,0), (1,0), (0,1) or (1,1) ). Depending on the patch we are currently looking at this coordinate can vary. Since we don't need to compute them, those known values are moved to the right-hand side of the linear system (equation 7).
Now, use your favorite pre-conditioner and solve the thing.
Having this parameterization, the quad domain is iteratively repaired, but that’s another issue. (I haven’t yet read into it.)
Frankly, I’m not quite sure whether this was the point you were struggling with. Could you add some references to the sections in the paper to which you’d like to have further explanations? That would be nice.
I hope that helped anyway.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
