Mouse acceleration patch

Simon Thum simon.thum at mni.fh-giessen.de
Tue Oct 3 05:12:37 PDT 2006


Hello List!

I'm a computer sciences student and I have done a patch to fix some 
problems in X pointer acceleration code, on the way providing a better 
mouse 'feeling' for the user.

Patch and detailed Documentation are attached.

The issue was quite much discussed, but AFAIK this is the first proposal 
to cover most of the associated issues. I am actually using the code and 
I'm very pleased with it. However, some points are left which require 
some more experience with x.org than I could easily acuire.

Thus, I'm seeking a developer who helps me remedy the TODOs and
FIXMEs before possible integration.

Thanks in advance,

Simon Thum
-------------- next part --------------

X.org mouse acceleration proposal

Author: Simon Thum (simon [dot] thum [at] gmx de)
Date: 09/2006


Intent

 - provide a better 'feel' for the X pointing device
 - fix current problems, especially with polynomial acceleration



Postulate
or
How to provide a better mouse feeling for the user?

It is presumed that the most critical part is doing a sophisticated guess on
the velocity of the device in a user's hand, as this is the reference the
user's brain has to build its own knowledge about the applied translation from
mouse to screen. Because this is an intuitive process, easing it just 'feels
better'.

Velocity is a physical quantity usually measured in m/s. This is what is
accessible to our nerves and brains, preparing the ground for intuitve access.
Acceleration therefore needs to depend on velocity, and here we try to deduct
that quantity from the measurements the device provides us with.

It follows that any introduced lag should be small enough not to be noted, and
any behind-the-scenes data should not counter intuitive mechanisms.



Current problems adressed

1) Current acceleration code devises velocity (and thus acceleration) directly
from device data at any given instant. This makes it very vunerable to
precision problems, such as a 'jumpy' mouse.

2) If a system is under load, a device may accumulate its movement delta 
over some time, causing irrational high cursor movement in case of polynomial
acceleration (threshold = 0, acc > 1) because velocity is guessed in an
oversimplified fashion.

3) Some people have overly responsive devices, creating a need to reduce speed
on precise tasks or in general. Current implementation will discard precision
if pushed there (threshold = 1, acc < 1).

These problems result in a reduced ability for our intuition to predict a
correct hand movement for desired screen movement, causing more correctional
moves than neccessary. Or put simply, the mouse 'feels bad'.



Method

First, a better guess on velocity is done.
Given available data, we calc dots per millisecond. This is quite intractable
in integers, so we multiply by a configurable factor to arrive at values the
usual X controls, treshold and acceleration, can be used for with some sense.

This velocity is then weighted with an exponentially dropping curve, i.e. the
longer a movement signal is back in time, the less influence it has on the
current guess.

After some short inactivity time, such background data is reset (called
non-visible state (reset) in the patch).

Second,the applied acceleration is made steady (over velocity) to enhance
intuitivity furter.

Third, reported values are slightly flattened (just below mouse precision)
ONLY if acceleration is actually performed to improve constant-speed movements
as painting w/mouse typically requires. This can be independently turned off
(Softening).

Fourth, for too responsive devices, two methods are available (together if
desired):
1) a constant deceleration can be applied
2) acceleration curve can be allowed to decelerate on slow movements
   (adaptive deceleration)



Benefits

Mostly, the polynomial acceleration becomes more usable. It can be used with
higher acceleration coefficients (x > 2), still providing enough control. But
also the classic acceleration should become less jumpy since it now graduates
(rather) soft towards accelerated motion.

Users with too precise devices can slow them without loosing precision,
independent of driver support. Even more important, polynomial acceleration
can now decelerate on slow movements, giving (sub)pixel precision without
sacrificing on pointer speed.

The code is more robust towards different devices: One could imagine a mouse
reporting very often, but only 1 dot per event. Old code would not accelerate 
such a device at all. While this is a theoretical case, there is more
robustness against jitter in device event frequency.

By introducing a coefficient in xorg.conf you can make two attached devices
feel similar, as is often the case on laptops. (untested)

Users disliking all this can switch it off, retaining constant deceleration
if desired.



Problems / Todo

I am not an experienced X dev, so some points are left.

More complex algorithms have more knobs, and currently they can only be set in
the server config. If you have suitable values however, change should only be
needed when the device changes. Better would be access via xset and/or API.
However, even removing the PerCent in VelocityScalePerCent would be an
improvement [by reading a float from cfg]. Or to make the code cease reding
those options into keyboards.

If adaptive deceleration is used, the first motion event after some time will
lead to (probalby) underestimated velocity, making it subject to maximum
slowdown, so it might appear to be skipped.

Some mice could push the limit and report so often that milliseconds don't
provide reliable timing; in that case, some precision is lost.

A mouse velocity monitor would be nice-to-have for tweaking. Any tracing in X?

The simple acceleration curve (threshold > 0) is now steady, but a function
steady also over its derivative(s) would be preferred. Also, it does not
support adaptive deceleration since it won't go below 1.


Configuration

The defaults should suffice if you had no big problems before, and feel quite
similar. Setting treshold to 0 is strongly recommended, to use the more
intuitive polynomial acceleration. Acceleration should be about 1.5 to 2.5
then.


A few tips

If you have a feeling your mouse moves far too fast, ConstantDeceleration is
your friend. Set to 2 or higher to divide speed accordingly. This will not
discard precision (at least only on nv-reset, see Method or below).

If you like the speed but need some more control at pixel-level, you should
set AdaptiveDeceleration to 2 or more. This allows to decelerate slow
movements down to the given factor. You might want to keep nv-resets away by
setting VelocityReset to e.g. 500 ms, and maybe tweak VelocityScalePerCent to
give good results. [Note this only works with polynomial acceleration]

If you are picky about a smooth kick-in of acceleration, for example to ease
doing art, I suggest tweaking VelocityScalePerCent so acceleration is done
before the device starts reporting axis deltas above 1 (which is the point the
old code starts accelerating). A good value for VelocityScalePerCent should
IMHO be around 200 to 2000, 1000 being default (x10). Unfortunately, there is
no live-monitor program for tweaking.


Settings

VelocityScalePerCent [integer]

In short, this controls sensitivity of acceleration.

It is designed to be device-dependent, i.e. you set it once to match your
device, and modify behaviour using the classical controls.
This factor is given in Percent, so multiply by 100.

Rationale: Device deltas are being divided by milliseconds before being
weighted, so they are about 10 times too small compared to a device reporting
every 10 ms. Because the reporting rate is usually unknown in advance, this is
the only way to scale up to 'normal' values.

Default is 1000, or 10x, which is suitable for devices reporting at 100hz
maximum. If your mouse reports x times per second, set to (1000/x)*100.

WeightingDecay [integer]

Default 25 milliseconds. Tweaks the weighting applied to approximate velocity.
Higher values exhibit more integrating behaviour, introducing some lag but
also may feel smoother. Lesser is more responsive, but less smooth.

VelocityReset [integer]

Specifiers after how much milliseconds of inactivity non-visible state (i.e.
background info not reflected by pointer position) is discarded.
Default 150 ms.

AdaptiveDeceleration [integer]

Allows polynomial acceleration funtion (threshold = 0) to actually decelerate
the pointer, giving enhanced precision on slow moves. Default is 1, which
deactivates adaptive deceleration. 2 or higher allow respective deceleration.

Adaptive deceleration should not affect your normal mouse useage; if it does,
VelocityScalePerCent is probably too low.

ConstantDeceleration [integer]

Constantly decelerates the mouse by given factor. Default is 1 (no
deceleration). Is applied after velocity guessing, so you don't need to adjust
VelocityScalePerCent when changing this setting.

Softening [boolean]

Tweaks motion deltas from device before applying acceleration a bit to
smooth rather constant moves. Tweaking is always below device precision to
make sure it doesn't get in the way. Also, when ConstantDeceleration is used,
Softening is not enabled by default because this already provides some
subpixel precision.
However you can set this "off" or "false" if you don't like it.

VelocityGuessing [boolean]

Settin this to "off" retains the simpler, old-fashioned algorithm for
determining velocity. It doesn't behave exactly alike but 



Reference

http://lists.freedesktop.org/archives/xorg/2005-September/010211.html
https://bugs.freedesktop.org/show_bug.cgi?id=138
https://bugs.freedesktop.org/show_bug.cgi?id=2927
-------------- next part --------------
diff -Bbu hw/xfree86/common_old/xf86Xinput.c hw/xfree86/common/xf86Xinput.c
--- hw/xfree86/common_old/xf86Xinput.c	2005-10-21 19:06:13.000000000 +0000
+++ hw/xfree86/common/xf86Xinput.c	2006-10-03 11:09:34.000000000 +0000
@@ -119,6 +119,144 @@
  *****************************************************************************/
 #define ENQUEUE(e) xf86eqEnqueue((e))
 
+
+
+
+/******************************************************************************
+ * Mouse softening fns
+ *
+ * Serves 3 complementary functions: 
+ * 1) provide a sphisticated ballistic velocity guess to give better acceleration
+ * 2) slightly soften out mouse data when acceleration is applied
+ * 3) decelerate if enabled
+ *****************************************************************************/
+
+static void 
+InitVelocityData(MouseVelocityPtr s, float rdecay)
+{
+    s->lrm_time = 0;
+    s->velocity  = 0;
+    s->corr_mul = 10.0;           //dots per 10 milisecond is a usable form
+    s->const_acceleration = 1.0;   //no acceleration/deceleration
+    s->rdecay = rdecay;           //TODO: init a lookup for common pow() values here
+    s->reset_time = 0;
+    s->last_dx = 0;
+    s->last_dy = 0;
+    s->use_softening = 1;
+    s->min_acceleration = 1.0;
+}
+
+
+// Perform velocity guessing
+// return true if non-visible state reset is suggested
+static inline short 
+AddVelocityData(MouseVelocityPtr s, int dx, int dy, int time)
+{
+    int diff = time - s->lrm_time;
+    float velocity = (float)sqrt(dx*dx + dy*dy) * s->const_acceleration;    //not a real velocity yet, more a motion delta
+    float weight;
+    short reset = FALSE;
+    
+    s->lrm_time = time;
+
+    if (s->reset_time < 0 || diff < 0) {     //disabled or timer overrun?
+        s->velocity = velocity;   //simply set velocity from current movement, no reset.
+        return 0;
+    }
+    if (diff >= s->reset_time) {  //no movement for some time, suggest to reset nonvisible state
+        s->velocity = 0;
+        reset = TRUE;
+    }
+    
+    if (diff == 0)
+	diff = 1;   //prevent div-by-zero, though it shouldn't happen anyway
+    else if (diff > s->reset_time)
+        diff = s->reset_time;
+    //translate velocity to dots/ms (somewhat untractable in integers, so we multiply by some adjustable factor)
+    velocity /= (float)diff;
+    weight = pow(0.5, ((float)diff) * s->rdecay);   //plot [x=0:10]  0.5**x, (0.5**x)/log(0.5) [its integral] for rationale
+    s->velocity *= weight;    //fade out old velocity info
+    s->velocity += velocity * s->corr_mul * (1.0f - weight);
+
+    return reset;
+}
+
+//this flattens significant values a little bit for more steady constant-velocity response
+static inline float
+ApplySimpleSoftening(int od, int d)
+{
+    float res = d;
+    if (d <= 1 && d >= -1)
+        return res;
+    if (d > od)
+        res -= 0.5;
+    else if (d < od)
+        res += 0.5;
+    return res;
+}
+
+//the name says it all
+static inline void
+ApplySofteningAndDeceleration(MouseVelocityPtr s, int dx, int dy, float* fdx, float* fdy, short do_soften)
+{
+    if (do_soften && s->use_softening) {
+	*fdx = ApplySimpleSoftening(s->last_dx, dx);
+	*fdy = ApplySimpleSoftening(s->last_dy, dy);
+    }
+    else {
+        *fdx = dx;
+        *fdy = dy;
+    }
+    *fdx *= s->const_acceleration;
+    *fdy *= s->const_acceleration;
+}
+
+
+
+//return acceleration for velocity/threshold
+typedef float (*accelerationFunc)(float velocity, float threshold, float max_acc);
+
+//classic X algorithm for threshold > 0, has the disadvantage of discarding all the nice data we have about mouse velocity
+static float
+ClassicAccelerationFunc(float velocity, float threshold, float acc)
+{
+    if (velocity <= threshold)
+        return 1;
+    else
+   	return acc;
+}
+
+//steady function similar to Classic
+static float
+SimpleAccelerationFunc(float velocity, float threshold, float acc)
+{
+    if (velocity <= threshold)
+        return 1;
+    velocity /= threshold;
+    if (velocity >= acc)
+        return acc;
+    else
+        return velocity;
+    
+}
+
+
+//Classic X Polynomial function for threshold = 0, somewhat quirky due to non-unity respone to velocity = 1 (unsteady acceleration)
+static float 
+ClassicPolynomialAccelerationFunc(float velocity, float ignored, float acc)
+{
+   return pow(velocity, (acc - 1.0) * 0.5) * 0.5;
+}
+
+//Polynomial function similar classic one, but with steady response
+static float 
+PolynomialAccelerationFunc(float velocity, float ignored, float acc)
+{
+   return pow(velocity, (acc - 1.0) * 0.5);
+}
+
+
+
 /***********************************************************************
  *
  * xf86AlwaysCoreControl --
@@ -233,6 +371,7 @@
 xf86ProcessCommonOptions(LocalDevicePtr local,
 			 pointer	list)
 {
+    float tempf;
     if (xf86SetBoolOption(list, "AlwaysCore", 0) ||
 	xf86SetBoolOption(list, "SendCoreEvents", 0)) {
 	local->flags |= XI86_ALWAYS_CORE;
@@ -255,8 +394,45 @@
 	xf86Msg(X_CONFIG, "%s: doesn't report drag events\n", local->name);
     }
     
-    local->history_size = xf86SetIntOption(list, "HistorySize", 0);
 
+    //FIXME These should be reachable by API/xset and/or be read only for (relative) pointing devices not keyboards
+    tempf = xf86SetIntOption(list, "WeightingDecay", 25);
+    xf86Msg(X_CONFIG, "%s: Weighting function decay %f ms\n", local->name, tempf);
+    if(tempf > 0)
+        tempf /= 1.0;   //set reciprocal if possible
+    else
+        tempf = 10000;   //else set fairly high
+        
+    InitVelocityData(&(local->velocitydata), tempf);
+    
+    tempf = xf86SetIntOption(list, "ConstantDeceleration", 1);
+    if(tempf > 1){
+        xf86Msg(X_CONFIG, "%s: Constant Deceleration by %f\n", local->name, tempf);    
+        local->velocitydata.const_acceleration = 1.0 / tempf;   //set reciprocal deceleration aka acceleration
+    }
+    
+    tempf = xf86SetIntOption(list, "AdaptiveDeceleration", 1);
+    if(tempf > 1){
+        xf86Msg(X_CONFIG, "%s: Adaptive Deceleration by %f\n", local->name, tempf);    
+        local->velocitydata.min_acceleration = 1.0 / tempf;   //set minimum acceleration    
+    }
+    // Read Softening cfg. if deceleration is used, this is expected to provide enough subpixel information so we enable
+    // Softening by default only if ConstantDeceleration is not used
+    local->velocitydata.use_softening = xf86SetBoolOption(list, "Softening", local->velocitydata.const_acceleration == 1.0);
+
+    local->velocitydata.reset_time = xf86SetIntOption(list, "VelocityReset", 150);
+    
+    local->velocitydata.corr_mul = xf86SetIntOption(list, "VelocityScalePerCent", 1000);  //FIXME reading a float preferred
+    local->velocitydata.corr_mul /= 100.0;
+    
+    if (xf86SetBoolOption(list, "VelocityGuessing", 1) == 0) {
+	local->velocitydata.reset_time = -1;    //Disable
+	local->velocitydata.use_softening = 0;
+	xf86Msg(X_CONFIG, "%s: Disabled velocity guessing\n", local->name);
+    }    
+    
+
+    local->history_size = xf86SetIntOption(list, "HistorySize", 0);
     if (local->history_size > 0) {
 	xf86Msg(X_CONFIG, "%s: has a history of %d motions\n", local->name,
 		local->history_size);
@@ -277,8 +453,8 @@
 {
     LocalDevicePtr        local = (LocalDevicePtr)dev->public.devicePrivate;
 
-    local->dxremaind = 0.0;
-    local->dyremaind = 0.0;
+    local->dxremaind = 0.5f;
+    local->dyremaind = 0.5f;
     
     if (InitIntegerFeedbackClassDeviceStruct(dev, xf86AlwaysCoreControl) == FALSE) {
 	ErrorF("Unable to init integer feedback for always core feature\n");
@@ -875,6 +1053,7 @@
     deviceKeyButtonPointer	*xev  = (deviceKeyButtonPointer*) xE;
     deviceValuator		*xv   = (deviceValuator*) xev+1;
     LocalDevicePtr		local = (LocalDevicePtr) device->public.devicePrivate;
+    MouseVelocityPtr            velocitydata;
     char			*buff = 0;
     Time			current;
     Bool			is_core = xf86IsCorePointer(device);
@@ -885,7 +1064,7 @@
     int				oldaxis[6];
     int				*axisvals;
     int				dx = 0, dy = 0;
-    float			mult;
+    float			acc, apxvelocity, fdx, fdy;
     int				x, y;
     int				loop_start;
     int				i;
@@ -922,6 +1101,7 @@
 	
 	if (loop % 6 == 5 || loop == num_valuators - 1)	{
 	    num = loop % 6 + 1;
+	    velocitydata = &local->velocitydata;
 	    /*
 	     * Adjust first two relative valuators
 	     */
@@ -930,43 +1110,53 @@
 		dx = valuator[0];
 		dy = valuator[1];
 
+		if (AddVelocityData(velocitydata, dx , dy, current)) {   //reset nonvisible state?
+		    local->dxremaind = local->dyremaind = 0.5f;  //do rounding by pre-adding 0.5 once (see below and xf86XinputFinalizeInit)
+		    velocitydata->last_dx = dx;   //prevent softening (somewhat quirky solution, as it depends on the algorithm)
+                    velocitydata->last_dy = dy;
+		}
+
 		/*
 		 * Accelerate
 		 */
-		if (device->ptrfeed && device->ptrfeed->ctrl.num) {
-		    /* modeled from xf86Events.c */
-		    if (device->ptrfeed->ctrl.threshold) {
-			if ((abs(dx) + abs(dy)) >= device->ptrfeed->ctrl.threshold) {
-			    local->dxremaind = ((float)dx * (float)(device->ptrfeed->ctrl.num)) /
-			        (float)(device->ptrfeed->ctrl.den) + local->dxremaind;
-			    valuator[0] = (int)local->dxremaind;
-			    local->dxremaind = local->dxremaind - (float)valuator[0];
+		if ((dx || dy) && device->ptrfeed) {
+                    apxvelocity = velocitydata->velocity;
 			    
-			    local->dyremaind = ((float)dy * (float)(device->ptrfeed->ctrl.num)) /
-			        (float)(device->ptrfeed->ctrl.den) + local->dyremaind;
-			    valuator[1] = (int)local->dyremaind;
-			    local->dyremaind = local->dyremaind - (float)valuator[1];
-			}
-		    }
-		    else if (dx || dy) {
-			mult = pow((float)(dx*dx+dy*dy),
-				   ((float)(device->ptrfeed->ctrl.num) /
-				    (float)(device->ptrfeed->ctrl.den) - 1.0) / 
-				   2.0) / 2.0;
+		    if (device->ptrfeed->ctrl.num) {
+                        // Calc Acceleration for current velocity
+			if (device->ptrfeed->ctrl.threshold) {  //select acceleration style
+			    //use ClassicAccelerationFunc for old-style jumpy behaviour
+			    acc = SimpleAccelerationFunc(apxvelocity, device->ptrfeed->ctrl.threshold,  (float)(device->ptrfeed->ctrl.num) /
+			                                                                              (float)(device->ptrfeed->ctrl.den));
+			}else {
+			    acc = PolynomialAccelerationFunc(apxvelocity, 0, (float)(device->ptrfeed->ctrl.num) / (float)(device->ptrfeed->ctrl.den));	
+			}
+			
+			//do at least this much acceleration (or deceleration)
+			if (acc < velocitydata->min_acceleration)
+                            acc = velocitydata->min_acceleration;
+						
+	
+			if(acc != 1.0 || velocitydata->const_acceleration != 1.0) {
+                            ApplySofteningAndDeceleration(velocitydata, dx, dy, &fdx, &fdy, acc > 1.0);
 			if (dx) {
-			    local->dxremaind = mult * (float)dx + local->dxremaind;
+				local->dxremaind = acc * fdx + local->dxremaind;
 			    valuator[0] = (int)local->dxremaind;
 			    local->dxremaind = local->dxremaind - (float)valuator[0];
 			}
 			if (dy) {
-			    local->dyremaind = mult * (float)dy + local->dyremaind;
+				local->dyremaind = acc * fdy + local->dyremaind;
 			    valuator[1] = (int)local->dyremaind;
 			    local->dyremaind = local->dyremaind - (float)valuator[1];
 			}
 		    }
-		    DBG(6, ErrorF("xf86PostMotionEvent acceleration v0=%d v1=%d\n",
-				  valuator[0], valuator[1]));
+			DBG(6, ErrorF("xf86PostMotionEvent acceleration v0=%d v1=%d vel=%.3f acc=%.2f appliedv=(%.1f, %.1f) devicev=(%d, %d)\n",
+-                                 valuator[0], valuator[1], apxvelocity, acc, fdx, fdy, dx, dy));
+                    }
 		}
+		//remember last motion delta (for softening)
+		velocitydata->last_dx = dx;
+		velocitydata->last_dy = dy;
 		
 		/*
 		 * Map current position back to device space in case
diff -Bbu hw/xfree86/common_old/xf86Xinput.h hw/xfree86/common/xf86Xinput.h
--- hw/xfree86/common_old/xf86Xinput.h	2005-08-24 11:18:32.000000000 +0000
+++ hw/xfree86/common/xf86Xinput.h	2006-10-03 09:44:11.000000000 +0000
@@ -113,6 +113,20 @@
 } InputDriverRec, *InputDriverPtr;
 #endif
 
+
+//Contains all Data needed to implement the mouse ballistics
+typedef struct _MouseVelocityData {
+    int     lrm_time;             //time the last motion event was processed
+    float   velocity;             //velocity as guessed by algo
+    int     last_dx, last_dy;     //last motions delta (for cheap softening algo)
+    float   corr_mul;             //config: multiply this into velocity; can be used to adujust behaviour, about 5 to 25 is sensible
+    float   rdecay;               //config: reciprocal decay ms are between full and half weight (see AddVelocityData)
+    float   const_acceleration;   //config: USED FOR CONSTANT DECELERATION ! but stored reciprocal for fmul is usually faster
+    float   min_acceleration;     //config: minimum acceleration; normally 1, set lower to enable subpixel precision
+    short   reset_time;           //config: reset non-visible state after this number of miliseconds inactivity, -1 means disable velocity guessing
+    short   use_softening;        //config: use softening of actual mouse values (if accelerated)
+} MouseVelocityData, *MouseVelocityPtr;
+
 /* This is to input devices what the ScrnInfoRec is to screens. */
 
 typedef struct _LocalDeviceRec {
@@ -155,6 +169,7 @@
     InputDriverPtr	    drv;
     pointer		    module;
     pointer		    options;
+    MouseVelocityData	    velocitydata;
 } LocalDeviceRec, *LocalDevicePtr, InputInfoRec, *InputInfoPtr;
 
 typedef struct _DeviceAssocRec 


More information about the xorg-mentors mailing list