2

我想在 Haskell 中使用Data.Tree包含Transform和Shape节点实现一个简单的 SceneGraph。在 SceneGraph 中，空间变换在遍历时累积并应用于形状以进行渲染。

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) 是否有更短的版本来定义这棵树？除了第一个 Node 定义和所有空的 subForests 之外的所有内容实际上都是多余的。

谢谢！

4

2 回答 2

2

矛盾的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

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

关于第 2 点，一旦您决定应该在IOmonad 中渲染圆形和正方形，您就无能为力了。

于 2010-07-29T08:34:18.457 回答
2

我喜欢将树表示为带有底层列表单子的单子列表。如果这句话让人迷惑，直接看代码：

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, _) n@(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在于：

  • 您可以将现有函数用于 monad 和列表（如scanl）。

  • 他们可以是一元的

  • 具有 0 个子节点的叶子和节点是不同的东西。这在某些情况下可能有意义（例如，将空目录与文件区分开来）
    • cons x mempty是一个叶子，cons x (joinL [])是一个有 0 个子节点的节点。
于 2010-07-25T13:15:59.273 回答