Communications of the ACM

they do not demand accuracy. The profile dimensions are guided by the object’s outlines. While sweeping, the 3D extent of the part is also defined by snapping to these outlines. To compensate for perspective distortion, during this process, the camera’s angle of view is estimated. Therefore, the part need only be sketched quickly and casually by the user. Figure 1c shows the result of sweeping along the tubes of the menorah (more examples could be seen in an online video at https://vimeo.com/148236679). We elaborate on the

3-Sweep operation in Section 4.

As more model parts are added, geometric relationships between them serve (i) to assist in disambiguating and defining the depth dimension and (ii) to optimize the positioning of the parts. These geometric relationships include parallelism, orthogonality, collinearity, and coplanarity. We use optimization to satisfy these geo-semantic constraints, while taking into account the snapping of the 3D geometry to the object’s outlines and the user’s sweeping input. A complete model with geo-semantic relationships is shown in Figure 1d. These geo-semantic relationships not only help define the 3D model, but become part of the 3D representation of the model, allowing smart editing of the 3D model later, as demonstrated in Figure 1f and in other figures in the paper.

Our interface also supports several operations for more effective modeling. For example, the user can copy and paste similar parts to other positions on the image. Although many geo-semantic constraints are automatically inferred, the user can also manually specify constraints between selected parts, constrain the parts to have uniform or linearly changing radii etc.

4. SINGLE PRIMITIVE FITTING

In this section, we first describe the 3-Sweep technique for creating one generalized cylinder. Simpler primitives such as spheroids or simple cubes are also supported by direct modeling in our system.

Preprocessing. In a preprocessing stage, we extract
image edges and build candidate object outlines. We adopt
a method for hierarchical edge feature extraction based on
spectral clustering. 2 We then apply a technique to link the
detected edge pixels into continuous point sequences, 7 each
shown in a different color in Figure 1b. An edge orientation
computed over a 5 × 5 neighborhood is associated with each
edge pixel.
Profile definition. In the first stage, the user draws the 2D
profile of the generalized cylinder, usually at one end of the
shape. This is illustrated in Figure 3, where black curves are
outlines detected in the input image. The task is to draw a
2D profile correctly oriented in 3D. This can be regarded as
positioning a disk in 3D by drawing its projection in 2D. To
simplify this task, we assume that the disk is a circle, thus
reducing the number of unknown parameters. Later, the cir-
cular disk can be warped into an elliptical disk based on the
3D reconstruction. The drawing of a circular disk is accom-
plished by drawing two straight lines S1S2 and S2S3 over the
image, as shown in Figure 3a (red and green arrows). The first
line defines the major diameter of the disk, and the second
line is then dragged to the end of the minor diameter. This
forms an ellipse in image space that matches the projection
of a circular disk: see the dark blue circle in Figure 3a. The
depth of the disk is set to 0. The normal direction and radius
of the disk are assigned according to the length and orienta-
tion of the two diameters of the elliptical projection.

Generalized cuboids are modeled in a similar way. The two strokes that define the profile of a cuboid follow the two edges of the base of the cuboid instead of the diameters of the disk, as shown by the red and green lines in the bottom row of Figure 2.

Sweeping. After completing the base profile, the user sweeps it along a curve that approximates the main axis of the 3D part. In general, this curve should be perpendicular to the profile of the 3D primitive (see blue arrow in Figure 3a). As the curve is drawn, copies of the profile are placed along the curve, and each of them is snapped to the object’s outline.

While sweeping, the axis curve is sampled in 2D image space at a uniform spacing of five pixels to produce 3D sample points A0, . . . , AN, that lie on one plane. At each sampled point Ai, a copy of the profile is created, centered around the curve. Its normal is aligned with the orientation of the curve at Ai, and its diameter is adjusted so that it’s projection on the image will fit the object’s outline. Together, the adjusted copies of the profile in 3D form a discrete set of slices along the generalized cylinder, as shown in Figure 3c.

At each point Ai, we first copy the profile from Ai− 1 and translate it to Ai. We then rotate it to take into account the bending of the curve. We then consider the two ends of the major axis (yellow points in Figure 3b) of the profile, denoted by pi0, pi1. For each contour point pij, j ∈ [0, 1] we cast a 2D ray from point Ai along the major axis, seeking an intersection with the object outline. Finding the correct intersection is somewhat challenging as the image may contain many edges in the vicinity of the new profile. The closest edge is not necessarily the correct one, for example, when hitting occluding edges. In other cases, the correct outline may be missing altogether. To deal with these cases, we first limit the search for an intersection to a fixed range, which limits the major axis of adjacent profiles not to vary by more than 20% in length. Secondly, we search for an intersecting edge that is not collinear to the ray ( creates an angle larger than p/4). Although this method cannot guarantee that it will find the correct intersections, the

Figure 3. Modeling a primitive by defining a 2D profile and sweeping it along the main axis of the object (a). The profile is copied along the centerline (b), and the copies are snapped to the image edges (c).