void GeomTree::RayTriIntersect(int numRays, const vector3f &origin, const vector3f *dirs, int triIdx, isect_t *isects) const
{
	const vector3f a(m_vertices[m_indices[triIdx+0]]);
	const vector3f b(m_vertices[m_indices[triIdx+1]]);
	const vector3f c(m_vertices[m_indices[triIdx+2]]);

	vector3f v0_cross, v1_cross, v2_cross;
	const vector3f n = (c-a).Cross(b-a);
	const float nominator = n.Dot(a-origin);

	v0_cross = (c-origin).Cross(b-origin);
	v1_cross = (b-origin).Cross(a-origin);
	v2_cross = (a-origin).Cross(c-origin);

	for (int i=0; i<numRays; i++) {
		const float v0d = v0_cross.Dot(dirs[i]);
		const float v1d = v1_cross.Dot(dirs[i]);
		const float v2d = v2_cross.Dot(dirs[i]);

		if (((v0d > 0) && (v1d > 0) && (v2d > 0)) ||
			 ((v0d < 0) && (v1d < 0) && (v2d < 0))) {
			const float dist = nominator / dirs[i].Dot(n);
			if ((dist > 0) && (dist < isects[i].dist)) {
				isects[i].dist = dist;
				isects[i].triIdx = triIdx/3;
			}
		}
	}
}

void SectorView::DrawFarSectors(matrix4x4f modelview)
{
	int buildRadius = ceilf((m_zoomClamped/FAR_THRESHOLD) * 3);
	if (buildRadius <= DRAW_RAD) buildRadius = DRAW_RAD;

	const vector3f secOrigin = vector3f(int(floorf(m_pos.x)), int(floorf(m_pos.y)), int(floorf(m_pos.z)));

	// build vertex and colour arrays for all the stars we want to see, if we don't already have them
	if (m_toggledFaction || buildRadius != m_radiusFar || !secOrigin.ExactlyEqual(m_secPosFar)) {
		m_farstars       .clear();
		m_farstarsColor  .clear();
		m_visibleFactions.clear();

		for (int sx = secOrigin.x-buildRadius; sx <= secOrigin.x+buildRadius; sx++) {
			for (int sy = secOrigin.y-buildRadius; sy <= secOrigin.y+buildRadius; sy++) {
				for (int sz = secOrigin.z-buildRadius; sz <= secOrigin.z+buildRadius; sz++) {
						if ((vector3f(sx,sy,sz) - secOrigin).Length() <= buildRadius){
							BuildFarSector(GetCached(sx, sy, sz), Sector::SIZE * secOrigin, m_farstars, m_farstarsColor);
						}
					}
				}
			}

		m_secPosFar      = secOrigin;
		m_radiusFar      = buildRadius;
		m_toggledFaction = false;
	}

	// always draw the stars, slightly altering their size for different different resolutions, so they still look okay
	if (m_farstars.size() > 0)
		m_renderer->DrawPoints(m_farstars.size(), &m_farstars[0], &m_farstarsColor[0], 1.f + (Graphics::GetScreenHeight() / 720.f));

	// also add labels for any faction homeworlds among the systems we've drawn
	PutFactionLabels(Sector::SIZE * secOrigin);
}

float vAngleCos (vector3f v1, vector3f v2)
{
	if ((v1.vModulo() != 0) && (v2.vModulo() != 0)) {
		return((v1.x*v2.x + v1.y*v2.y + v1.z*v2.z)/(v1.vModulo() * v2.vModulo()));
	}
	else
		return 0;
}

void LOD::Render(Graphics::Renderer *renderer, const matrix4x4f &trans, RenderData *rd)
{
	//figure out approximate pixel size on screen and pick a child to render
	const vector3f cameraPos(-trans[12], -trans[13], -trans[14]);
	const float pixrad = 0.5f * Graphics::GetScreenWidth() * rd->boundingRadius / cameraPos.Length();
	assert(m_children.size() == m_pixelSizes.size());
	if (m_pixelSizes.empty()) return;
	unsigned int lod = m_children.size() - 1;
	for (unsigned int i=m_pixelSizes.size(); i > 0; i--) {
		if (pixrad < m_pixelSizes[i-1]) lod = i-1;
	}
	m_children[lod]->Render(renderer, trans, rd);
}

	void Camera::lookAt(const vector3f &refPos, const vector3f &upVector)
	{
		front = refPos.normalized();
		up = upVector.normalized();
		vector3f s = cross(front, up);
		vector3f u = cross(s, front);
		view = matrix4f(
						s.x, u.x, -front.x, 0,
						s.y, u.y, -front.y, 0,
						s.z, u.z, -front.z, 0,
						0, 0, 0, 1
						);
	}

void LOD::Render(const matrix4x4f &trans, const RenderData *rd)
{
	//figure out approximate pixel size of object's bounding radius
	//on screen and pick a child to render
	const vector3f cameraPos(-trans[12], -trans[13], -trans[14]);
	//fov is vertical, so using screen height
	const float pixrad = Graphics::GetScreenHeight() * rd->boundingRadius / (cameraPos.Length() * Graphics::GetFovFactor());
	if (m_pixelSizes.empty()) return;
	unsigned int lod = m_children.size() - 1;
	for (unsigned int i=m_pixelSizes.size(); i > 0; i--) {
		if (pixrad < m_pixelSizes[i-1]) lod = i-1;
	}
	m_children[lod]->Render(trans, rd);
}

matrix4x4 matrix4x4::rotation_around_axis(vector3f const& axis, float const radians)
{
	vector3f axis_normalized{axis.normalized()};

	float const cos_value{std::cos(radians)};
	float const sin_value{std::sin(radians)};

	return matrix4x4{
		axis_normalized.x * axis_normalized.x * (1.0f - cos_value) + cos_value,
		axis_normalized.x * axis_normalized.y * (1.0f - cos_value) + axis_normalized.z * sin_value,
		axis_normalized.x * axis_normalized.z * (1.0f - cos_value) - axis_normalized.y * sin_value,
		0.0f,

		axis_normalized.x * axis_normalized.y * (1.0f - cos_value) - axis_normalized.z * sin_value,
		axis_normalized.y * axis_normalized.y * (1.0f - cos_value) + cos_value,
		axis_normalized.y * axis_normalized.z * (1.0f - cos_value) + axis_normalized.x * sin_value,
		0.0f,

		axis_normalized.x * axis_normalized.z * (1.0f - cos_value) + axis_normalized.y * sin_value,
		axis_normalized.y * axis_normalized.z * (1.0f - cos_value) - axis_normalized.x * sin_value,
		axis_normalized.z * axis_normalized.z * (1.0f - cos_value) + cos_value,
		0.0f,

		0.0f,
		0.0f,
		0.0f,
		1.0f};
}

int myMath::AABBPlaneIntersection(const vector3f &min,const vector3f &max, const vector3f &normal, const vector3f &vec){
	float d = vec.dotProduct(normal);
	float minD, maxD;

	if(normal.x > 0.0f){
		minD = normal.x*min.x; maxD = normal.x*max.x;}
	else{
		minD = normal.x*max.x; maxD = normal.x*min.x;}

	if(normal.y > 0.0f){
		minD += normal.y*min.y; maxD += normal.y*max.y;}
	else{
		minD += normal.y*max.y; maxD += normal.y*min.y;}

	if(normal.z > 0.0f){
		minD += normal.z*min.z; maxD += normal.z*max.z;}
	else{
		minD += normal.z*max.z; maxD += normal.z*min.z;}

	if(minD >= d)
		return +1;
	if(maxD <= d)
		return -1;
	return 0;
}

void matrix4x4f::rotate(const float angle, vector3f axis) {

    float s = sin(DEGTORAD(angle));
    float c = cos(DEGTORAD(angle));

    axis.normalize();

    float ux = axis.x;
    float uy = axis.y;
    float uz = axis.z;
    
    m[0]  = c + (1-c) * ux;
    m[1]  = (1-c) * ux*uy + s*uz;
    m[2]  = (1-c) * ux*uz - s*uy;
    m[3]  = 0;
    
    m[4]  = (1-c) * uy*ux - s*uz;
    m[5]  = c + (1-c) * pow(uy,2);
    m[6]  = (1-c) * uy*uz + s*ux;
    m[7]  = 0;
    
    m[8]  = (1-c) * uz*ux + s*uy;
    m[9]  = (1-c) * uz*uz - s*ux;
    m[10] = c + (1-c) * pow(uz,2);
    m[11] = 0;
    
    m[12] = 0;
    m[13] = 0;
    m[14] = 0;
    m[15] = 1;

}

void LOD::Render(const std::vector<matrix4x4f> &trans, const RenderData *rd)
{
	// anything to draw?
	if (m_pixelSizes.empty()) 
		return;

	// got something to draw with
	Graphics::Renderer *r = GetRenderer();
	if ( r!=nullptr )
	{
		const size_t count = m_pixelSizes.size();
		const size_t tsize = trans.size();

		// transformation buffers
		std::vector< std::vector<matrix4x4f> > transform;
		transform.resize(count);
		for (Uint32 i = 0; i<count; i++) {
			transform[i].reserve(tsize);
		}

		// seperate out the transformations
		for (auto mt : trans)
		{
			//figure out approximate pixel size of object's bounding radius
			//on screen and pick a child to render
			const vector3f cameraPos(-mt[12], -mt[13], -mt[14]);
			//fov is vertical, so using screen height
			const float pixrad = Graphics::GetScreenHeight() * rd->boundingRadius / (cameraPos.Length() * Graphics::GetFovFactor());
			unsigned int lod = m_children.size() - 1;
			for (unsigned int i = m_pixelSizes.size(); i > 0; i--) {
				if (pixrad < m_pixelSizes[i - 1]) {
					lod = i - 1;
				}
			}

			transform[lod].push_back(mt);
		}

		// now render each of the buffers for each of the lods
		for (Uint32 inst = 0; inst < transform.size(); inst++) {
			if (!transform[inst].empty()) {
				m_children[inst]->Render(transform[inst], rd);
			}
		}
	}
}

camera::camera(
	vector3f const& position,
	vector3f const& forward,
	vector3f const& fake_up,
	float const horizontal_fov,
	float const aspect_ratio,
	float const near_plane_z,
	float const far_plane_z)
	: m_position{position},
	  m_forward{forward.normalized()},
	  m_horizontal_fov{horizontal_fov},
	  m_vertical_fov{horizontal_fov * aspect_ratio},
	  m_aspect_ratio{aspect_ratio},
	  m_near_plane_z{near_plane_z},
	  m_far_plane_z{far_plane_z}
{
	establish_coordinate_system(fake_up.normalized());
}

void camera::establish_coordinate_system(vector3f const& fake_up)
{
	// fake_up vector does not represent the up vector itself
	// It might be different - together with m_forward it represents the plane where the correct up vector should be
	// So we use it to calculate right vector and then fix it
	//

	m_right = fake_up.cross(m_forward).normalized();
	m_up = m_forward.cross(m_right).normalized();
}

/**
 * Draws a horizontal line from (x1, y) to (x2, y) with color interpolation
 */
void gradient_line(float x1, vector3f c1, float x2, vector3f c2, int y) {
    if (x1 > x2) {
        swap(x1, x2);
        swap(c1, c2);
    }
    vector3f dc = (c2 - c1)/(x2 - x1);
    for (int x = x1; x <= x2; x++) {
            al_put_pixel(x, y, c1.as_color());
            c1 += dc;
    }
}

 ray::ray(vector3f const & origin, vector3f const & direction)
 : origin_(origin), direction_(direction.unitized())
 {}

 //! @brief 光の方向を設定する
 void direction(vector3f const &v){
     direction(v.x(), v.y(), v.z());
 }

void Camera::Draw(Renderer *renderer, const Body *excludeBody)
{
	if (!m_camFrame) return;
	if (!renderer) return;

	m_renderer = renderer;

	glPushAttrib(GL_ALL_ATTRIB_BITS & (~GL_POINT_BIT));

	m_renderer->SetPerspectiveProjection(m_fovAng, m_width/m_height, m_zNear, m_zFar);
	m_renderer->SetTransform(matrix4x4f::Identity());
	m_renderer->ClearScreen();

	matrix4x4d trans2bg;
	Frame::GetFrameRenderTransform(Pi::game->GetSpace()->GetRootFrame(), m_camFrame, trans2bg);
	trans2bg.ClearToRotOnly();

	// Pick up to four suitable system light sources (stars)
	m_lightSources.clear();
	m_lightSources.reserve(4);
	position_system_lights(m_camFrame, Pi::game->GetSpace()->GetRootFrame(), m_lightSources);

	if (m_lightSources.empty()) {
		// no lights means we're somewhere weird (eg hyperspace). fake one
		const Color col(1.f);
		m_lightSources.push_back(LightSource(0, Graphics::Light(Graphics::Light::LIGHT_DIRECTIONAL, vector3f(0.f), col, col)));
	}

	//fade space background based on atmosphere thickness and light angle
	float bgIntensity = 1.f;
	if (m_camFrame->GetParent() && m_camFrame->GetParent()->IsRotFrame()) {
		//check if camera is near a planet
		Body *camParentBody = m_camFrame->GetParent()->GetBody();
		if (camParentBody && camParentBody->IsType(Object::PLANET)) {
			Planet *planet = static_cast<Planet*>(camParentBody);
			const vector3f relpos(planet->GetInterpPositionRelTo(m_camFrame));
			double altitude(relpos.Length());
			double pressure, density;
			planet->GetAtmosphericState(altitude, &pressure, &density);
			if (pressure >= 0.001)
			{
				//go through all lights to calculate something resembling light intensity
				float angle = 0.f;
				for(std::vector<LightSource>::const_iterator it = m_lightSources.begin();
					it != m_lightSources.end(); ++it) {
					const vector3f lightDir(it->GetLight().GetPosition().Normalized());
					angle += std::max(0.f, lightDir.Dot(-relpos.Normalized())) * it->GetLight().GetDiffuse().GetLuminance();
				}
				//calculate background intensity with some hand-tweaked fuzz applied
				bgIntensity = Clamp(1.f - std::min(1.f, powf(density, 0.25f)) * (0.3f + powf(angle, 0.25f)), 0.f, 1.f);
			}
		}
	}

	Pi::game->GetSpace()->GetBackground().SetIntensity(bgIntensity);
	Pi::game->GetSpace()->GetBackground().Draw(renderer, trans2bg);

	{
		std::vector<Graphics::Light> rendererLights;
		for (size_t i = 0; i < m_lightSources.size(); i++)
			rendererLights.push_back(m_lightSources[i].GetLight());
		renderer->SetLights(rendererLights.size(), &rendererLights[0]);
	}

	for (std::list<BodyAttrs>::iterator i = m_sortedBodies.begin(); i != m_sortedBodies.end(); ++i) {
		BodyAttrs *attrs = &(*i);

		// explicitly exclude a single body if specified (eg player)
		if (attrs->body == excludeBody)
			continue;

		double rad = attrs->body->GetClipRadius();
		if (!m_frustum.TestPointInfinite((*i).viewCoords, rad))
			continue;

		// draw spikes for far objects
		double screenrad = 500 * rad / attrs->camDist;      // approximate pixel size
		if (attrs->body->IsType(Object::PLANET) && screenrad < 2) {
			// absolute bullshit
			double spikerad = (7 + 1.5*log10(screenrad)) * rad / screenrad;
			DrawSpike(spikerad, attrs->viewCoords, attrs->viewTransform);
		}
		else if (screenrad >= 2 || attrs->body->IsType(Object::STAR) ||
					(attrs->body->IsType(Object::PROJECTILE) && screenrad > 0.25))
			attrs->body->Render(renderer, this, attrs->viewCoords, attrs->viewTransform);
	}

	Sfx::RenderAll(renderer, Pi::game->GetSpace()->GetRootFrame(), m_camFrame);

	m_frame->RemoveChild(m_camFrame);
	delete m_camFrame;
	m_camFrame = 0;

	glPopAttrib();
}

void SectorView::DrawNearSector(int sx, int sy, int sz, const vector3f &playerAbsPos,const matrix4x4f &trans)
{
	m_renderer->SetTransform(trans);
	Sector* ps = GetCached(sx, sy, sz);

	int cz = int(floor(m_pos.z+0.5f));

	if (cz == sz) {
		const Color darkgreen(0.f, 0.2f, 0.f, 1.f);
		const vector3f vts[] = {
			vector3f(0.f, 0.f, 0.f),
			vector3f(0.f, Sector::SIZE, 0.f),
			vector3f(Sector::SIZE, Sector::SIZE, 0.f),
			vector3f(Sector::SIZE, 0.f, 0.f)
		};

		m_renderer->DrawLines(4, vts, darkgreen, LINE_LOOP);
	}

	Uint32 sysIdx = 0;
	for (std::vector<Sector::System>::iterator i = ps->m_systems.begin(); i != ps->m_systems.end(); ++i, ++sysIdx) {
		// calculate where the system is in relation the centre of the view...
		const vector3f sysAbsPos = Sector::SIZE*vector3f(float(sx), float(sy), float(sz)) + (*i).p;
		const vector3f toCentreOfView = m_pos*Sector::SIZE - sysAbsPos;

		// ...and skip the system if it doesn't fall within the sphere we're viewing.
		if (toCentreOfView.Length() > OUTER_RADIUS) continue;

		// if the system is the current system or target we can't skip it
		bool can_skip = !i->IsSameSystem(m_selected)
						&& !i->IsSameSystem(m_hyperspaceTarget)
						&& !i->IsSameSystem(m_current);

		// if the system belongs to a faction we've chosen to temporarily hide
		// then skip it if we can
		m_visibleFactions.insert(i->faction);
		if (m_hiddenFactions.find(i->faction) != m_hiddenFactions.end() && can_skip) continue;

		// determine if system in hyperjump range or not
		Sector *playerSec = GetCached(m_current.sectorX, m_current.sectorY, m_current.sectorZ);
		float dist = Sector::DistanceBetween(ps, sysIdx, playerSec, m_current.systemIndex);
		bool inRange = dist <= m_playerHyperspaceRange;

		// don't worry about looking for inhabited systems if they're
		// unexplored (same calculation as in StarSystem.cpp) or we've
		// already retrieved their population.
		if ((*i).population < 0 && isqrt(1 + sx*sx + sy*sy + sz*sz) <= 90) {

			// only do this once we've pretty much stopped moving.
			vector3f diff = vector3f(
					fabs(m_posMovingTo.x - m_pos.x),
					fabs(m_posMovingTo.y - m_pos.y),
					fabs(m_posMovingTo.z - m_pos.z));

			// Ideally, since this takes so f'ing long, it wants to be done as a threaded job but haven't written that yet.
			if( (diff.x < 0.001f && diff.y < 0.001f && diff.z < 0.001f) ) {
				SystemPath current = SystemPath(sx, sy, sz, sysIdx);
				RefCountedPtr<StarSystem> pSS = StarSystem::GetCached(current);
				(*i).population = pSS->GetTotalPop();
			}

		}

		matrix4x4f systrans = trans * matrix4x4f::Translation((*i).p.x, (*i).p.y, (*i).p.z);
		m_renderer->SetTransform(systrans);

		// for out-of-range systems draw leg only if we draw label
		if (m_drawSystemLegButton->GetPressed()
			&& (inRange || m_drawOutRangeLabelButton->GetPressed()) || !can_skip){

			const Color light(0.5f);
			const Color dark(0.2f);

			// draw system "leg"
			float z = -(*i).p.z;
			if (sz <= cz)
				z = z+abs(cz-sz)*Sector::SIZE;
			else
				z = z-abs(cz-sz)*Sector::SIZE;
			m_lineVerts->Add(systrans * vector3f(0.f, 0.f, z), light);
			m_lineVerts->Add(systrans * vector3f(0.f, 0.f, z * 0.5f), dark);
			m_lineVerts->Add(systrans * vector3f(0.f, 0.f, z * 0.5f), dark);
			m_lineVerts->Add(systrans * vector3f(0.f, 0.f, 0.f), light);

			//cross at other end
			m_lineVerts->Add(systrans * vector3f(-0.1f, -0.1f, z), light);
			m_lineVerts->Add(systrans * vector3f(0.1f, 0.1f, z), light);
			m_lineVerts->Add(systrans * vector3f(-0.1f, 0.1f, z), light);
			m_lineVerts->Add(systrans * vector3f(0.1f, -0.1f, z), light);
		}

		if (i->IsSameSystem(m_selected)) {
			m_jumpLine.SetStart(vector3f(0.f, 0.f, 0.f));
			m_jumpLine.SetEnd(playerAbsPos - sysAbsPos);
			m_jumpLine.Draw(m_renderer);
		}

		// draw star blob itself
		systrans.Rotate(DEG2RAD(-m_rotZ), 0, 0, 1);
		systrans.Rotate(DEG2RAD(-m_rotX), 1, 0, 0);
//.........这里部分代码省略.........

 //! @brief 光源の位置を設定する
 void posision(vector3f const &v){
     posision(v.x(), v.y(), v.z());
 }

void initialize()
{
    eye.set(1.5,1.5,1.5);

    fAspect = (GLfloat)WINDOW_WIDTH/(GLfloat)WINDOW_HEIGHT;

    GLfloat angleUp = 0;
    GLfloat angleDown = 0;
    GLfloat angleLeft = 0;
    GLfloat angleRight = 0;
}