VSD revisited

[VirtualAce]

Just read some more about visible surface determination in my 3D math book. I have perhaps a very simple way not described in the book to do this.


First take the parametric equation of a line or ray and use it to cast a ray out into space. This will only work with large outdoor scenes and so is probably limited to flight sims or it could be combined with frustrum culling, BSPs, quadtrees, or octrees as well.

Here is my idea:

Cast 2 rays from the player to the max viewable distance in your engine.

The first ray is cast at the leftmost side of the view frustrum. This will simply be the current view angle minus half of the total view. So if your view frustrum is 60 degrees (not counting vertical frustrum here) and you are looking at 0 degrees -> your first ray is 0-30 or 330 degrees and your second ray is cast at 30 degrees.

Based on where these rays 'land' in view space you can create a 2D frustrum or box. If any vertexes lie outside of this box...they are discarded and not processed. It is extremely simply to test whether a vertex lies in a box or not. This could be extended to a cube as well. But a better way would be to determine if the bounding box or sphere of an object was in the frustrum or not in it. If it is, render it and don't test to see if it is only half in or half out - the remaining geometry will be clipped by the hardware - much less though than if you threw every vertex at it with no frustrum culling.

This is akin to a quadtree although I think it might find the frustrum quicker. Think about it. When the rays are at max view distance at the correct angles - you can create a box. The only objects you will ever see must lie inside of where these rays land - you will never see past them or left of them or to the right of them.

Here is a non-D3D example using euler angles. Not optimized and not complete but it will give you an idea of what I'm talking about.

To extend this to 3D you would need to cast 4 rays to each corner of the frustrum.

Determine 2D view frustrum

float LAngle=Player.angle-(totalview>>1);
float RAngle=LAngle+totalview;


float L_raywx=Player.worldx+(Player.LAngle*Player.viewdist);
float L_raywz=Player.worldz+(Player.LAngle*Player.viewdist);

float R_raywx=Player.worldx+(Player.RAngle*Player.viewdist);
float R_raywz=Player.worldz+(Player.RAngle*Player.viewdist);


//  in class -> D3DXVECTOR3 Frustrum[4];

Frustrum[0]=D3DXVECTOR3(L_raywx,0,1.0f);
Frustrum[1]=D3DXVECTOR3(L_raywx,0,L_raywz);
Frustrum[2]=D3DXVECTOR3(R_raywx,0,R_raywz);
Frustrum[3]=D3DXVECTOR3(R_raywx,0,1.0f);



//Rotate/translate our view frustrum with the player
//Save data to test later

void Player::UpdateFrustrum
{
   D3DXMATRIX world;
   D3DXMATRIX trans;
   D3DXMATRIX rot;
   
   
   //class Player would have following members
   //D3DXVECTOR3   rotation;
   //D3DXVECTOR3   position;
   

    D3DXMatrixTranslation(&trans,position.x,position.y,position.z);
    D3DXMatrixRotationYawPitchRoll(&rot,rotation.x,rotation.y,rotation.z);
    
    world=trans*rot;

    for (int i=0;i<4;i++)
   {
      D3DXVECTOR3 newvec;
      D3DXVec3TransformCoord(&newvec,Frustrum[i],&world);
      
      Frustrum[i]=newvec;   //could have placed in *out above
    }

}

This will give you a rotated and translated view frustrum. Test against this and you are done.

Look at the D3DX math helper functions and I'm sure you can understand what I'm trying to do. Lots of great and useful functions in that library.