Visitor for Scene Graph

Various applications need their own conditions for tree traversal.

If spatial provides visitor interface, we don’t have to worry about Spatial/Node being messy.

I suggest Visitor interface and breadthFirstTraversal, depthFirstTraversal method().

Please rename it if it is ugly.



[patch]

Index: src/core/com/jme3/scene/Spatial.java

===================================================================

— src/core/com/jme3/scene/Spatial.java (revision 6397)

+++ src/core/com/jme3/scene/Spatial.java (working copy)

@@ -55,10 +55,7 @@

import com.jme3.scene.control.Control;

import com.jme3.util.TempVars;

import java.io.IOException;

-import java.util.ArrayList;

-import java.util.Collection;

-import java.util.Collections;

-import java.util.HashMap;

+import java.util.*;

import java.util.logging.Logger;





@@ -1383,5 +1380,19 @@

return store;

}


  • public abstract void depthFirstTraversal(Visitor visitor);

    +
  • public void breadthFirstTraversal(Visitor visitor) {
  •    Queue&lt;Spatial&gt; queue = new LinkedList&lt;Spatial&gt;();<br />
    
  •    queue.add(this);<br />
    

+

  •    while (!queue.isEmpty()) {<br />
    
  •        Spatial s = queue.poll();<br />
    
  •        visitor.visit(s);<br />
    
  •        s.breadthFirstTraversal(visitor, queue);<br />
    
  •    }<br />
    
  • }

    +
  • protected abstract void breadthFirstTraversal(Visitor visitor, Queue<Spatial> queue);

    }



    Index: src/core/com/jme3/scene/Node.java

    ===================================================================

    — src/core/com/jme3/scene/Node.java (revision 6397)

    +++ src/core/com/jme3/scene/Node.java (working copy)

    @@ -42,6 +42,7 @@

    import java.io.IOException;

    import java.util.ArrayList;

    import java.util.List;

    +import java.util.Queue;

    import java.util.logging.Level;

    import java.util.logging.Logger;



    @@ -629,5 +630,18 @@

    }

    }

    }

    +
  • @Override
  • public void depthFirstTraversal(Visitor visitor) {
  •    for(int i = 0, max = children.size(); i &lt; max; i++) {<br />
    
  •        children.get(i).depthFirstTraversal(visitor);<br />
    
  •    }<br />
    
  •    visitor.visit(this);<br />
    
  • }

    +
  • @Override
  • protected void breadthFirstTraversal(Visitor visitor, Queue<Spatial> queue) {
  •    queue.addAll(children);<br />
    
  • }



    }

    Index: src/core/com/jme3/scene/Visitor.java

    ===================================================================

    — src/core/com/jme3/scene/Visitor.java (revision 0)

    +++ src/core/com/jme3/scene/Visitor.java (revision 0)

    @@ -0,0 +1,5 @@

    +package com.jme3.scene;

    +

    +public interface Visitor {
  • public void visit(Spatial spatial);

    +}

    Index: src/core/com/jme3/scene/Geometry.java

    ===================================================================

    — src/core/com/jme3/scene/Geometry.java (revision 6397)

    +++ src/core/com/jme3/scene/Geometry.java (working copy)

    @@ -44,6 +44,8 @@

    import com.jme3.scene.VertexBuffer.Type;

    import com.jme3.util.TempVars;

    import java.io.IOException;

    +import java.util.LinkedList;

    +import java.util.Queue;



    public class Geometry extends Spatial {



    @@ -249,6 +251,14 @@

    }

    return 0;

    }

    +
  • @Override
  • public void depthFirstTraversal(Visitor visitor) {
  •    visitor.visit(this);<br />
    
  • }

    +
  • protected void breadthFirstTraversal(Visitor visitor, Queue<Spatial> queue) {
  • }



    /**
  • This version of clone is a shallow clone, in other words, the

    Index: src/test/com/jme3/scene/TestTraversal.java

    ===================================================================

    — src/test/com/jme3/scene/TestTraversal.java (revision 0)

    +++ src/test/com/jme3/scene/TestTraversal.java (revision 0)

    @@ -0,0 +1,33 @@

    +package com.jme3.scene;

    +

    +public class TestTraversal {
  • public static void main(String[] args) {
  •    Node root = new Node(&quot;root&quot;);<br />
    
  •    Node a = new Node(&quot;a&quot;);<br />
    
  •    Node b = new Node(&quot;b&quot;);<br />
    
  •    Spatial aa = new Geometry(&quot;aa&quot;);<br />
    
  •    Spatial ab = new Geometry(&quot;ab&quot;);<br />
    
  •    Spatial ba = new Geometry(&quot;ba&quot;);<br />
    
  •    Spatial bb = new Geometry(&quot;bb&quot;);<br />
    

+

  •    root.attachChild(a);<br />
    
  •    root.attachChild(b);<br />
    
  •    a.attachChild(aa);<br />
    
  •    a.attachChild(ab);<br />
    
  •    b.attachChild(ba);<br />
    
  •    b.attachChild(bb);<br />
    

+

  •    Visitor v = new Visitor() {<br />
    

+

  •        @Override<br />
    
  •        public void visit(Spatial searchScope) {<br />
    
  •            System.out.println(searchScope.getName());<br />
    
  •        }<br />
    
  •    };<br />
    

+

  •    System.out.println(&quot;DFS&quot;);<br />
    
  •    root.depthFirstTraversal(v);<br />
    
  •    System.out.println(&quot;BFS&quot;);<br />
    
  •    root.breadthFirstTraversal(v);<br />
    
  • }

    +}



    [/patch]
2 Likes

Is it useless?

I think this kind of approach gives the flexibility to scene graph handling

I like it :slight_smile:

I was waiting for the other opinion before commit.

If there is no objection,

Let me change the name of the interface ‘Visitor’ to ‘SceneGraphVisitor’ and commit it.

The name ‘Visitor’ seems to be ambiguous.

I wonder if it might be maybe better to have separate method calls in Visitor for Nodes and for Geometry. I suppose that in most of the cases people will be interested only in Geometries, so it will save a bit of instanceof/casts (empty method is probably giving intent cleaner). If you will provide SceneGraphVisitorAdapter (or AbstractGraphVisitor) with empty implementations of both methods, it can be even less verbose.

abies said:
I wonder if it might be maybe better to have separate method calls in Visitor for Nodes and for Geometry. I suppose that in most of the cases people will be interested only in Geometries, so it will save a bit of instanceof/casts (empty method is probably giving intent cleaner). If you will provide SceneGraphVisitorAdapter (or AbstractGraphVisitor) with empty implementations of both methods, it can be even less verbose.

Thank you for the suggestion.
I added it. :)
Waiting for more opinions before commit.
[java]
package com.jme3.scene;

public class SceneGraphVisitorAdapter implements SceneGraphVisitor {

public void visit(Geometry geom) {}

public void visit(Node geom) {}

@Override
public final void visit(Spatial spatial) {
if (spatial instanceof Geometry) {
visit((Geometry)spatial);
} else {
visit((Node)spatial);
}
}
}

[/java]

committed. rev 6468