Vector Graphics
If you have Cookies enabled,
you can check to see if any files you have downloaded
have been updated since you downloaded them
by clicking here.
|
|
Each of the Algorithms have been implemented as C++ classes using Microsoft Visual C++ V6.
Microsoft Foundation Classes (MFC) have been used where necessary.
Non MFC folk can remove the pragma statements and use the following info to adjust the code:
typedef unsigned char BYTE;
typedef unsigned short WORD;
typedef unsigned long DWORD;
My intention is to provide simple, free access to useable solutions to common but difficult programming problems.
I have treated the creation of each class as a puzzle and hopefully have come up with good solutions.
If you know any better solutions then please e-mail me so that everyone can share your wisdom!
Be aware that I use a non-standard "Coding Style"... and its infectious...
|
Fundamentals
Implementing Vector Graphics
If you want to re-invent the wheel and do your own graphics primitives, this is for you!
The code on this page is designed to allow you to store and draw lines and arc which may represent three-dimensional objects.
People used to worry about speed differences in using integers or floating-point arithmetic for graphics. Modern processors and graphics boards mean that we can just use what is most natural, so I use floating-point arithmetic and deal with rounding errors by specifying a tolerance.
This allows me to debug and see real values, and means I don't have any conversion from floating-point to integer.
The Graphics Primitive structures are all prefixed with "g" (for "graphic") and a number representing the number of Dimensions the structure will handle.
So the three-dimensional Point structure is a g3Point.
I present two and three dimensional structures for each concept and abuse the whole idea of object orientation by defining my structures in terms of the data they will hold rather than the object they represent.
At first this seems bizarre, but when you are actually working with the classes you'll be surprised at how rarely you think about the abject you're dealing with: you're almost always more concerned with the maths defining the object.
So, for example, I have a class which contains a Vertex and a Vector...
I use the word "Point" instead of "Vertex" so that I can call the class "g3PV" for "PointVector"...
This class could represent a Position Vector, or a Line, or an axis-aligned Box (Point is one corner, Vector points to opposite corner).
The maths for each possibility is likely to be in the primitive, so a g3PV will have a "Hit" function to to see if a point lies on the line; a "HitBox" function to see if it lies in the Box etc.
Thats why I refer to these structures as "Primitives": you can derive "proper" classes from them, but at this level, they are simple open boxes to hold things in.
All the structures are in one file which you can download here:
Co-ordinates
Using floating point arithmetic is evil.
Digital Computers aren't very good at it, and programmers are often really awful at implementing floating point arithmetic.
The big issue is that after a few sums there may be a rounding error which may be very small but can stop a program from working.
If a rounding error alters a number even slightly then comparisons may fail, for example,
if the result of a sum returns a value, x=1.00000000000000000000000000001, this tiny variation from the value 1.0 will make the following condition fail:
if(x==1.) DoSomething();
when the programmer didn't expect it to.
You can get around this by deciding on a sensible difference from the value you want to compare something to (tolerance) like this:
if(fabs(x-1.)<Tolerance)
Tolerance is usually fairly similar between applications and can usually be a very small number if necessary.
Most of the vector graphic projects I've been involved with use real-world coordinates in millimeters and a tolerance of 0.0001 is adequate.
Clearly you don't want to be writing huge expressions every time you want to test the value of a coordinate,
so I use a struct to hold a quantised double. Unfortunately C++ doesn't allow you to derive a class from the type "double", so the struct ends up with a lot of operators that help it model the behaviour of a double.
Since the main use for me is to hold Coordinates, I have called the class gCoord. You may prefer QDouble, Quable or something.
Be aware that if you use the standard min and max macros (etc.) on these, then the Tolerance will be used...
This can introduce bugs if you let it!
For example:
gCoord A=1.000000001;
A=acos(min(max(-1.0, A), 1.0)); // This will NOT clamp the value of A as you might expect!!!
you should use:
A=acos(min(max(-1.0, A.Coord), 1.0));
to make sure that the normal, untoleranced double comparison is used.
Tolerance is defined as a global const:
const double Tolerance=0.0001; // const for speed.
The struct has a double as its only member variable,
a Compare function (returning the usual -1,0,+1 integer) which is used by all the comparison operators,
and uses a static sgn function where the Tolerance comes into play:
struct gCoord { // A quantised double. Quantisation Tolerance is handled in the sgn function:
static int sgn(double d) {return d<-Tolerance ? -1 : (d>Tolerance);}
double Coord;
gCoord() {}
gCoord(double d) : Coord(d) {}
gCoord& operator= (const gCoord& c) {Coord= c.Coord; return *this;}
bool operator> (const gCoord& c) const {return Compare(c)> 0;}
[...all other operators for gCoord...]
gCoord& operator= (const double d) {Coord= d; return *this;}
bool operator> (const double d) const {return Compare(d)> 0;}
[...all other operators for double...]
gCoord& operator= (const int i) {Coord= i; return *this;}
bool operator> (const int i) const {return Compare(i)> 0;}
[...all other operators for int...]
gCoord operator- () const {return -Coord;}
bool operator! () const {return Compare(0)==0;}
operator bool() const {return Compare(0)!=0;}
operator double() const {return Coord ;}
int Compare(double d) const {return sgn(Coord-d) ;}
int sgn() const {return sgn(Coord) ;}
};
[...all operators for doubles and ints taking gCoord& ...]
This leaves you with a type that you can use like a double, but comparisons will be handled quickly, efficiently and sensibly.
There are lots of studies about the use of Vector and Vertex classes in graphics libraries.
Most agree that there is only a need for a Vector class and a Vertex can live in a Vector class.
So what I've done is use a generic object to hold the coordinates, and extend that to create separate Vector and Point (Vertex) objects.
The next structs, then, are g2D and g3D which simply hold two or three gCoords.
To construct with zeroed coordinates I provide an explicit bool constructor, so g2D DD(true); creates two zeroed gCoords.
The default constructor doesn't initialise the gCoords. This behaviour is used throughout the Primitives.
struct g2D { // 2 Doubles (Used as a 2 Dimensional Point or Vector)
gCoord x,y;
g2D() {}
g2D(gCoord x, gCoord y) : x(x), y(y) {}
explicit g2D(bool Zero) {if(Zero) Clear();}
g2D(double* DD) {x=*DD++; y=*DD;}
void Clear() {x=y=0;}
g2D& operator*=(const gCoord& c) {x*=c; y*=c; return *this;}
g2D& operator/=(const gCoord& c) {x/=c; y/=c; return *this;}
bool operator==(const g2D& DD) const {return Compare(DD)==0;}
bool operator!=(const g2D& DD) const {return Compare(DD)!=0;}
operator bool() const {return bool(x)||bool(y);}
int Compare(const g2D& DD) const { // For Sorting
int Result = x.Compare(DD.x);
return Result ? Result : y.Compare(DD.y);
}
};
To create a g3D I could have used g2D as its Base Class, but there are no advantages.
Every function would need redefining anyway, and, for example:
struct g3D : g2D { // 3 Doubles (Used as x 3 Dimensional Point or Vector)
gCoord z;
g3D() {}
g3D(gCoord x, gCoord y, gCoord z) : g2D(x,y), z(z) {}
explicit g3D(bool Zero) {if(Zero) Clear();}
g3D(double* DDD) : g2D(DDD) {z=*++DDD;}
void Clear() {g2D::Clear(); z=0;}
g3D& operator*=(const gCoord& c) {g2D::operator*=(c); z*=c; return *this;}
the Clear() function is more clearly written as x=y=z=0; as are most of the others.
So 3D objects are not derived from 2D objects.
Since there is now a danger in the redundancy that a change in one class is not also changed in the other,
the classes are all kept in the same file and interleaved so that changes to one class are easy to implement in the other at the same time.
Vertices
g3Point and g2Point are for holding vertices and provide appropriate arithmetic operations.
The operator bool() in g3D and g2D makes it easy to compare the Vertex with the Origin.
Vectors
g3Vector and g2Vector have most of the usual functions. GetL2 returns the length squared; this saves a sqrt and is often used in trigonometry.
g2Vector::cwTo(const g2Vector& V) effectively returns the z component of the Cross Product as a quick way to test for clockwiseness (Assumes Right Hand Screw Rule and 2D).
GetPerpendicular() is useful for 3D Planes where the vector is the Plane Normal and you want a Vector on the Plane.
The operator bool() in g3D and g2D makes it easy to check the validity of Vectors (false means the Vector has all zero values).
Geometric Storage
Position Vector, gPV
gPV is a Position Vector and has a Point and a Vector.
It may describe a Plane (P as the Local Origin, V as the Normal), or Axially aligned Cuboid (P is one corner, V is the diagonal extents).
GetPlaneOrigin() returns the point on the Plane which is closest to the Global Origin.
Others
g3Cr and g2Cr have a Vertex and a double which can be used as Centre and Radius of Spheres and Circles.
g3Circle has a g3Cr (sphere) and an Axis to indicate the Normal to the plane that the Circle is in.
g3Arc has a g3Circle and a g3PP to hold the Start and End Points of the Arc (which assumes right hand rule).
The g3Arc has an efficient Hit test (see if a Point lies on a 3D Arc).
I've found the GetAngle() useful for helping with 3D Rotations:
Create a g3Arc with centre and Axis defining the Axis you want to rotate around, set Radius to 1.0 and use the start and end points describe the rotation.
GetAngle() will provide the rotation angle which is often required when calling 3D Graphics APIs.
If anyone thinks its worth me maintaining or updating any of the above, please e-mail me.