// 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 <algorithm>
#include "mesh.h"
#include "bsp_node.h"
#include "c3ga_util.h"
#include "c3ga.h"
#include "surface_point.h"
#include "ray.h"
using namespace c3ga;
mesh::mesh() {
m_bsp_node = NULL;
}
mesh::mesh(const mesh &m) : m_vertex(m.m_vertex),
m_face(m.m_face),
m_bounding_sphere(m.m_bounding_sphere),
m_bsp_node((m.m_bsp_node) ? new bsp_node(*m.m_bsp_node) : NULL),
m_filename(m.m_filename) {
}
mesh::~mesh() {
if (m_bsp_node) delete m_bsp_node;
}
mesh &mesh::operator=(const mesh &m) {
if (this != &m) {
m_vertex = m.m_vertex;
m_face = m.m_face;
m_bounding_sphere = m.m_bounding_sphere;
m_filename = m.m_filename;
m_bsp_node = (m.m_bsp_node) ? new bsp_node(*m.m_bsp_node) : NULL;
}
return *this;
}
void mesh::set_vertex(int idx, const vertex &v) {
if ((idx < 0) || (idx >= (int)m_vertex.size()))
throw std::string("mesh::set_vertex(): index out of range");
m_vertex[idx] = v;
}
void mesh::set_face(int idx, const face &f) {
if ((idx < 0) || (idx >= (int)m_face.size()))
throw std::string("mesh::set_face(): index out of range");
m_face[idx] = f;
}
void mesh::set_filename(const std::string &s) {
m_filename = s;
}
void mesh::init() {
init_faces();
compute_bounding_sphere();
construct_bsp_tree();
compute_local_texture_basis();
}
void mesh::init_faces() {
// compute the constants:
{
for (unsigned int i = 0; i < m_face.size(); i++)
m_face[i].precompute_constants(*this);
}
// remove faces that have no surface area (these occur sometimes in certain models)
{
for (unsigned int i = 0; i < m_face.size(); i++)
if (-_Float(norm_r2(m_face[i].get_pl())) <= 0.0) {
/*
m_face[i] has no surface area:
Move last face of the vector to this position,
downsize the vector, and decrease 'i' by one
so m_face[i] get's processed again
*/
m_face[i] = m_face[m_face.size()-1];
m_face.resize(m_face.size()-1);
i--;
}
}
}
void mesh::compute_bounding_sphere() {
unsigned int i;
/*
Compute the center of the bounding sphere:
-create three orthogonal planes through the origin:
-compute minimal and maximal signed distance of each
vertex to these planes
*/
dualPlane pld[3] = {
_dualPlane(dual(no ^ e2 ^ e3 ^ ni)),
_dualPlane(dual(no ^ e3 ^ e1 ^ ni)),
_dualPlane(dual(no ^ e1 ^ e2 ^ ni))
};
mv::Float minDist[3] = {1e10, 1e10, 1e10};
mv::Float maxDist[3] = {-1e10, -1e10, -1e10};
for (i = 0; i < m_vertex.size(); i++) {
for (int j = 0; j < 3; j++) {
minDist[j] = std::min( _Float(pld[j] % m_vertex[i].get_pt()) , minDist[j]);
maxDist[j] = std::max( _Float(pld[j] % m_vertex[i].get_pt()), maxDist[j]);
}
}
/*
Compute the center 'c' of the bounding sphere.
*/
normalizedPoint center = cga_point(_vectorE3GA(
0.5f * (minDist[0] + maxDist[0]) * pld[0] +
0.5f * (minDist[1] + maxDist[1]) * pld[1] +
0.5f * (minDist[2] + maxDist[2]) * pld[2]));
/*
Compute the required radius 'r' (actually, -r^2/2) of the bounding sphere:
*/
mv::Float r = 0.0;
for (i = 0; i < m_vertex.size(); i++)
r = std::min(_Float(m_vertex[i].get_pt() % center), r);
/*
Construct the bounding dual sphere:
*/
m_bounding_sphere = _normalizedDualSphere(center + r * ni);
// printf("S = %s,\n", c3ga::string(m_bounding_sphere, "%f"));
}
namespace { // anonymous namspace
// function used with qsort for sorting bsp_sort_data
// TODO: use C++ std lib sort() template . . .
int construct_bsp_tree_sort(const void *v1, const void *v2) {
struct bsp_sort_data *d1 = (struct bsp_sort_data *)v1, *d2 = (struct bsp_sort_data *)v2;
if (d1->signed_distance < d2->signed_distance) return -1;
else return (d1->signed_distance > d2->signed_distance);
}
} // end of anonymous namspace
void mesh::construct_bsp_tree() {
unsigned int i;
// get memory used to sort vertices
std::vector<struct bsp_sort_data> bsp_vertex(m_vertex.size());
// assign the correct index to each entry in bsp_vertex
for (i = 0; i < bsp_vertex.size(); i++)
bsp_vertex[i].idx = i;
/*
construct the bsp tree...
0 is the 'direction' of the first partition plane
16 is the constant which determines how many vertices end up in one partition
*/
std::vector<unsigned int> lastSizes(3);
m_bsp_node = construct_bsp_tree(0, (int)bsp_vertex.size(), &(bsp_vertex[0]), 16, lastSizes);
// insert all faces into the bsp tree:
for (i =0; i < (unsigned int)get_nb_faces(); i++) {
std::vector<normalizedFlatPoint> vertex;
vertex.push_back(_normalizedFlatPoint(get_vertex(get_face(i).get_vtx_idx(0)).get_pt() ^ ni));
vertex.push_back(_normalizedFlatPoint(get_vertex(get_face(i).get_vtx_idx(1)).get_pt() ^ ni));
vertex.push_back(_normalizedFlatPoint(get_vertex(get_face(i).get_vtx_idx(2)).get_pt() ^ ni));
m_bsp_node ->insert_face(i, vertex);
}
}
bool mesh::check_planes(const std::vector<plane> &planes, unsigned int nb_vertices, struct bsp_sort_data*vertex) const {
bool bad = false;
for (unsigned int j = 0; j < nb_vertices; j++) {
const ::vertex &v(get_vertex(vertex[j].idx));
normalizedFlatPoint fpt = _normalizedFlatPoint(v.get_pt() ^ ni);
for (unsigned int i = 0; i < planes.size(); i++) {
mv::Float sdx = -_Float(no << (dual(planes[i]) << fpt));
if (sdx < 0.0) {
bad = true;
}
}
}
return bad;
}
bsp_node *mesh::construct_bsp_tree(/*std::vector<c3ga> planes, */int base_plane_idx,
unsigned int nb_vertices, struct bsp_sort_data*vertex,
unsigned int desired_vertices_per_partition, std::vector<unsigned int> lastSizes) const {
unsigned int i;
lastSizes.erase(lastSizes.begin());
lastSizes.push_back(nb_vertices);
// todo:
// remember last 3 sizes? create leaf node when three times equal size?
// we are done if the number of vertices <= the desired number of vertices per partition
if ((nb_vertices <= desired_vertices_per_partition) ||
((lastSizes[0] == lastSizes[1]) && (lastSizes[1] == lastSizes[2]))) {
return construct_bsp_leaf(/*planes, */nb_vertices, vertex);
}
/*
Get the 'base plane' we are going to use for partitioning the space:
The integer 'basePlaneIdx' tells us what plane to use:
*/
dualPlane dual_base_plane;
if (base_plane_idx == 0) dual_base_plane = _dualPlane(dual(no ^ e2 ^ e3 ^ ni));
else if (base_plane_idx == 1) dual_base_plane = _dualPlane(dual(no ^ e3 ^ e1 ^ ni));
else dual_base_plane = _dualPlane(dual(no ^ e1 ^ e2 ^ ni));
/*
Compute the signed distance of each vertex to the plane.
This distance is stored inside the vertices,
so we can use it to sort them:
*/
for (i = 0; i < nb_vertices; i++) {
vertex[i].signed_distance = -
_Float(dual_base_plane % get_vertex(vertex[i].idx).get_pt());
}
/*
Use quicksort to sort the vertices.
The function 'constructBSPTreeSort()' compares the
signed_distance fields of the vertices.
Todo: use stl quick sort . . .
*/
qsort(vertex, nb_vertices, sizeof(bsp_sort_data), construct_bsp_tree_sort);
/*
The required translation of the base plane is now simply the
average of the signed distance of the two vertices that came out
in the middle after sorting:
*/
int split_idx = nb_vertices / 2;
mv::Float d = 0.5f * (vertex[split_idx-1].signed_distance + vertex[split_idx].signed_distance);
int upto = split_idx;
int startat = split_idx;
/*
Temp test . . .
*/
if (vertex[split_idx-1].signed_distance == vertex[split_idx].signed_distance) {
while (((upto+1) < (int)nb_vertices) &&
(vertex[upto].signed_distance == vertex[upto+1].signed_distance))
upto++;
while (((startat-1) >= 0) &&
(vertex[startat].signed_distance == vertex[startat-1].signed_distance))
startat--;
}
/*
We now translate the dual base plane, (un)dualize it and store
it in the m_pl of the BSP node:
*/
plane pl = _plane(undual(dual_base_plane - d * ni));
struct bsp_sort_data *vertex2 = vertex;
std::vector<struct bsp_sort_data> bsp_vertex2;
if (upto != startat) {
bsp_vertex2.resize(nb_vertices);
vertex2 = &(bsp_vertex2[0]);
memcpy(vertex2, vertex, sizeof(struct bsp_sort_data) * nb_vertices);
}
return new bsp_node(pl,
construct_bsp_tree((base_plane_idx+1)%3, upto, vertex, desired_vertices_per_partition, lastSizes),
construct_bsp_tree((base_plane_idx+1)%3, nb_vertices - startat, vertex2 + startat, desired_vertices_per_partition, lastSizes));
}
bsp_node *mesh::construct_bsp_leaf(unsigned int nb_vertices, struct bsp_sort_data*vertex) const {
return new bsp_node();
}
void mesh::compute_local_texture_basis() {
for (unsigned int i = 0; i < m_face.size(); i++) {
m_face[i].compute_local_texture_basis(*this);
}
}
bool mesh::find_intersection(const ray &R, surface_point &spt, bool find_closest) const {
dualPlane ray_dual_plane = _dualPlane((no << R.get_position()) << R.get_direction());
// The point must be either inside the sphere . . .
dualSphere PI = _dualSphere(get_bounding_dual_sphere() << R.get_position()); // PI is a sphere (imaginary or real tells whether ray pos is inside sphere)
if (_Float(PI % PI) > 0.0f) {
/// . . . or the sphere must be ahead of the ray:
if (_Float(ray_dual_plane % get_bounding_dual_sphere()) < 0.0f)
return false;
}
dualLine ray_dual_line = _dualLine(dual((R.get_position() ^ ray_dual_plane)));
// OK, the sphere is ahead of the ray, now check for intersection
pointPair I = _pointPair(get_bounding_dual_sphere() << dual(ray_dual_line));
if (_Float(I % I) <= 0.0f) // is it a (dual) imaginary circle or a tangent?
return false; // if so, don't search on
return find_intersection_bsp(I, ray_dual_plane, ray_dual_line, spt, find_closest);
}
bool mesh::find_intersection_brute_force(const dualPlane &ray_dual_plane, const dualLine &ray_dual_line, surface_point &spt, bool find_closest) const {
if (find_closest) {
for (unsigned int i = 0; i < m_face.size(); i++)
if (m_face[i].find_intersection(ray_dual_plane, ray_dual_line, spt, find_closest))
spt.set_face_idx(i);
return spt.get_valid();
}
else {
for (unsigned int i = 0; i < m_face.size(); i++) {
if (m_face[i].find_intersection(ray_dual_plane, ray_dual_line, spt, find_closest)) {
spt.set_face_idx(i);
return true;
}
}
return false;
}
}
bool mesh::find_intersection_bsp(const pointPair &pp, const dualPlane &ray_dual_plane, const dualLine &ray_dual_line, surface_point &spt, bool find_closest) const {
// split 'pp' into two flat points
normalizedFlatPoint fpt1, fpt2;
dissect_point_pair_normalized_flat(pp, fpt1, fpt2);
// determine where those point are relative to (the start of) the ray
mv::Float d1, d2;
d1 = -_Float(no << (ray_dual_plane << fpt1));
d2 = -_Float(no << (ray_dual_plane << fpt2));
// descent down the bsp tree (but first order fpt1 and fpt2)
if (d1 < d2) {
bsp_descent_info bdi(this, fpt1, d1, fpt2, d2, ray_dual_plane, ray_dual_line, spt, find_closest);
return get_bsp_node()->find_intersection(bdi);
}
else {
bsp_descent_info bdi(this, fpt2, d2, fpt1, d1, ray_dual_plane, ray_dual_line, spt, find_closest);
return get_bsp_node()->find_intersection(bdi);
}
}
// leave this comment for online browsing anchors