Jump to content
  • Advertisement

Archived

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

bstepa

Questions about priority queues in ROAM

This topic is 6297 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

Hello, I''m currently implementing my own version of ROAM based on the Los Alamos/Lawrence Livermore National Laboratory paper (http://www.llnl.gov/graphics/ROAM/). I have a couple questions regarding the split and merge queues. Do all triangles in a triangulation get added to the split queue or just the triangles that do not have children? For example, take a triangle and split it twice, do we just add the final four triangle (triangles at level 2, I''m starting at level 0) to the split queue or all 7 triangles? Isn''t it expensive to recalculate the priority for each triangle every frame (the triangles in the split and merge queue)? The only way I can see it not being expensive is if you''re only updating the priorities of the triangles and diamonds that get split and merged respectively. I''m a bit confused here regarding the priority update process. Sorry for the long post and thanks, Brendon

Share this post


Link to post
Share on other sites
Advertisement
I''m working on ROAM now, so I could be wrong...

quote:

Do all triangles in a triangulation get added to the split queue or just the triangles that do not have children?


Only the triangles that do not have children should be in the split queue.

quote:

Isn''t it expensive to recalculate the priority for each triangle every frame (the triangles in the split and merge queue)? The only way I can see it not being expensive is if you''re only updating the priorities of the triangles and diamonds that get split and merged respectively. I''m a bit confused here regarding the priority update process.


Yes, the priorities must be updated each frame for every triangle in each queue.


Mike

Share this post


Link to post
Share on other sites
quote:
Original post by bstepa

Isn''t it expensive to recalculate the priority for each triangle every frame (the triangles in the split and merge queue)? The only way I can see it not being expensive is if you''re only updating the priorities of the triangles and diamonds that get split and merged respectively. I''m a bit confused here regarding the priority update process.


It''s been awhile since I focused my attention on this issue, but here''s what I recall. A priority queue is maintained. This queue is a set of buckets. When a new trianlge becomes part of the current tesselation, it''s distortion is calculated. There is some metric (I don''t have it off the top of my head) to determine how to classify the distortion of the trianlge. Based on this classification, the triangle is put into the proper bucket of the priortiy queue. Each bucket classifies triangles based on maximum achievable velocity of the viewpoint, and at what point in the future the triangles in this bucket will need their priorities recalculated.

As an example, triangles with high distortion will naturally be placed in bucket #1. Triangles which are in bucket #1 will have their priorities recalculated next frame. At the next frame, bucket #2 will then become bucket #1 and bucket #3 will become bucket #2 and so on. So, the distortion of the triangle and the maximum acheivable velocity determine at what point in the future the priorities of triangles need to be recalculated. As these priorities are recalculated, they are reclassified and placed in the proper bucket for priority recalculation again sometime in the future.



Share this post


Link to post
Share on other sites
bishop_pass,

What do you mean by "maximum achievable velocity of the viewpoint"?

Thanks,

Brendon

Share this post


Link to post
Share on other sites
quote:
Original post by bstepa
bishop_pass,

What do you mean by "maximum achievable velocity of the viewpoint"?


Given constraints on the mode of locomotion, the program should know what the fastest acheivable speed the viewpoint can obtain in the near future. You program at any given time is likely modeling some type of viewpoint locomotion such as walking, F16 flight, train travel, skydiving, whatever. Given the current speed, and the dynamics of the vehicle (maximum acceleration, etc.) the program should be able to calculate the maximum speed which can be obtained in the near future (next hundred frames or so).

Given the maximum possible speed in the near future, we have a bound on how close any given triangle can get to us in the near future. And given that and a distortion value for each triangle, we have an idea at what point in the future that triangle''s distortion will become relevant.



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!