Decimation Algorithm for Screen Resolution-Based Point Selection

The Problem: More Data Than Pixels

When the density of your data is much higher than the density of your screen's pixels, you end up drawing many data points within the same vertical column of pixels. The user can't distinguish these individual points; they just blend into a solid-looking shape.

The key insight is that we don't need to draw every single point. Instead, for each pixel column on our plot, we can find the minimum and maximum data values that fall within that column and just draw a single vertical line between them. This preserves the "envelope" or "range" of the signal, which is what the human eye perceives anyway.

This paper on fast time-series visualization has an excellent figure illustrating this exact idea.

This is the core of our decimation strategy. Instead of rendering N data points, we'll render W vertical lines, where W is the width of our plot in pixels. This decouples rendering performance from data volume, which is the central goal of our LOD plotter.

The Algorithm: From Pixel Columns to Data Ranges

We now have all the tools we need to implement this. From the previous lesson, we have our screenToWorld transformation. From the lesson before that, we have our MinMaxTree with its efficient getMinMaxInRange query. Now, we just need to connect them.

Our algorithm will be as follows:

1. Get the width of our drawing canvas in pixels (e.g., from ImGui). Let's call it canvas_width.
2. Create an empty list of "draw primitives." A primitive could be a struct like { float screen_x; float min_y; float max_y; }.
3. Loop for each pixel column of the canvas, from px = 0 to px < canvas_width.
4. Inside the loop, for each px, we must determine the range of data indices that falls within this specific pixel column.
   • Calculate the world-space x-coordinate for the start of the pixel column: world_x_start = screenToWorld({canvas_pos.x + px, ...}).
   • Calculate the world-space x-coordinate for the end of the pixel column: world_x_end = screenToWorld({canvas_pos.x + px + 1, ...}).
   • The values world_x_start.x and world_x_end.x give us the floating-point range of data indices for this pixel. Convert them to integer indices, let's call them idx_start and idx_end.
5. Now that we have a data range [idx_start, idx_end] for one pixel column, we query our MinMaxTree: MinMaxResult result = min_max_tree.getMinMaxInRange(idx_start, idx_end);
6. Add a new primitive to our list: { screen_x: canvas_pos.x + px, min_y: result.min, max_y: result.max }. Note that these y values are still in world space; we'll convert them to screen space right before drawing.
7. After the loop finishes, our list of draw primitives contains everything we need to draw the entire plot, but with only one primitive per pixel column.

Let's read a concise description of this exact approach.

From Theory to Code

Let's sketch out what this looks like in C++. We'll assume you have a function that can perform the screenToWorld transformation and a min_max_tree object ready to go.

// A struct to hold the data we need for drawing one vertical bar
struct PlotPrimitive {
    float screen_x;  // The screen x-coordinate for this bar
    float min_val;   // The minimum data value (in world space)
    float max_val;   // The maximum data value (in world space)
};

// --- In your main render function ---

// Get canvas properties from ImGui
ImVec2 canvas_pos = ImGui::GetCursorScreenPos();
ImVec2 canvas_size = ImGui::GetContentRegionAvail();

// Calculate the total visible data range (from previous lesson)
// This gives us world_pos_left and world_pos_right
// ...

// Check if we even need to decimate
float visible_data_span = world_pos_right.x - world_pos_left.x;
if (visible_data_span < canvas_size.x) {
    // If there are fewer data points than pixels, we can draw them directly.
    // We will implement this simple line-drawing logic later.
    // For now, we focus on the decimation case.
} else {
    // DECIMATION LOGIC
    std::vector<PlotPrimitive> primitives;
    primitives.reserve(static_cast<size_t>(canvas_size.x));

    for (int px = 0; px < canvas_size.x; ++px) {
        // Step 4: Find data range for this pixel column
        ImVec2 screen_pos_start = { canvas_pos.x + px, canvas_pos.y };
        ImVec2 screen_pos_end = { canvas_pos.x + px + 1, canvas_pos.y };

        ImVec2 world_pos_start = screenToWorld(screen_pos_start, pan, zoom);
        ImVec2 world_pos_end = screenToWorld(screen_pos_end, pan, zoom);

        // Clamp to ensure we don't go out of bounds of our data array
        size_t data_idx_start = std::max(0, static_cast<int>(floor(world_pos_start.x)));
        size_t data_idx_end = std::min(total_data_points - 1, static_cast<size_t>(ceil(world_pos_end.x)));

        if (data_idx_start > data_idx_end) {
            continue; // This can happen at the edges, just skip.
        }

        // Step 5: Query the MinMaxTree
        MinMaxResult range_data = min_max_tree.getMinMaxInRange(data_idx_start, data_idx_end);

        // Step 6: Store the primitive
        if (range_data.is_valid) { // A flag to check if the query returned actual data
             primitives.push_back({
                .screen_x = canvas_pos.x + px,
                .min_val = range_data.min,
                .max_val = range_data.max
            });
        }
    }

    // Step 7: Now 'primitives' contains our decimated data, ready for drawing!
    // We will cover the actual drawing in the next lesson.
}

This code is the bridge between our interactive controls and our optimized data structure. For every pixel on the screen, we perform a highly efficient logarithmic-time query on our MinMaxTree to find the exact min/max range to draw.

Conclusion

You've now designed the core algorithm for the Level-of-Detail (LOD) plotter. By combining screen-to-world transformations with our MinMaxTree, you've created a system that decouples rendering performance from data size.

Key Takeaways:

• Decimation is the technique of reducing data points to match screen resolution, avoiding wasteful overdraw.
• For time-series plots, the most effective decimation strategy is to find the min/max values for each pixel column.
• The algorithm iterates through each pixel column, uses screenToWorld to find the corresponding data index range, and queries the MinMaxTree for that range.
• This generates a list of draw primitives (e.g., vertical lines) that is proportional to the screen width, not the data size, achieving constant-time rendering complexity.

What's Next?

We have successfully generated an optimized list of what to draw. The final step in this module is to actually draw it!

In our next lesson, we will implement the renderer for our plot. You will learn how to use ImGui's low-level ImDrawList API to take our list of PlotPrimitive structs and render them as a series of vertical lines on the canvas. This will bring the LOD Plotter to life, and you'll be able to see all your hard work pay off in a fast, interactive visualization.