gdalgorithms-list

RE: [Algorithms] water caustics

[Jason M. (A. Technologies) <v-j...@mi...>]

   We use projective caustic maps in the Radeon's Ark demo (ships on the
Radeon end-user CD and has screenshots in the new GP Gems book if you're
interested) in the fish tanks.  There is one static caustic map and it is
used twice (two slightly different projections) with multitexturing.  After
the projection, the maps are scrolled, twisted and scaled over time to
taste.  Naturally, the two textures are scrolled/rotated in different ways.
The great thing about the projective nature of the texture coordinate
assignment (as opposed to the DX SDK dolphin sample which uses essentially a
parallel projection) is that you can simulate the "tight" caustic details in
the shallow water and the more diffused patterns you get in deeper areas.
(IIRC, Mark Watt has a SIGGRAPH 1990 paper on doing this "right.")

    The new MS water sample which was used at the XBox launch and appears on
the DX8 SDK was written by Loren McQuade and uses the actual water surface
simulation to generate a dynamic caustic map as you suggest.

    Another issue is projecting onto objects in water (as opposed to the
container itself).  The DX SDK dolphin sample takes pain to make sure that
the caustic map does not appear on the under side of the dolphin.  While
this looks fine, we neglected this as a first cut in our water tanks and
found that allowing the caustics to project through the animals in our tanks
looked just fine.  The caustic maps get modulated with a directional light
from above anyway and the caustics on the underside are diffused enough to
appear to be reflected up from inside the tank.

    On a related note, if you've played Zelda on the N64, there is a level
which simulates *reflected* caustics *outside* the water with a scrolling
caustic map.  It looks kinda hokey, but I'm sure it's very inexpensive to do
and the level would be less immersive without it.

                          -Jason



> -----Original Message-----
> From: Charles Bloom [mailto:cb...@cb...]
> Sent: Thursday, August 03, 2000 12:04 PM
> To: gda...@li...
> Subject: [Algorithms] water caustics
> 
> 
> 
> It just occurred to me that this could probably
> be hacked pretty convincingly using projective
> texturing.  Any object underwater would just get
> an extra additive pass from a projective texture
> which had some fake caustic lines in it.  If you
> wanted to be fancy, you could even use the
> heightmap of your water to draw some caustic
> lines that resembled the crests of the wave
> surface; totally incorrect, but probably great
> looking for games.
> 
> --------------------------------------
> Charles Bloom           www.cbloom.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] FPS Questions

[Vianet <sc...@vi...>]

please do not send messages to me anymore

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
Andrew Howe
Sent: August 10, 2000 11:25 AM
To: gda...@li...
Subject: Re: [Algorithms] FPS Questions


> staring at a bright white ZX Spectrum(*) screen while coding in basic that

> (*) Home computer, contemporary (and clear superior, obviously) of the
C64.
> I think it was called a TRS80 on the other side of the pond? Fantastically
> popular here in Britland.

I think you might mean Timex Sinclair.  The ZX-81 was a TS 1000 I think, but
I don't know the number for the Spectrum.

Andrew.



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

Re: [Algorithms] FPS Questions

[gl <gl...@nt...>]

> Which leads me to a question: do you folks think that the eyes & brain can
> be trained to better perceive such errors?

Of course.  True of anything you study (in the loosest sense of the word).

> The movies never used to bother
> me until I became a graphics programmer. Now it bugs me. Also, PAL didn't
> used to bother me, but now I find the lower frame rate intolerable, which
is
> why I make a point of not watching TV when I am in the UK, but spend the
> time in pubs instead!

Smile.
--
gl

RE: [Algorithms] VIPM and UV texturing

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

Hoppe's version of the QEM metric that deals with attributes does help with
these sorts of things, and may well be just what the doctors ordered. It
certainly deals with similar problems with vertex colours, as demonstrated
very convincingly by the "baboon" picture done entirely with untextured
vertex-coloured triangles.

For animation, I have in my brain an idea about having several typical poses
for the character in memory while calculating the QEMs, and using the metric
that gives you the _greatest_ error of all the poses when deciding which
collapse is best to do. That way things like elbows and knees won't vanish
far too early, but the artists don't need any specialist knowledge, or need
to worry about default poses too much.

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

> -----Original Message-----
> From: Jeff Lander [mailto:je...@di...]
> Sent: 10 August 2000 16:09
> To: gda...@li...
> Subject: RE: [Algorithms] VIPM and UV texturing
> 
> 
> I started adding some code to the metric to try and detect 
> and weight the case but never got it to work well with all 
> the other settings in the metric.  Having the artistic 
> control was just more flexible.  We are doing a new rev on 
> the tool and I have someone else working on it so I will have 
> him revisit that.
> 
> There are a lot of aspects to the decimation that I am 
> looking at for the next rev.  Our current metric doesn't take 
> into count the changes brought by animation.  It uses the 
> rest pose which as you know artists can build in strange ways 
> to make weighting easier.  I don't know if anyone else has 
> looked at this.
> 
> Also, the current algorithm leads to a bit of hollowness on 
> the low end of the scale.  It does decent at preserving the 
> base shape but things like the legs get a bit thin.  I am 
> thinking about adding in some volume preservation (like Hoppe 
> had in his recent paper on metrics) or trying some 
> image-space stuff from orthogonal angles to address this.
> 
> -Jeff
> 
> At 05:58 AM 8/10/2000 -0700, you wrote:
> >However, you then get >the nice situation of  (1,0) ------ 
> (1,0).  Doesn't
> >look so hot.  I have the artists tag 
> > >reflected seam vertices as uncollapsable until very late 
> in the order.
> >
> >Can you not algorithmically detect this situation as well? 
> Compute the
> >tangent-normal basis for the polygon, and look at the 
> derivative of the
> >texture coordinates w.r.t the tangent vector - if this 
> changes sign you have
> >a seam.
> >
> >More work, I grant you, and I admit not as flexible as 
> having a tool that
> >lets the artists do the markup, but still possible.
> >
> >Tony Cox - DirectX Luminary
> >Windows Gaming Developer Relations Group
> >http://msdn.microsoft.com/directx 
> >
> >_______________________________________________
> >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] FPS Questions

[Dominic R. <dro...@wa...>]

The Trash80 was a whole different animal ( also 'obviously' inferior to the
Speccy ) - it lacked the rubber 'dead flesh' keyboard for one thing.

Those were the days.

Dominic

> -----Original Message-----
> From: Tom Forsyth [mailto:to...@mu...]
> Sent: 10 August 2000 16:15
> To: gda...@li...
> Subject: RE: [Algorithms] FPS Questions
> 
> 
> Kim, you'll find that if you spend enough time in the pubs, 
> the movies won't
> bother you any more. :-)
> 
> And yes, I think they can be trained. Maybe it's from years of sitting
> staring at a bright white ZX Spectrum(*) screen while coding 
> in basic that
> I've become allergic to low frame rates.
> 
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
> 
> (*) Home computer, contemporary (and clear superior, 
> obviously) of the C64.
> I think it was called a TRS80 on the other side of the pond? 
> Fantastically
> popular here in Britland.
> 
> 
> > From: Pallister, Kim [mailto:kim...@in...]
>  
> [snip]
> 
> > Which leads me to a question: do you folks think that the 
> > eyes & brain can
> > be trained to better perceive such errors? The movies never 
> > used to bother
> > me until I became a graphics programmer. Now it bugs me. 
> > Also, PAL didn't
> > used to bother me, but now I find the lower frame rate 
> > intolerable, which is
> > why I make a point of not watching TV when I am in the UK, 
> > but spend the
> > time in pubs instead!
> > 
> > Kim Pallister
> > 
> > We will find a way or we will make one.
> >                      - Hannibal
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] FPS Questions

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

> staring at a bright white ZX Spectrum(*) screen while coding in basic that

> (*) Home computer, contemporary (and clear superior, obviously) of the
C64.
> I think it was called a TRS80 on the other side of the pond? Fantastically
> popular here in Britland.

I think you might mean Timex Sinclair.  The ZX-81 was a TS 1000 I think, but
I don't know the number for the Spectrum.

Andrew.

RE: [Algorithms] FPS Questions

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

Kim, you'll find that if you spend enough time in the pubs, the movies won't
bother you any more. :-)

And yes, I think they can be trained. Maybe it's from years of sitting
staring at a bright white ZX Spectrum(*) screen while coding in basic that
I've become allergic to low frame rates.

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

(*) Home computer, contemporary (and clear superior, obviously) of the C64.
I think it was called a TRS80 on the other side of the pond? Fantastically
popular here in Britland.


> From: Pallister, Kim [mailto:kim...@in...]
 
[snip]

> Which leads me to a question: do you folks think that the 
> eyes & brain can
> be trained to better perceive such errors? The movies never 
> used to bother
> me until I became a graphics programmer. Now it bugs me. 
> Also, PAL didn't
> used to bother me, but now I find the lower frame rate 
> intolerable, which is
> why I make a point of not watching TV when I am in the UK, 
> but spend the
> time in pubs instead!
> 
> Kim Pallister
> 
> We will find a way or we will make one.
>                      - Hannibal

RE: [Algorithms] VIPM and UV texturing

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

I started adding some code to the metric to try and detect and weight the case but never got it to work well with all the other settings in the metric.  Having the artistic control was just more flexible.  We are doing a new rev on the tool and I have someone else working on it so I will have him revisit that.

There are a lot of aspects to the decimation that I am looking at for the next rev.  Our current metric doesn't take into count the changes brought by animation.  It uses the rest pose which as you know artists can build in strange ways to make weighting easier.  I don't know if anyone else has looked at this.

Also, the current algorithm leads to a bit of hollowness on the low end of the scale.  It does decent at preserving the base shape but things like the legs get a bit thin.  I am thinking about adding in some volume preservation (like Hoppe had in his recent paper on metrics) or trying some image-space stuff from orthogonal angles to address this.

-Jeff

At 05:58 AM 8/10/2000 -0700, you wrote:
>However, you then get >the nice situation of  (1,0) ------ (1,0).  Doesn't
>look so hot.  I have the artists tag 
> >reflected seam vertices as uncollapsable until very late in the order.
>
>Can you not algorithmically detect this situation as well? Compute the
>tangent-normal basis for the polygon, and look at the derivative of the
>texture coordinates w.r.t the tangent vector - if this changes sign you have
>a seam.
>
>More work, I grant you, and I admit not as flexible as having a tool that
>lets the artists do the markup, but still possible.
>
>Tony Cox - DirectX Luminary
>Windows Gaming Developer Relations Group
>http://msdn.microsoft.com/directx 
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] Bicubic normals for a bicubic world

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

No - in the S shape, each component of the normal goes from value A to value
B and back to value A, which can be described by a quadratic.

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

> -----Original Message-----
> From: John Sensebe [mailto:jse...@ho...]
> Sent: 04 August 2000 14:41
> To: gda...@li...
> Subject: Re: [Algorithms] Bicubic normals for a bicubic world
> 
> 
> Actually, an (n-1) order polynomial can describe the tangent 
> vectors in one
> direction, so the normals would be the cross product of two 
> (n-1) order
> polynomials, one being the tangents in u and one in v.
> 
> Approximating the normals of a bicubic with a single 
> quadratic would lead to
> problems, however. Consider the 2D case, where a bicubic 
> curve can make an
> 'S' shape, but a quadratic can't.
> 
> John Sensebe
> jse...@ho...
> Quantum mechanics is God's way of ensuring that we never 
> really know what's
> going on.
> 
> Check out http://members.home.com/jsensebe to see prophecies 
> for the coming
> Millennium!

Re: [Algorithms] water caustics

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

On Thu, 3 Aug 2000, Charles Bloom wrote:

> It just occurred to me that this could probably
> be hacked pretty convincingly using projective
> texturing.  Any object underwater would just get
> an extra additive pass from a projective texture
> which had some fake caustic lines in it.  If you
> wanted to be fancy, you could even use the
> heightmap of your water to draw some caustic
> lines that resembled the crests of the wave
> surface; totally incorrect, but probably great
> looking for games.
 
There is a nice demo of exactly that - called 'Atlantis'
IIRC.  You should find it one one of the OpenGL sites
out there.  It has whales and sharks swimming around
in a blue fog with projective texture caustics.

It looks pretty good - although a better choice of
caustic texture could have been made IMHO.

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] 3d Lines Intersection

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

> > But the explanation of the math behind an algorithm, or maybe a couple
> > of different algorithms, is a lot more informative than a pointer to
> > somone else's code, isn't it?
> >
> 
> Many of the people here would rather have the code than the
> explanation...code they can use. If they could use the explanation then they
> probably could have been worked it out themselves as it sounds you might be
> able to.  They probably came to this list because they couldn't find the
> code library to use...i.e. a function that returns a point when giving it
> two lines.  Or, they want to write the code themselves in which case they
> just want the formula/algorithm in a format that they can code with.

I'm with Ron on this one.  I would rather have the
explanation first, that way if I get code with it,
I may or may not be able to use it in my own stuff.

The biggest problem is people trying to write black
boxes for everything and saying here use this.  Only
after all your searching and browsing do you find out 
that you have two female connectors. DOH! (ie. Data
structures are RARELY compatible between software
components.)

Also, code is harder to read than english.  At least
I think so.

Just my 2cents,
-DaveS

Re: [Algorithms] finding an optimal OBB

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

Yeah. Another $50 dollar book I need to buy
only for a reference.  I liked his old site
better.  :-(

I assume you read the paper on OBBTree's.
I don't have it with me or I'd give you the 
reference.

They talked about sampling the convex hull to
find a tighter fit bbox. 

I don't know what MgcContainment does, if that's
similar or not.

-DaveS


Corrinne Yu wrote:
> 
> Your savior and mine, magic source code.
> http://www.magic-software.com/MgcContainment.html
> Thank you, Dave E. My Dave E. book is on its way, and am looking forward to
> it.
> 
> The math here (Ron L. would have to correct me if I were wrong about this)
> is better / more correct than most on-line tutorials, papers and algorithms.
> 
> Corrinne Yu

RE: [Algorithms] finding an optimal OBB

[Jason F. <Jas...@co...>]

Are you referring to his new book, "3D Game Engine Design: A Practical
Approach to Real-Time Computer Graphics" ??  I was seriously thinking about
picking that one up...

---------------------------
Jason H. Frisvold
Head ATM Engineer
Engineering Dept.
Penteledata
fr...@co...
---------------------------
"All our science measured against reality, is primitive and childlike--and
yet it is the most precious thing we have." - Albert Einstein

-----Original Message-----
From: Corrinne Yu [mailto:cor...@ho...]
Sent: Thursday, August 10, 2000 9:47 AM
To: gda...@li...
Subject: Re: [Algorithms] finding an optimal OBB


Your savior and mine, magic source code.
http://www.magic-software.com/MgcContainment.html
Thank you, Dave E. My Dave E. book is on its way, and am looking forward to
it.

The math here (Ron L. would have to correct me if I were wrong about this)
is better / more correct than most on-line tutorials, papers and algorithms.

Corrinne Yu




----- Original Message -----
From: "Charles Bloom" <cb...@cb...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 2:01 PM
Subject: [Algorithms] finding an optimal OBB


>
> I'm sure there are lots of papers on this - any
> good pointers?  I want to find the tightest
> possible OBB for a collection of points.
>
> --------------------------------------
> Charles Bloom           www.cbloom.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] finding an optimal OBB

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

Corrinne Yu  wrote:

>Your savior and mine, magic source code.
>http://www.magic-software.com/MgcContainment.html
>Thank you, Dave E. My Dave E. book is on its way, and am looking forward to
>it.
>
>The math here (Ron L. would have to correct me if I were wrong about this)
>is better / more correct than most on-line tutorials, papers and algorithms.
>

Indeed, Dave Eberly is an authority, his web site is authoritative and
has lots of good stuff. 

Re: [Algorithms] finding an optimal OBB

[Corrinne Y. <cor...@ho...>]

Your savior and mine, magic source code.
http://www.magic-software.com/MgcContainment.html
Thank you, Dave E. My Dave E. book is on its way, and am looking forward to
it.

The math here (Ron L. would have to correct me if I were wrong about this)
is better / more correct than most on-line tutorials, papers and algorithms.

Corrinne Yu




----- Original Message -----
From: "Charles Bloom" <cb...@cb...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 2:01 PM
Subject: [Algorithms] finding an optimal OBB


>
> I'm sure there are lots of papers on this - any
> good pointers?  I want to find the tightest
> possible OBB for a collection of points.
>
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

RE: [Algorithms] VIPM and UV texturing

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

>One particular problem I will share that comes up often is when texturing
characters.  My >system automatically will preserve vertices that have
texture coordinate discontinuities.  >However, artists will often model a
character with only half of the texture (particularly >in the face) then
just reflect the texture coords to save texture space.
>
>Now the problem as you would guess is you have the face with coordinates
like (1,0) -----  >(0,0) ---- (1,0).  Obviously more granular then that.
There are no texture coordinate 
>discontinuities so the algorithm says it is ok.  The surface of the face is
roughly flat 
>so the internal vertex and edges are good candidates for collapse.
However, you then get >the nice situation of  (1,0) ------ (1,0).  Doesn't
look so hot.  I have the artists tag 
>reflected seam vertices as uncollapsable until very late in the order.

Can you not algorithmically detect this situation as well? Compute the
tangent-normal basis for the polygon, and look at the derivative of the
texture coordinates w.r.t the tangent vector - if this changes sign you have
a seam.

More work, I grant you, and I admit not as flexible as having a tool that
lets the artists do the markup, but still possible.

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

Re: [Algorithms] VIPM and UV texturing

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

Check Stan Melax feedback page about handling tex coords.
http://www.cs.ualberta.ca/~melax/polychop/feedback/

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


----- Original Message -----
From: "Mark Wayland" <mwa...@to...>
To: <gda...@li...>
Sent: Tuesday, August 08, 2000 1:58 AM
Subject: [Algorithms] VIPM and UV texturing


> Hey all,
>
> For those of you who are using/experimenting with VIPM, how are you
> generating your texture coords when the mesh is reduced ?  Do you all
assume
> planar mapping or what ?
> Any info or discussion on this topic would be appreciated.
>
> Thanks,
>
> Mark
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] View-Depend vs. View-Independent LOD

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

If you look at the amount of CPU work required for VIPM, it's tiny. And you
don't touch any vertex data, just indices. It certainly is useful for scenes
with lots of people - my characters go up to around 120ktris each. Draw
twenty of them at full rez, and you'll kill even the best chip. VIPM is
absoloutely required for this sort of stuff, and it's very fast.

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

> -----Original Message-----
> From: Pai-Hung Chen [mailto:pa...@ac...]
> Sent: 09 August 2000 22:03
> To: gda...@li...
> Subject: Re: [Algorithms] View-Depend vs. View-Independent LOD
> 
> 
> In a HW T&L setting (GeForce), are VIPM/VDPM really worth the extra
> management cost omposed on CPU?  Or a simple Quadtree/Octree 
> paradigm will
> suffice, in which I may well just send the un-LODed polys to 
> the HW T&L
> pipeline that is so fast at handling huge amount of polys 
> that it still
> beats the LOD optimization?
> 
> Thank you,
> 
> Pai-Hung Chen
> 
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] GJK

[Jenny A. <aj...@fr...>]

I studied this algorithm months ago, so let's go :

I suppose that you have two polytope, that is two set of vertices, which
are supposed to be convex (for concave object, you have to decompose the
object in a sum of concave object, but that's quiet complex).

So finding, these closest points is equivalent to find the closest point
from origin to minkoski sum of the object (quiet easy to check).

The GTK algorithm creates a set of simplex which is imbricated, that is
the new simplex is smaller that the previous one and so on. And as the
number
of vertex is not infinite, the algorithm ends in a finite time.

For the details of the set construction, I'm afraid that you should read
original paper, or this one, which improves time coherance of the algorithm
:

A fast and robust GTK implementation for collision detection of convex
objects, Gino van den Bergen
http://www.win.tue.nl/cs/tt/gino/solid/index.html#papers

Alexandre

-----Message d'origine-----
De : Pierre Terdiman [mailto:p.t...@wa...]
Envoyé : jeudi 10 août 2000 02:03
À : gda...@li...
Objet : [Algorithms] GJK


Hi,

I'd like to implement my own version of the GJK algorithm involved in
collision detection, without just using any of the available packages
(Solid, Stephen Cameron's version, etc). But I admit I have some
difficulties with the theory behind it. Is there any GJK expert here, who
would be kind enough to briefly summarize that algorithm? For example, even
Gilbert's underlying layer - that is, Johnson's algorithm to compute the
closest point to the origin for a simplex - looks quite weird to me. The
original paper by Gilbert is quite painful to read IMHO, and I don't really
understand what's going on here. So, to start with, if someone can explain
in a few words Johnson's algorithm, it would be cool. I'm familiar with
Minkowski sums, supporting vertices and most of the usual terminology, so
don't be afraid to use the right words in the right place.

Pierre



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

RE: [Algorithms] Ray-AABB intersection

[Zhang Z. S. <Zha...@ub...>]

There is an error in the book. But the source i downloaded from the Internet
seems right.

	/* Check final candidate actually inside box */
	if (maxT[whichPlane] < 0.) return (FALSE);
	for (i = 0; i < NUMDIM; i++)
		if (whichPlane != i) {
			coord[i] = origin[i] + maxT[whichPlane] *dir[i];
			if (coord[i] < minB[i] || coord[i] > maxB[i])
				return (FALSE);
		} else {
			coord[i] = candidatePlane[i];
		}
	return (TRUE);				/* ray hits box */

-----Original Message-----
From: Pierre Terdiman [mailto:p.t...@wa...]
Sent: Thursday, August 10, 2000 12:03 PM
To: gda...@li...
Subject: [Algorithms] Ray-AABB intersection


Is there any known problem with Andrew Woo's Ray-AABB intersection code? (in
Graphic Gems I). It seems to miss some intersections... (?)


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

[Algorithms] Ray-AABB intersection

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

Is there any known problem with Andrew Woo's Ray-AABB intersection code? (in
Graphic Gems I). It seems to miss some intersections... (?)

[Algorithms] GJK

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

Hi,

I'd like to implement my own version of the GJK algorithm involved in
collision detection, without just using any of the available packages
(Solid, Stephen Cameron's version, etc). But I admit I have some
difficulties with the theory behind it. Is there any GJK expert here, who
would be kind enough to briefly summarize that algorithm? For example, even
Gilbert's underlying layer - that is, Johnson's algorithm to compute the
closest point to the origin for a simplex - looks quite weird to me. The
original paper by Gilbert is quite painful to read IMHO, and I don't really
understand what's going on here. So, to start with, if someone can explain
in a few words Johnson's algorithm, it would be cool. I'm familiar with
Minkowski sums, supporting vertices and most of the usual terminology, so
don't be afraid to use the right words in the right place.

Pierre

Re: [Algorithms] VIPM and UV texturing

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

Thanks one and all for your contributions, things are infinitely clearer now
...

Mark

----- Original Message -----
From: "Charles Bloom" <cb...@cb...>
To: <gda...@li...>
Sent: Thursday, August 10, 2000 4:15 AM
Subject: Re: [Algorithms] VIPM and UV texturing


>
> Hi Jeff,
>
> really, you should be including UV's and RGB's and Normals as
> part of the quadric error metric, so that this kind of thing
> should be detected automagically, and should be put late in
> the collapse list by the system.  I've found that if you
> use a proper (eg. comprehensive and robust) error metric,
> then almost zero artist intervention is necessary.  In fact,
> I find that the system is generally much better at ordering
> collapses than artists are.  Of course, there are exceptions,
> which usually occur because of the fact that I'm not actually
> looking in the texture bits; eg. changing the uv's slightly
> in a region of the texture which is very high frequency
> produces much more visual error than if you change the uv's in
> a very low frequency region of the texture.  To handle this
> correctly, you do need some sort of artist cue, as you propose.
> I like Tom's method of reducing to a specific mesh.
>
> At 10:06 AM 8/9/2000 -0700, you wrote:
> >Now the problem as you would guess is you have the face with coordinates
> like (1,0) -----  (0,0) ---- (1,0).  Obviously more granular then that.
> There are no texture coordinate discontinuities so the algorithm says it
is
> ok.  The surface of the face is roughly flat so the internal vertex and
> edges are good candidates for collapse.  However, you then get the nice
> situation of  (1,0) ------ (1,0).  Doesn't look so hot.  I have the
artists
> tag reflected seam vertices as uncollapsable until very late in the
order.>
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] VIPM and UV texturing

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

Now this sounds like a cool idea :)

Mark

----- Original Message -----
From: "Tom Forsyth" <to...@mu...>
To: <gda...@li...>
Sent: Thursday, August 10, 2000 3:32 AM
Subject: RE: [Algorithms] VIPM and UV texturing


> This is also solved if you start with a low-poly mesh from the artists,
> tesselate and displace up to a high-poly mesh, then VIPM down again, but
> preserving the original edges. Because the tesselation only uses linear
> interpolation for non-geometry attributes, you don't have to deal with
nasty
> cases like this. Fortunately, coz they are a real pain.
>
> http://www.muckyfoot.com/downloads/tom.shtml
>
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
>
> > -----Original Message-----
> > From: Jeff Lander [mailto:je...@di...]
> > Sent: 09 August 2000 18:06
> > To: gda...@li...
> > Subject: Re: [Algorithms] VIPM and UV texturing
> >
> >
> > Hi all.  New to this discussion but I have recently had a
> > couple of projects where this issue has been very important.
> >
> > The issue you bring up about texture coordinates and any sort
> > of mesh LOD system is critical.  That is why I insist that
> > the LOD tools allow artists to hand designate edges that will
> > not collapse.  Any algorithmic method you try and find will
> > fail in certain cases.  The algorithms handle texture
> > projections like sphere and cylinder wraps pretty well but
> > arbitrary UV texturing is a real problem.
> >
> > One particular problem I will share that comes up often is
> > when texturing characters.  My system automatically will
> > preserve vertices that have texture coordinate
> > discontinuities.  However, artists will often model a
> > character with only half of the texture (particularly in the
> > face) then just reflect the texture coords to save texture space.
> >
> > Now the problem as you would guess is you have the face with
> > coordinates like (1,0) -----  (0,0) ---- (1,0).  Obviously
> > more granular then that. There are no texture coordinate
> > discontinuities so the algorithm says it is ok.  The surface
> > of the face is roughly flat so the internal vertex and edges
> > are good candidates for collapse.  However, you then get the
> > nice situation of  (1,0) ------ (1,0).  Doesn't look so hot.
> > I have the artists tag reflected seam vertices as
> > uncollapsable until very late in the order.
> >
> > Let me paraphrase you by saying the algorithms are most
> > efficient when working on trivially textured objects.
> > Anything else requires good artist tools and some TLC.
> >
> > -Jeff
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] VIPM and UV texturing

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

Thanks Tom,

The feature edges were what I am referring to ... what I'm trying to get at
is
that simple edge collapsing doesn't work _across_ a feature edge (yielding
the
undesired incorrect texture interpolation performed _by the card_, not me).

Fortunately you're a bit more eloquent (spelling?) than I :)

Your explanation is very much appreciated.

Thanks,

Mark

----- Original Message -----
From: "Tom Forsyth" <to...@mu...>
To: <gda...@li...>
Sent: Wednesday, August 09, 2000 7:19 PM
Subject: RE: [Algorithms] VIPM and UV texturing


> > From: Mark Wayland [mailto:mwa...@to...]
> [snip]
> > I cite different vertices because the actual UV coords are different
> > (eg. a vertex is NOT just gemoetry, as in the D3D definition)
> >
> > Doesn't anyone use large meshes that are textured using
> > multiple textures
> > with VIPM,
> > in that you would want the mesh as a whole to reduce, not the
> > similarly
> > textured "pieces" ?
>
> Ugh - no. Who would want to do that? :-)
>
> Actually, yes. Edges where two textures meet (or indeed any discontinuous
> data - colours, normals, etc) are what I call "feature" edges. The way I
> deal with them is that you find all your feature eges, and then only allow
> collapses _along_ edges and _onto_ edges. But I never allow collapses of a
> vertex on a feature edge onto a another vertex that isn't on the same edge
> (remember to disallow collapses of one feature vertex to another feature
> vertex that _isn't_ on the same edge, e.g. between two parallel feature
> edges).
>
> But the fewer feature edges you have on your model, the better VIPM can
cope
> with it, and the better it collapses.
>
> > What I'm tending to now assume is that most users of VIPM are
> > using it on
> > trivially textured
> > objects ... would this be a fair assumption, or once again
> > have I missed
> > something ?
>
> I dunno about "trivially" - mapping textures onto humanoid models (and
> indeed the not-so-humanoid - we have slugs, two-headed creatures and ones
> with four arms in Startopia) can get quite tricky.
>
> But yes, VIPM only works well when there are comparatively few feature
> edges.
>
> There are some schemes that try to perform collapses across feature edges.
> One is Jan Svarovsky's (follow the GDC link from the ultra-minimalist
> homepage: http://www.svarovsky.com/), which has a discussion of these
> collapses. But they're not pretty, and they complicate the collapse
process.
> By far the best way to proceed is to use friendly persuasion and Pavlovian
> conditioning (a big stick is handy for this) until the artists to create
> models with few feature edges.
>
> Tom Forsyth - Muckyfoot bloke.
> Whizzing and pasting and pooting through the day.
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list