Войти

Заметки велосипедиста

Блог

2D коллизии. Функция. Итог.
"Магия" описанной ранее функции оказалась бесполезной. Работает не так, как хотелось бы. Решения есть проще...
Зато она позволяла рисовать красивые звёзды

Ссылка
3 дек. 2012

2D коллизии. Функция
Немного поразмыслив и поиследовав, пришел к заключению, что функцию хакать не надо. Во-первых, это усложнит её, во-вторых, декомпозиция выпуклых объектов тем хороша, что уменьшит количество операций для определения местоположения точки. Но и декомпозицию я решил отложить в ящик, ибо там есть некоторые подводные камни, с которыми надо разобраться.
Текущая реализация принимает на вход многогранник, заданный своими вершинами с обходом против часовой стрелки и, собственно, точку, для которой необходимо посчитать значение. На выходе может быть два случая: 0 - значит точка не принадлежит фигуре, > 0 - значит точка принадлежит фигуре. При это, градиент направлен в сторону ближайшей грани. Возможно, потом я немного её изменю и она будет возвращать точное расстояние до этой грани.
double depth(PointF[] figure, PointF point)
        {
            double r = double.PositiveInfinity;
            PointF p0 = figure[figure.Length - 1];
            PointF p1 = figure[0];
            PointF p2;
            float vx, vy, vx0, vy0, vx1, vy1;
            double d0, d1, nx, ny;
            for (int i = 0; i < figure.Length; i++)
            {
                p2 = figure[(i + 1) % figure.Length];
                vx = point.X - p1.X;
                vy = point.Y - p1.Y;
                vx0 = p0.X - p1.X;
                vy0 = p0.Y - p1.Y;
                vx1 = p2.X - p1.X;
                vy1 = p2.Y - p1.Y;
                p0 = p1;
                p1 = p2;
                d0 = Math.Sqrt(sqr(vx0) + sqr(vy0));
                d1 = Math.Sqrt(sqr(vx1) + sqr(vy1));
                nx = (vx * vy1 - vy * vx1) / d1;
                ny = (vy * vx0 - vx * vy0) / d0;
                if (nx < 0.0 || ny < 0.0)
                {
                    r = 0.0;
                    break;
                }
                r = Math.Min(r, (nx + ny) / Math.Sqrt(sqr(nx) + sqr(ny)));
            }
            return r;
        }

Ссылка
3 дек. 2012

2D коллизии
Два дня ломал голову над тем, как проще и эффективнее реализовать обнаружение столкновений объектов на плоскости. Возможно, кому то покажется это странным, ведь есть уже гора готовых решений... Но я лёгкий путей никогда не искал.
Под конец второго дня придумал таки странную штуку. По трудоёмкости сравнима с построением AABB, если не считать 3~4 (по вкусу) вычислений квадратного корня. Пока-что прекрасно работает с выпуклой геометрией, но кажется мне, что один маленький хак может расширить "сферу влияния".

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

Pen p = new Pen(Color.White);
                PointF[] ps = figures[0];
                float x = 0;
                for (; x < ClientSize.Width; x++)
                {
                    for (float y = 0; y < ClientSize.Height; y++)
                    {
                        double w = 0.0;
                        for (int i = 0; i < ps.Length; i++)
                        {
                            PointF p0 = ps[(ps.Length + i - 1) % ps.Length];
                            PointF p1 = ps[i];
                            PointF p2 = ps[(i + 1) % ps.Length];
                            float vx = x - p1.X;
                            float vy = y - p1.Y;
                            float vx0 = p0.X - p1.X;
                            float vy0 = p0.Y - p1.Y;
                            float vx1 = p2.X - p1.X;
                            float vy1 = p2.Y - p1.Y;
                            double d = Math.Sqrt(sqr(vx) + sqr(vy));
                            double d0 = Math.Sqrt(sqr(vx0) + sqr(vy0));
                            double d1 = Math.Sqrt(sqr(vx1) + sqr(vy1));
                            double nx = (vx * vy1 - vy * vx1) / (d1 * d);
                            double ny = (vy * vx0 - vx * vy0) / (d0 * d);        
                            if (nx < 0.0 || ny < 0.0)
                            {
                                w = 0.0;
                                break;
                            }
                            d = Math.Sqrt(sqr(nx) + sqr(ny));                    
                            w += (nx + ny) / d;
                        }
                        w /= ps.Length;
                        w *= 110;
                        if (w >= 0.0)
                        {
                            if (w > 255.0)
                                w = 255.0;
                            p.Color = Color.FromArgb((int)(w), (int)(w), (int)(w));
                            gbuf.Graphics.DrawLine(p, x, y, x + 1, y);
                        }
                    }
                }
                p.Dispose();

Ссылка
2 дек. 2012