Анализ поверхности

← →
Toxic (2005-03-20 15:14) [0]

Здравствуйте.
Кратко: есть поверхность, есть точка с известными X и Z координатами. Необходимо рассчитать высоту (Y-координату) точки над поверхностью.
Проще говоря, при перемещении точки она должна скользить ПО ПОВЕРХНОСТИ, а не над или под ней.
Подробнее:
Поверхность состоит из одномерного массива Vertexes
type TVertex = record
X, Y, Z : real;
end;

и одномерного массива Quads
type TQuad = record
A, B, C, D : integer;
end;

для разложения поверхности на элементы (квадраты).
Естественно, известны все координаты всех точек и какая точка какому квадрату принадлежит. Итак, уважаемые мастера, прошу поделиться опытом/знаниями/соображениями/идеями в области определения координат :)

← →
XProger © (2005-03-20 15:25) [1]

1) Делай треугольниками
2) находи треугольник на позиции X Z
3) составляй уравнение плоскости треугольника
4) подставляй в него X Z и выражай Y

← →
Toxic (2005-03-20 18:54) [2]

//Делай треугольниками
Сам базовый элемент не столь важен. Сделал и трианглами.
//Находи триангл на позиции X Z
Тоже нашел
//Составляй уравнение плоскости триангла
Здесь нужна помощь знатока - я с математикой дружен, но не настолько.

← →
Asteroid © (2005-03-20 19:48) [3]

> Toxic (20.03.05 18:54) [2]
> Составляй уравнение плоскости триангла

Для четырех точек тебе не удастся написать уранение плоскости, т.к. одна из точек Quad-а при первом же искривлении поверхности не будет лежать в одной плоскости с другими тремя точками.

Я так понял, треугольники получаются прямоугольные? Если да, то все довольно просто...

← →
Asteroid © (2005-03-20 19:48) [4]

← →
Asteroid © (2005-03-20 19:49) [5]

(прошу прощения за дубль)

← →
XProger © (2005-03-20 21:43) [6]

Имеем 3 вершины треугольника: v1, v2, v3
И уравнение плоскости: A*x + B*y + C*z + D = 0
Вектор N(A, B, C) - нормаль к полигону, вычисляется путём нехитрых действий называемых векторным умножением.
w1.X := v2.X - v1.X; w1.Y := v2.Y - v1.Y; w1.Z := v2.Z - v1.Z; w2.X := v3.X - v2.X; w2.Y := v3.Y - v2.Y; w2.Z := v3.Z - v2.Z; A := w2.Y * w1.Z - w2.Z * w1.Y; B := w2.Z * w1.X - w2.X * w1.Z; C := w2.X * w1.Y - w2.Y * w1.X; Затем нормализуем полученную нормаль len := sqrt(A*A + B*B + C*C) A := A/len B := B/len C := C/len Далее, псле того как нашли нормаль, подаставляем её в уравнение, а также вместо x y z указываем координаты одной из врешин полигона (не важно какой) Отседа выражаем D = -(A*v1.X + B*v1.Y + C*v1.Z) Всё! Теперь осталось подставить твои X Z и выразить Y := - (D + C*Z + A*X)/B Заметь, что для вертикальных полигонов (которых я надеюсь у тебя нет) этот метод не подходит.

← →
Toxic (2005-03-20 21:44) [7]

У меня есть оба варианта реализации поверхности - по трианглам и по квадам.
А треугольники прямоугольные.
//Если да, то все довольно просто...
Поделись, пожалуйста!

← →
Toxic (2005-03-20 21:52) [8]

Вот спасибо, XProger, выручил! :)

← →
Toxic (2005-03-25 14:19) [9]

Возвращаясь к этой теме... Судя по тому, что все не так хорошо работает, как хотелось бы, где-то в куске кода есть ошибка:

function TSurface.GetHeightAtPosition(Vector : TVector): real;
var D : real;
Triangle : integer;
begin
Triangle := IndexTriangle(Vector);
D := -(FNormals[Triangle].X * FVertex[FFaces[Triangle].A].X + FNormals[Triangle].Y * FVertices[FFaces[Triangle].A].Y + FNormals[Triangle].Z * FVertices[FFaces[Triangle].A].Z);
Result := -(D + FNormals[Triangle].Z * FVertices[FFaces[Triangle].A].Z + FNormals[Triangle].X * FVertices[FFaces[Triangle].A].X) / FNormals[Triangle].Y;
end;
Такая вот громоздкая функция определения высоты...

А вот функция IndexTriangle, которую позаимствовал с сишного кода:
function TSurface.IndexTriangle(Vector : TVector): integer;
const
MATCH_FACTOR : real = 0.9999; // Used to cover up the error in floating point
var
Angle : real; // Initialize the angle
vA, vB, vC : TVector; // Create temp vectors
i : integer;

function GetAngleBetweenVectors(V1, V2 : TVector) : real;
var DotProduct : real;
Magnitude : real;
Angle : real;
begin
DotProduct := VectorDotProduct(V1, V2);
Magnitude := VectorMagnitude(V1) * VectorMagnitude(V2);
Angle := arccos(DotProduct / Magnitude);
Result := Angle;
end;

begin
Angle := 0.0;

for i := 0 to FFacesCount - 1 do // Go in a circle to each vertex and get the angle between
begin
vA := VectorSub(VertexAsVector(FVertices[FFaces[i].A]), Vector); // Subtract the intersection point from the current vertex
vB := VectorSub(VertexAsVector(FVertices[FFaces[i].B]), Vector); // Subtract the point from the next vertex
vC := VectorSub(VertexAsVector(FVertices[FFaces[i].C]), Vector); // Subtract the point from the next vertex
Angle := Angle + GetAngleBetweenVectors(vA, vB); // Find the angle between the 2 vectors and add them all up as we go along
Angle := Angle + GetAngleBetweenVectors(vB, vC);
Angle := Angle + GetAngleBetweenVectors(vC, vA);
if(Angle >= (MATCH_FACTOR * (2.0 * PI)) ) then // If the angle is greater than 2 PI, (360 degrees)
begin
result := i; // The point is inside of the polygon
exit;
end;
end;

result := 0; // If you get here, it obviously wasn"t inside the polygon, so Return FALSE

end;

А функции VectorMagnitude и VectorDotProduct такие:
function VectorMagnitude(Vec : TVector) : real;
begin
Result := sqrt(Vec.X * Vec.X + Vec.Y * Vec.Y + Vec.Z * Vec.Z);
end;

function VectorDotProduct(Vec1, Vec2: TVector): Single;
begin
Result := Vec1.X * Vec2.X + Vec1.Y * Vec2.Y + Vec1.Z * Vec2.Z;
end;

Вот и весь код. Где и в чем ошибка - в упор не вижу. Объясните бестолковому, пожалуйста!

← →
Toxic (2005-03-25 14:22) [10]

P.S.: нормали к треугольникам рассчитаны заранее.

Всё! Теперь осталось подставить твои X Z и выразить
Y := - (D + C*Z + A*X)/B

Я имел ввиду координаты игрока X и Z а не вершины полигона! :)

with FNormals[Triangle] do Result := -(D + Z * Vector.Z + X * Vector.X)/Y;
Вот так заработает

И по поводу поиска полигона под ногами...
Я конечно понимаю что сегоднашние программисты не стремятся искать красивые решения, но всё же хочу дать тебе подсказку: у тебя Height map - сетка - матрица ты знаешь координаты X и Z соответственно путём нехитрых махинаций ты найдёшь полигон под копытами в FFacesCount*N раз быстрее чем тем методом который ты содрал из сишного кода.
И вот пример. есть экран 640х480 разделён он на 20х30 клеточек? нумерующикся слева-направо сверху-вниз. Следовательно размер каждой клеточки 32х16 пикселей. Вопрос: Как определить номер клетки в которой находится точка M (в экранной системе координат)? Ответ: M.Y div 16 * 40 * M.X div 32
А у тебя тут треугольники, что совсем незначительно усложнит задачу.

P.S.
А потом народ спрашивает "А почему у меня низкий FPS?". Так что не доводи до этого... ;)

Ответ: (M.Y div 16) * 20 + (M.X div 32)
:)

← →
Toxic (2005-03-26 17:39) [13]

Ндя... Признаюсь - невнимателен (: Спасибо, что поправил.
А решения красивые искать стремлюсь (: Хотя и не от желания - энцатьлетней давности P-233 без гипертрединга, с никаким кэшем... так что волей-неволей приходится сокращаться... иначе никак (:

Анализ поверхности Найти похожие ветки