Direct2D Succinctly®
CHAPTER 13
Hit Testing or Picking
It is often useful in a charting application to determine if the user has clicked the mouse on a node or other object in the chart. This is called hit testing or picking.
Tip: The Direct2D geometries have a method called FillContainsPoint, which returns a BOOL indicating whether the filled geometry contains a specified point. This method is not useful for hit testing a collection of simple primitives, because the geometries are device independent and are very slow at this type of task. Geometries will determine if a point lies within a complex shape fairly quickly, but they are not good at telling which of a large collection of nodes is closest to a given point.
We will examine actual hit testing (determining if a point lies inside a shape) using Direct2D in the Geometries section that follows. This section will concentrate on a more efficient way to select a node with the pointer. The particular mechanism we will create is common in graphing software; it allows the user of the chart a little freedom when they are selecting a node. The pointer doesn't need to be exactly on top of a tiny node, but just close enough. This mechanism makes selecting a single small node from a collection of many much easier for the user.
All we have to do is figure out which node is closest to the pointer, and then whether the pointer is close enough to the node. For example, if the pointer is distant from all nodes, then no nodes should be picked. If we wish to know which node the pointer is closest to, we can very quickly examine all the nodes and calculate the distance to each, determining which is the smallest. We will edit the ScatterPlot class and have it show the user which node is being selected by enlarging the selected node. The ellipses and points that comprise the scatter plot are all device independent resources, so the CPU is in control of them. Open the ScatterPlot.h file and add a public method prototype called PickPoint. This method will take the x and y position position of the cursor as parameters. I have added this prototype at the end of the class.
virtual void CreateDeviceDependentResources(Microsoft::WRL::ComPtr<ID2D1DeviceContext> context) override; virtual void Render(Microsoft::WRL::ComPtr<ID2D1DeviceContext> context) override; // Method to select a node void PickPoint(float x, float y); }; |
Add a private member variable to the same class. This will be used to keep track of the index of the node that is selected.
NodeShape m_NodeShape; // The shape of the nodes
// Selected node index int m_selectedNode; public: |
Initialize the m_selectedNode to -1 in the ScatterPlot constructor.
ScatterPlot::ScatterPlot(float* x, float* y, float nodeSize, D2D1::ColorF nodeColor, NodeShape nodeShape, int count): m_NodeColor(0), GraphVariable(x, y, count), m_selectedNode(-1) { // Save half the node size. The nodes are drawn with // the point they're representing at the middle of the shape. this->m_HalfNodeSize = nodeSize / 2; this->m_NodeShape = nodeShape; this->m_NodeColor = nodeColor; } |
Add the body of the PickPoint method to the end of the ScatterPlot.cpp file.
void ScatterPlot::PickPoint(float x, float y) { float smallestDistance = (x - m_points[0].x) * (x - m_points[0].x) + (y - m_points[0].y) * (y - m_points[0].y); int indexOfSmallest = 0; // Assume closest node is the first one // Run through all nodes and see if any are closer for(int i = 1; i < m_nodeCount; i++) { // Approximate the distance, don't take the sqrt()! float thisDistance = ((x - m_points[i].x) * (x - m_points[i].x) + (y - m_points[i].y) * (y - m_points[i].y)); // If this one's closer, update the index and dist if(thisDistance < smallestDistance) { smallestDistance = thisDistance; indexOfSmallest = i; } } // Calculate the sqrt to get the real Euclidean distance smallestDistance = sqrt(smallestDistance); // If the distance is greater than a threshhold (50.0f), assume // no points are selected at all: if(smallestDistance > 50.0f) m_selectedNode = -1; // Nothing is selected // Otherwise, select the node that's closest to the pointer else m_selectedNode = indexOfSmallest; } |
To work out which node is closest to our pointer, we must calculate the distance (I have used the Euclidean distance) from each of the nodes to the pointer, and decide which node is closest. Initially, I assumed the pointer is closest to the first node. Then I ran through every other node checking the distance to the pointer. If the pointer is closer to a node than our current shortest distance, update the shortest distance and the index of the node. In this way, by the time we reach the final node, we will have the index of the node that is closest to the pointer.
Finally, alter the render method of the ScatterPlot class (in the ScatterPlot.cpp file) such that it renders the selected node a different color and size. I have only included example code for circle nodes, but the idea could be extended to the square shape.
void ScatterPlot::Render( Microsoft::WRL::ComPtr<ID2D1DeviceContext> context) { switch(m_NodeShape) { // Draw as circle nodes case NodeShape::Circle: for(int i = 0; i < m_nodeCount; i++) { context->FillEllipse(D2D1::Ellipse(m_points[i], m_HalfNodeSize, m_HalfNodeSize), m_brush); } if(m_selectedNode != -1) // If a node is selected, render it larger context->FillEllipse( D2D1::Ellipse(m_points[m_selectedNode], m_HalfNodeSize*2.0f, m_HalfNodeSize*2.0f), m_brush); break;
// Draw as square nodes case NodeShape::Square: for(int i = 0; i < m_nodeCount; i++) { context->FillRectangle(D2D1::RectF(m_points[i].x - m_HalfNodeSize, m_points[i].y - m_HalfNodeSize, m_points[i].x + m_HalfNodeSize, m_points[i].y + m_HalfNodeSize), m_brush); } break; // Additional shapes could follow default: break; } } |
We want the PickPoint method to execute when the pointer moves at the moment the GraphRenderer class has a PointerMoved method. However, it is only called when the pointer is depressed, either the mouse button is down or the user is sliding his or her finger.
Add a new public member method to the GraphRenderer class called UpdatePointerPosition. I have placed the prototype after the PointerMoved method in the GraphRenderer.h file.
// Capture the pointer movements so the user can pan the chart void PointerMoved(Windows::Foundation::Point point);
// Record pointers x and t value void UpdatePointerPosition(Windows::Foundation::Point point);
// Method for updating time-dependent objects. void Update(float timeTotal, float timeDelta); |
Add two private member variables to the GraphRenderer class for recording the pointer’s position.
float m_zoomX; // The amount the x-axis is scaled by float m_zoomY; // The amount the y-axis is scaled by float m_pointerX; // X position of pointer in pixels float m_pointerY; // Y position of pointer in pixels Microsoft::WRL::ComPtr<IDWriteTextFormat> m_textFormat; Microsoft::WRL::ComPtr<ID2D1SolidColorBrush> m_blackBrush; |
Add the body of UpdatePointerPosition method to the GraphRenderer.cpp file. I have added it at the end.
void GraphRenderer::UpdatePointerPosition(Windows::Foundation::Point point) { m_pointerX = point.X; m_pointerY = point.Y; } |
And finally, we need to call the m_graphVariable->PickPoint method. We could call this in the UpdatePosition method every time the pointer moves, but PickPoint is a slow method so we should call it less frequently. I have placed the call in the GraphRenderer::Update method inside a new condition, which will cause it to execute once every 32 frames.
void GraphRenderer::Update(float timeTotal, float timeDelta) { static int fpsCounter = -1; // Start at -1 so frame 0 updates timers fpsCounter++; if((fpsCounter & 15) == 0) { // Update every 16 frames // Record the times for display in the render method: m_timeDelta = timeDelta; m_timeTotal = timeTotal; } if((fpsCounter & 31) == 0) { ((ScatterPlot*)m_graphVariable)->PickPoint( (m_pointerX-m_pan.X)/m_zoomX, (-m_pointerY + m_d2dContext->GetSize().height + m_pan.Y)/m_zoomY ); } } |
The member variables m_pointerX and m_pointerY are screen coordinates of the pointer so we have to convert them to the graph’s coordinates when we use them as parameters to the PickPoint method.
Tip: Avoid using sqrt in tight loops. I have removed the sqrt function (used to properly calculate the Euclidean distances between the pointer and the nodes) from the body of my loop in the previoud codesamplee. We do not need to know the actual distance in the middle of this loop. All we need to know is the index of the node that has the shortest distance. I have calculated the actual distance using the square root only once after the loop. Removing the square root from the loop allows it to execute around 100 times faster.
I have included a threshold in the previous code (50.0f). If the cursor is more than 50.0f units from all the nodes we conclude that it is too far and no node is selected, setting the selected node to -1. If the cursor is within 50.0f of one or more nodes, this function will set the index of the nearest node. If the threshold value is equal to the radius of a collection of circular nodes (the m_halfNodeSize member variable in our ScatterPlot class), this method becomes a hit test, and the cursor must be exactly on a node to select it instead of being near.
The next section contains another interesting and flexible method for performing hit tests, this time using geometries. The geometries are capable of real hit testing on a pixel level, not the simple nearest neighbor search I presented previously. The use of geometries is potentially far slower than the manual hit testing we have just examined. The reason is that geometries themselves are complex, device independent structures; they are very flexible but they are also heavy weight.
We have now reached the end of developing our graphing application. The remainder of this book is a discussion of some extra topics and tools which will not be applied to the current application.
- 1800+ high-performance UI components.
- Includes popular controls such as Grid, Chart, Scheduler, and more.
- 24x5 unlimited support by developers.