Shadow is a source code library for computing 3D projections and rendering them in HTML5 web pages.
To see this code in action, click the Next link at top right, and continue from there.
To read the code, just scroll down in this page. Shown is an older Dart version; there is a newer JavaScript version, with better factoring. (I have not maintained the Dart code.) These pages actually run the JavaScript code, which is public and unobfuscated. (Use your browser’s View Source facility.)
To use Shadow, you decide on a geometric configuration:
Shadow comprises two main classes and several auxiliary classes. They are defined in dependency order. You can click the links to jump directly to them.
/**
* Elementary matrix operations. (For vectors, we just use plain Lists.)
*/
class Matrix {
int height = 3;
int width = 3;
List> contents;
// Default value is 3x3 identity matrix.
Matrix() {
contents = [ [1.0, 0.0, 0.0],
[0.0, 1.0, 0.0],
[0.0, 0.0, 1.0] ];
}
//------------------------------------------------------------------------------
Matrix.withArray(this.contents) {
// List should be a literal, not shared.
height = contents.length;
width = contents[0].length; // Rows better be all same length!!
}
//------------------------------------------------------------------------------
Matrix.withMatrix(Matrix other) {
final contents = new List>(other.height);
for (var r = 0; r < other.height; r++) {
// Unexpectedly, final can apply inside a loop where row gets reassigned.
final row = new List(other.width);
for (var c = 0; c < other.width; c++) {
row[c] = other.contents[r][c];
}
contents[r] = row;
}
height = other.height;
width = other.width;
}
//------------------------------------------------------------------------------
double at(int r, int c) {
return contents[r][c];
}
//------------------------------------------------------------------------------
String toString() {
List s = [];
for (var r = 0; r < contents.length; r++) {
s.add(contents[r].join(','));
}
return s.join('\n');
}
//------------------------------------------------------------------------------
// Not an in-place operation. Hence the past-tense name.
Matrix transposed() {
var result = new List>(width);
for (var col = 0; col < width; col++) {
result[col] = new List(height);
for (var row = 0; row < height; row++) {
result[col][row] = contents[row][col];
}
}
return new Matrix.withArray(result);
}
//------------------------------------------------------------------------------
// Special-case for applying matrices to vectors.
// Returns a plain Dart List rather than a Matrix object.
// "Normal" order, that is, result = Mv with v a COLUMN vector.
List apply(List vector) {
if (width != vector.length) {
throw 'Shadow error: incompatible sizes in Matrix.apply().';
}
var result = new List(height);
for (var row = 0; row < height; row++) {
result[row] = 0.0;
for (var col = 0; col < width; col++) {
result[row] += contents[row][col] * vector[col];
}
}
return result;
}
//------------------------------------------------------------------------------
// Special-case for applying matrices to vectors.
// Returns a plain Dart List rather than a Matrix object.
// "Left-hand" order, that is, result = vM with v a ROW vector.
List applyLeft(List vector) {
if (height != vector.length) {
throw 'Shadow error: incompatible sizes in Matrix.applyLeft().';
}
var result = new List(width);
for (var col = 0; col < width; col++) {
result[col] = 0.0;
for (var row = 0; row < height; row++) {
result[col] += contents[row][col] * vector[row];
}
}
return result;
}
//------------------------------------------------------------------------------
// General case of multiplying two matrices.
// Returns M*other.
Matrix multBy(Matrix other) {
if (width != other.height) {
throw 'Shadow error: incompatible sizes in Matrix.multBy().';
}
var result = new List>(height);
for (var row = 0; row < height; row++) {
result[row] = new List(other.width);
for (var col = 0; col < other.width; col++) {
var sum = 0.0;
for (var k = 0; k < width; k++) {
// Here we reach right into the other's contents.
sum += contents[row][k] * other.contents[k][col];
}
result[row][col] = sum;
}
}
return new Matrix.withArray(result);
}
//------------------------------------------------------------------------------
// In-place implied by present-tense. (As opposed, e.g. to ‘scaled’.)
void scale(double scalar) {
for (var row = 0; row < height; row++) {
for (var col = 0; col < width; col++) {
contents[row][col] *= scalar;
}
}
}
//------------------------------------------------------------------------------
void scaleElement(double scalar, int row, int col) {
contents[row][col] *= scalar;
}
//------------------------------------------------------------------------------
void setElement(double value, int row, int col) {
contents[row][col] = value;
}
//------------------------------------------------------------------------------
// Special-case 3x3 matrix inverse.
Matrix inverse33() {
if (width != 3 || height != 3) {
throw 'Shadow error: not 3x3 in Matrix.inverse33().';
}
// Just for more readable code.
final a = contents[0][0];
final b = contents[0][1];
final c = contents[0][2];
final d = contents[1][0];
final e = contents[1][1];
final f = contents[1][2];
final g = contents[2][0];
final h = contents[2][1]; // Skip i,j since they are already
final k = contents[2][2]; // so overloaded with meanings.
// Find determinant by evaluating sub-determinants.
final determinant = a * (e*k - f*h) +
b * (f*g - k*d) +
c * (d*h - e*g);
if (determinant == 0.0) {
// TODO: have some tolerance; check for
// denormalized number at least.
throw 'Shadow error: singular in Matrix.inverse33().';
}
final rawResult = [ [e*k - f*h, c*h - b*k, b*f - c*e],
[f*g - d*k, a*k - c*g, c*d - a*f],
[d*h - e*g, g*b - a*h, a*e - b*d] ];
final result = new Matrix.withArray(rawResult);
result.scale(1.0/determinant);
return result;
}
//------------------------------------------------------------------------------
// Special-case code for right-inverse of 3x4 matrix.
// Right-inverse X+ of X is Xt * (X * Xt)^-1, where Xt is
// transpose of X. If X is MxN, X+ is NxM.
Matrix rightInverse34() {
if (height != 3 ||width != 4) {
throw 'Shadow error: not 3x4 in Matrix.rightInverse().';
}
// Set M33 = M34 * M34t.
final transposed = this.transposed(); // Use "this" for clarity.
final m33 = this.multBy(transposed); // Ditto.
final m33inv = m33.inverse33();
return this.transposed().multBy(m33inv);
}
}
/**
* Various geometric convenience functions, scoped in a Class.
* (Contra the style guidelines. TODO: factor into another library.)
*/
class Geometry {
// Easy enough to generalize into N-dimensional inner product.
// But in this library, it is an error to not be a 3-vector.
static double dotProduct3(List x, List y) {
if (x.length != 3 || y.length != 3) {
throw 'Shadow error: not 3-vector in Geometry.dotProduct3().';
}
return x[0]*y[0] + x[1]*y[1] + x[2]*y[2];
}
//------------------------------------------------------------------------------
static double length3(List v) {
return sqrt(dotProduct3(v,v));
}
//------------------------------------------------------------------------------
static List crossProduct3(List x, List y) {
return [ x[1]*y[2] - x[2]*y[1],
x[2]*y[0] - x[0]*y[2],
x[0]*y[1] - x[1]*y[0] ];
}
//------------------------------------------------------------------------------
// Finds equation ax + by + cz + d = 0 of plane thru points P, Q, R.
static List planeFunctionCoefs(List P,
List Q,
List R) {
final a = (P[1]-Q[1]) * (P[2]-R[2]) - (P[2]-Q[2]) * (P[1]-R[1]);
final b = (P[2]-Q[2]) * (P[0]-R[0]) - (P[0]-Q[0]) * (P[2]-R[2]);
final c = (P[0]-Q[0]) * (P[1]-R[1]) - (P[1]-Q[1]) * (P[0]-R[0]);
final d = -(a*P[0] + b*P[1] + c*P[2]);
return [a, b, c, d]; // Coefficients of equation.
}
//------------------------------------------------------------------------------
// Evaluates plane function.
static double planeFunction(List P, List coefficients) {
return coefficients[0]*P[0] +
coefficients[1]*P[1] +
coefficients[2]*P[2] +
coefficients[3];
}
//------------------------------------------------------------------------------
static bool pointInRect(List P,
List leftBot,
List rightTop) {
return P[0] > leftBot[0] && P[0] < rightTop[0] &&
P[1] > leftBot[1] && P[1] < rightTop[1];
}
}
/**
* Encapsulates the values needed to specify a 3D environment.
*
* We pass an instance of this into Projector to initialize it.
* And we initialize *this* with a plain Map literal, for readability.
*/
class Config {
// Here are sample values and explanations.
// These are points and distances in the (x,y,z) space.
List viewNorm; // [2, 2, 2], Viewplane normal vector.
double eyeDist; // 6, Distance of eye to origin.
double planeDist; // 3, Distance of view plane to origin.
// Dimensions of rect in view plane, that we "look through".
double viewWidth; // 4, Width of view rect.
double viewHeight; // 2, Height of view rect.
// These are corners of the drawing rect in our device (canvas) plane.
// The corners of the view rect get mapped to these points:
// [-viewWidth/2, -viewHeight/2] gets mapped to devLeftBot;
// [+viewWidth/2, +viewHeight/2] gets mapped to devRightTop.
// To avoid aspect distortion, the drawing rect should have the same
// proportion as the view rect.
// Most commonly the drawing rect is identical to the canvas boundary.
// But it could be larger or smaller than the canvas.
List devLeftBot; // [0, 0]
List devRightTop; // [800, 400]
// We initialize with a Map literal, for readability at the call site.
Config(Map config) {
viewNorm = config['viewNorm'];
eyeDist = config['eyeDist'];
planeDist = config['planeDist'];
viewWidth = config['viewWidth'];
viewHeight = config['viewHeight'];
devLeftBot = config['devLeftBot'];
devRightTop = config['devRightTop'];
}
}
/**
* Values derived from the Config instance.
* Used internally in Projector.
* This is a passive structure; see the JavaScript version for a more active
* design that factors some code out of the Projector.
*/
class Derived {
List eye; // Center of perspectivity (eye location).
List refPoint; // Viewplane reference point.
List viewUp; // Viewplane up direction.
double clipAhead; // Viewplane eq evaluated at forward clip plane.
double clipBehind; // Viewplane eq evaluated at rear clip plane.
double eyeConst; // Viewplane eq evaluated at eye.
double planeConst; // Constant in eq of viewPlane.
double devLeft; // Coordinates (u,v) in the device
double devBot; // plane of the drawing rectangle.
double devRight; // More convenient to work with than
double devTop; // bottom-left and top-right points.
double devWidth;
double devHeight;
Derived() {
eye = [0.0,0.0,0.0];
refPoint = [0.0,0.0,0.0];
viewUp = [0.0,0.0,0.0];
// The rest can remain null; will be initialized by
// Projector.setViewPlanEquation().
}
}
/**
* Represents the projection of a point from the object space into the
* display rectangle. The original xyz coordinates are saved for
* convenience; the important new values are the display U and V, and
* a string describing the visibility of the point.
*/
class ProjectedPoint {
List XYZ; // World coordinates.
List UV; // Display device coordinates.
int vis; // Visibility status. BEHIND, etc.
static const double TOLERANCE = 1e-3; // Tolerance for point to be ideal.
// Eventually these should be enums;
// see http://news.dartlang.org/2013/04/enum-proposal-for-dart.html.
static const int BEHIND = 1; // Behind plane thru eyePlane.
static const int IDEAL = 2; // Within TOLERANCE of eyePlane.
static const int INVISIBLE = 3; // Ahead but out of cone of vision.
static const int VISIBLE = 4; // Visible.
//------------------------------------------------------------------------------
bool isVisible() {
return vis == VISIBLE;
}
}
/**
* Class for
* 1) Projecting object points into eye location
* 2) Finding where that line intersects the view plane
* 3) Mapping the view rect to the display rect.
* Knows nothing about drawing or HTML graphics contexts.
*
* See Penna & Patterson, "Projective Geometry and its Applications
* to Computer Graphics", 1986 Prentice-Hall, ISBN 0-13-730649-0
*
* This class is too big; the JavaScript version factors out the matrix
* initialization into helper objects.
*/
class Projector {
Config config; // Geometric layout of eye position and view frame.
bool applyObjectTransform = true; // false is for drawing axes.
// The following members are calculated from config and method invocations.
Derived derived; // Geometric values derived from config.
// Transform matrices. M0 and M3 are generally the
// only ones changed after initialization; then Mo is recalculated.
Matrix M0; // 4x4; Object transformations. Starts out as identity.
Matrix M1; // 4x4; Perspective or parallel projection. Rarely used.
Matrix M2; // 4x3; Right inverse of parametrization.
Matrix M3; // 3x3; Image adjustment. Starts out as identity.
Matrix M4; // 3x3; Display transformation
Matrix Ma; // 4x3; Overall, without object xform = M1∙M2∙M3∙M4
Matrix Mo; // 4x3; Overall transform matrix = M0∙M1∙M2∙M3∙M4
static const int X = 0; // Parameters to spinObject().
static const int Y = 1;
static const int Z = 2;
static const int NEITHER = 0; // Return values for frontEdge().
static const int FIRST = 1;
static const int SECOND = 2;
//------------------------------------------------------------------------------
Projector.withConfig(this.config) {
derived = new Derived();
setViewPlaneEquation();
initializeM0();
initializeM1();
initializeM2();
initializeM3();
initializeM4();
setMo();
}
//------------------------------------------------------------------------------
// Uses config information to set derived information.
void setViewPlaneEquation() {
// We keep these around just for readability.
derived.devLeft = config.devLeftBot [0];
derived.devRight = config.devRightTop[0];
derived.devBot = config.devLeftBot [1];
derived.devTop = config.devRightTop[1];
derived.devWidth = derived.devRight - derived.devLeft;
derived.devHeight = derived.devTop - derived.devBot;
final viewNormLength = Geometry.length3(config.viewNorm);
for (var i = 0; i < 3; i++) {
final viewHat = config.viewNorm[i] / viewNormLength;
derived.eye[i] = config.eyeDist * viewHat;
derived.refPoint[i] = config.planeDist * viewHat;
derived.viewUp[i] = 0.0;
}
if (config.viewNorm[0] == 0 && config.viewNorm[1] == 0) {
derived.viewUp[1] = 1.0;
} else {
derived.viewUp[2] = 1.0;
}
derived.planeConst = -Geometry.dotProduct3(config.viewNorm,
derived.refPoint);
// Equation of view plane is
// (viewNorm dot x) + planeConst = Fplane(x) = 0.
derived.eyeConst =
Geometry.dotProduct3(config.viewNorm, derived.eye) + derived.planeConst;
// eyeConst = Fplane(eye). If Fplane(p) has same sign
// as eyeConst, p is on same side of reference plane.
if (derived.eyeConst > 0.0) {
derived.clipAhead = derived.eyeConst - ProjectedPoint.TOLERANCE;
derived.clipBehind = derived.eyeConst + ProjectedPoint.TOLERANCE;
} else {
derived.clipAhead = derived.eyeConst + ProjectedPoint.TOLERANCE;
derived.clipBehind = derived.eyeConst - ProjectedPoint.TOLERANCE;
}
}
//------------------------------------------------------------------------------
// Changes are made to M0 by the methods shiftObject(), etc.
void initializeM0() {
final M = [
[ 1.0, 0.0, 0.0, 0.0],
[ 0.0, 1.0, 0.0, 0.0],
[ 0.0, 0.0, 1.0, 0.0],
[ 0.0, 0.0, 0.0, 1.0]
];
M0 = new Matrix.withArray(M);
}
//------------------------------------------------------------------------------
// Does not change after configuration is established.
void initializeM1() {
// Set these up just for more readable code.
final u0 = config.viewNorm[0];
final u1 = config.viewNorm[1];
final u2 = config.viewNorm[2];
final u3 = -Geometry.dotProduct3(config.viewNorm, derived.refPoint);
final e0 = derived.eye[0];
final e1 = derived.eye[1];
final e2 = derived.eye[2];
// We overflow 80-char width here for visual coherence.
final M = [
[ u1*e1 + u2*e2 + u3, -u0*e1 , -u0*e2 , -u0 ],
[ -u1*e0 , u0*e0 + u2*e2 + u3, -u1*e2 , -u1 ],
[ -u2*e0 , -u2*e1 , u0*e0 + u1*e1 + u3, -u2 ],
[ -u3*e0 , -u3*e1 , -u3*e2 , u0*e0 + u1*e1 + u2*e2 ]
];
M1 = new Matrix.withArray(M);
}
//------------------------------------------------------------------------------
// This one's tricky enough to do element-by-element.
void initializeM2() {
final M = [
[0.0, 0.0, 0.0, 0.0],
[0.0, 0.0, 0.0, 0.0],
[0.0, 0.0, 0.0, 0.0]
];
// c = up-direction vector x viewPlane direction vector
var c = Geometry.crossProduct3(derived.viewUp, config.viewNorm);
var denom = Geometry.length3(c);
M[0][0] = c[0] / denom;
M[0][1] = c[1] / denom;
M[0][2] = c[2] / denom;
M[0][3] = 0.0;
c = Geometry.crossProduct3(config.viewNorm, M[0]);
denom = Geometry.length3(c);
M[1][0] = c[0] / denom;
M[1][1] = c[1] / denom;
M[1][2] = c[2] / denom;
M[1][3] = 0.0;
M[2][0] = derived.refPoint[0];
M[2][1] = derived.refPoint[1];
M[2][2] = derived.refPoint[2];
M[2][3] = 1.0;
final Mmu = new Matrix.withArray(M);
M2 = Mmu.rightInverse34();
}
//------------------------------------------------------------------------------
// Changes are made to M3 by the image methods shiftImage(), etc.
void initializeM3() {
final M = [
[ 1.0, 0.0, 0.0],
[ 0.0, 1.0, 0.0],
[ 0.0, 0.0, 1.0]
];
M3 = new Matrix.withArray(M);
}
//------------------------------------------------------------------------------
void initializeM4() {
// Just to make the following equation readable.
final dw = derived.devWidth; // device rect width
final dh = derived.devHeight; // device rect height
// device middle coordinates horizontal and vertical.
final hMid = (derived.devLeft + derived.devRight) / 2.0;
final vMid = (derived.devBot + derived.devTop) / 2.0;
final vw = config.viewWidth;
final vh = config.viewHeight;
final M = [
[ dw/vw, 0.0, 0.0 ],
[ 0.0, -dh/vh, 0.0 ], // Negative because canvas origin is top-left.
[ hMid, vMid, 1.0 ]
];
M4 = new Matrix.withArray(M);
}
//------------------------------------------------------------------------------
// Gets called repeatedly after changes to M0 or M3.
void setMo() {
var M33 = M3.multBy(M4 ); // M33 = M3M4
Ma = M2.multBy(M33); // Ma = M2M3M4
Ma = M1.multBy(Ma ); // Ma = M1M2M3M4
Mo = M0.multBy(Ma ); // Mo = M0M1M2M3M4
}
//==============================================================================
// Methods for transforming the object in its 3D space.
// They work by changing the M0 matrix.
// 'a' is an angle in radians. We would prefer to use 'θ'.
void spinObject(int axis, double a) {
List> R;
if (axis == Z) {
R = [ [ cos(a), sin(a), 0.0, 0.0 ],
[ -sin(a), cos(a), 0.0, 0.0 ],
[ 0.0, 0.0, 1.0, 0.0 ],
[ 0.0, 0.0, 0.0, 1.0 ] ];
} else if (axis == Y) {
R = [ [ cos(a), 0.0, -sin(a), 0.0 ],
[ 0.0, 1.0, 0.0, 0.0 ],
[ sin(a), 0.0, cos(a), 0.0 ],
[ 0.0, 0.0, 0.0, 1.0 ] ];
} else if (axis == X) {
R = [ [ 1.0, 0.0, 0.0, 0.0 ],
[ 0.0, cos(a), sin(a), 0.0 ],
[ 0.0, -sin(a), cos(a), 0.0 ],
[ 0.0, 0.0, 0.0, 1.0 ] ];
} else {
throw 'Shadow error: ' + axis.toString() +
' is not an axis type in Projector.spinObject().';
}
final rotationMatrix = new Matrix.withArray(R);
M0 = M0.multBy(rotationMatrix);
setMo(); // Doing it here is slower because we could save up all
// the changes first, but saves the caller from remembering to do it.
}
// This combination is used when doing absolute operations,
// as opposed to incremental ones provided by previous function.
void spinObjectFromScratch(int axis, double a) {
initializeM0(); // i.e. reset it to identity transform.
spinObject(axis, a);
}
//------------------------------------------------------------------------------
void shiftObject(double dx, double dy, double dz) {
final R = [
[ 1.0, 0.0, 0.0, 0.0 ],
[ 0.0, 1.0, 0.0, 0.0 ],
[ 0.0, 0.0, 1.0, 0.0 ],
[ dx, dy, dz, 1.0 ]
];
final shiftMatrix = new Matrix.withArray(R);
M0 = M0.multBy(shiftMatrix);
setMo(); // Doing it here is slower etc... (see above).
}
// For absolute operations etc... (see above).
void shiftObjectFromScratch(double dx, double dy, double dz) {
initializeM0();
shiftObject(dx,dy,dz);
}
//------------------------------------------------------------------------------
void scaleObject(double mx, double my, double mz, double mw) {
for (var row = 0; row < 4; row++) {
// Could generalize more as 4D dot-product, but later, if ever.
M0.scaleElement(mx, row, 0);
M0.scaleElement(my, row, 1);
M0.scaleElement(mz, row, 2);
M0.scaleElement(mw, row, 3);
}
setMo(); // Doing it here is slower etc... (see above).
}
// For absolute operations etc... (see above).
void scaleObjectFromScratch(double mx, double my, double mz, double mw) {
initializeM0();
scaleObject(mx,my,mz,mw);
}
//------------------------------------------------------------------------------
// Will anyone ever use this?
void perspectXformObject(double kx, double ky, double kz) {
for (var row = 0; row < 4; row++) {
final newValue = kx * M0.at(row, 0) +
ky * M0.at(row, 1) +
kz * M0.at(row, 2) +
M0.at(row, 3);
M0.setElement(newValue, row, 3);
}
setMo(); // Doing it here is slower etc... (see above).
}
//==============================================================================
// Methods for transforming the projected image in its 2D space.
// They work by changing the M3 matrix.
void spinImage(double a) {
final R = [
[ cos(a), sin(a), 0.0 ],
[ -sin(a), cos(a), 0.0 ],
[ 0.0, 0.0, 1.0 ]
];
final rotationMatrix = new Matrix.withArray(R);
M3 = M3.multBy(rotationMatrix);
setMo(); // Doing it here is slower etc... (see above).
}
//------------------------------------------------------------------------------
void shiftImage(double du, double dv) {
List> R = [
[ 1.0, 0.0, 0.0 ],
[ 0.0, 1.0, 0.0 ],
[ du, dv, 1.0 ]
];
Matrix shiftMatrix = new Matrix.withArray(R);
M3 = M3.multBy(shiftMatrix);
setMo(); // Doing it here is slower etc... (see above).
}
//------------------------------------------------------------------------------
void scaleImage(double mu, double mv, double mw) {
for (var row = 0; row < 3; row++) {
M3.scaleElement(mu, row, 1);
M3.scaleElement(mv, row, 2);
M3.scaleElement(mw, row, 3);
}
setMo(); // Doing it here is slower etc... (see above).
}
//------------------------------------------------------------------------------
/**
* The key method of Projector. Finds intersection with viewPlane
* of line from point P to eye, maps that to display rect, yielding
* display coordinates (U,V). Also decides if point is actually in
* field of view. E.g. even if line P-to-eye intersects viewPlane,
* P could be *behind* eye position.
*
* Could be used by client of Shadow, but more likely is called
* indirectly when client calls moveTo(), lineTo(), drawSegment().
*/
ProjectedPoint projectPoint(List P) {
var result = new ProjectedPoint();
result.XYZ = new List.from(P);
List P2 = [P[0], P[1], P[2], 1.0];
// Perform the actual projection.
List UVW; // The homogeneous coords of the 2D point.
if (applyObjectTransform) {
UVW = Mo.applyLeft(P2); // Normal transform.
} else {
UVW = Ma.applyLeft(P2); // Skip M0; for drawing axes.
}
result.UV = [UVW[0] / UVW[2], UVW[1] / UVW[2]];
// Now find visibility class.
final currentConst = Geometry.dotProduct3(config.viewNorm, P) + derived.planeConst;
if (derived.eyeConst > 0.0) {
if (currentConst < derived.clipAhead) { // In potential field of view.
if (Geometry.pointInRect(result.UV, config.devLeftBot, config.devRightTop)) {
result.vis = ProjectedPoint.VISIBLE;
} else {
result.vis = ProjectedPoint.INVISIBLE;
}
} else {
if (currentConst > derived.clipBehind) {
result.vis = ProjectedPoint.BEHIND;
} else { // Point is within TOLERANCE of view plane.
result.vis = ProjectedPoint.IDEAL;
}
}
} else { // eyeConst <= 0
if (currentConst > derived.clipAhead) { // In potential field of view.
if (Geometry.pointInRect(result.UV, config.devLeftBot, config.devRightTop)) {
result.vis = ProjectedPoint.VISIBLE;
} else {
result.vis = ProjectedPoint.INVISIBLE;
}
} else {
if (currentConst < derived.clipBehind) {
result.vis = ProjectedPoint.BEHIND;
} else {
result.vis = ProjectedPoint.IDEAL;
}
}
}
return result;
}
//------------------------------------------------------------------------------
/**
* Perform only the object transform on the point. This is useful
* for figuring out depth order.
*/
List objectXformPoint(List P) {
final PP = [ P[0], P[1], P[2], 1.0 ]; // Homogeneous 3D point.
final transformedPP = M0.applyLeft(PP);
return [ transformedPP[0]/transformedPP[3],
transformedPP[1]/transformedPP[3],
transformedPP[2]/transformedPP[3] ];
}
//------------------------------------------------------------------------------
/**
* Evaluates plane function for plane through origin and normal to eye-origin
* vector. It is negative for points on the far side; positive for near side.
*/
double planeThroughOriginFunction(p) {
return Geometry.dotProduct3(config.viewNorm, p);
}
/**
* True if p is this side of the origin. For objects that are symmetric
* about origin, can be used for graying out or hiding back side.
*/
bool nearSide(p) {
final p2 = objectXformPoint(p);
return planeThroughOriginFunction(p2) > 0.0;
}
//------------------------------------------------------------------------------
/**
* Finds which edge (PQ or RS) is in front of the other.
* Depends on having the eye coordinates calculated by earlier function.
*/
int frontEdge(List P,List Q, List R,List S) {
var abcd = Geometry.planeFunctionCoefs(P, Q, derived.eye);
final FpqeOfR = Geometry.planeFunction(R, abcd);
final FpqeOfS = Geometry.planeFunction(S, abcd);
abcd = Geometry.planeFunctionCoefs(R, S, derived.eye);
final FrseOfP = Geometry.planeFunction(P, abcd);
final FrseOfQ = Geometry.planeFunction(Q, abcd);
if ( (FpqeOfR>0.0 && FpqeOfS>0.0 || FpqeOfR<0.0 && FpqeOfS<0.0) ||
(FrseOfP>0.0 && FrseOfQ>0.0 || FrseOfP<0.0 && FrseOfQ<0.0) ) {
return NEITHER; // Nowhere near each other (from our eye).
} else {
abcd = Geometry.planeFunctionCoefs(P,Q,R);
final FpqrOfEtimesFpqrOfS =
Geometry.planeFunction(derived.eye, abcd) *
Geometry.planeFunction(S, abcd);
if (FpqrOfEtimesFpqrOfS > ProjectedPoint.TOLERANCE) {
return SECOND; // RS occludes PQ.
} else if (FpqrOfEtimesFpqrOfS < -ProjectedPoint.TOLERANCE) {
return FIRST; // PQ occludes RS.
} else {
return NEITHER; // They intersect.
}
}
}
//------------------------------------------------------------------------------
/**
* Finds sign of x, with leeway of ±1e-6.
*
* For x < -1e-6, returns -1
* For -1e-6 < x < 1e-6, returns 0
* For x > 1e-6, returns +1
*/
int signum(double x) {
if (x < -1e-6) {
return -1;
} else if (x < 1e-6) {
return 0;
} else {
return 1;
}
}
//------------------------------------------------------------------------------
List zSort(List> pointArray) {
final numPoints = pointArray.length;
final distanceArray = new List>(numPoints);
for (var i = 0; i < numPoints; i++) {
// Strangely, these loop variables can be finals.
final xformedPoint = objectXformPoint(pointArray[i]);
final vectorToEye = [ derived.eye[0] - xformedPoint[0],
derived.eye[1] - xformedPoint[1],
derived.eye[2] - xformedPoint[2] ];
final distSquaredToEye = vectorToEye[0] * vectorToEye[0] +
vectorToEye[1] * vectorToEye[1] +
vectorToEye[2] * vectorToEye[2];
distanceArray[i] = [i, distSquaredToEye];
}
// Now sort distanceArray by second component of each entry.
distanceArray.sort((a,b) => signum(b[1]-a[1]));
final result = new List(numPoints);
for (var i = 0; i < numPoints; i++) {
result[i] = distanceArray[i][0];
}
return result;
}
} // end Projector
/**
* Manages drawing to an HTML5 2d context. All HTML dependencies
* are encapsulated in this class.
*
* Contains a Projector, so the relation between Projector and Drawer is
* at most many (P) to 1 (D), more often 1:1. However there is nothing
* to prohibit changing the Projector member of a Drawer, so the relation
* is effectively many-to-many.
*/
class Drawer {
Projector projector;
CanvasRenderingContext2D context; // An HTML5 graphics context.
ProjectedPoint _currentProjPt; // For ongoing lineTo() calls.
Drawer(this.projector, this.context);
//------------------------------------------------------------------------------
void clear([String color]) {
if (color == null) {
color = 'white';
}
var savedColor = context.fillStyle;
context.fillStyle = color;
context.fillRect(
projector.derived.devLeft , projector.derived.devBot,
projector.derived.devWidth, projector.derived.devHeight
);
context.fillStyle = savedColor;
}
//------------------------------------------------------------------------------
void dotAt(List P) {
final pProj = projector.projectPoint(P);
context.fillRect(pProj.UV[0]-1, pProj.UV[1]-1, 2, 2);
}
//------------------------------------------------------------------------------
void drawSegment(List P, List Q) {
final pProj = projector.projectPoint(P);
final qProj = projector.projectPoint(Q);
context.beginPath();
if (pProj.isVisible() && qProj.isVisible()) {
context.moveTo(pProj.UV[0], pProj.UV[1]);
context.lineTo(qProj.UV[0], qProj.UV[1]);
} else if (pProj.isVisible() || qProj.isVisible()) {
// A long else-branch!
// Make a the visible one.
var a, b;
if (pProj.isVisible()) {
a = P;
b = Q;
} else {
a = Q;
b = P;
}
// Find point at which projection is off-screen, with
// resolution of 1 in 2^7 = 128.
final mid = new List(3);
for (var i = 1; i < 7; i++) {
mid[0] = (a[0] + b[0]) / 2.0;
mid[1] = (a[1] + b[1]) / 2.0;
mid[2] = (a[2] + b[2]) / 2.0;
final midProj = projector.projectPoint(mid);
if (midProj.isVisible()) {
a = mid;
} else {
b = mid;
}
}
final aProj = projector.projectPoint(a);
if (pProj.isVisible()) {
context.moveTo(pProj.UV[0], pProj.UV[1]);
} else {
context.moveTo(qProj.UV[0], qProj.UV[1]);
}
context.lineTo(aProj.UV[0], aProj.UV[1]);
}
context.stroke();
_currentProjPt = qProj; // In case we're called by lineTo().
}
//------------------------------------------------------------------------------
void moveTo(List P) {
_currentProjPt = projector.projectPoint(P);
context.moveTo(_currentProjPt.UV[0], _currentProjPt.UV[1]);
}
//------------------------------------------------------------------------------
// Inefficient to pass in XYZ and have to re-project it.
void lineTo(List P) {
drawSegment(_currentProjPt.XYZ, P);
}
//------------------------------------------------------------------------------
/**
* Draw a cube centered at C with side length s.
* Useful as a sanity check while debugging.
*/
void drawCube(List C, double s) {
// Array of cube vertices.
final v = new List>(8);
// Consider v0,1,2,3 to be vertices of one face;
// v4,5,6,7 of opposite face.
final s2 = s/2.0;
for (var i = 0; i < 8; i++) {
v[i] = [C[0], C[1], C[2]]; // Start with all vertices copies of center.
}
// Expand in the x-direction.
v[0][0] += s2;
v[1][0] += s2;
v[2][0] += s2;
v[3][0] += s2;
v[4][0] -= s2;
v[5][0] -= s2;
v[6][0] -= s2;
v[7][0] -= s2;
// Expand in the y-direction.
v[1][1] += s2;
v[2][1] += s2;
v[6][1] += s2;
v[5][1] += s2;
v[0][1] -= s2;
v[3][1] -= s2;
v[7][1] -= s2;
v[4][1] -= s2;
// Expand in the z-direction.
v[3][2] += s2;
v[2][2] += s2;
v[6][2] += s2;
v[7][2] += s2;
v[0][2] -= s2;
v[1][2] -= s2;
v[5][2] -= s2;
v[4][2] -= s2;
context.lineWidth = 1;
context.strokeStyle = 'black';
// Draw first square.
context.beginPath();
moveTo(v[0]);
lineTo(v[1]);
lineTo(v[2]);
lineTo(v[3]);
context.closePath();
context.stroke();
// Draw second square.
context.beginPath();
moveTo(v[4]);
lineTo(v[5]);
lineTo(v[6]);
lineTo(v[7]);
context.closePath();
context.stroke();
// Connect squares.
drawSegment(v[0],v[4]);
drawSegment(v[1],v[5]);
drawSegment(v[2],v[6]);
drawSegment(v[3],v[7]);
}
//------------------------------------------------------------------------------
void drawSphere(List C, double r,
[String botColor, String topColor, bool wantStroke]) {
if (wantStroke == null) {
wantStroke = true;
}
if (botColor == null) {
botColor = '#666';
}
if (topColor == null) {
topColor = '#FFF';
}
final pc = projector.projectPoint(C);
if (!pc.isVisible()) {
return;
}
// Array of neighborhood points.
final n = new List>(6);
double r2 = r/2.0;
// Start with all vertices copies of center.
for (var i = 0; i < 6; i++) {
n[i] = new List.from(C);
}
// Now make n[0..5] the neighbors in the six 3-D directions.
n[0][0] += r2;
n[1][0] -= r2;
n[2][1] += r2;
n[3][1] -= r2;
n[4][2] += r2;
n[5][2] -= r2;
// Find all projections.
final pn = new List(6);
for (var i = 0; i < 6; i++) {
pn[i] = projector.projectPoint(n[i]);
}
var sum = 0.0;
for (var i = 0; i < 6; i++) {
final du = pc.UV[0] - pn[i].UV[0];
final dv = pc.UV[1] - pn[i].UV[1];
sum += du*du + dv*dv;
}
final screenRadius = sqrt(sum/6); // Root mean square value.
context.beginPath();
context.arc(pc.UV[0], pc.UV[1], screenRadius, 0, 2*PI, false);
var grd = context.createLinearGradient(pc.UV[0]-screenRadius,
pc.UV[1]-screenRadius,
pc.UV[0]+screenRadius,
pc.UV[1]+screenRadius);
grd.addColorStop(0, topColor);
grd.addColorStop(1, botColor);
context.fillStyle = grd;
context.fill();
if (wantStroke) {
final savedWidth = context.lineWidth;
final savedStyle = context.strokeStyle;
context.lineWidth = 1;
context.strokeStyle = 'white';
context.stroke();
context.lineWidth = savedWidth;
context.strokeStyle = savedStyle;
}
}
//------------------------------------------------------------------------------
void drawAxes([double scale, bool useAxisFrame]) {
final savedFrame = projector.applyObjectTransform;
projector.applyObjectTransform =
useAxisFrame == null ? false : !useAxisFrame;
// Default is useAxisFrame == true => applyObjectTransform == false.
double u = 1.0; // u for unit.
double m = 0.07;
if (scale != null) {
u *= scale;
m *= scale;
}
// x axis, with "branding iron"
drawSegment([0.0, 0.0, 0.0], [u, 0.0, 0.0]);
drawSegment([ u, m, m], [u, -m, -m]);
drawSegment([ u, -m, m], [u, m, -m]);
// y axis
drawSegment([0.0, 0.0, 0.0], [ 0.0, u, 0.0 ]);
drawSegment([0.0, u, 0.0], [ m, u, m ]);
drawSegment([0.0, u, 0.0], [-m, u, m ]);
drawSegment([0.0, u, 0.0], [ 0.0, u, -u/10.0]);
// z axis
drawSegment([ 0.0, 0.0, 0.0], [ 0.0, 0.0, u]);
drawSegment([ -m, m, u], [ m, m, u]);
drawSegment([ m, m, u], [ -m, -m, u]);
drawSegment([ -m, -m, u], [ m, -m, u]);
projector.applyObjectTransform = savedFrame;
}
} // end Drawer