gdalgorithms-list

RE: [Algorithms] rather odd

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

I think it just doesn't work. I've been referred to the archives a few times re my questions on VIPM's. Do a search on VIPM and you get back nothing. 

(Apologies for the HTML if you see it. My mail department says your not getting it :) )

-----Original Message-----
From: Akbar A. [mailto:sye...@ea...]
Sent: Wednesday, 23 August 2000 8:49 AM
To: gda...@li...
Subject: [Algorithms] rather odd
is the search feature of the list broken?
i did a search forbarycentric
and i found nothing.

i am pretty sure that word has been mentioned before ;)
http://www.geocrawler.com/lists/3/SourceForge/4856/0/

peace.
akbar A.

"US4643421: Video game in which a host image repels ravenous images by
serving filled vessels "
http://www.patents.ibm.com/details?&pn10=US04643421
this was a fun game though ;)




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

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
>

[Algorithms] rather odd

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

is the search feature of the list broken?
i did a search for
barycentric
and i found nothing.

i am pretty sure that word has been mentioned before ;)
http://www.geocrawler.com/lists/3/SourceForge/4856/0/


peace.
akbar A.

"US4643421: Video game in which a host image repels ravenous images by
serving filled vessels "
http://www.patents.ibm.com/details?&pn10=US04643421
this was a fun game though ;)

RE: [Algorithms] Tangential Curvature of terrain

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

> -----Original Message-----
> From: Klaus Hartmann [mailto:k_h...@os...]
>
> 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).
> 

That would provide you with finding a single bump or pit in a flat, level
surface.  If it's on a mountain slope then the average may give you a flat
surface instead of a large outcropping or cave that may exist there.  I
don't use height maps and don't know what Pm,n stands for, but you are on
the right track using the difference between the heights of each point.

In reality our eyes determine curvature and slope in kinda the following:

Spot three points X1, X2, X3 equidistant along the line of sight and judge
height H1, H2, H3 at each point.  Visually check H3-H1 and then visually
check H2-H1 and H3-H2.  In the general case if (H2-H1)/(X2-X1) is greater
than (H3-H1)/(X3-X1) then there's a bump (convex), if they are equal then
it's flat, if it's less then a pit (concave).  Where (X2-X1) = (X3-X2) = 1/2
(X3-X1) then just compare (H2-H1) * 2 with (H3-H1). Note that we don't need
to check between X2 and X3.

Hope that helps...otherwise I might start saying stuff like the second
derivative is negative for bumps (convex) and positive for pits (concave).
;)

Steve

Re: [Algorithms] Geodesic Sphere

[Adam M. <amo...@dp...>]

The classic way to subdivide quadruples your number of triangles with every
step.  You might find Leif Kobbelt's sqrt(3) subdivision paper from this
year's siggraph interesting.  While the paper focuses on subdivision
surfaces, he describes a method of subdividing which could be applied to
arbitrary problems of tessellation.  His approach triples the number of
triangles with every step, allowing for finer LOD control.  It is in fact
very simple -- I would be surprised if no one was using this scheme before
him.

--
--Adam Moravanszky
http://www.n.ethz.ch/student/adammo

-----Original Message-----
From: Dave Eberly <eb...@ma...>
To: gda...@li...
<gda...@li...>
Date: Tuesday, August 22, 2000 3:11 PM
Subject: Re: [Algorithms] Geodesic Sphere


>From: "Aldo ." <al...@ho...>
>> I'm looking for an algoritm to create a geodesic sphere(is the name
>> correct?), a sphere made of equilateral triangles. I would be nice if I
>> could choose the resolution(more or less triangles).
>
>From: "Peter Warden" <Pet...@vi...>
>> Here's a link I've used (found on Dave Eberly's site,
>> www.magic-software.com, in the Other Links section);
>>
>> http://forum.swarthmore.edu/dr.math/problems/matz12.15.96.html
>
>Or you could just use the code (with MS Windows test program)
>at http://www.magic-software.com/gr_dcmp.htm , section with
>files sphrtesl.{h,cpp,pdf} and sptstest.cpp.  The tessellation is
>by recursive subdivision.  You start with any inscribed convex
>polyhedron.  If you want the 'classic' cases, start with an
>octahedron (part of the sptstest program) or an icosahedron.
>
>--
>Dave Eberly
>eb...@ma...
>http://www.magic-software.com
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] Geodesic Sphere

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

This problem is difficult since all three sides of all triangles will be
equal.  It requires dividing a sphere longitudinally by X number of
triangles while dividing it laterally by Xsin(pi/3) = X * [sqr(3)/2] and
where sqr(3)/2 * X is a whole number or whole fraction...and offhand I can't
think of any whole number X where multiplying it by sqr(3)/2 will result in
something like 8 or 1/2.

I suggest using isosceles triangles since the algorithm is much simpler and
I posted it earlier concerning spherical texture mapping...here's a clip
from it (yes it's in basic...hope you can read it):

For example here's how I create a sphere:

Dim pi as single
Dim pi2 as single

Dim spherecount as long
Dim spherename() As String
Dim spherevertexcount As Long

Dim sphereradius(1) As Single
Dim spherecenter(1) As D3DVERTEX
Dim spheredx7vertex(1100) As D3DVERTEX

pi=3.14159265
pi2=pi * 2

spherecount = 1
spherename(1) = "Sphere 1"
spherecenter(1).x = 0
spherecenter(1).y = 4
spherecenter(1).z = 6
sphereradius(1) = 1			'radius

c = 16	'number of sections...smaller c means larger triangles, larger c
means smaller triangles
b = 0
For cameraangle.x = 0 To pi * (c - 1) / c + 0.0001 Step pi / c
 For cameraangle.y = 0 To pi2 + 0.0001 Step pi / c
  b = b + 1
  dx7.CreateD3DVertex sphereradius(1) * Sin(cameraangle.y) *
Sin(cameraangle.x) + spherecenter(1).x, sphereradius(1) * Cos(cameraangle.x)
+ spherecenter(1).y, sphereradius(1) * Cos(cameraangle.y) *
Sin(cameraangle.x) + spherecenter(1).z, Sin(cameraangle.y) *
Sin(cameraangle.x), Cos(cameraangle.x), Cos(cameraangle.y) *
Sin(cameraangle.x), cameraangle.y / pi2, cameraangle.x / pi,
spheredx7vertex(b)
  b = b + 1
  dx7.CreateD3DVertex sphereradius(1) * Sin(cameraangle.y) *
Sin(cameraangle.x + pi / c) + spherecenter(1).x, sphereradius(1) *
Cos(cameraangle.x + pi / c) + spherecenter(1).y, sphereradius(1) *
Cos(cameraangle.y) * Sin(cameraangle.x + pi / c) + spherecenter(1).z,
Sin(cameraangle.y) * Sin(cameraangle.x + pi / c), Cos(cameraangle.x + pi /
c), Cos(cameraangle.y) * Sin(cameraangle.x + pi / c), cameraangle.y / pi2,
(cameraangle.x + pi / c) / pi, spheredx7vertex(b)
 Next
Next

spherevertexcount = b
vertexperstrip = c * 4 + 2

d3d7device.SetTexture 0, dd7surface(7)  'sphere
For b = 1 To spherevertexcount - vertexperstrip + 1 Step vertexperstrip
 Call d3d7device.DrawPrimitive(D3DPT_TRIANGLESTRIP, D3DFVF_VERTEX,
spheredx7vertex(b), vertexperstrip, D3DDP_DEFAULT)
Next



> -----Original Message-----
> From: Aldo . [mailto:al...@ho...]
> Sent: Tuesday, August 22, 2000 5:45 AM
> To: gda...@li...
> Subject: [Algorithms] Geodesic Sphere
> 
> 
> 
> Hi!
> 
> I'm looking for an algoritm to create a geodesic sphere(is the name 
> correct?), a sphere made of equilateral triangles. I would be 
> nice if I 
> could choose the resolution(more or less triangles).
> 
> 
> 
> Thanks in advance.
> 
> Aldo Spanghero
> 
> 
> ______________________________________________________________
> __________
> Get Your Private, Free E-mail from MSN Hotmail at 
http://www.hotmail.com


_______________________________________________
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] Massive spaces

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

(1) Not as long as your partitions in dvMinZ, dvMaxZ don't overlap, though
that is another way of getting even more precision. But it chews fillrate.
It's not usually necessary.

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

> -----Original Message-----
> From: Sam Kuhn [mailto:sa...@ip...]
> Sent: 21 August 2000 13:28
> To: gda...@li...
> Subject: Re: [Algorithms] Massive spaces
> 
> 
> Thanks for the info tom, exactly what I wanted to hear. A couple of
> questions:
> 
> 1) Interesting.. do you have to clear the zbuffer when rendering each
> partition?
> 
> 2) Yeah, but if you nail all distant objects to the back clip 
> plane, they
> have the same z and consequently the same parallax. dont 
> they? I guess I
> could treat the back of the view volume as the back of the 
> galaxy, and nail
> the objects into the view volume at their relevant scaled 
> positions. That
> should work.
> 
> 3) Your dead right dude, I tried this yesterday after I sent 
> the mail...
> works very nicely! ;)
> 
> Cheers,
> 
> Sam.
> 
> 
> -----Original Message-----
> From: Tom Forsyth <to...@mu...>
> To: gda...@li...
> <gda...@li...>
> Date: 21 August 2000 2:59 AM
> Subject: RE: [Algorithms] Massive spaces
> 
> 
> >(1) Partition your Z buffer. In D3D this is done using the dvMinZ and
> dvMaxZ
> >values in the viewport. There is a pretty direct equivalent 
> in OpenGL - I
> >forget what it's called. Then you can even out your precision quite
> happily.
> >
> >(2) They're planets. Big spherical things. And they don't (usually -
> depends
> >what sort of game you are doing I guess :-) actually 
> intersect in space.
> >Possibly nothing in the universe is easier to sort from back 
> to front and
> >draw that way. So you can nail them to the far clip plane, 
> set your Z test
> >to LESSTHAN, and there you go.
> >
> >(3) Move your near clip plane according to the nearest 
> object. So if you
> are
> >on a planet's surface, the near clip plane is quite close. If you are
> >zooming about in space, it's millions of miles away.
> >
> >By using all these three, you can get huge spaces done pretty easily.
> >
> >If the archives are working, this has been discussed a fair number of
> times.
> >
> >Tom Forsyth - Muckyfoot bloke.
> >Whizzing and pasting and pooting through the day.
> >-----Original Message-----
> >From: Sam Kuhn [mailto:sa...@ip...]
> >Sent: 21 August 2000 02:33
> >To: gda...@li...
> >Subject: [Algorithms] Massive spaces
> >
> >
> >Hey,
> >
> >I've got a little mind game for you lot.
> >
> >Say you needed to render an entire solar system, in which 
> you can zoom down
> >to a planet surface and see detail of about 1/100000 meter, 
> or shoot over
> to
> >the sun and see the same sort of detail. There are a couple 
> of immediate
> >problems:
> >
> >You would need need an enormous view volume (what say 20 
> lightyears big)
> >which gives an appauling zbuffer resolution.
> >So whats are you to do? Render the distant objects closer than they
> actually
> >are (i.e. at the far end of a planet-sized view volume) and 
> scale them down
> >accordingly?. This surely would give incorrect parralax 
> between the distant
> >objects
> >
> >Also you need the planets to be of enormous size so that the 
> front clipping
> >plane doesn't cut through the planets fine detail when you 
> are in very
> close
> >(lets say an ant view for example). Which again buggers the 
> zbuffer, since
> >you're using a planet sized view volume.
> >
> >Any ideas?
> >
> >Regards,
> >
> >Sam.
> >
> >
> >
> >_______________________________________________
> >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] N-body processing

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

> A lozenge looks like an OBB that is 'rounded' at the
> edges and corners.  You effectively have the same

Wouldn't it be a Rectangle Swept Sphere, a.k.a. RSS ?
A lozenge looks like a 2D thing to me (I mean, "un losange" in French
couldn't possibly be a bounding volume. Hence my confusion.)

But now I understand, since RSS are good candidates indeed.

Pierre

Re: [Algorithms] Geodesic Sphere

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

From: "Robert Dibley" <RD...@ac...>
> I don't think the geodesic is made of equilateral triangles ... in fact I
> believe the only solid of vaguely spherical shape that you can make with
> equilateral triangles is the icosahedron (20 tri's)

Yes.  The code I mentioned in an earlier post generates a
mesh of triangles that are not equilateral.  But a related
question might be the following.  Given a scalar function
that determines how 'close' a triangle is to equilateral, can
you construct a triangle mesh such that all its triangles
have metric smaller than a prescribed tolerance?  Such
a scalar function is F(T) = sum_{i=1}^3 |A_i - pi/3|^2 where
the A_i are the angles of the triangle T.  Or maybe a function
that is zero when all three sides have same length, positive
otherwise.  Or a combination of the two.

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

Re: [Algorithms] Geodesic Sphere

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

From: "Aldo ." <al...@ho...>
> I'm looking for an algoritm to create a geodesic sphere(is the name 
> correct?), a sphere made of equilateral triangles. I would be nice if I 
> could choose the resolution(more or less triangles).

From: "Peter Warden" <Pet...@vi...>
> Here's a link I've used (found on Dave Eberly's site,
> www.magic-software.com, in the Other Links section);
> 
> http://forum.swarthmore.edu/dr.math/problems/matz12.15.96.html

Or you could just use the code (with MS Windows test program)
at http://www.magic-software.com/gr_dcmp.htm , section with
files sphrtesl.{h,cpp,pdf} and sptstest.cpp.  The tessellation is
by recursive subdivision.  You start with any inscribed convex
polyhedron.  If you want the 'classic' cases, start with an
octahedron (part of the sptstest program) or an icosahedron.

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

RE: [Algorithms] Geodesic Sphere

[Robert D. <RD...@ac...>]

I don't think the geodesic is made of equilateral triangles ... in fact I
believe the only solid of vaguely spherical shape that you can make with
equilateral triangles is the icosahedron (20 tri's)

Apart from that I can't help, but I'd have thought a quick search on the web
would throw up several.

Robert

> -----Original Message-----
> From: Aldo . [mailto:al...@ho...]
> Sent: 22 August 2000 13:45
> To: gda...@li...
> Subject: [Algorithms] Geodesic Sphere
> 
> 
> 
> Hi!
> 
> I'm looking for an algoritm to create a geodesic sphere(is the name 
> correct?), a sphere made of equilateral triangles. I would be 
> nice if I 
> could choose the resolution(more or less triangles).
> 
> 
> 
> Thanks in advance.
> 
> Aldo Spanghero
> 
> 
> ______________________________________________________________
> __________
> Get Your Private, Free E-mail from MSN Hotmail at 
http://www.hotmail.com


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

RE: [Algorithms] Geodesic Sphere

[Peter W. <Pet...@vi...>]

Here's a link I've used (found on Dave Eberly's site,
www.magic-software.com, in the Other Links section);

http://forum.swarthmore.edu/dr.math/problems/matz12.15.96.html

> I'm looking for an algoritm to create a geodesic sphere(is the name 
> correct?), a sphere made of equilateral triangles. I would be 
> nice if I 
> could choose the resolution(more or less triangles).
> 
> Aldo Spanghero

[Algorithms] Geodesic Sphere

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

Hi!

I'm looking for an algoritm to create a geodesic sphere(is the name 
correct?), a sphere made of equilateral triangles. I would be nice if I 
could choose the resolution(more or less triangles).



Thanks in advance.

Aldo Spanghero


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

RE: [Algorithms] fast triangle-segment test *with precomputation*

[Robert D. <RD...@ac...>]

> This third test is done because of the possibility of a 
> triangle location which has 
> 
> 1) No vertices inside the box
> 2) No edges which intersect any box face
> 
> In this case I compute 4 ( you are right, I overestimated 
> when I tried to visualise this! :) ) line segments and test if these 
> intersect the face of the triangle.
> 
> Having just looked at your reply you are also right in that 4 
> parallel box edges would do exactly the same thing as 4 diagonal lines.

Actually this is not true ... if the triangle was also parallel to the
chosen four parallel box edges, then it could fall between all of them, not
intersect with any of them, and yet still intersect with the box.

The four diagonal lines on the other hand will cover every possible case,
since it is impossible for a plane to pass through the cube without crossing
at least one diagonal somewhere.

Robert

RE: [Algorithms] visualizing frustum planes?

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

i haven't been following this thread to closely.
but.
nate robbins has made a set of tutorials for all the eye camera,
tweakable settings, "learning material",  etc..
if you look on google you are sure to find his site.
he is also mentioned in the red book as well.
prob in the beg < pg 30 .?

heh-
i'm sure someone has already told you about him.
sorry if it's a repeat.



peace.
akbar A.

"We want technology for the sake of the story, not for its own sake. When
you look back, say 10 years from now, current technology will seem quaint"
Pixars' Edwin Catmull.


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
Pallister, Kim
Sent: Tuesday, August 22, 2000 12:39 AM
To: gda...@li...
Subject: RE: [Algorithms] visualizing frustum planes?


Also, if you are on DX7 or OpenGL 1.1, you can download the eval version of
GPT from Intel's web site. It include's a 'wide angle' and 'reverse wide
angle' view that will do this transparently for you. Just run the EXE
through it and voila.

Kim Pallister

We will find a way or we will make one.
                     - Hannibal


> -----Original Message-----
> From: Michael S. Harrison [mailto:mic...@ud...]
> Sent: Monday, August 21, 2000 11:31 AM
> To: gda...@li...
> Subject: Re: [Algorithms] visualizing frustum planes?
>
>
> Duh.  This is precisely the reason I like working on teams
> where more than one person is familiar with a given system.
> Sometimes having someone state the obvious is a good kick in the seat.
>
> It hadn't even occurred to me to use an artificial model
> matrix and draw the simulated frustum planes, in order to
> check (and help visualize) the camera math
>
> At 07:10 PM 8/21/00, you wrote:
> >Hey,
> >
> >Here's a piece of code which will render the camera frustum,
> which I find to
> >be useful when hunting camera problems. It works best when
> viewed from a
> >second camera though (since the frustum is mostly clipped by the very
> >frustum planes it is meant to visualize), with the AABB
> culling code (or
> >whatever you may end up using it for) hardwired to the first
> camera - only,
> >the second camera should just render everything, or only
> rely on culling
> >code of which you're certain that it works.
> >
> >----8<----
> >  float     ax, ay, bx, by, fx, fy;
> >  static Vertex verts[8];
> >  static ushort indices[24] = {
> >   0,1, 1,2, 2,3, 3,0,
> >   4,5, 5,6, 6,7, 7,4,
> >   0,4, 1,5, 2,6, 3,7
> >  };
> >
> >   // Calculate fov/2 angles in x and y direction.
> >  ax = mFov / 2;
> >  ay = ax * ((float) mViewport.height / (float) mViewport.width);
> >   // Calculate x/y coordinates of the front plane.
> >  fx = mFront * (float) tan(ax);
> >  fy = mFront * (float) tan(ay);
> >   // Calculate x/y coordinates of the back plane.
> >  bx = mBack * (float) tan(ax);
> >  by = mBack * (float) tan(ay);
> >   // Setup frustum verts.
> >  verts[0].loc.set(-fx, +fy, mFront);
> >  verts[1].loc.set(+fx, +fy, mFront);
> >  verts[2].loc.set(+fx, -fy, mFront);
> >  verts[3].loc.set(-fx, -fy, mFront);
> >  verts[4].loc.set(-bx, +by, mBack);
> >  verts[5].loc.set(+bx, +by, mBack);
> >  verts[6].loc.set(+bx, -by, mBack);
> >  verts[7].loc.set(-bx, -by, mBack);
> >  for (short i = 0; i < 8; i++)
> >   verts[i].color = Color3(0.8f, 0.8f, 0.8f);
> >   // Render frustum.
> >  GfxDevice->SetTransform(eTransformWorld, mMatrix);
> >  GfxDevice->Draw(GfxDevice::PrimLineList, verts, 8, indices, 24);
> >----8<----
> >
> >If you have any questions about the specifics of the above
> code, mail me
> >offline.
> >
> >HTH
> >
> >Jim Offerman
> >
> >Innovade
> >- designing the designer
> >----- Original Message -----
> >From: "Michael S. Harrison" <mic...@ud...>
> >To: <gda...@li...>
> >Sent: Monday, August 21, 2000 9:18 AM
> >Subject: [Algorithms] visualizing frustum planes?
> >
> >
> >> I'm attempting to implement the AABB culling code talked
> about here some
> >time ago and I'm running into a general problem in
> visualizing the frustum
> >planes used to cull objects based on their AABB's
> >>
> >> I'm using both Klaus Hartmann's AABBCull sample and the
> Viewcull sample
> >included with the OpenGL FAQ.
> >>
> >> While the code generally works, I'm having some difficulty
> visualizing the
> >relationship between the plane vector and the "distance"
> value stored with
> >it, which I'm sure is the reason I can't quite figure out
> why the code
> >generates intersection results when it should generate a full cull.
> >>
> >> As you might guess, I'm fairly new to the world of 3d
> projection and I'm
> >still wrapping my mind around all the transformations that
> take an object
> >from "world" space to screen space.
> >>
> >> Can anyone suggest a reference or way to visualize exactly
> what's going on
> >with the plane extraction and how the vectors relate back to
> the AABB?
> >>
> >>
> >> _______________________________________________
> >> 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
>
>
> _______________________________________________
> 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] visualizing frustum planes?

[Pallister, K. <kim...@in...>]

Also, if you are on DX7 or OpenGL 1.1, you can download the eval version of
GPT from Intel's web site. It include's a 'wide angle' and 'reverse wide
angle' view that will do this transparently for you. Just run the EXE
through it and voila.

Kim Pallister

We will find a way or we will make one.
                     - Hannibal


> -----Original Message-----
> From: Michael S. Harrison [mailto:mic...@ud...]
> Sent: Monday, August 21, 2000 11:31 AM
> To: gda...@li...
> Subject: Re: [Algorithms] visualizing frustum planes?
> 
> 
> Duh.  This is precisely the reason I like working on teams 
> where more than one person is familiar with a given system.  
> Sometimes having someone state the obvious is a good kick in the seat.
> 
> It hadn't even occurred to me to use an artificial model 
> matrix and draw the simulated frustum planes, in order to 
> check (and help visualize) the camera math
> 
> At 07:10 PM 8/21/00, you wrote:
> >Hey,
> >
> >Here's a piece of code which will render the camera frustum, 
> which I find to
> >be useful when hunting camera problems. It works best when 
> viewed from a
> >second camera though (since the frustum is mostly clipped by the very
> >frustum planes it is meant to visualize), with the AABB 
> culling code (or
> >whatever you may end up using it for) hardwired to the first 
> camera - only,
> >the second camera should just render everything, or only 
> rely on culling
> >code of which you're certain that it works.
> >
> >----8<----
> >  float     ax, ay, bx, by, fx, fy;
> >  static Vertex verts[8];
> >  static ushort indices[24] = {
> >   0,1, 1,2, 2,3, 3,0,
> >   4,5, 5,6, 6,7, 7,4,
> >   0,4, 1,5, 2,6, 3,7
> >  };
> >
> >   // Calculate fov/2 angles in x and y direction.
> >  ax = mFov / 2;
> >  ay = ax * ((float) mViewport.height / (float) mViewport.width);
> >   // Calculate x/y coordinates of the front plane.
> >  fx = mFront * (float) tan(ax);
> >  fy = mFront * (float) tan(ay);
> >   // Calculate x/y coordinates of the back plane.
> >  bx = mBack * (float) tan(ax);
> >  by = mBack * (float) tan(ay);
> >   // Setup frustum verts.
> >  verts[0].loc.set(-fx, +fy, mFront);
> >  verts[1].loc.set(+fx, +fy, mFront);
> >  verts[2].loc.set(+fx, -fy, mFront);
> >  verts[3].loc.set(-fx, -fy, mFront);
> >  verts[4].loc.set(-bx, +by, mBack);
> >  verts[5].loc.set(+bx, +by, mBack);
> >  verts[6].loc.set(+bx, -by, mBack);
> >  verts[7].loc.set(-bx, -by, mBack);
> >  for (short i = 0; i < 8; i++)
> >   verts[i].color = Color3(0.8f, 0.8f, 0.8f);
> >   // Render frustum.
> >  GfxDevice->SetTransform(eTransformWorld, mMatrix);
> >  GfxDevice->Draw(GfxDevice::PrimLineList, verts, 8, indices, 24);
> >----8<----
> >
> >If you have any questions about the specifics of the above 
> code, mail me
> >offline.
> >
> >HTH
> >
> >Jim Offerman
> >
> >Innovade
> >- designing the designer
> >----- Original Message -----
> >From: "Michael S. Harrison" <mic...@ud...>
> >To: <gda...@li...>
> >Sent: Monday, August 21, 2000 9:18 AM
> >Subject: [Algorithms] visualizing frustum planes?
> >
> >
> >> I'm attempting to implement the AABB culling code talked 
> about here some
> >time ago and I'm running into a general problem in 
> visualizing the frustum
> >planes used to cull objects based on their AABB's
> >>
> >> I'm using both Klaus Hartmann's AABBCull sample and the 
> Viewcull sample
> >included with the OpenGL FAQ.
> >>
> >> While the code generally works, I'm having some difficulty 
> visualizing the
> >relationship between the plane vector and the "distance" 
> value stored with
> >it, which I'm sure is the reason I can't quite figure out 
> why the code
> >generates intersection results when it should generate a full cull.
> >>
> >> As you might guess, I'm fairly new to the world of 3d 
> projection and I'm
> >still wrapping my mind around all the transformations that 
> take an object
> >from "world" space to screen space.
> >>
> >> Can anyone suggest a reference or way to visualize exactly 
> what's going on
> >with the plane extraction and how the vectors relate back to 
> the AABB?
> >>
> >>
> >> _______________________________________________
> >> 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 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

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] 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] N-body processing

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

From: "Pierre Terdiman" <p.t...@wa...>

> Dave,
> Welcome. Stefan actually tried that approach, but later. Well, whatever.
> Could you explain what would be the benefit of lozenges ? Especially a
> lozenge-tree ?!

A lozenge looks like an OBB that is 'rounded' at the
edges and corners.  You effectively have the same
degrees of freedom to provide a good fit of an
object by an OBB or lozenge.  So now the problem
is to decide whether an OBB-OBB or lozenge-lozenge
test is cheaper.  For static OBBs, you have up to
15 separating axes to test.  You can compute an
average time for the test based on empirical
probabilities about which axes tend to yield the
separation (for randomly generated OBBs, the
face axes covered about 95% of the cases when
boxes did not intersect).  For static lozenges, you
need to determine the time it takes to compute
the distance between two rectangles in 3D.  I
believe this distance test wins.

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

Re: [Algorithms] Bezier Triangle Rendering

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

From: "Tom Hubina" <to...@3d...>
> Welcome to the list.

Thanks.

> As for the book, I'll probably buy it when it ships, although I've never 
> heard of anyone making enough money off a tech book to actually pay the 
> bills :)

The presales indicate that this might very well be
possible.  But I am conservative.  So there are a
couple more books in the works, one on geometry
tools for computer graphics (co-authored with Philip
Schneider at Disney Feature Interactive) and one on
game physics.  And I gave up my job at NDL to
concentrate on Magic Software and do some contract
work.  I believe all these cover the bills...

From: "Dave Smith" <Dav...@sd...>
> All I know is that before, when I went to your site to 
> look up a topic, it had a paper and some source.
> Now, it seems that it's just source.  I saw your source
> for this post.  I was looking for references.  

Apparently I need to work on ease of navigation at
my site.  All the documentation is easy to get to by
going directly to http://www.magic-software.com/Documentation

> I wasn't criticizing your $60 book.  I was critizing
> the web site change.

Sorry, I must have misread your previous comments,
in particular the part about 'dog you...'.

> Thanks anyway Dave.  Just FYI, I liked your old site
> better since it included papers and references on it
> as opposed to source with book purchase.  But I can't
> dog you for trying to make a living.

From: "Akbar A." <sye...@ea...>
> just a little curious, for some reason i can't wait :)
> but; did you write most of the api code with opengl or d3d?

The book focuses on scene graph management.
There is an abstract renderer class.  The code
includes a software renderer for MS Windows, an
OpenGL renderer for MS Windows, and a GLUT-based
renderer for MS Windows and Linux.  I'll admit that
the renderers are simple and could be greatly improved.
For example, there is no display list or compiled
vertex array code in it.  I avoided D3D because (1) I
wanted to minimize time spent on implementing a
renderer and (2) I wanted code that ran on Linux as
well as MS Windows.

If I get the time to write a D3D renderer, I'll include it
as an update at my web site.  As it is, the first update
(to be posted when the book ships in mid-September)
will have a lot of stuff in it that I did not have ready when
the CD-ROM was due at the end of July.

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

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] 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] Keyframing, bones etc Free to use?

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

Don't yet all this patent stuff get you too paranoid.  Even if it were patented, there are so many ways to form the data and perform the deformation, it would be very hard to cover it by patent and even easier to avoid.  I do like strolling through the patent server to see what silliness still occurs. It has now become too absurd to worry about.  99 and 2000 were huge years for the release of patents on software.  There are tons on IK, Mocap, dynamics, etc.  Expect more every year from now on.

Whenever I talk about matrix deformation, I talk about it in terms of a mathematical formula.  That cannot be patented.  Maybe one exact implementation could and possibly has been but it would be easy to get around.  As to your exact question, I have never seen a paper let alone a patent on exactly matrix deformation for articulated objects.  When I first wanted to do it, I figured out mathematically how Softimage must do it since that is what I was using.  So for me, Softimage was prior art.  The Thalmann's have written on enveloping a skeleton but that is not quite the same as taking an arbitrary mesh and deforming it with matrices.  If anyone else has the definitive reference for this, I would love it for my archives.  

PDI has a patent (99 filed 96) on the technique they use to automatically generate the weights for this deformation but not for the deformation itself.  They reference the Softimage and Alias users manual strangely enough.
http://www.patents.ibm.com/details?pn=US05892691__

This Lucas (filed 95) one seems kind of close but most the prior art listed covers most the technique so I would really need to study it to figure out what they are claiming to have invented.  Seems like it is combining matrix deformation with vertex morphing.
http://www.patents.ibm.com/details?pn=US05883638__

I believe what we would call "keyframe" animation is covered by lots.  A good list is in the prior-art/patent section of this one from Hitatchi.  Which from nearest I can figure covers real-time cut-scene movies.  http://www.patents.ibm.com/details?pn=US06072478__  It also references one from Namco that must be for one of their games.  It covers a 3D game on a grid where you track objects and distance between them on a map.  The distance is used to pick an LOD for the objects and stuff like that.  It seems like they are just covering every aspect of one of their games and claiming it as an "invention."  That way no one could make the same game I guess.  I wonder if this will eventually lead to all games being patented as well as copyrighted as a "unique" combination of prior art techniques.  I guess they don't think look-and-feel copyrights hold up well enough.
http://www.patents.ibm.com/details?&pn10=US05616079  

You also gotta love http://www.patents.ibm.com/details?&pn10=US04643421  "Video game in which a host image repels ravenous images by serving filled vessels...  A video game in which the player must fill mugs from a keg and slide the filled mugs down a bar to advancing thirsty patrons to repel the patron out the bar. "  They patented TAPPER but it expired because they didn't pay the fees.

-Jeff



At 11:37 AM 8/21/2000 -1000, you wrote:
>Is Keyframing, bones, or skinning patented in any way?
>
>
>thanks
>dave
>
>________________________________________________________________________
>Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] visualizing frustum planes?

[Jim O. <j.o...@in...>]

> Duh.  This is precisely the reason I like working on teams where more than
one person is familiar with a given system.  Sometimes having someone state
the obvious is a good kick in the seat.
>
> It hadn't even occurred to me to use an artificial model matrix and draw
the simulated frustum planes, in order to check (and help visualize) the
camera math

That's what we're here for :-)

Jim Offerman

Innovade
- designing the designer