As I woke up this morning I got greeted by a WordPress-ping that somebody (Chris Hellmuth, from https://www.render-blog.com/) had cross-referenced an earlier blog post of mine, about the first few fun steps of wrangling the Moana Motunui Island Model (see original post here)…. back then still with Embree and OptiX.

Chris’ blog talks about the next step of that voyage: making Moana render well with a GPU (and in particular, OptiX) : for his full post, look here: https://www.render-blog.com/2020/10/03/gpu-motunui/. It’s an interesting read indeed.

Now looking at this post, I got reminded that I never wrote about my own experiences with this … because of course, the very first thing I did when switching to NVidia two years ago was to start writing a OptiX-based renderer for Moana – there isn’t anything like a challenging model to find weak spots and painpoints, so of course that’s the first thing I did. At the time, getting Moana to run on a GPU wasn’t actually all that easy: Turing had only just come out, OptiX 7 wasn’t even out, yet, and though the – back then just released – RTX 8000 cards did finally have some “real” GPU memory (48GB, to be exact), dealing with a model of that size and complexity still wasn’t exactly easy.

The whole journey is actually a story of many fits and start (and re-starts, and re-re-starts, ….) because this model is so challenging on so many fronts – but still, I did get this to render some two years ago … but never shared any results from that. Initially this was because early version contained a lot of work-arounds for limitations that have since gone away: For example, OptiX 7 is much more effective at rendering this model than OptiX 6 was; and even OptiX 7 initially had some restrictions that required workaround (eg, at most 16 million instances). For the latter problem at some point I actually wrote some really cool tools – and most of a never-published paper – about the best way of transforming a more-than-16-million single-level instance model into a multi-level instancing model…. which is an interesting problem indeed … but I digress.

Another issue I initially had to fight a lot with was memory consumption: For the first version I did indeed need two 8000s coupled with NVLink, at least when loading textures and/or tessellating curves – I could actually replicate the “high-frequency” data like acceleration structures, but vertex positions, shading normals, textures, etc, were shared over NVLink. The latest version can squeeze it all into less than 48GBs (at some point I squeezed it into a 24GB RTX 6000!), so if you have more than one card you can actually have them render in parallel …. but again, i digress.

Yet another issue I ended up spending a truly unholy amount of time and brain power on is textures: the original textures for Moana come in Disney’s Ptex format, for which I couldn’t find any CUDA sampling code …. and doing texturing on the host (which yes, one can do, through managed memory and some nasty multi-pass thingys… just saying) kind-of defeats the purpose. So, eventually I ended up writing some additional tools that would bake out the ptex’es into little 8×8 or 16×16 textures for each invidual pair of triangles in this model, to throw those into some larger texture atlas (because no, CUDA does not like a few million tiny textures ), and then doing some fancy texture coordinate mapping to make bilinear hardware texturing work with that. Thinking about it, that problem alone would be a fun blog post to write about….

Anyway. I digress. Again.

Having read Chris’ blog I was reminded that I should probably dig out some of that code I wrote these two years back. A lot has changed since then – in particular, the OWL library (that I initially wrote for pretty much this project!) has become quite a bit more mature; and a lot of the early limitations have since been lifted in OptiX. Anyway, I did manage to at least make this code compile again, so here’s the very first picture of I got after the first 10 minutes of re-activating whatever code of that I could still find:

Quite obviously, this’ll need some more work to make it look pretty again: For some reason the water is now entirely white (it’s still a full path tracer, though, as you can see on the indirect illumination on the trees). Also, the environment map is missing in this pic, and the light sources are floating around as actual red square geometry pieces (on the beach, in the lower left). Also, memory usage is a bit higher than I remember (close on using the full 48GB, it should be less). Anyway – it still works. I’ll see if I can fix those missing pieces, and will post those, too, once done.

BTW: The entire project is – obviously – all written on top of OWL; in fact, it was one of the main drivers for this library, because it became pretty clear early on that if you want to focus your thoughts on what matters (like how to wrangle the content), then you really do want something that having something that takes the job of acceleration structure builds, Shader Binding Table construction, uploading of textures, buffers, etc, off your hand, and that you can reasonably rely on. Which, of course, reminds me of the fact that I still haven’t written about OWL. Which I should. And will. I promise.

With that: back to fixing that path tracer….

PS: In case anybody is wondering: roughly half of those 47GBs that it uses is textures ….

Update 1: Textures

Huh, as usual, it took a bit longer than expected, but here some first pic with real textures. The image above did contain some texels (quite a few, actually), but was actually buggy …. in my defense, I did say that dealing with this baking out is tricky. And it actually helps to realize that the pbrt file may actually contain the same logical texture in multiple different pbrt “ImageTexture” nodes. Here some first picture of one (!) of the corals. Gives you an idea of how massive this model really is: In the default picture, that entire shot will probably map to a single pixel (and is under the water).

Update 2: Envmap …

Turns out my github pbrtParser library I was using to load the model had somehow been broken over the course of the last few years, and didn’t actually “remember” any of the light sources again. Well, fixed that (which was a lot of work), after which making the environment map appear was as simple as using OWL’s recent support for 2D textures, and copying a few lines of code from Matt’s pbrt-v3 library (to match his fancy way of mapping from a ray direction to texture u/v coordinates).

And with that (four hours for the former, 15 minutes for the latter :-/) here we are once again with a proper environment map (and proper environment map lighting, of course):

(obviously that’s without the water and beach – still need to re-convert the full model after the parser fixes).

Also interesting how much of an impat the choice of lighting can have on the objects: here’s the same Coral as above, but now with the env-map lighting rather than a default “oversaturated white” that I used above:

TLDR: If any vis (or other researcher) is in need of a large unstructured mesh data set (tets and/or other linear elements): I’m hereby sharing a properly wrangled and pre-processed version of the “NASA Mars Lander” Data Set (link at bottom).

For those that haven’t yet heard of this data set: It’s one of the most amazing data sets I’ve ever gotten my hands on – partly because of the amazing back-story (simulating the landing of Mars, how much geekier could it get?), but also because

1. it’s gigantic (over 6 billion tets – yes, billion, not million)
2. it’s not – as most ‘big’ data sets – some artificial test case, but a “real world” data set (yes, the did simulate at that accuracy)
3. it even contains multiple time steps, so you can make cool animations (see here: https://developer.nvidia.com/techdemos/video/d2s20)
4. it’s a “raw” data drop in the sense that this is really what the sim code (Fun3D) wrote out (ie, it’s useful for “in situ” and “data-parallel rendering” research, too; and
5. it actually looks awesome when rendered:
   

   

    

   (image credits: Nate Morrical, UofU)

The full, unadulterated  data for that “Mars Lander Retropulsion Study” is available from the “Fun3D Retropulsion Data Portal” at https://data.nas.nasa.gov/fun3d/, and has been made available for the wider vis rendering community by the scientists that ran this data (for full attribution, see https://data.nas.nasa.gov/fun3d/), with a lot of help from Pat Moran.

Unfortunately, if you start working on that data you’ll quickly realize that the main reasons for its awesomeness – its  “raw data dump” nature, and sheer size – have a flip side in that getting this data into any form useful for rendering comes with a “non trivial” amount of data wrangling : you need to get the thousands of different files downloaded, parse them, strip ghost cells, extract variables and time steps, re-merge from hundreds of per-rank results to a single mesh, etc. Doing so has been a lot of fun, but it was also a lot(!) of work (even for somebody that has a lot of hardware, and a lot of experience dealing with those things)… so to make it easier for others to use this data I decided to make both the result of my wrangling, and the code used for doing it, available to others that might want to work with it.

The resulting data for me is – for both the “small” (order three-quarters of a billion tets) and the large lander (about six billion – with a ‘b’) — a single unstructured mesh, with a single per-vertex scalar field (for me, ‘rho’, for one of the later time steps). For really high-quality rendering you probably want more than one variable; and/or multiple time steps …. but since my google drive space is limited I’ll provide only these two dumps, which should be more than enough to get you started. I’ll also provide the library I wrote to deal with this data set, so anybody serious enough to deal with data of that size should be able to follow my steps and extract other variables, time steps, etc.

With that:

• The data I made available on my google drive: https://drive.google.com/drive/folders/1NwteqBEd4WDAWlWNEfgjRX_FWeEwq1Di (if anybody has a better/more permanent link to host this data, let me know!)
• The library I used for it (‘umesh’ for ‘unstructured mesh’ library) is available under apache 2 on my gitlab page; https://gitlab.com/ingowald/umesh/

And as usual: Any comments/praise/feedback/criticism…. let me know. I’d be particularly interested in hearing from you if you actually use this data!

Cheers

Ingo

PS: If you end up using this data, please do not forget to properly attribute the researchers that made this data available; please check the corresponding info on the original data portal!

Having introduced the idea of a series of articles on “fun problems” earlier today, let’s get the first one out of the door: How to tetrahedralize an unstructured mesh that contains pyramids, wedges, and hexes, into a mesh that contains only tets, and in a way that one does not lose any shared-face connectivity in the output mesh. Most of the unstructured meshes I dealt with in the past have been “pure” tetrahedral meshes, but more recently more and more of those I encountered in any unstructured-mesh visualization projects also contained wedges, pyramids, and hexes – sometimes because those are natively the most obvious choices (eg, in the Agulhas data set multiple water depth layers for a triangulated ocean surface nativly form wedges, etc), and sometimes because the dual mesh of a structured AMR data set actually contains pyramids, wedges, and hexes, … so there we are. Maybe the most prominent example of such data is the NASA Mars Lander Retropulsion study data set that they recently released – almost all tets, but a few wedges thrown in, too. But since triangles and tets are so much easier to deal with, the most obvious choice for such data sets (if only for comparison purposes) is typically to simply tetrahedralize them into a tet-only mesh.

Now: Why is this tricky? After all, splitting an given wedge, pyramid, or hexahedron into tetrahedra isn’t all that complicated (in fact, I actually do remember that as a toddler I had toy puzzle with colored plastic tetrahedra that did just that!). After googling for solutions to that I found that you can actually also split a tet into five tets (rather than the obvious six ones), but that aside, the basic concept of tetrahedralizing such unstructured meshes isn’t all that complicated.

The problem, in fact, comes in through the back-door, if one innocently expects this tetrahedralization to maintain proper face connectivity: ie, if two elements shared a face in the input, we want the generated tetrahedra to also share faces in the output. For those faces in the input mesh that were triangle faces — ie, the four faces of any input tet, the four sides of an input pyramid, and the front and back sides of a wedge — that’s actually not a problem: those are triangles, and those won’t change. For those faces that are quadrilaterals, however — ie, the the base of a pyramid, the left side, right side, and bottom of a wedge, or the six faces of a hexahedron — it’s a bit more complicated: if the element itself gets split into tets these sides will, by necessity, have to end up as pairs of triangles… and there’s two ways of doing that, based on which of the two opposing pairs of vertices in that quadrilateral one ends up connecting.

Now if both elements that originally shared a quadrilateral face do this split in exactly the same way then both elements would end up with the “same” pair of triangles, so each triangle from the one element will have a matching one from the other one, and all is good. If, however, those two adjoining elements end up splitting that face in different ways, then the one’s triangles will not match the other ones, which can be, ahem, “problematic” for all the kind of algorithms that assume that each face can tell what the neighboring tet on the other side of that face would be (e.g., for face-to-face ray marching, or for the “shared faces” method in our 2019 “RTX Beyond Ray Tracing” paper).

In fact, even for algorithms that do not need to know this “neighbor on the other side”, ending up with an inconsistent way of splitting these shared faces can result in nasty surprises: quadrilateral faces in an unstructured mesh do not (!) have to be planar, but can actually be general bilinear patches (to visualize this imagine a hexahedron that’s a perfect cube, then take one of the vertices and pull it into an arbitrary direction …. then the three faces adjoining that vertex will become curved, bilinear patches). Now if two elements share a bilinear patch but split that into two triangles with different edges, then the resulting tet-mesh would either have a gap between these elements (if both chose the inward-flipping edge), or both elements would overlap in a tet-shaped region (if both flip outwards … and in case you were wondering: one going inwards and one going outwards only happens if they select the same edge).

Though this problem is kind-of obvious once one thinks a bit about it, I actually had to learn the hard way; most illustrations of wedges and hexes show only planar faces, so it took me a while to figure out why rendering my first tetrahedralized meshes seemed to produce some nasty “pockets” of empty space. Well, learned that one, didn’t we?

Anyway, i digress again. How to fix that problem? First obvious idea is to just make sure that all pairs or elements that share a face will always flip the same way; e.g., by always placing the edge into the vertex with the smallest index, or always picking the shorter of the two edges, etc. Again I spent quite a while trying to do just that, only to realize that this isn’t actually that trivial, either: to do this one would have to be able to independently choose the edge orientation in any of a hex’s faces …. but you can’t do that because at least one pair of opposing faces in a hex always has to have the same orientation (in case you’re wondering: tetrahedralizing a hex works by first using a diagonal plane to split it into two wedges, but that means that the two opposing faces split by that plane will have the same edge orientation….). Now I’m sure there’s a global optimization problem somewhere in there that would allow to somehow rescue that idea, but at that point I realized that this is a good deal more tricky than initially thought.

So, what else to do? Instead of always splitting each quad face with an edge into two triangles, I decided to instead insert a new vertex into the center of each such face, and split it into four triangles by connecting this new vertex to the four edges of that face (for unstructured meshes with scalar per-vertex data we obviously also have to interpolate the scalar values for this new vertex).  The obvious downside of this is that one has to create some new vertices, which has all kind of issues (more vertices, more tets, more memory; the need to interpolate scalar values, etc) …. but if we’re willing to do that we can guarantee that any shared bi-linear patch will always end up with the same four vertices.

Having decided to do this for the faces, the next question is how to actually tetrahedralize the elements such that the faces will end up with this pattern. Here some little illustrations:

First, a tet will obvious remain a tet, no changes whatsoever.

Second, let’s look at a pyramid, which has exactly one bilinear face (see sketch below this paragraph, red and blue faces just for illustration): We create a new vertex C in the center of this face (by averaging vertices 0,1,2, and 3; green arrow), then connect this new vertex with the top (4) and the four base vertices (0-3, new edges in green), and and up with four nice tets that, on the bottom face, create exactly the pattern we’re aiming for (green for new edges on that face). Perfect.

(and, yes, i absolutely did steal my kid’s school pencils for this awesomely professional illustration… and free-hand sketching is so much faster than all the fancy programs!)

Third, let’s look at a wedge with front face 0,1,2 (blue) and back face 3,4,5 (red). We now have three quadrilaterals to deal with, for each of which we want to have the “four triangles” pattern described above. Luckily, there’s an easy way to create just that: we simply ignore the faces completely, and create a new vertex C in the center of the wedge (again, by averaging); now if we connect this new vertex to the existing five faces we end up with two tets (C to front and back triangle), and three pyramids (C to bottom, left and right quadrilateral). For the pyramids we do the same as described above, so our desired pattern appears on all quad faces of our wedge, too … perfect.

One will obviously have to further subdivide the three pyramids in this sketch (ending up with a total of 16 tets), but that got too much to draw …. and should be obvious.

Finally, compared to the wedge case the hexes are almost trivial: create a center vertex C, then connect it to the four faces, and get four pyramids …. feed those into step 2, and done.

All in all, that algorithm is trivially simple to code up (oh, if only I had found that one earlier ….). Only one thing to consider: thanks to limited floating-point accuracy it is, in theory, possible that two elements sharing a face might end up with slightly different results for the center vertex, which might then throw off the code to find the “matching” triangles. This can, however, easily be avoided by always sorting the four vertex indices before adding the vertices, in which case both elemens would always perform the same computations, and up with the exactly same vertex (note we only have to do that for the face vertices, the inner vertices in the wedge and hex case are only ever created once, anyway).

As said above, the algorithm is simple, and foolproof; the main disadvantage is that additional vertices require more memory, and compute more tets, than tessellating without introducing new vertices. For example a hex can be represented with as few as 5 tets… but in our method it would create 24.

Hope that whoever found that page found it useful – I only wish I had found one like this before I tried the other routes. I wouldn’t be surprised at all if lots of people had done exactly that before, too … in fact, I’d be surprised if nobody did…. I just couldn’t find it. Any comments, suggestions, or issues with this: let me know!

PS: Fun fact – this all started with “just” needing to produce some more testing data for our “RTX Beyond Ray Tracing” paper – why not simply take an AMR data set (that we had plenty of), compute the dual mesh, and then tetrahedralize the result … can’t be that hard, right? Well …

It’s been a while since I’ve written anything; for a lot of reasons (it’s 2020, what can I say….).

Anyway. One thing I recently realized is that there’s a ton of stuff I should be writing either papers and/or blog articles about (such as the OWL project, https://owl-project.github.io/, some of my “Moana on GPUs” experiences, or some of my recent work on data-parallel ray tracing) …. but that I don’t get to because I spend far too much time worrying about writing up other things that are fun, but significantly less important. These are typically “side problems” that I ran into while working on something totally different – often things I thought were trivial, but that suddenly turned out to be unexpectedly tricky, and that I (say: google) simply couldn’t find any solutions for.

Anyway. Many of these (solutions to) fun problems do indeed need to get documented if only so I could reference them in my code or papers ….  but in “proper paper form” – with previous work, discussions, comparisons to other solution, and in particular all the insane latex-polishing and perfect-figure-crafting – it just takes up too much time, and distracts from the real problems.

So. To break that log-jam I’ve decided to instead share some of these ideas in blog form; using hand-drawn-and-scanned scribbles rather than perfectly designed illustrations (if only i could have all the time back I spent experimenting with ever new sketching program ….), using wordpress rather than latex (oh my beloved \vspace*{…}, \multicolumn{}, and \includegraphics{}….), and doing away with all the stuff that otherwise takes up so much time. To distinguish those write-ups from any other “update”-style articles I’ll explicitly tag each one with a “Fun Problems:” prefix; in the same spirit as the “ISPC bag of tricks” series i wrote a few years ago. Basically they’re the same category: something worth sharing that’ll hopefully(?) help others; but that’s not worth making a real paper about.

As such: on to the first one – how to tetrahedralize a unstructured element with pyramids, wedges, and hexes, without losing proper shared-face connectivity….

Not sure if a “blog post” is the right medium for that, but just in case anybody stumbles over this: I just upgraded my ubuntu 18 based laptop to ubuntu 20, and after that ran into some issues compiling my CUDA projects – apparently, the gcc version 9 that Ubuntu 20 ships with isn’t yet supported in CUDA (at least, not in the version I have installed!?), meaning I ended up with an error of

/usr/local/cuda/include/crt/host_config.h:129:2: error:

#error -- unsupported GNU version! gcc versions later than 8 are not supported!

Just in case anybody else stumbles over this, the solution is actually quite simple: First, make sure to install the ‘g++-8’ package:

sudo apt install g++-8

(note: mind the “++”: my machine already had `gcc-8` installed by default, but you need g++-8)

Once installed, just tell nvcc to always use ‘/usr/bin/gcc-8’. If you’re using cmake under linux, that’s as simple as setting CUDA_HOST_COMPILER to /usr/bin/gcc-8; cmake and make should then run through just fine.

Hope that helps.

PS: I also previously experimented with using ‘alternatives’ to change my system to use gcc-8 by default, but that didn’t go all too well: yes, setting gcc-8 as default compiler did make nvcc work, but the next apt update ended up being quite confused …. not good. Setting it in the project seems to work just fine.

PPS: Update – for another machine I also installed U20 “from scratch” (rather than upgrading). In this case, installing U20 was actually an amazingly impressive experience: not only did it install out-of-the-box on a RTX-enabled Thinkpad laptop that I had not gotten any other distribution to run on at all, it even came with pre-packaged nvidia 440 driver, with apt packages for CUDA, etc. You still need the “g++-8” think from above, but overall that was a very pleasant experience.

As Matt Pharr just let me know: the original Graphics Gems II cover image was in fact a 3D model, and was in fact even ray traced! (that really made my day 🙂 ).

That notwithstanding, the challenge still stands: Anybody out there to create (and donate) a 3D model of that that looks somewhat more “ray trace’y” for us all to play with?

PS: And I promise, we’ll work very hard to ray trace that faster than what was possible back then … I’ll leave it to you to find out how fast that was! (Tip: The book has an “About the Cover” page 🙂 )

Usually I use this blog to share updates, such a newly published papers, etc …. but this time, I’m actually – kind-of – calling for some “community help”: In particular, I’m curious if there’s any graphics people out there that knows how to use a modelling program (I don’t; not if my life depended on it :-/), and that would be able to create a renderable model of the “scene” depicted on the “Graphics Gems 2” book. To be more specific, to create a model that looks roughly like that:

Now you may wonder “where does that suddenly come from?” … so let me give a tiny bit of background: We – Adam Marrs, Pete Shirley, and I – recently brainstormed a bit about some “potentially” upcoming “Ray Tracing Gems II” book (which hasn’t been officially announced, yet, but ignore that for now), and while doing so we all realized how much we are, in fact, channeling the original “Graphics Gems” series (which at that time was awesome, by the way!).

Now at one instance, I was actually googling for the old books (to check if they used “II/III/IV” or “2/3/4” in the title, in case you were wondering), and while doing so stumbled over this really nice cover … which would probably look amazing if that was a properly ray traced 3D model rather than an artist’s sketch. And what could possibly be a better cover image – or test model – used in RTG2 than the original cover from GG2!?

So – if there is anybody around that know his modelling tools, and looking for a fun challenge: Here is one! If anybody does model this and has anything to share – ideally full model with public-access license, or even only just images – please send it over. I can of course not promise that we’ll actually use such material in said book (which so far is purely hypothetical, anyway) – but I’d find it amazing if we could find a way of doing so.

PS: Of course, a real-time demo of that scene would be totally awesome, too 🙂