MiniLight 1.5.2.1 Scala

MiniLight.scala

package hxa7241.minilight


import hxa7241.general.TokenStream




/**
 * Control-module and entry point.<p>
 *
 * Handles command-line UI, and runs the main progressive-refinement render
 * loop.<p>
 *
 * Supply a model file pathname as the command-line argument. Or -? for help.<p>
 */


object MiniLight
{
/// user messages --------------------------------------------------------------

   private val TITLE     = "MiniLight 1.5.2.1 Scala"
   private val COPYRIGHT = "Harrison Ainsworth / HXA7241 : 2008-2010"
   private val URI       = "http://www.hxa.name/minilight/"
   private val DATE      = "2010-01-09"

   private val BANNER_MESSAGE = "\n  " + TITLE + "\n  " + COPYRIGHT + "\n  " +
      URI + "\n"

   private val HELP_MESSAGE   = """
----------------------------------------------------------------------
  """ + TITLE + "\n\n  " + COPYRIGHT + "\n  " + URI + "\n\n  " + DATE + """
----------------------------------------------------------------------

MiniLight is a minimal global illumination renderer.

usage:
  minilight modelFilePathName

The model text file format is:
  #MiniLight

  iterations

  imagewidth imageheight

  viewposition viewdirection viewangle

  skyemission groundreflection
  vertex0 vertex1 vertex2 reflectivity emitivity
  vertex0 vertex1 vertex2 reflectivity emitivity
  ...

-- where iterations and image values are ints, viewangle is a float,
and all other values are three parenthised floats. The file must end
with a newline. Eg.:
  #MiniLight

  100

  200 150

  (0 0.75 -2) (0 0 1) 45

  (3626 5572 5802) (0.1 0.09 0.07)
  (0 0 0) (0 1 0) (1 1 0)  (0.7 0.7 0.7) (0 0 0)
"""


/// other declarations ---------------------------------------------------------

   private val MODEL_FORMAT_ID = "#MiniLight"
   private val SAVE_PERIOD     = 240L * 1000L


   private def saveImage( imageFilePathname:String, image:Image, frameNo:Int )
   {
      // open file, write, close
      val imageFile = new java.io.PrintStream( imageFilePathname )
      image.formatted( imageFile, (frameNo - 1) )
      imageFile.close()
   }


/// entry point ----------------------------------------------------------------

   def main( args:Array[String] )
   {
      // catch everything
      try
      {
         // check for help request
         if( args.isEmpty || ("-?" == args(0)) || ("--help"== args(0)) )
         {
            println( HELP_MESSAGE )
         }
         // execute
         else
         {
            println( BANNER_MESSAGE )

            // get/make file names
            val modelFilePathname = args(0)
            val imageFilePathname = modelFilePathname + ".ppm"

            // open model file
            val modelFile = new TokenStream( modelFilePathname )

            // check model file format identifier at start of first line
            if( MODEL_FORMAT_ID != (modelFile.next + modelFile.next) )
               throw new Exception( "invalid model file" )

            // read frame iterations
            val iterations = modelFile.next.toInt

            // create main rendering objects, from model file
            val image  = new Image ( modelFile )
            val camera = new Camera( modelFile )
            val scene  = new Scene ( modelFile, camera.eyePoint )

            modelFile.close

            // remove seed parameter for non-deterministicality
            val random = new util.Random( 0 )

            // make frame number visible to interruption/ctrl-c handler
            var frameNumber = 0

            // setup interruption/ctrl-c handler
            // (will also run at successful exit)
            Runtime.getRuntime().addShutdownHook( new Thread()
               {
                  override def run()
                  {
                     saveImage( imageFilePathname, image, frameNumber )
                     if( frameNumber < iterations ) println( "\ninterrupted" )
                  }
               } )

            // do progressive refinement render loop
            var lastTime = 0L
            for( i <- 1 to iterations )
            {
               // render a frame
               camera.getFrame( scene, random, image )
               frameNumber = i

               // save image periodically, and at start
               if( (SAVE_PERIOD < (System.currentTimeMillis() - lastTime)) )
               // save image every iteration doubling
               //if( (i & (i - 1)) == 0 )
               {
                  lastTime = System.currentTimeMillis()
                  saveImage( imageFilePathname, image, frameNumber )
               }

               // display latest frame number
               Console.out.append( "\riteration: " + frameNumber ).flush
            }

            println( "\nfinished" )
        }
      }
      // print any exception message
      catch
      {
         case e:Throwable => println( "\n*** execution failed: " + e )
      }
   }
}

Camera.scala

package hxa7241.minilight


import hxa7241.graphics.Vector3f




/**
 * A view definition with rasterization capability.<p>
 *
 * @constant <p>
 *
 * @invariants <ul>
 * <li>viewAngle_m is >= 10 and <= 160 degrees in radians</li>
 * <li>viewDirection_m is unitized</li>
 * <li>right_m is unitized</li>
 * <li>up_m is unitized</li>
 * <li>above three form a coordinate frame</li>
 * </ul>
 *
 * @param modelFile_c  to read from
 */
class Camera( modelFile_c:{def next:String} ) extends NotNull
{
/// queries --------------------------------------------------------------------

   def eyePoint = viewPosition_m


   /**
    * Accumulate a frame to the image.
    *
    * @param scene   scene to render
    * @param random  random number generator
    * @param image   image to add to
    */
   def getFrame( scene:Scene, random:util.Random, image:Image )
   {
      val rayTracer = new RayTracer( scene )

      // do image sampling pixel loop
      for( y <- 0 until image.height;  x <- 0 until image.width )
      {
         // make sample ray direction, stratified by pixels
         val sampleDirection =
         {
            // make image plane displacement vector coefficients
            val xF = ((x + random.nextFloat) * 2.0f / image.width ) - 1.0f
            val yF = ((y + random.nextFloat) * 2.0f / image.height) - 1.0f

            // make image plane offset vector
            val offset = (right_m * xF) + (up_m * (yF *
               (image.height.toFloat / image.width)))

            // add offset to view direction
            (viewDirection_m + (offset * Math.tan(viewAngle_m * 0.5f).
               toFloat)).unitized
         }

         // get radiance from RayTracer
         val radiance = rayTracer.radiance( viewPosition_m, sampleDirection,
            random, null )

         // add radiance to pixel
         image.addToPixel( x, y, radiance )
      }
   }


/// fields ---------------------------------------------------------------------

   // view definition
   private val viewPosition_m  = Vector3f( modelFile_c )
   private val viewDirection_m =
   {
      val vd = Vector3f( modelFile_c ).unitized
      if( !vd.isZero ) vd else Vector3f(0, 0, 1)
   }

   private val viewAngle_m = Math.toRadians(
      (modelFile_c.next.toFloat max 10.0f) min 160.0f ).toFloat

   // rest of the view coord frame
   private val (right_m, up_m) =
   {
      val right = (Vector3f(0, 1, 0) cross viewDirection_m).unitized
      if( !right.isZero )
         ( right, (viewDirection_m cross right).unitized )
      else
      {
         val up = Vector3f( 0, 0, if(viewDirection_m.y < 0.0f) +1 else -1 )
         ( (up cross viewDirection_m).unitized, up )
      }
   }
}

Image.scala

package hxa7241.minilight


import hxa7241.graphics.Vector3f




/**
 * Pixel sheet with simple tone-mapping and file formatting.<p>
 *
 * Uses PPM image format:
 * <cite>http://netpbm.sourceforge.net/doc/ppm.html</cite><p>
 *
 * Uses Ward simple tonemapper:
 * <cite>'A Contrast Based Scalefactor For Luminance Display'
 * Ward;
 * Graphics Gems 4, AP 1994.</cite><p>
 *
 * @mutable <p>
 *
 * @invariants <ul>
 * <li>width  >= 1 and <= 10000</li>
 * <li>height >= 1 and <= 10000</li>
 * <li>pixels_m.length == (width * height)</li>
 * </ul>
 *
 * @param modelFile_c  to read from
 */
class Image( modelFile_c:{def next:String} ) extends NotNull
{
/// commands -------------------------------------------------------------------

   /**
    * Accumulate (add, not just assign) a value to the image.
    *
    * @param x         x coord
    * @param y         y coord
    * @param radiance  light value
    */
   def addToPixel( x:Int, y:Int, radiance:Vector3f )
   {
      // only inside image bounds
      if( (x >= 0) & (x < width) & (y >= 0) & (y < height) )
         pixels_m(x + ((height - 1 - y) * width)) += radiance
   }


/// queries --------------------------------------------------------------------

   /**
    * Format the image.
    *
    * @param out        to receive the image
    * @param iteration  number of accumulations made to the image
    */
   def formatted( out:java.io.PrintStream, iteration:Int )
   {
      // make pixel value accumulation divider, and tonemap scaling
      val divider        = 1.0f / ((iteration max 0) + 1)
      val tonemapScaling = toneMapping( divider )

      // write ID and comment
      out.print( "P6\n# " + Image.MINILIGHT_URI + "\n\n" )

      // write width, height, maxval
      out.print( width + " " + height + "\n" + 255 + "\n" )

      // write pixels
      for( pixel <- pixels_m;  c <- 0 to 2;  val channel = pixel(c) )
      {
         // tonemap and gamma encode
         val mapped  = (channel * divider * tonemapScaling) max 0.0f
         val gammaed = Math.pow( mapped, Image.GAMMA_ENCODE ).toFloat

         // quantize and output as byte
         out.write( (((gammaed * 255.0f) + 0.5f) min 255.0f).toByte )
      }
   }


/// implementation -------------------------------------------------------------

   /**
    * Calculate tone-mapping scaling factor.
    *
    * @param divider  pixel scaling
    *
    * @return  scaling factor
    */
   private def toneMapping( divider:Float ) =
   {
      // calculate log mean luminance of scene,
      // as an estimate of world-adaptation luminance
      val logMeanLuminance =
      {
         // sum
         val sumOfLogs = pixels_m.foldLeft( 0.0f )( (sum, pixel) =>
            {
               val y = (pixel dot Image.RGB_LUMINANCE) * divider
               // clamp luminance to a perceptual minimum
               sum + java.lang.Math.log10( y max 1e-4f ).toFloat
            } )
         // mean
         Math.pow( 10.0f, (sumOfLogs / pixels_m.length) ).toFloat
      }

      // make scale-factor from:
      // ratio of minimum visible differences in luminance, in display-adapted
      // and world-adapted perception (discluding the constant that cancelled),
      // divided by display max to yield a [0,1] range
      val a = 1.219f + Math.pow( (Image.DISPLAY_LUMINANCE_MAX * 0.25f), 0.4f )
      val b = 1.219f + Math.pow( logMeanLuminance,                      0.4f )

      Math.pow( (a / b), 2.5f ).toFloat / Image.DISPLAY_LUMINANCE_MAX
   }


/// fields ---------------------------------------------------------------------

   val width  = (modelFile_c.next.toInt max 1) min 10000
   val height = (modelFile_c.next.toInt max 1) min 10000

   private val pixels_m = Array.make( width * height, Vector3f() )
}




object Image
{
/// constants ------------------------------------------------------------------

   // image file comment
   private val MINILIGHT_URI = "http://www.hxa.name/minilight/"

   // guess of average screen maximum brightness
   private val DISPLAY_LUMINANCE_MAX = 200.0f
   // ITU-R BT.709 standard RGB luminance weighting
   private val RGB_LUMINANCE         = Vector3f( 0.2126f, 0.7152f, 0.0722f )
   // ITU-R BT.709 standard gamma
   private val GAMMA_ENCODE          = 0.45f
}

RayTracer.scala

package hxa7241.minilight


import hxa7241.graphics.Vector3f




/**
 * Ray tracer for general light transport.<p>
 *
 * Traces a path with emitter sampling each step: A single chain of ray-steps
 * advances from the eye into the scene with one sampling of emitters at each
 * node.<p>
 *
 * @constant <p>
 *
 * @param scene_c  collection of objects
 */
class RayTracer( scene_c:Scene ) extends NotNull
{
/// queries --------------------------------------------------------------------

   /**
    * Radiance returned from a trace.
    *
    * @param rayOrigin     ray start point
    * @param rayDirection  ray direction (unitized)
    * @param random        random number generator
    * @param lastHit       previous intersected object, or null
    *
    * @return  radiance
    */
   def radiance( rayOrigin:Vector3f, rayDirection:Vector3f, random:util.Random,
      lastHit:AnyRef ):Vector3f =
   {
      // intersect ray with scene
      scene_m.intersection( rayOrigin, rayDirection, lastHit ) match
      {
         // hit
         case Some( (hitObject, hitPosition) ) =>
         {
            // make SurfacePoint of intersection
            val surfacePoint = new SurfacePoint( hitObject, hitPosition )

            // local emission (only for first-hit)
            val localEmission = if( lastHit != null ) Vector3f.ZERO else
               surfacePoint.emission( rayOrigin, -rayDirection, false )

            // emitter sample
            val illumination = emitterSample(rayDirection, surfacePoint, random)

            // recursive reflection:
            // single hemisphere sample, ideal diffuse BRDF:
            //    reflected = (inradiance * pi) * (cos(in) / pi * color) *
            //       reflectance
            // -- reflectance magnitude is 'scaled' by the russian roulette, cos
            // is importance sampled (both done by SurfacePoint), and the pi and
            // 1/pi cancel out -- leaving just: inradiance * reflectance color
            val reflection =
               // check surface bounces ray
               surfacePoint.nextDirection( -rayDirection, random ) match
               {
                  // recurse
                  case Some( (nextDirection, color) ) =>
                     color * radiance( surfacePoint.position, nextDirection,
                        random, surfacePoint.hitObject )
                  // end
                  case None => Vector3f.ZERO
               }

            // total radiance returned
            reflection + illumination + localEmission
         }
         // no hit: default/background scene emission
         case None => scene_m.defaultEmission( -rayDirection )
      }
   }


/// implementation -------------------------------------------------------------

   /**
    * Radiance from an emitter sample.
    *
    * @param rayDirection  previous ray direction (unitized)
    * @param surfacePoint  surface point receiving emission
    * @param random        random number generator
    *
    * @return  radiance
    */
   private def emitterSample( rayDirection:Vector3f, surfacePoint:SurfacePoint,
      random:util.Random ) =
   {
      // single emitter sample, ideal diffuse BRDF:
      //    reflected = (emitivity * solidangle) * (emitterscount) *
      //       (cos(emitdirection) / pi * reflectivity)
      // -- SurfacePoint does the first and last parts (in separate methods)

      // check an emitter was found
      scene_m.emitter( random ).flatMap( { case (emitter, emitPosition) =>
         {
            // make direction to emit point
            val emitDirection = (emitPosition - surfacePoint.position).unitized

            // send shadow ray to get light
            scene_m.intersection( surfacePoint.position, emitDirection,
               surfacePoint.hitObject ) match
               {
                  // unshadowed
                  case None | Some( (`emitter`, _) ) =>
                  {
                     // get inward emission value
                     val emissionIn = new SurfacePoint( emitter, emitPosition
                        ).emission(surfacePoint.position, -emitDirection, true)

                     // get amount reflected by surface
                     Some( surfacePoint.reflection( emitDirection,
                        (emissionIn * scene_m.emittersCount), -rayDirection ) )
                  }
                  // shadowed
                  case _ => None
               }
         } } ).getOrElse( Vector3f.ZERO )
   }


/// fields ---------------------------------------------------------------------

   private val scene_m = scene_c
}

Scene.scala

package hxa7241.minilight


import hxa7241.graphics.Vector3f




/**
 * The objects in the environment.<p>
 *
 * Makes a sub-grouping of emitting objects.<p>
 *
 * @constant <p>
 *
 * @invariants <ul>
 * <li>skyEmission_m      >= 0</li>
 * <li>groundReflection_m >= 0</li>
 * <li>triangles_m length <= 2^20</li>
 * <li>emitters_m length  <= 2^20</li>
 * </ul>
 *
 * @param modelFile_c    to read from
 * @param eyePosition_c  eye position
 */
class Scene( modelFile_c:{def next:String}, eyePosition_c:Vector3f )
   extends NotNull
{
/// queries --------------------------------------------------------------------

   /**
    * Nearest intersection of ray with object.
    *
    * @param rayOrigin     ray origin
    * @param rayDirection  ray direction (unitized)
    * @param lastHit       previous intersected object, or null
    *
    * @return  triangle and position (Tuple Option)
    */
   def intersection( rayOrigin:Vector3f, rayDirection:Vector3f,
      lastHit:AnyRef ) =
   {
      spatialIndex_m.intersection( rayOrigin, rayDirection, lastHit, None )
   }


   /**
    * Monte-carlo sample point on monte-carlo selected emitting object.
    *
    * @param random  random number generator
    *
    * @return  triangle and position (Tuple Option)
    */
   def emitter( random:util.Random ) =
   {
      if( emittersCount > 0 )
      {
         // select emitter
         val emitter = emitters_m( random.nextInt(emittersCount) )

         // get position on triangle
         Some( (emitter, emitter.samplePoint( random )) )
      }
      else
         None
   }


   /**
    * Number of emitters in scene.
    *
    * @return  number of emitters
    */
   def emittersCount = emitters_m.length


   /**
    * Default/'background' light of scene universe.
    *
    * @param eyeDirection  direction to eye
    *
    * @return  emitted radiance
    */
   def defaultEmission( eyeDirection:Vector3f ) =
   {
      // sky for downward ray, ground for upward ray
      if( eyeDirection.y < 0.0f ) skyEmission_m else groundReflection_m
   }


/// fields ---------------------------------------------------------------------

   // default scene background
   private val skyEmission_m = Vector3f(modelFile_c).clampedMin( Vector3f.ZERO )
   private val groundReflection_m = Vector3f(modelFile_c).clamped01 *
      skyEmission_m

   // main objects
   private val triangles_m =
   {
      def readTriangle( ts:List[Triangle], i:Int ):List[Triangle] =
      {
         try
         {
            if( i == 0 )
               ts else readTriangle( new Triangle(modelFile_c) :: ts, i - 1 )
         }
         catch
         {
            // EOF is not really exceptional here, but the code is simpler
            case _:java.io.EOFException => ts
         }
      }
      // read maximum of 2^20
      readTriangle( Nil, Scene.MAX_TRIANGLES ).toArray
   }
   // find emitting triangles
   private val emitters_m = triangles_m.filter(
      // has non-zero emission and area
      t => (!t.emitivity.isZero) && (t.area > 0.0f) )

   // acceleration index
   private val spatialIndex_m = new SpatialIndex( eyePosition_c, triangles_m )
}




object Scene
{
/// constants ------------------------------------------------------------------

   private val MAX_TRIANGLES = 0x100000
}

SpatialIndex.scala

package hxa7241.minilight


import hxa7241.graphics.Vector3f




/**
 * A minimal spatial index for ray tracing.<p>
 *
 * Suitable for a scale of 1 metre == 1 numerical unit, and has a resolution of
 * 1 millimetre. (Implementation uses fixed tolerances)<p>
 *
 * @implementation <p>
 * Octree: axis-aligned, cubical. Subcells are numbered thusly (in binary):<pre>
 *            110---111
 *            /|    /|
 *         010---011 |
 *    y z   | 100-|-101
 *    |/    | /   | /
 *    .-x  000---001      </pre><p>
 *
 * Each cell stores its bound: fatter data, but simpler code.<p>
 *
 * Calculations for building and tracing are absolute rather than incremental --
 * so quite numerically solid. Uses tolerances in: bounding items (in
 * Triangle.bound), and checking intersection is inside cell (both effective
 * for axis-aligned items). Also, depth is constrained to an absolute subcell
 * size (easy way to handle overlapping items).<p>
 *
 * Sacrificed some clarity for compactness.<p>
 *
 * @constant <p>
 *
 * @invariants <ul>
 * <li>bound_m length is 6</li>
 * <li>subParts_m is SpatialIndex.SubCells or SpatialIndex.Items</li>
 * </ul>
 */
final class SpatialIndex private (
   bound_c:Array[Float], items_c:Array[Triangle], level_c:Int ) extends NotNull
{
/// standard object services ---------------------------------------------------

   /**
    * Construct (publicly).
    *
    * @param eyePosition  position of eye
    * @param items        collection of all items
    */
   def this( eyePosition:Vector3f, items:Array[Triangle] ) = this(
      {
         // make overall bound
         val bound =
         {
            // accommodate all items, and eye position (makes tracing algorithm
            // simpler)
            val rectBound = items.foldLeft( (eyePosition, eyePosition) )(
               (rb, item) =>
               {
                  // accommodate item
                  val ib = item.bound
                  ( (rb._1 clampedMax ib._1), (rb._2 clampedMin ib._2) )
               } )
            // make cubical
            val cube = Vector3f( (rectBound._2 - rectBound._1).fold(Math.max) )
            ( rectBound._1, (rectBound._2 clampedMin (rectBound._1 + cube)) )
         }

         // convert to array
         Array.range(0,6).map( i => (if(i < 3) bound._1 else bound._2)(i % 3) )

      // delegate to main (recursive) constructor
      }, items, 0 )


/// queries --------------------------------------------------------------------

   /**
    * Find nearest intersection of ray with item.
    *
    * @param rayOrigin     ray origin
    * @param rayDirection  ray direction (unitized)
    * @param lastHit       previous intersected item, or null
    * @param _start        current traversal point, or None
    *
    * @return  item and position (Tuple Option)
    */
   def intersection( rayOrigin:Vector3f, rayDirection:Vector3f,
      lastHit:AnyRef, _start:Option[Vector3f] ):Option[(Triangle,Vector3f)] =
   {
      subParts_m match
      {
         // branch: step through subcells and recurse
         case SpatialIndex.SubCells( subCells ) =>
         {
            val start = _start.getOrElse( rayOrigin )

            // find which subcell holds ray origin (ray origin is inside cell)
            val subCell =
               // compare dimensions with center
               (if( start.x >= ((bound_m(0) + bound_m(3)) * 0.5f) ) 1 else 0) |
               (if( start.y >= ((bound_m(1) + bound_m(4)) * 0.5f) ) 2 else 0) |
               (if( start.z >= ((bound_m(2) + bound_m(5)) * 0.5f) ) 4 else 0)

            // define subcell walker
            def walk( subCell:Int, cellPosition:Vector3f )
               :Option[(Triangle,Vector3f)] =
            {
               // intersect subcell
               // if no hit, continue walking across subcells
               subCells(subCell).flatMap( _.intersection( rayOrigin,
                  rayDirection, lastHit, Some(start) ) ).orElse(
               {
                  // find next subcell ray moves to
                  // (by finding which face of corner ahead is crossed first)
                  val (step, axis) = (0 to 2).foldLeft( Math.MAX_FLOAT, 0 )( {
                     case ((step, axis), i) =>
                     {
                        val high = (subCell >>> i) & 1
                        val face = if( (rayDirection(i) < 0.0f) ^ (high == 1) )
                              bound_m(i + (high * 3))
                           else
                              (bound_m(i) + bound_m(i + 3)) * 0.5f
                        // distance to face
                        // (div by zero produces infinity, which is then
                        // discarded)
                        val distance = (face - rayOrigin(i)) / rayDirection(i)
                        if( distance < step ) (distance, i) else (step, axis)
                     } } )

                  // leaving branch if: direction is negative and subcell is
                  // low, or direction is positive and subcell is high
                  if( (rayDirection(axis) < 0.0f) ^
                     (((subCell >>> axis) & 1) == 1) )
                     None
                  else
                     // move to (outer face of) next subcell
                     walk( subCell ^ (1 << axis),
                        rayOrigin + (rayDirection * step) )
               } )
            }
            // step through intersected subcells
            walk( subCell, start )
         }
         // leaf: exhaustively intersect contained items
         case SpatialIndex.Items( items ) =>
         {
            // apply nearest-finder to items list
            items.foldLeft( None:Option[(Triangle,Vector3f)], Math.POS_INF_FLOAT
               )( (nearest, item) =>
               {
                  // intersect item and inspect if nearest so far
                  val distance = item.intersection( rayOrigin, rayDirection
                     ).getOrElse( Math.POS_INF_FLOAT )
                  // also avoid false intersection with surface just come from
                  if( (distance < nearest._2) && (item != lastHit) )
                  {
                     val hit = rayOrigin + (rayDirection * distance)
                     // check intersection is inside cell bound (with tolerance)
                     val t = Triangle.TOLERANCE
                     if( (bound_m(0) - hit.x > t) | (hit.x - bound_m(3) > t) |
                         (bound_m(1) - hit.y > t) | (hit.y - bound_m(4) > t) |
                         (bound_m(2) - hit.z > t) | (hit.z - bound_m(5) > t) )
                        nearest else (Some((item, hit)), distance)
                  }
                  else
                     nearest
               } )._1
         }
      }
   }


/// fields ---------------------------------------------------------------------

   private val bound_m    = bound_c
   private val subParts_m =
   {
      // if items overflow leaf and tree not too deep,
      // make branch: make subcells, and recurse construction
      if( (items_c.length > SpatialIndex.MAX_ITEMS) &
         (level_c < (SpatialIndex.MAX_LEVELS - 1)) )
      {
         // make subcells
         var q1 = 0
         SpatialIndex.SubCells( for( subcellIndex <- Array.range(0,8) ) yield
         {
            // make subcell bound
            val subBound = for( i <- Array.range(0,6);  val m = i % 3 ) yield
               if( (((subcellIndex >> m) & 1) ^ (i / 3)) != 0 )
                  (bound_c(m) + bound_c(m + 3)) * 0.5f else bound_c(i)

            // collect items that overlap subcell
            val subItems = for( i <- items_c;  val (itemLo, itemHi) = i.bound;
               // must overlap in all dimensions
               if (0 to 5).foldLeft( true )( (b, j) => b & ((subBound(j) <=
                  (if(j > 2) itemLo else itemHi)(j % 3)) ^ (j > 2)) )
               ) yield i

            // curtail degenerate subdivision by adjusting next level
            // (degenerate if two or more subcells copy entire contents of
            // parent, or if subdivision reaches below approx mm size)
            // (having a model including the sun requires one subcell copying
            // entire contents of parent to be allowed)
            q1 += (if( subItems.length == items_c.length ) 1 else 0)
            val q2  = (subBound(3) - subBound(0)) < (Triangle.TOLERANCE * 4.0f)

            // maybe recurse
            if( !subItems.isEmpty )
               new Some( new SpatialIndex( subBound, subItems,
               (if((q1 > 1) | q2) SpatialIndex.MAX_LEVELS else level_c + 1) ) )
            else
               None
         } )
      }
      // otherwise (size limit reached),
      // make leaf: store items, and end recursion
      else
         // (try to trim any reserve capacity)
         SpatialIndex.Items( items_c.slice( 0, items_c.length ).force )
   }
}




object SpatialIndex
{
/// constants ------------------------------------------------------------------

   // accommodates scene including sun and earth, down to cm cells
   // (use 47 for mm)
   private val MAX_LEVELS = 44

   // 8 seemed reasonably optimal in casual testing
   private val MAX_ITEMS  =  8


/// types ----------------------------------------------------------------------

   private case class SubCells( subCells:Array[Option[SpatialIndex]] )
   private case class Items   (    items:Array[Triangle]     )
}

SurfacePoint.scala

package hxa7241.minilight


import hxa7241.graphics.Vector3f




/**
 * Surface point at a ray-object intersection.<p>
 *
 * All direction parameters are away from surface.<p>
 *
 * @constant <p>
 *
 * @param triangle_c  surface's object
 * @param position_c  position of point on surface
 */
class SurfacePoint( triangle_c:Triangle, position_c:Vector3f ) extends NotNull
{
/// queries --------------------------------------------------------------------

   /**
    * Emission from surface element to point.
    *
    * @param toPosition    point being illuminated
    * @param outDirection  direction (unitized) from emitting point
    * @param isSolidAngle  use solid angle
    *
    * @return  emitted radiance
    */
   def emission( toPosition:Vector3f, outDirection:Vector3f,
      isSolidAngle:Boolean ) =
   {
      val distance2 = { val ray = toPosition - position;  ray dot ray }
      val cosArea   = (outDirection dot triangle_m.normal) * triangle_m.area

      // clamp-out infinity
      val solidAngle = if( isSolidAngle )
         cosArea / (distance2 max 1e-6f) else 1.0f

      // emit from front face of surface only
      if( cosArea > 0.0f ) triangle_m.emitivity * solidAngle else Vector3f.ZERO
   }


   /**
    * Light reflection from ray to ray by surface.
    *
    * @param inDirection   negative of inward ray direction
    * @param inRadiance    inward radiance
    * @param outDirection  outward (eyeward) ray direction
    *
    * @return  reflected radiance
    */
   def reflection( inDirection:Vector3f, inRadiance:Vector3f,
      outDirection:Vector3f ) =
   {
      val inDot  = inDirection  dot triangle_m.normal
      val outDot = outDirection dot triangle_m.normal

      // directions must be on same side of surface
      if( (inDot < 0.0f) ^ (outDot < 0.0f) )
         Vector3f.ZERO
      else
         // ideal diffuse BRDF:
         // radiance scaled by cosine, 1/pi, and reflectivity
         (inRadiance * triangle_m.reflectivity) * (inDot.abs / Math.Pi.toFloat)
   }


   /**
    * Monte-carlo direction of reflection from surface.
    *
    * @param inDirection  eyeward ray direction
    * @param random       random number generator
    *
    * @return sceneward ray direction (unitized) and light scaling of
    *         interaction point (Tuple Option)
    */
   def nextDirection( inDirection:Vector3f, random:util.Random ) =
   {
      val reflectivityMean = (triangle_m.reflectivity dot Vector3f.ONE) / 3.0f

      // russian-roulette for reflectance 'magnitude'
      if( random.nextFloat < reflectivityMean )
      {
         // cosine-weighted importance sample hemisphere

         val _2pr1 = Math.Pi.toFloat * 2.0f * random.nextFloat
         val sr2   = Math.sqrt( random.nextFloat ).toFloat

         // make coord frame coefficients (z in normal direction)
         val x = Math.cos( _2pr1 ).toFloat * sr2
         val y = Math.sin( _2pr1 ).toFloat * sr2
         val z = Math.sqrt( 1.0f - (sr2 * sr2) ).toFloat

         // make coord frame
         val tangent = triangle_m.tangent
         val normal  =
         {
            val n = triangle_m.normal
            if( (n dot inDirection) >= 0.0f ) n else -n
         }

         // make vector from frame times coefficients
         val outDirection = (tangent * x) + ((normal cross tangent) * y) +
            (normal * z)

         // make color by dividing-out mean from reflectivity
         val color = triangle_m.reflectivity * (1.0f / reflectivityMean)

         if( !outDirection.isZero ) Some( (outDirection, color) ) else None
      }
      else
         None
   }


   def hitObject:AnyRef = triangle_m


/// fields ---------------------------------------------------------------------

   private val triangle_m = triangle_c
           val position   = position_c
}

Triangle.scala

package hxa7241.minilight


import hxa7241.graphics.Vector3f




/**
 * A simple, explicit/non-vertex-shared triangle.<p>
 *
 * Includes geometry and quality.<p>
 *
 * Adapts ray intersection code from:
 * <cite>'Fast, Minimum Storage Ray-Triangle Intersection'
 * Moller, Trumbore;
 * Journal of Graphics Tools, v2 n1 p21, 1997.
 * http://www.acm.org/jgt/papers/MollerTrumbore97/</cite><p>
 *
 * @constant <p>
 *
 * @invariants <ul>
 * <li>vertexs_m.length == 3</li>
 * <li>reflectivity_m >= 0 and <= 1</li>
 * <li>emitivity_m    >= 0</li>
 * </ul>
 *
 * @param modelFile_c  to read from
 */
final class Triangle( modelFile_c:{def next:String} ) extends NotNull
{
/// queries --------------------------------------------------------------------

   /**
    * Axis-aligned bounding box of triangle.
    *
    * @return  lower corner and upper corner (Tuple)
    */
   def bound =
   {
      // calculate max and min across all vertexs
      val lower = (vertexs_m(0) clampedMax vertexs_m(1)) clampedMax vertexs_m(2)
      val upper = (vertexs_m(0) clampedMin vertexs_m(1)) clampedMin vertexs_m(2)

      // add/subtract tolerance
      // (lower is reduced, upper is increased (whatever their signs))
      ( lower - ((lower.abs + Vector3f.ONE) * Triangle.TOLERANCE),
         upper + ((upper.abs + Vector3f.ONE) * Triangle.TOLERANCE) )
   }


   /**
    * Intersection point of ray with triangle.
    *
    * (Vector operations are manually inlined (is faster).)
    *
    * @param rayOrigin     ray origin
    * @param rayDirection  ray direction (unitized)
    *
    * @return  distance along ray (Option)
    */
   def intersection( rayOrigin:Vector3f, rayDirection:Vector3f ) =
   {
      // make vectors for two edges sharing vert0
      val e3x = vertexs_m(2).x - vertexs_m(0).x
      val e3y = vertexs_m(2).y - vertexs_m(0).y
      val e3z = vertexs_m(2).z - vertexs_m(0).z

      val e0x = vertexs_m(1).x - vertexs_m(0).x
      val e0y = vertexs_m(1).y - vertexs_m(0).y
      val e0z = vertexs_m(1).z - vertexs_m(0).z

      // begin calculating determinant -- also used to calculate U parameter
      //val pvec = rayDirection cross edge3
      val pvx = (rayDirection.y * e3z) - (rayDirection.z * e3y)
      val pvy = (rayDirection.z * e3x) - (rayDirection.x * e3z)
      val pvz = (rayDirection.x * e3y) - (rayDirection.y * e3x)

      // if determinant is near zero, ray lies in plane of triangle
      //val det = edge0 dot pvec
      val det = (e0x * pvx) + (e0y * pvy) + (e0z * pvz)
      val epsilon = 0.000001f
      if( (det > -epsilon) & (det < epsilon) )
         None
      else
      {
         val inv_det = 1.0f / det

         // calculate distance from vertex 0 to ray origin
         //val tvec = rayOrigin - vertexs_m(0)
         val tvx = rayOrigin.x - vertexs_m(0).x
         val tvy = rayOrigin.y - vertexs_m(0).y
         val tvz = rayOrigin.z - vertexs_m(0).z

         // calculate U parameter and test bounds
         //val u = (tvec dot pvec) * inv_det
         val u = ((tvx * pvx) + (tvy * pvy) + (tvz * pvz)) * inv_det
         if( (u < 0.0f) | (u > 1.0f) )
            None
         else
         {
            // prepare to test V parameter
            //val qvec = tvec cross edge0
            val qvx = (tvy * e0z) - (tvz * e0y)
            val qvy = (tvz * e0x) - (tvx * e0z)
            val qvz = (tvx * e0y) - (tvy * e0x)

            // calculate V parameter and test bounds
            //val v = (rayDirection dot qvec) * inv_det
            val v = ((rayDirection.x * qvx) + (rayDirection.y * qvy) +
               (rayDirection.z * qvz)) * inv_det
            if( (v < 0.0f) | (u + v > 1.0f) )
               None
            else
            {
               // calculate t, ray intersects triangle
               //val hitDistance = (edge3 dot qvec) * inv_det
               val hitDistance = ((e3x * qvx) + (e3y * qvy) + (e3z * qvz)) *
                  inv_det

               // only allow intersections in the forward ray direction
               if(hitDistance >= 0.0f) Some( hitDistance ) else None
            }
         }
      }
   }


   /**
    * Monte-carlo sample point on triangle.
    *
    * @param random  random number generator
    *
    * @return  sample point
    */
   def samplePoint( random:util.Random ) =
   {
      // get two randoms
      val (sqr1, r2) = (Math.sqrt(random.nextFloat).toFloat, random.nextFloat)

      // make barycentric coords
      val (a, b) = ( (1.0f - sqr1), ((1.0f - r2) * sqr1) )

      // interpolate position by scaling edges by barycentric coords
      (edge0 * a) + (edge3 * b) + vertexs_m(0)
   }


   def normal  = (edge0 cross edge1).unitized

   def tangent = edge0.unitized

   // (half area of parallelogram)
   def area    = 0.5f * (edge0 cross edge1).length


/// implementation -------------------------------------------------------------

   private def edge0 = vertexs_m(1) - vertexs_m(0)
   private def edge1 = vertexs_m(2) - vertexs_m(1)
   private def edge3 = vertexs_m(2) - vertexs_m(0)


/// fields ---------------------------------------------------------------------

   private val vertexs_m = Array.range(0,3).map( i => Vector3f(modelFile_c) )

   val reflectivity = Vector3f(modelFile_c).clamped01
   val emitivity    = Vector3f(modelFile_c).clampedMin( Vector3f.ZERO )
}




object Triangle
{
/// constants ------------------------------------------------------------------

   // General tolerance of 1 mm seems reasonable.
   private[minilight] val TOLERANCE = 1.0f / 1024.0f
}

Vector3f.scala

package hxa7241.graphics




/**
 * Yes, its the 3D vector class!.<p>
 *
 * ...mostly the usual sort of stuff.
 * (Unused methods are commented out. They do work fine though.)<p>
 *
 * @constant <p>
 */
final class Vector3f( val x:Float, val y:Float, val z:Float ) extends NotNull
{
/// standard overrides----------------------------------------------------------

   // must enable this method if == or != is used
   //override def equals( v:Any ) = v match
   //{
   //   case v:Vector3f => (x == v.x) & (y == v.y) & (z == v.z)
   //   case _          => false
   //}
   //override def hashCode = (x, y, z).hashCode

   //override def toString = "(" + x + " " + y + " " + z + ")"
   //def toArray = Array( x, y, z )


/// queries --------------------------------------------------------------------

/// elements
   def apply( i:Int ) = i match { case 2 => z; case 1 => y; case 0 => x }

/// => Float
   //def sum      =  x + y + z
   //def average  = (x + y + z) * (1.0f / 3.0f)
   //def smallest = x min (y min z)
   //def largest  = x max (y max z)

   def length            = Math.sqrt( this dot this ).toFloat
   def dot( v:Vector3f ) = (x * v.x) + (y * v.y) + (z * v.z)
   //def distance( v:Vector3f ) = (this - v).length

/// => vector3f
   def unary_-  = new Vector3f( -x, -y, -z )
   def abs      = new Vector3f( x.abs, y.abs, z.abs )
   // Zero vectors, and vectors of near zero magnitude, return zero vectors;
   // Vectors of extremely large magnitude return zero vectors:
   def unitized = if( length != 0.0f ) this * (1.0f / length) else Vector3f.ZERO
   def cross( v:Vector3f ) = new Vector3f(
      (y * v.z) - (z * v.y),
      (z * v.x) - (x * v.z),
      (x * v.y) - (y * v.x) )

   def +( v:Vector3f ) = new Vector3f( (x + v.x), (y + v.y), (z + v.z) )
   def -( v:Vector3f ) = new Vector3f( (x - v.x), (y - v.y), (z - v.z) )
   def *( v:Vector3f ) = new Vector3f( (x * v.x), (y * v.y), (z * v.z) )
   //def /( v:Vector3f ) = new Vector3f( (x / v.x), (y / v.y), (z / v.z) )
   def *( f:Float )    = new Vector3f( (x * f),   (y * f),   (z * f)   )
   //def /( f:Float )    = this * (1.0f / f)

/// logical
   def isZero = (x == 0.0f) & (y == 0.0f) & (z == 0.0f)

/// clamp
   def clampedMin( lower:Vector3f )           = zip( Math.max, lower )
   def clampedMax( upper:Vector3f )           = zip( Math.min, upper )
   //def clamped   ( lo:Vector3f, up:Vector3f ) = clampedMin(lo).clampedMax(up)
   def clamped01 = clampedMin(Vector3f.ZERO).clampedMax(Vector3f.ONE)

/// comprehensions
   def fold( f:(Float,Float)=>Float ) = f( f(x, y), z )
   def zip ( f:(Float,Float)=>Float, v:Vector3f ) =
      new Vector3f( f(x, v.x), f(y, v.y), f(z, v.z) )
}




object Vector3f
{
/// constructors ---------------------------------------------------------------

   def apply()                            = new Vector3f( 0.0f, 0.0f, 0.0f )
   def apply( n:Float )                   = new Vector3f( n, n, n )
   def apply( x:Float, y:Float, z:Float ) = new Vector3f( x, y, z )

   def apply( modelFile:{def next:String} ) =
   {
      val a = Array.range(0,5).map( i => modelFile.next )

      new Vector3f( a(1).toFloat, a(2).toFloat, a(3).toFloat )
   }


/// constants ------------------------------------------------------------------

   val ZERO       = Vector3f( 0.0f )
   //val HALF       = Vector3f( 0.5f )
   val ONE        = Vector3f( 1.0f )
   //val EPSILON    = Vector3f( Math.EPS_FLOAT )
   //val ALMOST_ONE = Vector3f( 1.0f - Math.EPS_FLOAT )
   //val MINIMUM    = Vector3f( -Math.MAX_FLOAT )
   //val MAXIMUM    = Vector3f( Math.MAX_FLOAT )
   //val SMALL      = Vector3f( 1e-12f )
   //val LARGE      = Vector3f( 1e+12f )
   //val SMALL_48   = Vector3f( 1.0f / (65536.0f * 65536.0f * 65536.0f) )
   //val LARGE_48   = Vector3f( 65536.0f * 65536.0f * 65536.0f )
   //val X          = Vector3f( 1.0f, 0.0f, 0.0f )
   //val Y          = Vector3f( 0.0f, 1.0f, 0.0f )
   //val Z          = Vector3f( 0.0f, 0.0f, 1.0f )
}

TokenStream.scala

package hxa7241.general


import java.io.{FileReader, BufferedReader, StreamTokenizer, EOFException}




/**
 * Make some dismal Java file-reading things half-usable.<p>
 */
class TokenStream( pathname_c:String ) extends NotNull
{
/// commands -------------------------------------------------------------------

   def close = file_m.close()


/// queries --------------------------------------------------------------------

   def next =
   {
      tokens_m.nextToken()
      if( tokens_m.ttype == StreamTokenizer.TT_EOF ) throw new EOFException
      if( tokens_m.ttype < 0 ) tokens_m.sval else "" + tokens_m.ttype.toChar
   }


/// fields ---------------------------------------------------------------------

   private val file_m   = new BufferedReader( new FileReader( pathname_c ) )
   private val tokens_m = new StreamTokenizer( file_m )

   tokens_m.ordinaryChars( 42, 122 );  tokens_m.wordChars( 42, 122 )
}

License

The source code is available according to the (new) BSD license:

———