Re: [vos-d] Movement interpolation update
Karsten Otto wrote: > You cannot really fix this with a "don't-interpolate" flag, > as there is no good place to put one. You could extend the property- > update notification, but a lot of properties do not use interpolation That's ok. Nothing stops you from adding whatever fields you want to the message, and for Terangreal to check for the field for the position property. This is why fields have names. Pete's idea of having extensible method types is interesting though, might be useful. Reed ___ vos-d mailing list vos-d@interreality.org http://www.interreality.org/cgi-bin/mailman/listinfo/vos-d
Re: [vos-d] Movement interpolation update
On Thu, May 03, 2007 at 04:23:38PM +0200, Karsten Otto wrote: > Funny... the problems you mention actually result from a lack of > semantics! > ... > The only *real* solution, both in S4 and S5, would be what the games > do: Send a custom "movement" message... and loose the genericity of > the VOS platform. This is actually really insightful. We talk a lot about how it's easy to extend the semantics of vobjects. Why not be able to extend the sematics of messages? Presently, types list their entire inheritance in the name. For example, "a3dl:object3D.sphere" is in the a3dl namespace, is an "object3D", with additional semantics indicating that it is a "sphere". If a program doesn't understand (or doesn't care about) the type "a3dl:object3D.sphere", it is permitted to interpret it as just "a3dl:object3D". Why not do the same for messages? For example, "core:property-replace" could have specializations "core:property-replace.movement" and "core:property-replace.teleport". Your implementation could handle them separately, and they would be permitted to have additional fields, but would indicate explicitly to the interface that the action (and fields) is an elaboration on "core:property-replace". Such messages could be "sliced" to their simpler versions if a handler for the specialization isn't available. > My hope is that this problem might get smoothed over a bit in S5. I > assume that both position and orientation will likely be embedded > children of an avatar vobject. If you change both, you need to > acquire the lock of the parent, change the values, and release the > lock (ok, VOS will do this for you transparently). In this case, VOS > should defer the update notifications until the parent lock gets > released, and the send them all in an atomic "compund > update" (message block?) which is semantically slightly closer to the > actual user action. I am not quite sure how you could squeeze a > "don't-interpolate" flag into the mix though - unless it is an actual > embedded child of the avatar vobject, which is somewhat messy. What you want is a transaction system for updates. This is something I've been mulling over for awhile, but haven't really found a good way to do it yet. The problem isn't so much for transactions themselves, but that we also was atomic *notify events* so that if I perform a transaction that changes three values, listeners are notified in such a way that they can know that the entire set of values changed at once, so they get a single atomic callback and not three callbacks for each of the three values that changed. That's what makes things like physics work, where position and velocity need to change atomically. Any thoughts on a good model for this? The s5 design is going to make this easier, I think, because instead of strict callbacks for notify events, it will use the same message passing system as for method calls. This might make it easier to implicitly or explicitly recognize cases where notify events should be combined. -- [ Peter Amstutz ][ [EMAIL PROTECTED] ][ [EMAIL PROTECTED] ] [Lead Programmer][Interreality Project][Virtual Reality for the Internet] [ VOS: Next Generation Internet Communication][ http://interreality.org ] [ http://interreality.org/~tetron ][ pgpkey: pgpkeys.mit.edu 18C21DF7 ] signature.asc Description: Digital signature ___ vos-d mailing list vos-d@interreality.org http://www.interreality.org/cgi-bin/mailman/listinfo/vos-d
Re: [vos-d] Movement interpolation update
Reed Hedges wrote: > Terangreal (internally) should have the option of interpolating a > "teleport", maybe. Then if we add a way to click on an object and zoom > up to it, or if you want to do an interpolation for zooming to some > bookmark or viewpoint, you could use it. Maybe add a "don't > interpolate" flag to a position update call? Well if you're talking about interpolating the current avatar's position -- that's something you can do just in ter'angreal and my csplugin modifications won't affect it at all. That is, unless you want other people looking at you to see you "zooming" around smoothly as well. In that case, yeah, we'd need some way to communicate to other people that this object has a higher maximum velocity (or that it doesn't teleport) temporarily. That's for you guys to decide -- I don't want to add anything to the metaobject specs just yet :) Maybe I will add a disable-teleport option to csplugin however. -Ken ___ vos-d mailing list vos-d@interreality.org http://www.interreality.org/cgi-bin/mailman/listinfo/vos-d
Re: [vos-d] Movement interpolation update
Peter Amstutz wrote: > VOS s3 used extrapolation, sending position, velocity and acceleration > and seemed to work pretty well, but we never really tested it in cases > with a lot of rapidly changing motion. I feel like you should be able > to get good results from an extrapolation approach using control theory > and filters (to smooth out network lag and jitter) but there's still the > common edge case where someone stops, the system over-compensates for > their motion and then "snaps back" like a rubber band. I see how > interpolation is a simpler solution to the problem. In the back of my mind, I've been using a sort of "rule-of-thumb" that goes "if it's more complicated than what a modern FPS game does, perhaps we shouldn't do it that way." Obviously, things that are specific to vos's object structure and message passing are excepted, but for things like interpolation, prediction, physics, etc -- why re-invent the wheel? An example of this I noticed is in the commented-out physics code. It looks like you were trying to control avatar turns with torques -- most people don't bother with that! They model their player physics as cylindrically-symetrical shapes so that turning has to physical meaning, then they just move the mesh orientation directly with no physics interaction. Likewise, for keeping players upright, most just force the rigid body to be upright every frame rather than trying to apply physical forces. Others, who want a realistic "wobbling" (like for hover-car games or something) use a spring constraint to keep things upright. Setting velocity usually uses a spring constraint, too. I haven't looked to closely at ODE, but it might have a more powerful constraint system, and you might be able to do things with it rather than manually. > You're right, VOS is not clocked, due in part to the current > multithreading design that encourages asynchronous "anytime" execution > of tasks. This is something we may need to revisit in the s5 design, > actually, and I'd be interested to hear your thoughts about it. Actually, if the VIP already spaces out updates (as you say below), then that basically accomplishes the same thing as why games do it -- so smooth movements don't flood the network with updates. A precise timestamp server-side is something you might want to help assist in client-side prediction if the physics of the avatar are controlled server-side; but this is something that could be done at the message level rather than at VIP (add a new "timestamp" field to position update messages, for instance). > I > should note that the VIP low latency protocol used for sending out > position updates does use a 100ms clock. Also you might want to compare > your ICMP ping times with your VOS ping times just to get an idea of how > much of the variance in latency is inherent in your connection to > interreality.org. I get a consistent <100ms... when packets aren't dropped :) So dropped packets may account for what I was seeing. Or lag on my side in sending updates to the server (I was running two debug terangreals simultaneously, which gets a little bogged down.) > This sounds terrific! I have to talk to Reed, but since you've shown > some dedication (and a willingness to wade through the CS plugin code, > which is pretty much trial by fire) I will probably go ahead and set you > up to be able to commit to the main branch on interreality.org -- I > don't know when Reed and I have the time to merge your changes ourselves > right now, but it would be a terrible shame to let this good work linger > in the queue. > That would be excellent! But I'm surprised you'd trust me without seeing my code first :) Actually, if I can make a revision bundle without line-ending problems this time (and I looked at my previous revision-bundle -- I think it was my fault), then all you need to do is a "bzr merge kens-revision-bundle" or "bzr pull kens-revision-bundle" rather than patching everything by hand. So it shouldn't take too much time, and you can check right there whether I break your build or not :P -Ken ___ vos-d mailing list vos-d@interreality.org http://www.interreality.org/cgi-bin/mailman/listinfo/vos-d
Re: [vos-d] Movement interpolation update
Funny... the problems you mention actually result from a lack of semantics! Consider the case of a specialized VR application like a game: You already know all possible actions a user can take, and your protocol usually transmits them directly. E.g. if a user wants to jump, the client sends a "jump" PDU, if he wants to teleport, you get a "teleport" PDU, and for regular continous movement a "movement" PDU. In contrast, "generic" VR platforms usually center around a common data model; the protocol covers synchronization of this data model among participants. The advantage is that you can have arbitrary user actions, as long as you can express them in terms of model changes (which are transmitted in corresponding PDUs). The disadvantage is that you loose application semantics in this process; the receiver only sees (possibly unrelated) changes in the data model, and has to infer the originator's action/intention from the changes. In the way Ter'angreal currently handles movement updates, this problem is also evident, since we don't really have a "movement" PDU in VOS, only "property change" PDUs. If a client moves his avatar, Ter'angreal changes the position and orientation child properties of the avatar, which results in two *different* update messages. A receiver has no way of knowing that these two updates are related, i.e. whether the avatar moved a bit and then turned, turned and then moved, or did both at the *same time*. Luckily this semantic problem is of no consequence to a human user, as the resulting differences in the visual presentation are too small to percieve. Teleporting or jumping are worse, since the resulting property changes are indistinguishable from those caused by regular continuous movement. You cannot really fix this with a "don't-interpolate" flag, as there is no good place to put one. You could extend the property- update notification, but a lot of properties do not use interpolation (hmm interpolate a nickname change? cool :-) My hope is that this problem might get smoothed over a bit in S5. I assume that both position and orientation will likely be embedded children of an avatar vobject. If you change both, you need to acquire the lock of the parent, change the values, and release the lock (ok, VOS will do this for you transparently). In this case, VOS should defer the update notifications until the parent lock gets released, and the send them all in an atomic "compund update" (message block?) which is semantically slightly closer to the actual user action. I am not quite sure how you could squeeze a "don't-interpolate" flag into the mix though - unless it is an actual embedded child of the avatar vobject, which is somewhat messy. The only *real* solution, both in S4 and S5, would be what the games do: Send a custom "movement" message... and loose the genericity of the VOS platform. Regards, Karsten Otto (kao) ___ vos-d mailing list vos-d@interreality.org http://www.interreality.org/cgi-bin/mailman/listinfo/vos-d
Re: [vos-d] Movement interpolation update
Thanks for working on this, Ken, it will really make things smoother and more usable! Peter Amstutz wrote: > clear line between "developers" and "users", it is better to keep > everyone on the same list so that everyone sees all of the discussion. Yes, we don't have enough people to split, that would kill discussion, and we also want "users" to give their input on "development" decisions (and as we develop different scripting possabilities then "users" can become "developers" :) >> Another thing to worry about is teleportation -- not as common in VOS as in >> FPS games (you teleport when you die), but it happens. > The "maximum velocity" approach makes sense. > Terangreal (internally) should have the option of interpolating a "teleport", maybe. Then if we add a way to click on an object and zoom up to it, or if you want to do an interpolation for zooming to some bookmark or viewpoint, you could use it. Maybe add a "don't interpolate" flag to a position update call? Reed ___ vos-d mailing list vos-d@interreality.org http://www.interreality.org/cgi-bin/mailman/listinfo/vos-d
Re: [vos-d] Movement interpolation update
On Wed, May 02, 2007 at 08:28:49AM -0700, Ken Taylor wrote: > First of all, a question: Would it make any sense to start a "VOS > Development" mailing list separate from this discussion one? I hate clogging > the list with all my posts about build problems and such, but also don't > feel good about just sending it directly to the main developers -- there may > be other people out there looking at the code who would be interested. Vos-d *is* the development list. If people don't want to see the daily grind of software development that is discussion like this, they should join the announce list. Presently there isn't enough traffic to justify splitting vos-d up, and also it's my experience that unless there is a clear line between "developers" and "users", it is better to keep everyone on the same list so that everyone sees all of the discussion. > send velocity vectors along with position, or discern velocity from previous > updates, and keep moving the objects out along their current path. However, > while this works when everyone's going pretty straight, it can lead to > distracting artifacts when there's lots of starting and stopping or changing > direction.) Since there's already network lag, lagging a little bit more is > an acceptable tradeoff for much smoother looking motion. VOS s3 used extrapolation, sending position, velocity and acceleration and seemed to work pretty well, but we never really tested it in cases with a lot of rapidly changing motion. I feel like you should be able to get good results from an extrapolation approach using control theory and filters (to smooth out network lag and jitter) but there's still the common edge case where someone stops, the system over-compensates for their motion and then "snaps back" like a rubber band. I see how interpolation is a simpler solution to the problem. > There's one big difference between the network activity of games like > Half-Life 2 and of VOS: Online games usually use a known, fixed update > heartbeat, and differences in packet arrival times are generally due to > network jitter, server lag, or dropped packets. As far as I could tell, VOS > has no such update clock, and my measurements of movement arrival intervals > varied between 30ms and 240ms for just walking an avatar across the screen > on the interreality world server. Usually the history buffer size is around > 2x the update period, but 500ms of lag would have been a bit much. So I > chose a default buffer size of 250ms for now (Half-Life 2 uses 100ms) -- but You're right, VOS is not clocked, due in part to the current multithreading design that encourages asynchronous "anytime" execution of tasks. This is something we may need to revisit in the s5 design, actually, and I'd be interested to hear your thoughts about it. I should note that the VIP low latency protocol used for sending out position updates does use a 100ms clock. Also you might want to compare your ICMP ping times with your VOS ping times just to get an idea of how much of the variance in latency is inherent in your connection to interreality.org. > that can be changed by the application (and in the future, perhaps an > adaptive buffer size would be doable -- not sure if it's worth the effort, > though). The variable update period doesn't affect the algorithm greatly, > but a few things are affected -- for instance, when an object starts moving > from standing still, I don't know whether that update represents 30ms of > movement or 240ms. I assume worst case for now and interpolate starting > movements over the full 250ms, which looks fine in most cases, but also > leads to a weird "slow-start" effect in others (such as jumping). I may tune > this parameter a bit before submitting my changes. Something that isn't exposed currently, but probably should be, is the current round trip time reported by the VIP layer. This gives you a smoothed value for the round trip time for the last N packets and is used by VIP to determine retransmits, estimate network congestion, etc. Having that data on hand would probably help make the interpolation smarter. > Another thing to worry about is teleportation -- not as common in VOS as in > FPS games (you teleport when you die), but it happens. You can always "Warp > to starting point" in Ter'Angreal, for instance. But visually you'd want the > teleport to look like a teleport, not like the object is zooming across the > sector really fast. The way I'm addressing this is having a "maximum > velocity" specified. Any object travelling faster than this between two > points is assumed to be teleporting, and is "snapped" to its position. There > is a default maximum velocity, and it can also be set per-object. In the > future, other ways to explicitly specify a teleport event might be possible. The "maximum velocity" approach makes sense. > [details snipped] > > And that's about it. I still have some things to work on (I haven't actually > done the
[vos-d] Movement interpolation update
First of all, a question: Would it make any sense to start a "VOS Development" mailing list separate from this discussion one? I hate clogging the list with all my posts about build problems and such, but also don't feel good about just sending it directly to the main developers -- there may be other people out there looking at the code who would be interested. Secondly, my movement interpolation modifications are going pretty well. My local branch is now at the point where it officially "works" and correctly interpolates the movement and rotation for any vobject that moves (including other avatars and things like the doors in Peter's demo world) -- but there's still some things that need to be cleaned up and fleshed out, so it's not quite ready to be revision-bundled and submitted yet. However, I thought it would be good to send an email summarizing the basic design I'm using, for comments/suggestions. So here goes: The algorithm itself is a familiar one from any modern online game: to interpolate, you must add some visible lag -- enough so you can get at least two network updates before having to display the movement from the first one -- and keep a history buffer of movement updates for all moving objects. Then you can interpolate between the updates in the history buffer. (There's another method known as extrapolation, where you add no lag, and you either send velocity vectors along with position, or discern velocity from previous updates, and keep moving the objects out along their current path. However, while this works when everyone's going pretty straight, it can lead to distracting artifacts when there's lots of starting and stopping or changing direction.) Since there's already network lag, lagging a little bit more is an acceptable tradeoff for much smoother looking motion. There's one big difference between the network activity of games like Half-Life 2 and of VOS: Online games usually use a known, fixed update heartbeat, and differences in packet arrival times are generally due to network jitter, server lag, or dropped packets. As far as I could tell, VOS has no such update clock, and my measurements of movement arrival intervals varied between 30ms and 240ms for just walking an avatar across the screen on the interreality world server. Usually the history buffer size is around 2x the update period, but 500ms of lag would have been a bit much. So I chose a default buffer size of 250ms for now (Half-Life 2 uses 100ms) -- but that can be changed by the application (and in the future, perhaps an adaptive buffer size would be doable -- not sure if it's worth the effort, though). The variable update period doesn't affect the algorithm greatly, but a few things are affected -- for instance, when an object starts moving from standing still, I don't know whether that update represents 30ms of movement or 240ms. I assume worst case for now and interpolate starting movements over the full 250ms, which looks fine in most cases, but also leads to a weird "slow-start" effect in others (such as jumping). I may tune this parameter a bit before submitting my changes. Another thing to worry about is teleportation -- not as common in VOS as in FPS games (you teleport when you die), but it happens. You can always "Warp to starting point" in Ter'Angreal, for instance. But visually you'd want the teleport to look like a teleport, not like the object is zooming across the sector really fast. The way I'm addressing this is having a "maximum velocity" specified. Any object travelling faster than this between two points is assumed to be teleporting, and is "snapped" to its position. There is a default maximum velocity, and it can also be set per-object. In the future, other ways to explicitly specify a teleport event might be possible. I should also mention that interpolation can be enabled or disabled globally, and I've added a menu item to my local Ter'Angreal to do this (mostly so I can do a before/after comparison, but some people may want to disable interpolation for some reason). It can also be disabled per-object -- for example, you don't want to do interpolation on your own avatar. OK. For the actual code design, I've created a new class, HistoryBufferEntry, and two inheritors of that class, PositionBufferEntry and OrientationBufferEntry. The parent class keeps the timestamp for the entry and has utility functions relating to time. The children classes keep a csVector3 and a csQuaternion respectively, along with functions to interpolate between two entries. csMetaObject3D gets a couple deques holding vRefs to HistoryBufferEntries -- one for positions and one for orientations. If interpolation is enabled, instead of snapping right to a new position as soon as a property update is received, it pushes it on to the deque (i use deque instead of queue for the at() function -- I need access to both the element on the front and the one right behind it to interpolate between them). Instead of calculating inter