Boost logo

Boost-Commit :

From: huseyinakcan_at_[hidden]
Date: 2007-08-09 21:19:02


Author: huseyinakcan
Date: 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
New Revision: 38557
URL: http://svn.boost.org/trac/boost/changeset/38557

Log:
more Euler operators implemented
base functions corrected and tested

Text files modified:
   sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.hpp | 256 ++++++++++++++++++++++++++++++---------
   sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.t.cpp | 105 ++++------------
   sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/euler_operators.hpp | 216 +++++++++++++++++++++++++++++++--
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_ds.hpp | 115 ++++++-----------
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_selectors.hpp | 5
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/meta_functions.hpp | 5
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_selectors.hpp | 3
   7 files changed, 475 insertions(+), 230 deletions(-)

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.hpp (original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.hpp 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -28,88 +28,171 @@
 namespace boost {
 namespace hdstl {
 
-// \cond
-namespace detail {
 
-template<typename HalfedgeGen, typename Tag=next_in_facet_tag>
-struct stitch_cycle_helper
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_next_in_facet(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor
+ , HalfedgeGen& , Tag const& )
 {
- static void
- stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
- {
- set_next_in_facet(h,g,hds);
- }
-};
+ // No-op
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, prev_in_facet_tag>
+template <typename HalfedgeGen>
+void
+stitch_next_in_facet(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+ , HalfedgeGen& hds, next_in_facet_tag const&)
 {
- static void
- stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
- {
- set_prev_in_facet(h,g,hds);
- }
-};
+ set_next_in_facet(h,g,hds);
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, next_at_source_tag>
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_prev_in_facet(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor
+ , HalfedgeGen& , Tag const& )
 {
- static void
- stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
- {
- set_next_at_source(h,g,hds);
- }
-};
+ // No-op
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, prev_at_source_tag>
+template <typename HalfedgeGen>
+void
+stitch_prev_in_facet(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+ , HalfedgeGen& hds, prev_in_facet_tag const&)
 {
- static void
- stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
- {
- set_prev_at_source(h,g,hds);
- }
-};
+ set_prev_in_facet(h,g,hds);
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, next_at_target_tag>
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_next_at_source(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor
+ , HalfedgeGen& , Tag const& )
 {
- static void
- stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
- {
- set_next_at_target(h,g,hds);
- }
-};
+ // No-op
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, prev_at_target_tag>
+template <typename HalfedgeGen>
+void
+stitch_next_at_source(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+ , HalfedgeGen& hds, next_at_source_tag const&)
 {
- static void
- stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
- {
- set_prev_at_target(h,g,hds);
- }
-};
+ set_next_at_source(h,g,hds);
+}
 
-} // end namespace detail
-// \endcond
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_prev_at_source(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor
+ , HalfedgeGen& , Tag const& )
+{
+ // No-op
+}
 
 template <typename HalfedgeGen>
 void
-stitch_next(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
- // Sets the appropriate forward accessor relations between h and g, based on the configuration of the 'hds'
+stitch_prev_at_source(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+ , HalfedgeGen& hds, prev_at_source_tag const&)
 {
- typedef typename HalfedgeGen::halfedge_selector::next_tag tag;
- detail::stitch_cycle_helper<HalfedgeGen, tag>::stitch(h,g,hds);
+ set_prev_at_source(h,g,hds);
+}
+
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_next_at_target(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor
+ , HalfedgeGen& , Tag const& )
+{
+ // No-op
 }
 
 template <typename HalfedgeGen>
 void
-stitch_prev(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
- // Sets the appropriate backward accessor relations between h and g, based on the configuration of the 'hds'
+stitch_next_at_target(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+ , HalfedgeGen& hds, next_at_target_tag const&)
 {
- typedef typename HalfedgeGen::halfedge_selector::prev_tag tag;
- detail::stitch_cycle_helper<HalfedgeGen, tag>::stitch(h,g,hds);
+ set_next_at_target(h,g,hds);
+}
+
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_prev_at_target(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor
+ , HalfedgeGen& , Tag const& )
+{
+ // No-op
+}
+
+template <typename HalfedgeGen>
+void
+stitch_prev_at_target(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+ , HalfedgeGen& hds, prev_at_target_tag const&)
+{
+ set_prev_at_target(h,g,hds);
+}
+
+template <typename HalfedgeGen, typename ForwardCategory>
+typename HalfedgeGen::halfedge_descriptor
+get_next_in_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, ForwardCategory const&)
+{
+ return static_cast<typename HalfedgeGen::halfedge_descriptor>(next_in_facet(h, hds));
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::halfedge_descriptor
+get_next_in_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, empty_tag const&)
+{
+ // No-op
+}
+
+template <typename HalfedgeGen, typename BackwardCategory>
+typename HalfedgeGen::halfedge_descriptor
+get_prev_in_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, BackwardCategory const&)
+{
+ return static_cast<typename HalfedgeGen::halfedge_descriptor>(prev_in_facet(h, hds));
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::halfedge_descriptor
+get_prev_in_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, empty_tag const&)
+{
+ // No-op
+}
+
+template <typename HalfedgeGen, typename FacetS>
+typename HalfedgeGen::facet_descriptor
+get_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, FacetS const&)
+{
+ return facet(h, hds);
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::facet_descriptor
+get_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, noFacetS const&)
+{
+ // No-op
+}
+
+template <typename HalfedgeGen, typename Type>
+typename HalfedgeGen::vertex_descriptor
+get_source(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, Type const&)
+{
+ // No-op
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::vertex_descriptor
+get_source(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, sourceS const&)
+{
+ return source(h, hds);
+}
+
+template <typename HalfedgeGen, typename Type>
+typename HalfedgeGen::vertex_descriptor
+get_target(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, Type const&)
+{
+ // No-op
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::vertex_descriptor
+get_target(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, targetS const&)
+{
+ return target(h, hds);
 }
 
 // \cond
@@ -202,6 +285,59 @@
>::stitch(h,v,hds,vds);
 }
 
+template <typename HalfedgeGen>
+void
+splice(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descritor g
+ , typename HalfedgeGen::halfedge_descriptor i, typename HalfedgeGen::halfedge_descritor j, HalfedgeGen& hds)
+{
+ typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+ typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag;
+
+ stitch_next_in_facet(h, j, hds, next_tag());
+ stitch_prev_in_facet(j, h, hds, prev_tag());
+
+ stitch_next_in_facet(i, g, hds, next_tag());
+ stitch_prev_in_facet(g, i, hds, prev_tag());
+
+ stitch_next_at_source(opposite(h, hds), j, hds, next_tag());
+ stitch_prev_at_source(j, opposite(h, hds), hds, prev_tag());
+
+ stitch_next_at_source(opposite(i, hds), g, hds, next_tag());
+ stitch_prev_at_source(g, opposite(i, hds), hds, prev_tag());
+
+ stitch_next_at_target(h, opposite(j, hds), hds, next_tag());
+ stitch_prev_at_target(opposite(j, hds), h, hds, prev_tag());
+
+ stitch_next_at_target(i, opposite(g, hds), hds, next_tag());
+ stitch_prev_at_target(opposite(g, hds), i, hds, prev_tag());
+}
+
+template <typename HalfedgeGen>
+void
+detach(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descritor g
+ , typename HalfedgeGen::halfedge_descriptor i, typename HalfedgeGen::halfedge_descritor j, HalfedgeGen& hds)
+{
+ typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+ typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag;
+
+ stitch_next_in_facet(h, g, hds, next_tag());
+ stitch_prev_in_facet(g, h, hds, prev_tag());
+
+ stitch_next_in_facet(i, j, hds, next_tag());
+ stitch_prev_in_facet(j, i, hds, prev_tag());
+
+ stitch_next_at_source(opposite(h, hds), g, hds, next_tag());
+ stitch_prev_at_source(g, opposite(h, hds), hds, prev_tag());
+
+ stitch_next_at_source(opposite(i, hds), j, hds, next_tag());
+ stitch_prev_at_source(j, opposite(i, hds), hds, prev_tag());
+
+ stitch_next_at_target(h, opposite(g, hds), hds, next_tag());
+ stitch_prev_at_target(opposite(g, hds), h, hds, prev_tag());
+
+ stitch_next_at_target(i, opposite(j, hds), hds, next_tag());
+ stitch_prev_at_target(opposite(j, hds), i, hds, prev_tag());
+}
 } // end namespace hdstl
 } // end namespace boost
 

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.t.cpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.t.cpp (original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.t.cpp 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -10,8 +10,7 @@
 #include <boost/hdstl/halfedge_ds/halfedge_selectors.hpp>
 #include <boost/hdstl/halfedge_ds/facet_functions.hpp>
 #include <boost/hdstl/halfedge_ds/vertex_functions.hpp>
-#include <boost/hdstl/halfedge_ds/meta_functions.hpp>
-#include <boost/pending/ct_if.hpp>
+#include <boost/hdstl/halfedge_ds/halfedge_ds.hpp>
 #include <boost/test/minimal.hpp>
 
 #include <set>
@@ -25,73 +24,6 @@
 // CLASS HALFEDGE_GEN
 // ===========================================================================
 
-typedef void* halfedge_ptr;
-
-template <typename HalfedgeS, typename VertexS, typename FacetS>
-struct halfedge_config {
- // This halfedge_config to identically replace the halfedge_ds_gen::config
- // and reproduced here for test purposes only. Note that this tests are
- // not for the config class, but the halfedge_selectors, so config will
- // be tested in its own package.
-
- enum {
- halfedge_has_opposite_member = !meta_is_same<
- typename HalfedgeS::container_selector, vecS>::value,
- is_forward = HalfedgeS::is_forward,
- is_backward = HalfedgeS::is_backward,
- halfedge_supports_vertices = !meta_is_same<VertexS,noVertexS>::value,
- is_source = VertexS::is_source,
- halfedge_supports_facets = !meta_is_same<FacetS,noFacetS>::value
- };
- typedef typename boost::ct_if<halfedge_has_opposite_member,
- halfedge_ptr, std::size_t>::type halfedge_descriptor;
-};
-
-template <typename HalfedgeS>
-struct halfedge_config<HalfedgeS, noVertexS, noFacetS> {
- enum {
- halfedge_has_opposite_member = !meta_is_same<
- typename HalfedgeS::container_selector, vecS>::value,
- is_forward = HalfedgeS::is_forward,
- is_backward = HalfedgeS::is_backward,
- halfedge_supports_vertices = false,
- is_source = false,
- halfedge_supports_facets = false
- };
- typedef typename boost::ct_if<halfedge_has_opposite_member,
- halfedge_ptr, std::size_t>::type halfedge_descriptor;
-};
-
-template <typename HalfedgeS, typename FacetS>
-struct halfedge_config<HalfedgeS, noVertexS, FacetS> {
- enum {
- halfedge_has_opposite_member = !meta_is_same<
- typename HalfedgeS::container_selector, vecS>::value,
- is_forward = HalfedgeS::is_forward,
- is_backward = HalfedgeS::is_backward,
- halfedge_supports_vertices = false,
- is_source = false,
- halfedge_supports_facets = !meta_is_same<FacetS,noFacetS>::value
- };
- typedef typename boost::ct_if<halfedge_has_opposite_member,
- halfedge_ptr, std::size_t>::type halfedge_descriptor;
-};
-
-template <typename HalfedgeS, typename VertexS>
-struct halfedge_config<HalfedgeS, VertexS, noFacetS> {
- enum {
- halfedge_has_opposite_member = !meta_is_same<
- typename HalfedgeS::container_selector, vecS>::value,
- is_forward = HalfedgeS::is_forward,
- is_backward = HalfedgeS::is_backward,
- halfedge_supports_vertices = !meta_is_same<VertexS,noVertexS>::value,
- is_source = VertexS::is_source,
- halfedge_supports_facets = false
- };
- typedef typename boost::ct_if<halfedge_has_opposite_member,
- halfedge_ptr, std::size_t>::type halfedge_descriptor;
-};
-
 template <typename HalfedgeGen>
 void create_hds(HalfedgeGen& halfedgeGen){
     // Types must exist.
@@ -128,9 +60,13 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
- stitch_next(ha, hb, halfedgeGen);
+ stitch_next_in_facet(ha, hb, halfedgeGen, next_in_facet_tag());
+ stitch_next_at_source(ha, hb, halfedgeGen, next_in_facet_tag());
+ stitch_next_at_target(ha, hb, halfedgeGen, next_in_facet_tag());
     
     BOOST_CHECK(( next_in_facet(ha, halfedgeGen) == hb ));
+ BOOST_CHECK(( get_next_in_facet(ha, halfedgeGen, next_in_facet_tag()) == hb ));
+
     return true;
 }
 
@@ -148,7 +84,9 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
- stitch_next(ha, hb, halfedgeGen);
+ stitch_next_in_facet(ha, hb, halfedgeGen, next_at_source_tag());
+ stitch_next_at_source(ha, hb, halfedgeGen, next_at_source_tag());
+ stitch_next_at_target(ha, hb, halfedgeGen, next_at_source_tag());
     
     BOOST_CHECK(( next_at_source(ha, halfedgeGen) == hb ));
 
@@ -169,7 +107,9 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
- stitch_next(ha, hb, halfedgeGen);
+ stitch_next_in_facet(ha, hb, halfedgeGen, next_at_target_tag());
+ stitch_next_at_source(ha, hb, halfedgeGen, next_at_target_tag());
+ stitch_next_at_target(ha, hb, halfedgeGen, next_at_target_tag());
     
     BOOST_CHECK(( next_at_target(ha, halfedgeGen) == hb ));
 
@@ -190,9 +130,12 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
- stitch_prev(ha, hb, halfedgeGen);
+ stitch_prev_in_facet(ha, hb, halfedgeGen, prev_in_facet_tag());
+ stitch_prev_at_source(ha, hb, halfedgeGen, prev_in_facet_tag());
+ stitch_prev_at_target(ha, hb, halfedgeGen, prev_in_facet_tag());
     
     BOOST_CHECK(( prev_in_facet(ha, halfedgeGen) == hb ));
+ BOOST_CHECK(( get_prev_in_facet(ha, halfedgeGen, prev_in_facet_tag()) == hb ));
 
     return true;
 }
@@ -211,7 +154,9 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
- stitch_prev(ha, hb, halfedgeGen);
+ stitch_prev_in_facet(ha, hb, halfedgeGen, prev_at_source_tag());
+ stitch_prev_at_source(ha, hb, halfedgeGen, prev_at_source_tag());
+ stitch_prev_at_target(ha, hb, halfedgeGen, prev_at_source_tag());
     
     BOOST_CHECK(( prev_at_source(ha, halfedgeGen) == hb ));
 
@@ -232,7 +177,9 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
- stitch_prev(ha, hb, halfedgeGen);
+ stitch_prev_in_facet(ha, hb, halfedgeGen, prev_at_target_tag());
+ stitch_prev_at_source(ha, hb, halfedgeGen, prev_at_target_tag());
+ stitch_prev_at_target(ha, hb, halfedgeGen, prev_at_target_tag());
     
     BOOST_CHECK(( prev_at_target(ha, halfedgeGen) == hb ));
 
@@ -253,9 +200,9 @@
                     halfedge_gen<
                       halfedgeS<ContainerS, TraversalS>,
                       int, int,
- halfedge_config<
+ typename halfedge_ds_gen<
                         halfedgeS<ContainerS, TraversalS>,
- VertexS, FacetS> >
+ VertexS, FacetS>::config>
>(next_tag()) ));
    return true;
 }
@@ -270,9 +217,9 @@
                     halfedge_gen<
                       halfedgeS<ContainerS, TraversalS>,
                       int, int,
- halfedge_config<
+ typename halfedge_ds_gen<
                         halfedgeS<ContainerS, TraversalS>,
- VertexS, FacetS> >
+ VertexS, FacetS>::config>
>(prev_tag()) ));
     return true;
 }

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/euler_operators.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/euler_operators.hpp (original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/euler_operators.hpp 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -4,9 +4,9 @@
 //
 //@CLASSES:
 // 'create_lens':
-// 'destroy_lens':
+// 'delete_lens':
 // 'create_torus':
-// 'destroy_torus'
+// 'delete_torus'
 // 'split_facet':
 // 'join_facets':
 // 'split_vertex':
@@ -14,8 +14,47 @@
 //
 //@SEE_ALSO: {hds_concepts.hpp, halfedge_ds.hpp}
 //
-//@DESCRIPTION: //
+//@DESCRIPTION:
 //
+// - 'create_lens': Create_lens is an Euler operator whose purpose is to create a topological ball. It makes a new lens
+// (i.e. a vertex, two halfedges, and two faces) and connects them in the HDS.
+// - 'delete_lens': Delete_lens takes a halfedge which is adjacent to a lens, and reclaims the vertex, the halfedge and
+// its opposite, and the two adjacent facets. The behaviour is undefined if the halfedge is not
+// adjacent to a lens.
+// - 'create_torus': Create_torus is an Euler operator whose purpose is to create a topological torus. The smallest
+// torus representable in our HDS is a torus split along a major and a minor circle (one vertex, two
+// edges, one facet with one loop, one shell). This torus can be obtained by gluing
+// a square along opposite sides (h2 and h4 in figure, top, then the two cycles h1 and h3). Note that
+// the torus is completely symmetric in h1, h2, h3 or h4. This functions makes such a new toric HDS,
+// and returns the handle to h1.
+// - 'delete_torus': Delete_torus takes a halfedge which is adjacent to a torus, and reclaims the vertex, the four
+// halfedges, and the adjacent facet. The behaviour is undefined if the halfedge is not adjacent to a
+// torus.
+// - 'split_facet': Split_facet is an Euler operator whose purpose is to insert an edge inside an existing facet,
+// attach both its endpoints at two (not necessarily distinct) vertices in the boundary, and split
+// the existing facet into two (one which is a copy of the previous one, and a new one which is
+// created). If holes are supported, the attach vertices must be both on the outer boundary or on the
+// same hole boundary; care must be taken to assign the holes of the split facet to either of the new
+// two facets. In this case, our default behavior is to not assign any hole to the new facet that is
+// created. Specifically, h1 and h2 must be consecutive in the facet boundary, same with g1 and g2,
+// and all four must be adjacent to the same facet f, and on the same outer or inner boundary if
+// holes are supported. Two halfedges k1 and k2 are created, k1 is stitched as the successor of h1
+// and predecessor of g2, and k2 becomes the successor of g1 and predecessor of h2; k1 and k2 are
+// also stitched in the cycles around the two anchor vertices. A new facet f2 is created and made
+// adjacent to k2 and to all its successors and predecessors. If holes are supported, all the holes
+// of f remain assigned to f and none to f2. The halfedge k2 whose incident facet is the new facet f2
+// is returned.
+//
+// - 'join_facet': Join_facets is an Euler operator whose purpose is to remove an edge incident to two existing
+// facet, and delete one of the two facets while extending the boundary of the other to include both
+// boundary cycles (minus the removed edge). If holes are supported, the two facets must be distinct.
+// In that case, the new facet contains the holes of both. Specifically, let f1 be the facet
+// incident to k1, k2 its opposite and f2 be the facet incident to k2. The boundary cycle of f2 is
+// traversed starting from k2, and the incident facet is set to f1 for all halfedges in this cycle.
+// Then, the predecessor h1 of k1 is stitched (in cycle and in facet) with the successor h2 of k2,
+// and so are the successor g2 of k1, and the predecessor g1 of k2. Finally k1 and k2 are deleted.
+// This operation is strictly the reverse of split_facet and takes the same running time.
+
 ///Usage Example
 //--------------
 // Suppose we want to build a square shaped halfedge data structure from scratch. First
@@ -68,12 +107,33 @@
           , typename HalfedgeGen::vertex_descriptor v1, typename HalfedgeGen::vertex_descriptor v2
           , typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
 {
- set_next(h, opposite(h, hds), hds);
- set_next(opposite(h, hds), h, hds);
- set_vertex(h, v1, hds);
- set_vertex(opposite(h), v2, hds);
- set_facet(h, f1, hds);
- set_facet(opposite(h), v2, hds);
+ typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+ typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag;
+ typedef typename HalfedgeGen::facet_selector facet_tag;
+ typedef typename HalfedgeGen::vertex_selector vertex_tag;
+
+ stitch_next_in_facet(h, h, hds, next_tag());
+ stitch_prev_in_facet(h, h, hds, prev_tag());
+
+ stitch_next_in_facet(opposite(h, hds), opposite(h, hds), hds, next_tag());
+ stitch_prev_in_facet(opposite(h, hds), opposite(h, hds), hds, prev_tag());
+
+ stitch_next_at_source(h, opposite(h,hds), hds, next_tag());
+ stitch_prev_at_source(opposite(h,hds), h, hds, prev_tag());
+
+ stitch_next_at_source(opposite(h,hds), h, hds, next_tag());
+ stitch_prev_at_source(h, opposite(h,hds), hds, prev_tag());
+
+ stitch_next_at_target(h, opposite(h,hds), hds, next_tag());
+ stitch_prev_at_target(opposite(h,hds), h, hds, prev_tag());
+
+ stitch_next_at_target(opposite(h,hds), h, hds, next_tag());
+ stitch_prev_at_target(h, opposite(h,hds), hds, prev_tag());
+
+ stitch_set_facet(h, f1, hds, facet_tag());
+ stitch_set_facet(opposite(h), f2, hds, facet_tag());
+ stitch_set_vertex(h, v1, hds, vertex_tag());
+ stitch_set_vertex(opposite(h), v2, hds, vertex_tag());
 }
 
 template <typename HalfedgeGen>
@@ -81,10 +141,30 @@
 create_lens(typename HalfedgeGen::vertex_descriptor v1, typename HalfedgeGen::vertex_descriptor v2
           , typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
 {
- set_next(h, opposite(h, hds), hds);
- set_next(opposite(h, hds), h, hds);
- set_vertex(h, v1, hds);
- set_vertex(opposite(h), v2, hds);
+ typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+ typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag;
+ typedef typename HalfedgeGen::vertex_selector vertex_tag;
+
+ stitch_next_in_facet(h, h, hds, next_tag());
+ stitch_prev_in_facet(h, h, hds, prev_tag());
+
+ stitch_next_in_facet(opposite(h, hds), opposite(h, hds), hds, next_tag());
+ stitch_prev_in_facet(opposite(h, hds), opposite(h, hds), hds, prev_tag());
+
+ stitch_next_at_source(h, opposite(h,hds), hds, next_tag());
+ stitch_prev_at_source(opposite(h,hds), h, hds, prev_tag());
+
+ stitch_next_at_source(opposite(h,hds), h, hds, next_tag());
+ stitch_prev_at_source(h, opposite(h,hds), hds, prev_tag());
+
+ stitch_next_at_target(h, opposite(h,hds), hds, next_tag());
+ stitch_prev_at_target(opposite(h,hds), h, hds, prev_tag());
+
+ stitch_next_at_target(opposite(h,hds), h, hds, next_tag());
+ stitch_prev_at_target(h, opposite(h,hds), hds, prev_tag());
+
+ stitch_set_vertex(h, v1, hds, vertex_tag());
+ stitch_set_vertex(opposite(h), v2, hds, vertex_tag());
 }
 
 template <typename HalfedgeGen>
@@ -92,17 +172,119 @@
 create_lens(typename HalfedgeGen::facet_descriptor f1, typename HalfedgeGen::facet_descriptor f2
           , typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
 {
- set_next(h, opposite(h, hds), hds);
- set_next(opposite(h, hds), h, hds);
- set_facet(h, f1, hds);
- set_facet(opposite(h), v2, hds);
+ typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+ typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag;
+ typedef typename HalfedgeGen::facet_selector facet_tag;
+
+ stitch_next_in_facet(h, h, hds, next_tag());
+ stitch_prev_in_facet(h, h, hds, prev_tag());
+
+ stitch_next_in_facet(opposite(h, hds), opposite(h, hds), hds, next_tag());
+ stitch_prev_in_facet(opposite(h, hds), opposite(h, hds), hds, prev_tag());
+
+ stitch_next_at_source(h, opposite(h,hds), hds, next_tag());
+ stitch_prev_at_source(opposite(h,hds), h, hds, prev_tag());
+
+ stitch_next_at_source(opposite(h,hds), h, hds, next_tag());
+ stitch_prev_at_source(h, opposite(h,hds), hds, prev_tag());
+
+ stitch_next_at_target(h, opposite(h,hds), hds, next_tag());
+ stitch_prev_at_target(opposite(h,hds), h, hds, prev_tag());
+
+ stitch_next_at_target(opposite(h,hds), h, hds, next_tag());
+ stitch_prev_at_target(h, opposite(h,hds), hds, prev_tag());
+
+ stitch_set_facet(h, f1, hds, facet_tag());
+ stitch_set_facet(opposite(h), f2, hds, facet_tag());
 }
 
 template <typename HalfedgeGen>
 typename HalfedgeGen::halfedge_descriptor
 create_lens(HalfedgeGen& hds)
 {
+ // in order to use this method with no parameters except hds, we have to use specialized helpers
+ // to create the lens based on the many configuration options such as has vertex, has facet etc...
+}
+
+template <typename HalfedgeGen>
+void
+delete_lens(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
+{
+ delete_vertex(source(h, hds), hds);
+ delete_facet(facet(h, hds), hds);
+ delete_edge(h, hds);
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::halfedge_descriptor
+create_torus(typename HalfedgeGen::facet_descriptor f, typename HalfedgeGen::vertex_descriptor v
+ , typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+ , HalfedgeGen& hds)
+{
+ typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+ typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag;
+ typedef typename HalfedgeGen::facet_selector facet_tag;
+ typedef typename HalfedgeGen::vertex_selector vertex_tag;
+
+ stitch_next_in_facet(h, g, hds, next_tag());
+ stitch_prev_in_facet(g, h, hds, prev_tag());
+
+ stitch_next_in_facet(g, opposite(h, hds) , hds, next_tag());
+ stitch_prev_in_facet(opposite(h, hds), g , hds, prev_tag());
+
+ stitch_next_in_facet(opposite(h, hds), opposite(g, hds), hds, next_tag());
+ stitch_prev_in_facet(opposite(g, hds), opposite(h, hds), hds, prev_tag());
+
+ stitch_next_in_facet(opposite(g, hds), h, hds, next_tag());
+ stitch_prev_in_facet(h, opposite(g, hds), hds, prev_tag());
+
+ stitch_next_at_source(h, opposite(g,hds), hds, next_tag());
+ stitch_prev_at_source(opposite(g,hds), h, hds, prev_tag());
+
+ stitch_next_at_source(opposite(g,hds), opposite(h,hds), hds, next_tag());
+ stitch_prev_at_source(opposite(h,hds), opposite(g,hds), hds, prev_tag());
+
+ stitch_next_at_source(opposite(h,hds), g, hds, next_tag());
+ stitch_prev_at_source(opposite(g,hds), h, hds, prev_tag());
+
+ stitch_next_at_source(g, h, hds, next_tag());
+ stitch_prev_at_source(h, g, hds, prev_tag());
+
+ stitch_next_at_target(h, opposite(g,hds), hds, next_tag());
+ stitch_prev_at_target(opposite(g,hds), h, hds, prev_tag());
+
+ stitch_next_at_target(opposite(g,hds), opposite(h,hds), hds, next_tag());
+ stitch_prev_at_target(opposite(h,hds), opposite(g,hds), hds, prev_tag());
+
+ stitch_next_at_target(opposite(h,hds), g, hds, next_tag());
+ stitch_prev_at_target(g, opposite(h,hds), hds, prev_tag());
+
+ stitch_next_at_target(g, h, hds, next_tag());
+ stitch_prev_at_target(h, g, hds, prev_tag());
+
+ stitch_set_vertex(h, v, hds, vertex_tag());
+ stitch_set_vertex(opposite(h, hds), v, hds, vertex_tag());
+ stitch_set_vertex(g, v, hds, vertex_tag());
+ stitch_set_vertex(opposite(g, hds), v, hds, vertex_tag());
+ stitch_set_facet(h, f, hds, facet_tag());
+ stitch_set_facet(opposite(h, hds), f, hds, facet_tag());
+ stitch_set_facet(g, f, hds, facet_tag());
+ stitch_set_facet(opposite(g, hds), f, hds, facet_tag());
+}
+
+template <typename HalfedgeGen>
+void
+delete_torus(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
+{
+ typedef typename HalfedgeGen::halfedge_selector halfedge_selector;
+ typename HalfedgeGen::halfedge_descriptor op_h = opposite(h, hds);
+ typename HalfedgeGen::halfedge_descriptor g = get_next_in_facet(h, hds, halfedge_selector::is_forward);
+ g = get_prev_in_facet(h, hds, halfedge_selector::is_backward);
+ typename HalfedgeGen::halfedge_descriptor op_g = opposite(g, hds);
 
+ delete_vertex(source(h, hds), hds);
+ delete_facet(facet(h, hds), hds);
+ delete_edge(h, hds);
 }
 
 } // end namespace hdstl

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_ds.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_ds.hpp (original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_ds.hpp 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -34,109 +34,78 @@
 #include <boost/hdstl/halfedge_ds/halfedge_selectors.hpp>
 #include <boost/hdstl/halfedge_ds/vertex_selectors.hpp>
 #include <boost/hdstl/halfedge_ds/facet_selectors.hpp>
+#include <boost/pending/ct_if.hpp>
 
 namespace boost {
 namespace hdstl {
 
+typedef void* halfedge_ptr;
 
 template <typename HalfedgeS, typename VertexS, typename FacetS>
 struct halfedge_ds_gen {
     struct config {
-
- enum { halfedge_has_opposite_member = !meta_is_same<
- typename HalfedgeS::container_selector, vecS>::value };
- enum { is_forward = HalfedgeS::is_forward };
- enum { is_backward = HalfedgeS::is_backward };
- typedef typename HalfedgeS::tag traversal_tag;
- // halfedge config
-
- enum { halfedge_supports_vertices = !meta_is_same<
- VertexS,noVertexS>::value };
- enum { is_source = VertexS::is_source };
- enum { is_target = VertexS::is_target };
- enum { has_vertex_link = VertexS::has_vertex_link };
- // vertex config
-
- enum { halfedge_supports_facets= !meta_is_same<FacetS,noFacetS>::value};
- // facet config
-
+ enum {
+ halfedge_has_opposite_member = !meta_is_same<
+ typename HalfedgeS::container_selector, vecS>::value,
+ is_forward = HalfedgeS::is_forward,
+ is_backward = HalfedgeS::is_backward,
+ halfedge_supports_vertices = !meta_is_same<VertexS,noVertexS>::value,
+ is_source = VertexS::is_source,
+ halfedge_supports_facets = !meta_is_same<FacetS,noFacetS>::value
+ };
         typedef typename boost::ct_if<halfedge_has_opposite_member,
- halfedge_ptr, std::size_t>::type halfedge_descriptor;
+ halfedge_ptr, std::size_t>::type halfedge_descriptor;
     };
 };
 
 template <typename HalfedgeS>
 struct halfedge_ds_gen<HalfedgeS, noVertexS, noFacetS> {
     struct config {
-
- enum { halfedge_has_opposite_member = !meta_is_same<
- typename HalfedgeS::container_selector, vecS>::value };
- enum { is_forward = HalfedgeS::is_forward };
- enum { is_backward = HalfedgeS::is_backward };
- typedef typename HalfedgeS::tag traversal_tag;
- // halfedge config
-
- enum { halfedge_supports_vertices = false };
- enum { is_source = false }; // has no meaning here,
- // but vertex_helper in stored_halfedge
- // requires it defined even for noVertexS.
- enum { is_target = false }; // has no meaning here
-
- enum { halfedge_supports_facets = false };
-
+ enum {
+ halfedge_has_opposite_member = !meta_is_same<
+ typename HalfedgeS::container_selector, vecS>::value,
+ is_forward = HalfedgeS::is_forward,
+ is_backward = HalfedgeS::is_backward,
+ halfedge_supports_vertices = false,
+ is_source = false,
+ halfedge_supports_facets = false
+ };
         typedef typename boost::ct_if<halfedge_has_opposite_member,
- halfedge_ptr, std::size_t>::type halfedge_descriptor;
+ halfedge_ptr, std::size_t>::type halfedge_descriptor;
     };
 };
 
 template <typename HalfedgeS, typename FacetS>
 struct halfedge_ds_gen<HalfedgeS, noVertexS, FacetS> {
     struct config {
-
- enum { halfedge_has_opposite_member = !meta_is_same<
- typename HalfedgeS::container_selector, vecS>::value };
- enum { is_forward = HalfedgeS::is_forward };
- enum { is_backward = HalfedgeS::is_backward };
- typedef typename HalfedgeS::tag traversal_tag;
- // halfedge config
-
- enum { halfedge_supports_vertices = false };
- enum { is_source = false }; // has no meaning here,
- // but vertex_helper in stored_halfedge
- // requires it defined even for noVertexS.
- enum { is_target = false }; // has no meaning here
-
- enum { halfedge_supports_facets= !meta_is_same<FacetS,noFacetS>::value};
- // facet config
-
+ enum {
+ halfedge_has_opposite_member = !meta_is_same<
+ typename HalfedgeS::container_selector, vecS>::value,
+ is_forward = HalfedgeS::is_forward,
+ is_backward = HalfedgeS::is_backward,
+ halfedge_supports_vertices = false,
+ is_source = false,
+ halfedge_supports_facets = !meta_is_same<FacetS,noFacetS>::value
+ };
         typedef typename boost::ct_if<halfedge_has_opposite_member,
- halfedge_ptr, std::size_t>::type halfedge_descriptor;
+ halfedge_ptr, std::size_t>::type halfedge_descriptor;
     };
 };
 
 template <typename HalfedgeS, typename VertexS>
 struct halfedge_ds_gen<HalfedgeS, VertexS, noFacetS> {
     struct config {
-
- enum { halfedge_has_opposite_member = !meta_is_same<
- typename HalfedgeS::container_selector, vecS>::value };
- enum { is_forward = HalfedgeS::is_forward };
- enum { is_backward = HalfedgeS::is_backward };
- typedef typename HalfedgeS::tag traversal_tag;
- // halfedge config
-
- enum { halfedge_supports_vertices = !meta_is_same<
- VertexS,noVertexS>::value };
- enum { is_source = VertexS::is_source };
- enum { is_target = VertexS::is_target };
- enum { has_vertex_link = VertexS::has_vertex_link };
- // vertex config
-
- enum { halfedge_supports_facets= false };
- // facet config
-
+ enum {
+ halfedge_has_opposite_member = !meta_is_same<
+ typename HalfedgeS::container_selector, vecS>::value,
+ is_forward = HalfedgeS::is_forward,
+ is_backward = HalfedgeS::is_backward,
+ halfedge_supports_vertices = !meta_is_same<VertexS,noVertexS>::value,
+ is_source = VertexS::is_source,
+ halfedge_supports_facets = false
+ };
         typedef typename boost::ct_if<halfedge_has_opposite_member,
- halfedge_ptr, std::size_t>::type halfedge_descriptor;
+ halfedge_ptr, std::size_t>::type halfedge_descriptor;
     };
 };
 

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_selectors.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_selectors.hpp (original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_selectors.hpp 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -37,12 +37,14 @@
 
                    // =========================
                    // halfedge selector classes
- // =========================
+ // =========================
+struct empty_tag {};
 
 template <typename ForwardCategory>
 struct forwardS {
     typedef forward_traversal_tag tag;
     typedef ForwardCategory next_tag;
+ typedef empty_tag prev_tag;
     enum { is_forward = true };
     enum { is_backward = false };
 };
@@ -51,6 +53,7 @@
 struct backwardS {
     typedef backward_traversal_tag tag;
     typedef BackwardCategory prev_tag;
+ typedef empty_tag next_tag;
     enum { is_forward = false };
     enum { is_backward = true };
 };

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/meta_functions.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/meta_functions.hpp (original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/meta_functions.hpp 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -1,3 +1,7 @@
+
+#ifndef BOOST_HDSTL_META_FUNCTIONS_HPP
+#define BOOST_HDSTL_META_FUNCTIONS_HPP 1
+
 struct true_type {};
 struct false_type{};
 
@@ -13,3 +17,4 @@
     typedef true_type type;
 };
 
+#endif

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_selectors.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_selectors.hpp (original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_selectors.hpp 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -191,6 +191,7 @@
 template <typename VertexType>
 struct base_vertexS {
     // A selector that specializes whether source or target vertices are stored.
+ typedef noVertexS t_type;
 };
 
 template<>
@@ -202,6 +203,7 @@
     enum { type = true };
     enum { is_source = true };
     enum { is_target = !is_source };
+ typedef sourceS t_type;
 };
 
 template<>
@@ -213,6 +215,7 @@
     enum { type = false };
     enum { is_target = true };
     enum { is_source = !is_target };
+ typedef targetS t_target;
 };
 
 template <typename ContainerS, bool HasVertexLink=false,


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk