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}

_{Dec}

S  M  T  W  T  F  S 





1
(31) 
2
(28) 
3
(10) 
4
(15) 
5
(22) 
6
(21) 
7
(30) 
8
(30) 
9
(44) 
10
(6) 
11
(5) 
12
(50) 
13
(33) 
14
(61) 
15
(68) 
16
(43) 
17
(24) 
18
(14) 
19
(85) 
20
(33) 
21
(30) 
22
(38) 
23
(1) 
24
(5) 
25
(6) 
26
(6) 
27
(29) 
28
(34) 
29
(81) 
30
(61) 
31
(10) 
From: Jason Zisk <ziskj@op...>  20010308 22:40:37

> Totally agreed, but I'm curious there: what kind of game does need about 2 > million meshes ?! Wow. More like 1 million. I wish it was something cool and groundbreaking, but it was just for our last game, which was a deer hunting simulation. We didn't absolutely need to place every single rock and bush but we needed to manually place enough things that in the end it was just easier and faster to store it all. Our next game won't need so many objects or large areas but just in case I'm still thinking about ram usage, you never know when you'll need to model 16 square miles of terrain and be accurate to the tree. :)  Jason Zisk  nFusion Interactive LLC 
From: Armen Levonian <armen@su...>  20010308 22:22:02

If you are modeling an astronomical database, then quaternions would be the way to go, since the rotation vector can be trivially extracted from the quaternion. However, at some point you'd want the matrix if only to do vector transforms to the screen. The two can be complementary. If used in a complementary manner, the quaternion can help keeping your rotation matrix orthonormal, especially if the object is undergoing cumulative rotation. Original Message From: gdalgorithmslistrequest@... [mailto:gdalgorithmslistrequest@...] Sent: Thursday, March 08, 2001 2:06 PM To: gdalgorithmslist@... Subject: GDAlgorithmslist digest, Vol 1 #693  9 msgs Send GDAlgorithmslist mailing list submissions to gdalgorithmslist@... To subscribe or unsubscribe via the World Wide Web, visit http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist or, via email, send a message with subject or body 'help' to gdalgorithmslistrequest@... You can reach the person managing the list at gdalgorithmslistadmin@... When replying, please edit your Subject line so it is more specific than "Re: Contents of GDAlgorithmslist digest..." Today's Topics: 1. Re: quaternions in a 3d engine (Charles Bloom) 2. RE: Interpolation Over a Triangle (Rui Ferreira) 3. Re: ROAM textures and new frontiers in LOD (was ROAM textures) (Jake Cannell) 4. RE: Interpolation Over a Triangle (Chris Hecker) 5. RE: OT: Sore back (was: Off topic: Tired eyes.) (Skelton, Jeff) 6. Re: quaternions in a 3d engine (Jason Zisk) 7. RE: VIPM, VDPM, ROAM questions (Tom Hubina) 8. Re: quaternions in a 3d engine (Ron Levine) 9. Re: quaternions in a 3d engine (Pierre Terdiman) ____ Message: 1 Date: Thu, 08 Mar 2001 12:12:55 0800 To: gdalgorithmslist@... From: Charles Bloom <cbloom@...> Subject: Re: [Algorithms] quaternions in a 3d engine ReplyTo: gdalgorithmslist@... At 11:24 AM 3/8/2001 0800, you wrote: >Umm. Neither matrices nor quaternions are "fundamental rotation types". >Rather, they are two different algebraic formalisms for working with a >common geometric abstraction: 3D rotations (which in my nomenclature means >the same as "orientations"). I meant "fundamental" as a reference to its role in the engine architecture. In every sensible 3d engine you must store some representation of the rotation group in your objects or scene graph nodes. Certainly, you can think of quats and mats as "tools", but if you find that you are using quats all the time, then storing matrices as your "fundamental" type is the wrong choice. You want to choose a fundamental type which is the most common form that you talk to rotations in. >Nor should you think of one "versus" the other. They are two tools, each >with its advantages for different jobs. See above. >Your two lists leave out the most important property, even the most >fundamental property, of matrices, which quaternions definitely lack; >namely, that they directly display the basis vectors of the rotated frame in >their components with respect to the unrotated frame (and vice versa). Ok, this is an excellent point which I totally forgot and probably seals the deal. If it weren't for this then I think quats would win because of their smaller size and better interpolation properties.  Charles Bloom cbloom@... http://www.cbloom.com ____ Message: 2 From: "Rui Ferreira" <rui.ferreira@...> To: <gdalgorithmslist@...> Subject: RE: [Algorithms] Interpolation Over a Triangle Date: Thu, 8 Mar 2001 20:27:24 0000 ReplyTo: gdalgorithmslist@... Heh. Reply 1: W' = W0 + (dW/dX)(X'  X0) + (dW/dY)(Y'  Y0) "(...)...This stuff is pretty obvious with rasterizers and edge delta walk..." Reply 2: p = s p_0 + t p_1 + q p_2 (s + t + q = 1 inside the triangle) "logical that the value on the baricenter is like the average of the of all the 3 vertices..." I probably should start reading my own posts looking for answers ! :] Thanks for the heads up. Rui PS: Yeah, I have "Real Time Rendering", but I'm on page 158! Go figure... PS2: "I'll let you do it"... Hecker, you old softy :] ____ Message: 3 From: "Jake Cannell" <jcannell@...> To: <gdalgorithmslist@...> Subject: Re: [Algorithms] ROAM textures and new frontiers in LOD (was ROAM textures) Date: Thu, 8 Mar 2001 12:36:25 0800 Organization: ... ReplyTo: gdalgorithmslist@... > With that "digest" subject, I didn't realize you were > replying to me ;) Whoops, I knew I forgot something. :) [snip] > Oh, are you the guy who posted the cool screenshots a while back > on the realtime fractal planet? Great stuff! Thanks.:) > > As for precomputation, that is when you have real data. When > you are inventing it as you subdivide, then you end up with looser > bounds (based on min/max possible random displacements), > or can just go with statisticsbased priorities. But the > overall framework like dual queues, flagbased incremental > culling, priority deferral etc should remain unchanged. No, in the worst case you can just generate your displacement data then get the bounds from it directly. If you use a bintree, it would just be essential to be able to construct it quickly. > > > The general incremental LOD idea also came in handy here for > > caching procedural data. > > Makes sense: it is costly to generate the terrain/textures, > and the incremental split/merge ideas let you budget that > effort per frame. What is cool is that this is now fast enough > to be realtime. That just blows my mind. About twelve years > ago I did a "gods eye" topdown version of what you > are talking about (pretty shaded fractal landscape, maybe > 768x768 pixels at a time, unlimited pan and zoom), but > it took a few seconds per frame. Getting frames per > second...WOW! Its pretty cool, as long as generating the surfaces doesn't take so long that fast camera motion results in unacceptable delays. I've found that you can expect between a 1030 times speedup, ie somewhere between 310% of your surfaces can change each frame with typical camera flight. If you consider that surfaces that are moving quickly in screenspace 1.) need less detail anyway and 2.) aren't going to be visible for very long, your priority metric can take this into account and get much better visual results. > > > I'm curious now about 'binary texture hierachies'. > > How are your textures aligned in the bintree? How many triangles do they > > cover? > > Well, I'm working on a paper with all the details, but here's a > preview. > > Recall that a triangle bintree hierarchy can also be viewed as > a bunch of diamonds (do NOT confuse these with quadtree cells). > Diamonds are two equalsized triangles meeting on a base edge. > Identify a diamond by its split point (the vertex in the grid > at the center of the mutual base edge). There are easy ways to > get to the two parents and four kids in the diamond view, and > associating a split bit with the diamond and queueing diamonds > is more compact that working on bintree triangles (which was > the old way in the ROAM paper). So diamonds for a regular grid > at every level of the hierarchy, but rotate grid alignment > 45 degrees every level. Now assign a 128x128 texture (for example) > to each diamond, with bilinear interpolation, so that the > texels on the edge have their centers (basis "peaks") right on > the diamond edge. So really only the 126x126 texels in the > center are unique to the diamond. The edges are shared/duplicated > by the neighboring diamonds. Ok, I used the same idea with quadtrees, allowing a variable sized shared border. I found that I needed a few pixels of border for calculating surface normals, interpolating various shader values (heightfield, noises, etc), and bilinear filtering. [snip ascii art] > Note that the number of texels per unit area only doubles > from one level to the next. In practice I've found you > don't need any mipmaps, blending etc if you have your refinement > such that each texel projects to about a pixel or two on the screen > (tweek this until you get a good balance between aliasing and > overfuzzing). Of course you really need to lowpass filter to > get coarser levels, so that the edge texels don't exactly agree > any more, but again in practice with welltuned projected texel > sizes, I didn't see a need for blending or special "transition" > textures at the boundary where resolution changes. If you did > decide to blend or transition, this scheme is also a big win because > the triangle bintree adaptive grids have only two cases across > any edge: both triangles are at the same resolution, or they differ > by one level (in this case, the edge is a base edge of the > finer trinagle). So you can create two versions of each texture > (transition and nontransition) without any blending during the > draw, or have only one set of textures and a simple blend option. > This ends up MUCH simpler than what you end up with for quadtrees. > If you can always maintain a 1:1 texel/pixel ratio or higher, then I think the mipmapping/filtering on the card would naturally hide the discrepancies along textures borders of different resolutions. In my case where the textures are generated procedurally, I have to deal gracefully with the common situation in which I can't perfectly keep up with the camera and the texel/pixel ratio drops well below one ... at which point both pixel popping and borders become noticeable artifacts. So I blend between the current texture for a node and the node's parent texture to hide the borders and blend in new textures gracefully over a number of frames. It looks considerably better in my case and it was fairly easy to do with quadtrees. > So the simplest bintree texture scheme is to just have a fixed > relationship with the bintree triangles, as the ASCI art implied. > But in reality this causes a problem near horizons. So it turns > out you want to decouple the triangles from any specific texture, > and let them refine more as needed. The priorityqueue scheme > I use keeps track of the min and max estimated projected texel sizes, > and splits whenever max/min>A and merges when max/min<A for its > parent (this is a really vague description I know...the paper is > in the works). > Ahh ok I was wondering about this .... having two triangles of the diamond associated with each texture is also clearly ineffecient in terms of GPU useage. The ideal triangle/texture ratio is going to be dependent upon the system, but I'm certain is always going to be much higher than 1. So decoupling triangles and textures solves that problem, and also solves the problem you mention above. So you have essentially two seperate interlinked trees then? One for textures and one for triangles? I started with a single quadtree for both and quickly ran into the problem you mention above, which in my case was even worse .. .. the ideal metric for textures is very different than the ideal for geometry, and also it can take a very long time to generate four textures for a quadtree split, which unecessarily prevents quick geometry optimization. [..snip..] > > The triangle bintree stuff *is* regular grids! But with a lot > fewer cases, and single displacements (at the new "centroid" > i.e. "split points"). Here is what happens in ASCII art: > > ***** >      >  o  o  o  o  >      > ***** >      >  o  o  o  o  >      > ***** >      >  o  o  o  o  >      > ***** This I don't quite understand: "the triangle bintree stuff is regular grids!" .. . I can see how the bintree is derived from a regular grid . .. > > The "*" and "o" are the old and new vertices during a refinement > step. You can do fractal displacements from the centroids > of the "*" faces, for example. If you want a smoother > subdivision scheme, there is a really slick one: > > Step 1) compute "o" vertices as the centroid (average) of the "*" faces > Step 2) move the "*" vertices halfway towards the centroid of > its four nearest "o" vertices that you just computed > > If you want to do "good" fractals, I would also need to tell you > a couple of other steps relating to some wavelets we have in this > subdivision context. But I want to get a publication out first... Well I'm not totally sure what you mean by "good" fractals :) I would consider "good" fractals to be something along the lines of what Ken Musgrave has done .. .. http://www.fractalworlds.com. I've based most of my stuff on his, with the major exception that my speed constraint means that I must cache noise evaluations and thus only add in ONE new octave when I generate each new LOD. This makes perfect sense from the wavelet perspective, at each new LOD evaluation, you only calculate and add in the new frequency for this LOD, you don't actually recalculate the entire fractal/texture from scratch. The difference between log(n) noise evaluations and 1 noise evaluation can be up to 20x or more for a planet texture and makes all the difference in speed . ... Vanilla fbm and vanilla multifractals are trivial to convert to this wavelet evaulation, but Ken's favorite, the "ridged multifractal", has a basis function considerably more complex than the bicubic .. that is C1 discontinous where the noise function has been folded (ie the ridges). Ken Perlin used the same noise evaulation technique for his java planet applet which just uses vanilla fbm. . .... Also, I don't think its worthwhile to evaluate your fractals directly on vertices . .. you need the heightfield anyway for generating the texture (as many shader/texture parameters depend on it and you want per pixel shading) . .. so I evaluate everything as images and then just sample vertices from the displacement image. > > > I believe (hope) that on the GF3 a vertex shader could be used for this, > > reducing your per vertex memory footprint by a factor of 8. In that case, > > quadtrees+regular grids could perhaps beat other schemes in mesh > > approximation quality by shear vertex count. > > HmmmI am NOT a fan of vertex shading in the context of multires > geometry. I think you are far better off using textures for > all your lighting. Think as follows: look up you normal/base color > from textures, perform transforms/ops in the register combiners, > use results to look up from a "diffuse" and "specualar"filtered > environment maps, and voila!, infinite numbers > of lights for full phong shading! Apparently GF3 is the first > hardware that can manage this, and it is not because of > the vertex programming. I don't have a GF3 to try this out > on yet, but you can get my softwareonly version at > http://www.cognigraph.com/LibGen > See the Surftools/Mesh code if you are interested (IRIX/Linux only). > Screenshots at: > http://graphics.cs.ucdavis.edu/~duchaine/mesh.html > > I AM a fan of pervertex operations for geometry effects. I agree here on all these points, which is why I mentioned using a vertex shader that just reads in a single displacement scalar and generates the vertex from that ... . if all your shading is done with images at the pixel level, then the vertex shader could reduce to something very simple (texture coordinates are implicit, vertex surface normal is unecessary) and very fast (hopefully even doing geometry blending on the card). High triangle counts are still important for having very complex (ie rough) terrains. > > > > > Of course, neither quadtrees nor ROAM nor VIPM are going to help much with > > rendering a realistic forest on top of your terrain. I'm surprised there's > > not more interest and research in more general volumetric LOD schemes. > > Everyone seems to forget the very limiting assumptions that surfaceLOD > > schemes make. > > No kidding! Wouldn't it be great to unify surface LOD and imagebased > rendering/light fields into a single logical representation? ROAMing > lightfields anyone? ;) Yes! I've been thinking about this for a while. You would need some sort of metaLOD, octrees perhaps, and then numerous different ways of modelling/rendering the contents of a node with different fined grained LOD's representations. One method could be volumetric modelling and IBR, then at a finer level you could have isosurface extraction and some novel lumigraph/surface LOD scheme, which then degenerates to true surface LOD once that becomes most effecient. There are numerous obstacles here: using volumes are probably still too expensive in both memory and generation time, IBR is memory intensive as well .. transitions between different reps are a pain ... but this is the way to go I think. The way to apply LOD to a plenoptic surface or volume isn't quite intuitive to me .. .. other than something simple like storing multiple rendered images for each octree node and using blending (perhaps with warping) to render with a few of them each frame. > > BTW, we do have a tetrahedral version of the triangle bintrees. > Not quite as simple and clean: there are three flavors of tets > that come in phases. New vertices alternate being associated > with the cells, faces and edges of an octree grid. The "diamond" > based view of the triangle bintree carries over essentially unchanged, > and selective refinement is as fast as with the 2D grid (which > surprised me when I first saw it). The big trick is what do > you put in the tets? Right now we are struggling with isosurfaces > from gigantic 3D finiteelement simulations, examples go up to > 460 million trangles per fineres surface, and they can be nasty > surfaces! See > http://muldoon.cipic.ucdavis.edu/~hvm00/abstracts/duchaineau.pdf > for a tiny piece of one. The tetbased scheme seems to be the > best way to quickly change isolevel. The surfacebased schemes > break down because there isn't a single surface, but in principle > an infinite family of them. Kind of like an animating freeform > surface... Hmm .. this looks quite interesting. .. thanks for the paper:) ____ Message: 4 Date: Thu, 08 Mar 2001 12:46:13 0800 To: gdalgorithmslist@..., gdalgorithmslist@... From: Chris Hecker <checker@...> Subject: RE: [Algorithms] Interpolation Over a Triangle ReplyTo: gdalgorithmslist@... >With my pedant's hat on, I point out that s+t+q = 1 anywhere on the plane of >the triangle, not just inside it. :) The nit has been picked. For more fun with barycentric coordinates, write out the math as a matrix equation and solve it that way, and then do it for a triangle in 2D and a tetrahedron in 3D. There are some interesting differences between the (n1)D manifold embedded in nD space (like a triangle in 3D) and the full simplex (triangle in 2D, tetrahedron in 3D). Linear algebra rulz0rs. Chris ____ Message: 5 From: "Skelton, Jeff" <jskelton@...> To: "'gdalgorithmslist@...'" <gdalgorithmslist@...> Subject: RE: [Algorithms] OT: Sore back (was: Off topic: Tired eyes.) Date: Thu, 8 Mar 2001 12:51:24 0800 ReplyTo: gdalgorithmslist@... Actually Intacs surgery doesn't have anywhere near those odds since it is minimally invasive surgery, there is literally 5% of the cutting that is involved in LASIK, and none of it is within the field of sight. If I recall correctly the chances of cataract formation with Intacs surgery was essentially nil. Of course all surgery entails SOME risk though. This is why I chose Intacs. LASIK scares the crap out of me as well. PRK scares me even more. Jeff Original Message From: Scott LeGrand [mailto:varelse@...] Sent: Wednesday, March 07, 2001 12:04 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] OT: Sore back (was: Off topic: Tired eyes.) > The main advantage is that it is completely reversible...they just make > another slit (mine was 0.8mm outside of the field of view)) and take them > out. Bam I'm back to whatever my vision was before. The downside is that any eye surgery has a chance of inducing cataract formation. Once that happens, you have a 1 in 1000 chance of losing all vision in the eye, a 1 in 100 chance of a significant retinal detachment, and a 100% chance of becoming presbyopic (assuming you get the cataract treated). Lasik, OTOH, scares the bejeezus out of me. There are plenty of horror story web sites out there that explain why, in gory detail. Scott _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist ____ Message: 6 From: "Jason Zisk" <ziskj@...> To: <gdalgorithmslist@...> Subject: Re: [Algorithms] quaternions in a 3d engine Date: Thu, 8 Mar 2001 16:14:16 0500 ReplyTo: gdalgorithmslist@... > Moreover, if you are using them as your fundamental parameters of > orientation, then you are opening yourself up to real grief because of the > inescapable mathematical singularities of such a parametrization. You will > meet this grief whenever you find yourself asking for the Euler angles to > produce a given rotation. This is exactly why I am willing to use up another float to use something more robust. > Bah. The storage requirements for your rotation parameters, be they > expressed in matrices or quaternions or other, are typically orders of > magnitude smaller than the storage required for the vertex data of the > rotated objects. Therefore, multiplication of the rotation storage You are completely wrong for once. We instance our mesh data and store rotation/position/scale for each instance. With a million or more objects this data has to be as small as possible, the mesh data is only loaded once so its inconsequential. Its the difference between 28 megs ram in object data or 48. Its much easier to store our orientation as a quat and save 20 bytes per object than to set up some sort of dynamic loading scheme, well worth the tradeoff in conversion time since only a small number of these objects needs to be rendered each frame (and thus converted from quat to matrix). I think you yourself said it, these are tools and they have thier uses in certain places. I choose quats because they are smaller and thats whats important.  Jason Zisk  nFusion Interactive LLC ____ Message: 7 Date: Thu, 08 Mar 2001 14:01:44 0800 To: gdalgorithmslist@... From: Tom Hubina <tomh@...> Subject: RE: [Algorithms] VIPM, VDPM, ROAM questions ReplyTo: gdalgorithmslist@... At 04:20 AM 3/8/2001, you wrote: >Swapping in chunks shouldn't be a problem  this comes under the >completelydynamic "lock buffer and completely overwrite contents" category, >which is fine (coz the driver multibuffers behidn your back  at least it >does in D3D). In OpenGL you make use of the fence and flush operations (NVIDIA only extensions AFAIK) to break a large chunk of AGP memory into multiple smaller chunks make sure that a chunk of the AGP memory is finished being processed before you write over it. In other words, all double (triple, whatever) buffering is under the application's control and there's no copying of the memory by the driver except to the video card through DMA. I'm not certain if the doublebuffering for D3D you describe implies additional copies on the CPU or not. Tom ____ Message: 8 From: "Ron Levine" <ron@...> To: <gdalgorithmslist@...> Subject: Re: [Algorithms] quaternions in a 3d engine Date: Thu, 8 Mar 2001 14:04:16 0800 ReplyTo: gdalgorithmslist@... Jason Zisk wrote > ... We instance our mesh data and store > rotation/position/scale for each instance. With a million or more objects > this data has to be as small as possible, the mesh data is only loaded once > so its inconsequential. Its the difference between 28 megs ram in object > data or 48. > Sounds like you are talking about playback of canned (precomputed) animations, rather than dynamics. True, in that case rotation parameter storage becomes more important. But that's the boring case. In dynamics, when you have to compute the unpredictable motion for each frame, my point has validitiy. That's the more interesting case to me. ____ Message: 9 From: "Pierre Terdiman" <p.terdiman@...> To: <gdalgorithmslist@...> Subject: Re: [Algorithms] quaternions in a 3d engine Date: Thu, 8 Mar 2001 23:00:56 +0100 ReplyTo: gdalgorithmslist@... > You are completely wrong for once. We instance our mesh data and store > rotation/position/scale for each instance. With a million or more objects > this data has to be as small as possible, the mesh data is only loaded once > so its inconsequential. Its the difference between 28 megs ram in object > data or 48. Totally agreed, but I'm curious there: what kind of game does need about 2 million meshes ?! Wow. > tradeoff in conversion time since only a small number of these objects needs > to be rendered each frame (and thus converted from quat to matrix). On top of that, the conversiontime is probably cheaper than your average cache miss. Pierre ____ _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist End of GDAlgorithmslist Digest 
From: Jason Dorie <jason.dorie@bl...>  20010308 22:16:17

If you're so concerned about space, storing said quats as normalized 16 bit values can save a whole lot of RAM. 0.0  1.0 == 0x0000  0xffff. A lot of todays hardware (PSXII, PIII, etc..) can automagically convert these for you using SIMD in parallel  one instruction to go from 4 shorts to 4 floats. You can also store a quat as 8 bits per value (4 bytes), 10 bits (5 bytes), or 12 bits (6 bytes). You can even leave off the last component, assuming all your quats are normalized, though renormalizing a quat at runtime can be a significant speed hit. Jason Dorie BlackBoxGames Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...]On Behalf Of Jason Zisk Sent: Thursday, March 08, 2001 1:14 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] quaternions in a 3d engine > Moreover, if you are using them as your fundamental parameters of > orientation, then you are opening yourself up to real grief because of the > inescapable mathematical singularities of such a parametrization. You will > meet this grief whenever you find yourself asking for the Euler angles to > produce a given rotation. This is exactly why I am willing to use up another float to use something more robust. > Bah. The storage requirements for your rotation parameters, be they > expressed in matrices or quaternions or other, are typically orders of > magnitude smaller than the storage required for the vertex data of the > rotated objects. Therefore, multiplication of the rotation storage You are completely wrong for once. We instance our mesh data and store rotation/position/scale for each instance. With a million or more objects this data has to be as small as possible, the mesh data is only loaded once so its inconsequential. Its the difference between 28 megs ram in object data or 48. Its much easier to store our orientation as a quat and save 20 bytes per object than to set up some sort of dynamic loading scheme, well worth the tradeoff in conversion time since only a small number of these objects needs to be rendered each frame (and thus converted from quat to matrix). I think you yourself said it, these are tools and they have thier uses in certain places. I choose quats because they are smaller and thats whats important.  Jason Zisk  nFusion Interactive LLC _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist 
From: Pierre Terdiman <p.terdiman@wa...>  20010308 22:04:13

> You are completely wrong for once. We instance our mesh data and store > rotation/position/scale for each instance. With a million or more objects > this data has to be as small as possible, the mesh data is only loaded once > so its inconsequential. Its the difference between 28 megs ram in object > data or 48. Totally agreed, but I'm curious there: what kind of game does need about 2 million meshes ?! Wow. > tradeoff in conversion time since only a small number of these objects needs > to be rendered each frame (and thus converted from quat to matrix). On top of that, the conversiontime is probably cheaper than your average cache miss. Pierre 
From: Ron Levine <ron@do...>  20010308 22:04:05

Jason Zisk wrote > ... We instance our mesh data and store > rotation/position/scale for each instance. With a million or more objects > this data has to be as small as possible, the mesh data is only loaded once > so its inconsequential. Its the difference between 28 megs ram in object > data or 48. > Sounds like you are talking about playback of canned (precomputed) animations, rather than dynamics. True, in that case rotation parameter storage becomes more important. But that's the boring case. In dynamics, when you have to compute the unpredictable motion for each frame, my point has validitiy. That's the more interesting case to me. 
From: Tom Hubina <tomh@3d...>  20010308 22:01:06

At 04:20 AM 3/8/2001, you wrote: >Swapping in chunks shouldn't be a problem  this comes under the >completelydynamic "lock buffer and completely overwrite contents" category, >which is fine (coz the driver multibuffers behidn your back  at least it >does in D3D). In OpenGL you make use of the fence and flush operations (NVIDIA only extensions AFAIK) to break a large chunk of AGP memory into multiple smaller chunks make sure that a chunk of the AGP memory is finished being processed before you write over it. In other words, all double (triple, whatever) buffering is under the application's control and there's no copying of the memory by the driver except to the video card through DMA. I'm not certain if the doublebuffering for D3D you describe implies additional copies on the CPU or not. Tom 
From: Jason Zisk <ziskj@op...>  20010308 21:17:29

> Moreover, if you are using them as your fundamental parameters of > orientation, then you are opening yourself up to real grief because of the > inescapable mathematical singularities of such a parametrization. You will > meet this grief whenever you find yourself asking for the Euler angles to > produce a given rotation. This is exactly why I am willing to use up another float to use something more robust. > Bah. The storage requirements for your rotation parameters, be they > expressed in matrices or quaternions or other, are typically orders of > magnitude smaller than the storage required for the vertex data of the > rotated objects. Therefore, multiplication of the rotation storage You are completely wrong for once. We instance our mesh data and store rotation/position/scale for each instance. With a million or more objects this data has to be as small as possible, the mesh data is only loaded once so its inconsequential. Its the difference between 28 megs ram in object data or 48. Its much easier to store our orientation as a quat and save 20 bytes per object than to set up some sort of dynamic loading scheme, well worth the tradeoff in conversion time since only a small number of these objects needs to be rendered each frame (and thus converted from quat to matrix). I think you yourself said it, these are tools and they have thier uses in certain places. I choose quats because they are smaller and thats whats important.  Jason Zisk  nFusion Interactive LLC 
From: Skelton, Jeff <jskelton@ea...>  20010308 20:48:06

Actually Intacs surgery doesn't have anywhere near those odds since it is minimally invasive surgery, there is literally 5% of the cutting that is involved in LASIK, and none of it is within the field of sight. If I recall correctly the chances of cataract formation with Intacs surgery was essentially nil. Of course all surgery entails SOME risk though. This is why I chose Intacs. LASIK scares the crap out of me as well. PRK scares me even more. Jeff Original Message From: Scott LeGrand [mailto:varelse@...] Sent: Wednesday, March 07, 2001 12:04 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] OT: Sore back (was: Off topic: Tired eyes.) > The main advantage is that it is completely reversible...they just make > another slit (mine was 0.8mm outside of the field of view)) and take them > out. Bam I'm back to whatever my vision was before. The downside is that any eye surgery has a chance of inducing cataract formation. Once that happens, you have a 1 in 1000 chance of losing all vision in the eye, a 1 in 100 chance of a significant retinal detachment, and a 100% chance of becoming presbyopic (assuming you get the cataract treated). Lasik, OTOH, scares the bejeezus out of me. There are plenty of horror story web sites out there that explain why, in gory detail. Scott _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist 
From: Chris Hecker <checker@d6...>  20010308 20:43:47

>With my pedant's hat on, I point out that s+t+q = 1 anywhere on the plane of >the triangle, not just inside it. :) The nit has been picked. For more fun with barycentric coordinates, write out the math as a matrix equation and solve it that way, and then do it for a triangle in 2D and a tetrahedron in 3D. There are some interesting differences between the (n1)D manifold embedded in nD space (like a triangle in 3D) and the full simplex (triangle in 2D, tetrahedron in 3D). Linear algebra rulz0rs. Chris 
From: Jake Cannell <jcannell@cs...>  20010308 20:33:37

> With that "digest" subject, I didn't realize you were > replying to me ;) Whoops, I knew I forgot something. :) [snip] > Oh, are you the guy who posted the cool screenshots a while back > on the realtime fractal planet? Great stuff! Thanks.:) > > As for precomputation, that is when you have real data. When > you are inventing it as you subdivide, then you end up with looser > bounds (based on min/max possible random displacements), > or can just go with statisticsbased priorities. But the > overall framework like dual queues, flagbased incremental > culling, priority deferral etc should remain unchanged. No, in the worst case you can just generate your displacement data then get the bounds from it directly. If you use a bintree, it would just be essential to be able to construct it quickly. > > > The general incremental LOD idea also came in handy here for > > caching procedural data. > > Makes sense: it is costly to generate the terrain/textures, > and the incremental split/merge ideas let you budget that > effort per frame. What is cool is that this is now fast enough > to be realtime. That just blows my mind. About twelve years > ago I did a "gods eye" topdown version of what you > are talking about (pretty shaded fractal landscape, maybe > 768x768 pixels at a time, unlimited pan and zoom), but > it took a few seconds per frame. Getting frames per > second...WOW! Its pretty cool, as long as generating the surfaces doesn't take so long that fast camera motion results in unacceptable delays. I've found that you can expect between a 1030 times speedup, ie somewhere between 310% of your surfaces can change each frame with typical camera flight. If you consider that surfaces that are moving quickly in screenspace 1.) need less detail anyway and 2.) aren't going to be visible for very long, your priority metric can take this into account and get much better visual results. > > > I'm curious now about 'binary texture hierachies'. > > How are your textures aligned in the bintree? How many triangles do they > > cover? > > Well, I'm working on a paper with all the details, but here's a > preview. > > Recall that a triangle bintree hierarchy can also be viewed as > a bunch of diamonds (do NOT confuse these with quadtree cells). > Diamonds are two equalsized triangles meeting on a base edge. > Identify a diamond by its split point (the vertex in the grid > at the center of the mutual base edge). There are easy ways to > get to the two parents and four kids in the diamond view, and > associating a split bit with the diamond and queueing diamonds > is more compact that working on bintree triangles (which was > the old way in the ROAM paper). So diamonds for a regular grid > at every level of the hierarchy, but rotate grid alignment > 45 degrees every level. Now assign a 128x128 texture (for example) > to each diamond, with bilinear interpolation, so that the > texels on the edge have their centers (basis "peaks") right on > the diamond edge. So really only the 126x126 texels in the > center are unique to the diamond. The edges are shared/duplicated > by the neighboring diamonds. Ok, I used the same idea with quadtrees, allowing a variable sized shared border. I found that I needed a few pixels of border for calculating surface normals, interpolating various shader values (heightfield, noises, etc), and bilinear filtering. [snip ascii art] > Note that the number of texels per unit area only doubles > from one level to the next. In practice I've found you > don't need any mipmaps, blending etc if you have your refinement > such that each texel projects to about a pixel or two on the screen > (tweek this until you get a good balance between aliasing and > overfuzzing). Of course you really need to lowpass filter to > get coarser levels, so that the edge texels don't exactly agree > any more, but again in practice with welltuned projected texel > sizes, I didn't see a need for blending or special "transition" > textures at the boundary where resolution changes. If you did > decide to blend or transition, this scheme is also a big win because > the triangle bintree adaptive grids have only two cases across > any edge: both triangles are at the same resolution, or they differ > by one level (in this case, the edge is a base edge of the > finer trinagle). So you can create two versions of each texture > (transition and nontransition) without any blending during the > draw, or have only one set of textures and a simple blend option. > This ends up MUCH simpler than what you end up with for quadtrees. > If you can always maintain a 1:1 texel/pixel ratio or higher, then I think the mipmapping/filtering on the card would naturally hide the discrepancies along textures borders of different resolutions. In my case where the textures are generated procedurally, I have to deal gracefully with the common situation in which I can't perfectly keep up with the camera and the texel/pixel ratio drops well below one ... at which point both pixel popping and borders become noticeable artifacts. So I blend between the current texture for a node and the node's parent texture to hide the borders and blend in new textures gracefully over a number of frames. It looks considerably better in my case and it was fairly easy to do with quadtrees. > So the simplest bintree texture scheme is to just have a fixed > relationship with the bintree triangles, as the ASCI art implied. > But in reality this causes a problem near horizons. So it turns > out you want to decouple the triangles from any specific texture, > and let them refine more as needed. The priorityqueue scheme > I use keeps track of the min and max estimated projected texel sizes, > and splits whenever max/min>A and merges when max/min<A for its > parent (this is a really vague description I know...the paper is > in the works). > Ahh ok I was wondering about this .... having two triangles of the diamond associated with each texture is also clearly ineffecient in terms of GPU useage. The ideal triangle/texture ratio is going to be dependent upon the system, but I'm certain is always going to be much higher than 1. So decoupling triangles and textures solves that problem, and also solves the problem you mention above. So you have essentially two seperate interlinked trees then? One for textures and one for triangles? I started with a single quadtree for both and quickly ran into the problem you mention above, which in my case was even worse .. .. the ideal metric for textures is very different than the ideal for geometry, and also it can take a very long time to generate four textures for a quadtree split, which unecessarily prevents quick geometry optimization. [..snip..] > > The triangle bintree stuff *is* regular grids! But with a lot > fewer cases, and single displacements (at the new "centroid" > i.e. "split points"). Here is what happens in ASCII art: > > ***** >      >  o  o  o  o  >      > ***** >      >  o  o  o  o  >      > ***** >      >  o  o  o  o  >      > ***** This I don't quite understand: "the triangle bintree stuff is regular grids!" .. . I can see how the bintree is derived from a regular grid . .. > > The "*" and "o" are the old and new vertices during a refinement > step. You can do fractal displacements from the centroids > of the "*" faces, for example. If you want a smoother > subdivision scheme, there is a really slick one: > > Step 1) compute "o" vertices as the centroid (average) of the "*" faces > Step 2) move the "*" vertices halfway towards the centroid of > its four nearest "o" vertices that you just computed > > If you want to do "good" fractals, I would also need to tell you > a couple of other steps relating to some wavelets we have in this > subdivision context. But I want to get a publication out first... Well I'm not totally sure what you mean by "good" fractals :) I would consider "good" fractals to be something along the lines of what Ken Musgrave has done .. .. http://www.fractalworlds.com. I've based most of my stuff on his, with the major exception that my speed constraint means that I must cache noise evaluations and thus only add in ONE new octave when I generate each new LOD. This makes perfect sense from the wavelet perspective, at each new LOD evaluation, you only calculate and add in the new frequency for this LOD, you don't actually recalculate the entire fractal/texture from scratch. The difference between log(n) noise evaluations and 1 noise evaluation can be up to 20x or more for a planet texture and makes all the difference in speed . ... Vanilla fbm and vanilla multifractals are trivial to convert to this wavelet evaulation, but Ken's favorite, the "ridged multifractal", has a basis function considerably more complex than the bicubic .. that is C1 discontinous where the noise function has been folded (ie the ridges). Ken Perlin used the same noise evaulation technique for his java planet applet which just uses vanilla fbm. . .... Also, I don't think its worthwhile to evaluate your fractals directly on vertices . .. you need the heightfield anyway for generating the texture (as many shader/texture parameters depend on it and you want per pixel shading) . .. so I evaluate everything as images and then just sample vertices from the displacement image. > > > I believe (hope) that on the GF3 a vertex shader could be used for this, > > reducing your per vertex memory footprint by a factor of 8. In that case, > > quadtrees+regular grids could perhaps beat other schemes in mesh > > approximation quality by shear vertex count. > > HmmmI am NOT a fan of vertex shading in the context of multires > geometry. I think you are far better off using textures for > all your lighting. Think as follows: look up you normal/base color > from textures, perform transforms/ops in the register combiners, > use results to look up from a "diffuse" and "specualar"filtered > environment maps, and voila!, infinite numbers > of lights for full phong shading! Apparently GF3 is the first > hardware that can manage this, and it is not because of > the vertex programming. I don't have a GF3 to try this out > on yet, but you can get my softwareonly version at > http://www.cognigraph.com/LibGen > See the Surftools/Mesh code if you are interested (IRIX/Linux only). > Screenshots at: > http://graphics.cs.ucdavis.edu/~duchaine/mesh.html > > I AM a fan of pervertex operations for geometry effects. I agree here on all these points, which is why I mentioned using a vertex shader that just reads in a single displacement scalar and generates the vertex from that ... . if all your shading is done with images at the pixel level, then the vertex shader could reduce to something very simple (texture coordinates are implicit, vertex surface normal is unecessary) and very fast (hopefully even doing geometry blending on the card). High triangle counts are still important for having very complex (ie rough) terrains. > > > > > Of course, neither quadtrees nor ROAM nor VIPM are going to help much with > > rendering a realistic forest on top of your terrain. I'm surprised there's > > not more interest and research in more general volumetric LOD schemes. > > Everyone seems to forget the very limiting assumptions that surfaceLOD > > schemes make. > > No kidding! Wouldn't it be great to unify surface LOD and imagebased > rendering/light fields into a single logical representation? ROAMing > lightfields anyone? ;) Yes! I've been thinking about this for a while. You would need some sort of metaLOD, octrees perhaps, and then numerous different ways of modelling/rendering the contents of a node with different fined grained LOD's representations. One method could be volumetric modelling and IBR, then at a finer level you could have isosurface extraction and some novel lumigraph/surface LOD scheme, which then degenerates to true surface LOD once that becomes most effecient. There are numerous obstacles here: using volumes are probably still too expensive in both memory and generation time, IBR is memory intensive as well .. transitions between different reps are a pain ... but this is the way to go I think. The way to apply LOD to a plenoptic surface or volume isn't quite intuitive to me .. .. other than something simple like storing multiple rendered images for each octree node and using blending (perhaps with warping) to render with a few of them each frame. > > BTW, we do have a tetrahedral version of the triangle bintrees. > Not quite as simple and clean: there are three flavors of tets > that come in phases. New vertices alternate being associated > with the cells, faces and edges of an octree grid. The "diamond" > based view of the triangle bintree carries over essentially unchanged, > and selective refinement is as fast as with the 2D grid (which > surprised me when I first saw it). The big trick is what do > you put in the tets? Right now we are struggling with isosurfaces > from gigantic 3D finiteelement simulations, examples go up to > 460 million trangles per fineres surface, and they can be nasty > surfaces! See > http://muldoon.cipic.ucdavis.edu/~hvm00/abstracts/duchaineau.pdf > for a tiny piece of one. The tetbased scheme seems to be the > best way to quickly change isolevel. The surfacebased schemes > break down because there isn't a single surface, but in principle > an infinite family of them. Kind of like an animating freeform > surface... Hmm .. this looks quite interesting. .. thanks for the paper:) 
From: Rui Ferreira <rui.ferreira@mo...>  20010308 20:24:07

Heh. Reply 1: W' = W0 + (dW/dX)(X'  X0) + (dW/dY)(Y'  Y0) "(...)...This stuff is pretty obvious with rasterizers and edge delta walk..." Reply 2: p = s p_0 + t p_1 + q p_2 (s + t + q = 1 inside the triangle) "logical that the value on the baricenter is like the average of the of all the 3 vertices..." I probably should start reading my own posts looking for answers ! :] Thanks for the heads up. Rui PS: Yeah, I have "Real Time Rendering", but I'm on page 158! Go figure... PS2: "I'll let you do it"... Hecker, you old softy :] 
From: Charles Bloom <cbloom@cb...>  20010308 20:11:18

At 11:24 AM 3/8/2001 0800, you wrote: >Umm. Neither matrices nor quaternions are "fundamental rotation types". >Rather, they are two different algebraic formalisms for working with a >common geometric abstraction: 3D rotations (which in my nomenclature means >the same as "orientations"). I meant "fundamental" as a reference to its role in the engine architecture. In every sensible 3d engine you must store some representation of the rotation group in your objects or scene graph nodes. Certainly, you can think of quats and mats as "tools", but if you find that you are using quats all the time, then storing matrices as your "fundamental" type is the wrong choice. You want to choose a fundamental type which is the most common form that you talk to rotations in. >Nor should you think of one "versus" the other. They are two tools, each >with its advantages for different jobs. See above. >Your two lists leave out the most important property, even the most >fundamental property, of matrices, which quaternions definitely lack; >namely, that they directly display the basis vectors of the rotated frame in >their components with respect to the unrotated frame (and vice versa). Ok, this is an excellent point which I totally forgot and probably seals the deal. If it weren't for this then I think quats would win because of their smaller size and better interpolation properties.  Charles Bloom cbloom@... http://www.cbloom.com 
From: Charles Bloom <cbloom@cb...>  20010308 19:59:46

Axis + Angle is exactly equivalent to a quaternion, that's what a quaternion is. The memory use is the same (4 floats). I think you'll find that if you write out the math operators, quaternions end up being much simpler, because they've essentially got the sin & cos of the angle cached out. At 01:29 PM 3/8/2001 0500, you wrote: >This is almost spooky, I was just contemplating how I was going to store >rotations for our 3D objects. Right now we use euler angles and its just >not cutting it. > >For me matrices are out of the question (too much memory), so it was between >quaternions and axis+angle representation. With axis+angle you get the same >memory usage and a more humanunderstandable representation, but I'm not >sure of the speed of converting to/from matrices. > >Is there a reason to not even consider axis+angle?  Charles Bloom cbloom@... http://www.cbloom.com 
From: Blake Senftner <bsenftner@ro...>  20010308 19:44:42

The key to remember is: For counter clockwise arranged verts all points inside the triangle have positive barycentric coords and points outside have mixed positive/negative barycentric coords. And for clockwise arranged verts all points inside the triangle have negative barycentric coords and points outside have mixed positive/negative barycentric coords. Blake > Original Message > From: Tom Forsyth [mailto:tomf@...] > Sent: Thursday, March 08, 2001 11:25 AM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Interpolation Over a Triangle > > > > From: Chris Hecker [mailto > > > Barycentric coordinates are: > > > > p = s p_0 + t p_1 + q p_2 (s + t + q = 1 inside the triangle) > > With my pedant's hat on, I point out that s+t+q = 1 anywhere > on the plane of > the triangle, not just inside it. :) > > > Chris > > > > Tom Forsyth  Muckyfoot bloke. > > What's he up to now? > http://www.muckyfoot.com/startopia/cam.html > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 
From: Ron Levine <ron@do...>  20010308 19:33:49

Jason Zisk wrote > This is almost spooky, I was just contemplating how I was going to store > rotations for our 3D objects. Right now we use euler angles and its just > not cutting it. > Moreover, if you are using them as your fundamental parameters of orientation, then you are opening yourself up to real grief because of the inescapable mathematical singularities of such a parametrization. You will meet this grief whenever you find yourself asking for the Euler angles to produce a given rotation. > For me matrices are out of the question (too much memory), ... Bah. The storage requirements for your rotation parameters, be they expressed in matrices or quaternions or other, are typically orders of magnitude smaller than the storage required for the vertex data of the rotated objects. Therefore, multiplication of the rotation storage requirements by 3/2 (the factor involved in going from quaternions to matrices) must be inconsequential. In today's game applications, the time needed to convert between matrices and quaternions and back must be a much more important consideration. >  Original Message  > From: "Charles Bloom" <cbloom@...> > To: <gdalgorithmslist@...> > Sent: Thursday, March 08, 2001 12:42 PM > Subject: [Algorithms] quaternions in a 3d engine > > > > > > Ok, I just wanted to go over the pros/cons of quaternions > > vs. matrices as a fundamental rotation type for a 3d > > engine (eg. in all my objects, etc.). > > > > Pro Quats : > > Lower memory use. 4 floats instead of 9. > > Slightly faster vector>vector transform and > > quat>quat transform (maybe). > > Easier to interpolate neatly. > > > > Anti Quats (Pro Matrices) : > > Must do semiexpensive conversion to matrices to > > hand them to D3D. Probably not a big deal > > since you're doing row major > column major > > conversion anyway most likely. > > Must store a separate scale float if you want that, > > and/or a scaling vector for nonuniform scale. > > This separation of rotation and scale is seen > > as an advantage by some. > > > > > >  > > Charles Bloom cbloom@... http://www.cbloom.com > > > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 
From: Tom Forsyth <tomf@mu...>  20010308 19:24:46

> From: Chris Hecker [mailto > Barycentric coordinates are: > > p = s p_0 + t p_1 + q p_2 (s + t + q = 1 inside the triangle) With my pedant's hat on, I point out that s+t+q = 1 anywhere on the plane of the triangle, not just inside it. :) > Chris Tom Forsyth  Muckyfoot bloke. What's he up to now? http://www.muckyfoot.com/startopia/cam.html 
From: Ron Levine <ron@do...>  20010308 19:23:59

Charles Bloom wrote > > Ok, I just wanted to go over the pros/cons of quaternions > vs. matrices as a fundamental rotation type for a 3d > engine (eg. in all my objects, etc.). > Umm. Neither matrices nor quaternions are "fundamental rotation types". Rather, they are two different algebraic formalisms for working with a common geometric abstraction: 3D rotations (which in my nomenclature means the same as "orientations"). Nor should you think of one "versus" the other. They are two tools, each with its advantages for different jobs. But the fact is that in most graphics and game applications, you cannot do without matrices. The question is whether it is worth your while also to implement quaternions. > Pro Quats : > Lower memory use. 4 floats instead of 9. > Slightly faster vector>vector transform and > quat>quat transform (maybe). > Easier to interpolate neatly. > > Anti Quats (Pro Matrices) : > Must do semiexpensive conversion to matrices to > hand them to D3D. Probably not a big deal > since you're doing row major > column major > conversion anyway most likely. > Must store a separate scale float if you want that, > and/or a scaling vector for nonuniform scale. > This separation of rotation and scale is seen > as an advantage by some. Your two lists leave out the most important property, even the most fundamental property, of matrices, which quaternions definitely lack; namely, that they directly display the basis vectors of the rotated frame in their components with respect to the unrotated frame (and vice versa). I use this property in my 3D programming all the time. 
From: Tom Forsyth <tomf@mu...>  20010308 19:21:30

> Must do semiexpensive conversion to matrices to > hand them to D3D. Probably not a big deal > since you're doing row major > column major > conversion anyway most likely. Eh? Just store your matrices the other way up natively. IMHO, quats are good for: Animation storage. They're small, and compress well. Animation lerping. They lerp well. "trackball" user interfaces. ...and that's it. Everywhere else they are either slower, or roughly equivalent to matrices. And my brain understands matrices so much better, making debugging far easier, which is why I use matrices wherever possible. Tom Forsyth  Muckyfoot bloke. What's he up to now? http://www.muckyfoot.com/startopia/cam.html > Original Message > From: Charles Bloom [mailto:cbloom@...] > Sent: 08 March 2001 17:42 > To: gdalgorithmslist@... > Subject: [Algorithms] quaternions in a 3d engine > > > > Ok, I just wanted to go over the pros/cons of quaternions > vs. matrices as a fundamental rotation type for a 3d > engine (eg. in all my objects, etc.). > > Pro Quats : > Lower memory use. 4 floats instead of 9. > Slightly faster vector>vector transform and > quat>quat transform (maybe). > Easier to interpolate neatly. > > Anti Quats (Pro Matrices) : > Must do semiexpensive conversion to matrices to > hand them to D3D. Probably not a big deal > since you're doing row major > column major > conversion anyway most likely. > Must store a separate scale float if you want that, > and/or a scaling vector for nonuniform scale. > This separation of rotation and scale is seen > as an advantage by some. > > >  > Charles Bloom cbloom@... http://www.cbloom.com 
From: Chris Hecker <checker@d6...>  20010308 18:59:16

You had it right here: >the values on that edge vertices. Also, its logical that the value on the >baricenter is like the average of the of all the 3 vertices... ^^^^^^^^^^^ Use barycentric coordinates. Use the point to calculate the barycentric coordinates of itself inside the triangle, and then use the barycentric coordinates to calculate the interpolated value. You can do out the math in a bunch of different ways, but it's fun, so I'll let you do it. Barycentric coordinates are: p = s p_0 + t p_1 + q p_2 (s + t + q = 1 inside the triangle) Chris 
From: Pierre Terdiman <p.terdiman@wa...>  20010308 18:56:50

> memory usage and a more humanunderstandable representation, but I'm not > sure of the speed of converting to/from matrices. You don't convert directly from AngleAxis to matrices (AFAIK, and correct me if I'm wrong, could be interesting). As far as I'm concerned, I first convert the AngleAxis to a quat (5 muls, 1 cos, 1 sin) then the quat to a matrix. > Is there a reason to not even consider axis+angle? The only advantage of AngleAxis is the readable form (AFAIK again). IMHO the everlasting flame wars about quats/mats/etc provide a very obvious conclusion: there's no "best" representation. So use them all in the right places. I use matrices, quats, angleaxis and Euler angles. The extra coding effort was way cheaper / faster than trying to do everything with matrices or everything with quats, or always going back to the same questions without answers. P. 
From: Amit Bakshi <abakshi@ra...>  20010308 18:47:29

Quaternions are essentially a scaled form of angleaxis representation. In order to go from angleaxis to matrix, you'll essentially be doing an intermediate "toquaternion" step where you'll be making some calls to cos/sin. Since the quaternion is already in this format, you can convert to a matrix with a few multiplies/adds. Amit  Original Message  From: "Jason Zisk" <ziskj@...> To: <gdalgorithmslist@...> Sent: Thursday, March 08, 2001 10:29 AM Subject: Re: [Algorithms] quaternions in a 3d engine > This is almost spooky, I was just contemplating how I was going to store > rotations for our 3D objects. Right now we use euler angles and its just > not cutting it. > > For me matrices are out of the question (too much memory), so it was between > quaternions and axis+angle representation. With axis+angle you get the same > memory usage and a more humanunderstandable representation, but I'm not > sure of the speed of converting to/from matrices. > > Is there a reason to not even consider axis+angle? > >  Jason Zisk >  nFusion Interactive LLC 
From: Graham Rhodes <grhodes@se...>  20010308 18:41:07

You will probably want to use barycentric coordinates to do the interpolation, which is a way to interpolate over a triangle using two parametric coordinates (e.g., s and t). You can interpolate any number of properties at a vertex quite easily. See "RealTime Rendering" by Haines and Moller for an introduction. (But probably someone here who has a bit of time will provide details before you can look at the book.) Graham Rhodes > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...]On Behalf Of Rui > Ferreira > Sent: Thursday, March 08, 2001 12:50 PM > To: gdalgorithmslist@... > Subject: [Algorithms] Interpolation Over a Triangle > > > Hi all, long time no post. > > What is the canonical way to do a vertex values interpolation over a > triangle ? If I have 3 value properties on each of the 3 vertices, and I > have, say, how far a point is on two of the edges. What is the best way to > get the interpolated result ? > > On the middle of the edges, its well know that the result is half > the sum of > the values on that edge vertices. Also, its logical that the value on the > baricenter is like the average of the of all the 3 vertices... > > I can weight the contribution to the final result of each of the vertices > with a distance from the point to each vertex... but that may give some > "squished" results if we have slivery tris... or do it the other > way and use > the distances from each middle edge to the point instead of > simple distance > to vertices, but in this case I'm lerping the edges and averaging the > result! It doesn't seem right... I've tried a glorified bilerp > but its a lot > easier with a fourth vertex there :] > > This stuff is pretty obvious with rasterizers and edge delta walk but what > is the analytical way of doing this ?... > > Thanks in advance. > > Rui Ferreira > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 
From: Jack Mathews <jack@re...>  20010308 18:40:05

Well, you can actually have scale in a quat. Since quats are pretty much only usable normalized, you could encode the scale as the magnitude of the quat. And of course the scale would have to be positive or 0. Of course you have normalization costs and all that, but if you're purely concerned about memory usage, this could help. Of course, it just changes the con to "having to renormalize a quat with scale all the time." :) Jack Original Message From: Charles Bloom [mailto:cbloom@...] Sent: Thursday, March 08, 2001 11:42 AM To: gdalgorithmslist@... Subject: [Algorithms] quaternions in a 3d engine Ok, I just wanted to go over the pros/cons of quaternions vs. matrices as a fundamental rotation type for a 3d engine (eg. in all my objects, etc.). Pro Quats : Lower memory use. 4 floats instead of 9. Slightly faster vector>vector transform and quat>quat transform (maybe). Easier to interpolate neatly. Anti Quats (Pro Matrices) : Must do semiexpensive conversion to matrices to hand them to D3D. Probably not a big deal since you're doing row major > column major conversion anyway most likely. Must store a separate scale float if you want that, and/or a scaling vector for nonuniform scale. This separation of rotation and scale is seen as an advantage by some.  Charles Bloom cbloom@... http://www.cbloom.com _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist 
From: Amit Bakshi <abakshi@ra...>  20010308 18:34:29

I'd also add that quaternions are easier to normalize than rotation matrices. Also, it's not just easier to interpolate, it's the only way to interpolate between 2 orientations and get the shortest path. I don't think you can just interpolate between 2 rotation matrices (someone correct me if I'm wrong). It's never been an either/or thing for me. I use quaternions where I need them and avoid them where I don't. Hell, even eulers make sense for some things :) As for 4 floats vs 9, you can actually compress a quaternion down even more by just storing x,y,z (which can be quantized) plus a sign bit. Amit  Original Message  From: "Charles Bloom" <cbloom@...> To: <gdalgorithmslist@...> Sent: Thursday, March 08, 2001 9:42 AM Subject: [Algorithms] quaternions in a 3d engine > > Ok, I just wanted to go over the pros/cons of quaternions > vs. matrices as a fundamental rotation type for a 3d > engine (eg. in all my objects, etc.). > > Pro Quats : > Lower memory use. 4 floats instead of 9. > Slightly faster vector>vector transform and > quat>quat transform (maybe). > Easier to interpolate neatly. > > Anti Quats (Pro Matrices) : > Must do semiexpensive conversion to matrices to > hand them to D3D. Probably not a big deal > since you're doing row major > column major > conversion anyway most likely. > Must store a separate scale float if you want that, > and/or a scaling vector for nonuniform scale. > This separation of rotation and scale is seen > as an advantage by some. > > >  > Charles Bloom cbloom@... http://www.cbloom.com > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist 
From: Jason Zisk <ziskj@op...>  20010308 18:28:37

This is almost spooky, I was just contemplating how I was going to store rotations for our 3D objects. Right now we use euler angles and its just not cutting it. For me matrices are out of the question (too much memory), so it was between quaternions and axis+angle representation. With axis+angle you get the same memory usage and a more humanunderstandable representation, but I'm not sure of the speed of converting to/from matrices. Is there a reason to not even consider axis+angle?  Jason Zisk  nFusion Interactive LLC  Original Message  From: "Charles Bloom" <cbloom@...> To: <gdalgorithmslist@...> Sent: Thursday, March 08, 2001 12:42 PM Subject: [Algorithms] quaternions in a 3d engine > > Ok, I just wanted to go over the pros/cons of quaternions > vs. matrices as a fundamental rotation type for a 3d > engine (eg. in all my objects, etc.). > > Pro Quats : > Lower memory use. 4 floats instead of 9. > Slightly faster vector>vector transform and > quat>quat transform (maybe). > Easier to interpolate neatly. > > Anti Quats (Pro Matrices) : > Must do semiexpensive conversion to matrices to > hand them to D3D. Probably not a big deal > since you're doing row major > column major > conversion anyway most likely. > Must store a separate scale float if you want that, > and/or a scaling vector for nonuniform scale. > This separation of rotation and scale is seen > as an advantage by some. > > >  > Charles Bloom cbloom@... http://www.cbloom.com > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > http://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > 