Generating a Fractal Landscape

Creating the Landscape

Landscape 's initial task is to build the terrain and the four walls around it. The resulting scene graph is shown in Figure 26-4.

The number of TexturedPlanes objects will vary depending on the height of the generated quads . Each TexturedPlanes holds all the quads within a given height range, therefore allowing them to be assigned the same texture. This means that the program only has to create one texture per TexturedPlanes object as opposed to one texture for each quad, a significant reduction in the number of objects.

Figure 26-4. Landscape's scene graph

The moving viewpoint hugs the landscape by utilizing Java 3D picking. I'll explain the details later, but it involves shooting a pick ray straight down underneath the viewpoint to hit a quad in the floor. The (x, y, z) coordinate of the intersection with the quad is obtained, and the y-value is used to set the y-axis position of the viewpoint.

The TexturedPlanes are grouped under the floorBG BranchGroup so picking can be localized to everything below floorBG , excluding the walls attached to the landBG BranchGroup .

No transformGroup nodes are in the graph, and landBG is attached directly to the top-level sceneBG node. This means that the local coordinates used inside the TexturedPlanes and ColouredPlane objects are scene coordinates, and mapping between local and world values is unnecessary. This is an important optimization when picking is employed: it means that the (x, y, z) coordinate returned from the hit quad is the intersection point in world coordinates, so can be used immediately to modify the viewpoint's position.

Creating Floors

Landscape calls on FractalMesh to generate the coordinates for the floor:

FractalMesh fm = new FractalMesh(flatness);
    // fm.printMesh(1);   // for debugging: x=0; y=1; z=2
    vertices = fm.getVertices(  );

The size of the floor is FLOOR_LEN , centered around the origin in the XZ plane.

vertices[] holds Point3d objects organized by FractalMesh into groups of four, each group representing a distinct quad. The four points in a group are specified in counterclockwise order when the points are viewed from above, with the bottom leftmost point first. For example, a possible sequence of points could be (0,5,1), (1,5,1), (1,5,0), (0,5,0), which corresponds to the quad shown in Figure 26-5.

Figure 26-5. A quad from above

The quads in vertices[] are sorted into separate ArrayList s in platifyFloor( ) based on their average heights and then passed to TexturedPlanes objects:

private void platifyFloor(  )
    {
      ArrayList[] coordsList = new ArrayList[NUM_TEXTURES];
      for (int i=0; i < NUM_TEXTURES; i++)
        coordsList[i] = new ArrayList(  );
   
      int heightIdx;
      for (int j=0; j < vertices.length; j=j+4) {   // test each quad
        heightIdx = findHeightIdx(j);   //which height applies to quad?
        addCoords( coordsList[heightIdx], j);   // add quad to list
        checkForOrigin(j);       // check if (0,0) in the quad
      }
   
      // use coordsList and texture to make TexturedPlanes object
      for (int i=0; i < NUM_TEXTURES; i++)
        if (coordsList[i].size(  ) > 0)    // if used
          floorBG.addChild( new

TexturedPlanes

(coordsList[i],
                                  "images/"+textureFns[i]) );  // add to floor
    } // end of platifyFloor(  )

platifyFloor( ) passes a filename to each TexturedPlanes, holding the texture that will be laid over each of the quads. The resulting TexturedPlanes object is a Shape3D , added to floorBG as shown in Figure 26-4.

Don't bother looking for "platify" in a dictionary; it's my invention, meant to capture the idea that the floor is covered (plated) with textured quads.

platifyFloor( ) also checks the coordinates in vertices[] to find the one positioned at (0, 0) on the XZ plane, to obtain its height. The coordinate is stored in originVec and made accessible with the public method getOriginVec( ) . That method is utilized by KeyBehavior to position the viewpoint at (0, 0) and at the correct height.

Creating Walls

addWalls( ) generates eight coordinates that specify the top and bottom corners of the four walls around the floor. The coordinates are passed to four ColouredPlane objects to create the walls attached to landBG (see Figure 26-4). Here is a code fragment:

private void addWalls(  )
    {
      Color3f eveningBlue = new Color3f(0.17f, 0.07f, 0.45f);
   
      // the eight corner points
      // back, left
      Point3d p1 = new Point3d(-WORLD_LEN/2.0f, MIN_HEIGHT, -WORLD_LEN/2.0f);
      Point3d p2 = new Point3d(-WORLD_LEN/2.0f, MAX_HEIGHT, -WORLD_2.0f);
     
      // code for seven more corners, finishing with ...
      // back, right
      Point3d p7 = new Point3d(WORLD_LEN/2.0f, MIN_HEIGHT, -WORLD_LEN/2.0f);
      Point3d p8 = new Point3d(WORLD_LEN/2.0f, MAX_HEIGHT, -WORLD_LEN/2.0f);
   
      // left wall; its points are specified in counter-clockwise order
      landBG.addChild( new ColouredPlane(p3, p1, p2, p4,
                                      new Vector3f(-1,0,0), eveningBlue) );
      // code for three more walls, finishing with ...
      // back wall
      landBG.addChild( new ColouredPlane(p7, p8, p2, p1,
                                       new Vector3f(0,0,1), eveningBlue) );
    } // end of addWalls(  )

Take care to supply the points in the right order so the front face of each plane is pointing into the scene. Otherwise, the lighting effects will appear on the face pointing out, hidden from the user .

On the Floor

When the user walks into a wall, any further forward movement is ignored. KeyBehavior prevents the user walking off the edge of the floor by calling the public method inLandscape( ) offered by the Landscape class:

public boolean inLandscape(double xPosn, double zPosn)
    {
      int x = (int) Math.round(xPosn);
      int z = (int) Math.round(zPosn);
      if ((x <= -WORLD_LEN/2)  (x >= WORLD_LEN/2) 
          (z <= -WORLD_LEN/2)  (z >= WORLD_LEN/2))
        return false;
      return true;
    }

Picking a Height

When the user presses a key to move, KeyBehavior can easily calculate the new (x, z) position, but the viewpoint cannot move until the height of the floor at that new spot (its y-value) is obtained. This is the task of getLandHeight( ) , by using picking on the floor's BranchGroup . However, before getLandHeight( ) can be employed, a PickTool object is created in Landscape 's constructor:

private PickTool picker;   // global
   
    picker = new PickTool(floorBG);   // only check the floor
    picker.setMode(PickTool.GEOMETRY_INTERSECT_INFO);

picker 's mode is set so the intersection coordinates can be obtained. It's restricted to the floor's BranchGroup , eliminating the walls from the intersection calculations. getLandHeight( ) uses the (x, z) coordinate as a starting location for a downward pointing pick ray which intersects with the floor. The returned intersection information includes the height of the floor at that (x, z) point, which is passed back to KeyBehavior . The relevant code fragment from the moveBy( ) method in KeyBehavior is shown here:

Vector3d nextLoc = tryMove(theMove);   // next (x,?,z) user position
    if (!land.inLandscape(nextLoc.x, nextLoc.z))   // if not on landscape
      return;
   
    // Landscape returns floor height at (x,z)
    double floorHeight = land.

getLandHeight

(nextLoc.x, nextLoc.z, currLandHeight);

The getLandHeight( ) method is:

public double getLandHeight(double x, double z, double currHeight)
    {
      Point3d pickStart = new Point3d(x,MAX_HEIGHT*2,z);  // start high
      picker.setShapeRay(pickStart, DOWN_VEC);   // shoot ray downwards
   
      PickResult picked = picker.pickClosest(  );
      if (picked != null) {    // pick sometimes misses an edge/corner
        if (picked.numIntersections(  ) !=0) { // sometimes no intersects
          PickIntersection pi = picked.getIntersection(0);
          Point3d nextPt;
          try {   // handles 'Interp point outside quad' error
            nextPt = pi.getPointCoordinates(  );
          }
          catch (Exception e) {
             // System.out.println(e);
             return currHeight;
          }
          return nextPt.y;
        }
      }
      return currHeight;  // if we reach here, return old height
    }

The downward pointing vector is defined in DOWN_VEC :

private final static Vector3d DOWN_VEC =  new Vector3d(0.0,-1.0, 0.0);

pickClosest( ) gets the PickResult nearest to the ray's origin, which should be a quad inside a TexturedPlanes node. The PickResult object is then queried to get a PickIntersection object, and the intersection coordinate is accessed with getPointCoordinates( ) . This level of access requires the TexturedPlanes objects to have the INTERSECT_COORD picking capability:

PickTool.setCapabilities(this, PickTool.INTERSECT_COORD);

getLandHeight( ) is complicated by having to deal with several error cases:

No quad is found by the pick ray, so the PickResult object is null.
The PickResult object contains no intersections.
The extraction of the intersection coordinate from the PickIntersection object raises an Interp point outside quad exception.

None of these errors should occur since the pick ray is aimed straight down at a floor covered entirely by quads. Nevertheless, they do, reflecting the buggy nature of picking in Java 3D 1.3.1. Typically, an error occurs if a ray intersects with a quad at its edge or corner.

My error recovery strategy is to have KeyBehavior pass the current floor height into getLandHeight( ) (i.e., the height of the floor where the user will be currently standing). If an error occurs, then that height will be returned.

The effect is that when the user moves, the viewpoint may remain at the same height even if the user is moving up or down a hill. This would seem to be less than ideal since it may mean the user will walk into the side of a hill or off into thin air when descending the hill. In practice, errors occur infrequently, and one move only adjusts the height marginally, so this approach is adequate.

Another description of this picking technique, with similar code, can be found in Ben Moxon's "The Little Purple Dude Walks," online at http://www.newview.co.uk/e/tutorials/java3d/index.jsp.

Issues with Terrain Representation

My approach to representing terrain uses the Landscape class to group quads with similar heights together into the same Shape3D , so they all share the same Appearance node component. This means that the application only has to manage a few geometries and their associated textures at run time. Normal generation and stripification (described in the next section, "Constructing the Ground") only have to be applied to several large geometries, rather than numerous individual quads, which would be less efficient.

However, this approach has some drawbacks, especially if the terrain is large. One issue is view frustum culling, where Java 3D renders only what can be seen in the user's FOV. In effect, Java 3D only displays what the user can see, which may accelerate the overall rendering time. Culling is only carried out if a shape is completely hidden from the user's viewpoint. Unfortunately, the Shape3D objects in FractalLand3D are composed from quads distributed all over the landscape. This means that little culling can be achieved in most situations, resulting in little (or no) rendering gains.

Another problem is the cost of picking, which automatically employs bounds checks to exclude Shape3D s from more detailed intersection calculations. Again, the grouping of dispersed quads means these checks may not be able to exclude many shapes .

The problems with view frustum culling and picking are caused by the simplistic approach of grouping quads together, based solely on their y-axis positions . Both problems would be alleviated if the quads were grouped based on their x- and z-coordinates. This would allow the culling and picking algorithms to exclude shapes that were located far away from the viewpoint.