Tracing a contour from hex data?

Graphics and GPU Programming Programming

Started by rubicondev May 19, 2010 05:19 PM

16 comments, last by rubicondev 13 years, 11 months ago

656

May 20, 2010 01:47 AM

Just coming up with this now so I dunno if it will work in all cases.

A tile has six neighbors, let's number them from 0 to 5 in clockwise order where 0 is the one to the left and up.

In pseudo code:

cellIndex = findTopLeftCell();addToPath(cellIndex); // Add this cell to the patholdDirection = 0;firstCellIndex = cellIndex;for (; ; ){  for (i = 1; i < 6; ++ i){    testDirection = (oldDirection + i) % 6;    testCellIndex = getNeighborCellIndex(cellIndex, testDirection);    if (!cellIsEmpty(testCellIndex))      break;  }  if (i == 6){    // We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell.    if (cellIndex == firstCellIndex)      break; // found a complete path of a single cell      testDirection = oldDirection;    testCellIndex = getCellIndex(cellIndex, oldDirection);  }  if (testCellIndex == firstCellIndex)    break; // Found a complete path  cellIndex = testCellIndex; // Update current cell index  oldDirection = (testDirection + 3) % 6; // Swicth direction from "going to" to "coming from"  addToPath(cellIndex);}

The algorithm doesn't need you to first remove the "inner" tiles and handles single cell wide "lines".

Edit:
The algorithm should work equally well on a regular grid, using 4 neighbors instead of 6 for straight contours or 8 if stepping diagonally is allowed.
Edit2:
The find top left step could be replaced by a flood fill from a user selected starting cell. I.e flood fill from the selected cell until you find the top left cell.

szecs

2,990

May 20, 2010 02:37 AM

Pseudo:

Visited_Edge_List[];Hex_List[];edge_index=0;hex_index=0;Visited_Edge_List[0] = Find_a_valid__contour_segment();//referred as "coast" from nowwhile( Visited_Edge_List[0] != Visited_Edge_List[edge_index-1] )//this is                                  //fishy, but you get the idea: loop closed {    Next_Right_side_edge = next_right_from_edge(Visited_Edge_List[edge_index]);    Next_Left_side_edge = next_left_from_edge(Visited_Edge_List[edge_index]);    if( is_coast(Next_Right_side_edge) )    {        Visited_Edge_List[edge_index++] = Next_Right_side_edge;        if( Hex_List[hex_index-1] != Location_of_Green_Hex_by_Edge(Next_Right_side_edge) )        {   Hex_List[hex_index] = Index_of_Green_Hex_by_Edge(Next_Right_side_edge);            hex_index ++;        }        continue;    }    if( is_coast(Next_Left_side_edge) )    {        Visited_Edge_List[edge_index++] = Next_Left_side_edge;        if( Hex_List[hex_index-1] != Location_of_Green_Hex_by_Edge(Next_Left_side_edge) )        {   Hex_List[hex_index] = Index_of_Green_Hex_by_Edge(Next_Left_side_edge);            hex_index ++;        }        continue;    }}for( i = 1; i < hex_index; i++ )    Connect(Middle_of_Hex(Hex_List,Hex_List[i-1]));

Okay, I guess that just makes understanding harder.

[Edited by - szecs on May 20, 2010 2:37:58 AM]

[size=2]Portfolio [size=2]| Youtube channel | Paper modeller development blog | Journal

rubicondev

296

Author

May 20, 2010 02:45 AM

One thing I should've made clear - I don't have any "edges" to start with. The diagram above isn't a diagram but actually a screenie from my 2D editor. The hexes are sprites.

So really, there is no concept of an edge of a hex - centres is all I have and so far all these suggestions to use outside edges break down. I guess I could look into making some virtual edges somehow, but I think that needs exactly the same heuristic as what I'm already looking for without them, given my starting conditions.

Here's a better example of the problem.

more hexes

------------------------------Great Little War Game

szecs

2,990

May 20, 2010 02:54 AM

You should be able to identify "edges" just from the indexing of the hex grid. Or is it not consistent? I mean

(0,0)(1,0)(2,0)(3,0)(4,0)(0,1)(1,1)(2,1)(3,1)(4,1)(0,2)(1,2)(2,2)(3,2)(4,2)(0,3)(1,3)(2,3)(3,3)(4,3)

Finding a "coast": if one side is green, and the other is blue: it's a coast. Otherwise not.

I'm not sure if you can avoid the use of the contour. Maybe you can avoid it with a very complex algorithm to handle all cases.

[size=2]Portfolio [size=2]| Youtube channel | Paper modeller development blog | Journal

szecs

2,990

May 20, 2010 03:03 AM

Maybe the marching squares/hex is a simpler stuff.
Since you have fewer cases with hex, than with squares. You only have to check 3 hexes, instead of four squares.

Anyway, you have 3 different approaches now, that should be enough :P

[size=2]Portfolio [size=2]| Youtube channel | Paper modeller development blog | Journal

656

May 20, 2010 04:15 AM

I was bored at work so I tested the algorithm that I gave (on a grid), works like a charm:
(The red lines are half an arrow so that you can see the direction)

You can also allow for diagonals (8 neighbors):

It handles "thin" cells ok:

Even a single cell is ok:

And lines:

Everything I threw at it worked ok:

656

May 20, 2010 04:22 AM

Oh.. and the source:
(Will not compile out of the box, but you should be able to fix it up).

typedef std::pair<uint, uint> CellIndex;bool getNeighborCellIndex(CellIndex& neighborIndex, const CellIndex& cellIndex, const uint direction, const uint w, const uint h){	static const int directions[4][2] = 	{		0, -1,		1, 0,		0, 1,		-1, 0,	};	neighborIndex.first = cellIndex.first + directions[direction][0];	if (neighborIndex.first >= w)		return false;	neighborIndex.second = cellIndex.second + directions[direction][1];	if (neighborIndex.second >= h)		return false;	return true;}void traceContour(std::vector<CellIndex>& contour, const Image* const im, const uint x, const uint y, const uint w, const uint h, const uint p){	CellIndex cellIndex = CellIndex(x, y);	contour.push_back(cellIndex);	uint oldDirection = 0;	CellIndex firstCellIndex = cellIndex;	for (; ; ){		uint testDirection;		CellIndex testCellIndex;		uint i;		for (i = 1; i < 4; ++ i){			testDirection = (oldDirection + i) & 3;			if (getNeighborCellIndex(testCellIndex, cellIndex, testDirection, w, h)){				uint pp;				im->getIndex(testCellIndex.first, testCellIndex.second, pp);				if (pp == p)					break;			}		}		if (i == 4){			// We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell.			if (cellIndex == firstCellIndex)				break; // found a complete path of a single cell  			testDirection = oldDirection;			if (!getNeighborCellIndex(testCellIndex, cellIndex, testDirection, w, h))				break; // Should never happen!		}		if (testCellIndex == firstCellIndex)			break; // Found a complete path		cellIndex = testCellIndex; // Update current cell index		oldDirection = (testDirection + 2) & 3; // Swicth direction from "going to" to "coming from"		contour.push_back(cellIndex);	}}bool getNeighborCellIndexDiag(CellIndex& neighborIndex, const CellIndex& cellIndex, const uint direction, const uint w, const uint h){	static const int directions[8][2] = 	{		0, -1,		1, -1,		1, 0,		1, 1,		0, 1,		-1, 1,		-1, 0,		-1, -1,	};	neighborIndex.first = cellIndex.first + directions[direction][0];	if (neighborIndex.first >= w)		return false;	neighborIndex.second = cellIndex.second + directions[direction][1];	if (neighborIndex.second >= h)		return false;	return true;}void traceContourDiag(std::vector<CellIndex>& contour, const Image* const im, const uint x, const uint y, const uint w, const uint h, const uint p){	CellIndex cellIndex = CellIndex(x, y);	contour.push_back(cellIndex);	uint oldDirection = 0;	CellIndex firstCellIndex = cellIndex;	for (; ; ){		uint testDirection;		CellIndex testCellIndex;		uint i;		for (i = 1; i < 8; ++ i){			testDirection = (oldDirection + i) & 7;			if (getNeighborCellIndexDiag(testCellIndex, cellIndex, testDirection, w, h)){				uint pp;				im->getIndex(testCellIndex.first, testCellIndex.second, pp);				if (pp == p)					break;			}		}		if (i == 8){			// We're on single side that has no other connected neighbors than the previous one. So we must step back on the same cell.			if (cellIndex == firstCellIndex)				break; // found a complete path of a single cell  			testDirection = oldDirection;			if (!getNeighborCellIndexDiag(testCellIndex, cellIndex, testDirection, w, h))				break; // Should never happen!		}		if (testCellIndex == firstCellIndex)			break; // Found a complete path		cellIndex = testCellIndex; // Update current cell index		oldDirection = (testDirection + 4) & 7; // Swicth direction from "going to" to "coming from"		contour.push_back(cellIndex);	}}

rubicondev

296

Author

May 20, 2010 05:24 AM

Had it running from your pseudo code, but thanks anyway. Kudos for writing pseudo code that actually did work first time, and even more of it for solving my problem.

Nice one! :)

------------------------------Great Little War Game

Tracing a contour from hex data?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Tracing a contour from hex data?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines