Highlighting 2d meshes, a technique

Problems building or running the engine, queries about how to use features etc.
Post Reply
Octal Forty
Kobold
Posts: 33
Joined: Thu Dec 16, 2004 1:39 pm

Highlighting 2d meshes, a technique

Post by 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?

Image

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
Last edited by Octal Forty on Sat Aug 06, 2005 2:16 am, edited 3 times in total.
User avatar
baxissimo
Greenskin
Posts: 135
Joined: Wed Feb 23, 2005 1:28 pm
Location: Tokyo, JAPAN

Re: Excluding internal edges when outlining a mesh

Post by 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
Kobold
Posts: 33
Joined: Thu Dec 16, 2004 1:39 pm

Solved

Post by 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.

Image

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
Kobold
Posts: 33
Joined: Thu Dec 16, 2004 1:39 pm

Post by 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:
Image
User avatar
:wumpus:
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 3067
Joined: Tue Feb 10, 2004 12:53 pm
Location: The Netherlands
x 1

Post by :wumpus: »

If you publish code, add it to the wiki please, on the forum it might get lost!
Octal Forty
Kobold
Posts: 33
Joined: Thu Dec 16, 2004 1:39 pm

Post by 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.
User avatar
Olex
Hobgoblin
Posts: 593
Joined: Fri Apr 08, 2005 6:08 pm
Location: WA, USA

Post by Olex »

Goo job on resolving your problem by yourself from a simple hint. :D :wink:
Octal Forty
Kobold
Posts: 33
Joined: Thu Dec 16, 2004 1:39 pm

Post by Octal Forty »

Thanks a lot.
Post Reply