Архивы

Point inversion (Fig. 1) is a fundamental algorithm which allows obtaining a preimage of a 3D point in the parametric domain of a surface. In essence, point inversion is equivalent to point projection. The mathematical formulation of the point inversion problem is given in The NURBS Book [L. Piegl, W. Tiller, The NURBS Book, Springer, New York, 1997].

Fig. 1. Schematical view of point inversion process.

Figure 2 illustrates the poles of a control net projected to the B-surface using the point inversion technique (the projected points are denoted with green color).

Fig. 2. Point inversion for B-surface poles.

There are some important notes on the proper implementation of the Newton iterations for point inversion.

1. The search space should be constrained with U_min, U_max, V_min and V_max extremities of a B-surface. If the next test point of the Newton iteration falls outside the domain, the corresponding coordinate is normally snapped to its extremity. However, snapping the points during the Newton iterations may lead to the divergence of the optimization. If so, it may help to let the Newton iterations sample the objective function out of its domain. Such out-of-domain sampling is not prohibited for the B-spline surface even though the natural extrapolation rarely gives any meaningful shape.



Fig. 3. Non-orthogonal projection result.

2. If the search space is constrained as mentioned above, then the objective functions are often non-minimizable because they express the cosine whose values are sometimes geometrically restricted from being zeros (think of a border point whose projection cannot be orthogonal as illustrated by Figure 3). In such cases, the algorithm cannot converge to an unconstrained minimum. Therefore, the stop criterion to use is not only the value of a function (which should ideally become zero) but also the step size in the search space.



Fig. 4. Unexpected but formally correct solution.

3. The Newton iterations perform the local search. Therefore, it is necessary to properly choose the initial guess. If the point inversion process always starts from a randomly picked point (e.g., the simplest way of choosing the initial guess is to pick up the midpoint of the surface in its domain), the local search may take the solution far from the desired one (Fig. 4). In the worst case, it may even diverge. An example of a formally correct but unsuitable solution of point inversion is shown in the Figure 4. Intuitively, we expect the projected point to lie as close to the origin point as possible. To fit this requirement, the local search should be accompanied by a wise global search. Fortunately, for B-spline surfaces, the global search is quite straightforward. It may consist in picking up the control pole closest to the point being inverted and taking the midpoint of its support subdomain (Fig. 5).

Fig. 5. Subdomain for choosing the initial guess.

In the Analysis Situs workbench, there is invert-point-surf Tcl command for point inversion (Anim. 6). To project all poles of a B-surface, there is a test command misc-project-bpoles.

Anim. 6. Point inversion in Analysis Situs (ver.0.3.0).

The point inversion process has two phases:

1. The first attempt to invert the point is done with the automatic snapping of the sampling coordinates to the surface limits. If this phase succeeds, the algorithm halts.



Fig. 7. Snapping technique leads to non-convergence.

2. If the previous attempt fails (Fig. 7), the Newton iterations are performed without intermediate snapping to let the optimizer find its way out of the surface domain (Fig. 8).

Fig. 8. Letting the optimizer go outside the surface domain.

As one can see, even the very basic algorithms such as point inversion are sometimes tricky to implement correctly. At the same time, the reliability of those fundamental algorithms has a significant impact on higher-level modeling operators. The framework of fast, accurate, and robust tools is the key ingredient of a truly modular (hence maintainable) geometric modeling system.

Want to discuss this? Jump in to our forum.