Hardware Bresenham line setup (can I do sub-pixel correct line drawing?) \ VOGONS

Hardware Bresenham line setup (can I do sub-pixel correct line drawing?)

Topic actions

First post, by riplin

Posted on 2025-06-06, 17:23

riplin Offline

Rank Newbie

Rank: Newbie
Posts: 83
Joined: 2023-05-11, 07:04

Hi folks,

I'm writing some code for the Matrox Mystique just for fun and am now working on the hardware accelerated drawing functions. I've got line, rectangle and trapezoid working. The thing that bothers me though is that the setups for line and trapezoid use regular Bresenham initialization and don't account for sub-pixel shifts of the jaggies. This results in very jittery motion. I was wondering if it's possible to adapt the setup to do sub-pixel correct Bresenham instead. Here's my code for the two functions.

To illustrate: This is what a regular Bresenham line looks like when you step down just one pixel:

A----------_______B

The step over is always in the center. With sub-pixel correct line drawing, the step over point moves along the line and you can end up with variations like this:

A--_____________B

A-----___________B

A---------________B

A-------------_____B

A-------------------_B

In motion, this looks like the line is slowly tilting up on the left, which is a lot better than a sudden jump as in the above case.

Line code:

1// AR0      2b (1)
2// AR1      Error term: 2b - a - sdy
3// AR2      Minor axis increment: 2b - 2a
4// SGN      Vector quadrant (2)
5// XDST     The x start position
6// YDSTLEN  The y start position and vector length      Can use YDST and LEN instead; must use
7//                                                      YDST and LEN when destination address is
8//                                                      linear (i.e.. ylin = 1, see PITCH)
9// (1) Definitions: a = max (|dY|, |dX|), b = min (|dY|, |dX|).
10// (2) Sets major or minor axis and positive or negative direction for x and y.
11
12void PGMDrawLine(Hag::Matrox::Shared::PCI::ControlAperture_t controlAperture, int16_t width, int16_t x0, int16_t y0, int16_t x1, int16_t y1, uint32_t fgcolor)
13{
14    using namespace Hag;
15    using namespace Hag::Matrox::Shared;
16
17    int32_t dX = x1 - x0;
18    int32_t dY = y1 - y0;
19    int32_t absdX = uint32_t(abs(dX));
20    int32_t absdY = uint32_t(abs(dY));
21    int32_t a = max(absdY, absdX);
22    
23    if (a != 0)
24    {
25        int32_t b = min(absdY, absdX);
26        uint32_t sdX = (uint32_t(dX) >> 31) & 1;
27        uint32_t sdY = (uint32_t(dY) >> 31) & 1;
28        uint32_t sdYdX = (uint32_t((absdY - absdX)) >> 31) & 1;
29
30        uint32_t AR0 = uint32_t(b << 1);
31        uint32_t AR2 = uint32_t((b - a) << 1);
32        uint32_t AR1 = uint32_t(((b - (a - sdY)) << 1));    //Error term. Notice the difference to the documentation
33        Sign_t sign = (sdYdX << Sign::Shift::SignDeltaYMinusDeltaX) |
34                    (sdX << Sign::Shift::SignOfDeltaX) |
35                    (sdY << Sign::Shift::SignOfDeltaY);
36
37        XDestination_t xdst = x0;
38        YDestination_t ydst = y0 * (width >> 5);
39        Length_t len = a;
40        DrawingControl_t dwgctl = DrawingControl::LineOpen |
41                                  DrawingControl::AccessReplace |
42                                  DrawingControl::ZAlways |
43                                  DrawingControl::Solid |
44                                  DrawingControl::ShiftZero |
45                                  DrawingControl::BoolSrc |
46                                  DrawingControl::BlitFormattedColor;
47
48        MMIO::Status::WaitDrawingEngineReady(controlAperture);
49        MMIO::ForegroundColor::Write(controlAperture, fgcolor);
50        MMIO::MultiPurposeAddress::Write0(controlAperture, AR0 & MultiPurposeAddress0::Value);
51        MMIO::MultiPurposeAddress::Write1(controlAperture, AR1 & MultiPurposeAddress1::Value);
52        MMIO::MultiPurposeAddress::Write2(controlAperture, AR2 & MultiPurposeAddress2::Value);
53        MMIO::Sign::Write(controlAperture, sign);
54        MMIO::XYAddress::WriteXDestination(controlAperture, xdst);
55        MMIO::XYAddress::WriteYDestination(controlAperture, ydst);
56        MMIO::Length::Write(controlAperture, len);
57        MMIO::DrawingControl::WriteCommit(controlAperture, dwgctl);
58    }
59}

And here's the trapezoid code:

1// AR0      Left edge major axis increment: dYl         yl_end - yl_start
2// AR1      Left edge error term: errl                  (sdxl == XL_NEG) ? dXl + dYl - 1 : - dXl
3// AR2      Left edge minor axis increment: -|dXl|      -|xl_end - xl_start|
4// AR4      Right edge error term: errr                 (sdxr == XR_NEG) ? dXr + dYr - 1 : - dXr
5// AR5      Right edge minor axis increment: -|dXr|     -|xr_end - xr_start|
6// AR6      Right edge major axis increment: dYr        yr_end - yr_start
7// SGN      Vector quadrant
8// FXBNDRY  Filled object x left and right coordinates Can use FXRIGHT and FXLEFT
9// YDSTLEN  The y start position and number of lines Can use YDST and LEN instead;
10//          must use YDST and LEN when destination address is linear
11//          (i.e.. ylin = 1, see PITCH)
12
13void PGMDrawTrapezoid(Hag::Matrox::Shared::PCI::ControlAperture_t controlAperture, int16_t width, int16_t xLt, int16_t xLb, int16_t xRt, int16_t xRb, int16_t yT, int16_t yB, uint32_t fgcolor)
14{
15    using namespace Hag;
16    using namespace Hag::Matrox::Shared;
17
18    int32_t dY = yB - yT;
19    if ((dY > 1) && (((xRt - xLt) > 1) || ((xRb - xLb) > 1)))
20    {
21        int32_t dXL = xLb - xLt;
22        int32_t dXR = xRb - xRt;
23        int32_t absdXL = abs(dXL);
24        int32_t absdXR = abs(dXR);
25        uint32_t sdXL = (uint32_t(dXL) >> 31) & 1;
26        uint32_t sdXR = (uint32_t(dXR) >> 31) & 1;
27
28        uint32_t AR0 = dY;
29        uint32_t AR1 = (sdXL != 0) ? (dXL + dY) - 1 : -dXL;    //Left error term
30        uint32_t AR2 = -absdXL;
31        uint32_t AR4 = (sdXR != 0) ? (dXR + dY) - 1 : -dXR;    //Right error term
32        uint32_t AR5 = -absdXR;
33        uint32_t AR6 = dY;
34        uint32_t sign = (sdXL << Sign::Shift::SignOfDeltaX) |
35                        (sdXR << Sign::Shift::SignOfDeltaXRight);
36        YDestination_t ydst = yT * (width >> 5);
37        DrawingControl_t dwgctl = DrawingControl::Trapezoid |
38                                    DrawingControl::AccessReplace |
39                                    DrawingControl::ZAlways |
40                                    DrawingControl::Solid |
41                                    DrawingControl::ShiftZero |
42                                    DrawingControl::BoolSrc;
43
44        MMIO::Status::WaitDrawingEngineReady(controlAperture);
45        MMIO::Sign::Write(controlAperture, sign);
46        MMIO::XYAddress::WriteLeft(controlAperture, xLt);
47        MMIO::XYAddress::WriteRight(controlAperture, xRt);
48        MMIO::XYAddress::WriteYDestination(controlAperture, ydst);
49        MMIO::MultiPurposeAddress::Write0(controlAperture, AR0 & MultiPurposeAddress0::Value);
50        MMIO::MultiPurposeAddress::Write1(controlAperture, AR1 & MultiPurposeAddress1::Value);
51        MMIO::MultiPurposeAddress::Write2(controlAperture, AR2 & MultiPurposeAddress2::Value);
52        MMIO::MultiPurposeAddress::Write4(controlAperture, AR4 & MultiPurposeAddress4::Value);
53        MMIO::MultiPurposeAddress::Write5(controlAperture, AR5 & MultiPurposeAddress5::Value);
54        MMIO::MultiPurposeAddress::Write6(controlAperture, AR6 & MultiPurposeAddress6::Value);
55        MMIO::Length::Write(controlAperture, dY);
56        MMIO::ForegroundColor::Write(controlAperture, fgcolor);
57        MMIO::DrawingControl::WriteCommit(controlAperture, dwgctl);
58    }
59}

What I'm hoping for is some kind of adaptation of the error term and stepping value to be higher resolution and allow for sub-pixel correct stepping.

One thing I would obviously have to do is upgrade my values to be fixed point instead of straight up integers, but the hard part (if at all possible) is what to feed into the hardware setup to properly handle that.

I know this is super niche, but any help would be greatly appreciated. 😀

Reply 1 of 2, by riplin

Posted on 2025-06-07, 08:38

riplin Offline

Rank Newbie

Rank: Newbie
Posts: 83
Joined: 2023-05-11, 07:04

After doing more research, the documentation of the G400 states that sub-pixel Bresenham needs to be explicitly enabled, so that means the answer to my question above is no. Can't be done with the regular line / trapezoid interpolator. The docs for the Mystique do state that sub-pixel positioning is available, so perhaps this is another case of omitted documentation. Matrox seems to like doing this a lot (the entire texture mapper is omitted from the Mystique datasheet as well). Oh well, more experimenting to do it seems.

Reply 2 of 2, by PainDictator

Posted on 2025-06-11, 19:38

PainDictator Offline

Rank Newbie

Rank: Newbie
Posts: 38
Joined: 2024-11-29, 18:56

riplin wrote on 2025-06-07, 08:38:

After doing more research, the documentation of the G400 states that sub-pixel Bresenham needs to be explicitly enabled, so that means the answer to my question above is no. Can't be done with the regular line / trapezoid interpolator. The docs for the Mystique do state that sub-pixel positioning is available, so perhaps this is another case of omitted documentation. Matrox seems to like doing this a lot (the entire texture mapper is omitted from the Mystique datasheet as well). Oh well, more experimenting to do it seems.

Maybe they consider the Availability of the inital error value as subpixel accuracy. This enables drawing Segments of a line. In fact, it can be used to achieve the effect desribed above. Also, you can alternatively using the Hardware clipping for the same purpose, but with a Performance Hit.

And yes, I implemented line drawing for the matrox cards just a few days ago.

Go to top of page Go to top of page

Back to Video