Michael Iv : Ray to Triangle intersection test-Right way

[Michael Iv]

So here it is guys ,after several hours the last night and some more like these a few couples of months ago i finaly manages to write a correct code to perform Ray-Triangle intersection test using ray.getIntersect() ,method.I think it is pointless to explain why you would wish to perform such kind of test ( especially for those who develop FPS games) .So here is how this should be done(for any question on implementation you van ask me):

private function RayFaceTest():Vector3D{
            var intersectVector:Vector3D;
            var ray:Ray=new Ray();

            for(var i:int=0;i<_objB.faces.length;++i){
                var p0:Vector3D=_objB.sceneTransform.transformVector(_objB.faces[i].vertices[0].position);
                var p1:Vector3D=_objB.sceneTransform.transformVector(_objB.faces[i].vertices[1].position);
                var p2:Vector3D=_objB.sceneTransform.transformVector(_objB.faces[i].vertices[2].position);

                ray.orig=_objA.position;
                var dd:Vector3D=new Vector3D(0,400,0);
                var dird:Vector3D=_objA.transform.transformVector(dd);
               
                ray.dir=dird;
                rayDebug(ray.orig,ray.dir);
                intersectVector=ray.getIntersect(ray.orig,ray.dir,p0,p1,p2);
           
               if(intersectVector){
                   break;
               }
     
            }
      
            return intersectVector;
        }

Explanation:
_objA and _objB are two spheres which have the same Z  position. _objA is movable by keyboard input.We draw a ray from the center of sphere _objA in the direction of its local Y with the arbitrary length ( I set to 400).So basically when you rotate _objA around Z the ray direction transforms according to local _objA Y direction.We test the ray hits against the triangles of _objB sphere. Notice that right after for loop start we convert each face 3 vertices coords from obj local space into scene spaceNot doing so you will never get intersection(actually this was my pitfall ).Then we cast the ray passing into getIntersect() ray origin,ray direction vectors ,and 3 vertex vectors for the currently tested triangle.
If the intersection occurs intersectVector returns the coords of the hit otherwise it is null.If it is not null we break fro the loop in order to return the hit to the function and start the iteration again.This is it .I hope it was usefull . :))

--
Michael Ivanov ,Programmer
Neurotech Solutions Ltd.
Flex|Air |3D|Unity|
www.neurotechresearch.com
http://blog.alladvanced.net
http://www.meetup.com/GO3D-Games-Opensource-3D/
Tel:054-4962254
explo...@gmail.com
te...@neurotech.co.il

[Aji Pamungkas]

Thanks, Michael. :)

--
Aji Pamungkas

[John Brookes]

Nice.
So whats the UV position of the hit ;)

[Michael Iv]

You should transform these coords to barycentric . I am too stuffed to write a showcase on this.But there is a lot of materia on this in the web.Also Ask Fabrice he told once he is a barycentric GURU :))

But it seems to me that transform material should contain such an example as it projects texture based on vector.

On Tue, Nov 23, 2010 at 2:19 PM, John Brookes <jbp...@googlemail.com> wrote:

Nice.
So whats the UV position of the hit ;)

[John Brookes]

Ahh so thats what Barycentric class does.

Basically
var vtx0:Vertex = VectortoVertex(p0);
var vtx1:Vertex = VectortoVertex(p1);
var vtx2:Vertex = VectortoVertex(p2);

var uv0:UV = objB.faces[i].uv0;
var uv1:UV = objB.faces[i].uv1;
var uv2:UV = objB.faces[i].uv2;

hitUV = BaryCentricTest.getUVs(vtx0,vtx1,vtx2,uv0,uv1,uv2,intersectVector)


WooYAY :)

[Michael Iv]

Ok here is a quick way to get UVs from ray-triangle intersection point:



A;B;C vectors of triangle vertices
P intersection vector
uA uB uC- U coords of A B C
vA vB vC -V coords of A B C

First, you compute distances from P to A, B and C:

dA = distance from A to P
dB = distance from B to P
dC = distance from C to B

sum = dA + dB + dC
coefA = dA / sum
coefB = dB / sum
coefC = dC / sum

So, the texture coordinate at point P is :

uP = uA * coefA + uB * coefB + uC * coefC
vP = vA * coefA + vB * coefB + vC * coefC

Read it in one of 3d math forums ,have not tested yet. But it is expressed exactly as barycentric formulas are formulated in math.
Good Luck :))

[Michael Iv]

Very cool! I did not know of the existence of this class :)))

[Fabrice3D]

Also Ask Fabrice he told once he is a barycentric GURU :))

Can't recall that! Truth is far away from that. I needed other ways to retreive uvs than I was doing previously for the raytracer I was working on,

and came across a version of this principle I liked. Credits due are in the class as its basically a 1/1 copy of this publication.

In its first version/first commit, It was a variation of it, using away face order, which turned out be wrong, was easyer fix the raytracer and set it back

and be able use the class for more cases. Such as the HitTest class for BSP.

Pretty much all we need has been done, it's a matter of adaptation. No guru, no voodoo, no magic and certainly not me!

Fabrice

[Michael Iv]

Fabrice that is ok , I recall you told me ,you used to work  alot with barycentric space . I looked through several techniques  for UV picking and found that each of them is pretty different from another. Like that one I posted above is different from one in Away3D BaryCentricTest class. One thing I don't undestand in BaryCentricTest  getUVs(0 is why you invert the denominator? is it for simplifying math calculations or it must be done for some other reason.?

[John Brookes]

Just something to watch out for with the barycentric
If your hit is along the edge of a UV it doesn't return a value.

eg was testing a ray against the horizontal center of a plane. If the segments were divisible by 2 it didn't return a hit.

[Fabrice3D]

@michael

I recall it was saving on math, but not 100% sure, its been a while since I've dived in this

@John

If your hit is along the edge of a UV it doesn't return a value.

I use another way in prebaker and normalmapgeneration, at least for a part of the code to prevent these problems. Tho its not 100% full proof, just ok enough for bitmapdata purpose.

Corner to point distance to edge/line intersect test, which gives me 3 dist percentages, all added giving me not more than 1 (added 0.02 to it tho, because due to roundings it was failing sometimes) from these I simply interpolate between vertex values, either uv's or color I set at vertexes.

so in a way very similar, except it came out very handy for my code.

There are more ways to retreive uv's, using the rect defined by the uv's for instance. Made few tests in that direction but as they were resulting in "star" like at corners

when combined with gradients, I've let them go. Might be the way that I was doing that was wrong tho.

Note en passant: the BarycentricTest class was updated last summer, not its concepts but formating, all Vector based, its obviously more complex to follow, but it should be faster

and low on memory than in its previous form. Added optional uvholder as well.

Fabrice