An optimized Maya function that returns the dag node names that are at least visible once on whole frames between requested start and end frame, this accounts for animated visibilities of the nodes and their parents.

maya_get_visible_in_frame_range.py

import maya.api.OpenMaya as om2
import maya.cmds as mc
import contextlib

from colorbleed.maya.lib import iter_parents


@contextlib.contextmanager
def maintained_time():
    ct = cmds.currentTime(query=True)
    try:
        yield
    finally:
        cmds.currentTime(ct, edit=True)


def memodict(f):
    """Memoization decorator for a function taking a single argument"""
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__


def get_visible_in_frame_range(nodes, start, end):
    """Return nodes that are visible in start-end frame range.

    - Ignores intermediateObjects completely.
    - Considers animated visibility attributes + upstream visibilities.
    
    This is optimized for large scenes where some nodes in the parent
    hierarchy might have some input connections to the visibilities,
    e.g. key, driven keys, connections to other attributes, etc.
    
    This only does a single time step to `start` if current frame is
    not inside frame range since the assumption is made that changing 
    a frame isn't so slow that it beats querying all visibility 
    plugs through MDGContext on another frame.

    Args:
        nodes (list): List of node names to consider.
        start (int): Start frame.
        end (int): End frame.

    Returns:
        list: List of node names. These will be long full path names so
            might have a longer name than the input nodes.

    """
    # States we consider per node
    VISIBLE = 1  # always visible
    INVISIBLE = 0  # always invisible
    ANIMATED = -1  # animated visibility

    # Consider only non-intermediate dag nodes and use the "long" names.
    nodes = cmds.ls(nodes, long=True, noIntermediate=True, type="dagNode")
    if not nodes:
        return []


    with maintained_time():
        # Go to first frame of the range if we current time is outside of
        # the queried range. This is to do a single query on which are at
        # least visible at a time inside the range, (e.g those that are
        # always visible)
        current_time = cmds.currentTime(query=True)
        if not (start <= current_time <= end):
            cmds.currentTime(start)
            
        visible = cmds.ls(nodes, long=True, visible=True)
        if len(visible) == len(nodes) or start == end:
            # All are visible on frame one, so they are at least visible once
            # inside the frame range.
            return visible

    # For the invisible ones check whether its visibility and/or
    # any of its parents visibility attributes are animated. If so, it might
    # get visible on other frames in the range.
    @memodict
    def get_state(node):
        plug = node + ".visibility"
        connections = mc.listConnections(plug, source=True, destination=False)
        if connections:
            return ANIMATED
        else:
            return VISIBLE if mc.getAttr(plug) else INVISIBLE

    visible = set(visible)
    invisible = [node for node in nodes if node not in visible]
    always_invisible = set()
    # Iterate over the nodes by short to long names, so we iterate the highest
    # in hierarcy nodes first. So the collected data can be used from the
    # cache for parent queries in next iterations.
    node_dependencies = dict()
    for node in sorted(invisible, key=len):

        state = get_state(node)
        if state == INVISIBLE:
            always_invisible.add(node)
            continue

        # If not always invisible by itself we should go through and check
        # the parents to see if any of them are always invisible. For those
        # that are "ANIMATED" we consider that this node is dependent on
        # that attribute, we store them as dependency.
        dependencies = set()
        if state == ANIMATED:
            dependencies.add(node)

        traversed_parents = list()
        for parent in iter_parents(node):

            if not parent:
                # Workaround bug in iter_parents
                continue

            if parent in always_invisible or get_state(parent) == INVISIBLE:
                # When parent is always invisible then consider this parent,
                # this node we started from and any of the parents we
                # have traversed in-between to be *always invisible*
                always_invisible.add(parent)
                always_invisible.add(node)
                always_invisible.update(traversed_parents)
                break

            # If we have traversed the parent before and its visibility
            # was dependent on animated visibilities then we can just extend
            # its dependencies for to those for this node and break further
            # iteration upwards.
            parent_dependencies = node_dependencies.get(parent, None)
            if parent_dependencies is not None:
                dependencies.update(parent_dependencies)
                break

            state = get_state(parent)
            if state == ANIMATED:
                dependencies.add(parent)

            traversed_parents.append(parent)

        if node not in always_invisible and dependencies:
            node_dependencies[node] = dependencies

    if not node_dependencies:
        return list(visible)

    # Now we only have to check the visibilities for nodes that have animated
    # visibility dependencies upstream. The fastest way to check these
    # visibility attributes across different frames is with Python api 2.0
    # so we do that.
    @memodict
    def get_visibility_mplug(node):
        """Return api 2.0 MPlug with cached memoize decorator"""
        sel = om2.MSelectionList()
        sel.add(node)
        dag = sel.getDagPath(0)
        return om2.MFnDagNode(dag).findPlug("visibility", True)

    # We skip the first frame as we already used that frame to check for
    # overall visibilities. And end+1 to include the end frame.
    scene_units = om2.MTime.uiUnit()
    for frame in range(start + 1, end + 1):

        mtime = om2.MTime(frame, unit=scene_units)
        context = om2.MDGContext(mtime)

        # Build little cache so we don't query the same MPlug's value
        # again if it was checked on this frame and also is a dependency 
        # for another node
        frame_visibilities = {}
        
        for node, dependencies in node_dependencies.items():

            for dependency in dependencies:

                dependency_visible = frame_visibilities.get(dependency, None)
                if dependency_visible is None:
                    mplug = get_visibility_mplug(dependency)
                    dependency_visible = mplug.asBool(context)
                    frame_visibilities[dependency] = dependency_visible

                if not dependency_visible:
                    # One dependency is not visible, thus the
                    # node is not visible.
                    break

            else:
                # All dependencies are visible.
                visible.add(node)
                # Remove node with dependencies for next iterations
                # because it was visible at least once.
                node_dependencies.pop(node)

        # If no more nodes to process break the frame iterations..
        if not node_dependencies:
            break

    return list(visible)

Here's an alternate version that is much simpler, but in most cases where not all objects have keys/connections this is much slower.

import maya.cmds as cmds
import contextlib


@contextlib.contextmanager
def maintained_time():
    ct = cmds.currentTime(query=True)
    try:
        yield
    finally:
        cmds.currentTime(ct, edit=True)


def get_visible_in_frame_range(nodes, start, end):
    """Return nodes that are visible in start-end frame range.

    This will step through time frame by frame until is has
    checked and considered all frames.

    Args:
        nodes (list): List of node names to consider.
        start (int): Start frame.
        end (int): End frame.

    Returns:
        list: List of node names. These will be long full path names so
            might have a longer name than the input nodes.

    """
    # Consider only non-intermediate dag nodes
    nodes = cmds.ls(nodes, noIntermediate=True, type="dagNode", long=True)
    if not nodes:
        return []

    visible = set()
    remaining = set(nodes)
    with maintained_time():
        for frame in range(start, end+1):
            
            cmds.currentTime(frame)
            new_visible = set(cmds.ls(remaining, visible=True, long=True))
            
            if new_visible:
                visible.update(new_visible)
                remaining -= new_visible
            
                if not remaining:
                    break
                   
    return list(visible)

Here's a little helper script to create some transforms with randomly keyed visibility attributes in multiple hierarchies. This can act as a quick sample scene to test the speed of the scripts.

# Create some random node hierarchies with random visibility keys
import random
from maya import cmds

# SETTINGS
# Number of separate hierarchy chains
num_hierarchies = 350

# Depth of nodes in each hierarchy
num_depth = 10

# Set random value for non-keyed objects
set_random_default = True

# Number of keyframes when something is keyed randomly
num_keyframes = 25

# Chances that a node has keys/connections on visibility
keyed_probability = 0.5

# Start and end frame to randomly place keys between
start = 1
end = 1000

# CREATE
for a in range(num_hierarchies):
    parent = None
    for b in range(num_depth):
        transform = cmds.createNode("transform")
        if parent:
            transform = cmds.parent(transform, parent)[0]
        
        if set_random_default:
            random_default_state = random.choice([True, False])
            cmds.setAttr(transform + ".visibility", random_default_state)
            
        # Set 25 random visibility keys between start end frame
        if random.uniform(0, 1) < keyed_probability:
            for c in range(num_keyframes):
                random_frame = random.randint(start, end)
                random_visibility = random.choice([True, False])
                cmds.setKeyframe(transform, attribute="visibility", time=random_frame, value=random_visibility)
            
        # Use as parent for next iteration
        parent = transform

As a reference, MEL procedure nodeIsVisible to query whether a node is considered visible.

The Evaluation Manager documentation mentions a Invisibility Evaluator which seems to perform a similar task. Potentially we could take the information from the EM and query the visible nodes that way.

The invisibility evaluator prevents the evaluation of any node not upstream from a visible DAG node by identifying all DAG nodes considered invisible for the purposes of the modeling viewport. To determine which nodes to render invisible, the evaluator takes any of the following states into consideration:

• A node with its "Visibility" attribute set to false.
• A node with its "Draw Override Visibility" attribute set to false and its "Draw Override Enabled' attribute set to true.
• A node in a display layer that causes option #2 (above) to be true.
• A node has its "IsIntermediateObject" attribute set to true.
• Every path from a node upward to the root encounters at least one node for which at least one of the above is true. (Every is important in this case, with regard to instancing - every instance path to a node must be rendered invisible by one of the above.)

Any nodes the only drive invisible nodes are frozen and do not evaluate. (A visible DAG node is considered to drive itself so it will always evaluate.)

In most cases, the net result of enabling the invisibility evaluator should be no visible change in your scene, and a modest-to-significant increase in playback speed (depending on what is invisible).

Could be something worth investigating.