Check GPU gems. No sqrts(), no arccos().
Printable View
Check GPU gems. No sqrts(), no arccos().
I do not have it, would you be kind enough to post a method that only requires dotproducts?
As I've said, the only method for ray/triangle intersection that works only with dotproduct is when you store the information for 3 inward pointing planes that represent each edge of the triangle...if the ray intersects the triangle plane, and if that point is in front of all 3 other planes, then the ray intersects the triangle.
Else, you need to induce the other method I am talking about, which you evidently haven't heard of (very common for 3D graphics programmers to know about) which induces 3 sqrts and 3 acos calls.
This was taken from 3D Mathematics for Game Programming and Development. I only altered it to suit Direct3D using the D3DX library of functions. The code was also taken from an algorithm by Didier Badoul out of Graphics Gems I, pp 390-393.Code:
float RayTriangleIntersection(D3DXVECTOR3 &rayOrg,D3DXVECTOR3 &rayDelta,D3DXVECTOR3 &p0,D3DXVECTOR3 &p1,D3DXVECTOR3 &p2,float minT)
{
const float kNoIntersection=1e30f;
D3DXVECTOR3 e1,e2;
e1=p1-p0;
e2=p2-p1;
D3DXVECTOR n;
D3DXVec3Cross(&n,e1,e2);
float dot=n * rayDelta;
if (!(dot<0.0f)) return kNoIntersection;
float d=D3DXVec3Dot(&n,&p0);
float t=d-(D3DXVec3Dot(&n,&rayOrg);
if (!(t<0.0f)) return kNoIntersection;
if (!(t>=dot*minT)) return kNoIntersection;
t/=dot;
assert(t>=0.0f);
assert(t<=minT);
D3DXVector3 p;
p=rayOrg+rayDelta*t;
float u0,u1,u2;
float v0,v1,v2;
if (fabs(n.x) > fabs(n.y))
{
if (fabs(n.x)>fabs(n.z))
{
u0=p.y-p0.y;
u1=p1.y-p0.y;
u2=p2.y-p0.y;
v0=p.z-p0.z;
v1=p1.z-p0.z;
v2=p2.z-p0.z;
}
else
{
u0=p.x-p0.x;
u1=p1.x-p0.x;
u2=p2.x-p0.x;
v0=p.y-p0.y;
v1=p1.y-p0.y;
v2=p2.y-p0.y;
}
}
else
{
if (fabs(n.y)>fabs(n.z))
{
u0=p.x-p0.x;
u1=p1.x-p0.x;
u2=p2.x-p0.x;
v0=p.z-p0.z;
v1=p1.z-p0.z;
v2=p2.z-p0.z;
}
else
{
u0=p.x-p0.x;
u1=p1.x-p0.x;
u2=p2.x-p0.x;
v0=p.y-p0.y;
v1=p1.y-p0.y;
v2=p2.y-p0.y;
}
}
float temp=u1*v2-v1*u2;
if (!(temp!=0.0f)) return kNoIntersection;
temp=1.0f/temp;
float alpha=(u0*v2-v0*u2)*temp;
if (!(alpha>=0.0f)) return kNoIntersection;
float beta=(u1*v0-v1*u0)*temp;
if (!(beta>=0.0f)) return kNoIntersection;
float gamma=1.0f-alpha-beta;
if (!(gamma>=0.0f)) return kNoIntersection;
return t;
}
Assuming I made no mistakes it should work just fine.
In D3D, are the verts of visible triangles winded in clockwise or counter clockwise direction?
The portal rendering scheme only works well for inside environments which is what I thought we were talking about. For other environments you could switch to a quad tree or some type of ROAM implementation. This combined with a BSP portal renderer for interior scenes would be more than adequate. If a window or door leads to the outside you would need to switch VSDs. Or you could limit your game to either indoor only or outside only scenes. Most quake, unreal, and doom maps are exclusively indoor with outdoor areas made to look like an outdoor scene, when in actuality it is a modified indoor scene. None of the scenes stretch too far into the distance. For a better outdoor scene you would need to implement something like FarCry or some type of other VSD. There are a millions ways to do it.
It can be either. The algo above might not work for a CCW winding order. But that is easily solved.
In Direct3D winding order is controlled by:
Device->SetRenderState(D3DRS_CULLMODE,[D3DCULL_CW | D3DCULL_CCW]);
um...yea....all this goes WAY over my head at this point....i'll leave dot products and ray tracing and what ever else you mentioned for another time ;}
-psychopath
That is a very interesting algorithm. I have never seen it before, but if it really is from a book then I trust it works. I don't actually understand where all of it comes from, but if it does work with an arbitrary triangle* then it looks to be the best algorithm because it involves no square roots or acos, but also doesn't need to inflate the data with inward pointing planes.
*My only question is this: does it really work for an arbitrary triangle (i.e, the triangle doesn't have to be aligned to any specific axis or anything like that)...it seems like it does, but I just want to make sure.
According to the book, yes it does. I have not tried it yet because I'm not that far into my engine at this point.