I was implementing a cylinder primitive to my little pet project, a
raytracer, when I run into some problems.

The cylinder is defined the same way as in POV, by two vectors and a float,
representing the base and apex points and the radius, respectively. Writing
an intersection finder and other needed stuff for such a general case would
be rather difficult, so I reasoned that it would be easiest (and perhaps
most efficient, too?) to make the cylinder always lie along a coordinate
axis (say, the Y axis) in object space, and then provide an appropriate
transformation from object space to world space.

The problem is, how would I go about constructing such a transformation? I
took a look at the relevant part of the POV source code, but didn't quite
figure out how it does the trick. I could of course just grab the code, but
I'd rather understand the algorithm behind it.

I'd also like some insight into how to invert a transformation (4x4) matrix.
I did a bit googling but didn't come by anything too relevant.

Thanks in advance,

-Johannes

Post a reply to this message

Cool... hope someone answers this, cos I wanna know too!

(I can't read C... It's one of the few languages I can't understand... I
know Java (!!), Smalltalk, Eiffel, Pascal, BASIC, naturally POV-Ray SDL,
SQL, HTML, LaTeX, XSLT (!!!!), various scripting languages, automake,
MatLab, 6502 assembly and even machine code... and yet I can't follow C,
Perl or VB. Go figure.)

Thanks.
Andrew.

Post a reply to this message

The inverse of a matrix is always the array which
multiplied with the original array results in an
array with 1 on the upper-left to lower-right diagonal.

Here's a (german) link I found while searching for my
math examn:

http://miss.wu-wien.ac.at/~leydold/MOK/HTML/node31.html

Basically, what you do is write the uniform matrix aside the
original one:

original | uniform

1 2 5 | 1 0 0
4 6 7 | 0 1 0
8 3 5 | 0 0 1

And then solve the rows and trying to get
1 0 0
0 1 0
0 0 1
at the left side. The right side would then be the inverse
matrix.

Creating an algorithm which tries to solve the left side to get
the uniform matrix shouldn't be too difficult, but I espect that
there is some better method for that.

About how to go along with this on your raytracer: don't know.
But I thought perhaps the inverse-matrix thingy could help...

Regards,
Tim

--
Tim Nikias v2.0
Homepage: http://www.digitaltwilight.de/no_lights
Email: Tim### [at] gmxde

> I was implementing a cylinder primitive to my little pet project, a
> raytracer, when I run into some problems.
>
> The cylinder is defined the same way as in POV, by two vectors and a
float,
> representing the base and apex points and the radius, respectively.
Writing
> an intersection finder and other needed stuff for such a general case
would
> be rather difficult, so I reasoned that it would be easiest (and perhaps
> most efficient, too?) to make the cylinder always lie along a coordinate
> axis (say, the Y axis) in object space, and then provide an appropriate
> transformation from object space to world space.
>
> The problem is, how would I go about constructing such a transformation? I
> took a look at the relevant part of the POV source code, but didn't quite
> figure out how it does the trick. I could of course just grab the code,
but
> I'd rather understand the algorithm behind it.
>
> I'd also like some insight into how to invert a transformation (4x4)
matrix.
> I did a bit googling but didn't come by anything too relevant.
>
> Thanks in advance,
>
> -Johannes
>
>
>

Post a reply to this message

You might find an answer or two by looking at my Transformation JavaScript
object used in the JavaScript Raytracer at
http://www.slimeland.com/jsinclude/transformation.js . The code is a little
more complicated than it needs to be, but it does the trick.

You might also benefit from looking at the cylinder intersection code at
http://www.slimeland.com/raytrace/objects/cylinder.js .

I wrote all of this code myself, without any references, so it's possible
that I overcomplicated some things.

 - Slime
[ http://www.slimeland.com/ ]

Post a reply to this message

Johannes Dahlstrom wrote:

> I was implementing a cylinder primitive to my little pet project, a
> raytracer, when I run into some problems.
> 
> The cylinder is defined the same way as in POV, by two vectors and a
> float, representing the base and apex points and the radius, respectively.
> Writing an intersection finder and other needed stuff for such a general
> case would be rather difficult, so I reasoned that it would be easiest
> (and perhaps most efficient, too?) to make the cylinder always lie along a
> coordinate axis (say, the Y axis) in object space, and then provide an
> appropriate transformation from object space to world space.
> 
> The problem is, how would I go about constructing such a transformation? I
> took a look at the relevant part of the POV source code, but didn't quite
> figure out how it does the trick. I could of course just grab the code,
> but I'd rather understand the algorithm behind it.

I exactly have implemented this for my ray-tracer recently. My base cylinder 
is z-axe aligned radius 1, length 1. To allow arbitrary cylinders from base 
and cap points you need to implement an axis-rotate (vaxis_rotate in pov I 
think). You can do this from:

    // R(phi,N) = cos(phi)*I + (1-cos(phi))*N^T*N + sin(phi) * A
    // with phi: angle; N: axis; A = [[0 N3 -N2] [-N3 0 N1] [N2 -N1 0]]

Where R(phi,N) is the rotation matrix, N is the axe to rotate around. You 
can see this implemented in c++ in 
http://www.povworld.org/raytracer/cvsweb.cgi/~checkout~/raytracer/raytracer/transformatable.cpp?rev=1.9&content-type=text/plain

Then for the rotation matrix for your cylinder rotate around the axe which 
stands orthogonal on the base-cylinder-axe and the to-cylinder-axe by the 
necessary angle. Again you can see this in c++ in
http://www.povworld.org/raytracer/cvsweb.cgi/~checkout~/raytracer/raytracer/cylinder.cpp?rev=1.5&content-type=text/plain

> 
> I'd also like some insight into how to invert a transformation (4x4)
> matrix. I did a bit googling but didn't come by anything too relevant.
> 

Basically there is the Gauss-algorithm for inverting matrixes. But when you 
have fixed size you probably want to hardcode it. I use 3x3 matrixes in my 
ray-tracer so this time the code won't be usable for you. (matrix.cpp would 
be the file if you're intersted)

At
http://www.povworld.org/raytracer/cvsweb.cgi/raytracer/raytracer/
you can browse the whole CVS version of my ray-tracer.

- Micha

-- 
POV-Ray Objects Collection: http://objects.povworld.org

Post a reply to this message

"Johannes Dahlstrom" <sad### [at] tkukoulufi> wrote in
news:web.3e89ee318267de92f7cbce3c0@news.povray.org: 

...
> I'd also like some insight into how to invert a transformation (4x4)
> matrix. I did a bit googling but didn't come by anything too relevant.

Below is some code that will do this for you.

A good phrase for searching texts about inversion
of matrices will be:

elementary linear algebra


Tor Olav


// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
// How to invert 3x3 and 4x4 matrices with POV SDL.
// By Tor Olav Kristensen

#macro printMatrix(MM)

  #local DimR = dimension_size(MM, 1);
  #local DimC = dimension_size(MM, 2);
  #debug concat("array[", str(DimR, 0, 0), "]")
  #debug concat("[", str(DimC,0, 0), "] {\n")
  #local CntR = 0;
  #while (CntR < DimR)
    #debug " { "
    #local CntC = 0;
    #while (CntC < DimC)
      #debug str(MM[CntR][CntC], 0, -1)
      #if (CntC < DimC - 1)
        #debug ", "
      #end // if
      #local CntC = CntC + 1;
    #end // while
    #debug " }"
    #if (CntR < DimR - 1)
      #debug ","
    #end // if
    #debug "\n"
    #local CntR = CntR + 1;
  #end // while
  #debug "}\n"

#end // macro printMatrix


#macro det3D(v0, v1, v2)

  vdot(v0, vcross(v1, v2))

#end // macro det3D


#macro invertMatrix33(MM)

  #local vX = <MM[0][0], MM[0][1], MM[0][2]>;
  #local vY = <MM[1][0], MM[1][1], MM[1][2]>;
  #local vZ = <MM[2][0], MM[2][1], MM[2][2]>;
  #local Det = det3D(vX, vY, vZ);
  #local v0 =  vcross(vY, vZ)/Det;
  #local v1 = -vcross(vX, vZ)/Det;
  #local v2 =  vcross(vX, vY, vT)/Det;

  array[3][3] {
    { v0.x, v1.x, v2.x }
    { v0.y, v1.y, v2.y }
    { v0.z, v1.z, v2.z }
  }

#end // macro invertMatrix33


#macro vdot4D(vA, vB)

  (vA.x*vB.x + vA.y*vB.y + vA.z*vB.z + vA.t*vB.t)

#end // macro vdot4D


#macro vcross4D(vA, vB, vC)

  #local v00 = <vA.y, vA.z, vA.t>;
  #local v01 = <vB.y, vB.z, vB.t>;
  #local v02 = <vC.y, vC.z, vC.t>;

  #local v10 = <vA.x, vA.z, vA.t>;
  #local v11 = <vB.x, vB.z, vB.t>;
  #local v12 = <vC.x, vC.z, vC.t>;

  #local v20 = <vA.x, vA.y, vA.t>;
  #local v21 = <vB.x, vB.y, vB.t>;
  #local v22 = <vC.x, vC.y, vC.t>;

  #local v30 = <vA.x, vA.y, vA.z>;
  #local v31 = <vB.x, vB.y, vB.z>;
  #local v32 = <vC.x, vC.y, vC.z>;

  <
    det3D(v00, v01, v02),
   -det3D(v10, v11, v12),
    det3D(v20, v21, v22),
   -det3D(v30, v31, v32)
 >

#end // macro vcross4D


#macro det4D(v0, v1, v2, v3)

  vdot4D(v0, vcross4D(v1, v2, v3))

#end // macro det4D


#macro invertMatrix44(MM)

  #local vX = <MM[0][0], MM[0][1], MM[0][2], MM[0][3]>;
  #local vY = <MM[1][0], MM[1][1], MM[1][2], MM[1][3]>;
  #local vZ = <MM[2][0], MM[2][1], MM[2][2], MM[2][3]>;
  #local vT = <MM[3][0], MM[3][1], MM[3][2], MM[3][3]>;
  #local Det = det4D(vX, vY, vZ, vT);
  #local v0 =  vcross4D(vY, vZ, vT)/Det;
  #local v1 = -vcross4D(vX, vZ, vT)/Det;
  #local v2 =  vcross4D(vX, vY, vT)/Det;
  #local v3 = -vcross4D(vX, vY, vZ)/Det;

  array[4][4] {
    { v0.x, v1.x, v2.x, v3.x }
    { v0.y, v1.y, v2.y, v3.y }
    { v0.z, v1.z, v2.z, v3.z }
    { v0.t, v1.t, v2.t, v3.t }
  }

#end // macro invertMatrix44

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7
//Examples:

#declare M33 =
  array[3][3] {
    {  1,  3, -2 },
    { -7,  2,  6 },
    {  2, -1,  2 }
  }

printMatrix(M33)
printMatrix(invertMatrix33(M33))

#declare M44 =
  array[4][4] {
    {  1,  3, -2,  4 },
    { -7,  2,  6,  5 },
    {  2, -1,  2, -3 },
    { -3, -6,  4,  5 }
  }

printMatrix(M44)
printMatrix(invertMatrix44(M44))

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

Post a reply to this message

Thanks guys, greatly appreciated. I think I'll make it from here.

-Johannes

Post a reply to this message

Tor Olav Kristensen <tor_olav_kCURLYAhotmail.com> wrote in 
news:Xns### [at] 204213191226:

...
> #macro invertMatrix33(MM)
> 
>   #local vX = <MM[0][0], MM[0][1], MM[0][2]>;
>   #local vY = <MM[1][0], MM[1][1], MM[1][2]>;
>   #local vZ = <MM[2][0], MM[2][1], MM[2][2]>;
>   #local Det = det3D(vX, vY, vZ);
>   #local v0 =  vcross(vY, vZ)/Det;
>   #local v1 = -vcross(vX, vZ)/Det;
>   #local v2 =  vcross(vX, vY, vT)/Det;
> 
>   array[3][3] {
>     { v0.x, v1.x, v2.x }
>     { v0.y, v1.y, v2.y }
>     { v0.z, v1.z, v2.z }
>   }
> 
> #end // macro invertMatrix33
...

It seems that my last minute corrections
to this macro did not make into my post.

Here's the correct line for v2:

  #local v2 =  vcross(vX, vY)/Det;


Sorry about that.


Tor Olav

Post a reply to this message