import java.awt.*; import java.applet.*; import java.awt.event.*; import java.util.*; import java.awt.image.*; /** * applet that demonstrates my shadowing algorithm */ public class Shadower extends Applet { /** * azimuthal angle of the sun, in degrees. 0 is on the horizon, * 90 is directly overhead */ double solarAscension = 46; /** * compass direction towards the sun, 0 being due north, 90 being east */ double solarAzimuth = 1; /** * angle between the primary shadow and the line of absolute darkness */ double penumbralAngle = 46; /** * flag indicating whether the shadowing algorithm should be used */ boolean useShadow = true; /** * flag indicating whether ambient lighting should be used (possibly in * addition to angle-of-incidence lighting) */ boolean useAmbient = false; /** * flag indicating whether angle-of-incidence lighting should be used * (possibly in addition to ambient lighting) */ boolean useAOI = true; /** * the number of levels of expansion for the terrain hierarchical function */ public final static int LEVELS = 8; /** * the dimension of the picture and the altitude array */ public final static int DIM = ( 1 << LEVELS ); /** * 2D array of altitudes at each point */ double [][] altitudes = new double[ DIM + 1 ][ DIM + 1 ]; /** * the panel responsible for rendering the shadowed view of the terrain */ ShadowPanel panel; /** * Construct the applet; the actual work is done in buildPanel() */ public Shadower() { setForeground( Color.yellow ); setBackground( Color.black ); buildPanel(); } /** * Start the applet */ public void run() { setSize( 525, 425 ); } /** * run the terrain hierarchical function to fill in the altitudes array; also * draw any other terrain features of interest */ public void fillInAscensions() { Random ran = new Random(); // init the corners altitudes[ 0 ][ 0 ] = 0.0; altitudes[ DIM ][ 0 ] = 0.0; altitudes[ 0 ][ DIM ] = 0.0; altitudes[ DIM ][ DIM ] = 0.0; double damping = 1.2; double amplitude = 1.0; for ( int i = 0; i < LEVELS; i++ ) { int stride = ( 1 << ( LEVELS - i - 1 ) ); // interpolate and perturb the face centers for ( int x = stride; x <= DIM; x += 2 * stride ) { for ( int y = stride; y <= DIM; y += 2 * stride ) { altitudes[ x ][ y ] = 0.25 * ( altitudes[ x - stride ][ y - stride ] + altitudes[ x + stride ][ y - stride ] + altitudes[ x - stride ][ y + stride ] + altitudes[ x + stride ][ y + stride ] ) + ( ran.nextDouble() - 0.5 ) * amplitude; } } // interpolate and perturb the edge centers for ( int y = 0; y <= DIM; y += 2 * stride ) { for ( int x = stride; x <= DIM; x += 2 * stride ) { if ( ( y == 0 ) || ( y == DIM ) ) { altitudes[ x ][ y ] = 0.5 * ( altitudes[ x - stride ][ y ] + altitudes[ x + stride ][ y ] ) + ( ran.nextDouble() - 0.5 ) * amplitude; altitudes[ y ][ x ] = 0.5 * ( altitudes[ y ][ x - stride ] + altitudes[ y ][ x + stride ] ) + ( ran.nextDouble() - 0.5 ) * amplitude; } else { altitudes[ x ][ y ] = 0.25 * ( altitudes[ x - stride ][ y ] + altitudes[ x + stride ][ y ] + altitudes[ x ][ y - stride ] + altitudes[ x ][ y + stride ] ) + ( ran.nextDouble() - 0.5 ) * amplitude; altitudes[ y ][ x ] = 0.25 * ( altitudes[ y ][ x - stride ] + altitudes[ y ][ x + stride ] + altitudes[ y - stride ][ x ] + altitudes[ y + stride ][ x ] ) + ( ran.nextDouble() - 0.5 ) * amplitude; } } } amplitude *= Math.pow( 2.0, -damping ); } // put in some towers, height = 2 int N_TOWERS = 4; for ( int i = 0; i < N_TOWERS; i++ ) { int r = ran.nextInt(); if ( r < 0 ) r = -r; r = r % ( DIM - 10 ); int tx = r + 5; r = ran.nextInt(); if ( r < 0 ) r = -r; r = r % ( DIM - 10 ); int ty = r + 5; for ( int jx = 0; jx < 4; jx++ ) { for ( int jy = 0; jy < 4; jy++ ) { altitudes[ tx + jx ][ ty + jy ] = altitudes[ tx - 1 ][ ty - 1 ] + 0.1; } } } } /** * Set up all the GUI components, including adding listeners in appropriate places */ public void buildPanel() { // fill in the HF altitudes fillInAscensions(); // set up the component setSize( 525, 425 ); // add the pieces GridBagLayout gbl = new GridBagLayout(); setLayout( gbl ); GridBagConstraints gbc = new GridBagConstraints(); gbc.gridx = 0; gbc.gridy = 0; gbc.gridheight = 1; gbc.gridwidth = 1; gbc.weightx = 1.0; gbc.weighty = 0.2; gbc.ipadx = 0; gbc.ipady = 0; gbc.anchor = gbc.CENTER; gbc.fill = gbc.NONE; // scrollbar controlling the sun's azimuthal angle Scrollbar altitudeScroll = new Scrollbar( Scrollbar.HORIZONTAL, ( int ) solarAscension, 2, 0, 90 ); add( altitudeScroll ); altitudeScroll.addAdjustmentListener( new AdjustmentListener () { public void adjustmentValueChanged( AdjustmentEvent ae ) { solarAscension = ae.getValue(); panel.regenerateImage(); } } ); gbc.fill = gbc.HORIZONTAL; gbl.setConstraints( altitudeScroll, gbc ); // scrollbar controlling the shadow's softening angle Scrollbar softScroll = new Scrollbar( Scrollbar.HORIZONTAL, ( int ) penumbralAngle, 2, 0, 90 ); add( softScroll ); softScroll.addAdjustmentListener( new AdjustmentListener () { public void adjustmentValueChanged( AdjustmentEvent ae ) { penumbralAngle = ae.getValue(); panel.regenerateImage(); } } ); gbc.gridy = 1; gbl.setConstraints( softScroll, gbc ); // panel that displays the shadowed terrain panel = new ShadowPanel( altitudes, DIM, DIM ); gbc.fill = gbc.NONE; gbc.weighty = 1.0; gbc.gridy = 2; gbc.gridheight = 3; add( panel ); gbl.setConstraints( panel, gbc ); // scrollbar controlling the sun's compass direction Scrollbar surfaceAngleScroll = new Scrollbar( Scrollbar.HORIZONTAL, ( int ) solarAzimuth, 2, 0, 180 ); surfaceAngleScroll.addAdjustmentListener( new AdjustmentListener () { public void adjustmentValueChanged( AdjustmentEvent ae ) { solarAzimuth = ae.getValue(); panel.regenerateImage(); } } ); add( surfaceAngleScroll ); gbc.fill = gbc.HORIZONTAL; gbc.gridy = 5; gbc.gridheight = 1; gbc.weighty = 0.2; gbl.setConstraints( surfaceAngleScroll, gbc ); gbc.anchor = gbc.WEST; gbc.fill = gbc.NONE; Label altLabel = new Label( "Solar ascension angle" ); add( altLabel ); gbc.gridy = 0; gbc.gridx = 1; gbl.setConstraints( altLabel, gbc ); Label softLabel = new Label( "Shadow softening" ); gbc.gridy = 1; add( softLabel ); gbl.setConstraints( softLabel, gbc ); // checkbox controlling whether to use angle-of-incidence lighting gbc.gridy = 2; gbc.weighty = 1.0; Checkbox aoiBox = new Checkbox( "Angle of incidence shading", useAOI ); aoiBox.addItemListener( new ItemListener() { public void itemStateChanged( ItemEvent e ) { if ( e.getStateChange() == e.SELECTED ) { useAOI = true; } else { useAOI = false; } panel.regenerateImage(); } } ); add( aoiBox ); gbl.setConstraints( aoiBox, gbc ); // checkbox controlling whether to use shadows gbc.gridy = 3; Checkbox shadowBox = new Checkbox( "Shadowing", useShadow ); shadowBox.addItemListener( new ItemListener() { public void itemStateChanged( ItemEvent e ) { if ( e.getStateChange() == e.SELECTED ) { useShadow = true; } else { useShadow = false; } panel.regenerateImage(); } } ); add( shadowBox ); gbl.setConstraints( shadowBox, gbc ); // checkbox controlling whether to use ambient lighting gbc.gridy = 4; Checkbox ambientBox = new Checkbox( "Ambient light", useAmbient ); ambientBox.addItemListener( new ItemListener() { public void itemStateChanged( ItemEvent e ) { if ( e.getStateChange() == e.SELECTED ) { useAmbient = true; } else { useAmbient = false; } panel.regenerateImage(); } } ); add( ambientBox ); gbl.setConstraints( ambientBox, gbc ); gbc.gridy = 5; gbc.weighty = 0.2; Label angLabel = new Label( "Solar azimuth" ); add( angLabel ); gbl.setConstraints( angLabel, gbc ); panel.regenerateImage(); } /** * Panel that draws a shadowed and lighted view of the terrain map */ class ShadowPanel extends Panel { /** * the number of distinct colors allowed in the picture; if this number is * less than 255, the colors will be missing the brightest ones, not evenly * distributed over the range */ final static int N_COLORS = 255; /** * width of the image in pixels */ int xdim; /** * height of the image in pixels */ int ydim; /** * padding on the left side of the image in pixels */ int xpad; /** * size of this panel */ Dimension mySize = null; /** * array of altitudes */ double [][] y; /** * array of shadow values at each terrain pixel; 1 = totally obscured, 0 = no shadow here */ double [][] shade; /** * color index of each pixel in the terrain map (the result of the lighting and * shadowing calculations) */ int [][] color_index; /** * indicator whether each pixel has been visited by the shadowing algorithm */ boolean [][] visited; /** * memory buffer of color indices used to generate the MemoryImageSource */ int [] membuf; /** * image producer for the image of the terrain */ MemoryImageSource source; /** * image of the terrain that gets rendered */ Image memage = null; /** * color model used in generating the image of the terrain */ DirectColorModel color_model = new DirectColorModel( 32, 255 << 16, 255 << 8, 255 ); /** * flag indicating that the image is currently drawing; if this flag is true, * new redraws (i.e. calls to regenerateImage() ) are suppressed */ boolean needsRedraw = false; int [] sideStartX; int [] sideEndX; int [] sideDX; int [] sideStartY; int [] sideEndY; int [] sideDY; double lx, ly, lz; /** * constructor for a Panel that displays a rendered image of terrain * @param altitudes 2D array of terrain heights at each pixel * @param xdim width of the terrain map * @param ydim height of the terrain map */ public ShadowPanel( double [][] altitudes, int xdim, int ydim ) { this.y = altitudes; // Figure out the size of this panel and the necessary padding to // center the image left-right int xsize = xdim; xpad = 0; if ( xsize < 200 ) { xpad = ( 200 - xsize ) / 2; xsize = 200; } mySize = new Dimension( xsize, ydim ); setSize( xsize, ydim ); this.xdim = xdim; this.ydim = ydim; // allocate local arrays shade = new double[ y.length ][ y[ 0 ].length ]; color_index = new int[ xdim ][ ydim ]; visited = new boolean[ y.length ][ y[ 0 ].length ]; membuf = new int[ xdim * ydim ]; // allocate the direction-from-side arrays used for traverses, which always // occur in the +x or +y direction. The index order is NESW sideStartX = new int[ 4 ]; sideStartX[ 0 ] = 0; sideStartX[ 1 ] = xdim - 1; sideStartX[ 2 ] = 0; sideStartX[ 3 ] = 0; sideEndX = new int[ 4 ]; sideEndX[ 0 ] = xdim - 1; sideEndX[ 1 ] = xdim - 1; sideEndX[ 2 ] = xdim - 1; sideEndX[ 3 ] = 0; sideStartY = new int[ 4 ]; sideStartY[ 0 ] = 0; sideStartY[ 1 ] = 0; sideStartY[ 2 ] = ydim - 1; sideStartY[ 3 ] = 0; sideEndY = new int[ 4 ]; sideEndY[ 0 ] = 0; sideEndY[ 1 ] = ydim - 1; sideEndY[ 2 ] = ydim - 1; sideEndY[ 3 ] = ydim - 1; sideDX = new int[ 4 ]; sideDX[ 0 ] = 1; sideDX[ 1 ] = 0; sideDX[ 2 ] = 1; sideDX[ 3 ] = 0; sideDY = new int[ 4 ]; sideDY[ 0 ] = 0; sideDY[ 1 ] = 1; sideDY[ 2 ] = 0; sideDY[ 3 ] = 1; // set up the image producer for the rendered terrain image source = new MemoryImageSource( xdim, ydim, color_model, membuf, 0, xdim ); source.setAnimated( true ); memage = createImage( source ); // scale the terrain altitudes to lie between -1 and 1 double ymax = 0.0; double ymin = 0.0; for ( int i = 0; i < xdim; i++ ) { for ( int j = 0; j < ydim; j++ ) { if ( y[ i ][ j ] > ymax ) ymax = y[ i ][ j ]; if ( y[ i ][ j ] < ymin ) ymin = y[ i ][ j ]; } } for ( int i = 0; i < xdim; i++ ) { for ( int j = 0; j < ydim; j++ ) { y[ i ][ j ] = ( ( y[ i ][ j ] - ymin ) / ( ymax - ymin ) ) * 2.0 - 1.0; } } } double a, b; /** * recompute the shadow fraction everywhere based on the current position of the * sun. The results are stored in the class variable */ public void updateShadows() { long startTime = System.currentTimeMillis(); // from the solar bearing, find the "main" side and the "secondary" side; // the main side is defined as the side from which all edge pixels start // a traverse; the secondary side is the side from which some, all, or no // edge pixels start a traverse int primarySide, secondarySide; if ( solarAzimuth == 0 ) { primarySide = 0; secondarySide = -1; } else if ( solarAzimuth <= 45 ) { primarySide = 0; secondarySide = 1; } else if ( solarAzimuth < 90 ) { primarySide = 1; secondarySide = 0; } else if ( solarAzimuth == 90 ) { primarySide = 1; secondarySide = -1; } else if ( solarAzimuth <= 135 ) { primarySide = 1; secondarySide = 2; } else if ( solarAzimuth < 180 ) { primarySide = 2; secondarySide = 1; } else if ( solarAzimuth == 180 ) { primarySide = 2; secondarySide = -1; } else if ( solarAzimuth <= 225 ) { primarySide = 2; secondarySide = 3; } else if ( solarAzimuth < 270 ) { primarySide = 3; secondarySide = 2; } else if ( solarAzimuth == 270 ) { primarySide = 3; secondarySide = -1; } else if ( solarAzimuth <= 315 ) { primarySide = 3; secondarySide = 0; } else { primarySide = 0; secondarySide = 3; } // clear out the visited array for ( int i = 0; i < xdim; i++ ) { for ( int j = 0; j < ydim; j++ ) visited[ i ][ j ] = false; } // set the sign of the horizontal and vertical steps taken on a traverse int di_sign_major = 0; int dj_sign_major = 0; switch ( primarySide ) { case 0 : dj_sign_major = 1; break; case 1 : di_sign_major = -1; break; case 2 : dj_sign_major = -1; break; case 3 : di_sign_major = 1; break; } int di_sign_minor = di_sign_major; int dj_sign_minor = dj_sign_major; switch ( secondarySide ) { case 0 : dj_sign_major = 1; break; case 1 : di_sign_major = -1; break; case 2 : dj_sign_major = -1; break; case 3 : di_sign_major = 1; break; } /* String [] sideName = new String [] { "none", "N", "E", "S", "W" }; System.out.println( "Azimuth = " + solarAzimuth + " primary = " + sideName[ primarySide + 1 ] + " secondary = " + sideName[ secondarySide + 1 ] + " major step = ( " + di_sign_major + ", " + dj_sign_major + " ) minor = ( " + di_sign_minor + ", " + dj_sign_minor + " )" ); */ // work out some constants needed for the stepping process double theta = Math.PI * ( ( ( 90 - solarAzimuth ) + 540 ) % 360 ) / 180; a = Math.sin( theta ); b = Math.cos( theta ); if ( Math.abs( a - b ) < 0.0001 ) { a = Math.sin( theta + 0.01 ); b = Math.cos( theta + 0.01 ); } // compute the rate of descent of the edges of the umbra and penumbra double dz = Math.abs( Math.tan( Math.PI * solarAscension / 180.0 ) ) / DIM; double maxAngle = solarAscension + penumbralAngle; if ( maxAngle > 88 ) maxAngle = 88; double dz_soft = Math.abs( Math.tan( Math.PI * maxAngle / 180.0 ) ) / DIM; int [] oppositeX = new int[ 4 ]; oppositeX[ 0 ] = -1; oppositeX[ 1 ] = xdim; oppositeX[ 2 ] = -1; oppositeX[ 3 ] = -1; int [] oppositeY = new int[ 4 ]; oppositeY[ 0 ] = ydim; oppositeY[ 1 ] = -1; oppositeY[ 2 ] = -1; oppositeY[ 3 ] = -1; // run the primary side int iend = oppositeX[ primarySide ]; int jend = oppositeY[ primarySide ]; for ( int i = sideStartX[ primarySide ], j = sideStartY[ primarySide ]; ( i <= sideEndX[ primarySide ] ) && ( j <= sideEndY[ primarySide ] ); i += sideDX[ primarySide ], j += sideDY[ primarySide ] ) { propagateShadowLine( i, j, iend, jend, dz, dz_soft, di_sign_major, dj_sign_major, di_sign_minor, dj_sign_minor ); } // run the secondary side if any if ( secondarySide != -1 ) { for ( int i = sideStartX[ secondarySide ], j = sideStartY[ secondarySide ]; ( i <= sideEndX[ secondarySide ] ) && ( j <= sideEndY[ secondarySide ] ); i += sideDX[ secondarySide ], j += sideDY[ secondarySide ] ) { if ( !visited[ i ][ j ] ) { propagateShadowLine( i, j, iend, jend, dz, dz_soft, di_sign_major, dj_sign_major, di_sign_minor, dj_sign_minor ); } } } long deltaTime = System.currentTimeMillis() - startTime; // System.out.println( "Elapsed time in shadows = " + deltaTime + " ms" ); } /** * Propagate a shadow along a Bresenham path from the given starting point * along a line with angle * @param istart starting x coordinate * @param jstart starting y coordinate * @param dz descent distance of the umbra per grid square * @param dz_soft descent distance of the penumbra per grid square * @param di_sign sign of the horizontal step (1, -1, or 0) * @param dj_sign sign of the vertical step (1, -1, or 0) */ public void propagateShadowLine( int istart, int jstart, int iend, int jend, double dz, double dz_soft, int di_sign_major, int dj_sign_major, int di_sign_minor, int dj_sign_minor ) { // initialize the Bresenham remainder term double ceiling = -1.0; double soft_ceiling = -1.0; double d = 0.0; int di = 0, dj = 0; double dd_major = di_sign_major * a + dj_sign_major * b; double dd_minor = di_sign_minor * a + dj_sign_minor * b; if ( dd_major * dd_minor >= 0.0 ) { return; } for ( int j = jstart, i = istart; ( i != DIM ) && ( j != DIM ) && ( i != -1 ) && ( j != -1 ); i += di, j += dj ) { // Figure out what sort of step we're taking double dz_eff, dz_soft_eff; if ( d * dd_minor > 0.0 ) { di = di_sign_major; dj = dj_sign_major; dz_eff = dz * 1.414; dz_soft_eff = dz_soft * 1.414; d += dd_major; } else { di = di_sign_minor; dj = dj_sign_minor; dz_eff = dz; dz_soft_eff = dz_soft; d += dd_minor; } // Propagate the shadows double next_ceiling = ceiling - dz_eff; double next_soft_ceiling = soft_ceiling - dz_soft_eff; if ( y[ i ][ j ] >= ceiling ) { // fully lit; push the ceilings back up to here shade[ i ][ j ] = 0.0; next_ceiling = y[ i ][ j ] - dz_eff; next_soft_ceiling = y[ i ][ j ] - dz_soft_eff; } else if ( y[ i ][ j ] > soft_ceiling ) { // in the penumbra; push the soft ceiling back up to here shade[ i ][ j ] = 1.0 - ( y[ i ][ j ] - soft_ceiling ) / ( ceiling - soft_ceiling ); next_soft_ceiling = y[ i ][ j ] - dz_soft_eff; } else { // in the umbra; lower the ceilings as usual shade[ i ][ j ] = 1.0; } ceiling = next_ceiling; soft_ceiling = next_soft_ceiling; // note that this square has been visited visited[ i ][ j ] = true; } } /** * Do everything needed to re-render the image. This includes shadowing, * shading, ambient light, and importation of the results into the MemoryImageSource * that does the actual drawing. */ public void regenerateImage() { if ( !needsRedraw ) { updateShadows(); // compute the shadows; store in the array updateColors(); // compute the color everywhere; store in the array // import the array into the MemoryImageSource representing the // terrain image long startTime = System.currentTimeMillis(); int ct = 0; int mask = ( 1 << 16 ) + ( 1 << 8 ) + 1; for ( int j = 0; j < ydim; j++ ) { for ( int i = 0; i < xdim; i++ ) { membuf[ ct++ ] = color_index[ i ][ j ] * mask; } } // notify the terrain image that it has new data and needs to repaint source.newPixels( 0, 0, xdim, ydim ); long deltaTime = System.currentTimeMillis() - startTime; // System.out.println( "Elapsed time in image fill = " + deltaTime + " ms" ); needsRedraw = true; } } /** * To prevent flickering, override update to NOT clear the screen each time */ public void update( Graphics g ) { this.paint( g ); } /** * return the color index of the terrain pixel at the given i (horizontal) and * j (vertical) coordinates * @param i the horizontal coordinate of the pixel of interest * @param j the vertical coordinate of the pixel of interest * @return the color index of the pixel of interest, as in int between 0 (dark) * and N_COLORS (bright) */ public int getPixelColor( int i, int j ) { double brightness = 0.0; if ( useAmbient ) brightness = 0.3; // compute angle-of-incidence lighting if ( useAOI ) { double dzdx = ( y[ i + 1 ][ j ] - y[ i ][ j ] + y[ i + 1 ][ j + 1 ] - y[ i + 1 ][ j ] ) * 100.0; double dzdy = ( y[ i ][ j ] - y[ i ][ j + 1 ] + y[ i + 1 ][ j + 1 ] - y[ i + 1 ][ j ] ) * 100.0; double nx = -dzdx; double ny = -dzdy; double nz = 1.0; double mag = Math.sqrt( nx * nx + ny * ny + nz * nz ); nx /= mag; ny /= mag; nz /= mag; double adotb = - nx * lx - ny * ly - nz * lz; if ( adotb < 0.0 ) adotb = 0.0; brightness += adotb; if ( brightness > 1.0 ) brightness = 1.0; } if ( useShadow ) { double s = 0.25 * ( shade[ i ][ j ] + shade[ i + 1 ][ j ] + shade[ i ][ j + 1 ] + shade[ i + 1 ][ j + 1 ] ); brightness *= ( 1.0 - s ); } return ( int ) ( brightness * N_COLORS ); } /** * draw the Image representing the terrain */ public void paint( Graphics g ) { if ( memage != null ) { g.drawImage( memage, xpad, 0, this ); needsRedraw = false; } } /** * fill in the array with the current color indices */ public void updateColors() { long colorStartTime = System.currentTimeMillis(); double theta = Math.PI * ( ( 360 + 90 - solarAzimuth ) % 360 ) / 180; double phi = Math.PI * ( ( 360 + 90 - solarAscension ) % 360 ) / 180; lx = - Math.cos( theta ) * Math.sin( phi ); ly = - Math.sin( theta ) * Math.sin( phi ); lz = - Math.cos( phi ); for ( int i = 0; i < xdim; i++ ) { for ( int j = 0; j < ydim; j++ ) { color_index[ i ][ j ] = getPixelColor( i, j ); } } long colorDeltaTime = System.currentTimeMillis() - colorStartTime; // System.out.println( "Elapsed time in coloring = " + colorDeltaTime + " ms" ); } public Dimension getMinimumSize() { return mySize; } public Dimension getMaximumSize() { return mySize; } public Dimension getPreferredSize() { return mySize; } } }