Experience with MD2's? Your brains are needed!

Jones
Unregistered
 
Post: #16
akb825 Wrote:For the BST, both methods you mentioned are used. However, the second method is preferable when you don't know the size to begin with.

For your math, you're going to have to deal with a much larger set of indices to reliably scale it up. With such a small sample, what you have really isn't accurate. You're also assuming that it scales linearly: this is not necessarily the case. Since you need to search through the array each and every time you go to another index, you're essentially running proportional to the square of the numbers of the indices. This means your estimated times aren't even proportional to the real times you'll use.

You are of course, correct. I figured that the nested looping would mess up those estimates. It was late though, and they were just estimates.

After making a further study of the OBJ file format, I understand your comments about needing to the know the total number verts/indices. MDLs, MD2s, MD3s would all work fine with my method, because the header gives away all needed information. In an OBJ though, you'd have to count all the 'v' tags first.

I had no idea the OBJ format was so simple (as in being text based) Shock . Like Direct3D models, almost.

I'm off to test this with 40 000 vertices...

EDIT: Perhaps afterwards I could send you this data so that we could compare speeds? I'm curious to see the results. Smile
Quote this message in a reply
Jones
Unregistered
 
Post: #17
I made a file of semi-random vertices. Many of them were duplicates.

The original file size was 960,000 bytes. It contained 60000 vertices with 60000 indices. The final file was 258,108 bytes. It contained the 1509 vertices that were actually needed and the 60000 indices.

It takes 3 + 6 over 2, seconds to complete on average. 3 was the fastest time, and 6 was the longest out of 6 or 7 runs. 4.5 seconds is not so horrible. Smile

If you'd like to test your method with this data... (I'd like to compare them, but you are in no way obligated to participate in this little experiment.)

Download this file : Link

The file looks like this:
180000 floats (4bytes).
60000 ints (4bytes).

It is encoded as binary, rather than ascii. The file is Big-Endian, in case you are on an intel mac. If you do run your code through it, could you please save the results as a file with the result vertices first and the indices second (in any endian that you choose, as long as I know what it is Rasp). If your code manages to get rid of more vertices than my own, you'll have to tell me how many are left.

If you're short on time then by no means do this just for me. I'm pretty satisfied with my results either way. Smile

EDIT: I realize that akbs cpu might be faster than mine, but if BST's really as great as you say (I hope they are, as I plan to learn to use them...) then the difference should be amazingly apparent. Rasp
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #18
I would hardly call being text based simple: it takes a lot more effort to parse these than just read binary from a file, even if you need to swap the bytes. Some of the parsing is pretty easy, but then you get to the point where you need to parse an indefinite number of items for the faces etc. Also, I had problems with windows files having a '\r' ending rather than a '\n'. Of course, I wrote my loader about 9 months ago before I knew as much as I know now, so it's probably much more complicated than I need it to be, but it works.

Anyways, I might try this out a bit later. However, I tried a couple of tests. (with some real models I have) When I ran my time calculations, I tried to get rid of all the parsing overhead that I could so I could concentrate on just the optimization of vertices.

For the smaller one:
Number indices: 65272
Number vertices: 10932
Time to consolodate vertices: 0.141118 s

The resulting file ended up being 856 KB, which includes indices, vertices, normals, colors, and texture coordinates. (note that this should be similar to yours, since it has a similar number of indices)

The larger model:
Number indices: 401958
Number vertices: 99243
Time to consolodate vertices: 1.182231 s

The resulting model was 5.8 MB, including indices, vertices, normals, and texture coordinates.

BTW, can you send me your original test program for comparison? (preferably as source, so I can add a timer within it)
Quote this message in a reply
Jones
Unregistered
 
Post: #19
Sure:

Project Download

I wrote it rather quickly, if it's not quite as efficient as it could be then that's probably why. Wink

Your code is obviously very fast. Smile
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #20
I ended up just writing my own, since was pretty quick. Here's the results (with just the algorithms, no file IO times):
Time with BST: 0.067782 s
Time with nested loops: 0.723343 s

So it's essentially almost 11x faster with this example, but the distance will only grow with more complex models. BTW, I noticed in your source that you're using ==. Don't. With floats, you want to subtract them, take the absolute value and see if the result is < some epsilon. My resulting files were 246,036 bytes in long.

Edit: Also, just FYI, that large file that took 1.18 s to open: when I still had an n^2 solution similar to the nested loops (except I used a linked list), it literally took over 10 minutes to open. For a long time I thought I was infinite looping until I waited long enough. (that time does include the IO, but it takes roughly 5s to open with IO right now, so I doubt that 4s of IO time will effect it that much Rasp)
Quote this message in a reply
Jones
Unregistered
 
Post: #21
Wow, that's impressive. 11x faster. After further study of the obj file format I've come to a conclusion.

Binary Search Trees would indeed be very useful for an Wavefront Object loader, because the .obj format has no defined indices. That's where BST's would be great! You could add the vertices one by one to your tree. There would be no duplicates, and the indices would be the return value of your insert commands (assuming they return a slot/address). Smile

The MD2 format has predefined indices though. It think that's why it didn't make much sense to me at first. You could use a BST to sort the indices or the vertices, but in the end the order they're saved in is the order you're stuck with. The indices *must* line up with their verts. Annoyed

While you were testing that file I figured out how to make my MD2-to-VBO loader work!

But first, a quick question, are you a chiropractor? Because sydney (the test model) needs one. (Not that I support chiropractor or the lies they perform/invent. That's just my personal opinion, remember.)

Following these transformations:
Code:
glTranslatef(0.0, -1.0, -19.0);
    glRotatef(-90.0, 1.0, 0.0, 0.0);
    glRotatef(-30.0, 0.0, 0.0, 1.0);
    glScalef(0.4, 0.4, 0.4);

She renders like this:
[Image: syd_help.png]

That looks *extremely* painful. It also looks like one of those depth illusion images, like the stairs that go eternally upwards. (BTW, depth testing *is* enabled.)

If I change the second rotation to positive 30.0Ëš...
http://homepage.mac.com/gareth.cross/stu..._help2.png

Ow. LOL

In the first it's almost like her feet are twisted *into* the screen while her legs are coming *out* of the screen. In the second it's the same, her body kind of goes into the screen, her feet come out along with her breasts...

It's a weird error, because it looks almost normal. Her shape is correct, the texturing is correct... it's just wrong. Shock

Slight endian error? Horrible bicycle accident?

25¢ to look at the freak! Okay, I'm done now. Wink

The fix itself works like this:

Rather than line the tex-coords up with the vertices, I lined the vertices up with the tex-coords! This might cause the funkyness, and I'm investigating the possibility.

*goes to fix ==* (Which aren't actually used in the fix I came up with...)

EDIT: What exactly did you mean by 'some epsilon'?
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #22
Just putting the vertices in the BST doesn't make it so you don't have to count the vertices. You still have to store all the original vertices so the indices stored in the file can access them. Also, you really don't want to use something like a linked list to do that, since nothing beats an array with index accessibility. I guess I could have resized an array instead of reading through the file multiple times, but there were other things I needed to count as well, not just the vertices, and I also needed to make sure that I handled objects and groups correctly, as well as material files.

Anyways, I think the only time I've had weird things like that was when I was trying to do matrix calculations while drawing in immediate mode. Are you using immediate mode right now or using vertex arrays/VBOs?
Quote this message in a reply
Member
Posts: 440
Joined: 2002.09
Post: #23
Jones Wrote:That looks *extremely* painful.
Actually, it looks like your triangle windings are backwards (you're looking at backfaces).
Quote this message in a reply
Moderator
Posts: 1,140
Joined: 2005.07
Post: #24
BTW, to clarify about my obj loader, right now I have 3 passes. For the first pass, I read in the number of vertices, normals, texture coordinates, objects/groups, and material files. The second pass I read the vertices, normals, and texture coordinates, count the number of indices in each group, and read which material files I need to open. (and then actually open those files and read their contents) The third pass consists of reading in the indices and getting the new indices by inserting the vertex, normal, texture coordinate, and current material's color into the tree. Using resizable arrays etc. I may be able to do it in 1 pass, but I'll have to see how strict the rules are in case that brings up a new set of problems. I may eventually re-write my obj loader anyway, though, since it's rather messy. (since I wasn't as experienced with parsing at the time, though it does work well)
Quote this message in a reply
Jones
Unregistered
 
Post: #25
akb825 Wrote:Anyways, I think the only time I've had weird things like that was when I was trying to do matrix calculations while drawing in immediate mode. Are you using immediate mode right now or using vertex arrays/VBOs?

At the time of those screenshots I was using immediate mode. I get the same result in VBO and Vertex Array modes. I'm going to sift through some endian stuff and change it a little, I think there are some slight variances because of the ways I read the scale/translate floating point numbers.


Quote:Actually, it looks like your triangle windings are backwards (you're looking at backfaces).

If they were backwards I wouldn't see anything, I cull all BackFaces. Smile
Quote this message in a reply
Sage
Posts: 1,403
Joined: 2005.07
Post: #26
Quote:If they were backwards I wouldn't see anything, I cull all BackFaces.
imagine if your windings were backwards, and you culled backfaces.. what would you see?

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Jones
Unregistered
 
Post: #27
I have discovered disturbing new evidence...

Look at this picture:
[Image: syd_help3.png]

The sydney on the right is rendered with the new code. The sydney on the left is rendered with my old old old MD2 code. It had no features like VBO support but it could render correctly, and yet now... after some transformations like those of the other model, it does not. Blink

This is strange. Shock
Quote this message in a reply
Jones
Unregistered
 
Post: #28
unknown Wrote:imagine if your windings were backwards, and you culled backfaces.. what would you see?

Nothing..., because backwards windings are like the backfaces of what their forward faces would be if they existed.

Wait... is that correct? ZZZ *refers to red book*

Well, I've misplaced my copy of the red book but OpenGL Distilled states modeling transformations can affect the winding of faces, but that it doesn't matter anyway because OpenGL uses window coordinates for face culling.

EDIT:

sonufagun! You guys were right! If I disable GL_CULL_FACE then everything looks fine! I've been drawing them clockwise without realizing it! Rasp

Woot it works! Thanks a ton Akb, Frank and unknown!

Once I've perfected my MD3 loader I shall release the code for my MESH class, so that others will not have to deal with the same stuff I've wrestled with in this thread! Grin
Quote this message in a reply
Post Reply