Embodiments of this invention relate to preprocessing video such that visual elements, such as advertisements, can be inserted at a later point in time when the video is requested by a user. In an embodiment, a video and target data is received. The video is analyzed to determine how a target moves and changes over time. Metadata describing how the target moves and changes over time is stored. When a user requests an on-demand video such as from a video sharing site, a visual element is inserted into the video. The visual elements move and change as defined in the stored metadata. In this way, advertisements can be inserted into on-demand video such as video from a video sharing website.