"subtractive geometry"?

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()....

  1. #16
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    Check GPU gems. No sqrts(), no arccos().

  2. #17
    Registered User
    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

  3. #18
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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;
    }
    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.

    Assuming I made no mistakes it should work just fine.

  4. #19
    Registered User
    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

  5. #20
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.

  6. #21
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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]);

  7. #22
    The Right Honourable psychopath's Avatar
    Join Date
    Mar 2004
    Location
    Where circles begin.
    Posts
    1,070
    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
    Memorial University of Newfoundland
    Computer Science

    Mac and OpenGL evangelist.

  8. #23
    Registered User
    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

  9. #24
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    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.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21