Ray tracing black holes

Lately I’ve been studying up on ray tracing, and one of my goals has been to build a nonlinear ray tracer — that is, a ray tracer that works in curved space, for example space that is curved by a nearby black hole. (See the finished source code!)

image_basic_disk

In order to do this, the path of each ray must be calculated in a stepwise fashion, since we can no longer rely on the geometry of straight lines in our world. With each step taken by the ray, the velocity vector of the ray is updated based on an equation of motion determined by a “force field” present in our space.

This idea has certainly been explored in the past, notably by Riccardo Antonelli, who derived a very clever and simple equation for the force field that guides the motion of the ray in the vicinity of a black hole, namely

$$\vec F(r) = – \frac{3}{2} h^2 \frac{\hat r}{r^5}$$

I decided to use the above equation in my own ray tracer because it’s very efficient computationally (and because I’m not nearly familiar enough with the mathematics of GR to have derived it myself). The equation models a simple Schwarzschild black hole (non-rotating, non-charged) at the origin of our coordinate system. The simplicity of the equation has the tradeoff that the resulting images will be mostly unphysical, meaning that they’re not exactly what a real observer would “see” in the vicinity of the black hole. Instead, the images must be interpreted as instantaneous snapshots of how the light bends around the black hole, with no regard for redshifting or distortions relative to the observer’s motion.

Nevertheless, this kind of ray tracing provides some powerful visualizations that help us understand the behavior of light around black holes, and help demystify at least some of the properties of these exotic objects.

My goal is to build on this existing work, and create a ray tracer that is more fully featured, with support for other types of objects in addition to the black hole. I also want it to be more extensible, with the ability to plug in different equations of motion, as well as to build more complex scenes, or even to build scenes algorithmically. So, now that my work on this ray tracer has reached a semi-publishable state, let’s dive into all the things it lets us do.

Accretion disk

The ray tracer supports an accretion disk that is either textured or plain-colored. It also supports multiple disks, at arbitrary radii from the event horizon, albeit restricted to the horizontal plane around the black hole. The collision point of the ray with the disk is calculated by performing a binary search for the exact intersection. If we don’t search for the precise point of intersection, we would see artifacts due to the “resolution” of the steps taken by each ray (notice the jagged edges at the bottom of the disk):

render_00001_baddisk

Once the intersection search is implemented, the lines and borders become nice and crisp:

render_00001_perfect

We can also apply different colors to the top and bottom of the disk. Observe that the black hole distorts the disk in a way that makes the bottom (colored in green) appear around the lower semicircle of the photon sphere, even though we’re looking at the disk from above:

image_disk_close1

Note that the dark black circle is not the event horizon, but is actually the photon sphere. This is because photons that cross into the photon sphere from the outside cannot escape. (Only photons that are emitted outward from inside the photon sphere can be seen by an outside observer.)

If we zoom in on the right edge of the photon sphere, we can see higher-order images of the disk appear around the sphere (second- and even third-order images are visible). These are rays of light that have circled around the photon sphere one or more times, and eventually escaped back to the observer.

image_disk_close2

And here is the same image with a more realistic-looking accretion disk:

image_disk_close3

Great! Now that we have the basics out of the way, it’s time to get a little more crazy with ray tracing arbitrary materials around the black hole.

Additional spheres

The ray tracer allows adding an unlimited number of spheres, positioned anywhere (outside the event horizon, that is!) and either textured or plain-colored. Here is a scene with one hundred “stars” randomly positioned in an “orbit” around the black hole (click to view larger versions of the images):

image

Notice once again how we can see second- and third-order images of the spheres as we get closer to the photon sphere. By the way, here is a similar image of stars around the black hole, but with the curvature effects turned off (as if the black hole did not curve the surrounding space):

image

And here is a video, generated using the ray tracer, that shows the observer circling around the black hole with stars in its vicinity. Once again, this is not a completely realistic physical picture, since the stars are not really “orbiting” around the black hole, but rather it’s a series of snapshots taken at different angles:

Notice how the spherical stars are distorted around the Einstein ring, as well as how the background sky is affected by the curvature.

Reflective spheres

And finally, the ray tracer supports adding spheres that are perfectly reflective:

image_with_reflective2

All that’s necessary for doing this is to calculate the exact point of impact by the ray on the sphere (again using a binary intersection search) and get the corresponding reflected velocity vector based on the normal vector on the sphere at that point. Here is a similar image, but with a textured accretion disk:

image_with_reflective3

Future work

Eventually I’d like to incorporate more algorithms for different equations of motion for the rays. For example, someone else has encoded a similar algorithm for a Kerr black hole (i.e. a black hole with angular momentum), and there is even a port of it to C# already, which I was able to integrate into my ray tracer easily:

image_kerr_1

A couple more ideas:

  • There’s no reason the ray tracer couldn’t support different types of shapes besides spheres, or even arbitrary mesh models (e.g. STL files).
  • I’d also like to use this ray tracer to create some more animations or videos, but that will have to be the subject of a future post.
  • Make it run on CUDA?

Simple ray tracing in pure Javascript

As a quick diversion, I recently followed Peter Shirley’s excellent Ray Tracing in One Weekend guide, which is a terrific refresher of the surprisingly simple math involved in ray tracing.  And in the spirit of Atwood’s Law, I decided to do it in Javascript, since I don’t work with Javascript very often, and thought I could use a refresher in it, as well. The result is some relatively passable Javascript code (which is slow as hell!), but some really pretty pictures:

3

4

Some possible future work might be to create a renderer for black holes (in addition to regular spheres) which would actually curve the surrounding space and affect the direction of the rays. This would necessitate a radically more complex ray tracer, which would need to follow the path of the ray in a stepwise fashion using Boyer–Lindquist coordinates within the Kerr metric. Perhaps a project for another weekend (or two)!

Knock-off apps: the sincerest form of flattery

As the developer of a relatively popular app, there are numerous things I have to worry about on a regular basis. One of these things, however, is something for which I was kind of unprepared, and still not sure how to deal with: the emergence of knock-off apps — apps that have a suspicious and often hilarious resemblance to the original.

There were, of course, counterfeit apps that were blatantly using my trademark in their name (“DiskDigger” is a registered trademark in the U.S.), or my graphics in their store listings, in which case the Google Play Store thankfully took them down upon request.

But then there are apps that don’t quite use my trademark, and don’t quite have the same icon and screenshots. But because they are close enough, they can take advantage of being near the top search results for this category of apps, and lead numerous unsuspecting users to install them and be greeted with a barrage of ads and spyware.

Most of these apps seem to come from Indian and Middle-Eastern developers, which makes the horribly broken English in their app verbiage even more amusing to read. A small part of me even applauds their enterprising spirit, and I don’t fault them for wanting to make a buck, but I wish they’d find ways of doing it more honestly.

Take a look! Can you tell the knock-off apps from the real ones?

diskdigger_fake_apps

The problem is that because these apps don’t explicitly violate my trademark, Google refuses to take them down, which is unfortunate because these apps do literally nothing except shove ads in the user’s face, and therefore actively harm the ecosystem of the Play Store. Shouldn’t Google care more about preventing the Play Store from becoming a cesspool of bottom-feeding cash grabbers?

Premature optimization of Android View hierarchies

In my day job, one of my responsibilities is to oversee the technical evolution of our product and to optimize its performance. I’ve even written a few guidelines that detail numerous recommendations for maximizing performance of Android apps in general.

One of the things I have always recommended is to reduce the complexity of View hierarchies, and try not to overcrowd or have too many nesting levels of your Views, since this can supposedly have a negative impact on performance.  However, I made these statements based on common sentiment on the web, and based on the Android documentation, instead of on actual hard evidence.  So I  looked into it from an interesting perspective:  I dug into View hierarchies as they are used by other major apps, and compared them with our own usage.  This isn’t a totally “scientific” analysis, and it only looks at a single facet of proper View usage. Nevertheless the findings are rather surprising, and are actually challenging my insistence on View minimalism.

I looked at the Twitter, Facebook, and Slack apps, and compared each of their “feed” screens to the feed screen of our own Wikipedia app. (The reason I chose these apps is that the “performance” of their feeds is nearly perfectly smooth, especially considering that some of their content includes auto-playing videos and animations.)  I used the superbly useful and little-known UI Automator Viewer tool, which is bundled with the Android SDK, to explore these view hierarchies.

For reference, the deepest nesting that I found in the feed of the Wikipedia app is seven (7) levels deep:

layout_dump3

But get ready:  The deepest nesting in the Slack app is… eighteen (18) levels deep. And yet it performs perfectly smoothly:

layout_dump2

The deepest nesting in the Facebook app is twenty (20) levels deep. And yet it works just fine:

layout_dump4

The deepest nesting in the Twitter app is twenty three (23) levels deep, which includes eight (8) nesting levels for each item in their ListView (it’s not even a RecyclerView!). And yet I’m able to scroll the Twitter feed infinitely without a single hiccup.

layout_dump1

Therefore I’m compelled to reevaluate the importance we should be placing on optimizing View hierarchies, at least from the perspective of “nesting.”  Indeed, this seems to be yet another case for balancing reasonable performance guidelines with more immediate product goals, or put more simply, avoiding premature optimization.

FileSystemAnalyzer: a tool that does what it says

Today I’m happy to release a tool for low-level analysis of file systems, which includes digging through file system structures that aren’t normally visible when exploring your disks, looking at metadata of files and folders that isn’t normally accessible, and even browsing file systems that aren’t supported by Windows or your PC.

Download FileSystemAnalyzer

This is actually the software that I use “internally” to test and experiment with new features for DiskDigger, but I thought that it might be useful enough to release this tool its own. It accesses the storage devices on your PC and reads them at the lowest level, bypassing the file system drivers of the OS.

On the surface, this software is very simple: it allows you to browse the files and folders on any storage device connected to your PC, and supports a number of file systems, including some that aren’t supported by Windows itself. However, the power of this tool comes from what else it shows you in addition to the files and folders:

FAT

The program supports FAT12, FAT16, and FAT32 partitions. When looking at FAT partitions, you can see the file and directory structure, and detailed metadata and previews of files that you select. When selecting a file or folder, you can also see its position in the FAT table. And indeed you can explore the entire FAT table independently of the directory structure, to see how the table is structured and how it relates to the files and directories:

filesystemanalyzer5

exFAT

Similarly to FAT, this lets you explore the exFAT file system, while also letting you look at the actual FAT table and see how each file corresponds to each FAT entry.

NTFS

In addition to exploring the NTFS file and folder structure, you can also see the MFT table, and which MFT entry corresponds to which file or folder:

filesystemanalyzer3

HFS+

HFS+ is the default file system used in macOS (although it is slowly being superseded by APFS), and is fully supported in FileSystemAnalyzer. You can explore the folders and files in an HFS+ partition, and you can also see the actual B-Tree nodes and node contents that correspond to each file:

filesystemanalyzer2

ext4

Ext4 partitions (used in Linux and other *nix operating systems) are also supported in FileSystemAnalyzer. In addition to exploring the folders and files, you can also see the actual inode table, and observe how the inodes correspond to the directory structure:

filesystemanalyzer4

APFS

Support for APFS is still very rudimentary, since there isn’t yet any official documentation on its internal structure, and requires some reverse engineering. Nevertheless, support for APFS is planned for a near-future update.

Disk images

The program supports E01 (EWF) disk images, as well as VHD (Microsoft Virtual Hard Disk), VDI (from VirtualBox), VMDK (from VMware), and of course plain dd images.

Creating reports

Given the exhaustiveness of the information that this tool presents about the file system that it’s reading, there’s no end to the types of reports that it could generate. Before committing to specific type(s) of reports for the program to create, I’d like to get some feedback from other forensics specialists on what kind of information would be the most useful. If you have any suggestions on what to include in reports, please contact me.

Limitations

For now, FileSystemAnalyzer is strictly a read-only tool: it lets you read files and folders from a multitude of partitions, but does not let you write new data to them. In some ways this can actually be beneficial (especially for forensics purposes), but is clearly a limitation for users who might want to use the tool to add or modify files in partitions that are not supported natively by the operating system.

Feedback

I’d love to hear what you think of FileSystemAnalyzer so far, and any ideas that you might have for new features or improvements. If you have any suggestions, feel free to contact me!

Download FileSystemAnalyzer