Check GPU gems. No sqrts(), no arccos().

This is a discussion on *"subtractive geometry"?* within the **Game Programming** forums, part of the General Programming Boards category; Check GPU gems. No sqrts(), no arccos()....

- 10-12-2004 #16

- 10-12-2004 #17

- Join Date
- Mar 2003
- Posts
- 580

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.See you in 13

- 10-12-2004 #18Code:
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; }

*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.

Assuming I made no mistakes it should work just fine.

- 10-12-2004 #19

- Join Date
- Mar 2003
- Posts
- 580

In D3D, are the verts of visible triangles winded in clockwise or counter clockwise direction?

See you in 13

- 10-12-2004 #20
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.

- 10-12-2004 #21
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]);

- 10-13-2004 #22
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

- 10-13-2004 #23

- Join Date
- Mar 2003
- Posts
- 580

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.See you in 13

- 10-13-2004 #24
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.

- Exactly how to get started with C++ (or C) today
- C Tutorial
- C++ Tutorial
- 5 ways you can learn to program faster
- The 5 Most Common Problems New Programmers Face
- How to set up a compiler
- 8 Common programming Mistakes
- What is C++11?
- Creating a game, from start to finish

- How to create a shared library on Linux with GCC - December 30, 2011
- Enum classes and nullptr in C++11 - November 27, 2011
- Learn about The Hash Table - November 20, 2011
- Rvalue References and Move Semantics in C++11 - November 13, 2011
- C and C++ for Java Programmers - November 5, 2011
- A Gentle Introduction to C++ IO Streams - October 10, 2011