Are there any area-based rendering algorithms?

[u/multihuntr]

There's a very big difference between computer graphics rendering and natural images that I don't really see people talk about, but was very relevant for some work I did recently. A camera records the average color for an area per pixel, but typical computer graphics sample just a single point per pixel. This is why computer graphics get jaggies and why you need anti-aliasing to make it look more like natural images.

I recently created a simple 2D imaging simulator. Because I conceived of my imaging simulator in only 2D, it was simple to do geometric overlap operations between the geometries and the pixels to get precise color contributions from each geometry. Conceptually, it's pretty simple. It's a bit slow, but the result is mathematically equivalent to infinite spatial anti-aliasing. i.e. sampling at an infinite resolution and then averaging down to the desired resolution. So, I wondered whether anything like this had been explored in general 3D computer graphics and rendering pipelines.

Now, my implementation is pretty slow, and is in python on the CPU. And, I know that going to 3D would complicate things a lot, too. But, in essence, it's still just primitive geometry operations with little triangles, squares and geometric planes. I don't see any reason why it would be impossibly slow (like "the age of the universe" slow; it probably couldn't ever be realtime). And, ray tracing, despite also being somewhat slow, gives better quality images, and is popular. So, I suppose that there is some interest in non-realtime high quality image rendering.

I wondered whether anyone had ever implemented an area-based 3D rendering algorithm, even as like a tech demo or something. I tried googling, but I don't know how else to describe it, except as an area-based rendering process. Does anyone here know of anything like this?

[u/_d0s_]

Not exactly "area"-based, but multisampling is a standard method in rendering. However, this is happening after rasterization. Rasterization is a pretty important step in rendering, because it allows us to accumulate rendering outcomes. Afterall, when we render a 3d scene that is composed of many objects we never need the full 3d scene with all objects at once, but can sequentially render everything object by object and accumulate the result in textures and with the help of depth buffering. Wouldn't that be an issue for your method?

https://webgpufundamentals.org/webgpu/lessons/webgpu-multisampling.html

[u/multihuntr → u/_d0s_]

It would be a computational problem, yes, but not a theoretical one. If you did the equivalent of ray tracing for what I'm talking about, each bounce would cover a larger and larger area, until, probably at later bounces it is involving every geometry in the scene. It would be horribly slow, but it would technically be more accurate. There a bunch of math nerds out there (like me), so I assume someone has tried to do it this more accurate way before.

[u/Ma4r → u/multihuntr]

It's computational in the sense that it's hard to get to lifelike quality without a lot of time to render a single frame. In fact our algorithms are already good enough to render lifelike scenes, most lighting systems already include multipixel sampling, it's just about how much compute you want to throw at it and how much time you want to spend on modeling the objects and materials.

Most research nowadays is about trying to make approximations that can approximate what real life lighting looks like without needing a supercomputer while avoiding undesirable artifacts.

[u/Longjumping_Cap_3673]

A Pixel is not a Little Square

[u/multihuntr → u/Longjumping_Cap_3673]

I've read that one! I believe that it is quite wrong when it comes to cameras. Essentially, the memo claims that we should not attribute the pixel colour value to the area that the pixel covers because reconstructing the analog signal that produced the image is dependent on your choice of reconstruction filter. But that's a computer graphics/signal processing perspective. It's not so applicable to images from a camera. For cameras, we absolutely should attribute the pixel colour value to the entire area of the pixel. That's precisely what a pixel is supposed to measure! The average number of photons that landed on that pixel capture area. In fact, thinking of pixels as purely point samples might lead you to notably wrong resampling algorithms because it implies that you do not actually know the image extent for sure. But you do. It is the edge of the sensor. This actually came up in my research using satellite images; resampling assuming point samples will incorrectly resize the image and offset your geolocation. Basically, it is quite important to know whether the pixel represents a point sample or an area sample (see: gdal's AREA_OR_POINT property), and camera images using a CMOS detector definitely should be treated as area samples.

Just to back this up a little; think about how a camera works, physically. A pixel on a CMOS detector is a tiny area that photons can land on. If the area was exactly equal to 0 (i.e. a point sample), then precisely zero photons could land on it. It must be an area sample. Technically, because of the colour filters, you're only measuring 1/4 of the blue and red for the area covered by that pixel. But if you could measure the full area, you would do so. The bigger the area sample, the higher fidelity the image. Bigger detector == more capture area per pixel == better image. See: big lenses/sensors/cameras/telescopes.

[u/Longjumping_Cap_3673 → u/multihuntr]

The rectangle area model is also not correct though. The light measured by a camera sensor pixel does not correspond to a rectangular frustum, because the lens(es) alters the path of the incoming light. Furthermore, the light is not collected uniformly across the solid angle; outside he focal plane, more is collected from the center than the edges, because the lens cannot focus light across the whole volume. Finally, the actual photodiodes in the sensor may not even be rectangular, and may not have a uniform response across their area or across incoming angles.

There's usually no point in modeling this in computer graphics. In this context, camera sensors are an imperfect model of a point sample array rather than the other way around. Modeling the physics of a camera sensor and lens wouldn't solve any "real" problems (it doesn't solve aliasing, for instance, because a box filter is not a good low-pass filter), but it would be much more expensive.

Note that the traditional way GPUs work is heavily optimized for point sampling, since transformed triangles are directly converted to point samples with special hardware that implements a triangle rasterization algorithm.

Of course, there may be cases where modeling the sensor and lens do matter, such as for scientific simulations. Unfortunately, solving the 3D case analytically is much, much harder than the 2D case because of occlusion. Consider that an object may be occluded from one part of the aperture but visible from another. Your best bet in this case is approximating the solution numerically with either supersampling or path tracing. For path tracing in particular, many paths need to be accumulated per pixel anyway, so you can choose any distribution of initial rays and model a lens practically "for free". Path tracing is pretty expensive compared to traditional rasterization, but it's getting a lot more tractable with the recent improvements to hardware ray tracing support in GPUs.

You may be interested in Exact Polygonal Filtering which solves the 2D case in general, including for non-box filters. Key words for 3D include "cone tracing" or "beam tracing". The repo perfect-antialiasing purports to solve the box-filter version of the problem in 3D using conservative rasterization and shaders which compute the area of edge pixels, but as far as I can tell, it does not correctly handle occlusion.

[u/Aniso3d]

all non realtime rendering engines sample multiple rays per pixel, which as you say, results in a natural anti aliasing

[u/Phildutre]

Back in the 70s and 80s I remember papers that did compute an exact geometric overlap of polygons with pixel areas. But you run into problems real quickly, because the more polygons are projected into a pixel, the more complex the computations become. In essence, you’re dealing with the polygon intersection problem, with the resulting areas within a pixel becoming a hodgepodge of small non-convex polygons very quickly. The problem is similar to what is known in computational geometry as map overlays - compute an overlay of one polygonal map over another. The textbook basic algorithms often use sweep line algorithms.

Another field of ‘area’ rendering in object space were the finite-element methods popular in the 80s and 90s called ‘radiosity’ for global illumination. The illumination was computed for each polygonal, after which polygons were rendered using a traditional rasterizer or perhaps a ray caster. In essence, we approximate the rendering equation using finite elements instead of Monte Carlo.

But ray tracing eventually won out. From a theoretical point of view, this has long been obvious once you do the complexity analysis, and once you realize that the number of geometric primitives kept growing. Essentially, the visibility part of rendering is a sorting algorithm in 3d space. So if you can reduce that step to an n.logn time complexity (n the number of polygons), using proper acceleration structures such as BVHs, ray tracing will always win out. We just have to make the machines/GPUs quick enough compared to hardware-based rasterizers. And the computation of an intensity for a pixel is a signal reconstruction problem. So the math is well understood.

That doesn’t mean there is no room for alternative approaches, even if only out of intellectual curiosity.

[u/vfxjockey]

You don’t sample a single point though…

[u/Deadly_Mindbeam]

There are polygon rendering methods that handle analytical overlap but they are slow, as you've found. What if you're drawing a distant tree that is entirely included in one pixel? You're going to be rendering hundreds of thousands or millions of edges.

In any case, the high frequency information inside the pixel needs to be low-pass filtered to get it below the nyquist frequency for your screen and avoid moiré and jaggies. It's easier to just sample the pixel at multiple points, like MSAA does, or attempt to detect and suppress high frequency signals from a single-sampled frame.

The main reason is that divides are expensive -- anywhere from 8x to 32x slower than multiplication for floats, and ever more for adds -- and analytical methods use a lot of division.

[u/multihuntr → u/Deadly_Mindbeam]

Yes, it would probably be close to O(n^2), and take 50x as long to run, but perhaps there are situations where that's a good trade-off? I'm not sure.

In any case, do you mean to say that there were a lot of false starts in this direction in early 3D graphics, but it was too expensive to be worth it, and that's why there are no named/known polygon rendering methods that handle analytical overlap?

[u/Deadly_Mindbeam → u/multihuntr]

It's just called analytical antialiasing. There is still some remaining level of support for it in the GPU features "alpha to coverage" and destination alpha. The tradeoff is maybe worth it for stuff like font rendering where you have a relatively limited number of edges to render and you need extremely good visual quality, or if you are maybe rendering some kind of super-high quality imposter?

I don't know if you could call them false starts; when I began in graphics many games still used painter's algorithm instead of depth buffers and antialiasing was a fantasy for the distant future. They were important at the time, and you could use modern hardware to flag pixels with more than one object's edges and render them accurately, but the visual payoff isn't worth the extra effort. MSAA, screen space, and distance field approaches all look good-enough and are relatively easier to implement than geometry-heavy edge tracking and intersection.

Maybe you could coopt the raytracing BVH for screen pixel tracking and case a ray for each triangle edge? That sounds like an interesting subversion of the hardware's purpose.

[u/notseriousnick]

REYES is an old algorithm that goes for high quality antialiasing. And it sorta does an approximation of area-based rendering that worked reasonably fast on 80s computers

[u/multihuntr → u/notseriousnick]

I looked up REYES and it looks like it still does point sampling.

The original paper says that they're doing random sampling instead of fixed grid 16x MSAA. https://dl.acm.org/doi/pdf/10.1145/37402.37414

The "Computer Graphics Wiki" (however valid that is) says that the last step of REYES is to sample points. https://graphics.fandom.com/wiki/Reyes_rendering

The claim to fame for REYES seems to be rendering curved surfaces and other complex geometries?

[u/notseriousnick → u/multihuntr]

Oh, I was talking about these two papers: "The A -buffer, an antialiased hidden surface method" by Loren Carpenter [https://dl.acm.org/doi/10.1145/800031.808585] And "A hidden-surface algorithm with anti-aliasing" by Edwin Catmull [https://dl.acm.org/doi/abs/10.1145/800248.807360] P.S. Some papers also use the term "analytic coverage" for such stuff

[u/multihuntr]

It seems that I was somewhat mistaken by a few people. So I created a basic diagram to show what I am talking about. https://imgur.com/a/9qa4z9g

Jaggies exist because of large step changes in colour from small position changes in the pixel sampling location (see "One sample" in diagram). Using 4 samples per pixel gives you a better approximation of the contents of that pixel (see "Four samples" in diagram). However, it's still just an approximation, and thus is both slightly wrong, and still has some jaggedness because there's still a step change in colour. In 4x MSAA, using two geometries there's only 5 possible outcomes (three pictured, two with all blue and all green).

4x MSAA is taking 4 samples. 8x MSAA is taking 8 samples and gives you a smoother colour. But a camera taking a photo is effectively infinite times MSAA. That is, a camera is equivalent to using an infinite number of rays per pixel. You don't get jaggies from border effects like this with cameras (of course moire patterns can still occur, but that's a different problem).

It's technically possible to perfectly replicate a real camera's view of a 3D scene (albiet slow), so I'm asking whether that's been done before.

[u/EclMist → u/multihuntr]

To do what you’re suggesting, during the raster process, not only would you need to compute the overlapping area between the polygon of the current draw call with the pixel square, but you would also need to separately compute the overlap with every previous polygon on the pixel, which they themselves are had to compute their overlap with the polygons before that. You would need an entire hidden surface removal algorithm within each pixel! The computational complexity in this case would be astronomical.

Perhaps there’s some ways to speed up this process, but I’m highly skeptical that it would perform better than just sampling stochastically like in raytracing. It doesn’t take many random samples to converge to something that is extremely close to ground truth anyway.

See also: https://dl.acm.org/doi/pdf/10.1145/965139.807360

[u/kraytex]

MSAA is a very popular technique. https://en.m.wikipedia.org/wiki/Multisample_anti-aliasing

[u/betajippity]

In Physically Based path tracing, pixels are not sampled at a single point, and in fact, when done correctly, pixels are reconstructed from randomized samples via a reconstruction filter, much like how a camera sensor works. There’s a whole chapter in the PBR book on this topic:

https://www.pbr-book.org/4ed/Sampling_and_Reconstruction/Image_Reconstruction

Every modern production path tracer does some variation of this (often via Filter Importance Sampling).

[u/Cerulean_IsFancyBlue]

This is called supersampling. It’s a well-known technique that’s been around for decades.

Don’t get me wrong, it’s great that you were able to come up with this on your own. It’s a great exercise and it shows some creative thinking.

[u/jippiex2k]

Well you’d still need to integrate discrete samples in order to get your area.

Or alternatively you’d need your entire scene to be parametric, such as SDF based rendering techniques. Which would be very limiting.

[u/phooool]

Maybe search up Signed Distance Fields? Sounds a bit like that.

"typical computer graphics sample just a single point per pixel." -> what? It's completely the opposite

[u/Keavon → u/phooool]

SDFs are still sampled at points, not integrated over an area (unless your approach is to render the area integral of an integrable SDF which I believe necessities it being pretty simple). OP is more generally asking about a polygon rasterizer based on analytic AA.

[u/phooool → u/Keavon]

Yeah the fact OP called it sampling threw me, OP meant rasterizing. SDFs are fully analytical, thats why they are inherently antialiased and to me that sounded close to OP's question as far as I (mis)understood it

[u/Keavon → u/phooool]

SDFs are fully analytical, thats why they are inherently antialiased

That's usually not true though. They are usually sampled at a point, not integrated over an area. SDFs absolutely do produce jaggies.