three.js/test/benchmark/computeBoundingSphere.js at 22815117cd09abcb8caf1ccd3872990f4b0f9be3 · mrdoob/three.js · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/**
 * Benchmark: BufferGeometry.computeBoundingSphere() fast path vs the previous
 * implementation (per-vertex Vector3.fromBufferAttribute access).
 *
 * Run with: node test/benchmark/computeBoundingSphere.js
 */

import { BufferGeometry } from '../../src/core/BufferGeometry.js';
import { BufferAttribute } from '../../src/core/BufferAttribute.js';
import { Box3 } from '../../src/math/Box3.js';
import { Sphere } from '../../src/math/Sphere.js';
import { Vector3 } from '../../src/math/Vector3.js';

const _box = new Box3();
const _vector = new Vector3();

// faithful copy of the previous implementation (no morph targets)

function computeBoundingSphereOld( geometry ) {

	const sphere = new Sphere();
	const position = geometry.attributes.position;
	const center = sphere.center;

	// old Box3.setFromBufferAttribute path

	_box.makeEmpty();

	for ( let i = 0, il = position.count; i < il; i ++ ) {

		_box.expandByPoint( _vector.fromBufferAttribute( position, i ) );

	}

	_box.getCenter( center );

	let maxRadiusSq = 0;

	for ( let i = 0, il = position.count; i < il; i ++ ) {

		_vector.fromBufferAttribute( position, i );

		maxRadiusSq = Math.max( maxRadiusSq, center.distanceToSquared( _vector ) );

	}

	sphere.radius = Math.sqrt( maxRadiusSq );

	return sphere;

}

function makeGeometry( vertexCount ) {

	const array = new Float32Array( vertexCount * 3 );

	for ( let i = 0; i < array.length; i ++ ) {

		array[ i ] = Math.random() * 200 - 100;

	}

	const geometry = new BufferGeometry();
	geometry.setAttribute( 'position', new BufferAttribute( array, 3 ) );

	return geometry;

}

function bench( fn, iterations ) {

	const times = [];

	for ( let i = 0; i < iterations; i ++ ) {

		const start = performance.now();
		fn();
		times.push( performance.now() - start );

	}

	times.sort( ( a, b ) => a - b );

	return times[ Math.floor( times.length / 2 ) ]; // median

}

const sizes = [ 10_000, 100_000, 1_000_000, 5_000_000 ];
const iterations = 20;

console.log( `median of ${ iterations } runs per case\n` );
console.log( 'vertices'.padStart( 10 ), 'old (ms)'.padStart( 12 ), 'new (ms)'.padStart( 12 ), 'speedup'.padStart( 10 ) );

for ( const size of sizes ) {

	const geometry = makeGeometry( size );

	// correctness check

	const oldSphere = computeBoundingSphereOld( geometry );
	geometry.computeBoundingSphere();
	const newSphere = geometry.boundingSphere;

	if ( Math.abs( oldSphere.radius - newSphere.radius ) > 1e-10 ||
		oldSphere.center.distanceTo( newSphere.center ) > 1e-10 ) {

		console.error( `MISMATCH at ${ size } vertices: old`, oldSphere, 'new', newSphere );
		process.exit( 1 );

	}

	// warmup

	for ( let i = 0; i < 3; i ++ ) {

		computeBoundingSphereOld( geometry );
		geometry.computeBoundingSphere();

	}

	const oldMs = bench( () => computeBoundingSphereOld( geometry ), iterations );
	const newMs = bench( () => geometry.computeBoundingSphere(), iterations );

	console.log(
		String( size ).padStart( 10 ),
		oldMs.toFixed( 3 ).padStart( 12 ),
		newMs.toFixed( 3 ).padStart( 12 ),
		( oldMs / newMs ).toFixed( 2 ).padStart( 9 ) + 'x'
	);

}