gdalgorithms-list

Re: [Algorithms] Skeletal Animation...

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

Has Game Developer got some issues for you.  I have written several articles on deformation of a mesh using an imbedded skeleton.  That will handle the rendering aspect of a kinematic animation.

http://www.darwin3d.com/gdm1999.htm#gdm1099
http://www.darwin3d.com/gdm1998.htm#gdm0598

For the physics, Chris Hecker wrote a multi-part series on linked rigid body dynamics.  Specifically the example was a ponytail that moved dynamically connected to a kinematic head.

www.d6.com

I don't know if Chris posted his ponytail app yet but if he hasn't send him a note bugging him.  It should be there :)

The person you were thinking of is Brian Mirtich from MERL.  His website is http://www.merl.com/people/mirtich/

-Jeff

At 10:58 PM 8/28/2000 -0700, you wrote:
>Hello.
>
>I was wondering if anyone had links to some good skeletal animation
>techniques and perhaps some information about the kinematics involved.
>
>For example, if I was a model to have a ponytail which moves realistically.
>Given gravity and the mass of my character, I should be able to generate the
>normal force produced by walking (feet hitting the ground).
>
>Assuming the ponytail is just a couple bones end-to-end sharing intermediate
>vertices, the problem I arrive at is the way to correctly propogate a force
>applied at the origin vertex (ie the one connecting the ponytail to the
>head) down into the other vertices.
>
>Any possible links would be great.  I heard that someone wrote quite a few
>papers on the physics involved in this, but I can't remember his name
>exactly.  I know his last name is something like Mirich, but thats not quite
>it.
>
>Thanx!
>Brandon Moro
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Spline Surface Extremal Points ?

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

From: "Steve Wood" <Ste...@im...>
> I don't know anything about spline patches...but extrema is defined as the
> point where the the slope of the tangent=0 AND the slope of the tangent to
> the left of that point is the opposite sign from the slope of the tangent
to
> the right of that point...ie...it's not an inflection point.

Your definition is for the graph of a function y = f(x).  A local maximum
occurs at x0 if f'(x0) = 0 and f"(x0) < 0.  Unfortunately these extrema
are tied into the coordinate system.  Consider f(x) = 1-x^2 for |x| <= 1.
The local maximum occurs at x = 0.  Now rotate the curve (x,f(x)) about
the origin a small amount (so that no tangent line becomes vertical).
The new curve is a graph of another function, but the local maximum
for it is not at the same point as in the original coordinate system.

For a graph z = (x,y,f(x,y)), a local maximum occurs at (x0,y0) if
Gradient(f)(x0,y0) = (0,0) and Hessian(f)(x0,y0) is a negative
definite matrix.  Just as in the one dimensional case, if the graph
has no vertical tangents, and if you rotate the graph a small amount
so that you still have no vertical tangents, the new surface is a
graph of another function, but the local maxima are not at the
same location as in the original coordinate system.

If the original poster has a coordinate system in mind for the
surface, then the definition above will locate the extremal
points.  But if the idea is to find some "intrinsic" extrema,
for example, the vertices of an ellipsoid that do not change
with orientation of the ellipsoid, you need a different concept
for extremum.  The usual ones involve measuring principal
curvatures and deriving some scalar function from them, then
applying the definition mentioned above for finding extrema
of that function.  This approach is what is used for defining
"ridges"  (curves of extreme points) on a surface.

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

[Algorithms] Building BSPs Robustly

[Bernd K. <bk...@lo...>]

Charles Bloom writes:
 > make your BSP building robust (eg. numerically safe) ?

Snapping the original vertices to a grid of integral 
coordinates? The split vertices won't be integral, but 
you might get a better error estimate.

If you can find an upper bound on the error, could you 
shift newly created vertices by that amount along the 
normal, by default? The deeper your tree, the more such 
changes you will accumulate, but if you find a sufficently 
low upper bound maybe you can make sure that you err on 
the right side without introducing a visible error?

Minimizing splits is a good start. Maybe reject splits 
too close to existing vertices, or splits that create 
to big an error (sign?) with respect to

   d = plane.DistanceToPoint( split_vertex );

Investing cycles into a good heuristic might come cheaper 
than checking correctness?

                                       b.



Side question: if you don't use the BSP for depth sorting 
(rendering) but just for hierarchical culling and collision 
detection, do you have to split polygons (i.e. create new 
vertices) at all? With respect to point-vs.-plane tests, 
isn't your leaf is essentially just a list of planes to 
test against, so does it matter whether a plane (that can 
cover all coplanar polygons) appears in more than one leaf 
(flip sign for orientation)?

I am not sure how big the penalty for a depth buffer clear 
and a more or less unsorted z read/write pass (as opposed 
to back-to-front z fill) is these days, especially as 
moving objects approach polygon budgets larger than the 
visible part of the scene.

[Algorithms] Skeletal Animation...

[Brandon M. <the...@us...>]

Hello.

I was wondering if anyone had links to some good skeletal animation
techniques and perhaps some information about the kinematics involved.

For example, if I was a model to have a ponytail which moves realistically.
Given gravity and the mass of my character, I should be able to generate the
normal force produced by walking (feet hitting the ground).

Assuming the ponytail is just a couple bones end-to-end sharing intermediate
vertices, the problem I arrive at is the way to correctly propogate a force
applied at the origin vertex (ie the one connecting the ponytail to the
head) down into the other vertices.

Any possible links would be great.  I heard that someone wrote quite a few
papers on the physics involved in this, but I can't remember his name
exactly.  I know his last name is something like Mirich, but thats not quite
it.

Thanx!
Brandon Moro

RE: [Algorithms] Spline Surface Extremal Points ?

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

I don't know anything about spline patches...but extrema is defined as the
point where the the slope of the tangent=0 AND the slope of the tangent to
the left of that point is the opposite sign from the slope of the tangent to
the right of that point...ie...it's not an inflection point.

Hope that helps.

Rockn-Roll

> -----Original Message-----
> From: Tim Thomas [mailto:sup...@gm...]
> Sent: Friday, August 18, 2000 2:27 PM
> To: gda...@li...
> Subject: [Algorithms] Spline Surface Extremal Points ?
> 
> 
> Hi !
> 
> How do i calculate the extremal points of a given ( tangents, 
> 4 points )
> spline patch ?
> 
> Any help welcome, even little hints or links
> 
> Thanks in advance
> 
> Tim
> 
> -- 
> Sent through GMX FreeMail - http://www.gmx.net
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] Water Effects

[Tony C. <to...@mi...>]

>Also it is difficult to combine animated water grid 
>with geometry based reflections (not rendered into texture).
>So my ocean has flat water :)

FYI, the MS water demo that you might have seen shown at various DirectX
developer events is now sample code on the DX 8 SDK (as of beta 2). I think
it's one of the nicer water effects I've seen.

Tony Cox - DirectX Luminary
Windows Gaming Developer Relations Group
http://msdn.microsoft.com/directx

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

[Mark W. <mwi...@cy...>]

Hi Niki,

You could also try the trick that many people used when
making outdoor levels for Quake based games.  They create a
2D grid of lightsources on a plane in the sky.  The
brightness of each light is adjusted based on the sun
position.  This method approximates an area light source
(sky/clouds) instead of just a point light (sun).  Search
around the Quake modeling sites for more details.  By the
way... I think your lightmap looks fine.  Lightmaps never
look very good when viewed alone.  You have to blend them
with a noisy base texture to get a decent effect.

-Mark

----- Original Message -----
From: "Klaus Hartmann" <k_h...@os...>
To: <gda...@li...>
Sent: Monday, August 28, 2000 12:33 PM
Subject: Re: [Algorithms] It looks terrible (was: Lightmap
Terrain)


> Kim,
>
> it sure is worth a try to let the 'anti sun' shine from
above :) Curious to
> see what it looks like, but can't try it right now.
>
> The reason why I chose to place the 'anti sun' to the
west, and the sun to
> the east is, because I saw our artist model terrain. The
results looked way
> great, and he placed the 'anti sun' to the west, and the
sun to the east.
>
> Also, I was thinking about something completely different:
Create an
> invisible sphere that represents the atmosphere and
encloses the whole
> terrain. Then light the 'faces' of the sphere so that it
is brightest where
> the sun is. Then for each ray/surface intersection point
compute the normal
> at that point and use it to cast a ray towards the sphere.
You'll hit a more
> or less bright on that sphere, and this point is then used
as a light source
> (the color of that point on the sphere then represents the
color of the
> light emitted from the 'virtual' light source). I'm not
quite sure what will
> happen to the shadows, but it's possible that they'll be
correct (including
> penumbrae).
>
> Maybe I'm wrong, but I have the feeling, that this can
look more than just
> good.
>
> Everyone: What do you think?
>
> Niki
>

Re: [Algorithms] Lightmap Terrain

[Johan H. <jh...@mw...>]

> It's notable, however, that nobody complains about unrealistic
> Television images - and they have the same brightness range as
> your computer screen.

Yes, but please don't compare us to the brainwashed television masses out
there ................. :-)

Johan

Re: [Algorithms] Rolling Ball Algorithm GGemsIII

[Dave S. <Dav...@sd...>]

Ok, after looking at the example source.
I got it to work(somewhat).  Not quite what I 
expected.  Oh well live and learn.

Thanks anyway (other ideas are still welcome :-)
-DaveS

I wrote:
> 
> I'm trying to implement the Rolling Ball Algorithm
> for viewing objects,
....stuff snipped

> Are there other types of algorithms similar to this
> for viewing objects in 3D that involve the camera being
> focused on an object and the mouse motions rotating
> about that object.

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

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

Kim,

it sure is worth a try to let the 'anti sun' shine from above :) Curious to
see what it looks like, but can't try it right now.

The reason why I chose to place the 'anti sun' to the west, and the sun to
the east is, because I saw our artist model terrain. The results looked way
great, and he placed the 'anti sun' to the west, and the sun to the east.

Also, I was thinking about something completely different: Create an
invisible sphere that represents the atmosphere and encloses the whole
terrain. Then light the 'faces' of the sphere so that it is brightest where
the sun is. Then for each ray/surface intersection point compute the normal
at that point and use it to cast a ray towards the sphere. You'll hit a more
or less bright on that sphere, and this point is then used as a light source
(the color of that point on the sphere then represents the color of the
light emitted from the 'virtual' light source). I'm not quite sure what will
happen to the shadows, but it's possible that they'll be correct (including
penumbrae).

Maybe I'm wrong, but I have the feeling, that this can look more than just
good.

Everyone: What do you think?

Niki

From: Pallister, Kim <kim...@in...>
> On topic: Niki, I understand what you are saying about ambient. Would then
> your 'anti sun' best be approximated with a directional light from
straight
> above? Not sure this captures it well, but at least overhang's would get
> complete shadow.

Re: [Algorithms] Alpha Channel

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

On Sat, 26 Aug 2000, Pai-Hung Chen wrote:

> I want to use billboard in my program but cannot find a good way to create
> 32-bit bitmap with alpha channel of appropriate values.  Basically I want to
> create a bitmap of tree with leaves in various green colors (with alpha =
> 255) and all non-green colors transparent (alpha = 0) so that I can use it
> as the texture for my billboarded trees.  It would be nice if I can specify
> a non-green color C and make the alpha of all the pixels of color C in the
> bitmap to 0.  Is there any program capable of doing that with 32-bit bitmap
> with alpha channel?  This may be off-topic and you could send your advise to
> me off-line.
 
Use GLUT

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

RE: [Algorithms] It looks terrible (was: Lightmap Terrain)

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

On topic: Niki, I understand what you are saying about ambient. Would then
your 'anti sun' best be approximated with a directional light from straight
above? Not sure this captures it well, but at least overhang's would get
complete shadow.

Off topic:
> From: Ralf Schneider [mailto:rap...@ra...]
>...
> by the way rappongi.com came from "roppongi" a district in 
> tokyo: nightclubs, bars, discos, ... some people say: 
> roppongi is the place where you can feel the pulse of the 
> city. i like the name and i like roppongi, so i have choosen 
> it as my domain name.

I know, that's why I made the comment. I'll be there on business in a couple
weeks. BTW, Maybe you could sell web page space to clubs there :-)

Kim Pallister

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


> -----Original Message-----
> From: Ralf Schneider [mailto:rap...@ra...]
> Sent: Monday, August 28, 2000 4:51 AM
> To: gda...@li...
> Subject: RE: [Algorithms] It looks terrible (was: Lightmap Terrain)
> 
> 
> Hello Kim,
> 
> i don't know what you are talking about! i joined the 
> mailing-list 3 days ago.
> if you take a look wou will see "ralf schneider" has 
> registered the domain "rappongi.com". nothing special about 
> that. klaus hartmann alias niki know me, i wrote 2 small 
> games for him when i was working as a freelancer.
> 
> by the way rappongi.com came from "roppongi" a district in 
> tokyo: nightclubs, bars, discos, ... some people say: 
> roppongi is the place where you can feel the pulse of the 
> city. i like the name and i like roppongi, so i have choosen 
> it as my domain name.
> but i'm german, anyway. 
> 
> ... this is the last time, i will write about an off-topic, 
> personal thread in the mailinglist. but i think i missed 
> something in the past, wich would explain this behaviour.
> 
> have a nice day!
> 
> - ralf
> 
> | Everyone else, am I the only one that find's Ralf's email address
> | intriguing?
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] Lightmap Terrain

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

On Fri, 25 Aug 2000, Bernd Kreimeier wrote:

> Charles Bloom writes:
>  > The more I look at real outdoor environments (eg. life) the
>  > more I feel that it may be hopeless to simulate them realistically
>  > on a computer screen.  The problem is the sun. 
> 
> Isn't the Sun just a special case of a general problem:
> the way we handle dynamic range between graphics card and CRT's? 

Yes...and it's a hard problem.  CRT's are getting brighter
and other display technologies (direct laser-on-retina displays
for example) could actually produce real-world brightnesses (DANGEROUS!)

It's notable, however, that nobody complains about unrealistic
Television images - and they have the same brightness range as
your computer screen.

With the right combination of tricks like lens flare, you can
reproduce the *effect* of that extra brightness without actually
emitting more photons.

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

Re: [Algorithms] View culling example

[Michael S. H. <mic...@ud...>]

Done.

I'll be uploading the modified version momentarily.


At 08:35 AM 8/28/00, you wrote:
>That's a *very* nice sample, Michael.
>
>However, I would prefer if you didn't name that culling method after me,
>because I didn't invent it :) I also had a look at the source and saw 'tons'
>of "swHartmann" variables in there... even in the plane extraction, which
>was 'invented' by Gil Gribb. Also, I would prefer if you didn't mention my
>e-mail address in the source code :)
>
>So, please remove my name as well as my e-mail address from the source. Of
>course, you may mention me in the header and maybe write something like
>"Parts of this source code are based on Klaus Hartmann's AABB-Culling
>sample", but that's enough. Don't give me too much credit for something I
>didn't invent. I only reused existing algorithms, and put them into a small
>sample.
>
>Thanks,
>Niki
>
>PS: I didn't take this off-line, because I'm sure that some people on this
>list will download the source. I think they should know that it wasn't me
>who invented these nice algorithms.
>
>From: Michael S. Harrison <mic...@ud...>
>> As (what I hope is) a favor to the people who've helped me with the view
>culling code and in an attempt to help future coders, I've taken the view
>culling example from the OpenGL FAQ, Klaus Hartmann's view culling sample
>and merged them both with Nate Robbin's OpenGL tutors (mostly because his
>projection sample really helped me to see what was going on with the various
>culling examples out there).
>>
>> It's available at http://lynx.inertiagames.com/~michael/OPENGLTUTORS.zip
>>
>> make sure you uncompress with directory re-creation
>>
>> run the viewcull.exe program to play with the sample
>>
>> - software culling is toggled with the spacebar
>> - if software culling is enabled, Hartmann culling is toggled with the 'h'
>key
>> - if a model is selected from the screen menu (right click on the screen
>space view)
>>   that model will be displayed at the origin.  If it's culled, it will be
>drawn untextured.
>>
>> NOTE that this should probably not be linked to on any web page or
>generally distributed other than through word of mouth.  I haven't asked
>Nate to include it "officially" as part of his tutor group but perhaps he
>will if he thinks it's useful enough.
>>
>>
>> - Michael Harrison
>>   High Plains Coder,
>>   United Developers / Inertia, LLC
>>   Work log @ http://lynx.inertiagames.com
>>
>> _______________________________________________
>> 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] It looks terrible (was: Lightmap Terrain)

[<sro...@te...>]

>I very much appreciate all the usefull help and suggestions from you
people.
>I appreciate it so much, that I decided to make this test program (+
source)
>available to the members of this list (only to the members of this list).
>I'll leave a note as soon as I've made the code a bit prettier.

Just a idea for your demo:
Put a part of your heightfield data all in black with some basic white form
like a square, cercle, line, triangle to see the shadow of this object on
the lightmap

Regards,
Corrosif

RE: [Algorithms] It looks terrible (was: Lightmap Terrain)

[<sro...@te...>]

>I very much appreciate all the usefull help and suggestions from you
people.
>I appreciate it so much, that I decided to make this test program (+
source)
>available to the members of this list (only to the members of this list).
>I'll leave a note as soon as I've made the code a bit prettier.

Cool,

I got my raytracing working but it's only black and white :)

How many time in sec that take to perform your lightmap (1025x1025)?
Just for me curiosity :)

Corrosif

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Klaus
Hartmann
Sent: Monday, August 28, 2000 7:58 AM
To: gda...@li...
Subject: Re: [Algorithms] It looks terrible (was: Lightmap Terrain)


Hi,

I've now modified my ray tracer into a true recursive ray tracer that
reflects rays, and I also included the light-jittering that was suggested by
Phil. It looks better now, as can be seen in the following image (290 KB):
http://www.thecore.de/TheCore/shadows2.jpg

Please, note that there's no longer a second light source. Instead, the
details on the shadow sides now come from the reflected rays. I know that
pieces of this image look like rubble. This makes it a bit difficult to
understand the image, but you must never forget that this is a lightmap, and
in 3D you have actual elevations that help to understand the lighting.

I very much appreciate all the usefull help and suggestions from you people.
I appreciate it so much, that I decided to make this test program (+ source)
available to the members of this list (only to the members of this list).
I'll leave a note as soon as I've made the code a bit prettier.

Thanks a lot,
Niki

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

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

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

> One of the most important aspet in the final scene, is the color of the
> light map. By making the light orange / yellow, and the shadows blue, you
> inrease the visual experience  a lot. Currently I am tweaking my lightmaps
> in photoshop to do this.

A better use of complementary colors would be to use the complementary
colors of the texture in the shaded area. I.e. if you want to create a
really dark shadow in a green area, use a red tint in the shadow (note: this
trick is frequently applied in pencil art). An obvious problem is
calculating complementary colors on the fly...

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

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

> I don't use any ambient color at all. Instead I use a second directional
> light source (opposite to the sun).

I have read your disliking of ambient light in the other post. I always use
a little ambient light in my scenes - I dislike those totally black shadows,
takes away all the texture... but that's an arguable opinion though.

> I do use the pixel-corners, but I don't average them. This is sort of an
> accident really. Perhaps, I should cast the rays through the center of
each
> pixel. Thanks for reminding me :)

Your welcome. I'd also play with averaging four rays to get a single shade
value, since it should nicely soften the shadow's edges.

> Funny! This is exactly what I did last night :) This made the lightmap
look
> a bit better, but I haven't tried it in 3D, yet.

Well what do you know... Let me know the results. I would certainly like to
know whether it is worth the effort, before I start wasting time on such a
thing.

> Well, I think I'll bite the bullet and try some true recursive ray tracing
> (with reflected rays), today. Technically this is wrong for diffuse light,
> but maybe it looks better, and that's what counts.

Alternatively, you might consider using five (or even more) directional
light sources, each with a slightly different direction and blend the
results together. We always treat sunlight as being parrallel in our
simulations, but it is not 100% parrallel in real life...

Jim Offerman

Innovade
- designing the designer

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

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

Hi,

I've now modified my ray tracer into a true recursive ray tracer that
reflects rays, and I also included the light-jittering that was suggested by
Phil. It looks better now, as can be seen in the following image (290 KB):
http://www.thecore.de/TheCore/shadows2.jpg

Please, note that there's no longer a second light source. Instead, the
details on the shadow sides now come from the reflected rays. I know that
pieces of this image look like rubble. This makes it a bit difficult to
understand the image, but you must never forget that this is a lightmap, and
in 3D you have actual elevations that help to understand the lighting.

I very much appreciate all the usefull help and suggestions from you people.
I appreciate it so much, that I decided to make this test program (+ source)
available to the members of this list (only to the members of this list).
I'll leave a note as soon as I've made the code a bit prettier.

Thanks a lot,
Niki

RE: [Algorithms] It looks terrible (was: Lightmap Terrain)

[Ralf S. <rap...@ra...>]

Hello Kim,

i don't know what you are talking about! i joined the mailing-list 3 days ago.
if you take a look wou will see "ralf schneider" has registered the domain "rappongi.com". nothing special about that. klaus hartmann alias niki know me, i wrote 2 small games for him when i was working as a freelancer.

by the way rappongi.com came from "roppongi" a district in tokyo: nightclubs, bars, discos, ... some people say: roppongi is the place where you can feel the pulse of the city. i like the name and i like roppongi, so i have choosen it as my domain name.
but i'm german, anyway. 

... this is the last time, i will write about an off-topic, personal thread in the mailinglist. but i think i missed something in the past, wich would explain this behaviour.

have a nice day!

- ralf

| Everyone else, am I the only one that find's Ralf's email address
| intriguing?

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

[Johan H. <jh...@mw...>]

Hi

One of the most important aspet in the final scene, is the color of the
light map. By making the light orange / yellow, and the shadows blue, you
inrease the visual experience  a lot. Currently I am tweaking my lightmaps
in photoshop to do this.

Johan Hammes

Re: [Algorithms] Building BSPs Robustly

[Angel P. <ju...@bi...>]

> A question for the BSP experts : what do you do to make
> your BSP building robust (eg. numerically safe) ?
> Is there an article on these issues?
>(still working on  that BSP article, Angel?).
Not yet, too busy right now. I hope to finish it next month.
 
> Now for more detail.  Let me stick to two dimensions for
> simplicity.  I'm building a 2d BSP from convex polygons.
> To do that, you just take the polygon and send it down
> the tree, clipping it against each plane in the tree.
> Eventually you arrive at a leaf. 

If you just want to create a BSP from all convex polygons - then
first put all edge segments from all polygons in the root node of the
BSP.

Then pick a hyperplane from one of the stored edges (polys in 3D ) and move
all edges in front of the plane to node->Front and all edges behind the
plane to node->Back. If node->Front or node->Back is NULL and an
edge has to be put in it - then create that leaf.
Handling edges that lie on the plane depends on the kind of BSP tree
you want to do:
1. If it's a solid BSP with polygons(3D) in the BSP leaves forming solid convex
clumps then move the edge to node->Back.
2. If it's a solid BSP with polygons(3D) in the BSP leaves forming hollow convex
clumps then move the edge to node->Front, this kind of BSP
is used for automatic portalization.
3. If it's a classic BSP with polygons(3D) in the BSP nodes - then just store that
polygon there.
Recurse through node->Front and node->Back.


The approach you described is more suitable to CSG operations using BSP
trees (this is actually quite fast and can be done in realtime).

You can safely delete the clipped polygons which arive in
"IN" NULL leaf. See this picture:
http://thegeleto.tripod.com/bsp-figure1.jpg
This will clip away the polygons that are inside the current BSP.

For the edges that end in "OUT" NULL leaf - create a new
BSP leaf and store the edge and it's hyperplane in it.

For edges that arrive at a BSP node and lie on the separating
hyperplane  for that node - for now just store it there (although it's
not that simple, see below)

You have to clip the BSP line segments to the convex hull (or BSP if
the polygon is concave) of the polygon. Because clipping ALL BSP
line segments can be very slow you can use the bounding circle of the
polygon to visit only nodes that potentially intersect it.

The result will be a classic BSP with edges stored at nodes

There are two optimizations that can be done with this:
1. When all edges from a BSP node were clipped to the polygon
- this node can be safely removed from the BSP if either node->Front
or node->Back is NULL (the node that is not NULL replaces the
current node in the BSP and the current node is deleted). If that node
is a leaf - simply delete that leaf.
2. When the BSP edges are clipped to the BSPed polygon they may
get split quite a lot even if nothing is clipped away. You can keep a binary
tree with the split history of the edge and restore the unclipped parts from it.
This is quite beneficial in 3D where merging polygons can be tedious.

> At that point I take
> all the segments of the clipped polygon which arrives
> at that leaf, and add them to the tree if and only if
> the plane they create isn't already in the tree.  
> This make it so that if you have a little empty leaf in
> the tree and you add a polygon that covers it completely
> you don't end up adding any planes, you just mark that
> leaf is solid now.

In my explanation on doing CSG above I said that when the edge lies on
a node's hyperplane it should be stored in that node. This is partially
true except that before doing that you have to clip that edge to both
node->Front and node->Back. If you want to handle decals properly
this becomes quite complicated ( you have to be careful how you clip
the BSP segments to the polygon, etc )
 
> Now, we run into robustness problems.  The first problem
> is just with tiny segments.  Sometimes after clipping you
> end up with very short segments in your leaves, that you
> can't do a reliable cross product on to make a normal for
> use in the plane.  I just throw out these short segments
> (seems reasonable).

Calculate the planes for the original polygons and store them with
the polygon. When it is split - set the same plane for the splitted
polys. If you use EPSILON aware polygon splitting routine(see below)
you should not have such short segments.

> All of the remaining problems come from numerical errors
> on the plane clipping.  This arises because when you take
> a point, find the distance to a plane, and push it by
> that distance, you don't end up with a point right on that
> plane.
> 
>    d = plane.DistanceToPoint( point );
>    point += d * plane.normal;
>    d = plane.DistanceToPoint( point );
> 
> Now d is small, but not zero !  The point is slightly off
> the plane in some direction.  This will always happen, no
> matter how you do your plane clipping, and whether you
> use floats or doubles (I use floats).

You should assume that a polygon/segment lies on a plane
if it's verts lie on less than some small (EPSILON = 0.001) distance
away from the plane. This hould not be a problem if your polygon
splitting routine is EPSILON aware.
Here is my one:

A few notes:
The CVertex class contains a fourth comonent called dist that stores the distance
of the point from the Plane. This is calculated in PlaneSide. So PlaneSplit can
be safely used only after PlaneSide was called for the polygon:

if( poly-->PlaneSide( plane )==SIDE_Intersect )
{
    CPolygon *frontPoly, *backPoly;
    poly->PlaneSplit( frontPoly, backPoly );
    .............
}

int CPolygon::PlaneSide( CPlane &P )
{
 vfloat d;
 bool vertexInFront=false, vertexBehind=false;
 for( int i=0; i<NumSides; i++ )
 {
  d = P.DistToVert( Verts[i] );
  if( d>EPSILON )
   vertexInFront=true;
  else
   if( d<-EPSILON )
    vertexBehind=true;
  Verts[i].dist = d;//will need it in PlanesSplit
 }
 if( vertexInFront )
 {
  if( vertexBehind )
   return SIDE_Intersect;
  else
   return SIDE_Front;
 }
 else
 {
  if( vertexBehind )
   return SIDE_Back;
  else
   return SIDE_OnPlane;
 }
}


void CPolygon::PlaneSplit( CPolygon *&FrontPoly, CPolygon *&BackPoly )
{
 int numFrontVerts=0, numBackVerts=0;
 vfloat d;
 vfloat prevd = Verts[NumSides-1].dist;
 for( int i=0; i<NumSides; i++ )
 {
  d = Verts[i].dist; //calculated in PlaneSide()
  if( myabs( d ) < EPSILON )
  {
   numBackVerts++;
   numFrontVerts++;
  }
  else
  {
   if( d < 0 )
   {
    if( prevd > EPSILON )
    {//intersection point
     numFrontVerts++;
     numBackVerts++;
    }
    numBackVerts++;
   }
   if( d > 0 )
   {
    if( prevd < -EPSILON )
    {//intersection point
     numFrontVerts++;
     numBackVerts++;
    }
    numFrontVerts++;
   }
  }
  prevd = d;
 }

 FrontPoly = new CPolygon( numFrontVerts, this );
 BackPoly = new CPolygon( numBackVerts, this );

 int backindex=0, frontindex=0;
 int previ = NumSides-1;
 prevd = Verts[previ].dist;//calculated in PlaneSide()
 for( i=0; i<NumSides; i++ )
 {
  d = Verts[i].dist;
  if( myabs( d ) < EPSILON )
  {
   FrontPoly->Verts[frontindex] = Verts[i];
   frontindex++;
   BackPoly->Verts[backindex] = Verts[i];
   backindex++;
  }
  else
  {
   if( d < 0 )
   {
    if( prevd > EPSILON )
    {//intersection point
     FrontPoly->Verts[frontindex].Interpolate( Verts[previ], Verts[i], prevd/(prevd-d) );
     BackPoly->Verts[backindex] = FrontPoly->Verts[frontindex];
     frontindex++;
     backindex++;
    }
    BackPoly->Verts[backindex] = Verts[i];
    backindex++;
   }
   if( d > 0 )
   {
    if( prevd < -EPSILON )
    {//intersection point
     FrontPoly->Verts[frontindex].Interpolate( Verts[previ], Verts[i], prevd/(prevd-d) );
     BackPoly->Verts[backindex] = FrontPoly->Verts[frontindex];
     frontindex++;
     backindex++;
    }
    FrontPoly->Verts[frontindex] = Verts[i];
    frontindex++;
   }
  }
  prevd = d;
  previ = i;
 }
}

> The result is that you can end up with non-convex polygons
> in the leaves.  These can happen in 2 major ways (
> see http://www.cbloom.com/bsp_problems.gif "):
> 
> 1. "bend-ins".  This is when you have three verts that
> are very nearly co-linear.  If the clipping had been perfect,
> they would have been colinear.  Instead, the middle one fell
> a bit to the inside of the other two, creating a very mild
> star-trek-symbol shape.  I get rid of these by finding the
> triangles that have very small areas and deleting their middle
> vertex.
> 
> 2. "fish-tails".  Take a triangle.  Duplicate one of the verts
> to make it a quad with two verts right on top of eachother.
> Take one of the duplicated verts and pull it across its twin
> so that the segments of the quad intersect.  This makes a
> segment with the wrong winding, two triangles with upside
> down normals.  This is a big crisis for a BSP, because that
> wrong-facing segment will make a plane facing the wrong way.
> Most of the time, this will be fixed by deleting the very
> short segments, but I still seem to get it once in a rare
> while.  The rest of the time, I fix it by turning the segments
> in to planes.  In my convention, proper planes will have
> all the other verts of the polygon on its front side.  Thus,
> any plane which has verts of the polygon on its back side
> is simply tossed out, and its end-points are snapped together.

The above algho should take care of these cases.

Re: [Algorithms] OpenGL LockArrayEXT ... workaround

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

I believe that this limit was DMA related, rather than index addressing
related.
I am also under the impression that this limitation is no longer in effect
if using the
latest drivers (and perhaps DX8) ... and yes, the document should be updated
:)

> First off, the 64k limit is just because 16-bit indices are used for
vertices,
> and that's a hard limit to stay for quite some time, I imagine.  As for
that 2k
> vertices per buffer, that was an anomaly of old GeForce drivers, and has
been
> removed.  Hey NVidia, you need to make a new document on how to optimize
for T&L
> that doesn't dwell so much on the oddities of the GeForce (which really
does
> have odd performance characterics which are not typical of Radeon and
other
> future T&L products, like NV20 presumably).

I could be wrong, though ... search DirectX list archives for confirmation
(I think Richard Huddy from nVidia mentioned the fix).

Mark

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

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

----- Original Message -----
From: Pallister, Kim <kim...@in...>
> Niki,
>
> Why are you anti-ambient lighting?

I don't like to lose the shading on the shadow sides of the mountains. In 3D
terrain it looks *much* better if you use an anti-sun light source instead
of ambient light. Ambient light is, in my opinion, one of the worst features
of the Phong reflection model... especially when you use to light terrain.

> Everyone else, am I the only one that find's Ralf's email address
> intriguing?

This is not the 'rappongi' you are thinking about :) If I remember
correctly, then the other 'rappongi' is even spelled differently...

Niki

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

Re: [Algorithms] It looks terrible (was: Lightmap Terrain)

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

Johan,

yes I did read your post, but it was too late to completely understand it.
But... I have all intentions to make things look good with the approach I'm
currently using. Your two methods would be completely different from what
I'm doing right now, and I'd like to avoid that. Maybe I'll give it a try as
soon as the my current version yields acceptable results. I'll let you know,
when I do.

Niki

----- Original Message -----
From: Johan Hammes <jh...@mw...>
> Hi,, have you read my previous email on radiocity in hardware? Thta should
> solve most of this?
> I dont really know how this comares in speed to your current method
though.
>
> Johan
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>