Most efficient way to render complex shapes

I am new to OpenGL and I appreciate those who can suggest me the most efficient way to render objects with complex bumps and etches.

I have a huge dynamic matrix defining the depth of a surface (usually 1000 x 1000 matrix, but depending on the resolution desired). Some parts of the surface are mainly flat while other parts have high definition bumps. My initial approach rendering this surface is using lots triangles, each with vertices of 3 adjacent depth points, and then recursively grouping these triangles with adjacent ones that have the same normal, thus making quads or polygons (for video card rendering efficiency: true?). I don’t have to care about how complex the surface is with this approach.
The second approach is figuring out where curved surfaces exist and use quads and cylinders (but aren’t those shapes basically formed with triangles?). Because some regions of the surface are strictly parts of a cone and I have height and radius information, I can use those existing information efficiently. This way the rendering doesn’t have to go through all the triangles like in the first approach. However, the downside of this approach is that I have to separate out regions for triangle parts, for partly cone parts, and for planar parts (regions usually not rectangle bounds but unions of rectangles or more complexed).
The last thought of approach is uncertain. I don’t know if there is a function in the GLU that does unions/subtration of solid shapes (like in AutoCAD solids). This would be the best way to implement my code if the function exists because the bumps and etches are solely based on solid additions and subtractions (with boxes, cones, and spheres).

Thank you for your help!

Is heightmap the way?

This is just a thought (I have never seen it or tried it). If the surface is really flat with a few bumps you could render the surface first then the bumps. Since the surface is flat you will only need to specify one normal. Additionally, there’s no reason you can’t render that surface using large quads/tris (the equivalent of 4 or more quads/tris) which would be faster. Lighting concerns might be the only reason not to do this.

If you can render the bumps using tris/quads do so. Any other function will break a complex shape down to a set of tris, so it should be faster if you do the work yourself.

You can use display lists speed up everything. Draw to a display list and then use it until the image changes. You could also break up the DL into several smaller ones and update only the one that needs changing.

You can also use vertex arrays to speed up your drawing. I also hear frustrum culling is good too.