libs/render.h

   1 /*
   2 Copyright (C) 2001-2006, William Joseph.
   3 All Rights Reserved.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22 #if !defined(INCLUDED_RENDER_H)
  23 #define INCLUDED_RENDER_H
  24
  25 /// \file
  26 /// \brief High-level constructs for efficient OpenGL rendering.
  27
  28 #include "irender.h"
  29 #include "igl.h"
  30
  31 #include "container/array.h"
  32 #include "math/vector.h"
  33 #include "math/pi.h"
  34
  35 #include <vector>
  36
  37 typedef unsigned int RenderIndex;
  38 const GLenum RenderIndexTypeID = GL_UNSIGNED_INT;
  39
  40 /// \brief A resizable buffer of indices.
  41 class IndexBuffer
  42 {
  43   typedef std::vector<RenderIndex> Indices;
  44   Indices m_data;
  45 public:
  46   typedef Indices::iterator iterator;
  47   typedef Indices::const_iterator const_iterator;
  48
  49   iterator begin()
  50   {
  51     return m_data.begin();
  52   }
  53   const_iterator begin() const
  54   {
  55     return m_data.begin();
  56   }
  57   iterator end()
  58   {
  59     return m_data.end();
  60   }
  61   const_iterator end() const
  62   {
  63     return m_data.end();
  64   }
  65
  66   bool empty() const
  67   {
  68     return m_data.empty();
  69   }
  70   std::size_t size() const
  71   {
  72     return m_data.size();
  73   }
  74   const RenderIndex* data() const
  75   {
  76     return &(*m_data.begin());
  77   }
  78   RenderIndex& operator[](std::size_t index)
  79   {
  80     return m_data[index];
  81   }
  82   const RenderIndex& operator[](std::size_t index) const
  83   {
  84     return m_data[index];
  85   }
  86   void clear()
  87   {
  88     m_data.clear();
  89   }
  90   void reserve(std::size_t max_indices)
  91   {
  92     m_data.reserve(max_indices);
  93   }
  94   void insert(RenderIndex index)
  95   {
  96     m_data.push_back(index);
  97   }
  98   void swap(IndexBuffer& other)
  99   {
 100     std::swap(m_data, m_data);
 101   }
 102 };
 103
 104 namespace std
 105 {
 106   /// \brief Swaps the values of \p self and \p other.
 107   /// Overloads std::swap.
 108   inline void swap(IndexBuffer& self, IndexBuffer& other)
 109   {
 110     self.swap(other);
 111   }
 112 }
 113
 114 /// \brief A resizable buffer of vertices.
 115 /// \param Vertex The vertex data type.
 116 template<typename Vertex>
 117 class VertexBuffer
 118 {
 119   typedef typename std::vector<Vertex> Vertices;
 120   Vertices m_data;
 121 public:
 122   typedef typename Vertices::iterator iterator;
 123   typedef typename Vertices::const_iterator const_iterator;
 124
 125   iterator begin()
 126   {
 127     return m_data.begin();
 128   }
 129   iterator end()
 130   {
 131     return m_data.end();
 132   }
 133   const_iterator begin() const
 134   {
 135     return m_data.begin();
 136   }
 137   const_iterator end() const
 138   {
 139     return m_data.end();
 140   }
 141
 142   bool empty() const
 143   {
 144     return m_data.empty();
 145   }
 146   RenderIndex size() const
 147   {
 148     return RenderIndex(m_data.size());
 149   }
 150   const Vertex* data() const
 151   {
 152     return &(*m_data.begin());
 153   }
 154   Vertex& operator[](std::size_t index)
 155   {
 156     return m_data[index];
 157   }
 158   const Vertex& operator[](std::size_t index) const
 159   {
 160     return m_data[index];
 161   }
 162
 163   void clear()
 164   {
 165     m_data.clear();
 166   }
 167   void reserve(std::size_t max_vertices)
 168   {
 169     m_data.reserve(max_vertices);
 170   }
 171   void push_back(const Vertex& vertex)
 172   {
 173     m_data.push_back(vertex);
 174   }
 175 };
 176
 177 /// \brief A wrapper around a VertexBuffer which inserts only vertices which have not already been inserted.
 178 /// \param Vertex The vertex data type. Must support operator<, operator== and operator!=.
 179 /// For best performance, quantise vertices before inserting them.
 180 template<typename Vertex>
 181 class UniqueVertexBuffer
 182 {
 183   typedef VertexBuffer<Vertex> Vertices;
 184   Vertices& m_data;
 185
 186   struct bnode
 187   {
 188     bnode()
 189       : m_left(0), m_right(0)
 190     {
 191     }
 192     RenderIndex m_left;
 193     RenderIndex m_right;
 194   };
 195
 196   std::vector<bnode> m_btree;
 197   RenderIndex m_prev0;
 198   RenderIndex m_prev1;
 199   RenderIndex m_prev2;
 200
 201   const RenderIndex find_or_insert(const Vertex& vertex)
 202   {
 203     RenderIndex index = 0;
 204
 205     while(1)
 206     {
 207       if(vertex < m_data[index])
 208       {
 209         bnode& node = m_btree[index];
 210         if(node.m_left != 0)
 211         {
 212           index = node.m_left;
 213           continue;
 214         }
 215         else
 216         {
 217           node.m_left = RenderIndex(m_btree.size());
 218           m_btree.push_back(bnode());
 219           m_data.push_back(vertex);
 220           return RenderIndex(m_btree.size()-1);
 221         }
 222       }
 223       if(m_data[index] < vertex)
 224       {
 225         bnode& node = m_btree[index];
 226         if(node.m_right != 0)
 227         {
 228           index = node.m_right;
 229           continue;
 230         }
 231         else
 232         {
 233           node.m_right = RenderIndex(m_btree.size());
 234           m_btree.push_back(bnode());
 235           m_data.push_back(vertex);
 236           return RenderIndex(m_btree.size()-1);
 237         }
 238       }
 239
 240       return index;
 241     }
 242   }
 243 public:
 244   UniqueVertexBuffer(Vertices& data)
 245     : m_data(data), m_prev0(0), m_prev1(0), m_prev2(0)
 246   {
 247   }
 248
 249   typedef typename Vertices::const_iterator iterator;
 250
 251   iterator begin() const
 252   {
 253     return m_data.begin();
 254   }
 255   iterator end() const
 256   {
 257     return m_data.end();
 258   }
 259
 260   std::size_t size() const
 261   {
 262     return m_data.size();
 263   }
 264   const Vertex* data() const
 265   {
 266     return &(*m_data.begin());
 267   }
 268   Vertex& operator[](std::size_t index)
 269   {
 270     return m_data[index];
 271   }
 272   const Vertex& operator[](std::size_t index) const
 273   {
 274     return m_data[index];
 275   }
 276
 277   void clear()
 278   {
 279     m_prev0 = 0;
 280     m_prev1 = 0;
 281     m_prev2 = 0;
 282     m_data.clear();
 283     m_btree.clear();
 284   }
 285   void reserve(std::size_t max_vertices)
 286   {
 287     m_data.reserve(max_vertices);
 288     m_btree.reserve(max_vertices);
 289   }
 290   /// \brief Returns the index of the element equal to \p vertex.
 291   RenderIndex insert(const Vertex& vertex)
 292   {
 293     if(m_data.empty())
 294     {
 295       m_data.push_back(vertex);
 296       m_btree.push_back(bnode());
 297       return 0;
 298     }
 299
 300     if(m_data[m_prev0] == vertex)
 301       return m_prev0;
 302     if(m_prev1 != m_prev0 && m_data[m_prev1] == vertex)
 303       return m_prev1;
 304     if(m_prev2 != m_prev0 && m_prev2 != m_prev1 && m_data[m_prev2] == vertex)
 305       return m_prev2;
 306
 307     m_prev2 = m_prev1;
 308     m_prev1 = m_prev0;
 309     m_prev0 = find_or_insert(vertex);
 310
 311     return m_prev0;
 312   }
 313 };
 314
 315
 316 /// \brief A 4-byte colour.
 317 struct Colour4b
 318 {
 319   unsigned char r, g, b, a;
 320
 321   Colour4b()
 322   {
 323   }
 324
 325   Colour4b(unsigned char _r, unsigned char _g, unsigned char _b, unsigned char _a)
 326     : r(_r), g(_g), b(_b), a(_a)
 327   {
 328   }
 329 };
 330
 331 inline bool operator<(const Colour4b& self, const Colour4b& other)
 332 {
 333   if(self.r != other.r)
 334   {
 335     return self.r < other.r;
 336   }
 337   if(self.g != other.g)
 338   {
 339     return self.g < other.g;
 340   }
 341   if(self.b != other.b)
 342   {
 343     return self.b < other.b;
 344   }
 345   if(self.a != other.a)
 346   {
 347     return self.a < other.a;
 348   }
 349   return false;
 350 }
 351
 352 inline bool operator==(const Colour4b& self, const Colour4b& other)
 353 {
 354   return self.r == other.r && self.g == other.g && self.b == other.b && self.a == other.a;
 355 }
 356
 357 inline bool operator!=(const Colour4b& self, const Colour4b& other)
 358 {
 359   return !operator==(self, other);
 360 }
 361
 362 /// \brief A 3-float vertex.
 363 struct Vertex3f : public Vector3
 364 {
 365   Vertex3f()
 366   {
 367   }
 368
 369   Vertex3f(float _x, float _y, float _z)
 370     : Vector3(_x, _y, _z)
 371   {
 372   }
 373 };
 374
 375 inline bool operator<(const Vertex3f& self, const Vertex3f& other)
 376 {
 377   if(self.x() != other.x())
 378   {
 379     return self.x() < other.x();
 380   }
 381   if(self.y() != other.y())
 382   {
 383     return self.y() < other.y();
 384   }
 385   if(self.z() != other.z())
 386   {
 387     return self.z() < other.z();
 388   }
 389   return false;
 390 }
 391
 392 inline bool operator==(const Vertex3f& self, const Vertex3f& other)
 393 {
 394   return self.x() == other.x() && self.y() == other.y() && self.z() == other.z();
 395 }
 396
 397 inline bool operator!=(const Vertex3f& self, const Vertex3f& other)
 398 {
 399   return !operator==(self, other);
 400 }
 401
 402
 403 inline Vertex3f vertex3f_from_array(const float* array)
 404 {
 405   return Vertex3f(array[0], array[1], array[2]);
 406 }
 407
 408 inline float* vertex3f_to_array(Vertex3f& vertex)
 409 {
 410   return reinterpret_cast<float*>(&vertex);
 411 }
 412
 413 inline const float* vertex3f_to_array(const Vertex3f& vertex)
 414 {
 415   return reinterpret_cast<const float*>(&vertex);
 416 }
 417
 418 const Vertex3f vertex3f_identity(0, 0, 0);
 419
 420 inline Vertex3f vertex3f_for_vector3(const Vector3& vector3)
 421 {
 422   return Vertex3f(vector3.x(), vector3.y(), vector3.z());
 423 }
 424
 425 inline const Vector3& vertex3f_to_vector3(const Vertex3f& vertex)
 426 {
 427   return vertex;
 428 }
 429
 430 inline Vector3& vertex3f_to_vector3(Vertex3f& vertex)
 431 {
 432   return vertex;
 433 }
 434
 435
 436 /// \brief A 3-float normal.
 437 struct Normal3f : public Vector3
 438 {
 439   Normal3f()
 440   {
 441   }
 442
 443   Normal3f(float _x, float _y, float _z)
 444     : Vector3(_x, _y, _z)
 445   {
 446   }
 447 };
 448
 449 inline bool operator<(const Normal3f& self, const Normal3f& other)
 450 {
 451   if(self.x() != other.x())
 452   {
 453     return self.x() < other.x();
 454   }
 455   if(self.y() != other.y())
 456   {
 457     return self.y() < other.y();
 458   }
 459   if(self.z() != other.z())
 460   {
 461     return self.z() < other.z();
 462   }
 463   return false;
 464 }
 465
 466 inline bool operator==(const Normal3f& self, const Normal3f& other)
 467 {
 468   return self.x() == other.x() && self.y() == other.y() && self.z() == other.z();
 469 }
 470
 471 inline bool operator!=(const Normal3f& self, const Normal3f& other)
 472 {
 473   return !operator==(self, other);
 474 }
 475
 476
 477 inline Normal3f normal3f_from_array(const float* array)
 478 {
 479   return Normal3f(array[0], array[1], array[2]);
 480 }
 481
 482 inline float* normal3f_to_array(Normal3f& normal)
 483 {
 484   return reinterpret_cast<float*>(&normal);
 485 }
 486
 487 inline const float* normal3f_to_array(const Normal3f& normal)
 488 {
 489   return reinterpret_cast<const float*>(&normal);
 490 }
 491
 492 inline Normal3f normal3f_for_vector3(const Vector3& vector3)
 493 {
 494   return Normal3f(vector3.x(), vector3.y(), vector3.z());
 495 }
 496
 497 inline const Vector3& normal3f_to_vector3(const Normal3f& normal)
 498 {
 499   return normal;
 500 }
 501
 502 inline Vector3& normal3f_to_vector3(Normal3f& normal)
 503 {
 504   return normal;
 505 }
 506
 507
 508 /// \brief A 2-float texture-coordinate set.
 509 struct TexCoord2f : public Vector2
 510 {
 511   TexCoord2f()
 512   {
 513   }
 514
 515   TexCoord2f(float _s, float _t)
 516     : Vector2(_s, _t)
 517   {
 518   }
 519
 520   float& s()
 521   {
 522     return x();
 523   }
 524   const float& s() const
 525   {
 526     return x();
 527   }
 528   float& t()
 529   {
 530     return y();
 531   }
 532   const float& t() const
 533   {
 534     return y();
 535   }
 536 };
 537
 538 inline bool operator<(const TexCoord2f& self, const TexCoord2f& other)
 539 {
 540   if(self.s() != other.s())
 541   {
 542     return self.s() < other.s();
 543   }
 544   if(self.t() != other.t())
 545   {
 546     return self.t() < other.t();
 547   }
 548   return false;
 549 }
 550
 551 inline bool operator==(const TexCoord2f& self, const TexCoord2f& other)
 552 {
 553   return self.s() == other.s() && self.t() == other.t();
 554 }
 555
 556 inline bool operator!=(const TexCoord2f& self, const TexCoord2f& other)
 557 {
 558   return !operator==(self, other);
 559 }
 560
 561
 562 inline float* texcoord2f_to_array(TexCoord2f& texcoord)
 563 {
 564   return reinterpret_cast<float*>(&texcoord);
 565 }
 566
 567 inline const float* texcoord2f_to_array(const TexCoord2f& texcoord)
 568 {
 569   return reinterpret_cast<const float*>(&texcoord);
 570 }
 571
 572 inline const TexCoord2f& texcoord2f_from_array(const float* array)
 573 {
 574   return *reinterpret_cast<const TexCoord2f*>(array);
 575 }
 576
 577 inline TexCoord2f texcoord2f_for_vector2(const Vector2& vector2)
 578 {
 579   return TexCoord2f(vector2.x(), vector2.y());
 580 }
 581
 582 inline const Vector2& texcoord2f_to_vector2(const TexCoord2f& vertex)
 583 {
 584   return vertex;
 585 }
 586
 587 inline Vector2& texcoord2f_to_vector2(TexCoord2f& vertex)
 588 {
 589   return vertex;
 590 }
 591
 592 /// \brief Returns \p normal rescaled to be unit-length.
 593 inline Normal3f normal3f_normalised(const Normal3f& normal)
 594 {
 595   return normal3f_for_vector3(vector3_normalised(normal3f_to_vector3(normal)));
 596 }
 597
 598 enum UnitSphereOctant
 599 {
 600   UNITSPHEREOCTANT_000 = 0 << 0 | 0 << 1 | 0 << 2,
 601   UNITSPHEREOCTANT_001 = 0 << 0 | 0 << 1 | 1 << 2,
 602   UNITSPHEREOCTANT_010 = 0 << 0 | 1 << 1 | 0 << 2,
 603   UNITSPHEREOCTANT_011 = 0 << 0 | 1 << 1 | 1 << 2,
 604   UNITSPHEREOCTANT_100 = 1 << 0 | 0 << 1 | 0 << 2,
 605   UNITSPHEREOCTANT_101 = 1 << 0 | 0 << 1 | 1 << 2,
 606   UNITSPHEREOCTANT_110 = 1 << 0 | 1 << 1 | 0 << 2,
 607   UNITSPHEREOCTANT_111 = 1 << 0 | 1 << 1 | 1 << 2,
 608 };
 609
 610 /// \brief Returns the octant for \p normal indicating the sign of the region of unit-sphere space it lies within.
 611 inline UnitSphereOctant normal3f_classify_octant(const Normal3f& normal)
 612 {
 613   return static_cast<UnitSphereOctant>(
 614     ((normal.x() > 0) << 0) | ((normal.y() > 0) << 1) | ((normal.z() > 0) << 2)
 615   );
 616 }
 617
 618 /// \brief Returns \p normal with its components signs made positive based on \p octant.
 619 inline Normal3f normal3f_fold_octant(const Normal3f& normal, UnitSphereOctant octant)
 620 {
 621   switch(octant)
 622   {
 623   case UNITSPHEREOCTANT_000:
 624     return Normal3f(-normal.x(), -normal.y(), -normal.z());
 625   case UNITSPHEREOCTANT_001:
 626     return Normal3f(normal.x(), -normal.y(), -normal.z());
 627   case UNITSPHEREOCTANT_010:
 628     return Normal3f(-normal.x(), normal.y(), -normal.z());
 629   case UNITSPHEREOCTANT_011:
 630     return Normal3f(normal.x(), normal.y(), -normal.z());
 631   case UNITSPHEREOCTANT_100:
 632     return Normal3f(-normal.x(), -normal.y(), normal.z());
 633   case UNITSPHEREOCTANT_101:
 634     return Normal3f(normal.x(), -normal.y(), normal.z());
 635   case UNITSPHEREOCTANT_110:
 636     return Normal3f(-normal.x(), normal.y(), normal.z());
 637   case UNITSPHEREOCTANT_111:
 638     return Normal3f(normal.x(), normal.y(), normal.z());
 639   }
 640   return Normal3f();
 641 }
 642
 643 /// \brief Reverses the effect of normal3f_fold_octant() on \p normal with \p octant.
 644 /// \p normal must have been obtained with normal3f_fold_octant().
 645 /// \p octant must have been obtained with normal3f_classify_octant().
 646 inline Normal3f normal3f_unfold_octant(const Normal3f& normal, UnitSphereOctant octant)
 647 {
 648   return normal3f_fold_octant(normal, octant);
 649 }
 650
 651 enum UnitSphereSextant
 652 {
 653   UNITSPHERESEXTANT_XYZ = 0,
 654   UNITSPHERESEXTANT_XZY = 1,
 655   UNITSPHERESEXTANT_YXZ = 2,
 656   UNITSPHERESEXTANT_YZX = 3,
 657   UNITSPHERESEXTANT_ZXY = 4,
 658   UNITSPHERESEXTANT_ZYX = 5,
 659 };
 660
 661 /// \brief Returns the sextant for \p normal indicating how to sort its components so that x > y > z.
 662 /// All components of \p normal must be positive.
 663 /// \p normal must be normalised.
 664 inline UnitSphereSextant normal3f_classify_sextant(const Normal3f& normal)
 665 {
 666   return
 667     normal.x() >= normal.y()
 668     ? normal.x() >= normal.z()
 669       ? normal.y() >= normal.z()
 670         ? UNITSPHERESEXTANT_XYZ
 671         : UNITSPHERESEXTANT_XZY
 672         : UNITSPHERESEXTANT_ZXY
 673         : normal.y() >= normal.z()
 674         ? normal.x() >= normal.z()
 675         ? UNITSPHERESEXTANT_YXZ
 676         : UNITSPHERESEXTANT_YZX
 677         : UNITSPHERESEXTANT_ZYX;
 678 }
 679
 680 /// \brief Returns \p normal with its components sorted so that x > y > z based on \p sextant.
 681 /// All components of \p normal must be positive.
 682 /// \p normal must be normalised.
 683 inline Normal3f normal3f_fold_sextant(const Normal3f& normal, UnitSphereSextant sextant)
 684 {
 685   switch(sextant)
 686   {
 687   case UNITSPHERESEXTANT_XYZ:
 688     return Normal3f(normal.x(), normal.y(), normal.z());
 689   case UNITSPHERESEXTANT_XZY:
 690     return Normal3f(normal.x(), normal.z(), normal.y());
 691   case UNITSPHERESEXTANT_YXZ:
 692     return Normal3f(normal.y(), normal.x(), normal.z());
 693   case UNITSPHERESEXTANT_YZX:
 694     return Normal3f(normal.y(), normal.z(), normal.x());
 695   case UNITSPHERESEXTANT_ZXY:
 696     return Normal3f(normal.z(), normal.x(), normal.y());
 697   case UNITSPHERESEXTANT_ZYX:
 698     return Normal3f(normal.z(), normal.y(), normal.x());
 699   }
 700   return Normal3f();
 701 }
 702
 703 /// \brief Reverses the effect of normal3f_fold_sextant() on \p normal with \p sextant.
 704 /// \p normal must have been obtained with normal3f_fold_sextant().
 705 /// \p sextant must have been obtained with normal3f_classify_sextant().
 706 inline Normal3f normal3f_unfold_sextant(const Normal3f& normal, UnitSphereSextant sextant)
 707 {
 708         return normal3f_fold_sextant(normal, sextant);
 709 }
 710
 711 const std::size_t c_quantise_normal = 1 << 6;
 712
 713 /// \brief All the components of \p folded must be positive and sorted so that x > y > z.
 714 inline Normal3f normal3f_folded_quantised(const Normal3f& folded)
 715 {
 716   // compress
 717   double scale = static_cast<float>(c_quantise_normal) / (folded.x() + folded.y() + folded.z());
 718   unsigned int zbits = static_cast<unsigned int>(folded.z() * scale);
 719   unsigned int ybits = static_cast<unsigned int>(folded.y() * scale);
 720
 721   // decompress
 722   return normal3f_normalised(Normal3f(
 723     static_cast<float>(c_quantise_normal - zbits - ybits),
 724     static_cast<float>(ybits),
 725     static_cast<float>(zbits)
 726   ));
 727 }
 728
 729 /// \brief Returns \p normal quantised by compressing and then decompressing its representation.
 730 inline Normal3f normal3f_quantised_custom(const Normal3f& normal)
 731 {
 732   UnitSphereOctant octant = normal3f_classify_octant(normal);
 733   Normal3f folded = normal3f_fold_octant(normal, octant);
 734   UnitSphereSextant sextant = normal3f_classify_sextant(folded);
 735   folded = normal3f_fold_sextant(folded, sextant);
 736   return normal3f_unfold_octant(normal3f_unfold_sextant(normal3f_folded_quantised(folded), sextant), octant);
 737 }
 738
 739
 740
 741 struct spherical_t
 742 {
 743   double longditude, latitude;
 744
 745   spherical_t(double _longditude, double _latitude)
 746     : longditude(_longditude), latitude(_latitude)
 747   {
 748   }
 749 };
 750
 751 /*
 752 {
 753   theta = 2pi * U;
 754   phi = acos((2 * V) - 1);
 755
 756   U = theta / 2pi;
 757   V = (cos(phi) + 1) / 2;
 758 }
 759
 760 longitude = atan(y / x);
 761 latitude = acos(z);
 762 */
 763 struct uniformspherical_t
 764 {
 765   double U, V;
 766
 767   uniformspherical_t(double U_, double V_)
 768     : U(U_), V(V_)
 769   {
 770   }
 771 };
 772
 773
 774 inline spherical_t spherical_from_normal3f(const Normal3f& normal)
 775 {
 776   return spherical_t(normal.x() == 0 ? c_pi / 2 : normal.x() > 0 ? atan(normal.y() / normal.x()) : atan(normal.y() / normal.x()) + c_pi, acos(normal.z()));
 777 }
 778
 779 inline Normal3f normal3f_from_spherical(const spherical_t& spherical)
 780 {
 781   return Normal3f(
 782     static_cast<float>(cos(spherical.longditude) * sin(spherical.latitude)),
 783     static_cast<float>(sin(spherical.longditude) * sin(spherical.latitude)),
 784     static_cast<float>(cos(spherical.latitude))
 785   );
 786 }
 787
 788 inline uniformspherical_t uniformspherical_from_spherical(const spherical_t& spherical)
 789 {
 790   return uniformspherical_t(spherical.longditude * c_inv_2pi, (cos(spherical.latitude) + 1) * 0.5);
 791 }
 792
 793 inline spherical_t spherical_from_uniformspherical(const uniformspherical_t& uniformspherical)
 794 {
 795   return spherical_t(c_2pi * uniformspherical.U, acos((2 * uniformspherical.V) - 1));
 796 }
 797
 798 inline uniformspherical_t uniformspherical_from_normal3f(const Normal3f& normal)
 799 {
 800   return uniformspherical_from_spherical(spherical_from_normal3f(normal));
 801   //return uniformspherical_t(atan2(normal.y / normal.x) * c_inv_2pi, (normal.z + 1) * 0.5);
 802 }
 803
 804 inline Normal3f normal3f_from_uniformspherical(const uniformspherical_t& uniformspherical)
 805 {
 806   return normal3f_from_spherical(spherical_from_uniformspherical(uniformspherical));
 807 }
 808
 809 /// \brief Returns a single-precision \p component quantised to \p precision.
 810 inline float float_quantise(float component, float precision)
 811 {
 812   return float_snapped(component, precision);
 813 }
 814
 815 /// \brief Returns a double-precision \p component quantised to \p precision.
 816 inline double double_quantise(double component, double precision)
 817 {
 818   return float_snapped(component, precision);
 819 }
 820
 821 inline spherical_t spherical_quantised(const spherical_t& spherical, float snap)
 822 {
 823   return spherical_t(double_quantise(spherical.longditude, snap), double_quantise(spherical.latitude, snap));
 824 }
 825
 826 inline uniformspherical_t uniformspherical_quantised(const uniformspherical_t& uniformspherical, float snap)
 827 {
 828   return uniformspherical_t(double_quantise(uniformspherical.U, snap), double_quantise(uniformspherical.V, snap));
 829 }
 830
 831 /// \brief Returns a \p vertex quantised to \p precision.
 832 inline Vertex3f vertex3f_quantised(const Vertex3f& vertex, float precision)
 833 {
 834   return Vertex3f(float_quantise(vertex.x(), precision), float_quantise(vertex.y(), precision), float_quantise(vertex.z(), precision));
 835 }
 836
 837 /// \brief Returns a \p normal quantised to a fixed precision.
 838 inline Normal3f normal3f_quantised(const Normal3f& normal)
 839 {
 840         return normal3f_quantised_custom(normal);
 841   //return normal3f_from_spherical(spherical_quantised(spherical_from_normal3f(normal), snap));
 842   //return normal3f_from_uniformspherical(uniformspherical_quantised(uniformspherical_from_normal3f(normal), snap));
 843   //  float_quantise(normal.x, snap), float_quantise(normal.y, snap), float_quantise(normal.y, snap));
 844 }
 845
 846 /// \brief Returns a \p texcoord quantised to \p precision.
 847 inline TexCoord2f texcoord2f_quantised(const TexCoord2f& texcoord, float precision)
 848 {
 849   return TexCoord2f(float_quantise(texcoord.s(), precision), float_quantise(texcoord.t(), precision));
 850 }
 851
 852 /// \brief Standard vertex type for lines and points.
 853 struct PointVertex
 854 {
 855   Colour4b colour;
 856   Vertex3f vertex;
 857
 858   PointVertex()
 859   {
 860   }
 861   PointVertex(Vertex3f _vertex)
 862     : colour(Colour4b(255, 255, 255, 255)), vertex(_vertex)
 863   {
 864   }
 865   PointVertex(Vertex3f _vertex, Colour4b _colour)
 866     : colour(_colour), vertex(_vertex)
 867   {
 868   }
 869 };
 870
 871 inline bool operator<(const PointVertex& self, const PointVertex& other)
 872 {
 873   if(self.vertex != other.vertex)
 874   {
 875     return self.vertex < other.vertex;
 876   }
 877   if(self.colour != other.colour)
 878   {
 879     return self.colour < other.colour;
 880   }
 881   return false;
 882 }
 883
 884 inline bool operator==(const PointVertex& self, const PointVertex& other)
 885 {
 886   return self.colour == other.colour && self.vertex == other.vertex;
 887 }
 888
 889 inline bool operator!=(const PointVertex& self, const PointVertex& other)
 890 {
 891   return !operator==(self, other);
 892 }
 893
 894 /// \brief Standard vertex type for lit/textured meshes.
 895 struct ArbitraryMeshVertex
 896 {
 897   TexCoord2f texcoord;
 898   Normal3f normal;
 899   Vertex3f vertex;
 900   Normal3f tangent;
 901   Normal3f bitangent;
 902
 903   ArbitraryMeshVertex() : tangent(0, 0, 0), bitangent(0, 0, 0)
 904   {
 905   }
 906   ArbitraryMeshVertex(Vertex3f _vertex, Normal3f _normal, TexCoord2f _texcoord)
 907     : texcoord(_texcoord), normal(_normal), vertex(_vertex), tangent(0, 0, 0), bitangent(0, 0, 0)
 908   {
 909   }
 910 };
 911
 912 inline bool operator<(const ArbitraryMeshVertex& self, const ArbitraryMeshVertex& other)
 913 {
 914   if(self.texcoord != other.texcoord)
 915   {
 916     return self.texcoord < other.texcoord;
 917   }
 918   if(self.normal != other.normal)
 919   {
 920     return self.normal < other.normal;
 921   }
 922   if(self.vertex != other.vertex)
 923   {
 924     return self.vertex < other.vertex;
 925   }
 926   return false;
 927 }
 928
 929 inline bool operator==(const ArbitraryMeshVertex& self, const ArbitraryMeshVertex& other)
 930 {
 931   return self.texcoord == other.texcoord && self.normal == other.normal && self.vertex == other.vertex;
 932 }
 933
 934 inline bool operator!=(const ArbitraryMeshVertex& self, const ArbitraryMeshVertex& other)
 935 {
 936   return !operator==(self, other);
 937 }
 938
 939 const float c_quantise_vertex = 1.f / static_cast<float>(1 << 3);
 940
 941 /// \brief Returns \p v with vertex quantised to a fixed precision.
 942 inline PointVertex pointvertex_quantised(const PointVertex& v)
 943 {
 944   return PointVertex(vertex3f_quantised(v.vertex, c_quantise_vertex), v.colour);
 945 }
 946
 947 const float c_quantise_texcoord = 1.f / static_cast<float>(1 << 8);
 948
 949 /// \brief Returns \p v with vertex, normal and texcoord quantised to a fixed precision.
 950 inline ArbitraryMeshVertex arbitrarymeshvertex_quantised(const ArbitraryMeshVertex& v)
 951 {
 952   return ArbitraryMeshVertex(vertex3f_quantised(v.vertex, c_quantise_vertex), normal3f_quantised(v.normal), texcoord2f_quantised(v.texcoord, c_quantise_texcoord));
 953 }
 954
 955
 956 /// \brief Sets up the OpenGL colour and vertex arrays for \p array.
 957 inline void pointvertex_gl_array(const PointVertex* array)
 958 {
 959   glColorPointer(4, GL_UNSIGNED_BYTE, sizeof(PointVertex), &array->colour);
 960   glVertexPointer(3, GL_FLOAT, sizeof(PointVertex), &array->vertex);
 961 }
 962
 963 class RenderablePointArray : public OpenGLRenderable
 964 {
 965   const Array<PointVertex>& m_array;
 966   const GLenum m_mode;
 967 public:
 968   RenderablePointArray(const Array<PointVertex>& array, GLenum mode)
 969     : m_array(array), m_mode(mode)
 970   {
 971   }
 972   void render(RenderStateFlags state) const
 973   {
 974 #define NV_DRIVER_BUG 1
 975 #if NV_DRIVER_BUG
 976     glColorPointer(4, GL_UNSIGNED_BYTE, 0, 0);
 977     glVertexPointer(3, GL_FLOAT, 0, 0);
 978     glDrawArrays(GL_TRIANGLE_FAN, 0, 0);
 979 #endif
 980     pointvertex_gl_array(m_array.data());
 981     glDrawArrays(m_mode, 0, GLsizei(m_array.size()));
 982   }
 983 };
 984
 985 class RenderablePointVector : public OpenGLRenderable
 986 {
 987   std::vector<PointVertex> m_vector;
 988   const GLenum m_mode;
 989 public:
 990   RenderablePointVector(GLenum mode)
 991     : m_mode(mode)
 992   {
 993   }
 994
 995   void render(RenderStateFlags state) const
 996   {
 997     pointvertex_gl_array(&m_vector.front());
 998     glDrawArrays(m_mode, 0, GLsizei(m_vector.size()));
 999   }
1000
1001   std::size_t size() const
1002   {
1003     return m_vector.size();
1004   }
1005   bool empty() const
1006   {
1007     return m_vector.empty();
1008   }
1009   void clear()
1010   {
1011     m_vector.clear();
1012   }
1013   void reserve(std::size_t size)
1014   {
1015     m_vector.reserve(size);
1016   }
1017   void push_back(const PointVertex& point)
1018   {
1019     m_vector.push_back(point);
1020   }
1021 };
1022
1023
1024 class RenderableVertexBuffer : public OpenGLRenderable
1025 {
1026   const GLenum m_mode;
1027   const VertexBuffer<PointVertex>& m_vertices;
1028 public:
1029   RenderableVertexBuffer(GLenum mode, const VertexBuffer<PointVertex>& vertices)
1030     : m_mode(mode), m_vertices(vertices)
1031   {
1032   }
1033
1034   void render(RenderStateFlags state) const
1035   {
1036     pointvertex_gl_array(m_vertices.data());
1037     glDrawArrays(m_mode, 0, m_vertices.size());
1038   }
1039 };
1040
1041 class RenderableIndexBuffer : public OpenGLRenderable
1042 {
1043   const GLenum m_mode;
1044   const IndexBuffer& m_indices;
1045   const VertexBuffer<PointVertex>& m_vertices;
1046 public:
1047   RenderableIndexBuffer(GLenum mode, const IndexBuffer& indices, const VertexBuffer<PointVertex>& vertices)
1048     : m_mode(mode), m_indices(indices), m_vertices(vertices)
1049   {
1050   }
1051
1052   void render(RenderStateFlags state) const
1053   {
1054 #if 1
1055     pointvertex_gl_array(m_vertices.data());
1056     glDrawElements(m_mode, GLsizei(m_indices.size()), RenderIndexTypeID, m_indices.data());
1057 #else
1058     glBegin(m_mode);
1059     if(state & RENDER_COLOURARRAY != 0)
1060     {
1061       for(std::size_t i = 0; i < m_indices.size(); ++i)
1062       {
1063         glColor4ubv(&m_vertices[m_indices[i]].colour.r);
1064         glVertex3fv(&m_vertices[m_indices[i]].vertex.x);
1065       }
1066     }
1067     else
1068     {
1069       for(std::size_t i = 0; i < m_indices.size(); ++i)
1070       {
1071         glVertex3fv(&m_vertices[m_indices[i]].vertex.x);
1072       }
1073     }
1074     glEnd();
1075 #endif
1076   }
1077 };
1078
1079
1080 class RemapXYZ
1081 {
1082 public:
1083   static void set(Vertex3f& vertex, float x, float y, float z)
1084   {
1085     vertex.x() = x;
1086     vertex.y() = y;
1087     vertex.z() = z;
1088   }
1089 };
1090
1091 class RemapYZX
1092 {
1093 public:
1094   static void set(Vertex3f& vertex, float x, float y, float z)
1095   {
1096     vertex.x() = z;
1097     vertex.y() = x;
1098     vertex.z() = y;
1099   }
1100 };
1101
1102 class RemapZXY
1103 {
1104 public:
1105   static void set(Vertex3f& vertex, float x, float y, float z)
1106   {
1107     vertex.x() = y;
1108     vertex.y() = z;
1109     vertex.z() = x;
1110   }
1111 };
1112
1113 template<typename remap_policy>
1114 inline void draw_circle(const std::size_t segments, const float radius, PointVertex* vertices, remap_policy remap)
1115 {
1116   const double increment = c_pi / double(segments << 2);
1117
1118   std::size_t count = 0;
1119   float x = radius;
1120   float y = 0;
1121   while(count < segments)
1122   {
1123     PointVertex* i = vertices + count;
1124     PointVertex* j = vertices + ((segments << 1) - (count + 1));
1125
1126     PointVertex* k = i + (segments << 1);
1127     PointVertex* l = j + (segments << 1);
1128
1129     PointVertex* m = i + (segments << 2);
1130     PointVertex* n = j + (segments << 2);
1131     PointVertex* o = k + (segments << 2);
1132     PointVertex* p = l + (segments << 2);
1133
1134     remap_policy::set(i->vertex, x,-y, 0);
1135     remap_policy::set(k->vertex,-y,-x, 0);
1136     remap_policy::set(m->vertex,-x, y, 0);
1137     remap_policy::set(o->vertex, y, x, 0);
1138
1139     ++count;
1140
1141     {
1142       const double theta = increment * count;
1143       x = static_cast<float>(radius * cos(theta));
1144       y = static_cast<float>(radius * sin(theta));
1145     }
1146
1147     remap_policy::set(j->vertex, y,-x, 0);
1148     remap_policy::set(l->vertex,-x,-y, 0);
1149     remap_policy::set(n->vertex,-y, x, 0);
1150     remap_policy::set(p->vertex, x, y, 0);
1151   }
1152 }
1153
1154 #if 0
1155 class PointVertexArrayIterator
1156 {
1157   PointVertex* m_point;
1158 public:
1159   PointVertexArrayIterator(PointVertex* point)
1160     : m_point(point)
1161   {
1162   }
1163   PointVertexArrayIterator& operator++()
1164   {
1165     ++m_point;
1166     return *this;
1167   }
1168   PointVertexArrayIterator operator++(int)
1169   {
1170     PointVertexArrayIterator tmp(*this);
1171     ++m_point;
1172     return tmp;
1173   }
1174   Vertex3f& operator*()
1175   {
1176     return m_point.vertex;
1177   }
1178   Vertex3f* operator->()
1179   {
1180     return &(operator*());
1181   }
1182 }
1183
1184 template<typename remap_policy, typename iterator_type
1185 inline void draw_circle(const std::size_t segments, const float radius, iterator_type start, remap_policy remap)
1186 {
1187   const float increment = c_pi / (double)(segments << 2);
1188
1189   std::size_t count = 0;
1190   iterator_type pxpy(start);
1191   iterator_type pypx(pxpy + (segments << 1));
1192   iterator_type pynx(pxpy + (segments << 1));
1193   iterator_type nxpy(pypx + (segments << 1));
1194   iterator_type nxny(pypx + (segments << 1));
1195   iterator_type nynx(nxpy + (segments << 1));
1196   iterator_type nypx(nxpy + (segments << 1));
1197   iterator_type pxny(start);
1198   while(count < segments)
1199   {
1200     const float theta = increment * count;
1201     const float x = radius * cos(theta);
1202     const float y = radius * sin(theta);
1203
1204     remap_policy::set((*pxpy), x, y, 0);
1205     remap_policy::set((*pxny), x,-y, 0);
1206     remap_policy::set((*nxpy),-x, y, 0);
1207     remap_policy::set((*nxny),-x,-y, 0);
1208
1209     remap_policy::set((*pypx), y, x, 0);
1210     remap_policy::set((*pynx), y,-x, 0);
1211     remap_policy::set((*nypx),-y, x, 0);
1212     remap_policy::set((*nynx),-y,-x, 0);
1213   }
1214 }
1215
1216 template<typename remap_policy, typename iterator_type
1217 inline void draw_semicircle(const std::size_t segments, const float radius, iterator_type start, remap_policy remap)
1218 {
1219   const float increment = c_pi / (double)(segments << 2);
1220
1221   std::size_t count = 0;
1222   iterator_type pxpy(start);
1223   iterator_type pypx(pxpy + (segments << 1));
1224   iterator_type pynx(pxpy + (segments << 1));
1225   iterator_type nxpy(pypx + (segments << 1));
1226   iterator_type nxny(pypx + (segments << 1));
1227   iterator_type nynx(nxpy + (segments << 1));
1228   iterator_type nypx(nxpy + (segments << 1));
1229   iterator_type pxny(start);
1230   while(count < segments)
1231   {
1232     const float theta = increment * count;
1233     const float x = radius * cos(theta);
1234     const float y = radius * sin(theta);
1235
1236     remap_policy::set((*pxpy), x, y, 0);
1237     remap_policy::set((*pxny), x,-y, 0);
1238     remap_policy::set((*nxpy),-x, y, 0);
1239     remap_policy::set((*nxny),-x,-y, 0);
1240
1241     //remap_policy::set((*pypx), y, x, 0);
1242     //remap_policy::set((*pynx), y,-x, 0);
1243     //remap_policy::set((*nypx),-y, x, 0);
1244     //remap_policy::set((*nynx),-y,-x, 0);
1245   }
1246 }
1247
1248
1249 #endif
1250
1251 inline void draw_quad(const float radius, PointVertex* quad)
1252 {
1253   (*quad++).vertex = Vertex3f(-radius, radius, 0);
1254   (*quad++).vertex = Vertex3f(radius, radius, 0);
1255   (*quad++).vertex = Vertex3f(radius, -radius, 0);
1256   (*quad++).vertex = Vertex3f(-radius, -radius, 0);
1257 }
1258
1259 inline void draw_cube(const float radius, PointVertex* cube)
1260 {
1261   (*cube++).vertex = Vertex3f(-radius, -radius, -radius);
1262   (*cube++).vertex = Vertex3f(radius, -radius, -radius);
1263   (*cube++).vertex = Vertex3f(-radius, radius, -radius);
1264   (*cube++).vertex = Vertex3f(radius, radius, -radius);
1265   (*cube++).vertex = Vertex3f(-radius, -radius, radius);
1266   (*cube++).vertex = Vertex3f(radius, -radius, radius);
1267   (*cube++).vertex = Vertex3f(-radius, radius, radius);
1268   (*cube++).vertex = Vertex3f(radius, radius, radius);
1269 }
1270
1271
1272 /// \brief Calculates the tangent vectors for a triangle \p a, \p b, \p c and stores the tangent in \p s and the bitangent in \p t.
1273 inline void ArbitraryMeshTriangle_calcTangents(const ArbitraryMeshVertex& a, const ArbitraryMeshVertex& b, const ArbitraryMeshVertex& c, Vector3& s, Vector3& t)
1274 {
1275   s = Vector3(0, 0, 0);
1276   t = Vector3(0, 0, 0);
1277   {
1278     Vector3 cross(
1279       vector3_cross(
1280         vector3_subtracted(
1281           Vector3(b.vertex.x(), b.texcoord.s(), b.texcoord.t()),
1282           Vector3(a.vertex.x(), a.texcoord.s(), a.texcoord.t())
1283         ),
1284         vector3_subtracted(
1285           Vector3(c.vertex.x(), c.texcoord.s(), c.texcoord.t()),
1286           Vector3(a.vertex.x(), a.texcoord.s(), a.texcoord.t())
1287         )
1288       )
1289     );
1290
1291     if(fabs(cross.x()) > 0.000001f)
1292     {
1293       s.x() = -cross.y() / cross.x();
1294     }
1295
1296     if(fabs(cross.x()) > 0.000001f)
1297     {
1298       t.x() = -cross.z() / cross.x();
1299     }
1300   }
1301
1302   {
1303     Vector3 cross(
1304       vector3_cross(
1305         vector3_subtracted(
1306           Vector3(b.vertex.y(), b.texcoord.s(), b.texcoord.t()),
1307           Vector3(a.vertex.y(), a.texcoord.s(), a.texcoord.t())
1308         ),
1309         vector3_subtracted(
1310           Vector3(c.vertex.y(), c.texcoord.s(), c.texcoord.t()),
1311           Vector3(a.vertex.y(), a.texcoord.s(), a.texcoord.t())
1312         )
1313       )
1314     );
1315
1316     if(fabs(cross.x()) > 0.000001f)
1317     {
1318       s.y() = -cross.y() / cross.x();
1319     }
1320
1321     if(fabs(cross.x()) > 0.000001f)
1322     {
1323       t.y() = -cross.z() / cross.x();
1324     }
1325   }
1326
1327   {
1328     Vector3 cross(
1329       vector3_cross(
1330         vector3_subtracted(
1331           Vector3(b.vertex.z(), b.texcoord.s(), b.texcoord.t()),
1332           Vector3(a.vertex.z(), a.texcoord.s(), a.texcoord.t())
1333         ),
1334         vector3_subtracted(
1335           Vector3(c.vertex.z(), c.texcoord.s(), c.texcoord.t()),
1336           Vector3(a.vertex.z(), a.texcoord.s(), a.texcoord.t())
1337         )
1338       )
1339     );
1340
1341     if(fabs(cross.x()) > 0.000001f)
1342     {
1343       s.z() = -cross.y() / cross.x();
1344     }
1345
1346     if(fabs(cross.x()) > 0.000001f)
1347     {
1348       t.z() = -cross.z() / cross.x();
1349     }
1350   }
1351 }
1352
1353 inline void ArbitraryMeshTriangle_sumTangents(ArbitraryMeshVertex& a, ArbitraryMeshVertex& b, ArbitraryMeshVertex& c)
1354 {
1355   Vector3 s, t;
1356
1357   ArbitraryMeshTriangle_calcTangents(a, b, c, s, t);
1358
1359   reinterpret_cast<Vector3&>(a.tangent) += s;
1360   reinterpret_cast<Vector3&>(b.tangent) += s;
1361   reinterpret_cast<Vector3&>(c.tangent) += s;
1362
1363   reinterpret_cast<Vector3&>(a.bitangent) += t;
1364   reinterpret_cast<Vector3&>(b.bitangent) += t;
1365   reinterpret_cast<Vector3&>(c.bitangent) += t;
1366 }
1367
1368
1369 #endif