Обход SceneGraph в Хаскеле - PullRequest
Новая
       20

Обход SceneGraph в Хаскеле

2 голосов
/ 25 июля 2010

Я хочу реализовать простой SceneGraph в Haskell, используя Data.Tree, состоящий из Transform и Shape узлов. В 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) Как избежать обходного ввода-вывода?

3) Существует ли более короткая версия для определения этого дерева? Все, кроме первого определения узла и всех пустых подфорестов, на самом деле излишни.

Спасибо!

Ответы [ 2 ]

2 голосов
/ 29 июля 2010

Как это ни парадоксально, 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.

2 голосов
/ 25 июля 2010

Мне нравится представлять деревья в виде монадических списков с монадой базового списка.если это предложение сбивает с толку, просто посмотрите на код: 

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 тем, что:

  • Вы можете использовать существующийфункции для монад и списков (например, scanl) для них.

  • Они могут быть монадическими

  • Листья и узлы с 0 дочерними элементами - это разные вещи.Это может иметь смысл в некоторых ситуациях (например, чтобы отличить пустой каталог от файла)
    • cons x mempty - это лист, а cons x (joinL []) - это узел с 0 дочерними элементами.
...