Huw Davies : gdi32: Add a directional bias for the case when the Bresenham error term is zero.

[Alexandre Julliard]

Module: wine
Branch: master
Commit: a9675b35093aa3226814c37dd8b2c36270056293
URL:    http://source.winehq.org/git/wine.git/?a=commit;h=a9675b35093aa3226814c37dd8b2c36270056293

Author: Huw Davies <huw at codeweavers.com>
Date:   Wed Apr 20 12:52:06 2011 +0100

gdi32: Add a directional bias for the case when the Bresenham error term is zero.

---

 dlls/gdi32/dibdrv/objects.c |   83 +++++++++++++++++++++++++++++++++++++++++-
 dlls/gdi32/tests/dib.c      |   21 +++++++++++
 2 files changed, 102 insertions(+), 2 deletions(-)

diff --git a/dlls/gdi32/dibdrv/objects.c b/dlls/gdi32/dibdrv/objects.c
index c8fb7fe..a2411c3 100644
--- a/dlls/gdi32/dibdrv/objects.c
+++ b/dlls/gdi32/dibdrv/objects.c
@@ -106,7 +106,31 @@ static inline BOOL pt_in_rect( const RECT *rect, const POINT *pt )
             (pt->y >= rect->top) && (pt->y < rect->bottom));
 }
 
-static void WINAPI solid_pen_line_callback(INT x, INT y, LPARAM lparam)
+/**********************************************************************
+ *                  get_octant_number
+ *
+ * Return the octant number starting clockwise from the +ve x-axis.
+ */
+static inline int get_octant_number(int dx, int dy)
+{
+    if(dy > 0)
+        if(dx > 0)
+            return ( dx >  dy) ? 1 : 2;
+        else
+            return (-dx >  dy) ? 4 : 3;
+    else
+        if(dx < 0)
+            return (-dx > -dy) ? 5 : 6;
+        else
+            return ( dx > -dy) ? 8 : 7;
+}
+
+static inline DWORD get_octant_mask(int dx, int dy)
+{
+    return 1 << (get_octant_number(dx, dy) - 1);
+}
+
+static void solid_pen_line_callback(INT x, INT y, LPARAM lparam)
 {
     dibdrv_physdev *pdev = (dibdrv_physdev *)lparam;
     RECT rect;
@@ -119,6 +143,61 @@ static void WINAPI solid_pen_line_callback(INT x, INT y, LPARAM lparam)
     return;
 }
 
+static void bres_line_with_bias(INT x1, INT y1, INT x2, INT y2, void (* callback)(INT,INT,LPARAM), LPARAM lParam)
+{
+    INT xadd = 1, yadd = 1;
+    INT err, erradd;
+    INT cnt;
+    INT dx = x2 - x1;
+    INT dy = y2 - y1;
+    DWORD octant = get_octant_mask(dx, dy);
+    INT bias = 0;
+
+    /* Octants 3, 5, 6 and 8 take a bias */
+    if(octant & 0xb4) bias = 1;
+
+    if (dx < 0)
+    {
+        dx = -dx;
+        xadd = -1;
+    }
+    if (dy < 0)
+    {
+        dy = -dy;
+        yadd = -1;
+    }
+    if (dx > dy)  /* line is "more horizontal" */
+    {
+        err = 2*dy - dx; erradd = 2*dy - 2*dx;
+        for(cnt = 0; cnt < dx; cnt++)
+        {
+            callback(x1, y1, lParam);
+            if (err + bias > 0)
+            {
+                y1 += yadd;
+                err += erradd;
+            }
+            else err += 2*dy;
+            x1 += xadd;
+        }
+    }
+    else   /* line is "more vertical" */
+    {
+        err = 2*dx - dy; erradd = 2*dx - 2*dy;
+        for(cnt = 0; cnt < dy; cnt++)
+        {
+            callback(x1, y1, lParam);
+            if (err + bias > 0)
+            {
+                x1 += xadd;
+                err += erradd;
+            }
+            else err += 2*dx;
+            y1 += yadd;
+        }
+    }
+}
+
 static BOOL solid_pen_line(dibdrv_physdev *pdev, POINT *start, POINT *end)
 {
     const WINEREGION *clip = get_wine_region(pdev->clip);
@@ -188,7 +267,7 @@ static BOOL solid_pen_line(dibdrv_physdev *pdev, POINT *start, POINT *end)
         if(clip->numRects == 1 && pt_in_rect(&clip->extents, start) && pt_in_rect(&clip->extents, end))
             /* FIXME: Optimize by moving Bresenham algorithm to the primitive functions,
                or at least cache adjacent points in the callback */
-            LineDDA(start->x, start->y, end->x, end->y, solid_pen_line_callback, (LPARAM)pdev);
+            bres_line_with_bias(start->x, start->y, end->x, end->y, solid_pen_line_callback, (LPARAM)pdev);
         else if(clip->numRects >= 1)
             ret = FALSE;
     }
diff --git a/dlls/gdi32/tests/dib.c b/dlls/gdi32/tests/dib.c
index 784d8d5..3046799 100644
--- a/dlls/gdi32/tests/dib.c
+++ b/dlls/gdi32/tests/dib.c
@@ -78,6 +78,7 @@ static const char *sha1_graphics_a8r8g8b8[] =
     "a3cadd34d95d3d5cc23344f69aab1c2e55935fcf",
     "2426172d9e8fec27d9228088f382ef3c93717da9",
     "9e8f27ca952cdba01dbf25d07c34e86a7820c012",
+    "664fac17803859a4015c6ae29e5538e314d5c827",
     "17b2c177bdce5e94433574a928bda5c94a8cdfa5",
     "fe6cc678fb13a3ead67839481bf22348adc69f52",
     "d51bd330cec510cdccf5394328bd8e5411901e9e",
@@ -150,6 +151,18 @@ static void compare_hash(BITMAPINFO *bmi, BYTE *bits, const char ***sha1, const
     HeapFree(GetProcessHeap(), 0, hash);
 }
 
+static const RECT bias_check[] =
+{
+    {100, 100, 200, 150},
+    {100, 100, 150, 200},
+    {100, 100,  50, 200},
+    {100, 100,   0, 150},
+    {100, 100,   0,  50},
+    {100, 100,  50,   0},
+    {100, 100, 150,   0},
+    {100, 100, 200,  50}
+};
+
 static const RECT hline_clips[] =
 {
     {120, 120, 140, 120}, /* unclipped */
@@ -251,6 +264,14 @@ static void draw_graphics(HDC hdc, BITMAPINFO *bmi, BYTE *bits, const char ***sh
     compare_hash(bmi, bits, sha1, "diagonal solid lines");
     memset(bits, 0xcc, dib_size);
 
+    for(i = 0; i < sizeof(bias_check) / sizeof(bias_check[0]); i++)
+    {
+        MoveToEx(hdc, bias_check[i].left, bias_check[i].top, NULL);
+        LineTo(hdc, bias_check[i].right, bias_check[i].bottom);
+    }
+    compare_hash(bmi, bits, sha1, "more diagonal solid lines");
+    memset(bits, 0xcc, dib_size);
+
     /* solid brush PatBlt */
     solid_brush = CreateSolidBrush(RGB(0x33, 0xaa, 0xff));
     orig_brush = SelectObject(hdc, solid_brush);