Нахождение центра массы на 2D битовом массиве
Учитывая треугольник, определенный его тремя вершинами ABC, вектор, перпендикулярный («нормальный») этому треугольнику, легко получить с помощью перекрестного произведения двух векторов, например ABxAC. Но также ABxBC.
Дело в том, что перекрестное произведение НЕ коммутативно. Итак, ABxAC - это не то же самое, что ACxAB. Именно это ABxAC = - ACxAB, это тот же вектор, но в противоположном направлении .
Нормальное направление движения по передней поверхности должно быть рассчитано в соответствии с порядком намотки или треугольником. Тот же порядок, в котором вы устанавливаете вершины треугольника в буфере, - это порядок выбора векторов для перекрестного произведения.
Вы должны знать, как GL делает порядок намотки в зависимости от типа треугольного примитива
ПРИМЕР
Допустим, вы используете glDrawArrays (GL_TRIANGLES, ... ) и ваш буфер вершин выглядит как v1, v2, v3, v1, v3, v4, v1, v4, v5 и т. д. (vi = vix, viy, viz), где все порядки намотки расположены против часовой стрелки. Тогда:
Vector AB = v2 - v1
Vector AC = v3 - v1
Vector perp = cross(AB, AC)
Vector norm = normalize(perp) //divide each component by lenght of perp
Теперь у вас есть нормаль к граням, нормали в точках немного хитры.
Простейшим способом является вычисление среднего значения нормалей к треугольникам, разделяющим вершину. Когда каждый фрагмент треугольника заштрихован, нормаль в этой точке может быть интерполирована из нормалей в вершинах. В результате вы получаете «мягкий» переход от треугольника к треугольнику.
Если вы хотите сохранить края (жесткий переход), то вы должны предоставить разные нормали для разных треугольников. Таким образом, каждая вершина, если смотреть на шейдер, получает свою собственную нормаль. Повторите вершину для другого треугольника, затем установите другую нормаль даже для той же вершины.
3 ответа
Как насчет этого алгоритма (psuedo-код) на основе булевой матрицы как в Вашем примере:
xSum = 0
ySum = 0
points = 0
for point in matrix
if point is marked
xSum += pointX
ySum += pointY
points++
return (xSum/points, ySum/points)
Ничто также сложное, вычислите, где X больше всего присутствует, то же для Y, разделитесь на число очков, которое Вы считали, и Вы получили центр массы. Можно далее усложнить это путем предоставления определенным моментам другого веса в усреднении, но это должно быть основным направлением.
Этот вопрос получил меня думающий о расширении на этот вопрос, на который я не мог найти хороший ответ. Я отправил вопрос здесь: Нахождение кластеров массы в матрице/битовом массиве
Вы могли считать количество смежных ячеек, затем центрироваться на ячейках с самым высоким соседним количеством.
012345678 0 XX | 1 XXX | 2 XXX | 3 XXXXXXX| 4 XXX | 012345678 0 23 | 1 454 | 2 775 | 3 3686421| 4 454 |
В этом примере Вы могли использовать единственную ячейку с 8, как центральная точка.
При предложении нескольких ячеек с тем же числом соседей Вы просто выполнили бы стандартную программу подсчета снова, но на этот раз только с высокими ячейками числа.
Например, позволяет, притворяются, что ячейки, которые имели 6, 7, и 8, вместо этого все имели восемь соседей.
012345678 0 23 | 1 454 | 2 885 | 3 3888421| 4 454 | 012345678 0 -- | 1 --- | 2 XX- | 3 -XXX---| 4 --- | 012345678 0 -- | 1 --- | 2 34- | 3 -342---| 4 --- | 012345678 0 -- | 1 --- | 2 -X- | 3 --X----| 4 --- |
В случае простой связи я пошел бы с той, которая была ближе центр. В этом случае это был бы верхний из двух.
Примечание: Я принимаю Ваш не использование этого для точного моделирования физики.
В зависимости от природы Вашего actionscript интерпретатора и предварительной обработки, сделанной на формах, можно видеть улучшение скорости (по прямому подходу, на который указывает Yuval) путем начального создания второй копии битового массива/массива, зеркально отраженного по диагонали, затем использования строки или функций обработки строк для подведения итогов точек на каждой строке и столбце на единственных шагах. Это было бы O (2 млн) вместо O (nn) [посмотрите ниже], но с больше служебным.
xSum = 0
ySum = 0
points = 0
for row in matrix
ySum += rowX * countpoints(row)
points += countpoints(row)
for row in mirroredmatrix
xSum += rowX * countpoints(row)
return (xSum/points, ySum/points)
Где countpoints () считает на точках подряд. Это полагается на countpoints (который имеет O (n) время выполнения), наличие более низкого постоянного множителя, чем время выполнения наивного подхода (следовательно выше, 'm' быть временем выполнения countpoints и 'n' быть временем для интерпретатора для цикличного выполнения через строку). Природа countpoints () зависит от Вашего метода устройства хранения данных, который может вовлечь символы подсчета в строку или биты в битовом поле.