# Mesh extraction

This topic is 4815 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello. I am using D3DXCreateText to get a 3d mesh of some large text which I am using in my application. The application is in 2d so the text will only ever be used 'front facing' if you see what I mean. What I need to do is to extract from the mesh, just the 'outline' of the text. The text is always large single characters so for example, if I use D3DXCreateText to create a T, I get the mesh and then I need to get the vertices which make the outlint of a T shape. Thanks for any help, any pointers to anything which might help are greatly appreciated. Kind regards. Mark Coleman

##### Share on other sites
I presume you're fine with actually getting the geometry (locking the mesh's vertex buffer and pulling it all out...)

I don't think there are any pre-built functions that are going to do this for you, so it looks like a few graphics algorithms might be what you need [smile].

On face value, it sounds like a modified version of the shadow-volume extrusion technique might work well. In this algorithm you work on each edge in the mesh (you may need the index buffer to get this list) and the corresponding edges on either side. Calculate the face normals for these faces and compare them. If the angles are suitably different (e.g Dot Product is <= 0.0f) you can be sure that your edge is actually a sharp edge ("on the edge of your mesh").

Provided you haven't got an excessively smoothed piece of text, then this algorithm should give you all the edges that make up the front/back of the geometry, store these in an array and delete any duplicates that project to the same place on your XY/XZ plane and voila! you have a list of verticies around the edge of your text.

Is that any good?
Jack

##### Share on other sites
Hmm, well I haven't done any of this stuff before so it is a bit of learning curve at the moment. I kind of see what you mean but what happens when I am drawing a G or some other 'curly' letter like that one?

I had the basic idea that I could find the x,y of the most top left vertex, then I could go round the vertices clockwise, i.e. always choosing the 'most left' next turn, storing the vertices as I go.

This works for letters such as H, T, S etc but it will not work for letters such as O, P, B which have gaps in them.

There must be an algorithm for finding out the outline of a mesh? The shadow volume idea is a good one, I will look into that. In the mean time if anybody else has any ideas I will be very appreciative.

Thanks for the help JollyJeffers.

edit: I have just re-read your post and I see what you mean now. If we assume that the text is basically a prism of the 2d letters then your suggestion effectively 'flattens' the text, am I right?

So would you suggest that I check every face against every neighbour and the store all the faces that are perpendicular to their neighbour?

One question arises, how do I know which edge of the face was touching the perpendicular neighbour?

Mark Coleman

##### Share on other sites
Correct me if I'm wrong, but if you only want the front face of the text (no 3D outline at all) wouldn't you just run through all the triangles and only keep the ones where dot(normal, view_direction) < MIN_COS_ANGLE for some value of MIN_COS_ANGLE around -0.9f?

That way you'd get just the triangles that are facing towards the camera, and you only have to look at each triangle once rather than finding all its neighbours.

##### Share on other sites
Quote:
 Original post by fractoidCorrect me if I'm wrong, but if you only want the front face of the text (no 3D outline at all) wouldn't you just run through all the triangles and only keep the ones where dot(normal, view_direction) < MIN_COS_ANGLE for some value of MIN_COS_ANGLE around -0.9f?That way you'd get just the triangles that are facing towards the camera, and you only have to look at each triangle once rather than finding all its neighbours.

That could work quite well, but it depends on how D3DX generates the geometry for the given letters.

Another way of getting all the camera-facing geometry would be to flatten the text onto a given plane and remove the duplicates (where the back vertex now has the same depth/height as the front vertex).

Thing is, identifying the edges seems a bit trickier there - if you manipulate it in 3D then you can make use of the depth information to identify the correct edges.

Quote:
 edit: I have just re-read your post and I see what you mean now. If we assume that the text is basically a prism of the 2d letters then your suggestion effectively 'flattens' the text, am I right?

Yeah, but not quite flattens it in the way that I commented on above. My way would give you, essentially, a line-list of verticies that made up the outline (silouette) of the shape:

+----------+|          |+---+  +---+    |  |    |  |    |  |    |  |    +--+

That is, you'd end up with the verticies where you have a "+" above, and the appropriate lines between them. You wouldn't end up with the various subdivided triangles that make up that face:

+-+-+-+-+-+|\|\|\|\|\|+-+-+-+-+-+    |\|    +-+    |\|    +-+    |\|    +-+

(Ascii art sucks a bit for this [smile])

Quote:
 So would you suggest that I check every face against every neighbour and the store all the faces that are perpendicular to their neighbour?One question arises, how do I know which edge of the face was touching the perpendicular neighbour?

Right, you'd need both the index and vertex buffers for the mesh. I'm assuming standard ID3DXMesh stuff here.

The indicies form a triangle list, so index 0,1,2 is your first triangle and 3,4,5 is your second triangle (and so on)...

for a triplet of 0,1,2 you have 3 edges: 0-1, 1-2 and 2-0. For each of these edges there should be a neighbouring triangle that also has this pairing (providing you have a closed mesh with no funky joins!).

If you loop through your index buffer and build up this list of edges (store them as [MIN(i0,i1), MAX(i0,i1)] so you can be sure of a certain ordering). For each edge stored (two WORD's for start/finish index) you want to assign a triangle ID as well (another two WORD's for each one).

For each triangle, if the edge exists in your array, then you already know one of the triangles, so just append this triangles ID to that entry. If the edge does not exist in the array, you need to add it, and this triangles ID becomes the first known triangle.

At the end of the loop, you should have a long list of unique edges and 2 triangle ID's for each edge.

Next step.

For each edge, you need to calculate the normal for the triangle on either side; you can do this using standard maths based on the vertex data for each triangle. Look up the vertex data based on the index data that you look up using your triangle ID's (bit complicated, I know!).

You should now have 2 normals. Perform a dot-product on them. If the result is less than or equal to 0.0 then you know that the given edge is on a right-angle (or greater) "fold" in your geometry. That is, it's a substantial edge.

You can now add this edge to your list of final edges that make up the sillouette of your letter.

Once you've processed every edge you'll probably have a duplicate outline - because this algorithm will identify both the front/back outline of the letter. However, if you flatten these onto a plane (e.g. set the Z coordinate as 0.0) then you can quite easily check for duplicates and discard them.

Let me know if you want any more detail on the finer points here [smile]

hth
Jack

##### Share on other sites
Fractoid, thanks for the suggestion but when the non-forward facing triangles have been culled it becomes difficult to then remove the inner edges of the triangles that comprise the letter shape.

JJ, on paper I believe your idea works but I have one question which you (or others) may be able to answer for me. It seems that your first step is essentially just building adjacency information and I was under the impression that D3DX could do this for me automatically with the ID3DXMesh::GenerateAdjacency method?

Is this incorrect?

Thanks again.

Mark Coleman

##### Share on other sites
Quote:
 Original post by mrmrcolemanJJ, on paper I believe your idea works but I have one question which you (or others) may be able to answer for me. It seems that your first step is essentially just building adjacency information and I was under the impression that D3DX could do this for me automatically with the ID3DXMesh::GenerateAdjacency method?

Yup, I believe said function will do the trick for you. If you take up my idea, then you'll probably find it easier and quicker (both dev. and runtime) to use ID3DXMesh::GenerateAdjacency( ) [smile]

When I'm coming up with "new" graphics algorithms I tend to think of them in general terms before seeing if/what D3DX can do to help out...

Jack

##### Share on other sites
Ok, so here is what I have so far and the questions I have about each step:

1. Create the font to be used and select it into the DC.
2. Call CreateText with the device and device context, store the mesh object and the adjacency information that is returned.
3. Step through the index buffer and for each entry compare the normal of the current face with the normals of it's neighbours. If the dotproduct of these indicates perpendicular or greater then make a note of the edge in a structure containing two vertices.
4. Go through the list of edges and remove any duplicated edges.

Ok and now the questions.

Question with step 2.

Is the adjacency information that is returned from the CreateText call the same that I would get from call the GenerateAdjacency method on the mesh?

Question with step 3.

How do I calculate the normal of a face?

Question with step 4.

Because this is 3d text but in 2d, each edge in the final list will be doubled anyway because the back face will be exactly the same as the front face. One solution to this that I thought of was to ignore the Z value when searching for duplicates. Will this work?

Thanks again for any help.

Mark Coleman

##### Share on other sites
I'm assuming this doesnt have to be all that fast (ie, done on a per frame basis)

First extract only faces which face the camera (back face culling)

Next go through each triangle edge and see if another triangle shares that edge.. if two triangles share an edge (and it can only be 1 or 2 triangles using an edge) then this edge is NOT an outline edge.. ie, store all the edges which are only used once in the culled mesh.

Now you have 'edge soup' which you need to link together into 1 or more 'outline' groups ..each outline group should loop back on itself.. A->B->C->D->A

The letter 'A' would have 2 outline groups in a typical font.. the outside edge and the inside cutout.. the letter 'B' would have 3 groups. C would have a single group. And so on..

##### Share on other sites
Quote:
 Original post by mrmrcolemanOk, so here is what I have so far and the questions I have about each step:1. Create the font to be used and select it into the DC.2. Call CreateText with the device and device context, store the mesh object and the adjacency information that is returned.3. Step through the index buffer and for each entry compare the normal of the current face with the normals of it's neighbours. If the dotproduct of these indicates perpendicular or greater then make a note of the edge in a structure containing two vertices.4. Go through the list of edges and remove any duplicated edges.

Seems good so far.

Quote:
 Original post by mrmrcolemanIs the adjacency information that is returned from the CreateText call the same that I would get from call the GenerateAdjacency method on the mesh?

Off the top of my head, yes. However you might want to double check against the SDK documentation. OR, if you notice anything odd going on, make a subsequent call to GenerateAdjacency( ) after you've loaded it.

Quote:
 Original post by mrmrcolemanHow do I calculate the normal of a face?

You have 3 verticies, v0, v1 and v2 - In clockwise order (for ID3DXMesh you should just be able to read them in the order they're stored in the buffer).

Create two vectors: v01 and v02:
v01 = v1 - v0
v02 = v2 - v0

Now, take the cross product of v01 and v02 (D3DXVec3Cross( ) iirc) then normalize the result with D3DXVec3Normalize( ).

The resultant vector will be your face normal. For reference, this can be different from a vertex normal that may (or may not) involve smoothing groups. For this algorithm, you want a face normal...

Quote:
 Original post by mrmrcolemanthe back face will be exactly the same as the front face. One solution to this that I thought of was to ignore the Z value when searching for duplicates. Will this work?

Yes. What will happen is, at the point you detect an important edge that you want to store, you should have both the start/finish index. These should always be unique. However, if you store it in your final array/list as the actual position. When you look for duplicates and/or store the results, do the comparison on a 2D plane (ignoring the Z value for example). That way, the "matching" edges at Z=0 and Z=10 (for a font with a depth of 10..) will seem to be the same and your code will reject them as duplicates.

Quote:
 Original post by mrmrcolemanThanks again for any help.

My pleasure - I enjoy exercising the brain [smile].

Jack

• 23
• 15
• 23
• 10
• 19
×

## Important Information

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!