The first maxim of improving frame rate is: the fastest way to draw an object is not to draw it. This has always been tempered with "unless determining not to draw it takes longer than drawing it." Ideally, for example, the triangles of a 3D model would not be sent to the GPU if the model were not visible. To check if each triangle of the model was visible or not would be too CPU intensive and result in a lower frame rate than always sending the model to the GPU.
Graphics applications typically create bounding spheres that encompass logical sets of triangles, such as a model. A sphere can quickly be checked for visibility. The model is drawn only if the bounding sphere is visible. Because the sphere doesn't exactly represent the 3D model, sometimes the model will be sent to the GPU even though the model isn't visible. Tighter bounding spheres reduce these false positives.
STK has always calculated bounding spheres for 3D models, terrain, et al. For Point Break, we decided to revisit our bounding spheres to see if we could calculate tighter spheres.
While I could find many bounding sphere algorithms on the web, I couldn't find timing and quality comparisons between these algorithms; so, I compared three popular algorithms myself using various area targets. If you are not familiar with STK area targets, they are areas on the Earth defined by a list of points that define the border and are filled inside, e.g., Afghanistan pictured above. STK calculates a bounding sphere from those points. All of the tested algorithms run in linear time, but vary in CPU usage.
The first algorithm is the simplest and fastest. I'll call it Naive. It is also the one we have always used in STK. In the first pass of the point data, an axis aligned bounding box is calculated, and the center of the sphere is the center of the box. In the second pass, the radius of the sphere is calculated as the point most distant from the center. This sphere and the time required to calculate the sphere is the baseline from which I compared the other algorithms. The drawback to this approach is that it almost never calculates the tightest sphere.
The second algorithm is Jack Ritter's and is documented in GRAPHICS GEMS I. The code can be downloaded here; the file is BoundSphere.c. A general description can be found here. Ritter's sphere is calculated in two passes like the Naive sphere. The first pass calculates an initial guess of the sphere. In the second pass, a point is added to the sphere one at a time. If the point lies within the sphere, nothing is done. If the point lies outside the sphere, the center and radius are modified to include the point. This is different from Naive that only modifies the radius.
This was the most frustrating of the algorithms. According to the author, the sphere is within 5% of the exact sphere, and isn't much slower to calculate than Naive. In my tests, there were spheres 19% worse than the Naive sphere much less the best, and there were spheres 11% better. This algorithm is highly dependent on the initial sphere and the order in which the points are added. I experimented with the initial sphere calculation. Adding just a few more compares to the code, I created an initial sphere that was larger than previously created. This change created a tighter sphere in many cases. For example, the sphere that was previously 19% worse than the Naive sphere was now the same. I suspect that if the initial sphere was based on the two points farthest from each other, the final sphere would typically be tighter than the original algorithm. I never tried that as calculating those two points would compromise the algorithm's speed.
The last algorithm I tried was Welzl's, which calculates the exact or minimum bounding sphere. The algorithm is based on the simple idea that the minimum bounding sphere is defined from two, three, or four of the points. All other points either lie on or within the sphere.
A significant shortcoming of this algorithm is that it takes a long time to compute relative to others. This isn't an issue if the sphere is calculated offline, but is if it is calculated in real-time. I tried both Bernd Gärtner's and Dave Eberly's implementations.
Here are the results of the different algorithms for five area targets:
| Number of Points: 336 | |||
|---|---|---|---|
| Method | Time (msec) | Radius (m) | Time / Naive Time |
| Naive | 0.009 | 296870 | 1.0 |
| Ritter | 0.012 | 278722 | 1.3 |
| Gärtner | 0.134 | 266354 | 14.8 |
| Eberly | 0.185 | 266354 | 20.3 |
| Number of Points: 362 | |||
|---|---|---|---|
| Method | Time (msec) | Radius (m) | Time / Naive Time |
| Naive | 0.009 | 388544 | 1.0 |
| Ritter | 0.012 | 350717 | 1.4 |
| Gärtner | 0.151 | 348700 | 17.5 |
| Eberly | 0.165 | 348700 | 19.3 |
| Number of Points: 795 | |||
|---|---|---|---|
| Method | Time (msec) | Radius (m) | Time / Naive Time |
| Naive | 0.020 | 648404 | 1.0 |
| Ritter | 0.025 | 647093 | 1.2 |
| Gärtner | 0.460 | 647093 | 23.3 |
| Eberly | 0.282 | 647093 | 14.3 |
| Number of Points: 1331 | |||
|---|---|---|---|
| Method | Time (msec) | Radius (m) | Time / Naive Time |
| Naive | 0.032 | 1229436 | 1.0 |
| Ritter | 0.041 | 1286992 | 1.3 |
| Gärtner | 0.930 | 1206456 | 28.9 |
| Eberly | 0.605 | 1206456 | 18.8 |
| Number of Points: 21543 | |||
|---|---|---|---|
| Method | Time (msec) | Radius (m) | Time / Naive Time |
| Naive | 0.479 | 3802142 | 1.0 |
| Ritter | 0.581 | 3715345 | 1.2 |
| Gärtner | 33.625 | 3711390 | 70.2 |
| Eberly | 10.562 | 3711390 | 22.0 |
Welzl's exact solution was 11% better for the first two and nearly the same for the remaining area targets.
Eberly and Gärtner calculated the same and smallest radius as is expected for Welzl's algorithm. While Eberly ran about 20 times slower than Naive, Gärtner ran more slowly as the number of points increased. Welzl is supposed to scale linearly to the number of points, so the Gärtner results were unexpected. Gärtner ran faster than Eberly for the lower number of points.
For the third area target, Ritter calculated the same radius as Welzl. Ritter also calculated a larger radius than Naive for the fourth area target, which isn't good since it took longer to run.
What does all this mean? We learned that using Naive in STK all these years hasn't been a catastrophe. We can improve our numbers, though.
I decided not to use Welzl because the improvement over Naive didn't justify additional time required to calculate the sphere.
Ritter takes only 20% more time than Naive and generally creates smaller spheres. However, Ritter sometimes creates larger spheres. Based on that, I decided to use a hybrid method as the default bounding sphere code for Point Break; Ritter and Naive are run simultaneously, and the code returns the smaller of the two spheres. This method increased the run time over Ritter only slightly. We can still run Naive and Ritter independently if needed. We expect to use Naive for objects that are constantly changing size or are short lived.
The N.Y. Giants were the giant killers. Ironic.
cool beans… did you try benchmarking difference in run-time performance in using naive vs exact (without measuring the construction time)? because that would give you the maximum possible performance improvement you can get, and would help tell you whether or not it’s worth putting a lot of effort into finding a more compact fit =P
ps: I like how you have “Time / Naive Time”. how about a “Radius / Naive Radius”?
Good question. Given the typical arrangement of objects in STK/Point Break and the minor improvement in bounding sphere size, I would not expect to see a frame rate increase; I would expect to be limited in other ways. (We don’t do collision detection, but I wonder if that would be a more telling test if we did.) If I had seen a post like this before I dove into this, I would have continued using the Naive and moved on to higher priority work.
Since I had done all this work already, I decided to use the Hybrid by default. If the extra time required to create a Hybrid bounding sphere is limiting, I can switch back to Naive. Once again, I doubt we will notice given other significant time consuming processes that will likely be executing on these same triangles: tessellation, vertex cache optimizations, vertex buffer optimization and creation, etc.
It would be good to show the percent change or ratio of the radii, but hand typing HTML tables for a guy who has never written a line of HTML until this post – sheesh.
html tables suck =P
Stumbled on your page when I did a search on Ritter. Nice article by the way. Maybe you want to check out the EPOS algorithm as an alternative to Ritter, it was developed by a scientist at my university
scientist.
http://www.ep.liu.se/ecp/034/009/ecp083409.pdf
Mattias, thanks. The paper you mention is very interesting and gives me thoughts regarding the choice of axes to compute the extreme points especially for 3D models.
Many models have symmetry, like an airplane. It seems that model builders are predisposed to build these models along the x, y, or z axis. Given this predisposition, I wonder if those or some other axis are more likely than others to have the extreme points and if in the paper’s test cases, there was a bias towards a particular axis to produce the smallest sphere.
45. I savour, lead to I discovered just what I was looking for. You have ended my four day lengthy hunt! God Bless you man. Have a nice day. Bye
Thanks, this was helpful. Here is another approach to a tight-fitting sphere alternative to Welzl. It is simple. First use the Naive method to get an approximate fit. Then search near the center for a better center along the 3 axes (+/-) with some starting fraction delta of the sphere radius. I use 10%. If the fit improves from the test point (the radius is smaller), continue in that direction. If not, multiply the delta by 0.5 and iterate, until delta is smaller than some desired amount; for example, 1% of the original radius. It is roughly linear in time and only took about half an hour to code.
very nice post, i certainly love this website, keep on it
Excellent billet. Le billet est complémentaire à celui.
Going to put this airtlce to great use now.
Well, I don’t know if that’s going to work for me, but definitely worked for you! Great post!
I just determined your site and also have also been reading through alongside. When i identified many creepy reviews, but in most cases I passionately go along with what the different rewiewers say. Witnessing a lot of nicegreat opinions of this web site, I was thinking we might in addition jump in plus make you aware that I really favored reading this submit. I really assume this could produce my personal initial opinion: “I believe you have made many interesting things. Certainly not so many people would likely in fact think about this and the choice of merely did. Now i’m really satisfied there’s a great deal with this subject which were discovered and you simply achieved it thus well, with the considerably category!inch
House and Rent : Acquire Home Rentals offers listings of houses in place of rent throughout the U.S. Search intended for rental homes, condos, townhouses, apartments also every types of rental … http://www.houseandrent.com
Great post, I think blog owners should acquire a lot from this weblog its very user pleasant.
You made some clear points there. I looked on the internet for the subject matter and found most people will consent with your website.
thank you for sharing with us, I think this website genuinely stands out : D.
some times its a pain in the ass to read what website owners wrote but this site is really user pleasant! .
Rattling excellent information can be found on weblog .
I would like to hear a little more about the merit scholarships, in particular the Cornelius Vanderbilt Scholarship. Any information would be appreciated!
Hiya very cool website!! Guy .. Beautiful .. Wonderful .. I’ll bookmark your website and take the feeds additionally?I am satisfied to find so many helpful info right here within the publish, we’d like work out more techniques in this regard, thank you for sharing. . . . . .
But wanna input on few general things, The website pattern is perfect, the subject material is really fantastic : D.
If your real friends know you as your nickname, use that nickname as your first name online. When you very first friend someone, focus on generating a personal comment that weaves connection.
I think other website proprietors should take this web site as an model, very clean and fantastic user friendly style and design, let alone the content. You are an expert in this topic!
You made some respectable points there. I searched on the internet for the difficulty and located most people will go together with along with your website.
Not long ago i discovered your site post and still have been recently reading through alongside. There are many odd responses, however typically I need to accept what the additional rewiewers are generally producing. Discovering numerous greatgreat reviews of this web site, I believed that I should additionally join in and explain how I must say i enjoyed looking over this your articles. And so i think this would make our initial comment: “I can see that you’ve made several really intriguing factors. Very few men and women would in fact think about this the method that you simply do. Now i’m truly pleased that there are a lot about this theme that is found and also you made it happen thus nicely, with a great deal school!”
as soon as I discovered this internet site I went on reddit to share some of the love with them.
The following time I learn a blog, I hope that it doesnt disappoint me as a lot as this one. I mean, I do know it was my option to read, but I actually thought youd have something interesting to say. All I hear is a bunch of whining about one thing that you would repair when you werent too busy on the lookout for attention.
You have mentioned very interesting points ! ps decent website .
This will be a fantastic web site, will you be interested in doing an interview regarding just how you developed it? If so e-mail me!
I simply identified your site submit even though I was in fact running a browse Yahoo and google, trying to find such like however, not quite a similar… Nevertheless I am over delighted to learn that, when you actually seem to have an topical standpoint. I’d personally rather say it’s around controversy… but I am just scared not to make you my personal enemy, ‘, ha, haya… In any case, if you’d want to talk more about this, make sure you answer to our review as well as I am going to ensure that you register to ensure I will be recommended are available back again in charge of much more… Your aspirant buddy
Effectively… to become absolutely sincere, I don’t anticipate to discover such a info by mistake, as Used to do, simply because I recently stumbled upon your own post whilst I used to be really owning a look on Msn, trying to find something similar however, not exactly the same… Nevertheless right now I am just greater than delighted you just read this and I’d like to provide that your perspective is actually remarcable though somewhat controversial for the identified… I’d alternatively say it is approximately controversy… nevertheless I’m worried to help you my own opposing forces, ‘, ‘, haya… Anyway, if you will speak at length regarding it, you should respond to my review and I am going to make an effort to register in order that I am notified are available again in charge of much more…
It’s very good post.
Outstanding post, I think people should learn a lot from this weblog its rattling user friendly .
Spot on with this write-up, I truly suppose this website needs rather more consideration. I’ll probably be again to learn way more, thanks for that info.
I don’t suppose I’ve never read something like this before. So nice to see someone with some unique thoughts on this subject. I really thank you for starting it. This web site is one thing that’s wanted on the web, someone with just a little originality.
Exactly what I was searching for, appreciate it for putting up.
you are my inhalation , I have few web logs and often run out from to brand : (.
I loved as much as you will receive carried out right here. The sketch is attractive, your authored subject matter stylish. nonetheless, you command get bought an edginess over that you wish be delivering the following. unwell unquestionably come further formerly again since exactly the same nearly a lot often inside case you shield this increase.
Great, merely brilliant! Ideal to determine content of which cause you to feel full of life. Difficulty . we don’t have greater number of these. This specific created a cardiovascular content……….
Hello, Thank you for this specific material I had been seeking all Yahoo to be able to locate it!
read. |Thanks for good news!|Thanks for best news!|thank! for this news it’s a good infomation !|Nice post…Thank you for sharing some good things!! |Thans
Jeden Tag stellt man sich die Frage Was Koche Ich Heute?! Zerbrechen Sie sich nicht den Kopf, besuchen Sie uns am besten direkt auf unserer Webseite uns lassen Sie sich inspirieren
Not long ago i came across your site and also rapidly scanned along. I have seen some weird feedback, yet typically I just accept what the some other rewiewers are saying. With the amount of nicegreat reviews regarding this blog, I was thinking that i would furthermore start along with tell you just how I really appreciated looking at this web site. Therefore i consider this could create my personal first comment: “I can see you have created several really interesting points. Very few folks might actually look at this how we simply does. I am just genuinely amazed that there is a great deal relating to this theme that has been discovered and you also made it happen consequently well, with a lot training!inch
Some really nice stuff on this site, I like it.
My wife and i were really thankful when Ervin could carry out his survey via the precious recommendations he had in your web pages. It is now and again perplexing just to choose to be offering points which often the rest might have been making money from. And we discover we have got you to be grateful to for this. All the explanations you made, the straightforward web site menu, the relationships you assist to instill – it’s got most incredible, and it’s really assisting our son and the family feel that that idea is enjoyable, which is certainly incredibly pressing. Thanks for all!
Only wanna tell that this is invaluable , Thanks for taking your time to write this.
Very efficiently written post. It will be useful to everyone who utilizes it, as well as me. Keep up the good work – for sure i will check out more posts.
I’ll gear this review to 2 types of people: current Zune owners who are considering an upgrade, and people trying to decide between a Zune and an iPod. (There are other players worth considering out there, like the Sony Walkman X, but I hope this gives you enough info to make an informed decision of the Zune vs players other than the iPod line as well.)
marketing through articles is unexciting, it happens to be definitely worth the moment that you choose to spend.
wohh exactly what I was looking for, regards for putting up.
Very well written post. It will be helpful to everyone who utilizes it, including me. Keep up the good work – can’r wait to read more posts.
I wanted to follow up and let you know how great I cherished discovering your site today. We would consider it a great honor to do things at my company and be able to make use of the tips provided on your web-site and also participate in visitors’ opinions like this. Should a position connected with guest publisher become offered at your end, you should let me know.
I agree with your points , great post.
some truly prize content on this site, saved to my bookmarks .
very good post, i certainly love this website, keep on it
That i therefore savored your site. Good subject matter. Satisfy keep on advertisment these sort of good cotent.
This is getting a bit more subjective, but I much prefer the Zune Marketplace. The interface is colorful, has more flair, and some cool features like ‘Mixview’ that let you quickly see related albums, songs, or other users related to what you’re listening to. Clicking on one of those will center on that item, and another set of “neighbors” will come into view, allowing you to navigate around exploring by similar artists, songs, or users. Speaking of users, the Zune “Social” is also great fun, letting you find others with shared tastes and becoming friends with them. You then can listen to a playlist created based on an amalgamation of what all your friends are listening to, which is also enjoyable. Those concerned with privacy will be relieved to know you can prevent the public from seeing your personal listening habits if you so choose.
It is actually very seriously a great page. Some sort of tip coupled those wrinkles demonstrates in what way greatly the particular style is normally valued by the pack leader reliable.
Thenk you very much
I would like to express my affection for your kindness supporting all those that absolutely need help on this area. Your personal commitment to passing the solution all over ended up being wonderfully beneficial and have without exception made somebody like me to get to their objectives. Your new important publication means a lot a person like me and especially to my fellow workers. Many thanks; from all of us.
I do not even know how I ended up here, but I thought this post was good. I don’t know who you are but certainly you are going to a famous blogger if you aren’t already
Cheers!
Bounding Sphere at AGI Graphics Team Blog This is the appropriate weblog for anyone who wants to find out about this topic. You understand so much its almost hard to argue with you (not that I actually would want…HaHa). You undoubtedly put a brand new spin on a subject thats been written about for years. Nice stuff, just great! Regards, Teak Furniture
i called a left a message when i saw the poster a few months back. didn’t know it was his actual number but i left a funny, long, rambling message pretending to actually need a babysitter-. totally insane. can’t wait to see if it gets saved out and picked for others to hear. could be fun…. Buy Tera Gold
just left him a message hahaBuy Tera Gold
If you’re still on the fence: grab your favorite earphones, head down to a Best Buy and ask to plug them into a Zune then an iPod and see which one sounds better to you, and which interface makes you smile more. Then you’ll know which is right for you.
Apple now has Rhapsody as an app, which is a great start, but it is currently hampered by the inability to store locally on your iPod, and has a dismal 64kbps bit rate. If this changes, then it will somewhat negate this advantage for the Zune, but the 10 songs per month will still be a big plus in Zune Pass’ favor.
An absorbing communication is couturier observe. I expect that you should compose statesman on this subject, it mightiness not be a preconception person but generally people are not enough to communicate on much topics. To the succeeding. Cheers like your Bounding Sphere at AGI Graphics Team Blog.
You made a few good points there. I did a search on the issue and found a good number of people will consent with your blog.
Hello, Nice work! I saw this really great post today.
There are a handful of intriguing points at some point in this posting but I don’t determine if I see these center to heart. There exists some validity but Let me take hold opinion until I take a look at it further. Superb write-up , thanks and we want a great deal more! Combined with FeedBurner too
I feel like I’m often looking for intriguing points to read about a variety of niches, but I manage to include your weblog among my reads every day because you’ve compelling entries that I appear forward to. Here’s hoping there’s a good deal far more wonderful material coming!
All the best for one’s files. Substantially prized.
*An intriguing discussion will likely be worth comment. I believe which you can write read far more about this subject, might effectively surely be a taboo topic but normally folks are inadequate to chat on such topics. To a higher. Cheers
You produced some decent points there. I looked online for the issue and identified most people will go in addition to your web site.
I got what you specify, thanks for swing up. Woh I am glad to gestate this website finished google. Thanks For Share Bounding Sphere at AGI Graphics Team Blog.
I must show my gratitude for your kindness in support of persons who actually need assistance with your subject matter. Your very own commitment to passing the solution all around appears to be really informative and has without exception helped guys much like me to arrive at their targets. Your own insightful guidelines entails a great deal a person like me and a whole lot more to my fellow workers. Regards; from all of us.
ligtv yayinakisi
I had been examining some of your content within this internet site and i also believe that this page is incredibly instructive! Keep submitting.
An interesting discussion is worth comment. I feel that you must write extra on this subject, it might not be a taboo topic but typically persons are not enough to talk on such topics. To the next. Cheers
Great post. I was checking constantly this blog and I’m impressed! Very useful info specially the last part
I care for such information much. I was looking for this certain info for a long time. Thank you and good luck.
Throughout this awesome scheme of things you secure an A for effort. Where exactly you actually lost us was first in the particulars. You know, as the maxim goes, the devil is in the details… And that couldn’t be much more true at this point. Having said that, let me inform you precisely what did deliver the results. Your writing is very persuasive which is most likely why I am making the effort in order to opine. I do not really make it a regular habit of doing that. Secondly, even though I can see the jumps in logic you make, I am definitely not convinced of how you seem to unite the details that help to make the actual final result. For right now I will yield to your position however hope in the foreseeable future you connect your dots much better.
I do like the way you have framed this particular difficulty plus it does indeed provide me a lot of fodder for thought. However, from just what I have observed, I basically wish when other remarks pack on that people today keep on issue and not start on a tirade associated with some other news du jour. Anyway, thank you for this excellent point and although I can not go along with it in totality, I regard the point of view.
Hi there almost everyone. I used to be just browsing the net for exciting and came upon your website. Terrific post. Thank you quite a bit for sharing your encounter! It is great to grasp that some people still set in an energy into controlling their online resources. I am going to you should definitely check back again from time totime.
It’s rather difficult to seem to get a very good corporation that does foundation repair in Galena Park Tx. I really wish to be careful in deciding on the foundation repair company that I am planning to retain to ensure that I is not going to end up squandering time and cash.