You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(390) 
_{Aug}
(767) 
_{Sep}
(940) 
_{Oct}
(964) 
_{Nov}
(819) 
_{Dec}
(762) 

2001 
_{Jan}
(680) 
_{Feb}
(1075) 
_{Mar}
(954) 
_{Apr}
(595) 
_{May}
(725) 
_{Jun}
(868) 
_{Jul}
(678) 
_{Aug}
(785) 
_{Sep}
(410) 
_{Oct}
(395) 
_{Nov}
(374) 
_{Dec}
(419) 
2002 
_{Jan}
(699) 
_{Feb}
(501) 
_{Mar}
(311) 
_{Apr}
(334) 
_{May}
(501) 
_{Jun}
(507) 
_{Jul}
(441) 
_{Aug}
(395) 
_{Sep}
(540) 
_{Oct}
(416) 
_{Nov}
(369) 
_{Dec}
(373) 
2003 
_{Jan}
(514) 
_{Feb}
(488) 
_{Mar}
(396) 
_{Apr}
(624) 
_{May}
(590) 
_{Jun}
(562) 
_{Jul}
(546) 
_{Aug}
(463) 
_{Sep}
(389) 
_{Oct}
(399) 
_{Nov}
(333) 
_{Dec}
(449) 
2004 
_{Jan}
(317) 
_{Feb}
(395) 
_{Mar}
(136) 
_{Apr}
(338) 
_{May}
(488) 
_{Jun}
(306) 
_{Jul}
(266) 
_{Aug}
(424) 
_{Sep}
(502) 
_{Oct}
(170) 
_{Nov}
(170) 
_{Dec}
(134) 
2005 
_{Jan}
(249) 
_{Feb}
(109) 
_{Mar}
(119) 
_{Apr}
(282) 
_{May}
(82) 
_{Jun}
(113) 
_{Jul}
(56) 
_{Aug}
(160) 
_{Sep}
(89) 
_{Oct}
(98) 
_{Nov}
(237) 
_{Dec}
(297) 
2006 
_{Jan}
(151) 
_{Feb}
(250) 
_{Mar}
(222) 
_{Apr}
(147) 
_{May}
(266) 
_{Jun}
(313) 
_{Jul}
(367) 
_{Aug}
(135) 
_{Sep}
(108) 
_{Oct}
(110) 
_{Nov}
(220) 
_{Dec}
(47) 
2007 
_{Jan}
(133) 
_{Feb}
(144) 
_{Mar}
(247) 
_{Apr}
(191) 
_{May}
(191) 
_{Jun}
(171) 
_{Jul}
(160) 
_{Aug}
(51) 
_{Sep}
(125) 
_{Oct}
(115) 
_{Nov}
(78) 
_{Dec}
(67) 
2008 
_{Jan}
(165) 
_{Feb}
(37) 
_{Mar}
(130) 
_{Apr}
(111) 
_{May}
(91) 
_{Jun}
(142) 
_{Jul}
(54) 
_{Aug}
(104) 
_{Sep}
(89) 
_{Oct}
(87) 
_{Nov}
(44) 
_{Dec}
(54) 
2009 
_{Jan}
(283) 
_{Feb}
(113) 
_{Mar}
(154) 
_{Apr}
(395) 
_{May}
(62) 
_{Jun}
(48) 
_{Jul}
(52) 
_{Aug}
(54) 
_{Sep}
(131) 
_{Oct}
(29) 
_{Nov}
(32) 
_{Dec}
(37) 
2010 
_{Jan}
(34) 
_{Feb}
(36) 
_{Mar}
(40) 
_{Apr}
(23) 
_{May}
(38) 
_{Jun}
(34) 
_{Jul}
(36) 
_{Aug}
(27) 
_{Sep}
(9) 
_{Oct}
(18) 
_{Nov}
(25) 
_{Dec}

2011 
_{Jan}
(1) 
_{Feb}
(14) 
_{Mar}
(1) 
_{Apr}
(5) 
_{May}
(1) 
_{Jun}

_{Jul}

_{Aug}
(37) 
_{Sep}
(6) 
_{Oct}
(2) 
_{Nov}

_{Dec}

2012 
_{Jan}

_{Feb}
(7) 
_{Mar}

_{Apr}
(4) 
_{May}

_{Jun}
(3) 
_{Jul}

_{Aug}

_{Sep}
(1) 
_{Oct}

_{Nov}

_{Dec}
(10) 
2013 
_{Jan}

_{Feb}
(1) 
_{Mar}
(7) 
_{Apr}
(2) 
_{May}

_{Jun}

_{Jul}
(9) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}
(14) 
_{Feb}

_{Mar}
(2) 
_{Apr}

_{May}
(10) 
_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}

S  M  T  W  T  F  S 





1

2
(2) 
3
(12) 
4
(16) 
5
(43) 
6
(22) 
7
(35) 
8
(4) 
9
(5) 
10
(6) 
11
(2) 
12
(17) 
13
(5) 
14
(8) 
15
(5) 
16
(10) 
17
(11) 
18
(6) 
19
(14) 
20
(1) 
21

22
(2) 
23
(8) 
24
(2) 
25
(1) 
26
(4) 
27
(31) 
28
(28) 
29
(1) 
30
(4) 
31
(12) 
From: Tom van Dijck <tom@mu...>  20040131 23:12:44

Uhm.... you just don't use it.... The preprocessing pipeline should strip most of the geometry to reduce vertex count. Otherwise, in case you really want to use it, you still have to do some preprocessing, to make sure each batch does not use indices outside the batch, and since batches are rather small, I think it is of no use to do so... But my guess is, that this is kinda offtopic by now, since we are going to discuss PS2 specifics, I guess we could better continue on the ps2newgroups, before Brian is kicking our butts..  Original Message  From: "Jani Kajala" <kajala@...> To: <gdalgorithmslist@...> Sent: Saturday, January 31, 2004 11:37 PM Subject: Re: [Algorithms] indexed face list efficiency > > VUs can use indices efficiently enough, as well as posttransform caching. > > The performance implications aren't exactly the same as on other hardware > > How do you handle the VU1 memory limit when using indexing? > > > Regards, > Jani > >  Original Message  > From: "Rok Erjavec" <rok@...> > To: <gdalgorithmslist@...> > Sent: Friday, January 09, 2004 11:08 AM > Subject: Re: [Algorithms] indexed face list efficiency > > > > > Until you start coding on PS2 though... the damn machine doesn't even > know > > > what indices are... > > VUs can use indices efficiently enough, as well as posttransform caching. > > The performance implications aren't exactly the same as on other hardware > > (ie. prelit or trivial shader geometry may actually run slower with > > indexing) but it's still usefull. > > > > > > >  > The SF.Net email is sponsored by EclipseCon 2004 > Premiere Conference on Open Tools Development and Integration > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > http://www.eclipsecon.org/osdn > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: Jamie Fowlston <jamief@qu...>  20040131 23:09:12

chop your model up :) jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Jani Kajala Sent: 31 January 2004 22:37 To: gdalgorithmslist@... Subject: Re: [Algorithms] indexed face list efficiency > VUs can use indices efficiently enough, as well as posttransform caching. > The performance implications aren't exactly the same as on other hardware How do you handle the VU1 memory limit when using indexing? Regards, Jani  Original Message  From: "Rok Erjavec" <rok@...> To: <gdalgorithmslist@...> Sent: Friday, January 09, 2004 11:08 AM Subject: Re: [Algorithms] indexed face list efficiency > > Until you start coding on PS2 though... the damn machine doesn't even know > > what indices are... > VUs can use indices efficiently enough, as well as posttransform caching. > The performance implications aren't exactly the same as on other hardware > (ie. prelit or trivial shader geometry may actually run slower with > indexing) but it's still usefull. >  The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 35 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Jani Kajala <kajala@ga...>  20040131 22:37:48

> VUs can use indices efficiently enough, as well as posttransform caching. > The performance implications aren't exactly the same as on other hardware How do you handle the VU1 memory limit when using indexing? Regards, Jani  Original Message  From: "Rok Erjavec" <rok@...> To: <gdalgorithmslist@...> Sent: Friday, January 09, 2004 11:08 AM Subject: Re: [Algorithms] indexed face list efficiency > > Until you start coding on PS2 though... the damn machine doesn't even know > > what indices are... > VUs can use indices efficiently enough, as well as posttransform caching. > The performance implications aren't exactly the same as on other hardware > (ie. prelit or trivial shader geometry may actually run slower with > indexing) but it's still usefull. > 
From: Crosbie Fitch <crosbie@cy...>  20040131 21:22:42

How about tesselating a sphere and precomputing indices to bounding circles? Say your sphere is tesselated in regular polygons (bar peculiar tiles). You tabulate a list of all potential minimal bounding circles (for all permutations of tesselation pattern). Each polygon contains a list of indices to all circles that contain it. You then project your cones and wherever they cover or intersect with a tile, the whole tile is marked, and all indexed circles are rejected. What you are then left with is a list of virgin circles. If you've ordered them by size, it should be easy to find the largest. This is then your candidate minimal bounding circle. You can shrink this by the diameter of a tile, and create a rejection circle and reject all cones that fall within it. You could conduct this process iteratively on successively greater resolution tesselated spheres. Perhaps you map a peculiar tile to your cones' centroid (to eliminate it and its antipode from consideration  if the peculiarities are only at poles)? There may also be symmetry optimisations available. 
From: Kyle Wilson <kyle@ga...>  20040131 20:56:36

Stephan Rose wrote: > Ok here's the problem... > > Have an arbitrary polygon... > > Need to figure out a way to create a list of triangles out of this for the > video card to render...correctly if at all possible. :) I recommend Seidel's algorithm. You can find an implementation used in realtime graphics at: http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html Delaunay triangulation would probably produce betterlooking results (fewer long, thin triangles), but be much slower. Regards, Kyle 
From: Jamie Fowlston <jamief@qu...>  20040131 20:37:49

googling for 'tessellate polygon' seems to turn up lots of relevant hits. Last time this discussion came round, lots of people pointed at OGL (e.g. http://www.sgi.com/software/opengl/glandx/xlib/subsubsection3_2_2_1.html). jamie Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Stephan Rose Sent: 31 January 2004 20:00 To: gdalgorithmslist@... Subject: [Algorithms] Polygon to triangles Ok here's the problem... Have an arbitrary polygon... It is 2D only... Can be convex... Can be concave... Can be self intersecting... (although I could live without this case, but it'd be nice if I can handle it) Need to figure out a way to create a list of triangles out of this for the video card to render...correctly if at all possible. :) I've been trying to google on this but so far have had no luck... So I thought I'd ask here..any ideas anyone? Thanks, Stephan  The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 35 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Stephan Rose <kermos@so...>  20040131 20:03:38

Ok here's the problem... Have an arbitrary polygon... It is 2D only... Can be convex... Can be concave... Can be self intersecting... (although I could live without this case, but it'd be nice if I can handle it) Need to figure out a way to create a list of triangles out of this for the video card to render...correctly if at all possible. :) I've been trying to google on this but so far have had no luck... So I thought I'd ask here..any ideas anyone? Thanks, Stephan 
From: Tom Forsyth <tom.forsyth@ee...>  20040131 11:20:47

I think it's O(n^3) actually! n for the first vector, n for the second, = then n to check if that plane is on the hull. But yes, interesting idea. I think it should be fairly straightforward = to be able to take two cones and find the two planes that bound them (the = cones themselves are "end caps"). So you don't need to test a whole bunch of vectors on the cones, which helps. > Using this plane, and the other vector, shoot a vector down=20 > the center.=20 > This is the direction of the new cone, and the angle can be derived=20 > from the plane and vector (V) the you found. Not sure this is true. In general, the planes that you're finding will = _not_ touch the final bounding cone, so they're not chords. But iffthey are on = the bounding _hull_, then that means the cones they are between will touch = the bounding cone. But once you know which the magic three cones are, I think you can = either do it analytically, just anneal the solution down to an acceptable one. Annealing at this stage is fine because you know which three it is, so = it's not an O(n^something)  it's just a vaguely constant cost. Someone also mentioned finding the frustum planes directly rather than making a final single bounding cone. That's definately an interesting idea. TomF. > Original Message > From: gdalgorithmslistadmin@...=20 > [mailto:gdalgorithmslistadmin@...] On=20 > Behalf Of John Pollard > Sent: 29 January 2004 04:48 > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Bounding cones. >=20 >=20 > Hmm, maybe this would work, but it may be a bit slow: >=20 > For each cone, build a list vectors that wrap around the cones origin=20 > (they would start at the origin, and travel along the cone=20 > hull). The=20 > number of vectors for each cone would be a function of each cones=20 > cos(theta). >=20 > Take two neighboring vectors (they should be neighbors, and belong to=20 > the same cone), and create a plane, where the normal should=20 > point away=20 > from all other vector end points. If all other vectors are=20 > on the back=20 > side of this plane, this is the correct plane, otherwise=20 > choose another=20 > two neighboring vectors until you find the correct plane. >=20 > If you don't find any planes that satisfy this, you can't solve it.=20 > Basically, we're looking for planes that are in the outer=20 > edge of the cones. >=20 > While checking if this was the correct plane, remember the=20 > vector that=20 > was the farthest from this plane, call the vector V, and the dist D. >=20 > Of all the planes that you find, choose the plane with the largest D. >=20 > Using this plane, and the other vector, shoot a vector down=20 > the center.=20 > This is the direction of the new cone, and the angle can be derived=20 > from the plane and vector (V) the you found. >=20 > Hope this makes sense. It's probably a tad bit slow, as it's=20 > O(n2), but=20 > could be a good starting point? >=20 > Tom Forsyth wrote: >=20 > > I have a bunch of circularcrosssection cones in 3D space,=20 > all originating > > from a single point (assume it's the origin). They are defined by a > > unitlength vector V (the central axis) and a cos(theta)=20 > term, where theta > > is half the base angle. All points P on the cone obey the equation > > (P.V)/P=3Dcos(theta). I've worked out the maths to take two=20 > cones and find > > the cone that tightly bounds both of them. So I can merge a=20 > bunch of cones > > by calling this on pairs of cones, but depending on the=20 > order you combine > > them you get a very loosefitting result, and the more=20 > cones you want to > > merge, the looser the result fits. > >=20 > > So I'm wondering if anyone knows a good way to find the=20 > bounding cone of a > > whole bunch of cones. If the cone angle goes over 180 then=20 > it's fine to > > return "don't know", so it doesn't need to handle crazy cases. > >=20 > > I'm using this to find frustums for shadowbuffers  each object is > > represented by a cone from the (point)light that bounds the=20 > mesh, and I want > > to find the frustum that bounds a collection of objects as=20 > tightly as > > possible. > >=20 > > I have a feeling this is a similar problem to finding good=20 > bounding spheres, > > but I don't know how to solve that particularly well=20 > either. It's also > > almost identical to the 2D version  finding bounding=20 > circles  but not > > quite because the circles are the projections of the cones=20 > on the surface of > > the unit sphere  you can't simply project them to a flat=20 > plane and solve > > the problem there because (a) which plane do you use? and=20 > (b) they're not > > circles when you project them, they're ellipses. > >=20 > > TomF. > >=20 > >=20 > >=20 > >=20 > >=20 > >=20 > >  > > The SF.Net email is sponsored by EclipseCon 2004 > > Premiere Conference on Open Tools Development and Integration > > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > > http://www.eclipsecon.org/osdn > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > >=20 >=20 >=20 >=20 >  > The SF.Net email is sponsored by EclipseCon 2004 > Premiere Conference on Open Tools Development and Integration > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > http://www.eclipsecon.org/osdn > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 >=20 
From: John Pollard <johnp@3d...>  20040131 04:40:02

Hmm, maybe this would work, but it may be a bit slow: For each cone, build a list vectors that wrap around the cones origin (they would start at the origin, and travel along the cone hull). The number of vectors for each cone would be a function of each cones cos(theta). Take two neighboring vectors (they should be neighbors, and belong to the same cone), and create a plane, where the normal should point away from all other vector end points. If all other vectors are on the back side of this plane, this is the correct plane, otherwise choose another two neighboring vectors until you find the correct plane. If you don't find any planes that satisfy this, you can't solve it. Basically, we're looking for planes that are in the outer edge of the cones. While checking if this was the correct plane, remember the vector that was the farthest from this plane, call the vector V, and the dist D. Of all the planes that you find, choose the plane with the largest D. Using this plane, and the other vector, shoot a vector down the center. This is the direction of the new cone, and the angle can be derived from the plane and vector (V) the you found. Hope this makes sense. It's probably a tad bit slow, as it's O(n2), but could be a good starting point? Tom Forsyth wrote: > I have a bunch of circularcrosssection cones in 3D space, all originating > from a single point (assume it's the origin). They are defined by a > unitlength vector V (the central axis) and a cos(theta) term, where theta > is half the base angle. All points P on the cone obey the equation > (P.V)/P=cos(theta). I've worked out the maths to take two cones and find > the cone that tightly bounds both of them. So I can merge a bunch of cones > by calling this on pairs of cones, but depending on the order you combine > them you get a very loosefitting result, and the more cones you want to > merge, the looser the result fits. > > So I'm wondering if anyone knows a good way to find the bounding cone of a > whole bunch of cones. If the cone angle goes over 180 then it's fine to > return "don't know", so it doesn't need to handle crazy cases. > > I'm using this to find frustums for shadowbuffers  each object is > represented by a cone from the (point)light that bounds the mesh, and I want > to find the frustum that bounds a collection of objects as tightly as > possible. > > I have a feeling this is a similar problem to finding good bounding spheres, > but I don't know how to solve that particularly well either. It's also > almost identical to the 2D version  finding bounding circles  but not > quite because the circles are the projections of the cones on the surface of > the unit sphere  you can't simply project them to a flat plane and solve > the problem there because (a) which plane do you use? and (b) they're not > circles when you project them, they're ellipses. > > TomF. > > > > > > >  > The SF.Net email is sponsored by EclipseCon 2004 > Premiere Conference on Open Tools Development and Integration > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > http://www.eclipsecon.org/osdn > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > 
From: Jonathan Blow <jon@nu...>  20040131 04:36:47

> up. If that doesn't solve it, I may end up rewriting the normal map shader > we're using entirely (it was one of the Neb2default ones)  maybe there's a > bug in it, and it would be good experience anyways. To be clear, it's not a matter of a bug or not a bug. The ATI shader works fine, and I'm sure the normal map shader you are using works fine. The issue is that there are several different ways to do things, so the tools on both sides have to match. The best option for this is to thoroughly understand what the generation tool does so you can just write the shader yourself. Failing that, you could just find a matched set of tool and shader (I'm sure the ATI tool has one). Modeling the higherres mesh even higher isn't going to magically fix the problem; it's not that kind of problem. 
From: tweety <mitea@sy...>  20040131 04:14:24

Look, thank you for your answers, both on the list and off it, but this is getting a lot more offtopic than my initial post (which, as it's been said, is not so much offtopic). This last post is just a flame. Please, stop responding. Again, thank you.  Peace and love, Tweety mitea@...  tweety_04_01@... YahooID: tweety_04_01 Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Tom Plunket Sent: January 27, 2004 5:01 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Game engine question > > He's asking what algorithm he should use that is (a) object > > oriented, and (b) minimizes texture swaps. > > The answer is, there isn't one. Obviously. There is rarely one solution to a given problem. Indeed, there are MANY ways that one could do this. > Well, you could maybe concoct something that is really complex and > weird and you manage to convince yourself is objectoriented, but at > that point you've dug yourself into a bunch of silliness. One of the implicit requirements should have been "is not complex and weird". This doesn't seem too farfetched to me. > Objectoriented design assumes a certain organization of your control > and data hierarchy. But optimization nearly always involves > crosscuts of hierarchies like that. This really should speak more to "this is not the proper OO architecture" than "OO is not useful in this case." One who actually understands OO would know this. > So if the point of your algorithm is to be efficient, you will often > find that it clashes with an objectoriented design (or any other kind > of overly structured design, for that matter). Overengineering is a huge problem in general, but not one that OO either solves or exacerbates. Clearly if your data structures are laid out idiotically then you'll have performance issues, but there's no rule that says to be OO you must be slow and stupid. Let's say that OO says that objects are nouns and their methods are verbs. Let's say that objects know how to do everything that they need to do to get their job done. (These are both things that I feel are valuable ways to think, at some level.) We are not saying that the EnemyAi Render routine plots pixels on the screen. That is SO the opposite of OO that I can't even begin to explain where the problems are. That EnemyAi has a Render call doesn't even mean to imply that the object will be rendered on the screen right now. It could be deferred by whatever other mechanism (be it OO or not) that pools this stuff, does texture sorting, you name it. Back to the OP, there is no one algorithm. However, one needs to consider that there is a layer in between the game code and the render code, and that they are not running in lockstep. To state that this is impossible, unweildy, or otherwise silly to do is simply ignorant. Being ignorant is not, in itself, a problem. The problem comes up when people claim to be experts and their arguments are so ridiculously filled with holes and hyperbole that even a moderately experienced practitioner can sink them with ease. OO is a tool. Nothing more, nothing less. To state that OO is useless for some problems is as valueless as stating that OO is the appropriate solution for all problems. Let's consider actually exploring the possibilities before stating with certainty what it's useful for and what it's not, mmk? tom!  The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 35 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Crosbie Fitch <crosbie@cy...>  20040131 02:32:28

> From: Paul Du Bois > To paraphrase for your case, find the point in S(2) farthest away > from any of your cones Then, one could find the nearest three cones? As those will then be sufficient to define the bounding cone. Dunno if that helps tho. 
From: Jason Mitchell <J<asonm@at...>  20040130 23:24:13

The Nature Demo on this page http://www.ati.com/developer/demos/r8000.html does some simple animation of a field of grass using a few Taylor Series sine waves. The lighting is done by using the same sum of sines to lerp between yellow and green, rather than actually do any lighting math. The details are discussed in the first ShaderX book (www.shaderx.com) in a chapter called "Animated Grass with Pixel and Vertex Shaders" by John Isidoro and Drew Card. There is nothing really sophisticated going on here...just a simple way to give a sense of motion that looks something like a field of animated grass... Let me know if you want the actual shader code. Jason Original Message From: Andrey Iones [mailto:iones@...] Sent: Wednesday, January 28, 2004 1:40 PM To: gdalgorithmslist@... Subject: [Algorithms] Grass animation Gentlemen, Can anyone share the experience of grass field animation using vertex shaders? Thanks, Andrey.  Andrey Iones Project Leader PhD in Computer Science http://www.saber3d.com 
From: <hmmklord@op...>  20040130 23:11:46

I'm thinking of using multilayer terrain (think drakan's terrain). Does anyone know anywhere i can find papers or info on techniques to perform LOD, texture coordinate assignment and culling on multilayer terrain? Thanks Kez 
From: Christian Seger <christian.seger@bt...>  20040130 19:39:38

Hi! Whatever tool you use (ATI's, ORB, or Kaldera, etc, etc) the most important thing (as said by other people) is that your tangent basis are correct. While making ORB and including normal mapping in my engine I tried a bunch of algorithms and find that many are flawed, including ones presented by nvidia and microsoft (in tutorials for example). The one that works in all cases (under the restrictions mentinioned earlier like [0,1] range, etc) is the one by Eric Lengyel in his book Mathematics for 3D game programming and CG, http://www.terathon.com/books/mathgames2.html With his permission I include a .pdf with Ccode that you can copy and paste into your engine. The pdf lies in the ORB.zip at /docs/orb_tangentvectors.pdf http://www.soclab.bth.se/practices/orb.html (direct download): http://www.soclab.bth.se/practices/orb/orb.zip You can also read Eric's post in the Opengl forum http://www.opengl.org/discussion_boards/ubb/Forum3/HTML/011349.html From what I've heard Kaldera is the best, but it does cost some moneys... Soon nvidia will release Melody, we'll see how good that one is, they've been working on it quite long now, tried an alpha a year ago. good luck chris 
From: Guillaume Provost <G<uillaume@ps...>  20040130 19:05:15

Megan, I somewhat concur with previous posts. We also happen to be using the ATI normalmapper tools here and we've definitly gotten much better results than the ones I see in your screenshots.  It seems your tangent space is different then the one that ATI creates.  Make sure that you preview the results of the normal map using the nmfviewer that comes with the ATI normal mapper tools. (simply select the lowres mesh, and then the generated normal map). If it looks bad in their viewer, then you might want to consider checking the following:  Make sure the mesh does not overlap in UV space. For complex pieces like a face, a simple sphere or cylindrical map won't do  you'll need to have your artists manually unwrap the face so that no triangles overlap. Don't mirror the face map either (which would overlap), or you'll get a gradient discontinuity at the mirroring edge.  Make sure that both objects are in the same coordinate spaces (I guess that one was a bit obvious)  The normal mapper tool itself has additional constraints that UVs all lie in the 01 range. I suggest you read (and have your artist read) the readme that accompanies the normalmapper. FYI: our high resolution meshes typically encompass about a quarter to a million polygons for maps ranging from 256>1024 pixels. Cheers Guillaume. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Megan Fox Sent: Wednesday, January 28, 2004 12:50 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Normal mapping error  not sure if it's a generation error, or a rendering error It does look a bit better, but as I thought I said (or at least meant to) in the original email, it really does seem like we should be getting MUCH better results. I agree the painted normals aren't very good... I'm not really sure it's possible to paint good normals anyways  but they do look better than the soup the ATI tool is putting out. TomF, thanks for the input  if anyone happens to know what sort of data the ATI normal mapper tool puts out (and so how to properly handle it), or a better tool period, such would be appreciated. For the moment, the artist is working up a much higherres version to see if that clears the problem up. If that doesn't solve it, I may end up rewriting the normal map shader we're using entirely (it was one of the Neb2default ones)  maybe there's a bug in it, and it would be good experience anyways. Thanks for your help,  Megan Fox > All that said, your handpainted normal mapped mesh doesn't actually > look better than your vertexlit mesh (in the still screenshot). > Normal mapping > is expensive (both in terms of GPU resources and developer resources) > so you should only do it if you are really getting your effort's worth. > Clearly your artist isn't drawing very good normal maps (I mean... I see > a little bit of extra 3Dness around the edges of the eyes and lips... but > that's it).  The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 35 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: Tom Forsyth <tom.forsyth@ee...>  20040129 05:45:05

Yeah, a bounding box aligned to, say, the world axis isn't nearly good enough. Think of two very small objects at (1,1,1) and (10,10,10) relative to the light. The bounding cone is pretty slim. But the bounding box is 9 units on a side, which is enormous! And yes, this is a moderately common case :) TomF. > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...] On > Behalf Of Greg Seegert > Sent: 28 January 2004 20:41 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Bounding cones. > > > I know you asked for an algorithm to merge cones, but for > what you're trying > to do, do you have access to any other information besides > the cone for each > object? I imagine it would be pretty easy to merge the > bounding boxes of > your objects, and form a cone from the light to the center of > the bbox, with > a theta of arcsin(bounding_radius/distance)? I'm sure I'm > missing something > here though  maybe this isn't tight enough of a fit. > > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Tom > Forsyth > Sent: Tuesday, January 27, 2004 2:38 PM > To: gdalgorithmslist@... > Subject: [Algorithms] Bounding cones. > > > I have a bunch of circularcrosssection cones in 3D space, > all originating > from a single point (assume it's the origin). They are defined by a > unitlength vector V (the central axis) and a cos(theta) > term, where theta > is half the base angle. All points P on the cone obey the equation > (P.V)/P=cos(theta). I've worked out the maths to take two > cones and find > the cone that tightly bounds both of them. So I can merge a > bunch of cones > by calling this on pairs of cones, but depending on the order > you combine > them you get a very loosefitting result, and the more cones > you want to > merge, the looser the result fits. > > So I'm wondering if anyone knows a good way to find the > bounding cone of a > whole bunch of cones. If the cone angle goes over 180 then > it's fine to > return "don't know", so it doesn't need to handle crazy cases. > > I'm using this to find frustums for shadowbuffers  each object is > represented by a cone from the (point)light that bounds the > mesh, and I want > to find the frustum that bounds a collection of objects as tightly as > possible. > > I have a feeling this is a similar problem to finding good > bounding spheres, > but I don't know how to solve that particularly well either. It's also > almost identical to the 2D version  finding bounding circles >  but not > quite because the circles are the projections of the cones on > the surface of > the unit sphere  you can't simply project them to a flat > plane and solve > the problem there because (a) which plane do you use? and (b) > they're not > circles when you project them, they're ellipses. > > TomF. > > > > > > >  > The SF.Net email is sponsored by EclipseCon 2004 > Premiere Conference on Open Tools Development and Integration > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > http://www.eclipsecon.org/osdn > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > >  > The SF.Net email is sponsored by EclipseCon 2004 > Premiere Conference on Open Tools Development and Integration > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > http://www.eclipsecon.org/osdn > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: Andrey Iones <iones@sa...>  20040128 21:37:41

Gentlemen, Can anyone share the experience of grass field animation using vertex shaders? Thanks, Andrey.  Andrey Iones Project Leader PhD in Computer Science http://www.saber3d.com 
From: Greg Seegert <greg@st...>  20040128 20:42:13

I know you asked for an algorithm to merge cones, but for what you're trying to do, do you have access to any other information besides the cone for each object? I imagine it would be pretty easy to merge the bounding boxes of your objects, and form a cone from the light to the center of the bbox, with a theta of arcsin(bounding_radius/distance)? I'm sure I'm missing something here though  maybe this isn't tight enough of a fit. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Tom Forsyth Sent: Tuesday, January 27, 2004 2:38 PM To: gdalgorithmslist@... Subject: [Algorithms] Bounding cones. I have a bunch of circularcrosssection cones in 3D space, all originating from a single point (assume it's the origin). They are defined by a unitlength vector V (the central axis) and a cos(theta) term, where theta is half the base angle. All points P on the cone obey the equation (P.V)/P=cos(theta). I've worked out the maths to take two cones and find the cone that tightly bounds both of them. So I can merge a bunch of cones by calling this on pairs of cones, but depending on the order you combine them you get a very loosefitting result, and the more cones you want to merge, the looser the result fits. So I'm wondering if anyone knows a good way to find the bounding cone of a whole bunch of cones. If the cone angle goes over 180 then it's fine to return "don't know", so it doesn't need to handle crazy cases. I'm using this to find frustums for shadowbuffers  each object is represented by a cone from the (point)light that bounds the mesh, and I want to find the frustum that bounds a collection of objects as tightly as possible. I have a feeling this is a similar problem to finding good bounding spheres, but I don't know how to solve that particularly well either. It's also almost identical to the 2D version  finding bounding circles  but not quite because the circles are the projections of the cones on the surface of the unit sphere  you can't simply project them to a flat plane and solve the problem there because (a) which plane do you use? and (b) they're not circles when you project them, they're ellipses. TomF.  The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 35 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 
From: Andrew Willmott <awillmott@ma...>  20040128 18:54:46

Just a thought: * Sum the Vs weighted by solid angle to give V'  take that as your projective plane direction. * Find the farthest point of each projected cone from the origin. Ostensibly you could work out the projected ellipse and work from there, but I bet there's a faster way. * Fit a circle to the points  your enclosing spotlight is in direction V' with theta coming from that circle. Projecting to a plane only starts to fail as the enclosing angle gets up towards 180, which is an acceptable failure case only. This isn't going to be optimal, and maybe the results won't be good enough, but, I can imagine it being reasonably fast, and it doesn't suffer from hysteresis. For better results you could do a bounding ellipse and work backwards to a spotlight that's not aligned with V'. I wonder if it's not faster to drop down a level and do direct frustum plane fitting to the bounding spheres of the objects? A. Tom Forsyth wrote: >I have a bunch of circularcrosssection cones in 3D space, all originating >from a single point (assume it's the origin). They are defined by a >unitlength vector V (the central axis) and a cos(theta) term, where theta >is half the base angle. All points P on the cone obey the equation >(P.V)/P=cos(theta). I've worked out the maths to take two cones and find >the cone that tightly bounds both of them. So I can merge a bunch of cones >by calling this on pairs of cones, but depending on the order you combine >them you get a very loosefitting result, and the more cones you want to >merge, the looser the result fits. > >So I'm wondering if anyone knows a good way to find the bounding cone of a >whole bunch of cones. If the cone angle goes over 180 then it's fine to >return "don't know", so it doesn't need to handle crazy cases. > >I'm using this to find frustums for shadowbuffers  each object is >represented by a cone from the (point)light that bounds the mesh, and I want >to find the frustum that bounds a collection of objects as tightly as >possible. > >I have a feeling this is a similar problem to finding good bounding spheres, >but I don't know how to solve that particularly well either. It's also >almost identical to the 2D version  finding bounding circles  but not >quite because the circles are the projections of the cones on the surface of >the unit sphere  you can't simply project them to a flat plane and solve >the problem there because (a) which plane do you use? and (b) they're not >circles when you project them, they're ellipses. > >TomF. > > > > > > > >The SF.Net email is sponsored by EclipseCon 2004 >Premiere Conference on Open Tools Development and Integration >See the breadth of Eclipse activity. February 35 in Anaheim, CA. >http://www.eclipsecon.org/osdn >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 > > > 
From: Jon Watte <hplus@mi...>  20040128 18:04:35

You absolutely, positively have to use a profiler at this point. I've found crappy implementations of STL to sometimes suck up amazing percentages of CPU. Seeing as you don't run on a cell phone, another thing to post to make the question more answerable is: what CPU, memory speed, memory amount, and graphics card? (Actually, you took out rendering, so that's not as important). How big is each node? I recall that you tried CodeAnalyst, which means you're probably on Athlon. However, I recommend still using VTune (you can download the free trial) in timeerbased sampling mode; it can sample 1000 times a second, and show you where the time is going on a rough scale. Or try running the same app on an Intel CPU, and use real eventbased sampling. Then look at the places where you spend the time, and figure out whether you need to call those places at all. If you do, then figure out whether the problem is pipeline stalls, cache misses, page faults, ... Cheers, / h+ Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Robert Cannell Sent: Wednesday, January 28, 2004 1:41 AM To: gdalgorithmslist@... Subject: RE: [Algorithms] Quadtree speed ups Thank you all for your help so far. I feel silly for having such a problem of what I thought was a simple thing. Learn something new every day :P. > That's way out of bounds, it sounds to me like you are doing something > horribly wrong. If I were you I would log your quadtree traversal for > one frame; I bet you have some O(N^2) (or worse) iteration/recursion > hiding in your program. >If at each and every one of those leaves you go off and call some deep >render path or other routine that kicks the tree out of cache you've just >wasted all that effort in generating a cache friendly layout. I agree with these points also, I just need to find the exact place where it is happening :P. I will attempt to try and log a frame as Thatcher had pointed out. Basically this is all there is to my quadtree node recursion. function node>GetRenerableItems()  Get Child Iterator ( stl hash_map )  Loop through children  call childnode>GetRenderableItems() // If leaf  Get Geometry Iterator  loop through geometry and add to render queue list ( vector ) > For running on a cell phone, this is an amazing frame rate! What algorithm > did you use to get there? It is my own special crappyslow algorithm :). > If there is no change between 33x33 and 17x17, then the bottleneck isn't > there  there's no use trying 65x65 I did realise this, I have removed all my render calls, which didn't make a difference  I was just mentioning this because Ivan had mentioned that 17x17 vertices was too few to be using :). > Original Message > From: gdalgorithmslistadmin@... [mailto:gdalgorithms > listadmin@...] On Behalf Of Thatcher Ulrich > Sent: Wednesday, 28 January 2004 5:15 a.m. > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Quadtree speed ups > > On Jan 27, 2004 at 10:15 +1300, Robert Cannell wrote: > > > > A) Does this sound right for a 16x16 quadtree (4 levels, 256 patches > > when in full view, with 50fps)? Sometimes I think it doesn't, and > > sometimes I think that I have done something horribly wrong ;). > > That's way out of bounds, it sounds to me like you are doing something > horribly wrong. If I were you I would log your quadtree traversal for > one frame; I bet you have some O(N^2) (or worse) iteration/recursion > hiding in your program. > >  > Thatcher Ulrich > http://tulrich.com > > >  > The SF.Net email is sponsored by EclipseCon 2004 > Premiere Conference on Open Tools Development and Integration > See the breadth of Eclipse activity. February 35 in Anaheim, CA. > http://www.eclipsecon.org/osdn > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188  The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 35 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=6188 
From: <castanyo@ya...>  20040128 15:40:39

Megan Fox wrote: > It does look a bit better, but as I thought I said (or at least meant to) in > the original email, it really does seem like we should be getting MUCH > better results. I agree the painted normals aren't very good... I'm not > really sure it's possible to paint good normals anyways  but they do look > better than the soup the ATI tool is putting out. > > TomF, thanks for the input  if anyone happens to know what sort of data the > ATI normal mapper tool puts out (and so how to properly handle it), or a > better tool period, such would be appreciated. Take in mind that you should use the same tangent basis that the normalmapper uses in order to obtain good results. So, if your application generates a different tangent basis that may explain the bad results. You can also try with my normalmapper tool, it's a plugin for max4 or max5.1, you can grab it here: http://www.ludicon.com/castano/files/old/ I used the nvidia MeshMender to compute the tangent basis in that tool, so that it would be easy to reproduce them. The tool is free, but unsupported and discontinued.  Ignacio Castaño castanyo@... 
From: Willem de Boer <wdeboer@pl...>  20040128 12:40:54

> >You can take the structure of Welzl's algorithm (who took it from >Seidel's LP algorithm) and add the necessary operations for your case: > > 1. Test a cone for containment in another cone > 2. Construct a bounding cone for a set of 1 (trivial), 2, or 3 > cones. > >Notably the hull for 3 cones could be a challenge. I think as a reasonable approximation, you could take the average of the 3 Vi's, that make up the three cones {Ci}, and use that as the V for your containing cone. Then compute H (ie., cos(halfangleofV)) from that..?  Willem 
From: Gino van den Bergen <gvandenbergen@pl...>  20040128 11:57:00

> Original Message > From: Tom Forsyth [mailto:tom.forsyth@...] > Sent: Wednesday, January 28, 2004 12:07 > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Bounding cones. >=20 > [Stuff deleted] =20 > Which means that although Nick is (probably) right when he says that any > bounding cone is formed by at most three cones, adding another cone may > produce a new bounding cone that uses a _completely different three_. > Which > is a pain. > It is not as much a pain as it sems. This problem occurs also for bounding spheres. Welzl showed in http://citeseer.nj.nec.com/welzl91smallest.html that on average a randomized algorithm takes only linear time. That is, the number of "painful" moments is relatively small. =20 =20 > However, I suspect the number you actually need to track will be > reasonable > in practice  you should be able to throw most of them away (anything that > is inside the hull is definately never going to be part of the hull in > future). So this is certainly a plausable avenue of attack. You can take the structure of Welzl's algorithm (who took it from Seidel's LP algorithm) and add the necessary operations for your case: 1. Test a cone for containment in another cone 2. Construct a bounding cone for a set of 1 (trivial), 2, or 3 cones. Notably the hull for 3 cones could be a challenge. Gino van den Bergen http://www.dtecta.com =20 
From: Stefan Boberg <stefan.boberg@di...>  20040128 11:31:05

The old scene graph discussion! I think part of the problem is that people have different ideas of what a "scene graph" really is. Many think it's the uberstructure which is used to represent the entire world, some (including myself) have more general definitions. A problem with many generic scene graph implementations is that in practice, they simply perform worse than rendering systems with more hardwired behaviour. This is especially true for the PS2, where memory access is something you really want to avoid. "Pure" OO designs often perform like crud compared to more pragmatic approaches simply because with OO you tend to group data in ways that make sense from a purely structural perspective instead of a performance perspective. A prime example would be your reference to having a node per bone in a skeleton. This does not perform well at all and offers little, if any, benefit. You're much better off describing your skeleton hierarchy using an array of transformation matrices and an array of indices describing the relationships between these transformations. Another really bad idea is having hierarchical state propagation. For example, having some kind of nodes for controlling whether backface culling is on or off, which affects all nodes below it. This "feels" powerful but just ends up complicating and slowing the system down by having to maintain state stacks etc, and it's rarely useful in a reallife scenario. Well, I could go on forever actually but I have to go. This is more of a SWEngtype discussion anyway really. In the end I think this is all about being pragmatic and not getting carried away and overgeneralizing systems if it has little benefit. The problem is that often you won't know this until you tried both approaches ;) /Stefan Stefan Boberg Chief Technical Officer Digital Illusions CE AB 