The scope of this document is to provide some basic knowledge about the
geometry we deal with. This document is not intended to provide definition
level information, nor are the details of any particular entity discussed
rigorously. Rather, everything is attempted to be explained by example and
analogy, in the simplest possible context. I provide as many different terms
as possible to give key words to use for looking at other documents. I hope
that I have covered an extremely wide variety of terms with some type of
context to understand in general where they fit in.
I haven't figured out the best format yet, so it's going to be my default
of question and answers.
shape of model compared to parm space (use ISO lines to explain)
Curve
Curves are things like lines and arcs. They have no surface area.
However, they may be closed (like a circle), which sort of implies a
surface area, but this doesn't count. The complete list of basic curves
in GDX includes: arc, polyline, conic (including ellipse, parabola, and
hyperbola), nurb curve, and spline curve.
Other curve types which exist in GDX are considered (by me) to be data
structures which use other curves to make something more 'complex'. In GDX,
the curve entities which fit this description are the composite curve, offset
curve, and trim curve.
Boy it would be nice if I could point to a nice description (like the man
pages) that included graphical and data structure examples. Maybe I should
provide a link into the DESIGNBASE man pages, since they have this.
Surface
Surfaces are things like planes and spheres. It's tempting to say they
have surface area, but that's not quite technically accurate. It's not
absolutely necessary that a surface cover any area. Worse yet, the area may
be infinite. The basic surfaces that are in GDX are nurb surface, spline
surface, plane, cylinder, cone, sphere, and torus. Just like the curves,
this is not sufficient for CAD/CAM geometry.
The other surface types vary in complexity. Some are derived from other
surfaces similar to the curves. Some are derived from curves. The 'complex'
surfaces in GDX are ruled surface, revolved surface, extruded surface, offset,
and rectangular trimmed surfaces.
Still more complex Surfaces
Even though GDX has several surfaces beyond the basics, there are several
more classes beyond those. There are more complex forms of nurbs (Gregory
patches), composite surfaces, and a whole range of procedural surfaces
which are represented more by an operation than a surface contour (like
fillets, chamfers, skins, and blends).
Basics of Nurbs
Curves and surfaces such as lines, arcs, cylinders, and spheres each can
only represent a single specific shape (unless you have bunches of small
sections of them). Nurbs, on the other hand, have a general mathematical
definition which allows the representation of virtually any shape.
Additionally, several dissimilar shapes can be joined together with Nurbs.
This example shows a simplistic view of representing a box with rounded
corners using lines, arcs, and nurbs. The desired figure is accurately
represented by using 4 lines and 4 arcs all joined together to make the
shape.
The way the Nurb is defined is by breaking it into sections. For the desired
shape above, you can start with a linear segment (like the left side). You
define a NURBs curve which goes from the end of the arc at the top to the
end of the arc at the bottom - curve (1) in the figure. A segment of a NURBS
curve can be defined which exactly represents that linear segment. Then, the
arc around the bottom can be handled - curve (2) in the figure. Again, NURBs
allow you to define a segment which precisely represents the arc. It continues
around the figure until you have the complete curve as a single NURBs curve.
Another area where NURBs are better than arcs, lines, spheres, etc. is in the
handling of 'free-form' curves and surfaces. I tend to think of free-form as
the types of surfaces generated by sculpters (which is really what car
designers are).
Other Advantages of Nurbs
The section above describes the advantages of nurbs in terms of being able
to be used to represent other types of geometry precisely. Another implied
advantage in that section is the ability to group curves or surfaces together
to make a single curve or surface. This becomes especially useful when trying
to build psudeo-topology on top of the surfaces.
Perhaps the most important advantage of NURBs is the aspect of mathematical
stability. There were several pre-cursors to NURBs that tried to do the same
thing (various types of splines), but they tended to have serious problems
when the inevitable machine precision issues came into play. The structure
of the NURBs data representation makes it such that precision problems will
not cause gaps between segments (which is the main problem with other spline
types). Another advantage of NURBs is that they allow for the precise storage
of conic sections. It is the R (for rational) in NURBs which allows this
precision. This is discussed in more detail in the next section.
Information stored in Nurbs data structures
I guess we should start with the breakdown of the acronym. Non-Uniform
Rational B-Spline. With that start, it's easier to describe each part. To
make any sense at all, I better start with the B-spline part. ***
Psuedo-Topology
I can't remeber where I picked up the term, but it's definitely stuck with me.
It refers to things that have some kind of connection, but not the same level
as solid geometry has. For example, a square represented as 4 lines in a
composite curve has the top connected to each side, but not to the bottom.
This connectivity information is very similar to the connectivity information
in a solid, hence the psuedo-topology term.
Real Topology
For a Boundary Representation (BREP) solid (which is the type of solid in GDX),
the relationship between faces is of critical importance. Thinking of a cube,
it is important to know that the top is connected to each side and that the
top is not connected to the bottom. These connections are the topology of
a structure.
Other Solids
The only other widely accepted solid data structures I'm familiar with are the
elements of Constructive Solid Geometry (CSG). The uselessly high level view of
CSG is that you keep track of the shapes that are used to form the solid and
the operations and order used to put them together. A programming analogy is
that CSG is a script, while BREP is a compiled executable (which you don't have
source code for). In theory, this makes it a lot easier to modify the behaviour
of the solid by adding/deleting/changing operations and shapes in the CSG tree.
In reality, this doesn't work all that well because operations fail (like a
line in the script crashing). Extending the concept to data exchange, it gets
even worse since systems do not have a common set of shapes and operations
(like trying to run a script written in one language on a system which uses
a different language - or like trying to run a perl script on solaris ;-).
Model Space
I figured this question might come up ;-) Model space refers to 3D coordinates
(standard X,Y,Z coordinates). Model space is how the curve or surface looks.
So why isn't everything represented purely in model space ? The computations
involved in model space are very complex and would take rediculous amounts of
time to do meaningful operations based on model space only entities.
Parameter Space
Parameter space is a way to represent model space with 'simpler' geometry.
Of course, this is at the cost of making the data structures and issues
much more complex. There are two required elements for representing model
space data in parameter space. There is the parameter space data, and the
basis functions to map from the parameter space into model space. For curves,
the parameter space data of a particular point on the curve is a single
floating point number (conventionally called t). The basis functions will
take this single floating point number and produce an x,y,z (model space)
point.
Parameter space in conjunction with surfaces adds another dimension to the
parameter space of curves (literally). To represent a point on a surface,
you need both an x and a y parameter space value (conventionally called u and
v). The surface basis functions take these values and produce an x,y,z model
space point.
So far, so good. However, the real complexity comes into it when you are trying
to represent a model space curve (that exists on a surface) within the parameter
space of the surface. In this case, the basis functions would really need to be
used to evaluate every point on the curve (which has an infinite number of
points), to get the correct model space curve (actually, it would just be an
infinte number of points). Since this topic gets pretty involved, it's been
broken out into the Parm Space to Model Space topic.
Mapping Parameter Space Curves to Model Space
Since points are easy to get from parameter space into model (by simply
evaluating the basis functions), why would a curve be harder ? The reason
is that the curve is defined across a parametric range. This range covers
an infinite number of points, so the mapping into model space is necessarily
an approximation. My intuitive understanding of the way this approximation
should work is to check for special cases (like a line in the parameter space
of a cylinder should map into a model space line, arc, or ellipse (depending
on the direction the line is going in parameter space). If no special case
is found, then the parameter space curve should be approximated with a set
of points. These points should be evaluated (through the basis functions).
Then the set of model space points should have a curve fit through them.
(Ideally, the nature of the curve should be similar to the nature of the
parameter space curve.) Then, the model space curve needs to be checked to
see if it is on the surface within a tolerance. See Model
Space to Parm Space for more information on the difficulties of doing
this. If the curve is not within tolerance of the surface, then more points
need to be evaluated and a new curve fit through the new set of points.
Now is the time to go look at GDX and see if this is the algorithm that
is used...I'll leave that as an exercise for the reader
Mapping Model Space to Parameter Space
Unfortunately, there is nothing like a set of basis functions to determine
parameter space from a given model space curve (and the surface). It requires
an iterative algorithm. In general terms, this is done by selecting a set of
sample points in parameter space, evaluating each one into model space. Then
each model space point can be compared to the 'target' point (the model space
point being projected into parameter space). Then the closest set of points
is used, a new set of points approximated and evaluated, and the algorithm
continues until a point has been found that is within tolerance of the target
point.
Even using the simple case of a point, this can cause the algorithm
to 'lock up'. Imagine that the point is a little ways off the actual surface
of surface. If this little bit is far enough to exceed the tolerance being
used, then the algorithm will never find a solution. (By the way, this is
where max_iters is used in GDX...it limits the number of times to try to
refine the grid of points.) Imagine the number of times that this needs to
be done to project a reasonable set of points on a curve, and you can easily
see where a lot of time during translation can be spent. It also makes for
a really interesting computer science case study, since there is a lot of
cacheing that can be done to improve efficiency.
Seams in Surfaces
Seams occur in surfaces where the surface folds around and touches itself
along one edge. This is the case of a full cylinder. A slightly more rigorous
definition is that you have a seam when there are two parameter space lines
(in different locations) which produce the same model space curve. The easiest
way for me to think about it is to think of a cylinder as a piece of paper
rolled up. When you unroll it, you get a flat sheet of paper. This is the
parameter space. When you roll it into the cylinder, you end up touching
two edges together to close the tube. In parameter space, these touching
edges are on opposite sides, but in model space, they coincide. Seams are
tougher to detect when you have a NURBS representation of the cylinder, but
it's still the same concept.
Seams cause trouble (especially in GDX) because of the ambiguity when trying
to project from model space into parameter space. If you happen to be
projecting a point which is exactly on the seam, there are two legitimate
parameter space points which match that model space point. Since the
projection is iterative and needs to consider tolerance, you can even chose
a model space point that's a little on one side of the seam and still get
an answer that really is on the other side of the seam. If you are trying
to project a curve instead of a point, you might get a parameter space curve
which wanders back and forth across the seam.
This is where one of the key aspects of CAD system requirements becomes an
issue. Some systems require that the parameter space curves be closed, and
other systems require that parameter space curves never go outside the
boundary of the surface. In the following diagram, the blue line in model
space represents the seam. Then, the two blue lines in parmeter space are
the two parameter space curves that make the seam. To handle the circle
that crosses over the seam, theoretical system a and system b have differing
requirements. System a requires that the parameter space curve stay within
the boundary of the surface. However, this generates questionable data, since
the curve is now broken into 2 pieces that don't touch. System b cannot
handle a parameter space curve which is split up like that, so it makes a
nice connected circle. This circle just happens to wander outside the
parameter limits of the surface.
Poles in Surfaces
The classic example of a pole is the top (and bottom) of a sphere. If you
make a slit in the sphere from top to bottom, then try to lay it out in
a flat sheet, you can imagine the problems that happen at the top and
bottom of the slit. To be able to lay it flat, you really need the top
and bottom to be elastic. If you fight it down flat into a rectangle,
imagine the point which used to be the top of the slit. It is now the
entire upper edge of the rectangle. (and yes, the slit is a seam)
A more rigorous description is that a pole occurs when all points on a line
in parameter space project to the same model space point. In the image above,
the parameter space line across the top evaluates into the point at the top
of the sphere in model space (red line and red asterisk).
These cause problems in a couple of different ways. For basic spheres, there
are some conflicting requirements for different systems. Some systems do not
allow degenerate model space curves (which is what you get when you evaluate
the parameter space for the pole). This can be avoided by removing the red
lines from parameter space. However, this creates a non-closed parameter space
curve, which is often a problem for some systems. So, then just have the 2
model space curves and all 4 parameter space curves. Well, most systems
require a 1 to 1 correspondence between curves in model and parameter space.
There are some interesting methods employed to resolve these problems. A
certain CAD system scales back from the poles a very small amount. That allows
it to have a parameter space curve without creating a degenerate model space
curve. In some instances, GDX will make two L shaped curves in parameter space.
Each of these maps into an arc in model space, which is the desired result.
So, this creatively solves the problem by making closed parameter space loops
without creating the degenerate model space curves. However, this causes lots
of problems. 1) The implementation is not robust. 2) When the L in parameter
space gets mapped to model space, it generates a NURBs curve which has a
degenerate segment. 3) If the model space curve starts in the middle of the
sphere instead of at a pole, the algorithm breaks down. 4) Some systems can't
handle the G1 discontinuity created by the L shaped parameter space curves.
The problem becomes even more complex if you want to have a part of the sphere
which includes a pole and maybe crosses over the seam a couple times,