Thread: "subtractive geometry"?

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

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.

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]);

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.