next_inactive up previous root


Source code for Virtual World movies

Gene Michael Stover

created Sunday, 2006 February 26
updated Monday, 2006 December 25

Copyright © 2006 Gene Michael Stover. All rights reserved. Permission to copy, store, & view this document unmodified & in its entirety is granted.


Contents

1. What is this?

These are my notes & source code which I used to create my virtual world movies [2].

Since the beginning of this project, & current as of 2006 September 24, I plan to keep the source code private. That's why it's in a document by itself & not in the virtual world movies document.

2. License

The source code is currently private. If I release it publicly, it will probably be under the Gnu General Public License.

3. All source code

world.zip is everything in a ZIP file.

4. First try: fractal balls

To create the Fractal balls:

  1. Make sure your current directory is such that you have a src/balls.lisp file & a src/balls.data file. Do this in your operating system's command line or by binding the correct pathname to *DEFAULT-PATHNAME-DEFAULTS* .4.1
  2. Go to your Lisp command line if you aren't there already.
  3. (load "src/balls.lisp")
  4. (in-package "COM.CYBERTIGGYR.GENE.WORLD.BALLS")
  5. (balls0)
  6. Leave that balls0 function call running. Meanwhile, go to another window or another command line session of some sort.
  7. Make sure your current directory is the tmp directory within the current directory you used in Lisp.
  8. On the command line (probably the operating system command line), run ``avi-ar -davi-ar.stop -E -ccvid -f24 balls0.avi''.

The balls0 Lisp function will generate frame file & leave them in the ./tmp directory. The avi-ar function will consume the frame files & delete each file as it's consumed. It will leave a movie in the balls0.avi file. The movie will be encoded with Cinepak.

The source code & data for Fractal balls includes:


4.1 balls.data

The balls.data file is too big to print. It is available at http://cybertiggyr.com/gene/world/src/balls.lisp.


4.2 balls.lisp

This source code is also available at
http://cybertiggyr.com/gene/world/src/balls.lisp. 

;;; -*- Mode: Lisp -*-
;;;
;;; $Header: /home/gene/library/website/docsrc/world/src/RCS/balls.lisp,v 395.1 2008/04/20 17:25:50 gene Exp $
;;;
;;; Copyright (c) 2006 Gene Michael Stover.  All rights reserved.
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as
;;; published by the Free Software Foundation; either version 2 of the
;;; License, or (at your option) any later version.
;;;
;;; This program is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;; GNU General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public
;;; License along with this program; if not, write to the Free Software
;;; Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
;;; USA
;;;

(defpackage "COM.CYBERTIGGYR.GENE.WORLD.BALLS"
  (:use "COMMON-LISP"))
(in-package "COM.CYBERTIGGYR.GENE.WORLD.BALLS")

(defun save-world-as-pbrt (z)
  (with-open-file (strm (make-pathname :name "balls-tmp" :type "pbrt")
                        :direction :output :if-exists :rename-and-delete)
    (format strm "ConcatTransform [ 0.52635503 -0.48208499")
    (format strm " -0.70038903 0 -0.85026503 -0.29843301 -0.43357399")
    (format strm " 0 7.2777104e-18 0.82372999 -0.56698197 0 0 0 0 1")
    (format strm " ]~&")
    (format strm "Translate -2.0999999 -1.3 ~,9E~&" z)
    (with-open-file (s2 "src/balls.data")
      (do ((line (read-line s2 nil s2) (read-line s2 nil s2)))
          ((eq line s2))
          (format strm "~A~&" line)))
    (truename strm)))

(defvar *frame-number* 0)

(defun start-movie ()
  "Prepare external programs so we can write frames.  Return
NIL on error, true on success."
  (setq *frame-number* 0)
  (delete-file "tmp/avi-ar.stop")
  'start-movie)

(defun write-frame (world)
  "WORLD is a description of the world.  In our case, it's
just the camera location.  It's a list of (X Y Z)."
  (let ((tmpbmp (make-pathname :directory '(:relative "tmp")
                               :name (format nil "~A" *frame-number*)
                               :type "tmp"))
        (bmp (make-pathname :directory '(:relative "tmp")
                            :name (format nil "~A" *frame-number*)
                            :type "bmp")))
    (incf *frame-number*)
    (if (and
         ;; Describe the world in a PBRT file.  The PBRT file is
         ;; always called "balls-tmp.pbrt" in the current directory.
         (save-world-as-pbrt world)
         ;; Tell PBRT to render the scene.  It will put its
         ;; output in "pbrt.exr" in the current directory.
         (ext:run-program "pbrt" :arguments (list "balls-tmp.pbrt"))
         ;; Convert the PBRT file to a PPM file called "balls-tmp.ppm".
         (ext:run-program "exrtoppm" :arguments (list "-ipbrt.exr"
                                                      "-oballs-tmp.ppm"))
         ;; Convert the PPM file to a BMP file.  
         (ext:run-program "ppmtobmp" :arguments (list "-bpp=24"
                                                      "balls-tmp.ppm")
                          :output tmpbmp))
        (progn
          (rename-file tmpbmp bmp)
          ;; Dispose of the temporary files.
          (dolist (pn '("balls-tmp.pbrt" "pbrt.exr" "balls-tmp.ppm"))
            (unless (delete-file pn)
              (format t "~&Can't delete ~A" pn)))
          t)
      ;; else
      (progn
        (format t "~&One of the external programs failed.")
        (force-output)
        nil))))

(defun finish-movie ()
  (with-open-file (strm "tmp/avi-ar.stop" :direction :output
                        :if-exists :rename-and-delete)
    (format strm "Woo woo!~&")))

(defun balls0 ()
  (if (start-movie)
      (let* ((zmin -3.0)
             (zmax 0.0)
             (fps 24.0)
             (movie-length 20.0)        ; movie duration in seconds
             (dz (/ (- zmax zmin) fps movie-length)))
        (do ((z zmin (+ z dz)))
            ((or (>= z zmax) (not (write-frame z))))
            (format t "~&Z is ~A" z) (force-output))
        (finish-movie))
    (format t "~&~A: ~A failed" 'balls0 'start-movie)))

;;; --- end of file ---

5. World 0: Two pyramids, a sphere, & a cylinder

These notes may or may not accurately describe the final form of World 0.

For the Group of 3 world, I'll have a pyramid, a cube about the height of the pyramid, & a sphere about that same size, too. They will be near each other but not touching.

The camera will point into the center of the group of three objects. It will circle them, taking 60 seconds to make a complete circle.

The floor will be flat, a solid, single color. It will not extend to infinity; instead, it will have a limit on its size.

We'll have two light sources. One will be directly above the center of the group. The other will be above the group but to one side.

To create the movie, do this:

  1. Make sure your current directory is such that you have a src/world0.lisp file. Do this in your operating system's command line or by binding the correct pathname to *DEFAULT-PATHNAME-DEFAULTS* .
  2. Go to your Lisp command line if you aren't there already.
  3. (load "src/world0.lisp")
  4. (in-package "COM.CYBERTIGGYR.GENE.WORLD0")
  5. (make-movie)
  6. Leave that make-movie function call running. Meanwhile, go to another window or another command line session of some sort.
  7. Make sure your current directory is the tmp directory within the current directory you used in Lisp.
  8. On the command line (probably the operating system command line), run ``avi-ar -davi-ar.stop -E -ccvid -f24 world0.avi''.


5.1 world0.lisp

This source code is also available at
http://cybertiggyr.com/gene/world/src/world0.lisp. 

;;; -*- Mode: Lisp -*-
;;;
;;; $Header: /home/gene/library/website/docsrc/world/src/RCS/world0.lisp,v 395.1 2008/04/20 17:25:50 gene Exp $
;;;
;;; Copyright (c) 2006 Gene Michael Stover.  All rights reserved.
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as
;;; published by the Free Software Foundation; either version 2 of the
;;; License, or (at your option) any later version.
;;;
;;; This program is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;; GNU General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public
;;; License along with this program; if not, write to the Free Software
;;; Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
;;; USA
;;;

(defpackage "COM.CYBERTIGGYR.GENE.WORLD0"
  (:use "COMMON-LISP" "COM.CYBERTIGGYR.GENE.WORLD.MATH"))
(in-package "COM.CYBERTIGGYR.GENE.WORLD0")

(let* ((package (find-package "EXT")) ; for clisp
       (run (and package (find-symbol "RUN-PROGRAM" package))))
  (defun xrun-program (&rest args)
    (if run
        (apply run args)
      (format t "~&Can't run external program ~S" args))))

;;;
;;; WORLD
;;;

(defstruct world
  (duration 0 :type real)
  (camera-angle-delta 0 :type real)
  (fps 24.0 :type real)
  (frame-count 0 :type (integer 0)))

(defun create-world (radians duration fps)
  "Create a WORLD designed to rotate the camera around the
picture in DURATION seconds at FPS frame/second."
  (let ((delta (/ radians duration fps)))
    (format t "~%~A: Camera angle delta is ~G radians." 'create-world delta)
    (make-world
     :camera-angle-delta delta
     :fps fps)))

(defun world-camera-angle (w)
  "Return camera angle in radians."
  (declare (type world w))
  (mod (* (world-camera-angle-delta w) (world-frame-count w)) K2PI))

(defun world-seconds (w)
  "Return the number of seconds which have passed in the world.
Converts the frame counter to seconds."
  (declare (type world w))
  (assert (plusp (world-fps w)))
  (/ (world-frame-count w) (world-fps w)))

(defun increment-world (w)
  (declare (type world w))
  (incf (world-frame-count w))
  w)

(defun write-pbrt (w)
  (declare (type world w))
  (with-open-file (strm (make-pathname :name "world0-tmp" :type "pbrt")
                        :direction :output :if-exists :rename-and-delete)
    (format strm "~%")
    (format strm "~%LookAt 5 5 1   0 0 0    0 0 1")
    (format strm "~%Camera \"perspective\" \"float fov\" [30]")
    (format strm "~%Film \"image\"")
    (format strm "~&     \"integer xresolution\" [320]")
    (format strm "~&     \"integer yresolution\" [200]")

    (format strm "~&WorldBegin")
    (format strm "~&LightSource \"distant\" \"point from\" [100 100 100]")
    (format strm "~&            \"point to\" [0 0 0]")
    (format strm "~&            \"color L\" [18 18 18]")
    (format strm "~&Rotate ~,,,,,,'EG  0 0 1"
            (radians-to-degrees (world-camera-angle w)))
    (format strm "~&AttributeBegin")
    (format strm "~&Include ~S" "src/world0-a.pbrt")
    (format strm "~&AttributeEnd")
    (format strm "~&WorldEnd")
    (format strm "~&")
    (truename strm)))

;;;
;;; MOVIES & WRITING FRAMES
;;;
  
(defvar *frame-number* 0)

(defun start-movie ()
  "Prepare external programs so we can write frames.  Return
NIL on error, true on success."
  (setq *frame-number* 0)
  (delete-file "tmp/avi-ar.stop")
  'start-movie)

(defun write-frame (world)
  "WORLD is a description of the world.  In our case, it's
just the camera location.  It's a list of (X Y Z)."
  (let ((tmpbmp (make-pathname :directory '(:relative "tmp")
                               :name (format nil "~A" *frame-number*)
                               :type "tmp"))
        (bmp (make-pathname :directory '(:relative "tmp")
                            :name (format nil "~A" *frame-number*)
                            :type "bmp")))
    (incf *frame-number*)
    (if (and
         ;; Describe the world in a PBRT file.  The PBRT file is
         ;; always called "world0-tmp.pbrt" in the current directory.
         (write-pbrt world)
         ;; Tell PBRT to render the scene.  It will put its
         ;; output in "pbrt.exr" in the current directory.
         (xrun-program "pbrt" :arguments (list "world0-tmp.pbrt"))
         ;; Convert the PBRT file to a PPM file called "world0-tmp.ppm".
         (xrun-program "exrtoppm" :arguments (list "-ipbrt.exr"
                                                      "-oworld0-tmp.ppm"))
         ;; Convert the PPM file to a BMP file.  
         (xrun-program "ppmtobmp" :arguments (list "-bpp=24"
                                                   "world0-tmp.ppm")
                       :output tmpbmp))
        (progn
          (rename-file tmpbmp bmp)
          ;; Dispose of the temporary files.
          (dolist (pn '("world0-tmp.pbrt" "pbrt.exr" "world0-tmp.ppm"))
            (unless (delete-file pn)
              (format t "~&Can't delete ~A" pn)))
          bmp)
      ;; else
      (progn
        (format t "~&One of the external programs failed.")
        (force-output)
        nil))))

(defun finish-movie ()
  (with-open-file (strm "tmp/avi-ar.stop" :direction :output
                        :if-exists nil)
    (when strm
      (format strm "Woo woo!~&"))
    (and strm (truename strm))))

(defun make-movie (seconds &optional (w0 (create-world K2PI seconds 24)))
  (if (start-movie)
      (do ((w w0 (increment-world w)))
          ((or (>= (world-seconds w) seconds) (not (write-frame w)))
           (progn (finish-movie) w)))
    ;; else
    (format t "~&~A: ~A failed" 'make-movie 'start-movie)))

;;; --- end of file ---

6. World 1: Field of changing pyramids

As of Monday, 2006 December 25, I have not worked on World 1 since October or before. I do not feel motivated to finish it. Maybe I will later.


6.1 world1.lisp

This source code is also available at
http://cybertiggyr.com/gene/world/src/world1.lisp. 

;;; -*- Mode: Lisp -*-
;;;
;;; $Header: /home/gene/library/website/docsrc/world/src/RCS/world1.lisp,v 395.1 2008/04/20 17:25:50 gene Exp $
;;;
;;; Copyright (c) 2006 Gene Michael Stover.  All rights reserved.
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as
;;; published by the Free Software Foundation; either version 2 of the
;;; License, or (at your option) any later version.
;;;
;;; This program is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;; GNU General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public
;;; License along with this program; if not, write to the Free Software
;;; Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
;;; USA
;;;

;;;
;;; WORLD 1 is a field of pyramids.
;;; The base of every pyramid is 2 by 2, but each pyramid has
;;; a randomly selected height, color, material, &
;;; translucence (if appropriate for the material).
;;; The bases of the pyramids fit together in the plane.
;;; The camera circles the field so you can get a look at the
;;; pyramids.
;;;

(defpackage "COM.CYBERTIGGYR.GENE.WORLD1"
  (:use "COMMON-LISP" "COM.CYBERTIGGYR.GENE.WORLD.MATH"))
(in-package "COM.CYBERTIGGYR.GENE.WORLD1")

;;gms (let* ((package (find-package "EXT"))     ; for clisp
;;gms        (run (and package (find-symbol "RUN-PROGRAM" package))))
;;gms   (defun xrun-program (&rest args)
;;gms     (if run
;;gms   (apply run args)
;;gms       (format t "~&Can't run external program ~S" args))))
;;gms 
;;gms ;;;
;;gms ;;; Protocol for objects in the world
;;gms ;;;
;;gms 
;;gms (defgeneric write-pbrt (x strm)
;;gms   (:documentation
;;gms    "Tell object X to describe itself for the PBRT ray tracer.  Send
;;gms the description to STRM.  STRM is a character output stream.
;;gms Probably should return X."))
;;gms 
;;gms (defgeneric update (x delta)
;;gms   (:documentation
;;gms    "Tell object X to increment itself.  DELTA, a real number, is the
;;gms number of seconds which have passed since X last updated itself."))
;;gms 
;;gms ;;;
;;gms ;;; Class Shape.
;;gms ;;;
;;gms 
;;gms (defclass shape ()
;;gms   ((location :accessor shape-location :initform (make-point))
;;gms    (anglex :accessor shape-anglex :initform 0)
;;gms    (angley :accessor shape-angley :initform 0)
;;gms    (anglez :accessor shape-anglez :initform 0)
;;gms    (scale :accessor shape-scale :initform 1)
;;gms    (material :accessor shape-material :initform nil)
;;gms    (texture :accessor shape-material :initform nil))
;;gms   (:documentation
;;gms    "A Shape has a position, three angles (one against each axis), a
;;gms scale, a material, & a texture."))
;;gms 
;;gms ;;;
;;gms ;;; Class Pyramid
;;gms ;;;
;;gms 
;;gms                                   ; (defclass pyramid (shape)
;;gms                                   ;   (
;;gms 
;;gms 
;;gms ;;;
;;gms ;;; WORLD
;;gms ;;;
;;gms 
;;gms (defstruct world
;;gms   (duration 0 :type real)
;;gms   (camera-angle-delta 0 :type real)
;;gms   (fps 24.0 :type real)
;;gms   (frame-count 0 :type (integer 0))
;;gms   (pyramids nil :type (array * (* *))))
;;gms 
;;gms (defun create-world (radians duration fps)
;;gms   "Create a WORLD designed to rotate the camera around the
;;gms picture in DURATION seconds at FPS frame/second."
;;gms   (let ((delta (/ radians duration fps)))
;;gms     (format t "~%~A: Camera angle delta is ~G radians." 'create-world delta)
;;gms     (make-world
;;gms      :camera-angle-delta delta
;;gms      :fps fps)))
;;gms 
;;gms (defun world-camera-angle (w)
;;gms   "Return camera angle in radians."
;;gms   (declare (type world w))
;;gms   (mod (* (world-camera-angle-delta w) (world-frame-count w)) K2PI))
;;gms 
;;gms (defun world-seconds (w)
;;gms   "Return the number of seconds which have passed in the world.
;;gms Converts the frame counter to seconds."
;;gms   (declare (type world w))
;;gms   (assert (plusp (world-fps w)))
;;gms   (/ (world-frame-count w) (world-fps w)))
;;gms 
;;gms (defun increment-world (w)
;;gms   (declare (type world w))
;;gms   (incf (world-frame-count w))
;;gms   w)
;;gms 
;;gms (defun write-pbrt (w)
;;gms   (declare (type world w))
;;gms   (with-open-file (strm (make-pathname :name "world1-tmp" :type "pbrt")
;;gms                   :direction :output :if-exists :rename-and-delete)
;;gms     (format strm "~%")
;;gms     (format strm "~%LookAt 10 10 1   0 0 0    0 0 1")
;;gms     (format strm "~%Camera \"perspective\" \"float fov\" [30]")
;;gms     (format strm "~%Film \"image\"")
;;gms     (format strm "~&     \"integer xresolution\" [320]")
;;gms     (format strm "~&     \"integer yresolution\" [200]")
;;gms 
;;gms     (format strm "~&WorldBegin")
;;gms     (format strm "~&LightSource \"distant\" \"point from\" [100 100 100]")
;;gms     (format strm "~&            \"point to\" [0 0 0]")
;;gms     (format strm "~&            \"color L\" [18 18 18]")
;;gms     (format strm "~&Rotate ~,,,,,,'EG  0 0 1"
;;gms       (radians-to-degrees (world-camera-angle w)))
;;gms     (format strm "~&AttributeBegin")
;;gms     (format strm "~&Include ~S" "src/world1-a.pbrt")
;;gms     (format strm "~&AttributeEnd")
;;gms     (format strm "~&WorldEnd")
;;gms     (format strm "~&")
;;gms     (truename strm)))
;;gms 
;;gms ;;;
;;gms ;;; MOVIES & WRITING FRAMES
;;gms ;;;
;;gms   
;;gms (defvar *frame-number* 0)
;;gms 
;;gms (defun start-movie ()
;;gms   "Prepare external programs so we can write frames.  Return
;;gms NIL on error, true on success."
;;gms   (setq *frame-number* 0)
;;gms   (delete-file "tmp/avi-ar.stop")
;;gms   'start-movie)
;;gms 
;;gms (defun write-frame (world)
;;gms   "WORLD is a description of the world.  In our case, it's
;;gms just the camera location.  It's a list of (X Y Z)."
;;gms   (let ((tmpbmp (make-pathname :directory '(:relative "tmp")
;;gms                          :name (format nil "~A" *frame-number*)
;;gms                          :type "tmp"))
;;gms   (bmp (make-pathname :directory '(:relative "tmp")
;;gms                       :name (format nil "~A" *frame-number*)
;;gms                       :type "bmp")))
;;gms     (incf *frame-number*)
;;gms     (if (and
;;gms    ;; Describe the world in a PBRT file.  The PBRT file is
;;gms    ;; always called "world1-tmp.pbrt" in the current directory.
;;gms    (write-pbrt world)
;;gms    ;; Tell PBRT to render the scene.  It will put its
;;gms    ;; output in "pbrt.exr" in the current directory.
;;gms    (xrun-program "pbrt" :arguments (list "world1-tmp.pbrt"))
;;gms    ;; Convert the PBRT file to a PPM file called "world1-tmp.ppm".
;;gms    (xrun-program "exrtoppm" :arguments (list "-ipbrt.exr"
;;gms                                              "-oworld1-tmp.ppm"))
;;gms    ;; Convert the PPM file to a BMP file.  
;;gms    (xrun-program "ppmtobmp" :arguments (list "-bpp=24"
;;gms                                              "world1-tmp.ppm")
;;gms                  :output tmpbmp))
;;gms   (progn
;;gms     (rename-file tmpbmp bmp)
;;gms     ;; Dispose of the temporary files.
;;gms     (dolist (pn '("world1-tmp.pbrt" "pbrt.exr" "world1-tmp.ppm"))
;;gms       (unless (delete-file pn)
;;gms         (format t "~&Can't delete ~A" pn)))
;;gms     bmp)
;;gms       ;; else
;;gms       (progn
;;gms   (format t "~&One of the external programs failed.")
;;gms   (force-output)
;;gms   nil))))
;;gms 
;;gms (defun finish-movie ()
;;gms   (with-open-file (strm "tmp/avi-ar.stop" :direction :output
;;gms                   :if-exists nil)
;;gms     (when strm
;;gms       (format strm "Woo woo!~&"))
;;gms     (and strm (truename strm))))
;;gms 
;;gms (defun make-movie (seconds &optional (w0 (create-world K2PI seconds 24)))
;;gms   (if (start-movie)
;;gms       (do ((w w0 (increment-world w)))
;;gms     ((or (>= (world-seconds w) seconds) (not (write-frame w)))
;;gms      (progn (finish-movie) w)))
;;gms     ;; else
;;gms     (format t "~&~A: ~A failed" 'make-movie 'start-movie)))

;;; --- end of file ---

7. World 2: Faultline landscape

7.1 How to build it

To create the movie, do this:

  1. Make sure your current directory is such that you have a src/world2.lisp file. Do this on your operating system's command line or by binding the correct pathname to *DEFAULT-PATHNAME-DEFAULTS* .
  2. Go to your Lisp command line if you aren't there already.
  3. If you are loading my entire CGI movie system from scratch, (load "src/loadall.lisp"). Otherwise, you've already loaded the whole system, & you just need to load the World 2 part (maybe because you've edited it), so (load "src/world2.lisp").
  4. (in-package "COM.CYBERTIGGYR.GENE.WORLD2")
  5. (make-movie)
  6. Leave that make-movie function call running. Meanwhile, go to another window or another command line session of some sort.
  7. Make sure your current directory is the tmp directory within the current directory you used in Lisp.
  8. On the command line (probably the operating system command line), run ``avi-ar -davi-ar.stop -E -ccvid -f24 world2.avi''.
  9. After both the Lisp make-movie function finishes & the avi-ar program finishes, your movie will be in tmp/world2.avi.

7.2 Description

Once created, World 2 is a static landscape. The camera tours it, but the landscape does not change.

The landscape is generated with a variation of the ``faultline displacement'' algorithm from Chapter 7 of [1].

  1. The world is a cubic kilometer.

  2. Within the ray-tracer, positions in the world are measures in millimeters.

    1. The point which is most south-west & at the lowest elevation is at $0, 0, 0$.

    2. The point which is most north-east & at the highest elevation is at $10^{6}, 10^{6}, 10^{6}$.

  3. Within Lisp, the world's units are also millimeters, but Lisp is free to measure them as integers, floating point, or ratios.

  4. Sea level in the world is $500 \times 10^{3}$.

  5. We'll try to draw the water. I think we can put a horizontal, reflective blue plain through the world at elevation $500 \times 10^{3}$.

  6. We'll have four light sources, one for each corner at the highest elevation.

    1. The light source at the south-west corner will be the brightest. It is supposed to be the sun.

    2. The lights at the south-east, north-east, & north-west corners all have the same intensity, & that intensity is less than that of the sun (south-west) light source.

  7. The six walls which bound the world will reflect light. Maybe they should be gray. I'll use something so you can see them & so they reflect light to help keep the world brighter. It's okay if the walls make it look like the world is in a box. It's also okay if the walls have a nice texture or even if they have a texture which would not make sense in context (like bricks or wood).

  8. The camera will tour the world.

  9. The camera will remain above the terrain height at the camera's latitude & longitute. It will never go below sea level.

  10. The camera's height should be roughly ``eye level''. A height of 150 centimeters might be appropriate, but I can experiment with different values.

  11. The camera will avoid passing through surfaces. I'm sure I can stick to that rule most of the time, but if I end up with a few cases where it breaks the rule, that's okay.

  12. The movie starts while the world is being created. So we see the world created. I predict that won't take many frames, so that part of the movie could be boring. That's fine.

  13. While the world is being created, the camera will provide a basic view, probably from a high elevation at one corner of the world. After the world is created, the camera begins its tour.

7.3 Discussion

We'll put the entire World 2 in its own Lisp package. 

(in-package "COM.CYBERTIGGYR.GENE.WORLD2")

What's the Lisp data structure for the world? We must be able to manipulate it (so we can create it), create a camera tour through it, & describe it for the ray tracer.

The book [1] talks about height maps. I thought that height maps would not work for me because I need to describe the world with triangles or other polygons for the ray tracer. Then I realized that it's easy to convert a height map to a field of trangles.

Let's say that the height map is a 2-D matrix of heights. For example, elevation $z = height(x)(y)$. I can make a triangle in 3-space with these three vertices:

I can get another triangle from (x, y, height(x)(y)), (x + 1, y, height(x + 1)(y)), (x, y + 1, height(x)(y + 1)).

If the triangles are small enough, the user won't notice them.

That solves that problem, but it reminds me that memory is limited, so I need to know how many data points I'll have in the virtual world. Notice that this is independant of the units of measurement within the world.

Let's assume that a numeric value in Lisp requires 8 octets. That's more than the value probably requires, but Lisp has some overhead. So I think this 8 octet estimate is better than the 4 octet estimate I was tempted to use.

Here's a table which maps the space between elevation measurements to memory requirements. It assumes the world is a cubic kilometer.

resolution per-side total space English
1 mm $10^{6}$ $10^{12}$ $8 \times 10^{12}$ too big
10 mm $10^{5}$ $10^{10}$ $80 \times 10^{9}$ 80 gigabytes
100 mm $10 \times 10^{3}$ $100 \times 10^{6}$ $800 \times 10^{6}$ 800 megabytes
500 mm $2 \times 10^{3}$ $4 \times 10^{6}$ $32 \times 10^{6}$ 32 megabytes
1000 mm $10^{3}$ $10^{6}$ $8 \times 10^{6}$ 8 megabytes

Some informal tests with clisp on Walleye, my Windows computer, suggest that this table of estimates is realistic. Actually, they're a little pessimistic. So I'll go with a measurement every 500 millimeters. That resolution is lower than I had hoped, but it's about all I can do without pulling some kind of variable resolution tricks. Maybe I'll pull tricks like that some day, but not for this project. For this project, I make a single, static world. Or maybe another way to describe it is a world with a single room. I'm concerned that a measurement every half meter will be noticeable & annoying in the movie, but we'll see. That's the point of an exercise like this. It helps me learn.

7.3.1 Terrain

The World object can contain a Terrain object.

The Terrain contains elevation samples. Maybe it could also contain land type information, but for now, let's stick with elevations.

Because coordinates in the world are conceptually continuous, Terrain does not have a sample for every possible location. Even if coordinates are digital, not continuous, the computer probably does not have enough memory for Terrain to have a sample for each location.

Here's a possible Terrain structure: 

(defstruct terrain
  ;; World's width (East-to-West) & breadth (North-to-South)
  ;; in millimeters
  (width 0 :type real)
  (breadth 0 :type real)
  ;; 2-D matrix of elevation samples.
  ;; Here's a default.  You can specify your own 2-D matrix
  ;; with different dimentions.
  (sample (make-array '(1000 1000) :element-type 'real
                      :initial-element 0 :adjustable nil
                      :fill-pointer nil)))

We can ask Terrain for the elevation at any point in the world. If that point falls on a sample, Terrain can return the sample, but most points will not fall on a sample. So Terrain must interpolate.

Remember that Terrain contains samples on an xy grid, & we'll use three saples ( (x, y, z), (x + 1, y, z), (x, y + 1, z) ) to form a triangle we give to the ray tracer.

A plane is $Ax + By + Cz = 0$.

We'll want to solve for z, given x & y. With that x & y, we'll be able to find three points from the terrain. Those three points are $(x_1, y_1, z_1)$, $(x_2, y_2, z_2)$, and $(x_3, y_3, z_3)$.

We'll need to know A, B, & C.


\begin{displaymath} A = \frac{-B y - Cz}{x} \end{displaymath} (7.1)

This works when $x \ne 0$. When $x = 0$, we can make A be anything. At those times, we might as well make $A = 0$.

Similarly, we can solve for B & C.


\begin{displaymath} B = \frac{-Ax - Cz}{y} \end{displaymath} (7.2)


\begin{displaymath} C = \frac{-Ax - By}{z} \end{displaymath} (7.3)

I might as well insert the three known points into those equations. That gives us:


\begin{displaymath} A = \frac{-B y_1 - Cz_1}{x_1} \end{displaymath} (7.4)


\begin{displaymath} B = \frac{-A x_2 - C z_2}{y_2} \end{displaymath} (7.5)


\begin{displaymath} C = \frac{-A x_3 - B y_3}{z_3} \end{displaymath} (7.6)

Use B to solve for A in terms of C:


\begin{displaymath} A = \frac{-(\frac{-A x_2 - C z_2}{y_2}) y_1 - Cz_1} {x_1} \end{displaymath} (7.7)


\begin{displaymath} A x_1 + Cz_1 = -(\frac{-A x_2 - C z_2}{y_2}) y_1 \end{displaymath} (7.8)


\begin{displaymath} A \frac{x_1}{y_1} + C \frac{z_1}{y_1} = \frac{A x_2 + C z_2}{y_2} \end{displaymath} (7.9)


\begin{displaymath} A \frac{x_1}{y_1} + C \frac{z_1}{y_1} = A \frac{x_2}{y_2} + C \frac{z_2}{y_2} \end{displaymath} (7.10)


\begin{displaymath} A (\frac{x_1}{y_1} - \frac{x_2}{y_2}) = C (\frac{z_2}{y_2} - \frac{z_1}{y_1}) \end{displaymath} (7.11)

Simplify by multiplying by $y_1$ ...


\begin{displaymath} A (x_1 - \frac{y_1 x_2}{y_2}) = C (\frac{y_1 z_2}{y_2} - z_1) \end{displaymath} (7.12)

...then by $y_2$ ...


\begin{displaymath} A (x_1 y_2 - y_1 x_2) = C (y_1 z_2 - z_1 y_2) \end{displaymath} (7.13)

Isolate A ...


\begin{displaymath} A = C \frac{y_1 z_2 - z_1 y_2}{x_1 y_2 - y_1 x_2} \end{displaymath} (7.14)

Use our new interpretation of A to obtain C in terms of B.


\begin{displaymath} C = \frac{-(C \frac{y_1 z_2 - z_1 y_2}{x_1 y_2 - y_1 x_2}) x_3 - B y_3}{z_3} \end{displaymath} (7.15)


\begin{displaymath} C z_3 = -(C \frac{y_1 z_2 - z_1 y_2}{x_1 y_2 - y_1 x_2}) x_3 - B y_3 \end{displaymath} (7.16)


\begin{displaymath} C z_3 + (C \frac{y_1 z_2 - z_1 y_2}{x_1 y_2 - y_1 x_2}) x_3 = - B y_3 \end{displaymath} (7.17)

Multiply by $x_1 y_2 - y_1 x_2$ ...


\begin{displaymath} C (z_3) (x_1 y_2 - y_1 x_2) + C (y_1 z_2 - z_1 y_2) x_3 = - B (y_3) (x_1 y_2 - y_1 x_2) \end{displaymath} (7.18)


\begin{displaymath} C (x_1 y_2 z_3 - y_1 x_2 z_3) + C (y_1 z_2 x_3 - z_1 y_2 x_3) = - B (x_1 y_2 y_3 - y_1 x_2 y_3) \end{displaymath} (7.19)

Coalesce the terms on C & the minus sign in front of B to simplify ...


\begin{displaymath} C (x_1 y_2 z_3 - y_1 x_2 z_3 + y_1 z_2 x_3 - z_1 y_2 x_3) = B (y_1 x_2 y_3 - x_1 y_2 y_3) \end{displaymath} (7.20)

You'd think I could simplify something so lengthy, but I don't see a way to do it. So let's divide to isolate C.


\begin{displaymath} C = B \frac{y_1 x_2 y_3 - x_1 y_2 y_3}{x_1 y_2 z_3 - y_1 x_2 z_3 + y_1 z_2 x_3 - z_1 y_2 x_3} \end{displaymath} (7.21)

We can also obtain A in terms of B by substituting Equation 7.21 into Equation 7.14:


\begin{displaymath} A = B \frac{y_1 x_2 y_3 - x_1 y_2 y_3}{x_1 y_2 z_3 - y_1 x_2... ...z_1 y_2 x_3} \cdot \frac{y_1 z_2 - z_1 y_2}{x_1 y_2 - y_1 x_2} \end{displaymath} (7.22)

Now we can express B purely in terms of the three known points.


\begin{displaymath} B = \frac{-(B \frac{y_1 x_2 y_3 - x_1 y_2 y_3}{x_1 y_2 z_3 -... ... y_2 z_3 - y_1 x_2 z_3 + y_1 z_2 x_3 - z_1 y_2 x_3}) z_2}{y_2} \end{displaymath} (7.23)

Yuuuuuuck. This is one ugly equation. At least it's what we want (B) in terms of what we have (the three known points, ($x_i$, $y_i$, $z_i$)). We just have to simplify it for run-time efficiency & so we can understand it.


\begin{displaymath} B y_2 = -(B \frac{y_1 x_2 y_3 - x_1 y_2 y_3}{x_1 y_2 z_3 - y... ...3}{x_1 y_2 z_3 - y_1 x_2 z_3 + y_1 z_2 x_3 - z_1 y_2 x_3}) z_2 \end{displaymath} (7.24)


\begin{displaymath} B y_2 = -(B \frac{y_1 {x_2}^2 y_3 - x_1 x_2 y_2 y_3}{x_1 y_2... ...2 y_3}{x_1 y_2 z_3 - y_1 x_2 z_3 + y_1 z_2 x_3 - z_1 y_2 x_3}) \end{displaymath} (7.25)

fixme: I think Equation 7.25 is wrong.


7.4 world2.lisp

This source code is also available at
http://cybertiggyr.com/gene/world/src/world2.lisp. 

;;; -*- Mode: Lisp -*-
;;;
;;; $Header: /home/gene/library/website/docsrc/world/src/RCS/world2.lisp,v 395.1 2008/04/20 17:25:50 gene Exp $
;;;
;;; Copyright (c) 2006 Gene Michael Stover.  All rights reserved.
;;;
;;; This program is free software; you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as
;;; published by the Free Software Foundation; either version 2 of the
;;; License, or (at your option) any later version.
;;;
;;; This program is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;;; GNU General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public
;;; License along with this program; if not, write to the Free Software
;;; Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
;;; USA
;;;

;;;
;;; WORLD 2 is a ....
;;;

(defpackage "COM.CYBERTIGGYR.GENE.WORLD2"
  (:use "COMMON-LISP" "COM.CYBERTIGGYR.GENE.WORLD.MATH")
  (:import-from "CYBERTIGGYR-TEST" "DEFTEST"))
(in-package "COM.CYBERTIGGYR.GENE.WORLD2")

(deftest test0000 ()
  "This test always succeeds."
  'test0000)

(defstruct terrain
  ;; World's width (East-to-West) & breadth (North-to-South)
  ;; in millimeters
  (width 0 :type real)
  (breadth 0 :type real)
  ;; 2-D matrix of elevation samples.
  ;; Here's a default.  You can specify your own 2-D matrix
  ;; with different dimentions.
  (sample (make-array '(1000 1000) :element-type 'real
                      :initial-element 0 :adjustable nil
                      :fill-pointer nil)))

(deftest test0002 ()
  "Verify that MAKE-TERRAIN doesn't crash."
  (make-terrain))

(deftest test0003 ()
  "Verify that a bunch of MAKE-TERRAIN calls don't crash.  This test
is probably pointless.
On Plague (one of my home computers), SBCL requires 60 seconds to
call MAKE-TERRAIN 1,000 times.  "
  (dotimes (i 1000) (assert (make-terrain)))
  'test0003)

;;; --- end of file ---

A. Other File Formats

A.1 Source code archive

All of the source code is available in a single archive file at
http://cybertiggyr.com/gene/world/world.zip.


A.2 nrdl0.c 

/* -*- Mode: C -*-
 *
 * $Header: /home/gene/library/website/docsrc/world/RCS/world.tex,v 395.1 2008/04/20 17:25:50 gene Exp $
 * 
 * Copyright (c) 2006 Gene Michael Stover.  All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL GENE MICHAEL STOVER BE LIABLE FOR
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 * 
 * Except as contained in this notice, the name of Gene Michael Stover
 * shall not be used in advertising or otherwise to promote the sale, use
 * or other dealings in this Software without prior written authorization
 * from Gene Michael Stover.
 */

/* Standard C */
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* This */
typedef int Boolean;
#ifndef FALSE
#define FALSE (0)
#endif
#ifndef TRUE
#define TRUE (!0)
#endif

/*
 */
void *
xmalloc (size_t count)
{
  void *p;

  p = malloc (count);
  if (p == NULL) {
    fprintf (stderr, "\n%s:%d: malloc (%u) failed", __FILE__, __LINE__,
             (unsigned) count);
    abort ();
  }
  return p;
}

/*
 */
static void *
xfree (void *p)
{
  if (p == NULL) {
    fprintf (stderr, "\n%s:%d: Can't free NULL", __FILE__, __LINE__);
    abort ();
  }
  free (p);
  return NULL;
}

/*
 * To use in your own programs, copy-&-paste everything
 * between the "cut here" comment lines.
 */

/* --- cut here --- begin --- cut here --- */
/*
 */
static Boolean
is_good_terminator (FILE *fp, int c, int is_strict, size_t i,
                    size_t max)
{
  return (!is_strict && (c == -1 || c == 0x0A)) ||
    (c == 0x0D && fgetc (fp) == 0x0A);
}

/*
 */
char *
internet_readline (FILE *fp, Boolean is_strict, size_t max)
{
  char *x = NULL;
  int c, i = 0;

  c = fgetc (fp);
  if (c == -1) {
    /*
     * When the input source is already at end-of-file,
     * we return NULL.
     */
    assert (x == NULL);
  } else {
    /*
     * The input is not already empty, so we allocate space &
     * accumulate characters.
     */
    x = (char *) xmalloc (max + 1);
    while (c != -1 && c != 0x0D && c != 0x0A && i < max) {
      x[i++] = c;
      c = fgetc (fp);
    }
    if (is_good_terminator (fp, c, is_strict, i, max)) {
      x[i] = '\0';
    } else {
      /*
       * There was an error, so we ditch the memory we've
       * allocated.  We'll return NULL.
       */
      x = (char *) xfree (x);
    }
  }
  return x;
}
/* --- cut here --- end --- cut here */

/*
 * Null test.  Always succeeds.
 */
static Boolean
S_Test0000 ()
{
  return TRUE;
}

/*
 */
static Boolean
S_BasicTest (Boolean is_strict, size_t max, Boolean is_binary,
             char octets[], size_t octets_len, char *expected[])
{
  Boolean is_good = FALSE;
  char pathname[] = "test.txt";
  FILE *fp;
  size_t i;
  char *line;

  /* Create the input file */
  fp = fopen (pathname, "wb");
  if (fp != NULL) {
    if (octets_len == 0 || fwrite (octets,
                                   octets_len * sizeof octets[0],
                                   1, fp) == 1) {
      is_good = TRUE;
    } else {
      printf ("\n");
      perror ("fwrite");
      printf ("%s:%d:", __FILE__, __LINE__);
      printf (" Did not write the list of %u octets", octets_len);
      printf (" to the temporary file.");
      is_good = FALSE;
    }
    fclose (fp);
  } else {
    printf ("\n");
    perror ("fopen");
    printf ("%s:%d:", __FILE__, __LINE__);
    printf (" Could not create the temorary file, %s.", pathname);
    is_good = FALSE;
  }
  if (is_good) {
    /* Read the input file. */
    fp = fopen (pathname, is_binary ? "rb" : "r");
    if (fp != NULL) {
      i = 0;
      line = internet_readline (fp, is_strict, max);
      while (line != NULL && expected[i] != NULL &&
             strcmp (expected[i], line) == 0) {
        line = (char *) xfree (line);
        ++i;
        line = internet_readline (fp, is_strict, max);
      }
      is_good = expected[i] == NULL && line == NULL;
      if (line != NULL) {
        line = (char *) xfree (line);
      }
      fclose (fp);
    } else {
      printf ("\n");
      perror ("fopen");
      printf ("\n%s:%d:", __FILE__, __LINE__);
      printf (" Could not open %s to read from it.", pathname);
      is_good = FALSE;
    }
  }
  if (is_good) {
    remove (pathname);
  } else {
    /*
     * There was an error, so we don't delete the temporary
     * file.  It might be useful to inspect it later.
     */
  }
  return is_good;
}

/*
 */
#define entry(test) { &test, #test }
static struct {
  int (*fn) ();
  char *name;
} S_a[] = {
  entry (S_Test0000),
  { NULL, NULL }
};
static size_t S_alen = sizeof S_a / sizeof S_a[0];

int
main ()
{
  int rc = 0;
  size_t i;

  for (i = 0; rc == 0 && S_a[i].fn != NULL; ++i) {
    printf ("\n%3d%% %s =>", i * 100 / (S_alen - 1),
            S_a[i].name);
    if ((*S_a[i].fn) ()) {
      printf (" good");
    } else {
      printf (" FAIL");
      rc = 2057;
    }
  }
  printf ("\n");
  return rc == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
}

/* --- end of file --- */

Bibliography

1
Guy W. Lecky-Thompson.
Infinite Game Universe: Level Design, Terrain, and Sound.
Charles Rivert Media, Inc., 2002.
ISBN 1-58450-213-4.

2
Gene Michael Stover.
Virtual world movies.
cybertiggyr.com/gene, September 2006.
http://cybertiggyr.com/gene/movies/.

next_inactive up previous root
Gene Michael Stover 2008-04-20