Point'n'click terrain and optimization

Hi there !

I’m having a problem and I’m out of idea to solve it. I come here seeking for suggestions.

My pathfinding works like this: some points are dropped on the map,to show where the characters can go. When someone clicks on the terrain, I get the coordinates of the collision and look for the closest waypoint.

The problem with this is that the collision test happens directly on the geometry of the terrain’s model. Sometimes these models can be really huge, and the collision test starts taking a lot of time.

So this is the current situation: I have a big big model. I need to find at which coordinates the mouse has clicked on it with performances that are as little as possible influenced by the polygon count.

It is to be considered that the camera can move in all angles. There might be several ‘terrain’ models. There might be several floors of terrains.

Has someone any ideas to help me solve this problem ?

Hi

Are you using CollisionRay to do your picking ?
I have a scene with a 1025x1025 GeoMip terrain (using LOD)
and models on that and it seems to be pretty quick…

Greetings !
It’s a CollisionRay indeed.
And true, my 1025x1025 maps are fine. It gets a little slow with bigger ones however. I should maybe mention that I don’t really understand what those dimensions correspond to, I just re-implemented some code to export EarthScultor’s terrains to bam. 1025x1025 is the size I picked for my smallest maps.

I figured that perhaps I could cut the bigger ones in several maps. Would it make things faster ?
I might be able to do it myself. But I’d rather code something to do it instead. If that’s a possible solution, by what means might I achieve such a deed ?

It’s really a big performance issue with me, especially considering that I not only use it for click events, but also hovering events. The collision check is performed much more often.

I think that geomipterrain makes 2 triangles for each point of the map (at lod 0) so that makes ~2 milion polygons from a 1025x1025 map.
Things you can do
-use a lower lod seting or a resized map to make a collision
-use octree
-Bullet has a heightmap shape, could be worth trying that
-use a plane for mouse collisions and cast a ray up from the point where the mouse/plane collision happened. You could have a few planes and select the point that was nearest (a bit crazy idea, but could work)

Hi

The 1025X1025 dimensions is the dimensions of the height map image file.
GeoMip uses it to construct where the vertices are, the position
of the pixels in the image file correspond to the x,y position of terrain
vertices and the intensity value of the pixel is used to give the vertices
their z (height) value. The pixel value is a number between 0 and 1 so
that’s why you use set_sz on the terrain node to give it some noticeable
height.

Yes cutting your larger terrain into smaller ones can help, that will give you
more bounding boxes for it to narrow down on if your collision traverser is set
to the root node of them all; or you can just give it the one terrain node that
your camera is over.

Actually my scene consists of multiple 1025x1025 terrain areas (3x3 of them)
so 9 terrain areas of the size 1025x1025 and I’m happy with the picking. I use
the picking to point my camera and to select models and place models.

That’s actually exactly what I used to do before.
The problem was that to pick the y position of the plane, I made an average of the y position of all the waypoints of the floor. So when the terrain was getting bumpy, or when the average was completely off for some part of the map, the precision issues were very noticeable (or downright ruining the experience of the game in the worst cases).
But yeah it was pretty fast :slight_smile: !

From what I can gather on google, this looks like a good way to implement the cutting of the terrain.
This topic might help, if I can port the code to C++:

Thanks a lot for all the details ! It helps a great deal !
This looks very promising: I’ll check out the octree, and if I get it to work properly I’ll come back with a C++ port of the ‘Egg Octree’ script.

Yesterday I tried to come up with my own solution, and the results seem promising (although, admittedly, I have little experience using terrains, so you are advised to do some rigorous testing). It makes use of my single-pixel camera, which renders the terrain as being textured with its own heightmap. This “terrain camera” renders only the pixel that the mouse cursor is over, so this is quite fast. The color of that pixel immediately gives you the height of the horizontal plane to intersect the mouse ray with, and the precision of this height value seems quite acceptable. The accuracy is not so good when the mouse ray is nearly horizontal, or when the point lies on a steep slope.
If you can live with those limitations, maybe the following code sample will be of use to you:

from panda3d.core import *
from direct.showbase.ShowBase import ShowBase



class TerrainCamera(object):

  def __init__(self, app, pixel_color, height_map):

    self._app = app
    self._tex = Texture("pixel_texture")
    self._buffer = app.win.makeTextureBuffer("pixel_buffer",
                                              1, 1,
                                              self._tex,
                                              to_ram=True)

    self._buffer.setClearColor(VBase4())
    self._buffer.setSort(-100)
    self._tex_peeker = self._tex.peek()
    self._np = app.makeCamera(self._buffer)
    node = self._np.node()
    self._mask = BitMask32.bit(21)
    node.setCameraMask(self._mask)
    lens = node.getLens()
    lens.setFov(.1) # appropriate for 800 x 600 window size

    self._mouse_watcher = app.mouseWatcherNode
    self._main_cam_lens = app.camLens

    state_np = NodePath("state_np")
    state_np.setTexture(app.loader.loadTexture(height_map), 1)
    state_np.setMaterialOff(1)
    state_np.setShaderOff(1)
    state_np.setLightOff(1)
    state_np.setColorOff(1)
    state_np.setColorScaleOff(1)
    node.setInitialState(state_np.getState())

    self._pixel_color = pixel_color

    app.taskMgr.add(self.__initTexPeeker, "init_tex_peeker", priority=0)


  def __initTexPeeker(self, task):

    if not self._tex_peeker:
      self._tex_peeker = self._tex.peek()
      return task.cont

    self._app.taskMgr.add(self.__update, "get_pixel_under_mouse", priority=0)

    return task.done


  def __update(self, task):

    if not self._mouse_watcher.hasMouse():
      return task.cont

    screen_pos = self._mouse_watcher.getMouse()
    far_point = Point3()
    self._main_cam_lens.extrude(screen_pos, Point3(), far_point)
    self._np.lookAt(far_point)

    self._tex_peeker.lookup(self._pixel_color, .5, .5)

    return task.cont


  def getMask(self):

    return self._mask



class Terrain(object):

  def __init__(self, app, parent_np, height_map, height, focal_point):

    self._terrain = GeoMipTerrain("terrain")
    self._terrain.setHeightfield(height_map)
    self._terrain.setBlockSize(128)
    self._terrain.setMinLevel(2)
##    self._terrain.setBruteforce(True)
    self._terrain.setNear(4)
    self._terrain.setFar(100)
    self._terrain.setFocalPoint(focal_point)
##    self._terrain.setAutoFlatten(GeoMipTerrain.AFMStrong)
    root = self._terrain.getRoot()
    root.reparentTo(parent_np)
    self._height = height
    root.setSz(height)
##    root.setTexture(app.loader.loadTexture("terrain_tex.jpg"))
    self._terrain.generate()

    app.taskMgr.add(self.__update, "update_terrain")


  def __update(self, task):

    self._terrain.update()

    return task.cont


  def getElevation(self, x, y):

    return self._terrain.getElevation(x, y) * self._height



class Cube(object):

  def __init__(self, parent_np):

    vertex_format = GeomVertexFormat.getV3n3cpt2()
    vertex_data = GeomVertexData("cube_data", vertex_format, Geom.UHStatic)
    tri = GeomTriangles(Geom.UHStatic)

    pos_writer = GeomVertexWriter(vertex_data, "vertex")
    normal_writer = GeomVertexWriter(vertex_data, "normal")

    vertex_count = 0

    for direction in (-1, 1):

      for i in range(3):

        normal = VBase3()
        normal[i] = direction

        for a, b in ( (-1., -1.), (-1., 1.), (1., 1.), (1., -1.) ):

          pos = VBase3()
          pos[i] = direction
          pos[(i + direction) % 3] = a
          pos[(i + direction * 2) % 3] = b

          pos_writer.addData3f(pos)
          normal_writer.addData3f(normal)

        vertex_count += 4

        tri.addVertices(vertex_count - 2, vertex_count - 3, vertex_count - 4)
        tri.closePrimitive()
        tri.addVertices(vertex_count - 4, vertex_count - 1, vertex_count - 2)
        tri.closePrimitive()

    cube_geom = Geom(vertex_data)
    cube_geom.addPrimitive(tri)
    cube_node = GeomNode("cube_geom_node")
    cube_node.addGeom(cube_geom)

    self._origin = parent_np.attachNewNode(cube_node)


  def getOrigin(self):

    return self._origin



class Panda3DApp(ShowBase):

  def __init__(self):

    ShowBase.__init__(self)

    self.setFrameRateMeter(True)

    p_light = PointLight("point_light")
    p_light.setColor(VBase4(1., 1., 1., 1.))
    self._light = self.camera.attachNewNode(p_light)
    self._light.setPos(5., -10., 7.)
    self.render.setLight(self._light)

    self._pixel_color = VBase4()
    self._terrain_cam = TerrainCamera(self, self._pixel_color, "height_map.png")

    self._marker = Cube(self.render).getOrigin()
    self._marker.setColor(1., 0., 0.)
    self._marker.hide(self._terrain_cam.getMask())

    self._terrain = Terrain(self, self.render, "height_map.png",
                            100., self.camera)

    self.accept("enter", self.__copyMarker)

    self.taskMgr.add(self.__setMarkerPos, "set_marker_pos", priority=1)

    self.run()


  def __copyMarker(self):

    self._marker.copyTo(self.render)


  def __setMarkerPos(self, task):

    if not self.mouseWatcherNode.hasMouse():
      return task.cont

    elevation = self._pixel_color[0] * 100.
    plane = Plane(Vec3(0., 0., 1.), Point3(0., 0., elevation))

    screen_pos = self.mouseWatcherNode.getMouse()

    far_point_local = Point3()
    self.camLens.extrude(screen_pos, Point3(), far_point_local)
    far_point = self.render.getRelativePoint(self.camera, far_point_local)
    cam_pos = self.camera.getPos(self.render)

    point = Point3()

    if plane.intersectsLine(point, cam_pos, far_point):
##      self._marker.setPos(point) # point might not be on terrain
      x, y, z = point
      z = self._terrain.getElevation(x, y) # point might not be under mouse
      self._marker.setPos(x, y, z)

    return task.cont




if __name__ == "__main__":
  Panda3DApp()

Simple yet brilliant.
[EDIT: I thought something was off but turns out I was wrong. It’s unflawed indeed, apart from the camera angle part]

Right now I’m still on the Octree solution: it will also optimize display performance. And since I intend to make much much bigger maps that what I’m doing right now, I am probably going to need this octree thing sooner or later anyway.

Hey !

I need some more information.
I’ve given up the octree, it’s much too hard to implement and I’ll probably never achieve it. I’ve also given up anything that require building an egg myself for that matter, all my attempts resulted in complete failure (not even a single piece of visible geometry).

While working on this, I noticed that my terrain geometry was already divided in even groups of nodes.
I generate them with GeoMipTerrain. Does it already optimize the egg in any way that I should know of ?

And what if I cut the heightmap in several pictures, then generated separately the eggs with GeoMipTerrain, would it optimize anything if I found a way to group all the results in a single egg ?
Is that even possible ?
Would it be as easy as that:

  • Creating an EggData for each EGG file, load the EGG files in each EggData.
  • Create a last EggData and do nothing with it.
  • Set all the EggData of the 1st point as children of the one created in the 2nd point.
  • Save the EggData from 2nd point as a new EGG file.
    Would that work ? I highly doubt it will, there are probably steps missing, but I can’t think of what.

Actually I may have something even better :slight_smile: .

The following attempt involves the use of the depth buffer (*). It solves both problems encountered with the previous code, although it’s not perfect either:

  • accuracy depends on the precision of the depth buffer (it’s possible to use the average of the image values, but that may not always be desirable);
  • since it doesn’t seem possible to get the correct image from the depth buffer every single frame, there will be a lag when checking the terrain continuously.

These shortcomings may prove more acceptable than the previous ones, but even if not, you could try to combine both methods, e.g.:
use the previous code to get the difference between the point guaranteed to be under the mouse and the point guaranteed to be on the terrain; if that difference is greater than a certain threshold value, use the depth buffer instead.

from panda3d.core import *
loadPrcFileData("", "sync-video 1")
##loadPrcFileData("", "prefer-texture-buffer 1")
##loadPrcFileData("", "prefer-parasite-buffer 0")
##loadPrcFileData("", "force-parasite-buffer 0")
from direct.showbase.ShowBase import ShowBase



class TerrainCamera(object):

  def __init__(self, app):

    self._app = app
    self._average_depth = False # whether or not the depth buffer image should be averaged
    props = FrameBufferProperties()
    props.setDepthBits(1)
    winprops = WindowProperties.size(*((4, 4) if self._average_depth else (1, 1)))
    self._buffer = app.graphicsEngine.makeOutput(app.pipe, "depth_buffer", -2,
                                                  props, winprops,
                                                  GraphicsPipe.BFRefuseWindow,
                                                  app.win.getGsg(), app.win)

    assert self._buffer is not None
  
    self._depth_tex = Texture("depth_texture")
    self._buffer.addRenderTexture(self._depth_tex, GraphicsOutput.RTMBindOrCopy,
                                  GraphicsOutput.RTPDepth)
    self._np = app.makeCamera(self._buffer)
    node = self._np.node()
    self._mask = BitMask32.bit(21)
    node.setCameraMask(self._mask)
    lens = OrthographicLens() # for a linear depth buffer
    lens.setFilmSize(*((5., 5.) if self._average_depth else (.01, .01)))
    lens.setNearFar(0., 100000.)
    node.setLens(lens)

    self._mouse_watcher = app.mouseWatcherNode
    self._main_cam_lens = app.camLens
    self._depth = 0.
    self._point = Point3()

    self._app.taskMgr.add(self.__update, "get_pixel_under_mouse", priority=0)

    # calling GraphicsEngine.extractTextureData() every frame seems problematic
    self._app.taskMgr.doMethodLater(.02, self.__getDepth, "get_depth", priority=1)


  def __getDepth(self, task):

    if self._app.graphicsEngine.extractTextureData(self._depth_tex, self._app.win.getGsg()):
      if self._average_depth:
        img = PNMImage(4, 4)
        self._depth_tex.store(img)
        self._depth = img.getAverageGray() * 100000.
      else:
        img = PNMImage(1, 1)
        self._depth_tex.store(img)
        pixel = img.getXelA(0, 0)
        self._depth = pixel[2] * 100000.
    else:
      print "Could not retrieve texture data!"

    return task.again


  def __update(self, task):

    if not self._mouse_watcher.hasMouse():
      return task.cont

    screen_pos = self._mouse_watcher.getMouse()
    far_point = Point3()
    self._main_cam_lens.extrude(screen_pos, Point3(), far_point)
    self._np.lookAt(far_point)

    dir_vec = self._app.render.getRelativeVector(self._np, Vec3(0., 1., 0.))
    self._point = self._np.getPos(self._app.render) + dir_vec * self._depth

    return task.cont


  def getMask(self):

    return self._mask


  def getPoint(self):

    return self._point



class Terrain(object):

  def __init__(self, app, parent_np, height_map, height, focal_point):

    self._terrain = GeoMipTerrain("terrain")
    self._terrain.setHeightfield(height_map)
    self._terrain.setBlockSize(128)
    self._terrain.setMinLevel(2)
    self._terrain.setBruteforce(True)
    self._terrain.setNear(4)
    self._terrain.setFar(100)
    self._terrain.setFocalPoint(focal_point)
##    self._terrain.setAutoFlatten(GeoMipTerrain.AFMStrong)
    root = self._terrain.getRoot()
    root.reparentTo(parent_np)
    self._height = height
    root.setSz(height)
##    root.setTexture(app.loader.loadTexture("terrain_tex.jpg"))
    self._terrain.generate()

    app.taskMgr.add(self.__update, "update_terrain")


  def __update(self, task):

    self._terrain.update()

    return task.cont


  def getElevation(self, x, y):

    return self._terrain.getElevation(x, y) * self._height



class Cube(object):

  def __init__(self, parent_np):

    vertex_format = GeomVertexFormat.getV3n3cpt2()
    vertex_data = GeomVertexData("cube_data", vertex_format, Geom.UHStatic)
    tri = GeomTriangles(Geom.UHStatic)

    pos_writer = GeomVertexWriter(vertex_data, "vertex")
    normal_writer = GeomVertexWriter(vertex_data, "normal")

    vertex_count = 0

    for direction in (-1, 1):

      for i in range(3):

        normal = VBase3()
        normal[i] = direction

        for a, b in ( (-1., -1.), (-1., 1.), (1., 1.), (1., -1.) ):

          pos = VBase3()
          pos[i] = direction
          pos[(i + direction) % 3] = a
          pos[(i + direction * 2) % 3] = b

          pos_writer.addData3f(pos)
          normal_writer.addData3f(normal)

        vertex_count += 4

        tri.addVertices(vertex_count - 2, vertex_count - 3, vertex_count - 4)
        tri.closePrimitive()
        tri.addVertices(vertex_count - 4, vertex_count - 1, vertex_count - 2)
        tri.closePrimitive()

    cube_geom = Geom(vertex_data)
    cube_geom.addPrimitive(tri)
    cube_node = GeomNode("cube_geom_node")
    cube_node.addGeom(cube_geom)

    self._origin = parent_np.attachNewNode(cube_node)


  def getOrigin(self):

    return self._origin



class Panda3DApp(ShowBase):

  def __init__(self):

    ShowBase.__init__(self)

    self.setFrameRateMeter(True)

    p_light = PointLight("point_light")
    p_light.setColor(VBase4(1., 1., 1., 1.))
    self._light = self.camera.attachNewNode(p_light)
    self._light.setPos(5., -10., 7.)
    self.render.setLight(self._light)

    self._terrain_cam = TerrainCamera(self)

    self._marker = Cube(self.render).getOrigin()
    self._marker.setColor(1., 0., 0.)
    self._marker.hide(self._terrain_cam.getMask())

    self._terrain = Terrain(self, self.render, "height_map.png",
                            100., self.camera)

    self._get_point_on_terrain = False # whether the point should be on the terrain,
                                       # rather than under the mouse cursor

    self.accept("enter", self.__copyMarker)

    self.taskMgr.add(self.__setMarkerPos, "set_marker_pos", priority=1)

    self.run()


  def __copyMarker(self):

    self._marker.copyTo(self.render)


  def __setMarkerPos(self, task):

    if not self.mouseWatcherNode.hasMouse():
      return task.cont

    if self._get_point_on_terrain:
      x, y, z = self._terrain_cam.getPoint()
      z = self._terrain.getElevation(x, y)
      # point might not be under mouse, but is guaranteed to be on terrain
      self._marker.setPos(x, y, z)
    else:
      # point might not be on terrain, but is guaranteed to be under mouse
      self._marker.setPos(self._terrain_cam.getPoint())

    return task.cont




if __name__ == "__main__":
  Panda3DApp()

(*) It was actually kinda hard to access the depth buffer image. For those interested, here are my misadventures:

  • using DisplayRegion.getScreenshot() or GraphicsOutput.getScreenshot() gave me the contents of the main window instead of the depth buffer, presumably because a parasite buffer was created, but “prefer-texture-buffer 1”, “prefer-parasite-buffer 0” and/or “force-parasite-buffer 0” did not help;
  • creating a TexturePeeker failed, probably because it’s incompatible with the format of the depth texture;
  • calling GraphicsEngine.extractTextureData() every single frame gave incorrect results (first, the image stayed blank, but after moving the mouse out of the window and back, it started changing seemingly randomly).