Ray-Sphere Intersection

Ray Sphere Intersection

When developing atmospheric scattering shaders, we will need to calculate intersection points between rays and spheres. So here is how we can do that.

Defining a ray
To define a ray, we specify two vectors: One point o, which goes from zero to a point on the ray and another one d, which goes along the ray and defines therefore the ray’s direction. The direction vector is multiplied by an argument t. When varying t, we can reach any point on the ray. Now you might say, that we did not define a ray, but a line. The only difference between rays and lines is, that t has a minimum value for rays. A line goes from -infinity to infinity, while a ray has a starting point and goes to infinity from there. In our use case, that’s not that important tough.
\displaystyle\overrightarrow{x}=\overrightarrow{o}+t\overrightarrow{d}

Defining a sphere
To define a sphere, we need to specify a center point c and a radius r. All points on a sphere are points, which have a distance to the center point equally to the sphere’s radius. So a sphere’s definition can be: \displaystyle\|\overrightarrow{x}-\overrightarrow{c}\|=r If we can assume, that the center of the sphere is at the origin of our coordinate system, the equation simplifys to \displaystyle\|\overrightarrow{x}\|=r, so “all vectors with a certain length r”.

Intersecting both
In our use case, we will have the spheres always centered, so we can use the easier version of the sphere definition. Inserting the ray definition into the sphere definition yields:
\displaystyle\|\overrightarrow{o}+t_{\mathrm{hit}}\overrightarrow{d}\|=r I replaced t with \displaystyle t_{\mathrm{hit}} because now it is not a varying parameter anymore. Instead it is a symbol for all values which fulfill this equation (a ray can hit a sphere zero, one or two times).
Image a vector \displaystyle\overrightarrow{a}\, then there is: \displaystyle\|\overrightarrow{a}\|^2 = \|\overrightarrow{a}\|\|\overrightarrow{a}\|

From the definition of the dot product and \displaystyle\cos{0}=1 \Rightarrow \overrightarrow{a}\cdot\overrightarrow{a}=\|\overrightarrow{a}\|\|\overrightarrow{a}\|\cos{\alpha} = \|\overrightarrow{a}\|\|\overrightarrow{a}\|
So there is \displaystyle\|\overrightarrow{a}\|^2 = \overrightarrow{a}\cdot\overrightarrow{a}

To apply this to the intersection, we need to square it first:
\displaystyle\|\overrightarrow{o}+t_{\mathrm{hit}}\overrightarrow{d}\|=r \Leftrightarrow r^2 =\|\overrightarrow{o}+t_{\mathrm{hit}}\overrightarrow{d}\|^2
=(\overrightarrow{o}+t_{\mathrm{hit}}\overrightarrow{d})\cdot(\overrightarrow{o}+t_{\mathrm{hit}}\overrightarrow{d})
\displaystyle=\overrightarrow{o}^2+2\overrightarrow{o}t_{\mathrm{hit}}\overrightarrow{d}+(t_{\mathrm{hit}}\overrightarrow{d})^2  =\overrightarrow{o}^2+2\overrightarrow{o}\cdot\overrightarrow{d}t_{\mathrm{hit}}+\overrightarrow{d}^2t_{\mathrm{hit}}^2
\displaystyle\Leftrightarrow\overrightarrow{o}^2+2\overrightarrow{o}\cdot\overrightarrow{d}t_{\mathrm{hit}}+\overrightarrow{d}^2t_{\mathrm{hit}}^2-r^2=0
\displaystyle\Leftrightarrow \overrightarrow{d}^2t_{\mathrm{hit}}^2 +2\overrightarrow{o}\cdot\overrightarrow{d}t_{\mathrm{hit}}+\overrightarrow{o}^2-r^2=0
\displaystyle\Leftrightarrow t_{\mathrm{hit}}^2 +\frac{2\overrightarrow{o}\cdot\overrightarrow{d}}{\overrightarrow{d}^2}t_{\mathrm{hit}}+\frac{\overrightarrow{o}^2-r^2}{\overrightarrow{d}^2}=0

To make the calculation easier we assume, that \displaystyle\overrightarrow{d} is normalized: \displaystyle\|\overrightarrow{d}\|=1 \Rightarrow \overrightarrow{d}^2 = \overrightarrow{d}\cdot\overrightarrow{d} = \|\overrightarrow{d}\|\|\overrightarrow{d}\| = 1*1 = 1 So the denominators above are one and are left out.

Now we use the reduced quadratic formula to solve the equation for \displaystyle t_{\mathrm{hit}}:
\displaystyle p=2\overrightarrow{o}\overrightarrow{d}, q=\overrightarrow{o}^2-r^2
The discriminant is \displaystyle D=\left(\frac{p}{2}\right)^2-q
\displaystyle t_{\mathrm{hit}}=-\frac{p}{2}\pm\sqrt{D}
\displaystyle=-\frac{2\overrightarrow{o}\overrightarrow{d}}{2}\pm\sqrt{\left(\frac{2\overrightarrow{o}\overrightarrow{d}}{2}\right)^2-\overrightarrow{o}^2+r^2}
\displaystyle=  -\overrightarrow{o}\overrightarrow{d}\pm\sqrt{\left(\overrightarrow{o}\overrightarrow{d}\right)^2-\overrightarrow{o}^2+r^2}
So the cheapest way to calculate the intersection point is:

\displaystyle t_{\mathrm{hit}}=-a\pm\sqrt{a^2-\overrightarrow{o}^2+r^2} with a=\overrightarrow{o}\cdot\overrightarrow{d}

Keep in mind, that \overrightarrow{d} has to be normalized!


Numerical Integration

To describe atmospheric scattering, we will use several equations with integrals which can’t be solved analytically – so we will make use of middle Riemann sums to approximate those.

Image a function f which can’t be integrated analytically. It might have a function graph like this:

In this case it is the graph for f(x)=e^{-x}, which is important for atmospheric scattering. Of course, we can integrate it directly, but we will use this function anyway, so that we can compare our approximation with the direct result.

Let’s say, we want to integrate it from x=1 to x=2:
To calculate this integral, we will divide the complete integral into n intervals and approximate each part with a rectangle, for example n=3:

When the bounds are a und b, each interval has a width of: \displaystyle \mathrm{d}=\frac{b-a}{n}=\frac{2-1}{3}=\frac{1}{3}

Next we need the height of each rectangle. Here there are several possibilities to choose from, we use the value of our function in the middle of each interval (that’s why it is called middle sum):

Now we can calculate the area of each rectangle: \displaystyle A_i = \mathrm{d}\times f(a+(i+\frac{1}{2})\mathrm{d})

i a+(i+0.5)d f(a+(i+0.5)d) Ai
0 1.16666666666667 0.311403223914598 0.103801074638199
1 1.5 0.22313016014843 0.074376720049477
2 1.83333333333333 0.159879746079694 0.053293248693231

Adding all rectangles yields:

\displaystyle\sum A_i = 0.231471043380907

Let’s check: \displaystyle\int_1^2 e^{-x}= \left[ -e^{-x} \right]_1^2 = -e^{-2}+e^{-1}=\frac{1}{e}-\frac{1}{e^2}=\frac{e}{e^2}-\frac{1}{e^2}
\displaystyle=\frac{e-1}{e^2}\approx 0.23254415793483

In this case there is an error of 0.46606%, pretty good for just using three sample intervals. When using more samples, the approximation gets more accurate, here are the results when using 3, 10, 50 and 500 samples:

n Approximation Error
3 0.231471043380907 0.461467 %
10 0.232447292788817 0.041655 %
50 0.232540282244081 0.001667 %
500 0.232544119177475 0.000017 %

There is a lot of theory for quantifying the error, but I will omit it here. All we will need is the following equation for numeric integration by middle Riemann sums:

\displaystyle\int_a^b f(x)\,dx \approx \frac{b-a}{n}\sum_{i=0}^{n-1} f\left(a+\left(\frac{1}{2}+i\right)\frac{b-a}{n}\right)

Exec Guildpage

Exec Guildpage

With the release of the World of Warcraft expansion “Warlords of Draenor”, I joined the German raiding guild “Exec”. At that time, they were using a GildenDKP website, which was quite costly and inflexible. So I made a new guild website. You can find an archived copy here!

Requirements

  • Message board: The guild members should be able to communicate outside the game using a forum software, including all expected functions (thread-based conversation, private messaging, …).
  • Voice communication: There should be some kind of voice communication service for talking while playing but also for out of game conversation. Since a World of Warcraft raid can consist of up to 30 individuals, the service had to support such group sizes.
  • Homepage: The guild also needed a guild homepage for recruitment and news postings.

Aside from these functional requirements it was also necessary, that an interested novice would be able to handle basic administrative tasks.

Possible Extensions

  • DKP-System: DKP are some kind of reward points, which each guild member earns and spends. An additional design target was to implement a system for DKP management.
  • Simulationcraft: Simulationcraft is an open-source combat simulation tool, which is used by players to optimize their characters. Since it is a bit difficult to use for some people, we planned to provide all guild members with a daily simulation of their characters.
  • Warcraftlogs: Warcraftlogs is a combat logging site, which analyses and visualizes uploaded combat logs. Since Warcraftlogs does not provide an API we just wanted to embed it into our page.
  • Progression Banner: Many raiding guilds use a banner on their homepages to show their current raiding progress.
  • Voice server monitor: It would have been convenient for the users to be able to view the current visitors on the voice server from the site.

Software Used

Implementation

Since a content management system would be required, this was an obvious place to start. First test installations with common CMS like Joomla, Drupal, e107 and WordPress were made. In the end Joomla has been chosen because of it’s great market share (which results in a larger quantity of available plugins) and great documentation. The administrative backend was quite convincing too. e107 and Drupal did have a lot less plugins and WordPress’ scope was more on blogging than content management.

The next step was the forum software. First some tests with the Joomla plugin Kunena have been made, but it got discarded. It’s default look wasn’t too great and the navigation wasn’t very intuitive. So I had to integrate some fully fledged bulletin board software with Joomla. Two different systems were reviewed (PhpBB and Simple Machines Forum) and since the PhpBB Homepage had been hacked and therefore wasn’t available for days, I chose SMF.

The licences of Joomla (GPLv2) and SMF (BSD) are incompatible, so there is no direct login bridge available in form of a SMF plugin. After some research I found JFusion, which is a more general approach to integrate software into Joomla. It is implemented as Joomla plugin and provides “adapters” to different platforms esp. SMF. At first I configured JFusion to authenticate users against the SMF database, so that SMF was the place to keep user data. Next JFusion provided a login module for Joomla that also sets SMF related auth cookies when logging in into Joomla, so users only need to use Joomla’s login form. To make it less confusing, I hid the login button in SMF. Lastly I used the frame wrapper of JFusion to embed SMF into Joomla as a menu entry (see demo).

In the next step I created a Joomla template from scratch and searched for a fitting SMF template, which I found in “Flat”. I adjusted both templates to integrate into each other.

Now let’s visit the extensions:

  • Voice server monitor: This one was easy, because there are plenty Teamspeak viewer modules for Joomla.
  • Progression Banner: For this design target, I wrote a small Joomla module, which used WoWProgress to pull progression data. Since they don’t provide an API, I used some regular expressions to parse their website. To reduce the performance impact of sending requests to another server, I used Joomla’s cache so that progression was only pulled once every hour.
  • Warcraftlogs: I used Joomla’s iframe wrapper module for embedding Exec’s guild overview page on Warcraftlogs.
  • DKP-System: To provide a first band aid solution I embedded a Microsoft Live spreadsheet into an iframe wrapper. I planned to implement a more convenient solution, like installing EQdkp in the background and embed some of it’s pages directly or writing a small home brew solution in form of an Joomla plugin. This did not become reality before I left.
  • Simulationcraft: This never has been implemented, but since we had some simc-files already it would not have been too difficult to implement. Simc already produces HTML files while simulating, so it would have been possible to run it by a cronjob. It’s result HTML files would have been accessed by the webserver directly.

For voice communication I used Teamspeak, because the users were already used to it. Alternatives like Ventrilo or Mumble were not evaluated.

Demo

I have stopped playing World of Warcraft, so I am not with this guild anymore. That is why I took the original site offline, but I still want to use it for demonstration purposes. Using WinHTTrack I rendered all dynamic PHP-pages to static HTML pages. That way you can still view the site, but I don’t have to maintain it anymore. If you are interested, here is the link!

Review

In Retrospect Joomla wasn’t the best choice. It is a very complex system and esp. the SMF integration required a lot of tinkering before it worked. Even then, there were different small bugs, for example the WYSIWYG-editor in SMF did not catch some key events under some browsers when using the frameless wrapper. Another example is that the iframe wrapper is not able to adjust it’s size after loading, so when SMF changes it’s size (it has some pulldown menus), scroll bars were appearing. Adjusting two templates (one for Joomla and one for SMF) was really time consuming, even though I used an existing for SMF. I kept finding small errors on some sub pages in SMF quite a time after building the page.

Having to manage two systems (Joomla and SMF) didn’t help very much for making administrative tasks easy to handle. Our novice admins were confused quite badly.

JFusion’s login bridging worked quite well after some initial difficulties and Joomla’s plugin and template framework provided great benefit when developing the progression banner and the template.

So the most important caveat of Joomla was the lack of a good forum component. I might choose WordPress next time, because it seems to have a good forum plugin in form of bbPress (I didn’t test it very intensively though). It also provides all CMS functionality we needed and is more easy to manage because it doesn’t require admins to handle two separate systems.


Appreciation

When creating Earthviewer, I used a bunch of free libraries and assets. Here are the most important ones:

Libs

Assets

  • Natural Earth III: Earth image data, going from texture maps to elevation maps. I used a night texture, a cloud map and the land/water mask.
  • NASA Visible Earth – The Blue Marble: This is where the day texture is from and I also used one of their Bathymetry maps.
  • Ponies & Light Normal Map: The personal blog of @tgfrerer, he wrote an article about extracting normal maps from elevation data. I used his results in my project.
  • Milky Way Skybox Textures: Originally made for Kerbal Space Program using Space Engine. Unfortunately I do not know the author because of his reddit and mediafire account being deleted.

I also want to appreciate some tutorials which helped me alot:

Tutorials


Earthviewer

Earthviewer is a small project, which renders a moving model of the Earth using a bunch of textures and some other cg tricks. Currently I am implementing atmospheric scattering.


Dieses Video sowie der folgende Download basieren auf Revision EEAA90CE.

Earthviewer Download
Visual C++ x86 Runtime Try to install this, if there is an error message while starting.

Project Page