gdalgorithms-list

RE: [Algorithms] octree and HSR

[Akbar A. <sye...@ea...>]

>1. How can I check if line intersects a cube?
>2. How can I check if triangle and cube intersect?
>3. How do I compute the view frustrum? (I think I need those eight
points)
>4. How can I check if the view frustrum and a cube intersect? (or if the
cube is inside the view frustrum)

use www.google.com it's your friend.
also www.realtimerendering.com if you don't have the book i suggest you get
it.
there is also dave eberly's book which is coming out soon, it should have
some good stuff in it (relating to "tech" / "math" techniques)
also check the comp.graphics.algoritms faq.
iirc it' has all that you asked


>And then these hard ones:
first get the first ones done, then work on the hard ones. a lot of work has
been done on oct-trees.
iirc ati has released a terrain demo and it uses a hybrid of an octree?
look for the radeon sdk at www.ati.com
again, www.google.com
also check www.flipcode.com

>Don't tell me about those great books like Graphics Gems
hmm, i suppose you don't have the means to get the series. a lot of it does
not apply to the "3d programmers", it is a "graphics gems". it has a few
good articles that apply to us ;)
I recommend you to realtime rendering. this is a very good book and it goes
over the majority of the techniques that we use in rtr. also watt and watt
"advanced animation and rendering techniques". the one by "foley" is
"supposed" to be good but i always preferred watt and watt.


anyways, i'm sure you'll get a reply or a "how to", but i think it's better
if you "teach a person to fish, instead of giving him a fish" ;)

peace.
akbar A.


isn't it ironic, in the paper "A Characterization of Ten Hidden-Surface
Algorithms", by sutherland, sproull and schumacker that we use the eleventh
algorithm ;)
makes you really think


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
Jaakko Westerholm
Sent: Wednesday, August 30, 2000 9:53 AM
To: alg...@3d...
Subject: [Algorithms] octree and HSR


Hi everyone!

I have these few questions about octrees and hiddens surface removal.

First the simple questions:
1. How can I check if line intersects a cube?
2. How can I check if triangle and cube intersect?
3. How do I compute the view frustrum? (I think I need those eight   points)
4. How can I check if the view frustrum and a cube intersect? (or if the
cube is inside the view frustrum)

And then these hard ones:

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.

2. Can I use trianlge strips with octrees? If a strip goes through several
nodes and for example only one node is visible should I clip the strip?

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!
=)

--Jaakko W--





---JAAKKO---
Get your Free E-mail at http://bosti.zzn.com
___________________________________________________________________
Hae oma Web-perusteinen sähköposti palvelusi http://www.zzn.com:sta
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

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.

Re: [Algorithms] octree and HSR

[Dave E. <eb...@ma...>]

From: "A. Jeffrey Cahyono" <Alb...@te...>

> > 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.
<snip of code>

I do not believe your code handles the case when the eight
corners of the box are outside the frustum, but the box
still intersects the frustum (or completely contains the frustum).
If you can guarantee that your bounding boxes are small
enough relative to the frustum (for example a rectangular
face can never be large enough to contain the near face
of the frustum), then not a problem.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com

Re: [Algorithms] octree and HSR

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

----- Original Message -----
From: "Dave Eberly" <eb...@ma...>
To: <gda...@li...>
Sent: Thursday, August 31, 2000 7:47 PM
Subject: Re: [Algorithms] octree and HSR


> From: "A. Jeffrey Cahyono" <Alb...@te...>
>
> > > 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.
> <snip of code>
>
> I do not believe your code handles the case when the eight
> corners of the box are outside the frustum, but the box
> still intersects the frustum (or completely contains the frustum).
> If you can guarantee that your bounding boxes are small
> enough relative to the frustum (for example a rectangular
> face can never be large enough to contain the near face
> of the frustum), then not a problem.

I've tested that kind of case and  the testing function returns IC_STRADDLE.
This algorithm is a conservative testing.

BTW I've checked out tour intersection library and it really cool!

I also would like to apologize because I forget to mention that the original idea of this
algorithm was came from Thatcher Ulrich's terrain demo.

[Algorithms] Bibliography of "Real-Time Rendering" now on web

[Eric H. <er...@ac...>]

We wrote a little Perl conversion program and so now the bibliography of the book "Real-Time
Rendering" is available online, with URLs:

    http://www.realtimerendering.com/refs.html

We hope you find it of use, and please let us know of updates for any links,

Tomas & Eric

RE: [Algorithms] Bibliography of "Real-Time Rendering" now on web

[Akbar A. <sye...@ea...>]

perfect timing ;)
i was "just" looking up *something.


*talisman arch reference.
sigh, to bad there is no online ref in the book that i know off



peace,
akbar A.



-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Eric
Haines
Sent: Tuesday, September 19, 2000 8:54 PM
To: gda...@li...
Subject: [Algorithms] Bibliography of "Real-Time Rendering" now on web


We wrote a little Perl conversion program and so now the bibliography of the
book "Real-Time
Rendering" is available online, with URLs:

    http://www.realtimerendering.com/refs.html

We hope you find it of use, and please let us know of updates for any links,

Tomas & Eric

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list