Page 205 - Geometric Modeling and Algebraic Geometry

208 C. Liang et al.
vectors by their i-th coordinates. Assuming the sorted points v j are indexed by j =
0, 1, 2, ..., we form the edges v k , v k+1 ,for k =0, 2, 4, ...
However, a special case has to be taken into account, that is when v j has a mul-
tiplicity m i > 1, for instance, when C is tangent to the bounding domain D at v i .
In this case, we can treat v j conceptually as a multiple point which plays the role of
m i points. In this way, we proceed the connecting process in the same manner as we
do for the general case. To determine the multiplicity of a point v j , we only have to
evaluate the derivatives of C at this point.

11.3.3 Hierarchical subdivision

We adopted a hierarchical octree to partition the R space, for several reasons:
3
• each cell of the octree is equivalent to a cube-shaped domain D; which stores
the coefficients of the polynomials in the Bernstein basis of the corresponding
domain.
• we can take cares of faces shared by cells, to minimize the number of calls to
solvers;
• the hierarchical structure of octree allows us to terminate (stop further subdivi-
sion) early when a cell is deemed regular or irrelevant.
We begin by setting a initial bounding domain D 0 to a root cell. A cell is sub-
divided if the curve C defined in the correspondent domain fails the regularity test.
For each subdivision, we result in several smaller domains in form of sub-cells. For
each of them, we repeat the regularity test and, if necessary, further subdivides. The
subdivision of a cell will terminate either when the curve within is deemed regular,
or the size of the cell is beyond a predefined precision .
There are several techniques to save computation efforts. As the sub-cells share
certain faces with their parent cell, the earlier computed intersections on the parent
cell’s faces are inherited directly by the sub-cells. In addition, sub-cells split from the
same parent cell do share some faces as well. Once again, the shared faces should be
computed exactly once.
Once a new face is introduced in the octree decomposition, the bivariate solver
described in section 11.2.2, is called directly with the Bernstein coefficients of the
polynomials on this face. The points we found are shared by neighbor cells, con-
nected to this face in the octree.

11.3.4 Symbolic-numeric approach

Some geometric operations such as computing the self-intersection curve or the ridge
curve of a parameterized surface leads to the computation of implicit curves of high
degree with coefficients of large size. This is either due to projection techniques (see
[9]), or to their definition through composed operations (see [3]). In order to be able
to handle such curve, the main difficulty is to control the result, using approximate
computation, since exact computation though possible, would be prohibitive. We de-
scribe here the symbolic-numeric approach that we have developed for this purpose.