Поиск всех квадратов в сетке

Question

Я загружаю сетку через Three.js, и я пытаюсь текстурировать каждый квадрат отдельно. Прямо сейчас я могу текстурировать каждую грань (три), но я не уверен, как определить, являются ли текущий и последний треугольники частью квадрового (они будут делиться двумя вершинами, но какие?)

Я выясняю, образуют ли два треугольника квадрант?

var last = null; 
for(var i in geometry.faces) 
{ 
    var face = geometry.faces[i]; 
    var normal = face.normal.clone().normalize(); 

    if(normal.y >= 0.9999) 
    { 
     face.materialIndex = 1; 

     //Determine if face & last are part of a quad 
     if(face && last == same quad) 
     { 
      face.color = last.color; 
     } 
     else 
     { 
      face.color = new THREE.Color(Math.random() * 0xFFFFFF); 
     } 

     last = face; 
    } 
} 

Answer 1

Во-первых, вам нужно понять, что проблема недопределена. В связанной треугольной сетке каждый треугольник имеет 3 соседства. Каждый из них мог бы быть четырьмя. Поэтому вы можете только догадываться о том, что такое квадроциклы. Ваш выбор проверки нормального является хорошим началом, но не работает, например, если сетка была плоскостью.

Первый шаг - найти всех соседей для каждого треугольника. Каждый треугольник имеет ровно 3 соседей. Это забавный двухпроходный алгоритм, который должен быть линейным во времени и в памяти. Каждый треугольник должен иметь нечто вроде соседей [3] - это индексы для других треугольников.

Затем вы можете вычислить эвристику «четности» для каждого из них. Они должны быть грубо копланарными и прямоугольными. Я бы забил по нормалям и внутренним углам с четырех сторон. После этого вы можете отсортировать все треугольники по этому номеру. Сначала удалите лучшие предположения, объедините их в квадрат и продолжайте, пока не закончите.

Это должно работать довольно нормально в большинстве случаев, но будут случаи, когда это ломается. В зависимости от того, почему вам нужны квадроциклы, вы можете попытаться исправить свою эвристическую функцию, соответствующую вашему делу. Но важно помнить, что нет правильного решения. Проблема определена.