Haskell中的场景图遍历

我想使用由Transform和Shape节点组成的Data.Tree在Haskell中实现简单的SceneGraph。在SceneGraph中，空间变换在遍历时进行累加并应用于渲染形状。Haskell中的场景图遍历

type Transform = Vector2 Double 
data Shape  = Circle Double | Square Double 
data SceneNode = XFormNode Transform | ShapeNode Shape

说我们有与我想出了这个树定义，移动到右侧和底部是一个四方的对象，并在上面

^ 
| 
| () 
| [] 
0----->

一个圈一个场景：

let tree = Node (XFormNode (vector2 10 0)) 
       [Node (ShapeNode (Square 10)) [] 
       ,Node (XFormNode (vector2 0 10)) 
         [Node (ShapeNode (Circle 10)) []] 
       ]

渲染会是这样的：

render :: Position2 -> Shape -> IO() 
render p (Circle r) = drawCircle p r 
render p (Square a) = drawSquare p a

我的问题是：

1）您如何定义一个traverse函数，该函数累积转换并调用渲染任务？

2）你如何避免进行遍历IO？

3）是否有更短的版本来定义这棵树？除第一个节点定义和所有空子树外，其他所有节点实际上都是多余的。

谢谢！

来源

2010-07-25 Gerold Meisinger

矛盾的是，Data.Tree没有在Haskell，因为定义一个定制的树型是那么容易的使用非常频繁。在你的情况，如下我将实现场景图（树）：

type Transform = Vector2 Double 
data Shape  = Circle Double | Square Double 
data Scene  = Transform Transform [Scene] | Shape Shape

你的榜样成为

example :: Scene 
example = Transform (vector2 10 0) 
        [ Shape (Square 10) 
        , Transform (vector2 0 10) [Shape (Circle 10)] 
        ]

这个答案指向3.

遍历树，使用递归：

render :: Position2 -> Scene -> IO() 
render p (Transform v scenes) = mapM_ (render (p+v)) scenes 
render p (Shape (Circle r)) = drawCircle p r 
render p (Shape (Square a)) = drawSquare p a

还有更多的通用遍历可用，例如在Data.Traversable，但他们更“统一”。总之，在树上使用递归是非常好的。

考虑到第2点，一旦您决定圆形和方块应该在IO monad中呈现，没有什么可以做的了。

来源

2010-07-29 08:34:18

我喜欢用基础列表monad表示树作为单子列表。如果这句话是混乱的，只是看代码：

import Control.Applicative (liftA2) 
import Control.Monad.ListT (ListT) -- "List" in hackage 
import Data.List.Class (cons, joinL, lastL, scanl) -- "List" in hackage 
import Data.Monoid (mempty) 
import Data.Tensor (Vector2 (..)) -- "Tensor" in hackage 
import Prelude hiding (scanl) 

type Transform = Vector2 Double 
data Shape  = Circle Double | Square Double deriving Show 
data SceneNode = XFormNode Transform | ShapeNode Shape deriving Show 

tree :: ListT [] SceneNode 
tree 
    = cons (XFormNode (Vector2 10 0)) 
    $ joinL 
     [ cons (ShapeNode (Square 10)) mempty 
     , cons (XFormNode (Vector2 0 10)) $ cons (ShapeNode (Circle 10)) mempty 
     ] 

traverseStep :: (Transform, SceneNode) -> SceneNode -> (Transform, SceneNode) 
traverseStep (ta, _) [email protected](XFormNode tb) = (liftA2 (+) ta tb, n) 
traverseStep (t, _) n = (t, n) 

ghci> lastL $ scanl traverseStep (Vector2 0 0, XFormNode (Vector2 0 0)) tree 
[ (Vector2 10.0 0.0, ShapeNode (Square 10.0)) 
, (Vector2 10.0 10.0, ShapeNode (Circle 10.0)) 
]

这些树的出入在Data.Tree在于：

您可以使用现有功能的单子和列表（如scanl）对于这些。
它们可以是一元
- 例如目录结构树可以为你遍历这其中产生IO-一元树。它的类型将是ListT (ListT IO) FilePath。对于此示例，请参见http://github.com/yairchu/generator/blob/master/ListTree/src/System/Directory/ListTree.hs
具有0个孩子的叶和节点是不同的东西。这或许会让人感觉在某些情况下（例如区分一个文件的空目录）
- cons x mempty是叶，并cons x (joinL [])是0孩子的节点。

来源

2010-07-25 13:15:59 yairchu

Haskell中的场景图遍历

回答

相关问题