git.mutantstargoat.com Git - summerhack/blob - src/3dengfx/src/gfx/3dgeom.cpp

   1 /*
   2 This file is part of the 3dengfx, realtime visualization system.
   3 Copyright (c) 2004, 2005 John Tsiombikas <nuclear@siggraph.org>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18 */
  19
  20 /* fundamendal data structures for 3D graphics
  21  *
  22  * Author: John Tsiombikas 2004
  23  * Modified:
  24  *              Mihalis Georgoulopoulos 2004, 2005
  25  *              John Tsiombikas 2005
  26  */
  27
  28 #include "3dengfx_config.h"
  29
  30 #include <iostream>
  31 #include <cstdlib>
  32 #include <cfloat>
  33 #include <algorithm>
  34 #include "3dgeom.hpp"
  35 #include "common/psort.hpp"
  36
  37 #ifdef USING_3DENGFX
  38 #include "3dengfx/3denginefx.hpp"
  39 #endif  // USING_3DENGFX
  40
  41 using std::vector;
  42 using namespace glext;
  43
  44 TexCoord::TexCoord(scalar_t u, scalar_t v, scalar_t w) {
  45         this->u = u;
  46         this->v = v;
  47         this->w = w;
  48 }
  49
  50 // Vertex class implementation
  51
  52 Vertex::Vertex() {
  53         //normal = Vector3(0, 1, 0);
  54 }
  55
  56 Vertex::Vertex(const Vector3 &position, scalar_t tu, scalar_t tv, const Color &color) {
  57         pos = position;
  58         normal = Vector3(0, 1, 0);
  59         tex[0].u = tex[1].u = tu;
  60         tex[0].v = tex[1].v = tv;
  61         this->color = color;
  62 }
  63
  64 /////////// Edge class implementation ///////////
  65
  66 Edge::Edge() {
  67         vertices[0] = vertices[1] = 0;
  68         adjfaces[0] = adjfaces[1] = NO_ADJFACE;
  69 }
  70
  71 Edge::Edge(Index v1, Index v2, Index af1, Index af2) {
  72         vertices[0] = v1;
  73         vertices[1] = v2;
  74         adjfaces[0] = af1;
  75         adjfaces[1] = af2;
  76 }
  77
  78 std::ostream &operator <<(std::ostream &o, const Edge &e) {
  79         o << "v(" << e.vertices[0] << ", " << e.vertices[1] << ")";
  80         o << " t(" << e.adjfaces[0] << ", " << e.adjfaces[1] << ")";
  81         return o;
  82 }
  83
  84 /////////// Triangle class implementation /////////////
  85 Triangle::Triangle(Index v1, Index v2, Index v3) {
  86         vertices[0] = v1;
  87         vertices[1] = v2;
  88         vertices[2] = v3;
  89
  90         smoothing_group = 0;
  91 }
  92
  93 void Triangle::calculate_normal(const Vertex *vbuffer, bool normalize) {
  94         Vector3 v1 = vbuffer[vertices[1]].pos - vbuffer[vertices[0]].pos;
  95         Vector3 v2 = vbuffer[vertices[2]].pos - vbuffer[vertices[0]].pos;
  96         normal = cross_product(v1, v2);
  97         if(normalize) normal.normalize();
  98 }
  99
 100 void Triangle::calculate_tangent(const Vertex *vbuffer, bool normalize){
 101         Vector3 a, b, c, d;
 102         scalar_t au, bu, cu, du;
 103
 104         a = vbuffer[vertices[0]].pos;
 105         b = vbuffer[vertices[1]].pos;
 106         c = vbuffer[vertices[2]].pos;
 107
 108         au = vbuffer[vertices[0]].tex[0].u;
 109         bu = vbuffer[vertices[1]].tex[0].u;
 110         cu = vbuffer[vertices[2]].tex[0].u;
 111
 112         int i=0;
 113
 114         // rotate a b and c until au!=bu and au != cu
 115         while ( fabs(au - bu) < xsmall_number &&
 116                         fabs(au - cu) < xsmall_number && i < 3)
 117         {
 118                 du = cu; cu = bu; bu = au; au = du;
 119                 d = c; c = b; b = a; a = d;
 120                 i++;
 121         }
 122
 123         if (i == 3)
 124         {
 125                 // all u's are the same. cannot calculate tangent
 126                 tangent = Vector3(0, 0, 0);
 127                 return;
 128         }
 129
 130         // find d using linear interpolation
 131         d = a + (((bu - au) / (cu - au)) * (c - a));
 132
 133         // find the projection of a to b->d
 134         Vector3 bd = d - b;
 135         bd.normalize();
 136         Vector3 ab = b - a;
 137         Vector3 a_proj = ab - (dot_product(ab, bd) * bd);
 138
 139         if (bu > au) tangent = a_proj - a;
 140         else tangent = a - a_proj;
 141         if (normalize) tangent.normalize();
 142 }
 143
 144 std::ostream &operator <<(std::ostream &o, const Triangle &t) {
 145         o << "[" << t.vertices[0] << ", " << t.vertices[1] << ", " << t.vertices[2] << "]";
 146         return o;
 147 }
 148
 149 Quad::Quad(Index v1, Index v2, Index v3, Index v4) {
 150         vertices[0] = v1;
 151         vertices[1] = v2;
 152         vertices[2] = v3;
 153         vertices[3] = v4;
 154 }
 155
 156 void Quad::calculate_normal(const Vertex *vbuffer, bool normalize) {
 157         Vector3 v1 = vbuffer[vertices[1]].pos - vbuffer[vertices[0]].pos;
 158         Vector3 v2 = vbuffer[vertices[2]].pos - vbuffer[vertices[0]].pos;
 159         normal = cross_product(v1, v2);
 160         if(normalize) normal.normalize();
 161 }
 162
 163 ///////////////////////////////////////////
 164 // Index specialization of GeometryArray //
 165 ///////////////////////////////////////////
 166
 167 GeometryArray<Index>::GeometryArray(bool dynamic) {
 168         data = 0;
 169         count = 0;
 170         buffer_object = INVALID_VBO;
 171         vbo_in_sync = false;
 172
 173         set_dynamic(dynamic);
 174 }
 175
 176 GeometryArray<Index>::GeometryArray(const Index *data, unsigned long count, bool dynamic) {
 177         this->data = 0;
 178         this->count = 0;
 179         buffer_object = INVALID_VBO;
 180         set_dynamic(dynamic);
 181
 182         set_data(data, count);
 183 }
 184
 185 void tri_to_index_array(GeometryArray<Index> *ia, const GeometryArray<Triangle> &ta) {
 186         ia->dynamic = ta.get_dynamic();
 187
 188         unsigned long tcount = ta.get_count();
 189         Index *tmp_data = new Index[tcount * 3];
 190
 191         Index *ptr = tmp_data;
 192         for(unsigned long i=0; i<tcount; i++) {
 193                 for(int j=0; j<3; j++) {
 194                         *ptr++ = ta.get_data()[i].vertices[j];
 195                 }
 196         }
 197
 198         ia->set_data(tmp_data, tcount * 3);
 199         delete [] tmp_data;
 200 }
 201
 202 GeometryArray<Index>::GeometryArray(const GeometryArray<Triangle> &tarray) {
 203         tri_to_index_array(this, tarray);
 204 }
 205
 206 GeometryArray<Index>::GeometryArray(const GeometryArray<Index> &ga) {
 207         data = 0;
 208         count = 0;
 209         buffer_object = INVALID_VBO;
 210         dynamic = ga.dynamic;
 211
 212         set_data(ga.data, ga.count);
 213 }
 214
 215 GeometryArray<Index>::~GeometryArray() {
 216         if(data) {
 217                 delete [] data;
 218         }
 219 #ifdef USING_3DENGFX
 220         if(buffer_object != INVALID_VBO) {
 221                 glDeleteBuffers(1, &buffer_object);
 222         }
 223 #endif  // USING_3DENGFX
 224 }
 225
 226 GeometryArray<Index> &GeometryArray<Index>::operator =(const GeometryArray<Index> &ga) {
 227         dynamic = ga.dynamic;
 228         if(data) delete [] data;
 229
 230         set_data(ga.data, ga.count);
 231
 232         return *this;
 233 }
 234
 235 void GeometryArray<Index>::sync_buffer_object() {
 236 #ifdef USING_3DENGFX
 237         if(dynamic) return;
 238
 239         if(buffer_object == INVALID_VBO) {
 240                 glGenBuffers(1, &buffer_object);
 241                 glBindBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, buffer_object);
 242                 glBufferData(GL_ELEMENT_ARRAY_BUFFER_ARB, count * sizeof(Index), data, GL_STATIC_DRAW_ARB);
 243                 glBindBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, 0);
 244         } else {
 245
 246                 int glerr;
 247                 while((glerr = glGetError()) != GL_NO_ERROR) {
 248                         std::cerr << get_glerror_string(glerr) << " ";
 249                 }
 250                 glBindBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, buffer_object);
 251
 252                 glBufferData(GL_ELEMENT_ARRAY_BUFFER_ARB, count * sizeof(Index), data, GL_STATIC_DRAW_ARB);
 253                 glBindBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, 0);
 254         }
 255 #endif  // USING_3DENGFX
 256         vbo_in_sync = true;
 257
 258 }
 259
 260 void GeometryArray<Index>::set_data(const Index *data, unsigned long count) {
 261         if(!data) return;
 262         if(!this->data || count != this->count) {
 263                 if(this->data) {
 264                         delete [] this->data;
 265                 }
 266                 this->data = new Index[count];
 267         }
 268
 269         memcpy(this->data, data, count * sizeof(Index));
 270
 271 #ifdef USING_3DENGFX
 272         if(!dynamic) {
 273                 if(buffer_object != INVALID_VBO && count != this->count) {
 274                         glDeleteBuffers(1, &buffer_object);
 275                 }
 276                 sync_buffer_object();
 277                 vbo_in_sync = true;
 278         }
 279 #endif  // USING_3DENGFX
 280
 281         this->count = count;
 282 }
 283
 284
 285 ///////////// Triangle Mesh Implementation /////////////
 286 TriMesh::TriMesh() {
 287         indices_valid = false;
 288         vertex_stats_valid = false;
 289         edges_valid = false;
 290         index_graph_valid = false;
 291         triangle_normals_valid = false;
 292         triangle_normals_normalized = false;
 293 }
 294
 295 TriMesh::TriMesh(const Vertex *vdata, unsigned long vcount, const Triangle *tdata, unsigned long tcount) {
 296         indices_valid = false;
 297         vertex_stats_valid = false;
 298         edges_valid = false;
 299         index_graph_valid = false;
 300         triangle_normals_valid = false;
 301         triangle_normals_normalized = false;
 302         set_data(vdata, vcount, tdata, tcount);
 303 }
 304
 305 void TriMesh::calculate_edges() {
 306
 307         if (!index_graph_valid)
 308                 calculate_index_graph();
 309
 310         unsigned int vcount = varray.get_count();
 311         vector<Edge> *edge_table = new vector<Edge>[vcount];
 312         const Triangle *tris = tarray.get_data();
 313         const Index *igraph = index_graph.get_data();
 314         unsigned int tcount = tarray.get_count();
 315         unsigned int num_edges = 0;
 316
 317         // Triangle loop
 318         for (unsigned int i=0; i<tcount; i++)
 319         {
 320                 unsigned int a, b, temp;
 321                 for (unsigned int j=0; j<3; j++)
 322                 {
 323                         a = igraph[tris[i].vertices[j]];
 324                         b = igraph[tris[i].vertices[(j + 1) % 3]];
 325
 326                         if (a > b)
 327                         {
 328                                 temp = b;
 329                                 b = a;
 330                                 a = temp;
 331                         }
 332
 333                         int edge_found = -1;
 334                         for (unsigned int edge = 0; edge < edge_table[a].size(); edge++)
 335                         {
 336                                 if (edge_table[a][edge].vertices[1] == b)
 337                                 {
 338                                         edge_found = edge;
 339                                         break;
 340                                 }
 341                         }
 342
 343                         if (edge_found != -1)
 344                         {
 345                                 // edge was already in the list
 346                                 // add the second face to this edge
 347                                 edge_table[a][edge_found].adjfaces[1] = i;
 348                         }
 349                         else
 350                         {
 351                                 // add a new edge to the list
 352                                 Edge new_edge(a, b, i);
 353                                 edge_table[a].push_back(new_edge);
 354                                 num_edges++;
 355                         }
 356                 }
 357         } // End triangle loop
 358
 359         // collect edges
 360         Edge *edges = new Edge[num_edges];
 361         int k = 0;
 362         for (unsigned int i=0; i<vcount; i++)
 363         {
 364                 for (unsigned int j=0; j<edge_table[i].size(); j++)
 365                 {
 366                         edges[k] = edge_table[i][j];
 367                         k++;
 368                 }
 369         }
 370
 371         earray.set_data(edges, num_edges);
 372         edges_valid = true;
 373
 374         // cleanup
 375         delete [] edge_table;
 376         delete [] edges;
 377 }
 378
 379 void TriMesh::calculate_triangle_normals(bool normalize)
 380 {
 381         // calculate the triangle normals
 382         for(unsigned int i=0; i<tarray.get_count(); i++) {
 383                 tarray.get_mod_data()[i].calculate_normal(varray.get_data(), normalize);
 384         }
 385
 386         triangle_normals_valid = true;
 387         triangle_normals_normalized = normalize;
 388 }
 389
 390 const IndexArray *TriMesh::get_index_array() {
 391         if(!indices_valid) {
 392                 tri_to_index_array(&iarray, tarray);
 393                 indices_valid = true;
 394         }
 395         return &iarray;
 396 }
 397
 398 const GeometryArray<Edge> *TriMesh::get_edge_array() const {
 399         if(!edges_valid) {
 400                 const_cast<TriMesh*>(this)->calculate_edges();
 401         }
 402         return &earray;
 403 }
 404
 405 void TriMesh::set_data(const Vertex *vdata, unsigned long vcount, const Triangle *tdata, unsigned long tcount) {
 406         get_mod_vertex_array()->set_data(vdata, vcount);        // also invalidates vertex stats
 407         get_mod_triangle_array()->set_data(tdata, tcount);      // also invalidates indices and edges
 408 }
 409
 410 void TriMesh::calculate_normals_by_index() {
 411         // precalculate which triangles index each vertex
 412         std::vector<unsigned int> *tri_indices;
 413         tri_indices = new std::vector<unsigned int>[varray.get_count()];
 414
 415         for(unsigned int i=0; i<tarray.get_count(); i++) {
 416                 for(int j=0; j<3; j++) {
 417                         tri_indices[tarray.get_data()[i].vertices[j]].push_back(i);
 418                 }
 419         }
 420
 421         // calculate the triangle normals
 422         if (!triangle_normals_valid)
 423                 calculate_triangle_normals(false);
 424
 425         // now calculate the vertex normals
 426         for(unsigned int i=0; i<varray.get_count(); i++) {
 427                 Vector3 normal;
 428                 for(unsigned int j=0; j<(unsigned int)tri_indices[i].size(); j++) {
 429                         normal += tarray.get_data()[tri_indices[i][j]].normal;
 430                 }
 431
 432                 // avoid division by zero
 433                 if(tri_indices[i].size()) {
 434                         normal.normalize();
 435                 }
 436                 varray.get_mod_data()[i].normal = normal;
 437         }
 438
 439         delete [] tri_indices;
 440 }
 441
 442 /* TriMesh::calculate_normals() - (MG)
 443  */
 444 void TriMesh::calculate_normals()
 445 {
 446         if (!index_graph_valid)
 447                 calculate_index_graph();
 448
 449         // calculate the triangle normals
 450         if (!triangle_normals_valid)
 451                 calculate_triangle_normals(false);
 452
 453         // precalculate which triangles index each vertex
 454         std::vector<unsigned int> *tri_indices;
 455         tri_indices = new std::vector<unsigned int>[varray.get_count()];
 456
 457         for(unsigned int i=0; i<tarray.get_count(); i++) {
 458                 for(int j=0; j<3; j++) {
 459                         Index tri_index = index_graph.get_data()[tarray.get_data()[i].vertices[j]];
 460                         tri_indices[tri_index].push_back(i);
 461                 }
 462         }
 463
 464         // now calculate the vertex normals
 465         for(unsigned int i=0; i<varray.get_count(); i++) {
 466
 467                 if (index_graph.get_data()[i] != i)
 468                 {
 469                         // normal already calculated. Just copy
 470                         varray.get_mod_data()[i].normal = varray.get_mod_data()[index_graph.get_data()[i]].normal;
 471                         continue;
 472                 }
 473
 474                 Vector3 normal;
 475                 for(unsigned int j=0; j<(unsigned int)tri_indices[i].size(); j++) {
 476                         normal += tarray.get_data()[tri_indices[i][j]].normal;
 477                 }
 478
 479                 // avoid division with zero
 480                 if (tri_indices[i].size())
 481                         normal.normalize();
 482                 varray.get_mod_data()[i].normal = normal;
 483         }
 484
 485         delete [] tri_indices;
 486 }
 487
 488 void TriMesh::normalize_normals() {
 489         Vertex *vptr = varray.get_mod_data();
 490         for(unsigned int i=0; i<varray.get_count(); i++) {
 491                 vptr[i].normal.normalize();
 492         }
 493 }
 494
 495 /* TriMesh::invert_winding() - (JT)
 496  * inverts the order of vertices (cw/ccw) as well as the normals
 497  */
 498 void TriMesh::invert_winding() {
 499         Triangle *tptr = tarray.get_mod_data();
 500         int tcount = tarray.get_count();
 501
 502         for(int i=0; i<tcount; i++) {
 503                 Index tmp = tptr->vertices[1];
 504                 tptr->vertices[1] = tptr->vertices[2];
 505                 tptr->vertices[2] = tmp;
 506                 tptr->normal = -tptr->normal;
 507                 tptr++;
 508         }
 509
 510         Vertex *vptr = varray.get_mod_data();
 511         int vcount = varray.get_count();
 512
 513         for(int i=0; i<vcount; i++) {
 514                 vptr->normal = -vptr->normal;
 515                 vptr++;
 516         }
 517 }
 518
 519
 520 void TriMesh::calculate_tangents() {
 521         // precalculate which triangles index each vertex
 522         std::vector<unsigned int> *tri_indices;
 523         tri_indices = new std::vector<unsigned int>[varray.get_count()];
 524
 525         for(unsigned int i=0; i<tarray.get_count(); i++) {
 526                 for(int j=0; j<3; j++) {
 527                         tri_indices[tarray.get_data()[i].vertices[j]].push_back(i);
 528                 }
 529         }
 530
 531         // calculate the triangle tangents
 532         for(unsigned int i=0; i<tarray.get_count(); i++) {
 533                 tarray.get_mod_data()[i].calculate_tangent(varray.get_data(), false);
 534         }
 535
 536         // now calculate the vertex tangents
 537         for(unsigned int i=0; i<varray.get_count(); i++) {
 538                 Vector3 tangent;
 539                 for(unsigned int j=0; j<(unsigned int)tri_indices[i].size(); j++) {
 540                         tangent += tarray.get_data()[tri_indices[i][j]].tangent;
 541                 }
 542
 543                 // avoid division by zero
 544                 if(tri_indices[i].size()) {
 545                         tangent.normalize();
 546                 }
 547                 varray.get_mod_data()[i].tangent = tangent;
 548         }
 549
 550         delete [] tri_indices;
 551 }
 552
 553 void TriMesh::apply_xform(const Matrix4x4 &xform) {
 554         Vertex *vptr = varray.get_mod_data();
 555         unsigned long count = varray.get_count();
 556
 557         for(unsigned long i=0; i<count; i++) {
 558                 vptr->pos.transform(xform);
 559                 (vptr++)->normal.transform((Matrix3x3)xform);
 560         }
 561 }
 562
 563 void TriMesh::operator +=(const TriMesh *m2) {
 564         join_tri_mesh(this, this, m2);
 565 }
 566
 567 /* TriMesh::sort_triangles - (MG)
 568  * sorts triangles according to their distance from a
 569  * given point (in model space).
 570  */
 571 void TriMesh::sort_triangles(Vector3 point, bool hilo)
 572 {
 573         const Vertex *verts = get_vertex_array()->get_data();
 574         unsigned int vcount = get_vertex_array()->get_count();
 575         Triangle *tris = get_mod_triangle_array()->get_mod_data();
 576         unsigned int tcount = get_triangle_array()->get_count();
 577
 578         // store square distance for each vertex
 579         scalar_t *sq_distances = new scalar_t[vcount];
 580
 581         for (unsigned int i=0; i<vcount; i++)
 582         {
 583                 sq_distances[i] = (verts[i].pos - point).length_sq();
 584         }
 585
 586         // store sum of sq distances for each triangle
 587         scalar_t *tri_distances = new scalar_t[tcount];
 588
 589         for (unsigned int i=0; i<tcount; i++)
 590         {
 591                 tri_distances[i] = 0;
 592                 for (unsigned int j=0; j<3; j++)
 593                 {
 594                         tri_distances[i] += sq_distances[tris[i].vertices[j]];
 595                 }
 596         }
 597
 598         // sort
 599         sort(tris, tri_distances, tcount, hilo);
 600
 601         // cleanup
 602         delete [] sq_distances;
 603         delete [] tri_distances;
 604 }
 605
 606 VertexStatistics TriMesh::get_vertex_stats() const {
 607         if(!vertex_stats_valid) {
 608                 vstats.xmin = vstats.ymin = vstats.zmin = FLT_MAX;
 609                 vstats.xmax = vstats.ymax = vstats.zmax = -FLT_MAX;
 610
 611                 const Vertex *varray = get_vertex_array()->get_data();
 612                 int count = get_vertex_array()->get_count();
 613
 614                 const Vertex *vptr = varray;
 615                 vstats.centroid = Vector3(0, 0, 0);
 616                 for(int i=0; i<count; i++) {
 617                         Vector3 pos = (vptr++)->pos;
 618                         vstats.centroid += pos;
 619
 620                         if(pos.x < vstats.xmin) vstats.xmin = pos.x;
 621                         if(pos.y < vstats.ymin) vstats.ymin = pos.y;
 622                         if(pos.z < vstats.zmin) vstats.zmin = pos.z;
 623                         if(pos.x > vstats.xmax) vstats.xmax = pos.x;
 624                         if(pos.y > vstats.ymax) vstats.ymax = pos.y;
 625                         if(pos.z > vstats.zmax) vstats.zmax = pos.z;
 626                 }
 627                 vstats.centroid /= count;
 628
 629                 scalar_t min_len_sq = FLT_MAX;
 630                 scalar_t max_len_sq = 0.0;
 631                 scalar_t avg_len_sq = 0.0;
 632
 633                 vptr = varray;
 634                 for(int i=0; i<count; i++) {
 635                         scalar_t len_sq = ((vptr++)->pos - vstats.centroid).length_sq();
 636                         if(len_sq < min_len_sq) min_len_sq = len_sq;
 637                         if(len_sq > max_len_sq) max_len_sq = len_sq;
 638                         avg_len_sq += len_sq;
 639                 }
 640
 641                 vstats.min_dist = sqrt(min_len_sq);
 642                 vstats.max_dist = sqrt(max_len_sq);
 643                 vstats.avg_dist = sqrt(avg_len_sq / (scalar_t)count);
 644                 vertex_stats_valid = true;
 645         }
 646         return vstats;
 647 }
 648
 649 /* get_contour_edges - (MG, JT)
 650  * returns the contour edges relative to the given point of view or direction
 651  * The edges are in clockwise order, so they can be used to create a shadow volume
 652  * mesh by extruding them...
 653  * NOTE: pov_or_dir should be given in model space
 654  */
 655 std::vector<Edge> *TriMesh::get_contour_edges(const Vector3 &pov_or_dir, bool dir)
 656 {
 657         static std::vector<Edge> cont_edges;
 658
 659         // calculate triangle normals
 660         if(!triangle_normals_valid) {
 661                 calculate_triangle_normals(false);
 662         }
 663
 664         const Vertex *va = get_vertex_array()->get_data();
 665         unsigned long vc = get_vertex_array()->get_count();
 666         const Triangle *ta = get_triangle_array()->get_data();
 667         unsigned long tc = get_triangle_array()->get_count();
 668
 669         vector<Edge> *vert_edge = new vector<Edge>[vc];
 670
 671         Vector3 direction = pov_or_dir;
 672         for(unsigned long i=0; i<tc; i++) {
 673                 if(!dir) {
 674                         direction = va[ta[i].vertices[0]].pos - pov_or_dir;
 675                 }
 676
 677                 if(dot_product(ta[i].normal, direction) > 0) {
 678                         for(int j=0; j<3; j++) {
 679                                 int v0idx = j;
 680                                 int v1idx = (j + 1) % 3;
 681
 682                                 Index v0 = ta[i].vertices[v0idx];
 683                                 Index v1 = ta[i].vertices[v1idx];
 684
 685                                 Edge edge(v1, v0);
 686                                 std::vector<Edge>::iterator iter = vert_edge[v0].begin();
 687
 688                                 bool found = false;
 689                                 for(unsigned int k=0; k<vert_edge[v0].size(); k++, iter++) {
 690                                         if(vert_edge[v0][k].vertices[1] == v1) {
 691                                                 vert_edge[v0].erase(iter);
 692                                                 found = true;
 693                                                 break;
 694                                         }
 695                                 }
 696
 697                                 if(!found) {
 698                                         iter = vert_edge[v1].begin();
 699                                         for(unsigned int k=0; k<vert_edge[v1].size(); k++, iter++) {
 700                                                 if(vert_edge[v1][k].vertices[0] == v0) {
 701                                                         vert_edge[v1].erase(iter);
 702                                                         found = true;
 703                                                         break;
 704                                                 }
 705                                         }
 706                                 }
 707
 708                                 if(!found) vert_edge[v0].push_back(edge);
 709
 710                         }
 711
 712                 }
 713         }
 714
 715         cont_edges.clear();
 716         for(unsigned int i=0; i<vc; i++) {
 717                 for(unsigned int j=0; j<vert_edge[i].size(); j++) {
 718                         cont_edges.push_back(vert_edge[i][j]);
 719                 }
 720         }
 721
 722         return &cont_edges;
 723 }
 724
 725 /* get_uncapped_shadow_volume() - (MG)
 726  * specify pov_or_dir in model space
 727  * delete the returned mesh after using it
 728  */
 729 const scalar_t infinity = 100000;
 730 TriMesh *TriMesh::get_shadow_volume(const Vector3 &pov_or_dir, bool dir)
 731 {
 732         TriMesh *ret = new TriMesh;
 733
 734         const Vertex *va = get_vertex_array()->get_data();
 735         std::vector<Edge> *contour_edges = get_contour_edges(pov_or_dir, dir);
 736
 737         // calculate number of vertices and indices for the mesh
 738         unsigned long num_quads = contour_edges->size();
 739         unsigned long num_verts = num_quads * 4;
 740         unsigned long num_tris = num_quads * 2;
 741
 742         // allocate memory
 743         Vertex *verts = new Vertex[num_verts];
 744         Triangle *tris = new Triangle[num_tris];
 745
 746         // add contour vertices
 747         for (unsigned long i=0; i<num_quads; i++)
 748         {
 749                 for (unsigned long j=0; j<2; j++)
 750                 {
 751                         verts[2 * i + j].pos = va[(*contour_edges)[i].vertices[j]].pos;
 752                 }
 753         }
 754
 755         // add extruded vertices
 756         for (unsigned long i=0; i<num_verts/2; i++)
 757         {
 758                 verts[i + num_verts/2].pos = extrude(verts[i].pos, infinity, pov_or_dir, dir);
 759         }
 760
 761         // make triangles
 762         for (unsigned long i=0; i<num_quads; i++)
 763         {
 764                 Index p1, p2, ep1, ep2;
 765                 p1 = 2 * i;
 766                 p2 = 2 * i + 1;
 767                 ep1 = p1 + num_verts / 2;
 768                 ep2 = p2 + num_verts / 2;
 769                 tris[2*i] = Triangle(p1, ep1, ep2);
 770                 tris[2*i + 1] = Triangle(p1, ep2, p2);
 771         }
 772
 773         ret->set_data(verts, num_verts, tris, num_tris);
 774
 775         // cleanup
 776         delete [] verts;
 777         delete [] tris;
 778
 779         return ret;
 780 }
 781
 782 /* get_shadow_volume - (MG)
 783  * returns a capped shadow volume.
 784  * Only the front side is capped.
 785  * Delete the returned TriMesh* when finished using it.
 786  * TODO: implement back cap
 787  */
 788 /*TriMesh *TriMesh::get_shadow_volume(const Vector3 &pov_or_dir, bool dir)
 789 {
 790         TriMesh *uncapped = get_uncapped_shadow_volume(pov_or_dir, dir);
 791         TriMesh *capped = join_tri_mesh(this, uncapped);
 792         delete uncapped;
 793         return capped;
 794 }*/
 795
 796 /* class VertexOrder - (MG)
 797  * used by this module only
 798  */
 799 class VertexOrder
 800 {
 801 public:
 802         Index   order;
 803         Vertex  vertex;
 804
 805         // Constructor
 806         VertexOrder()
 807         {
 808                 order = 0;
 809                 vertex = Vertex();
 810         }
 811
 812         VertexOrder(Index order, const Vertex& vertex)
 813         {
 814                 this->order = order;
 815                 this->vertex = vertex;
 816         }
 817 };
 818
 819 // fwd declaration
 820 static std::vector<unsigned int> process_vo_array(VertexOrder *array, unsigned int size, unsigned int crit);
 821
 822 void TriMesh::calculate_index_graph()
 823 {
 824         Index *igraph = new Index[varray.get_count()];
 825         for (unsigned int i=0; i<varray.get_count(); i++)
 826         {
 827                 igraph[i] = i;
 828         }
 829
 830         VertexOrder *vo = new VertexOrder[varray.get_count()];
 831         for (unsigned int i=0; i<varray.get_count(); i++)
 832         {
 833                 vo[i] = VertexOrder(i, varray.get_data()[i]);
 834         }
 835
 836         // sort by x, then by y , then by z, and return constant-z parts
 837         std::vector<unsigned int> parts;
 838         parts = process_vo_array(vo, varray.get_count(), 0);
 839
 840         for (unsigned int i=0; i<parts.size(); i += 2)
 841         {
 842                 // find min index of this part
 843                 Index min_index = vo[parts[i]].order;
 844                 for (unsigned int j=0; j<parts[i + 1]; j++)
 845                 {
 846                         if(min_index > vo[parts[i] + j].order) {
 847                                 min_index = vo[parts[i] + j].order;
 848                         }
 849                 }
 850
 851                 // replace index
 852                 for (unsigned int j=0; j<parts[i + 1]; j++)
 853                         igraph[vo[parts[i] + j].order] = min_index;
 854         }
 855
 856         index_graph.set_data(igraph, varray.get_count());
 857         index_graph_valid = true;
 858
 859         delete [] vo;
 860         delete [] igraph;
 861 }
 862
 863 /* join_tri_mesh - (MG)
 864  * Gets 2 trimeshes and returns a new one
 865  * that contains both meshes
 866  */
 867 void join_tri_mesh(TriMesh *ret, const TriMesh *m1, const TriMesh *m2)
 868 {
 869         const Vertex *varr1 = m1->get_vertex_array()->get_data();
 870         const Vertex *varr2 = m2->get_vertex_array()->get_data();
 871
 872         unsigned long vcount1 = m1->get_vertex_array()->get_count();
 873         unsigned long vcount2 = m2->get_vertex_array()->get_count();
 874
 875         const Triangle *tarr1 = m1->get_triangle_array()->get_data();
 876         const Triangle *tarr2 = m2->get_triangle_array()->get_data();
 877
 878         unsigned long tcount1 = m1->get_triangle_array()->get_count();
 879         unsigned long tcount2 = m2->get_triangle_array()->get_count();
 880
 881         // allocate memory
 882         int vcount = vcount1 + vcount2;
 883         int tcount = tcount1 + tcount2;
 884         Vertex *varray = new Vertex[vcount];
 885         Triangle *tarray = new Triangle[tcount];
 886
 887         // copy memory
 888         memcpy(varray, varr1, vcount1 * sizeof(Vertex));
 889         memcpy(varray + vcount1, varr2, vcount2 * sizeof(Vertex));
 890         memcpy(tarray, tarr1, tcount1 * sizeof(Triangle));
 891         memcpy(tarray + tcount1, tarr2, tcount2 * sizeof(Triangle));
 892
 893         // Fix indices
 894         for (unsigned long i = 0; i < tcount2; i++)
 895         {
 896                 for (int j=0; j<3; j++)
 897                 {
 898                         tarray[tcount1 + i].vertices[j] += vcount1;
 899                 }
 900         }
 901
 902         ret->set_data(varray, vcount, tarray, tcount);
 903
 904         // cleanup
 905         delete [] varray;
 906         delete [] tarray;
 907 }
 908
 909 /* Nicer join_tri_mesh - (JT)
 910  * This is a much better way to do things.
 911  */
 912 TriMesh *join_tri_mesh(const TriMesh *m1, const TriMesh *m2) {
 913         TriMesh *mesh = new TriMesh;
 914         join_tri_mesh(mesh, m1, m2);
 915         return mesh;
 916 }
 917
 918 /* extrude() - (MG)
 919  * extrude a vertex given a point of view (or direction) to the specified
 920  * distance
 921  */
 922 Vector3 extrude(const Vector3 &vec, scalar_t distance, const Vector3 &pov_or_dir, bool dir) {
 923         Vector3 direction;
 924
 925         if (dir) {
 926                 direction = pov_or_dir;
 927         }
 928         else {
 929                 direction = vec - pov_or_dir;
 930         }
 931
 932         direction.normalize();
 933         direction *= distance;
 934
 935         return vec + direction;
 936 }
 937
 938 /* utilities for finding duplicate vertices - (MG)
 939  */
 940 extern const scalar_t xsmall_number;
 941
 942 // Sort criteria for VertexOrder objects
 943 static bool vo_sort_crit_x(const VertexOrder& a, const VertexOrder& b)
 944 {
 945         return (a.vertex.pos.x < b.vertex.pos.x);
 946 }
 947
 948 static bool vo_sort_crit_y(const VertexOrder& a, const VertexOrder& b)
 949 {
 950         return (a.vertex.pos.y < b.vertex.pos.y);
 951 }
 952
 953 static bool vo_sort_crit_z(const VertexOrder& a, const VertexOrder& b)
 954 {
 955         return (a.vertex.pos.z < b.vertex.pos.z);
 956 }
 957
 958 // equality criteria for VertexOrder objects
 959 static bool vo_eq_crit_x(const VertexOrder& a, const VertexOrder& b)
 960 {
 961         return (b.vertex.pos.x - a.vertex.pos.x < xsmall_number);
 962 }
 963
 964 static bool vo_eq_crit_y(const VertexOrder& a, const VertexOrder& b)
 965 {
 966         return (b.vertex.pos.y - a.vertex.pos.y < xsmall_number);
 967 }
 968
 969 static bool vo_eq_crit_z(const VertexOrder& a, const VertexOrder& b)
 970 {
 971         return (b.vertex.pos.z - a.vertex.pos.z < xsmall_number);
 972 }
 973
 974 static bool (* vo_sort_crit[])(const VertexOrder& a, const VertexOrder& b) = {vo_sort_crit_x, vo_sort_crit_y, vo_sort_crit_z};
 975
 976 static bool (* vo_eq_crit[])(const VertexOrder& a, const VertexOrder& b) = {vo_eq_crit_x, vo_eq_crit_y, vo_eq_crit_z};
 977
 978 static std::vector<unsigned int> vo_find_constant_parts(VertexOrder *array, unsigned int size, unsigned int crit)
 979 {
 980         std::vector<unsigned int> parts;
 981         if (crit > 2) return parts;
 982
 983         bool (* eq_crit)(const VertexOrder& a, const VertexOrder& b);
 984         eq_crit = vo_eq_crit[crit];
 985
 986         unsigned int start=0;
 987         for (unsigned int i=0; i<size; i++)
 988         {
 989                 if (!eq_crit(array[start], array[i]))
 990                 {
 991                         if (i - start > 1)
 992                         {
 993                                 parts.push_back(start);
 994                                 parts.push_back(i - start);
 995                         }
 996
 997                         start = i;
 998                 }
 999         }
1000
1001         if (size - start > 1)
1002         {
1003                 parts.push_back(start);
1004                 parts.push_back(size - start);
1005         }
1006
1007         return parts;
1008 }
1009
1010 static std::vector<unsigned int> process_vo_array(VertexOrder *array, unsigned int size, unsigned int crit)
1011 {
1012         std::vector<unsigned int> r_parts;
1013         if (crit > 2) return r_parts;
1014
1015         bool (* sort_crit)(const VertexOrder& a, const VertexOrder& b);
1016         sort_crit = vo_sort_crit[crit];
1017
1018         // sort array
1019         std::sort(array, array + size, sort_crit);
1020
1021         // find constant parts
1022         std::vector<unsigned int> parts;
1023         parts = vo_find_constant_parts(array, size, crit);
1024
1025         if (crit < 2)
1026         {
1027                 for (unsigned int i=0; i<parts.size(); i += 2)
1028                 {
1029                         std::vector<unsigned int> new_parts;
1030                         new_parts = process_vo_array(array + parts[i], parts[i + 1], crit + 1);
1031                         for (unsigned int j=0; j<new_parts.size(); j+=2)
1032                         {
1033                                 r_parts.push_back(new_parts[j] + parts[i]);
1034                                 r_parts.push_back(new_parts[j+1]);
1035                         }
1036                 }
1037                 return r_parts;
1038         }
1039         else
1040         {
1041                 // found constant z parts. just return them
1042                 return parts;
1043         }
1044 }