winding.cpp

3D游戏开发需要用到BSP树来经行场景渲染的管理。本代码包含完整的BSP及文件生成实现

/*
	This file is part of rmapc - a fast BSP map compiler.

    Copyright (C) 2008 Rouslan Dimitrov

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "winding.h"
#include "memcopy.h"

void CWinding::CreateBaseWinding(vec4 *plane) {
	int	small_axis = 0;
	vec4 up, right;
	vec4 normal = plane->normal();
	float dist = plane->dist();

	vec4 p = normal * (-dist);
	p.w = 1.0f;

	vec4 abs_normal = fabs4(&normal);

	if(abs_normal.y < abs_normal.x)
		small_axis++;
	if(abs_normal.z < abs_normal.x && abs_normal.z < abs_normal.y)
		small_axis = 2;

	right.clear();
	right[small_axis] = 1.0f;
	
	float right_dot_normal = normal[small_axis];
	right -= right_dot_normal*normal;
	right.normalize();
	up = normal.cross3D(right);

	float half_world = 0.5f * WORLD_SIZE;

	points.Reserve(4);
	points[0] = p - half_world*(right - up);
	points[1] = p - half_world*(right + up);
	points[2] = p + half_world*(right - up);
	points[3] = p + half_world*(right + up);
	
	points.SetNum(4);
}

void CWinding::ChopWinding(vec4 *plane) {
	int			npoints = points.GetNum();

	if(!npoints || npoints > 2*MAX_WINDING_POINTS/3)
		return;

	vec4		new_points[MAX_WINDING_POINTS];
	int			pos = 0;

	vec4 prev_p = points[npoints - 1];
	int prev_side = plane->side(prev_p);

	for(int i = 0; i < npoints; i++) {
		vec4 p = points[i];
		int side = plane->side(p);

		switch(prev_side) {
			case P_FRONT:
				if(side == P_BACK)
					new_points[pos++] = plane->lineIntersect(prev_p, p);
				else
					new_points[pos++] = p;
				break;
			case P_BACK:
				if(side == P_FRONT) {
					new_points[pos++] = plane->lineIntersect(prev_p, p);
					new_points[pos++] = p;
				}else if(side == P_ON)
					new_points[pos++] = p;
				break;
			case P_ON:
				if(side != P_BACK)
					new_points[pos++] = p;
				break;
		}
		prev_p = p;
		prev_side = side;
	}

	// if winding has only 1 side on the plane and the other sides behind,
	// then it is discarded.
	if(pos < 3 && npoints >= 3) {
		points.Clear();
	} else {
		points.SetNum(pos);
		MemCopy(points.GetData(), new_points, pos*sizeof(vec4));
	}
}

// if winding is coinciding with plane, then it is added to both front and back
void CWinding::SplitWinding(CWinding &front, vec4* plane) {
	front = *this;
	front.ChopWinding(plane);

	vec4 rev_plane = reverse4(plane);
	ChopWinding(&rev_plane);
}

void CWinding::OnSide(sPlane *plane, int *sides) {
	for(int i = 0; i < 3; i++)
		sides[i] = 0;

	for(int i = 0; i < points.GetNum(); i++)
		sides[ plane->side(points[i]) ] ++;
}

int CWinding::OnSide(sPlane *plane) {
	int sides[3] = {0,0,0};

	for(int i = 0; i < points.GetNum(); i++)
		sides[ plane->side(points[i]) ] ++;

	if(sides[P_FRONT] > 0)
		if(sides[P_BACK] > 0)
			return P_CROSS;
		else
			return P_FRONT;
	else if(sides[P_BACK] > 0)
		return P_BACK;

	return P_ON;
}

float CWinding::Area() {
	float area = 0.0f;
	for(int i=2; i<points.GetNum(); i++) {
		vec4 v1 = points[i-1] - points[0];
		vec4 v2 = points[i] - points[0];
		area += v1.cross3D(v2).magnitude();
	}
	return 0.5f*area;
}

void CWinding::AddPointToConvexHull(vec4 *point, sPlane *plane) {

	const int	npoints = points.GetNum();

	// FIXME: variable length arrays in VC++ ?
	vec4		new_points[MAX_WINDING_POINTS];
	int			state[MAX_WINDING_POINTS];
	int			pos = 0;

	if(npoints < 2) {
		points.Append(*point);
		return;
	}

	if(npoints > MAX_WINDING_POINTS - 1) {
		g_CLog.Log(LOG_SYSTEM, "AddPointToConvexHull: Too many points already - %d.", npoints);
		return;
	}

	for(int i=0; i<npoints; i++) {
		vec4	dir = points[(i+1)%npoints] - points[i];
		dir.normalize();
		vec4	normal = dir.cross3D(*plane);
		vec4	dir2 = *point - points[i];

		state[i] = normal.side(dir2);
	}

	for(int i=0; i<npoints; i++) {
		switch(state[i]) {
			case P_BACK:
				new_points[pos++] = points[i];
				break;

			case P_FRONT:
				switch(state[(i-1+npoints)%npoints]) {
					case P_BACK:
						new_points[pos++] = points[i];
						new_points[pos++] = *point;
						break;
					case P_ON:
						new_points[pos++] = *point;
						break;
				}
				break;

			case P_ON:
				if(state[(i-1+npoints)%npoints] != P_FRONT)
					new_points[pos++] = points[i];
				break;
		}
	}

	points.SetNum(pos);
	MemCopy(points.GetData(), new_points, pos*sizeof(vec4));
}

void CWinding::AddWindingToConvexHull(CWinding *w) {
	CAlignedVec<vec4>	*p = w->GetPoints();

	if(p->GetNum() < 3)
		return;

	vec4 v1 = p->GetElemNoBCheck(1) - p->GetElemNoBCheck(0);
	vec4 v2 = p->GetElemNoBCheck(2) - p->GetElemNoBCheck(0);
	vec4 plane = v1.cross3D(v2);

	AddWindingToConvexHull(w, &plane);
}

// O(this->n * w->n)
void CWinding::AddWindingToConvexHull(CWinding *w, sPlane *plane) {
	CAlignedVec<vec4> *wp = w->GetPoints();

	for(int i=0; i<wp->GetNum(); i++) {
		vec4 *point = &wp->GetElemNoBCheck(i);

		AddPointToConvexHull(point, plane);
	}
}