50
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
00
10
01
11
00
10
01
11
(a)
(b)
(c)
Fig. 3.1. The quadrisection of a triangle oriented: (a) tip-up; (b) tip-down; (c) an example of
a triangle quadtree
data distributed on the plane or on the sphere. In this latter case, the idea is to model
(i.e. to approximate) the sphere with a regular polyhedron, namely one of the five
Platonic solids (i.e. tetrahedron, hexahedron, octahedron, dodecahedron, and icosahedron that have 4, 6, 8, 12, and 20 faces, respectively), and then to subdivide the
surface of the polyhedron using regular decomposition. In the case of the tetrahedron,
octahedron, and icosahedron, the individual faces of the solid are triangles and they
are in turn represented by a triangle quadtree that provides a representation that has
both a variable and a multiple resolution variant. Clearly, the fact that the icosahedron
has the most faces of the Platonic solids means that it provides the best approximation to a sphere and consequently has been studied the most (e.g. [14, 15, 25]). The
goal of these studies has been primarily to enable a way to rapidly navigate between
adjacent elements of the surface (termed “neighbor finding”). However, the methods by Lee and Samet [25] are not limited to the icosahedron and, in fact, are also
applicable to the tetrahedron and octahedron. In particular, neighbor finding can be
performed in worst-case constant time on triangle quadtrees.
Most of the regular multiresolution terrain models are based on triangle bisection. The square domain is initially subdivided in two right triangles. The bisection
rule subdivides a triangle t into two similar triangles by splitting t at the midpoint of
its longest edge (see Fig. 3.2 (a)). The recursive application of this splitting rule to the
subdivided square domain defines a binary tree of right triangles in which the children of a triangle t are the two triangles obtained by splitting t. The multiresolution
model generated by this subdivision rule is described by a forest of triangles, called
a “triangle bintree.” Each node in a triangle bintree represents a triangle t generated
in the recursive subdivision, while the children of node t describe the two triangles
arising from the subdivision of t (see Fig. 3.2 (b)).
If vertices are available at all nodes of the supporting regular grid, then a triangle bintree consists of two full trees that can be represented implicitly as two
arrays [10, 13]. On the contrary, if data are available at different resolutions over
different parts of the domain, then the binary forest of triangles is not complete, and
Emanuele Danovaro, Leila De Floriani, Enrico Puppo, and Hanan Samet
00
10
01
11
00
10
01
11
(a)
(b)
(c)
Fig. 3.1. The quadrisection of a triangle oriented: (a) tip-up; (b) tip-down; (c) an example of
a triangle quadtree
data distributed on the plane or on the sphere. In this latter case, the idea is to model
(i.e. to approximate) the sphere with a regular polyhedron, namely one of the five
Platonic solids (i.e. tetrahedron, hexahedron, octahedron, dodecahedron, and icosahedron that have 4, 6, 8, 12, and 20 faces, respectively), and then to subdivide the
surface of the polyhedron using regular decomposition. In the case of the tetrahedron,
octahedron, and icosahedron, the individual faces of the solid are triangles and they
are in turn represented by a triangle quadtree that provides a representation that has
both a variable and a multiple resolution variant. Clearly, the fact that the icosahedron
has the most faces of the Platonic solids means that it provides the best approximation to a sphere and consequently has been studied the most (e.g. [14, 15, 25]). The
goal of these studies has been primarily to enable a way to rapidly navigate between
adjacent elements of the surface (termed “neighbor finding”). However, the methods by Lee and Samet [25] are not limited to the icosahedron and, in fact, are also
applicable to the tetrahedron and octahedron. In particular, neighbor finding can be
performed in worst-case constant time on triangle quadtrees.
Most of the regular multiresolution terrain models are based on triangle bisection. The square domain is initially subdivided in two right triangles. The bisection
rule subdivides a triangle t into two similar triangles by splitting t at the midpoint of
its longest edge (see Fig. 3.2 (a)). The recursive application of this splitting rule to the
subdivided square domain defines a binary tree of right triangles in which the children of a triangle t are the two triangles obtained by splitting t. The multiresolution
model generated by this subdivision rule is described by a forest of triangles, called
a “triangle bintree.” Each node in a triangle bintree represents a triangle t generated
in the recursive subdivision, while the children of node t describe the two triangles
arising from the subdivision of t (see Fig. 3.2 (b)).
If vertices are available at all nodes of the supporting regular grid, then a triangle bintree consists of two full trees that can be represented implicitly as two
arrays [10, 13]. On the contrary, if data are available at different resolutions over
different parts of the domain, then the binary forest of triangles is not complete, and