Недавно получен запрос на 10 Вт данных для обмена данными в социальных сетях, чтобы сделать диаграмму социальных отношений, чтобы провести макроанализ, он должен быть полностью визуализирован. В этой статье обсуждаются методы оптимизации для плавного рендеринга узлов уровня 10 000.
Примечание:
Оригинальная ссылка:Woohoo.404forest.com/2018/10/12/…
Резервная копия статьи:GitHub.com/jin5354/404…
Код этой статьи был инкапсулирован как компонентD3-Force-Graph,Адрес складаGitHub.com/jin5354/ 3-….
Эффект рендеринга:
Рендеринг крупномасштабного графа социальных отношений в реальном времени на стороне браузера и обеспечение бесперебойной работы требуют различных оптимизаций.Давайте поделимся некоторым практическим опытом с точки зрения рендеринга графики, ввода-вывода данных, расчета данных и деталей.
1. Рендеринг графики
Формат необработанных данных для обмена в социальных сетях выглядит следующим образом:
{
"source": "sourceNodeName",
"target": "targetNodeName"
}10 Вт фрагментов исходных данных после дедупликации, удаления неверных точек и предварительной обработки могут получить около 5 Вт узлов и 4 Вт множественных соединений. Эти данные хранятся в объекте, формат данных следующий, занимая около 10 МБ памяти.
{
"nodes": ["A", "B", "C", ...],
"links": [{
"source": "A",
"target": "B"
}, {
"source": "C",
"target": "D"
}, ...]
}1.1 Выбор: d3-force Force-Directed графическая компоновка + рендеринг webgl
Как распределить столько точек на полотне, причем плотно и плотно, лучше всего крупные структуры расположить в центре, а розничных инвесторов на периферии? Алгоритм направленного усилия — это алгоритм компоновки графика, который позволяет четко и красиво представить отношения точка-линия. Этот алгоритм основан на физике элементарных частиц, имитирует каждый узел как атом и генерирует новую позицию, генерируя скорость и ускорение узла за счет отталкивания между атомами (и привязки линии) в каждом кадре. После многих итераций наконец получается стабильный макет с низким энергопотреблением. Дополнительные сведения об алгоритмах принудительного управления см.d3-force.
С положением каждого узла, как я могу рисовать точки и линии? Я написал один в SVGdemo, отрисовка 5000 точек с помощью SVG на моей машине снизилась до 10 кадров в секунду. Видно, что невозможно отрисовать узлы уровня 10 000, не полагаясь на аппаратное ускорение. Автор неплохо знаком с three.js, поэтому для рендеринга я выбрал webgl (three.js).
Рендеринг примера круга 5k svg, очень застрял1.2 Система частиц + LineSegments + BufferGeometry
Чаще всего используется при создании объектов в Three.js.THREE.GeometryПостроить геометрию.GeometryЭто структура данных в Three.js, которая содержит такую информацию, как положение вершины, цвет и т. д. При сохранении информации она используетTHREE.Vector3, THREE.Colorи другие структуры данных, чтение и запись очень интуитивно понятны и удобны, но производительность средняя. В самом общем смысле для каждого узла нам нужно использоватьTHREE.CircleGeometryПостройте круг, для каждой линии нам нужно использоватьTHREE.LineПостроить линию.
// 最初版本
// 每个节点绘制一个圆
this.paintData.nodes.forEach((node) => {
node.geometry = new THREE.CircleGeometry(5, 12)
node.material = new THREE.MeshBasicMaterial({color: 0xAAAAAA})
node.circle = new THREE.Mesh(node.geometry, node.material)
this.scene.add(node.circle)
})
// 每条线绘制一个线段
this.paintData.links.forEach((link) => {
link.lineMaterial = new THREE.LineBasicMaterial({color: 0xAAAAAA})
link.lineGeometry = new THREE.Geometry()
link.line = new THREE.Line(link.lineGeometry, link.lineMaterial)
link.line.frustumCulled = false
this.scene.add(link.line)
})Тем не менее, фактическое измерение обнаружило, что система также будет очень трудно представлять при нанесении на 5К узлами. Если вы хотите три.js, чтобы нарисовать объекты круга 5W, объекты с несколькими линиями 4W, и каждый объект круга имеет 13 вершин, в общей сложности более 70 W вершины должны быть нарисованы. Если вы хотите оптимизировать, вы должны начать уменьшить количество вершин и уменьшить количество объектов.
Для большого количества объектов с небольшим разницей, используйтеСистема частицхороший выбор. В системе частиц каждому узлу нужна только одна вершина, и к ней привязана текстура кругового узора. А после использования системы частиц десятки тысяч круглых объектов можно свести к одному объекту системы частиц, что значительно снижает сложность.
Система частиц рендерит 100 тысяч узлов без стрессаДля большого количества прямых сегментов (без поворотов) можно использоватьTHREE.LineSegments.THREE.LineSegmentsиспользоватьgl.LINES, вы можете передать набор вершин, каждая пара которых образует отрезок. Таким образом, десятки тысяч линейных объектов могут быть сведены к одному объекту LineSegments, что значительно снижает сложность.
Недостатком систем частиц и LineSegments является то, что если вы хотите настроить позжеиндивидуальныйЦвет или размер частиц должен быть написан от руки в шейдерах GLSL.
D3-Force-GraphПоддерживает пользовательские стили узлов и линий, такие как настройкаразмер,цвети т. д., используйте Язык GLSL упрощает написание шейдеров. Из-за ограниченного объема эта статья не знакомит с GLSL.Посмотреть исходный кодК пониманию. Вы также можете взглянуть на серию демонстраций, оставленных автором при изучении WebGL:WebGL tutorial.
BufferGeometryС участиемGeometryАналогичная структура данных, используемая для описания геометрии, которая использует двоичные массивы для хранения информации, такой как позиции вершин, цвета и т. д. Javascript должен использовать бинарные данные при обмене данными с видеокартой.Если это традиционный текстовый формат, его необходимо конвертировать, что занимает очень много времени.BufferGeometryДвоичные данные можно передавать на видеокарту без изменений, что значительно повышает производительность скриптов. В сценарии этой статьи массив позиций и массив цветов из 10 000 узлов уровня имеют размер в несколько M. ИспользуйтеBufferGeometryзаменятьGeometryЭто необходимо.
Использование двоичных массивов снижает читабельность кода, но значительно повышает производительность.
// 这是绘制节点的部分代码
// 预准备节点，使用BufferGeometry，位置先统一定到 (-9999, -9999, 0)
point.geometry = new THREE.BufferGeometry()
// 使用二进制数组，每个节点需要 x,y,z 三个坐标确定位置，所以数组长度分配为 节点数 * 3
point.positions = new Float32Array(paintData.nodes.length * 3)
// 使用粒子系统，不再用几何体画圆，而是使用一张带透明背景的圆形图案 png
// 后期为了更高的灵活度，会将各种物体的 material 都替换为 ShaderMaterial
point.material = new THREE.PointsMaterial({
size: 10,
map: texture,
transparent: true
})
// 填充位置的二进制数组，可读性有所下降，只能用下标+1,+2来找x,y,z了
paintData.nodes.forEach((e, i) => {
point.positions[i * 3] = -9999
point.positions[i * 3 + 1] = -9999
point.positions[i * 3 + 2] = 0
})
...
// 绑定位置二进制数组
point.geometry.addAttribute('position', new THREE.BufferAttribute(point.positions, 3))
point.geometry.computeBoundingSphere()
let points = new THREE.Points(point.geometry, point.material)
// 节点加入场景
scene.add(points)
// 绘制线段
line.geometry = new THREE.BufferGeometry()
line.positions = new Float32Array(paintData.links.length * 6) //线段有起点终点，共6个位置
line.material = new THREE.LineBasicMaterial({
vertexColors: THREE.VertexColors
})
// 所有点初始位置 (-9999, -9999, -0.1)
paintData.links.forEach((e, i) => {
line.positions[i * 6] = -9999
line.positions[i * 6 + 1] = -9999
line.positions[i * 6 + 2] = -0.1
line.positions[i * 6 + 3] = -9999
line.positions[i * 6 + 4] = -9999
line.positions[i * 6 + 5] = -0.1
})
line.geometry.addAttribute('position', new THREE.BufferAttribute(line.positions, 3))
line.geometry.computeBoundingSphere()
line.lines = new THREE.LineSegments(line.geometry, line.material)
scene.add(line.lines)Также есть небольшая хитрость: поскольку используются бинарные массивы, то лучше использовать бинарные массивы с самого начала логики, как, например, в приведенном выше коде.Float32Array. Хотя вы всегда можете использовать обычные массивы в своем бизнесе (обычные массивы имеют больше API, чем бинарные массивы, что более удобно), не звоните, пока не захотите передать данные в three.jsTHREE.Float32BufferAttributeПреобразуйте его, но это привело к серьезной потере производительности для объема данных уровня 10000.
После такой оптимизации время, необходимое для отрисовки кадра, сократилось до менее чем 50 мс, а отрисовка в натуральную величину может гарантировать частоту кадров 15~30 кадров в секунду, что в основном плавно. После завершения макета при использовании управляющего плагина Three.js для перетаскивания, панорамирования, масштабирования и других операций просмотра стабильность составляет 60 кадров в секунду.
1.3 Используйте веб-воркеры, чтобы не блокировать основной поток
Учитывая количество данных в этой статье,d3-forceИтерация каждого кадра занимает около 2 секунд. Итак, мы можем увидеть этот эффект:
Экран перемещается каждые 2 секунды, что, кажется, зависает, основной поток блокируется во время процесса вычислений, пользовательский интерфейс не отвечает, и опыт очень плохой. Мы можем переместить часть d3-force в worker, чтобы обеспечить плавность основного потока. Более подробную демонстрацию можно найти в разделе Ссылки.Force-Directed Web Worker.
// main
this.worker = new Worker('worker.js')
// 将节点与线的信息传入 worker
worker.postMessage({
nodes: nodes,
links: links
})
// d3-force 每迭代完一次，将位置信息传送回来，执行回调
worker.onmessage = function(event) {
switch (event.data.type) {
case 'tick': return ticked(event.data);
case 'end': return ended(event.data);
}
}// worker.js
// 调用 d3-force 进行布局迭代
importScripts("https://d3js.org/d3-collection.v1.min.js");
importScripts("https://d3js.org/d3-dispatch.v1.min.js");
importScripts("https://d3js.org/d3-quadtree.v1.min.js");
importScripts("https://d3js.org/d3-timer.v1.min.js");
importScripts("https://d3js.org/d3-force.v1.min.js");
onmessage = function(event) {
var nodes = event.data.nodes,
links = event.data.links;
var simulation = d3.forceSimulation(nodes)
.force("charge", d3.forceManyBody())
.force("link", d3.forceLink(links).distance(20).strength(1))
.force("x", d3.forceX())
.force("y", d3.forceY())
.stop();
for (var i = 0, n = Math.ceil(Math.log(simulation.alphaMin()) / Math.log(1 - simulation.alphaDecay())); i < n; ++i) {
postMessage({type: "tick", progress: i / n});
simulation.tick();
}
postMessage({type: "end", nodes: nodes, links: links});
}1.4 Твин-анимация
Будуd3-forceПосле того, как расчет лейаута перемещен в воркер, основной поток больше не блокируется, а ограничивается скоростью лейаута, экран по-прежнему перемещается каждые 2 с. В течение этого 2-секундного интервала основной поток простаивает, поэтому мы можем активно добавлять анимации перехода для улучшения беглости.
Например, если первый кадр рассчитан на 2000 мс, позиция x = 5, второй кадр рассчитан на 4000 мс, а позиция x = 10, мы можем начать рисовать на 4000 мс, и цель рисования: на 2000 мс x наклоны от 5 до 10 с течением времени. Затем при вызове и выполнении rAF, если текущее время 4400мс, то текущая позиция должна быть (4400 - 4000)/2000*(10 - 5)+5=6, то есть при этом выполнении отрисовывается x=6 . Поскольку время расчета d3-force на кадр относительно стабильно, а скорость расчета становится немного выше на более позднем этапе, твин-стратегию можно немного скорректировать, но общая идея остается прежней. После добавления анимации движения вы можете напрямую обновить анимацию до При частоте около 30 кадров в секунду впечатления значительно улучшаются.
2. Ввод/вывод данных
2.1 Индикатор выполнения
Из-за увеличения количества данных, многие мелкие места, на которые раньше не нужно было обращать внимание, также стали узкими местами.Например, 10w куски данных имеют размер около 10M.Вытягивание занимает определенное время интерфейс, расчет и макет, поэтому индикатор выполнения можно добавить к части без напоминания пользовательского интерфейса раньше. такие как макет,d3-forceПо умолчанию для достижения стабильного состояния требуется около 300 итераций.В этом сценарии параметры настраиваются на 50 итераций до конца, что также занимает от 1 до 2 минут. Добавление индикатора выполнения может сделать пользователей более дружелюбными.
2.2 Transferable ArrayBuffer
в волеd3-forceВ процессе миграции на рабочие заметил такое явление:
В это время не выполняется ни одна функция, и моя интуиция подсказывает мне, что эта часть должна быть потерей ввода-вывода при обмене данными между основным потоком и рабочим потоком. Проверьте это на MDNдокументация postMessageОбнаружить:postMessageТакже получает второй параметр, который может быть толькоTransferableтипа, в том числеArrayBuffer,
MessagePort and ImageBitmap, используйте этот параметр, чтобы напрямую передать управление переменной Transferable из основного потока в рабочий поток. Включить статьи GoogleРабочие ♥ ArrayBufferВведение в: использованиеArrayBufferПередавать двоичные данные между основным потоком и рабочими потоками очень просто. выключательArrayBufferСравнение производительности было сделано кем-то, позаимствовавшимExamining Web Worker PerformanceСравнительная таблица:
Таким образом, переданные данные перезаписываются и реконструируются в ArrayBuffer. Читабельность также приносится в жертву (ранее описывалась объектами, теперь она должна быть полностью тайлирована в массив, а ArrayBuffer очень хлопотно пропускает буквы и китайские иероглифы, лучше всего сопоставлять их с цифрами) в обмен на производительность. Производительность после перехода на ArrayBuffer следующая:
3. Расчет данных
3.1 Оптимизация сложности
Исходные данные всегда необходимо предварительно обрабатывать, например, подсчитывать наиболее влиятельные узлы (с наибольшим количеством общих ресурсов), отфильтровывать бесполезные узлы, не имеющие отношений совместного использования, выполнять отсечение данных и т. д. В случае массивных данных очень важно использовать соответствующий алгоритм; первая версия была написана очень небрежно, обходя множество обходов, и сложность высока, данные могут быть приняты 1w, и требуется несколько сотен мс. выходят, и данные 10 Вт напрямую застревают на шесть или семь секунд. Позже его оптимизировали, используя больше хэш-карт, меняя пространство на время, переписывая две или три версии и, наконец, сокращая время расчета до менее чем 2 с, что по-прежнему является идеальным.
3.2 Разделение нескольких веб-воркеров
Миграция вычислительного процесса в рабочие процессы позволяет избежать блокировки основного потока и обеспечить плавное взаимодействие, однако для максимального ускорения вычислений мы можем разделить его на несколько веб-воркеров, чтобы в полной мере воспользоваться преимуществами многоядерной производительности.Javascript Web Workers Test v1.4.0Это тест веб-работника, и тест показывает, что на многоядерных машинах разбиение действительно может значительно сократить время вычислений. через интерфейс браузераnavigator.hardwareConcurrencyМы можем получить количество ядер процессора, а затем разделить их, например, 8-ядерная машина может вывести 7 рабочих потоков, чтобы максимально использовать ядра. Разделение логики расчета и объединение результатов должны быть разработаны сами по себе.Эта статья только проводит исследование.Поскольку время расчета уже короткое, работа по разделению выполняться не будет.
4. Детали
4.1 Избегайте наблюдения Vue
Мы знаем, что Vue будет наблюдать за данными под данными, но когда количество данных очень велико, наблюдение также занимает очень много времени, как показано на следующем рисунке:
Задание и изменение массива позиций часто происходит при рендеринге.Если такую операцию 90мс запускать каждый кадр, то это точно будет многовато.Поэтому рекомендуется не размещать массивы и объекты с большим объемом данных под данных как можно больше, чтобы избежать потребления, вызванного наблюдением.Время.
4.2 Энергосбережение
После того, как макет закончен, непрерывный рендеринг также очень требователен к производительности, и вентилятор машины будет продолжать работать; мы можем начать рисование, когда курсор мыши находится на холсте, и завершить рисование, когда мышь находится в других областях. чтобы избежать потребления во время чистого отображения.производительность машины.
4.3 Дросселирование
Когда количество узлов велико, вытягивание и отрисовка аватаров узлов станет проблемой производительности.Вообще говоря, когда поле зрения большое, узлы маленькие и изображения не нужно загружать.Аватар в окно просмотра загружается только тогда, когда координата Z камеры сцены меньше определенного значения). Если частота работы «оценки того, какие узлы находятся в поле зрения и загрузки» слишком высока в каждом кадре, вы можете использовать технологию дросселирования, чтобы ограничить выполнение до одного раза в секунду, при этом объект аватара кэшируется. , а динамическая выгрузка и загрузка выполняются, когда поле зрения перемещается, чтобы избежать загрузки слишком большого количества аватаров, вызывающих проблемы с производительностью.
4.4 Ускорение графического процессора
Изображения аватара на сервере все квадратные, но когда мы хотим нарисовать круглое изображение, как быть с эффектом закругленного угла? Согласно обычному мышлению, мы можем нарисовать круг, чтобы заполнить изображение с помощью canvas API, и, наконец, экспортировать новое изображение (см. замечательную статью Чжан Синьсюй:Небольшой совет: SVG и Canvas соответственно достигают эффекта закругленных углов изображения.). Но поскольку у нас есть возможность манипулировать фрагментными шейдерами, мы можемИзменяйте текстуры прямо в шейдере, не только скругление углов, но и обводки и сглаживание. Шейдеры работают непосредственно на На GPU производительность хорошая. Если сглаживание моделируется в программном обеспечении, накладные расходы должны быть намного больше.
Некоторые демонстрационные изображения:
5. Ссылки
- d3-force
- Geometry - three.js docs
- BufferGeometry - three.js docs
- ArrayBuffer — начало работы с ECMAScript 6
- Points - three.js docs
- LineSegments - three.js docs
- Force-Directed Web Worker
- Рабочие ♥ ArrayBuffer | Интернет | Разработчики Google
- Examining Web Worker Performance
- Worker.postMessage() - Web APIs | MDN
- Javascript Web Workers Test v1.4.0
- navigator.hardwareConcurrency - Web APIs | MDN
- Drawing Anti-aliased Circular Points Using OpenGL/WebGL
- WebGL tutorial