72 pages

# cPanel Database Mapping

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

• revision - matière potentielle : 12 cpanel
• revision
• cours - matière potentielle : action
cPanel Database Mapping Abstraction of the Account-Database Relationship Prepared for: cPanel, Inc. Partners & Customers Prepared by: David Neimeyer, Quality Assurance and Integrations April 14, 2010 Document Revision 12: October 28, 2010 cPanel, Inc. 3131 W. Alabama Houston, TX 77098 T 713-529-0800 cPanel, Inc. Houston, Tx
• virtual users
• mysql grants with db
• 11.26 ui
• primary database user
• db mapping
• cpanel
• 11.28 system
• account
• database

Sujets

##### Relationship

Informations

 Publié par Nombre de lectures 48

13.472J/1.128J/2.158J/16.940J
COMPUTATIONAL GEOMETRY
Lectures 10 - 12
N. M. Patrikalakis
Massachusetts Institute of Technology
Cambridge, MA 02139-4307, USA
Copyrightc 2003 Massachusetts Institute of Technology
Contents
10.1 Overview of intersection problems . . . . . . . . . . . . . . . . . . . . . . . . . 3
10.2 Intersection problem classi cation . . . . . . . . . . . . . . . . . . . . . . . . . 5
10.2.1 Classi cation by dimension . . . . . . . . . . . . . . . . . . . . . . . . 5
10.2.2 by type of geometry . . . . . . . . . . . . . . . . . . . . . 5
10.2.3 by number system . . . . . . . . . . . . . . . . . . . . . . 6
10.3 Point/point \intersection" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
10.4 Point/curve intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
10.4.1 Point/Implicit curve intersection . . . . . . . . . . . . . . . . . . . . . 8
10.4.2 Point/Parametric curve in . . . . . . . . . . . . . . . . . . . . 10
10.4.3 Point/Procedural parametric (o set, evolute, etc.) curve intersection . 12
10.5 Point/surface intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
10.5.1 Point/Implicit (usually algebraic) surface intersection . . . . . . . . . . 13
10.5.2 Point/Rational polynomial surface intersection . . . . . . . . . . . . . . 13
10.5.3 Point/Procedural surface intersection . . . . . . . . . . . . . . . . . . . 19
10.6 Curve/curve intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
10.6.1 Case D3: RPP/IA curve intersection . . . . . . . . . . . . . . . . . . . 20
10.6.2 Case D1: RPP/RPP Curve In . . . . . . . . . . . . . . . . . 27
10.6.3 Case D2/D5: RPP/PP and PP/PP Curve Intersections . . . . . . . . . 28
10.6.4 Case D6: PP/IA Curve Intersection . . . . . . . . . . . . . . . . . . . . 28
10.6.5 Case D8: IA/IA Curve In . . . . . . . . . . . . . . . . . . . . 29
10.7 Curve/surface intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
10.7.1 Case E3: RPP Curve/IA Surface Intersection . . . . . . . . . . . . . . 30
10.7.2 Case E1: RPP Curve/RPP In . . . . . . . . . . . . . 31
10.7.3 Case E2/E6: RPP/PP, PP/PP Curve/Surface Intersection . . . . . . . 31
10.7.4 Case E7: PP Curve/IA Surface Intersection . . . . . . . . . . . . . . . 31
110.7.5 Case E11: IA Curve/IA Surface Intersection . . . . . . . . . . . . . . . 32
10.7.6 IA Curve/RPP Surface Intersection . . . . . . . . . . . . . . . . . . . . 33
10.8 Surface/Surface Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
10.8.1 Case F3: RPP/IA Surface Intersection . . . . . . . . . . . . . . . . . . 34
10.8.2 Case F1: RPP/RPP In . . . . . . . . . . . . . . . . . 42
10.8.3 Case F8: IA/IA Surface Intersection . . . . . . . . . . . . . . . . . . . 46
10.9 Nonlinear Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
10.9.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
10.10Local Solution Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
10.11Classi cation of Global Solution Methods . . . . . . . . . . . . . . . . . . . . . 54
10.12Subdivision Method (Projected Polyhedron Method) . . . . . . . . . . . . . . 55
10.13Interval Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
10.13.1Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
10.13.2De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
10.13.3Interval Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
10.13.4Algebraic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
10.13.5Rounded Interval Arithmetic and its Implementation . . . . . . . . . . 62
10.14Interval Projected Polyhedron Algorithm . . . . . . . . . . . . . . . . . . . . . 65
10.15Interval Newton method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Bibliography 72
Chapters 4 and 5, pp. 73 - 160
2Lectures 10 - 12
Intersection Problems, Nonlinear
Solvers and Robustness Issues
10.1 Overview of intersection problems
Intersections are fundamental in computational geometry, geometric modeling and design,
analysis and manufacturing applications. Examples of intersection problems include:
Shape interrogation (eg. visualization) through contouring (intersection with a series of
parallel planes, coaxial cylinders, and cones etc.)
Numerical control machining (milling) involving intersection of o set surfaces with a
series of parallel planes, to create machining paths for ball (spherical) cutters.
Representation of complex geometries in the \Boundary Representation" scheme; for
example, the description of the internal geometry and of structural members of cars,
airplanes, ships, etc, involves
{ Intersections of free-form parametric surfaces with low order algebraic surfaces
{ Intersections of low order algebraic surfaces.
in a process called boundary evaluation, in which the Boundary Representation is cre-
ated by \evaluating" the Constructive Solid Geometry model of the object. During this
process, intersections of the surfaces of primitives (see Figure 10.1) must be found during
Boolean operations.
Boolean opertations on point sets A, B include (see Figure 10.2)
Union: A[B,
Intersection: A\B, and
Di erence: A B.
3Figure 10.1: Primitive solids.
)))
Figure 10.2: Example of a Boolean operation: union.
All such operations involve intersections of surfaces to surfaces. In order to solve general
surface to surface intersection problems, the following auxiliary intersection problems (similar
to distance computation problems used in CAM for inspection of manufactured objects) need
to be considered
point/point (P/P)
point/curve (P/C)
point/surface (P/S)
curve/curve (C/C)
curve/surface (C/S)
All above types of intersection problems are also useful in geometric modeling, robotics,
collision avoidance, manufacturing simulation, scienti c visualization, etc.
When the geometric elements involved in intersections are nonlinear (curved), intersection
problems typically reduce to solving complex systems of nonlinear equations, which may be
either polynomial or more general in character. Solution of systems is a very com-
plex process in general in numerical analysis and there are specialized textbooks on the topic.
However, geometric modeling applications pose severe robustness, accuracy, automation, and
e ciency requirements on solvers of a nonlinear systems as we will see later. Therefore, geo-
metric modeling researchers have developed specialized solvers to address these requirements
explicitly using geometric formulations.
410.2 Intersection problem classi cation
Intersection problems can be classi ed according to the dimension of the problems and ac-
cording to the type of geometric equations involved in de ning the various geometric elements
(points, curves and surfaces). The solution of intersection problems can also vary according to
the number system in which the input is expressed and the solution algorithm is implemented.
10.2.1 Classi cation by dimension
P/P, P/C, P/S
C/C, C/S
S/S
10.2.2 Classi cation by type of geometry
Parametric Implicit
(eg. R = R(t) ) (eg. f(x;y) = 0; z = 0)
Rational PolynomialProcedural
polynomial (algebraic)
Figure 10.3: Curve geometry classi cation
1. Points
Explicit: R = R ; R = [x;y;z]0
Procedural: Intersection of two procedural curves, procedural curve and surface, or
three procedure surfaces, eg. o set or blending surfaces.
Algebraic: f(R) =g(R) =h(R) = 0; where f, g, and h are polynomials.
2. Curves
A classi cation of curves is illustrated in Figure 10.3.
Parametric: R = R(t) AtB
(a) Rational Polynomials (eg: NURBS, rational Bezier).
(b) Procedural, eg: o sets, evolutes, ie. the locus of the centers of curvature of a
curve.
Implicit: These require solution of (usually nonlinear) equations
56
6
(a) Algebraics (polynomial)
f(R) =g(R) = 0 space curves
z = 0; f(x;y) = 0 planar curves
(b) Procedural o sets (eg. non-constant distance o sets involving convolution, see
Pottmann 1997)
3. Surfaces
Parametric R = R(u;v) where u;v vary in some nite domain, the parametric
space.
(a) (Rational) Polynomial (eg: NURBS, Bezier, rational Bezier etc.)
(b) Procedural
{ o sets
{ blends
{ generalized cylinders
Implicit: Algebraics
f(R) = 0
where f is a polynomial.
10.2.3 Classi cation by number system
In our discussion of intersection problems, we will refer to various classes of numbers:
integer numbers;
rational numbers, m=n, n = 0, where m;n are integers;
oating point numbers in a computer (which are a subset of the rational numbers);
q
radicals of rational numbers, eg. m=n, n = 0, where m;n are integers;
algebraic numbers (roots of polynomials with integer coe cien ts);
transcendental (e, , trigonometric, etc.) numbers.
real numbers;
interval numbers, [a;b], where a;b are real numbers;
rounded interval numbers, [c;d], where c;d are oating point numbers.
Issues relating to oating point and interval numbers a ecting the robustness of intersection
algorithms are addressed in the next section on nonlinear solvers.
66
10.3 Point/point \intersection"
Check ifjR R j<, where represents the maximum allowable tolerance.1 2
Choice of \tolerances" in a geometric modeller is di cult{an open question.
Lack of transitivity, see Figure 10.4:
R = R1 2 ) R = R1 3
R = R2 3
R1.
R2.
R3.

Figure 10.4: Intersections of points within a tolerance is intransitive.
What should re ect?
76
10.4 Point/curve intersection
10.4.1 Point/Implicit curve intersection
R \fz = 0; f(x;y) = 0g0
where f(x;y) is usually a polynomial (and f(x;y) = 0 represents an algebraic curve). In an
exact arithmetic context, we can substitute R infz; f(x;y) = 0g and verify if the results are0
zero. Similarly, we could handle:
R \ff(R) =g(R) = 0g0
where f(R) =g(R) = 0 represents an implicit 3D space curve.
What does verify mean in \ oating point" arithmetic?
Example A:
Let z = 0 and x , y satisfy0 0 0
jf(x ;y )j< 1 (10.1)0 0
where is a small constant andjf(x;y)j 1 in the domain of interest including (x ;y ),0 0
then a \distance" check can be performed by:
jf(x ;y )j0 0
< 1 (10.2)
j5f(x ;y )j0 0
provided j5f(x ;y )j = 0. Equation 10.1 is called the \algebraic distance" and Equa-0 0
tion 10.2 is called the \non-algebraic distance". The true geometric distance is given
by:
d =minjR R j; where R = (x;y); f(R) = 0 (10.3)0
The true geometric distance is di cult and expensive to compute (particularly for implicit
f(R) = 0 and involves computing the global minimum ofjR R j. Equation 10.2 results0
from the rst order approximation of Equation 10.3 as derived by Taylor expansion and
is exact when f(R) is represents a plane.
8d
d
f
d
f(R) = 0
R0 g(R) = 0.
Figure 10.5: Curves meet at small angle.
Example B:
R \ff(R) =g(R) = 0g0
5f 5g When curves f = 0, g = 0 meet at a small angle ( = 1), then the condition
j5fj j5gj
jfj
jfj< and = <1 j5fj
jgjjgj< and = <2 j5gj
(wherejfj;jgj; ; are evaluated with R = R and ; 1) are not enough to guarantee1 2 0
proximity of R to the intersection of f, g, see Figure 10.5.0
f
1
3
2
g
Figure 10.6: Approximate curves with straight lines.
Using a linear approximation, and letting
5f 5g1 = cos j j
j5fj j5gj
be the angle of intersection as in Figure 10.6 near the intersection point, a better criterion
for evaluating if R is near the intersection of f and g is0
jfj jgj
1 = f + g< 13
j5fj j5gj
910.4.2 Point/Parametric curve intersection
1. Rational polynomial curves
R \ R = R(t) AtB0
Brute force elementary method:
We solve each of the following three nonlinear polynomial equations separately and
we search for common real roots in AtB.
0 0x(t) x = 0 ! t ;;t0 1 n
00 00y(t) y = 0 ! t ;;t0 1 n
000 000z(t) z = 0 ! t ;;t0 1 n
In principle, this elementary approach is \easy" for polynomials. However, in prac-
tice, this process is complex and ine cien t and prone to numerical inaccuracies.
Preprocessing and subdivision method
{ Use bounding box of R(t) to eliminate easily resolvable cases, with some level
of subdivision (splitting) to reduce box size.
{ Concept of subdivision in rational arithmetic: To eliminate numerical error
in the subdivision process (which can lead to erroneous decisions), rational
arithmetic may be employed (if the input coe cien ts of R(t) are rational or
oating point numbers). This can be easily done in object-oriented languages
{ Continue subdivision until box is small.
{ Then, we could use a numerical technique , such as:
2F(t) =minfjR R(t)j g t2D [A;B]0 1
and use some t from the interval D as the initial approximation. Use of the1
square of the distance function is necessary to avoid possible divergence of the
derivative of the distance function, if it approaches zero.
q
{ If the minimization process converges tot and F(t )<,t =t is the desired0 0 0
solution.
Implicitization (perhaps with box preprocessing) such as
(x ;y ) \ fx =x(t); y =y(t)g0 0
Let us consider an example where x(t);y(t) are quadratic polynomials (the curve is
a parabola). We will attempt to eliminate t to get a polynomial f(x;y) = 0 which
the x;y coordinates of all points on the curve satisfy. We start with the system
2 2x =a t +b t +c a t +b t +c x = 00 0 0 0 0 0)0 2 0 0 0 2 0 0y =a t +b t +c a t +b t +c y = 00 0 0 0 0 0
10