Notes on Lisp raytracer.

Working on KD-tree.

2011-04-05T02:51:00.000-07:00

Trying to implement KD-tree for the ray tracer, I solve appearing problems with both environment and the language itself.
Anyway, the result can be found any moment on the github.

Currently I am working on KD-tree, on the build-tree function, to be specific. The most difficult part of it seems to be a SAH function (surface area heuristics).

And the next difficult part would be a traverse-kd-tree function, which is implemented, but I am looking for good testing techniques for it: a 3D geometrical data is difficult to visualize either in console or on screen.

Parse-line

2011-01-25T07:47:00.000-08:00

Spent a lot of time trying to simplify and clarify the function parse-line.

Here is the result.

KD-tree

2011-01-19T03:15:00.000-08:00

I spent a lot of time.. er.. well, I wasted a lot of time fighting with Emacs, SBCL, SLIME, quicklisp, lispbuilder-sdl, MacOSX port of lispbuilder-sdl-gfx and other stuff.
Now I am a little bit closer to my goal: skills in Lisp development.

Anyway, I forced my code to work at least on Windows.
Currently it builds a KD-tree of given OBJ-file and displays it in animated manner.

The code is available here.

Don't hesitate to contact me if you wish to run it.
I guess you would need my help.

Timeout

2010-12-05T23:45:00.000-08:00

This blog is not abandoned (as you might have thought).
I'm just a little bit overwhelmed with the amount of the information I got.
Currently I read "On Lisp" by P. Graham and it takes a lot of time.
As soon as I finish it, I will continue with RT.

OBJ file format.

2009-12-29T11:17:00.000-08:00

For this raytracer I chose to import the OBJ file format as the easiest one to parse.
So here is the first draft implementation of the importing of vertex positions.
This simple code is ready to use, the form is: (take-vertexes "test-file.obj")

(defmacro for-each-line (file line body)
  "Takes all liines from the file one by one."
  `(with-open-file (s ,file :direction :input)
                   (let ((r nil) (eof-reached nil))
                     (loop while (not eof-reached) do
                           (multiple-value-setq (,line eof-reached) (read-line s r))
                           (if ,line ,body)))))



(defmacro read-vertex-data (v-line vertexes index &key count-only)
  "Reads three floats from the given line to the vertexes array starting with index.
Index is increased and returned as a result afterwards."
  `(let* ((trimmed-line (string-trim '(#\Space #\Tab #\Newline) ,v-line)))
     (if (and (> (string-size-in-octets trimmed-line) 2)
              (char= #\v (char trimmed-line 0))
              (or (char= #\Space (char trimmed-line 1))
                  (char= #\Tab (char trimmed-line 1))))
         (let* ((trash1 t) (trash2 t)
                (val 0d0)
                (start-from 2)) ; skip "v " in the string

           (progn
             (multiple-value-setq (val start-from) (read-from-string trimmed-line trash1 trash2 :start start-from))
             (if ,vertexes (setf (aref ,vertexes ,index) (coerce val 'double-float)))
             (incf ,index)
             (multiple-value-setq (val start-from) (read-from-string trimmed-line trash1 trash2 :start start-from))
             (if ,vertexes (setf (aref ,vertexes ,index) (coerce val 'double-float)))
             (incf ,index)
             (multiple-value-setq (val start-from) (read-from-string trimmed-line trash1 trash2 :start start-from))
             (if ,vertexes (setf (aref ,vertexes ,index) (coerce val 'double-float)))
             (incf ,index)
             ,index)))))



(defun take-vertexes (file)
  "Takes all found vertexes from the given file to the given array.
Returns the number of the read floats, not vertexes!"
  (let* ((count
          (let ((i 0)) (for-each-line file line (read-vertex-data line nil i)) i)) ; only count, no store

         (temporar-vertexes (make-array count :element-type 'double-float))
         (actually-read-floats 0))
    (for-each-line file line (read-vertex-data line temporar-vertexes actually-read-floats)) ; read+store

    temporar-vertexes))

Random rays.

2009-12-17T06:30:00.000-08:00

Trying to generate random rays, I have got a problem.
Basically I had few ways to get a 'random' vector or in other words a random point on the surface of the unit sphere.

The first way was to generate random points in unit cube discarding points that are out of the unit sphere.
But it can take much time, because of points that are just being generated outside of the sphere and are being discarded just wasting time.
The second way was to get random 'rho' and 'phi' for polar coordinates.
The problem was, I had non-uniform probability of points of the sphere due to 'cylindrical coords. ->spherical coords. transformation' (closer to poles - higher probability).
The third way was to just normalize the random point in the unit cube to the unit sphere.
The problem here was, I had non-uniform probability distribution (it's pretty clear, why).
There is another way to do it, unimplemented though. It is as follows:
"My idea is this: I want to create a tetrahedron, normalize its vertexes, split each face (triangle) with the point in the middle, normalize it and repeat recursively until I have enough points. Then I "distort" these points a little bit if any. Then I normalize them again. That's it."

Finally, I have found more or less easy way to generate random rays without mentioned drawbacks, thanks to David Norman and WolframMathWorld.
It is a method marked with formulas (6), (7) and (8) in the article on the last link. It is pretty close to 'my' first method but is has z calculated not via angle, but directly. It fixes the problem with non-uniformity.

And regarding the 4th described method: I will try to implement it later, I am pretty satisfied with results received from the Stackoverflow.

Renderman.

2009-05-14T05:36:00.000-07:00

It seems that if I want to follow industry standards, I have not too much to choose from. It is either Renderman or Mental, or Blender, or something like Cg or alike. Yes, I know that they are "of different type", but my problem is to choose something distant just to set the direction. I have no preferences, and so after talk with one guy, the Renderman was chosen. Yet I have no idea about reyes and other renderman-specific things, but I will find it out.

Direction.

2009-05-14T04:21:00.000-07:00

I thought a bit about this task and more and more I like the Haskell with its laconism. And more and more I see that LISP is pretty weak here comparing to the Haskell. But on the other hand, as LISP has weakness here, it has a strength somewhere else. And I believe, it is macros. Just because the LISP has nothing special else.

So now my idea is to pay as much attention to macros as possible. I don't want to put them just everywhere, but simply to make the language more laconic.

And one more thing, but not the least. I decided to implement the support of some already available shader language just to be able to use the code already written for this lamguage. I am still deciding which language to chose.

Next, please!

2008-11-22T08:19:00.000-08:00

Ok, I canceled this latest change. But the library is implemented (well, taken...) and can be used any time.
The main reason for cancellation is that I get and absorb the information faster than I implement "the best" idea I have for the moment. And that lazy computation can tie me too much. Anyway, it isn't Haskell. Alas.
So, now the best idea is this:
I design the language like LEGO, i.e. the language that permits to work with blocks of calculations. I imagine it like Houdini net editor or something like that with textual description. Maybe it will be XML.
I haven't decided yet.

Streams.

2008-10-02T02:38:00.000-07:00

Impressed by lectures of Gerald Jay Sussmann and Harold Abelson, I decided to put the streams into the rendering engine to simplify it and to add lazy calculations. I'm too "imperative" and it takes some time and pain to move to functional style.

One may say "First implement it and then play", but I desagree. Features are just a bunch of code which will prevent me from doing any changes. So now is the most correct time.

Self-testing.

2008-09-29T06:51:00.000-07:00

So there is new feature in the renderer available.

It is a testing framework from the "Practical Common Lisp" book. The book is awesome and I recommend it for reading for everyone who did not read it yet.

Anyway, I took the "framework" as it is without changes: it suits well as it is.

So, not too much, but the code is revisited a little bit and, anyway, it is a progress.

One small step is better than nothing...

By the way, on the picture one can see the new "checker" shader: it shows V direction with white and U direction with solid color, putting the round mark at the first vertex in the list.

Path tracing.

2008-08-26T03:19:00.000-07:00

For the main loop I decided to use path tracing as the most simple and more or less acceptable solution. So, now I'm working on it.
The bidirectional path tracing appeared to be not so easy to implement. I just could not find enough description and formulas for it. Anyway, I can implement it later, it's not so important for now.
So I'm working on the basic path tracing.

SBCL, CLISP, CMUCL.

2008-08-19T05:22:00.000-07:00

I spend already two or three days trying to run EMACS+SLIME+SBCL under my WinXP and Vista Home.
So eventually I found that I use AMD Athlon64 processor. That means for example that SBCL 1.0.19 doesn't work but SBCL 1.0.13 does. So I switched to SBCL 1.0.13.
I also use "Ubuntu+CMUCL+EMACS+SLIME" for this task (under virtual machine).

Simplification.

2008-08-17T23:26:00.000-07:00

So I added packages into the project.
And this feature added one unexpected problem: the code seems to be slower. Much slower. Even after compilation. Anyway, the optimization will be done a little bit later.

Books about raytracing.

2008-08-06T02:09:00.000-07:00

So, I've got two new books:

3d computer graphics. a mathematical introduction with opengl.
realistic image synthesis using photon mapping.

thanks to http://www.pdfchm.com/

Anyway, the information I searched for is available in these books: general ray tracing. And the second book looks interesting: I was always interested in global illumination methods at all and particular in photon mapping.

The first draft render.

2008-08-04T05:54:00.000-07:00

So, here is the first test result.

The rendered data is:

(list
(make-t3d :v0 (make-v3d :x -3 :y 2 :z 0)
:v1 (make-v3d :x -4 :y 2 :z 2)
:v2 (make-v3d :x 1 :y 6 :z 0)
:color '"255 100 0")

(make-t3d :v0 (make-v3d :x -3 :y 4 :z 0)
:v1 (make-v3d :x 4 :y 4 :z -5)
:v2 (make-v3d :x 4 :y 4 :z 5)
:color '"0 255 0")
)

Cameras are:
(list
(make-c3d :from (make-v3d :x 0 :y -3 :z 0)
:to (make-v3d :x 0 :y 0 :z 0)
:up (make-v3d :x 0 :y 0 :z 1)
:d 5
:w-px 320
:h-px 256
:w-m 10
:h-m 8)
)

Lights were not used.

Ok. Let's begin.

2008-07-30T06:51:00.000-07:00

So I decided to write a raytracer engine using LISP.
The "first step" is available.
It does nothing except for one important thing: being the first step, it empowers me to continue work on it.

     1: ; version 0.1
     2: ; Features:
     3: ;   main render loop.
     4: ;   results' display function.
     5: 
     6: ; All physical sizes will be called "meters".
     7: ; They correspont to units from the scene.
     8: 
     9: ; ---------------------------------------------------
    10: ; Stubs.
    11: (defun init-screen (camera the-format) "Stub.")
    12: (defun update-screen (screen x y pixel) "Stub.")
    13: (defun store-to-file (screen name the-format) "Stub.")
    14: ; ---------------------------------------------------
    15: 
    16: (defvar *SMALL-NUM* 0.0001)
    17: 
    18: 
    19: ; Vectors 
    20: 
    21: (defstruct V3D "Vector. Just x y z." x y z)
    22: 
    23: (defun V3D- (A B) "Difference between two 3D vectors."
    24:        (make-V3D :x (- (V3D-x A) (V3D-x B))
    25:          :y (- (V3D-y A) (V3D-y B))
    26:          :z (- (V3D-z A) (V3D-z B))))
    27: 
    28: (defun V3D+2or1 (A B) "Sum of 3D vectors."
    29:        (if (null a)
    30:        (make-v3d :x 0 :y 0 :z 0)
    31:        (if (null b) A
    32:            (make-v3d :x (+ (V3D-x A) (V3D-x  b))
    33:              :y (+ (V3D-y A) (V3D-y  b))
    34:              :z (+ (V3D-z A) (V3D-z  b))))))
    35:       
    36: (defun v3d+ (&rest args) (reduce #'v3d+2or1 args))
    37: 
    38: (defun V3D^ (A B)
    39:   "Cross product of vectors in 3D."
    40:   (make-V3D :x (- (* (V3D-y A) (V3D-z B)) (* (V3D-z A) (V3D-y B)))
    41:         :y (- (* (V3D-z A) (V3D-x B)) (* (V3D-x A) (V3D-z B)))
    42:         :z (- (* (V3D-x A) (V3D-y B)) (* (V3D-y A) (V3D-x B)))))
    43: 
    44: (defun V3D* (A B)
    45:   "Dot product of two vectors in 3D."
    46:   (+ (* (V3D-x A) (V3D-x B))
    47:      (* (V3D-y A) (V3D-y B))
    48:      (* (V3D-z A) (V3D-z B))))
    49: 
    50: (defun V3D-NULL-P (a)
    51:   "Checks if the vector is zero length."
    52:   (and (eql (v3d-x a) 0)
    53:        (eql (v3d-y a) 0)
    54:        (eql (v3d-z a) 0)))
    55: 
    56: (defun V3D-NORMA (A)
    57:   "Returns normalized A."
    58:   (let ((l (sqrt (+ (* (v3d-x a) (v3d-x a))
    59:             (* (v3d-y a) (v3d-y a))
    60:             (* (v3d-z a) (v3d-z a))))))
    61:     (if (v3d-null-p a)
    62:     nil ; cannot normalize empty vector
    63:     (make-v3d :x (/ (v3d-x a) l)
    64:           :y (/ (v3d-y a) l)
    65:           :z (/ (v3d-z a) l)))))
    66: 
    67: (defun V3D-SCALE (A S) ; A is vector, S is scalar
    68:   "Scaling."
    69:   (make-v3d :x (* (v3d-x A) S)
    70:         :y (* (v3d-y A) S)
    71:         :z (* (v3d-z A) S)))
    72: 
    73: (defun v3d-length (a b)
    74:   "The length of the vector."
    75:   (let ((dx (- (v3d-x a) (v3d-x b)))
    76:     (dy (- (v3d-y a) (v3d-y b)))
    77:     (dz (- (v3d-z a) (v3d-z b))))
    78:     (sqrt (+ (* dx dx) (* dy dy) (* dz dz)))))
    79: 
    80: ;
    81: ; Useful structures.
    82: (defstruct T3D "Triangle. Just 3 vertices."
    83:        v0 v1 v2 ; positions
    84:        color) ; temporar, for testing
    85: (defstruct R3D "Ray. Just 2 vectors." p0 p1)
    86: (defstruct C3D "Camera."
    87:        from to up ; vectors. up is correct and normalized
    88:        d w-px h-px w-m h-m) ; px=pixels m=meters d=distance to screen
    89: (defstruct W3D "World." light geometry cameras)
    90: (defstruct PIXEL3D position color depth)
    91: ;
    92: 
    93: (defun start-new-line () "Stub." (format t "~%"))
    94: 
    95: (defun show-pixel (x y pixel)
    96:   "Stub."
    97:   (if (null pixel)
    98:       (format t "0 0 0 ")
    99:       (format t "~a " (pixel3d-color pixel))))
   100: 
   101: (defun load-world (&key light-filename geometry-filename cameras-filename)
   102:   (make-w3d :light    (eval (with-open-file (in light-filename)
   103:                   (with-standard-io-syntax (read in))))
   104:         :geometry (eval (with-open-file (in geometry-filename)
   105:                   (with-standard-io-syntax (read in))))
   106:         :cameras  (eval (with-open-file (in cameras-filename)
   107:                   (with-standard-io-syntax (read in))))))
   108: 
   109: (defun emit-ray (camera x y)
   110:   "Emits one ray using given camera."
   111:   (let* ((w (/ (c3d-w-m camera)
   112:            (c3d-w-px camera)))   ; physical pixel width
   113:      (h (/ (c3d-h-m camera)
   114:            (c3d-h-px camera))) ; physical pixel height
   115:      (f (v3d-scale (v3d-norma (v3d- (c3d-to camera) (c3d-from camera)))
   116:                (c3d-d camera))) ; front
   117:      (r (v3d-norma (v3d^ f (c3d-up camera)))) ; right
   118:      (r-ph (v3d-scale r w)) ; physical right step (pixel size)
   119:      (u-ph (v3d-scale (c3d-up camera) h))
   120:      (to (v3d+ (c3d-from camera)    ; ->eye
   121:            f                    ; eye->center
   122:            (v3d-scale r-ph (+ (/ (- 1 (c3d-w-px camera)) 2) x)) ; -(w-1)/2+x * r-ph. center->left
   123:            (v3d-scale u-ph (- (/ (- (c3d-h-px camera) 1) 2) y))))) ; left->lefttop
   124:     (make-r3d :p0 (c3d-from camera) :p1 to)))
   125: 
   126: (defun render (&key world camera
   127:            (file-format 'RAW-RGBA) (name nil)
   128:            (new-line-hook nil) (display-pixel-hook nil))
   129:   "Renders the \"world\" on \"screen\"."
   130:   (let ((screen (init-screen camera file-format)))
   131:     (dotimes (y (c3d-h-px camera))
   132:       (when new-line-hook (funcall new-line-hook)) ; newline jump
   133:       (dotimes (x (c3d-w-px camera))
   134:     ; actual rendering is done here
   135:     (let ((pixel (render-pixel world (emit-ray camera x y))))
   136:       (when display-pixel-hook (funcall display-pixel-hook x y pixel))
   137:       (update-screen screen x y pixel)  ; here the rendered pixel is stored
   138:       ; TODO: add the interrupt ability here.
   139:       (when name (store-to-file screen name file-format)))))))
   140: 
   141: (defun render-test ()
   142:   (let* ((w (load-world :light-filename "H:/raytrace/lights.data"
   143:             :geometry-filename "h:/raytrace/geometry.data"
   144:             :cameras-filename "h:/raytrace/cameras.data"))
   145:      (c (first (w3d-cameras w))))
   146:     (render :world w :camera c
   147:         :new-line-hook 'start-new-line
   148:         :display-pixel-hook 'show-pixel)))
   149: 
   150: (defun intersect-ray-triangle (ray tri)
   151:   "Intersects ray with given triangle and returns T if intersected.
   152: After the resulting color data is returned. If not intersected,
   153: then NIL is returned."
   154:   ; get triangle edge vectors and plane normal
   155:   (block nil
   156:     (let* ((u (v3d- (t3d-v1 tri) (t3d-v0 tri)))
   157:        (v (v3d- (t3d-v2 tri) (t3d-v0 tri)))
   158:        (n (v3d^ u v))) ; cross product
   159:       (if (v3d-null-p n)
   160:       nil ; triangle is degenerate
   161:       (let* ((dir (v3d- (r3d-p1 ray) (r3d-p0 ray))) ; ray direction vector
   162:          (w0  (v3d- (r3d-p0 ray) (t3d-v0 tri))) ; w0 = R.P0 - T.V0
   163:          (a   (- (v3d* n w0))) ; a = -dot(n,w0)
   164:          (b   (v3d* n dir)))   ; b = dot(n,dir)
   165:         (if (< (abs b) *SMALL-NUM*)
   166:         nil ; ray is parallel to the triangle plane
   167:         (let ((r (/ a b))) ; get intersect point of ray with plane
   168:           (if (< r 0) ; ray goes away from triangle
   169:               nil ; no intersect
   170:               ; intersect point of ray and plane
   171:               (let* ((i (v3d+ (r3d-p0 ray)
   172:                       (make-v3d :x (* r (v3d-x dir))
   173:                         :y (* r (v3d-y dir))
   174:                         :z (* r (v3d-z dir)))))
   175:                  (uu (v3d* u u))
   176:                  (uv (v3d* u v))
   177:                  (vv (v3d* v v))
   178:                  (w  (v3d- i (t3d-v0 tri)))
   179:                  (wu (v3d* w u))
   180:                  (wv (v3d* w v))
   181:                  (d  (- (* uv uv) (* uu vv)))
   182:                  (s  (/ (- (* uv wv) (* vv wu)) d)))
   183:             (if (or  (< s 0) (> s 1))
   184:                 nil ; point is outside of the triangle
   185:                 (let ((tt (/ (- (* uv wu) (* uu wv)) d)))
   186:                   (if (or (< tt 0) (> (+ s tt) 1))
   187:                   ; point is outside:
   188:                   nil
   189:                   ; point is inside:
   190:                   (return
   191:                     (make-pixel3d
   192:                      :position i
   193:                      :color (t3d-color tri)
   194:                      :depth (v3d-length i (r3d-p0 ray))))))))))))))))
   195: 
   196: (defun compare2pixels (a b) ; takes two pixels
   197:   (if (null a)
   198:       b
   199:       (if (null b)
   200:       a
   201:       (if (< (pixel3d-depth a) (pixel3d-depth b))
   202:           a
   203:           b))))
   204: 
   205: (defun compare-pixels (&rest args)
   206:   (reduce #'compare2pixels args)) 
   207: 
   208: (defun render-pixel (world ray)
   209:   (reduce #'compare-pixels
   210:       (mapcar #'(lambda (tri)
   211:               (intersect-ray-triangle ray tri))
   212:           (w3d-geometry world))))