Войти
ПрограммированиеФорумГрафика

Способ выделения объектов мышью в OpenGL приложениях. (Комментарии к статье)

Страницы: 1 2 Следующая »
#0
1:01, 5 авг. 2005

Комментарий к Статье Способ выделения объектов мышью в OpenGL приложениях.


#1
1:01, 5 авг. 2005

Честно сказать немного непонятно что есть "Dot Product и Cross Product"
1-е я так понял это вектор * вектор = число
2-е вектор на число? , но тогда получается , что в "(v2 - v1) ^ (ip - v1) " какая-то из скобок должна быть чилом, не так ли?

#2
3:26, 5 авг. 2005

bumblebee
dotproduct
x*y=|x|*|y|*cos(a)
да это число=)))
crossproduct
смешаное произведение векторов.получается вектор...gooogle it =)))

#3
4:08, 5 авг. 2005

Zlodei
crossproduct это не смешанное, а векторное.
в смешанном результат - число.

#4
16:50, 6 авг. 2005

Sark7
перепутал)))

#5
2:10, 7 авг. 2005

// вычисляем точку пересечения отрезка с плоскостью треугольника.
  CVector3 ip = (p1 + ((p2 - p1) * (-r1 / (r2 - r1))));
                                                    ^ мне интересно почему тут должен стоять "-". когда я писал код я с этим примером разобрался полностью и у меня все правильно работало когда минуса не было

#6
14:22, 19 ноя. 2005

У автора ошибка в тексте
Когда мы определяем принадлежит ли точка к заданному треугольнику, то
следующие выражения должны быть одного знака, а не меньше или равными нулю.

if( (((v2 - v1) ^ (ip - v1)) & n) <= 0) return FALSE;
if( (((v3 - v2) ^ (ip - v2)) & n) <= 0) return FALSE;
if( (((v1 - v3) ^ (ip - v3)) & n) <= 0) return FALSE;
Вот исправленный код
if( (((v2 - v1) ^ (ip - v1)) & n) >= 0)
{
	if( (((v3 - v2) ^ (ip - v2)) & n) <= 0) return FALSE;
	if( (((v1 - v3) ^ (ip - v3)) & n) <= 0) return FALSE;
}
else
{
	if( (((v3 - v2) ^ (ip - v2)) & n) >= 0) return FALSE;
	if( (((v1 - v3) ^ (ip - v3)) & n) >= 0) return FALSE;
}

Прошло более 1 года
#7
12:14, 29 июня 2007

А я наоборот проецирую полигон в плоскость ViewPort-a функцией gluProject. ИМХО так тратиться меньше тактов проца, т.к. нету гемороя с выбором плоскости проецирования. Плюс проецированый полигон можно не обновлять пока объект не изменит положение относительно камеры.
Правда мне это для GUI-шника нужно.... Может в некоторых других случаях это не так удобно.

#8
12:59, 29 июня 2007

> Честно сказать немного непонятно что есть "Dot Product и Cross Product"

2 вектора определяют плоскость, так? Cross Product возвращает вектор, перпендикулярный этой плоскости (нормаль). Проще говоря это векторное произведение векторов...(http://elib.ispu.ru/library/math/sem1/index.html)

Прошло более 9 месяцев
#9
15:09, 20 апр. 2008

вообще, ближнюю точку селецирующего отрезка (где глубина передается -1) можно не вычислять :) это просто позиция камеры

Прошло более 10 месяцев
#10
9:13, 25 фев. 2009

По идее для правильного выбора объектов в 3D мы не должны видеть линию, проведенную от начала отрезка к концу, но в данном примере она видна :(

#11
12:08, 7 мар. 2009

привет,может кто исходник кинуть? я то у меня ерор,не знаю что делать,только нечал этим увлекатьсо

  p1 = CVector3(wx,wy,wz);
Error  1  error C2661: 'CVector3::CVector3' : no overloaded function takes 3 arguments

#12
20:55, 23 мар. 2009

От автора:

К сожалению при написании статьи были не освещены некоторые
тонкие или важные моменты, которые привели к большому количеству
вопросов и "непоняток". Постараюсь разъяснить некоторые моменты.
-------------------------------------------------------
Принцип действия функции intersect_triangle_line()
и математика, лежащая в ее основе (от автора).
-------------------------------------------------------

Итак, функция intersect_triangle_line() вычисляет точку пересечения
между отрезком и треугольником без использования тормозных
тригонометрических функций типа acos() и т.п.

Исходные данные:

Допустим мы имеем треугольник (v1,v2,v3) и отрезок (p1,p2). Мы
хотим узнать, пересекает ли данный отрезок наш треугольник и если да,
то вычислить точку пересечения (pc).

Для сокращение объема кода введем оператор DotProduct "&" и CrossProduct "^".

Для класса CVector3 (из статьи) эти операторы будут определяться так:

float operator & (const CVector3& v1, const CVector3& v2)
{
  return (v1.x * v2.x + v1.y * v2.y + v1.z * v2.z);
}

CVector3 operator ^ (const CVector3& v1, const CVector3& v2)
{
  return CVector3(v1.y * v2.z - v2.y * v1.z,
                  v1.z * v2.x - v2.z * v1.x,
                  v1.x * v2.y - v2.x * v1.y);
}

Нормаль треугольника (v1,v2,v3) вычисляется по формуле:

n = Normalize((v2 - v1) ^ (v3 - v2));

где функция Normalize() выглядит так:

CVector3 Normalize(CVector3 v)
{
  float len = Length(v);
  return (v / len);
}

где :)

float Length(CVector3 v)
{
  return sqrt(v.x * v.x + v.y * v.y + v.z * v.z);
}

Примечание: Эти функции отсутствуют в статье, но приведены здесь
в качестве примера. В функции Normalize() отсутствует проверка деления
на 0.0 - для простоты :)

(В статье подразумевается, что нормаль (n) уже вычислена и передается в функцию
intersect_triangle_line() в качестве параметра).

Точка наблюдения. Если мы посмотрим на треугольник "сверху", то вершины будут
обходиться против часовой стрелки, а нормаль направлена "на нас".

Плоскость треугольника имеет положительное (+ПП) и отрицательное (-ПП)
полупространство. (+ПП) это то пространство, в которое
направлена нормаль треугольника (n). Т.о. наблюдатель, т.е. "мы" находимся
в (+ПП) и видим лицевую сторону треугольника.

Примерно таковы исходные данные.

----------------------------------------------------------------------
Вычисление точки пересечения отрезка (p1,p2) с плоскостью треугольника.
----------------------------------------------------------------------

Далее следует код (см. текст функции):

float r1 = n & (p1 - v1);
float r2 = n & (p2 - v1);

Если длинна нормали треугольника (v1,v2,v3) - вектора (n)
равна 1.0 (а так и должно быть), то параметры (r1),(r2) численно
равны расстоянию соответствующей точки (p1 или p2) до плоскости
треугольника. Здесь вершина (v1) играет роль "точки, лежащей на
плоскости", т.е. чисто вспомогательную роль.
Вместо нее можно взять любую точку лежащую на плоскости,
напр. (v2) или (v3).

Знак параметров (r1),(r2) важен, т.к. он показывает, в каком (ПП)
находится соответствующая точка отрезка (p1,p2).
Если (r1 > 0.0) то точка (p1) находится в (+ПП) - со стороны наблюдателя.
Если (r1 < 0.0) - то соотв. в (-ПП) - "за треугольником".
Если (r1 == 0.0) - то точка (p1) лежит на плоскости треугольника.

Далее по тексту следует строка:

if( f1_sgn(r1) == f1_sgn(r2) ) return FALSE;

Здесь вводится новая вспомогательная функция f1_sgn() которая
возвращает целое число, символизирующее знак аргумента.
Данная строка означает, что если знаки параметров (r1),(r2) одинаковые,
то отрезок не пересекает плоскость треугольника. Действительно
это так, ведь отрезок будет пересекать плоскость только если точки
(p1),(p2) лежат либо в разных (ПП) (а это разные знаки), либо одна из
этих точек лежит на плоскости, а другая - нет (тоже разные знаки).
А если оба знака == 0, то это значит что обе точки (p1),(p2) лежат на
плоскости - а следовательно отрезок паралелен плоскости и точку
пересечения искать бессмыслено - ее нет.

Далее следует строка, в которой мы вычисляем точку пересечения
отрезка (p1,p2) с плоскостью треугольника:

CVector3 ip = (p1 + ((p2 - p1) * (-r1 / (r2 - r1))));

В этой формуле "незримо" присутствует параметр "t", который я
хотел бы рассмотреть отдельно. Он равен:

float t = -r1 / (r2 - r1);

Геометрический смысл этого параметра такой - это "нормированное"
(а не реальное! - Length(ip - p1)) расстояние между точкой (p1) и
точкой пересечения с плоскостью (ip).

Причем точке (p1) соответствует значение t = 0.0,
точке (p2) соответствует значение t = 1.0. А точке пересечения (ip),
которая находится между точками (p1) и (p2) - соответственно
t = (0.0 ... 1.0). Этот параметр удобно использовать для сравнения
близости точки пересечения (ip) к точке (p1), которая соответствует
координатам курсора мыши на экране в мировой системе координат (см.
статью). Это нужно для выбора ближайшего к точке (p1) треугольника
сцены.

Здесь следует обратить внимание на знаменатель (r2 - r1) и не
допускать чтобы это значение приблизилось к 0.0, что соответствует
"почти параллельности" отрезка (p1,p2) плоскости треугольника.

С использованием параметра (t) формула для вычисления (ip)
будет выглядеть так:

CVector3 ip = p1 + (p2 - p1) * t;

Продолжение следует...

#13
20:57, 23 мар. 2009

...Продолжение.
---------------------------------------------
Проверка принадлежности точки (ip) внутренней области треугольника.
---------------------------------------------

Итак, мы нашли точку пересечения (ip) отрезка (p1,p2) с плоскостью
треугольника. Теперь нам нужно определить, находится ли эта точка
"внутри треугольника", т.е. принадлежит ли она ему?

Эту проверку выполняют сл. строки:

if( (((v2 - v1) ^ (ip - v1)) & n) <= 0) return FALSE; 
if( (((v3 - v2) ^ (ip - v2)) & n) <= 0) return FALSE;
if( (((v1 - v3) ^ (ip - v3)) & n) <= 0) return FALSE;

Каждое условие (строка) - тест положения точки (ip) относительно
соответствующего ребра (v1,v2), (v2,v3) и (v3, v1).

Для того чтобы понять, как работают эти формулы, рассмотрим подробнее
первое условие, где анализируется положение точки (ip) по отношению к
первому ребру треугольника (v1,v2).

Как мы уже условились, вершины треугольника (v1,v2,v3) идут против
часовой стрелки
, а его нормаль (n) направлена "к нам". Теперь рассмотрим
вспомогательный треугольник (v1,v2,ip). Вычислим нормаль этого треугольника:

n12 = (v2 - v1) ^ (ip - v1)

(подождите, не ругайтесь! Я знаю, что (n12) - не единичная нормаль, но
для наших расчетов это не играет роли!)

и сравним взаимное направление векторов (n) и (n12) с помощью операции
DotProduct:

dot12 = (n12 & n)

Теперь давайте мысленно сориентируем наш треугольник (v1,v2,v3) так, чтобы
вершина (v1) находилась внизу, а вершина (v2) - вверху (для удобства).

Если точка (ip) (по отношению к точке наблюдения) будет располагаться
справа от ребра (v1,v2), а точнее - справа от прямой, проходящей
через это ребро, то эта точка никак не может принадлежать треугольнику
(v1,v2,v3) в независимости от результатов остальных тестов. В этом случае
вершины треугольника (v1,v2,ip) будут идти по часовой стрелке, а
векторы (n12) и (n) - направлены в противоположные стороны, что и
даст нам dot12 < 0 !

Если (ip) расположена слева от (v1,v2) - с той же стороны, что и (v3), то
и (v1,v2,v3) и (v1,v2,ip) будут идти против часовой стрелки и нормали
(n) и (n12) будут направлены в одну и ту же сторону и соответственно их
dot12 > 0 .

Если (ip) лежит на самом ребре (v1,v2), то dot12 == 0. Этот случай считаем
как "точка принадлежит треугольнику".

Таким образом, если (ip) находится слева от (v1,v2) то мы по точно такой же
схеме должны проверить положение (ip) относительно оставшихся ребер (v2,v3) и
(v2,v1), что и делаем :

if( (((v3 - v2) ^ (ip - v2)) & n) <= 0) return FALSE;
if( (((v1 - v3) ^ (ip - v3)) & n) <= 0) return FALSE;

Точка (ip) находится внутри треугольника (v1,v2,v3) только в том случае, если
ни одно из 3 вышеуказанных условий не выполнилось. В этом случае:

pc = ip; return TRUE; 

Если хотя бы одно из условий выполнилось, то точка (ip) не принадлежит
треугольнику (v1,v2,v3) и проводить остальные тесты нет смысла.

----------------------------------------------------------------
Функция intersect_triangle_line() легко адаптируется и для выпуклых
многоугольников. В этом случае лишь возрастет количество ребер и соответственно
количество тестов в конце функции. Например для 6-угольника с вершинами
(v1,v2,v3,v4,v5,v6) эти тесты будут выглядеть так:

if( (((v2 - v1) ^ (ip - v1)) & n) <= 0) return FALSE; 
if( (((v3 - v2) ^ (ip - v2)) & n) <= 0) return FALSE;
if( (((v4 - v3) ^ (ip - v3)) & n) <= 0) return FALSE;
if( (((v5 - v4) ^ (ip - v4)) & n) <= 0) return FALSE; 
if( (((v6 - v5) ^ (ip - v5)) & n) <= 0) return FALSE;
if( (((v1 - v6) ^ (ip - v6)) & n) <= 0) return FALSE;

----------------------------------------------------------------
Фуууу! Много накатал! Теперь коротко по вопросам:
----------------------------------------------------------------

> Честно сказать немного непонятно что есть "Dot Product и Cross Product"

DotProduct(v1,v2) - скалярное произведение векторов (v1) и (v2).
Результат - число. Геометрический смысл:
Dot > 0.0, если угол между обоими векторами < 90 гр.
Dot < 0.0 если угол между обоими векторами > 90 гр.
Dot == 0.0 если угол между обоими векторами == 90гр.

CrossProduct(v1,v2) - векторное произведение векторов (v1) и (v2).
Результат - вектор. Геометрический смысл:
вектор результата перпендикулярен одновременно и (v1) и (v2).

> мне интересно почему тут должен стоять "-". когда я писал код я с
> этим примером разобрался полностью и у меня все правильно работало
> когда минуса не было

Гм... често говоря знак важен (см. текст выше). Стоит у меня перепутать
знак в этой формуле, как сразу все перестает на хрен работать :)
Возможно у тебя вершины треугольников для лицевых граней идут "по
часовой".. тогда.. может и будет работать... гм.. не знаю. Трудно
сказать не видя кода.

> У автора ошибка в тексте...

Нет. Условия написаны правильно. Функция 100% проверенная в работе.
Жаль сейчас под рукой нет тестовой демки - можно было бы показать.
Каждое условие (из трех) - тест положения точки (ip) относительно
соотв. ребра. Как работает тест для ребра - описано выше.

> А я наоборот проецирую полигон в плоскость ViewPort-a

Да, такой вариант возможен если решается задача именно "выделения
мышью". Тогда делать проверки в 2d - менее затратно. Но я писал
функцию именно для 3d- целей, чтобы потом использовать эти формулы
для всяких collision-detection, тестов на пересечения ребер и граней
многогранников и т.п. Хотя для выделения мышью - согласен, можно и так.

> вообще, ближнюю точку селецирующего отрезка (где глубина передается -1)
> можно не вычислять :) это просто позиция камеры

Нет, надо. Точка (p1) - это не позиция камеры, а точка лежащяя на
передней отсекающей плоскости (near clip plane), которая в
свою очередь расположена на расстоянии (z_near) от позиции камеры.
Все пикселя, расположенные ближе этой плоскости обрезаются z-буфером
и не видны. Короче - (p1) лежит на (near clip plane) а (p2) - на
(far clip plane).

В принципе если значение (z_near) невелико по отношению к размерам
треугольников, то так тоже будет работать, но возможны глюки, когда
отрезок (camera_pos, p2) на участке между (camera_pos) и (near clip plane)
случайно выделит треугольник, который на экране не виден (обрезан).

Но в принципе - работать будет. А вычисление (p1) - это для чистоты
эксперемента :) Так мы будем выделять лишь те поверхности треугольников,
которые реально видны и находятся в зоне видимости между (z_near) и
(z_far).

> По идее для правильного выбора объектов в 3D мы не должны видеть
> линию, проведенную от начала отрезка к концу, ...

Совершенно верно. Селектирующий отрезок действительно не должен быть
виден (если все правильно сделано), т.к. для наблюдателя находящегося
в позиции камеры (camera_pos) эта линия превращается в точку под курсором
мыши.

> но в данном примере она видна :(

Не понял, где видна? А где она должна быть видна?

Прошло более 9 месяцев
#14
14:23, 12 янв. 2010

Автор - молодец! Очень полезная статья, особенно когда самому не хочется поднимать старые конспекты по математике и физике. А также очень мне понравилось, что пример можно использовать почти сразу, это помогает когда нужно что-то быстро и сейчас. С начала, в самой статье, было многовато дыр (не освященных моментов), что делало статью весьма осложненной для восприятия. Например, описание операторов... ну не всем же очевидны такие обозначения умножения векторов. Но после, в комментариях, приведенные пояснения полностью раскрывают всю тему целиком.

Спасибо ^_^, всё ясно и понятно!

Страницы: 1 2 Следующая »
ПрограммированиеФорумГрафика

Тема в архиве.