Improving FPS of meshes -- general question

[syscrusher]

syscrusher -

Thank you very much for your info, but... it's something missing there I think :] You haven't explained what exactly one-sided or two-sided collision means :]

Well, I'm asking because I work with various collisions for years now, and read a lot of things about them in the past but never ever I've encountered such terms anywhere. This is the first time when I can read about one- or two-sided collisions. So without an understanding of the key element your posts about it aren't as valuable as they may be ;] So, please post two pictures - one with one sided collision and another with two-sided, or even better (if you want) - upload those two nifs with different collisions somewhere, so others could check them and learn something in the process :]

Really sorry about that! I didn't realize you were actually asking for information, as I thought the question about 2-sided meshes was rhetorical in the context of critiquing my test report. You were quite right to do so, as my results were reported with very ambiguous wording.

I don't want to upload my house mesh at this time, because that would become a publicly-posted spoiler for my quest mod, but I'll try to offer a more detailed explanation of what I meant.

The direction of the normal of a polygon in a visual mesh determines which of its two faces will be rendered with texture and which will not. For example, a house interior mesh typically has its walls' normals facing inward, so that you can see through the walls from outside to make it easier to work in the CS while cluttering. With a two-sided mesh, the polygon effectively has two normals, one facing each direction, so it is always eligible for rendering regardless of which side faces the camera.

For visual meshes, one-sided normals reduce the amount of processing by the GPU to render the textures, but not as much as you might think. It's physically impossible for any viewpoint to see both sides of a plane, so a well-designed GPU just has to figure out which side of a given polygon is potentially visible to the player camera, then render that side. It will not render both sides, ever. There is, however, still a performance gain if the rendering algorithm is smart enough. For any given polygon P, figure out which side of the mesh is facing the camera. If the mesh is one-sided, and the normal is facing the other way, skip rendering. The detection of which side faces the viewport camera is a relatively cheap computation compared to rendering. If the polygon is two-sided, this trivial rejection algorithm [1] doesn't gain you anything because all polygons will always pass the test and remain eligible for rendering.

In effect, the normal direction of a one-sided visible polygon is a way for the human model designer to give a mathematical hint to the GPU by pre-thinking which side of each polygon will never be seen by the player and can therefore be safely ignored.

Visual rendering only happens for the player's viewport camera, not for other objects in the game. The NPCs don't see anything; there are no NPC first-person cameras. This means that a lot of one-sided polygons can be excluded from rendering with a trivial-rejection algorithm based on normal facing. (If the NPCs actually could "see", then a given surface would have to be rendered if any of the viewpoint cameras could see it, not just the one belonging to the player, so fewer could be trivially rejected.) But as someone else pointed out, poly texturing is usually offloaded to the GPU, so the impact on frame rate may not be as high as one would intuitively expect. Still, on a complex mesh, it is likely to be nonzero.

For collision meshes, though, every Havok-enabled object in the cell is affected. Particles, projectile weapons, falling or rolling objects, objects being moved by the player, NPCs and all their carried swords and apparel have to be collisioned. The game engine also clearly is checking stationary Havok items (clutter etc.) for collision intersection, because otherwise we would not have the annoying bugs of food floating off of plates and poorly-placed clutter jumping off of shelves that we see from time to time in mods. In effect, each Havok item (including Actors) has its own "camera" (but not a vision camera) with respect to collision meshes.

Collision polygons are not textured, but typically are only checked for plane intersection with any edge [2] of a polygon on a Havok object. But because this test has to be done for multiple Havok items (including Actors), and because it has to be done by the CPU and not the GPU on many systems, there is something to be gained by being able to trivially reject collision polygons whose normals face away from both ends of the edge under test. [3] On the other hand, the algorithm in [2] provides the directionality of a collision as a by-product of detecting that the collision exists, so in effect it has calculated both sides of the face in one step if the software is well-designed. Even so, potential hits on the limitless plane still have to be refined to see if the intersection point lies within the finite triangle of the face under test; that's not a complex calculation, but it is still a calculation.

So we have two opposing factors to consider here: First, there is less to gain from trivial rejection, per polygon intersection test, for collision meshes than for visual meshes because collision meshes do not have to be texture-rendered and because at least one commonly-used algorithm can compute two-sided and one-sided collision in one step. Conversely, there are more intersection tests needed per polygon for collision meshes than for visible meshes because more than one "viewpoint" has to be considered; a small improvement becomes more significant if you have to do the calculation more times. These opposing influences make it more complicated to predict how much of an impact switching from a two-sided mesh to a one-sided mesh will make. Further, although I cite a common published detection algorithm below, it is not the only such algorithm, and we don't know exactly what Bethesda is using, nor do we know how much (if any) of this process can be offloaded onto the video card.

What we are left with is this: Assuming Bethesda is using this fairly typical collision detection algorithm, or something similar to it, the underlying mathematics suggests that one-sided versus two-sided collision meshes should make only a small difference. We have at least one post in this thread from someone who has observed that arrows and other projectiles go through one-sided meshes, which proves Bethesda is taking the normals into account in their collision detection, but that doesn't imply they do it for performance reasons. And we have my test results, which do -- for whatever reason -- show a performance gain with the one-sided collision mesh, but which I am now beginning to question because I understand the math better now, and this shouldn't make as much difference as what I observed.

To muddy the waters further, our testing process is not precisely repeatable. FPS rates vary depending on how NPCs in the area are moving, exactly where the player is standing, and pseudo-random variations in system CPU load from all the other programs that are running in the background while you are looking at Oblivion in full-screen foreground. If I run my test three times, and try to stand at exactly the same point, I may get FPS rates of 28, 31, and 30 and report it as "about 30 FPS", but it does vary slightly over time.

I did run several tests with the one-sided versus two-sided collision meshes, same number of polygons, and reported an approximate average before/after result. But "several" tests is admittedly not enough to rule out the possibility that something else besides the 1S/2S change was affecting the results. Maybe my system was checking for Windows updates in the background during the 2S test but not the 1S test, for example. I am convinced there is a difference and that on my system it is about 15% with the particular cluttered and lighted house mesh I am testing, and about 35% if I took the same house mesh into an otherwise-empty test cell, but your mileage may vary.

What I can say is that at a certain approximate player position inside the house, I was consistently seeing frame rates below 20 FPS most of the time before I started this process, and that I'm seeing frame rates above 30 FPS most of the time now. I observed similar percentage gains in other areas of the house, although the absolute numbers vary widely depending on where you are standing. I attribute most of the improvement to the changes in lighting, as others have suggested, but I do believe there is at least some improvement due to the one-sided collision mesh. However, now that I look at the underlying mathematics, I am surprised that I observed 15% or more rather than just a small change, and I am beginning to wonder if I observed a repeatable improvement or a transient fluke due to system load, NPC movement, or some other factor.

As a next step, I'm going to take the NPCs out of the cell and run the comparison a few more times, restarting the game between each observation, to see if I can determine whether I really saw an improvement or just happened to catch a lucky break on my background CPU load. I may not have time to do this tonight, as I have to run a meeting of the local beekeepers' club, but I will post the results here. As an engineer, I would much rather verify or disprove my hypothesis and arrive at the truth, even if it means admitting my initial test results with the one-sided mesh were a fluke. I hope to gather enough repeatable data in the next couple of days to draw a reliable conclusion about whether or not one-sided versus two-sided collision meshes really do matter.

As an aside, when I went looking for descriptions of the detection algorithms to cite the mathematics, I went first to a reference book I have for computer graphics algorithms, thinking they haven't changed much since the book was published. {ahem} Wrong. The book I have assumes that you will mathematically calculate the position of every pixel on a raster screen, or of every line segment endpoint on a vector screen (!!!!) directly from the physics and geometric parameters of the scene. It never mentions rendering surfaces as polygons, because at that time you didn't render that way. And collision detection isn't even discussed, because at that time animating a non-trivial 3D scene in realtime was impossible. The underlying rules of geometry and mathematics haven't changed, but the way the hardware works has changed fundamentally since the book was published in 1976. I guess it's time for a new edition.

Kind regards,

Syscrusher

---

[1] The purpose of trivial rejection algorithms is to quickly scan a list of prospective matches and discard as many as possible with the least effort. The presumption is that the majority of candidates can be rejected with a trivial, low-CPU algorithm, leaving more machine cycles free to apply a more precise and complex algorithm to the few that remain. For example, suppose you are in a gymnasium whose floor is completely covered with balls of different sizes and types. You are told that five green tennis balls have diamonds inside. Your brain will immediately trivial-reject everything except green tennis balls, because you can easily do this with a quick visual scan. Having rid yourself of the 90% or more non-tennis balls and the remaining non-green tennis balls, you now take a knife to the small number of green tennis balls and quickly recover the diamonds.

[2] The published mathematics I was able to find suggests that 3D intersection algorithms typically look for intersection of an edge rather than trying to intersect polygon with polygon. If you want to find out if polygon P1, described by points P1a, P1b, and P1c, intersects polygon P2 (with points P2a, P2b, and P2c), the typical approach is to project P2 to an infinite plane P2I, then check each of the line segments (P1a, P1b), (P1b, P1c), and (P1c, P1a) for intersection. If none of these line segments intersect infinite plane P2I, then the two finite polygons do not intersect. This algorithm will get some false-positives because it is possible for a line segment to intersect P2I but not actually intersect P2 (the finite plane). However, the rejections are definitive, so this simple algorithm can be used as a trivial-reject filter, and then the positives can be treated as "possibles" for rechecking with a more definitive algorithm. Some further discussion of the mathematics can be found here: http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm#Intersect%20Segment%20and%20Polyhedron .

[3] It is noteworthy that the published algorithm cited in [2] specifically states that a directional normal is used to determine on which side of the plane each of the two endpoints of the segment under test lies. In the page cited, they use this information to determine whether the vector of the line segment is entering or leaving the enclosed polyhedra, but in our context this same information will tell us whether a prospective intersecting polygon is colliding from the active or the inactive face of a one-sided collision polygon. A positive here, again, is non-definitive for overall collision detection, but a negative is definitive for rejection relative to this particular face of each of the two potentially colliding polyhedra.

[Khettienna]

And here's something more interesting too!!! Pyffiing the meshes got them both to be 179 kb !

Somewhat off-topic personal anecdote:

I mushed some pieces together in to make a large static mesh and gave it a new simple box collision, all in Nifskope. The mesh was about 800 KB. I wondered if I could do a cleaner job in Blender, so I imported the mesh, cleaned up some excess stuff that would no longer be visible, and re-exported. The exported mesh was 9 MB! So as a test, I ran both meshes through Pyffi. It had no effect on the size of the mesh I'd re-exported, but it turned the 800 KB Nifskope mash into 9 MB also! However, I couldn't find any technical differences between the meshes. I am sure there were some, but it would probably take a more experienced eye to see.

So then I did an FPS test on both meshes. The cell containing the object was fairly heavily cluttered, and I couldn't add much more to it before gameplay would stop being buttery (at least on my machine). The 800 KB mesh I already had in there was fine. But the 9 MB mesh doubled my loading time almost, and I could feel the greater strain on my system panning around the room. So I am sticking with my slightly-messier 800 KB version that, for reasons I cannot explain, just works better.

[syscrusher]

I wasn't so precise there I admit ;] I put everything to the same bucket to make post shorter, but it doesn't change that much anyway.

Of course the direction of normals is important for arrows or particles (and is recorded in collision data), and it changes nothing for the player (he still is blocked from both sides). But the double sided feature does exactly nothing - the collision is exported and works as it has only one side enabled.

The player is not necessarily blocked from both sides. I've had cases where I accidentally made one-sided collision polygons pointing the wrong way, and my character fell through the floor in testing.

[syscrusher]

Somewhat off-topic personal anecdote:

I mushed some pieces together in to make a large static mesh and gave it a new simple box collision, all in Nifskope. The mesh was about 800 KB. I wondered if I could do a cleaner job in Blender, so I imported the mesh, cleaned up some excess stuff that would no longer be visible, and re-exported. The exported mesh was 9 MB! So as a test, I ran both meshes through Pyffi. It had no effect on the size of the mesh I'd re-exported, but it turned the 800 KB Nifskope mash into 9 MB also! However, I couldn't find any technical differences between the meshes. I am sure there were some, but it would probably take a more experienced eye to see.

I have noticed in some vanilla meshes that they seem to have both textured and collision nodes that point to the same triangular mesh record. I wonder if the game engine does some smart caching of its calculations such that reusing a large mesh can be more efficient, overall, than using a smaller mesh dedicated just to collision.

This whole thread is leading me to wonder what kind of power-tools the folks at Bethesda must have access to, in order to be able to rigorously test things like this. You know they must be doing it, but it would take some really specialized test harnesses to be able to fully control the test conditions.

[Artisanix]

syscrusher -

forgive me to not commenting on your long post now, as it's quite late and I haven't read it carefully yet, but in the meantime I carried out some few simple tests and now need to take some sleep... ;]

I created a simple plane, then duplicated it and created collision with exactly the same shape. Double sided button was unchecked for both (plane and its collision) all normals were facing in the same direction.

Then I dropped four copies of this plane into the testing hall cell. Two in horizontal and two in vertical position, and the two rotated 180 degrees to face in opposite directions. And here are the results:

- this plane is impassable for player no matter in which direction normals are facing - vertical plane acted as wall and horizontal as floor (my character wasn't falling down at all through the normal plane and through the plane with inverted normals),

- such plane also acted as a barrier for all the spells - those couldn't pass through no matter from what direction they were fired,

- the only exception were arrows - as I set collision's properties to be made of stone, the arrows shot from one side were blocked by the collision and fired from the other they passed through it like nothing was there.

Then I imported this plane into the Blender and enabled double sided button for both the plane and its collision and exported that to check the difference. Well... there wasn't any at all. The collision behaved like one sided and there was no difference in file size or collision's properties...

So, I'm still quite skeptical here... I understand that you do not want to give away your house mesh so freely ;] but in fact it is not needed that much. What should be enough for me to test is any kind of mesh with such double-sided collision. So if you would be so kind to generate some simple object (even without textures or materials applied) and create such double sided collision for it - that would be perfect. Because as all the examples here show so far, Blender can't generate such double-sided collisions (or at least no one here shared the way how to do so ;]).

[Arthmoor]

Figured I'd toss in my own anecdotal bit of info.

In two mods, I'm using the Nordic Tomb tileset. In the course of testing the second mod to use this set, items placed on the meshes were vanishing and I couldn't figure out why. So in an act of in-game frustration I had the character throw a sword at the wall. Needless to say I was surprised when the sword fell right through the mesh and disappeared into the void. It didn't take long to realize that the collision on a few of the pieces in that tileset had this "one sided" problem where stuff, and more than just arrows, would fall through never to be seen again.

Of course I had no idea how to fix it, and still don't, so I asked for help. Phitt figured out that the collision on the affected pieces had "flipped normals" and he was able to correct that. No more stuff falling through.

During the whole mess of course, the player was never affected by it.

[syscrusher]

So, I'm still quite skeptical here... I understand that you do not want to give away your house mesh so freely ;] but in fact it is not needed that much. What should be enough for me to test is any kind of mesh with such double-sided collision. So if you would be so kind to generate some simple object (even without textures or materials applied) and create such double sided collision for it - that would be perfect. Because as all the examples here show so far, Blender can't generate such double-sided collisions (or at least no one here shared the way how to do so ;]).

[Artisanix]

Arthmoor -

That's exactly what my tests have shown... luckily such things like inverted normals on collision are easy to test/spot if you have some experience working with them.

Though very rarely still there may be other cases of similar behaviors where the culprit is broken collision data or some other obscured and inaccurate settings - then just re-exporting collision may fix that without actually any other changes to it.

syscrusher -

Glad we had this long though interesting discussion, as it put some things into various perspectives for us ;] And that is always beneficial.

And your beginnings wasn't that much different from mine or others. As modding for Oblivion may always surprise you even while you think that you've seen it all ;]

For instance I remember an interesting behavior from one of my collision in the past - that was a wooden floor and during the tests everything was fine - player could walk on it with proper sounds, arrow fired at it sticked properly from the floor, etc. great! But everything changed when second arrow was fired ;p Then it just passed through the floor as it had no collision at all, and player and clutter objects on it were starting to sink into the floor then :> Well, can someone try to explain that? ;]

Anyway, as this is a thread about optimizations, I can share something that I observed many times but the consequences of it are rarely discussed ;]

I mean that I've seen many posts and requests on these and official forums how to convert misc/clutter objects to statics. And most of the time the answer is to change particular collision's settings in NifSkope. While this is the easiest way to have such change to object's behavior done and often the only way for someone who has a zero experience in modeling applications, it is not the best way to do so as it may affect performance greatly in some cases.

The main culprit is the convex collision here. While swords and other weapons usually have the simplest of all shapes as collisions (cylinders or boxes), so "converting" them to statics in NifSkope won't hurt the performance much. But it is much different for all other misc objects that have convex type collision (like all pottery, potions,etc.). The same with beginning modders that start their adventure with Blender - I've seen many complex objects (released even as resources used later by others) with convex type of collision. Well, I can only presume that it is caused by a relatively easy way to generate such collision (scripts -> hull -> convex).

And the problem with convex collision is that it is not optimized at all for static objects and in same cases it may reduce performance by really significant amounts. That is true especially for very complex models like miniature statues, buildings, ships, etc. if they have convex type collision the performance may drop even by a dozens of FPS when these objects are being viewed from certain angles.

To fix this is to either create a new collision from scratch manually or just change draw properties of such convex collision to polyheder type in Blender. This on export will make it as hkPackedNiTriStripsData and generate additional bhkMoppBvTreeShape block which contains optimized data related to this collision. The difference in performance between "pure" convex collision and the collision that has exactly the same shape and which was changed to polyheder type (NiTriStrips/Shape) may be sometimes quite huge, and it gets greater the more complex object and its collision shape are.

Well, these are my small 2c to this topic ;]

[syscrusher]

Arthmoor -

That's exactly what my tests have shown... luckily such things like inverted normals on collision are easy to test/spot if you have some experience working with them.

Though very rarely still there may be other cases of similar behaviors where the culprit is broken collision data or some other obscured and inaccurate settings - then just re-exporting collision may fix that without actually any other changes to it.

[Artisanix]

It's nothing wrong with using convex hull script, but it's good to know such collision properties and limitations, and how it is different from other types.

What I meant there is that in some cases more important is the type of collision than its shape. You can have more complex collision that has far more vertices than much simpler one, and yet it will be more efficient and performance friendly than the latter. And that's because of inaccurate types of collision assigned and not their shapes.

Second, I'd like to hear more about the draw properties being set to Polyhedr in Blender. I have always done that with convex hull meshes, because when I use the script the default draw type leaves that dropdown empty.

[syscrusher]

It's nothing wrong with using convex hull script, but it's good to know such collision properties and limitations, and how it is different from other types. (...snip...)

Thanks, Trollf, for a great post. I didn't know that about "true" convex hull; it never occurred to me that a missing value from a selection dropdown would be an implied choice in and of itself. I'll keep that in mind.