gdalgorithms-list

[Algorithms] Curves...

[Mats L. <ma...@al...>]

Witch curve-algho "should" you use for a simple terrain rendering?
Bezier or Nurb:s?? or maybe something else...
Which is more efficient when storing the terrain info and then rendering it??
pros - cons...

Re: [Algorithms] Projecting a point on a plane

[Pierre T. <p.t...@wa...>]

P = point to project
N = unit plane normal
| = dot product

Projected point = P - (D + P | N)N,

----- Original Message -----
From: Aldo Spanghero <al...@ho...>
To: <gda...@li...>
Sent: Friday, September 01, 2000 7:39 PM
Subject: [Algorithms] Projecting a point on a plane


>
>
> Hi!
>
> I can't remember how to project a point (p2) on a plane (n, p1). I need
this
> to finish the 3D sound system of my engine(this afternoon!) and my math
book
> is in my home!
>
> Someone could, please, help me?
>
> I don't wanna use DirectSound3D, for now.
>
>
> Again, thanks in advance.
>
> Aldo
>
>
> _________________________________________________________________________
> Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.
>
> Share information about yourself, create your own public profile at
> http://profiles.msn.com.
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Projecting a point on a plane

[Ron L. <ro...@do...>]

Aldo Spanghero
>
> I can't remember how to project a point (p2) on a plane (n, p1). I need
this
> to finish the 3D sound system of my engine(this afternoon!) and my math
book
> is in my home!
>
> Someone could, please, help me?
>
> I don't wanna use DirectSound3D, for now.
>
>
> Again, thanks in advance.
>

Why would you need your math book?

Line through p2 perpendicular to plane is described parametrically by
    p2 + t n

This hits plane when the vector from this point to p1 is perpendicular to n
so

   ((p2 + tn) - p1) dot n = 0

Use elementary algebraic properties of dot product to rearrange terms and
solve for t:

    t = (p1 - p2) dot n

In which I also used the fact that n dot n = 1 (unit normal vector).

So the projection is p2 + ((p1 - p2) dot n)n

Re: [Algorithms] Projecting a point on a plane

[Jeff L. <je...@di...>]

That is the same problem that I described how I solve it for 2D IK.

Using your notation, I assume for the plane, n is the normal and p1 is a point on the plane.

v = p2 - p1
p3 = p2 - n ( n dot v) 

That should do it for you.

-Jeff


At 05:39 PM 9/1/2000 +0000, you wrote:


>Hi!
>
>I can't remember how to project a point (p2) on a plane (n, p1). I need this to finish the 3D sound system of my engine(this afternoon!) and my math book is in my home!
>
>Someone could, please, help me?
>
>I don't wanna use DirectSound3D, for now.
>
>
>Again, thanks in advance.
>
>Aldo
>
>
>_________________________________________________________________________
>Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.
>
>Share information about yourself, create your own public profile at http://profiles.msn.com.
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

[Algorithms] Projecting a point on a plane

[Aldo S. <al...@ho...>]

Hi!

I can't remember how to project a point (p2) on a plane (n, p1). I need this 
to finish the 3D sound system of my engine(this afternoon!) and my math book 
is in my home!

Someone could, please, help me?

I don't wanna use DirectSound3D, for now.


Again, thanks in advance.

Aldo


_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.

Share information about yourself, create your own public profile at 
http://profiles.msn.com.

Re: [Algorithms] floats, doubles, epsilons, joy

[Jamie F. <j.f...@re...>]

>
> Also I was wondering if there was a down side to using doubles rather than
> floats.  This code doesn't use any ram so size doesn't matter, but is doing
> floating point math with doubles much slower or have other unwanted side
> effects?

Not all platforms have hardware support for doubles.

Jamie

Re: [Algorithms] floats, doubles, epsilons, joy

[Pierre T. <p.t...@wa...>]

Errr..............

Doubles notoriously are slower than floats. Moreover if you use D3D you
really shouldn't be messing around with doubles. From the DX7 docs:

"Applications that require double-precision accuracy can include the
DDSCL_FPUPRESERVE flag when calling the IDirectDraw7::SetCooperativeLevel
method to set the DirectDraw cooperative level. When the DDSCL_FPUPRESERVE
flag is used, the system still uses single-precision mode, but it saves the
state of the FPU prior to changing the precision mode, then restores the
mode when it returns control to the application. (Calling the method again
using the DDSCL_FPUSETUP flag returns Direct3D to its default behavior.)
Obviously, this check, save, then restore process takes time and can
noticeably affect performance. This flag should only be used when the
application must have double-precision accuracy and you do not want to
include code to manually set and restore the FPU mode as the application
requires."

And all in all, using doubles is just a way to hide a problem, not a way to
fix it. No magic bullet there, it really depends on the piece of code
involved I'm afraid.

Pierre


----- Original Message -----
From: Jason Zisk <zi...@n-...>
To: <gda...@li...>
Sent: Thursday, August 31, 2000 7:14 PM
Subject: [Algorithms] floats, doubles, epsilons, joy


> I've been working on some collision stuff lately and I keep running into
> problems with floating point inaccuracies.  Specifically if the player is
> standing on top of a triangle, the distance should be zero, but with float
> it was very close to zero but not quite.  So I converted all my code to
use
> double and its much better but I'm still not getting exactly zero.  With
> float they were large enough to cause unwanted movement, with double they
> are tiny but I can easily imagine the player finding a way to make these
> values be higher than my epsilon amount (0.00001).  Just so everyone
knows,
> I'm doing ellipsoid vs. triangle collision with an algorithm I found on
> Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).
>
> This is the first time I've run into this, I'm wondering if there are some
> common ways to get around these types of problems?
>
> Also I was wondering if there was a down side to using doubles rather than
> floats.  This code doesn't use any ram so size doesn't matter, but is
doing
> floating point math with doubles much slower or have other unwanted side
> effects?
>
> Thanks for any suggestions,
>
> - Jason Zisk
> - nFusion Interactive LLC
>
>
>
>
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] floats, doubles, epsilons, joy

[Jason Z. <zi...@n-...>]

A bit of buffer, good idea.  So the general algorithm would be: after I find
the distance to collision make sure its always at least X (maybe 0.01 like
Steve suggested) units.  If its larger than X units, move X-0.01 units
instead of the full X.  This sounds like it will make the system much more
robust, thanks again.

- Jason Zisk
- nFusion Interactive LLC


----- Original Message -----
From: "Gil Gribb" <gg...@ma...>
To: <gda...@li...>
Sent: Thursday, August 31, 2000 3:36 PM
Subject: Re: [Algorithms] floats, doubles, epsilons, joy


> I wouldn't use doubles, they just obscure the problem but don't eliminate
> it. If an algorithm is unstable with floats, it is usually unstable with
> doubles too.
>
> So, how to solve the problem? The only solution is carefully analize the
> situation and do things robustly. That isn't very helpful, but it is true,
> you gotta really think about the situation to solve the problem.
>
> I solve your collision problem like this typically. I don't attempt to
rest
> directly on the floor, I attempt to hover .1 inches or so off the floor.
> Therefore, even with floating point inaccuracy, I never find I am IN the
> floor at the start of the next round. This does use a tolerence, but it is
> subtly different than your approach. Your approach attempts to correct the
> problem after is occurs and my approach is proactive, insuring the problem
> does not occur. (This all assumes finding yourself in the floor is the
> problem).
>
> Even if you get this problem licked, if you are doing anything
interesting,
> like say having things push the player, you will run into half a dozen
other
> more subtle problems. You gotta think through each one to figure out how
to
> solve the problem with inexact arithmatic. It is really really hard work.
>
> -Gil
>
>
> > I've been working on some collision stuff lately and I keep running into
> > problems with floating point inaccuracies.  Specifically if the player
is
> > standing on top of a triangle, the distance should be zero, but with
float
> > it was very close to zero but not quite.  So I converted all my code to
> use
> > double and its much better but I'm still not getting exactly zero.  With
> > float they were large enough to cause unwanted movement, with double
they
> > are tiny but I can easily imagine the player finding a way to make these
> > values be higher than my epsilon amount (0.00001).  Just so everyone
> knows,
> > I'm doing ellipsoid vs. triangle collision with an algorithm I found on
> > Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).
> >
> > This is the first time I've run into this, I'm wondering if there are
some
> > common ways to get around these types of problems?
> >
> > Also I was wondering if there was a down side to using doubles rather
than
> > floats.  This code doesn't use any ram so size doesn't matter, but is
> doing
> > floating point math with doubles much slower or have other unwanted side
> > effects?
> >
> > Thanks for any suggestions,
> >
> > - Jason Zisk
> > - nFusion Interactive LLC
> >
> >
> >
> >
> >
> >
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] floats, doubles, epsilons, joy

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

>This is the first time I've run into this, I'm wondering if there are some
>common ways to get around these types of problems?

*cough* hack;
but it really depends on your type of application.

often you would just do a check, if it's between this number and this
number, then just set it to the number it *should* (this is a hack as well)
be.
it takes a "hell-of-a-lot-" of tweaking to get right.
just design your code with these thoughts, and make sure to add in these
"checks", if you don't you will run into lots of subtle bugs.
but there comes a point, where you just have to stop, or you might be get
the "just one more time syndrome".


>Also I was wondering if there was a down side to using doubles rather than
>floats.  This code doesn't use any ram so size doesn't matter, but is doing
>floating point math with doubles much slower or have other unwanted side
>effects?
there is no reason to "downsize" your program if you don't have to :)
anyways, i wrote up a small little test case just to make sure the
performance question.

i'm on a p3 750

time it took for double calculation 3562
time it took for float calculation 985



// time.cpp
#include <stdio.h>
#include <windows.h>
#include <iostream.h>

int main()
{
	float trash = 0;
	double trash2 = 0;
	DWORD timer;
	DWORD elapsed;
	int i;

	printf("double size = %i\n", sizeof(double));
	printf("float size = %i\n", sizeof(int));

	timer = GetTickCount();
	for(i = 0; i < 99999999; i++)	{
		trash2 += 0.23533423533412;
	}
	elapsed = GetTickCount() - timer;
	cout<<"time it took for double calculation "<<elapsed<<endl;

	timer = GetTickCount();

	for(i = 0; i < 99999999; i++)	{
		trash += 0.123412f;
	}

	elapsed = GetTickCount() - timer;
	cout<<"time it took for float calculation "<<elapsed<<endl;
}

/////////

cl -o crap time.cpp
crap :)

you could go ahead and try a while version just to be totally sure about
this issue.


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 Jason
Zisk
Sent: Thursday, August 31, 2000 12:14 PM
To: gda...@li...
Subject: [Algorithms] floats, doubles, epsilons, joy


I've been working on some collision stuff lately and I keep running into
problems with floating point inaccuracies.  Specifically if the player is
standing on top of a triangle, the distance should be zero, but with float
it was very close to zero but not quite.  So I converted all my code to use
double and its much better but I'm still not getting exactly zero.  With
float they were large enough to cause unwanted movement, with double they
are tiny but I can easily imagine the player finding a way to make these
values be higher than my epsilon amount (0.00001).  Just so everyone knows,
I'm doing ellipsoid vs. triangle collision with an algorithm I found on
Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).

This is the first time I've run into this, I'm wondering if there are some
common ways to get around these types of problems?

Also I was wondering if there was a down side to using doubles rather than
floats.  This code doesn't use any ram so size doesn't matter, but is doing
floating point math with doubles much slower or have other unwanted side
effects?

Thanks for any suggestions,

- Jason Zisk
- nFusion Interactive LLC







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

RE: [Algorithms] floats, doubles, epsilons, joy

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Jason Zisk [mailto:zi...@n-...]
> 
> I've been working on some collision stuff lately and I keep 
> running into problems with floating point inaccuracies.
> Specifically if the player is standing on top of a triangle,
> the distance should be zero, 
>

If it was zero then the bottom of the player and the top of the triangle
would occupy the same space...not what I would expect to happen.  Maybe if
you always keep objects a set distance away...like maybe .01 and still use
an epsilon like .00001 then objects at rest won't be triggering a collision
detection.

> 
> is doing floating point math with doubles much slower or
> have other unwanted side effects?
> 

I believe they take just as long if the code is running on a 64bit data bus
with a 64bit floating point unit.  The only side effect is when converting
types which will throw some variance in results...but your epsilon should
solve that.

Rockn-Roll

Re: [Algorithms] floats, doubles, epsilons, joy

[Gil G. <gg...@ma...>]

I wouldn't use doubles, they just obscure the problem but don't eliminate
it. If an algorithm is unstable with floats, it is usually unstable with
doubles too.

So, how to solve the problem? The only solution is carefully analize the
situation and do things robustly. That isn't very helpful, but it is true,
you gotta really think about the situation to solve the problem.

I solve your collision problem like this typically. I don't attempt to rest
directly on the floor, I attempt to hover .1 inches or so off the floor.
Therefore, even with floating point inaccuracy, I never find I am IN the
floor at the start of the next round. This does use a tolerence, but it is
subtly different than your approach. Your approach attempts to correct the
problem after is occurs and my approach is proactive, insuring the problem
does not occur. (This all assumes finding yourself in the floor is the
problem).

Even if you get this problem licked, if you are doing anything interesting,
like say having things push the player, you will run into half a dozen other
more subtle problems. You gotta think through each one to figure out how to
solve the problem with inexact arithmatic. It is really really hard work.

-Gil


> I've been working on some collision stuff lately and I keep running into
> problems with floating point inaccuracies.  Specifically if the player is
> standing on top of a triangle, the distance should be zero, but with float
> it was very close to zero but not quite.  So I converted all my code to
use
> double and its much better but I'm still not getting exactly zero.  With
> float they were large enough to cause unwanted movement, with double they
> are tiny but I can easily imagine the player finding a way to make these
> values be higher than my epsilon amount (0.00001).  Just so everyone
knows,
> I'm doing ellipsoid vs. triangle collision with an algorithm I found on
> Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).
>
> This is the first time I've run into this, I'm wondering if there are some
> common ways to get around these types of problems?
>
> Also I was wondering if there was a down side to using doubles rather than
> floats.  This code doesn't use any ram so size doesn't matter, but is
doing
> floating point math with doubles much slower or have other unwanted side
> effects?
>
> Thanks for any suggestions,
>
> - Jason Zisk
> - nFusion Interactive LLC
>
>
>
>
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

[Algorithms] floats, doubles, epsilons, joy

[Jason Z. <zi...@n-...>]

I've been working on some collision stuff lately and I keep running into
problems with floating point inaccuracies.  Specifically if the player is
standing on top of a triangle, the distance should be zero, but with float
it was very close to zero but not quite.  So I converted all my code to use
double and its much better but I'm still not getting exactly zero.  With
float they were large enough to cause unwanted movement, with double they
are tiny but I can easily imagine the player finding a way to make these
values be higher than my epsilon amount (0.00001).  Just so everyone knows,
I'm doing ellipsoid vs. triangle collision with an algorithm I found on
Flipcode (http://www.flipcode.com/tutorials/tut_coll-ellipsoids.shtml).

This is the first time I've run into this, I'm wondering if there are some
common ways to get around these types of problems?

Also I was wondering if there was a down side to using doubles rather than
floats.  This code doesn't use any ram so size doesn't matter, but is doing
floating point math with doubles much slower or have other unwanted side
effects?

Thanks for any suggestions,

- Jason Zisk
- nFusion Interactive LLC

Re: [Algorithms] Octree\KD tree Generation for better cache coherence...

[Conor S. <cs...@tp...>]

RE: [Algorithms] Octree\KD tree Generation for better cache =
coherence...Well, I would say your best bet for cache coherance is to =
actually optimise for size. But it doesn't really matter that much, =
because the trees don't have that many nodes, and traversal doesn't =
happen often (unless you have a raytracer).=20

Kd-tree tends to be the better I find (maybe not in terms of storage, =
but in terms of speed/flexibility).=20

If you don't wanna fragment RAM, the easiest way would be to just =
allocate a chunk, and use your own memory handler. Although, the easiest =
way to write a kd-tree or octree generation system tends to be with =
recursive constructors.=20

When it comes to in order traversal, both systems can be used to easily =
traverse in order (although, for frustum culling it isn't needed). A =
kd-tree is the same to do back to front as a BSP, except all your planes =
to test are axis aligned (means you only need a single compare to =
traverse).=20

Front to back for a kd-tree (sorta pseudo cody stuff warning):

class kdtreenode {
    float m_partition;
    UINT8 m_axii;
    kdtreenode* m_children[2];
public:
    void Traverse(float* camera,FifoStack* fs);
};

void kdtreenode::Traverse(float* camera,FifoStack* fs) {
    if (m_children[0]) { // Test leaf
        // Not leaf, traverse further
        UINT8 travtest=3D(m_partition>camera[m_axii]);
        m_children[travtest]->Traverse(camera);
        m_children[travtest^1]->Traverse(camera);
    } else {
        // Is leaf, put on stack (in order)=20
        fs->Push(this);       =20
    }
}

An octree can be traversed similarily, although you do 3 axii tests at =
once, and use binary logic for the sort.=20

Conor Stokes

  ----- Original Message -----=20
  From: Chris Brodie=20
  To: 'gda...@li...'=20
  Sent: Thursday, August 31, 2000 8:57 AM
  Subject: RE: [Algorithms] Octree\KD tree Generation for better cache =
coherence...


  (Apologies for the HTML. My mail administrators are still working on =
it. Something to do with the mail system ignoring the client settings. =
If this goes on much longer I'll switch to a native SMTP client and talk =
to a unix box.)

  I've been thinking recently about how to best structure the data in =
ram to make best use of my cache. Initially I was thinking about a =
tightly packed array that stores the data\splitting planes =
hierarchically top down. Using this method I could use pointer math to =
move around within the tree's data, which I'm not sure is a good thing =
or not from a performance point.

  The other idea I had recently is to store my tree in traversal order. =
Obviously this wouldn't be optimised for every situation but the more =
traversal that you do the greater you efficiency would be as all the =
data will likely be in order until you start skipping hunks of the tree. =


  I'm guessing that this is probably one or the more important things to =
optimise in an engine. The only source I've ever seen to do with these =
kinds of tree's was on flipcode(ask midnight) and that used dynamic =
memory allocation for storage.=20

  One last question. When you perform frustum culling to get your list =
of visible nodes do you use a special traversal technique to get a front =
to back order or do you just read them in any order then blast them =
through a radix sort. I have seen some references to techniques that do =
this but I'm not sure if the unusual traversal order would be worse on =
the cache than just reading them in as you find them and then doing a =
fast sort. In my case I'm only expecting to find perhaps 150-250 nodes =
at most.

  Many thanks=20

  Chris=20

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.

Re: [Algorithms] 256 colour palette

[Kent Q. <ken...@co...>]

Gil Gribb wrote:
> 
> > build the palette first and give it to your artists.
> 
> Our artists would kill us. Have the artists make the palette. Thankfully we
> will never use palettes again....they just suck.

Good point...

But sometimes you may want to cooperate with them on it. For example, if
you're doing some sort of lighting effects or palette cycling, you may
want to (for examples) arrange the palette with certain colors in
certain locations, or make sure that you have 16 shades of grey.

However, it's always a good idea to tell the artists your technical
constraints, and then leave them as much freedom as possible.

	Kent

-- 
-----------------------------------------------------------------------
Kent Quirk                   | CogniToy: Intelligent toys...
Game Architect               |           for intelligent minds.
ken...@co...      | http://www.cognitoy.com/     
_____________________________|_________________________________________

Re: [Algorithms] Problem with Woo's "Fast Ray-Box Intersection"

[Andrew H. <an...@co...>]

I spent a while optimizing this test.
Generally you're going to test a ray against many AABBs.
Instead of doing the divides each time you test a box, just do them once,
and multiply instead.  This is much quicker.
Watch out for axis aligned rays.  One or two of the deltas can be zero, but
luckily this is a special case and you don't even need to do the divide.
For example, if delta.x==0, all you want is: min.x <= origin.x <= max.x.
I do this by swapping to a slower routine if one or more of the delta
components is zero.

Andrew.

Re: [Algorithms] Problem with Woo's "Fast Ray-Box Intersection"

[Pierre T. <p.t...@wa...>]

For interested people, I put a modified version of Andrew Woo's Ray-AABB
intersection test here:

http://www.codercorner.com/RayAABB.cpp

Apparently it is faster than the original code (~20-30% on my machine) and
now even more robust thanks to Niki. Nothing really great, I just rewrote it
slightly, in order for it to be Intel-processor-friendly (yeah Steve, I know
:)

Maybe it can be useful to some of you.

Pierre

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] 256 colour palette

[Stephen J B. <sj...@li...>]

On Wed, 30 Aug 2000, Gil Gribb wrote:

> This isn't right steve. RGB(8,16,8) = (8/31,16/63,8/31) in 565. Oddly, the
> divisor is not a power of two, because 31, not 32 is the maximum value that
> can be stored in 5 bits.

Yes - but if you can set up your own palette, you can still arrange
that the even numbered values for G have the same brightnesses as
the equivelent R's and B's.  Admittedly, this will mean that
"White" will be 1/31 == ~3% dimmer than you might expect...but
that's a small price to pay for nice greys.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1

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\KD tree Generation for better cache coher ence...

[Chris B. <Chr...@ma...>]

(Apologies for the HTML. My mail administrators are still working on it. Something to do with the mail system ignoring the client settings. If this goes on much longer I'll switch to a native SMTP client and talk to a unix box.)

I've been thinking recently about how to best structure the data in ram to make best use of my cache. Initially I was thinking about a tightly packed array that stores the data\splitting planes hierarchically top down. Using this method I could use pointer math to move around within the tree's data, which I'm not sure is a good thing or not from a performance point.

The other idea I had recently is to store my tree in traversal order. Obviously this wouldn't be optimised for every situation but the more traversal that you do the greater you efficiency would be as all the data will likely be in order until you start skipping hunks of the tree. 

I'm guessing that this is probably one or the more important things to optimise in an engine. The only source I've ever seen to do with these kinds of tree's was on flipcode(ask midnight) and that used dynamic memory allocation for storage. 

One last question. When you perform frustum culling to get your list of visible nodes do you use a special traversal technique to get a front to back order or do you just read them in any order then blast them through a radix sort. I have seen some references to techniques that do this but I'm not sure if the unusual traversal order would be worse on the cache than just reading them in as you find them and then doing a fast sort. In my case I'm only expecting to find perhaps 150-250 nodes at most.

Many thanks

Chris

Re: [Algorithms] Unattainable effects?

[Mark W. <mwa...@to...>]

Too many scientists going blind I expect ;)

Sorry, couldn't resist :)

Mark

> They generally have fast passive shutters that cut in if
> the laser gets out of reasonable limits...I'm not really
> familiar with the details though.
> 
> They are not widely used (AFAIK) right now - something of
> a lab-experiment/rarity.

Re: [Algorithms] 256 colour palette

[Gil G. <gg...@ma...>]

This isn't right steve. RGB(8,16,8) = (8/31,16/63,8/31) in 565. Oddly, the
divisor is not a power of two, because 31, not 32 is the maximum value that
can be stored in 5 bits.
-Gil

> > True. But, as I stated earlier, this can be a bad thing (tm) as
> > you don't get a pure grey ramp... just lots of icky slightly
> > off greys in your palette, so its worth avoiding.
>
> Suppose you have one extra bit of Green - compared to
> Red and Blue....you just have to set up the colour
> lookup table such that even numbered green inputs
> have the same output as the corresponding R and B
> entries.
>
> Hence, R=8, G=16, B=8 would be an exact grey, but
>        R=8, G=15, B=8 would be a purplish grey and
>        R=8, G=17, B=8 would be a greenish grey.
>
> Then, so long as your greys have identical numbers for
> Red and Blue and even numbered Greens, you'll get perfect
> greys with the in between green values used for non-grey-scale
> colours.
>
> The (slight) lossage here is that you can't quite get
> maximum brightness Red or Blue entries.
>
> Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
> L3Com/Link Simulation & Training (817)619-2466 (Fax)
> Work: sj...@li...           http://www.link.com
> Home: sjb...@ai...       http://web2.airmail.net/sjbaker1
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] octree and HSR

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

Various code for these at my web site.  The first
part of each file indicates the page to go to.

----- Original Message -----
From: "Jaakko Westerholm" <za...@bo...>
> 1. How can I check if line intersects a cube?
MgcIntersection.html:  MgcIntrLin3Box3.{h,cpp} has
code for "test" or "find" intersections.  The "test"
code uses the method of separating axes and is
quite fast.

> 2. How can I check if triangle and cube intersect?

I have not converted this code to the new code base.
The old code is
MgcIntersection.html:  tr3bx3ti.{h,cpp} for "test",
tr3bx3fi.{h,cpp} for "find".

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

Better to specify a coordinate frame and near,far,... values.
MgcCore.html: MgcFrustum.{h,inl,cpp} for a view frustum that
is not skewed.  MgcIntersection.html:  MgcIntrBox3Frustum3.{h,cpp}
for cull testing of oriented box against frustum.

Most of the code requires files from MgcCore.html.  You can download
the zip files rather than the individual files.

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

RE: [Algorithms] Unattainable effects?

[Stephen J B. <sj...@li...>]

On Wed, 30 Aug 2000, Akbar A. wrote:

> >A direct laser-on-retina display is perfectly capable of
> >making you squint

> i don't want to sound foolish but i barely trust my self into looking into
> the sun (sometimes i just do it to "see" ;)
> but, trusting a programmer to control let alone software :|
> is it just me or is this tech very dangerous?
 
Yep - it's pretty dangerous.
 
They generally have fast passive shutters that cut in if
the laser gets out of reasonable limits...I'm not really
familiar with the details though.

They are not widely used (AFAIK) right now - something of
a lab-experiment/rarity.

Steve Baker                      (817)619-2657 (Vox/Vox-Mail)
L3Com/Link Simulation & Training (817)619-2466 (Fax)
Work: sj...@li...           http://www.link.com
Home: sjb...@ai...       http://web2.airmail.net/sjbaker1