Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

ageny6

Speed of transformation

This topic is 5281 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Rather than writing a huge paragraph on what the scenario is, i''ll just get right to the point. We have a set a 3D coordinates that must be transformed into 2D coords. All the 3D coords are stored in an array (for fast indexing), and there comes a crucial point where the manner in which those 3D coords are transformed is important. Now, i'' ve boiled down the manner in which I transform my point to two solutions. 1-> Only transform the points that need to be transformed, and make sure that they are transformed only once. This, in terms of the amount of matrix multiplication, is fast. However, to make sure that the points are only transformed once, a temporairy array of booleans has to be used. For example, if point 1 has just been transformed, the array of booleans at index 1 is turned true. If a later request for transformation of point 1 is demanded, a quick check at the boolean array will indicate that this point is already transformed, and therefore that it does not need to be transformed again. However, at the frameMove, all the booleans have to be turned to false in order to permit the new transformations to take place. This has O(n) complexity, which is very bad. Then, rather than iterating through the boolean array and making each boolean false, I attempted something like
 booleanList = new bool [size];  
or
redim booleanList(0 to size-1) as boolean 
for the VB people Still, reallocating memory every frameMove does not sound like a fast operation, expecially when the booleanList is very large. Thus came about the second option. 2) Don''t even bother with limiting the transformation of point and transform them all once. Sure, we have a lot more matrix multiplications to perform, but we don''t have the issue of the cumbersome booleanList. So bluntly, which one is faster? Option 1 or Option 2? Is there something even faster than option 1 or 2? Thanks My signature used to suck. But it''s much better and more accurate now.

Share this post


Link to post
Share on other sites
Advertisement
Cant you "touch" the ones that will need processing?

In other words;
1) Do a first pass to see which vertices will need transforming
2) As each vertex gets signaled, copy it to a temp array
3) At the end, do the matrix transformations using a fast MMX/ SSE/ SSE2 algorithm (where available).

Points of interest:
You''ll need a temp array. One way to speed this up is to have an array equal in size to the max number of vertices it is expected it will need to hold throughout the life of the program.

Also, using your own memory manager, with a managed memory might speed things up a notch by not calling Windows with allocations.

On (1) instead of signaling each individual vertex, try to signal a whole group. For example, if a ball is rotating, then its vertices have changed position in the next frame, and therefore ALL of the ball''s vertices require a transformation pass.

Also don''t forget that:
V'' = V * M1 * M2 == V'' = V * Ma
where Ma=(M1*M2)

So, in other words, combine all the matrices in your matrix stack...

Hope it helped

Salsa cooked it, your eyes eat it!
[Hugo Ferreira][Positronic Dreams][Colibri 3D Engine][Entropy HL2 MOD][My DevDiary]
[Yann L.][Enginuity] [Penny Arcade] [MSDN][VS RoadMap][Humus][BSPs][UGP][NeHe]
"our stupidity allways comes back to bite us in the ass... in a white-shark sort of way..." - Prozak

Share this post


Link to post
Share on other sites
quote:
Original post by Prozak
Points of interest:
You'll need a temp array. One way to speed this up is to have an array equal in size to the max number of vertices it is expected it will need to hold throughout the life of the program.


Indeed, this is what happens. But, after the frameMove(), the array containing the old data has to be reset. So, if we are storing the vertices in a temp array, that temp array has to be reset for the next frameMove.

Or, if we are using the booleanList (see first post), we have to set each vertices to false. Unless there is a mad fast way to change all the booleans in the list to false (or to remove and realocate the memory), this can be quite inneficient, and this is the problem I am encountering. Any insight on this issue?



My signature used to suck. But it's much better and more accurate now.



[edited by - ageny6 on May 7, 2004 11:27:06 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!