Shape Modeling
SWEEP REPRESENTATION
L-systems, Fractals
Lecture 11
A sweep represents a shape by moving an object (called a generator) along a trajectory through space. The simplest sweep is an extrusion which translates a 2D curve along a linear path normal to the plane of the curve. Surfaces of revolution are also sweeps of 2D curves around an axis. Sweeps need not use only 2D curves; for example, sweeps of surfaces or solids are useful operations. Sweeps whose generator can change size, orientation, or shape are called general sweeps. One of the advantages of sweeps is their naturalness in representing a large class of man-made objects.
Notions of sweeping
A generator is a curve, surface, or solid to be moved.
A path (trajectory, director) is a curve to move the generator along.
A sweep (swept object) consists of all points swept (visited) by the generator as it is moved along the path.
Classification of sweeps
Planar generator (2D set, plane patch)
• Translational sweep (extrusion).
The trajectory is a line segment orthogonal to the plane of the generator. We need to fix a reference point on the generator that will traverse the trajectory. Orientation and shape of the generator do not change.
• Rotational sweep.
The trajectory (circular arc) directs rotation of each point in the generator around the axis the given angle. The shape of the generator does not change.
• PD curve sweep.
A PD (position and direction) curve defines a trajectory and orientation of the generator. The result is called a constant cross-section solid.
• Generalized cylinders.
Parametrized (variable shape) cross-section swept along an arbitrary curve.
Solid generator
• Canal surface.
Sweeping by a 3D ball/sphere (or a disk in 2D space) moving along a curve.
Figure illustrates moving a 2D disk and 3D ball.
• Offset surface.
Sweeping by a 3D ball/sphere moving across a surface of another solid. In 2D case it is sweeping by a 2D disk moving across a boundary of a 2D solid.
• General sweeping.
- Arbitrary and variable shape of the generator, including set-theoretic and nonrigid objects. Shape variations during the motion may include deformations, topology changes and appearance of disconnected components.
- General type motion of the generator with self-intersections allowed.
Example: sweeping by a cylinder
Example: sweeping by a CSG solid
L-bracket sweep with sinusoidal deformation along directions normal to linear translation.
Dimensionally non-homogeneous sweeps
(a) The translational sweep of a curve creates a 2D solid and two dangling edges.
(b) 2D solids are connected by a 1d edge.
(c,d) Invalid generators: a cross-section with dangling edges creates a nonregular solid.
(e,f) The rotational sweep of a generator passing through the axis of rotation produces a surface or a solid with a singularity: singular point in (e) and nonmanifold edge in (f).
Constant cross-section objects with PD curves
Generator: planar area (cross-section).
Path: six-component trajectory and generator-orientation curve (position and direction, PD curve).
A closed planar curve defining a cross-section sweeps along an axis to form the outline surface. This model is then trimmed by limiting planes. A curved axis defines a nonlinear transformation of the model.
A PD curve is a general form of a six-component curve, usually a parametric cubic curve that continuously specifies position and an associated direction:
(p(t),d(t)) = (px(t), py(t), pz(t), dx(t), dy(t), dz(t))
here p defines position transformation of the direction and d defines generator orientation or vector defining the initial reference direction.
In the given point pi we compute a tangent vector pui and construct a local orthogonal system as follows:
The Figure illustrates transformed orthogonal axis at point Pi on curve.
The axes I and n define a direction plane in which di is located. A PD curve defines continuous transformation for a cross-section to be swept.
Generalized cylinders
Generator: contour c defined by parametric functions
c(n) = (cx(n), cy(n)) , where nI £ n £ nF
Trajectory: 3D curve t defined as
t(u) = (tx(u), ty(u),tz(u)), where uI £ u £ uF.
At every point of the trajectory, the spatial relation between the contour and the trajectory is defined by the Frenet frame, which defines a local coordinate system
e1, e2, e3:
e1(u) = ,
e2(u) = ,
e3(u) = ,
e1 is the unit tangent vector to the trajectory;
e2 (the normal) is the unit vector orthogonal to e1 and directed towards the center of curvature;
e3 (the binormal) is the vector product of e1 and e2, and thus orthogonal to the plane defined by e1 and e2.
A problem: in points where the curvature is equal to zero vector t"(u) is a linear multiple of t'(u), vectors e2 and e3 are undefined.
Figure. Two Frenet frames and contours along a trajectory t of a generalized cylinder:
Contour scaling: parametric functions for x- and y-directions
S(u) = (Sx(u), Sy(u)), where uI £ u £ uF
The parametric surface of the generalized cylinder:
G(u,n) = t(u) + Sx(u)cx(n)e2(u) + Sy(u)cy(n)e3(u), where uI £ u £ uF, nI £ n £ nF
Figure: GeneratingG(ui,ni) points on adjacent contours along the trajectory t(u).
Problems with generalized cylinders
• Possible "self-intersections (pathological cases, degeneracies) with more than one axis parameter value corresponding to the same point:
1) sharp bend of the trajectory
2) a planar area with fixed orientation is moved along a path that has a tangent parallel
to the plain containing a moving area:
® problems with conversion to B-rep.
• The Frenet frame is not well defined when the curvature of the axis is zero.
• Point-membership classification is not obvious.
• Sweeps are not closed under regularized set operations:
Figure (a). Two simple sweeps of 2D objects (triangles). Figure (b). The union of the sweeps shown in (a) is not itself a simple sweep of a 2D object.
Point membership classification (PMC) for sweeps
Consider the situations for PMC of a self-intersecting sweep:
PMC algorithm for the given point P and the planar object A:
1) Find all values of the trajectory parameter t, for which a sweeping (contour) plane goes through the point P.
2) Apply inverse sweeping and get an image point Q on the initial plane:
Figure: Inverse sweep of test point to initial plane of sweep
3) The point P is in, on or out of the swept solid according to the following rules:
1. If $t Î [t0, t1] such that Q ÎA, then P is in the swept solid.
2. If $t Î [t0, t1] such that Q on A and Q not in A for all other values of t,
then P is on the swept solid.
3. If Q out A " t Î [t0, t1]
then P is out of the swept solid.
4. If Q ÎA for t = t0 or t = t1 and Q not in A for t ¹ t0 and t ¹ t1,
then P is on of the swept solid.
This approach
• reduces the 3D PMC problem to a 2D PMC problem;
• does not make any assumption on sweep self-intersection;
• can be simplified by assuming non-self-intersecting sweep.
Sweep-CSG representation
The structure and characteristics of the sweep-CSG tree:
• the leaf nodes are sweeping contour or sweep transformation defining together a sweep primitive with described PMC;
• internal nodes are sweep operations or set operations;
• a sweep internal node defines sweeping by a moving solid;
• another possible way is to convert swept primitives in CSG subtree;
• an equivalent CSG tree is either not possible or is more verbose (requires more primitives and operations).
Application: Sweep-to-CSG conversion using pattern recognition
Algorithm for the conversion of the extruded sweeps bounded by planar and cylindrical surfaces.
Input: sweep outline (contour, cross-section) and sweeping parameters. Example of a valid sweep outline:
Output: primitives and set operations required to form a linear sweep solid.
System primitives (block, wedge, cylinder)
Extended set of primitives (triangular prism, fillet, convex prism)
Two vertex sweep solids (double cylinder, lens, crescent, minor chorded cylinder, major chorded cylinder)
Pattern recognition decomposition algorithm:
1. Search the input outline until a simple sweep solid is found.
2. The simple sweep solid is created and stored wit a specific set operation.
3. The outline is simplified by converting an arc into a line or by deleting one or more vertices.
4. This search and reduction procedure is stopped when the outline no longer encloses any area.
5. The CSG free of the sweep solid is formed by applying the proper set operations to simple sweep solids.
Figure. Outline decomposition example
Example of an outline and a generated CSG solid:
Sweeping a solid and envelopes
A surface of a moving solid is defined in the implicit or in the parametric form. The problem is to find a description of the boundary surface of the swept solid.
Consider an object is given in implicit form
F(x, y, z, t) = 0,
where t is time, defines a family of implicit surfaces or a moving implicit surface. The envelope to this family is that surface which is tangent to all members of the family.
Consider the intersection of two curves in 2D
f(x,y,t) = 0 and f(x,y,t+dt) = 0:
As t ® 0, the two intersections converge onto the envelope. Since f(x,y,t) -f(x,y,t+dt) = 0 at the intersection, it implies the following system defining the envelope:
The implicit form of the envelope surface can be obtained by eliminating t from these two equations giving
e(x,y) = 0
Example of a 2D envelope
Consider sweeping in 2D plane the circle initially described as
(x-5)2 +y2 -1=0
with its center moving around a circular path
x2 + y2 - 52 = 0
It can be shown using the definition of the envelope that the result of sweeping produced by the elimination methods is
x4 + y4 +2x2y2 - 52x2- 52y2 + 576 = 0
This expression has to be factorized to separate the different geometric elements:
(x2 + y2 - 42)(x2 +y2- 62) = 0
Therefore, sweeping the given circle results in a pair of curves (boundaries of the envelope):
Applications of solid sweeps
Numerically controlled (NC) machining
Graphic verification of NC tool paths includes:
• generation of the tool path from NC codes;
• sweeping by a NC tool along the pat;
• set-theoretic difference between a sample and a swept solid (removing material from a sample);
• visual verification of the generated part;
• if there is a different model of the desired part, the toolpath can be verified by taking a set intersection between the part and the swept solid (null set would indicate correct sweeping).
Maintainability check
Aircraft engine physical prototype costs $1-1O million.
Questions:
• Can parts be easily removed?
• Are bolts, nuts, etc. accessible to appropriate tools?
• Does a mechanic has enough flexibility and field of view to perform the maintenance operation?
To answer these questions a modeling system should be able to generate a removal path for a part and to a swept volume traversed by a part as it is removed. Example of designing aircraft engines with Parasolid:
Figure 1: The heat exchanger is a typical part which needs to be readily accessible to the maintenance engineer
Figure 2: The swept volume for the heat exchanger. This volume needs to be kept
empty to allow for maintenance
Note The part is represented with B-rep. It is converted to an implicit (distance) function to model a sweep, which is later triangulated.
References
[1] D. Marsh, Applied Geometry for Computer Graphicals and CAD, Springer, 1999[2] M.E. Mortenson, Geometric Modeling, John Wiley &Sons, 1985
[3]•John M. Snyder, "Generative Modeling for Computer Graphics and CAD, Academic Press, 1992, 311 p.
[4]D.L. Vossler,Sweep-to-CSG conversion using pattern recognition techniques, IEEE Computer Graphics and Applications, vol.5, No.8, 1985, pp.61-68.
[5] W.P. Wang, K.K. Wang, Geometric modeling for swept volume of moving solids, IEEE Computer Graphics and Applications, vol.6, No.12, 1986, pp. 8-17.
[6] R.R. Martin, P.C. Stephenson, Sweeping of three-dimensional objects, Computer Aided Design, vol.22, No.4, 1990, pp.223-234.
[7] K.C. Hui, Solid modelling with sweep-CSG representation, CSG 94 Set-theoretic Solid Modelling: Techniques and Applications, Information Geometers, 1994, pp. 119-131.
[8] GENMOD system http://www.gg.caltech.edu/genmod/gen_mod_page.html
Fractals and Their Applications, Grammar-Based Models, L-Systems
Fractals, introduced by Mandelbrott have become significant tools in natural sciences and they are of great interest to graphics designers for their ability to simulate most of the natural phenomenon. The word fractal is derived from the latin adjective “fractus” which means broken or fragmented.
Fractal objects are entities that can not be represented with Euclidean methods
They have fractional dimension, a number that agrees with our intuitive notion of dimension
Fractals have the property of self-similarity, they are invariant under change of scale
The basic principle of generating fractals involves repetitive application of a specified transformation function to points within a region of space.
Deterministic fractals
Dusts
Sometimes in applications point sets are studied that consist of ‘extremely many’, ‘very small’ subsets, e.g. systems of very small pores. Such sets are called ‘dusts’.
Fig. 1. Schematic description of the Cantor dust
Example 1. Cantor Dust C. The set C is a subset of the real axis. It is obtained by deleting step by step open sub-intervals of [0,1]. The intervals deleted are (see Fig. 1.):
Step 1: (1/3, 2/3)
Step 2 (1/9,2/9), (4/9,5/9), (7/9,8/9)
....
Step n: ((3k-2)/3n,(3k-1/3n)), k= 1,...,3n-1
The set C can be written as follows:
C = [0,1]\((3k-2)/3n, (3k-1)/3n ).
Fig. 2. Schematic description of a square dust
Example 2. Square Dust . The set Q is a planar set. It is obtained by taking from the unit square step by step cross-shaped subsets, Fig. 2. This set contains unaccountably many disconnected points.
Fig. 3. Generator for the generalized von Koch snow-flake
Example 3. von Koch Snow Flake. What we mean by self-similarity is best illustrated by an example, the von Koch snowflake (Fig. 3.). In every step all line segments of the figure are replaced by suitably diminished generators, where the vertices always point outwards.
The notion of fractal dimension is associated with the notion of self-similarity. Hausdorf and Besicovich were the first to propose non-integer dimensions. They demonstrated that thought a line has a dimension of 1 and a square a dimension of 2, many sets have an in-between dimension related to the varying amounts of “material” they contain. To define fractal dimension, we simply extend the formula for calculating traditional dimensions. The number of line segments n of a unit is equal to the inverse of the scaling factor s raised to the appropriate dimension D. For instance, a line segment is 1D; if we divide a line into n equal parts, the parts each look like the original line scaled down by a factor sD. The general equation is represented by
n = 1/ sD.
For example, a square divides nicely into nine subsquares; each one looks like the original scaled by a factor of 1/3. When the von Koch snowflake is divided into four pieces (the pieces associated with original scaled four segments), each resulting piece looks like the original scaled down by a factor of 3. We would like to say it has a dimension D: