Pass the 2.5D grid

Question

I am trying to figure out how to efficiently bypass a 2.5D grid. The grid itself is 2D, but each cell in the grid has a floating minimum / maximum height. The line for moving is determined by two three-dimensional coordinates with a floating point. I want to stop crossing the line if the range of z values ​​between the input / output of the grid cell does not overlap with the minimum / maximum height for this cell.

I am currently using the 2D DDA algorithm to traverse grid cells in order (see the figure), but I'm not sure how to calculate the z value when each grid cell is reached. If I could do this, I could check the z value when entering / exiting the cell against the minimum / maximum height for the cell.

Is there a way to change this algorithm, which allows you to calculate z when you enter each grid cell? Or is there a better workaround algorithm that would allow me to do this?

Here is the current code I'm using:

void Grid::TraceGrid(Point3<float>& const start, Point3<float>& const end, GridCallback callback ) { // calculate and normalize the 2D direction vector Point2<float> direction=end-start; float length=direction.getLength( ); direction/=length; // calculate delta using the grid resolution Point2<float> delta(m_gridresolution/fabs(direction.x), m_gridresolution/fabs(direction.y)); // calculate the starting/ending points in the grid Point2<int> startGrid((int)(start.x/m_gridresolution), (int)(start.y/m_gridresolution)); Point2<int> endGrid((int)(end.x/m_gridresolution), (int)(end.y/m_gridresolution)); Point2<int> currentGrid=startGrid; // calculate the direction step in the grid based on the direction vector Point2<int> step(direction.x>=0?1:-1, direction.y>=0?1:-1); // calculate the distance to the next grid cell from the start Point2<float> currentDistance(((step.x>0?start.x:start.x+1)*m_gridresolution-start.x)/direction.x, ((step.y>0?start.y:start.y+1)*m_gridresolution-start.y)/direction.y); while(true) { // pass currentGrid to the callback float z = 0.0f; // need to calculate z value somehow bool bstop=callback(currentGrid, z); // check if the callback wants to stop or the end grid cell was reached if(bstop||currentGrid==endGrid) break; // traverse to the next grid cell if(currentDistance.x<currentDistance.y) { currentDistance.x+=delta.x; currentGrid.x+=step.x; } else { currentDistance.y+=delta.y; currentGrid.y+=step.y; } } } 

Answer 1

I came up with a good way to do this. Add to the beginning of the function:

 float fzoffset=end.z-start.z; Point2<float> deltaZ(fzoffset/fabs(end.x-start.x), fzoffset/fabs(end.y-start.y)); Point2<float> currentOffset((step.x>0?start.x:start.x+1)*m_gridresolution-start.x, (step.y>0?start.y:start.y+1)*m_gridresolution-start.y); 

Inside the loop, where currentDistance.x / .y increases, add:

 currentOffset.x+=m_gridresolution; //When stepping in the x axis currentOffset.y+=m_gridresolution; //When stepping in the y axis 

Then, to calculate z at each step:

 z=currentOffset.x*deltaZ.x+start.z; //When stepping in the x axis z=currentOffset.y*deltaZ.y+start.z; //When stepping in the y axis 

Answer 2

It seems that the 3D extension of the Bresenham line algorithm will work. You have to iterate over X and independently track the error for the Y and Z components of your line segment to determine the Y and Z values ​​for each corresponding X value. You simply stop when the accumulated error in Z reaches some critical level, which indicates that it is beyond beyond your minimum / maximum.

Answer 3

For each cell, you know which cell you came from. This means that you know which side you came from. The calculation of z at the intersection of the green line and the given grid line seems trivial.