CS888 Project : 2.5 Silhouette World.


Based on Tolba, Dorsey and McMillan "Projective Drawing System", I created a 3D world of silhouettes projected on a sphere. It allows fast view of the space and easy manipulation of the objects in a 3D looking world.

Basic Idea

Tolba's method used 2D stroke drawings that are projected on a sphere, using the effectiveness of the 2D projective points representation. 2D strokes are given a 3D appearance by being projected on a unit sphere with the view point fixed at the center of it. This representation permits reprojection on the image plane that gives an illusion of 3D world transformation when the view at the center of the sphere is rotated or zoomed. However, the stroke data extracted from 2D images does not contain depth information. 3D information is essential to extend the view navigation to translation transformation. My goal was to produce more view interactivity at the cost of extra computation when necessary. For this reason, I decided to reproduce the projective mapping to the unit sphere, but based on 3D data in order to extend the capabilities of view navigation and object orientation. I, therefore, used as initial data, 3D mesh objects, which are displayed as a simplified silhouette representation. With this data representation, I was able to perform view translation and also change rotation of the objects on themselves (change in orientation).

Implementation Details

1. World

The spherical world is displayed as a 3D wire-frame half-sphere cutted by a blended plane to give a good representation that the view is in a middle of a spherical dome. The transparency of the plane makes the positioning of the objects on the ground a less demanding task.

2. Three Projections

  1. 3D Mesh Object to 3D Silhouette
    2. A 3D curve silhouette is extracted from the view position, center of the sphere, and the 3D object, located at position (x,y,z), and oriented with an angle theta around the y-axis.

    Basic Object Space Silhouette
    The objects are loaded at a certain distance of the view, according to object's dimension. A silhouette is computed based of Hertzmann Notes on Object Space Silhouette Detection. All mesh triangles are traversed to find the ones that contain silhouette edges. The silhouette consists of all edges that connect back-facing (invisible) triangle to front-facing (possibly visible) triangles. The silhouette consists of all surface points with surface normal perpendicular to the view vector. In my implementation, all mesh triangles are traversed to find the silhouette edges.

    Visible Silhouette, hidden-edges removal
    The basic object space silhouette algorithm includes silhouette edges, that may be hidden because they are behind some other part of the object. Some visibility tests need to be done. An ID image, as described in the WYSIWYG NPR paper, is used. On an image, the initial silhouette edges are drawn with different colour identifying them; then on top of it, all mesh triangles are drawn with the background colour using OpenGL polygons offset, to push them backwards. The triangles will cover the edges that are hidden. Finally, the image is read to identify the edges that remain, and therefore constitute the visible silhouette. This computation is expensive, since the image needs to be read.



  2. 3D Silhouette Projection on the Sphere
    3. From the 3D silhouette points in space and the view location, a silhouette 3D curve is mapped to the sphere. The 3D silhouette edges are projected on the sphere with ray-surface intersection between the ray from the center of sphere to the 3D edges points and the sphere surface.



  3. Image Projection
    4. The 3D silhouette curve on the sphere is projected on the image plane by perspective projection using OpenGL.


Object Transformation

Object transformation modifies only the object that has been selected for transformation. Translation and scaling do not change the set of silhouette edges whereas rotation of the object does.

  • Translation
    • The object can simulate translation on the plane by recomputing the 3D silhouette projection on the sphere with the position of the silhouette rotated around the center of the sphere. The blue dot on the pictures below is the location of the object that has rotated around the sphere y-axis to translate the car on the plane from right to left (it is really far because the mesh data uses a big scale). Then to get the final image, 2D OpenGL projection needs to be done.
    Translate can be : right/left, corresponding to a rotation around the z-axis of the sphere; or up/down, corresponding to a rotation around the x-axis.



  • Scale
    • Object can be scaled by moving the 3D object position closer or farther away from the center of the sphere. Then, to get the scale, the 3D set of silhouette edges needs to be reprojected on the sphere, followed by the projection of the curve on the sphere onto the image plane. Notice on the pictures the small blue point (position of 3D object in 3D space) getting closer from the sphere center (represented by a red dot).



  • Orientation
    • Change in orientation of the object, i.e. rotation around the object y-axis necessitates the recomputation of the 3D silhouette with a rotation of the mesh points. Then, both, the 3D silhouette projection on the sphere and the projection to a 2D image are evaluated. See how the position of the 3D object, i.e. small point stays at the same position. This transformation, since it requires all 3 projections to be performed, is costly.

    View Transformation

    Modes

    Results

    Speed Performance

    This table was created with only one model loaded: the cow object. The models contain 5804 triangles which represent 17412 edges to traverse.
    The values in the table represent the displayed frame rate per second for all transformations. It is important to notice that it is model size dependent. There are 2 silhouette modes : one with all silhouette edges (basic silhouette), and one with only the visible silhouette edges (visible silhouette). The second one, when re-computed, is costly because an ID image needs to be created and then read. The visible silhouette has less edges than the basic silhouette. The set of edges silhouette depends on the object orientation and view position, but in average the ratio between the number of basic edges silhouette and the number of visible edges silhouette is in the order of two to one (1000 edges against 500).

    Transformation

    Basic Silhouette

    Visible Silhouette

    View Zooming

    1300-1400

    1800-1900

    View Rotation

    1400-1500

    1900-2000

    View Translation

    30-40

    2-5

    Object Scaling

    200-230

    240-250

    Object Translating

    200-230

    230-250

    Object Orientation

    25-30

    2-3


    As in Tolba's paper, the view rotation and zooming can be executed at minimum cost. Only the image projection needs to be recomputed since the view point is fixed and the silhouettes do not change at all. The frame rate is above 1200 frame/sec. The display rate for the visible silhouette is even faster because it has half less silhouette edges to project from the sphere to the final image plane.

    Object scaling and translating are also quite fast, because only the set of detected silhouette edges in 3D space needs to be reprojected onto the sphere and then on the image plane. The position in 3D space of the object changes : rotate around sphere center (translating object) or go closer or farther of the center of the sphere (scaling object). Therefore, only the matrix applied on the silhouette edges on 3D space changed. The set of silhouette edges do not change, so do not need to be re-evaluated. Again, the visible silhouette in this case has a better speed performance, because there are less edges to remap to the sphere.

    View translation and change in object orientation are the two most costly operations. The set of silhouette edges needs to be re-evaluated. In this case, it is less costly for the simple silhouette because it does not requires writing the ID image and then reading from it to find the visible edges, which is quite expensive.

    Quality

    The visible silhouette is an improvement in general over the basic silhouette, it gives more clues about how the object is oriented and what parts are in front or behind. However, its computation is complex and sometimes gives poor silhouette from certain views. This limitation is due to the algorithm itself that is advantageous if the object is seen from an appropriate point of view and render at a big scale. The polygon offset of OpenGL used to evaluate the visible edges responds negatively to floating point precision of the transformations that are applied to the object, mostly visible when the object is scaled down. The images below show the different qualities of visible silhouettes; sometimes the visible silhouette rendering is simply improved by moving back to the view at the center of the sphere or closer to the object.



    Conclusion

    The performance gain that Tolba's paper emphasizes for fast view rotation and zooming was maintained. It requires a minimum of recomputation in order to investigate a 2.5 dimensional world from a fixed view location. Tolba went from 2D drawing strokes to 2.5D strokes projected on a sphere. Tolba sketches technique enables the used of loaded drawings created on a tablet. Moreover, displayed images can be updated with more strokes using the tablet. Its method integrates together 2D sketches in a 3D world. It is quite powerful to create architectural environment that need to be looked around. I choose a different technique. I also focused on sketches as output primitive by using silhouettes but I desired 3D information to extend the world and object manipulations. The use of 3D object meshes gave satisfactory results in term of speed and quality. The extraction of set of silhouette edges produces sensible speed rendering outcomes under all transformations, as well as good quality images in most cases. The work could be improved by finding a better algorithm to create the visible silhouette that would guarantee a perfect silhouette on all view positions, orientations and object sizes. Another issue of the visible silhouette algorithm is its low speed. The use of the GPU and textures could significantly improve the speed of detecting the visible silhouette. It was an interesting and full-filling project to build and think about. Some generalization on projective geometry could be derived and included as a more general transformation from 3D silhouette to the image plane. Tolba's method and my extensions were validated by the creating of satisfactory results for the goals set. The gain in speed that my method achieved proves the method to be worth it, especially for a lot of looking around and less of moving around.

    Acknowledgements



    References