Sunday, September 13, 2020

Infinite plane rendering 3: Image texturing, filtering, and antialiasing

This post is part three on the topic of infinite plane rendering. See part 1 and part 2.

Last time we textured the plane with a simple procedural texture. Now we add a proper image texture. First we use the texture coordinates from the procedural texture in part 2, to place a repeated version of a proper image on our infinite plane.

Filtering

Without texture filtering, we see many artifacts. Notice the graininess toward the horizon. Also note the Moire patterns in the patterns of parallel lines at near to mid distance:

Inifinite plane tiled with an unfiltered image texture. The image looks sorta OK up close, but everything is grainy at larger distances, and patterns of fine lines look bad even at moderate distances.

We can clear up most of those artifacts with trilinear filtering. When creating the texture, call
    glGenerateMipmap(GL_TEXTURE_2D);
and
    glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR_MIPMAP_LINEAR);

Compared to the earlier unfiltered image, this trilinear filtered view avoids most of the artifacts. But the areas near the horizon get too blurry too fast.

Regular texture filtering does not work perfectly for oblique viewpoints, which is always the case near the horizon for our infinite plane. We need to use a technique called anisotropic filtering, which applies different filtering in different directions. Anisotropic filtering is not supported in pure OpenGL, so you need to load an extension GL_TEXTURE_MAX_ANISOTROPY_EXT and use it like this.
   glGetFloatv(GL_MAX_TEXTURE_MAX_ANISOTROPY_EXT, &f_largest);
   glTexParameterf(GL_TEXTURE_2D, GL_TEXTURE_MAX_ANISOTROPY_EXT, f_largest);

With anisotropic filtering, the texture pattern looks better near the horizon (below):

Anisotropic filtering looks better by increasing the sharpness near the horizon. There remain some minor artifacts and shimmering, especially when viewed in VR. But this is the best I know how to do. Besides, we would ordinarily use much less demanding texture images. This texture is specifically designed to reveal display imperfections.

Using a more natural texture image, like the patch of grass below, shows no artifacts when viewed in VR using anisotropic filtering:

After gazing at this infinite vista of grass in VR, the game "Infinimower" practically writes itself.


Efficiency and Antialiasing

Up to this point we have been inefficiently drawing the plane. The vertex shader creates a procedural triangle strip covering the entire screen, and the fragment shader rejects all the pixels not on the infinite plane using the "discard" command. So even if you are looking up, away from the plane, the fragment shader is still executed for every single pixel on the screen. We can be more efficient than this, and also solve the problem of antialiasing at the horizon line at the same time.

So far we have been using a procedural vertex buffer, defined in the vertex shader, that covers the entire visible screen (pink rectangle). This is inefficient because the fragment shader gets invoked for each sky pixel too, even though these are never displayed.

Here we use a more carefully selected vertex set, that matches the exact visible area of the infinite plane. This is a more efficient imposter geometry.

It would be possible to compute the optimal vertices on the host side, but today we'll compute it using a geometry shader program.

This also solves the horizon aliasing problem. Now that we have a triangle boundary along the horizon, it can be antialiased using multisample antialiasing (MSAA). This is a widely used technique so I won't describe the details here.

Shader source code is at https://gist.github.com/cmbruns/5b1c2b211766cdcb3b29689e0c32a63d


Next Time:

  • Using a 360 photo to cover the entire plane.

Wednesday, May 13, 2020

Infinite Plane Rendering 2: Texturing and depth buffer

This is the second post about rendering infinite planes in 3D computer graphics. Last time we got as far as rendering a uniform brown plane. This time we will add texturing and correct use of the Z/depth buffer.

"Brown plane" example from the previous post.

Simplifying the math

Now that I'm looking at all this again, I see that we can simplify the plane math somewhat. Sorry I'm now going to change the variable names to match the plane ray tracing derivation in the OpenGL Super Bible. By the way, we aren't actually doing ray tracing in this infinite plane project, but rather simply "ray casting".

Remember the implicit plane equation from last time:

   Ax + By + Cz + Dw = 0  (1b)

Where:

  • (A B C) is a vector normal to the plane, 
  • (x y z) is any point in the plane, and 
  • D is the signed distance from the plane to the origin

We can rewrite that in vector form:

   P·N + d = 0    (1c)

Where: 

  • N is a vector perpendicular to the plane
  • P is any point on the plane, and 
  • d is the signed distance of the plane from the origin
That dot represents the dot product or inner product of two vectors.

We will combine the plane equation above with the ray equation below:

   P = O + tD    (3)

Where:

  • P is any point along the ray, 
  • O is the origin of the ray (i.e. the camera/viewer location), 
  • D is the direction of the view ray, and 
  • t is the scalar ray parameter. 
Plug (3) into (1c) to get:

   (O + tD)·N + d = 0

now solve for t:

   t = -(O·N + d)/(D·N)

and plug that back into the ray equation to get I, the intersection between the plane and the view ray:

   I = O - D(O·N + d)/(D·N)

Now we can simplify this further: If we solve for the intersection of the plane and the view ray in view/camera space, then the view ray origin O, the position of the camera/eye, is all zeros (0, 0, 0), and the intersection point equation reduces to:

   I = -dD/(D·N)  (4)

That's pretty simple.

In our vertex shader, we compute the intersection point and pass it into the fragment shader as a homogeneous coordinate, with the denominator in the homogeneous w coordinate, as we discussed last time. A GLSL vertex shader code fragment is shown below:



    point = vec4(
        -d * D.xyz,  // xyz, numerator
        dot(D.xyz, N.xyz)  // w, denominator


    );


Texturing the plane

That solid brown plane from the previous post could be hiding all sorts of errors. By adding texturing to the plane, we can visually distinguish different parts of the plane, so it becomes much easier to carefully verify correct rendering from inside the VR headset.

There are 4 different types of texturing we could apply to our plane:


  1. Solid color rendering, like we did in the previous brown plane example.
  2. Ordinary 2D image texture rendering, where an image pattern is repeated over the plane.
  3. Procedural texture rendering, where a computed texture is applied in the fragment shader.
  4. Spherical image texture rendering, using a 360 image. This way we can paint the whole plane with one single image. That's a great way to combine the special "whole universe" coverage of spherical panoramas, with the "half universe" coverage of infinite planes. We will get to this final case in a future post.
For now we will start with the simplest of procedural textures: a color version of the texture coordinates themselves. This helps us to debug texturing, and establishes the basis for other more advanced texturing schemes.

A simple procedural texture tiling this infinite plane.
Now with the texturing in place, we can inspect the plane more carefully in VR, to help debug any rendering defects. For now it's (mostly) looking pretty good.

The grainy junk near the horizon is there because we have no texture filtering. Texture filtering for procedural textures like this is an advanced and difficult task. We won't be solving it here, because this is just a waypoint for us on the way to ordinary image-based texturing. There, the filtering techniques available to us will become much more conventional and straightforward.

Populating the depth buffer

I mentioned in the previous post that our initial brown plane example does not correctly clip through other objects. Let's correct that now.

We can compute the correct depth buffer value for the plane intersection point by first converting the plane/ray intersection point into clip space (Normalized Device Coordinates) and then insert the depth value into the Z-buffer in the fragment shader.

  vec4 ndc = projection * point;
  ...
  gl_FragDepth = (ndc.z / ndc.w + 1.0) / 2.0;


Notice the top section of a cube mesh being correctly clipped by the infinite plane. The rest of the cube is correctly hidden beneath the surface of the plane. Thanks to gl_FragDepth.
There is one more nuance to using infinite planes with the depth buffer. We need to use a special sort of projection matrix that goes all the way to infinity, i.e. it has no far clip plane. So, for example, two infinite planes at different angles would clip each other correctly all the way to the horizon. To infinity! (but not beyond...)

Shader code for this version is at https://gist.github.com/cmbruns/3c184d303e665ee2e987e4c1c2fe4b56


Topics for future posts:


  • Image-based texturing
  • Antialiasing
  • Drawing the horizon line
  • What happens if I look underneath that plane?
  • More efficient imposter geometries for rendering

Sunday, May 10, 2020

How to draw infinite planes in computer graphics


Back in 2016 I figured out how to draw an infinite plane, stretching to the horizon, in my VR headset.  I did this because I wanted a very simple scene, with the ground at my feet, stretching out to infinity. This blog post describes some of the techniques I use to render infinite planes.

These techniques are done at the low-level OpenGL (or DirectX) layer. So you won't be doing this in Unity or Unreal or Blender or Maya. Unless you are developing or writing plugins for those systems.

The good news is that we can use the usual OpenGL things like model, view, and projection matrices to render infinite planes. Also we can use clipping, depth buffering, texturing, and antialiasing. But we first need to understand some maths beyond what is usually required for the conventional "render this pile of  triangles" approach to 3D graphics rendering. The infinite plane is just one among several special graphics primitives I am interested in designing custom renderers for, including infinite lines, transparent volumes, and perfect spheres, cylinders, and other quadric surfaces.

Why not just draw a really big rectangle?

The first thing I tried was to just draw a very very large rectangle, made of two triangles. But the horizon did not look uniform. I suppose one could fake it better with a more complex set of triangles. But I knew it might be possible to do something clever to render a mathematically perfect infinite plane. A plane that really extends endlessly all the way to the horizon.

How do you draw the horizon?

The horizon of an infinite plane always appears as a mathematically perfect straight line in the perspective projections ordinarily used in 3D graphics and VR. This horizon line separates the universe into two equal halves. Therefore, our first simple rendering of an infinite plane just needs to find out where that line is, and draw it.

The ocean surface is not really an infinite plane, of course. But it is similar enough to help motivate our expectations of what a truly infinite plane should look like. Notice that the horizon is a straight line. Image courtesy of https://en.wikipedia.org/wiki/File:Into_the_Horizon.jpg
But before we figure out where that line is, we need to set up some mathematical background.

Implicit equation of a plane

A particular plane can be defined using four values A, B, C, D in the implicit equation for a plane:

Ax + By + Cz + D = 0  (1a)

All points (x y z) that satisfy this equation are on the plane. The first three plane values, (A B C), form a vector perpendicular to the plane. I usually scale these three (A B C) values to represent a unit vector with length 1.0. Then the final value, D, is the signed closest distance between the plane and the world origin at (0, 0, 0).

This implicit equation for the plane will be used in our custom shaders that we are about to write. It's only four numbers, so it's much more compact than even the "giant rectangle" version of the plane, which takes at least 12 numbers to represent.

When rendering the plane, we will often want to know exactly where the user's view direction intersects the plane. But there is a problem here. If the plane is truly infinite, sometimes that intersection point will consist of obscenely large coordinate values if the viewer is looking near the horizon. How do we avoid numerical problems in that case? Good news! The answer is already built into OpenGL!

Homogeneous coordinates to the rescue

In OpenGL we actually manipulate four dimensional vectors (x y z w) instead of three dimensional vectors (x y z). The w coordinate value is usually 1, and we usually ignore it if we can. It's there to make multiplication with the 4x4 matrices work correctly during projection and translation. In cases where the w is not 1, you can reconstruct the expected (x y z) values by dividing everything by w, to get the point (x/w, y/w, z/w, 1), which is equivalent to the point (x y z w).

But that homogeneous coordinate w is actually our savior here. We are going to pay close attention to w, and we are going to avoid the temptation to divide by w until it is absolutely necessary.

The general principle is this: if we see cases, like points near the plane horizon, where it seems like coordinate values (x y z) might blow up to infinity, let's instead try to keep the (x y z) values smaller and stable, while allowing the w value to approach zero. Allowing w to approach zero is mathematically equivalent to allowing (x y z) to approach infinity, but it does not cause the same numerical stability problems on real world computers - as long as you avoid dividing by w.

By the way, the homogeneous version of the plane equation is

Ax + By + Cz + Dw = 0  (1b)




Intersection between view ray and plane

The intersection between a line and a plane (in vector notation, those are cross products and dot products below) is


I = ((Pn(VL)) - PV)/(Pn·V)    (2)

where I is the intersection point, Pn is the plane normal (A B C), V is the view direction, L is the camera/viewer location, and Pd is the D component of the plane equation.

Problems can occur when the denominator of this expression approaches zero. The intersection point needs to be expressed in the form (xyz)/w. Instead of setting w to 1, as usual, let's set w to the denominator Pn·V.

This means that the w (homogeneous) coordinate of the point on the plane intersecting a particular view ray will be the dot product of the view direction with the plane normal. The range of w values will range between -1 (when the view direction is directly opposite the plane normal) and +1 (when the view direction is exactly aligned with the plane normal). And the w value will be zero when the view is looking exactly at the horizon.

At this point, we can actually create our first simple rendering of an infinite plane. And we only need to consider the homogeneous w coordinate of the view/plane intersection point at first.




Version 1: Brown plane

Here is the first version of our plane renderer, which only uses the homogeneous w coordinate:
Screenshot as I was viewing this infinite plane in VR

The horizon looks a little higher than it does when you look out at the ocean. But that's physically correct. The earth is not flat.

This plane doesn't intersect other geometry correctly, the horizon shows jaggedy aliasing, there's no texture, and it probably does not scale optimally. We will fix those things later. But this is a good start.

Source code for the GLSL shaders I used here is at at https://gist.github.com/cmbruns/815fc875afd8fe2755500907325b15f0

Continue to the next post in this series at https://biospud.blogspot.com/2020/05/infinite-plane-rendering-2-texturing.html

Topics for future posts:


  • Texturing the plane
  • Using the depth buffer to intersect other geometry correctly
  • Antialiasing
  • Drawing the horizon line
  • What happens if I look underneath that plane?
  • More efficient imposter geometries for rendering

Thursday, March 03, 2016

What programming language do 20-year-olds use?

In the interest of converting vague correlations into divisive stereotypes, here are some programming languages, sorted by the age of the programmer:
  • 70 year-old programmers code in FORTRAN
  • 60 year-old programmers code in COBOL
  • 50 year-old programmers code in C++
  • 40 year-old programmers code in Java
  • 30 year-old programmers code in JavaScript
  • (I don't know what 20 year-olds do; something on smartphones?)
  • 10 year-old programmers code in Minecraft command blocks
  • newborn programmers (will) code in Code-a-pillar*
  • Everyone codes in Python for their hobby projects, because life is short.
 * I am not affiliated with the makers of Code-a-pillar. I just think it's funnier to have the 20-year-olds be the only ones I'm confused about.

Corollary: Asking programmer job applicants what their strongest programming languages are should be illegal in the USA, where "age" is a protected hiring category.


Friday, October 02, 2015

High-performance Visualization of Neurons, Molecules, and Other Graph-Like Models Using Quadric Imposters


 In my day job in scientific visualization, I am sometimes called upon to display models of neurons or molecules. Both types of models are "graph-like", in the computer science data structure sense, in that they consist of a collecion of Nodes, connected by Edges.

General Graph data structure. This graph consists of six edges and seven nodes.






In the case of molecules, the Nodes are Atoms, and the Edges are Bonds. Molecules and atoms make up all of the air and earth and animals and tacos and all the other stuff of the world.

This serotonin molecule contains 24 atoms and 26 bonds. This representation uses spheres and cylinders to represent atoms and bonds.
In the case of neurons, the Edges are piecewise linear segments of neurites, and the Nodes are branch points, tips, and bends of those segments. In both molecules and neurons, the Nodes have an XYZ location in space, and a size. These Nodes are usually well represented by spheres of a particular size.

This neuron has many branch points, tips and bends. Neurons are the cells that animals use to think and to control movement.
In the past few years, I have been very interested in using Quadric Imposters to represent scientific models. I have been able to achieve very high-performance rendering, while attaining flawless image quality. By high-performance, I mean that I am now able to display models containing hundreds of thousands of nodes, with flawless performance, compared to perhaps only thousands of nodes using traditional mesh-based rendering methods.

Imposter models look better and run faster. What's not to like? The only downside is that it requires a lot of tricky work on the part of the programmer. Me.

You probably learned the quadratic formula in high school:
$$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$$

In any case, the quadratic formula can be used to solve for \(x\) in polynomial equations of the form:
$$ax^2+bx+c=0$$ 

So the trick for imposter rendering is to derive a quadratic polynomial for each analytic shape you want to display. I have already done this and have it working for the following shapes:
  • Sphere (easiest)
  • Cylinder
  • Cone
I wrote a little about sphere imposters in the past.

I plan to eventually do the same treatment for
  • Ellipsoid
  • Ellipsoid cylinder
  • Ellipsoid cone
  • Single sheet hyperboloid
  • Dual sheet hyperboloid
By the way, I just now started using  MathJax for displaying equations. The equations look nice, right?


Sunday, March 17, 2013

Chumby and Zeo and Reader; Oh My!

My old digital lifestyle is falling apart. Three of my daily standbys are being discontinued.

It started last month when my Chumby, a sort of internet connected clock radio, stopped displaying my chosen widgets, and started showing only one weird clock. It turns out they have been out of business for a year.

Then I heard that Zeo, my headband-mounted sleep-tracker, is going out of business. Unlike chumby, I had time to download my historical data in advance. But I might not be able to get my FUTURE sleep data.

Now I learn that Reader, Google's RSS aggregation service will be shut down this summer. That's how I read the internet! I'm looking into feedly as a replacement.

There is a positive way to look at this. Perhaps the sickly vestiges of the previous boom economy are being sloughed off, so the next boom can commence.

Saturday, July 14, 2012

Seven ways to communicate depth in 3D graphics

This video from YouTube shows a molecule visualization I created this morning, using a little application I have been working on.  I'm using this as an excuse to pontificate about my philosophy of 3D visualization today.

Much of my work centers around creating computer software for visualizing various three-dimensional objects.  These applications run on computers with two-dimensional displays; so there is a problem with conveying information in that third (depth) dimension.  The human brain is hard-wired to convert two dimensional visual information into an internal three-dimensional representation of a scene.  We can leverage this specialized hardware to convey a sense of depth using only a two dimensional screen.

You might assume that I believe stereo 3D to be the best way to convey depth information.  But you'd be wrong.  I am an evangelist for stereoscopic visualization.  I love stereo 3D displays.  But there are at least four other 3D visualization techniques that are more important than stereo.  You must nail those four before you even think about stereo 3D.  Below I have summarized my list of seven ways to enhance the perception of depth in 3D computer applications.

Without further ado; the list.  In order of most important to least important:
  1. Occlusion  

    Occlusion is the most important cue for communicating depth (Not "ambient occlusion", that's a kind of shading, technique #2). Occlusion means that you cannot see an object when it is behind another object.  It's that simple.  But displaying occlusion correctly is the most important part of conveying depth in computer graphics.  In my caffeine video, atoms in the front occlude the atoms behind them.  Fortunately, almost nobody gets this wrong; because everyone recognizes that it looks terrible when it is done wrong.  OpenGL has always used a z-buffer to manage occlusion, so most 3D applications get occlusion right.  Another approach, used by side-scrolling video games, is the "painters algorithm" (draw the stuff in back first) to give a sense of depth by occlusion.

    Occlusion tells me that the orange thing is in front of the other things.

    One interesting display technique that does not respect occlusion, is volume rendering by maximum intensity projection.  Although volume rendering is difficult to do well, the maximum intensity projection method yields a robust rendering of brightness and detail   But the image looks the same whether viewed front-to-back or back-to-front.  I know from experience that this can be confusing.  But the advantages of the maximum intensity projection can sometimes make this tradeoff worthwhile.

  2. Shading

    By shading, I mean all of the realistic colors, gradations, shadows and highlights seen on objects in the real world.  Shading is so important, that when some folks say "3D graphics", all they mean is fancy shading.  This is one area that has been steadily evolving in computer graphics. My caffeine video uses a primitive (by modern standards) Lambertian shading model for the spheres, with a single point light source.  The Lambertian model is sufficient to convey depth and roundness, but looks rather fake compared to state-of-the art rendering.  Part of my excruciating jealousy of QuteMol comes from the clever shading techniques they have used.  For this reason I plan to continue to improve the shading methods in my application.

    Just look at the beautiful shading possible with QuteMol. I'm so jealous:

  3. Perspective 

    Perspective, what artists call foreshortening, is the visual effect that objects close to you appear larger than objects far away from you.  In my caffeine video, nearby atoms appear larger than distant atoms, especially when the molecule is close to the camera.  This is one area where my worship of QuteMol breaks down.  QuteMol appears to use orthographic projection, not perspective.  Close atoms are rendered the same size as distant ones.  But it took me a long time to notice, because QuteMol's beautiful shading is otherwise so effective at communicating depth.
  4. Motion parallax

    There are several ways that motion can reveal depth information by showing parallax, in which closer objects appear more displaced than more distant objects.  When an object rotates or moves, parallax effects reveal important depth information.  In my caffeine video, the rotations of the molecule help to convey the sense of depth.

    Many 3D visualization applications use mouse dragging to rotate the scene.  Users are constantly rotating the scene with the mouse while trying to examine the objects.  These users crave motion parallax.  In response, I have been experimenting with automated subtle wiggling of the scene so the user might not need to constantly drag the mouse.  But I am not sure I have nailed the solution yet.

    Another important source of parallax is when the viewer moves. This is the basis of head tracking in 3D graphics.  Every time I give a stereoscopic 3D demo, the first thing the viewer does after putting on the 3D glasses is to move her head from side to side; because that is the natural response to wanting to maximize the perception of depth.  But it doesn't work; because my applications do not do head tracking (yet).  Motion parallax is more important than stereoscopic 3D.

    The video below from 2007 is a famous example of the effectiveness of head tracking for conveying depth.
  5. Stereoscopy 

    Your left and right eyes see slightly different views of a scene, and your brain can use these two images to perceive your distance from the objects you see.  This is static parallax, as opposed to motion parallax (described in the previous section).  Done properly, stereoscopic viewing can complete the sense of depth in a scene.  But there are a lot of ways to get it wrong.  That is why stereoscopic display must be approached with extreme care.  My caffeine video uses YouTube's awesome stereoscopic support to display the molecule in stereo 3D.  I like viewing it with my Nvidia 3D vision glasses (requires a special 120Hz monitor); though for some reason the aspect ratio is wrong in this mode.   The other 3D modes seem to work fine though.  Part of what I enjoy about stereo 3D is that there are so many details that must be done correctly;  I like details.
  6. Fog 

    When you see a mountain on the horizon far away, it appears much paler and bluer than it does close up.  That distant mountain can be almost indistinguishable from the color of sky behind it.  The more distant an object is, the closer its color becomes to the color of the sky.  Even on a clear day, for extremely distant objects, like far off mountains, what I am calling "fog" has an important effect.  On a foggy day, the same thing occurs on a vastly smaller scale.  In either case, that change in color is an important cue about the distance of an object.  In computer graphics, fog (or depth cueing) is easy to compute and has been used for ages, especially when other 3D effects were too hard to achieve. My molecule viewing application uses fog, but at a low setting, and might not be visible in my caffeine video.  Fog is especially important as objects approach the rear clipping plane, to avoid "pop ups", the sudden appearance or disappearance of objects.  It is more pleasing if the objects disappear by gradually receding into the fog.
  7. Depth of field

    When you photograph a scene using a wide aperture lens, the focal point of your scene may be in sharp focus, but other objects that are either much closer to the camera or much farther away appear blurry.  This blurriness is a cue that those other objects are not at the same distance as the focal point.  This depth cue can also convey a false sense of scale in trick photography.  An aerial city scene with an extremely narrow depth of field can appear to be just a tiny model of a city.  Depth of field is not widely used in interactive computer graphics, because it is expensive to compute, it's a subtle effect, and to really do it properly, the focused part of the image should follow the user's gaze.  Not just head tracking; but eye tracking would be required.  Even the Hollywood movies make only light use of depth of field; in part because it is not possible to be certain where the audience's gaze is directed.

Most of the techniques I know of can be assigned to one of those seven categories. Have I missed any other depth conveying techniques?   Comments are welcome below.