2 This file is part of the 3dengfx, realtime visualization system.
3 Copyright (c) 2004, 2005 John Tsiombikas <nuclear@siggraph.org>
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.
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.
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
20 /* fundamendal data structures for 3D graphics
22 * Author: John Tsiombikas 2004
24 * Mihalis Georgoulopoulos 2004, 2005
25 * John Tsiombikas 2005
28 #include "3dengfx_config.h"
35 #include "common/psort.hpp"
38 #include "3dengfx/3denginefx.hpp"
39 #endif // USING_3DENGFX
42 using namespace glext;
44 TexCoord::TexCoord(scalar_t u, scalar_t v, scalar_t w) {
50 // Vertex class implementation
53 //normal = Vector3(0, 1, 0);
56 Vertex::Vertex(const Vector3 &position, scalar_t tu, scalar_t tv, const Color &color) {
58 normal = Vector3(0, 1, 0);
59 tex[0].u = tex[1].u = tu;
60 tex[0].v = tex[1].v = tv;
64 /////////// Edge class implementation ///////////
67 vertices[0] = vertices[1] = 0;
68 adjfaces[0] = adjfaces[1] = NO_ADJFACE;
71 Edge::Edge(Index v1, Index v2, Index af1, Index af2) {
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] << ")";
84 /////////// Triangle class implementation /////////////
85 Triangle::Triangle(Index v1, Index v2, Index v3) {
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();
100 void Triangle::calculate_tangent(const Vertex *vbuffer, bool normalize){
102 scalar_t au, bu, cu, du;
104 a = vbuffer[vertices[0]].pos;
105 b = vbuffer[vertices[1]].pos;
106 c = vbuffer[vertices[2]].pos;
108 au = vbuffer[vertices[0]].tex[0].u;
109 bu = vbuffer[vertices[1]].tex[0].u;
110 cu = vbuffer[vertices[2]].tex[0].u;
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)
118 du = cu; cu = bu; bu = au; au = du;
119 d = c; c = b; b = a; a = d;
125 // all u's are the same. cannot calculate tangent
126 tangent = Vector3(0, 0, 0);
130 // find d using linear interpolation
131 d = a + (((bu - au) / (cu - au)) * (c - a));
133 // find the projection of a to b->d
137 Vector3 a_proj = ab - (dot_product(ab, bd) * bd);
139 if (bu > au) tangent = a_proj - a;
140 else tangent = a - a_proj;
141 if (normalize) tangent.normalize();
144 std::ostream &operator <<(std::ostream &o, const Triangle &t) {
145 o << "[" << t.vertices[0] << ", " << t.vertices[1] << ", " << t.vertices[2] << "]";
149 Quad::Quad(Index v1, Index v2, Index v3, Index v4) {
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();
163 ///////////////////////////////////////////
164 // Index specialization of GeometryArray //
165 ///////////////////////////////////////////
167 GeometryArray<Index>::GeometryArray(bool dynamic) {
170 buffer_object = INVALID_VBO;
173 set_dynamic(dynamic);
176 GeometryArray<Index>::GeometryArray(const Index *data, unsigned long count, bool dynamic) {
179 buffer_object = INVALID_VBO;
180 set_dynamic(dynamic);
182 set_data(data, count);
185 void tri_to_index_array(GeometryArray<Index> *ia, const GeometryArray<Triangle> &ta) {
186 ia->dynamic = ta.get_dynamic();
188 unsigned long tcount = ta.get_count();
189 Index *tmp_data = new Index[tcount * 3];
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];
198 ia->set_data(tmp_data, tcount * 3);
202 GeometryArray<Index>::GeometryArray(const GeometryArray<Triangle> &tarray) {
203 tri_to_index_array(this, tarray);
206 GeometryArray<Index>::GeometryArray(const GeometryArray<Index> &ga) {
209 buffer_object = INVALID_VBO;
210 dynamic = ga.dynamic;
212 set_data(ga.data, ga.count);
215 GeometryArray<Index>::~GeometryArray() {
220 if(buffer_object != INVALID_VBO) {
221 glDeleteBuffers(1, &buffer_object);
223 #endif // USING_3DENGFX
226 GeometryArray<Index> &GeometryArray<Index>::operator =(const GeometryArray<Index> &ga) {
227 dynamic = ga.dynamic;
228 if(data) delete [] data;
230 set_data(ga.data, ga.count);
235 void GeometryArray<Index>::sync_buffer_object() {
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);
247 while((glerr = glGetError()) != GL_NO_ERROR) {
248 std::cerr << get_glerror_string(glerr) << " ";
250 glBindBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, buffer_object);
252 glBufferData(GL_ELEMENT_ARRAY_BUFFER_ARB, count * sizeof(Index), data, GL_STATIC_DRAW_ARB);
253 glBindBuffer(GL_ELEMENT_ARRAY_BUFFER_ARB, 0);
255 #endif // USING_3DENGFX
260 void GeometryArray<Index>::set_data(const Index *data, unsigned long count) {
262 if(!this->data || count != this->count) {
264 delete [] this->data;
266 this->data = new Index[count];
269 memcpy(this->data, data, count * sizeof(Index));
273 if(buffer_object != INVALID_VBO && count != this->count) {
274 glDeleteBuffers(1, &buffer_object);
276 sync_buffer_object();
279 #endif // USING_3DENGFX
285 ///////////// Triangle Mesh Implementation /////////////
287 indices_valid = false;
288 vertex_stats_valid = false;
290 index_graph_valid = false;
291 triangle_normals_valid = false;
292 triangle_normals_normalized = false;
295 TriMesh::TriMesh(const Vertex *vdata, unsigned long vcount, const Triangle *tdata, unsigned long tcount) {
296 indices_valid = false;
297 vertex_stats_valid = false;
299 index_graph_valid = false;
300 triangle_normals_valid = false;
301 triangle_normals_normalized = false;
302 set_data(vdata, vcount, tdata, tcount);
305 void TriMesh::calculate_edges() {
307 if (!index_graph_valid)
308 calculate_index_graph();
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;
318 for (unsigned int i=0; i<tcount; i++)
320 unsigned int a, b, temp;
321 for (unsigned int j=0; j<3; j++)
323 a = igraph[tris[i].vertices[j]];
324 b = igraph[tris[i].vertices[(j + 1) % 3]];
334 for (unsigned int edge = 0; edge < edge_table[a].size(); edge++)
336 if (edge_table[a][edge].vertices[1] == b)
343 if (edge_found != -1)
345 // edge was already in the list
346 // add the second face to this edge
347 edge_table[a][edge_found].adjfaces[1] = i;
351 // add a new edge to the list
352 Edge new_edge(a, b, i);
353 edge_table[a].push_back(new_edge);
357 } // End triangle loop
360 Edge *edges = new Edge[num_edges];
362 for (unsigned int i=0; i<vcount; i++)
364 for (unsigned int j=0; j<edge_table[i].size(); j++)
366 edges[k] = edge_table[i][j];
371 earray.set_data(edges, num_edges);
375 delete [] edge_table;
379 void TriMesh::calculate_triangle_normals(bool normalize)
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);
386 triangle_normals_valid = true;
387 triangle_normals_normalized = normalize;
390 const IndexArray *TriMesh::get_index_array() {
392 tri_to_index_array(&iarray, tarray);
393 indices_valid = true;
398 const GeometryArray<Edge> *TriMesh::get_edge_array() const {
400 const_cast<TriMesh*>(this)->calculate_edges();
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
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()];
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);
421 // calculate the triangle normals
422 if (!triangle_normals_valid)
423 calculate_triangle_normals(false);
425 // now calculate the vertex normals
426 for(unsigned int i=0; i<varray.get_count(); i++) {
428 for(unsigned int j=0; j<(unsigned int)tri_indices[i].size(); j++) {
429 normal += tarray.get_data()[tri_indices[i][j]].normal;
432 // avoid division by zero
433 if(tri_indices[i].size()) {
436 varray.get_mod_data()[i].normal = normal;
439 delete [] tri_indices;
442 /* TriMesh::calculate_normals() - (MG)
444 void TriMesh::calculate_normals()
446 if (!index_graph_valid)
447 calculate_index_graph();
449 // calculate the triangle normals
450 if (!triangle_normals_valid)
451 calculate_triangle_normals(false);
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()];
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);
464 // now calculate the vertex normals
465 for(unsigned int i=0; i<varray.get_count(); i++) {
467 if (index_graph.get_data()[i] != i)
469 // normal already calculated. Just copy
470 varray.get_mod_data()[i].normal = varray.get_mod_data()[index_graph.get_data()[i]].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;
479 // avoid division with zero
480 if (tri_indices[i].size())
482 varray.get_mod_data()[i].normal = normal;
485 delete [] tri_indices;
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();
495 /* TriMesh::invert_winding() - (JT)
496 * inverts the order of vertices (cw/ccw) as well as the normals
498 void TriMesh::invert_winding() {
499 Triangle *tptr = tarray.get_mod_data();
500 int tcount = tarray.get_count();
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;
510 Vertex *vptr = varray.get_mod_data();
511 int vcount = varray.get_count();
513 for(int i=0; i<vcount; i++) {
514 vptr->normal = -vptr->normal;
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()];
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);
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);
536 // now calculate the vertex tangents
537 for(unsigned int i=0; i<varray.get_count(); i++) {
539 for(unsigned int j=0; j<(unsigned int)tri_indices[i].size(); j++) {
540 tangent += tarray.get_data()[tri_indices[i][j]].tangent;
543 // avoid division by zero
544 if(tri_indices[i].size()) {
547 varray.get_mod_data()[i].tangent = tangent;
550 delete [] tri_indices;
553 void TriMesh::apply_xform(const Matrix4x4 &xform) {
554 Vertex *vptr = varray.get_mod_data();
555 unsigned long count = varray.get_count();
557 for(unsigned long i=0; i<count; i++) {
558 vptr->pos.transform(xform);
559 (vptr++)->normal.transform((Matrix3x3)xform);
563 void TriMesh::operator +=(const TriMesh *m2) {
564 join_tri_mesh(this, this, m2);
567 /* TriMesh::sort_triangles - (MG)
568 * sorts triangles according to their distance from a
569 * given point (in model space).
571 void TriMesh::sort_triangles(Vector3 point, bool hilo)
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();
578 // store square distance for each vertex
579 scalar_t *sq_distances = new scalar_t[vcount];
581 for (unsigned int i=0; i<vcount; i++)
583 sq_distances[i] = (verts[i].pos - point).length_sq();
586 // store sum of sq distances for each triangle
587 scalar_t *tri_distances = new scalar_t[tcount];
589 for (unsigned int i=0; i<tcount; i++)
591 tri_distances[i] = 0;
592 for (unsigned int j=0; j<3; j++)
594 tri_distances[i] += sq_distances[tris[i].vertices[j]];
599 sort(tris, tri_distances, tcount, hilo);
602 delete [] sq_distances;
603 delete [] tri_distances;
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;
611 const Vertex *varray = get_vertex_array()->get_data();
612 int count = get_vertex_array()->get_count();
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;
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;
627 vstats.centroid /= count;
629 scalar_t min_len_sq = FLT_MAX;
630 scalar_t max_len_sq = 0.0;
631 scalar_t avg_len_sq = 0.0;
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;
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;
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
655 std::vector<Edge> *TriMesh::get_contour_edges(const Vector3 &pov_or_dir, bool dir)
657 static std::vector<Edge> cont_edges;
659 // calculate triangle normals
660 if(!triangle_normals_valid) {
661 calculate_triangle_normals(false);
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();
669 vector<Edge> *vert_edge = new vector<Edge>[vc];
671 Vector3 direction = pov_or_dir;
672 for(unsigned long i=0; i<tc; i++) {
674 direction = va[ta[i].vertices[0]].pos - pov_or_dir;
677 if(dot_product(ta[i].normal, direction) > 0) {
678 for(int j=0; j<3; j++) {
680 int v1idx = (j + 1) % 3;
682 Index v0 = ta[i].vertices[v0idx];
683 Index v1 = ta[i].vertices[v1idx];
686 std::vector<Edge>::iterator iter = vert_edge[v0].begin();
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);
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);
708 if(!found) vert_edge[v0].push_back(edge);
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]);
725 /* get_uncapped_shadow_volume() - (MG)
726 * specify pov_or_dir in model space
727 * delete the returned mesh after using it
729 const scalar_t infinity = 100000;
730 TriMesh *TriMesh::get_shadow_volume(const Vector3 &pov_or_dir, bool dir)
732 TriMesh *ret = new TriMesh;
734 const Vertex *va = get_vertex_array()->get_data();
735 std::vector<Edge> *contour_edges = get_contour_edges(pov_or_dir, dir);
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;
743 Vertex *verts = new Vertex[num_verts];
744 Triangle *tris = new Triangle[num_tris];
746 // add contour vertices
747 for (unsigned long i=0; i<num_quads; i++)
749 for (unsigned long j=0; j<2; j++)
751 verts[2 * i + j].pos = va[(*contour_edges)[i].vertices[j]].pos;
755 // add extruded vertices
756 for (unsigned long i=0; i<num_verts/2; i++)
758 verts[i + num_verts/2].pos = extrude(verts[i].pos, infinity, pov_or_dir, dir);
762 for (unsigned long i=0; i<num_quads; i++)
764 Index p1, p2, ep1, ep2;
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);
773 ret->set_data(verts, num_verts, tris, num_tris);
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
788 /*TriMesh *TriMesh::get_shadow_volume(const Vector3 &pov_or_dir, bool dir)
790 TriMesh *uncapped = get_uncapped_shadow_volume(pov_or_dir, dir);
791 TriMesh *capped = join_tri_mesh(this, uncapped);
796 /* class VertexOrder - (MG)
797 * used by this module only
812 VertexOrder(Index order, const Vertex& vertex)
815 this->vertex = vertex;
820 static std::vector<unsigned int> process_vo_array(VertexOrder *array, unsigned int size, unsigned int crit);
822 void TriMesh::calculate_index_graph()
824 Index *igraph = new Index[varray.get_count()];
825 for (unsigned int i=0; i<varray.get_count(); i++)
830 VertexOrder *vo = new VertexOrder[varray.get_count()];
831 for (unsigned int i=0; i<varray.get_count(); i++)
833 vo[i] = VertexOrder(i, varray.get_data()[i]);
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);
840 for (unsigned int i=0; i<parts.size(); i += 2)
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++)
846 if(min_index > vo[parts[i] + j].order) {
847 min_index = vo[parts[i] + j].order;
852 for (unsigned int j=0; j<parts[i + 1]; j++)
853 igraph[vo[parts[i] + j].order] = min_index;
856 index_graph.set_data(igraph, varray.get_count());
857 index_graph_valid = true;
863 /* join_tri_mesh - (MG)
864 * Gets 2 trimeshes and returns a new one
865 * that contains both meshes
867 void join_tri_mesh(TriMesh *ret, const TriMesh *m1, const TriMesh *m2)
869 const Vertex *varr1 = m1->get_vertex_array()->get_data();
870 const Vertex *varr2 = m2->get_vertex_array()->get_data();
872 unsigned long vcount1 = m1->get_vertex_array()->get_count();
873 unsigned long vcount2 = m2->get_vertex_array()->get_count();
875 const Triangle *tarr1 = m1->get_triangle_array()->get_data();
876 const Triangle *tarr2 = m2->get_triangle_array()->get_data();
878 unsigned long tcount1 = m1->get_triangle_array()->get_count();
879 unsigned long tcount2 = m2->get_triangle_array()->get_count();
882 int vcount = vcount1 + vcount2;
883 int tcount = tcount1 + tcount2;
884 Vertex *varray = new Vertex[vcount];
885 Triangle *tarray = new Triangle[tcount];
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));
894 for (unsigned long i = 0; i < tcount2; i++)
896 for (int j=0; j<3; j++)
898 tarray[tcount1 + i].vertices[j] += vcount1;
902 ret->set_data(varray, vcount, tarray, tcount);
909 /* Nicer join_tri_mesh - (JT)
910 * This is a much better way to do things.
912 TriMesh *join_tri_mesh(const TriMesh *m1, const TriMesh *m2) {
913 TriMesh *mesh = new TriMesh;
914 join_tri_mesh(mesh, m1, m2);
919 * extrude a vertex given a point of view (or direction) to the specified
922 Vector3 extrude(const Vector3 &vec, scalar_t distance, const Vector3 &pov_or_dir, bool dir) {
926 direction = pov_or_dir;
929 direction = vec - pov_or_dir;
932 direction.normalize();
933 direction *= distance;
935 return vec + direction;
938 /* utilities for finding duplicate vertices - (MG)
940 extern const scalar_t xsmall_number;
942 // Sort criteria for VertexOrder objects
943 static bool vo_sort_crit_x(const VertexOrder& a, const VertexOrder& b)
945 return (a.vertex.pos.x < b.vertex.pos.x);
948 static bool vo_sort_crit_y(const VertexOrder& a, const VertexOrder& b)
950 return (a.vertex.pos.y < b.vertex.pos.y);
953 static bool vo_sort_crit_z(const VertexOrder& a, const VertexOrder& b)
955 return (a.vertex.pos.z < b.vertex.pos.z);
958 // equality criteria for VertexOrder objects
959 static bool vo_eq_crit_x(const VertexOrder& a, const VertexOrder& b)
961 return (b.vertex.pos.x - a.vertex.pos.x < xsmall_number);
964 static bool vo_eq_crit_y(const VertexOrder& a, const VertexOrder& b)
966 return (b.vertex.pos.y - a.vertex.pos.y < xsmall_number);
969 static bool vo_eq_crit_z(const VertexOrder& a, const VertexOrder& b)
971 return (b.vertex.pos.z - a.vertex.pos.z < xsmall_number);
974 static bool (* vo_sort_crit[])(const VertexOrder& a, const VertexOrder& b) = {vo_sort_crit_x, vo_sort_crit_y, vo_sort_crit_z};
976 static bool (* vo_eq_crit[])(const VertexOrder& a, const VertexOrder& b) = {vo_eq_crit_x, vo_eq_crit_y, vo_eq_crit_z};
978 static std::vector<unsigned int> vo_find_constant_parts(VertexOrder *array, unsigned int size, unsigned int crit)
980 std::vector<unsigned int> parts;
981 if (crit > 2) return parts;
983 bool (* eq_crit)(const VertexOrder& a, const VertexOrder& b);
984 eq_crit = vo_eq_crit[crit];
986 unsigned int start=0;
987 for (unsigned int i=0; i<size; i++)
989 if (!eq_crit(array[start], array[i]))
993 parts.push_back(start);
994 parts.push_back(i - start);
1001 if (size - start > 1)
1003 parts.push_back(start);
1004 parts.push_back(size - start);
1010 static std::vector<unsigned int> process_vo_array(VertexOrder *array, unsigned int size, unsigned int crit)
1012 std::vector<unsigned int> r_parts;
1013 if (crit > 2) return r_parts;
1015 bool (* sort_crit)(const VertexOrder& a, const VertexOrder& b);
1016 sort_crit = vo_sort_crit[crit];
1019 std::sort(array, array + size, sort_crit);
1021 // find constant parts
1022 std::vector<unsigned int> parts;
1023 parts = vo_find_constant_parts(array, size, crit);
1027 for (unsigned int i=0; i<parts.size(); i += 2)
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)
1033 r_parts.push_back(new_parts[j] + parts[i]);
1034 r_parts.push_back(new_parts[j+1]);
1041 // found constant z parts. just return them