Приветствую.
Так получилось, что некоторое время назад я принимал участие в проекте, разрабатывал браузерную игру с принципиально новым подходом в хранении данных - предполагалось создать некую вариацию на тему .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 removeexport {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; }
Ввиду описательности названий и подробного описания алгоритма комментарии излишни.
Заключение
В заключение хотелось бы сказать, что подход, озвученный выше,
безусловно обладает рядом проблем - все мы понимаем, что реализация
алгоритмов "с наскока" довольно редко получается удачной. Однако,
несмотря на очевидные проблемы с производительностью, а также
невозможностью сопряжения с большей частью уже готовых решений, нам
хотелось бы верить, что мы хотя бы затронули тот отдел, о котором
читатель даже тривиально не задумывался, а принимал как данность.
Всегда плоскость полигона принималась аксиомой, с этим, на моей
памяти никто и никогда не пытался спорить, по крайней мере на морей
памяти. Однако - мы попробовали реализовать проект с полигонами
второго порядка, и у нас почти получилось. Возможно, кто-то из вас
пройдет начатый нами путь до конца.
Все исходники, все наши наработки, которыми я могу поделиться,
расположены по ссылке.
