A Semantic Space Partitioning Approach to Virtual Camera Composition
Marc Christie, Jean‐Marie Normand · Computer Graphics Forum · 2005
Positioning a virtual camera in a 3D virtual environment is generally a non-intuitive task when using a 2D input device such as a mouse. The user has a mental representation of the result in terms of what he wants to see on the screen, and has to apply a mental inversion process to determine the location, orientation and field of view parameters of the camera. This task is generally achieved through a tedious and time-consuming process requiring a succession of "place the camera" and "check the result" operations. Current 3D modelers surprisingly lack integration of tools to assist the user in this task, despite the fact that cinema, in more than a hundred years, has provided a rich grammar that allows a director to unambiguously describe shots. Modelers are based on complex mathematical notions (spline curves, velocity graphs) more or less hidden by high-level manipulators. Manipulators allow positioning and animating the camera, but lack correlation with well established cinematographic notions relative to camera composition (object framing, distance shot specification, relative viewing angles, occlusions). In this paper we propose a new approach to virtual camera composition that fully relies on this grammar, relieves the user from low-level parameter manipulation and offers him classes of possible solutions w.r.t. current cinematographic notions. In related literature, numerous approaches have utilized cinematographic properties such as subject size and location within the frame to assist users in camera composition and camera planning. J. Blinn [Bli88] propose a vector algebra-based solution to pin two objects at given locations on the screen. Gleicher and Witkin [GW92] offer means to control 2D points directly on the display screen through differential manipulation techniques instead of controlling the camera parameters. Blinn's algebraic method has laid the groundwork for cinematographic idiom-based approaches, such as Christianson et al.'s compiler for the Declarative Camera Control Language (DCCL) [CAH*96] or He's et al.'s Virtual Cinematographer [HCS96]. These approaches however suffer from the point representation of the objects that doesn't capture the occlusion properties and thus avoids one of the main problems in camera planning, namely occlusion. Moreover the "point-like" representation cannot take into account the real geometry of the scene. Camera composition and camera planning can be viewed as constrained optimization problems in which the properties of the shot are expressed as numerical constraints on the camera variables (respectively the camera's path variables) and a broad range of solving procedures is available to compute solutions. The solvers differ in the way to manage over-constrained and under-constrained cases, in their complete or incomplete search capacities, in local minima management and possible optimization processes (generally finding the best solution w.r.t. an objective function). In their CAMDROID system for automated camera planning [DZ95], Drucker et al. use an existing numerical constraint solver package (CFSQP) and have to compile the shot specifications in the input script used by this library. Unfortunately, the solving process is sensitive to the initial configuration and is subject to local minima failures. Bares et al. use a partial constraint satisfaction system named CONSTRAINTCAM [BGL98] in order to provide alternate solutions when constraints cannot be completely satisfied. This solution is based on a limited subset of cinematographic properties (viewing angle, viewing distance and occlusion avoidance), which limits the procedure to small problems. P. Olivier et al.[OHPL99] propose a rich set of properties for composition purposes. The authors have developed the CAMPLAN system [HO00] that numerically solves the optimization problem via a metaheuristic search (genetic algorithms) method. The main shortcomings of this purely optimization-based technique is that the CAMPLAN genetic algorithm produces solutions in widely varying amounts of time and is also subject to the initial population of solutions. Gooch et al.[GRMS01] also use optimization procedures in order to produce images fitting artistic composition criterion like rules of thirds and fifths and the notion of canonical viewpoint (viewpoint leading to better identification of an object). The CSP (Constraint Satisfaction Problem) framework has proven to succeed in some camera composition and motion planning approaches. In [BMBT00] Bares et al. propose a heuristic-based complete search algorithm. The process is applied inside promising 3D areas computed through simple geometric intersections. Although efficient, the approach avoids problems related to multiple solutions. Unlike Bares et al. who utilize partial constraint satisfaction through cost functions, Jardillier & Languénou use pure interval methods in The Virtual Cameraman[JL98] to compute camera paths which yield sequences of images fulfilling temporally indexed image properties. This idea has been improved by Christie et al. in [CLG02]. Unfortunately, the benefits of interval-based techniques that guarantee the fulfillment of the properties during the whole sequence are counterbalanced by the computational effort required, and the absence of any mechanism for constraint relaxation. However, whenever the method fails, the user has a guarantee that there are no solutions to his problem (due to completeness of interval-based approaches). Some approaches combine constraints and optimization. One of these was presented by J. Pickering [Pic02] and is closely related to our work. In this solving method, the constraints are used to create feasible regions of space that will serve as bounds for an optimization procedure. The search space is subdivided by a "shadow-volumes" algorithm based on the properties of the image, and the feasible regions are then discretized and stored in an octree structure. Each node of the octree is then used as a starting point for a genetic algorithm that tries to find a solution to the problem. The main shortcomings of this approach lay in the computational effort required to create the octree, and the fact that multiple distinct solutions are ignored. Most of the methods we mention rely upon optimization processes to compute satisfactory camera placements and therefore lead to a unique solution closely related to the objective function. However, the description of a cinematic shot can possibly yield different visual solutions. Therefore, in computing the set of semantically distinct solutions w.r.t. cinematographic properties, one provides the user meaningful results. Figure 1 presents a top view of a simple scene containing three objects A, B and C. Whenever the user describes a shot in which he constrains A and B respectively to lay on the left and on the right of the screen, it clearly yields three possible classes of camera configurations: area (1) object C is on the left of A and B on the screen, (2) object C is between A and B, and (3) object C is on the right of A and B. Moreover, when considering possible occlusions, two classes can be added (4) A occludes C and (5) B occludes C. In such cases, classical optimization and incomplete CSP-based approaches fail in that a unique solution [DZ95,OHPL99,Pic02], or a reduced subset [JL98,CLG02] of solutions is proposed, whereas all classes of solutions should be equally considered. These approaches actually lose the semantics of the problem while relying upon pure numerical approaches. Once a solution is computed, no further information on its characteristics or differences with other possible solutions is provided. Certainly, any classification process can be provided afterhand, but requires an important computational effort. Possible distinct areas for viewing a couple of objects A and B (resp. on the left and right of the screen) w.r.t. to a third object C. In this paper, we propose to integrate a semantic dimension in the solving and interaction processes to assist the user in his camera placement tasks. We follow a threefold declarative approach: describe the desired solution with a set of cinematographic-based properties, compute distinct classes of solutions satisfying the description with related cinematographic properties, explore and interact with the classes of possible solutions. In the description phase, as in previous approaches [OHPL99,HO00,JL98,DZ95], a high-level grammar is offered including composition properties (framing objects on screen surface, relative object orientation and size) and shot properties (close shot, establishing shot, low and high angle). The geometry of the scene (locations and orientation of objects) is considered as an input provided by the user. In the computational phase, two processes are combined. The first process partitions the search space according to cinematographic properties (e.g. area such that A occludes B on the screen) and builds the intersection of the space partitions. The second process computes a nice representative of each possible class of solutions via a continuous domain implementation of a local search metaheuristic algorithm. Finally, in a third phase, the user navigates in the possible solution sets and interacts with the semantic information provided in each area. This paper concentrates on the first two phases and offers solid foundations for high-level interactions with the user. This paper is organized as follows: Section 2 introduces our semantic space partitioning approach to virtual camera composition, Section 3 details the numerical solving process. The exploitation of the semantic volumes is presented in Section 4 and relevant results are then presented in Section 5. Finally Section 6 discusses future research directions and concludes. Our approach to virtual camera compostion (VCC) is based on the primary idea of Binary Space Partition (BSP) and can be considered as an extension of visual aspects[KvD79] and closely related works such as viewpoint space partitioning[PD90] in the field of object recognition. The idea behind visual aspects is to gather all the viewpoints of a single polyhedron that share similar topological characteristics on the image. A change of appearance of the polyhedron with changing viewpoint, gives rise to boundaries in the search space. Computing all the boundaries enables the construction of regions of constant aspect, namely viewpoint space partitions. In this paper, we propose an extension of viewpoint space partitions to multiple objects and replace the topological characteristics of a polyhedron by cinematographic properties such as occlusions, relative viewing angles, distance shots and relative object locations. We introduce the notion of semantic volume as a volume of possible camera locations that give rise to qualitatively equivalent shots w.r.t. to cinematographic properties, i.e. semantically equivalent shots. Each volume is characterized by a set of semantic tags issued from film grammar [Ari76] and each tag is associated to a satisfied property in the volume. Tags are either related to a single object such as viewing angle, or to a couple of objects such as occlusion and relative image location. Therefore, the entire space of possible camera locations is thoroughly partitioned for each object, and each couple of objects. We then derive from the user's description the subset of volumes to be considered and intersect them. This process leads to a set of non-connected regions of which each represents a different class of solutions in terms of visual aspect. The computation of semantic volumes can be formalized as follows. We define the geometric filtering operator Gƒ that inputs a property p and provides a semantic volume sv, which is defined by sv=〈S, V〉 where S is a conjunction of semantic tags (e.g. LeftOf(A) ΛMediumShotOn(B) ΛOccludes(A,B) Λ…) and V is a subset of possible camera locations in ℜ3. Every camera location inside sv possibly satisfies the property p, whereas every camera location outside sv certainly violates p. Possible camera orientations are to be further computed by the numerical process (see Section 3). The filtering operator is complete in that it does not lose any correct camera locations. The operator Gƒ computes (possibly) non-connected volumes by pruning the space of most of the inconsistent camera locations w.r.t. p and associates a semantic tag to the resulting volumes. For example, the user description "A occludes B" (see Fig. 5) leads to a cone-shaped volume V coupled with the semantic tag Occlusion (B,A). Occlusion cones computation (both partial and total occlusions). The following subsections present how the filtering operator Gf provides the semantic volumes related to each property. Below, we consider that the camera's roll degree of freedom (i.e. around the look-at vector) is restricted to interval , and the tilt angle is confined in (no upside-down cameras). Camera compositions seldom break these conventions. The projection property is based on the notion of scale shots in cinematography (cf.Fig 2). It allows the artist to specify a viewing shot for an object. There are basically six different kinds of shots : the Extreme Close-Up, the Close-Up, the Medium Close-Up, the Medium Long Shot (or Plan Américain), the Long Shot, the Extreme Long Shot. Related semantic tags reflect all six kinds of shots (ExtremeCloseUp(Object) to ExtremeLongShot(Object)). The six distances between the camera and a character according to Arijon [Ari76]. The underlying semantic volume is computed given the position of an object and a cinematographic scale shot specified by the user. One can deduce an optimal size corresponding to each scale shot presented in Figure 2. The object's bounding sphere and desired area in the frame are used to determine the range of camera distances. In order to add some flexibility to the solving system, we compute an interval range related to this optimal value by subtracting and adding an epsilon to it (see [BMBT00]). The minimum and maximum bounds of the interval correspond to two distances defining the inner and outer radiuses of an hollow sphere that includes the set of consistent positions for the camera (cf.Fig. 3). Distance is trivially computed by the following equation: Semantic volumes leading to characteristics shots. The orientation property lets the virtual cinematographer specify the viewing angle required to shoot an object or a character. A common set of 8 viewing angles is offered (e.g. relative to object A, there are IsLeftProfileOf(A), IsRightProfileOf(A), IsInFrontOf(A), IsInBackOf(A), IsThreeQuaterFrontLeft(A) up to IsThreeQuaterBackRight(A)) and each can be composed with high and low relative angles IsHighAngle(A) and IsLowAngle(A). Computing orientation semantic volumes consists in building a prism-shaped volume of possible camera locations, w.r.t. the vector to consider (front, back, left, …). Once again, a variation with the optimal orientation is accepted in order to avoid being too restrictive (cf.Fig. 4). Four common relative viewing angles and related semantic tags. The occlusion property gives the user the opportunity to specify some visibility constraints between two objects of the scene. The cinematographer can characterize a total occlusion of an object by another, a partial occlusion or an absence of occlusion between two objects. A partial occlusion occurs when a part of an object's projection overlaps some part of the second object's projection. The semantic volumes induced by an occlusion property are computed given characteristic cones defined with respect to the positions of the two objects involved in the occlusionproperty [DDP02]. The inside bounds of the cones define the volumes of partial occlusion. The outside bounds of the cones define the volumes where no possible occlusion can occur (cf.Fig. 5). The framing property allows the virtual cinematographer to constrain an object in a given frame inside, partially inside, or outside the screen space. This expressive property defines the relative locations and sizes of objects on the screen. It constrains altogether the distance shot and the camera locations and orientations. Moreover, total or partial occlusions can be derived from overlapping frames, and conversely non-occlusions can be derived from the absence of overlap (cf.Fig. 6and 8). A non-overlapping description constraining three objects. An overlapping description constraining three objects with an overlap. The computation and characterization of the semantic volumes related to this property depend on the number of framing properties defined by the user and their relative location on the screen. We two (1) whenever a single frame is the framing property will like a projection the size of the frame and the size of the object in the scene lead to the computation of a volume that limits the all possible camera locations around the object are possible w.r.t. this (2) the user has specified two or more a is to be for every couple of objects in order to The of all the distinct frame is not provided we propose a two leading to different semantic volumes considering overlapping and non-overlapping 8 and that the semantic volumes computed at the of the framing will the between the on the screen (e.g. object A is left of but not the locations of the objects in the the numerical process will compute camera orientations to locations in the Figure 6 a user input related to a non-overlapping Figure provides a 2D of the scene with locations of objects A, B and C. For the representation is two but all the computation occurs in The first semantic volume is as 1 A and and with possible camera location in this area can lead to a shot in which the object A on the left of B. as 1 and 2 not overlap on the screen, no occlusion should occur between A and B. 2 and 3 are by computing the occlusion cones [DDP02]. tags are where B A and when A B. the area of Figure for the possible camera locations satisfying the user's description 2D of the semantic volumes related to couple , when respectively on the left and right of the screen. This process is for every couple of objects in the screen, Figure 8 an overlapping the overlapping is partial and areas and are not considered as possible camera locations and are with or the area between A and B is not considered as possible 3 does not provide any overlapping configuration and is with in the areas containing possible camera locations are at the left and right of Figure distinct volumes are the camera is in the right solution B will than A in the shot, whereas it is to the left, A will than B. 2D of semantic volumes related to overlapping on objects A and B the further semantic partitioning and characterization is offered by considering and The of the whole set of distinct frame follow the process. positioning properties allow to specify some relative positions between objects on the screen, one can that one wants to see the object A on the right of B, B, These relative placements describe the of objects being to within a visual composition as a conjunction of properties is by a intersection of the semantic volumes. a set of properties provided by the user results in the following computation : The intersection process lead to an a unique volume or to a set of non-connected volumes. In order to the intersection of 3D we propose to rely on of the semantic volumes than pure geometric Each is the of a field the function. For each point of the the of the are A 3D volume is when a value such that provides with the following (1) of volumes by the (2) in that we avoid or (3) to a point in the via a and simple Our implementation relies upon the that provides and means to create by defining for each object and with the bounding the whole 3D scene. For example, the possible camera locations the scale shots distances between the camera and an object (cf.Fig. are via the volumes the occlusion property are defined as cones the objects (see Fig. thus the regions of total or partial The to the use of in the computational cost of our approach requires a unique at the in order to determine the number of non-connected The cost of the is by the number of and for our the computation of the non-connected with The of the space partitioning approach consists in a semantic volume V containing possible camera locations. the numerical computes a nice representative of each volume in This consists in in V a consistent camera configuration orientation and that satisfies the framing properties and that each property corresponding to a semantic tag of S a cost function). The problem therefore to determine a of variables such that : where for the cost associated to property and where is the framing property given by the user. optimization and constrained optimization techniques a objective (e.g. In order to manage algebraic constraints such as and algebraic constraints such as we rely on The underlying of the framework can be in 1 presents our The algorithm relies on the of the search space a semantic starting from an initial and the around the current The a set of in V within a around the current It introduces the notions of and The allows on promising regions of the search space by the size the being in local no has been for a while a of the initial is to allow a of the search space. The procedure is by the maximum number of and and the number of at each of the function. each the best in terms of constraint satisfaction and cost the new current the user's description not lead to a solution framing is to respect as objects have been in the 3D we propose to integrate the satisfaction of the framing constraints in the cost function. Therefore, is given by : The cost to the respect of a property considering the orientation property of for example, the best are vector and such that the camera's orientation is to This local search technique be used to compute solutions of camera composition problems to Olivier et al.'s However, the process the solver in promising regions and the of the associated to each property. The constraint is by a simple of the related to a semantic the configuration in V and conversely is outside The main of this paper is to offer a semantic for and with the volumes. We two possible on the computed semantic volumes and on the whole 3D scene the computed volumes. For a given each computed volume provided by the geometric solver some related to the satisfaction of the properties. the characterization of each distinct volume can be semantically according to properties the user has not For example, a semantic volume sv is characterized by the relative location some further characterization of sv can be computed by considering the orientation properties related to A and B (e.g. a the user can two semantically volumes and the description and for the differences between them. This to compute all tags in and in that not each object and couple of objects in the scene their semantic it is to on a computed volume sv any possible object or property. The to computing a new geometric intersection and the number of computed by For example, in 2 of Section one can there a possible camera location such that A, B and C can be viewed from the relative angle : where sv is the computed semantic volume and Gf the geometric that computes the semantic volume related to the property is the is all possible volumes the a computed volume w.r.t. a property a similar For example, the of a volume sv into all the possible shot distances relative to an object A can be expressed as : The set of properties in Section 2 is provided via a as an extension to the It is for the and the of the solutions given to the user. Moreover it the into existing by the of and 2 the related to most properties. The framing property as parameters the of the left and top right of the frame containing the object. less than or more than 1 frame objects of the screen. The orientation property requires an object and a viewing angle presented in Section The projection property an object and a shot class 2). Occlusion properties associates with and the occlusion or our the classical shot two and then a framing shot with possible classes of solutions. The classical shot is when a between two or more and consists in the camera behind one while framing the Figure the related semantic volume and a result is presented in Figure The shot is given by the following declarative script w.r.t. and view of the search space computed by the shot and of the volume A result of the The geometry of the scene is composed of objects (see Fig. The user objects A, B and C respectively in the left, and right of the screen, and constrains and to to the screen any occlusion. Some results are presented in Figure three shots the users description and different classes of solutions. view of the shot and related to possible camera locations with further semantic information related to orientations of A , B and C shots associated to the framing 3 presents the time during the and numerical in computation of one representative of each semantic volume. is directly related to the of the are and 1 and 2 respectively and is the time in the local search with and provide a Although the total time to compute all important time representative is around which is for interaction purposes. The semantic approach offers the following the cinematographic properties provide semantic volumes containing the possible solutions of the problem through a geometric process that areas of the The computation of the boundaries relies on and avoids volume Whenever the intersection process leads to an there is a guarantee of in the user's The numerical process offers a representative of each volume at low computational The use of as object boundaries in the occlusion computation can be present the of being for bounding objects that are one or for This lead to regions of the search space that possibly lead to correct shots during occlusions and results can be through but to integrate in our can be by computing volumes provided an representation of such volumes is The computational cost of our approach is related to the number of objects in the scene and to the user's Most time is in the computation of the number of non-connected volumes which is related to the of the function. We to this process by computing the intersection of of each semantic volume and then the on this Finally, the approach to is our main objective being to characterize possible camera positions for a of time the computation of camera A extension is volumes. the extension is not and the main in with the time criterion in each volume. in this paper we have presented an approach to virtual camera composition that classes of distinct provides means to characterize and computes the notion of visual we the notion of Semantic as a set of possible camera locations that share a set of cinematographic results the of our approach and in and to virtual camera