C++ C++ C# C# ASP.NET Security ASP.NET Security ASM ASM Скачать Скачать Поиск Поиск Хостинг Хостинг  
  Программа для работы с LPT портом...
Язык: .NET — ©Alexey...
  "ASP.NET Atlas" – AJAX в исполнении Micro...
Язык: .NET — ©legigor@mail.ru...
  "Невытесняющая" Многопоточность...
Язык: C/C++ — ©...
  01.05.2010 — Update World C++: Сборник GPL QT исходников
  15.12.2007 — Весь сайт целиком можно загрузить по ссылкам из раздела Скачать
Хостинг:
Windows 2003, ASP.NET 2.0
бесплатный и от 80 руб./мес


   Отправить письмо
Кулабухов Артем, Беларусь




 Глава 7 Проверка попадания / 3D DirectX / Литература

Глава 7 Проверка попадания


Одна из распространенных задач, возникающих при работе с трехмерной графикой, - выяснить, принадлежит ли точка в трехмерном окне какому-либо из видимых объектов. Иногда этот процесс называют выделением (selection) или выбором (picking). В документации по DirecQD он назван выбором, однако я буду именовать его проверкой попадания (hit testing), потому что я пользовался этим термином с первых дней программирования для Microsoft Windows.

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

Во втором примере мы научимся определять грань объекта, в которую попала указанная точка. Это может пригодиться, например, если вы хотите задать цвет отдельной грани объекта. В третьем примере мы определим фактическое положение точки попадания в объекте. Зная точные координаты точки попадания, можно модифицировать объект тем или иным образом - скажем, добавить выпуклость на плоской поверхности.

Примеры приложений для этой главы находятся в каталоге Select. И снова я предлагаю вам сесть за компьютер и запускать необходимые программы по мере развития сюжета.

Процесс выделения

Выделение объектов мышью выглядит очень естественно - пользователь наводит указатель мыши на объект и нажимает кнопку. Тем не менее приложению не так просто определить, какой же объект был выделен. Прежде всего, пользователь может применять мышь для манипуляций с объектами, поэтому сообщения, посылаемые Windows главному окну (о том, где находится указатель мыши и какая кнопка была нажата), должны попадать сразу в несколько мест. Обычно это делается следующим образом: некий центральный фрагмент программы перехватывает сообщения мыши и направляет их всем другим фрагментам, которым они могут понадобиться. Вы сохраняете текущее состояние мыши в глобальной переменной и позволяете всему коду непосредственно обращаться к ней. Альтернативный вариант - реализовать предложенную мной схему, то есть написать простую функцию, которая обрабатывает сообщения мыши и обращается к другим фрагментам приложения, уведомляя их о наступлении того или иного события.

Предположим, вы знаете, в какой точке экрана находится указатель мыши и что пользователь нажал кнопку, желая выделить объект в макете. Но как же определить, в каком объекте пользователь произвел щелчок мышью? Первым делом необходимо привести экранные координаты мыши к координатам клиент-ной области вашего окна. Затем вам фактически понадобится обратить проекционное преобразование, которым пользуется механизм визуализации, и перевести двумерные координаты на вашем экране в пространственные. Сделать это не так просто, как может показаться с первого взгляда. Как мы вскоре увидим, меха-

Процесс выделения 'тЦЦ 165


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

В наших приложениях-примерах в любой момент времени разрешается выделить только один объект. Подобное ограничение упрощает код, поскольку можно завести переменную-указатель (m_pCurShape), которая ссылается на текущий выделенный объект или равна NULL, если выделенных объектов нет. Позднее мы увидим, что в наших приложениях также поддерживается концепция текущей выделенной грани объекта - грани текущего выделенного объекта, над которой находился указатель мыши в момент выделения.

Для того чтобы реализовать проверку попаданий в приложениях-примерах, мне пришлось включить в них немало фрагментов, рассредоточенных по разным местам. В последующих разделах я постараюсь объяснить, где должен находиться тот или иной фрагмент и как он работает. Если вы не следите за моими объяснениями и хотите самостоятельно разобраться, как работает программа, советую запустить приложение под отладчиком, установить точку прерывания в функции C3dWnd::OnWndMsg (файл 3dWnd.cpp в библиотеке 3dPlus) и следить за выполнением программы. Еще раз хочу подчеркнуть, что эту задачу можно было решить множеством способов, причем выбранное мною решение, вероятно, ничуть не лучше любого другого. Если вам кажется, что ваша собственная идея даст сто очков вперед предложенной мною, - наверное, вы правы и именно ей вам следует пользоваться в ваших программах.

Выделение всего объекта

Основная часть задачи выделения объектов выполняется механизмом визуализации в рамках интерфейса ракурса. Тем не менее перед тем, как приступать к изучению его работы, я бы хотел кратко описать последовательность событий, происходящих с момента щелчка мышью на объекте макета. Мы пройдемся по различным фрагментам программы, начиная с трехмерного окна, в котором отображается макет.

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

int CMainFrame::OnCreate(LPCREATESTRUCT IpCreateStruct) {

// Разрешить выделение объектов мышью m_wnd3d.EnableMouseSelection(OnSelChange, this);

}

166 lly Глава 7. Проверка попадания


В приведенной выше строке программы устанавливается уведомляющая функция OnSelChange. Функция OnSelChange является статической функцией класса CMainFrame, и потому значение указателя this для нее не определено. Как мы вскоре увидим, второй аргумент функции EnableMouseSetection передается в виде аргумента рАгд при вызове уведомляющей функции - в данном случае мы передаем указатель на объект C++ (если этот момент покажется вам непонятным, просмотрите код функции EnableMouseSelection в файле C3dWnd.cpp). Давайте посмотрим, как щелчок мышью обрабатывается в классе C3dWnd - это снова приведет нас к обсуждению уведомляющей функции. Ниже приведен фрагмент обработчика сообщений окна, связанный с проверкой попадания:

BOOL C3dWnd::OnWndMsg(UINT message, WPARAM wParam,

LPARAM IParam, LRESULT* pResult ) {

// Разрешено ли выделение объектов мышью?

if (m_bEnableMouseSelection

&& (message == WM_LBUTTONDOWN)) (

CPoint pt(LOWORDfIParam), HIWORD(IParam));

C3dShape* pShape = HitTest(pt);

if (m_p3elChangeFn) {

// Вызвать уведомляющую функцию m_pSelChangeFn(pShape, pt, m pSelChangeArg);

} }

return CWnd::OnWndMsg(message, wParam, IParam, pResult);

}

Если выделение мышью было разрешено (рассматривается именно этот случай), мы создаем объект CPoint по координатам мыши, содержащимся в сообщении WM_LBUTTONDOWN, а затем вызываем функцию HitTest, чтобы определить, произошло ли попадание в фигуру. Результат проверки (который равен NULL, если под мышью не оказалось ни одного объекта) возвращается приложению через уведомляющую функцию (которая была указана при разрешении выделения мышью). Давайте посмотрим, как уведомляющая функция используется в приложении:

void CMainFrame::OnSelChange(C3dShape* pShape, CPoint pt,

void* pArg) (

// Получить указатель на класс

CMainFrame* pThis = (CMainFrame*) pArg;

ASSERT(pThis) ;

ASSERT (pThis->IsKindOf (RUNTIME_CLASS (CMainFrame) ) ) ;

if (pShape) {

// Убедиться, что попадание пришлось

Выделение всего пбъеш-а тТО 1&7


// не в рамку выделения и не в фигуру-указатель if ( !pShape->IsPartO? (pThis->m_pSelBox)

&& !pShape->IsPartOf (pThis->m_pHitPtr) ) {

// Определить грань, в которую мы попали

C3dViewport* pViewport =

pThis->m_wnd3d.GetStage() ->GetViewport

p3hape->HitTest (pt, pViewport,

&pThis->m_iHitFace, &pThis->m_vHitPoint) ;

1 .'. i ^ i * \

pShape = NULL;

}

i

I / Сделать выделенную фигуру текущей pThis->MakeCurrent (pShape) ;

}

Выделенный объект передается функции MakeCurrent, которая рисует вокруг него рамку, чтобы отличить от других объектов (мы подробнее рассмотрим функцию MakeCurrent на стр. 177). Самая важная особенность этого фрагмента заключается в том, что 41ункция OnSelChange является статической, и потому, как было сказано выше, не имеет указателя this. Мы справились с данным затруднением, передавая адрес объекта C++ в качестве аргумента функции, разрешившей выделение объектов мышью (EnableMouseSelection). Значение, полученное уведомляющей функцией, преобразуется к типу указателя на наш класс. Хитро, не правда ли? Реализация косвенного вызова (callback) функции класса требует несколько больших усилий, поэтому уведомляющая функция была сделана статической для упрощения программы.

Теперь давайте более подробно рассмотрим, как же происходит проверка попадания. Функция C3dWnd::HitTest просто передает запрос ракурсу:

// Проверить на попадание в видимый объект C3dShape* C3dWnd::HitTest(CPoint pt) (

ASSERT(m_p3tage) ;

return m_pStage->GetViewport ()->HitTest (pt) ;

}

Фактическая проверка попадания производится в классе ракурса (код которого находится в файле 3dStage.cpp):

C3dShape* C3dViewport::HitTest(CPoint pt) {

IDirect3DRMPickedArray* pIPickArray = NULL;

168 ЯНУ Глава 7. Поовеока попадания


ASSERT(m_pIViewport) ;

m_hr = m_pIViewport->Pick(pt.x, pt.y, SpIPickArray);

if (FAILED(m_hr)) return NULL;

// Проверить, есть ли в массиве элементы if (pIPickArray->GetSize () == 0) { pIPickArray->Release () ;

return NULL;

)

// Получить первый (верхний) элемент IDirect3DRMVisual* pIVisual = NULL;

IDirect3DRMFrameArray* pIFrameList = NULL;

m hr = pIPickArray->GetPick(0, SpIVisual, SpIFrameList, NULL) ;

ASSERT(SUCCEEDED(m_hr)) ;

ASSERT(pIVisual) ;

ASSERT(pIFrameList) ;

// Получить последний фрейм в списке IDirect3DRMFrame* pIFrame - NULL;

pIFrameList->GetEiement (pIFrameList->GetSize () - 1, &pI Frame);

ASSERT(pIFrame) ;

// Получить значение 'AppData' фрейма, // которое должно быть указателем на класс C++

C3ctShape* pShape = (C3dShape*) pIFrame->GetAppData () ;

if (pShape) (

if(!pShape->IsKindOf(RUNTIME_CLASS(C3dShape))) { pShape = NULL;

}

pIFrame->Release () ;

pIFrameList->Release () pIVisual->Release () ;

pIPickArray->Release ()

return pShape;

Первым делом мы требуем от интерфейса ракурса создать то, что в механизме визуализации называется списком выбора (pick list), то есть список всех визуальных элементов, находящихся под определенной точкой окна. Список визуальных элементов (pIPickArray) упорядочен так, чтобы верхний элемент находился в начале списка. Затем мы определяем значение указателя (pIVisual) на первый визуальный элемент и получаем по нему список фреймов (pIFrameList), к которым присо-

<::::й^

Выделение всего объекта тЃЃЃЃ 169


единен данный визуальный элемент. На рис. 7-1 показано, как связаны между собой объекты различных списков.

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

102.jpg

Рис. 7-1. Структура списка выбора

Последнее, что нам осталось сделать, - извлечь значение переменной AppData из интерфейса фрейма. Объекты классов CSdFrame и C3dShape хранят в этой переменной значения своих указателей this. Мы преобразуем значение AppData к типу указателя на объект C3dShape и проверяем, не равен ли получившийся указатель NULL. Если не равен, то выполняется дополнительная проверка того, что данный указатель является указателем на объект C3dShape, с использованием функции MFC, возвращающей runtime-информацию о классе.

AppData может принимать значения трех типов: NULL, указатель на объект C3dFrame, указатель на объект C3dShape. Код проверки попадания работает лишь в том случае, если указатель ссылается на объект C3dShape и если объект класса C++, создавший визуальный элемент и фрейм, не был уничтожен. Деструктор класса C3dFrame (базового для C3dShape) присваивает AppData значение NULL, так что можно не опасаться случайного получения указателя на удаленный объект C++. Из всего сказанного следует, что функция HitTest полезна лишь при работе с теми трехмерными фигурами, с которыми связан текущий объект класса C3dShape.

Отображение выделения на экране

Если запустить приложение Select и щелкнуть на каком-нибудь объекте, вокруг последнего появляется рамка, похожая на изображенную на рис. 7-2.

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

170

Глава 7. Проверка попадания


тами О, О, О. В случае сферы на рис. 7-2, начало координат находится внутри объекта.

103.jpg

Рис. 7-2. Выделенный объект

Функция, рисующая рамку, несложна, хотя несколько длинна:

void CMainFrame::ShowSelection() {

// Определить граничную область объекта double xl, x2, yl, y2, zl, z2;

BOOL b = m_pCurShape->GetBox (xl, yl, zl, x2, y2, z2);

ASSERT(b) ;

// Создать новую рамку вокруг фигуры m_pSelBox = new CSdShape;

double r = 0.03;

double re = r * 2;

C3dShape rl, r2, r3, r4, r5, r6, r7, r8, r9,

rIO, rll, rl2, rd, ru, cd, cu;

// Создать цилиндры, из которых состоит рамка

m_pSelBox->AddChild(&r3) ;

r4.CreateRod(xl, y2, zl, x2, y2, zl, r) ;

m_pSelBox->AddChild(&r4) ;

r5.CreateRod(x2, yl, zl, x2, y2, zl, r) ;

m_pSelBox->AddChild(&r5) ;

r6.CreateRod(xl, y2, zl, xl, y2, z2, r) ;

^йй ВЫЛРПЙНИА япйгп nfi'^Rkra ''m^.

171


m_pSelBox->AddChild(&r6) ;

r7.CreateRod(x2, y2, zl, x2, y2, z2, r) ;

m_pSelBox->AddChild(&r7) ;

r8.CreateRod(x2, yl, zl, x2, yl, z2, r) ;

m_p3elBox->AddChild(&r8) ;

r9.CreateRod(xl, yl, z2, xl, y2, z2, r) ;

m_pSelBox->AddChild(&r9) ;

rIO.CreateRodfxl, yl, z2, x2, yl, z2, r) ;

m_pSelBox->AddChild(&rlO) ;  rll.CreateRod(x2, yl, z2, x2, y2, z2, r) ;

m_pSelBox->AddChild(&rll) ;

rl2.CreateRod(xl, y2, z2, x2, y2, z2, r) ;

m_pSelBox->AddChild(&rl2) ;

//Создать цилиндры и конусы для отображения векторов rd.CreateRod(0, 0, 0, 0, 0, z2 * 1.2, r) ;

m pSelBox->AddChild (&rd) ;

cd.CreateCone(0, 0, z2 * 1.2, re, TRUE, О, О, z2 * 1.4, 0, FALSE);

m_p3elBox->AddChild(&cd) ;

ru.CreateRod(0, 0, 0, 0, y2 * 1.1, 0, r) ;

m_pSelBox->AddChild(&ru) ;

cu.CreateCone(0, y2  1.1, 0, re, TRUE, 0, y2 * 1.2, О, О, FALSE) ;

m_pSelBox->AddChild(&cu) ;

// Задать положение и ориентацию рамки

// в соответствии с положением и ориентацией фигуры

double х, у, z, xd, yd, zd, xu, yu, zu;

m pCurShape->GetPosition (х, y, z) ;

m_pCurShape->GetDirection (xd, yd, zd, xu, yu, zu) ;

m_pSelBox->SetPosition (х, y, z) ;

m_pSelBox->SetDirection (xd, yd, zd, xu, yu, zu) ;

// Присоединить рамку к текущей фигуре,

// чтобы обеспечить их совместное перемещение

m_pCurShape->AddChild (m_pSelBox) ;

Граничная область фигуры используется для задания положения цилиндров, образующих рамку, и пар конус/цилиндр, которые изображают вектор направления и верхний вектор объекта. Все цилиндры и конусы присоединяются к одному объекту-рамке, имеющему то же положение и ориентацию, что и выделенный объект. Затем рамка присоединяется к выделенному объекту, чтобы она перемещалась вместе с ним.

Поскольку рамка также состоит из нескольких визуальных элементов, можно задать резонный вопрос - почему их нельзя выделить мышью? В уведомляющей функции на стр. 167 можно найти следующий оператор:

pShape->IsPartOf (pThis->m_pSelBox) 172 ад1'' Глава 7. Проверка попадания


Он является составной частью проверки, которая не позволяет выделять видимые элементы рамки. Функция IsPartOf проверяет, совпадает ли данный фрейм с фреймом-аргументом или с одним из его родителей. Другими словами, она проверяет, входит ли данный фрейм в иерархию другого фрейма.

Возможно, вы также вспомните мои слова о том, что видимые объекты, не имеющие присоединенных объектов C++, нельзя выделить. Если посмотреть на исходный текст функции, которая строит рамку, можно убедиться в том, что объекты C++, использованные при создании цилиндров и конусов, уничтожаются после создания рамки. Спрашивается, зачем же тогда нужна проверка IsPartOf? Дело в том, что один объект C++ все же остался - тот, на который ссылается переменная m_pSelBox. Чтобы заведомо устранить все возможные проблемы, мы идем на эту дополнительную проверку, хотя она и не является абсолютно необходимой. Кроме того, когда-нибудь в будущем функция, которая создает рамку, может измениться, и созданные объекты C++ не будут удаляться. Даже если это произойдет, выделение должно работать по-прежнему.

Мы научились выделять объекты. Запустите приложение Select, вставьте в текущий макет несколько объектов и пощелкайте на них мышью. При установке флажка Selection Box вы можете перемещать текущий выделенный объект и при этом видеть его рамку. Команда-флажок View Ѓ Selection Box разрешает (и запрещает) отображение рамки в окне.

Выделение отдельной грани

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

Задача состоит в следующем: зная координаты точки в трехмерном окне, необходимо определить грань объекта, находящуюся под данной точкой. Будем считать, что под точкой находится некоторый объект, который был найден с помощью методики, описанной в предыдущем разделе. На рис. 7-3 изображено графическое представление этой задачи.

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

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

Единственное затруднение может возникнуть при проектировании вершин грани на плоскость вида; этот процесс состоит из трех шагов. Сначала необходимо преобразовать координаты каждой вершины из локальных координат фрейма в систему общих, <мировых> координат. Затем мировые координаты преобразуются в однородные координаты в плоскости вида. Наконец, вектор однородных координат преобразуется в точку окна.

Выделение отдельной грани 4Ѓ^i 173


104.jpg

Рис. 7-3. Грань, спроектированная в трехмерное окно

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

BOOL C3dShape::HitTest(CPoint pt,

C3dViewport* pViewport, int* piFace, D3DVECTOR* pvHit)

int iHitFace = -1;

double dHitZ = 0;

// Просмотреть список граней D3DVECTOR lv;

D3DVECTOR wv;

D3DRMVECTOR4D sv;

for (int i = 0; i

// Получить данные грани IDirect3DRMFace* piFace њ NULL;

m hr = pIFac@List->GetElement (i, spIFace) ;

ASSERT;SUCCEEDED(m_hr)) ;

// Получить количество вершин и разместить массив // для хранения экранных координат int nVert = pIFace->GetVertexCount () ;

ASSERT(nVert > 2) ;

174

Глава 7. Проверка попадания


POINT* pScrnVert = new POINT [nVert];

// Преобразовать каждую вершину к экранным координатам double dZ = 0;

for (int v = 0; v

// Получить вектор в локальных координатах

// (координатах фрейма)

m_hr = pIFace->GetVertex(v, &lv, NULL) ;

ASSERT(SUCCEEDED(m_hr)) ;

// Преобразовать их в мировые координаты m_hr = m_pIFrame->Transform(&wv, &lv) ;

ASSERT(SUCCEEDED(m_hr)) ;

// Преобразовать мировые координаты // в экранные

m_hr = pIViewport->Transform(&sv, &wv) ;

ASSERT(SUCCEEDED(m_hr)) ;

// Преобразовать однородные координаты

// в абсолютные координаты пикселей

double w = sv.w;

if (w != 0) {

pScrnVert[v].x = (int) sv.x / w;

pScrnVert[v].у = (int) sv.y / w;

dZ += sv.z / w;

) else {

pScrnVert[v].x = 0;

pScrnVert[v].у = 0;

} } dZ /= nVert;

// Проверить, лежит ли точка попадания внутри // многоугольника на экране

if (::_3dPointInPolygon(pScrnVert, nVert, pt)) { if (iHitFace <0) { iHitFace="i;</font">

dHitZ = dZ;

} else (

if (dZ

iHitFace = i;

dHitZ = dZ;

} } )

// Освободить грань после завершения delete [] pScrnVert;

Выделение отдельной грани 'тЩ 175


pIFace->Release () ;

}

// Установить возвращаемое значение *piFace = iHitFace;

return TRUE;

}

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

Однородный вектор состоит из координат х, у, z и w. К чему так много координат, когда для представления точки в окне достаточно х и у? Причина заключается в том, что если вершина окажется очень близко к камере, то преобразование, отображающее координаты на плоскость вида, приведет к состоянию, близкому к делению на ноль, - разумеется, это нежелательно. Использование однородного вектора для представления результата позволяет избежать деления на ноль (поверьте мне на слово или покопайтесь в справочниках). При наличии однородного вектора мы вычисляем координаты точки в окне делением координат х, у и z на величину w. Если значение w равно нулю, мы считаем, что результат совпадает с точкой 0, 0. Но для чего нам нужно значение z? Разве точка на экране может обладать координатой z? Нет, не может, однако по координате z можно судить о положении на оси z той грани, которую мы проектируем на плоскость вида. С помощью этой информации мы выберем из множества возможных граней, содержащих точку попадания, ту, что находится ближе остальных.

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

С проверкой принадлежности точки многоугольнику мне пришлось изрядно повозиться. Один из способов выяснить, лежит ли точка внутри многоугольника, - провести линию из данной точки в другую, находящуюся внутри многоугольника, и подсчитать, сколько раз эта линия будет пересекать его стороны. Нечетное количество пересечений означает, что точка находится за пределами многоугольника, как показано на рис. 7-4.

105.jpg

Рис, 7-4. Проверка принадлежности точки многоугольнику

176 ily Глава 7. Проверка попадания


Сначала я поступил, немного глупо и решил написать код проверки самостоятельно. Я провел несколько часов, стараясь учесть все возможные случаи, и довольно близко подошел к ответу, когда здравый смысл все же взял верх. Я подумал, что на эту задача наверняка уже есть ответ и что найти его, вероятно, нетрудно. И оказался прав! Я отыскал нужный код в серии книг (Academic Press) и приготовился вставить его в свою программу, когда меня посетила еще одна мысль. Вдруг такая функция уже имеется в Windows? После быстрого просмотра Microsoft Developer Library я нашел то, что искал, и окончательный вариант функции проверки (которая находится в файле SdMath.cpp) выглядит следующим образом:

BOOL _3dPointInPolygon(POINT* Points, int nPoints,

CPoint pt) {

HRGN hrgn = ::CreatePolygonRgn(Points, nPoints, WINDING);

ASSERT(hrgn) ;

BOOL b = ::PtInRegion(hrgn, pt.x, pt.y);

::DeleteObject(hrgn) ;

return b;

}

Я воспользовался интерфейсом GDI для создания многоугольной области, а затем завершил проверку функцией PtInRegion. Из всего этого я сделал один важный вывод: то, что я не пользуюсь функциями GDI в основной части своего проекта, еще не значит, что я вообще не должен пользоваться ими.

У меня получилось красивое, компактное решение. Я даже не стал возиться с измерением скорости работы, поскольку проверка происходит только в ответ на отдельное действие пользователя и даже низкая скорость проверки не приведет к заметной задержке. Если вам понадобится провести тысячу таких проверок, то, возможно, предложенный вариант решения уступит другим опубликованным алгоритмам.

Последнее замечание: реализованный мною код проверки попадания в грань не учитывает направления, в котором она обращена. Таким образом, теоретически можно попасть в грань, повернутую от пользователя и потому невидимую. Это может случиться тогда, когда за невидимой гранью имеется другая, видимая (если допустить, что до этого было обнаружено попадание в объект), поскольку код выбора, входящий в интерфейс, не возвращает объектов, у которых попадания произошли только в <теневые> грани.

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

void CMainFrame::MakeCurrent(C3dShape* pShape) f

HideSelection() ;

m pCurShape = pShape;

Выделение отдельной грани ''до 177


ShowSelectionf) ;

if (m_pCurShape != NULL) { if (m_iHitFace >= 0) {

Status("Selected: %s (%d @ %3.1f,%3.1f,%3 if)"

ni_pCurShape->GetName () , m_iHitFace, ni_vHitPoint.x, m_vHitPoint.y, m_vHitPoint.z) ;

"PCurShape->SetFaceColor(m_iHitFace, 1, О, О).

J Q -L SG { '

^ Status ("Selected: %s", m_pCurShape->GetMame () ) ;

) else {

Status("No selection");

Определение точки попадания

106.jpg

Рис. 7-5. Проектирование точки попадания на объект

178

Глава/. Проверка попадания


Для этого необходимо взять экранные координаты точки попадания и последовательно преобразовать их в однородный вектор, затем в мировые координаты и снова в локальные координаты объекта. Ниже приведен завершающий фрагмент функции C3dShape::HitTest:

// Вычислить положение точки попадания на грани // Подготовить вектор, описывающий точку экрана // В качестве z используется среднее значение. sv.x = pt.x;

sv.y = pt.y;

sv.z = dHitZ;

sv.w = 1.0;

// Привести к мировым координатам m hr = pIViewport->InverseTransform ( &wv, &sv) ;

ASSERT(SUCCEEDED(m_hr)) ;

// Привести к локальным координатам фрейма m_hr = m_pIFrame->InverseTransform(&lv, &wv);

ASSERT(SUCCEEDED(m_hr));

// Вернуть результат *pvHit == Iv;

Для упрощения кода я воспользовался грубой аппроксимацией значения z для точки на экране. В программе это значение определяется как среднее арифметическое координат z всех вершин, образующих грань проекции. На самом деле такой способ неверен, поскольку в нем никак не учитывается положение точки попадания в многоугольнике. Более корректный способ определения z изображен на рис. 7-6.

р

107.jpg

Рис. 7-6> Вычисление координаты z точки Р

Определение точки попадания ''"Щ 179


Точки А, В и С на рис. 7-6 - вершины грани. Соединим точку А с С, а В - с точкой попадания Р. Отношение длин отрезков АХ и ХС используется для вычисления координаты z точки Х по значениям координат z точек А и С. Отношение длин отрезков РВ и ХВ используется для вычисления координаты z точки Р по значениям координат z точек В и X. Оставляю вам завершить рассуждение в качестве домашнего задания.

В приложении Select имеется команда меню, которая показывает положение точки попадания на объекте (View Ѓ Hit Point). Соответствующий фрагмент кода, расположенный в конце функции CMainFrame-:ShowSelection, создает конус и присоединяет его вершину к точке попадания, при этом ориентация конуса задается по нормали к выделенной грани:

// Получить точку попадания на фигуре

// и перейти от локальных координат к мировым

C3dVector vh = m pCurShape->Transform(m vHitPoint);

// Определить направление нормали к грани ASSERT(m_pCurShape) ;

C3dVector vn = m_pCurShape->GetFaceNormal (m iHitFace);

// Изменить длину нормали, прибавить нормаль к точке // попадания и преобразовать в мировые координаты C3dVector vx = vn * 0.5 + m vHitPoint;

vx = m pCurShape->Transform (vx) ;

// Направить вершину конуса в точку попадания m_pHitPtr = new C3dShape;

m_pHitPtr->CreateCone (vh.x, vh.y, vh.z, 0, FALSE, vx.x, vx.y, vx.z, 0.1, TRUE);

// Присоединить конус к фигуре m_pCurShape->AddChild(m_pHitPtr) ;

}

}

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

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

Проверка попадания на практике

Чтобы показать, как проверка попадания используется на практике, я создал приложение Blobs, в котором можно нарисовать на экране потрясающее космичес-

180 ЦУ Глава 7. Проверка попадания


108.jpg

Рис. 7-7. Конус, показывающий положение точки попадания на объекте

кое существо, наподобие изображенного на рис. 7-8 (более качественная иллюстрация из приложения Blobs приведена на цветной вкладке).

109.jpg

Рис. 7-8. Приложение Blobs

Приложение добавляет новое <пятно> к объекту, в точке где вы щелкаете мышью. Пятна на самом деле являются сферами, состоящими из четырех полос;

даже при небольшом количестве граней такая сфера выглядит неплохо. Чтобы создать это приложение, я взял пример Select, удалил все лишние команды меню

181

Проверка попадания на практике


и изменил уведомляющую функцию, чтобы она добавляла к макету новые пятна. Новая функция выглядит следующим образом:

void CMainFrame::OnSelChange(C3dShape* pShape, CPoint pt,

void* pArg) {

// Получить указатель на объект класса

CMainFrame* pThis = (CMainFrame*) pArg;

ASSERT(pThis);

ASSERT(pThis->IsKindOf (RUNTIME_CLASS(CMainFrame))) ;

if (pShape) {

// Определить, в какую грань пришлось попадание C3dViewport* pViewport =

pThis->m_wnd3d.GetStage () ->GetViewport () ;

int iFace;

C3dVector vHit;

if (pShape->HitTest (pt, pViewport, &iFace, &vHit) ) ( pThis->AddBlob (pShape, vHit) ;

}

l

}

Как видно из листинга, после определения точки попадания вызывается функция AddBlob, которая присоединяет к фигуре новое пятно:

void CMainFrame::AddBlob(C3dShape* pShape, C3dVector& vHit) {

// Определить точку попадания

// и перейти от локальных координат к мировым

ASSERT(pShape) ;

C3dVector vh = pShape->Transform (vHit) ;

// Создать новое пятно C3dShape* pBlob = new C3dShape;

pBlob->CreateSphere (0.5, 4);

// Установить его центр в точке попадания pBlob->SetPosition(vh) ;

// Присоединить пятно к фигуре pShape->AddChild (pBlob) ;

// Включить новое пятно в список фигур,

// чтобы можно было проверять попадание в него

m_pScene->m_ShapeList. Append (pBlob) ;

}

182 Уу Глава 7. Проверка попадания


Координаты точки попадания приводятся к мировым координатам. Мы создаем новое пятно, задаем его положение и присоединяем к текущей фигуре. Обратите внимание на то, что новый объект (пятно) присоединяется к списку фигур, тем самым мы обеспечиваем его удаление при уничтожении всего макета. Помните, что для правильной работы проверки попаданий нельзя удалять использованные объекты C++.

Предлагаю выполнить небольшое упражнение. Посмотрите на исходный текст функции AddBlob. Действительно ли необходимо приводить точку попадания к мировым координатам? Можно ли добиться того же результата, не выполняя этого преобразования? Попробуйте модифицировать программу и посмотрите, будет ли она работать.

Итоги

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

Далее..