# Feasibility of cylindrical rasterization? (Alien GPUs)

### Background / Rationale

Many fictional worlds feature sapient herbivores, but rarely spend much time considering how their tools and technology would differ. In the course of writing my story, however, I've come across one point of particular relevance...

Most herbivores (due to predation) have much wider horizontal fields of view than humans. While this may not be an issue for "functional" displays, it seems likely to be relevant when it comes to entertainment. To wit, these sophonts would prefer to not feel as if they're wearing blinkers when they go to watch a movie... or play a video game.

Now, for filmed and projected media, humans already have the technology to address this (and this world assumes a similar technological progression)... and "looking through a window" isn't always an issue. However, having a reduced field of view is already annoying to humans in some cases, especially "first person" games, and I can only imagine how much worse the effect would be for a sophont that's used to 270° or even 360° vision.

Here, however, we have a problem. Modern rasterization is based on projecting a 3D scene onto a flat 2D plane. The math for this is fairly straight forward; yes, it's linear algebra, but at its core, it's all based on addition, multiplication, and a bit of division. Because of this, significant pincushion distortion occurs when trying to render a scene at high FOV (example), and FOV ≥ 180° is mathematically impossible.

In the early days, multi-monitor setups would be quite popular, with multiple independent viewpoints being rendered. Catering for such setups would be the norm, rather than the exception... but the holy grail is combining rounded displays with true cylindrical projection.

The trouble is... cylindrical projection requires (AFAIK) doing trigonometry, which makes rasterization much more complicated.

### Question (TL;DR)

Is it plausible for a world which is technologically equivalent to our own (circa 2021) to have 3D video games (and other content) which use cylindrical projection while still being otherwise comparable (i.e. visual quality and frame rate) to what we have in the real world? How far back could this have existed? (IOW, could their early, circa-1995 games predating hardware 3D acceleration, have done it? Would it need to wait for circa-2020 GPUs? Something in between?) Keep in mind that this world is strongly motivated to achieve this (it's not just a curiosity, as it would be for us humans), so solutions requiring explicit hardware support (similar to how hardware ray tracing is starting to be a thing) are acceptable.

For bonus points; would spherical projection be possible? If so, would it be harder, easier, or comparably challenging? (The folks that keep insisting that "VR displays" will be mainstream some day¹ would really like to know...)

(¹ For reasons that aren't relevant, this world is quite far behind the real world in the development of VR headsets.)

### Technical Explanation

"Traditional" projection — that is, projection onto a planar "screen" — follows the formulae $$p_h = P * p_{world}$$ and $$p_{screen} = p_h .xyz / p_h .w$$, where $$P$$ is a 4×4 matrix which can be precomputed. Modern GPUs are, of course, highly optimized for performing linear algebra like this.

For cylindrical projection, I believe this continues to work for the $$y$$ component (at least, a similar calculation should be possible), but $$x$$ requires an arc[co]sine and some conditional branching, and I'm not entirely sure about $$z$$. ($$z$$ is the distance from the "screen" and is important for culling, depth testing, and some effects such as "fog". I don't know the actual formula for $$z$$ in a cylindrical projection, but I have a sneaking suspicion it requires taking a square root... which can be optimized pretty heavily, but is still another operation compared to planar projection.)

### Postscripts

• Please note that I'm not looking for hand-waved answers. Essentially, what I want to know is if and when the real world could do this, if we'd started working on it circa 1990 and applied similar resources to the problem as are applied to other aspects of modern GPUs. (Hence the tag.)

• Don't worry about display technology. Our real world abilities to display wide-HFOV content are close enough that it's easy to imagine them being up to the task if we'd had the desire to produce such displays. Similarly, producing filmed or pre-rendered HFOV content is easily accomplished in the real world. I'm only concerned with real-time rasterization.

• Assume the desired output has uniform radial spacing, i.e. each pixel has the same physical dimensions. Also assume that the quality loss of rendering using "traditional" techniques and distorting is considered unacceptable.

• ??? I am not sure that I see what exactly is the great additional complexity. Could you maybe explain in a short paragraph what part of the rendering process you consider to be heavily impacted by projecting onto a cylinder instead of onto a plane? Please also consider both plain olde skoole scanline rendering and the much more realistic ray casting and ray tracing processes. Is taking an arc sine for each vertex such a costly operation? Jan 4 at 19:12
• P.S. "Significant pincushion distortion occurs when trying to render a scene at high FOV": distortion (pincushion or not) won't occur unless the rendering process simulates a non-rectilinear lens. (And it is "wide" field of view, not "high".) For the best realistic effect, the field of view should correspond to the distance between the observer's eyes and the image; any significant deviation will make the image feel as if the perspective was altered, although it will not actually be. But altered perspective is not distortion. Jan 4 at 19:19
• "Is taking an arc sine for each vertex such a costly operation?" I suppose that's the question I'm really asking. AFAIK, the answer is "yes" (and that's possibly per fragment, not just per vertex). Rasterization relies on the projection of a vertex being a matrix product plus a division, with no trigonometric functions. As for "distortion", maybe that's not exactly the right word, but I think it's what most laymen would call this. Jan 4 at 19:33
• (1) What is a "fragment"? You mean a polygon? And "that" is looks very much like the grossly exaggerated simulation of the perspective alteration resulting from a ridiculously large field of view, as if the image was photographed with a rectilinear lens with an impossibly short focal length -- I cannot get the image to look right even if placing my eye a few centimeters away from the monitor. (2) That is why I suggested a comparison between plain scanline rendering (where the added arc sine might have a measurable impact) and ray tracing (where one arc sine would be utterly negligible). Jan 4 at 19:45
• Conclusion: Feasible either way, with only a +/-10 years if their tech progress is comparable to ours. Jan 4 at 21:58

First off, the herbivories you talk about having 270-360 degree vision tend to have little to no overlapping field of vision (monocular vision), thus lacking certain properties of 3D vision. most of their world tends to look fairly flat as it is, so the importance of 3D entertainment would not be as attractive to them as it is to a being with binocular vision.

Due to evolutional pressures, most prey animals, those that would benefit from monocular vision, do not focus on distances of objects, but focus on the presence of objects and their general direction relative to the observer. Many either lack visual acuity of humans, as their vision is basically go-no go, or their color perception is different in some way.

For such a creature, I would suggest focus less on clarity and depth perception of the entertainment, and focus more on display range and they quantity and quality of the audio/visual stimuli of the entertainment being provided.

After millions of years of being hunted and killed by predators, these creatures react to visual and audible stimuli. Now that they the undisputed rulers of the animal kingdom of their world, they may get a kick out of watching a bunch of abstract objects bounce around 200 degrees of their vision, feeling comfort that they do not need to fear such images. By contrast, they could feel comforted or calmed to see images of dull, slowly moving object in the front view (such as one would see wind blowing through trees.) Sharp, quickly moving objects at certain posterior view angles could be seen as exciting action or horror flick. To achieve some of these varied angles of views, it may be culturally encouraged to have large, wide or multiple screens set up to properly display the content.

Basically, to explain an entertainment system of a creature that once was a prey animal, one must understand the anatomy and psychology of the creature to know what they would actually react to.

• "3D" in this context is less about depth perception (that's stereoscopic 3D) and more about virtual worlds that are navigable in three dimensions. IOW, the difference between Microsoft Flight Simulator and Galaxian. For that matter, I feel like "real" 3D would be even more important to herbivores than to us. Jan 4 at 19:49
• a creature with monocular vision would not be too concerned about the depth of the images and be more entertained about images occupying more of their field of vision. You can paste 2D images all around them and they'd be entertained. A human observing the same thing would find it dull and they would miss 90% or the action Jan 4 at 19:56
• So... your assertion is that such critters will never care to create realistic graphics? Never be interested in "sight-seeing games"? Never progress from Pitfall to Tomb Raider? I'm just not buying that. (It also explicitly doesn't help me, because I have reasons to want them to want such.) Even if I bought that, just knowing where to place sprites involves trigonometry in a way it never did for us in the real world. Jan 4 at 20:11
• not saying they would not create realistic graphics. Just it would be suited to their desires. Im sure an eagle race were to observe out 8k TVs, they would probably laugh at out poor quality graphics and complain there is too much going on in the peripherals. A mantis shrimp would call our color selection bland Jan 4 at 20:14
• @Matthew I think he's saying since herbivores lack depth perception to begin with, what parameters humans use to define "realistic" would be different from that of an evolved herbivore. 3D depth is a very human experience.
– user93359
Jan 4 at 20:33

Just for a starting point, here's the equation for spherical projection of a vertex $$v$$ using Euler angles for visibility into how it's composed.

$$v' = v X Y Z$$

where:

$$X = \left[ \begin{array}{abc} 1 & 0 & 0 \\ 0 & \cos{\theta} & \sin{\theta} \\ 0 & -\sin{\theta} & cos{\theta} \end{array} \right]$$

$$Y = \left[ \begin{array}{abc} \cos{\phi} & 0 & -\sin{\phi} \\ 0 & 1 & 0 \\ \sin{\phi} & 0 & \cos{\phi} \end{array} \right]$$

$$Z = \left[ \begin{array}{abc} \cos{\psi} & \sin{\psi} & 0 \\ -sin{\psi} & cos{\psi} & 0 \\ 0 & 0 & 1 \end{array} \right]$$

and, for a vertex located at <1, 0, 0> before projection,

$$v = \left[ \begin{array}{abc} 1 \\ 0 \\ 0 \end{array} \right]$$

Please correct me if I'm wrong, but I believe cylindrical projection is just losing one degree of rotation, such that Z becomes :

$$Z = \left[ \begin{array}{abc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right]$$

## Computational Expense of Trig Functions

In older computers, the expense of trig functions was mediated by using pre-calculated tables,

$$\begin{array}{abc} \theta & \sin{\theta} \\ 0 & 0 \\ 30 & 0.5 \\ 45 & 0.7 \\ 90 & 1 \end{array}$$

and performing linear interpolation to get an approximation of the exact value.

$$y = {({x - x_{n-1}}) \over ({x_n - x_{n-1}})} ({y_n - y_{n-1}}) + y_{n-1}$$

I don't think there's a technical problem.

• Or, when they wanted really good approximations, they used the CORDIC algorithm, which is quite fast, giving one bit of precision per iteration. Jan 6 at 11:58
• Learned something new. Thanks! Jan 6 at 14:05
• Ah, yes... I hadn't thought of that; a GPU could certainly implement trig via a lookup table and linear interpolation (probably one with 32+ entries rather than only 4), and that would be "pretty fast" and probably good enough, especially for this particular use. Jan 6 at 15:53
• BTW, I don't think this is a coordinate system conversion. It looks like the formula for the rotation matrices to converting from a body's local (Cartesian) coordinates into world (Cartesian) coordinates. Jan 6 at 16:00
• Isn’t local to world what is being looked for? The example seems to be moving an object into the viewing plane for truncation of one axis and display of the other two. Jan 12 at 10:04

No real difference in rendering technology

Your screen would be different, but the creature has already adjusted the "projection issues" in its brain, no special GPU is needed, just a different projection formula.

While rendering a scene, the ray marching involves simulating rays hitting the view cylinder perpendicular, instead of hitting a view plane perpendicular.

Cameras may be more difficult

Cameras would require special measures: you'd have a very toric lens, with a cylindrical ccd inside, which may be quite a challenge to construct.

• "no special GPU is needed, just a different projection formula"... that does not follow. Yes, a different projection formula is needed; that's stated in the premise. The (admittedly highly technical) question is whether or not applying that formula (which is significantly different, at least computationally) can be done while maintaining similar performance. Jan 4 at 21:59
• It would be done at a similar speed, because the transformation would involve the usual Quaternion matrix, only with different coefficients. The hardware would have a different shape, but your pixels would still be organized in (projected onto) a rectangular grid on the surface of the cylinder (or torus).. maybe I understand your question wrong ? it would help to add a drawing explaining the problem. Jan 4 at 22:13
• I'm not sure what you call a "Quaternion matrix". If there's a homogeneous matrix that can transform from 3D cartesian coordinates to cylindrical coordinates via a simple multiplication, please show how to compute such a matrix, because AFAIK it can't be done. Jan 4 at 22:20
• A quaternion makes cylindrical projection easier (angle). But anyway, I'm afraid you're in the wrong forum.. check out graphicdesign.stackexchange.com/questions/tagged/3d maybe hypothetical cylindrical eyes are allowed there ? for a software answer you could go stackoverflow.com/questions/7981815/… Jan 4 at 22:34
• I think you meant gamedev.stackexchange.com 🙂. I considered that, but as much as I'd love to know how feasible this is in real life, I don't think a hypothetical "would this work if we'd spent the last 25-30 years caring about it?" sort of question would go over well there. Jan 4 at 22:38

I'm going to deem this "plausible", but it probably has to wait for the equivalent of modern (circa 2020) GPUs.

First off, we need to understand how existing rasterization works. As noted in the question, planar projection requires only a homogeneous matrix. By composing multiple matrices, we can account for the camera position and orientation, as well as the field of view and screen size. In essence, the transformation from world space to screen space is a single matrix multiplication followed by a single vector division. This involves only operations which are reasonably fast, and modern GPUs have of course been heavily optimized for this sort of thing.

Cylindrical projection throws a wrench in the works, because the conversion from world space to screen space can no longer be represented so trivially. Indeed, we end up needing to do three steps:

1. Convert from world space to camera Cartesian space. Basically, this step accounts for the position and orientation of the camera. The result is a Cartesian coordinate, but one which has been "normalized" such that 0,0,0 is the focal point of the camera and the basis vectors correspond to basis vectors of the camera. This is accomplished via affine transformations, same as for planar projections.
2. Convert from camera Cartesian space to camera Cylindrical space. The result is a vector with $$-\pi \le x \le \pi$$ where $$[0,1,1]$$ maps to itself¹.
3. Convert from camera Cylindrical space to screen space, such that $$[-1,-1,z]$$ and $$[1,1,z]$$ represent the corners of the screen. What makes this interesting is that it entails a homogeneous transform for the $$y$$ coordinate. This will account for the horizontal and vertical fields of view.

(¹ The selection of orientations is somewhat arbitrary, but does not affect the problem.)

By comparison, planar projection can accomplish steps 2+3 with a homogeneous matrix transform, allowing all three steps to be combined. Thus, cylindrical projection requires three steps to accomplish what planar projection can do in one.

What about the second step? How is that transformation accomplished? Well...

• $$x' = atan(x,y)$$
• $$y' = hypot(x, y)$$
• $$z' = z$$

...where $$atan$$ is a somewhat-magic function that yields the appropriate angle. Note that this function, internally, needs to perform some multiplications based on the sign of either $$x$$ or $$y$$ in addition to computing the arctangent (which will additionally require a division). Given sufficient motivation, this can be approximated to a degree that is most likely "good enough" using linear interpolation between known values derived from a hardware look-up table (thanks to James McLellan for pointing this out). So, we're looking at a vertex transform that is probably takes about 2-3 times as long as for a planar projection.

Unfortunately, that's not the end of the story.

The planar projection of a line is... a line. This is what allows us to quickly rasterize a triangle from its transformed vertices. (It's not quite that simple since linear interpolation of the U/V coordinates isn't quite right, but this was "good enough" for the early days.)

The cylindrical projection of a line, however, is a conic section. In fact, any line whose endpoints lie at different $$x'$$ values is going to be curved i screen space to some extent. This means all of our quick-and-dirty methods of rasterizing a triangle are "out", and there is no cylindrical projection before dedicated hardware acceleration.

Early implementations are more likely to render at larger-than-needed resolution and then texture map (using traditional techniques) onto a screen-covering mesh. The quality won't be as good as "proper" rendering, but it will effectively pick up some antialiasing at a similar cost as MSAA. The mesh can be pre-computed once and does not change frame by frame.

However, all is not lost. We can approximate a curve with a series of straight lines. Make the line segments short enough, and the discrepancy between the curve and the line segments becomes unnoticeable.

Moreover, we already take a similar approach for subdivision surfaces using geometry shaders. Doing this effectively and without unacceptable performance sacrifices will require "modern" GPUs with dedicated hardware acceleration, but leads to an interesting corrolary; 3D rendering in this world makes much more use of subdivision surfaces as compared to the real world, and may have been doing so for (comparatively) longer.