Optimizing Vertices

Member
Posts: 241
Joined: 2008.07
Post: #1
Alright, I'm finally satisfied that the vertices that I'm receiving from my 3DS exporter are indeed the vertices that I need in order to draw my object. Now what I need to do is optimize them by throwing away and duplicates and making an index array. Would anyone have any advice as to the correct way to do this?

Thanks!!
Quote this message in a reply
Moderator
Posts: 3,570
Joined: 2003.06
Post: #2
There's no "correct" way to do it.

First, you should make sure that your mesh is optimized by making vertices (and texCoords and normals) within a certain (arbitrary) small distance of each other share identical coordinates. Otherwise minute differences in vertices [can] throw off the duplicate removal process.

After that, to remove duplicates, I do it with an NSMutableDictionary for its hashing ability. It's definitely fast enough for an offline converter (maybe 7 seconds for 50k triangles), but you could do your own hash table for even more efficiency I suppose.

Here's a little snippet of where the action is at in my converter/loader:
Code:
NSString    *key;
NSData      *data;
NSNumber    *index;

key = [NSString stringWithFormat:@"%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f",
            vertexData->vertex[0], vertexData->vertex[1], vertexData->vertex[2],
            vertexData->normal[0], vertexData->normal[1], vertexData->normal[2],
            vertexData->texCoord[0], vertexData->texCoord[1]];
index = [vertexDataDictionary objectForKey:key];
if (index == nil)
{
    // no object found with this key so this is a unique vertex
    data = [NSData dataWithBytesNoCopy:vertexData length:sizeof(VertexData) freeWhenDone:NO];
    [vertexDataArray addObject:data];
    index = [NSNumber numberWithUnsignedInt:[vertexDataArray count] - 1];
    [vertexDataDictionary setObject:index forKey:key];
}
[vertexDataIndexArray addObject:index];

It's hard to describe exactly what is going on, but the meat of it is how I generate the key for the unique vertex. vertexData is the candidate vertex to be added, and the key, as you can see, is just an NSString (made up of all the vertex's unique coordinate data). So far it has worked out great.
Quote this message in a reply
Member
Posts: 241
Joined: 2008.07
Post: #3
Objective-C is like a booger, you don't want to touch it, especially if it isn't yours. Rasp
Quote this message in a reply
Moderator
Posts: 3,570
Joined: 2003.06
Post: #4
bmantzey Wrote:Objective-C is like a booger, you don't want to touch it, especially if it isn't yours. Rasp

LOLLOL That's funny, I haven't heard that one before!

Sorry it is so cryptic. Like I said, the main thing is that the key is generated using a formatted string from the candidate vertex data, something like so:

sprintf(key, "%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f", vertX, vertY, vertZ, normX, normY, normZ, texS, texT);
Quote this message in a reply
Member
Posts: 87
Joined: 2006.08
Post: #5
AnotherJake Wrote:LOLLOL That's funny, I haven't heard that one before!

Sorry it is so cryptic. Like I said, the main thing is that the key is generated using a formatted string from the candidate vertex data, something like so:

sprintf(key, "%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f%0.3f", vertX, vertY, vertZ, normX, normY, normZ, texS, texT);

For this task, the C++ STL will be vastly more efficient. You can use a stl::pair<type_a, type_b>, and the use that as the key into an stl::map, to perform the same mapping at tremendously greater runtime efficiency (probably hundreds of times faster). Fast enough to do it at application launch, than offline.

I just put up an example here: http://pastie.org/289812

This example shows a subset of the stanford bunny data (pastie doesn't like 1.1MB large blocks of text, for some unknowable reason...).

The vertex format may not match exactly what the OP has to work with, but it should show you how to use these tools to write an efficient converter.
Quote this message in a reply
Member
Posts: 241
Joined: 2008.07
Post: #6
Ooh yeah, a std::map ensures no duplicity. Hmm, I might use that. However, I don't have a problem with finding the unique vertices, it's generating the index array.

Basically what I'm doing is this: (first, I'm trying to load and render a basic cube)

1) Load a vertex in from file.
2) Check the vertex against every vertex in a std::vector.
3) If it is found, use the index of the for loop as the index to push into the vector for the index array.
4) If it is not found, push the vertex into the vector and use vector.size()-1 as the number to push into the index array.

Everything seems to run fine, until I look at the data.

When I compare the data I pull out of the 3ds file to that which I see in either a .obj or .fbx file (both text based), I'm seeing oddities.

1) y and z are swapped in the .obj compared to the 3ds.
2) Although I'm getting the same number of vertices in either format, they are appearing in a different order.

I've looked at just copying and pasting the data from either the .obj or the .fbx, but again, problems.

1) There are only 8 vertices in the .obj file (GOOD! That means that they are unique vertices). However, there is no index list. Instead, there's a list of faces that doesn't even make sense. What is this?

What's that beat-your-head-against-the-desk emoticon? Sad
Quote this message in a reply
Member
Posts: 241
Joined: 2008.07
Post: #7
Quote:I just put up an example here: http://pastie.org/289812

That's cool and thank you but the problem is, the data you have, you already know is good. My problem is, I'm not certain of the data I'm getting out of my exporter. It doesn't render, and it doesn't make sense. It does load up and display in the trial version of Cheetah3D though, so I know it's good. I must be doing something terribly wrong either in my exporter or in OpenGL or both.

I just graduated from Full Sail's game development program and I thought I knew what the hell I'm doing but I'm finding myself terribly frustrated. If I was doing regular OpenGL, I might have better luck but this is OpenGL ES 1.1 for iPhone, making it a very difficult job. Again, I appreciate all the help!!
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #8
There's no difference in OBJ loading between "regular" OpenGL and OpenGL ES Rasp
Quote this message in a reply
Moderator
Posts: 3,570
Joined: 2003.06
Post: #9
Frogblast Wrote:I just put up an example here: http://pastie.org/289812

Hey, thank you very much Frogblast!

Hehe, yeah obviously my NSDictionary route isn't going to win any speed records. Blush

I am not a C++ aficionado, but that is definitely one of the most elegant uses of it I've seen. I'll be studying up on that more when I get a spare chunk of time to spend on it. Smile



@bmantzey : be careful trying to parse fbx files, because they aren't documented (actually, the fbx docs point that out). The fbx format is to be read and written using the SDK, so relying on the file format itself is probably not wise. I think the best thing to do with fbx to iPhone would be to load in the file using the SDK in a converter on your desktop machine, and then export that data to your own format -- not directly from the fbx file itself.

Quote:If I was doing regular OpenGL, I might have better luck but this is OpenGL ES 1.1 for iPhone, making it a very difficult job.

That's interesting, because I have to say that I've had more fun with OpenGL ES than I did with desktop OpenGL. I don't know why, but it's appealing to me to pop open the ES header and see that's all there is to it!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Help optimizing an inconsistent framerate Duddd 6 4,489 Apr 4, 2010 09:27 PM
Last Post: Duddd
  Optimizing my Game Engine. Help needed! SamBaylus 25 14,852 Feb 12, 2010 07:45 AM
Last Post: kae_