Topological coding of surfaces with
boundary using Reeb graphs
Silvia Biasotti
Istituto di Matematica
Applicata e Tecnologie Informatiche – Sez. di Genova
Consiglio Nazionale
delle Ricerche - Italy
silvia.biasotti@ge.imati.cnr.it
This paper is supposed to be viewed, using Internet Explorer version 5.0 (or any later version). Other browsers may give incorrect representations of the content.
Contents
· Abstract
· 2.3 Region and super region classification
Abstract
Morse
theory provides the theoretical framework for defining several shape
descriptors related to the evolution on the surface of its contour levels. For
example, the Reeb graph gives a conceptual sketch of the surface, which can be
used to transmit/code abstract descriptions of the whole data set and to
compose the object signatures instead of the whole models. In this paper, the
basic concepts related to Reeb graphs are
adapted and extended to generic surfaces with boundary.
Keywords: Reeb graph, surface characterisation, shape analysis
Due to the conciseness of the Reeb graph
description, such a representation has been extensively applied to several
application contexts such as shape understanding [1,6], similarity estimation
[4], database retrieval [7,15] and model representation [8,9,16]. An overview
on the effectiveness of Reeb graph representations in shape modelling has been
proposed in [10].
Definition 1 (Reeb quotient space): Let S
be a surface and f:S®Â
be a real mapping function associated to S, the quotient space G=S/~
defined by the equivalence relation “~”:
(P,
f(p) ) ~ (Q, f(Q) ),
P,Q Î
S iff f(P)=f(Q)
P,Q
are in the same connected component of f –1(f(P))
is called the Reeb graph of S
with respect to the mapping function f.
The quotient space G can be
effectively coded as a graph (see figure 1), where nodes correspond to critical
points of the function f, while arcs represent the connections
between them, for details see [1,4,5]. In particular, the Reeb graph is
topologically equivalent to the original shape and the flexibility of the
choice of the function f makes the Reeb graph adaptable to
different application contents. Details on its implementation and the
computational complexity can be found in [10].
(a) (b)
Figure
1. Dotted ellipses in (a) are contour levels of f, while the
continuous lines show a possible representation of the quotient space G.
The Reeb graph representation of a bitorus is shown in (b).
Until now, most of methods for
representing the Reeb graph structure mainly focused on the representation of
closed surfaces [1,4,8,9,] or terrain-like models [2,11], where the Reeb graph
is also referred as contour tree [11,12]. Furthermore, since terrain
surfaces have only one boundary component that may be flattened, the Reeb graph
can be always defined by adding a global minimum that virtually closes
the surface and makes that homeomorphic to a sphere.
Things are slightly different when generic
surfaces with boundary are considered. From a mathematical point of view it is
known that, when f is a continuous map, the number of loops of G
is an upper bound of the number of loops of S. In fact, the
projection prjR:S ®G
is also continuous and the fundamental group pushes forward; that is, there is
a map prj*R:p1(S)
®
p1(G)
defined by taking the image of loops from S. Moreover, denoting g
the genus of an orientable surface S having bS
boundary components and #{loops} the number of loops of G,
when the function f is Morse, the following relations hold:
g
£
#{loops} £
2g + bS - 1
see [5] for details.
This fact implies that the number of loops
of G may change by varying the function f, for
example mapping a surface along different height directions like in figure 2;
therefore, when surfaces with boundary are considered, the characteristic of
the Reeb graph of representing the genus of the surface independently of the
mapping function is not any longer satisfied. The Reeb graph representation of
generic 2-manifold surfaces with boundary has been firstly proposed in [5].
Such an approach substantially extended the construction of the contour tree
presented in [11]; therefore it required that the function f is
Morse and no critical points and vertices on the boundary may assume the same
value of f, [13]. These hypotheses may become a limit when the
Reeb graph representation is applied to discrete models affected by noise
and/or uncertainty.
(a) (b) (c) (d)
Figure
2. If S is a surface with boundary, the number of loops of G
wrt the height function f may depend on the object position. In
case of a torus with two boundaries, the Reeb graph representation admits two
cycles, at most.
In our previous work [1,2] we described a
method for computing a discrete representation of the Reeb graph of triangle
meshes representing either a 2D scalar field or a closed manifold.
In this paper we detail the approach introduced in [16] for representing the
Reeb graph structure of triangle meshes with boundary, providing also the
pseudo-code of the key points of our method. In particular, our approach is
able to characterize mapping functions that are continuous but not
differentiable and admits also boundary components that are polygonal curves.
In addition, this paper describes a two level representation that codes both an
extension of the classical Reeb graph structure (ERG) and a so-called Extended
Reeb Super-graph (ERS) that highlights the genus of the surface.
The reminder of the paper is organized as
follows. First, our characterisation method is adapted to a generic surface
with boundary. Second, our two level graph representation is detailed. Then,
results are presented and possible choices of the function f are
discussed. Conclusive remarks and suggestions on future work end the paper.
In this section, we briefly discuss how to
extend the representation method proposed in [1,2,17] to generic surfaces with
boundary both in terms of characterisation and extraction algorithm.
Our idea is to organize the Reeb graph
representation on two levels: first, the evolution of the level sets is stored
obtaining a description analogous to [5]. Second, another representation, which
is topologically coherent with the genus of the surface S, is
obtained by virtually closing the boundary components. The second phase of the
algorithm is based on the classification theorem of surfaces that claims that
the topological type of an orientable, compact, connected surface with boundary
depends on the number of its boundary components and on the genus of the
surface S* obtained by gluing a disc onto each boundary
component, [14]. Thus, the most intuitive idea for highlighting the topological
type of S is to construct a closed model by physically filling
each boundary component. Unfortunately, even if the operation of closing the
boundary components is theoretically always possible, there are surfaces, such
as the Seifert's surfaces, that do not admit such a filling without any
self-intersection in the usual three dimensional space. Furthermore, since
there are several ways of closing a boundary component, several artefacts could
be introduced in the model during the filling phase. Founding upon these
considerations, our approach virtually closes S without
physically altering the model.
Our approach to surface characterization
analyses the evolution of a set of contour levels C(S) as
proposed in [1,2], where a region-oriented rather than a point-oriented
classification of the behaviour of S was considered.
The contour levels decompose the surface
into a set R(S) of regions; then, each region is classified
either as regular or critical, the latter being a maximum, a
minimum or a saddle. In case of surfaces with boundary the classification is
achieved in two steps: first, all regions are detected and classified. Second,
regions that belong to the same boundary component and assume the same value of
f are virtually grouped in the so-called super-regions.
Let BS(R)= B1 È
B2 È
… È
Bn be the border of a region R Î
R(S) and n the number of its connected
components, where a connected component of BS(R) is
either a closed contour or a polygonal line, that is a line whose end-points
belong to the surface boundary. Each region R of S
is classified according to the number of its border components and outgoing
directions, which are classified as ascending or descending
according to the behaviour of f across the corresponding border
component as explained in [1].
In our implementation, the contour levels C(S)
are inserted as constraints in the triangle mesh and the edges belonging to
them are defined constrained. The following C pseudo-code describes the
extraction of a surface region:
ExtractRegion(TIN,R)
{ /* input: TIN, a
triangle mesh; output R, a region*/
R=InitRegion(t); /*the
region is initialised with a generic triangle*/
while(there are non-visited triangles adjacent to R through a
non-constrained edge)
{
AddTriangle(R,t) /* add a new triangle to
the region R */
MarkTriangle(R,t); /* mark the triangle t as
visited */
}
DetectBoundaryRegion(R); /* detection of the boundary components of
R */
ClassifyRegion(R); /*the region is classified regular or
critical*/
/*according to criteria described in
section 2.3 */
if (!critical)
RemoveFromList(R); /* triangles of R are still marked as
visited*/
}
Therefore, the region extraction procedure is repeated until there are
triangles that have not been visited, yet. With reference to figure 3(a,b)
surface regions correspond to model portions bounded by contours and boundary
components, if any.
To obtain a Reeb graph representation of
an orientable surface S such that #{loops of G}=g=#{handles
of S}, a further region classification that simulates the virtual
closing of each boundary component, is accomplished. Our algorithm for the
closure of a boundary component modifies the approach proposed in [5]. Main
step of such an extension is the virtual union of the contour end points
belonging on same boundary component. Analogously to [5], maxima and minima of f
along each boundary component are detected and end-points of contour
levels that belong to the different portions of the same boundary component are
collapsed. In figure 3 the contour levels with respect to f are
depicted on a sphere with one boundary component; while circles highlight the
end points of contours and dashed lines represent its virtual closure.
The Bolzano-Weierstrass theorem implies
that, when the mapping function f is at least continuous, f
assumes on each boundary component Bi(S) of S
at least a maximum and a minimum value, both on the surface S and
its boundary. Moreover, if the restriction of f to BS
is Morse, the boundary sequentially alternates a maximum and a minimum point;
therefore each maximum is adjacent to two minima at most and vice-versa.
Nevertheless a similar behaviour is verified also when a boundary component is
a polyline, that is a piece-wise linear curve composed by a sequence of edges
that are joined along their end points. In fact, in this case, non isolated
maxima and minima like in figure 3(c) may be considered as a single point and
classified according to the behaviour of f around them.
(a) (b) (c)
Figure
3 Virtual closure of a
boundary component (a,b). Black circles indicate the critical
points with respect to the height function. In (b) m1=m2.
In (c) the edge E of the polyline is classified as maximum.
Let Mg be a
maximum of f assumed on a boundary component Bi(S)
of S and m1, m2
the two minima adjacent to Mg on Bi(S)
such that f(m1) £
f(m2), m1 and m2
may also overlap. Denoting m the point on the arc (Mg,m1)
such that f(m)=f(m2) two cases are distinguished.
First, there are no maxima Mk
of Bi(S) such that f(Mk) Î
[f(m), f(M)]. This implies that m1
and m2 coincide because m2 is
a minimum and, on Bi(S), maxima and minima are
sequentially alternated. In this case we virtually connect all end-points on
the arcs (Mg ,m) and (Mg, m2)
that belong on the opposite side of Bi(S) and have
same value of f, as shown in figure 3(b).
Second, we denote Mf = max{
f(Mk) | f(Mk) Î
[f(m),f(Mg)] }; in particular, we observe that the set Set(Mf)
of the maxima having value Mf may consist of several
points and, if m1¹
m2, Set(Mf) is not
empty. Let m'1 and m'2 be the
points on the arcs (Mg, m) and (Mg,m2),
respectively, such that f(m'1)=f(m'2)=Mf.
If the Euclidean distance between m'1 and m'2 (Euclid(m’1,m’2))
is less than that between the same points and the Set(Mf),
the arcs (Mg ,m) and (Mg, m2)
are collapsed; in practice such a control should determine if the critical
points of the boundary behave like in figure 4(b). Otherwise (see figure 4(a)),
we connect the end-points that belong to the arcs (Mg,m'1)
and (Mg,m'2) with same value of f;
while the remaining part of Bi(S) that does not
contain Mg is split into the sub-parts induced by the
points of Set(Mf).
Finally, such a gluing process is repeated
separately for the other sub-parts of Bi(S), until the
virtual correspondence among all contour end-points has been established.
(a) (b)
Figure
4. Possible configurations of two boundary components. In (a) the maximum M1
lies between m’1 and m’2,
therefore Euclid(m’1,m’2)³{Euclid(m’1,M1),Euclid(M1,m’2)}.
Then, the arcs (M,m’1) and (M,m’2)
will be connected and the reminder of the boundary splits. On the contrary,
when the Euclidean distance between m’1 and m’2
is less that the other, like in the case (b), the arcs (M,m) and (M,m2)
may be collapsed.
An example of the pseudo-code for the
detection of the generalized contours is proposed in the following:
GeneralizeContours(Bi(s))
/* input: Bi(s), a
boundary component of S; output: virtual closure of Bi(s)*/
{
CharacterizeBoundary(Bi(S)); /* maximum and minimum detection on
Bi(S)*/
Mg=MaximumVertex(Bi(S)); /* vertex having the highest
value of f */
m1, m2=AdjacentMinima(Bi(S), Mg); /*extraction of minima adjacent to Mg
on Bi(S)*/
/*the
minima m1 and m2 satisfy the inequality f(m1)£f(m2)*/
if (m1== m2)
CollapseArcs((Mg-m1),(Mg-m2));
/* the contour end
points lying on the two arcs are identified */
else
{
m=VertexOnArc(Mg-m1,f(m2)); /*vertex on the arc Mg-m1
such that f(m)=f(m2)*/
Set(Mf)=MaximaInInterval(f(Mg)-f(m)); /*maxima whose f value is bounded by
f(Mg) and f(m)*/
m’1=VertexOnArc(Mg-m,f(Set(Mf)))
m’2=VertexOnArc(Mg-m2,f(Set(Mf)))
dist=EuclideanDistance(m’1,m’2);
dist_sets=MaxMinDistance(m’1,m’2,Set(Mf)) /*minimum distance between m’1,
m’2 and
set of maxima Set(Mf)*/
if (dist £ dist_set)
{
CollapseArcs((Mg-m),(Mg-m2));
GeneralizeContours(Bi(s)); /* repetition on other subparts of Bi(S)*/
}
/* end if */
else
{
CollapseArcs((Mg-m’1),(Mg-m’2));
GeneralizeContours(subpart
of Bi(s) containing m2);
GeneralizeContours(subpart
of Bi(s) containing m1);
}
/*end else */
}
/*end else */
}
Once two arcs have been collapsed, the
function “GeneralizeContours” is recursively applied to the remaining subparts
of Bi(S). Finally, the extraction of the generalized
contours ends when such a procedure is applied to each boundary component Bi(S)
of S.
In figure 5(a) an example of the pipeline
of our gluing algorithm is shown. First, the maximum Mg
and the minima m1 and m2 of BS
are considered. Since f(M1) ³
f(m2) the points m'1
and m'2 are detected. Since the distance between m'1
and m'2 is less than the distance between m'1
and M1, the arcs (Mg,m) and (Mg,m2)
are glued (see figure 5(c)). Once the points m and m2
have been identified, the maximum M1 is selected.
Then, the maximum M2 generates a further split of the arcs (M1,m4)
and (M1,m7) introducing the points m5
and m6 (figure 4(d)). Analogously, M2
lies between m5 and m6. In
this case the two arcs (M1,m5) and (M1,m6)
glue together and the remainder portion of BS is split
in two subparts. Finally, the arcs (m5,m1)
and (m1,M2) are connected; similarly, (M2,m7)
and (m7,m6) do (see figure 4(e)). The
correspondence between the boundary portions is shown associating the same
colour to arcs that are glued together; in particular, in figure 5(c,d) the
line between m1 and m2
denotes that these vertices have been identified and (M1,m5)
will become an arc.
(a) (b)
(c) (d)
(e)
Figure 5 Sequence of steps for virtually closing a boundary component using our method.
In figure 6(d) we show a possible boundary
decomposition induced by the method proposed in [5]. There, arcs between minima
and maxima of a boundary component are connected without considering if other
critical values lie on the interval of values they span. In particular, once
the points m4 and m5 have
been identified, the arcs (Mg,m4) and (Mg,m3)
are glued; similarly (m3,M1) and (M1,m5)
do; finally, the pair (m4,m1) and (m5,m2)
is connected and, analogously, the arcs (M2,m1)
and (M2,m2) do.
(a) (b)
(c) (d)
Figure
6. Virtual correspondence using the criteria in [5].
As a result of our gluing algorithm,
contours with end points on same boundary component are virtually closed and we
refer to them as generalized contours.
2.3 Region and super region classification
In this section it is described our surface regions classification. Such
a classification mainly depends on the number of border components of a region
and the behaviour locally around its border. Given a
region R, we will denote BS(R) its
border and n the number of its border components; then, the
following classification scheme is adopted:
-
R is a maximum
area iff all the outgoing directions from BS(R) are
descending;
-
R is a minimum
area iff all the outgoing directions from BS(R) are
ascending;
-
R is a saddle
area iff n>2 and there are both ascending and descending
outgoing directions from BS(R);
-
finally, R is called regular
iff does not belong to the previous categories.
Super regions are extracted
gluing the regions whose image is in the same interval of values of f
and share at least one generalized contour. Considering the generalized
contours instead of the contour levels, the resulting super regions are further
classified using the criteria proposed for regions. Therefore the algorithm for
the extraction of the super regions works analogously to the method proposed in
section 2.1.To what the outgoing directions of a generalized contour are
concerned, they are still classified ascending or descending according to the
behaviour of the function f of along its contour levels. The set
of super regions is denoted by SR(S) and, analogously to R(S),
they provide a full partition of the surface S.
The generalized characterization just
described may be coded in a graph simply extending the equivalence relation
used in the Reeb graph. The equivalence notion we are introducing may be
applied not only to the region decomposition R(S), but to the
super region segmentation SR(S) too.
Let f: S ®
Â
be the a real function defined on S, and let [fmin,fmax]
be an interval containing the domain of f on the surface S,
and fmin < f1 < … < fnp < fmax
the distribution of the values of the contour levels C(S) of S
as proposed in [2]. In addition, let I={(fmin, f1),
(fi, fi+1), i=1, … , np-1, (fnp, fmax)}
È
{fmin, f1, … ,fnp, fmax}
be the partition of the interval [fmin, fmax]
provided by the function values of the contour levels and its np+1
interior parts.
Definition 2: An extended Reeb equivalence
between two points P, Q Î
S is given by the following two conditions:
f(P)
and f(Q) belong to the same element of t Î
I;
P
and Q belong to the same component of f -1(f(t)),
t Î
I.
In
case we consider the surface classification induced by R(S), each
region R is Reeb-equivalent in the extended sense; therefore it
collapses into the same point of the quotient space. In figure 7 the Reeb
quotient space of a torus is shown. In particular, each region in identified by
a point. Points of the quotient space are represented with circles if they
correspond to regular regions and rectangles if they correspond to contour
levels. The quotient space, which is an abstract sub-space of S
and is independent of the geometry, may be represented as a traditional graph,
we called the Extended Reeb Graph, (ERG) [1,2].
Figure 7. Extended Reeb graph equivalence with respect to the direction f for a torus.
Analogously, if we consider the super
regions previously described, each of them generates a single point in the
graph, even if it may be composed of many connected components. Also in this
case the quotient space is represented through a graph representation, we name Extended
Reeb Super-graph, (ERS).
The extended Reeb quotient space is
represented associating a node to each region (resp. to a super region), which
has been classified as critical and an arc to a sequence of regions (resp.
super regions) that connects the two critical ones. All vertices in a region
(resp. super region) are Reeb-equivalent, the Reeb graph extraction is based on
tracking the evolution of contour lines or generalized contours. In particular,
the degree of each node in the ERG representation equals the number of
contours (resp. generalized contours) of the corresponding critical region
(resp. super region).
The algorithm for the extraction of the ERG
works in two steps. First, arcs between minima (resp. maxima) and saddles are
inserted by connecting all maxima/minima to their nearest (in terms of region
expansion) critical area; then, the graph is completed through a region growing
process that stops when all possible ascending directions and arcs have been
visited, details are in [1,2].
The two level representation we have
introduced highlights the object topology. In particular, we observe that the ERG
obtained through our virtual closure of the boundary components still
recognizes the topological type of S and the number of cycles of G
equals the genus of S. In figure 8(a) the ERG of the
Seifert's surface of a trifolium is shown; dotted lines in 8(b) represent the
virtual correspondence of some points; finally, the ERS with respect to SR(S)
is drawn in 8(c).
(a) (b) (c)
Figure
8. ERG wrt f for the region classification (a), the
virtual correspondence along the boundary component (b) and the corresponding ERS
(c)}
In figure 9, other comparisons of the ERG
and the ERS representations are shown. In particular, the mapping
function of the sphere with two boundary components is the height direction
while for the animal skull we have chosen the distance from the centre of mass.
(a) (b) (c) (d) (e) (f)
Figure 9. ERG
(b,e) and ERS (c,f) of two models (a,d).
Since the shape features effectively coded
in the graph depends on the choice of f, this is a fundamental
subject. An overview of possible choices of such a function has been proposed
in [10], where the properties of several mapping functions are discussed. In
case of surfaces with boundary, the functions that seem to be the most suitable
are those that depend on the shape distribution in the space, such as the
height function and the point distance from the centre of mass [10], instead of
the point arrangement, such as the integral geodesic distance [4] and the
geodesic distance from a seed vertex [6,9]. In fact, the geodesic distance may
unnaturally increase in correspondence of a boundary component; therefore, each
boundary component may become a feature, which is indistinguishable from the
surface protrusions and cavities. On the contrary, functions such as the
distance from the barycentre emphasize the spatial embedding without altering
the value on the boundary components. An example of that is shown in figure 10:
although the graphs wrt the distance from the barycentre and the integral
geodesic distance coincide on the closed bitorus in 10(a), the distance from
barycentre 10(c) is less sensitive to the removal of some triangles than the
other one 10(b).
(a) (b) (c)
Figure 10. Reeb graph of a bitorus (a) without boundary; the graphs of the modified model are depicted for the distance in [4] (b) and that from the barycentre (c). In these representations the nodes are depicted as centre of mass of the contour levels of the critical areas.
5. Conclusions
Currently, the evolution of the boundary
components of S is not explicitly stored in the ERG either
in the ERS representations and may be performed only analysing the
evolution of the surface contours; therefore we are investigating on possible
methods for including such an information directly in the graph.
Moreover, we are interested on investigating the suitability of this
representation for shape matching and retrieval purposes. In particular, we are
planning to combine our representation with other shape descriptor to capture
both topological and geometric information and to contribute to the design of a
multistep search engines for 3D models.
This work has been partially supported by
the EU FP6 Network of Excellence AIM@SHAPE[1]
and the National Project "MACROGeo: Metodi Algoritmici
e Computazionali per la Rappresentazione di Oggetti Geometrici'', FIRB
grant.
The author would like to thank Bianca
Falcidieno, Michela Spagnuolo and all people of the Shape Modelling Group at
IMATI-CNR for their invaluable support. Moreover, thanks are due to Malcolm
Sabin, Massimo Ferri and the anonymous reviewers for their helpful suggestions.
[1] M. Attene, S. Biasotti, and M.
Spagnuolo, ‘Shape understanding by contour driven retiling’, The Visual
Computer, vol. 19, no. 2-3, pp. 127--138, 2003.
[2] S. Biasotti, B. Falcidieno, and M.
Spagnuolo, ‘Surface Shape Understanding based on Extended Reeb Graphs’, in Surface
Topological Data Structures: An Introduction for Geographical Information
Science, S. Rana, Eds., John Wiley & Sons, 2004, pp. 87--103.
[3] G. Reeb, ‘Sur les points singuliers d'une
forme de Pfaff complètement intégrable ou d'une fonction
numérique’, Comptes Rendu de l'Académie des Sciences,
222:847--849, 1946.
[4] M. Hilaga, Y. Shinagawa, T.Komura, and
T.L. Kunii, ‘Topology matching for fully automatic similarity estimation of 3D
shapes’, in ACM Computer Graphics, (Proc. of SIGGRAPH 2001), pp.
203--212, Los Angeles, 2001. ACM Press.
[5] K. Cole-McLaughlin, H. Edelsbrunner,
J. Harer, V. Natarajan, and V. Pascucci, ‘Loops in Reeb Graphs of 2-Manifolds’,
in Proceedings of the 19th ACM Symposium on Computational
Geometry, ACM Press, 2003, pp. 344--350.
[6] A. Verroust and F. Lazarus, ‘Extracting
skeletal curves from 3D scattered data’, The Visual Computer, vol. 16,
no. 1, pp. 15--25, 2000.
[7] D.Bespalov, W. C.
Regli, and A. Shokoufandeh, ‘Reeb Graph Based Shape Retrieval for
CAD’, In Proceedings of the 2003 ASME Design
Engineering Technical Conferences, Chicago, Illinois, September 2003. ASME
Press.
[8] Z. J. Wood, M. Desbrun, P.
Schröder, and D. Breen, ‘Semi-regular mesh extraction from volumes’, in Proc.
of the 11th Ann. IEEE Visualization Conference (VIS) 2000’,
2000.
[9] F. Hétroy and D. Attali,
‘Topological quadrangulations of closed triangulated surfaces using the Reeb
graph’, Graphical Models, vol. 65, no. 1, pp. 131--148, 2003.
[10] S.
Biasotti, S. Marini, M. Mortara,
and G. Patanè,
‘An overview on properties and efficacy of topological skeletons in shape
modelling’, In Proceedings of Shape Modelling and Applications, pp.
245--254, Seoul, South Korea, May 2003. IEEE Press.
[11] M. van Kreveld, R. van Oostrum, C.
Bajaj, V. Pascucci, and D. Schikore, ‘Contour trees and small seed sets for
isosurface traversal’, in Proceedings of the 13th International
Annual Symposium on Computational Geometry (SCG-97), New York: ACM Press,
June 4--6 1997, pp. 212--220.
[12] H. Carr, J. Snoeyink, and U. Axen,
‘Computing contour trees in all dimensions’. in Proceedings of the 11th
Annual ACM-SIAM Symposium on Discrete Algorithms, N.Y.: ACM Press, Jan.
9--11 2000, pp. 918--926.
[13] J. Milnor, Morse Theory, New
Jersey: Princeton University Press, 1963.
[14] W. Massey, Algebraic Topology: An
Introduction, Brace & World, Inc, 1967.
[15] S.
Biasotti, S. Marini, M. Mortara,
G. Patanè,
M. Spagnuolo, and B.
Falcidieno, ‘ 3D shape matching through topological structures’, In I.
Nyströn, G. S. di Baja, and S. Svennson, editors, Proceedings of the 11th
Discrete Geometry for Computer Imagery Conference, vol. 2886 of Lecture
Notes in Computer Science, pp. 194--203, Naples, 2003. Springer Verlag.
[16] Z. Wood, H, Hoppe, M. Desbrun, and P. Schröder, ‘Removing
Excess Topology From Isosurfaces, ACM Transactions on Graphics,
23(2):190—208, April 2004.
[17] S. Biasotti, ‘Reeb graph representation of surfaces with boundary’,
In Proceeding of Shape Modelling and Applications, pp. 371-374, June
7-9, Genova, Italy, 2004, IEEE Press.