CGAL 6.1 - 3D Envelopes

Loading...
Searching...
No Matches
User Manual

Authors
  Dan Halperin, Michal Meyerovitch, Ron Wein, and Baruch Zukerman

# Introduction

A continuous surface \( S\) in \( {\mathbb R}^3\) is called \( xy\)-monotone, if every line parallel to the \( z\)-axis intersects it at a single point at most. For example, the sphere \( x^2 + y^2 + z^2 = 1\) is not \( xy\)-monotone as the \( z\)-axis intersects it at \( (0, 0, -1)\) and at \( (0, 0, 1)\); however, if we use the \( xy\)-plane to split it to an upper hemisphere and a lower hemisphere, these two hemispheres are \( xy\)-monotone.

An \( xy\)-monotone surface can therefore be represented as a bivariate function \( z = S(x,y)\), defined over some continuous range \( R_S \subseteq {\mathbb R}^2\). Given a set \( {\cal S} = \{ S_1, S_2, \ldots, S_n \}\) of \( xy\)-monotone surfaces, their lower envelope is defined as the point-wise minimum of all surfaces. Namely, the lower envelope of the set \( {\cal S}\) can be defined as the following function:

\begin{eqnarray*} {\cal L}_{{\cal S}} (x,y) = \min_{1 \leq k \leq n}{\overline{S}_k (x,y)} \ , \end{eqnarray*}

where we define \(\overline{S}_k(x,y) = S_k(x,y)\) for \((x,y) \in R_{S_k}\), and \(\overline{S}_k(x,y) = \infty\) otherwise.

Similarly, the upper envelope of \({\cal S}\) is the point-wise maximum of the \(xy\)-monotone surfaces in the set:

\begin{eqnarray*} {\cal U}_{{\cal S}} (x,y) = \max_{1 \leq k \leq n}{\underline{S}_k (x,y)} \ , \end{eqnarray*}

where in this case \( \underline{S}_k(x,y) = -\infty\) for \( (x,y) \not\in R_{S_k}\).

Given a set of \( xy\)-monotone surfaces \( {\cal S}\), the minimization diagram of \( {\cal S}\) is a subdivision of the \( xy\)-plane into cells, such that the identity of the surfaces that induce the lower diagram over a specific cell of the subdivision (be it a face, an edge, or a vertex) is the same. In non-degenerate situation, a face is induced by a single surface (or by no surfaces at all, if there are no \( xy\)-monotone surfaces defined over it), an edge is induced by a single surface and corresponds to its projected boundary, or by two surfaces and corresponds to their projected intersection curve, and a vertex is induced by a single surface and corresponds to its projected boundary point, or by three surfaces and corresponds to their projected intersection point. The maximization diagram is symmetrically defined for upper envelopes. In the rest of this chapter, we refer to both these diagrams as envelope diagrams.

It is easy to see that an envelope diagram is no more than a planar arrangement (see Chapter 2D Arrangements), represented using an extended DCEL structure, such that every DCEL record (namely each face, halfedge and vertex) stores an additional container of it originators: the \( xy\)-monotone surfaces that induce this feature.

Lower and upper envelopes can be efficiently computed using a divide-and-conquer approach. First note that the envelope diagram for a single \( xy\)-monotone curve \( S_k\) is trivial to compute: we project the boundary of its range of definition \( R_{S_k}\) onto the \( xy\)-plane, and label the faces it induces accordingly. Given a set \( {\cal D}\) of (non necessarily \( xy\)-monotone) surfaces in \( {\mathbb R}^3\), we subdivide each surface into a finite number of weakly \( xy\)-monotone surfaces, We consider vertical surfaces, namely patches of planes that are perpendicular to the \( xy\)-plane, as weakly \( xy\)-monotone, to handle degenerate inputs properly. and obtain the set \( {\cal S}\). Then, we split the set into two disjoint subsets \( {\cal S}_1\) and \( {\cal S}_2\), and we compute their envelope diagrams recursively. Finally, we merge the diagrams, and we do this by overlaying them and then applying some post-processing on the resulting diagram. The post-processing stage is non-trivial and involves the projection of intersection curves onto the \( xy\)-plane - see [1] for more details.

# The Envelope-Traits Concept

The implementation of the envelope-computation algorithm is generic and can handle arbitrary surfaces. It is parameterized with a traits class, which defines the geometry of surfaces it handles, and supports all the necessary functionality on these surfaces, and on their projections onto the \( xy\)-plane. The traits class must model the `EnvelopeTraits_3` concept, the details of which are given below.

As the representation of envelope diagrams is based on 2D arrangements, and the envelop-computation algorithm employs overlay of planar arrangements, the `EnvelopeTraits_3` refines the `ArrangementXMonotoneTraits_2` concept. Namely, a model of this concept must define the planar types `Point_2` and `X_monotone_curve_2` and support basic operations on them, as listed in Section The Geometry Traits. Moreover, it must define the spatial types `Surface_3` and `Xy_monotone_surface_3` (in practice, these two types may be the same). Any model of the envelope-traits concept must also support the following operations on these spatial types:

(a) | (b)

Figure 40.1 (a) The spheres \( S_1\) and \( S_2\) have only one two-dimensional point \( p\) in their common \( xy\)-definition range. They do not necessarily intersect over this point, and the envelope-construction algorithm needs to determine their relative \( z\)-order over \( p\). (b) The \( z\)-order of the surfaces \( S_1\) and \( S_2\) should be determined over the \( x\)-monotone curve \( c\). The comparison is performed over the interior of \( c\), excluding its endpoints.

- Subdivide a given surface into continuous \( xy\)-monotone surfaces. It is possible to disregard \( xy\)-monotone surfaces that do not contribute to the surface envelope at this stage (for example, if we are given a sphere, it is possible to return just its lower hemisphere if we are interested in the lower envelope; the upper hemisphere is obviously redundant).

- Given an \( xy\)-monotone surface \( S\), construct all planar curves that form the boundary of the vertical projection \( S\)'s boundary onto the \( xy\)-plane.

  This operation is used at the bottom of the recursion to build the minimization diagram of a single \( xy\)-monotone surface.

- Construct all geometric entities that comprise the projection (onto the \( xy\)-plane) of the intersection between two \( xy\)-monotone surfaces \( S_1\) and \( S_2\). These entities may be:
  - A planar curve, which is the projection of an 3D intersection curve of \( S_1\) and \( S_2\) (for example, the intersection curve between two spheres is a 3D circle, which becomes an ellipse when projected onto the \( xy\)-plane). In many cases it is also possible to indicate the multiplicity of the intersection: if it is odd, the two surfaces intersect transversely and change their relative \( z\)-positions on either side of the intersection curve; if it the multiplicity is even, they maintain their relative \( z\)-position. Providing the multiplicity information is optional. When provided, it is used by the algorithm to determine the relative order of \( S_1\) and \( S_2\) on one side of their intersection curve when their order on the other side of that curve is known, thus improving the performance of the algorithm.
  - A point, induces by the projection of a tangency point of \( S_1\) and \( S_2\), or by the projection of a vertical intersection curve onto the \( xy\)-plane.
  Needless to say, the set of intersection entities may be empty in case \( S_1\) and \( S_2\) do not intersect.
- Given two \( xy\)-monotone surfaces \( S_1\) and \( S_2\), and a planar point \( p = (x_0,y_0)\) that lies in their common \( xy\)-definition range, determine the \( z\)-order of \( S_1\) and \( S_2\) over \( p\), namely compare \( S_1(x_0,y_0)\) and \( S_2(x_0,y_0)\). This operation is used only in degenerate situations, in order to determine the surface inducing the envelope over a vertex (see Figure 40.1 (a) for an illustration of a situation when this operation is used).

- Given two \( xy\)-monotone surfaces \( S_1\) and \( S_2\), and a planar \( x\)-monotone curve \( c\), which is a part of their projected intersection, determine the \( z\)-order of \( S_1\) and \( S_2\) immediately above (or, similarly, immediately below) the curve \( c\). Note that \( c\) is a planar \( x\)-monotone curve, and we refer to the region above (or below) it in the plane. If \( c\) is a vertical curve, we regard the region to its left as lying above it, and the region to its right as lying below it.

  This operation is used by the algorithm to determine the surface that induce the envelope over a face incident to \( c\).

- Given two \( xy\)-monotone surfaces \( S_1\) and \( S_2\), and a planar \( x\)-monotone curve \( c\), which fully lies in their common \( xy\)-definition range, and such that \( S_1\) and \( S_2\) do not intersect over the interior of \( c\), determine the relative \( z\)-order of \( s_1\) and \( s_2\) over the interior of \( c\). Namely, we compare \( S_1(x_0,y_0)\) and \( S_2(x_0,y_0)\) for some point \( (x_0, y_0)\) on \( c\).

  This operation is used by the algorithm to determine which surface induce the envelope over an edge associated with the \( x\)-monotone curve \( c\), or of a face incident to \( c\), in situations where the previous predicate cannot be used, as \( c\) is not an intersection curve of \( S_1\) and \( S_2\) (see Figure 40.1 (b) for an illustration of a situation where this operation is used).

The package currently contains a traits class for named `Env_triangle_traits_3<Kernel>` handling 3D triangles, and another named `Env_sphere_traits_3<ConicTraits>` for 3D spheres, based on geometric operations on conic curves (ellipses). In addition, the package includes a traits-class decorator that enables users to attach external (non-geometric) data to surfaces. The usage of the various traits classes is demonstrated in the next section.

# Examples

## Example for Envelope of Triangles

(a) | (b) | (c)

Figure 40.2 (a) Two triangles in \( {\mathbb R}^3\), as given in `envelope_triangles.cpp`. (b) Their lower envelope. (c) Their upper envelope.

The following example shows how to use the envelope-traits class for 3D triangles and how to traverse the envelope diagram. It constructs the lower and upper envelopes of the two triangles, as depicted in Figure 40.2 (a) and prints the triangles that induce each face and each edge in the output diagrams. For convenience, we use the traits-class decorator `Env_surface_data_traits_3` to label the triangles. When printing the diagrams, we just output the labels of the triangles:

File Envelope_3/envelope_triangles.cpp

// Constructing the lower and the upper envelope of a set of triangles.
#include <iostream>
#include <list>
#include <CGAL/Exact_rational.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Env_triangle_traits_3.h>
#include <CGAL/Env_surface_data_traits_3.h>
#include <CGAL/envelope_3.h>
using Number_type = CGAL::Exact_rational;
using Kernel = CGAL::Cartesian<Number_type>;
using Traits_3 = CGAL::Env_triangle_traits_3<Kernel>;
using Point_3 = Kernel::Point_3;
using Triangle_3 = Traits_3::Surface_3;
using Data_traits_3 = CGAL::Env_surface_data_traits_3<Traits_3, char>;
using Data_triangle_3 = Data_traits_3::Surface_3;
using Envelope_diagram_2 = CGAL::Envelope_diagram_2<Data_traits_3>;
/* Auxiliary function - print the features of the given envelope diagram. */
void print_diagram(const Envelope_diagram_2& diag) {
// Go over all arrangement faces.
for (auto fit = diag.faces_begin(); fit != diag.faces_end(); ++fit) {
// Print the face boundary.
if (fit->is_unbounded()) std::cout << "[Unbounded face]";
else {
// Print the vertices along the outer boundary of the face.
auto ccb = fit->outer_ccb();
std::cout << "[Face] ";
do std::cout << '(' << ccb->target()->point() << ") ";
while (++ccb != fit->outer_ccb());
}
// Print the labels of the triangles that induce the envelope on this face.
std::cout << "--> " << fit->number_of_surfaces() << " triangles:";
for (auto sit = fit->surfaces_begin(); sit != fit->surfaces_end(); ++sit)
std::cout << ' ' << sit->data();
std::cout << std::endl;
}
// Go over all arrangement edges.
Envelope_diagram_2::Edge_const_iterator eit;
for (auto eit = diag.edges_begin(); eit != diag.edges_end(); ++eit) {
// Print the labels of the triangles that induce the envelope on this edge.
std::cout << "[Edge] (" << eit->source()->point()
<< ") (" << eit->target()->point()
<< ") --> " << eit->number_of_surfaces()
<< " triangles:";
for (auto sit = eit->surfaces_begin(); sit != eit->surfaces_end(); ++sit)
std::cout << ' ' << sit->data();
std::cout << std::endl;
}
}
/* The main program: */
int main() {
// Construct the input triangles, makred A and B.
std::list<Data_triangle_3> triangles;
auto t1 = Triangle_3(Point_3 (0, 0, 0), Point_3 (0, 6, 0), Point_3 (5, 3, 4));
triangles.push_back(Data_triangle_3(t1, 'A'));
auto t2 = Triangle_3(Point_3 (6, 0, 0), Point_3 (6, 6, 0), Point_3 (1, 3, 4));
triangles.push_back(Data_triangle_3(t2, 'B'));
// Compute and print the minimization diagram.
Envelope_diagram_2 min_diag;
CGAL::lower_envelope_3(triangles.begin(), triangles.end(), min_diag);
std::cout << std::endl << "The minimization diagram:" << std::endl;
print_diagram(min_diag);
// Compute and print the maximization diagram.
Envelope_diagram_2 max_diag;
CGAL::upper_envelope_3 (triangles.begin(), triangles.end(), max_diag);
std::cout << std::endl << "The maximization diagram:" << std::endl;
print_diagram (max_diag);
return 0;
}
CGAL::Arrangement_2< EnvTraits >::Edge_const_iterator
Base::Edge_iterator Edge_const_iterator
CGAL::Env_surface_data_traits_3
The class Env_surface_data_traits_3 is a model of the EnvelopeTraits_3 concept and serves as a decora...
Definition: Env_surface_data_traits_3.h:39
CGAL::Env_triangle_traits_3
The traits class template Env_triangle_traits_3 models the EnvelopeTraits_3 concept,...
Definition: Env_triangle_traits_3.h:41
CGAL::Envelope_diagram_2
The class-template Envelope_diagram_2 represents the minimization diagram that corresponds to the low...
Definition: envelope_3.h:26
Kernel::Point_3
Kernel::Triangle_3
CGAL::upper_envelope_3
void upper_envelope_3(InputIterator begin, InputIterator end, Envelope_diagram_2< Traits > &diag)
Computes the upper envelope of a set of surfaces in , as given by the range [begin,...
CGAL::lower_envelope_3
void lower_envelope_3(InputIterator begin, InputIterator end, Envelope_diagram_2< Traits > &diag)
Computes the lower envelope of a set of surfaces in , as given by the range [begin,...
Kernel
CGAL::Cartesian

## Example for Envelope of Spheres

The next example demonstrates how to instantiate and use the envelope-traits class for spheres, based on the `Arr_conic_traits_2` class that handles the projected intersection curves. The program reads a set of spheres from an input file and constructs their lower envelope:

File Envelope_3/envelope_spheres.cpp

// Constructing the lower envelope of a set of spheres read from a file.
#include <CGAL/config.h>
#ifndef CGAL_USE_CORE
#include <iostream>
int main() {
std::cout << "Sorry, this example needs CORE ..." << std::endl;
return 0;
}
#else
#include <iostream>
#include <list>
#include <chrono>
#include <CGAL/Cartesian.h>
#include <CGAL/CORE_algebraic_number_traits.h>
#include <CGAL/Arr_conic_traits_2.h>
#include <CGAL/Env_sphere_traits_3.h>
#include <CGAL/envelope_3.h>
using Nt_traits = CGAL::CORE_algebraic_number_traits;
using Rational = Nt_traits::Rational;
using Algebraic = Nt_traits::Algebraic;
using Rat_kernel = CGAL::Cartesian<Rational>;
using Rat_point_3 = Rat_kernel::Point_3;
using Alg_kernel = CGAL::Cartesian<Algebraic>;
using Conic_traits_2 =
CGAL::Arr_conic_traits_2<Rat_kernel, Alg_kernel, Nt_traits>;
using Traits_3 = CGAL::Env_sphere_traits_3<Conic_traits_2>;
using Sphere_3 = Traits_3::Surface_3;
using Envelope_diagram_2 = CGAL::Envelope_diagram_2<Traits_3>;
int main(int argc, char* argv[]) {
// Get the name of the input file from the command line, or use the default
// fan_grids.dat file if no command-line parameters are given.
const char* filename = (argc > 1) ? argv[1] : "spheres.dat";
// Open the input file.
std::ifstream in_file(filename);
if (! in_file.is_open()) {
std::cerr << "Failed to open " << filename << " ..." << std::endl;
return 1;
}
// Read the spheres from the file.
// The input file format should be (all coordinate values are integers):
// <n> // number of spheres.
// <x_1> <y_1> <x_1> <R_1> // center and squared radious of sphere #1.
// <x_2> <y_2> <x_2> <R_2> // center and squared radious of sphere #2.
// : : : :
// <x_n> <y_n> <x_n> <R_n> // center and squared radious of sphere #n.
int n = 0;
std::list<Sphere_3> spheres;
int x = 0, y = 0, z = 0, sqr_r = 0;
in_file >> n;
for (int i = 0; i < n; ++i) {
in_file >> x >> y >> z >> sqr_r;
spheres.push_back(Sphere_3(Rat_point_3(x, y, z), Rational(sqr_r)));
}
in_file.close();
std::cout << "Constructing the lower envelope of " << n << " spheres.\n";
// Compute the lower envelope.
Envelope_diagram_2 min_diag;
auto start = std::chrono::system_clock::now();
CGAL::lower_envelope_3(spheres.begin(), spheres.end(), min_diag);
std::chrono::duration<double> secs = std::chrono::system_clock::now() - start;
// Print the dimensions of the minimization diagram.
std::cout << "V = " << min_diag.number_of_vertices()
<< ", E = " << min_diag.number_of_edges()
<< ", F = " << min_diag.number_of_faces() << std::endl;
std::cout << "Construction took " << secs.count() << " seconds.\n";
return 0;
}
#endif
CGAL::Arr_conic_traits_2
CGAL::CORE_algebraic_number_traits
CGAL::Env_sphere_traits_3
The traits class Env_sphere_traits_3 models the EnvelopeTraits_3 concept, and is used for the constru...
Definition: Env_sphere_traits_3.h:32
Kernel::Sphere_3

## Example for Envelope of Planes

The next example demonstrates how to instantiate and use the envelope-traits class for planes, based on the `Arr_linear_traits_2` class that handles infinite linear objects such as lines and rays.

File Envelope_3/envelope_planes.cpp

// Constructing the lower and the upper envelope of a set of planes.
#include <iostream>
#include <list>
#include <CGAL/Exact_rational.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Env_plane_traits_3.h>
#include <CGAL/envelope_3.h>
using Number_type = CGAL::Exact_rational;
using Kernel = CGAL::Cartesian<Number_type>;
using Plane_3 = Kernel::Plane_3;
using Traits_3 = CGAL::Env_plane_traits_3<Kernel>;
using Surface_3 = Traits_3::Surface_3;
using Envelope_diagram_2 = CGAL::Envelope_diagram_2<Traits_3>;
/* Auxiliary function - print the features of the given envelope diagram. */
void print_diagram(const Envelope_diagram_2& diag) {
// Go over all arrangement faces.
for (auto fit = diag.faces_begin(); fit != diag.faces_end(); ++fit) {
// Print the face boundary.
// Print the vertices along the outer boundary of the face.
auto ccb = fit->outer_ccb();
std::cout << "[Face] ";
do if (!ccb->is_fictitious()) std::cout << '(' << ccb->curve() << ") ";
while (++ccb != fit->outer_ccb());
// Print the planes that induce the envelope on this face.
std::cout << "--> " << fit->number_of_surfaces() << " planes:";
for (auto sit = fit->surfaces_begin(); sit != fit->surfaces_end(); ++sit)
std::cout << ' ' << sit->plane();
std::cout << std::endl;
}
}
/* The main program: */
int main() {
// Construct the input planes.
std::list<Surface_3> planes;
planes.push_back(Surface_3(Plane_3(0, -1, 1, 0)));
planes.push_back(Surface_3(Plane_3(-1, 0, 1, 0)));
planes.push_back(Surface_3(Plane_3(0, 1 , 1, 0)));
planes.push_back(Surface_3(Plane_3(1, 0, 1, 0)));
// Compute and print the minimization diagram.
Envelope_diagram_2 min_diag;
CGAL::lower_envelope_3(planes.begin(), planes.end(), min_diag);
std::cout << std::endl << "The minimization diagram:" << std::endl;
print_diagram(min_diag);
// Compute and print the maximization diagram.
Envelope_diagram_2 max_diag;
CGAL::upper_envelope_3(planes.begin(), planes.end(), max_diag);
std::cout << std::endl << "The maximization diagram:" << std::endl;
print_diagram (max_diag);
return 0;
}
CGAL::Env_plane_traits_3
The traits class template Env_plane_traits_3 models the EnvelopeTraits_3 concept, and is used for the...
Definition: Env_plane_traits_3.h:38
Kernel::Plane_3