Light Probe interpolation using Tetrahedral Tesselations

[bhouston]

Description of the problem

Now that we have a LightProbe class (#16191), the Spherical harmonic class (#16187) merged as well as some shader support(#16152), we should explore adding a Tetrahedral tesselation method for interpolating between light probes to the renderer so that it can set the 4 SH + weights per object.

The best reference is this presentation from Unity itself:

https://gdcvault.com/play/1015312/Light-Probe-Interpolation-Using-Tetrahedral

(Referenced from here: https://docs.unity3d.com/Manual/LightProbes-TechnicalInformation.html)

It seems that given a set of light probes you just do a 3D delaunay tetrahedralization and use 3D barycentric coordinates for interpolation and you cache which tetrahedral each object is in to speed up lookups. Pretty simple, just need a standard delaunay algorithm implemented along with a searchable tetrahedral data structure.

/ping @WestLangley @donmccurdy @richardmonette

[donmccurdy]

Overlaps a bit with my comment in #16223 (comment), but should objects opt in/out for lookups in the light probe volume? For example, static terrain should not be affected. A material-level option, e.g. material.useLightProbes=true/false would be sufficient.

[bhouston]

I think that first one should enable ".dynamicGI" mode on WebGLRenderer, this builds your LightProbe tetrahedralization, etc and keeps it maintained. And then you enable ".dynamicGI" on individual objects to have them opt into the lighting effects that result from this. I prefer it on an object basis rather than on a material basis, it just makes more sense that way. But I guess that may be hard given the Three.JS object model. If it is on a per-material basis then yeah, it probably is .lightProbes = null or .lightProbes = [ a structure of an SH array and a weight array ]. Thus it would behave like .map = null or not. Rather than having two separate variables controlling it.

[donmccurdy]

I prefer it on an object basis rather than on a material basis, it just makes more sense that way. But I guess that may be hard given the Three.JS object model.

Yes, I conceptually like this on an object basis but wasn't sure how that would work. Perhaps it won't be too difficult.

[donmccurdy]

It seems that given a set of light probes you just do a 3D delaunay tetrahedralization ... Pretty simple, just need a standard delaunay algorithm implemented along with a searchable tetrahedral data structure.

This sounded simple enough, but after spending some time on every 3D Delaunay JS library I can find...

• https://github.com/mikolalysenko/delaunay-triangulate
• https://github.com/mikolalysenko/incremental-delaunay
• https://github.com/darkskyapp/delaunay

... I'm not satisfied with the results:

delaunay-triangulate	incremental-delaunay	darkskyapp/delaunay
	bug

Note the near-intersecting lines crossing far corners of each volume, which I think indicate intersecting tetrahedra in the volume. For a simple cube 2x2x2 probe volume, the algorithms are generating 9-10 tetrahedra where 5-6 would be expected.

Referring back to Light probe interpolation using tetrahedral tessellations,

• Bowyer-Watson seems to be the algorithm of choice
• The method of finding the convex hull one dimension
  higher might be elegant and universal, but definitely
  not practical above 2D
• Numerically robust implementation of the incircle and
  orientation tests available from [JShewchuk]
• If you need a ready solution, [TetGen] by Hang Si is
  very decent and has some additional, potentially
  useful functionality, like tetrahedral mesh refinement

I cannot find a JS implementation of Bowyer-Watson. If Tetgen, a C++ implementation, is any indication, it is complex – tetgen.cxx is 35,000 lines of code. I'm mildly curious about the feasibility of compiling Tetgen to WASM, but would like to take a step back before putting time into something like that. In the interest of baby steps, here are some alternatives:

(a) Support a 2D Delaunay triangulation (not tetrahedralization) on the X/Z plane. For many uses this may be sufficient.
(b) Support only fixed grid layouts, similar to Blender's Irradiance Volumes.
(c) Use a simpler but more expensive interpolation method, and require users to limit the number of probes more closely.

Presumably this code will be in examples/js[m]/, rather than the core library, so while I'd like to have a universal solution, partial solutions may be a good starting point.

[donmccurdy]

Here is the relevant code:

dev...donmccurdy:feat-lightprobevolume

In particular, LightProbeVolume.build.

[donmccurdy]

A Comparison of Five Implementations of 3D Delaunay Tessellation, by Yuanxin Liu and Jack Snoeyink, 2005. (predates Tetgen by a year)

[donmccurdy]

Ok, I misinterpreted the visual debugging output I included. After configuring it to render individual tetrahedra instead of just the wireframe I can see what's going on:

(only a few cells shown for clarity)

The interior tetrahedra are just fine. The coplanar points at the boundaries of the volume are creating very thin tetrahedra, which aren't helpful but can be worked around or removed.

This approach is looking feasible.

[bhouston]

Yes, the weird tetrahedral on the outside are well weird, but who cares. This is amazing. Are you going to pre-interpolate the SH via the CPU so that you can just pass in a single SH to each mesh for lighting? This is amazing btw. Holy crap, Three.JS is going GI. :)

[donmccurdy]

Are you going to pre-interpolate the SH via the CPU so that you can just pass in a single SH to each mesh for lighting?

I think so. We could pass all 4 probes from the current cell and interpolate in the vertex shader, but (1) there are other ways to handle larger meshes, and (2) I'm not confident that approach would be correct or continuous near cell boundaries.

[donmccurdy]

Several issues remain (in particular, a lot of flickering...) but this is starting to look functional:

• Demo
• Code

The API could use some consideration. I'm assuming that this code will live in examples/js[m] rather than src/, and that users' applications can decide when to update a particular mesh:

import { LightProbeVolume } from 'three/examples/jsm/probes/LightProbeVolume.js';

var volume = new LightProbeVolume()
  .addProbe( probe1 )
  .addProbe( probe2 )
  .addProbe( probe3 )
  .build();

scene.add( volume );

function render () {

  volume.update( mesh );

  renderer.render( scene, camera );

}

This has some weird facets:

• Both LightProbe and LightProbeVolume extend Object3D. I'm not sure LightProbes should be (directly) added to the scene graph at all. But if not, and they remain in src/, what is their role there?
• How does the interpolated SH value get passed to the renderer? mesh.diffuseProbe? mesh.diffuseSH? mesh.material.diffuseSH?
• Do probe intensities affect interpolation? If a probe's intensity is 0, does that mean it has no weight during interpolation? Or that it has its normal weight, but its coefficients are considered 0? I'm not sure per-probe intensity and color make sense to me here.

[bhouston]

Both LightProbe and LightProbeVolume extend Object3D. I'm not sure LightProbes should be (directly) added to the scene graph at all. But if not, and they remain in src/, what is their role there?

I think that LightProbe only exists in the scene graph during editing. At run-time it should generally not be there. It is a luxury convenience for designing only. Sort of like Geometry, it is a luxury you use when you do not care to be fast or scalable.

How does the interpolated SH value get passed to the renderer? mesh.diffuseProbe? mesh.diffuseSH? mesh.material.diffuseSH?

I think that diffuseProbe should exist on the mesh at least in the long term, but for now I think it isn't too important. Thus this is great.

Do probe intensities affect interpolation? If a probe's intensity is 0, does that mean it has no weight during interpolation? Or that it has its normal weight, but its coefficients are considered 0? I'm not sure per-probe intensity and color make sense to me here.

I am unsure why LightProbe has an intensity that is separate from its SH values. I do not understand it and I think it is unnecessary functionality. If anything, I would make intensity derived from the average intensity of the SH and if you set it, it just derives the current intensity and scales its appropriately. Thus there is no intensity value outside of the SH values themselves. Otherwise it is an unnecessary degree of freedom that just complexifies things.

[donmccurdy]

I think that LightProbe only exists in the scene graph during editing. At run-time it should generally not be there.

I agree with the spirit of this, but functionally it implies...

• LightProbe could be added directly to scene graph (extends Object3D?)
• LightProbe could be added to LightProbeVolume (has position and SH, nothing else)
• LightProbe could be added to a mesh, e.g. mesh.diffuseProbe

... is that too much / overloaded? Does editing necessarily require that the probe be in the scene graph? To preview the effect of a change the LightProbeVolume needs to be rebuilt anyway, so maybe having a LightProbeVolume and LightProbeVolumeHelper might be sufficient for editing purposes.

I think that diffuseProbe should exist on the mesh at least in the long term...

Ok, I'm fine with that. It feels a little unnatural that the result of interpolating among probes should be another probe (I guess I expect the output to be an SH?) but I don't feel strongly about this.

Do probe intensities affect interpolation?

I am unsure why LightProbe has an intensity that is separate from its SH values. I do not understand it and I think it is unnecessary functionality.

@WestLangley @mrdoob would you be OK with removing intensity and perhaps color from the LightProbe class? I think we've agreed that probes do not need to extend Light, and these properties complicate things a bit.