Приветствую.
Так получилось, что некоторое время назад я принимал участие в проекте, разрабатывал браузерную игру с принципиально новым подходом в хранении данных - предполагалось создать некую вариацию на тему .krieger, игру, которая использовала бы экстремально мало памяти для хранения ресурсов, сохранив при этом высокополигональность моделей, пусть и жертвуя при этом производительностью. Ввиду комплекса причин - проект закрылся, не выпустив даже MVP - но у нас остался серьезный пласт наработок, которыми я, с дозволения остальных участников команды поделюсь тут. Само собой, с авторскими комментариями и рассмотрением идеи. Подробности под катом.
Общие положения
В основу графического движка был положен webGL - по сути дела чистый, без каких либо фреймворков и библиотек. Даже классы работы с матрицами мы писали самостоятельно. С одной стороны это было обусловлено дополнительной "челленджностью" задачи, с другой - мы хотели в точности понимать, что происходит у нас в коде, и при необходимости - иметь возможность изменить стандартное поведение тех или иных методов, без необходимости вмешиваться в чужой код.
Основная идея, которую мы преследовали - нам хотелось уйти от традиционного хранения массива полигонов и нормалей, перейти к чему то более абстрактному, и в то же время - позволяющему реализовать практически любую фигуру игрового мира.
Полигоны в пространстве
Утверждение: Любую фигуру можно представить в некотором конечном приближении как совокупность полигонов
Казалось бы, очевидная вещь. Все мы делали это, занимаясь моделированием - в явном или неявном виде. В явном виде получались угловатые параллелепипеды или пирамидки, в неявном виде - подобные принципы используются при натягивании Mesh`ей. Однако - как бы то ни было, с помощью традиционных треугольных полигонов неудобно хранить изогнутые поверхности - получается либо огромное число полигонов, либо слишком крупная сетка и вместо окружности мы получаем двадцатиугольник.
Однако, пробовал ли кто-либо рассматривать полигон как минимальную совокупность граней, но не на плоскости, в привычном нам понимании, а, например, на шаре? Насколько известно из открытых источников, таких проектов не было. Хотя казалось бы - работать должно точно так же, с той лишь разницей, что нужно условиться, какую именно часть сферы - внутреннюю или внешнюю относительно треугольника, проецируемого на его поверхность, считать "сферическим полигоном".
Тем не менее, сфера охватывает далеко не все случаи, которые могут понадобиться - по крайней мере, если не дробить ее слишком мелко, иначе мы снова скатываемся к проблеме большого числа полигонов. Кроме того, было бы неплохо задавать некоторые параметры для фигуры, в частности, если рассматривать случай сферы - ее радиус, угол поворота и координаты смещения относительно начала координат. И хотя для сферы угол поворота не играет большой роли, он пригодится для других фигур, ведь мы обобщили утверждения из предыдущих пары абзацев на любую поверхность второго порядка
Утверждение: Любую фигуру можно представить в некотором конечном приближении как совокупность ограниченных частей поверхностей второго порядка.
Уже чуть менее (казалось бы) очевидное утверждение, однако - стоит вспомнить, что полигон в традиционном смысле (т.е. треугольник в пространстве) есть тоже часть плоскости, которая есть частный случай поверхности второго порядка, поэтому все, что мы сейчас сделали - обобщили предыдущее утверждение. Однако при необходимости получить нечто не треугольное - у нас появляется новые возможности, и для отрисовки, например, сферы, достаточно задать просто сферу, а для отрисовки некоторого элемента, содержащего часть сферы - например, щита (плоски срез сферы) или наплечника (четверть сферы) - требуется задать еще и секущие плоскости.
Таким образом, мы пришли к мысли, что для описания любой фигуры в пространстве нужна просто совокупность поверхностей второго порядка и некоторые ограничивающие плоскости. Для трехмерного пространства для однозначного определения отсечения требуется 6 плоскостей, однако - можно использовать основные плоскости проецирования, смещая фигуру в нужное место уже после обрезки.
Отрисовка
Однако остается вопрос - как преобразовать множество поверхностей в полигоны? Тут все оказывается еще более тривиально - достаточно пустить множество лучей из камеры. В точках пересечения луча и поверхности можно ставить точку. А уже затем из данных точек формировать полигоны.
Что дает данный подход? Как минимум, можно динамически менять "полигональность" окружающего мира - чем большая плотность таких лучей, тем больше будет точек пересечения луча и поверхности, и тем ближе полученная сетка будет прилегать к самой поверхности. Кроме того, если задать лучам некоторое расхождение, например, лучи будут идти не параллельно, а расходиться некоторым довольно плотным пучком - объекты, удаленные от игрока, будут менее детальными, чем приближенные к камере, более того - чем ближе объект, тем более детальным он будет. Кроме того, плотность пуска лучей не обязательно должна быть равномерная - если плотность будет чуть ниже на краях, для бокового зрения графика будет низкополигональная, а для фронтального - напротив, высокополигональная. Само собой, это больше актуально для VR, но тем не менее - концепт получается интересный.
Более того, мы предполагали сделать на этой же основе не только отрисовку, но и физику - с честным просчетом коллизий как пересечением полигонов объектов, их составляющей. Полигонов уже в традиционном смысле слова, хотя ничто (кроме aлгоритмической сложности) не мешало отслеживать и пересечение поверхностей.
Непосредственно, код
Стоит понимать, что проект не был дописан, а существенная часть концепций так и осталась концепциями, проверенными на бумаге. Тем не менее, выкладываю все наши наработки - и прокомментирую их по мере возможности. Если кто-либо захочет вести работу в данном направлении, или же вообще - сделает вышеописанный принцип основополагающим для своего проекта - значит, мы не зря писали эту статью %)
Для реализации описанного алгоритма нам потребуются классы с описанием математических операций над матрицами (в частности, сложение/умножением, дискриминант и т.д), класс, описывающий точку, линию, полигон и поверхность. Остальное, из того, что требуется для разработки игры, либо не было реализовано и оттестировано, либо - не получило согласования на публикацию.
Точка - самая базовая сущность, все, что она делает - хранит и получает/устанавливает собственные координаты, а также - измеряет расстояние до товарки.
class Point{
x=0;
y=0;
z=0;
constructor(x,y,z) {
this.x = x?x:0;
this.y = y?y:0;
this.z = z?z:0;
}
get x(){
return this.x;
}
set x(x){
this.x = x;
}
get y(){
return this.y;
}
set y(y){
this.y = y;
}
get z(){
return this.z;
}
set z(z){
this.z = z;
}
toString(){
return `{"x": ${this.x}, "y": ${this.y}, "z": ${this.z}}`;
//for debug
}
/**
* @param {object} point1 - coordinates of first point
* @param {object} point2 - coordinates of second point
* @returns {number} - distance between points
*/
static getDistance(point1, point2){
return Math.sqrt(Math.pow(point2.x - point1.x, 2) +Math.pow(point2.y - point1.y, 2)+
Math.pow(point2.z - point1.z, 2) )
}
}
//console.log(new Point(2,3,4).toString()); //debug todo remove
export {Point}Однако точка - слишком мелкая единица. Введем код для полигона - пока что как как просто координаты трех точек в пространстве, и для нескольких методов работы с ним.
/**
* @returns {object} - coefficients for equation of plane,
* that contains current polygon
*/
getPlaneEquation(){
let a1 = this.point2.x - this.point1.x;
let b1 = this.point2.y - this.point1.y;
let c1 = this.point2.z - this.point1.z;
let a2 = this.point3.x - this.point1.x;
let b2 = this.point3.y - this.point1.y;
let c2 = this.point3.z - this.point1.z;
let a = b1 * c2 - b2 * c1;
let b = a2 * c1 - a1 * c2;
let c = a1 * b2 - b1 * a2;
let d = (- a * this.point1.x- b * this.point1.y - c * this.point1.z);
let plane = {
a:a,
b:b,
c:c,
d:d
}
return plane
}
/**
* @param {object} line - line in space crossing this plane
* @param {object} plane - coefficient for equation of plane that is crossed by line
* @returns {object} - coordinates of point of crossage
*/
getCrossingPointOfLIneAndPlane(line, plane){
let point1 = line.point1;
let point2 = line.point2;
let n= point2.y - point1.y;
let m = point2.x - point1.x;
let p = point2.z - point1.z;
let matrixLeft = [
[n, -1*m, 0],
[p, 0, -1*m],
[plane.a, plane.b, plane.c]
]
let matrixRight = [[n*point2.x-m*point2.y],[p*point2.x-m*point2.z],[-1*plane.d]]
let matrixLeft_1 = MatrixOperations.InverseMatrix(matrixLeft);
let solution = MatrixOperations.MultiplyMatrix(matrixLeft_1, matrixRight);
let point = {
x:solution[0][0],
y:solution[1][0],
z:solution[2][0],
}
return point;
}
/**
* @param {object} point - some point in space
* @returns {boolean} - is that point inside of current polygon
*/
isInsidePolygon(point){
let squareFull = this.getSquare(this.point1, this.point2, this.point3);
let square1 = this.getSquare(point, this.point2, this.point3);
let square2 = this.getSquare(point, this.point1, this.point3);
let square3 = this.getSquare(point, this.point2, this.point1);
const dimension = 0.0001;
/*console.log("s1 " + square1) debug todo remove
console.log("s2 " + square2)
console.log("s3 " + square3)
console.log("s " + squareFull)*/
return Math.abs(squareFull - (square1+square2+square3)) < dimension;
}
/**
* @param {object} polygon - polygon is crossing need to check
* @returns {object} - 3 points that are lying on prolongation of passed polygon borders
* and in current polygon plane
*/
getPolygonBorderLinesCrossPoints(polygon){
let plane = this.getPlaneEquation();
let crossPoint1 = this.getCrossingPointOfLIneAndPlane(new Line(polygon.point1, polygon.point2), plane);
let crossPoint2 = this.getCrossingPointOfLIneAndPlane(new Line(polygon.point1, polygon.point3), plane);
let crossPoint3 = this.getCrossingPointOfLIneAndPlane(new Line(polygon.point3, polygon.point2), plane)
let crossingPoints = {
p1: crossPoint1,
p2: crossPoint2,
p3: crossPoint3,
}
return crossingPoints;
}
/**
* @param {object} polygon - polygon is crossing need to check
* @returns {boolean} - is any of border of passed polygon crossing my plane inside my borders
*/
doesPolygonCrossMe(polygon){
let points = this.getPolygonBorderLinesCrossPoints(polygon);
return this.isInsidePolygon(points.p1) && polygon.isInsidePolygon(points.p1)
||
this.isInsidePolygon(points.p2) && polygon.isInsidePolygon(points.p2)
||
this.isInsidePolygon(points.p3) && polygon.isInsidePolygon(points.p3);
}
/**
* @param {object} polygon - polygon is crossing need to check
* @returns {boolean} - is passed polygon crossing me or am I crossing it
*/
arePolygonsCrossing(polygon){ //needs tests
return this.doesPolygonCrossMe(polygon) && polygon.doesPolygonCrossMe(this);
}
/**
* @param {object} point1 - vertex of triangle
* @param {object} point2 - vertex of triangle
* @param {object} point3 - vertex of triangle
* @returns {float} - square of triangle
*/
getSquare(point1, point2, point3){
let a = Point.getDistance(point1, point2);
let b = Point.getDistance(point2, point3);
let c = Point.getDistance(point1, point3)
let p = (a+b+c)/2;
let square = Math.sqrt(p*(p-a)*(p-b)*(p-c));
return square;
}
Однако для работы физического движка требуется проверять пересечения полигонов - для этого была реализована функция arePolygonsCrossing, с довольно интересным алгоритмом.
В ней мы утверждаем, что два полигона пересекаются тогда и только тогда, когда либо я пересекаю другой полигон, либо другой полигон пересекает меня.
В тоже самое время мы утверждаем, что полигон пересекает мня, если продолжение хотя бы одной линии, являющейся границей полигона, пересекает плоскость, в которой лежит исходный полигон, лежит внутри каждого из полигонов. Далее - утверждается, что точка находится внутри плоского полигона, только если суммарная площадь трех треугольников, которые данная точка составляет с вершинами, равна площади непосредственно полигона.
Далее - стоит посмотреть на класс Surface. В нем нет ограничивающих плоскостей - предполагалось вынести это на вышестоящий слой абстракции, который не ходит в текущую реализацию, однако для проверки нахождения какого-либо полигона между двумя (для каждого измерения) плоскостями, задача тривиальная (хотя если мелко разбить каждую из задач - каждая из них тривиальная). В рамках данной статьи ключевая задача стояла в том, чтобы рассмотреть глобальный концепт представления графики не как запеченный массив треугольничков), а как некоторую абстракцию высокого уровня. Собственно, сама реализация представлена под спойлером - там есть как раз необходимый функционал для реализации описанной концепции - конвертация массива поверхностей и массива линий в массив полигонов, который затем передается в вебГл для отрисовки, путем обхода всех точек и преобразования трех ближайших в полигон. Безусловно, честный обход в ширину был бы чуть более корректен, однако при равномерной плотности точек в пространстве, а также отсутствие резких переходов между поверхностями, позволяют утверждать, что приближение по трем самым близким точкам, будет достаточно точно.
getPointsOfCrossedByLine(line) {
let a = this.a2 * Math.pow(line.getEquation().m, 2) +
this.b2 * Math.pow(line.getEquation().n, 2) + this.c2 * Math.pow(line.getEquation().p, 2);
let b = this.a2 * 2 * line.getEquation().m + line.getEquation.m * this.a1 +
this.b2 * 2 * line.getEquation().n + line.getEquation.n * this.b1 +
this.c2 * 2 * line.getEquation().p + line.getEquation.p * this.c1;
let c = this.a2 * line.getEquation().x1 * line.getEquation().x1 + this.a1 * line.getEquation().x1 +
this.b2 * line.getEquation().y1 * line.getEquation().y1 + this.b1 * line.getEquation().y1 +
this.c2 * line.getEquation().z1 * line.getEquation().z1 + this.c1 * line.getEquation().z1 + this.d0;
let t = this.quadraticEquation(a, b, c);
return t.map((value) => {
return new Point(line.getEquation().x1 + value * line.getEquation().m,
line.getEquation().y1 + value * line.getEquation().n,
line.getEquation().z1 + value * line.getEquation().p,
)
})
}
getPointsOfCrossedByLineArray(lineArray) {
let rezultArray = [];
for (let i of lineArray) {
let temp = this.getPointsOfCrossedByLine(i);
for (let j of temp)
rezultArray.push(j)
}
return rezultArray;
}
getSortedGraphOfPoints(lineArray) {
let pointsNotVisited = this.getPointsOfCrossedByLineArray(lineArray);
let visitedPoints = [];
visitedPoints.push(pointsNotVisited[0])
pointsNotVisited.shift();
while (pointsNotVisited.length) {
pointsNotVisited.sort((p1, p2) => {
return Point.getDistance(visitedPoints[visitedPoints.length - 1], p1) -
Point.getDistance(visitedPoints[visitedPoints.length - 1], p2);
})
visitedPoints.push(pointsNotVisited[0])
pointsNotVisited.shift();
}
}
getPolygonMeshingArray(sortedPointsArray) {
let polygonArray = [];
for (let i = 9; i < sortedPointsArray - 3; i++)
polygonArray.push(new Polygon(sortedPointsArray[i], sortedPointsArray[i + 1], sortedPointsArray[i + 2]))
return polygonArray;
}Ввиду описательности названий и подробного описания алгоритма комментарии излишни.
Заключение
В заключение хотелось бы сказать, что подход, озвученный выше, безусловно обладает рядом проблем - все мы понимаем, что реализация алгоритмов "с наскока" довольно редко получается удачной. Однако, несмотря на очевидные проблемы с производительностью, а также невозможностью сопряжения с большей частью уже готовых решений, нам хотелось бы верить, что мы хотя бы затронули тот отдел, о котором читатель даже тривиально не задумывался, а принимал как данность. Всегда плоскость полигона принималась аксиомой, с этим, на моей памяти никто и никогда не пытался спорить, по крайней мере на морей памяти. Однако - мы попробовали реализовать проект с полигонами второго порядка, и у нас почти получилось. Возможно, кто-то из вас пройдет начатый нами путь до конца.
Все исходники, все наши наработки, которыми я могу поделиться, расположены по ссылке.