diamond

Shadow

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 the JavaScript version; there is an older Dart version. (This JavaScript version has been refactored; the Dart code has not kept up.) These pages run this JavaScript, which is public and unobfuscated. (Use your browser’s View Source facility.)

In Brief

To use Shadow, you decide on a geometric configuration:

projection

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.


Matrix

//==============================================================================
// A class for matrices. (We use plain Arrays for vectors.)
//==============================================================================

// Create a Matrix object from a JavaScript 2-D array.

function Shadow_Matrix(m) {
    this.height = m.length;
    this.width = m[0].length;   // Rows better be all same length!!
    
    // Copy array contents to avoid side-effects to parameter m.
    this.matrix = [];
    for (var row = 0; row < this.height; row++) {
        this.matrix[row] = [];
        for (var col = 0; col < this.width; col++) {
            this.matrix[row][col] = m[row][col];
        }
    }
}

//------------------------------------------------------------------------------

Shadow_Matrix.prototype.toString = function() {
    var s = [];
    for (var row = 0; row < this.matrix.length; row++) {
        s.push(this.matrix[row].join(','));
    }
    return s.join('\n');
};

//------------------------------------------------------------------------------
// Not an in-place operation. Hence the past-tense name, rather than a
// present-tense imperative.

Shadow_Matrix.prototype.transposed = function() {
    var result = [];
    for (var col = 0; col < this.width; col++) {
        result[col] = [];
        for (var row = 0; row < this.height; row++) {
            result[col][row] = this.matrix[row][col];
        }
    }
    return new Shadow_Matrix(result);
};

//------------------------------------------------------------------------------
// Special-case for applying matrices to vectors.
// Returns a plain JavaScript vector rather than a Matrix object.
// "Normal" order, that is, result = Mv with v a COLUMN vector.

Shadow_Matrix.prototype.apply = function(vector) {
    if (this.width != vector.length) {
        throw 'Shadow error: incompatible sizes in Matrix.apply().';
    }

    var result = [];
    for (var row = 0; row < this.height; row++) {
        result[row] = 0;
        for (var col = 0; col < this.width; col++) {
                result[row] += this.matrix[row][col] * vector[col];
        }
    }
    return result;
};

//------------------------------------------------------------------------------
// Special-case for applying matrices to vectors.
// Returns a plain JavaScript vector rather than a Matrix object.
// "Left-hand" order, that is, result = vM with v a ROW vector.

Shadow_Matrix.prototype.applyLeft = function(vector) {
    if (this.height != vector.length) {
        throw 'Shadow error: incompatible sizes in Matrix.applyLeft().';
    }

    var result = [];
    for (var col = 0; col < this.width; col++) {
        result[col] = 0;
        for (var row = 0; row < this.height; row++) {
                result[col] += this.matrix[row][col] * vector[row];
        }
    }
    return result; 
};

//------------------------------------------------------------------------------
// General case of multiplying two matrices.
// Returns M*other.

Shadow_Matrix.prototype.multBy = function(other) {
    if (this.width != other.height) {
        throw 'Shadow error: incompatible sizes in Matrix.multBy().';
    }
 
    var result = [];
    for (var row = 0; row < this.height; row++) {
        result[row] = [];
        for (var col = 0; col < other.width; col++) {
            var sum = 0;
            for (var k = 0; k < this.width; k++) {
                sum += this.matrix[row][k] * other.matrix[k][col];
            }
            result[row][col] = sum;
        }
    }
    return new Shadow_Matrix(result); 
};

//------------------------------------------------------------------------------
// Present tense implies in-place operation.

Shadow_Matrix.prototype.scale = function(scalar) {
    for (var row = 0; row < this.height; row++) {
        for (var col = 0; col < this.width; col++) {
            this.matrix[row][col] *= scalar;
        }
    }
};

//------------------------------------------------------------------------------

Shadow_Matrix.prototype.scaleElement = function(scalar, row, col) {
    this.matrix[row][col] *= scalar;
};

//------------------------------------------------------------------------------

Shadow_Matrix.prototype.setElement = function(value, row, col) {
    this.matrix[row][col] = value;
};

//------------------------------------------------------------------------------

Shadow_Matrix.prototype.at = function(row, col) {
    return this.matrix[row][col];
};

//------------------------------------------------------------------------------
// Special-case 3x3 matrix inverse.

Shadow_Matrix.prototype.inverse33 = function() {
    if (this.width != 3 || this.height != 3) {
        throw 'Shadow error: not 3x3 in Matrix.inverse33().';
    }            

    // Just for more readable code.
    var a = this.matrix[0][0];
    var b = this.matrix[0][1];
    var c = this.matrix[0][2];
    var d = this.matrix[1][0];
    var e = this.matrix[1][1];
    var f = this.matrix[1][2];
    var g = this.matrix[2][0];
    var h = this.matrix[2][1]; // Skip i,j since they are already
    var k = this.matrix[2][2]; // so overloaded with meanings.
    
    // Find determinant by evaluating sub-determinants.
    var determinant = a * (e*k - f*h) +
                      b * (f*g - k*d) +
                      c * (d*h - e*g);
    
    if (determinant === 0) {
        throw 'Shadow error: singular matrix in Matrix.inverse33().';
    }
    
    var 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]  ];
    
    var result = new Shadow_Matrix(rawResult);
    result.scale(1/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.

Shadow_Matrix.prototype.rightInverse34 = function() {
    if (this.height != 3 || this.width != 4) {
        throw 'Shadow error: not 3x4 in Matrix.rightInverse34().';
    }
    
    // Set M33 = M34 * M34t.
    
    var m33 = this.multBy(this.transposed());
    
    var m33inv = m33.inverse33();
    
    return this.transposed().multBy(m33inv);
};

 

Geometry

//==============================================================================
// Various geometric functions. All class methods in Dart version.
//==============================================================================

var _Shadow_Geometry = {};   // Just stores a bunch of utility functions.

// Easy enough to generalize into N-dimensional inner product.
// But in this library, it is an error to not be a 3-vector.
_Shadow_Geometry.dotProduct3 = function(X,Y) {
    if (X.length != 3 || Y.length != 3) {
        throw 'Shadow error: not a 3-vector in Geometry.dotProduct3().';
    }
    
    return X[0]*Y[0] + X[1]*Y[1] + X[2]*Y[2];
};

//------------------------------------------------------------------------------

_Shadow_Geometry.length3 = function(V) {
    return Math.sqrt(_Shadow_Geometry.dotProduct3(V, V));
};

//------------------------------------------------------------------------------

_Shadow_Geometry.crossProduct3 = function(X,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] ];
};

//------------------------------------------------------------------------------
//  Plane functions.

// v∘p = 0 defines plane through origin ⟂ to v.
// v∘(p - p0) defines plane through p0 ⟂ to v

/**     
 *  Return hpf where hpf(0) defines plane thru origin ⟂ to v.
 *  
 *  Hpf stands for homogeneous plane function.
 *  Derivation:
 *      * v∘p = 0 defines plane through origin ⟂ to v.
 *      * hpf ≡ v∘ is the partially-applied function
 *      * => hpf(p) = 0 defines plane thru origin ⟂ to v.
 */
_Shadow_Geometry.hpf = function(norm) {
    function result(p) {s
        return _Shadow_Geometry.dotProduct3(norm, p);
    }
    return result;
}

/**     
 *  Return pf where pf(p) = 0 defines plane ⟂ to v through p0.
 *  
 *  Pf stands for plane function.
 *  Derivation:
 *    * v∘(p - p0) = 0 defines plane through p0 ⟂ to v 
 *    * pf ≡ v∘ - v∘p0 is the partially-applied function.
 *    * => pf(p) = 0 defines plane ⟂ to v through p0
 */

_Shadow_Geometry.pf = function(norm, through) {
    function result(p) {
        var deltap = [p[0] - through[0], p[1] - through[1], p[2] - through[2]];
        return _Shadow_Geometry.dotProduct3(norm, deltap);
    }
    return result;
};

_Shadow_Geometry.pf2 = function(P, Q, R) {
    function result(p) {
        var a = (P[1]-Q[1]) * (P[2]-R[2]) - (P[2]-Q[2]) * (P[1]-R[1]);
        var b = (P[2]-Q[2]) * (P[0]-R[0]) - (P[0]-Q[0]) * (P[2]-R[2]);
        var c = (P[0]-Q[0]) * (P[1]-R[1]) - (P[1]-Q[1]) * (P[0]-R[0]);
        var d = -(a*P[0] + b*P[1] + c*P[2]);
        return a * p[0] + b * p[1] + c * p[2] + d;
    }
    return result;
};

//------------------------------------------------------------------------------

_Shadow_Geometry.pointInRect2 = function(P, minU, minV, maxU, maxV) {
    return  minU < P[0] && P[0] < maxU &&
            minV < P[1] && P[1] < maxV;
};

 

Config

//==============================================================================
// Starting values, passed in by user to Configuration constructor.
// These are reasonable starting values.

var _sampleSeed = {
     // These are points and distances in the (x,y,z) space.
     'viewNorm'  : [2, 2, 2],    // Viewplane normal vector.
     'eyeDist'   : 6,            // Distance of eye to origin.
     'planeDist' : 3,            // Distance of view plane to origin.
    
     // Dimensions of rect in view plane, that we "look through".
     'viewWidth' : 4,            // Width of view rect. 
     'viewHeight': 2,            // Height of view rect.

     // These are bounds of the drawing rect in our device (canvas) plane.
     // The corners of the viewplane get mapped to these points:
     //   [-viewWidth/2, -viewHeight/2] gets mapped to (devMinU, devMinV); 
     //   [+viewWidth/2, +viewHeight/2] gets mapped to (devMaxU, devMaxV).
     // To avoid aspect distortion, the drawing rect should have the same
     // proportions 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.
     'devMinU' :  0,
     'devMinV' :  0,
     'devMaxU' :  800,
     'devMaxV' :  400 
};

//------------------------------------------------------------------------------

function Shadow_Configuration(seed) {
    // Copy seed values.
    this.viewNorm  = seed.viewNorm;
    this.eyeDist   = seed.eyeDist;
    this.planeDist = seed.planeDist;
    
    this.viewWidth  = seed.viewWidth;
    this.viewHeight = seed.viewHeight;
             
    this.devMinU   = seed.devMinU;
    this.devMaxU   = seed.devMaxU;
    this.devMinV   = seed.devMinV;
    this.devMaxV   = seed.devMaxV;
  
    // Calculate derived values.
 
    this.devWidth  = this.devMaxU - this.devMinU;
    this.devHeight = this.devMaxV - this.devMinV;
   
    var viewNormLength = _Shadow_Geometry.length3(this.viewNorm);
    
    this.viewHat   = [0, 0, 0];
    this.eye       = [0, 0, 0];
    this.refPoint  = [0, 0, 0];
    
    for (var i = 0; i < 3; i++) {
        this.viewHat [i] = this.viewNorm[i] / viewNormLength;
        this.eye     [i] = this.eyeDist   * this.viewHat[i];
        this.refPoint[i] = this.planeDist * this.viewHat[i];
    }
    
    if (this.viewNorm[0] === 0 && this.viewNorm[1] === 0) {
        this.viewUp = [0, 1, 0];
    } else {
        this.viewUp = [0, 0, 1];
    }

    // Should come out to be eyeDist - planeDist.
    // this.eyeConst = _Shadow_Geometry.dotProduct3(this.viewHat, this.eye) + this.planeConst;
    this.eyeConst = this.eyeDist - this.planeDist

    var TOLERANCE = 1e-3;
  
    if (this.eyeConst > 0) {
        this.clipAhead  = this.eyeConst - TOLERANCE;
        this.clipBehind = this.eyeConst + TOLERANCE
    } else {
        this.clipConst  = this.eyeConst + TOLERANCE;
        this.clipBehind = this.eyeConst - TOLERANCE
    }

}

//------------------------------------------------------------------------------

Shadow_Configuration.prototype.visibility = function(p) {
    var currentConst = _Shadow_Geometry.dotProduct3(this.viewHat, p) - this.planeDist;
    
    if (this.eyeConst > 0) {
        if (currentConst < this.clipAhead) {     // In potential field of view.
            return 'ahead';
        } else if (currentConst > this.clipBehind) {
            return 'behind';
        } else { // Point is within TOLERANCE of view plane.
            return 'ideal';      
        }
    } else { // eyeConst <= 0
        if (currentConst > this.clipAhead) {  // In potential field of view.
            return 'ahead';
        } else if (currentConst < this.clipBehind) { 
            return 'behind';
        } else {
            return 'ideal';
        }
    }

}


Initializing

var _Shadow_Initial = { };   // The object that vends initial transform matrix values.

//------------------------------------------------------------------------------

_Shadow_Initial.M0 = function() {
   var M = [
        [ 1, 0, 0, 0],
        [ 0, 1, 0, 0],
        [ 0, 0, 1, 0],
        [ 0, 0, 0, 1]
    ];

    return new Shadow_Matrix(M);
};

//------------------------------------------------------------------------------
// Does not change after configuration is established.

_Shadow_Initial.M1 = function(config) {

    // Set these up just for more readable code.
    var u0 = config.viewHat[0];
    var u1 = config.viewHat[1];
    var u2 = config.viewHat[2];
    var u3 = -_Shadow_Geometry.dotProduct3(config.viewHat, config.refPoint);
    
    var e0 = config.eye[0];
    var e1 = config.eye[1];
    var e2 = config.eye[2];
    
    var 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 ] 
    ];

    return new Shadow_Matrix(M);
};

//------------------------------------------------------------------------------
// This one's tricky enough to do element-by-element.

_Shadow_Initial.M2 = function(config) {
    var M = new Array(3);

    for (var row = 0; row < 3; row++) {
        M[row] = new Array(4);
    }

    // c = up-direction vector x viewPlane direction vector 
    var c = _Shadow_Geometry.crossProduct3(config.viewUp, config.viewHat);
                    
    var denom = _Shadow_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;
                    
    c = _Shadow_Geometry.crossProduct3(config.viewHat, M[0]);

    denom = _Shadow_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;
    
    M[2][0] = config.refPoint[0];
    M[2][1] = config.refPoint[1];
    M[2][2] = config.refPoint[2];
    M[2][3] = 1;

    var Mμ = new Shadow_Matrix(M);
    return Mμ.rightInverse34();
};

//------------------------------------------------------------------------------
// Changes are made to M3 by the image methods shiftImage(), etc.

_Shadow_Initial.M3 = function() {
    var M = [
        [ 1, 0, 0],
        [ 0, 1, 0],
        [ 0, 0, 1]
    ];
    
    return new Shadow_Matrix(M);
};

//------------------------------------------------------------------------------

_Shadow_Initial.M4 = function(config) {
    // Just to make the following equation readable.
    
    var dw = config.devWidth;     // device rect width
    var dh = config.devHeight;    // device rect height

    // device middle coordinates horizontal and vertical.
    var uMid = (config.devMinU + config.devMaxU) / 2.0;
    var vMid = (config.devMinV + config.devMaxV)   / 2.0;

    var vw = config.viewWidth;
    var vh = config.viewHeight;
    
    var M = [
        [ dw/vw,      0, 0 ],
        [     0, -dh/vh, 0 ],   // Negative because canvas origin is top-left.
        [ uMid,    vMid, 1 ]
    ];

    return new  Shadow_Matrix(M);
};


ProjectedPoint

/**
 * 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 Bool describing the visibility of the point.
 *
 *  We use this type of hash for the return values:
 *
 *  { 
 *    XYZ:  [x, y, z],  // World coordinates. 
 *    UV :  [u, v],     // Display device coordinates. 
 *    vis:  Bool        // Visibility of point.
 *  }
 *
 */


Projector

// ==============================================================================
// Class for projecting object points into eye location, and finding
// where that line intersects the view plane.  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
// 

function Shadow_Projector(seed) {
    this.config = new Shadow_Configuration(seed);

    this.TOLERANCE = 1e-3;  // Tolerance for points to be ideal.
    
    this.applyObjectTransform = true;   // False for drawing axes.
    
    
    // Matrices, set using config and derived. M0 and M3 are generally the 
    // only ones changed after initialization; then Mo is recalculated.

    this.M0 = _Shadow_Initial.M0();              // 4x4;  Object transformations. Starts out as identity.
    this.M1 = _Shadow_Initial.M1(this.config);   // 4x4;  Perspective or parallel projection.
    this.M2 = _Shadow_Initial.M2(this.config);   // 4x3;  Right inverse of parametrization.
    this.M3 = _Shadow_Initial.M3();              // 3x3;  Image adjustment. Starts out as identity.
    this.M4 = _Shadow_Initial.M4(this.config);   // 3x3;  Display transformation
    
    this.Ma = undefined;  // 4x3;  Overall, without object xform = M1∙M2∙M3∙M4
    this.Mo = undefined;  // 4x3;  Overall transform matrix = M0∙M1∙M2∙M3∙M4 
    
    this.setMo();
}

//------------------------------------------------------------------------------
// Gets called repeatedly after changes to M0 or M3.

Shadow_Projector.prototype.setMo = function() {     
    var  M33 = this.M3.multBy(this.M4 );  // M33 =       M3M4
    this.Ma  = this.M2.multBy(     M33);  // Ma  =     M2M3M4
    this.Ma  = this.M1.multBy(this.Ma );  // Ma  =   M1M2M3M4
    this.Mo  = this.M0.multBy(this.Ma );  // Mo  = M0M1M2M3M4  
};

//------------------------------------------------------------------------------
// Take point P, apply all transformations to it, and return a projective
// ProjectedPoint object (see above). This is where we use the *overall* transform matrix Mo.

Shadow_Projector.prototype.projectPoint = function(P) {
    var UVW;           // The homogeneous coords of the 2D point.
    var result = {};
    
    result.XYZ = P.slice(0);
    var P2 = [P[0], P[1], P[2], 1];
    
    if (this.applyObjectTransform) { 
        UVW = this.Mo.applyLeft(P2);    // Normal projection.
    } else { 
        UVW = this.Ma.applyLeft(P2);    // Skip M0; for drawing coordinate axes.
    } 
    
    result.UV = [UVW[0] / UVW[2], UVW[1] / UVW[2]];    // U,V coords of result.
    
    var pointIsAheadOfEye;
    if (this.applyObjectTransform) { 
        var PP = this.objectXformPoint(P);
        pointIsAheadOfEye = this.config.visibility(PP) == 'ahead';
    } else {
        pointIsAheadOfEye = this.config.visibility(P) == 'ahead';
    }
    
    var pointIsInConeOfVision = _Shadow_Geometry.pointInRect2(
        result.UV, 
        this.config.devMinU, this.config.devMinV,
        this.config.devMaxU, this.config.devMaxV
    )
   
    result.isVisible = pointIsAheadOfEye && pointIsInConeOfVision;
       
    return result;
};

//------------------------------------------------------------------------------
// Perform only the object transform on the point. This is useful
// for figuring out depth order.

Shadow_Projector.prototype.objectXformPoint = function(P) {
    var PP = [ P[0], P[1], P[2], 1 ];
    var transformedPP = this.M0.applyLeft(PP);
    return [ transformedPP[0]/transformedPP[3], 
             transformedPP[1]/transformedPP[3], 
             transformedPP[2]/transformedPP[3] ];
};

//==============================================================================
// Methods for transforming the projected image in its 2D space.
// They work by changing the M3 matrix.

Shadow_Projector.prototype.spinImage = function(θ) {
    var R = [ [  Math.cos(θ), Math.sin(θ), 0 ],
              [ -Math.sin(θ), Math.cos(θ), 0 ],
              [            0,           0, 1 ] ];
    
    var rotationMatrix = new Shadow_Matrix(R);
    this.M3 = this.M3.multBy(rotationMatrix);
    this.setMo();    // Doing it here is slower etc... (see above).
};
    
//------------------------------------------------------------------------------

Shadow_Projector.prototype.shiftImage = function(du, dv) {
    var R = [ [ 1,  0, 0 ],
              [ 0,  1, 0 ],
              [du, dv, 1 ] ];

    var shiftMatrix = new Shadow_Matrix(R);
    this.M3 = this.M3.multBy(shiftMatrix);
    this.setMo();     // Doing it here is slower etc... (see above).
};

//------------------------------------------------------------------------------

Shadow_Projector.prototype.scaleImage = function(mu, mv) {
    var R = [ [ mu,  0, 0 ],
              [  0, mv, 0 ],
              [  0,  0, 1 ] ];

    var scaleMatrix = new Shadow_Matrix(R);
    this.M3 = this.M3.multBy(scaleMatrix);
    this.setMo();     // Doing it here is slower etc... (see above).
};

//==============================================================================
// Methods for transforming the object in its 3D space.
// They work by changing the M0 matrix.

Shadow_Projector.prototype.spinObject = function(axis, θ) {
    var R;
    if (axis == 'z') {
        R = [ [  Math.cos(θ), Math.sin(θ), 0, 0 ],
              [ -Math.sin(θ), Math.cos(θ), 0, 0 ],
              [            0,           0, 1, 0 ],
              [            0,           0, 0, 1 ] ];

    } else if (axis == 'y') {
        R = [ [  Math.cos(θ), 0, -Math.sin(θ), 0 ],
              [            0, 1,            0, 0 ],
              [  Math.sin(θ), 0,  Math.cos(θ), 0 ],
              [            0, 0,            0, 1 ] ];
    } else if (axis == 'x') {
        R = [ [ 1,            0,           0, 0 ],
              [ 0,  Math.cos(θ), Math.sin(θ), 0 ],
              [ 0, -Math.sin(θ), Math.cos(θ), 0 ],
              [ 0,            0,           0, 1 ] ];
    } else {
        throw 'Shadow error: ' + axis + ' is not an axis type in Projector.spinObject().';
    }

    var rotationMatrix = new Shadow_Matrix(R);
    this.M0 = this.M0.multBy(rotationMatrix);
    
    this.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.
Shadow_Projector.prototype.spinObjectFromScratch = function(axis, θ) {
    this.M0 = _Shadow_Initial.M0();  // i.e. reset it to identity transform.
    this.spinObject(axis, θ);
};

//------------------------------------------------------------------------------

Shadow_Projector.prototype.shiftObject = function(dx,dy,dz) {
    var R = [ [ 1,  0,  0, 0 ],
              [ 0,  1,  0, 0 ],
              [ 0,  0,  1, 0 ],
              [dx, dy, dz, 1 ] ];
    
    var shiftMatrix = new Shadow_Matrix(R);
    this.M0 = this.M0.multBy(shiftMatrix);
    this.setMo();    // Doing it here is slower etc... (see above).
};
            
// For absolute operations etc... (see above).
Shadow_Projector.prototype.shiftObjectFromScratch = function(dx,dy,dz) {
    this.M0 = _Shadow_Initial.M0();
    this.shiftObject(dx,dy,dz);
};

//------------------------------------------------------------------------------

Shadow_Projector.prototype.scaleObject = function(mx,my,mz) {
   var R = [ [ mx,  0,  0, 0 ],
             [  0, my,  0, 0 ],
             [  0,  0, mz, 0 ],
             [  0,  0,  0, 1 ] ];
    
    var scaleMatrix = new Shadow_Matrix(R);
    this.M0 = this.M0.multBy(scaleMatrix);
    this.setMo();    // Doing it here is slower etc... (see above).
};

// For absolute operations etc... (see above).
Shadow_Projector.prototype.scaleObjectFromScratch = function(mx,my,mz) {
    this.M0 = _Shadow_Initial.M0();
    this.scaleObject(mx,my,mz);
};

//------------------------------------------------------------------------------
// Will anyone ever use this?

Shadow_Projector.prototype.perspectXformObject = function(kx,ky,kz) {
    for (var row = 0; row < 4; row++) {
        var newValue = kx * this.M0.at(row, 0) +
                       ky * this.M0.at(row, 1) +
                       kz * this.M0.at(row, 2) +
                            this.M0.at(row, 3);
        this.M0.setElement(newValue, row, 3);
    }
    
    this.setMo();    // Doing it here is slower etc... (see above).
};

//------------------------------------------------------------------------------
// 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.

// TODO: Update these to the hvpf and vpf as done in Swift.

Shadow_Projector.prototype.planeThroughOriginFunction = function(p) {
    return _Shadow_Geometry.dotProduct3(this.config.viewNorm, p);
};

Shadow_Projector.prototype.nearSide = function(p) {
    var p2 = this.objectXformPoint(p);
    return this.planeThroughOriginFunction(p2) > 0;
};

//------------------------------------------------------------------------------
// Finds which edge (PQ or RS) is in front of the other.
// Depends only on having the eye coordinates.

Shadow_Projector.prototype.frontEdge = function(P,Q, R,S) {
    var pf = _Shadow_Geometry.pf2(P,Q,this.config.eye);

    var FpqeOfR = pf(R);    // This is general plane function,
    var FpqeOfS = pf(S);    // not planeThroughOrigin.

    pf = _Shadow_Geometry.pf2(R,S,this.config.eye);
    var FrseOfP = pf(P);
    var FrseOfQ = pf(Q);

    if ( (((FpqeOfR>0) && (FpqeOfS>0)) || ((FpqeOfR<0) && (FpqeOfS<0))) || 
         (((FrseOfP>0) && (FrseOfQ>0)) || ((FrseOfP<0) && (FrseOfQ<0))) ) {
        return 'neitherEdge';   // Nowhere near each other (from our eye).
    } else {
        pf = _Shadow_Geometry.pf2(P,Q,R);

        var FpqrOfEtimesFpqrOfS = 
            pf(this.config.eye) * pf(S);

        if (FpqrOfEtimesFpqrOfS > this.TOLERANCE) {
            return 'secondEdge';    // RS occludes PQ.
        } else if (FpqrOfEtimesFpqrOfS < -this.TOLERANCE) {
            return 'firstEdge';     // PQ occludes RS.
        } else {
            return 'neitherEdge';   // They intersect.
        }
    }
};

//------------------------------------------------------------------------------

Shadow_Projector.prototype.zSort = function(pointArray) {
    var numPoints = pointArray.length;
    var distanceArray = new Array(numPoints);
    
    for (var i = 0; i < numPoints; i++) {
    
        var xformedPoint = this.objectXformPoint(pointArray[i]);
        
        var vectorToEye = [ this.config.eye[0] - xformedPoint[0],
                            this.config.eye[1] - xformedPoint[1],
                            this.config.eye[2] - xformedPoint[2] ];

        var 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(function(a,b) { return b[1]-a[1]; });
    var result = new Array(numPoints);
    for (i = 0; i < numPoints; i++) {
        result[i] = distanceArray[i][0];
    }
    return result;
};


 

Drawer

//==============================================================================
// Class for managing drawing to an HTML context. All HTML dependencies
// are encapsulated in this class.

function Shadow_Drawer(projector, context) {
    this.projector = projector;
    this.htmlContext = context;
    this._currentProjPt = undefined;
}

//------------------------------------------------------------------------------

Shadow_Drawer.prototype.clear = function(color) {
    if (color === undefined) {
        color = 'white';
    }

    var savedColor = this.htmlContext.fillStyle;
    this.htmlContext.fillStyle = color;
    this.htmlContext.fillRect(
    // Here we apply knowledge that V increases in up direction.
        this.projector.config.devMinU , this.projector.config.devMinV, 
        this.projector.config.devWidth, this.projector.config.devHeight 
    );
    this.htmlContext.fillStyle = savedColor;
};

//------------------------------------------------------------------------------

Shadow_Drawer.prototype.dotAt = function(P) {
    var pProj = this.projector.projectPoint(P);
    this.htmlContext.fillRect(pProj.UV[0]-1, pProj.UV[1]-1, 2, 2);
};

//------------------------------------------------------------------------------

Shadow_Drawer.prototype.drawSegment = function(P, Q) {
    var pProj = this.projector.projectPoint(P);
    var qProj = this.projector.projectPoint(Q);

    this.htmlContext.beginPath();
    if (pProj.isVisible && qProj.isVisible ) {
        this.htmlContext.moveTo(pProj.UV[0], pProj.UV[1]);
        this.htmlContext.lineTo(qProj.UV[0], qProj.UV[1]);
    } else if (pProj.isVisible || qProj ) {
        // Make a the visible one.
        var a, b;
        if (pProj.isVisible)  {
            a = P.slice(0);     // Unnecessary copy??
            b = Q.slice(0);
        } else {
            a = Q.slice(0);
            b = P.slice(0);
        }
        
        // Find point at which projection is off-screen, with 
        // resolution of 1 in 2^7 = 128.
        var mid = new Array(3);
        for (var i = 1; i < 7; i++) {
            mid[0] = (a[0] + b[0]) / 2;
            mid[1] = (a[1] + b[1]) / 2;
            mid[2] = (a[2] + b[2]) / 2;
            
            var midProj = this.projector.projectPoint(mid);
            if (midProj.isVisible) {
                a = mid.slice(0);   // Unnecessary copy??
            } else {
                b = mid.slice(0);
            }
        }

        var aProj = this.projector.projectPoint(a);
        
        if (pProj.isVisible) {
            this.htmlContext.moveTo(pProj.UV[0], pProj.UV[1]);
        } else {
            this.htmlContext.moveTo(qProj.UV[0], qProj.UV[1]);
        }
        
        this.htmlContext.lineTo(aProj.UV[0], aProj.UV[1]);
    }
    this.htmlContext.stroke();
    
    this._currentProjPt = qProj;   // In case we're called by lineTo().
};

//------------------------------------------------------------------------------

Shadow_Drawer.prototype.moveTo = function(P) {
    this._currentProjPt = this.projector.projectPoint(P);
    this.htmlContext.moveTo(this._currentProjPt.UV[0], this._currentProjPt.UV[1]);
};

//------------------------------------------------------------------------------
// Inefficient to pass XYZ back in again and re-project it.

Shadow_Drawer.prototype.lineTo = function(P) {
    this.drawSegment(this._currentProjPt.XYZ, P);
};

//------------------------------------------------------------------------------
// Draw a cube centered at C with side length s.
// Useful as a sanity check while debugging.
// Consider v0,1,2,3 to be vertices of one face, v4,5,6,7 of opposite face.

Shadow_Drawer.prototype.drawCube = function(C, s) {
    var v = new Array(8);    // Array of cube vertices.
    var s2 = s/2;
    
    for (var i = 0; i < 8; i++) {
        v[i] = C.slice(0);   // 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;
                    
    this.htmlContext.lineWidth = 1;
    this.htmlContext.strokeStyle = 'black';
    
    // Draw first square.
    this.htmlContext.beginPath();
    this.moveTo(v[0]);
    this.lineTo(v[1]);
    this.lineTo(v[2]);
    this.lineTo(v[3]);
    this.htmlContext.closePath();
    this.htmlContext.stroke();
    
    // Draw second square.
    this.htmlContext.beginPath();
    moveTo(v[4]);
    this.lineTo(v[5]);
    this.lineTo(v[6]);
    this.lineTo(v[7]);
    this.htmlContext.closePath();
    this.htmlContext.stroke();
    
    // Connect squares.
    this.drawSegment(v[0],v[4]);
    this.drawSegment(v[1],v[5]);
    this.drawSegment(v[2],v[6]);
    this.drawSegment(v[3],v[7]);
};

//------------------------------------------------------------------------------

Shadow_Drawer.prototype.drawSphere = function(C, r, botColor, topColor, wantStroke, strokeColor) {
    if (wantStroke === undefined) {
        wantStroke = true;
    }
    if (botColor === undefined) {
        botColor = '#666';
    }
    if (topColor === undefined) {
        topColor = '#FFF';
    }

    var pc = this.projector.projectPoint(C);
    if (!pc.isVisible) {
        return;
    }

    var n = new Array(6);    // Array of neighborhood points.
    var r2 = r/2;
    
    for (var i = 0; i < 6; i++) {
        n[i] = C.slice(0);   // Start with all vertices copies of center. 
    }

    // 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.
    var pn = new Array(6);
    for (i = 0; i < 6; i++) {
        pn[i] = this.projector.projectPoint(n[i]);
    }

    var sum = 0;
    for (var i = 0; i < 6; i++) {
        var du = pc.UV[0] - pn[i].UV[0];
        var dv = pc.UV[1] - pn[i].UV[1];
        sum += du*du + dv*dv;
    }
    var screenRadius = Math.sqrt(sum/6);     // Root mean square value.

    this.htmlContext.beginPath();
    this.htmlContext.arc(pc.UV[0], pc.UV[1], screenRadius, 0, 2*Math.PI, false);
    var grd = this.htmlContext.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);
    this.htmlContext.fillStyle = grd;            
    this.htmlContext.fill();

    if (wantStroke) {
        var savedWidth = this.htmlContext.lineWidth;
        var savedStyle = this.htmlContext.strokeStyle;
        this.htmlContext.lineWidth = 1;
        if (!strokeColor) {
            this.htmlContext.strokeStyle = 'white';
        } else {
            this.htmlContext.strokeStyle = strokeColor;
        }
        this.htmlContext.stroke();
        this.htmlContext.lineWidth = savedWidth;
        this.htmlContext.strokeStyle = savedStyle;
    }
};

//------------------------------------------------------------------------------

Shadow_Drawer.prototype.drawAxes = function(scale, useColors, useAxisFrame) {
    var savedFrame = this.projector.applyObjectTransform;
    var savedStrokeStyle = this.htmlContext.strokeStyle;
    
    var colors = useColors === undefined ? false : useColors
    
    this.applyObjectTransform = useAxisFrame === undefined ? false : !useAxisFrame;
    // Default is useAxisFrame == true => applyObjectTransform == false.

    var u = 1;      // u for unit.
    var m = 0.07;
    
    if (scale !== undefined) {
        u *= scale;
        m *= scale;
    }

    if (colors) {
        this.htmlContext.strokeStyle = 'green'
    }
    this.drawSegment([0, 0, 0], [u, 0,  0]);     // x axis, with "branding iron"  
    this.drawSegment([u, m, m], [u,-m, -m]);
    this.drawSegment([u,-m, m], [u, m, -m]);
    
    if (colors) {
        this.htmlContext.strokeStyle = 'red'
    }
    this.drawSegment([0, 0, 0], [ 0, u, 0   ]);
    this.drawSegment([0, u, 0], [ m, u, m   ]);
    this.drawSegment([0, u, 0], [-m, u, m   ]);
    this.drawSegment([0, u, 0], [ 0, u,-u/10]);
    
    if (colors) {
        this.htmlContext.strokeStyle = 'blue'
    }
    this.drawSegment([ 0, 0, 0], [ 0,  0, u]);
    this.drawSegment([-m, m, u], [ m,  m, u]);
    this.drawSegment([ m, m, u], [-m, -m, u]);
    this.drawSegment([-m,-m, u], [ m, -m, u]);
    
    this.projector.applyObjectTransform = savedFrame;
    this.htmlContext.strokeStyle = savedStrokeStyle;
};