Sign in to follow this  
Structural

MS3D file format: need a second opinion

Recommended Posts

I decided to take a closer look at my MS3D file loader. When I first wrote it it was a very basic implementation that unwrapped all triangles and ignored any vertex indexing. Now I'm looking at it again because I want to implement vertex indexing for the performance gain, but the file format itself does not seem to take this into account. The part of the file format I'm having problems with is as follows: A model has a list of VERTICES; And a list of TRIANGLES; A TRIANGLE has: - 3 vertex indices (INDICES, not the vertices themselves!) - 3 normals (NO indices, the real deal) - 3 texcoords You can see the full spec here: http://chumbalum.swissquake.ch/ms3d/ms3dspec.txt Basically this implementation opens the way to have multiple normals/texcoords per vertex. This is good if you want very sharp edges, and still use the same vertices. If a vertex is part of triangle A it has this normal, if it's part of triangle B it has another normal. This sucks if you know a vertex will always have the same normal/texcoord which is the case for smooth surfaces. I want both... models that have smooth surfaces, and models that have sharp edges. So, what should I do? I can rewrite the loader to take advantage of the vertex indexing for smooth surfaces, and split the vertices for sharp edges. But it'll increase load time quite a bit (I speculate). On the other hand, I can leave it as it is, not taking advantage of the vertex indexing. How big of a deal is the vertex indexing? Any thoughts about this?

Share this post


Link to post
Share on other sites
been there, done that....

basically for a model viewer/editor app:

Thus:
Quote:

...and split the vertices for sharp edges. But it'll increase load time quite a bit (I speculate).


I generate the additional vertices (that you are talking about):
The most significant issue here is that, relatively speaking, ms3d models are low poly. So generally (this is a huge advantage), any increase in
load time is insignificant (for a model viewer/editor type of application).

Some (one really), interesting points, however, are:
(1) The additional vertices I generate are not for normals; I calculate
normals (perhaps unnecessarily, mind you?) on loading (which can be a killer, time wise, without minor coding contortions) anyhow!

The additonal vertices are generated to obtain
correct texture coordinates(oddly enough).
Have you tried loading an ms3d with a displayed texture yet?
Notice any uv problems?

Needless to say, what and how I do things currently is significantly influenced by the data structures in which I store(vert,tri etc) data (as usual). (e.g. lwo, x, im, pm, 3ds, obj types get loaded into one model class)


Share this post


Link to post
Share on other sites
The file format is what it is - you can't optimize the contents of the file. If the modeller wants smooth (or sharp - or both) models, the normals will be set correspondingly. For sharp ones, every triangle has three copies of the same normal, and it's perpendicular to the plane of the triangle. For smooth ones, every triangle has three different normals, with values that map one-to-one with the vertesx

So I don't really understand what the problem is. Are you trying to write code to "smooth" or "sharpen" existing models? What kind of in-memory data structure are you parsing the file into?

Share this post


Link to post
Share on other sites
Quote:
Original post by steven katic
Have you tried loading an ms3d with a displayed texture yet?
Notice any uv problems?

I haven't gotten the loader that does indexing to work yet, but this is a very good point you make here. The texcoords can also be different per tri. Hadn't thought about that yet.

Quote:
Original post by steven Zahlman
So I don't really understand what the problem is. Are you trying to write code to "smooth" or "sharpen" existing models? What kind of in-memory data structure are you parsing the file into?

I'm trying to write code that takes advantage of vertex indexing depending if a surface is smooth or sharp edged.
The problem is not the code or algorithm for that, the question is if it's worth the hassle and increased load times.


Let me elaborate:
Vertex A is part of a smooth surface. So its normal is the same for every triangle that vertex A is a part of.
Vertex B is part of a sharp edge, so its normal is different for every triangle that vertex B is part of.

For vertex A I can optimise the rendering by taking advantage of vertex indexing. Just store one vertex and one normal in memory and refer to that every time.

However, MS3D does not seem to differentiate between smooth and sharp surfaces.
For example, vertex A is shared by triangles X, Y and Z. These three triangles each store a separate normal for vertex A. Even if the the surface is smooth and the normal is the same for every triangle, it is stored three times.

The problem is that there is no easy way of telling if the surface is smooth or sharp. There is no flag that says "this one is smooth, so it's safe to use indexing" or "this is sharp, so duplicate the vertex".
In practice you'll have to look at all the normals of a vertex and compare them. If all the normals are the same you know it's a smooth surface, otherwise it's sharp.



So I'm facing a choice:
1) Write the algorithm that finds smooth surfaces by comparing the normals so I can use vertex indexing. This will increase load times.
2) Just duplicate the vertices even if the surface is smooth. This will increase rendering time for smooth surfaces.

I hope this is clearer (If it's not I blame the fact it's 7:30AM and I'm still on my first coffee).

Share this post


Link to post
Share on other sites
Quote:

I'm trying to write code that takes advantage of vertex indexing depending if a surface is smooth or sharp edged.

That's a new approach I haven't seen before...do you have a big
database programming background?(I guess I don't get around much).
Quote:

The problem is not the code or algorithm for that, the question is if it's worth the hassle and increased load times.


No.

(What are we talking about here, hundreds of triangles, or tens of thousands? )

still...

The short answer would still be...No..(for now).

Long (winded?) answer... still No...but:

The ms3d format is just about the only one (of the older well known ones) I have worked with that stores normals and uv's per triangle, as opposed to per vertex. And I presumed the purpose of that organisation was to minimize redundant vertex data...in the file.

Going to the other extreme of full on redundancy, you could store say a cube as ( a list of 36 verts(ordered set of 3 floats) 36 normals and 36 uvs) and triangle data made up of 12 tris (or 24 for double sided tris!) where a tri is an ordered set of 3 vertex indices...and maybe the kitchen sink to boot..der..[that's me trying to be funny]. Dump it all straight into memory, then perhaps into the graphics card (e.g. Vertex Buffer stuff: One large VBO or smaller numerous VBOs for thousands of cubes?) with minimal preprocessing.

Redundancy can be a good thing too.

However, for the same cube in an ms3d format file you would typically find
only 8 vertices and 12 triangles( where you still may get the same redundant normals and uvs,....just no redundant vertices). And you can index into the 8 vertices from the triangles at render time (very nicely in good ol' OpenGL immeadiate mode if you really feel the need to).

But you can also get stuck with preprocessing decisions such as these...and such as this topic.

To me it seems as though you have taken the intent of the ms3d format
(of reducing redundancy in the file) even further...out of the file and into your application..and to the extreme of micro-optimising something even before you have something to optimize?

Papers(and forum posts here) on Optimising (with regard to its philosophy, as opposed to specific implementaion strategies) might come in handy too.

Anyhow...back to the important point:
Quote:

So I'm facing a choice:
1) Write the algorithm that finds smooth surfaces by comparing the normals so I can use vertex indexing. This will increase load times.
2) Just duplicate the vertices even if the surface is smooth. This will increase rendering time for smooth surfaces.


Have you decided yet?

just pick one, and do it (personally I would do (2) since I already have(silly me)...and I see no real benefit in (1) without some specific purpose [ you haven't mentioned...apart from generally optimise]

Do it, and observe/profile/measure the performance against your requirements/expectations...(you may be pleasantly surprised..I usually am..)
and then start talking about optimising.

Programming is meant to be easily extensible these days (isn't it?),
so expect to continue to change/develop your code.

Obviously, you can disagree with me,
(and if so ...you certainly shouldn't feel compelled to jusify you disagreement)

Share this post


Link to post
Share on other sites
Personally I'd take a 2-phase approch to this;

1 - I wouldn't load ms3d files directly into my app, instead I'd come up with a more gpu-friendly version of the data and process the ms3d file into it in a build step somewhere

2 - the processing step basically takes the index of the vertex in the triangle and see's if it has already been used; if it is it compares the data to see if it is the same and if so just inserts another reference to that vertex into an index array. If it isn't, then a new vertex is generated and data duplicated, a new index inserted into the array and on we go.

Basically where where vertex A doesn't have the same normal and texture coords you need to duplicate the data so it is GPU friendly and can be accessed via a single index.

So, to take the cube example, the 8 positions would get expanded up to 24 for sharp edged cubes because the normals at each vertex (and thus each face) are different.

Share this post


Link to post
Share on other sites
Quote:
Original post by Structural
Let me elaborate:
Vertex A is part of a smooth surface. So its normal is the same for every triangle that vertex A is a part of.
Vertex B is part of a sharp edge, so its normal is different for every triangle that vertex B is part of.

For vertex A I can optimise the rendering by taking advantage of vertex indexing. Just store one vertex and one normal in memory and refer to that every time.


But vertex indexing can save space even for Vertex B - more accurately, for a set of "Vertices B". Note that different faces in the model can be coplanar, so that they coincidentally use common normal values.

And in the worst case, it will only cost you one index per vertex, which should be something like 33% overhead.

Quote:
So I'm facing a choice:
1) Write the algorithm that finds smooth surfaces by comparing the normals so I can use vertex indexing. This will increase load times.
2) Just duplicate the vertices even if the surface is smooth. This will increase rendering time for smooth surfaces.


Yep. The algorithm is not conceptually difficult (but be careful with comparing floating-point numbers!). Note that "load time" (once per... game level?) normally happens much less often than "rendering time" (once per frame). You can also pre-process the data (i.e. write a separate loading program that does the indexing work and then serializes a custom data structure to file, ready to be read "directly" by the main program).

Share this post


Link to post
Share on other sites
Quote:
Original post by steven katic
Quote:

I'm trying to write code that takes advantage of vertex indexing depending if a surface is smooth or sharp edged.

That's a new approach I haven't seen before...do you have a big
database programming background?(I guess I don't get around much).
Quote:

The problem is not the code or algorithm for that, the question is if it's worth the hassle and increased load times.


No.

(What are we talking about here, hundreds of triangles, or tens of thousands? )


No, no database programming background. I just saw a seemingly simple optimization: minimize geometry. I tried, found out it was not "seemingly simple", and came here for advice.

The general idea of the optimization is to take advantage of the GPU's vertex cache and to minimize the geometry sent over the bus.

Quote:

Quote:

So I'm facing a choice:
1) Write the algorithm that finds smooth surfaces by comparing the normals so I can use vertex indexing. This will increase load times.
2) Just duplicate the vertices even if the surface is smooth. This will increase rendering time for smooth surfaces.


Have you decided yet?

just pick one, and do it (personally I would do (2) since I already have(silly me)...and I see no real benefit in (1) without some specific purpose [ you haven't mentioned...apart from generally optimise]

Nope, haven't decided yet. The project is still in its infant stages, so it's not possible to decide if I'm really going to need the optimization as there is no game running yet. I just like to be prepared.


Quote:
Original post by phantom
Personally I'd take a 2-phase approch to this;

1 - I wouldn't load ms3d files directly into my app, instead I'd come up with a more gpu-friendly version of the data and process the ms3d file into it in a build step somewhere

...


Good idea, hadn't thought of using an intermediary processing step.


Quote:
Original post by Zahlman
Quote:
Original post by Structural
Let me elaborate:
Vertex A is part of a smooth surface. So its normal is the same for every triangle that vertex A is a part of.
Vertex B is part of a sharp edge, so its normal is different for every triangle that vertex B is part of.

For vertex A I can optimise the rendering by taking advantage of vertex indexing. Just store one vertex and one normal in memory and refer to that every time.


But vertex indexing can save space even for Vertex B - more accurately, for a set of "Vertices B". Note that different faces in the model can be coplanar, so that they coincidentally use common normal values.

In terms of memory usage that's true. But my worries are not memory usage, it's rendering and processing time.

Quote:
You can also pre-process the data (i.e. write a separate loading program that does the indexing work and then serializes a custom data structure to file, ready to be read "directly" by the main program).


As I said to phantom, indeed a good idea.

Share this post


Link to post
Share on other sites
Perhaps one other thing you can consider, apart from second (3rd,4th and 5th revised) opinions here,
is to apply computational complexity theory (e.g BigO notation) if you are
computer scientifically inclined with time to spare (bit like using the right tool for the job) to arrive at more concrete "theoretical" numbers(if they exist?) to help you decide.

Some posters have alluded to it in way
e.g.
Quote:

from Zahlman:

Note that "load time" (once per... game level?) normally happens much less often than "rendering time" (once per frame).


The initial (one off) complexity may be acceptable at load time, and (help) reduce it at render time?.... 'tis why I mention it.

Quote:

In terms of memory usage that's true. But my worries are not memory usage, it's rendering and processing time.


Typically there is (always?) an acceptable trade off between time and space(being a finder of these can be one of the best parts of a programmer's job description?) and computational complexity theory can be used to help you arrive at an optimal solution, just don't get too theortical 'bout it (you need be careful with it though[as usual?].

e.g. A simple example would be to look at phantom's sample solution. Since, it sounds like the best option so far.(And could end up being one of the most computationally expensive as well
[for each vertex in each tri, compare values of current vert with every other vert] what's that in worst case: polynomial time?). How long it takes depends on a few things: e.g. number of verts, how many normals are sharp, how many are smooth, best case, worst case (some other heavily theortical cases) and other assumptions you make about these expected amounts and acceptable load times vs
render time vs memory usage/alloc/destruction.

But still it wouldn't be as complex as computing normals (as I do at times) or maybe it is/could be [same...polynomial time?].
But there are usually ways around these things too[that's what programmers get paid to do..too, right?]:

let me digress a bit:
e.g. ...again..

for computing normals typically we need to loop thru each vertex
(find the number of triangles that share this vert;)
Each time we find a triangle that shares the current
vertex, we compute the triangle’s surface normal,and add it into a running tally. When we are done, we normalize the vertex normal,
and store it with the vertex. [Complexity O(n2)?].

For me this became an unacceptable bottle neck at some (worst case) load times:
(waiting an extra 2 or 3 seconds to see the loaded model: I hated it, 1 second or less would have been acceptable/expected for the sample models in question).

So I went about trying to find a way to get rid of the polynomial time complexity,.. quickly (i.e. use the first solution that gets the time under the 1 second load time for sample models in question):

So, typically the caveat here is: that the following is one solution and not necessarily the best(as usual) and hopefully clearly explained here to be useful:

A simple solution was to avoid looping thru the vertices and triangles
a second time (after loading them) in nested loops to compute the normals;
Instead, get what we need during triangle loading:
and with each vertex store
(1) the number of triangles that share it,and
(2) a list of the triangles (tri indices) that share it.

pseudocode:

struct Vertex { Position p, Normal n, SharedCount cnt, TriIndexList tl}
for each triangle t in the TriangleList
.....
for each vertexIndex vi in the triangle
increment the SharedCount of the vertex in the Model's VertexList
add the triangle index of triangle t to the TriIndexList of the vertex


We now have all the data we need to compute face and vertex normals,
so just loop thru, first the triangles,
to generate face normals, then loop thru the vertices computing
their normals (using SharedCount and the derived face normals of the
triangles that share the vertex accessed via TriIndexList):

for each triangle in the TriangleList
Triangle.ComputeFaceNormal()

for each Vertex in the VertexList
Vertex.ComputeNormal()

No doubt, phantom or Structural could do something similar to remove/avoid worst case polynomial time complexity in phantom's example (if even necessary).

Reading normals from the file is so much easier though isn't it? ;).

Anyhow back to the point: looking at computational complexity theory
may help.

[Edited by - steven katic on January 30, 2008 9:45:02 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this