Highlighting 2d meshes, a technique

[Octal Forty]

I have a bunch of meshes made from planes. I'd like to draw a border over the outline of the mesh only. I have the list of vertices and the list of indexes for each mesh, but I'm not sure how I can tell which ones are external edges (ie the border), and which ones are internal diagonals.

Take a look at the screenshot - I'd like to come up with a way to exclude all of those diagonal edges. Is this possible?



I've included the relevant code I'm using also:

Code: Select all

void GameState::outlineEntity(Ogre::Entity* entity )
{
	size_t vertex_count,index_count;
	Vector3* vertices;
	unsigned* indices;
	getMeshInformation(entity->getMesh(),vertex_count,vertices,index_count,indices);

	Vector3 *vertexArray = new Vector3[vertex_count];
	unsigned *indexArray = new unsigned[index_count];

	vertexArray = vertices;
	indexArray = indices;

	SceneNode *myNode = State::gSceneMgr->getRootSceneNode()->createChildSceneNode();
	Line3D *myLine = new Line3D();

	//Draw by index
	for (int i=0; i < index_count; i++)
	{
		int index = 0;
		printf("Index %d: %u\n", i, indexArray[i] );
		index = indexArray[i];

		Vector3 point = (Vector3)vertexArray[index];
		printf("Adding point %f %f %f to Line3d\n", point.x, point.y, point.z);

		myLine->addPoint(point);
	}

	myLine->drawLines();
	myNode->attachObject(myLine);

	//Entity SceneNodes scaled also - mesh modelled too small.
	myNode->setScale(10.5, 10.5, 10.3);

	delete[] vertices;
	delete[] indices;
}

Thanks in advance

[baxissimo]

The general problem you're trying to solve is called "detecting silhouette edges". There's a bunch of papers out there on the subject, many of them non-photorealistic rendering (NPR) papers.

The general way to do it is to look at the two triangles that are adjacent to a given edge and compare their projected normals under the current viewing matrix. If one is backfacing and one is frontfacing, then you have a silhouette edge (i.e. one projected normal has pos z component one has neg z). Instead of checking projected normals, you can equivalently look at the winding order of projected vertices. If one tri has verts in clockwise order and the other counter-clockwise, then the edge between them is on the silhouette.

[Octal Forty]

Thanks, baxissimo. After some research, it turns out that OGRE provides the pieces for me - I just didn't know what to look for until your response.

Anyway, for those who are interested, here is a screenshot of my 2d New England states mesh with thier silhouette edges outlined using Line3D. Note that the method I used only works with simple 2d meshes, because it determines which edge to draw by checking the degenerate flag of the Edge. I guess this could be useful to other people who are creating maps.



Here is the code as well - note that getMeshInformation and Line3d can be found on the Wiki.

This method detects the degenerate edges and draws a line over the entity at the edge endpoints (called after entity creation):

Code: Select all

void GameState::outlineEntity(Ogre::Entity* entity )
{
	size_t vertex_count,index_count;
	Vector3* vertices;
	unsigned* indices;

	getMeshInformation(entity->getMesh(),vertex_count,vertices,index_count,indices);

	Vector3 *vertexArray = new Vector3[vertex_count];
	vertexArray = vertices;

	SceneNode *myNode = State::gSceneMgr->getRootSceneNode()->createChildSceneNode();
	
	Ogre::EdgeData* edgeData = entity->getMesh()->getEdgeList(0);
	Ogre::EdgeData::EdgeGroupList::iterator i, iend;
	Ogre::EdgeData::EdgeList::iterator ei, eiend;

	iend = edgeData->edgeGroups.end();
	for (i = edgeData->edgeGroups.begin(); i != iend; ++i)
	{
		int num = 0;
		eiend = i->edges.end();

		for (ei = i->edges.begin(); ei != eiend; ++ei, ++num)
		{
			Line3D *myLine = new Line3D();
			Ogre::EdgeData::Edge& e = *ei;
			//If this edge is degenerate, then take the vertex index at 0 and 1,
			//do a lookup in the actual vertex array, and immediately
			//draw the line.
			if (e.degenerate)
			{
				Vector3 start = Vector3(vertexArray[e.vertIndex[0]]); 
				Vector3 end = Vector3(vertexArray[e.vertIndex[1]]);

				myLine->drawLine(start, end);
				myNode->attachObject(myLine);
			}
		}
	}

	//Entity SceneNodes scaled also - mesh modelled too small.
	myNode->setScale(10.5, 10.5, 10.3);

	delete[] vertices;
	delete[] indices;
}

[Octal Forty]

Ok. I'm not sure if anyone will ever use this, but the code I just posted has a major bug. I don't know if any of you are using OGRE in this manner, but I feel obliged to correct this mistake. Note that if you use the technique described below, although it takes alot of modelling work, it seems to be an effecient way to draw borders on a map.

Notice the framerate drop between the first and second screenshot, this was because I was adding a new scenenode for each line. I noticed this right after I posted but then moved on to another problem. Since my ultimate goal is to render 3007 seperate and distinct meshes on the screen at one time AND thier borders using Line3d - efffectively doubling the number of veritices - optimization is key. So, I'm making most of my display static. The outline entity method should be implemented in such a way as it pushes all points to draw in a vector before it does the draw, then after it has found all the edges, then draw the lines. Before, I was adding each line as a seperate SceneNode. Now, it's just one.

I was able to improve my FPS by a factor of 10 by doing this. Also, I used a technique in Bleder where I rendered the country map as a 2d plane first, then saved it as a seperate mesh (USA2d.mesh). Then, I extruded the edges and moved them in the negative z direction. I saved this model as a seperate mesh (USA3d.mesh). Then, I rendered USA3d.mesh and created an entity of USA2d.mesh but did not attach it to a SceneNode. Instead, I just passed the Entity to the outlineEntity helper function and drew the degenerate edges and batched them in a StaticGeometery without rendering the mesh. I'm not sure if this is a hack or if you geniuses out there would've thought of this last Monday, but it works - and quite well I might add. Here's the code:

Code: Select all

void GameState::outlineEntity(Ogre::Entity* entity, 
							  StaticGeometry* staticGeometry, 
							  SceneNode* sceneNode )
{
	size_t vertex_count,index_count;
	Vector3* vertices;
	unsigned* indices;

	getMeshInformation(entity->getMesh(),vertex_count,vertices,index_count,indices);

	Vector3 *vertexArray = new Vector3[vertex_count];
	vertexArray = vertices;

	Ogre::EdgeData* edgeData = entity->getMesh()->getEdgeList(0);
	Ogre::EdgeData::EdgeGroupList::iterator i, iend;
	Ogre::EdgeData::EdgeList::iterator ei, eiend;
	Line3D *myLine = new Line3D();
	iend = edgeData->edgeGroups.end();
	for (i = edgeData->edgeGroups.begin(); i != iend; ++i)
	{
		int num = 0;
		eiend = i->edges.end();

		for (ei = i->edges.begin(); ei != eiend; ++ei, ++num)
		{
			
			Ogre::EdgeData::Edge& e = *ei;
			//If this edge is degenerate, then take the vertex index at 0 and 1,
			//Add both vertices to the Line3d dequeue..
			if (e.degenerate)
			{
				Vector3 start = Vector3(vertexArray[e.vertIndex[0]]); 
				Vector3 end = Vector3(vertexArray[e.vertIndex[1]]);

				myLine->addPoint(start);
				myLine->addPoint(end);
			}
		}
	}

        /*Here is the major optimization. Rather than draw each line
           and add it as a seperate SceneNode, I can use the inbred
           batching functionality of Line3d to draw all lines at the END of 
           finding Silhouette Edges, and hence only have one Scene node as  
           opposed to several hundred. Which improved the FPS on my laptop  from ~7FPS to 79FPS. */
	myLine->drawLines();
	sceneNode->attachObject(myLine);
	staticGeometry->addSceneNode(sceneNode);

	delete[] vertices;
	delete[] indices;

Here's a screenshot because I'm really excited about my progress thus far:

[:wumpus:]

If you publish code, add it to the wiki please, on the forum it might get lost!

[Octal Forty]

Do you think this is quality enough to wiki?

edit: Wow. I just tried to Wiki and it's beyond me. Is there a wiki on the wiki?

edit 2: I think I have it. Never mind.

[Olex]

Goo job on resolving your problem by yourself from a simple hint.

[Octal Forty]

Thanks a lot.