How to compute Ray-Simplex-4d intersection in 4D?

If you don't know where to post something, put it here and an administrator or moderator will move it to the right place.

How to compute Ray-Simplex-4d intersection in 4D?

Postby MorgothV8 » Mon Feb 23, 2009 1:01 pm

Hi, I have one problem and maybe one of You can help me...
Here it is:
I have long ago written quite good raytracer (in 3D space), I/m rewriting it im my spare time into 4D

What have been rewriten:
triangle (ABC) became simplex4D (ABCD)
Localise tree (octtree became sixteen-tree with recursive voxel processing and minimalisation)
Normal compute (cross product of three simplex "edge-vectors" spanned from A)
All rendering stuff, 3D-retina, lod scene, save scene, 6 rotations (XY, XZ, XV, YZ, YV, ZV), all preprocessing
Now wandering how to coompute intersection (ray, simplex)
on 3D it was just ray (x0,y0,z0, dx,dy,dz) intersection with triangle surface ABCD and then checking if intersection was inside triangle - thats all
In 4D looks much more complex.
First try is to get hyper-surface containing simplex (ABCDE), (A,B,C,D are from normal vector, E is distance to (0,0,0,0) as in 3D)
then intersect this surface with ray (x0,y0,z0,v0,dx,dy,dz,dv) - this can be computed I thing (solve linear system)
But how to check if intersection point is within simpex4D?

Second problem.
In 3D my triagle has 3 normals on each vertex (pseud-curvilinear triangel), when intersection was computed, then I had to interpolate normal from NA, NB, NC
This was:
Intersection point is P
Fire line from A to P, it will intersect BC in point D
Interpolate normal from NB and NC using linear interpolation between B and C on point P, then normalize result and call it ND
Then interpolate normal from A and D on point P, normalize it and then I have smooth triangle Phong interpolation...

Think in 4D....
Guessing?
Hav intersection point with simplex: P
Fire from A onto 2D-surface BCD, compute (how) intersection -> becomes Q
With BCD and Q we have already algorithm (as in 3D) using B firing onto CD and having point S
Now C-----S--D interpolation (linear) gives NS, normalize
Now B--Q----S -> gives NQ, normalize
Now A---P---Q -> gives P, then normalize, thus having 3-linear (smooth?) interpolations:

Problems:
1. How to compute P? (ray-simplex intersection)
2. How to determine P is within simplex ABCD
3. How to compute first stage of 3-linear interpolation. fire A-->P -->Q (how to compute Q)?

Thanks :D
MorgothV8
Mononian
 
Posts: 8
Joined: Fri Feb 20, 2009 1:57 pm

Re: How to compute Ray-Simplex-4d intersection in 4D?

Postby pat » Mon Mar 09, 2009 10:35 pm

So... in your 3D raytracer you had triangles (which are 2D). Now, in the 4D version, you're using tetrahedrons (which are 3D). So, actually, you have 3D simplexes in 4D space.

Anyhow... you say you can already compute a normal given three edge vectors. So... calculate n as the normal of the three edges B-A, C-A, and D-A. Now, assuming your ray is x + d t for vectors x and d with scalar t, then your ray intersects the hyperplane containing your facet for the value of t so that ( x + d t ) . n = A . n, so... t = (A.n - x.n) / (d.n) .... assuming d.n is non-zero.

So, p = x + d ( A.n - x.n ) / (d.n).

From there, you then have to see if that point is inside the tetrahedron ABCD. A brute-force way would be to create a rotation matrix that takes the vector n to the vector (0,0,0,1). Then, take the matrix with columns (B-A)T, (C-A)T, and (D-A)T, rotate it with the just-calculated rotation matrix. It should then effectively be a 3x3 matrix. Invert that matrix, multiply (p-A)T by that. Now, check to make sure all components are greater-than-or-equal-to zero and less-than-or-equal-to one.

There may be some better ways... but most of this stuff can be precalculated.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN

Re: How to compute Ray-Simplex-4d intersection in 4D?

Postby MorgothV8 » Tue Mar 10, 2009 7:42 am

Anyhow... you say you can already compute a normal given three edge vectors. So... calculate n as the normal of the three edges B-A, C-A, and D-A. Now, assuming your ray is x + d t for vectors x and d with scalar t, then your ray intersects the hyperplane containing your facet for the value of t so that ( x + d t ) . n = A . n, so... t = (A.n - x.n) / (d.n) .... assuming d.n is non-zero.


My tetrahedron can is "curvilinear" so at A, B, C, D it has different normals (just like in 3D triangle has 3 different normals), but of course it also has its hyperplane-normal, so we have 5 different normals: nA, nB, nC, nD and real "mathematical" normal "n". my ray has start point "x" and direction "d" so all You written is clear, "n" can by computed as "cross product of three vectors", this have been already done

So, p = x + d ( A.n - x.n ) / (d.n).

So I have already intersection with hyperplane, it will almost always exist, only "hyperparallel" ray can be within hyperplae (so we have infinite number of intersections) or out of hyperplane (0 intersections). But now comes the worst...

From there, you then have to see if that point is inside the tetrahedron ABCD. A brute-force way would be to create a rotation matrix that takes the vector n to the vector (0,0,0,1). Then, take the matrix with columns (B-A)T, (C-A)T, and (D-A)T, rotate it with the just-calculated rotation matrix. It should then effectively be a 3x3 matrix. Invert that matrix, multiply (p-A)T by that. Now, check to make sure all components are greater-than-or-equal-to zero and less-than-or-equal-to one.


I don't know how to compute this "rotation matrix" which rotates "n" into (0,0,0,1).
Assuming I just have this matrix, let it be R(4x4), But matrix: M = (B-A)T, (C-A)T, (D-A)T is (4x3), so: R x M would be: (4x3), what to do, take its upper 3x3 part?
Let it be P, so P-1 (if it exists?) --> (p-A)T * P-1 --> v, each component in [0,1]. Om quite clear.
But can You tell me how to compute this R, which part of R x M to get?
Some more information.....
And what are the alternatives to "check if point is within" tetrahedron

And if you can can you tell me how to compute intersection:
ray/line with triangle (in 4D)
I have tetrahedron ABCD, and computed it intersection with the ray on "P"
Now I need to cast this "P" from A into triangle BCD, simple ray from A through "P" into BCD triangle, and get intersection: "Q"
Now the same: ray from B through "Q" into CD giving point "R"
Now using "R" interpolate normals from nC and nD linear at "Q" giving after normalisation nQ
After that interpolate normals nQ and nB giving nR
After that interpolate normals nR and nA giving nP
Finally nP is interpolated from tetrahedron's normalns nA, nB, nC, nD.
It worked simillary in 3D with triangle ABC and gave smooth Phong on triangulated sphere, NURBS etc. using triagles just with one normal (mathematical) gave bad results, and all triangles were visible. If it worked fine in 3D (with tri-interpolation) I assume this would work in 4D with quad-interpolation....

THANKS for Your help!!
MorgothV8
Mononian
 
Posts: 8
Joined: Fri Feb 20, 2009 1:57 pm

Re: How to compute Ray-Simplex-4d intersection in 4D?

Postby pat » Mon Mar 23, 2009 11:25 pm

I think the following is right....

In general, a rotation matrix that takes the unit vector a to the unit vector b looks like this... The i'th column is:
e_i + ( (c - 1) * a_i - s * b_i ) a + ( s * a_i + ( c - 1 ) * b_i ) b

Where c = a . b, and s = sqrt( 1 - c^2 ) and e_i is a vector with 1 in the i-th spot and zeros elsewhere and a_i and b_i are the i-th components of a and b, respectively.

For this, you'll be using n as a and [ 0, 0, 0, 1 ]T as b. That simplifies things lots because the b_i are mostly zero.

So, if you take the first three rows of the first four columns (i = 1, 2, 3, 4), then you'll have a matrix that when you multiply a point by it, will turn it into 3-D coordinates within the relevant hyperplane. Then, you still need to make sure the point is inside the tetrahedron. That means it's below each face of the tetrahedron. So rotate P, A, B, C, and D, check to be sure P is on the same side of the plane ABC as D is, the same side of the pane ABD as C is, etc...

Maybe better would be when preparing the facet, calculate the hyperplane normal and the above rotation matrix. Then, calculate the face-normals of the rotated faces ABC, ABD, ACD, BCD... then anti-rotate those normals back up to four-space. Then, you can just find P and make sure that it is on the same side of ABC that D is, the same side of ABD as C is, etc.
pat
Tetronian
 
Posts: 563
Joined: Tue Dec 02, 2003 5:30 pm
Location: Minneapolis, MN


Return to Where Should I Post This?

Who is online

Users browsing this forum: No registered users and 6 guests

cron