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}

2015 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}
(12) 
_{Nov}

_{Dec}
(1) 
2016 
_{Jan}

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

_{Jun}
(1) 
_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 




1
(30) 
2
(21) 
3
(16) 
4
(5) 
5
(6) 
6
(44) 
7
(36) 
8
(41) 
9
(25) 
10
(17) 
11
(19) 
12
(7) 
13
(26) 
14
(33) 
15
(30) 
16
(44) 
17
(38) 
18
(10) 
19
(16) 
20
(39) 
21
(44) 
22
(8) 
23
(23) 
24
(49) 
25
(26) 
26
(15) 
27
(41) 
28
(29) 
29
(41) 
30
(40) 


From: Charles Bloom <cbloom@cb...>  20001102 22:37:34

At 07:35 PM 11/2/2000 +0100, Joe Ante wrote: >Now this is all fine, but how do i find out which mipLevel will be needed? >Or how do I (fast) calculate or approximate the biggest size of any texel >given the texture UVs, vertices and OBB around the object? You precompute a number for each modeltexture pair. This number if the largest worldspace area that a texel from that texture is stretched over on that model. This requires some nasty pertriangle math, but it's all a prepass. Now, you take the obb of the object and find the shortest distance from the obb to the camera (much easier with a bounding sphere). If this distance is 0, you need the highest mip. Otherwise, you get the largest screenspace area of a texel by taking the precomputed worldspace area, multiplying by the number of pixels on screen, dividing by the distance to the object squared, and dividing by the area of the texture (in texels) at full resolution. That is : r0 = [ (screen area in pixels) / (texture area in texels) ] * [ (precomputed largest area for one texel) / (shortest distance to object ^2) ] This r0 is a ratio of area in pixels to area in texels, and it's a strict upper bound. The ratio for a mip level L is : r(L) = r0 * 4^L If you have too many texels per pixel (aliasing) then r < .5. If you have too many pixels per texel (blurring) then r > 2. For texture synthesis, you want to use the highest L (smallest mip) for which you don't get blurring, that is r <= 2 . So : L = floor( .5 * log2(2/r0) ) This can be done fast using the wellknown "integer log2 assembly" which can be found on my web page, and at http://www.stereopsis.com Thus, we have L = intlog2( sqrt(2/r0) ) tells you the highest mip level you need. This is in fact the very equation that we (surreal) used to use to generate our synthetic textures (we use "splatting" now). You can also generate the lowest mip level needed, in case you're doing trilinear filtering. To do that, you proceed just as before, but instead of always maximizing, you minimize; for example you use the largest distance to the object instead of the shortest. The lowest mip level is not totally reliable, however, because you may need lower mips due to polygons being at an angle to the camera. If you don't care about this subtlety, everything's fine.  Charles Bloom http://www.cbloom.com 
From: David Kormann <david@ik...>  20001102 21:35:18

> However this approach (which was the one that I used first) gives no > information about how close B and C are to AD, in other words an automatic > metric about how sliverlike the constructed triangles will be is given by > the method I currently use. This is a win (in terms of processor cycles in > the way that I have been approaching the problem), because I don't need to > do golden ratio type checks to prevent more sliver triangles being created. True. > 3.2 triangles are being flipped per constraint. High of 25. Bound to be > different with a different dataset. > Plus, I seem to be doing closer to 1300 edges per frame than 3000 most of > the time. I may peak at around 3000, but possibly if I was running at that > the whole time I might notice a hit on the slower machines  I haven't > checked. That's pretty nice anyway! > A mesh is a mesh is a mesh (just imagine lots of blue triangles with red > constrained edges)... Just curious!... > No. I do use a modified mesh walk using the sign of a rough triangle area > and a couple of tie break metrics though. What modifications are you using > (asked in the hope that you have a neat trick which will fix my occasional > bad case :))? Most of my speed comes from some tricks to pick a good > starting triangle to walk from. Well I noticed that to avoid the infinite loop with contrained edges, instead of computing the the sign of the determinant for one of the edges, I compute the sign for both edges sharing the triangles where I may jump into. The one which has the largest determinant is the best one to go to... and now it never hangs anymore! Cheers, David.  
From: Jay Stelly <Jay@va...>  20001102 21:21:35

Sure, These examples don't actually create the maximal 9sided polygon I was looking for, but now that I see them, I see how you can get a nine sided polygon by clipping a triangle to a AABB. In effect, the plane of the triangle cutting the box creates a hexagon (as in your jpg below). Then the problem effectively becomes clipping the triangle (in the plane) to the hexagon (also in the plane) and it follows trivially that you can get a nine sided polygon from that. Nice. Jay > Original Message > From: Charles Bloom [mailto:cbloom@...] > Sent: Wednesday, November 01, 2000 10:55 PM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] theoretical clipping behavior > > > > Brian's plane screenshots: > > http://www.cbloom.com/plane1.jpg > http://www.cbloom.com/plane2.jpg > http://www.cbloom.com/plane3.jpg > > And the tools I converted them with : > (raw2bmp command line app and other such goodies) > > http://www.cbloom.com/gfxutils.zip > > > > >Sure it is, if I understand what you're talking about... > > > >Given the axisaligned box with extreme corners (0,0,0) and > (1,1,1), all 6 > >of its faces are intersected by the plane defined by the > points (0,0,1), > >(2,0,2) and (0,2,2). I think... > > > >I'd put up screenshots but all I have is GIMP, not Photoshop, and it > >doesn't read raw files. If you have photoshop and care to > see screenshots, > > > >Brian > >========== > >GLSetup, Inc. > > 
From: Charles Bloom <cbloom@cb...>  20001102 20:27:51

Have you seen the "ishadowmap" demo ? http://www.daionet.gr.jp/~masa/ishadowmap/ From what I can tell from the japanese web page, he's doing objectindex shadow mapping. That is, from the light's view you render a shadow map with the index of the object in it. Any pixel is shadowed if the index of the rendering object doesn't match the index in the shadow map. I'm quite impressed by the performance of this demo. (btw Radeon is supposed to be able to do this natively in hardware, right?). I guess the only tricky part is doing that last texture op : if ( texture != const ) > black, else > white I'm not quite sure how to do that efficiently...  Charles Bloom http://www.cbloom.com 
From: <ron@do...>  20001102 20:09:23

Kent Quirk wrote: >Ron Levine wrote: >> >> Andrew Sega wrote: >> >> > >> >I actually meant to say "axisaligned" instead of "arbitrary", chalk that up >> >to temporary insanity. Seven is what I had determined heuristically, but >> >your explanation makes more sense (i.e. each clipping plane at worst >> >generates an edge). >> > >> >So, given that a large enough triangle is equivalent to an infinite plane as >> >far as we're concerned: How many face intersections can an infinite plane >> >cause with an AABB? I can't imagine a case in my head where it could touch >> >more than 5 sides, but perhaps someone has a counterexample? >> > >> >> A plane intersects all 6 faces of a box if and only if it is the >> (unique) plane containing a diagonally opposite pair of edges >> >> A plane intersects 5 or 6 of the faces of a box if and only if >> contains an edge of the box. > >Um, either I'm misunderstanding something or this is incorrect. > >I can make one cut through a cube and intersect all six faces without >having the cut contain any edge of the cube. Isn't that the situation >being described here? > >Please see: http://www.cognitoy.com/cutcube.jpg > Of course you are right. I was thinking in the smaller box of planes parallel to an axis. 
From: Dave Smith <Dave.Smith@sd...>  20001102 19:28:17

> In the meantime I'll start browsing Shewchucks > stuff, but if anyone can enlighten me on any of the > above, I would appreciate it. > Shewchuk's thesis chapter 2: "Not all triangulation edges are flippable,.. ,because the containing quadrilateral of an edge might not be convex" Makes sense. :) DaveS 
From: Jason Zisk <ziskj@n...>  20001102 19:05:52

To be absolutely clear. :) I use the same 4x4 matrix I send D3D, the "world matrix". I would call this the local to world matrix. Transpose that, multiply my direction vector by it and it works great. Terminology sucks. :)  Jason Zisk  nFusion Interactive LLC  Original Message  From: "Zhang Zhong Shan" <ZhangZhongShan@...> To: <gdalgorithmslist@...> Sent: Wednesday, November 01, 2000 9:03 PM Subject: RE: [Algorithms] Correct Way to transform direction vector > are you using the transpose of worldlocal or the transpose of localworld? > > i think its the later that you are using, the localworld is the revsers of > worldlocal, so you are accturely applying the rule without noticing. > > this cant be wrong, I can bet my left hand on this. ^_^ > > > zhongshan > > > Original Message > From: Jason Zisk [mailto:ziskj@...] > Sent: Thursday, November 02, 2000 1:26 AM > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Correct Way to transform direction vector > > > This doesn't work, at least it didn't for me. I had to use the transpose of > the matrix that transforms the vertex, no inverse at all. > > If I use the inverse transpose (or transpose inverse) of the worldlocal > matrix it would do position and scaling correctly but the rotation would be > all wrong. By not inverting the matrix all would work. > > I'm working with full 4x4 transformation matrices, the same ones you'd send > to D3D or OGL to tell it what to render. > >  Jason Zisk >  nFusion Interactive LLC > > >  Original Message  > From: "Zhang Zhong Shan" <ZhangZhongShan@...> > To: <gdalgorithmslist@...> > Sent: Wednesday, November 01, 2000 3:05 AM > Subject: RE: [Algorithms] Correct Way to transform direction vector > > > > hi jason, > > > > The rule is: To transform direction vectors, use the INVERSE TRANSPOSE OF > > THE MATRIX THAT TRANSFORMS VERTEX. > > > > In your case, you should use the transpose of inversed worldlocal matrix, > > which is exactly the transpose of your localworld matrix. > > > > btw, getting normals by first transforming the 2 vertices does not work > when > > there is reflection in transformation. > > > > > > > > > > > > Original Message > > From: Jason Zisk [mailto:ziskj@...] > > Sent: Wednesday, November 01, 2000 3:41 AM > > To: Algorithms List > > Subject: Re: [Algorithms] Correct Way to transform direction vector > > > > > > Well I know for sure that transforming 2 points doesn't work if the matrix > > contains scaling. I'm not entirely sure why, I thought I had it figured > out > > but you are right, the change in direction is what you want. All I know > is > > that when I do this, if the matrix has scaling its pointing in the wrong > > direction. > > > > I found out that to go from world space to object space you don't want to > > multiply the dir. vector by transpose(inverse), you just want to use just > > transpose(matrix). > > > > This makes sense since I believe transforming normals was in reference to > > going from object space to world space. > > > > So the final outcome is, if you want to transform a direction vector from > > one space to another, just multiply it by the transpose of the > > transformation matrix. Now if I could remember enough math to know why. > :) > > > >  Jason Zisk > >  nFusion Interactive LLC > > > > > >  Original Message  > > From: "Peter Warden" <Peter.Warden@...> > > To: <gdalgorithmslist@...> > > Sent: Tuesday, October 31, 2000 9:21 AM > > Subject: RE: [Algorithms] Correct Way to transform direction vector > > > > > > > Jason Zisk wrote: > > > > Hey everyone. I'm having a problem transforming a > > > > direction vector from one coordinate space to another. I > > > > need to transform the direction of the ray from world space > > > > to object space so I can do an intersection on the triangles > > > > in a mesh. > > > > > > > > I've tried two things. The first was taking two points on > > > > the line that the > > > > direction vector forms, transforming those by the inverse > > > > matrix of the > > > > object I'm trying to intersect with then recreating the > > > > vector from those > > > > two transformed points. That has problems if you have > > > > scaling in the matrix > > > > though, the direction of the vector could change. So this > > > > solution is no > > > > good in my situation. > > > > > > Surely in this case you _want_ the direction to change if > > > there's scaling. As a thought experiment in 2D, imagine you had > > > a square centred on the origin with corners at (1,1),(1,1), > > > (1,1) and (1,1). Now apply a localtoworld transform to take > > > this shape into worldspace, apply a scaling of x=x*2. This > > > leaves the corners at (2,1),(2,1),(2,1) and (2,1). Now, put > > > a ray into world space that starts at (0,2), and has a direction > > > of (2,1). This ray will touch the (2,1) corner of the square > > > in worldspace. The inverse of the localtoworld transform for > > > the square is x=x/2, and if we apply this to both the ray's > > > origin and to its direction vector, we end up with a ray at > > > (0,2) with a direction of (1,1) in the square's local space. > > > This ray still kisses the same corner of the square, in local > > > space coordinates (1,1). If the direction _hadn't_ been > > > affected by the scaling, the ray in local space would miss the > > > square, which isn't what you want! > > > > > > I'd say transforming the two points by the inverse matrix was > > > the right way to tackle this, the alteration of the direction by > > > scaling is needed in this case. > > > > > > > I looked back at the archives of this list and I noticed a > > > > discussion of > > > > transforming normals. It seems that using the transpose of > > > > the inverted > > > > transformation matrix is the right way to transform a normal. > > > > By doing this > > > > I actually solved some problems (with scaling) but caused others with > > > > rotation. > > > > > > Surface normals are a different case, but I can't come up with > > > an explanation as to why that I'm happy with! The closest I've > > > come is that the normal is part of a plane definition, and so > > > need the rules of plane transformation applied to it, whereas a > > > ray's direction vector isn't and doesn't. Implicit versus > > > explicit representations? An authorative answer from a maths bod > > > would be nice... > > > > > > I take it you've seen the 'Abnormal Normals' article by Eric > > > Haines at > > > http://www.acm.org/tog/resources/RTNews/html/rtnews1a.html > > > , and the response from David Rogers a few issues later? > > > > > > Peter Warden > > > _______________________________________________ > > > GDAlgorithmslist mailing list > > > GDAlgorithmslist@... > > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > > > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist 
From: Joe Ante <Joe@Titansoft.de>  20001102 18:35:25

Hi, I have implemented a texture system which provides on demand loading of textures. Basically it consists of two classes one is called TextureSynthesizer and is responsible for creating the textures, it is an abstract base class, with a virtual function SynthesizeTexture, which has the parameters width and height and returns the synthesized texture at the desired resolution. The Texture2D class has a ptr to a texture synthesizer and calls the synthesize texture function when it needs bigger textures or the synthesizer was invalidated. (eg. the parameters for a procedural texture were changed) so you construct a texture2D by passing it to the texturesynthesizer, then you can simply call texture2d>LoadTexture (desiredmiplevel); and Texture2D takes care of the rest. (I also take care of sharing textures and texturesynthesizer) This way I have already implemented a FileSynthesizer loading images for files and the EcosystemSynthesizer proposed by klaus. Now this is all fine, but how do i find out which mipLevel will be needed? Or how do I (fast) calculate or approximate the biggest size of any texel given the texture UVs, vertices and OBB around the object? Thanks in advance. bye joe 
From: Dave Smith <Dave.Smith@sd...>  20001102 14:48:16

> (2) if e forms a smaller minimum angle with the > outside edges than the other diagonal does. > I don't see how this is supposed to work at all given John H.'s example. Either I have misinterpreted the statement above or my implementation is goofed (which it might very well be). Looking at any concave quad formed by two triangles, why would you ever flip the edge? In my example, I have two perpindicular line segments, not touching, and depending on how long you make them, you can get (2) to be true or false.(Basically your making the minimum angles smaller for one diagonal than the other) So now, I'm stuck in a dilemma. Abandon this so called "easy" algorithm, or find another. I've read Chew's algorithm(the O(nlogn) one). The first thing that jumps out at me is that he sorts according to a dimension(x or y) and if you can't find a unique line for every coordinate(which you most likely never will), you must rotate the input set. Well that doesn't guarantee you will get a unique line plus finding how much to rotate isn't exactly straight forward. In the meantime I'll start browsing Shewchucks stuff, but if anyone can enlighten me on any of the above, I would appreciate it. Thanks, DaveS 
From: Tom Forsyth <tomf@mu...>  20001102 14:33:51

Using the destination alpha channel should work quite well. Pass 1  render gross alpha to framebuffer. Pass 2  use a DestAlpha:One equivalent blend. For the PS2 alpha blend, I think the equivalent of DestAlpha:One is A = srccolour, B = zero, C = destalpha, D = destcolour. This obviously requires a 32bpp framebuffer of course. Tom Forsyth  purely hypothetical Muckyfoot bloke. This email is the product of your deranged imagination, and does not in any way imply existence of the author. > Original Message > From: Paul Firth [mailto:pfirth@...] > Sent: 02 November 2000 10:10 > To: gdalgorithmslist@... > Subject: [Algorithms] splatting > > > Charles, > > I've been looking at your terrain "splatting" idea recently > (which looks very nice btw), but I've come across some > implementation issues with regard to the PS2: > > The second pass where you render the "splats" using their > second gross alpha map is a multitexture op, how would > you simulate this with multipass rendering  surely the > gross alpha requires different texture coords to the splat > texture because the two are different sizes? > > Cheers, Paul. 
From: Leigh McRae <leigh.mcrae@ro...>  20001102 14:26:43

I started to read the paper then it turned into a skim. I don't like this method much for this generation of games and I also think that its old. Didn't Tribes use something like this? The sample data that is used is close to best case for this algro as its mostly flat to light rolling hills. If a terrain block has any spike or other strong characteristic in it, then the block won't drop a LOD or you will get popping. This can be reduced by geomorphing or making the terrain blocks smaller but smalller terrain blocks puts more work on the CPU. Also the stitching of the blocks must be a pain and could generate thin triangles which tend to be bad for walking on. If your looking for an easy LOD scheme that you could code fast and the terrain isn't that important then maybe this is the algo for you. It mighty also be a good place to start with terrain rendering. Leigh McRae  Original Message  From: Phil Bak <phil@...> To: <gdalgorithmslist@...> Sent: Thursday, November 02, 2000 4:54 AM Subject: [Algorithms] has anyone else seen this terrain paper? > http://www.flipcode.com/tutorials/tut_geomipmaps.shtml > > which outlines an interesting idea called geomipmaps. > > just fishing for people's thoughts and ideas. > > Phil Bak > Rehab is for quitters. > ICQ:11204037 > Tel:01908 393837 > Email:phil@... > Web:www.deepred.co.uk >  > > Privileged/Confidential Information may be contained in this message. If > you are not the addressee indicated in this message (or responsible for > delivery of the message to such person), you may not copy or deliver this > message to anyone. In such case, you should destroy this message and kindly > notify the sender by reply email. Please advise immediately if you or your > employer does not consent to Internet email for messages of this kind. > Opinions, conclusions and other information in this message that do not > relate to the official business of my firm shall be understood as neither > given nor endorsed by it. > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > 
From: Kent Quirk <kent_quirk@co...>  20001102 13:56:58

Ron Levine wrote: > > Andrew Sega wrote: > > > > >I actually meant to say "axisaligned" instead of "arbitrary", chalk that up > >to temporary insanity. Seven is what I had determined heuristically, but > >your explanation makes more sense (i.e. each clipping plane at worst > >generates an edge). > > > >So, given that a large enough triangle is equivalent to an infinite plane as > >far as we're concerned: How many face intersections can an infinite plane > >cause with an AABB? I can't imagine a case in my head where it could touch > >more than 5 sides, but perhaps someone has a counterexample? > > > > A plane intersects all 6 faces of a box if and only if it is the > (unique) plane containing a diagonally opposite pair of edges > > A plane intersects 5 or 6 of the faces of a box if and only if > contains an edge of the box. Um, either I'm misunderstanding something or this is incorrect. I can make one cut through a cube and intersect all six faces without having the cut contain any edge of the cube. Isn't that the situation being described here? Please see: http://www.cognitoy.com/cutcube.jpg Kent   Kent Quirk  CogniToy: Intelligent toys... Game Architect  for intelligent minds. kent_quirk@...  http://www.cognitoy.com/ ______________________________________________________________________ 
From: Paul Firth <pfirth@at...>  20001102 10:11:29

Charles, I've been looking at your terrain "splatting" idea recently (which looks very nice btw), but I've come across some implementation issues with regard to the PS2: The second pass where you render the "splats" using their second gross alpha map is a multitexture op, how would you simulate this with multipass rendering  surely the gross alpha requires different texture coords to the splat texture because the two are different sizes? Cheers, Paul. 
From: Phil Bak <phil@de...>  20001102 09:52:52

http://www.flipcode.com/tutorials/tut_geomipmaps.shtml which outlines an interesting idea called geomipmaps. just fishing for people's thoughts and ideas. Phil Bak Rehab is for quitters. ICQ:11204037 Tel:01908 393837 Email:phil@... Web:www.deepred.co.uk  Privileged/Confidential Information may be contained in this message. If you are not the addressee indicated in this message (or responsible for delivery of the message to such person), you may not copy or deliver this message to anyone. In such case, you should destroy this message and kindly notify the sender by reply email. Please advise immediately if you or your employer does not consent to Internet email for messages of this kind. Opinions, conclusions and other information in this message that do not relate to the official business of my firm shall be understood as neither given nor endorsed by it. 
From: RocknRoll <RocknRoll@ro...>  20001102 08:04:51

Maybe put "data" through a function with "key" as a parameter? > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Peter > Dimov > Sent: Wednesday, November 01, 2000 3:45 AM > To: gdalgorithmslist@... > Subject: [Algorithms] encryption algorithm needed > > > I have a game that periodically reports its state to a scoreboard > server, using a (key, data) format. Key and data are 128 bit integers. > > I want to encrypt the data with the key; the algorithm would ideally be: > > * reasonably easy to implement in C++, Java, and Php; > * not trivial to reverse, assuming the attacker has several valid (key, > data) pairs and access to the source of the decoder. > > Suggestions? > >  > Peter Dimov > Multi Media Ltd. > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > 
From: RocknRoll <RocknRoll@ro...>  20001102 08:04:48

My brain is fried from work, so my only input is to work backward. Start with a simple case then increase the complexity. In 2D you can work with a single equation such as ax + by + c = 0 then insert into x and y the equation which you state is only a function of t; hence one equation with one unknown. When working with trig functions you may need to use identities such as sin^2(t) + cos^2(t) = 1 to put all trig terms into sin or cos functions then solve into a function using inverse trig function that you can code to give you t which you then test to see if it's in your time interval constraint. Some other helpful trig identities: sin(2t) = 2sin(t)cos(t) cos(2t) = cos^2(t)  sin^2(t) = 1  2sin^2(t) = 2cos^2(t)  1 asin(t) + bcos(t) = sqr(a^2 + b^2)sin(t + H) where H is the angle in a triangle with adjacent side a and opposite side b. With trig functions the equations can get nasty real quick. If you want a quick and dirty numeric solution then use a Maclaurin series for sin(t): sin(t) = t  (t^3)/3! + (t^5)/5!  (t^7)/7! + (t^9)/9! ... and sin(t) = 1  (t^2)/2! + (t^4)/4!  (t^6)/6! + (t^8)/8! ... ! means factorial (2!=2,3!=6,4!=24,5!=120,6!=720,7!=5040,8!=40320,9!=362880, etc) You usually just need to carry it out to 5 terms to get sufficient accuracy, or until (t^i)/i! < precision for largest expected value of t RocknRoll > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of > Thomas Luzat > Sent: Monday, October 23, 2000 10:38 AM > To: gdalgorithmslist@... > Subject: [Algorithms] Point/line collision > > > I have some trouble solving the following problem of which I thought a > solution (analytical if possible) wouldn't be too hard... Let's assume a > line (in 2D): > > g(s) = x0 + x1 * s, s = [0..1] > > And a moving point which rotates around another moving point (p0): > > p(t) = p0 + v * t + Mrot(omega * t) * p1 > > Now I want to check the point p for collision with the line g > during a time > interval (t = [0..1]). This gives: > > p(t) = g(s) > p0 + v * t + Mrot(omega * t) * p1 = x0 + x1 * s > > Simplifying this a bit (p0  x0 = a, omega = 1) gives: > > a + v * t + Mrot(t) * p1  x1 * s = 0 > > And finally: > > a_x + v_x * t + p1_x * cos(t)  p1_y * sin(t)  x1_x * s = 0 > ^ a_y + v_y * t + p1_x * sin(t) + p1_y * cos(t)  x1_y * s = 0 > ^ 0 <= s, t <= 1 > > Now, how do I solve this? :( > > > Thomas > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > 
From: Charles Bloom <cbloom@cb...>  20001102 06:55:51

Brian's plane screenshots: http://www.cbloom.com/plane1.jpg http://www.cbloom.com/plane2.jpg http://www.cbloom.com/plane3.jpg And the tools I converted them with : (raw2bmp command line app and other such goodies) http://www.cbloom.com/gfxutils.zip (fyi raw2bmp figures out the dimensions of the raw file by looking in the file name, or trying to match the file size to common sizes). At 11:50 PM 11/1/2000 0500, you wrote: >(oops, sent this from the wrong email address and it bounced, let's try >this email address instead... looks like someone's beaten me to the point, >but whatever...) > >At 12:03 PM 11/1/00 0800, you wrote: >>Should be: "Obviously for ALL definitions of "box"..." >> >>It's never possible to clip all of the planes... > >Sure it is, if I understand what you're talking about... > >Given the axisaligned box with extreme corners (0,0,0) and (1,1,1), all 6 >of its faces are intersected by the plane defined by the points (0,0,1), >(2,0,2) and (0,2,2). I think... > >I'd put up screenshots but all I have is GIMP, not Photoshop, and it >doesn't read raw files. If you have photoshop and care to see screenshots, >grab: > >www.maniacal.org/plane_cube.zip > >They're all 800x600x24bpp RGB raw files, that should get photoshop to load >them. > >I need to go find my tgawriting source one of these days... > >Brian >========== >GLSetup, Inc. > >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > >  Charles Bloom http://www.cbloom.com 
From: Brian Sharp <brian@ma...>  20001102 04:46:48

(oops, sent this from the wrong email address and it bounced, let's try this email address instead... looks like someone's beaten me to the point, but whatever...) At 12:03 PM 11/1/00 0800, you wrote: >Should be: "Obviously for ALL definitions of "box"..." > >It's never possible to clip all of the planes... Sure it is, if I understand what you're talking about... Given the axisaligned box with extreme corners (0,0,0) and (1,1,1), all 6 of its faces are intersected by the plane defined by the points (0,0,1), (2,0,2) and (0,2,2). I think... I'd put up screenshots but all I have is GIMP, not Photoshop, and it doesn't read raw files. If you have photoshop and care to see screenshots, grab: http://www.maniacal.org/plane_cube.zip They're all 800x600x24bpp RGB raw files, that should get photoshop to load them. I need to go find my tgawriting source one of these days... Brian ========== GLSetup, Inc. 
From: <ron@do...>  20001102 03:49:05

Andrew Sega wrote: > >I actually meant to say "axisaligned" instead of "arbitrary", chalk that up >to temporary insanity. Seven is what I had determined heuristically, but >your explanation makes more sense (i.e. each clipping plane at worst >generates an edge). > >So, given that a large enough triangle is equivalent to an infinite plane as >far as we're concerned: How many face intersections can an infinite plane >cause with an AABB? I can't imagine a case in my head where it could touch >more than 5 sides, but perhaps someone has a counterexample? > A plane intersects all 6 faces of a box if and only if it is the (unique) plane containing a diagonally opposite pair of edges A plane intersects 5 or 6 of the faces of a box if and only if contains an edge of the box. 
From: Zhang Zhong Shan <ZhangZhongShan@ub...>  20001102 02:02:09

are you using the transpose of worldlocal or the transpose of localworld? i think its the later that you are using, the localworld is the revsers of worldlocal, so you are accturely applying the rule without noticing. this cant be wrong, I can bet my left hand on this. ^_^ zhongshan Original Message From: Jason Zisk [mailto:ziskj@...] Sent: Thursday, November 02, 2000 1:26 AM To: gdalgorithmslist@... Subject: Re: [Algorithms] Correct Way to transform direction vector This doesn't work, at least it didn't for me. I had to use the transpose of the matrix that transforms the vertex, no inverse at all. If I use the inverse transpose (or transpose inverse) of the worldlocal matrix it would do position and scaling correctly but the rotation would be all wrong. By not inverting the matrix all would work. I'm working with full 4x4 transformation matrices, the same ones you'd send to D3D or OGL to tell it what to render.  Jason Zisk  nFusion Interactive LLC  Original Message  From: "Zhang Zhong Shan" <ZhangZhongShan@...> To: <gdalgorithmslist@...> Sent: Wednesday, November 01, 2000 3:05 AM Subject: RE: [Algorithms] Correct Way to transform direction vector > hi jason, > > The rule is: To transform direction vectors, use the INVERSE TRANSPOSE OF > THE MATRIX THAT TRANSFORMS VERTEX. > > In your case, you should use the transpose of inversed worldlocal matrix, > which is exactly the transpose of your localworld matrix. > > btw, getting normals by first transforming the 2 vertices does not work when > there is reflection in transformation. > > > > > > Original Message > From: Jason Zisk [mailto:ziskj@...] > Sent: Wednesday, November 01, 2000 3:41 AM > To: Algorithms List > Subject: Re: [Algorithms] Correct Way to transform direction vector > > > Well I know for sure that transforming 2 points doesn't work if the matrix > contains scaling. I'm not entirely sure why, I thought I had it figured out > but you are right, the change in direction is what you want. All I know is > that when I do this, if the matrix has scaling its pointing in the wrong > direction. > > I found out that to go from world space to object space you don't want to > multiply the dir. vector by transpose(inverse), you just want to use just > transpose(matrix). > > This makes sense since I believe transforming normals was in reference to > going from object space to world space. > > So the final outcome is, if you want to transform a direction vector from > one space to another, just multiply it by the transpose of the > transformation matrix. Now if I could remember enough math to know why. :) > >  Jason Zisk >  nFusion Interactive LLC > > >  Original Message  > From: "Peter Warden" <Peter.Warden@...> > To: <gdalgorithmslist@...> > Sent: Tuesday, October 31, 2000 9:21 AM > Subject: RE: [Algorithms] Correct Way to transform direction vector > > > > Jason Zisk wrote: > > > Hey everyone. I'm having a problem transforming a > > > direction vector from one coordinate space to another. I > > > need to transform the direction of the ray from world space > > > to object space so I can do an intersection on the triangles > > > in a mesh. > > > > > > I've tried two things. The first was taking two points on > > > the line that the > > > direction vector forms, transforming those by the inverse > > > matrix of the > > > object I'm trying to intersect with then recreating the > > > vector from those > > > two transformed points. That has problems if you have > > > scaling in the matrix > > > though, the direction of the vector could change. So this > > > solution is no > > > good in my situation. > > > > Surely in this case you _want_ the direction to change if > > there's scaling. As a thought experiment in 2D, imagine you had > > a square centred on the origin with corners at (1,1),(1,1), > > (1,1) and (1,1). Now apply a localtoworld transform to take > > this shape into worldspace, apply a scaling of x=x*2. This > > leaves the corners at (2,1),(2,1),(2,1) and (2,1). Now, put > > a ray into world space that starts at (0,2), and has a direction > > of (2,1). This ray will touch the (2,1) corner of the square > > in worldspace. The inverse of the localtoworld transform for > > the square is x=x/2, and if we apply this to both the ray's > > origin and to its direction vector, we end up with a ray at > > (0,2) with a direction of (1,1) in the square's local space. > > This ray still kisses the same corner of the square, in local > > space coordinates (1,1). If the direction _hadn't_ been > > affected by the scaling, the ray in local space would miss the > > square, which isn't what you want! > > > > I'd say transforming the two points by the inverse matrix was > > the right way to tackle this, the alteration of the direction by > > scaling is needed in this case. > > > > > I looked back at the archives of this list and I noticed a > > > discussion of > > > transforming normals. It seems that using the transpose of > > > the inverted > > > transformation matrix is the right way to transform a normal. > > > By doing this > > > I actually solved some problems (with scaling) but caused others with > > > rotation. > > > > Surface normals are a different case, but I can't come up with > > an explanation as to why that I'm happy with! The closest I've > > come is that the normal is part of a plane definition, and so > > need the rules of plane transformation applied to it, whereas a > > ray's direction vector isn't and doesn't. Implicit versus > > explicit representations? An authorative answer from a maths bod > > would be nice... > > > > I take it you've seen the 'Abnormal Normals' article by Eric > > Haines at > > http://www.acm.org/tog/resources/RTNews/html/rtnews1a.html > > , and the response from David Rogers a few issues later? > > > > Peter Warden > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/mailman/listinfo/gdalgorithmslist 
From: Ron Levine <ron@do...>  20001102 00:19:22

Neil Tringhan wrote > As I recall, the general result is that for clipping a convex polygon of n > vertices against m planes, the resulting clipped polygon can have up to > (n+m) vertices, though I can't find my proof for this:) The way to prove it is to bound the number of edges. Recall that the intersection of two convex sets is convex, so the result of clipping a convex polygon by a plane is convex. Consider the result of clipping a convex polygon by a single plane. The edges of the clipped polygon are each either an edge of the original polygon, a subsegment of an edge of the original polygon, or a segment contained in the line of intersection of the plane of the polygon and the clipping plane. Moreover, by convexity, each original edge can contribute at most one subsegment and the line of intersection can contribute at most one edge. So the result of clipping a convex polygon by a plane has at most one more edge than the original polygon. Also, the result of clipping a convex polygon by a plane is a convex polygon. So by induction, you can increase the number of edges by at most one for each clipping plane. A polygon has as many vertices as edges. QED >You can wave your > hands about and say something along the lines of "the maximum number of > output vertices is the number of input vertices plus the number of times an > input edge could have cut a plane", though. That is indeed handwaving, for the desired conclusion does not follow. It could happen that some input edges cut every clipping plane and some clipping planes are cut by two input edges, so this assertion still allows a greater limit on the number of vertices than you are seeking. To cut it down you have to invoke convexity and induction. 