Здравствуйте, Glagolev, Вы писали:
Задача не самая тривиальная, в общем случае
Практически — лучше взять уже готовый движок.
Начать можно отсюда:
http://code.google.com/p/physics2d/
Здравствуйте, NikeByNike, Вы писали:
NBN>Задача не самая тривиальная, в общем случае
NBN>Практически — лучше взять уже готовый движок.
NBN>Начать можно отсюда: http://code.google.com/p/physics2d/
Спасибо, я обязательно посижжу над его кодом в поисках решения (правда пишу не на си++), но всё-же был бы рад услашать конкретные предложения/алгоритмы/идеи/наводки по решению задачи.
Здравствуйте, Glagolev, Вы писали:
G>Спасибо, я обязательно посижжу над его кодом в поисках решения (правда пишу не на си++), но всё-же был бы рад услашать конкретные предложения/алгоритмы/идеи/наводки по решению задачи.
Подсмотреть можешь
здесь... << RSDN@Home 1.1.3 stable >>
Здравствуйте, o.kostya, Вы писали:
OK>Подсмотреть можешь здесь
Ты пробовал нарисовать там невыпуклую фигуру? Если нет, то попробуй, она просто её не сделает, т.к. расщитать пересечение выпуклого многоугольника очень просто. У меня задача иного плана, да и на плоскости разбивать я бы тоже не хотел.
Здравствуйте, Glagolev, Вы писали:
G>Есть 2 объекта:
G>1. Геометрическая фигура, скажем прямоугольник, который задан 4-мя точками.
G>2. Даже не фигура а набор точек, т.е. 2-х мерная матрица поверхности, на которой предположим единицей задан твердый участок, а нулями — пустота. И образовать "это" может что угодно.
G>Нужно расщитать поведение 1-й фигуры при столкновении об 2-ю, причем желательно более или менее реалистичное столкновение (или хоть образование грамотного вектора выталкивания). Так что она не просто упрется, а начнет скользить, если есть возможность, т.е. узнать силу кручения конечно желательно, но не критично.
G>Как вариант я думал о разбиении этого чуда на геометрические примитивы, но уж больно затратная операция выходит. Очень был бы благодарен даже за подсказку в каком направлении думать.
G>Спасибо.
В свое время я делал игрушку и написал статью на этот счет:
http://gamedev.ru/articles/?id=70124
Здравствуйте, Glagolev, Вы писали:
G>2. Даже не фигура а набор точек, т.е. 2-х мерная матрица поверхности, на которой предположим единицей задан твердый участок, а нулями — пустота. И образовать "это" может что угодно.
G>Нужно расщитать поведение 1-й фигуры при столкновении об 2-ю, причем желательно более или менее реалистичное столкновение (или хоть образование грамотного вектора выталкивания). Так что она не просто упрется, а начнет скользить, если есть возможность, т.е. узнать силу кручения конечно желательно, но не критично.
У этой задачи есть две подзадачи. Первая — поиск столкновений и векторов нормалей этих столкновений, а вторая — расчет реакции тел на столкновения.
Первая часть тебе нужно столкновения не геометрических фигур, что обычно делают в физических движках, а попиксельное. Это не так уж сложно реализовать и не так уж медленно работает. Общая идея, вначале смотришь, пересекаются ли OOB (описывающие прямоугольники вращающиеся вместе с телом, т.е. для спрайта — это просто прямоугольник который получиться если картинку залить одним цветом) спрайтов. Потом в области пересечения OOB проходишься по всем "единицам" одного тела и смотришь нет ли там "единицы" другого тела. Лучше, если разрешение карт столкновений поменьше, тогда и проверять точек можно поменьше.
Вот код, он конечно содержит всякую специфику, но алгоритм из него ясен:
bool Image::CheckCollisions(Rect &pos, Image rImage, Rect &rPos, float * px, float * py)
{
if(!impl_ || !rImage.impl_)
return false;
impl_->MakeCollMap();
rImage.impl_->MakeCollMap();
// Проверяем AAB
Rect const &q1 = pos;
Rect const &q2 = rPos;
float lx1 = q1.v[0].x, lx2 = q1.v[0].x;
float ly1 = q1.v[0].y, ly2 = q1.v[0].y;
float rx1 = q2.v[0].x, rx2 = q2.v[0].x;
float ry1 = q2.v[0].y, ry2 = q2.v[0].y;
for(int i = 1; i < 4; ++i)
{
lx1 = std::min(lx1, q1.v[i].x);
lx2 = std::max(lx2, q1.v[i].x);
ly1 = std::min(ly1, q1.v[i].y);
ly2 = std::max(ly2, q1.v[i].y);
rx1 = std::min(rx1, q2.v[i].x);
rx2 = std::max(rx2, q2.v[i].x);
ry1 = std::min(ry1, q2.v[i].y);
ry2 = std::max(ry2, q2.v[i].y);
}
if(lx1 > rx2 || lx2 < rx1 || ly1 > ry2 || ly2 < ry1)
return false;
// Проходимся по области пересечения AAB, сразу откидывая места, где OOB не пересекаются.
// Наверное это не самое быстрое, но тогда когда писал, написал так и работает вполне сносно
int x1 = int(lx1 > rx1 ? lx1 : rx1);
int x2 = int(lx2 < rx2 ? lx2 : rx2);
int y1 = int(ly1 > ry1 ? ly1 : ry1) + 1;
int y2 = int(ly2 < ry2 ? ly2 : ry2) + 1;
std::vector<bool> &m1 = impl_->record_->collMap_;
int m1W = impl_->record_->collWidth_;
int m1H = impl_->record_->collHeight_;
std::vector<bool> &m2 = rImage.impl_->record_->collMap_;
int m2W = rImage.impl_->record_->collWidth_;
int m2H = rImage.impl_->record_->collHeight_;
int nCollisions = 0;
for(int y = y1; y < y2; y += 3)
{
for(int x = x1; x < x2; x += 3)
{
int tx1 = int(((x - q1.v[0].x) * (q1.v[1].x - q1.v[0].x) +
(y - q1.v[0].y) * (q1.v[1].y - q1.v[0].y)) * m1W / (q1.w_*q1.w_));
if(tx1 < 0 || tx1 >= m1W)
continue;
int ty1 = int(((x - q1.v[0].x) * (q1.v[3].x - q1.v[0].x) +
(y - q1.v[0].y) * (q1.v[3].y - q1.v[0].y)) * m1H / (q1.h_*q1.h_));
if(ty1 < 0 || ty1 >= m1H)
continue;
int tx2 = int(((x - q2.v[0].x) * (q2.v[1].x - q2.v[0].x) +
(y - q2.v[0].y) * (q2.v[1].y - q2.v[0].y)) * m2W / (q2.w_*q2.w_));
if(tx2 < 0 || tx2 >= m2W)
continue;
int ty2 = int(((x - q2.v[0].x) * (q2.v[3].x - q2.v[0].x) +
(y - q2.v[0].y) * (q2.v[3].y - q2.v[0].y)) * m2H / (q2.h_*q2.h_));
if(ty2 < 0 || ty2 >= m2H)
continue;
// здесь находится среднее всех от всех точек пересечения, это не всегда то, что надо.
if(m1[tx1 + ty1 * m1W] && m2[tx2 + ty2 * m2W])
{
if(px)
((*px *= nCollisions) += 1.f * x) /= nCollisions + 1;
if(py)
((*py *= nCollisions) += 1.f * y) /= nCollisions + 1;
++nCollisions;
}
}
}
if(nCollisions)
return true;
return false;
}
Тут нету определения нормалей, мне это было не нужно. Я бы сделал например так, вокруг точки пересечения в небольшом радиусе находил все точки принадлежащие каждому из столкнувшихся тел и направление между средними точками каждого взял бы как нормаль.
Вторая часть задачи имеет несколько разных вариантов решения. Прочитай ссылку, что дал Кровосос, в принципе там много про нахождение столкновений, а про их обработку несколько более сумбурно, но понять можно. Почитай вообще про физические движки.
Мне в свое время хватило куда более простого, но и менее точного алгоритма: как реагирует тело на приложение к нему силы можно узнать из учебника физики. На каждом шаге, в точках столкновения тела действуют друг на друга по нормали к поверхности выталкивая друг друга константной силой...
Мы в своё время к "набору точек, 2-мерная матрица поверхности", т.е. битмапу отдельно извне подрисовывали окантовывающую форму... Так и быстрее работать будет и вообще ИМХО более универсально — можно рисовать на картинке всякие усики и тени — и это не будет автоматически участвовать в коллизиях.
Если всё таки сильно хочеться написать оконтуривалку, можно сделать это как раз во внешнем редакторе ресурсов (или импортировать их из фотошопа/иллюстратора, частенько контура готовые от художников могут валяться там), с возможностью ручной правки.
Евгений.
