I was having some conversation with chatgpt and he gave me this nice optimisation for LOD.
the trick is to avoid Math.sqrt() when updating by using distanceToSquared instead of distanceTo.
simply store the squared distances instead of normal distances and then evaluate the distances with distanceToSquared.
i suggest u use bounding sphere radius instead, cube is complicated
So this is effectively saying that, instead of using the “distanceTo” extension to compute distance:
d = sqrt(x^2 + y^2 + z^2) where d = distance, x = x distance, etc.
you should use the “distanceToSquared” extension:
d^2 = (x^2 + y^2 + z^2)
in cases where you don’t need the actual distance, but simply need to compare distances between objects?
I wonder if there is a similar extension you can use if you want to compute distance (or distance^2) from the origin (0,0,0) or if you have to create a dummy vector3(0,0,0)?
Wonder no more – lengthSq()
Thanks!
In another discussion, I opined that using these extensions would be slower than doing the math yourself since they are like a subroutine. But is that true?
When JS is compiled/interpreted does it treat them as subroutines or does it simply insert the contents of the “subroutine” into the program?
As an analogy, in shaders you can define a segment in such a way that, when the shader is compiled, the entire segment will be inserted automatically in the shader wherever it is referenced..
It’s a huge topic, but it depends on the js engine running the js. I think V8 can identify hot pieces of code like that and inline them where appropriate… via “PGO” profile guided optimization… so it might notice if length() is in your hot path, and notice that length is only a few lines of code, and decide to inline it.. Or it may decide that the cost of the sqrt itself dwarfs the subroutine call, so leave it as a function call… and similarly with lengthSq() it may decide to inline it since it’s just a few multiplies.
I’d be interested to see it profiled, and to see whether the general js overhead turns the difference between lengthSq and length into something negligable. I usually just reach for .length() first, and when I get to optimizing based on my profiling.. switch. It’s not worth the mental overhead if you’re doing it a handful of times per frame, but for 100s/1000s of objects, it might make a real difference.
It’s also quite interesting that this technique can even be effective at the scale of js. AFAIK even C/C++ compilers don’t do PGO by default, rather it’s something you have to invoke manually, but it’s something that you can be done automatically at scale if you’re compiling code on the fly as it’s running, like js engines do.
I doubt you will notice any difference in performance, unless you have a massive amount of calculations … but in this case something else will outslow the rendering.
The JS standard does not fix how such functions are compiled – whether they are inlined or not depends on the specific implementation of the JIT compiler.
You could make a test, and post here the results.
Thanks mathrax and PavelBoytchev
I am only using the distance calculation in my “Effects” module where I am computing the sound delay due to distance. Where accuracy is not an issue, I generally use a 3-way comparison to determine whether the point is within a cube.
If I were really interesting in avoiding the square root computation and was willing to forgo some accuracy, I could revert to the “old time” method of creating look-up tables.
Or could the sqrt function be made to work faster if you were willing to accept some lesser level of accuracy, e.g., if you were just happy with integer input and an integer result? Is there an extension for that (e.g. isqrt)?
Processors have sqrt as machine instruction. Replacing it with custom solutions is justified only in very iconoclastic use cases.
In his paper Structured Programming with go to Statements, page 268, Donald Knuth wrote:
In case the link does not work for you, here is a snapshot:
100% this ^
Also micro-optimizations like this have a very different reward curve in javascript vs compiled langs.
I doubt lookup tables would have as much of an effect due to js… but you never know until you profile profile profile!
heck the sqrt might even be faster than a 3 if check… but ^ is real.
PavelBoytchev and mantrax, I agree. For my purposes, trying to develop a better version probably would be a waste of time. That’s what I like about three.js - a lot of smart people have done most of the work for us.
And, bobWinner, that’s what I like about the original post: I have worked with three.js for several years. But from this post I learned about an extension that I did not know existed and I learned the importance of avoiding square root computations, if possible.
Thank you all!
The results of the benchmark below are appealing :
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>LOD Benchmark - distanceTo vs distanceToSquared</title>
<style>
* {
box-sizing: border-box;
}
body {
margin: 0;
padding: 30px;
background: #0f1117;
color: #e8eaf0;
font-family: system-ui, -apple-system, BlinkMacSystemFont, "Segoe UI", sans-serif;
}
.container {
max-width: 1100px;
margin: auto;
}
h1 {
margin-top: 0;
color: #ffffff;
}
.subtitle {
color: #9299aa;
margin-bottom: 30px;
}
.panel {
background: #181b24;
border: 1px solid #292e3b;
border-radius: 12px;
padding: 20px;
margin-bottom: 20px;
}
.controls {
display: grid;
grid-template-columns: repeat(auto-fit, minmax(200px, 1fr));
gap: 15px;
}
label {
display: block;
color: #aab1c2;
font-size: 14px;
margin-bottom: 7px;
}
input {
width: 100%;
padding: 10px 12px;
border-radius: 7px;
border: 1px solid #343a48;
background: #10131a;
color: white;
font-size: 15px;
}
button {
margin-top: 20px;
padding: 12px 22px;
border: 0;
border-radius: 8px;
background: #4f7cff;
color: white;
font-size: 15px;
font-weight: 600;
cursor: pointer;
}
button:hover {
background: #628bff;
}
button:disabled {
opacity: 0.5;
cursor: wait;
}
table {
width: 100%;
border-collapse: collapse;
}
th,
td {
padding: 13px 10px;
text-align: right;
border-bottom: 1px solid #292e3b;
}
th:first-child,
td:first-child {
text-align: left;
}
th {
color: #8f98aa;
font-weight: 500;
}
td {
font-variant-numeric: tabular-nums;
}
.winner {
color: #4dff9a;
font-weight: 700;
}
.loser {
color: #ff7373;
}
.gain {
font-size: 28px;
font-weight: 700;
color: #4dff9a;
}
.grid {
display: grid;
grid-template-columns: repeat(auto-fit, minmax(220px, 1fr));
gap: 15px;
}
.stat {
background: #11141b;
border: 1px solid #292e3b;
border-radius: 10px;
padding: 18px;
}
.stat-title {
color: #858da0;
font-size: 13px;
margin-bottom: 8px;
}
.stat-value {
font-size: 24px;
font-weight: 700;
}
.info {
color: #9da5b7;
line-height: 1.6;
font-size: 14px;
}
.bar-container {
height: 25px;
background: #10131a;
border-radius: 6px;
overflow: hidden;
margin-top: 10px;
}
.bar {
height: 100%;
transition: width 0.5s ease;
}
.bar-sqrt {
background: #ff6868;
}
.bar-squared {
background: #4dff9a;
}
code {
background: #10131a;
padding: 2px 5px;
border-radius: 4px;
color: #7fa3ff;
}
</style>
</head>
<body>
<div class="container">
<h1>LOD Benchmark</h1>
<div class="subtitle">
Comparing <code>distanceTo()</code> vs
<code>distanceToSquared()</code>
</div>
<div class="panel">
<div class="controls">
<div>
<label for="objects">
Number of LOD objects
</label>
<input
id="objects"
type="number"
value="10000"
min="1"
>
</div>
<div>
<label for="iterations">
Iterations
</label>
<input
id="iterations"
type="number"
value="100"
min="1"
>
</div>
<div>
<label for="warmup">
Warm-up iterations
</label>
<input
id="warmup"
type="number"
value="10"
min="0"
>
</div>
</div>
<button id="run">
Run Benchmark
</button>
<div id="status" style="margin-top: 15px; color: #9299aa;">
Ready.
</div>
</div>
<div class="panel">
<h2>Results</h2>
<table>
<thead>
<tr>
<th>Test</th>
<th>Total Time</th>
<th>Time / Iteration</th>
<th>Operations / Second</th>
</tr>
</thead>
<tbody>
<tr>
<td>
distanceTo()
</td>
<td id="sqrtTotal">
-
</td>
<td id="sqrtAverage">
-
</td>
<td id="sqrtOps">
-
</td>
</tr>
<tr>
<td>
distanceToSquared()
</td>
<td id="squaredTotal">
-
</td>
<td id="squaredAverage">
-
</td>
<td id="squaredOps">
-
</td>
</tr>
</tbody>
</table>
</div>
<div class="panel">
<div class="grid">
<div class="stat">
<div class="stat-title">
Performance Gain
</div>
<div
class="gain"
id="gain"
>
-
</div>
</div>
<div class="stat">
<div class="stat-title">
Time Saved
</div>
<div
class="stat-value"
id="saved"
>
-
</div>
</div>
<div class="stat">
<div class="stat-title">
Logic Verification
</div>
<div
class="stat-value"
id="checksum"
>
-
</div>
</div>
</div>
</div>
<div class="panel">
<h2>Performance Comparison</h2>
<p class="info">
The shorter the bar, the faster the calculation.
</p>
<div>
<div class="info">
distanceTo()
</div>
<div class="bar-container">
<div
id="barSqrt"
class="bar bar-sqrt"
style="width: 100%"
></div>
</div>
</div>
<br>
<div>
<div class="info">
distanceToSquared()
</div>
<div class="bar-container">
<div
id="barSquared"
class="bar bar-squared"
style="width: 100%"
></div>
</div>
</div>
</div>
<div class="panel">
<h2>What Does This Benchmark Measure?</h2>
<p class="info">
For every object, we calculate its distance from the camera
and then perform the same LOD selection logic.
</p>
<p class="info">
Classic approach:
</p>
<pre><code>const distance = Math.sqrt(
dx * dx +
dy * dy +
dz * dz
);</code></pre>
<p class="info">
Optimized approach:
</p>
<pre><code>const distanceSq =
dx * dx +
dy * dy +
dz * dz;</code></pre>
<p class="info">
Both values preserve exactly the same ordering.
Therefore, we can compare the squared distance directly
against squared LOD thresholds.
</p>
</div>
</div>
<script>
"use strict";
/*
* Deterministic pseudo-random number generator.
*
* Both benchmarks use exactly the same dataset,
* ensuring a fair comparison.
*/
function createRandom(seed) {
return function () {
seed |= 0;
seed = seed + 0x6D2B79F5 | 0;
let t = Math.imul(
seed ^ seed >>> 15,
1 | seed
);
t = t + Math.imul(
t ^ t >>> 7,
61 | t
) ^ t;
return (
(t ^ t >>> 14) >>> 0
) / 4294967296;
};
}
/*
* Generate object positions.
*/
function createPositions(count) {
const random = createRandom(123456);
const positions = new Float64Array(
count * 3
);
for (let i = 0; i < positions.length; i++) {
positions[i] =
(random() - 0.5) * 1000;
}
return positions;
}
/*
* Benchmark using the actual distance.
*
* This is conceptually equivalent to:
*
* position.distanceTo(cameraPosition)
*
* and therefore requires a square root.
*/
function benchmarkDistance(
positions,
iterations
) {
let checksum = 0;
const count =
positions.length / 3;
const cameraX = 12.3;
const cameraY = -27.8;
const cameraZ = 8.6;
/*
* LOD thresholds.
*/
const lod0 = 20;
const lod1 = 50;
const start =
performance.now();
for (
let iteration = 0;
iteration < iterations;
iteration++
) {
for (
let i = 0;
i < count;
i++
) {
const index = i * 3;
const dx =
positions[index] - cameraX;
const dy =
positions[index + 1] - cameraY;
const dz =
positions[index + 2] - cameraZ;
/*
* The square root is intentionally used.
*/
const distance = Math.sqrt(
dx * dx +
dy * dy +
dz * dz
);
/*
* Same LOD selection logic
* as the squared-distance version.
*/
if (distance < lod0) {
checksum += 1;
} else if (distance < lod1) {
checksum += 2;
} else {
checksum += 3;
}
}
}
const elapsed =
performance.now() - start;
return {
elapsed,
checksum
};
}
/*
* Benchmark using squared distance.
*/
function benchmarkDistanceSquared(
positions,
iterations
) {
let checksum = 0;
const count =
positions.length / 3;
const cameraX = 12.3;
const cameraY = -27.8;
const cameraZ = 8.6;
/*
* IMPORTANT:
*
* The thresholds are squared as well.
*/
const lod0Sq = 20 * 20;
const lod1Sq = 50 * 50;
const start =
performance.now();
for (
let iteration = 0;
iteration < iterations;
iteration++
) {
for (
let i = 0;
i < count;
i++
) {
const index = i * 3;
const dx =
positions[index] - cameraX;
const dy =
positions[index + 1] - cameraY;
const dz =
positions[index + 2] - cameraZ;
/*
* No Math.sqrt().
*/
const distanceSq =
dx * dx +
dy * dy +
dz * dz;
/*
* Exactly the same logical result.
*/
if (distanceSq < lod0Sq) {
checksum += 1;
} else if (distanceSq < lod1Sq) {
checksum += 2;
} else {
checksum += 3;
}
}
}
const elapsed =
performance.now() - start;
return {
elapsed,
checksum
};
}
/*
* Format milliseconds.
*/
function formatMs(value) {
return value.toFixed(3) + " ms";
}
/*
* Format large numbers.
*/
function formatNumber(value) {
return new Intl.NumberFormat(
"en-US"
).format(
Math.round(value)
);
}
/*
* Run benchmark.
*/
document
.getElementById("run")
.addEventListener(
"click",
async function () {
const button =
document.getElementById("run");
const objects =
Math.max(
1,
Number(
document.getElementById(
"objects"
).value
)
);
const iterations =
Math.max(
1,
Number(
document.getElementById(
"iterations"
).value
)
);
const warmup =
Math.max(
0,
Number(
document.getElementById(
"warmup"
).value
)
);
button.disabled = true;
document
.getElementById("status")
.textContent =
"Generating test data...";
/*
* Same data for both tests.
*/
const positions =
createPositions(objects);
/*
* JavaScript engine warm-up.
*
* This gives JIT engines such as V8
* an opportunity to optimize the code.
*/
document
.getElementById("status")
.textContent =
"Warming up the JavaScript engine...";
for (
let i = 0;
i < warmup;
i++
) {
benchmarkDistance(
positions,
1
);
benchmarkDistanceSquared(
positions,
1
);
}
/*
* Give the browser a moment before starting.
*/
await new Promise(
resolve =>
setTimeout(
resolve,
50
)
);
document
.getElementById("status")
.textContent =
"Benchmarking distanceTo()...";
/*
* Run several passes and keep the best result.
*
* This reduces the impact of occasional
* browser scheduling interruptions.
*/
const passes = 5;
let sqrtResult = null;
for (
let i = 0;
i < passes;
i++
) {
const result =
benchmarkDistance(
positions,
iterations
);
if (
sqrtResult === null ||
result.elapsed <
sqrtResult.elapsed
) {
sqrtResult = result;
}
}
await new Promise(
resolve =>
setTimeout(
resolve,
20
)
);
document
.getElementById("status")
.textContent =
"Benchmarking distanceToSquared()...";
let squaredResult = null;
for (
let i = 0;
i < passes;
i++
) {
const result =
benchmarkDistanceSquared(
positions,
iterations
);
if (
squaredResult === null ||
result.elapsed <
squaredResult.elapsed
) {
squaredResult = result;
}
}
/*
* Critical verification:
*
* Both methods must produce exactly
* the same LOD classification.
*/
const sameResult =
sqrtResult.checksum ===
squaredResult.checksum;
/*
* Calculate statistics.
*/
const sqrtAverage =
sqrtResult.elapsed /
iterations;
const squaredAverage =
squaredResult.elapsed /
iterations;
const totalOperations =
objects * iterations;
const sqrtOps =
totalOperations /
(sqrtResult.elapsed / 1000);
const squaredOps =
totalOperations /
(squaredResult.elapsed / 1000);
const gain =
(
1 -
squaredResult.elapsed /
sqrtResult.elapsed
) * 100;
const saved =
sqrtResult.elapsed -
squaredResult.elapsed;
/*
* Display results.
*/
document
.getElementById("sqrtTotal")
.textContent =
formatMs(
sqrtResult.elapsed
);
document
.getElementById("sqrtAverage")
.textContent =
formatMs(
sqrtAverage
);
document
.getElementById("sqrtOps")
.textContent =
formatNumber(
sqrtOps
);
document
.getElementById("squaredTotal")
.textContent =
formatMs(
squaredResult.elapsed
);
document
.getElementById("squaredAverage")
.textContent =
formatMs(
squaredAverage
);
document
.getElementById("squaredOps")
.textContent =
formatNumber(
squaredOps
);
document
.getElementById("gain")
.textContent =
gain.toFixed(2) + " %";
document
.getElementById("saved")
.textContent =
formatMs(saved);
document
.getElementById("checksum")
.textContent =
sameResult
? "âś“ Identical"
: "âś— ERROR";
/*
* Update performance bars.
*/
const maxTime =
Math.max(
sqrtResult.elapsed,
squaredResult.elapsed
);
document
.getElementById("barSqrt")
.style.width =
(
sqrtResult.elapsed /
maxTime *
100
) + "%";
document
.getElementById("barSquared")
.style.width =
(
squaredResult.elapsed /
maxTime *
100
) + "%";
/*
* Highlight the winner.
*/
document
.getElementById("squaredTotal")
.classList.add(
"winner"
);
document
.getElementById("sqrtTotal")
.classList.add(
"loser"
);
document
.getElementById("status")
.textContent =
"Benchmark complete — " +
objects.toLocaleString("en-US") +
" objects Ă— " +
iterations.toLocaleString("en-US") +
" iterations.";
button.disabled = false;
}
);
</script>
</body>
</html>