Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
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}

2017 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}
(1) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 







1
(4) 
2
(3) 
3
(3) 
4
(4) 
5
(10) 
6
(10) 
7
(6) 
8
(8) 
9
(1) 
10
(7) 
11
(7) 
12
(6) 
13
(6) 
14
(19) 
15
(1) 
16

17
(2) 
18
(3) 
19
(1) 
20

21
(2) 
22
(3) 
23
(2) 
24
(2) 
25

26
(3) 
27
(26) 
28
(4) 
29
(4) 
30







From: Stephane Etienne <setienne@hi...>  20060414 17:46:45

> Yes and no; it turns out that even if you won't overshoot if > you don't start braking at the start of the frame, at the end > of the frame you might be going too fast and end up > overshooting anyway. Yes, this is why I said you need to figure out how long it will take you to stop AFTER applying your acceleration. If you overshoot, you clearly can't apply full acceleration.=20 > > The 3D problem isn't any more complex than the 1D problem. You > > can treat all axes independently. > > The problem is that the axes aren't independent. The > acceleration vector is dependent on the move vector, both of > which are rotating through the course of the frame. You don't need to worry about the fact that the move vector and the acceleration are rotated. It simply is a side effect irrelevant to the problem at hand. Because your coordinate is orthogonal, axes do are independent. > > Also, if your dt is not constant, there simply is no solution > > to your problem. > > That's what integrating solves. I.e. that's why you compute > > curPos +=3D (curVel * dt) + (accel * dt * dt / 2) > curVel +=3D accel * dt > > instead of > > curVel +=3D accel * dt > curPos +=3D curVel * dt Nope it does not. The dt transforms your continuous problem into a discrete problem. As long as your dt is constant, it's ok. If your dt is not constant, there simply is no good solution. Just picture what would happen if you planned on reaching your target in an expected 2 timesteps. If your first dt is too long (e.g. > 2 expected timesteps), you missed your target because you overshot. If you have not transformed your problem into a constant dt, I recommend that you do that right now. Things will look a lot better already. > The math is fairly straight forward for an instant in time.=20 > The problem I'm having is in integrating the solution for > continuous behavior. This is a red herring as using a dt discretize your problem. > > In practice, if your time step is small enough not doing > > anything in case 3 will probably work just fine. > > Haven't done much work on PSP games lately, eh Stephane? :)=20 > In practice, though, I think #3 wouldn't be terribly hard to > solve, but again you need to figure out if you'll be able to > stop ontarget after you process this frame's motion. No PSP for me, that's for sure. But trust me on this one, just try it by applying 0 acceleration if after applying acceleration you will overshoot. Don't forget to check if you will overshoot by testing the situation at the next time step. Even if you apply no acceleration at this time step, you may overshoot at the next time step. If this is the case, then you need to start decelerating. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Tom Plunket Sent: Thursday, April 13, 2006 11:27 PM To: gdalgorithmslist@... Subject: RE: [Algorithms] Integrating acceleration in 3D > You need to account for your current velocity and how long it > will take you to stop, otherwise you will overshoot. Yep, that's why I compute the "desired acceleration" from the difference between the target point and the point where I'd stop if I were at maximum braking. > When you overshot in 1D, this is probably what happened. Yes and no; it turns out that even if you won't overshoot if you don't start braking at the start of the frame, at the end of the frame you might be going too fast and end up overshooting anyway. I.e. even if distancetostop might be larger than distancetotarget, you still need to make sure that after this timestep that fact still holds (and if it doesn't, you need to back up a bit). Incidentally, I'm trying a variation on this in 3D right now but it's tedious just because I have to recompute a bunch of stuff twice... ...perhaps I could compute the fact that I will overshoot earlier though, but I'll have to ponder it. > The 3D problem isn't any more complex than the 1D problem. You > can treat all axes independently. The problem is that the axes aren't independent. The acceleration vector is dependent on the move vector, both of which are rotating through the course of the frame. > In conclusion, you need to the following: > > 1  If after applying acceleration, I can still stop and not > overshoot, then apply maximum acceleration. > 2  If without applying acceleration I will still overshoot, > decelerate as much as possible to minimize overshooting. > 3  If none of the above, you can apply some amount of > acceleration. The math is fairly straight forward for an instant in time.=20 The problem I'm having is in integrating the solution for continuous behavior. > You could lerp from 0 to maxAccel as a function of how much > you would be overshooting if you applied full acceleration. I may go for an extra layer of continuity at some point, but I don't think I need to. > Since the equation for acceleration is not linear, your alpha > for your lerp needs to account for that. Linear acceleration is actually fine but not the battle I'm fighting at this time. > In practice, if your time step is small enough not doing > anything in case 3 will probably work just fine. Haven't done much work on PSP games lately, eh Stephane? :)=20 In practice, though, I think #3 wouldn't be terribly hard to solve, but again you need to figure out if you'll be able to stop ontarget after you process this frame's motion. > Also, if your dt is not constant, there simply is no solution > to your problem. That's what integrating solves. I.e. that's why you compute curPos +=3D (curVel * dt) + (accel * dt * dt / 2) curVel +=3D accel * dt instead of curVel +=3D accel * dt curPos +=3D curVel * dt tom!  This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.asus.falkag.net/sel?cmd=3Dlnk&kid=3D110944&bid=3D241720&dat=3D= 121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Tom Forsyth <tom.forsyth.gdalgo@ee...>  20060414 17:07:09

But in this case it doesn't matter  objects A and B don't overlap onscreen, so their relative order is unimportant. Obviously you can easily get problem sorts where there is no correct sorting (A in front of B in front of C in front of A), but if the objects are in different nodes, this always works. If you're just using this for earlyZ speed improvements rather than functionality, then any sort of sloppy ordering is fine. Even crude things like poweroftwo buckets gets you most of the benefit (buckets of 01 meter, 12, 24, 48, 816, 1632, etc). Larger buckets can be faster because within each bucket you have more opportunity for reducing state changes. TomF. > Original Message > From: gdalgorithmslistadmin@... > [mailto:gdalgorithmslistadmin@...] On > Behalf Of Richard Mitton > Sent: 13 April 2006 18:53 > To: gdalgorithmslist@... > Subject: Re: [Algorithms] Fronttoback traversal of quadtree > > > To clarify further  > (see diagram) > > Even though sector "1" would be considered in front of sector > "3", note > that object "A" is actually *behind* object "B". (from the camera's > point of view) > > Of course, if you're just doing this for performance reasons (e.g. to > reduce overdraw or something) then it might not matter, in which case > you're fine. > >  > ()() Richard Mitton > ( '.') > (")_(") code jester .:. treyarch .:. mitton@... > > > Richard Mitton wrote: > > Isn't it just a case of traversing the 4 children in fronttoback > > order, rather than the conventional 0,1,2,3 order? > > > > Although I'm not sure that's entirely correct (I think it > suffers from > > the same kind of problems as the Painter's Algorithm, when > it comes to > > deciding which node is in front). It might be more accurate > to simply > > sort the node list after traversal. > > > 
From: <christer_ericson@pl...>  20060414 16:57:22

Tom Plunket wrote: > I'm having trouble with something that I haven't done in a long > time (and was never really that good at it to begin with), and > I'm wondering if anyone with this stuff closer at hand may be > able to give me some help. As Jon Blow said, this is in the territory of control theory. While you explained the problem as having a stationary target, your "which to get me going can be assumed to be stopped" comment implies to me that you ultimately want a moving target. In such a scenario what you have is a "pursuitevasion" problem and that, along with "differential games" and "pursuit problems", are the terms you want to google for. One of the classic books on this topic is Isaacs "Differential Games" from 1965, which I read at university. It used to be out of print but I see that it is now available from Dover for a measly $11. A steal at that price and just what you want to solve your problem! Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica 
From: Erin Catto <erincatto@sb...>  20060414 08:05:09

Since the initial velocity is arbitrary, the point will follow a curved path. Therefore, as Jonathon hinted, you need to use some feedback. // Desired velocity based on feedback (beta in [0,1]) v_d = (beta / delta_t) * (x_target  x_1) // Desired acceleration a_d = (v_d  v_1) / delta_t // Clamp aMag = norm(a_d); if (aMag > maxA) a_D *= maxA / aMag // Integrate (symplectic Euler) v_2 = v_1 + delta_t * a_d x_2 = x_1 + delta_t * v_2 Caveat: I haven't tested these equations. I don't think clamping would cause stability problems, it will just slow the movement. Erin 
From: Tom Plunket <gamedev@fa...>  20060414 07:06:17

> You want to start reading books on "control theory". Thanks for the link, although reading said books might be overkill for my current needs. I have all of the "transfer functions" worked out algorithmically, I think, the problem that remains will be turning all of my inputs and functions into vector operations. It's pretty cool and should net me something that is highly useful if I'm reading it right. ...I'm reading it right if in that first diagram I'm interpreting r, e, u, and y as vectors and C and P as matrices. ...at least that seems to be kind of work, but I'm not sure then how the "1 +" fits into a matrix multiply. :) I'll keep hammering on it. tom! 
From: Tom Plunket <gamedev@fa...>  20060414 06:26:54

> You need to account for your current velocity and how long it > will take you to stop, otherwise you will overshoot. Yep, that's why I compute the "desired acceleration" from the difference between the target point and the point where I'd stop if I were at maximum braking. > When you overshot in 1D, this is probably what happened. Yes and no; it turns out that even if you won't overshoot if you don't start braking at the start of the frame, at the end of the frame you might be going too fast and end up overshooting anyway. I.e. even if distancetostop might be larger than distancetotarget, you still need to make sure that after this timestep that fact still holds (and if it doesn't, you need to back up a bit). Incidentally, I'm trying a variation on this in 3D right now but it's tedious just because I have to recompute a bunch of stuff twice... ...perhaps I could compute the fact that I will overshoot earlier though, but I'll have to ponder it. > The 3D problem isn't any more complex than the 1D problem. You > can treat all axes independently. The problem is that the axes aren't independent. The acceleration vector is dependent on the move vector, both of which are rotating through the course of the frame. > In conclusion, you need to the following: > > 1  If after applying acceleration, I can still stop and not > overshoot, then apply maximum acceleration. > 2  If without applying acceleration I will still overshoot, > decelerate as much as possible to minimize overshooting. > 3  If none of the above, you can apply some amount of > acceleration. The math is fairly straight forward for an instant in time. The problem I'm having is in integrating the solution for continuous behavior. > You could lerp from 0 to maxAccel as a function of how much > you would be overshooting if you applied full acceleration. I may go for an extra layer of continuity at some point, but I don't think I need to. > Since the equation for acceleration is not linear, your alpha > for your lerp needs to account for that. Linear acceleration is actually fine but not the battle I'm fighting at this time. > In practice, if your time step is small enough not doing > anything in case 3 will probably work just fine. Haven't done much work on PSP games lately, eh Stephane? :) In practice, though, I think #3 wouldn't be terribly hard to solve, but again you need to figure out if you'll be able to stop ontarget after you process this frame's motion. > Also, if your dt is not constant, there simply is no solution > to your problem. That's what integrating solves. I.e. that's why you compute curPos += (curVel * dt) + (accel * dt * dt / 2) curVel += accel * dt instead of curVel += accel * dt curPos += curVel * dt tom! 
From: Jonathan Blow <jon@nu...>  20060414 06:15:50

You want to start reading books on "control theory". http://en.wikipedia.org/wiki/Control_theory > In threespace, I'm stumped. My naive implementation swims all > over the place, the object essentially goes into orbit around > the target point once it's within a distance that I'm guessing > is relative to the acceleration value and the timestep. I > quickly realized that the problem was because I had just > reverted to computing the velocity once per frame and making it > constant over the whole timestep. I can "damp" the system > easily enough by truncating the move vector if it tries to go > past the point, but that's not desirable. > 
From: Stephane Etienne <setienne@hi...>  20060414 06:11:14

You need to account for your current velocity and how long it will take you to stop, otherwise you will overshoot. When you overshot in 1D, this is probably what happened. The 3D problem isn't any more complex than the 1D problem. You can treat all axes independently. In conclusion, you need to the following: 1  If after applying acceleration, I can still stop and not overshoot, then apply maximum acceleration. 2  If without applying acceleration I will still overshoot, decelerate as much as possible to minimize overshooting. 3  If none of the above, you can apply some amount of acceleration. It is getting late to do the math for this case though. You could lerp from 0 to maxAccel as a function of how much you would be overshooting if you applied full acceleration. Since the equation for acceleration is not linear, your alpha for your lerp needs to account for that. In practice, if your time step is small enough not doing anything in case 3 will probably work just fine. Also, if your dt is not constant, there simply is no solution to your problem. In that case, you will want to be more conservative. I recommend that you do whatever you can to transform this problem into a problem with a constant dt though. Stephane. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Tom Plunket Sent: Thursday, April 13, 2006 10:49 PM To: gdalgorithmslist@... Subject: [Algorithms] Integrating acceleration in 3D I'm having trouble with something that I haven't done in a long time (and was never really that good at it to begin with), and I'm wondering if anyone with this stuff closer at hand may be able to give me some help. What I've got is a thing in space moving at some velocity. I want that point to stop exactly at a given point (which to get me going can be assumed to be stopped). My desire is to model continuous velocity, but the acceleration given is a scalar magnitude which allows me to instantly hit full acceleration in any direction in 0 time. I'm computing the point in space where I'd end up if I were to stop as quickly as possible, and computing my acceleration vector as the vector between that fullstop point and the desired target, clamped in magnitude to the maximum acceleration. In onespace this is trivial, I just integrate as the acceleration which is, and currentPoint =3D oldPoint + (velocity * time) + (acceleration * time^2 / 2), where I compute acceleration as above (subtract my fullstop point from the target point and clamp to +/ maxAccel). (This actually overshoots a bit but that can be prevented with a bit of added complexity at the velocity maximum.) In threespace, I'm stumped. My naive implementation swims all over the place, the object essentially goes into orbit around the target point once it's within a distance that I'm guessing is relative to the acceleration value and the timestep. I quickly realized that the problem was because I had just reverted to computing the velocity once per frame and making it constant over the whole timestep. I can "damp" the system easily enough by truncating the move vector if it tries to go past the point, but that's not desirable. So, what I think I want to do is integrate the acceleration in 3D space, where the three components are interrelated (i.e. the maximum magnitude of the acceleration vector is fixed), but I can't for the life of me figure out how to make the above 1D process work for me when there's three equations with values that are related. I'm guessing this is just a hard problem (compared to, say, normalizing a vector), but if there's a straightforward way to do it, I'd love to hear about it. Thanks, tom!  This SF.Net email is sponsored by xPML, a groundbreaking scripting language that extends applications into web and mobile media. Attend the live webcast and join the prime developer group breaking into this new coding territory! http://sel.asus.falkag.net/sel?cmd=3Dlnk&kid=3D110944&bid=3D241720&dat=3D= 121642 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Tom Plunket <gamedev@fa...>  20060414 05:49:06

I'm having trouble with something that I haven't done in a long time (and was never really that good at it to begin with), and I'm wondering if anyone with this stuff closer at hand may be able to give me some help. What I've got is a thing in space moving at some velocity. I want that point to stop exactly at a given point (which to get me going can be assumed to be stopped). My desire is to model continuous velocity, but the acceleration given is a scalar magnitude which allows me to instantly hit full acceleration in any direction in 0 time. I'm computing the point in space where I'd end up if I were to stop as quickly as possible, and computing my acceleration vector as the vector between that fullstop point and the desired target, clamped in magnitude to the maximum acceleration. In onespace this is trivial, I just integrate as the acceleration which is, and currentPoint = oldPoint + (velocity * time) + (acceleration * time^2 / 2), where I compute acceleration as above (subtract my fullstop point from the target point and clamp to +/ maxAccel). (This actually overshoots a bit but that can be prevented with a bit of added complexity at the velocity maximum.) In threespace, I'm stumped. My naive implementation swims all over the place, the object essentially goes into orbit around the target point once it's within a distance that I'm guessing is relative to the acceleration value and the timestep. I quickly realized that the problem was because I had just reverted to computing the velocity once per frame and making it constant over the whole timestep. I can "damp" the system easily enough by truncating the move vector if it tries to go past the point, but that's not desirable. So, what I think I want to do is integrate the acceleration in 3D space, where the three components are interrelated (i.e. the maximum magnitude of the acceleration vector is fixed), but I can't for the life of me figure out how to make the above 1D process work for me when there's three equations with values that are related. I'm guessing this is just a hard problem (compared to, say, normalizing a vector), but if there's a straightforward way to do it, I'd love to hear about it. Thanks, tom! 
From: Maik Wagner <maikwagner@we...>  20060414 02:14:20

Richard Mitton wrote: > Even though sector "1" would be considered in front of sector "3", > note that object "A" is actually *behind* object "B". (from the > camera's point of view) I think this lies in nature of Quad/Octtrees, they're just approximating. Imagine the Cells of the tree reduced up to the size of its contents (with vertices it would get to zero), then such situations wont happen, but every performance enhancement would also be gone ;) Regarding the original questions, it doesn't depend on whats in this tree's cells, it should just be aware of the cells. If geometry is fixed (meaning: not moving) a bsptree might help (for 2D, as you speak of Quadtree. it might also work in 3D but i do not know exactly) 
From: Dan Glastonbury <dan.glastonbury@gm...>  20060414 02:06:11

On 4/14/06, Ben Garney <beng@...> wrote: > > I did this for a project a while back. You do your quadtreefrustrum > clipping normally, then compare your camera position with the center > dividing point of that node on the quadtree. In my case, I used a > small lookup table  4 entries for the four possible relative x/y > signs. I was using the signs off the camera direction, not the relative position the the centre of the current nodes bbox. I had a 4x4 entry table already. I'm going to try using the camera's position instead. cheers DanG  Dan Glastonbury, Dan dot Glastonbury at gmail dot com `Pour encourjay lays ortras' 
From: Richard Mitton <mitton@tr...>  20060414 01:53:21

To clarify further  (see diagram) Even though sector "1" would be considered in front of sector "3", note that object "A" is actually *behind* object "B". (from the camera's point of view) Of course, if you're just doing this for performance reasons (e.g. to reduce overdraw or something) then it might not matter, in which case you're fine.  ()() Richard Mitton ( '.') (")_(") code jester .:. treyarch .:. mitton@... Richard Mitton wrote: > Isn't it just a case of traversing the 4 children in fronttoback > order, rather than the conventional 0,1,2,3 order? > > Although I'm not sure that's entirely correct (I think it suffers from > the same kind of problems as the Painter's Algorithm, when it comes to > deciding which node is in front). It might be more accurate to simply > sort the node list after traversal. > 
From: Dan Glastonbury <dan.glastonbury@gm...>  20060414 01:52:23

On 4/14/06, christer_ericson@... < christer_ericson@...> wrote: > > I think you need to define better what you mean by "front to back" > order. Richard Mitton's suggestion is certainly a solution for one > particular definition of front to back. The implementation of his > suggestion would look something along these lines (untested code): My definition of (roughly) fronttoback, is to produce a walk of the quadtree where the leaf nodes are visited such that the leaves are renderin= g in an order to maximise the rejection of distance geometry using the Zbuffer. thanks DanG  Dan Glastonbury, Dan dot Glastonbury at gmail dot com `Pour encourjay lays ortras' 
From: <christer_ericson@pl...>  20060414 01:38:22

Dan Glastonbury wrote: >>Isn't it just a case of traversing the 4 children in fronttoback >>order, rather than the conventional 0,1,2,3 order? > > Well I've put some code into the traversal so that i changes the > order depending on the direction the camera is facing. The results > aren't really working though. I think you need to define better what you mean by "front to back" order. Richard Mitton's suggestion is certainly a solution for one particular definition of front to back. The implementation of his suggestion would look something along these lines (untested code): void TraverseQuadtreeF2B(QuadtreeNode *node, int32 order) { if (node == NULL) return; for (int i = 0; i < 4; i++) TraverseQuadtreeF2B(node>child[i ^ order], order); } // Call code as such: Vector2D eye = ... QuadtreeNode myQuadtree = ... int32 order = ((eye.y < 0.0f) << 1) + (eye.x < 0.0f); TraverseQuadtreeF2B(&myQuadtree, order); Christer Ericson, Director of Tools and Technology Sony Computer Entertainment, Santa Monica 
From: Ben Garney <beng@ga...>  20060414 00:51:39

On 4/13/06, Richard Mitton <mitton@...> wrote: > Isn't it just a case of traversing the 4 children in fronttoback > order, rather than the conventional 0,1,2,3 order? I did this for a project a while back. You do your quadtreefrustrum clipping normally, then compare your camera position with the center dividing point of that node on the quadtree. In my case, I used a small lookup table  4 entries for the four possible relative x/y signs. Hint  good way to test is to filter the entries you iterate over. You'll get a nice line of nodes going from your camera to infinite if you have it right.  Ben Garney Torque Technologies Director GarageGames.Com, Inc. 
From: Dan Glastonbury <dan.glastonbury@gm...>  20060414 00:43:29

On 4/14/06, Richard Mitton <mitton@...> wrote: > > Isn't it just a case of traversing the 4 children in fronttoback > order, rather than the conventional 0,1,2,3 order? Well I've put some code into the traversal so that i changes the order depending on the direction the camera is facing. The results aren't really working though. Although I'm not sure that's entirely correct (I think it suffers from > the same kind of problems as the Painter's Algorithm, when it comes to > deciding which node is in front). It might be more accurate to simply > sort the node list after traversal. That is an option that I've been considering... The other things is that this is for terrain, so I only want the leaves, an= d they're stored in an array. I could probably rasterise the 2D projection o= f frustum, and directly walk the array... thanks DanG  Dan Glastonbury, Dan dot Glastonbury at gmail dot com `Pour encourjay lays ortras' 
From: <robin_green@pl...>  20060414 00:41:38

These may have some interesting references. The Winchester Solid Modeller renderer (WINSOM) from IBM Research was one of the first to use this idea f= or fast CSG. http://domino.watson.ibm.com/tchjr/journalindex.nsf/2733206779564b3d85256bd= 500483abf/0f6e4ab70ee7ee3985256bfa00685c22?OpenDocument Todd, S and Halbert, A, "Fast Redundant Primitive Elimination in CSG processing", IBMUKSC Report 175 (April 1991) JM Burridge et al., =93The WINSOM Solid Modeler and Its Application. to Data Visualization,=94 IBM Systems .I., Vol. 28, No. 4. 1989, pp. 54 H. Samet, "The quadtree and related hierarchical data structures", ACM Comp= uting Surveys, 16, No.2, 187260 (June 1984)  Robin Green Dan Glastonbury wrote: > Hi List, > Doesn't anyone have a reference for traversing a quadtree, using a > frustum for culling, so that the leaves are returned fronttoback > order? My googling and searching gdalgorithms archive has been fruitles= s. >=20 > thanks > DanG > =20 > Dan Glastonbury, Dan dot Glastonbury at gmail dot com > `Pour encourjay lays ortras' 
From: Richard Mitton <mitton@tr...>  20060414 00:28:59

Isn't it just a case of traversing the 4 children in fronttoback order, rather than the conventional 0,1,2,3 order? Although I'm not sure that's entirely correct (I think it suffers from the same kind of problems as the Painter's Algorithm, when it comes to deciding which node is in front). It might be more accurate to simply sort the node list after traversal.  ()() Richard Mitton ( '.') (")_(") code jester .:. treyarch .:. mitton@... Dan Glastonbury wrote: > Hi List, > Doesn't anyone have a reference for traversing a quadtree, using a > frustum for culling, so that the leaves are returned fronttoback > order? My googling and searching gdalgorithms archive has been fruitless. > > thanks > DanG >  > Dan Glastonbury, Dan dot Glastonbury at gmail dot com > `Pour encourjay lays ortras' 
From: Dan Glastonbury <dan.glastonbury@gm...>  20060414 00:22:31

Hi List, Doesn't anyone have a reference for traversing a quadtree, using a frustu= m for culling, so that the leaves are returned fronttoback order? My googling and searching gdalgorithms archive has been fruitless. thanks DanG  Dan Glastonbury, Dan dot Glastonbury at gmail dot com `Pour encourjay lays ortras' 