Re: [Algorithms] octree and HSR

[A. J. C. <Alb...@te...>]

> From: "Jaakko Westerholm" <za...@bo...>
> Date: Wed, 30 Aug 2000 17:53:01 +0300
> To: alg...@3d...
> Subject: [Algorithms] octree and HSR

> 3. How do I compute the view frustrum? (I think I need those eight   points)
There are many ways to do that. One prefer to do it in the object space (before the points
is projected by viewing matrix) and the other prefer to do that  in the viewing space.
I prefer the first one.
I use my camera matrix to construct the view frustum planes (there are six planes, near
plane, far, left, right, top, bottom).
Your camera matrix might looks like this
[ a d g j ]
[ b e h k ]
[ c f i l ]
[ 0 0 0 1 ]
(This is the OpenGL-style matrix )

This matrix contains all information about your viewing orientation and position
(g h i) -> 3rd column of your matrix-> is your forward vector.
(d e f) -> 2nd column -> is your up vector
(a b c) is a vector that is perpendicular to forward and up vector
(j k l) is your camera's position.
With a little of imagination you can rotate that matrix by your fov and get the frustum
plane's normal.

Here is the code constructing the view frustum

// ---------------------------------
CViewFrustum::CViewFrustum(CGlobalCamera& cam){
  cam.Matrix().OrthogonalizeRotationAxis();

  CVec3 f,pos;
  CMat4 matcam=cam.Matrix();
  float fovx2=cam.FovX()*0.5; // half of fovx
  float fovy2=cam.FovY()*0.5; // half of fovy

  cam.Matrix().GetColumn(2,f); // get the forward vector
  cam.Matrix().GetColumn(3,pos); // get the camera's world position

  // zeroes the camera's world position
  matcam(0,3)=matcam(1,3);matcam(2,3)=0.;

  assert(cam.ZNear()>0 && cam.ZFar()>0);
  f.Negate(); // I use a right handed coord system
  m_Near.Normal = f;
  m_Near.D = -m_Near.Normal.Dot( pos + f*cam.ZNear() );

  m_Far.Normal = -f;
  m_Far.D = -m_Far.Normal.Dot( pos + f*cam.ZFar() );

  CMat4 mtmp;

  mtmp=matcam;
  mtmp.PostRotate( -fovx2, 0., 1., 0.); // rotate -half of fovx around Y axes
  mtmp.GetColumn(0,f); f.Negate();
  m_Right.Normal=f; // Right frustum plane' normal
  m_Right.D = -pos.Dot(m_Right.Normal);

  mtmp=matcam;
  mtmp.PostRotate( fovx2, 0., 1., 0.); // rotate  half of fovx around Y axes
  mtmp.GetColumn(0,f);
  m_Left.Normal=f; // Left frustum plane' normal
  m_Left.D = -pos.Dot(m_Left.Normal);

  mtmp=matcam;
  mtmp.PostRotate( -fovy2, 1., 0., 0.);
  mtmp.GetColumn(1,f);
  m_Bottom.Normal = f;
  m_Bottom.D = -pos.Dot(m_Bottom.Normal);

  mtmp=matcam;
  mtmp.PostRotate( fovy2, 1., 0., 0.);
  mtmp.GetColumn(1,f); f.Negate();
  m_Top.Normal = f;
  m_Top.D = -pos.Dot(m_Top.Normal);
}
// --------------------------


> 4. How can I check if the view frustrum and a cube intersect? (or if the cube is inside
the view frustrum)
This is easy once you've created the view frustum.
Just test the eight corners of the cube against the six frustum plane like this.

EIsectCriteria CViewFrustum::Test(const CBox& b) const{
  CVec3 v;
  unsigned OrFlag=0, AndFlag=~0, PFlag;

  for(int i=0; i<8; i++){
    PFlag=0;
    b.GetCorners(i,v);

    if(m_Left.Substitute(v)<0) // outside
      PFlag |= FPF_LEFT;
    if(m_Right.Substitute(v)<0) // outside
      PFlag |= FPF_RIGHT;
    if(m_Bottom.Substitute(v)<0) // outside
      PFlag |= FPF_BOTTOM;
    if(m_Top.Substitute(v)<0) // outside
      PFlag |= FPF_TOP;
    if(m_Near.Substitute(v)<0) // outside
      PFlag |= FPF_NEAR;
    if(m_Far.Substitute(v)<0) // outside
      PFlag |= FPF_FAR;

    OrFlag |= PFlag;
    AndFlag &= PFlag;
  }
  if(!OrFlag)
    return IC_INSIDE;
  if(AndFlag)
    return IC_OUTSIDE;
  return IC_STRADDLE;
}

> 1. Is it possible to know if one of nodes (or cubes) of the octree
> is possible to see from certain point? for example if it was behind a wall.

You need to add an occlusion culling algorithm to do that. Seth Teller have writen lots of
paper discussing that issue.

>
> I would also be interested of good sites.. Don't tell me about those great books like
Graphics Gems you have cause I can only read them in my dreams! =)

Have a look at Steve Baker's site (web2.airmail.net\sjbaker1\omniv.html)
It contains many excellent document that 3d programmers are looking for.