int QDockWidgetLayout::titleHeight() const
{
    QDockWidget *q = qobject_cast<QDockWidget*>(parentWidget());

    if (QWidget *title = widget(TitleBar))
        return perp(verticalTitleBar, title->sizeHint());

    QSize closeSize(0, 0);
    QSize floatSize(0, 0);
    if (QLayoutItem *item = item_list[CloseButton])
        closeSize = item->widget()->sizeHint();
    if (QLayoutItem *item = item_list[FloatButton])
        floatSize = item->widget()->sizeHint();

    int buttonHeight = qMax(perp(verticalTitleBar, closeSize),
                            perp(verticalTitleBar, floatSize));

    QFontMetrics titleFontMetrics = q->fontMetrics();
#ifdef Q_WS_MAC
    if (qobject_cast<QMacStyle *>(q->style())) {
        extern QHash<QByteArray, QFont> *qt_app_fonts_hash(); // qapplication.cpp
        QFont font = qt_app_fonts_hash()->value("QToolButton", q->font());
        titleFontMetrics = QFontMetrics(font);
    }
#endif

    int mw = q->style()->pixelMetric(QStyle::PM_DockWidgetTitleMargin, 0, q);

    return qMax(buttonHeight + 2, titleFontMetrics.lineSpacing() + 2*mw);
}

int QDockWidgetLayout::titleHeight() const
{
    QDockWidget *q = qobject_cast<QDockWidget*>(parentWidget());

    if (QWidget *title = widgetForRole(TitleBar))
        return perp(verticalTitleBar, title->sizeHint());

    QSize closeSize(0, 0);
    QSize floatSize(0, 0);
    if (QLayoutItem *item = item_list[CloseButton])
        closeSize = item->widget()->sizeHint();
    if (QLayoutItem *item = item_list[FloatButton])
        floatSize = item->widget()->sizeHint();

    int buttonHeight = qMax(perp(verticalTitleBar, closeSize),
                            perp(verticalTitleBar, floatSize));

    QFontMetrics titleFontMetrics = q->fontMetrics();
#ifdef Q_WS_MAC
    if (qobject_cast<QMacStyle *>(q->style())) {
        //### this breaks on proxy styles.  (But is this code still called?)
        QFont font = qt_app_fonts_hash()->value("QToolButton", q->font());
        titleFontMetrics = QFontMetrics(font);
    }
#endif

    int mw = q->style()->pixelMetric(QStyle::PM_DockWidgetTitleMargin, 0, q);

    return qMax(buttonHeight + 2, titleFontMetrics.height() + 2*mw);
}

void addPolygonPolylinePoint(Line& line,
    const glm::vec3 curr,
    const glm::vec3 next,
    const glm::vec3 last,
    const float extrude,
    size_t lineDataSize,
    size_t i,
    bool forward)
{
    glm::vec3 n0 = perp(curr - last);
    glm::vec3 n1 = perp(next - curr);
    bool right = glm::cross(n1, n0).z > 0.0;

    if ((i == 1 && forward) || (i == lineDataSize - 2 && !forward)) {
        line.push_back(last + n0 * extrude);
        line.push_back(last - n0 * extrude);
    }

    if (right) {
        glm::vec3 d0 = glm::normalize(last - curr);
        glm::vec3 d1 = glm::normalize(next - curr);
        glm::vec3 miter = computeMiterVector(d0, d1, n0, n1);
        line.push_back(curr - miter * extrude);
    } else {
        line.push_back(curr - n0 * extrude);
        line.push_back(curr - n1 * extrude);
    }
}

bool Intersect(float2 &point, const Line &line0, const Line &line1)
{
#if 0
	float d = perp(line0.d, line1.d);
	if (d > -0.000000000001f) // Parallel lines
		return false;

	float2 diff = line0.v - line1.v;

	float t = perp(line1.d, diff);

	if (t > 0.0f) // Intersects on the wrong side
		return false;

	point = line0.v + (t / d) * line0.d;
	return true;
#else
	float d = perp(line0.d, line1.d);
	if (fabsf(d) < 0.000000000001f) // Parallel lines
		return false;

	float t = perp(line1.d, line0.v - line1.v) / d;

	if (t < 0.5f) // Intersects on the wrong side
		return false;

	point = line0.v + t * line0.d;
	return true;

#endif
}

	DebugDraw::DebugDraw(const Collider &coll)
	{

		isRigidBody = false;

		switch (coll.shape)
		{
			case Collider::e_AABB:
			{
				Vertex vertices[] = { Vertex(coll.aabb.max, SHAPECOLOR),
									  Vertex(Vector2{ coll.aabb.min.x, coll.aabb.max.y }, SHAPECOLOR),
									  Vertex(coll.aabb.min, SHAPECOLOR),
									  Vertex(Vector2{ coll.aabb.max.x, coll.aabb.min.y }, SHAPECOLOR) };
				mesh = new Mesh(vertices, 4);
				break;
			}
			case Collider::e_CIRCLE:
			{
				int step = 36;
				
				std::vector<Vertex> vertices;

				float anglePerStep = DEG2RAD(360.0f / step);

				for (unsigned i = 0; i < step; ++i)
					vertices.push_back(Vertex{ Vector2{coll.circle.position.x + cosf(i * anglePerStep) * coll.circle.radius,
													   coll.circle.position.y + sinf(i * anglePerStep) * coll.circle.radius},Vector4{(float)i / step, ((float)i+3) / step * 2, ((float)i + 8) / step * 3 , 1 } });

				mesh = new Mesh(&vertices[0], step);
				break;
			}
			case Collider::e_RAY:
			{
				Vertex vertices[] = { Vertex(coll.ray.position, SHAPECOLOR),
									  Vertex(coll.ray.position +
											(coll.ray.direction *
											 coll.ray.length) , SHAPECOLOR) };
				mesh = new Mesh(vertices, 2);
				break;
			}
			case Collider::e_PLANE:
			{
				Vertex vertices[] = { Vertex(coll.plane.position + (perp(coll.plane.normal) * 30), SHAPECOLOR),
									  Vertex(coll.plane.position - (perp(coll.plane.normal) * 30), SHAPECOLOR) };
				mesh = new Mesh(vertices, 2);
				break;
			}
			case Collider::e_CONVEX:
			{
				std::vector<Vertex> vertices;
			
				for (unsigned i = 0; i < coll.chull.size; ++i)
					vertices.push_back(Vertex{ coll.chull.verts[i], SHAPECOLOR });

				mesh = new Mesh(&vertices[0], coll.chull.size);
				break;
			}
		}
	}

Point Line::intersect(const Line& o, float& t, float& s) const{
  Vector u = d;
  Vector v = o.d;
  Vector w = Vector(p - o.p);
  Vector vp = perp(v);
  Vector up = perp(u);
  t = -vp.dot(w) / vp.dot(u);
  s = up.dot(w) / up.dot(v);
  return eval(t);
}

bool IntersectNoParallelCheck(float2 &point, const Line &line0, const Line &line1)
{
	float d = perp(line0.d, line1.d);
	float t = perp(line1.d, line0.v - line1.v) / d;

	if (t < 0.5f) // Intersects on the wrong side
		return false;

	point = line0.v + t * line0.d;
	return true;
}

/* Separate Axis Theorem test - project both polygon's
   vertices onto all axes defined by edges the polygons
   and if there is a gap between the polygons in any
   projection then they do not overlap */
static int sat(polygon_t a, polygon_t b) {
    int i;
    for (i = 0; i < a.n; i++) {
        vector_t axis = perp(direction(vertex(a, i), vertex(a, i + 1)));
        range_t ap = project(a, axis), bp = project(b, axis);
        if (!overlap(ap, bp)) return 0;
    }
    for (i = 0; i < b.n; i++) {
        vector_t axis = perp(direction(vertex(b, i), vertex(b, i + 1)));
        range_t ap = project(a, axis), bp = project(b, axis);
        if (!overlap(ap, bp)) return 0;
    }
    return 1;
}

CollisionData iTest_data(const Ray2D &ac, const Plane2D &bc)
{
    CollisionData cd = { 0 };
    float r = mag(bc.normal * (ac.position - bc.position) / -(bc.normal * ac.direction));
    if (r <= 0 && r <= ac.length) cd = { r, perp(bc.normal) };
    return cd;
}

// return true if the polygon is couterclockwise ordered
bool glc::isCounterclockwiseOrdered(const QList<GLC_Point2d>& polygon)
{
	const int size= polygon.size();
	int j0= 0;
	int j1= size - 1;
	// test segment <polygon[i0], polygon[i1]> to see if it is a diagonal
	while (j0 < size)
	{
		GLC_Vector2d perp((polygon[j0] - polygon[j1]).perp());
		int j2= 0;
		int j3= size - 1;
		bool isIntersect= false;
		// Application of perp vector
		GLC_Point2d moy((polygon[j0] + polygon[j1]) * 0.5);
		while (j2 < size && !isIntersect)
		{
			if(j2 != j0 && j3 != j1)
			{
				if (isIntersectedRaySegment(moy, (perp + moy), polygon[j2], polygon[j3]))
					isIntersect= true;
			}
			j3= j2;
			++j2;
		}
		if(!isIntersect) return false;
		j1= j0;
		++j0;
	}

	return true;

}

void draw_arrow2d(const Vec2f& start, const Vec2f& end, float arrow_head_len)
{
   Vec2f direction = end - start;

   Vec2f dir_norm = direction;

   //TODO Possibly automatically scale arrowhead length based on vector magnitude
   if(dir_norm.norm() < 1e-14)
      return;

   dir_norm.normalize();
   Vec2f perp(dir_norm[1],-dir_norm[0]);

   Vec2f tip_left = end + arrow_head_len/(float)sqrt(2.0)*(-dir_norm + perp);
   Vec2f tip_right = end + arrow_head_len/(float)sqrt(2.0)*(-dir_norm - perp);

   glBegin(GL_LINES);
   glVertex2f(start[0], start[1]);
   glVertex2f(end[0], end[1]);
   glVertex2f(end[0], end[1]);
   glVertex2f(tip_left[0], tip_left[1]);
   glVertex2f(end[0], end[1]);
   glVertex2f(tip_right[0], tip_right[1]);
   glEnd();

}

void CCSBot::Panic(CBasePlayer *pEnemy)
{
	if (IsSurprised())
		return;

	Vector2D dir(BotCOS(pev->v_angle.y), BotSIN(pev->v_angle.y));
	Vector2D perp(-dir.y, dir.x);
	Vector spot;

	if (GetProfile()->GetSkill() >= 0.5f)
	{
		Vector2D toEnemy = (pEnemy->pev->origin - pev->origin).Make2D();
		toEnemy.NormalizeInPlace();

		float along = DotProduct(toEnemy, dir);

		float c45 = 0.7071f;
		float size = 100.0f;

		real_t shift = RANDOM_FLOAT(-75.0, 75.0);

		if (along > c45)
		{
			spot.x = pev->origin.x + dir.x * size + perp.x * shift;
			spot.y = pev->origin.y + dir.y * size + perp.y * shift;
		}
		else if (along < -c45)
		{
			spot.x = pev->origin.x - dir.x * size + perp.x * shift;
			spot.y = pev->origin.y - dir.y * size + perp.y * shift;
		}
		else if (DotProduct(toEnemy, perp) > 0.0)
		{
			spot.x = pev->origin.x + perp.x * size + dir.x * shift;
			spot.y = pev->origin.y + perp.y * size + dir.y * shift;
		}
		else
		{
			spot.x = pev->origin.x - perp.x * size + dir.x * shift;
			spot.y = pev->origin.y - perp.y * size + dir.y * shift;
		}
	}
	else
	{
		const float offset = 200.0f;
		real_t side = RANDOM_FLOAT(-offset, offset) * 2.0f;

		spot.x = pev->origin.x - dir.x * offset + perp.x * side;
		spot.y = pev->origin.y - dir.y * offset + perp.y * side;
	}

	spot.z = pev->origin.z + RANDOM_FLOAT(-50.0, 50.0);

	// we are stunned for a moment
	m_surpriseDelay = RANDOM_FLOAT(0.1, 0.2);
	m_surpriseTimestamp = gpGlobals->time;

	SetLookAt("Panic", &spot, PRIORITY_HIGH, 0, 0, 5.0);
	PrintIfWatched("Aaaah!\n");
}

// Pick the best support neighbor along n
// It's critical that this function return an array where the vertices
// are in the proper clockwise order
std::array<vec2, 2> OBB::GetSupportNeighbor(vec2 n, int idx) const {
	std::array<vec2, 2> ret;

	vec2 vb = GetVert(idx);
	vec2 va = GetVert(idx - 1);
	vec2 vc = GetVert(idx + 1);

	vec2 nab = glm::normalize(perp(vb - va));
	vec2 nbc = glm::normalize(perp(vc - vb));
	float d1 = glm::dot(nab, n);
	float d2 = glm::dot(nbc, n);

	if (d1 > d2)
		return{ { va, vb } };
	return{ { vb, vc } };
}

bool intersect2D_2Segments(Segment s1,Segment s2)//求线的交点
{
    Vector  u,v,w;
    u.x= s1.p2.x-s1.p1.x;
    u.y= s1.p2.y-s1.p1.y;
    v.x= s2.p2.x-s2.p1.x;
    v.y= s2.p2.y-s2.p1.y;
    w.x= s1.p1.x-s2.p1.x;
    w.y= s1.p1.y-s2.p1.y;
    double  D = perp(v,u);
    if (fabs(D) < SMALL_NUM)// S1 and S2 are parallel
            return 0;               // they are NOT collinear
    double sI=perp(w,v)/D;
    I0->x=s1.p1.x+u.x*sI;
    I0->y=s1.p1.y+u.y*sI;
    if(on_segment(s1,*I0)&&on_segment(s2,*I0)) return 1;//判断交点是否在两条线上
    else return 0;
}

  inline bool intersect2dSegPoly(Vec2r* seg,
				 Vec2r* poly,
				 unsigned n) {
    if (seg[0] == seg[1])
      return false;

    real  tE = 0;             // the maximum entering segment parameter
    real  tL = 1;             // the minimum leaving segment parameter
    real  t, N, D;            // intersect parameter t = N / D
    Vec2r dseg;                // the segment direction vector
    dseg = seg[1] - seg[0];
    Vec2r e;                   // edge vector

    for (unsigned i = 0; i < n; i++) { // process polygon edge poly[i]poly[i+1]
      e = poly[i+1] - poly[i];
      N = perp(e, seg[0] - poly[i]);
      D = -perp(e, dseg);
      if (fabs(D) < M_EPSILON) {
	if (N < 0)
	  return false;
	else
	  continue;
      }

      t = N / D;
      if (D < 0) {       // segment seg is entering across this edge
	if (t > tE) {    // new max tE
	  tE = t;
	  if (tE > tL)   // seg enters after leaving polygon
	    return false;
	}
      }
      else {             // segment seg is leaving across this edge
	if (t < tL) {    // new min tL
	  tL = t;
	  if (tL < tE)   // seg leaves before entering polygon
	    return false;
	}
      }
    }

    // tE <= tL implies that there is a valid intersection subsegment
    return true;
  }

/**
 * Influence my motion to flock with other nearby fish
 * 'amount' ranges from zero to one, representing the amount of flocking influence allowed
 * If 'other' is NULL, flock to the center of the pool.
 */
void CFish::FlockTo( CFish *other, float amount )
{
	// allow fish to disperse a bit at round start
	if (!m_disperseTimer.IsElapsed())
		return;

	const float maxRange = (other) ? 100.0f : 300.0f;

	Vector to = (other) ? (other->GetAbsOrigin() - GetAbsOrigin()) : (m_pool->GetAbsOrigin() - GetAbsOrigin());
	float range = to.NormalizeInPlace();

	if (range > maxRange)
		return;

	// if they are close and we are moving together, avoid them
	const float avoidRange = 25.0f;
	if (other && range < avoidRange)
	{
		// compute their relative velocity to us
		Vector relVel = other->GetAbsVelocity() - GetAbsVelocity();

		if (DotProduct( to, relVel ) < 0.0f)
		{
			const float avoidPower = 5.0f;

			// their comin' right at us! - avoid
			if (DotProduct( m_perp, to ) > 0.0f)
			{
				m_angleChange -= avoidPower * (1.0f - range/avoidRange);
			}
			else
			{
				m_angleChange += avoidPower * (1.0f - range/avoidRange);
			}
			return;
		}
	}

	// turn is 2 if 'other' is behind us, 1 perpendicular, and 0 straight ahead
	float turn = 1.0f + DotProduct( -m_forward, to );

	Vector perp( -m_forward.y, m_forward.x, 0.0f );
	float side = (DotProduct( perp, to ) > 1.0f) ? 1.0f : -1.0f;

	if (turn > 1.0f)
	{
		// always turn one way to avoid dithering if many fish are behind us
		side = (m_turnClockwise) ? 1.0f : -1.0f;
	}

	float power = 1.0f - (range / maxRange);

	const float flockInfluence = 0.7f; // 0.3f;	// 0.3
	m_angleChange += amount * flockInfluence * power * side * turn;
}

// untested - algorithm sound but could be typos
CollisionData sat_hull(const ConvexHull &A, const ConvexHull &B)
{
    CollisionData cd = { false, INFINITY }; // setup return value

    std::vector<vec2> axes;
    axes.reserve(A.verts.size() + B.verts.size());
           
    for (int i = 0; i < A.verts.size(); ++i)
        axes.push_back(perp(normal(A.verts[i] - A.verts[(i + 1) % A.verts.size()])));

    for (int i = 0; i < B.verts.size(); ++i)
        axes.push_back(perp(normal(B.verts[i] - B.verts[(i + 1) % B.verts.size()])));

    for (int j = 0; j < axes.size(); ++j)
    {
        float amin = INFINITY, amax = -INFINITY;
        float bmin = INFINITY, bmax = -INFINITY;

        for (int i = 0; i < A.verts.size(); ++i)
        {
            float pp = dot(axes[j],A.verts[i]);
            amin = fminf(pp, amin);
            amax = fminf(pp, amax);
        }

        for (int i = 0; i < B.verts.size(); ++i)
        {
            float pp = dot(axes[j], B.verts[i]);            
            amin = fminf(pp, amin);
            amax = fminf(pp, amax);
        }

        float pdepth = fminf(amax - bmin, bmax - amin);

        if (pdepth < cd.PenetrationDepth)
        {
            cd = { pdepth < 0, pdepth, axes[j] };
            if (pdepth < 0) return cd;
        }  
    }
    return cd;
}

//
// stoplights and stopsigns
//
void vtRoadMap3d::GenerateSigns(vtLodGrid *pLodGrid)
{
	if (!pLodGrid)
		return;

	vtContentManager3d &con = vtGetContent();
	osg::Node *stopsign = con.CreateNodeFromItemname("American Stopsign");
	osg::Node *stoplight = con.CreateNodeFromItemname("Stoplight (right)");

	if (!stopsign || !stoplight)
	{
		VTLOG("Couldn't find stopsign and stoplight.\n");
		return;
	}
	for (NodeGeom *pN = GetFirstNode(); pN; pN = pN->GetNext())
	{
		for (int r = 0; r < pN->NumLinks(); r++)
		{
			osg::Node *shape = NULL;
			if (pN->GetIntersectType(r) == IT_STOPSIGN && stopsign)
			{
				shape = (osg::Node *) stopsign->clone(osg::CopyOp::SHALLOW_COPY);
			}
			if (pN->GetIntersectType(r) == IT_LIGHT && stoplight)
			{
				shape = (osg::Node *) stoplight->clone(osg::CopyOp::SHALLOW_COPY);
			}
			if (!shape) continue;

			vtTransform *trans = new vtTransform;
			trans->addChild(shape);

			LinkGeom *link = pN->GetLink(r);
			FPoint3 unit = pN->GetUnitLinkVector(r);
			FPoint3 perp(unit.z, unit.y, -unit.x);
			FPoint3 offset;

			// Turn the sign (yaw) to face the oncoming traffic
			trans->RotateLocal(FPoint3(0,1,0), pN->GetLinkAngle(r) + PID2f);

			if (pN->GetIntersectType(r) == IT_STOPSIGN)
			{
				offset = pN->m_p3 + (unit * 6.0f) + (perp * (link->m_fRightWidth));
			}
			if (pN->GetIntersectType(r) == IT_LIGHT)
			{
				offset = pN->m_p3 - (unit * 6.0f) + (perp * (link->m_fRightWidth));
			}
			trans->Translate(offset);
			pLodGrid->AddToGrid(trans);
		}
	}
}

// Return true if we can see any part of the player
// Check parts in order of importance. Return the first part seen in "visParts" if it is non-NULL.
bool CCSBot::__MAKE_VHOOK(IsVisible)(CBasePlayer *player, bool testFOV, unsigned char *visParts) const
{
	Vector spot = player->pev->origin;
	VisiblePartType testVisParts = NONE;

	// finish chest check
	if (IsVisible(&spot, testFOV))
		testVisParts |= CHEST;

	// check top of head
	spot = spot + Vector(0, 0, 25.0f);

	if (IsVisible(&spot, testFOV))
		testVisParts |= HEAD;

	// check feet
	const float standFeet = 34.0f;
	const float crouchFeet = 14.0f;

	if (player->pev->flags & FL_DUCKING)
		spot.z = player->pev->origin.z - crouchFeet;
	else
		spot.z = player->pev->origin.z - standFeet;

	// check feet
	if (IsVisible(&spot, testFOV))
		testVisParts |= FEET;

	// check "edges"
	const float edgeOffset = 13.0f;
	Vector2D dir = (player->pev->origin - pev->origin).Make2D();
	dir.NormalizeInPlace();

	Vector2D perp(-dir.y, dir.x);

	spot = player->pev->origin + Vector(perp.x * edgeOffset, perp.y * edgeOffset, 0);

	if (IsVisible(&spot, testFOV))
		testVisParts |= LEFT_SIDE;

	spot = player->pev->origin - Vector(perp.x * edgeOffset, perp.y * edgeOffset, 0);

	if (IsVisible(&spot, testFOV))
		testVisParts |= RIGHT_SIDE;

	if (visParts != NULL)
		*visParts = testVisParts;

	if (testVisParts != NONE)
		return true;

	return false;
}

    //! \brief Attempt to create the simplex
    //! \details If the simplex cannot be verified the search direction and
    //!          simplex will be updated for the next iteration.
    //! \returns True iff simplex contains the origin
    bool do_simplex (void)
    {
        const auto& a = simplex[count - 1];
        auto ao = -a;

        if (count == 3)
        {
            const auto& b = simplex[1];
            const auto& c = simplex[0];
            auto ab = b - a;
            auto ac = c - a;

            auto ac_perp = ac.perp_ccw() * math::perp_dot(ac, ab);
            if (ac_perp.dot(ao) > 0)
            {
                // If the edge AC normal has the same direction as the origin
                // we remove point B and set the direction to the normal.
                simplex[1] = a;
                count--;

                d = ac_perp;
            }
            else
            {
                auto ab_perp = ab.perp_ccw() * math::perp_dot(ab, ac);
                if (ab_perp.dot(ao) > 0)
                {
                    // If the edge AB normal has the same direction as the origin
                    // we remove point C and set the direction to the normal.
                    simplex[0] = b;
                    simplex[1] = a;
                    count--;

                    d = ab_perp;
                }
                else
                {
                    // The origin lies inside both the AB and AC edge
                    return true;
                }
            }
        }
        else
        {
            const auto& b = simplex[0];
            auto ab = b - a;

            d = ab.perp() * math::perp_dot(ab, ao);
        }

        return false;
    }