앞선 개념

새로운 개념인 Reciprocal Velocity Obstacle(이하 RVO)를 제안함
각 에이전트가 다른 에이전트와 명시적으로 통신하지 않고 독립적으로 움직이는 경우를 고려함

다른 객체들이 유사한 충돌 회피 추론을 암묵적으로 가정함으로써 다른 객체의 반응적 행동을 고려함
정적 장애물과 이동 장애물을 모두 포함하는 인구 밀도가 높은 환경에서 수백 개의 에이전트를 탐색하는 것에 개념을 적용하고, 도전적인 시나리오에서 실시간 및 확장 가능한 성능을 달성한다는 것을 보여줌
사용하는 ORCA 개념의 경우 로보틱스에서 로봇간의 충돌을 막기 위해서도 쓰임

수정하고자 한 것

Velocity Obstacle(VO)에서 발생하는 진동현상을 수정하고자 제작함

핵심 내용

움직이는 장애물들 사이에서의 자연스러운 움직임을 위해 도입된 VO(Velocity Obstacle) 개념의 확장

ORCA(Optimal Reciprocal Collision Avoidance)라는 개념을 도입하여 각 객체간의 속도를 계산한 후 그 책임을 각각 반틈씩 가지게 만들어서 군중의 뭉치는 현상을 줄어들도록 만드는 것

결국 병목 현상(Bottleneck)을 개선하기 위해서 제작

- 민코우스키 합 (민코프스키 덧셈)

기하학에서, 유클리드 공간의 위치벡터 A와 B의 두 집합의 민코스키 합(팽창)은 A에 있는 모든 벡터를 B에 있는 각각의 벡터에 더해서 만들어진다.
 

 
 
민코프스키 덧셈은 장애물 사이로 지나는 모션계획에 사용된다.

추가 참고 자료

실제 작동 RVO2 Library

💡RVOSimulator-> doStep()

doStep을 실행하면 한프레임이 진행된다.

void RVOSimulator::doStep(float powfScalar)
{
    kdTree_->buildAgentTree();

    this->powfScalar = powfScalar;

#ifdef _OPENMP
#pragma omp parallel for
#endif
    for (int i = 0; i < static_cast<int>(agents_.size()); ++i) {
        agents_[i]->computeNeighbors();
        agents_[i]->computeNewVelocity();
        //agents_[i]->computeNewVelocityE();
    }

#ifdef _OPENMP
#pragma omp parallel for
#endif
    for (int i = 0; i < static_cast<int>(agents_.size()); ++i) {
        agents_[i]->update();
    }

    globalTime_ += timeStep_;
}

먼저 kdTree에 대한 정보들을 다시 생성한다.

void KdTree::buildAgentTree()
{
	if (agents_.size() < sim_->agents_.size()) {
		for (size_t i = agents_.size(); i < sim_->agents_.size(); ++i) {
			agents_.push_back(sim_->agents_[i]);
		}

		agentTree_.resize(2 * agents_.size() - 1);
	}

	if (!agents_.empty()) {
		buildAgentTreeRecursive(0, agents_.size(), 0);
	}
}

현재 agent의 수와 시뮬레이션에서 가지고 있는 agent의 수가 변경될 때 (즉, 추가될 때) 새로운 agent를 vector에 추가한다.

그리고 Agent kd-tree를 생성한다.

void KdTree::buildAgentTreeRecursive(size_t begin, size_t end, size_t node)
{
	agentTree_[node].begin = begin;
	agentTree_[node].end = end;
	agentTree_[node].minX = agentTree_[node].maxX = agents_[begin]->position_.x();
	agentTree_[node].minY = agentTree_[node].maxY = agents_[begin]->position_.y();

	for (size_t i = begin + 1; i < end; ++i) {
		agentTree_[node].maxX = std::max(agentTree_[node].maxX, agents_[i]->position_.x());
		agentTree_[node].minX = std::min(agentTree_[node].minX, agents_[i]->position_.x());
		agentTree_[node].maxY = std::max(agentTree_[node].maxY, agents_[i]->position_.y());
		agentTree_[node].minY = std::min(agentTree_[node].minY, agents_[i]->position_.y());
	}

	if (end - begin > MAX_LEAF_SIZE) {
		/* No leaf node. (leaf node : 부모가 없는 최상위 노드) */
		const bool isVertical = (agentTree_[node].maxX - agentTree_[node].minX > agentTree_[node].maxY - agentTree_[node].minY);
		const float splitValue = (isVertical ? 0.5f * (agentTree_[node].maxX + agentTree_[node].minX) : 0.5f * (agentTree_[node].maxY + agentTree_[node].minY));

		size_t left = begin;
		size_t right = end;

		while (left < right) {
			while (left < right && (isVertical ? agents_[left]->position_.x() : agents_[left]->position_.y()) < splitValue) {
				++left;
			}

			while (right > left && (isVertical ? agents_[right - 1]->position_.x() : agents_[right - 1]->position_.y()) >= splitValue) {
				--right;
			}

			if (left < right) {
				std::swap(agents_[left], agents_[right - 1]);
				++left;
				--right;
			}
		}

		if (left == begin) {
			++left;
			++right;
		}

		agentTree_[node].left = node + 1;
		agentTree_[node].right = node + 2 * (left - begin);

		buildAgentTreeRecursive(begin, left, agentTree_[node].left);
		buildAgentTreeRecursive(left, end, agentTree_[node].right);
	}
}

💡Agent -> computeNeighbors()

void Agent::computeNeighbors()
{
	obstacleNeighbors_.clear();
	float rangeSq = sqr(timeHorizonObst_ * maxSpeed_ + radius_);
	sim_->kdTree_->computeObstacleNeighbors(this, rangeSq);

	agentNeighbors_.clear();

	if (maxNeighbors_ > 0) {
		rangeSq = sqr(neighborDist_);
		sim_->kdTree_->computeAgentNeighbors(this, rangeSq);
	}
}

먼저 Agent의 이웃들(나랑 같이 움직이고 있다고 가정하는 Agent들에 대해 계산을 한다.

rangeSq는 속도와 timeHorizonObst(옵션)에 따라 달라지도록 만든 sqr(루트)를 적용한 반지름이다.

해당 변수를 kdTree->computeAgentNeighbors() 함수로 넘겨준다.

이중에 RVO는 Nearest Neighbor 방법을 사용하는듯하다.

computeObstacleNeighbors는 움직이지 않는 방해물을 계산할 때 사용하려고 계산한다.

💡k-d Tree
k차원 공간의 점들을 구조화하는 공간 분할 자료 구조
보통 다차원 공간에서 탐색할 때 사용되는 기법
Range Search, Nearest neighbor 등의 문제에 적용

💡kNN
주어진 Point와 가장 가까운(주어진 set안의) 점을 찾는 것
1. k 이웃의 기준을 정의
2. test 셋의 개별 포인트에 대해서 k 개의 이웃을 찾음
3. 이웃의 output을 가지고 예측값을 생성

void KdTree::computeAgentNeighbors(Agent *agent, float &rangeSq) const
{
    queryAgentTreeRecursive(agent, rangeSq, 0);
}

kd-tree 내에서 위치를 찾아서 insert해준다.

찾은 agentTree가 10개 이하면 그대로 삽입하고, 그렇지 않으면 kd-tree 내에서 위치를 다시 정확하게 탐색한다.

kNN에서 주어진 set이 10개라고 생각하면 된다.

void KdTree::queryAgentTreeRecursive(Agent *agent, float &rangeSq, size_t node) const
{
	//agentTree의 크기가 10보다 작다면 agent의 이웃에 해당 agent를 insert
	if (agentTree_[node].end - agentTree_[node].begin <= MAX_LEAF_SIZE) {
		for (size_t i = agentTree_[node].begin; i < agentTree_[node].end; ++i) {
			agent->insertAgentNeighbor(agents_[i], rangeSq);
		}
	}
	else {
		const float distSqLeft = sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minX - agent->position_.x())) + sqr(std::max(0.0f, agent->position_.x() - agentTree_[agentTree_[node].left].maxX)) + sqr(std::max(0.0f, agentTree_[agentTree_[node].left].minY - agent->position_.y())) + sqr(std::max(0.0f, agent->position_.y() - agentTree_[agentTree_[node].left].maxY));

		const float distSqRight = sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minX - agent->position_.x())) + sqr(std::max(0.0f, agent->position_.x() - agentTree_[agentTree_[node].right].maxX)) + sqr(std::max(0.0f, agentTree_[agentTree_[node].right].minY - agent->position_.y())) + sqr(std::max(0.0f, agent->position_.y() - agentTree_[agentTree_[node].right].maxY));

		if (distSqLeft < distSqRight) {
			if (distSqLeft < rangeSq) {
				queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].left);

				if (distSqRight < rangeSq) {
					queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].right);
				}
			}
		}
		else {
			if (distSqRight < rangeSq) {
				queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].right);

				if (distSqLeft < rangeSq) {
					queryAgentTreeRecursive(agent, rangeSq, agentTree_[node].left);
				}
			}
		}

	}
}

💡Agent -> computeNewVelocity()

주변 이웃을 결정하였으면 새로운 속도를 탐색한다.

새로운 속도를 위해 ORCA 라인을 새롭게 만든다.

행렬식의 절대값은 도형의 면적을 의미한다.

		const Obstacle *obstacle1 = obstacleNeighbors_[i].second;
		const Obstacle *obstacle2 = obstacle1->nextObstacle_;

		const Vector2 relativePosition1 = obstacle1->point_ - position_;
		const Vector2 relativePosition2 = obstacle2->point_ - position_;

		/*
		 * Check if velocity obstacle of obstacle is already taken care of by
		 * previously constructed obstacle ORCA lines.
		 * 장애물의 속도 장애물이 이전에 구축된 장애물 ORCA 라인에 의해 
		 * 이미 처리되었는지 확인합니다.
		 */
		bool alreadyCovered = false;

		for (size_t j = 0; j < orcaLines_.size(); ++j) {
			//det : 행렬식, radius_ : agent의 반지름
			if (det(invTimeHorizonObst * relativePosition1 - orcaLines_[j].point, orcaLines_[j].direction) - invTimeHorizonObst * radius_ >= -RVO_EPSILON 
			&& det(invTimeHorizonObst * relativePosition2 - orcaLines_[j].point, orcaLines_[j].direction) - invTimeHorizonObst * radius_ >=  -RVO_EPSILON) {
				alreadyCovered = true;
				break;
			}
		}

		if (alreadyCovered) {
			continue;
		}

먼저 구축된 장애물 ORCA 라인에 의해 이미 처리되었는지 확인하고, 처리 되었다면 생략한다.

그렇지 않다면 장애물 ORCA 라인을 만든다.

	/* Create obstacle ORCA lines. */
	for (size_t i = 0; i < obstacleNeighbors_.size(); ++i) {
	
		/* Not yet covered. Check for collisions. */

		const float distSq1 = absSq(relativePosition1);
		const float distSq2 = absSq(relativePosition2);

		const float radiusSq = sqr(radius_);

		const Vector2 obstacleVector = obstacle2->point_ - obstacle1->point_;
		const float s = (-relativePosition1 * obstacleVector) / absSq(obstacleVector);
		const float distSqLine = absSq(-relativePosition1 - s * obstacleVector);

		Line line;

		if (s < 0.0f && distSq1 <= radiusSq) {
			/* Collision with left vertex. Ignore if non-convex. */
			if (obstacle1->isConvex_) {
				line.point = Vector2(0.0f, 0.0f);
				line.direction = normalize(Vector2(-relativePosition1.y(), relativePosition1.x()));
				orcaLines_.push_back(line);
			}

			continue;
		}
		else if (s > 1.0f && distSq2 <= radiusSq) {
			/* Collision with right vertex. Ignore if non-convex
			 * or if it will be taken care of by neighoring obstace */
			if (obstacle2->isConvex_ && det(relativePosition2, obstacle2->unitDir_) >= 0.0f) {
				line.point = Vector2(0.0f, 0.0f);
				line.direction = normalize(Vector2(-relativePosition2.y(), relativePosition2.x()));
				orcaLines_.push_back(line);
			}

			continue;
		}
		else if (s >= 0.0f && s < 1.0f && distSqLine <= radiusSq) {
			/* Collision with obstacle segment. */
			line.point = Vector2(0.0f, 0.0f);
			line.direction = -obstacle1->unitDir_;
			orcaLines_.push_back(line);
			continue;
		}

		//아래 코드들 실행
        //...

		/*
		 * No collision.
		 * Compute legs. When obliquely viewed, both legs can come from a single
		 * vertex. Legs extend cut-off line when nonconvex vertex.
		 * 충돌은 없습니다.
		 * leg를 계산하세요. 비스듬히 볼 때, 두 leg는 하나의 꼭짓점에서 나올 수 있습니다. 
		 * leg는 볼록하지 않은 꼭짓점에서 절단선을 연장합니다.
		 */

		Vector2 leftLegDirection, rightLegDirection;

		if (s < 0.0f && distSqLine <= radiusSq) {
			/*
			 * Obstacle viewed obliquely so that left vertex 
			 * defines velocity obstacle.
			 * 왼쪽 꼭짓점이 속도 장애물을 정의하도록 비스듬히 보이는 장애물.
			 */
			if (!obstacle1->isConvex_) {
				/* Ignore obstacle. */
				continue;
			}

			obstacle2 = obstacle1;

			const float leg1 = std::sqrt(distSq1 - radiusSq);
			leftLegDirection = Vector2(relativePosition1.x() * leg1 - relativePosition1.y() * radius_, relativePosition1.x() * radius_ + relativePosition1.y() * leg1) / distSq1;
			rightLegDirection = Vector2(relativePosition1.x() * leg1 + relativePosition1.y() * radius_, -relativePosition1.x() * radius_ + relativePosition1.y() * leg1) / distSq1;
		}
		else if (s > 1.0f && distSqLine <= radiusSq) {
			/*
			 * Obstacle viewed obliquely so that
			 * right vertex defines velocity obstacle.
			 * 오른쪽 꼭짓점이 속도 장애물을 정의하도록 비스듬히 보이는 장애물.
			 */
			if (!obstacle2->isConvex_) {
				/* Ignore obstacle. */
				continue;
			}

			obstacle1 = obstacle2;

			const float leg2 = std::sqrt(distSq2 - radiusSq);
			leftLegDirection = Vector2(relativePosition2.x() * leg2 - relativePosition2.y() * radius_, relativePosition2.x() * radius_ + relativePosition2.y() * leg2) / distSq2;
			rightLegDirection = Vector2(relativePosition2.x() * leg2 + relativePosition2.y() * radius_, -relativePosition2.x() * radius_ + relativePosition2.y() * leg2) / distSq2;
		}
		else {
			/* Usual situation. */
			if (obstacle1->isConvex_) {
				const float leg1 = std::sqrt(distSq1 - radiusSq);
				leftLegDirection = Vector2(relativePosition1.x() * leg1 - relativePosition1.y() * radius_, relativePosition1.x() * radius_ + relativePosition1.y() * leg1) / distSq1;
			}
			else {
				/* Left vertex non-convex; left leg extends cut-off line. */
				leftLegDirection = -obstacle1->unitDir_;
			}

			if (obstacle2->isConvex_) {
				const float leg2 = std::sqrt(distSq2 - radiusSq);
				rightLegDirection = Vector2(relativePosition2.x() * leg2 + relativePosition2.y() * radius_, -relativePosition2.x() * radius_ + relativePosition2.y() * leg2) / distSq2;
			}
			else {
				/* Right vertex non-convex; right leg extends cut-off line. */
				rightLegDirection = obstacle1->unitDir_;
			}
		}

/*
		 * Legs can never point into neighboring edge when convex vertex,
		 * take cutoff-line of neighboring edge instead. If velocity projected on
		 * "foreign" leg, no constraint is added.
		 */

		const Obstacle *const leftNeighbor = obstacle1->prevObstacle_;

		bool isLeftLegForeign = false;
		bool isRightLegForeign = false;

		if (obstacle1->isConvex_ && det(leftLegDirection, -leftNeighbor->unitDir_) >= 0.0f) {
			/* Left leg points into obstacle. */
			leftLegDirection = -leftNeighbor->unitDir_;
			isLeftLegForeign = true;
		}

		if (obstacle2->isConvex_ && det(rightLegDirection, obstacle2->unitDir_) <= 0.0f) {
			/* Right leg points into obstacle. */
			rightLegDirection = obstacle2->unitDir_;
			isRightLegForeign = true;
		}

		/* Compute cut-off centers. */
		const Vector2 leftCutoff = invTimeHorizonObst * (obstacle1->point_ - position_);
		const Vector2 rightCutoff = invTimeHorizonObst * (obstacle2->point_ - position_);
		const Vector2 cutoffVec = rightCutoff - leftCutoff;

		/* Project current velocity on velocity obstacle. */

		/* Check if current velocity is projected on cutoff circles. */
		const float t = (obstacle1 == obstacle2 ? 0.5f : ((velocity_ - leftCutoff) * cutoffVec) / absSq(cutoffVec));
		const float tLeft = ((velocity_ - leftCutoff) * leftLegDirection);
		const float tRight = ((velocity_ - rightCutoff) * rightLegDirection);

		if ((t < 0.0f && tLeft < 0.0f) || (obstacle1 == obstacle2 && tLeft < 0.0f && tRight < 0.0f)) {
			/* Project on left cut-off circle. */
			const Vector2 unitW = normalize(velocity_ - leftCutoff);

			line.direction = Vector2(unitW.y(), -unitW.x());
			line.point = leftCutoff + radius_ * invTimeHorizonObst * unitW;
			orcaLines_.push_back(line);
			continue;
		}
		else if (t > 1.0f && tRight < 0.0f) {
			/* Project on right cut-off circle. */
			const Vector2 unitW = normalize(velocity_ - rightCutoff);

			line.direction = Vector2(unitW.y(), -unitW.x());
			line.point = rightCutoff + radius_ * invTimeHorizonObst * unitW;
			orcaLines_.push_back(line);
			continue;
		}

/*
		 * Project on left leg, right leg, or cut-off line, whichever is closest
		 * to velocity.
		 */
		const float distSqCutoff = ((t < 0.0f || t > 1.0f || obstacle1 == obstacle2) ? std::numeric_limits<float>::infinity() : absSq(velocity_ - (leftCutoff + t * cutoffVec)));
		const float distSqLeft = ((tLeft < 0.0f) ? std::numeric_limits<float>::infinity() : absSq(velocity_ - (leftCutoff + tLeft * leftLegDirection)));
		const float distSqRight = ((tRight < 0.0f) ? std::numeric_limits<float>::infinity() : absSq(velocity_ - (rightCutoff + tRight * rightLegDirection)));

		if (distSqCutoff <= distSqLeft && distSqCutoff <= distSqRight) {
			/* Project on cut-off line. */
			line.direction = -obstacle1->unitDir_;
			line.point = leftCutoff + radius_ * invTimeHorizonObst * Vector2(-line.direction.y(), line.direction.x());
			orcaLines_.push_back(line);
			continue;
		}
		else if (distSqLeft <= distSqRight) {
			/* Project on left leg. */
			if (isLeftLegForeign) {
				continue;
			}

			line.direction = leftLegDirection;
			line.point = leftCutoff + radius_ * invTimeHorizonObst * Vector2(-line.direction.y(), line.direction.x());
			orcaLines_.push_back(line);
			continue;
		}
		else {
			/* Project on right leg. */
			if (isRightLegForeign) {
				continue;
			}

			line.direction = -rightLegDirection;
			line.point = rightCutoff + radius_ * invTimeHorizonObst * Vector2(-line.direction.y(), line.direction.x());
			orcaLines_.push_back(line);
			continue;
		}

	const size_t numObstLines = orcaLines_.size();

	const float invTimeHorizon = 1.0f / timeHorizon_;

	/* Create agent ORCA lines. */
	for (size_t i = 0; i < agentNeighbors_.size(); ++i) {
		const Agent *const other = agentNeighbors_[i].second;

		const Vector2 relativePosition = other->position_ - position_;
		const Vector2 relativeVelocity = velocity_ - other->velocity_;
		const float distSq = absSq(relativePosition);
		const float combinedRadius = radius_ + other->radius_;
		const float combinedRadiusSq = sqr(combinedRadius);

		Line line;
		Vector2 u;

		if (distSq > combinedRadiusSq) {
			/* No collision. */
			const Vector2 w = relativeVelocity - invTimeHorizon * relativePosition;
			/* Vector from cutoff center to relative velocity. */
			const float wLengthSq = absSq(w);

			const float dotProduct1 = w * relativePosition;

			if (dotProduct1 < 0.0f && sqr(dotProduct1) > combinedRadiusSq * wLengthSq) {
				/* Project on cut-off circle. */
				const float wLength = std::sqrt(wLengthSq);
				const Vector2 unitW = w / wLength;

				line.direction = Vector2(unitW.y(), -unitW.x());
				u = (combinedRadius * invTimeHorizon - wLength) * unitW;
			}
			else {
				/* Project on legs. */
				const float leg = std::sqrt(distSq - combinedRadiusSq);

				if (det(relativePosition, w) > 0.0f) {
					/* Project on left leg. */
					line.direction = Vector2(relativePosition.x() * leg - relativePosition.y() * combinedRadius, relativePosition.x() * combinedRadius + relativePosition.y() * leg) / distSq;
				}
				else {
					/* Project on right leg. */
					line.direction = -Vector2(relativePosition.x() * leg + relativePosition.y() * combinedRadius, -relativePosition.x() * combinedRadius + relativePosition.y() * leg) / distSq;
				}

				const float dotProduct2 = relativeVelocity * line.direction;

				u = dotProduct2 * line.direction - relativeVelocity;
			}
		}
		else {
			/* Collision. Project on cut-off circle of time timeStep. */
			const float invTimeStep = 1.0f / sim_->timeStep_;

			/* Vector from cutoff center to relative velocity. */
			const Vector2 w = relativeVelocity - invTimeStep * relativePosition;

			const float wLength = abs(w);
			const Vector2 unitW = w / wLength;

			line.direction = Vector2(unitW.y(), -unitW.x());
			u = (combinedRadius * invTimeStep - wLength) * unitW;
		}

		line.point = velocity_ + 0.5f * u;
		orcaLines_.push_back(line);
	}

	size_t lineFail = linearProgram2(orcaLines_, maxSpeed_, prefVelocity_, false, newVelocity_);

	if (lineFail < orcaLines_.size()) {
		linearProgram3(orcaLines_, numObstLines, lineFail, maxSpeed_, newVelocity_);
	}

계산된 ORCA 라인들과 Linear Programming을 이용해서 새로운 속도를 얻는다.

💡Linear Programming
다양한 제약 조건을 고려하면서 선형 함수를 최대화하거나 최소화하는 수학적 모델링 기술

size_t lineFail = linearProgram2(orcaLines_, maxSpeed_, prefVelocity_, false, newVelocity_);

if (lineFail < orcaLines_.size()) {
	linearProgram3(orcaLines_, numObstLines, lineFail, maxSpeed_, newVelocity_);
}

result == newVelocity_랑 같다.

size_t linearProgram2(const std::vector<Line> &lines, float radius, const Vector2 &optVelocity, bool directionOpt, Vector2 &result)
{
	if (directionOpt) {
		//최적화되어 있는 방향. 이 경우 최적화 속도는 단위 길이입니다.
		result = optVelocity * radius;
	}
	else if (absSq(optVelocity) > sqr(radius)) {
		/* 가장 가까운 점과 바깥쪽 원을 최적화합니다. */
		result = normalize(optVelocity) * radius;
	}
	else {
		/* 가장 가까운 점과 안쪽 원을 최적화합니다. */
		result = optVelocity;
	}

	for (size_t i = 0; i < lines.size(); ++i) {
		//두 선이 같으면 0을 출력
		if (det(lines[i].direction, lines[i].point - result) > 0.0f) { // 평행사변형의 면적
			/* 결과가 제약조건 i를 만족하지 않습니다. 새로운 최적의 결과를 계산합니다. */
			const Vector2 tempResult = result;

			if (!linearProgram1(lines, i, radius, optVelocity, directionOpt, result)) {
				result = tempResult;
				return i;
			}
		}
	}

	return lines.size();
}

bool linearProgram1(const std::vector<Line> &lines, size_t lineNo, float radius, const Vector2 &optVelocity, bool directionOpt, Vector2 &result)
{
	//스칼라 곱, 벡터의 내적
	const float dotProduct = lines[lineNo].point * lines[lineNo].direction;
	const float discriminant = sqr(dotProduct) + sqr(radius) - absSq(lines[lineNo].point);

	if (discriminant < 0.0f) {
		/* 최대 속도 원은 line lineNo를 완전히 무효화합니다. */
		return false;
	}

	const float sqrtDiscriminant = std::sqrt(discriminant);
	float tLeft = -dotProduct - sqrtDiscriminant;
	float tRight = -dotProduct + sqrtDiscriminant;

	for (size_t i = 0; i < lineNo; ++i) {
		//분모
		const float denominator = det(lines[lineNo].direction, lines[i].direction);
		//분자
		const float numerator = det(lines[i].direction, lines[lineNo].point - lines[i].point);
		//fabs() : 절대값 연산
		if (std::fabs(denominator) <= RVO_EPSILON) {
			/* Lines lineNo과 i는 (거의) 나란하다. */
			if (numerator < 0.0f) {
				return false;
			}
			else {
				continue;
			}
		}

		const float t = numerator / denominator;

		if (denominator >= 0.0f) {
			/* Line i bounds line lineNo on the right. */
			tRight = std::min(tRight, t);
		}
		else {
			/* Line i bounds line lineNo on the left. */
			tLeft = std::max(tLeft, t);
		}

		if (tLeft > tRight) {
			return false;
		}
	}

	if (directionOpt) {
		/* 최적화 방향 */
		if (optVelocity * lines[lineNo].direction > 0.0f) {
			/* 오른쪽으로 극단적으로. */
			result = lines[lineNo].point + tRight * lines[lineNo].direction;
		}
		else {
			/* 왼쪽으로 극단적으로. */
			result = lines[lineNo].point + tLeft * lines[lineNo].direction;
		}
	}
	else {
		/* 가장 가까운 지점을 최적화합니다. */
		const float t = lines[lineNo].direction * (optVelocity - lines[lineNo].point);

		if (t < tLeft) {
			result = lines[lineNo].point + tLeft * lines[lineNo].direction;
		}
		else if (t > tRight) {
			result = lines[lineNo].point + tRight * lines[lineNo].direction;
		}
		else {
			result = lines[lineNo].point + t * lines[lineNo].direction;
		}
	}

	return true;
}

void linearProgram3(const std::vector<Line> &lines, size_t numObstLines, size_t beginLine, float radius, Vector2 &result)
{
	float distance = 0.0f;

	for (size_t i = beginLine; i < lines.size(); ++i) {
		if (det(lines[i].direction, lines[i].point - result) > distance) {
			/* 결과가 선 i의 제약 조건을 만족하지 않습니다. */
			std::vector<Line> projLines(lines.begin(), lines.begin() + static_cast<ptrdiff_t>(numObstLines));

			for (size_t j = numObstLines; j < i; ++j) {
				Line line;

				float determinant = det(lines[i].direction, lines[j].direction);

				if (std::fabs(determinant) <= RVO_EPSILON) {
					/* Line i 과 line j 는 나란하다 */
					if (lines[i].direction * lines[j].direction > 0.0f) {
						/* Line i 과 line j 는 같은 방향을 가리킨다 */
						continue;
					}
					else {
						/* Line i 과 line j 는 반대 방향을 가리킨다 */
						line.point = 0.5f * (lines[i].point + lines[j].point);
					}
				}
				else {
					line.point = lines[i].point + (det(lines[j].direction, lines[i].point - lines[j].point) / determinant) * lines[i].direction;
				}

				line.direction = normalize(lines[j].direction - lines[i].direction);
				projLines.push_back(line);
			}

			const Vector2 tempResult = result;

			if (linearProgram2(projLines, radius, Vector2(-lines[i].direction.y(), lines[i].direction.x()), true, result) < projLines.size()) {
				/* 원칙적으로 이런 일은 없어야 합니다. 
				 * 그 결과는 정의상 이 선형 프로그램의 실행 가능 영역에 이미 존재합니다.
				 * 실패할 경우 작은 부동 소수점 오차로 인해 발생하며 현재 결과는 그대로 
				 * 유지됩니다.
				 */
				result = tempResult;
			}

			distance = det(lines[i].direction, lines[i].point - result);
		}
	}
}

연관 키워드

half plane, ORCA, Linear Programming, Velocity Obstacle, 민코우스키 합

* 장애물에서 걸리는 현상이 많이 나오는 이유는 RVO 자체가 움직이는 Obstacle들이 서로 책임을 반틈씩 나누어 가지기 때문에 고정 장애물에서는 효과가 덜 나는 것으로 추측*

참고 사이트

논문의 핵심 내용

속도 장애물은 바뀌는 시간 환경을 위한 configuration space obstacle의 확장 개념이다.

즉 실시간 환경에 적합하다.

Velocity Obstacle(속도 장애물)은 객체의 Velocity가 속도 장애물인 VO 영역에 들어가지 않으면 물체는 충돌하지 않는다는 개념이다.
 

만약 위 그림과 같이 A와 B 객체가 존재한다면, A와 B가 충돌하지 않기 위해서 A는 B가 존재할 수 있는 공간에 들어가지 않으면 피할수 있다는 생각을 가지는 속도 조절 방법이다.
 

 
군중에서 한개의 객체들은 각각의 Velocity(방향을 가진 속도)를 가진다.  위의 그림에서는 A가 가진 속도는 VA로 나타내고, B가 가진 속도는 VB로 나타내었다.

VO를 계산하기 위해서는 Configurations Space로 변환해야하는데, Configuration Space는 수학에서는 위상 공간의 위치에 대한 점 모음 할당을 설명하는데 사용된다.
위상공간은 특정한 계가 가질 수 있는 모든 상태들의 공간이다.

점 A의 위치에서 바라볼 때 A의 몸체(원형)과 B의 몸체(원형)이 닿지 않는 점까지 고려해야 하기 때문에 A와B의 몸체의 위치들을 고려한 A+B 몸체(원형)과 맞닿아 있는 2개의 직선을 그어서 VO를 정의한다.
A에서 B에 대한 VO를 계산할 때, 위의 그림과 같이 점 A의 위치에서 B의 외곽을 지나는 직선 2개를 구한다. 이 직선 두개를 기준으로 VO는 회색 공간으로 표시된 공간이다. 현재 프레임에서 이 공간에 들어가지 않으면 B와 절대 충돌하지 않는다.
군중 시뮬레이션에서 Path Planning(경로 계획)을 지정할 때, 이러한 속도 장애물을 응용해서 넣는다.

다음 프레임에서 A가 B에 대해 계산한 회색 영역은 VB만큼 이동할 것이다.
회색 영역은 "Collision cone"이라고 부른다.
Collision cone은 계산할때 A와 B의 반지름을 더한 원에 대해서 외곽을 지나는 선 2개를 이용하여 구한다.
 
따라서, A의 Velocity를 조절할 때 VB만큼 이동한 회색 영역 VO를 침범하지 않는 Velocity를 조절하면 다음 프레임에서 A는 B를 피해서 이동하는 것처럼 보일것이다.

따라서 기존의 VA 속도를 VO를 피해서 빨간색 부분만큼으로 조정하면서 시뮬레이션을 진행시키면 충돌을 회피하는 시뮬레이션을 제작할 수 있다.

VO의 진동 현상을 줄인 RVO

 
velocity obstacle 관련 자료 : https://en.wikipedia.org/wiki/Velocity_obstacle

논문 참고 : Motion Planning in Dynamic Environments using Velocity Obstacles - 1998년도 발행 

- BIOS에서 SVM 활성화하기

- 그 후 Windows 기능 켜기/끄기 -> Windows 하이퍼바이저 플랫폼 체크 -> 재부팅

순서로 하면 해결 가능합니다!

포트란?

컴퓨터 하드웨어 포트 : 컴퓨터와 다른 컴퓨터, 장치 사이의 인터페이스 역할. 장비에 케이블이나 플러그를 연결하는 특별한 외부 단자

컴퓨터 소프트웨어 포트 : 프로그램 같 상호 정보 교환시 파일이나 임시 저장소를 거치지 않고 직접 연결하기 위한 가상의 논리적 접속

포트의 장점

-하나의 컴퓨터가 여러 인터넷 서비스를 제공할 수 있다.

-자신이 원하는 서버와 클라이언트 프로그램을 사용할 수 있다.

윈도우는 C:\WINDOWS\system32\drivers\etc\services 에서 확인할 수 있다.

service 파일에 예약된 주요 프로토콜

버블정렬을 이용하여 랭킹 시스템을 c++로 구현해보았습니다.

앞으로 게임을 짤때 랭킹 시스템에 종종 이용할 수 있겠군요

2017/09 작품

초밥의 길은 나 나름대로의 애정이 많이 담긴 프로젝트이다

모든 프로젝트가 그렇듯 순탄치 않은 프로젝트였지만 마무리는 잘되었다

공모전도 참여해보았지만 잘 되진 않았다

교내 해커톤 대회에서 무박2일로 프로토타입을 만든 후 개발자들끼리 짬짬이 한달 동안 개발하였었다.

우리팀 디자이너분이 고생해주셨다.(3명 프로그래밍, 1명 그래픽) 

그 중에 저는 손님에 대한 프로그래밍을 하였습니다.

실제 게임 화면이고 편집된 동영상을 캡쳐한 화면입니다.

밥 + 와사비 + 회를 이용해서 초밥을 만들어서 손님의 입으로 던지는 게임입니다.

실제로 던진다고 할 때 사람들의 흥미도가 가장 높았습니다.(흥미로운 발상이였나보네요)

영업시간이 종료되고 BreakTime일 때의 모습입니다.

회를 손질해서 도마에 재료를 채워넣는 부분입니다.

실제로 참치를 칼로 써는 부분이 있습니다!

물론 요리왕 비룡처럼 한번의 칼질로 다 손질이 되는 마법이 일어나지만 개발자들이 제일 재밌어 했던 부분입니다.

반대로 플레이어들은 제일 어려워했습니다.(아마도 VIVE에 익숙하지 않았던 사람들)

라이프가 다 깍이면 점수창이 나타나고 다시 재시작을 할 수 있습니다.

실제로 대구 엑스코에서 개최되었던 융합ICT 전시회에서 전시를 하였습니다.

디자이너분이 아주 훌륭하고 친절하게 아이들에게 가르쳐주고 있습니다.

제가 짠 코드의 부분부분을 올렸는데 좀더 나은 코드를 위해! 더 노력해야겠습니다~

시간이 된다면 좀 더 다듬어서 개발하고 싶은 마음이 있는 게임이기도 합니다.

- 트로이 목마

자기 복사 능력은 없이 고의적인 부작용만 일으키는 프로그램

고의적으로 포함되었다는 점에서 버그와는 다르지만 자기 자신을 다른 파일에 복사하지 않는다는 점에서 바이러스와 구별됨

어떤 프로그램을 실행시켰을 때 하드디스크의 파일을 지우지만 다른 프로그램에 복사되지 않는다면 바이러스가 아니라 트로이목마 프로그램

- 스니핑

자신이 아닌 다른 상대방들의 패킷을 엿듣거나 엿보는 것

네트워크 트래픽을 도청하는 것

- 웜(=인터넷 웜)

네트워크를 통하여 자기 자신을 복제하여 전파할 수 있는 프로그램

다른 프로그램을 감염시키지 않고 동작

- 스푸핑

해킹시 자신의 IP주소, DNS 이름, MAC 주소 등과 같은 고유 식별자를 위장하여 역추적을 어렵게 만드는 기법

​

2017/09월 참여

이틀동안 참가하면서 장고걸스 연결하는법과 서버에 오려보는 등 유익한 시간을 가졌다!

즐거웠고 서버개발에 대해 더욱더 알고 싶다는 생각을 하게되었다.

현재는 Unity의 Localize라는 좋은 기능이 있어서 해당 내용을 참고하여 제작하는 것이 더 좋을 것이다.

-------------------------------------------------------------------------------------------------------------------

Project_R을 만드는 중인데 XML을 이용하여서 NPC들의 언어를 받아오는 중이다.

대충 이런 형식으로 현재는 한국어에 대한 정보들만 먼저 불러와놓고 쓰는 형식인데 다양한 언어를 이용하려면 어떻게 할까..

일단 KOREAN만 불러오는건 좋지 않으니 여러가지를 받을 수 있도록 변경해보자

일단 langNum에 따라 두가지를 받아 올 수 있도록 변경하였고 이젠 이걸 option 바의 language설정에 따라 바꾸도록 변경하면 되는데

고민되는 부분이 언어를 바꾸고 확인버튼을 누르면 모든 설정값이 바뀌어야하는데 지금 xml에 들어 있는 값들은 npc들의 대사밖에 없다.

흠.. xml을 여러개 만들고 이것저것 끌어다가 쓸까 생각을 하는데 그렇게 되면 많은 데이터들을 불러오게 되면 렉이 생기지 않을까하는 생각이 든다.

일단 지금은 NPC 대사들에 대해서만 언어를 변경해보도록 하자.

완전 테스트 용이므로 ESC키를 누르면 버튼이 나타나고 버튼을 누르면 변경되는 형식으로 설정해놓아보자

대충 이런식으로 임시로 만들었다.

음.. 코드에 ESC를 누르면 저 창이 뜨도록 바꾸자

적용한 모습

흠 이제 언어 바꾸기를 누르면 npc의 언어가 바뀌도록 해봅시다.

완성화면

com 은 come으로 바꿔야겠다. 

다음번에는 옵션창에 버튼을 눌러서 2가지 선택지를 주고 저장하면 바뀌는 형식으로 좀 더 업그레이드 하여야겠다.

이번에는 맵 이동을 하는 알고리즘에 관한 고찰을 해볼것인데..

아직 리소스가 부족해서 마을은 못만들었지만 가명으로 F마을,W마을이라고 하겠다.

일단 MapManager를 만들어보자

F로 가는 포탈은 파란색 지점에 W로 가는 포탈은 초록색 지점에 있다.

먼저 mapArray로 3가지의 맵을 불러오자.

3개의 맵오브젝트는 Map이라는 게임 오브젝트의 하위에 들어있으며 Awake()함수에서 자동으로 불러오도록 하겠다.

게임을 시작하면 Map 하위 오브젝트들을 불러오는 것을 확인할 수 있다.

그다음 각각의 포탈들을 불러오는 코드들을 똑같이 적용하여준다.

포탈들도 똑같은 과정을 이용하여서 적용시켜준다.

하지만 구조를 다르게 만들었다. 두개 포탈을 이용하여서 왔다갔다 할 수 있도록 만들려고 한다.

두개의 transform을 담고 있는 linkedPotal이라는 클래스를 만들고 2개의 포탈 정보를 저장하고 포탈 정보를 들고 올 수 있도록 만들었다.

2중 for문을 이용하여서 하위 오브젝트 한개를 들고 오고 그 오브젝트의 하위오브젝트들을 저장하는 형식으로 제작하였다.

시작되면 차례차례대로 들어가는걸 볼 수 있다.

이제 포탈에 닿으면 지정된 위치로 변하는 코드를 짜보자

플레이어가 포탈에 닿으면 MapManager의 enterPotal이란 함수를 실행시키도록 하겠다.

밑에 부분은 짤렸는데 pos를 반환한다.

반환한것을 플레이어에서 임시로 저장해놓는다.

왜냐면 fade in과 out을 실행할 것이기 때문이다. 

여기서 잠깐 헤매었는데 fade in out을 시작 싸인을 주고 바로 position을 비꿔버리니까 어색한 감이 있어서 fade out으로 변하는 반환점에서 플레이어의 위치값을 변경해주었다.

할 때는 fade in과 out을 할 생각이 없었는데 하다보니 빠져들어서 홀린듯이 하게 되었다.

완성된 모습

흰색 큐브가 포탈 역할을 한다.

sweep and prune은 교수님께서 특정 논문을 읽으라고 하셨을 때 본 방법입니다

하지만 한글 해석이 된 포스팅이 없어서 간단하게 번역하여 놓고 점점 추가 및 보완할 예정입니다

해당 포스팅은 https://github.com/mattleibow/jitterphysics/wiki/Sweep-and-Prune 을 한국어로 해석한 포스팅으로 문제가될 시 삭제하도록 하겠습니다

광역 충돌 시스템은 모든 물리 엔진의 핵심 과정 중 하나입니다.

이미 광역 충돌에 대해 놓친 게 있다면 광역 충돌시스템을 최적화하는 코드를 짜서 복구하기는 어렵습니다.

물리 엔진에서 충돌 단계에는 3가지가 있습니다.

1. Broadphase : 광대한 범위

- 여기서 어떤 충돌이 실제로 일어날 수 있는지를 감지하고, 충돌할 수 없는 충돌을 폐기합니다.

참고할만한 사이트 : https://developer.nvidia.com/gpugems/gpugems3/part-v-physics-simulation/chapter-32-broad-phase-collision-detection-cuda

2. Midphase : 중간 범위

- 구나 천 물체 같은 기하학적 단계에서의 충돌을 말합니다. 

3. Narrowphase : 좁은 범위

- 이 단계에서 실제 충돌 감지를 수행합니다.  교차점, 충돌 법선 또는 침투 깊이와 같은 충돌 데이터를 검색하는 작업을 합니다.

거의 모든 광역 시스템은 객체의 축 정렬된 경계 상자(aabb)를 사용합니다.

aabb는 꽤 빨리 계산될 수 있으며 교차점을 확인하는 것도 몇 줄의 코드로 수행됩니다.

참고할만한 사이트 : https://blog.naver.com/mycode333/50031266282

그렇다면, 어떻게 하면 "겹치지 않는 쌍의 정렬 과정"을 가속화 할 수 있을까요?

충돌을 감지하기 위한 예전의 접근방식에 대해 몇 가지를 알아봅시다.

for (int i = 0; I < rigidBodies.Count; i++)
{
    for (int e = i; e < rigidBodies.Count; e++)
    {
        if (CheckBoundingBoxForOverlap(i, e))
            DetectNarrowPhase(i,e);
    }
}

그렇게 나쁘지는 않지만..

만약 10x10x10 충돌 감지 되는 큐브가 있다면, 최상의 경우 수천 개의 충돌 가능한 쌍을 확인하여 위의 코드를 수행해야 합니다. 좁은 범위의 충돌 체크는 0.25백만 개를 체크해야합니다.

자연적으로 광역 범위는 O(n^2) 문제가 생기는데 이에 대해 무엇을 할 수 있을까요?

데이터 구조를 가속화해야 합니다.

웹에서 "광역상 충돌 탐지"를 검색하면 Sweep And Prune(SAP)접근법을 발견하게 됩니다.

많은 변형된 구현들이 있지만 분류한 다음 다듬는다(Prune)는 공통점이 있습니다.

SAP 알고리즘에서 가장 간단한 "flavor"를 지속되지 않는 단일 축 SAP에서 사용한다는 것이 무엇을 의미하는지 알아봅시다.

1. 공간 안의 모든 물체들은 "AxisList"라는 목록 안에 들어있습니다. 경계상자의 시작을 이용해 한 개의 축(여기서는 X축)으로 리스트를 정렬합니다. 따라서 물체 5의 가장 왼쪽 지점이 X축을 직접 볼 때 물체 6의 가장 왼쪽 지점보다 더 왼쪽에 있다는 것을 알 수 있습니다.

2. "ActiveList"라는 새로운 임시 리스트를 만들자. 이제 "AxisList"의 다음 항목을 보고 "ActiveList"의 모든 항목과 비교합니다.(현재는 단 하나) 만약 새 항목의 왼쪽이 더 크면 현재 "ActiveList"의 오른쪽 항목이 제거되고 "ActiveList"에서 현재 "ActiveList" 아이템이 제거됩니다. 그렇지 않으면 새 "AxisList" 항목과 현재 "ActiveList" 항목 간의 충돌 가능성이 생깁니다. 새 항목 자체를 "ActiveList"에 추가하고 "AxisList"의 다음 항목을 계속합니다.

이 접근법이 지속적이지 않다는 것을 알게됩니다.

정렬은 처음부터 모든 프레임에서 수행되며(quicksort 성능이 좋다) 한 축(여기에서는 X축)에 대해 정렬된다.

우리는 장면의 일관성을 이용하지 않는다.(한 프레임에서 장면이 많이 변하지 않을 가능성이 있다)

속도 향상은 어디서 발생하는것일까?

정답은 충돌 탐지는 검색 문제이기 때문입니다. 그리고 사전 분류된 목록을 검색은 O(nlog(n)) 보다 빠릅니다.

이 쉬운 접근법을 구현하면 무차별 힘 알고리즘(brute force algorithm)에 비해 엄청난 속도 향상이 가능합니다.

JigLib (Danny Chapman이 만든 코드)에서 C # (JigLibX)로 이식되었을 때, JigLib의 원래 버전은 무차별적인 힘과 매우 기본적인 그리드 접근법을 포함하고있었습니다.
존 와트는 위에서 설명한 코드를 정확하게 사용하는 프로젝트에 SAP 알고리즘을 적용했는데, 이는 복잡한 그리드 접근법을 쉽게 극복했습니다.

따라서 이 코드는 이미 꽤 잘 수행되지만, 그럼에도 불구하고 X축에서 모든 물체가 겹치면 런타임은 다시 O (n *2)이다.

(따라서, 대부분의 물체가 그곳에서 겹치기 때문에, 분리 축으로 up-축을 사용하지 않아야 합니다)

Sweep and Prune을 하기 위한 더 복잡한(그리고 더 빠른) 접근법은 완전한 3축 검사를 하는 것입니다.

두 물체가 충돌하면 세 축 모두 겹치는 경우에만 충돌합니다 (분리 축 정리).

지속적 3Axis SAP는 다음과 같이 요약하여 작동합니다.

우리는 세 개의 목록 (각 축 1에 대해)을 사용하고 삽입 정렬을 사용하여 정렬된 목록을 유지합니다.

삽입 정렬은 거의 정렬된 목록에서 O(n)입니다.

삽입 정렬 알고리즘의 스왑은 개체가 다른 본체와 중첩되기 시작/중지하는 것을 의미합니다.

그래서 한 개의 해시 테이블을 겹쳐서 보관하고, 각 프레임은 삽입구역을 하고, 해시 테이블 구조를 업데이트하는 데 사용하는 변경사항만 보고받습니다.

Jitter의 절차

private void SortAxis(List<SweepPoint> axis)
{
    for (int j = 1; j < axis.Count; j++)
    {
        SweepPoint keyelement = axis[j];
        float key = keyelement.Value;
        
        int i = j - 1;
        
        while (i >= 0 && axis[i].Value > key)
        {
            SweepPoint swapper = axis[i];
            
            if (keyelement.Begin && !swapper.Begin)
            {
                if (CheckBoundingBoxes(swapper.Body, keyelement.Body))
                {
                    lock (fullOverlaps)
                    {
                        fullOverlaps.Add(new BroadphasePair(swapper.Body, keyelement.Body));
                    }
                }
            }
            
            if (!keyelement.Begin && swapper.Begin)
            {
                lock (fullOverlaps) 
                {
                    fullOverlaps.Remove(new BroadphasePair(swapper.Body, keyelement.Body));
                }
            }
            
            axis[i + 1] = swapper;
            i = i - 1;
        }
        axis[i + 1] = keyelement;
    }
}

만약 당신이 전형적인 SAP 데이터 구조의 모든 세부사항에 관심이 있다면, 나는 피에르 테르디만이 쓴 훌륭한 기사를 읽을 것을 추천합니다.

그렇지 않다면 각 프레임에 "A가 축 C에서 B와 겹친다"는 정보나 "A가 축 C에서 B의 중첩을 중지했다"는 정보만 전달받으면 X, Y 또는 Z축이 될 수 있습니다.

처음 이것을 시행했을 때, 나는 내가 받는 값싼 결과에 매우 만족했고, 그리고 나서 실수를 했습니다.

각각의 쌍이 얼마나 중복되는지를 기억하는 데이터 구조를 구현했습니다.

겹치는 횟수가 3회(모든 축에서 겹치는 횟수가 1회임을 의미)인 경우, 물체는 충돌합니다.

이것은 효과가 있지만 끔찍합니다.

한 축에 겹치는 쌍의 수는 매우 높을 수 있으므로 중복 계수 = 1인 수천 개의 잠재적 겹치는 쌍을 저장해야 한다. 단지 몇 개만 두 번째 축에 겹치고 겹치는 횟수가 2이고, 세 번째 축에 겹치는 횟수는 3이라는 것을 깨달았습니다.

결국 런타임은 O(nlogn)였지만 메모리 사용량은 O(n^2)이었다(내 사전 구조를 죽이는 것)

이 문제의 해결책은 간단합니다. 아무것도 저장하지 마라.

한 축이 중첩을 보고하는 경우 저렴한 전체 경계 상자 확인 – 양수일 경우 해당 쌍을 풀오버랩에 추가하십시오.

한 축에 두 개의 몸체가 분리되어 있다고 보고된 경우, 풀오버랩에서 쌍을 제거하십시오. (이것은 위의 코드로 행해진다.) 따라서 SAP에 사용되는 메모리는 다시 O(n)에 지나지 않습니다.

("CollisionSystemPersistent"에서 Jitter의 구현을 찾을 수 있음) SAP.cs".)

지속적인 Sweep and Prune 알고리즘의 단점 중 하나는 많은 비활성 객체를 가진 정말 큰 세계를 경험한다는 것이다.

총알이 정적인 물체가 많은 마을을 관통하는 것을 상상해보라.

각 물체(총탄으로부터 수마일 떨어져 있어도)와 탄환 자체 사이에 교환이 있다

이 문제는 그리드(광범위 단계)를 구성하는 여러 개의 소형 SAP를 사용하여 해결할 수 있다.

내가 알아차린 또 다른 문제는 광선과 경계 상자 질의가 효율적으로 수행될 수 없다는 것이다.

레이캐스팅의 경우, 정렬된 세 개의 목록은 균일하지 않은 복셀 그리드로 해석될 수 있으므로, 주문한 레이 쿼리를 얻을 수 있다.

이것은 실제로는 다소 느리다.

왜냐하면 많은 복셀 그리드가 비어 있고 초기 타격을 받은 광선에 대한 해결책일 뿐이기 때문이다.

단지 각 물체에 대해 거친 힘 검사를 하는 것이 종종 더 빠르기 때문이다.

또 다른 문제는 장면에 하나의 큰 물체(대개 지면이나 레벨)가 포함되어 있다는 것이다.
이 개체의 끝점은 완전히 왼쪽에 있고 목록 오른쪽에 있다.

스위프 포인트에 저장된 추가 정보가 없으면 개체가 훨씬 더 큰 엔티티의 끝점에 의해 둘러싸이는지 여부를 효율적으로 감지할 수 있는 방법이 없다.

소켓이란

-TCP/IP로 통신하는 컴퓨터가 가지는 네트워크 내의 주소인 IP address,IP address의 서브 address인 포트 번호를 조합한 Network address

-네트워크 상에서 클라이언트 프로그램과 서버 프로그램 사이의 통신방법

-네트워크상에서 서버와 클라이언트 두개의 프로그램이 특정포트를 통해 양방향 통신이 가능하도록 만들어주는 소프트웨어 장치

-멀리 떨어져 있는 두개의 호스트(host)를 연결시켜주는 매개체 역할

-소켓은 반드시 네트워크를 통해서 통신을 할 때만 사용되는 것은 아님

-유닉스 계열의 시스템에서 시스템 내부의 프로세스들끼리 통신을 하기 위한 용도로도 사용될 수 있음

프로토콜이란

정보기기 사이에서 정보교환이 필요한 경우, 이를 원활하게 하기 위하여 정한 여러가지 통신규칙과 방법에 대한 약속

일반적으로 기종이 다른 컴퓨터는 통신규약도 다르기 때문에 기종이 다른 컴퓨터간에 정보통신을 하려면 표준 프로토콜을 설정하여 통신망을 구축하여야 한다.

대표적인 표준 프로토콜의 예는 인터넷에서 사용하고 있는 TCP/IP가 이에 해당된다.

프로토콜에 포함되어야 할 목록

오류제어,동기,흐름제어,코드변환,전송속도,통신하는 상대방의 위치에 따라 통신 개체가 어느 OSI 계층에 있는 가,효율적인 정보전송을 위한 기법,정보의 안전성(보안)에 관한 약속

새 프로젝트를 눌러주자!

이런 창이 뜨면 Win32 콜솔 응용 프로그램을 만들것이다.

이름을 바꿔주면 프로젝트의 이름이 바뀌고 위치는 자신이 설정해주고 싶은 곳에 지정해주면 된다.

(참고로 이름과 솔루션 이름은 동일하게 자동으로 입력된다.)

확인을 누르고 그다음 뜨는 창에서 다음을 또 눌러주자.

이러한 창이 뜨게 되면 우리가 만들고 싶은 것은 빈 프로젝트이기에 빈프로젝트를 체크하고 마침을 눌러주면 생성된다.

자 그러면 이제 솔루션 탐색기에 내가 만든 프로젝트가 뜨게 되는데 여기에서

[소스파일] 우클릭 -> 추가 -> 새 항목 을 눌러주자

그러면 이러한 창이 뜨게 되는데

C++ 파일 을 클릭해놓고 이른에는 소스이름(소스이름은 꼭 영어로 만들도록 하자).c 를 해주어야한다.

소스이름.cpp 파일을 만들게 되면 C언어가 아닌 C++언어로 만들어지므로 확장자는 꼭 .c로 만들어주도록 하자.

야생의 빈 소스파일이 하나 만들어졌다!

그러면 이제 수학의 집합단원과 같은 C언어의 Hello,World! 출력하는 코드를 한번 만들어보자.

이렇게 적었으면 Ctrl+F5 번을 눌러서 솔루션을 빌드해보자.

이런 창이 떳다면 성공한것이다. (한글 윈도우에서는 "계속하려면 아무 키나 누르십시오..." 일것이다.)

한글을 적어도 잘 출력된다.

음 그런데 여기서 창의 색깔이 흰색인게 마음에 안든다 싶으면 창에서 마우스 우클릭을 하면

여기서 Properties(속성)에 들어가보자.

여기서 여러가지 속성을 바꿀 수 있다.

이렇게 바꿀 수 있다!

*C언어는 절차지향적 특성을 지닌다.

C언어는 정해진 순서의 실행흐름을 중시한다. 절차지향적이기 때문에 처음 접하는 사람도 조금만 공부하면 쉽게 익숙해질 수 있다.

*C언어로 구현된 프로그램은 좋은 성능을 보인다.

사용하는 메모리의 양이 상대적으로 적고, 속도를 저하시키는 요소들을 최소화한 언어이기 때문이다.

까먹지 말고 복습하자 STL은 꽤나 유용한 라이브러리이다.

간단하게 설명하자면 STL은 템플릿으로 작성된 많은 제네릭 클래스와 함수 라이브러리이다.

컨테이너,iterator,알고리즘로 분류된다.

- 컨테이너 종류

- iterator 종류

- 알고리즘

아무래도 이전에 올렸던 것들은 수업시간에 교수님의 도움을 받아 했던 것들인데

꽤 적지 않은 분들이 openGL에 대해 관심이 있는 것 같아서 공부도 할겸 내가 직접 여러가지 자료들을 참고하여서 만들어보려고 한다.

일단 나는 VisualStudio 2017을 사용할 것이다.

프로젝트를 만들고 main.cpp를 소스 추가해주고

프로젝트(P) → 속성(P) 을 클릭하여 프로젝트의 속성을 킨다.

1. C/C++ → 일반 → 추가 포함 디렉터리

2. 링커 → 일반 → 추가 포함 디렉터리

3. 링커 → 입력 → 추가 종속성

에 GLFW와 gl3w라이브러리를 추가해준다.

GLFW 라이브러리 : https://www.glfw.org/

GLFW는 데스크탑에서 OpenGL, OpenGL ES 및 Vulkan 개발을 위한 오픈 소스 다중 플랫폼 라이브러리이다.
창, 컨텍스트 및 표면 생성, 입력 및 이벤트 수신을 위한 간단한 API를 제공해준다.
glfwinit(), glfwCreateWindow() 등과 같은 함수를 포함하고 있다.

gl3w 라이브러리 : https://github.com/skaslev/gl3w (cmake 이용해서 빌드해야할듯)

gl3w는 glew를 대체할 수 있는 라이브러리로 glew는 옛날 버전의 OpenGL까지 지원한다.
gl3w 라이브러리는 OpenGL 3와 4의 코어 프로파일에 초점을 맞추고 있다.

만약 LNK2001 에러가 뜬다면 해당 함수의 초기화가 되지 않은 것이니 gl3w.c 파일을 프로젝트 안에 소스로 추가하자. 해결 방법 찾은 링크

main에 기본형을 적어주고(https://www.khronos.org/opengl/wiki/OpenGL_Loading_Library#GL3W 을 참고함)

그리고 

#include <GL/gl3w.h> #include <GLFW/glfw3.h>

이부분은 꼭 순서를 다르게 적지 말고 똑같이 적어야 한다.

그리고 컴파일해보면

이 창이 뜨면 정상이다. 에러가 뜨면 다시 라이브러리 경로가 잘못되진 않았는지,  64비트 32비트 잘 확인했는지 한번 더 체크해보자.

필자는 오픈소스인 ImGUI를 이용하여서 프로젝트를 진행하도록 하겠다.

참고 링크 : https://github.com/ocornut/imgui

다시 한 번 라이브러리를 추가 포함 디렉터리에 넣는다.

ImGUI는 라이브러리를 따로 자체적으로 제작하거나 아니면 통짜로 소스코드를 내부에 넣어서 빌드하면 된다.

나는 라이브러리 제작 아래 링크의 블로그를 따라서 제작해서 사용하였다.

https://swstar.tistory.com/229#gref

라이브러리 설정이 끝나면

https://github.com/ocornut/imgui/blob/master/examples/opengl3_example/main.cpp

이 쪽으로 들어가면 imgui와 glfw3,gl3w에 관한 예제를 찾을 수 있다.

이것을 조금 참고하여서 넣어보자.

--------------------------------------------------------------------------------------------------------------

최근에 다시 들어가보니 몇가지 URL도 사라지고 해서 간단한 방법을 쓰길 바란다.

아무래도 업데이트를 자주 하시다 보니 방법을 바꾼듯 한데

간단하게 https://github.com/ocornut/imgui 여기서 초록색 Code 버튼 -> download Zip -> 압축해제 후 imgui 관련 소스들을 프로젝트에 포함시켜서 진행하면 될 것 같다.

나는 위 그림과 같이 ImGUI 소스들을 추가하였고 속성들을 다시 재설정하였다.

glfw 라이브러리를 속성에 추가하여주었고

glviewport, glclearcolor, glclear 함수를 찾을 수 없는 LNK2019 에러가 뜨는 경우에는

위의 그림과 같이 추가 종속성에 glfw3.lib와 opengl32.lib를 넣어보길 바란다.

opengl3_loader.h의 경우 현재 gl3w.h의 최소한의 기능들을 땡겨서 오므로 나중에 gl3w.lib를 추가하고 땡겨오는 경우 재정의 문제가 발생한다.

https://github.com/ocornut/imgui/issues/4445

위의 링크는 해당 에러에 대한 imgui 제작자가 답변한 경우이며 gl3w_stripped라는 파일을 제작하여 두 개의 라이브러리를 충돌시키지 않게끔 만들라는 것인데

https://github.com/dearimgui/gl3w_stripped

나의 경우 cmake를 통해 프로젝트를 다시 만들어서 돌리니까 imgui_loader.h에 필요한 gl3w 파일들이 제작되어서 gl3w.h 헤더파일 대신 imgui_impl_opengl3_loader.h 파일을 사용하니까 해결되었다.

https://github.com/ocornut/imgui/blob/master/examples/example_glfw_opengl3/main.cpp

이 예제를 사용하여서 main 함수를 제작하였다.

본 화면이 떳다면 성공한 것이다. 앞으로 이 ImGUI와 함께 openGL을 공부해보도록 하자!

이에 몇 가지 참고할만한 사이트의 링크들을 좀 남겨놓겠습니다

저도 제 일이 정리가 되면 아마 포스팅을 다시 시작하게 될 것 같습니다~!

LearnOpenGL

learnopengl.com/

LearnOpenGL 번역 블로그

heinleinsgame.tistory.com/4

P.S 혹여나 문제가 되거나 틀린 사항은 가르쳐주시면 감사합니다 :)

Chapter 1. Ubuntu에서 mariadb 실행을 하여보자.

*모든 실행은 MariaDB 5.5에서 작동하는 예제입니다

mariadb를 다 설치하셨으면 한번 실행해볼까요? 먼저 Ubuntu 화면에서 terminal을 실행시킵니다.

이러한 실행창이 떴다면 성공하신겁니다. 그 다음으로는 mariadb를 실행시켜보기 위해 명령어를 적어보도록 하겠습니다. 그런데 mariadb를 실행하기 위해 mariadb –u root –p 명령어를 입력하였더니 찾을 수가 없다고 합니다.

mysql –u root –p 명령어를 입력하였더니 비밀번호를 입력하라는 문구가 나오고 초기에 설정하였던 비밀번호를 입력하게 되면 'Welcome to the MariaDB monitor' 라는 문구와 함께 mairaDB가 구동되게 됩니다.

.

Chapter 2. 새로운 데이터 베이스를 만들어보자.

mariaDB도 잘 구동되니 지금부터 나만의 데이터 베이스를 하나 만들어봅시다. 회원 관리 데이터베이스를 하나 만들어보겠습니다.

데이터베이스 이름은 'membership' 으로 하겠습니다.

mariadb에서는 mysql에서 데이터 베이스를 만들었던 것과 같은 명령어를 쓸 수 있습니다.

2.1 CREATE

create 명령어를 사용하면 데이터베이스 한 개를 만들 수 있다.

2.2 SHOW

show 명령어를 쓰면 위와 같은 결과가 나오는 것을 볼 수 있다. 

보면 db1이라는 데이터 베이스와 membership이라는 데이터 베이스 2개가 있음을 알 수 있다.

2.3 DROP

drop 명령어를 이용해서 db1과 membership 데이터베이스를 지운 모습이다.

2.4 USE

use를 이용해서 어느 데이터베이스를 쓸 것인지를 정합니다.

테이블의 내용을 조회하거나 변경할 때에는 반드시 대상 데이터베이스의 이름과 테이블의 이름이 명시되어야한다.

2.5 ALTER

ALTER문은 이미 존재하는 테이블의 구조나 형식등을 바꾸기 위해 사용한다. 아래의 문장은 테이블 안에 칼럼을 추가하는 문장이다.

datetime not null을 하게 되면

*칼럼 추가

*칼럼 삭제

*칼럼 변경

*인덱스에 새항목 추가

*인덱스 삭제

*Primary key 지정하기

*Primary key 삭제

Chapter 3. 데이터를 조작하여 보자

3.1 INSERT

테이블에 레코드를 저장하기 위해서 insert 문장을 사용한다. insert 문장이 실행되기 위해서는 반드시 먼저 테이블이 존재 해야 한다.

*테이블 생성하기

만약 이러한 데이터 테이블을 만들고 싶다면 이렇게 입력하면 된다.

테이블이 생성되었으면 INSERT를 이용하여서 테이블에 레코드를 저장하여보자.

5297734 KIM 22 을 넣어보도록 하자

INSERT INTO ... ON DUPLICATE KEY UPDATE ,,, 라는 형태의 구문이 사용되면 중복된 레코드가 

이미 존재할 때에는 UPDATE가 실행되고 그렇지 않을 때에는 INSERT가 실행된다.

이 구문에서 UPDATE가 실행되지 않고 INSERT가 실행된 이유는 테이블을 만들 때 PRIMARY KEY를 설정하지 않아서 그렇습니다.

테이블을 다시 만든 뒤 ON DUPLICATE KEY UPDATE라는 옵션을 설정하지 않은 채로 집어 넣으면 어떻게 될까? 당연히 오류 문구를 띄우게 됩니다.

3.2 SELECT

INSERT를 이용해서 레코드 값을 집고 show를 이용하여 내용을 보고 싶었지만 보이지가 않는다. 

테이블에 저장된 레코드를 조회하기 위해서는 select 문장을 사용한다.

그러면 아까 만들어봤던 membership테이블의 결과를 보도록 하자.

3.3 UPDATE

그런데 이 데이터가 마음에 들지 않는 다면 바꿔야 할 때 쓰는 것이 UPDATE 문장이다. 

INSERT된 레코드를 삭제하지 않고, 레코드의 일부 칼럼을 변경하기 위한 SQL문장이다.

name을 GAHYEON 으로 바꾸어보겠다.

*UPDATE 문장 사용시 주의해야 할 점

WHERE 조건절이 없는 경우 그 테이블의 모든 레코드에 대해서 칼럼 값을 변경하게 된다.

3.4 REPLACE

레코드가 존재하지 않으면 INSERT로 처리되고 레코드가 존재하는 경우에는 update로 처리된다.

그러나 이 코드 그대로 쓰려고 봤더니 내가 생각했던 대로 나오지가 않았다. 

중복된 레코드가 있을 경우 레코드를 삭제하고 다시 INSERT하게 된다고 하였는데 레코드가 3개인 테이블에서는 중간 값이 null로 들어가고 앞의 칼럼이 삭제 되지 않은 채로 INSERT가 되었다. 

그래서 인자 값이 모자라서 그렇게 된 것인가? 라는 생각을 해보았다.

세 개의 인자 값을 써서 REPLACE 문장을 써보았는데 이번에도 INSERT 문장이 실행되었다. 

그래서 구문의 문제가 있는가? 하고 다른 문장을 이용해보았다.

그러나 이번에도 똑같이 추가가 되는 형식으로 진행되었다. 

무엇인가 이상하여서 찾아보았더니(https://mariadb.com/kb/en/mariadb/replace 참고, 'Real MariaDB' 책에도 있는 내용) 'REPLACE는 INSERT와 비슷하게 동작된다. 

primary key나 unique키가 중복된 레코드가 있다면 먼저 그 레코드를 삭제하고 새로운 레코드로 insert를 수행한다.' 라는 전제조건이 있었다. 

그러면 primary key가 포함된 table을 하나 더 만들어서 replace문을 실행시켜 보도록 하자.

INSERT문장을 이용하여서 데이터를 삽입하고 아까 전의 REPLACE 문장을 다시 실행해보자.

생각한대로 결과값이 나오게 된다! REPLACE 문장은 중복된 레코드가 있을 경우 레코드를 삭제하고 다시 INSERT하게 되므로 INSERT INTO ... ON DUPLICATE KEY UPDATE ... 문장보다는 부하도 높고 시스템의 자원을 많이 소모하게 된다. 

가능한대로 REPLACE문장 보다는 INSERT INTO ... ON DUPLICATE KEY UPDATE ... 문장을 쓰도록 하자.

3.5 DELETE

테이블에 존재하는 레코드를 삭제할 때 DELETE문장을 사용한다.

WHERE 조건절이 있는 경우에는 그 조건에 부합되는 레코드만을 삭제하지만 WHERE 조건절이 없는 경우에는 테이블의 모든 레코드를 삭제한다.