// Filename: eggMesher.cxx
// Created by:  drose (13Mar05)
//
////////////////////////////////////////////////////////////////////
//
// PANDA 3D SOFTWARE
// Copyright (c) 2001 - 2004, Disney Enterprises, Inc.  All rights reserved
//
// All use of this software is subject to the terms of the Panda 3d
// Software license.  You should have received a copy of this license
// along with this source code; you will also find a current copy of
// the license at http://etc.cmu.edu/panda3d/docs/license/ .
//
// To contact the maintainers of this program write to
// panda3d-general@lists.sourceforge.net .
//
////////////////////////////////////////////////////////////////////

#include "eggMesher.h"
#include "eggMesherFanMaker.h"
#include "eggPolygon.h"
#include "eggCompositePrimitive.h"
#include "eggTriangleStrip.h"
#include "eggTriangleFan.h"
#include "eggGroup.h"
#include "config_egg.h"
#include "eggGroupNode.h"
#include "dcast.h"

#include <stdlib.h>

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::Constructor
//       Access: Public
//  Description: 
////////////////////////////////////////////////////////////////////
EggMesher::
EggMesher() {
  _vertex_pool = NULL;
  _strip_index = 0;
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::mesh
//       Access: Public
//  Description: Accepts an EggGroupNode, which contains a set of
//               EggPrimitives--typically, triangles and quads--as
//               children.  Removes these primitives and replaces them
//               with (mostly) equivalent EggTriangleStrips and
//               EggTriangleFans where possible.
//
//               If flat_shaded is true, then odd-length triangle
//               strips, and triangle fans of any length, are not
//               permitted (because these can't be rotated when
//               required to move the colored vertex of each triangle
//               to the first or last position).
////////////////////////////////////////////////////////////////////
void EggMesher::
mesh(EggGroupNode *group, bool flat_shaded) {
  _flat_shaded = flat_shaded;

  // Create a temporary node to hold the children of group that aren't
  // involved in the meshing, as well as the newly-generate triangle
  // strips.
  PT(EggGroupNode) output_children = new EggGroupNode;

  // And another to hold the children that will be processed next
  // time.
  PT(EggGroupNode) next_children = new EggGroupNode;
  PT(EggGroupNode) this_children = group;

  // Only primitives that share a common vertex pool can be meshed
  // together.  Thus, pull out the primitives with the same vertex
  // pool in groups.
  while (this_children->size() != 0) {
    clear();

    // Add each polygon in the group to the mesh pool.
    while (!this_children->empty()) {
      PT(EggNode) child = this_children->get_first_child();
      this_children->remove_child(child);
      
      if (child->is_of_type(EggPolygon::get_class_type())) {
        EggPolygon *poly = DCAST(EggPolygon, child);

        if (_vertex_pool == (EggVertexPool *)NULL) {
          _vertex_pool = poly->get_pool();
          add_polygon(poly, EggMesherStrip::MO_user);

        } else if (_vertex_pool == poly->get_pool()) {
          add_polygon(poly, EggMesherStrip::MO_user);

        } else {
          // A different vertex pool; save this one for the next pass.
          next_children->add_child(poly);
        }

      } else {
        // If it's not a polygon of any kind, just output it
        // unchanged.
        output_children->add_child(child);
      }
    }
    
    do_mesh();
    
    Strips::iterator si;
    for (si = _done.begin(); si != _done.end(); ++si) {
      PT(EggPrimitive) egg_prim = get_prim(*si);
      if (egg_prim != (EggPrimitive *)NULL) {
        output_children->add_child(egg_prim);
      }
    }

    this_children = next_children;
    next_children = new EggGroupNode;
  }

  // Now copy the newly-meshed primitives back to the group.
  group->clear();
  group->steal_children(*output_children);

  clear();
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::write
//       Access: Public
//  Description: 
////////////////////////////////////////////////////////////////////
void EggMesher::
write(ostream &out) const {
  /*
  out << _edges.size() << " edges:\n";
  copy(_edges.begin(), _edges.end(), ostream_iterator<Edge>(out, "\n"));
  */

  out << _verts.size() << " verts:\n";
  Verts::const_iterator vi;

  for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
    int v = (*vi).first;
    const EdgePtrs &edges = (*vi).second;
    out << v << " shares " << count_vert_edges(edges) << " edges:\n";
    EdgePtrs::const_iterator ei;
    for (ei = edges.begin(); ei != edges.end(); ++ei) {
      if (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty()) {
        out << "  " << **ei << "\n";
      }
    }
  }

  Strips::const_iterator si;
  out << _tris.size() << " tris:\n";
  for (si = _tris.begin(); si != _tris.end(); ++si) {
    out << (*si) << "\n";
  }

  out << _quads.size() << " quads:\n";
  for (si = _quads.begin(); si != _quads.end(); ++si) {
    out << (*si) << "\n";
  }

  out << _strips.size() << " strips:\n";
  for (si = _strips.begin(); si != _strips.end(); ++si) {
    out << (*si) << "\n";
  }
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::clear
//       Access: Private
//  Description: Empties the pool of meshable primitives and resets to
//               an initial state.
////////////////////////////////////////////////////////////////////
void EggMesher::
clear() {
  _tris.clear();
  _quads.clear();
  _strips.clear();
  _dead.clear();
  _done.clear();
  _verts.clear();
  _edges.clear();
  _strip_index = 0;
  _vertex_pool = NULL;
  _color_sheets.clear();
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::add_polygon
//       Access: Private
//  Description: Adds a single polygon into the pool of available
//               primitives for meshing.
////////////////////////////////////////////////////////////////////
bool EggMesher::
add_polygon(const EggPolygon *egg_poly, EggMesherStrip::MesherOrigin origin) {
  CPT(EggPolygon) this_poly = egg_poly;
  if (this_poly->size() != 3) {
    // If we have a higher-order or concave polygon, triangulate it
    // automatically.

    // We'll keep quads, unless they're concave.
    bool convex_also = (this_poly->size() != 4);

    PT(EggGroupNode) temp_group = new EggGroupNode;
    bool result = this_poly->triangulate_into(temp_group, convex_also);
    EggGroupNode::iterator ci;
    if (temp_group->size() != 1) {
      for (ci = temp_group->begin(); ci != temp_group->end(); ++ci) {
        add_polygon(DCAST(EggPolygon, *ci), EggMesherStrip::MO_user);
      }
      return result;
    }

    // Convert just the one polygon we got out of the group.  Don't
    // recurse, since it might be the same polygon we sent in.
    ci = temp_group->begin();
    this_poly = DCAST(EggPolygon, *ci);
  }

  if (_vertex_pool == NULL) {
    _vertex_pool = this_poly->get_pool();
  } else {
    nassertr(_vertex_pool == this_poly->get_pool(), false);
  }

  // Define an initial strip (probably of length 1) for the prim.
  EggMesherStrip temp_strip(this_poly, _strip_index++, _vertex_pool, 
                            _flat_shaded);
  Strips &list = choose_strip_list(temp_strip);
  list.push_back(temp_strip);
  EggMesherStrip &strip = list.back();
  strip._origin = origin;

  int i;
  int num_verts = this_poly->size();

  int *vptrs = (int *)alloca(num_verts * sizeof(int));
  EdgePtrs **eptrs = (EdgePtrs **)alloca(num_verts * sizeof(EdgePtrs *));

  // Get the common vertex pointers for the primitive's vertices.
  for (i = 0; i < num_verts; i++) {
    Verts::value_type v(this_poly->get_vertex(i)->get_index(), EdgePtrs());
    Verts::iterator n = _verts.insert(v).first;

    vptrs[i] = (*n).first;
    eptrs[i] = &(*n).second;

    strip._verts.push_back(vptrs[i]);
  }

  // Now identify the common edges.
  for (i = 0; i < num_verts; i++) {
    // Define an inner and outer edge.  A polygon shares an edge with a
    // neighbor only when one of its inner edges matches a neighbor's
    // outer edge (and vice-versa).
    EggMesherEdge inner(vptrs[i], vptrs[(i+1) % num_verts]);
    EggMesherEdge outer(vptrs[(i+1) % num_verts], vptrs[i]);
    
    // Add it to the list and get its common pointer.
    EggMesherEdge &inner_ref = (EggMesherEdge &)*_edges.insert(inner).first;
    EggMesherEdge &outer_ref = (EggMesherEdge &)*_edges.insert(outer).first;
    
    // Tell the edges about each other.
    inner_ref._opposite = &outer_ref;
    outer_ref._opposite = &inner_ref;
    
    // Associate the common edge to the strip.
    strip._edges.push_back(&inner_ref);
    
    // Associate the strip, as well as the original prim, to the edge.
    outer_ref._strips.push_back(&strip);
    
    // Associate the common edge with the vertices that share it.
    //      EggMesherEdge *edge_ptr = inner_ref.common_ptr();
    eptrs[i]->insert(&outer_ref);
    eptrs[(i+1) % num_verts]->insert(&outer_ref);
  }
  
  return true;
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::do_mesh
//       Access: Private
//  Description: Performs the meshing process on the set of primitives
//               that have been added via add_prim(), leaving the
//               result in _done.
////////////////////////////////////////////////////////////////////
void EggMesher::
do_mesh() {
  if (egg_consider_fans && !_flat_shaded) {
    find_fans();
  }

  // First, we try to make all the best quads we can.
  if (egg_retesselate_coplanar) {
    make_quads();
  }

  // Then, we do the rest of the tris.
  mesh_list(_tris);

  if (egg_show_quads) {
    // If we're showing quads, we shouldn't do any more meshing.
    Strips::iterator si;
    for (si = _quads.begin(); si != _quads.end(); ++si) {
      if ((*si)._status == EggMesherStrip::MS_alive) {
        (*si)._status = EggMesherStrip::MS_done;
      }
    }
    for (si = _strips.begin(); si != _strips.end(); ++si) {
      if ((*si)._status == EggMesherStrip::MS_alive) {
        (*si)._status = EggMesherStrip::MS_done;
      }
    }
  }

  // Then, build quads into sheets where possible.
  build_sheets();

  // Pick up any quads that might have been left behind.
  mesh_list(_quads);

  // Finally, do the longer strips.
  mesh_list(_strips);
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::get_prim
//       Access: Private
//  Description: Creates an EggPrimitive that represents the result of
//               the meshed EggMesherStrip object.
////////////////////////////////////////////////////////////////////
PT(EggPrimitive) EggMesher::
get_prim(EggMesherStrip &strip) {
  EggMesherStrip::PrimType orig_type = strip._type;
  PT(EggPrimitive) egg_prim = strip.make_prim(_vertex_pool);

  if (egg_show_tstrips) {
    // If we have egg_show_tstrips on, it means we need to color every
    // primitive according to which, if any, tristrip it is in.

    Colorf color1, color2;

    if (egg_prim->is_of_type(EggTriangleStrip::get_class_type()) ||
        egg_prim->is_of_type(EggTriangleFan::get_class_type())) {
      make_random_color(color2);
      color1 = (color2 * 0.8);   // somewhat darker.

    } else {
      // not-a-tristrip.
      color1.set(0.85, 0.85, 0.85, 1.0);
      color2.set(0.85, 0.85, 0.85, 1.0);
    }

    // Now color1 and color2 indicate the color for the first triangle
    // and the rest of the primitive, respectively.
    if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
      EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
      int num_components = egg_comp->get_num_components();
      if (num_components > 0) {
        egg_comp->get_component(0)->set_color(color1);
        for (int i = 1; i < num_components; i++) {
          egg_comp->get_component(i)->set_color(color2);
        }
      }
    } else {
      egg_prim->set_color(color1);
    }

    int num_verts = egg_prim->size();
    for (int i = 0; i < num_verts; i++) {
      egg_prim->get_vertex(i)->clear_color();
    }

  } else if (egg_show_qsheets) {
    // egg_show_qsheets means to color every primitive according to
    // which, if any, quadsheet it is in.  This is a bit easier,
    // because the entire primitive gets the same color.

    // Is this a quadsheet?
    Colorf color1;
    if (strip._row_id < 0) {
      // Yep!  Assign a new color, if it doesn't already have one.
      ColorSheetMap::iterator ci = _color_sheets.find(strip._row_id);

      if (ci == _color_sheets.end()) {
        make_random_color(color1);
        _color_sheets[strip._row_id] = color1;
      } else {
        color1 = (*ci).second;
      }
    }

    // Now color1 is the color we want to assign to the whole
    // primitive.
    egg_prim->set_color(color1);
    if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
      EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
      int num_components = egg_comp->get_num_components();
      for (int i = 0; i < num_components; i++) {
        egg_comp->get_component(i)->clear_color();
      }
    }
    int num_verts = egg_prim->size();
    for (int i = 0; i < num_verts; i++) {
      egg_prim->get_vertex(i)->clear_color();
    }

  } else if (egg_show_quads) {
    // egg_show_quads means to show the assembling of tris into quads
    // and fans.

    // We use the following color convention:

    // white: unchanged; as supplied by user.
    // dark blue: quads made in the initial pass.  These are more certain.
    // light blue: quads made in the second pass.  These are less certain.
    // very light blue: quadstrips.  These are unlikely to appear.
    // random shades of red: triangles and tristrips.
    // green: fans and retesselated fan polygons.

    // We need a handful of entries.
    Colorf white(0.85, 0.85, 0.85, 1.0);
    Colorf dark_blue(0.0, 0.0, 0.75, 1.0);
    Colorf light_blue(0.4, 0.4, 0.8, 1.0);
    Colorf very_light_blue(0.6, 0.6, 1.0, 1.0);
    Colorf green(0.2, 0.8, 0.2, 1.0);

    Colorf color1;
    if (strip._origin == EggMesherStrip::MO_user) {
      color1 = white;
    } else if (strip._origin == EggMesherStrip::MO_firstquad) {
      color1 = dark_blue;
    } else if (strip._origin == EggMesherStrip::MO_fanpoly) {
      color1 = green;
    } else {
      switch (orig_type) {
      case EggMesherStrip::PT_quad:
        color1 = light_blue;
        break;

      case EggMesherStrip::PT_quadstrip:
        color1 = very_light_blue;
        break;

      case EggMesherStrip::PT_tristrip:
        make_random_color(color1);
        // Make it a shade of red.
        if (color1[0] < color1[1]) {
          float t = color1[0];
          color1[0] = color1[1];
          color1[1] = t;
        }
        color1[2] = color1[1];
        break;

      case EggMesherStrip::PT_trifan:
        make_random_color(color1);
        // Make it a shade of green.
        if (color1[0] > color1[1]) {
          float t = color1[0];
          color1[0] = color1[1];
          color1[1] = t;
        }
        color1[2] = color1[0];
        break;

      default:
        color1 = white;
      }
    }

    // Now color1 is the color we want to assign to the whole
    // primitive.
    egg_prim->set_color(color1);
    if (egg_prim->is_of_type(EggCompositePrimitive::get_class_type())) {
      EggCompositePrimitive *egg_comp = DCAST(EggCompositePrimitive, egg_prim);
      int num_components = egg_comp->get_num_components();
      for (int i = 0; i < num_components; i++) {
        egg_comp->get_component(i)->clear_color();
      }
    }
    int num_verts = egg_prim->size();
    for (int i = 0; i < num_verts; i++) {
      egg_prim->get_vertex(i)->clear_color();
    }
  }

  return egg_prim;
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::count_vert_edges
//       Access: Private
//  Description: Returns the number of edges in the list that are used
//               by at least one EggMesherStrip object.
////////////////////////////////////////////////////////////////////
int EggMesher::
count_vert_edges(const EdgePtrs &edges) const {
  int count = 0;
  EdgePtrs::const_iterator ei;
  for (ei = edges.begin(); ei != edges.end(); ++ei) {
    count += (!(*ei)->_strips.empty() || !(*ei)->_opposite->_strips.empty());
  }
  return count;
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::choose_strip_list
//       Access: Private
//  Description: Selects which of several strip lists on the EggMesher
//               class the indicated EggMesherStrip should be added
//               to.
////////////////////////////////////////////////////////////////////
plist<EggMesherStrip> &EggMesher::
choose_strip_list(const EggMesherStrip &strip) {
  switch (strip._status) {
  case EggMesherStrip::MS_done:
    return _done;

  case EggMesherStrip::MS_dead:
    return _dead;

  case EggMesherStrip::MS_alive:
    switch (strip._type) {
    case EggMesherStrip::PT_tri:
      return _tris;

    case EggMesherStrip::PT_quad:
      return _quads;

    default:
      return _strips;
    }

  default:
    egg_cat.fatal() << "Invalid strip status!\n";
    abort();
  }

  return _strips; // Unreachable; this is just to make the compiler happy.
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::build_sheets
//       Access: Private
//  Description: Attempts to locate large quadsheets in the polygon
//               soup.  A quadsheet is defined as a uniform
//               rectangular mesh of quads joined at the corners.
//
//               Sheets like this are commonly output by modeling
//               packages, especially uniform tesselators, and they
//               are trivially converted into a row of triangle
//               strips.
////////////////////////////////////////////////////////////////////
void EggMesher::
build_sheets() {
  int first_row_id = 1;

  // First, move all the quads to our own internal list.
  Strips pre_sheeted;
  pre_sheeted.splice(pre_sheeted.end(), _quads);

  while (!pre_sheeted.empty()) {
    // Pick the first quad on the list.

    Strips::iterator best = pre_sheeted.begin();

    // If the row_id is negative, we've already built a sheet out of
    // this quad.  Leave it alone.  We also need to leave it be if it
    // has no available edges.
    if ((*best)._row_id >= 0 &&
        (*best)._status == EggMesherStrip::MS_alive &&
        !(*best)._edges.empty()) {
      // There are two possible sheets we could make from this quad,
      // in two different orientations.  Measure them both and figure
      // out which one is best.

      const EggMesherEdge *edge_a = (*best)._edges.front();
      const EggMesherEdge *edge_b = (*best).find_adjacent_edge(edge_a);

      int num_prims_a = 0;
      int num_rows_a = 0;
      int first_row_id_a = first_row_id;
      (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
                           first_row_id_a, 0, 0);
      first_row_id += num_rows_a;
      double avg_length_a = (double)num_prims_a / (double)num_rows_a;

      int num_prims_b = 0;
      int num_rows_b = 0;
      int first_row_id_b = first_row_id;
      double avg_length_b;
      if (edge_b != NULL) {
        (*best).measure_sheet(edge_b, true, num_prims_b, num_rows_b,
                             first_row_id_b, 0, 0);
        first_row_id += num_rows_b;
        avg_length_b = (double)num_prims_b / (double)num_rows_b;
      }

      // Which sheet is better?
      if (edge_b != NULL && avg_length_b >= avg_length_a) {
        // Sheet b.  That's easy.
        (*best).cut_sheet(first_row_id_b, true, _vertex_pool);

      } else {
        // Nope, sheet a is better.  This is a bit of a nuisance
        // because we've unfortunately wiped out the information we
        // stored when we measured sheet a.  We'll have to do it
        // again.

        num_prims_a = 0;
        num_rows_a = 0;
        first_row_id_a = first_row_id;
        (*best).measure_sheet(edge_a, true, num_prims_a, num_rows_a,
                             first_row_id_a, 0, 0);
        first_row_id += num_rows_a;

        // Now we can cut it.
        (*best).cut_sheet(first_row_id_a, true, _vertex_pool);
      }
    }

    // Now put it somewhere.  We'll never see this quad again in
    // build_sheets().
    Strips &list = choose_strip_list(*best);
    list.splice(list.end(), pre_sheeted, best);
  }
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::find_fans
//       Access: Private
//  Description: Looks for cases of multiple polygons all sharing a
//               common vertex, and replaces these with a single fan.
//
//               This step is performed before detecting triangle
//               strips.  We have to be careful: if we are too
//               aggressive in detecting fans, we may ruin the ability
//               to build good triangle strips, and we may thereby end
//               up with a less-than-optimal solution.
////////////////////////////////////////////////////////////////////
void EggMesher::
find_fans() {
  PT(EggGroupNode) unrolled_tris = new EggGroup;

  // Consider all vertices.  Any vertex with over a certain number of
  // edges connected to it is eligible to become a fan.

  Verts::iterator vi;

  for (vi = _verts.begin(); vi != _verts.end(); ++vi) {
    EdgePtrs &edges = (*vi).second;

    // 14 is the magic number of edges.  12 edges or fewer are likely
    // to be found on nearly every vertex in a quadsheet (six edges
    // times two, one each way).  We don't want to waste time fanning
    // out each vertex of a quadsheet, and we don't want to break up
    // the quadsheets anyway.  We bump this up to 14 because some
    // quadsheets are defined with triangles flipped here and there.
    if (edges.size() > 6) {
      int v = (*vi).first;

      // Build up a list of far fan edges.
      typedef pvector<EggMesherFanMaker> FanMakers;
      FanMakers fans;

      EdgePtrs::iterator ei;
      EggMesherEdge::Strips::iterator si;
      for (ei = edges.begin(); ei != edges.end(); ++ei) {
        for (si = (*ei)->_strips.begin();
             si != (*ei)->_strips.end();
             ++si) {
          EggMesherStrip *strip = *si;
          if (strip->_type == EggMesherStrip::PT_tri) {
            EggMesherFanMaker fan(v, strip, this);
            if (!fan._edges.empty()) {
              fans.push_back(fan);
            }
          }
        }
      }

      // Sort the fans list by edge pointers, and remove duplicates.
      sort(fans.begin(), fans.end());
      fans.erase(unique(fans.begin(), fans.end()),
                 fans.end());

      FanMakers::iterator fi, fi2;

      // Now pull out connected edges.
      bool joined_any;
      do {
        joined_any = false;
        for (fi = fans.begin(); fi != fans.end(); ++fi) {
          if (!(*fi).is_empty()) {
            fi2 = fi;
            for (++fi2; fi2 != fans.end(); ++fi2) {
              if (!(*fi2).is_empty()) {
                joined_any = (*fi).join(*fi2);
              }
            }
          }
        }
      } while (joined_any);

      for (fi = fans.begin(); fi != fans.end(); ++fi) {
        if ((*fi).is_valid()) {
          (*fi).build(unrolled_tris);
        }
      }
    }
  }

  // Finally, add back in the triangles we might have produced by
  // unrolling some of the fans.  We can't add these back in safely
  // until we're done traversing all the vertices and primitives we
  // had in the first place (since adding them will affect the edge
  // lists).
  EggGroupNode::iterator ti;
  for (ti = unrolled_tris->begin(); ti != unrolled_tris->end(); ++ti) {
    add_polygon(DCAST(EggPolygon, (*ti)), EggMesherStrip::MO_fanpoly);
  }
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::make_quads
//       Access: Private
//  Description: Attempts to join up each single tri to its neighbor,
//               to reconstruct a pattern of quads, suitable for
//               making into quadsheets or at least quadstrips.
//
//               Quads have some nice properties that make them easy
//               to manipulate when meshing.  We will ultimately
//               convert the quadsheets and quadstrips into tristrips,
//               but it's easier to work with them first while they're
//               quads.
////////////////////////////////////////////////////////////////////
void EggMesher::
make_quads() {
  // Ideally, we want to match tris across their hypotenuse to make a
  // pattern of quads.  (This assumes that we are working with a
  // triangulated mesh pattern, of course.  If we have some other
  // pattern of tris, all bets are off and it doesn't really matter
  // anyway.)

  // First, we'll find all the tris that have no doubt about their
  // ideal mate, and pair them up right away.  The others we'll get to
  // later.  This way, the uncertain matches won't pollute the quad
  // alignment for everyone else.

  typedef pair<EggMesherStrip *, EggMesherStrip *> Pair;
  typedef pair<Pair, EggMesherEdge *> Matched;
  typedef pvector<Matched> SoulMates;

  SoulMates soulmates;

  EggMesherStrip *tri, *mate, *mate2;
  EggMesherEdge *common_edge, *common_edge2;

  Strips::iterator si;
  for (si = _tris.begin(); si != _tris.end(); ++si) {
    tri = &(*si);

    if (tri->_status == EggMesherStrip::MS_alive) {
      if (tri->find_ideal_mate(mate, common_edge, _vertex_pool)) {
        // Does our chosen mate want us too?
        if (mate->_type == EggMesherStrip::PT_tri && 
            mate->_status == EggMesherStrip::MS_alive &&
            mate->find_ideal_mate(mate2, common_edge2, _vertex_pool) &&
            mate2 == tri) {
          // Hooray!
          soulmates.push_back(Matched(Pair(tri, mate), common_edge));
          // We'll temporarily mark the two tris as paired.
          tri->_status = EggMesherStrip::MS_paired;
          mate->_status = EggMesherStrip::MS_paired;
        }
      }
    }
  }

  // Now that we've found all the tris that are sure about each other,
  // mate them.
  SoulMates::iterator mi;
  for (mi = soulmates.begin(); mi != soulmates.end(); ++mi) {
    tri = (*mi).first.first;
    mate = (*mi).first.second;
    common_edge = (*mi).second;

    nassertv(tri->_status == EggMesherStrip::MS_paired);
    nassertv(mate->_status == EggMesherStrip::MS_paired);
    tri->_status = EggMesherStrip::MS_alive;
    mate->_status = EggMesherStrip::MS_alive;

    EggMesherStrip::mate_pieces(common_edge, *tri, *mate, _vertex_pool);
    tri->_origin = EggMesherStrip::MO_firstquad;
  }

  // Now move all the strips off the tri list that no longer belong.
  Strips::iterator next;
  si = _tris.begin();
  while (si != _tris.end()) {
    next = si;
    ++next;

    Strips &list = choose_strip_list(*si);
    if (&list != &_tris) {
      list.splice(list.end(), _tris, si);
    }

    si = next;
  }
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::mesh_list
//       Access: Private
//  Description: Processes all of the strips on the indicated list.
////////////////////////////////////////////////////////////////////
void EggMesher::
mesh_list(Strips &strips) {
  while (!strips.empty()) {
    // Pick the first strip on the list.

    Strips::iterator best = strips.begin();

    if ((*best)._status == EggMesherStrip::MS_alive) {
      (*best).mate(_vertex_pool);
    }

    // Put the strip back on the end of whichever list it wants.  This
    // might be the same list, if the strip is still alive, or it
    // might be _done or _dead.
    Strips &list = choose_strip_list(*best);
    list.splice(list.end(), strips, best);
  }
}

////////////////////////////////////////////////////////////////////
//     Function: EggMesher::make_random_color
//       Access: Private, Static
//  Description: Chooses a reasonable random color.
////////////////////////////////////////////////////////////////////
void EggMesher::
make_random_color(Colorf &color) {
  LVector3f rgb;
  float len;
  do {
    for (int i = 0; i < 3; i++) {
      rgb[i] = (double)rand() / (double)RAND_MAX;
    }
    len = length(rgb);

    // Repeat until we have a color that's not too dark or too light.
  } while (len < .1 || len > 1.5);

  color.set(rgb[0], rgb[1], rgb[2],
            0.25 + 0.75 * (double)rand() / (double)RAND_MAX);
}

