game.models.half-edge words for walking half-edge model representation

diff --git a/extra/game/models/half-edge/authors.txt b/extra/game/models/half-edge/authors.txt
new file mode 100644 (file)
index 0000000..f13c9c1
--- /dev/null
+++ b/extra/game/models/half-edge/authors.txt
@@ -0,0 +1 @@
+Joe Groff

diff --git a/extra/game/models/half-edge/half-edge-tests.factor b/extra/game/models/half-edge/half-edge-tests.factor
new file mode 100644 (file)
index 0000000..5431fcb
--- /dev/null
+++ b/extra/game/models/half-edge/half-edge-tests.factor
@@ -0,0 +1,66 @@
+USING: accessors game.models.half-edge kernel sequences
+tools.test ;
+IN: game.models.half-edge.tests
+
+CONSTANT: cube-edges
+    {
+        T{ edge { face 0 } { vertex  0 } { opposite-edge  6 } { next-edge  1 } }
+        T{ edge { face 0 } { vertex  1 } { opposite-edge 19 } { next-edge  2 } }
+        T{ edge { face 0 } { vertex  3 } { opposite-edge 12 } { next-edge  3 } }
+        T{ edge { face 0 } { vertex  2 } { opposite-edge 21 } { next-edge  0 } }
+
+        T{ edge { face 1 } { vertex  4 } { opposite-edge 10 } { next-edge  5 } }
+        T{ edge { face 1 } { vertex  5 } { opposite-edge 16 } { next-edge  6 } }
+        T{ edge { face 1 } { vertex  1 } { opposite-edge  0 } { next-edge  7 } }
+        T{ edge { face 1 } { vertex  0 } { opposite-edge 20 } { next-edge  4 } }
+
+        T{ edge { face 2 } { vertex  6 } { opposite-edge 14 } { next-edge  9 } }
+        T{ edge { face 2 } { vertex  7 } { opposite-edge 17 } { next-edge 10 } }
+        T{ edge { face 2 } { vertex  5 } { opposite-edge  4 } { next-edge 11 } }
+        T{ edge { face 2 } { vertex  4 } { opposite-edge 23 } { next-edge  8 } }
+
+        T{ edge { face 3 } { vertex  2 } { opposite-edge  2 } { next-edge 13 } }
+        T{ edge { face 3 } { vertex  3 } { opposite-edge 22 } { next-edge 14 } }
+        T{ edge { face 3 } { vertex  7 } { opposite-edge  8 } { next-edge 15 } }
+        T{ edge { face 3 } { vertex  6 } { opposite-edge 18 } { next-edge 12 } }
+
+        T{ edge { face 4 } { vertex  1 } { opposite-edge  5 } { next-edge 17 } }
+        T{ edge { face 4 } { vertex  5 } { opposite-edge  9 } { next-edge 18 } }
+        T{ edge { face 4 } { vertex  7 } { opposite-edge 13 } { next-edge 19 } }
+        T{ edge { face 4 } { vertex  3 } { opposite-edge  1 } { next-edge 16 } }
+
+        T{ edge { face 5 } { vertex  4 } { opposite-edge  7 } { next-edge 21 } }
+        T{ edge { face 5 } { vertex  0 } { opposite-edge  3 } { next-edge 22 } }
+        T{ edge { face 5 } { vertex  2 } { opposite-edge 15 } { next-edge 23 } }
+        T{ edge { face 5 } { vertex  6 } { opposite-edge 11 } { next-edge 20 } }
+    }
+
+: connect-cube-edges ( -- )
+    cube-edges [
+        [ cube-edges nth ] change-opposite-edge
+        [ cube-edges nth ] change-next-edge
+        drop
+    ] each ;
+
+connect-cube-edges
+
+[ 0 1 ]
+[ cube-edges first edge-vertices ] unit-test
+
+[ { 0 0 0 } ]
+[ cube-edges first vertex-edges [ vertex>> ] map ] unit-test
+
+[ 3 ]
+[ cube-edges first vertex-valence ] unit-test
+
+[ { 0 1 3 2 } ]
+[ cube-edges first face-edges [ vertex>> ] map ] unit-test
+
+[ 4 ]
+[ cube-edges first face-sides ] unit-test
+
+[ { 1 4 2 } ]
+[ cube-edges first vertex-neighbors ] unit-test
+
+[ { 1 4 3 5 } ]
+[ cube-edges first face-neighbors ] unit-test

diff --git a/extra/game/models/half-edge/half-edge.factor b/extra/game/models/half-edge/half-edge.factor
new file mode 100644 (file)
index 0000000..1b799bb
--- /dev/null
+++ b/extra/game/models/half-edge/half-edge.factor
@@ -0,0 +1,51 @@
+! (c)2010 Joe Groff bsd license
+USING: accessors arrays fry kernel locals math sequences ;
+IN: game.models.half-edge
+
+TUPLE: edge < identity-tuple face vertex opposite-edge next-edge ;
+
+: edge-vertices ( edge -- start end )
+    [ vertex>> ] [ opposite-edge>> vertex>> ] bi ;
+
+! building blocks for edge loop iteration
+
+: (collect) ( in quot iterator -- out )
+    [ collector ] dip dip >array ; inline
+
+: (reduce) ( in initial quot iterator -- accum )
+    [ swap ] 2dip call ; inline
+
+: (count) ( in iterator -- count )
+    [ 0 [ drop 1 + ] ] dip (reduce) ; inline
+
+: edge-loop ( ..a edge quot: ( ..a edge -- ..b ) next-edge-quot: ( ..b edge -- ..a edge' ) -- ..a )
+    pick '[ _ _ bi dup _ eq? not ] loop drop ; inline
+
+! iterate over related edges
+
+: each-vertex-edge ( ... edge quot: ( ... edge -- ... ) -- ... )
+    [ opposite-edge>> next-edge>> ] edge-loop ; inline
+
+: each-face-edge ( ... edge quot: ( ... edge -- ... ) -- ... )
+    [ next-edge>> ] edge-loop ; inline
+
+! 
+
+: vertex-edges ( edge -- edges )
+    [ ] [ each-vertex-edge ] (collect) ;
+
+: vertex-neighbors ( edge -- edges )
+    [ opposite-edge>> vertex>> ] [ each-vertex-edge ] (collect) ;
+
+: vertex-valence ( edge -- count )
+    [ each-vertex-edge ] (count) ;
+
+: face-edges ( edge -- edges )
+    [ ] [ each-face-edge ] (collect) ;
+
+: face-neighbors ( edge -- edges )
+    [ opposite-edge>> face>> ] [ each-face-edge ] (collect) ;
+
+: face-sides ( edge -- count )
+    [ each-face-edge ] (count) ;
+

diff --git a/extra/game/models/half-edge/summary.txt b/extra/game/models/half-edge/summary.txt
new file mode 100644 (file)
index 0000000..6f0aac5
--- /dev/null
+++ b/extra/game/models/half-edge/summary.txt
@@ -0,0 +1 @@
+Iterators for half-edge geometry structures