Scaling down block drawing without one block fighting to be two things

The code I lost in a hard drive failure however over a year later it still bugs me about it and I really want an answer so I can sleep at night without this popping into my head. So I was writing a defragmentation software and it displayed the clusters. The problem with the drawing code is floating point math. I'm not experienced enough to solve this math problem. I could draw the clusters no problem however due to floating point math the last pixel were fighting with the first pixel of a new cluster when I scaled it down to fit a window. I can't figure out how to prevent this. I tried rounding down and up but that left a pixel either empty or overwriting a pixel f the last cluster when it shouldn't be, etc. It should look like this. Can't figure out how this JkDefrag (open source) did it and I have the source code for it! This is what keeps me up at night. Please help me get a good nights sleep.

enter image description here

Drawing code from a backup:

void DrawTESTClusters( HWND hWnd, const CMemoryDC &memoryDC, LONGLONG ClusterStart, LONGLONG ClusterCount, int color )
{
    LONG Width;
    LONG Height;
    LONGLONG x1;
    LONGLONG y1;
    //LONGLONG x2;
    //LONGLONG y2;
    HDC hDC;
    LONG MaxLength;

    //DebugPrint(_T("%I64d - %I64d, %I64d\n"), ClusterStart, ClusterEnd, ClusterEnd - ClusterStart);

    // The usual checks
    if ( TotalClusters <= 0 ) // Can this happen ??
        return;
    //_ASSERT( ClusterStart != ClusterEnd );
    //if ( ClusterStart == ClusterEnd ) // Can this happen ??
    //  return;
    _ASSERT( ClusterStart >= 0 && ClusterStart <= TotalClusters );
    //if ( ClusterStart < 0 || ClusterStart > TotalClusters ) // Can this happen ??
    //  return;
    //_ASSERT( ClusterEnd >= 0 && ClusterEnd <= TotalClusters );
    //if ( ClusterEnd < 0 || ClusterEnd > TotalClusters ) // Can this happen ??
    //  return;
    _ASSERT( ClusterCount >= 0 && (ClusterStart + ClusterCount) <= TotalClusters );

    hDC = memoryDC.GetMemoryDC();
    Width = memoryDC.GetWidth();
    Height = memoryDC.GetHeight();
    MaxLength = memoryDC.GetMaxLength();

    // Calculate some stuff

    float Scale = static_cast<float>(MaxLength) / TotalClusters;
    // TODO: Test this drawing code with scale above 1.0.
    //       The current code should work in theory (to scale up) but if it doesn't the proposed fix-code below, commented:
    //if ( Scale > 1.0 )
    //  Scale = 1.0;
    LONG Length = static_cast<LONG>( ceil( static_cast<float>(ClusterCount) * Scale ) );

    if ( Length <= 0 )
        return;

    //LONG ScaleA = (ClusterStart  * Scale / TotalClusters);
    //LONG ScaleB = (ClusterEnd * Scale / TotalClusters);

    //x1 = (double)(ClusterStart * Scale) / (double)Width;
    //x1 = (double)((double)ClusterStart / (double)Width) * Scale;
    //y1 = (ClusterStart * Scale) % Width;
    //y1 = fmod( (ClusterStart * Scale), Width );
    //y1 = fmod( (double)ClusterStart / (double)Width), Scale );
    //x2 = ScaleB % Width;
    //y2 = ScaleB / Width;
    x1 = static_cast<LONGLONG>( fmod( static_cast<float>(ClusterStart * Scale), static_cast<float>(Width) ) );
    y1 = static_cast<LONGLONG>( static_cast<float>(ClusterStart * Scale) / static_cast<float>(Width) );
    
    // Calculation done, now check if there is any point in drawing it
    //if ( x1 <= 0 && x2 <= 0 )
    //  return;

    // Save original object.
    HGDIOBJ oldPen = SelectObject( hDC, GetStockObject(DC_PEN) );
    // Change the DC pen color
    SetDCPenColor( hDC, ClusterMapColors[ color ] );
    //if ( InUse == 1 )
    //  SetDCPenColor( hDC, RGB(160, 160, 160) ); // 160 == 0xA0
    //else if ( InUse == 0 )
    //  SetDCPenColor( hDC, RGB(0xFF, 0xFF, 0xFF) );
    //  //SetDCPenColor( hDC, RGB(0x00, 0x00, 0x00) );
    //else if ( InUse == 2 )
    //  //SetDCPenColor( hDC, RGB(0x00, 0xFF, 0x00) );
    //  SetDCPenColor( hDC, RGB(0x00, 0x00, 0xFF) ); // Blue
    //else if ( InUse == 3 )
    //  //SetDCPenColor( hDC, RGB(0x00, 160, 0xFF) );
    //  SetDCPenColor( hDC, RGB(0x00, 0xFF, 0x00) ); // Green
    //else if ( InUse == 4 )
    //  //SetDCPenColor( hDC, RGB(0x00, 160, 0xFF) );
    //  SetDCPenColor( hDC, RGB(0xFF, 0x00, 0x00) ); // Red
    //else if ( InUse == 5 ) // Debug
    //  SetDCPenColor( hDC, RGB(0xFF, 0xFF, 0x00) ); // Yellow

    //----------------------------------------------------
    // Only Draw code in here

    LONG step;
    LONG line = static_cast<LONG>( y1 );
    while ( Length > 0 )
    {
        step = Min( Length, static_cast<LONG>(Width - x1) );
        //step = Min( Length, Width );

        if ( MoveToEx( hDC, static_cast<int>(x1), static_cast<int>(line), NULL ) )
            LineTo( hDC, static_cast<int>(step + x1), static_cast<int>(line) );

        Length -= step;
        x1 = 0;
        line++;
    }

#if 0
    Width = clientRect.right;
    Height = clientRect.bottom;

    int Scale = (Width * Height) / TotalClusters;

    //x2 = (ClusterEnd * Scale ) % Width;
    //y2 = (ClusterEnd * Scale ) / Width;

    // Start
    int startX = (ClusterStart * Width * Height / TotalClusters ) % Width;
    int startY = (ClusterStart * Width * Height / TotalClusters ) / Width;

    int endX = ;
    int endY;
    LONG Length = ClusterEnd - ClusterStart;

    while ( Length > 0 )
    {
        LONG len = Min( Length, Width );
        len -= startX;
        
        MoveToEx( hDC, startX, startY, NULL );
        LineTo( hDC, startX + len, endY );

        Length -= len;
        startY++; // Next line
        startX = 0;
    }
#endif

    //----------------------------------------------------

    // Restore original object.
    SelectObject( hDC, oldPen );
}

1 answer

  • answered 2021-01-26 13:10 chux - Reinstate Monica

    ... due to floating point math the last pixel were fighting with the first pixel of a new cluster when I scaled it down to fit a window

    Rather than low precision floating point math, use integer math. Easier to control edge cases exactly.

    Form the scale as a numerator, denominator pair:

    // float Scale = static_cast<float>(MaxLength) / TotalClusters;
    long ScaleNumerator = MaxLength;
    long ScaleDenominator = TotalClusters;
    

    Replace FP with integer code. Use wider integer math when needed. Example:

    // x1 = static_cast<LONGLONG>( fmod( static_cast<float>(ClusterStart * Scale), 
    //     static_cast<float>(Width) ) );
    long long m = 1LL * ClusterStart * ScaleNumerator / ScaleDenominator;
    x1 =  m % Width;
    y1 =  m / Width;
    

    OP's commented code may have suffered with overflow issues. Alternative:

    // int startX = (ClusterStart * Width * Height / TotalClusters ) % Width;
    int startX = (1LL * ClusterStart * Width * Height / TotalClusters ) % Width; 
    

    Should this still result in edge case issues, adjusting integer math code is easier to remedy than FP code.