// 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 2
// 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, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
#include "bsp_node.h"
#include "mesh.h"
#include "surface_point.h"
using namespace c3ga;
bsp_node::bsp_node() :
m_backside_node(NULL),
m_frontside_node(NULL) {
}
bsp_node::bsp_node(const std::vector<int> &face) : m_face(face),
m_backside_node(NULL),
m_frontside_node(NULL) {
}
bsp_node::bsp_node(const plane &pl, bsp_node *backside, bsp_node *frontside) :
m_pl(pl),
m_backside_node(backside),
m_frontside_node(frontside) {
}
bsp_node::bsp_node(const bsp_node &b) : m_face(b.m_face),
m_pl(b.m_pl),
m_backside_node( (b.m_backside_node) ? new bsp_node(*b.m_backside_node) : NULL),
m_frontside_node( (b.m_frontside_node) ? new bsp_node(*b.m_frontside_node) : NULL) {
}
bsp_node::~bsp_node() {
if (m_backside_node) delete m_backside_node;
if (m_frontside_node) delete m_frontside_node;
}
bsp_node &bsp_node::operator=(const bsp_node &b) {
if (this != &b) {
m_face = b.m_face;
m_pl = b.m_pl;
m_backside_node = (b.m_backside_node) ? new bsp_node(*b.m_backside_node) : NULL;
m_frontside_node = (b.m_frontside_node) ? new bsp_node(*b.m_frontside_node) : NULL;
}
return *this;
}
bool bsp_node::find_intersection_leaf(bsp_descent_info &di) const {
if (di.find_closest) {
bool intersection_found = false;
for (unsigned int i = 0; i < m_face.size(); i++) {
if (di.m->get_face(m_face[i]).find_intersection(di.ray_dual_plane, di.ray_dual_line, di.spt, true)) {
intersection_found = true;
di.spt.set_face_idx(m_face[i]);
}
}
return intersection_found;
}
else {
for (unsigned int i = 0; i < m_face.size(); i++)
if (di.m->get_face(m_face[i]).find_intersection(di.ray_dual_plane, di.ray_dual_line, di.spt, false))
return true;
return false;
}
}
bool bsp_node::find_intersection_internal(bsp_descent_info &di) const {
// determine which of the two child nodes we should visit
mv::Float sd1 = -_Float((dual(m_pl) << di.fpt1) & ni);
mv::Float sd2 = -_Float((dual(m_pl) << di.fpt2) & ni);
if (sd1 * sd2 < 0.0) { // line segment intersects the partition plane
// compute intersection point of ray and partition plane
normalizedFlatPoint fptx = _normalizedFlatPoint((di.ray_dual_line << m_pl) * (1.0f / _float((noni) % (di.ray_dual_line << m_pl))));
// compute distance of intersection point to ray start:
mv::Float dx = -_Float(no << (di.ray_dual_plane << fptx));
// check if intersection point is still 'in' the line segment (redundant??)
if ((dx < di.d1) || (dx > di.d2))
return false;
if (sd1 < 0.0) {
normalizedFlatPoint tmp_fpt = di.fpt2;
mv::Float tmp_d = di.d2;
// visit the partition with di.fpt1 in it, because that's closest to the ray start
di.fpt2 = fptx;
di.d2 = dx;
if (m_backside_node->find_intersection(di)) return true;
// if no intersection found, search the other partition
di.fpt1 = fptx; di.d1 = dx;
di.fpt2 = tmp_fpt; di.d2 = tmp_d;
return m_frontside_node->find_intersection(di);
}
else {
normalizedFlatPoint tmp_fpt = di.fpt2;
mv::Float tmp_d = di.d2;
// visit the partition if di.fpt1 in it, because that's closest to the ray start
di.fpt2 = fptx;
di.d2 = dx;
if (m_frontside_node->find_intersection(di)) return true;
// if no intersection found, search the other partition
di.fpt1 = fptx; di.d1 = dx;
di.fpt2 = tmp_fpt; di.d2 = tmp_d;
return m_backside_node->find_intersection(di);
}
}
else if ((sd1 < 0.0) || (sd2 < 0.0)) { // line segment is entirely on the back side of the plane
return m_backside_node->find_intersection(di);
}
else if ((sd1 > 0.0) || (sd2 > 0.0)) { // line segment is entirely on the front side of the plane
return m_frontside_node->find_intersection(di);
}
else { // line segment lies in the plane
return (m_backside_node->find_intersection(di) ||
m_frontside_node->find_intersection(di));
}
}
void bsp_node::visit_bsp_node(const mesh *m, const normalizedFlatPoint &fpt) const {
mv::Float sd = -_Float(no << (dual(m_pl) << fpt));
if ((m_frontside_node) && (sd >= 0.0)) m_frontside_node->visit_bsp_node(m, fpt);
if ((m_backside_node) && (sd <= 0.0)) m_backside_node->visit_bsp_node(m, fpt);
}
void bsp_node::insert_face(int face_idx, const std::vector<normalizedFlatPoint> &vertex) {
if (m_frontside_node == NULL) {
m_face.push_back(face_idx);
return;
}
// check on what side of the plane the vertices are
std::vector<mv::Float> sd(vertex.size());
int nbCut = 0; // number of cuts (0, 1, 2, or, if > 2, face has a 'degenerate' position w.r.t. partition plane
for (unsigned int i = 0; i < vertex.size(); i++) {
sd[i] = _Float(no << (dual(m_pl) << vertex[i]));
// update the number of cuts:
if (sd[i] == 0.0) nbCut++; // vertex lies in partition plane
else if (i && (sd[i] * sd[i-1] < 0.0)) nbCut++; // edge intersects partition plane
if ((i == ( vertex.size()-1)) && (sd[i] * sd[0] < 0.0)) nbCut++; // edge n-1 -> 0 intersects partition plane
}
if (nbCut < 2) {
// face is not cut, so simply insert it into the corresponding child node:
for (unsigned int i = 0; i < vertex.size(); i++) {
// we must loop since the first child could be
if (sd[i] < 0.0) {
m_backside_node->insert_face(face_idx, vertex);
return;
}
else if (sd[i] > 0.0) {
m_frontside_node->insert_face(face_idx, vertex);
return;
}
}
return; // should never happen, it is just to prevent the compiler from complaining.
}
else if (nbCut > 2) {
// the face lies _in_ the partition plane, so insert it into both child nodes:
m_frontside_node->insert_face(face_idx, vertex);
m_backside_node->insert_face(face_idx, vertex);
return;
}
else { // number of cuts == 2
// the face must be cut into two halves:
std::vector<c3ga::normalizedFlatPoint> front_vertices;
std::vector<c3ga::normalizedFlatPoint> back_vertices;
// handle all vertices up to the first intersection:
for (unsigned int i = 0; i <= vertex.size(); i++) {
if ((i < vertex.size()) && (sd[i] == 0.0)) {
front_vertices.push_back(vertex[i]);
back_vertices.push_back(vertex[i]);
}
else {
unsigned int j = i % vertex.size();
if (i && (sd[j] * sd[i-1] < 0.0)) {
// intersect edge -> interpolate vertices
mv::Float wi = fabs(sd[i-1]) / (fabs(sd[j]) + fabs(sd[i-1]));
mv::Float wim1 = fabs(sd[j]) / (fabs(sd[j]) + fabs(sd[i-1]));
normalizedFlatPoint I = _normalizedFlatPoint(wi * vertex[j] + wim1 * vertex[i-1]);
back_vertices.push_back(I);
front_vertices.push_back(I);
}
if (i == vertex.size()) break; // terminate loop here, before we try to insert vertex[vertex.size()]!
// insert vertex[i]
if (sd[i] < 0.0) back_vertices.push_back(vertex[i]);
else front_vertices.push_back(vertex[i]);
}
}
/*
Insert the face in the child nodes.
But keep in mind that we still have to
check the number of vertices. It could be the case
that two vertices happened lie in the partition plane!
*/
if (back_vertices.size() > 2) m_backside_node->insert_face(face_idx, back_vertices);
if (front_vertices.size() > 2) m_frontside_node->insert_face(face_idx, front_vertices);
}
}