Research Abstracts - 2007

Figures

Figure 1: Visual representation of 3 rooms on a 2D floor plan (a bird-eye view)	Figure 2: Bird-eye view of a doorway between two rooms. This figure shows a shared edges conflict. Vertices 1 and 2 are in same place.
Figure 3: Closeness property. Edges 3 and 4 are counterparts of each other. Edges 3 and 4 form an implicit pair. Edge 5 and 6 is another pair. These pairs are implicit meaning that they are not represented this way in the 3D object model. This figure just illustrates the concept of closeness, that every edge has its equivalent counterpart. The rightmost segment is broken down into 3 edges to achieve the complete nature of the model.	Figure 4: The new representation of edge. The edge in the figure is composed of two semi-edges pointed in opposite direction (the direction of drawing them). In the case of an edge shared between two spaces (rooms), the left 'semi-edge' would belong to room M, and right “semi-edge” would belong to room N. We have achieved the storage of edge object in two different space (room) objects.
Figure 5: Instead of representing a door with portal as a 8-cornered polygonal surface, break the wall up into 3 quadrilaterals. This way portal 'semi-edges' preserve the uniqueness property with their respective adjacent 'semi-edges'

Introduction

There have been studies done in how to represent 3D models solidly and consistently [1]. In this proposal we will explore how to represent 3D building models such that they are consistent, complete, and watertight. Consistent means that every room is represented as a collection of quadrilaterals, and watertight means that there should be no cracks or places where walls of the room do not meet each other in corners. Imagine filling the room up with water. The watertight model will ensure that there is no place in the room that the water can leak through. Completeness means absence of gaps in the representation of different objects in the model.

There are many ways of representing 3D graphical data. In our case, we will deal with vertices, edges, and surfaces. Every quadrilateral surface is represented by 4 vertices and 4 edges. An edge is a segment that connects the two vertices in 3D space. In computer graphics, the order in which the vertices are drawn to define a surface is very important. If a surface was defined by vertices that were placed in counterclockwise order, only one side of the surface will be seen, but not the other. Reversing that order will reverse the visibility, and make the other side visible and the first one invisible. In the case of the surfaces that define the walls in the room, defining the points in certain sequence will make the wall visible from, let’s say, inside of the room, but not from outside the room. The outside side of the wall of the room need not be visible for reasons that I will describe below.

In our model, every room is represented as a space. The space has a set of vertices, edges, and walls (surfaces) that define the dimensions and representation of the room in the geometric graphical space. In our building model, many rooms are adjacent to each other. According to Figure 1, the 2D floor plan is broken into separate rooms, each room being separated by a double-layered wall. The double-layered means that the wall between two spaces is defined by two surfaces which coexist with each other. One wall faces room A, and another wall faces room B. There is no need to make the other side visible because it is in the space that is inaccessible to people. This is why we chose to draw only one side of the wall. The walls should not be visible from within the grey area in figure 1 because that area is obstructed by surrounding walls.

Some spaces (space and rooms are used interchangeably in this proposal) can be connected by doorways – we call them portals. In Figure 1 above, rooms A and B, and rooms B and C open into each other. In 3D space model, portals are openings in the walls. Because walls have gaps in them, the internal area between two surfaces that define the wall is exposed and the watertight principle of 3D model is violated. One way to fix this is to draw additional surfaces that define a doorframe and would close any gaps in the portal and make the grey area in figure 1 not visible.

In our 3D model, every geometric object is unique and has no copies in the same location. Every wall is closed. Every edge that defines a wall has its parallel counterpart (of same orientation and length) on the other side of the wall. For example, in figure 1, segment 1 and 2 are opposite each other. Segment 4 is the counterpart of segment 3. Figure 3 below illustrates this concept.

Problem & Approach

The main problem confronting us is determining how to represent the edges and portals that are shared between two adjacent rooms. How do we deal with edges and doorframe that lie between two rooms (at the doorway)? To which space should they belong? Figure 2 illustrates this problem graphically from the 2D standpoint. The circles 1-4 are edges that run up and down as seen from the bird-eye view, or in 2D space model. Edge 1 and 2 are identical copies of each other. The same applies to edges 3 and 4. In our 3D model every geometric shape belongs to a distinct space. No identical copies of shapes are allowed. So we have to constrain our problem to a single representation of the edge. In figure 2, edges 1 and 2 become the same edge. Edges 3 and 4 are the same edge. Where do we place the two edges 1&2 and 3&4? Should room X or room Y claim the ownership? I am proposing that both rooms claim the ownership of the shared edge. This is going to be done by defining an edge as a pair of two segments running in opposite direction.

This confirms the uniqueness property of the edge. Instead of having an edge that is shared by two walls (in a corner) being drawn in only one direction, we can represent a single edge as two semi-edges, each drawn in the opposite direction. This representation works not only in the case of edges between two rooms, but also in the case of edges within a room. Vertical edges that form corners of the room are shared between walls that meet at that edge. Both walls are drawn in the same clockwise direction, and segments of the walls that are adjacent to each other at the edge, form “semi-edges” (see figure 4). The drawing pattern of the walls is not disturbed here (i.e., there are no cases in which the walls might have to be drawn in counterclockwise direction just to maintain the uniqueness property of edges) It turns out that this representation of edges closely mirrors the paired edges of figure 3. For every edge there is another edge on the other side of the wall that has same length and orientation. The same principle dictates that every semi-edge must have an equal and opposite semi-edge in order for consistency and completeness of the geometric model to hold.

We would like to improve the representation of shared edges and portals and geometric representation of walls with portals and windows in them. In an effort to keep geometric shapes in our 3D model as simple as possible, we would like to deal only with quadrilaterals. Other polygons should be out of question because the bottom edge of the wall with portal (doorway) in it has to be broken down into 3 segments in order to maintain the closeness property. For example, where the bottom of the doorframe meets the hallway floor, the semi-edge belonging to the doorframe must have a counterpart edge belonging to the floor of the hallway that is equal in size. We should never encounter the case where the whole length of the hallway meets the short edge defining the bottom of the doorframe. The hallway edge has to be broken down to preserve the edge uniqueness property. Because of this property, the wall has to be broken down into quadrilateral sub-walls. A wall with a single portal has to be broken into three quadrilaterals instead of a single polygonal wall that is defined by 8 vertices. (see Figure 5) Door frames and portals should also belong to one of the two adjacent spaces, but not to both. We are going to use the direction of the door or the implicit properties of the portal to determine which space the portal and geometric information about the doorframe should belong to.

References:

[1] Murali T. M.and Funkhouser T. A. Consistent Solid and Boundary Representations from Arbitrary Polygonal Data. 3D solid Model Reconstruction