gdalgorithms-list

RE: [Algorithms] Multithreading with Hardware Acceleration

[Tom F. <to...@mu...>]

Yes, lots of people do this for various reasons, amongst them this one.

In D3D there are a variety of places you can do this sort of code:

while ( TRUE )
{
	res = DoAnOperation();
	if ( res == WORKED )
	{
		break;
	}
	Sleep(0);
}

I'm specifically thinking of Flip, Blt and Lock here. So there is certainly
possibilities there.

Sadly, so many apps have been written with this style:


DoAnOperation();
//Assume it worked without checking any flag or anything.


that many drivers have had to simply block internally and not return the
"can't do it just yet or it would block" error. And because of the special
thing that a driver is on most OSes, they often can't do the equivalent of
Sleep(0). So yet another good idea ruined by dodgy apps I'm afraid.

Still, some drivers do do this properly, which is cool.


The other way to do it, which does always work as far as I know, is code
such as the following:

while ( !ReadyToDoBlt() )
{
	Sleep (0);
}
res = Blt();
// Should only get actual _errors_ back from this.


This is certainly a good way to give way to other threads.

Some people go mad with threads and create them all over the place, e.g. one
for each AI character. That's possibly a little over the top, but can work.
You need to beware of the pitfalls of threading as well as the advantages,
but it sounds like you're aware of some of the problems already.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day. 

-----Original Message-----
From: Chris Brodie [mailto:Chr...@ma...]
Sent: 21 August 2000 04:39
To: 'gda...@li...'
Subject: [Algorithms] Multithreading with Hardware Acceleration


I've had a thought for a while. 
If I ran my main loop in a thread and the video rendering in a separate
thread (with a bit of sync'ing) I could net a bit of time during hardware
blocks to start preparing the next frame, maybe do a bit of extra occlusion
culling\tesselation or AI. Of course I have no idea about video cards and
blocking. (Like maybe on a T&L card it would just gather it's data and go
off for a while doing things and not bother the CPU. If the card however
keeps accessing the ram however the context switches might bite back at any
gains you make)
Does anyone know if this is a worth the effort? (I'm already threading the
network and file system queues so there is no learning involved)
Chris Brodie 
(I apologise for the HTML. My mail department says your not getting it :) ) 

RE: [Algorithms] Multithreading with Hardware Acceleration

[Charles B. <cb...@cb...>]

Of note here is the famed Windows 9x anomaly of rapid decreases in
performance when the running thread count goes over 32 (roughly).
NT and 2k seem (relatively) free of this problem.

At 05:02 AM 8/21/00 +0100, you wrote:
>Some people go mad with threads and create them all over the place, e.g. one
>for each AI character. That's possibly a little over the top, but can work.
>You need to beware of the pitfalls of threading as well as the advantages,
>but it sounds like you're aware of some of the problems already.

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com

[Algorithms] Tangential Curvature of terrain

[Klaus H. <k_h...@os...>]

Hi,

I'd like to enhance my texture synthesizer for terrain. In particular, I'd
like to make my ecosystem-classification depend on the tangential curvature
of the terrain. I guess that may require some explanation.

I have a set of ecosystem definititions. Such definitions include things
like:
[1] the upper elevation limit at which the ecosystem can exist
[2] the minimum and maximum slops at which the ecosystem can exist
[3] elevation skewing
[4] etc...

Now, for each data point in the height field, I go through the set of
ecosystems, and determine which ecosystem exists at this data point. Such a
system is very useful for 'realistic' texture synthesis, and it's also great
to create a natural distribution of trees.
However, there's one thing I haven't been able to implement, yet. I'd like
to make my ecosystem classification depend on the concavity/convexity of the
terrain. I know that this requires me to compute the tangential curvature of
the terrain (which is usually stored in an extra curvature field).

To make it easier for you to understand, you can have a loot at the
following web-site:
http://www2.gis.uiuc.edu:2280/modviz/

The fifth terrain image (from above) shows the tangential curvature of some
terrain. This is exactly what I'd like to do. I know how I need to use the
information from curvature field to modify my ecosystem classification, but
I have no idea how I to compute the tangential curvature field itself. In
know that there's a paper on the above mentioned web-site, and I also know
that there's an implementation in the GRASS package. However, I don't know
enough about the math here to understand the paper, and the implementation
in the GRASS package is, well, ... have a look at it, and you'll know what I
mean.

Finally, my question is this. Does anyone know of a more detailed and
I-don't-expect-you-know-everything resource on calculating the tangential
curvature? Or maybe some readable source? Or even better... can someone
explain this to me?

Again, I've reached a point, where I wished that my math skills were better.
At least I hope that the answer to my question is not too easy, so that
maybe some math guys are interested. I cannot even promise that I'll be able
to follow your replies, but I'm sure someday I will (after re-reading,
re-re-reading, ... :)

Thanks,
Niki

Re: [Algorithms] Tangential Curvature of terrain

[Thatcher U. <tu...@tu...>]

> I'd like to enhance my texture synthesizer for terrain. In particular, I'd
> like to make my ecosystem-classification depend on the tangential
curvature
> of the terrain. I guess that may require some explanation.
>
> I have a set of ecosystem definititions. Such definitions include things
> like:
> [1] the upper elevation limit at which the ecosystem can exist
> [2] the minimum and maximum slops at which the ecosystem can exist
> [3] elevation skewing
> [4] etc...
>
> Now, for each data point in the height field, I go through the set of
> ecosystems, and determine which ecosystem exists at this data point. Such
a
> system is very useful for 'realistic' texture synthesis, and it's also
great
> to create a natural distribution of trees.
> However, there's one thing I haven't been able to implement, yet. I'd like
> to make my ecosystem classification depend on the concavity/convexity of
the
> terrain. I know that this requires me to compute the tangential curvature
of
> the terrain (which is usually stored in an extra curvature field).
>
> To make it easier for you to understand, you can have a loot at the
> following web-site:
> http://www2.gis.uiuc.edu:2280/modviz/
>
> The fifth terrain image (from above) shows the tangential curvature of
some
> terrain. This is exactly what I'd like to do. I know how I need to use the
> information from curvature field to modify my ecosystem classification,
but
> I have no idea how I to compute the tangential curvature field itself. In

Ah.  I think I understand.  Basically, the curvature of a function is its
second derivative.  The first derivative is the slope.  But for a 2D
function like a heightfield, these derivatives are vectors, not scalars.
This makes sense intuitively by noticing that a heightfield can be convex in
one direction and concave in another direction.You're interested in scalar
values I think, which means you want the curvature of the heightfield with
respect to a certain direction.  In the web page you gave, they compute
profile curvature and tangential curvature, which are the curvatures of the
terrain in two orthogonal directions.

The profile curvature is the curvature along the "fall-line": i.e. the
direction of maximum slope.  You can find the fall-line with something like:

fall_line = | up_axis x (normal x up_axis)  |

That gives you a vector in the plane tangent to the surface, pointing down
the hill (Those 'x's are cross-products.)  When the normal is vertical,  the
fall-line is undefined (there's no downhill direction).  To estimate the
curvature, you measure the difference between the actual slope near the
point, and the fall-line.  So something like (assuming +y is up):

samp = fall_line * delta;
profile_curvature = ((terrainheight(p + samp) - (p.y + samp.y)) +
    (terrainheight(p - samp) - (p.y - samp.y))) / delta;

Delta is some "small" distance; it probably makes sense for it to be equal
to your heightfield sample spacing.  Basically you're measuring the
difference between the straight fall-line and what the terrain actually
does; if the terrain is concave, the actual terrain samples are higher than
the fall-line and the formula comes out positive; if the terrain is convex
then the samples are lower than the fall line and the formula comes out
negative.

The "tangent curvature" is the same thing, except instead of using the
fall-line, you use a vector that's perpendicular to the fall-line, and
parallel to the terrain surface, i.e. a vector that points across the slope
of the terrain.  It's easy to compute this tangent vector, it's just (normal
x fall_line).  Or the negative of that; it doesn't matter.  Replace
"fall-line" with the tangent vector, and you'll get the tangent curvature
you're looking for.

Apologies if I abused some calculus concepts or got some scale factors off.
But that's the basic idea.

Hope this helps,

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] Tangential Curvature of terrain

[Joe A. <jo...@ti...>]

> Basically, the curvature of a function is its second derivative.
I think geometrically viewn this is not the correct answer. Take as an
simplyfied 
example: f(x) = x^2 f''(x) = 2

Which meant that for every point the concavity/convexity is the same over
the entire graph.

What this concavity/convexity value actually specifies is how high a heixel
is in respect to the heixels in some distance around it. Maybe even in
respect to all heightsamples in the heightmap.

Consider for example an huge crater landscape and in the middle of this
crater there is a small hill.

The question now is, is the heixel on top of this small hill inside the huge
crater, more convex or concave?


So what you want is that heixels that are near have more influence than
heixels that are far away from the heixel, whose concavity/convexity you
want to find out.


So what you need to define is a function with a maximum distance, which
gives you out a value between 0...1 when you give it a value from
0...maximumdistance.
y = f (x)
x e [0...maximumDistance]
y e [0...1]

A gauss-like curve is propably best suited:
y = 360^-((x/maximumDistance)^5)
(This function has worked out for me just fine.)


Pseudocode:

float ConcaveConvex (long inX, long inZ, float inMaxDistance)
{
    float itsHeight = GetHeight (inX, inZ);
    float c = 0;
    
    for (z=0;z<HowmanyHeixels;z++)
    {
        for (z=0;z<HowmanyHeixels;z++)
        {
            float difference = itsHeight - GetHeight (x, z);
            float d = sqrt ((x-inX)*(x-inX) + (z-inZ)*(z-inZ));
            c += difference  * GaussFunction (d, inMaxDistance);
        }
    }
    
    c /= HowmanyHeixels* HowmanyHeixels;
    return c;
}

float GaussFunction (float inX, float inMax)
{
    return powf (360.0F, -powf (inX / (inMax), 5.0F)
}

float GetHeight () should give back a height scaled to [0...1] in this
context.



There is plenty room for optimization here (tables, tables, tables)
But even then it will be very slow. But it doesnt matter that much because
you dont want to calculate the ecomap in realtime or as a preprocessing
phase step anyways.


Note that I havent integrated this into my terrain engine yet, I have only
spent some thought on it, so I cant really guarentee that it works.

bye joe

Re: [Algorithms] Tangential Curvature of terrain

[Thatcher U. <tu...@tu...>]

From: Joe Ante <jo...@ti...>
> Thatcher wrote:
> > Basically, the curvature of a function is its second derivative.
> I think geometrically viewn this is not the correct answer. Take as an
> simplyfied
> example: f(x) = x^2 f''(x) = 2
>
> Which meant that for every point the concavity/convexity is the same over
> the entire graph.

Whoops, you're right, I made a totally bogus statement.  The curvature of a
function is actually much more than just the second derivative.  According
to my calc book it's:

for a parametric curve with x = f(t), y = g(t):

k = | x'y'' - y'x'' | / ((x'^2 + y'^2) ^ (3/2))

I'm not sure that corrected definition impacts the original problem or its
solution much.

> What this concavity/convexity value actually specifies is how high a
heixel
> is in respect to the heixels in some distance around it. Maybe even in
> respect to all heightsamples in the heightmap.
>
> Consider for example an huge crater landscape and in the middle of this
> crater there is a small hill.
>
> The question now is, is the heixel on top of this small hill inside the
huge
> crater, more convex or concave?
>
>
> So what you want is that heixels that are near have more influence than
> heixels that are far away from the heixel, whose concavity/convexity you
> want to find out.
>
>
> So what you need to define is a function with a maximum distance, which
> gives you out a value between 0...1 when you give it a value from
> 0...maximumdistance.
> y = f (x)
> x e [0...maximumDistance]
> y e [0...1]
>
> A gauss-like curve is propably best suited:
> y = 360^-((x/maximumDistance)^5)
> (This function has worked out for me just fine.)
>
>
> Pseudocode:
>
> float ConcaveConvex (long inX, long inZ, float inMaxDistance)
> {
>     float itsHeight = GetHeight (inX, inZ);
>     float c = 0;
>
>     for (z=0;z<HowmanyHeixels;z++)
>     {
>         for (z=0;z<HowmanyHeixels;z++)
>         {
>             float difference = itsHeight - GetHeight (x, z);
>             float d = sqrt ((x-inX)*(x-inX) + (z-inZ)*(z-inZ));
>             c += difference  * GaussFunction (d, inMaxDistance);
>         }
>     }
>
>     c /= HowmanyHeixels* HowmanyHeixels;
>     return c;
> }
>
> float GaussFunction (float inX, float inMax)
> {
>     return powf (360.0F, -powf (inX / (inMax), 5.0F)
> }
>
> float GetHeight () should give back a height scaled to [0...1] in this
> context.

That will give a nice smoothed scalar field, but it loses the directionality
of the tangent/profile curvature that I think Klaus was looking for.  If I
read Ron correctly then you're computing something similar to the "mean
curvature", although not exactly the same thing because you're averaging
over all directions and across a potentially large area.  But it's probably
still useful for ecosystem stuff.

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] Tangential Curvature of terrain

[Klaus H. <k_h...@os...>]

Thanks, Joe :)

At some point I'll try everything I can get my hands on. I'll collect all
those mails, and will try other algorithms as soon as this terrain sample is
finished (do some improvements afterwards).
At the moment I have a solution that looks pretty cool. And guess what...
it's the solution that I thought would never work. I was wrong and the
results can look just beautiful, and it nicely breaks up the transition
between two ecosystem.

What I did is this:
For each data point Pm,n in the height field compute the
elevation-difference between Pm,n and its eight direct neighbors. Sum these
differences up and average them, by dividing the sum by 8. The result is a
single value R (for each data point).

I then modify the elevation line as follows:
elevLine' = elevLine + R * ecosystem.relEffect;

where elevLine' is the new elevation line, elevLine is the elevation line of
the ecosystem after elevation skewing (or before - shouldn't matter), and
relEffect is a scale factor which you can use to increase/decrease the
effect.

You would honestly be surprised by the results of this simple solution.
There are places in my terrain that look almost real, and I could further
enhance this by casting shadows.

...And I thought it wouldn't work.

Niki

----- Original Message -----
From: Joe Ante <jo...@ti...>
To: <gda...@li...>
Sent: Monday, August 21, 2000 3:19 PM
Subject: Re: [Algorithms] Tangential Curvature of terrain


> > Basically, the curvature of a function is its second derivative.
> I think geometrically viewn this is not the correct answer. Take as an
> simplyfied
> example: f(x) = x^2 f''(x) = 2
>
> Which meant that for every point the concavity/convexity is the same over
> the entire graph.
>
> What this concavity/convexity value actually specifies is how high a
heixel
> is in respect to the heixels in some distance around it. Maybe even in
> respect to all heightsamples in the heightmap.
>
> Consider for example an huge crater landscape and in the middle of this
> crater there is a small hill.
>
> The question now is, is the heixel on top of this small hill inside the
huge
> crater, more convex or concave?
>
>
> So what you want is that heixels that are near have more influence than
> heixels that are far away from the heixel, whose concavity/convexity you
> want to find out.
>
>
> So what you need to define is a function with a maximum distance, which
> gives you out a value between 0...1 when you give it a value from
> 0...maximumdistance.
> y = f (x)
> x e [0...maximumDistance]
> y e [0...1]
>
> A gauss-like curve is propably best suited:
> y = 360^-((x/maximumDistance)^5)
> (This function has worked out for me just fine.)
>
>
> Pseudocode:
>
> float ConcaveConvex (long inX, long inZ, float inMaxDistance)
> {
>     float itsHeight = GetHeight (inX, inZ);
>     float c = 0;
>
>     for (z=0;z<HowmanyHeixels;z++)
>     {
>         for (z=0;z<HowmanyHeixels;z++)
>         {
>             float difference = itsHeight - GetHeight (x, z);
>             float d = sqrt ((x-inX)*(x-inX) + (z-inZ)*(z-inZ));
>             c += difference  * GaussFunction (d, inMaxDistance);
>         }
>     }
>
>     c /= HowmanyHeixels* HowmanyHeixels;
>     return c;
> }
>
> float GaussFunction (float inX, float inMax)
> {
>     return powf (360.0F, -powf (inX / (inMax), 5.0F)
> }
>
> float GetHeight () should give back a height scaled to [0...1] in this
> context.
>
>
>
> There is plenty room for optimization here (tables, tables, tables)
> But even then it will be very slow. But it doesnt matter that much because
> you dont want to calculate the ecomap in realtime or as a preprocessing
> phase step anyways.
>
>
> Note that I havent integrated this into my terrain engine yet, I have only
> spent some thought on it, so I cant really guarentee that it works.
>
> bye joe
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Tangential Curvature of terrain

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

> There are places in my terrain that look almost real, and I could further
> enhance this by casting shadows.

What about a new snapshot...?   :)

Pierre

Re: [Algorithms] Tangential Curvature of terrain

[Klaus H. <k_h...@os...>]

Pierre,

I think it's better if you look for yourself, because people tend to show
the nicest screenshot they can find, and so do I :)

(Win95/98/2K, 108 KB)
http://www.thecore.de/TheCore/gdhighlands.zip

Some instructions...

First run the program Highlands.exe. It'll then take a while before you see
some terrain, because the program needs to generate the height field and
textures.
If you have enough video memory, then try to maximize the window now,
because that looks better... after all you want to judge the quality of the
texture, and not of quality of the LOD algorithm. So it doesn't matter if
things run a bit slower.
Now press and hold the <4> key, until the status bar at the top reads "MRes:
15". Note, that the status bar will not update while you hold the key, so
just hold it long enough. Next step is to enable geomorphing by pressing the
<g> key once. Now you can walk around (press <h> for help).

Some more info...
[1] The sample is work-in-progress, so there are a couple of flaws. For
example, there are situations, where popping occurs, even though geomorphing
is enabled. Also, I don't free all memory, so don't use the <r> key too
much. In addition, the rendering code is slow (the OpenGL specific pieces).

[2] The terrain is 1025x1025, and the texture is 1024x1024 (divided into
sixteen 256x256 patches). Thus, there's less than 1 texel per data point.

[3] I didn't use any image files to create the surface texture. It is
color-based only. In fact there are seven different colors. 3 of these
colors are green, 2 are sand, and 2 are gray. The noise-like
ground-structure was done by adding a small random value to he illumination
factors.

[4] There are two light sources. The first one is a direct sun-light that
shines from the east, and the second is an anit-sunlight source that shines
from the west. The lighting is sort of bad, and that's why darker places
look much better than bright places.

[5] There's no additional noise used to break up the transitions between the
ecosystems. It's purely based on the height field.

[6] As I said... some places look good, which does not mean all places :) So
you'll have to walk a bit, and maybe try a couple of other terrain (see
help). Most of the time, things look good, if you are not too close to the
sight (there's no detail mapping or something like that).

Niki

----- Original Message -----
From: Pierre Terdiman <p.t...@wa...>
To: <gda...@li...>
Sent: Tuesday, August 22, 2000 4:29 PM
Subject: Re: [Algorithms] Tangential Curvature of terrain


> > There are places in my terrain that look almost real, and I could
further
> > enhance this by casting shadows.
>
> What about a new snapshot...?   :)
>
> Pierre
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

Re: [Algorithms] Tangential Curvature of terrain

[Pai-Hung C. <pa...@ac...>]

----- Original Message -----
From: Klaus Hartmann <k_h...@os...>
To: <gda...@li...>
Sent: Tuesday, August 22, 2000 4:34 PM
Subject: Re: [Algorithms] Tangential Curvature of terrain


> Pierre,
>
> I think it's better if you look for yourself, because people tend to show
> the nicest screenshot they can find, and so do I :)
>
> (Win95/98/2K, 108 KB)
> http://www.thecore.de/TheCore/gdhighlands.zip
>
> Some instructions...
>
> First run the program Highlands.exe. It'll then take a while before you
see
> some terrain, because the program needs to generate the height field and
> textures.
> If you have enough video memory, then try to maximize the window now,
> because that looks better... after all you want to judge the quality of
the
> texture, and not of quality of the LOD algorithm. So it doesn't matter if
> things run a bit slower.
> Now press and hold the <4> key, until the status bar at the top reads
"MRes:
> 15". Note, that the status bar will not update while you hold the key, so
> just hold it long enough. Next step is to enable geomorphing by pressing
the
> <g> key once. Now you can walk around (press <h> for help).
>
> Some more info...
> [1] The sample is work-in-progress, so there are a couple of flaws. For
> example, there are situations, where popping occurs, even though
geomorphing
> is enabled. Also, I don't free all memory, so don't use the <r> key too
> much. In addition, the rendering code is slow (the OpenGL specific
pieces).
>
> [2] The terrain is 1025x1025, and the texture is 1024x1024 (divided into
> sixteen 256x256 patches). Thus, there's less than 1 texel per data point.
>
> [3] I didn't use any image files to create the surface texture. It is
> color-based only. In fact there are seven different colors. 3 of these
> colors are green, 2 are sand, and 2 are gray. The noise-like
> ground-structure was done by adding a small random value to he
illumination
> factors.
>
> [4] There are two light sources. The first one is a direct sun-light that
> shines from the east, and the second is an anit-sunlight source that
shines
> from the west. The lighting is sort of bad, and that's why darker places
> look much better than bright places.
>
> [5] There's no additional noise used to break up the transitions between
the
> ecosystems. It's purely based on the height field.
>
> [6] As I said... some places look good, which does not mean all places :)
So
> you'll have to walk a bit, and maybe try a couple of other terrain (see
> help). Most of the time, things look good, if you are not too close to the
> sight (there's no detail mapping or something like that).
>
> Niki
>
> ----- Original Message -----
> From: Pierre Terdiman <p.t...@wa...>
> To: <gda...@li...>
> Sent: Tuesday, August 22, 2000 4:29 PM
> Subject: Re: [Algorithms] Tangential Curvature of terrain
>
>
> > > There are places in my terrain that look almost real, and I could
> further
> > > enhance this by casting shadows.
> >
> > What about a new snapshot...?   :)
> >
> > Pierre
> >
> >
> >
> > _______________________________________________
> > 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] Tangential Curvature of terrain

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

Klaus Hartmann  wrote:

>Hi,
>
>I'd like to enhance my texture synthesizer for terrain. In particular, I'd
>like to make my ecosystem-classification depend on the tangential curvature
>of the terrain. I guess that may require some explanation.
>
>.....
>To make it easier for you to understand, you can have a loot at the
>following web-site:
>http://www2.gis.uiuc.edu:2280/modviz/
>
>The fifth terrain image (from above) shows the tangential curvature of some
>terrain. This is exactly what I'd like to do.>....
>.....
>
>Finally, my question is this. Does anyone know of a more detailed and
>I-don't-expect-you-know-everything resource on calculating the tangential
>curvature? Or maybe some readable source? Or even better... can someone
>explain this to me?
>

Only if you can  better explain what is meant by "tangential
curvature", not a standard mathematical term. It might be a standard
GIS term, but  I could not find a real definition of the term on the
uiuc GIS site that you cite.  The image you cite, at first sight,
suggests to me a couple of possible definitions, but on closer
examination of its coloring I can eliminate one, and am left with one
guess:

Namely, at points where the Gaussian curvature is non-negative, the
absolute value of the tangential curvature is the Gaussian curvature
(or some monotonic function of the Gaussian curvature) and it is
positive or negative according to whether the surface is concave up or
concave down at that point. At points where the Gaussian curvature is
negative (i.e. at saddle points), the tangental curvature is zero, or
better, undefined.   Leaving it undefined at saddle points might be OK
in view of the fact that the text of the cited image suggests that the
GIS people are interested in this concept in connection with the
distinction between "convergent" and "divergent" flow of water, and it
seems to me that it too would be undefined at a saddle point.

>Again, I've reached a point, where I wished that my math skills were better.
>At least I hope that the answer to my question is not too easy, so that
>maybe some math guys are interested. I cannot even promise that I'll be able
>to follow your replies, but I'm sure someday I will (after re-reading,
>re-re-reading, ... :)
>

See your calculus book for the notion of "concave up" vs "concave
down" as applied to the graph of a function.  I would take issue with
Ulrich's use of the term "convex" where I use "concave down", because
it corresponds poorly with other important connotations in the usual
meaning of the term "convex".  

For discussions of the various kinds of curvatures of surfaces, see
any text on introductory classical differential geometry, an
enormously beautiful and powerful subject with many applications in
computer graphics.   Some facility in the calculus of several
variables, and, of course, elementary vector analysis, would be the
prerequisites.  My two favorite books at the introductory level are
the ones by Dirk Struik, and by Barrett O'Neill. I'm not sure whether
either is still in print, but they, and others, should be available in
college libraries. 

Differential geometry actually defines four different notions of
curvature of a surface at a point, all involving the second partial
derivatives of a parametric representation, but in different ways:
normal curvatures, principal curvatures, mean curvature and Gaussian
curvature. 

Note the distinction between plurals and singulars:  A smooth surface
can have infinitely many normal curvatures at a point, one for each
possible tangent vector direction. It can have only two different
principal curvatures at each point, namely the maximum and minimum of
the normal curvatures.  But at each point it has only one mean
curvature (the average of the two principal curvatures) and one
Gaussian curvature (the product of the two principal curvatures). 

The Gaussian curvature is the most telling single surface shape
parameter at a point--it occurs in the statements of the deepest and
most powerful theorems of the differential geometry of surfaces. Its
generalization to the 4D space-time manifold of general relativity is
the famous "curvature" of the "curved space-time" that measures the
gravitational field, but I digress.

For a terrain in GIS (as opposed to an abstract surface in pure math),
you also have the notions of "up" and "horizontal", and it is  clear
that the intended meaning of "tangential curvature" has something to
do with how the surface is oriented with respect to "up". 

Re: [Algorithms] Tangential Curvature of terrain

[Thatcher U. <tu...@tu...>]

From: Ron Levine <ro...@do...>

> Klaus Hartmann  wrote:
>
> >Again, I've reached a point, where I wished that my math skills were
better.
> >At least I hope that the answer to my question is not too easy, so that
> >maybe some math guys are interested. I cannot even promise that I'll be
able
> >to follow your replies, but I'm sure someday I will (after re-reading,
> >re-re-reading, ... :)
> >
>
> See your calculus book for the notion of "concave up" vs "concave
> down" as applied to the graph of a function.  I would take issue with
> Ulrich's use of the term "convex" where I use "concave down", because
> it corresponds poorly with other important connotations in the usual
> meaning of the term "convex".

Fair enough, I abused the calculus terms.  In the context of a heightfield
for GIS though, "concave up" and "concave down" are less intuitive than
"concave" and "convex" in the geometric sense, since we're talking about a
solid (the earth) with a well defined inside and outside.

> [snip]

Thanks for the interesting curvature stuff.

--
Thatcher Ulrich
http://tulrich.com

[Algorithms] Rotation about arbitrary axis

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

Hi,

Since I needed a piece of code to do that I searched the web and found:
http://www.iuk.tu-harburg.de/hypgraph/modeling/mod_tran/3drota.htm

I used the final matrix at the bottom of the page, but it seems to fail when
the arbitrary axis actually is the Z axis. The third column gets erased
where it should at least contain a 1. This is obvious when looking at the
provided matrix, since the third column of the third row depends on the
rotation angle - and of course if the input axis already is the Z axis, it
shouldn't.

Now, it sounds normal regarding the underlying method (mapping the rotation
axis to Z, etc). But I wonder whether there's an easy way to perform a real
arbitrary rotation about any arbitrary axis without using different code
paths according to the input axis.

I think it can probably be done by introducing quaternions or better,
angle-axis, in the story. But err.... maybe there's something simpler.

Pierre

Re: [Algorithms] Rotation about arbitrary axis

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

Quaternions are the baby :)

Unit quaternions can be very simply mapped to / from an axis and angle.

If your axis of rotation is ( x , y , z ) and your angle is r, an associated
quaternion is

{ x * sin ( r / 2 ) , y * sin ( r / 2 ) , z * sin ( r / 2 ) , cos ( r / 2 ) }

There are 2 quaternions for any given axis and angle, because rotating around
the negative vector by the negative angle is equivalent to the original
rotation.

But I don't have any code for the stuff I can give away, I'm afraid :)

I'm sure there are plenty of references to appropriate stuff in the archives of
the list... if they're working. :)

Jamie


Pierre Terdiman wrote:

> Hi,
>
> Since I needed a piece of code to do that I searched the web and found:
> http://www.iuk.tu-harburg.de/hypgraph/modeling/mod_tran/3drota.htm
>
> I used the final matrix at the bottom of the page, but it seems to fail when
> the arbitrary axis actually is the Z axis. The third column gets erased
> where it should at least contain a 1. This is obvious when looking at the
> provided matrix, since the third column of the third row depends on the
> rotation angle - and of course if the input axis already is the Z axis, it
> shouldn't.
>
> Now, it sounds normal regarding the underlying method (mapping the rotation
> axis to Z, etc). But I wonder whether there's an easy way to perform a real
> arbitrary rotation about any arbitrary axis without using different code
> paths according to the input axis.
>
> I think it can probably be done by introducing quaternions or better,
> angle-axis, in the story. But err.... maybe there's something simpler.
>
> Pierre
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Rotation about arbitrary axis

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

Pierre Terdiman wrote
>
> Since I needed a piece of code to do that I searched the web and found:
>......
> I used the final matrix at the bottom of the page, but it seems to fail
when
> the arbitrary axis actually is the Z axis. The third column gets erased
> where it should at least contain a 1. This is obvious when looking at the
> provided matrix, since the third column of the third row depends on the
> rotation angle - and of course if the input axis already is the Z axis, it
> shouldn't.
>

I haven't checked this out, but it must be wrong because it is perfectly
possible to write down the matrix in a form such that it applies to any
ARBITRARY axis, including the z-axis.

> Now, it sounds normal regarding the underlying method (mapping the
rotation
> axis to Z, etc). But I wonder whether there's an easy way to perform a
real
> arbitrary rotation about any arbitrary axis without using different code
> paths according to the input axis.
>
> I think it can probably be done by introducing quaternions or better,
> angle-axis, in the story. But err.... maybe there's something simpler.

Absolutely.  You can do it entirely in terms of elementary vector geometry,
which I certainly regard as simpler, or at least more elemenary than
quaternions.

It is an instructive exercise in elementary vector geometry to derive the
following formula.  Let A be a unit vector that points along the axis of
rotation, let ang be the angle of rotation, and let V be any vector.  The
result of rotating V through angle ang about axis A is the vector

V' = cos(ang)V + (1-cos(ang)) (A dot V) A + sin(ang) A cross V

Notice that this is a vector formula.  You can apply it directly to rotate
any given
vector V.  Or if you want the matrix of this rotation with respect to any
given
coordinate system, simply express A in that coordinate system and
successively
substitute (1, 0, 0), (0, 1, 0), (0, 0,1) for V, and the nine elements of
the three values
you get for V', naturally, form the elements of the 3x3 rotation matrix.
Whether you
arrange these three V' vectors in rows or columns depends on which matrix
convention you are using.

Notice how esthetically satisfying is this vector formula:  it expresses the
result of the rotation in terms of V, A, and the simplest vector that can be
constructed from V and A that is (in  general) linearly independent of V and
A, namely A cross V.  It uses only the elementary vector operations of
vector addition, multiplication by a scalar, dot and cross product, and it
uses all of them.

As for the derivation of this vector formula for rotation about an arbitrary
axis,
start by resolving V into components parallel and perpendicular to A.
Clearly, rotation preserves vector sums so V' must be the sum of the images
of the components under the rotation.   The rotation of the perpendicular
component is rotation in a plane, which you know how to do from elementary
analytic gometry, You need to put all that together with some trig
identities, and, (this is the trickiest part of the derivation), the
following identity from elementary vector analysis, which you will find in
your calculus book
        A cross (B cross C) = (A dot C)B - (A dot B)C
(correct up to a sign that I can never remember).

(You can find the derivation of the vector rotation spelled out in
Goldstein's "Classical Mechanics".  Also pay attention that there is a sign
ambiguity of the sense of A coupled with the sign of ang and also the
handedness of your cross product rule.  The same ambiguity exists, of
course, in any quaternion formulation).

Re: [Algorithms] Rotation about arbitrary axis

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

Thanks everyone, I followed Paul Bourke's steps there and now it works:
http://www.swin.edu.au/astronomy/pbourke/geometry/rotate/

I suppose the matrix in my former link was wrong.


> Absolutely.  You can do it entirely in terms of elementary vector
geometry,
> which I certainly regard as simpler, or at least more elemenary than
> quaternions.

Agreed !


>         A cross (B cross C) = (A dot C)B - (A dot B)C
> (correct up to a sign that I can never remember).

Yup, we call that one the "double produit vectoriel" :)

Thanks Ron, this is always a pleasure to read from someone who enjoys what
he writes about.

P.

Re: [Algorithms] Rotation about arbitrary axis

[Thatcher U. <tu...@tu...>]

From: Pierre Terdiman <p.t...@wa...>
>
> Since I needed a piece of code to do that I searched the web and found:
> http://www.iuk.tu-harburg.de/hypgraph/modeling/mod_tran/3drota.htm
>
> I used the final matrix at the bottom of the page, but it seems to fail
when
> the arbitrary axis actually is the Z axis. The third column gets erased
> where it should at least contain a 1. This is obvious when looking at the
> provided matrix, since the third column of the third row depends on the
> rotation angle - and of course if the input axis already is the Z axis, it
> shouldn't.
>
> Now, it sounds normal regarding the underlying method (mapping the
rotation
> axis to Z, etc). But I wonder whether there's an easy way to perform a
real
> arbitrary rotation about any arbitrary axis without using different code
> paths according to the input axis.
>
> I think it can probably be done by introducing quaternions or better,
> angle-axis, in the story. But err.... maybe there's something simpler.

Here's what I use.  I'm sure it could be streamlined by expanded out the
quaternion stuff and simplifying.

class quaternion {
public:
 quaternion(const quaternion& q) : S(q.S), V(q.V) {}
 quaternion(float s, const vec3& v) : S(s), V(v) {}
 // [...]
 quaternion operator*(const quaternion& q) const;
 // [...]
 void ApplyRotation(vec3* result, const vec3& v);
private:
 float S;
 vec3 V;
};


vec3 Rotate(float Angle, const vec3& Axis, const vec3& Point)
// Rotates the given point through the given angle (in radians) about the
given
// axis.
{
 quaternion q(cos(Angle/2), Axis * sin(Angle/2));

 vec3 result;
 q.ApplyRotation(&result, Point);

 return result;
}

quaternion quaternion::operator*(const quaternion& q) const
// Multiplication of two quaternions.  Returns a new quaternion
// result.
{
 return quaternion(S * q.S - V * q.V, q.V * S + V * q.S + V.cross(q.V));
}


void quaternion::ApplyRotation(vec3* result, const vec3& v)
// Rotates the given vec3 v by the rotation represented by this quaternion.
// Stores the result in the given result vec3.
{
 quaternion q(*this * quaternion(0, v) * quaternion(S, -V)); // There's
definitely a shortcut here.  Deal with later.

 *result = q.V;
}


--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] Convexity [was Tangential Curvature of terrain]

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

Thatcher Ulrich wrote:

> From: Ron Levine <ro...@do...>
>>....
> > See your calculus book for the notion of "concave up" vs "concave
> > down" as applied to the graph of a function.  I would take issue with
> > Ulrich's use of the term "convex" where I use "concave down", because
> > it corresponds poorly with other important connotations in the usual
> > meaning of the term "convex".
>
> Fair enough, I abused the calculus terms.  In the context of a heightfield
> for GIS though, "concave up" and "concave down" are less intuitive than
> "concave" and "convex" in the geometric sense, since we're talking about a
> solid (the earth) with a well defined inside and outside.
>

Yes,  but that solid earth is not a convex body, not if it has any valleys.
True, you can slice off a solid convex cap under a region whose outer
surface is concave down, but without specifying that solid cap in its
entirety it is meaningless to use the term "convex".  If  it is not
meaningless to you, then you are certainly watering down a very powerful and
important term.

The point is that, in 3D,  convexity is a property of solids, not of
surfaces, certainly not a property of surface patches (except for convex
regions of PLANAR subspaces).  And it is a global property, not a local
property.  And it is an extremely important global property--many powerful
theorems or algorithms are true for convex solids in space (or convex
regions of a plane) but not true of non-convex bodies (*).  On the other
hand, the properties of "concave up"  and "concave down"  are local
properties, rather than global properties; they are properties of surface
patches, not of solids.

So by using "convex" in the way that you did, as a local property of surface
patches, you are muddying or watering down a very important nomenclature, a
nomenclature with powerful connotations, connotations which do not hold at
all for the sense in which you are using the term.  It is that abuse of an
important term with which I take issue, no matter how you may justify it to
yourself.

The words you use are important.  Mathematics is nothing more nor less than
the discipline of using language with precision. Elegant and useful
mathematics requires choosing definitions to have consequence.  Your use of
"convex" violates that principle.

(*) Just a couple of examples from collision detection:  GJK applies to all
convex solids, but to no non convex solids.    The Separating Axis Theorem
applies to all convex polyhedra, but to no non convex polyhedra.  There are
many many more examples in both pure and applied geometry.

Re: [Algorithms] Convexity [was Tangential Curvature of terrain]

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

I  wrote:

>
>The point is that, in 3D,  convexity is a property of solids, not of
>surfaces, certainly not a property of surface patches (except for convex
>regions of PLANAR subspaces).  And it is a global property, not a local
>property.  And it is an extremely important global property--many powerful
>theorems or algorithms are true for convex solids in space (or convex
>regions of a plane) but not true of non-convex bodies (*).  On the other
>hand, the properties of "concave up"  and "concave down"  are local
>properties, rather than global properties; they are properties of surface
>patches, not of solids.
>
>.....
>
>The words you use are important.  Mathematics is nothing more nor less than
>the discipline of using language with precision. Elegant and useful
>mathematics requires choosing definitions to have consequence. 
 
To be a little more explicit, for the non-mathematicians who may not
be familiar with it, the standard mathematical definition of "convex"
is as follows:
 
" A set (i.e., any set of points) in a Euclidean space (of any
dimension) is convex if for any two points in the set the line segment
joining them lines entirely within the set".

This is the definition with consequence, the definition that leads to
all the nice properties of convex sets that we know and love.  The
concave down surface patches that Thatcher was discussing in the post
in question, considered as point sets,  cannot be understood to
satisfy this definition in any sense.  They have none of the nice
properties that are normally connoted by the term.

Re: [Algorithms] Tangential Curvature of terrain

[Klaus H. <k_h...@os...>]

Thather, and Ron... Thanks a lot for your replies :)

From: Ron Levine <ro...@do...>
> Only if you can  better explain what is meant by "tangential
> curvature", not a standard mathematical term. It might be a standard
> GIS term, but  I could not find a real definition of the term on the
> uiuc GIS site that you cite.  The image you cite, at first sight,
> suggests to me a couple of possible definitions, but on closer
> examination of its coloring I can eliminate one, and am left with one
> guess:

I knew you would say that, and I cannot blame you :) It took me almost half
a year to find the technical term for what I'm trying to do. Now that I know
that it's called tangential curvature (which is an obsolete name for
meridional curvature) I'm at least able to find some information on the
net... but not too much.

A hopefully good definition of tangential curvature (as used in GIS) can be
found here:
http://www.orbtek.com/glossary/definitions/tangentialcurvature.html

I'm now trying to give you a brief overview of how those GIS people compute
the tangential curvature, and after that I'll briefly explain why I'd like
to implement this.

[1] Tangential curvature

Unfortunately, I'm not a mathematician, and I can only *try* to summarize
what a certain GIS paper says. Basically, I'll just copy some parts of the
paper. I hope that it's enough for you to understand.

"
Surface geometry can be analyzed efficiently when the surface is
interpolated with a bivariate function z = f(x, y), that is continuous up to
second order derivatives and when parameters characterizing surface
geomoetry (topographic parameters) are expressed VIA derivates of this
function. This approach is demonstrated on the computation of basic
topographic parameters: slope, aspect, profile curvature, plan curvature,
tangential curvature, and on the computation of flow path length.
Before deriving mathematical expressions for these parameters, using the
basic principles of differential geometry, the following simplifying
notations are introduced:

fx = Dz/Dx
fy = Dz/Dy
fxx = (D^2)z/Dx^2
fyy = (D^2)z/Dy^2
fxy = (D^2)z/(DxDy)

and

p = (f^2)x + (f^2)y
q = p + 1
"
(Note, that I'm using a capital 'D' here, where the paper uses the Greek
letter delta). Unfortunately, we used a different notation in school. So I
can only guess, that fx and fy are first derivatives, and fxx, fyy, fxy are
second derivatives. But we never differentiated bivariate functions (which
is my biggest problem).

"
For the study of flow divergence/convergence, it is more appropriate to
introduce a curvature measured in the normal plane in the direction
perpendicular to gradient. This curvature will be called here a tangential
curvature because the direction perpendicular to gradient is, in fact, the
direction of tangent to contour at a given point. Equations for these
curvatures can be derived using the general equation for curvature K of a
plane section through a point on a surface:

K = (fxx * cos^2(B1) + 2*fxy*cos(B1)*cos(B2) + fyy*cos^2(B2)) / (sqrt(q) *
cos L)

where L (lamdba) is the angle between the normal to the surface at a given
point and the section plane; B1 (beta 1), B2 (beta 2) are angles between the
tangent of the given normal section at a point and axes x, y, respectively.
"

Whatever that means... And then, a bit later in the text, they give the
formula for tangential curvature:

"The equation for tangential curvature Kt at a given point is derived as the
curvature of normal plane section in a direction perpendicular to gradient
(direction of tangent to the contour line) after setting

cos L = 1
cos B1 = fy / sqrt(p)
cos B2 = -fx / sqrt(p)

and

Kt = (fxx*fy^2 - 2*fxy*fx*fy + fyy*fx^2) / (p * sqrt(q))
"

I only understand fractions of the above, and that's why I'm not able to
implement it.

[2] What I want to do...

Assume that you wanted to synthesize a texture for a height field. A simple
approach is to make each texel's color depend on the elevation E of the
corresponding data point P in the height field. For example, you could say
"Use snow, if the elevation E falls above a lower elevation limit H (say
1000 meters). If E <= H, then just use rock.".

If I now knew the tangantial curvature, T, (as a scalar) at the data point
P, then I could modify the elevation H in the following fashion:
H' = H - T * D,

where D is some scaling factor that increases/decreses the effect (negative
T means convex up, and positive T means concave down). My new classification
would now become: "Use snow, if the elevation E falls above a lower
elevation limit H' (say 1000 meters). If E <= H', then just use rock.".

Using such an approach, I can make the flow of the snow care about the shape
of the terrain. For example, I can make tongues of snow that flow from the
peak of a mountain, through concave down areas, all the way into the valley.
At the same time, the rock 'flows' from the valley, over convex up areas,
towards the peak.

No need to say, that this produces very realistic effects. In Questar
Productions' World Construction Set 2, for example, they call this the
'relative elevation effect'.


Also, thanks for the other pointers you gave. I'll not comment on them now,
because I'd like think about them, before I say something stupid :)

Thanks,
Niki

Re: [Algorithms] Tangential Curvature of terrain

[Klaus H. <k_h...@os...>]

Here are few images that hopefully explain the effect I'd like to achieve
(just in case that I speak Klingon :).

The three images show exactly two non-living ecosystems, namely sand and
rock.

ECO1.JPG:
http://www.thecore.de/TheCore/eco1.jpg

In this image the distribution of the ecosystems is based on elevation only.
Looks ugly :)

ECO2.JPG
http://www.thecore.de/TheCore/eco2.jpg

This image adds some pseudo-tangential-curvature effect. Well, it's not
really a tangential curvature effect, but rather a hack, and that's why the
image doesn't look as good as it could. Anyway, the image shows, that rock
tends to prefer convex up areas, whereas sand tends to prefer concave down
areas. This basically is as if the wind blew the sand from the convex up
areas and collects it in concave down ares.

ECO3.JPG
http://www.thecore.de/TheCore/eco3.jpg

This is for interested people only... It adds eleveation skewing to
ECO2.JPG. It basically simulates a certain wind direction. Note, how the
sand prefers the east side of the hills and moutains.

Also note, that there are only two colors (lit colors) in these images. This
should give you some idea of the power of such algorithms. Look at the big
picture with more than two ecosystems, and actual ecosystem base texture
(images).

Niki

RE: [Algorithms] Multithreading with Hardware Acceleration

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

Thanks guys. I was only planning on about ~3-4 threads(input+networking, file, video, main, (sound?))

Each thread has a threadsafe queue. Then to communicate with it I just send it a message throught the queue(like a pointer to where the data is it need to do it's work. 

I was once playing with WildTangets Gamedriver and profiled the 'explore' sample app to see where all the CPU time went. Just about all of it was spent in the nVidia driver, so I was betting that they were just doing a whole bunch of waits as bits were being rendered. 

Tom, while your way is correct (sleep(0) to return control to the OS to reschedule), and is a nice way of doing it, shouldn't the scheduler still switch to another thread if one is waiting and is of the same or higher priority? 

The reason I'm interested in this is that it'll give gains on single processors as well as the dual's.

Chris

-----Original Message-----
From: Charles Bloom [mailto:cb...@cb...]
Sent: Monday, 21 August 2000 2:22 PM
To: gda...@li...
Subject: RE: [Algorithms] Multithreading with Hardware Acceleration



Of note here is the famed Windows 9x anomaly of rapid decreases in
performance when the running thread count goes over 32 (roughly).
NT and 2k seem (relatively) free of this problem.

At 05:02 AM 8/21/00 +0100, you wrote:
>Some people go mad with threads and create them all over the place, e.g. one
>for each AI character. That's possibly a little over the top, but can work.
>You need to beware of the pitfalls of threading as well as the advantages,
>but it sounds like you're aware of some of the problems already.

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com


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

RE: [Algorithms] Multithreading with Hardware Acceleration

[Tom F. <to...@mu...>]

The Sleep(0) explicitly gives up the rest of the thread's timeslice to other
threads. So even if two threads are at the same priority, the other one will
get most of the CPU time, instead of spending half of it spinning tightly.
It's a way of surrendering time you don't need - sort of manually lowering
your priority, but with very fine-grained control.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day. 
-----Original Message-----
From: Chris Brodie [mailto:Chr...@ma...]
Sent: 21 August 2000 05:50
To: 'gda...@li...'
Subject: RE: [Algorithms] Multithreading with Hardware Acceleration


Thanks guys. I was only planning on about ~3-4 threads(input+networking,
file, video, main, (sound?)) 
Each thread has a threadsafe queue. Then to communicate with it I just send
it a message throught the queue(like a pointer to where the data is it need
to do it's work. 
I was once playing with WildTangets Gamedriver and profiled the 'explore'
sample app to see where all the CPU time went. Just about all of it was
spent in the nVidia driver, so I was betting that they were just doing a
whole bunch of waits as bits were being rendered. 
Tom, while your way is correct (sleep(0) to return control to the OS to
reschedule), and is a nice way of doing it, shouldn't the scheduler still
switch to another thread if one is waiting and is of the same or higher
priority? 
The reason I'm interested in this is that it'll give gains on single
processors as well as the dual's. 
Chris 

RE: [Algorithms] Multithreading with Hardware Acceleration

[Matt A. <de...@gm...>]

btw, why is everyone using sleep(0) instead of switchtothread ?
since some of my threads do have an different priority, it seems
to be better to give (especially the higher-priority threads )
part of the regained time, too.
Are there disadvantages in using switchtothread (is it slower, etc.) ?

Matt

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Tom
Forsyth
Sent: Montag, 21. August 2000 07:13
To: gda...@li...
Subject: RE: [Algorithms] Multithreading with Hardware Acceleration


The Sleep(0) explicitly gives up the rest of the thread's timeslice to other
threads. So even if two threads are at the same priority, the other one will
get most of the CPU time, instead of spending half of it spinning tightly.
It's a way of surrendering time you don't need - sort of manually lowering
your priority, but with very fine-grained control.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.
-----Original Message-----
From: Chris Brodie [mailto:Chr...@ma...]
Sent: 21 August 2000 05:50
To: 'gda...@li...'
Subject: RE: [Algorithms] Multithreading with Hardware Acceleration


Thanks guys. I was only planning on about ~3-4 threads(input+networking,
file, video, main, (sound?))
Each thread has a threadsafe queue. Then to communicate with it I just send
it a message throught the queue(like a pointer to where the data is it need
to do it's work.
I was once playing with WildTangets Gamedriver and profiled the 'explore'
sample app to see where all the CPU time went. Just about all of it was
spent in the nVidia driver, so I was betting that they were just doing a
whole bunch of waits as bits were being rendered.
Tom, while your way is correct (sleep(0) to return control to the OS to
reschedule), and is a nice way of doing it, shouldn't the scheduler still
switch to another thread if one is waiting and is of the same or higher
priority?
The reason I'm interested in this is that it'll give gains on single
processors as well as the dual's.
Chris

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

Re: [Algorithms] Multithreading with Hardware Acceleration

[Timur D. <ti...@3d...>]

SwitchToThread only supported on NT and 2k, good enough reason to not use it
in games.

_______________________
 Timur Davidenko.
 3Dion Inc. (www.3dion.com)
 e-mail: ti...@3d...


----- Original Message -----
From: "Matt Adams" <de...@gm...>
To: <gda...@li...>
Sent: Monday, August 21, 2000 12:03 PM
Subject: RE: [Algorithms] Multithreading with Hardware Acceleration


> btw, why is everyone using sleep(0) instead of switchtothread ?
> since some of my threads do have an different priority, it seems
> to be better to give (especially the higher-priority threads )
> part of the regained time, too.
> Are there disadvantages in using switchtothread (is it slower, etc.) ?
>
> Matt
>
> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of Tom
> Forsyth
> Sent: Montag, 21. August 2000 07:13
> To: gda...@li...
> Subject: RE: [Algorithms] Multithreading with Hardware Acceleration
>
>
> The Sleep(0) explicitly gives up the rest of the thread's timeslice to
other
> threads. So even if two threads are at the same priority, the other one
will
> get most of the CPU time, instead of spending half of it spinning tightly.
> It's a way of surrendering time you don't need - sort of manually lowering
> your priority, but with very fine-grained control.
>
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
> -----Original Message-----
> From: Chris Brodie [mailto:Chr...@ma...]
> Sent: 21 August 2000 05:50
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Multithreading with Hardware Acceleration
>
>
> Thanks guys. I was only planning on about ~3-4 threads(input+networking,
> file, video, main, (sound?))
> Each thread has a threadsafe queue. Then to communicate with it I just
send
> it a message throught the queue(like a pointer to where the data is it
need
> to do it's work.
> I was once playing with WildTangets Gamedriver and profiled the 'explore'
> sample app to see where all the CPU time went. Just about all of it was
> spent in the nVidia driver, so I was betting that they were just doing a
> whole bunch of waits as bits were being rendered.
> Tom, while your way is correct (sleep(0) to return control to the OS to
> reschedule), and is a nice way of doing it, shouldn't the scheduler still
> switch to another thread if one is waiting and is of the same or higher
> priority?
> The reason I'm interested in this is that it'll give gains on single
> processors as well as the dual's.
> Chris
>
> _______________________________________________
> 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
>