3d model tool: autoflip

Custom 3d models, houses, etc. for Return To Wonderland.
Post Reply
LinkyNStoof
Rainbow Master
Posts: 539
Joined: Tue Jan 06, 2004 1:06 am

3d model tool: autoflip

Post by LinkyNStoof » Fri Aug 27, 2004 12:24 pm

As I've mentioned sometime before, I have been trying to write a program to make it easier to deal with the problem Popo and I have run into with certain 3D models that uses 2-sided surfaces. With such models, since Wonderland always treats surfaces as 1-sided, you get a lot of triangular "holes" in those models from surfaces that aren't facing the right direction.

Well, I'm proud to annouce that my program is near completion at this point! I guess this isn't of much interest to most people here, but I think Popo at least will find this to be good news.

I do want to say right now that it's not going to be completely automatic, unfortunately. A completely automatic solution is probably a bit too tricky for me to program. But I do have something that works nearly automatically.

The attached screenshots illustrates what I could do now with my program, which has been named "autoflip". We start off with a model of a castle, which I think Popo has seen before. In its original version, there are major problems when displayed in Wonderland.

At one point some months ago, I suggest that maybe we can fix this kind of problem by taking the model, making a duplicate copy, flip the surfaces' facing direction on the duplicate, and then place the duplicate at the exact same position as the original. The idea being that now for each position where there was one surface in the original, in this new model, you'll have two surfaces, and one of them is guaranteed to face in the correct direction.

The result of that suggestion can be seen in the middle screenshot. You no longer have those ugly holes. Unfortunately, the triangles don't blend together very well, and so you can still see the individual triangles, especially on very flat surfaces. Not good.

Finally, in the last screenshot, we see now how my program can help fix the model in mere seconds. We first take the original model, and run it through my program "autoflip". Then we do the "duplicate and flip" as we did before. But whereas doing "duplicate and flip" on the raw model didn't work too well (screenshot 2), doing "duplicate and flip" on the autoflip-ed model works much better (screenshot 3)!

===============

The only thing that really remains for me to do before releasing the program here is to add the file open/save dialog boxes (right now I just hardcoded the filenames the program uses into the program), and also to create some sort of help file.

The concept behind autoflip is actually very simple. The key idea is that adjacent triangles, that is, two triangles sharing an edge, should have the same facing direction. So the program basically starts off with a triangle, assume that it has the right facing direction, and then propagate this facing direction from adjacent triangles to adjacent triangles. So whereas before you might have one big connected surface made of numerous triangles in random facing directions, after autoflip, they are all made to face the same facing direction.

This by itself would've fixed the problem, except notice that I have to start off picking some triangle and assume that it is facing in the right direction. So if the triangle I picked to start off is actually not facing the right direction, then you'll end up with a group of adjacent triangles all facing the wrong direction instead of all facing the right direction. This is why I couldn't get the program to be completely automatic. However, because the triangles' facing directions are now more consistent across a continuous surface, you can now use the "duplicate-and-flip" strategy and it'll work much better than before you did autoflip, as you can see in the screenshots.

=======

Anyway, I'm expecting to get the program ready for public release by this Sunday or so, if not earlier.

Oh yeah, if anyone thinks of a better name then "autoflip" for this program, feel free to suggest other names. :wink:
You do not have the required permissions to view the files attached to this post.
User avatar
popo
Rainbow AllStar
Posts: 4179
Joined: Fri Jan 23, 2004 1:07 pm

Post by popo » Fri Aug 27, 2004 12:50 pm

That looks much better LNS. :D

From reading your synopsis (?!?) above I gather that Wonderland won't display 2 sided faces. Does this mean that if I set 2 sided faces in AC3D I will still have trouble? I ask this because I have a model of a bench that had some faces the wrong way but when I made them 2 sided in AC3D it looked ok. But in the game it still looked wrong. Is that why it still doesn't look right?

Also, once you have 'autoflipped' the surfaces, why do you still have to 'duplicate and flip' them? Or would you only have to do it if you picked a wrong facing triangle in the first place?

I'm afraid I won't be around to beta test it for you if you get it out this weekend, perhaps Robbie could help out with that.

BTW is it just for use with Milkshape or any 3D program?
Pauline
LinkyNStoof
Rainbow Master
Posts: 539
Joined: Tue Jan 06, 2004 1:06 am

Post by LinkyNStoof » Sat Aug 28, 2004 1:28 am

popo wrote:From reading your synopsis (?!?) above I gather that Wonderland won't display 2 sided faces. Does this mean that if I set 2 sided faces in AC3D I will still have trouble? I ask this because I have a model of a bench that had some faces the wrong way but when I made them 2 sided in AC3D it looked ok. But in the game it still looked wrong. Is that why it still doesn't look right?
Yeah, in fact, most of the models I've worked with show up fine in AC3D, but not in the game. So it looks like Wonderland ignores the 2-sidedness. This is why I asked Patrick whether he could support 2-sidedness but he said no.
Popo wrote:BTW is it just for use with Milkshape or any 3D program?
It'll work with any 3D program, however, for the "duplicate and flip" part that you have to do yourself, AC3D provides much better support for it. In AC3D, you just select the whole model as a Group, do a copy, and then do a paste to get the duplicate, conveniently placed at the exact same location as the original. Then go to the menus and select "Reverse Vertex Order" and voila, you're done!

In Milkshape, it looks like you have to duplicate stuff group by group (remember that Milkshape's "group" = AC3D's "object"), and sometimes it looks like materials aren't handled correctly during duplication.
Popo wrote:Also, once you have 'autoflipped' the surfaces, why do you still have to 'duplicate and flip' them? Or would you only have to do it if you picked a wrong facing triangle in the first place?
I guess I should've explained it a little better (hence the help file in the released version). Ok, get ready for a slightly long explanation.

The thing is, my method relies on adjacent triangles. But in most 3D models you will get a number of disjoint surfaces where there are no adjacent triangles from one surface to another. For example, take the 4 wheels of a car. The triangles that make up each wheel will likely be all connected together in terms of adjacency; however, no triangle from one wheel will be adjacent to any triangles on the other wheels.

My method propagates the vertex order from adjacent triangles to adjacent triangles. As a result, it has to process disjoint surfaces independently. For example, with the 4 wheels, suppose my program starts off with a triangle on the front-left wheel. By propagating through adjacencies, the most you could cover are all the triangles on the front-left wheel, but you can't ever get to the other three wheels, because no triangles on the other wheels will be adjacent to a triangle on the front-left wheel. As a result, in order to process the other 3 wheels as well, you've have to do the propagation process once for each wheel.

Now here's the catch. My method always has to start off with a triangle that it assumes has the correct vertex order, and then propagates its vertex order through adjacencies. But currently I haven't found an easy-to-program way to actually get my program to pick a triangle that truly has the correct vertex order; instead my program just picks the first triangle listed in the file. As a result, it might either get a whole set of adjacent triangles all correct, or all incorrect. Now, because the propagation has to be done independently for each disjoint surface, it might be that it'll get some of the surfaces correct, but others incorrect. For example, with the 4 wheels, since each wheel is processed independently of the others, it might be that 2 of the wheels has the correct vertex order, but the other two aren't.

So to fix this, you have two choices. One, you go thru the model yourself, selecting the triangles that have the wrong vertex order, and then flip them. This sounds like zero improvement from before, but actually this isn't so bad, for two reasons:

1) after autoflip, adjacent triangles will have the same vertex order. So instead of having incorrect triangles scattered randomly throughout a surface, you end up with swaths of correct triangles and swaths of incorrect triangles. This should make it easier to select the incorrect ones.

2) it's often the case that a swath of incorrect triangles corresponds to a group/object, so rather than selecting the triangles, you could just select the group/object and then do the flip.

Still, this takes a bit of work, and moreover, in some cases you simply cannot fix the problem by flipping. For example, in the castle model, if you look at the drawbridge on the front, you'll see that it's only a 2D rectangle. Because of its angle, depending on how far you are from the castle, you get to see the rectangle both from its bottom side and from its top side. And so no matter which way you flip them, the bridge will disappear in one of the two possible views (top/bottom).

In order to fix this sort of problem, you really have to make a duplicate of the rectangle with the vertex order reversed. That way, no matter which view you're looking at the drawbridge from, either the original or the duplicate will have the correct vertex order, and so the drawbridge will never disappear. It's this general technique that I called "duplicate and flip", and it works on any kinds of surface.

And so that's why I recommend you to just do a duplicate and flip on the entire model, rather than going through the model parts by parts to flip/fix them. Of course, you do end up with twice the number of triangles after duplicate-and-flip.

-----------

One possibility as you suggest is to let the user pick the correct starting triangles for each disjoint surface. However, to do this, I'd need to write program to display the model, and allow the user to zoom/rotate/move around the model's 3d space in order to select the triangle to use. In short, I'd have to implement some of the functionalities you get in Milkshape/AC3D. Since I'm not really too experience in 3D graphics programming, I'd rather not have to do this.

One possibility I have considered is to have the program restructure the model so that each disjoint surface gets its own group/object. That way, you never have to select triangles directly, you can just select the group/object corresponding to the incorrect swath of triangles and then flip. The only thing is, it's actually somewhat involved to write a program to do this, because of the format of the 3ds files. It could be done, but unless you're really finding the duplicate-and-flip to be inadequate, I'd rather not have to write additional code to support this.

One other possibility is to have autoflip do the duplicate-and-flip for you as the step after it processed all the triangles. This is still somewhat involved to write a program to do, but not as bad. On the other hand, in some cases you might not want to fix the model via duplicate-and-flip. For example, after I did autoflip on that model of a frog I posted, I was able to just go through about 3 or 4 groups/objects and flip them to completely fix the model. This takes only a few minutes and avoids having to double the number of triangles you have, so in this case you might not want autoflip to impose the duplicate-and-flip upon you.

So yeah, the program as is right now could use some improvement, but hopefully it'll still be useful enough to be worth your time. I'd especially like to see whether, for example, it'll enable you to utilize the plant-making program Robbie (or is it sfseaman) pointed out.

And enjoy your vacation!
User avatar
popo
Rainbow AllStar
Posts: 4179
Joined: Fri Jan 23, 2004 1:07 pm

Post by popo » Sat Aug 28, 2004 8:21 am

Right, I understand now. :D Making the areas of wrong facing triangles bigger would ease doing 'reverse vertex order' if you didn't want to duplicate the whole model.

Doubling the triangles might make some models impossible to use. That would certainly be the case for the plant program as the plants already have very high polygon counts.

I am certainly looking forward to trying it out, and when I said Robbie could beta test it for you I actually meant Steve (I can't help it, I'm getting old!), but better still they could both do it.

Anything that helps in any way can't be a bad thing. There's so much to this modelling thing I really don't know how people manage to make such detailed models. I've read the AC3D forum and the things they talk about goes straight over my head. The rest of the Wonderland family think we're clever for doing the things we've done, but we haven't even scratched the surface. Whenever I see 3D graphics on TV I'm in awe of the people who do it. :shock:
Pauline
LinkyNStoof
Rainbow Master
Posts: 539
Joined: Tue Jan 06, 2004 1:06 am

Post by LinkyNStoof » Sat Aug 28, 2004 10:00 am

Ok, I'm going to post the program now.

I said I was going to include a help file along with it. However, I think I more or less gave a reasonably detailed explanation here, so for now I'll skip out on the help file. The program itself is so easy to use anyway.

The program file is in the attached zip. No setup required, just unzip the program to some convenient location like the desktop, and run by double-clicking on it.

Considering Popo's comments, I might consider making a new version later that regroups the triangles to make it easier to flip swaths of wrong triangles. But probably not until I finish w/ the custom floor generator first.

[edit: version 1.0 has been deleted. Please download version 1.1 instead.]
Last edited by LinkyNStoof on Sun Aug 29, 2004 8:34 am, edited 1 time in total.
LinkyNStoof
Rainbow Master
Posts: 539
Joined: Tue Jan 06, 2004 1:06 am

Post by LinkyNStoof » Sat Aug 28, 2004 10:16 am

After some thought, I thought of a trick I could use that could potentially make the program produce much less swaths of "wrong" triangles.

I'll look into it a little more and maybe get the next version of AutoFlip out in a week or two. In the meanwhile, feedback on version 1.0 are welcome.
User avatar
popo
Rainbow AllStar
Posts: 4179
Joined: Fri Jan 23, 2004 1:07 pm

Post by popo » Sat Aug 28, 2004 1:33 pm

I've downloaded it but won't have time to try it until I get back from my holidays (in the middle of packing right now :roll: ). You may well have the other one ready by then. 8)

Hope someone else gives it a try before I get back so I can read any comments. :D
Pauline
User avatar
popo
Rainbow AllStar
Posts: 4179
Joined: Fri Jan 23, 2004 1:07 pm

Post by popo » Sat Aug 28, 2004 8:07 pm

I gave it a quick go, tried to open the bench I mentioned, got a 'autoflip has encountered an problem and needs to close' error message. :?

Tried it on another model, and that worked, but when I looked at it in Milkshape it didn't look any different. But it wasn't a model that had any wrong facing triangles, so I don't know if that made a difference.

One thing I'm not sure about is, when I open a model in autoflip and it tells me it's completed the flip and asks me where to save it, what happens to the original model? Does it stay as it was originally and I save the flipped model as a separate item, or does it change the original model?
Pauline
LinkyNStoof
Rainbow Master
Posts: 539
Joined: Tue Jan 06, 2004 1:06 am

Post by LinkyNStoof » Sat Aug 28, 2004 10:26 pm

popo wrote:I gave it a quick go, tried to open the bench I mentioned, got a 'autoflip has encountered an problem and needs to close' error message. :?
Hmm, that's not good. Can you PM me the model so I can check why my program crashed?
popo wrote:But it wasn't a model that had any wrong facing triangles, so I don't know if that made a difference.
Well yeah, if there are no wrong facing triangles, there's nothing to fix so it wouldn't do anything. :wink:
popo wrote:One thing I'm not sure about is, when I open a model in autoflip and it tells me it's completed the flip and asks me where to save it, what happens to the original model? Does it stay as it was originally and I save the flipped model as a separate item, or does it change the original model?
Ah, I guess I do need a help file after all eh? The original model stays as is, and you save the flipped model as a separate item. You can, of course, choose to save the flipped model back to the same file as the original model (thereby overwriting it).

I felt it was a good idea to leave the original model untouched, just in case 1) my program really screwed up and spits out a garbage file that can't be opened; and 2) my program didn't screw up, but what it did wasn't too helpful that you'd rather manually flip triangles on the original model instead. As I said, if you feel confident enough about the program, you can always choose to save the result back to the original file.
LinkyNStoof
Rainbow Master
Posts: 539
Joined: Tue Jan 06, 2004 1:06 am

Post by LinkyNStoof » Sat Aug 28, 2004 10:42 pm

popo wrote:Tried it on another model, and that worked, but when I looked at it in Milkshape it didn't look any different. But it wasn't a model that had any wrong facing triangles, so I don't know if that made a difference.
I should also mention that some models might have its triangles marked as 2-sided, so it'll show up fine in Milkshape and AC3D. But as you've observed, it'll still be wrong in the game, because Wonderland always treat the triangles as one-sided.

In AC3D you can set the triangles to one-sided, so you might want to do that to get a more accurate picture of what the model would look like in Wonderland. I don't know if it's possible to set triangles to one-sided in Milkshape.

[edit: I checked. Milkshape also seems to ignore whether the triangles are marked as one-sided or two-sided. However, you can set it so that all triangles are displayed as two-sided, or as one-sided. To do so, right-click on the 3D perspective view panel, and at the popup menu, make sure to clear the checkmark on "Draw BackFaces". This will cause all triangles to be displayed as one-sided, just as in Wonderland.]
LinkyNStoof
Rainbow Master
Posts: 539
Joined: Tue Jan 06, 2004 1:06 am

Post by LinkyNStoof » Sun Aug 29, 2004 8:37 am

LinkyNStoof wrote:
popo wrote:I gave it a quick go, tried to open the bench I mentioned, got a 'autoflip has encountered an problem and needs to close' error message. :?
Hmm, that's not good. Can you PM me the model so I can check why my program crashed?
Woohoo!!!! 8) With Popo's model, I was able to not only reproduce the crash, but was able to diagnose what causes it.

A few changes have been made to my program to fix the problem, and now my program handles Popo's model just fine. :D

So here it is, ladies and gentleman, AutoFlip version 1.1.
You do not have the required permissions to view the files attached to this post.
User avatar
Robbie
Rainbow Wizard
Posts: 456
Joined: Wed Nov 26, 2003 12:00 pm

Post by Robbie » Sun Aug 29, 2004 10:45 am

Pauline wrote
I am certainly looking forward to trying it out, and when I said Robbie could beta test it for you I actually meant Steve (I can't help it, I'm getting old!), but better still they could both do it.
Nice work LnS - I'm still not sure about all this yet though so testing might be a bit beyond me at the moment. Just haven't had much time to really get much further into anything. Still working on understanding the really basic stuff.


Robbie :D
You do not have the required permissions to view the files attached to this post.
LinkyNStoof
Rainbow Master
Posts: 539
Joined: Tue Jan 06, 2004 1:06 am

Post by LinkyNStoof » Mon Aug 30, 2004 9:13 am

Ok, I'm now releasing version 1.8 of AutoFlip. (It would've been 2.0, but I felt at this point I might be able to tweak it just a bit more, so I don't want to go all the way to 2.0 just yet.)

The main thing about this version is, I made the program slightly smarter, so that it's more likely (or so I hope) to do the right thing. So hopefully you should be seeing more swaths of "correct" triangles and less swaths of "incorrect" triangles. I'll still keep version 1.1 around, just in case you have a model that you find works better on 1.1 than on 1.8. (If you're going to keep both versions around, you might want to rename 1.1 to something besides AutoFlip, or place the old one in another folder.)

For example, I tried it on Popo's bench, my frog, my beetle, and that castle. With the old program, Popo's bench has all the triangles facing the wrong direction, the frog's torso and legs are "wrong", my beetle's shell is "wrong", and there are quite a number of "wrong" swaths of triangles with the castle. With the new program, Popo's bench comes out completely corrected (true to the name "autoFlip" :wink: ), the frog's torso and legs are now correct (but the lotus leaf became wrong), the beetle's shell is "right", and finally the castle has much less swaths of incorrectness.

The program will still make mistakes however, particularly if you have a big, perfectly flat surface made of numerous triangles. This is because my program now relies on what's effectively the surface curvature to make decisions about flipping (in addition to the old method of making adjacent triangles consistent in their vertex order), and with a completely flat surface there's just no curvature. Also, if you have surfaces that are very bumpy, it will also likely mislead the program, though fortunately this latter kind of surfaces are somewhat rare.
You do not have the required permissions to view the files attached to this post.
Post Reply