Method and system for minimizing earthwork volumes

A method and system provide the ability to design a surface. An existing triangular surface mesh representative of an existing surface is obtained. A modification to the mesh in compliance with design constraints is received. A volume level set or a volume minimization set, for the modified mesh, is obtained in Euclidean space. A volume subgradient set based on the volume level set, is obtained. A scalar is determined and used to scale heights between vertices of a triangle. A projection is computed and may be scaled. The projection may then be removed from the triangle's vertices. The removing changes the triangular surface mesh into a converged triangular surface mesh that minimizes an objective function. The objective function computes an absolute earthwork volume and/or an absolute value of a net volume representing the difference between a fill and cut of earthwork material.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to civil engineering road design, and in particular, to a method, apparatus, and article of manufacture for minimizing earthwork volume movement in a triangular surface mesh.

2. Description of the Related Art

(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)

A common representation of three dimensional objects in computer applications such as graphics and design, are triangular meshes. In many instances, individual or groups of triangles need to satisfy spatial constraints that are imposed either by observation from the real world, or by concrete design specifications for the objects. For example, in road/drainage pool/channel design, grade/slope changes must comply with local minima/maxima (e.g., a road slope must be lower than a slope maximum according to federal highway road standards). Thus, designers must consider as variety of surface maximum and minimum slope constraints, surface alignment constraints, as well as other surface slope requirements that are not only based on the real-world feature being designed (e.g., a difficulty of a golf course) but also essential for drainage and environmental impact.

Patent application Ser. No. 15/705,083 contains a method to find design solutions that satisfy these constraints, and that are optimal with respect to terrain smoothing or terrain smoothness. Further, patent application Ser. No. 15/705,083 provides further background information on the various problems arising in civil engineering design, triangular irregular networks (TIN), etc.

While spatial/other constraints must be satisfied, it is often desirable to simultaneously attempt to achieve one or more objectives. For example, while a slope constraint must be complied with, the designer may also have an objective of minimizing the earthwork volume (e.g., the costs associated with the volume of earthwork used in a project). Another desired objective may consist of attempting to balance the earthwork cut and fill (e.g., reusing the cut earthwork volume in another area where fill is needed). Prior art methods fail to provide the ability to utilize both constraints and objectives, or to simply attempt to comply with objectives when designing a surface consisting of a triangular surface mesh.

SUMMARY OF THE INVENTION

One or more embodiments of the invention provide a method and system for designing a surface such that the earthwork volume is minimized in the triangular mesh representing the surface. The method may be used as a proximity operator on one or many triangles in the triangular surface mesh. Further, embodiments of the invention may utilize a proximity operator to balance the cut and fill of earthwork volume. The result is the ability to minimize and/or balance earthwork volumes in the computer-aided design of surfaces for civil engineering in three dimensions.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Overview

Embodiments of the invention define a method that can be used as a proximity operator for an objective function that minimizes earthwork volumes, in conjunction with projections (or proximity operators) onto civil engineering constraints on triangular surface meshes, where the method and other proximity operators can be assigned different weights.

Additional embodiments define a method that can be used as a proximity operator for an objective function that minimizes the difference between cut and fill volumes, in conjunction with projections (or proximity operators) onto other civil engineering constraints on triangular surface meshes, where the method and other proximity operators can be assigned different weights.

Method Overview

Embodiments of the invention are based on proximity operators and projections, and the use of proximity operators and projections in iterative ways to find solutions for feasibility or optimization problems.

As used herein, a projection of a point onto a convex set is the shortest distance of that point to the set. For example, if a set is a plane in three dimensions, then the projection of a point onto that set is its shadow on the plane. If the point to be projected is already on the plane, than the projection is the point itself. Given multiple sets (e.g. multiple planes in three dimensions) and a starting point, iterative projection methods can be used to find a point in the intersection of all these sets that is closest from the starting point. These methods project iteratively onto the different sets. If the given sets are convex, then the iterative projections will converge to a solution.

Proximity Operator

In mathematical optimization, the proximity operator or proximal operator is an operator associated with a convex function ƒ from a vector space X to, and is defined by
Proxƒ(v)=argminx∈X(ƒ(x)+½∥x−v∥2).  (1)
Proximity operators may be used in optimization algorithms associated with non-differentiable optimization problems such as total variation denoising.

The proximity operator reduces to the operator that projects a point onto a convex set if ƒ(x) is the 0-∞ indicator function of that convex set. Hence, a proximity or proximal operator is a generalization of a projection.

In embodiments of the invention, we first show the volume function that we try to minimize in order to reduce earthwork. The volume function provides the volume that is generated, when one or more triangles are modified in a triangular mesh that represents a terrain surface.

In embodiments of the invention, a triangle is modified by changing the elevations of a one or more of its vertices by some heights. The set of heights for which the volume function returns one, is called the volume level set. The volume level set looks like a spheroid (seeFIGS. 3A and 3B).

In embodiments of the invention, the set of all subgradients of the volume function is called the volume subgradient set. The volume subgradient set looks like a football (seeFIGS. 4A and 4B).

A polyhedral upper approximation of the volume function results in a approximate volume level set that is shown for a triangle in a triangular surface mesh (seeFIGS. 5A and 5B).

The polyhedral upper approximation of the volume function can be thought of as a combination of boxes and pyramids inside the spheroid, that make it look like the spheroid. Embodiments of the invention also encompass modifications to the polyhedral upper approximation of the volume function that add finer boxes and pyramids, and/or approximate the spheroid in different ways.

The subgradient set of the polyhedral upper approximation of the volume function is shown for a triangle in a triangular surface mesh (seeFIGS. 6A and 6B). This set is also an outer approximation of the volume subgradient set or the football. In embodiments of the invention, it is referred to as the approximate set or set D.

The polyhedral outer approximation of the football can be thought of as a combination of boxes and pyramids around the football, that make it look like the football. Embodiments of the invention also encompass modifications to the polyhedral outer approximation that add finer boxes and pyramids, and/or approximate the football in different ways.

The proximity operator is then derived by finding the projections on the outer approximation of the volume subgradient set or the football.

The pseudo-code below provides for an implementation of the proximity operator in a computer program, which can then be used in combination with other implemented projections and proximity operators in an iterative way, in order to obtain an optimized solution for a civil engineering design for terrain grading.

Logical Flow

FIG. 1Aillustrates the logical flow for designing a surface based on an absolute earthwork volume in accordance with one or more embodiments of the invention.

At step102, an existing triangular surface mesh that is representative of an existing surface is obtained/acquired. The existing triangular surface mesh consists of a first triangle and one or more additional triangles connected by vertices and edges.

At step104, a modification to the first triangle is received. The modification is in compliance with one or more design constraints, and results in a modified first triangle.

At step106, a volume level set (in Euclidean space) for the modified first triangle is obtained. Such an obtaining may include obtaining an approximation to the volume level set.

At step108, a volume subgradient set is obtained (in Euclidean space) based on the volume level set. As part of obtaining the volume subgradient set step, an approximate volume subgradient set (in Euclidean space) may be determined/obtained. Such an approximate volume subgradient set step may outer approximate the volume subgradient set using a polyhedral function. Alternative, or in addition, the approximate volume subgradient set step may contain the volume subgradient set.

At step110, a scalar to reduce the distance is determined (from the area of the first triangle or the modified first triangle).

At step112, the scalar is applied by scaling heights between the vertices of the modified first triangle and the first triangle using the scalar.

At step114, a projection is computed. The projection is from one or more scaled heights of the vertices of the modified first triangle onto the volume subgradient set (in a first of one or more embodiments). Alternatively, the projection may be of one or more heights of the vertices of the modified first triangle onto the net volume minimization set. The projection includes a direction and a distance.

At step116, the scalar is applied (to the projection) and removed (from the vertices of the modified first triangle) to reduce the distance of the projection. The scalar application provides the following: (1) changes the triangular surface mesh into a converged triangular surface mesh; and (2) the converged triangular surface mesh minimizes one or more objective functions. In addition, in one or more embodiments, (one or more of) the objective functions computes an absolute earthwork volume between the first triangle on the existing surface and the modified first triangle on the converged triangular surface mesh (i.e., the minimization of objective function attempts to minimize earthwork volume).

In one or more embodiments, the scalar is based on user input, and the determination and application of the scalar includes computing a proximity operator based on the scalar.

In one or more embodiments, the objective function may be symmetric positively homogenous, as well as continuous and convex.

In alternative embodiments, (one or more) of the objective functions computes an absolute value of one or more net volumes. In such embodiments, each net volume (of the one or more net volumes) includes a difference between a fill and a cut of earthwork material resulting from modifying the existing triangular surface mesh into the converged triangular surface mesh (i.e., the objective function attempts to balance the cut and fill volumes).

FIG. 1Billustrates the logical flow for designing a surface based on net volume in accordance with one or more embodiments of the invention.

Steps102and104ofFIG. 1Aare similar to that of.FIG. 1A. In particular, at step102, an existing triangular surface mesh that is representative of an existing surface is obtained/acquired. The existing triangular surface mesh consists of a first triangle and one or more additional triangles connected by vertices and edges. At step104, a modification to the first triangle is received. The modification is in compliance with one or more design constraints, and results in a modified first triangle.

At step118, a net volume minimization set for the modified first triangle is obtained (in Euclidean space).

At step120, a projection is determined of the one or more heights of the vertices of the modified first triangle onto the net volume minimization set. The projection consists of a direction and a distance.

At step122, similar toFIG. 1Astep110, a scalar to reduce the distance is determined (e.g., from the area of the first triangle or the modified first triangle).

At step124, the scalar is applied to reduce the distance of the projection. The application of the scalar: (1) changes the triangular surface mesh into a converged triangular surface mesh; (2) the converged triangular surface mesh minimizes one or more objective functions; (3) at least one of the objective functions computes an absolute value of one or more net volumes; and (4) each net volume of the net volumes includes a difference between a fill and cut of earthwork material resulting from modifying the existing triangular surface mesh into the converged triangular surface mesh.

Similar to the steps ofFIG. 1A, inFIG. 1B, the scalar may be based on user input, and the determination and application of the scalar may include computing a proximity operator based on the scalar.

Further to the above, in one or more embodiments, the minimization of the objective functions may be based on a proximity operator as set forth in further detail herein.

To better understand the two implementations (minimizing earthwork volumes and minimizing the net volume (i.e., balancing cut and fill volumes), a more detailed description of the proximity operators and actions performed are provided below.

Notation

The notation herein is fairly standard and follows largely [1].denotes the set of real numbers. By “x:=y”, or equivalently “y=: x”, we mean that “x is defined by y”. The assignment operators are denoted by “←” and “→”. For a set I, |I| denotes the cardinality of I. The angle between two vectors {right arrow over (n)} and {right arrow over (q)} is denoted by ∠({right arrow over (n)}, {right arrow over (q)}).

Volume Between Two Triangles

In construction, the amount for cut-and-fill can be represented by the volume difference between triangles in the original ground and the same triangles in the final design. This amount may be found by considering each triangle in the mesh, then summing up all the quantities.

FIGS. 2A and 2Billustrates two alternatives for the volume between two triangles in accordance with one or more embodiments of the invention. Let Ai=(ai, bi, 0), i=1, 2, 3, B1=(a1, b1, x1), B2=(a2, b2, x2), and B3=(a3, b3, x3) be given points in3. Let V be the volume between two triangles ΔA1A2A3and ΔB1B2B3(seeFIGS. 2A and 2B). A formula for V may be derived in terms of (x1, x2, x3).

Let S be the area of the triangle ΔA1A2A3. The two cases illustrated inFIGS. 2A and 2Bmay then be considered since all remaining cases may be derived by using symmetry.

Referring toFIG. 2B, Case 2: x1>0, x2≤0, and x3≤0. In this case, vertex “x1” corresponds to fill amount (+), and vertices “x2” and “x3” correspond to cut amount (−).

Based on the above, V consists of three volumes V1, V2, V3corresponding to the bases S1, S2, S3, respectively (seeFIG. 2B).FIG. 2Bshows S1, S2, and S3with the ratio of the sides.FIG. 2Cillustrates the triangle bases S1, S2, and S3representing the volume between the triangles ofFIGS. 2A and 2Bin accordance with one or more embodiments of the invention.

In view ofFIGS. 2A-2C, one may conclude:

s1+s2x1=s3x3=sx1+x3⇒S3=x3⁢sx1+x3⁢⁢and⁢⁢⁢S1+S2=x1⁢sx1+x3.(3)
It then implies

Thus, the volume is

V=V1+V2+V3=s3·[x1⁡(x12+x22+x32)+x2⁢x3⁡(x1-x2-x3)(x1-x2)⁢(x1-x3)].(9)
Since S is constant, one may focus on

g⁡(x1,x2,x3):=x1⁡(x12+x22+x32)+x2⁢x3⁡(x1-x2-x3)(x1-x2)⁢(x1-x3).(10)
In summary, embodiments of the invention are interested in the following function (which may define the volume minimization set)

As used herein, the set where function (11) is smaller or equal to one, is referred to as the volume set/spheroid.FIGS. 3A and 3Bare different orthographic views of a visualization of the volume set in accordance with one or more embodiments of the invention. In this regard, step106ofFIG. 1obtains the volume set which may consist of the spheroid represented by (11) and illustrated inFIGS. 3A and 3B.

It is obvious that (11) is symmetric positively homogeneous. In order to find a volume subgradient set that can be used by the proximity operators, it suffices to show that the function (11) is continuous and convex.

Proposition 6.1 The function ƒ in (11) is continuous on3.

Proof. Clearly ƒ is continuous in the interior of each Ωiand −Ωi, i∈{0, 1, 2, 3}. One needs to show that ƒ is continuous on the boundaries.

First, it is clear that ƒ is continuous on Ω0up the boundary.

Next, consider ƒ on Ω1. We have

Forx1>0, it is clear that

Forx2<0, we have

Forx3<0, by symmetry, we have

Forx1>0,x2<0, it is clear that

Forx1>0,x3<0, by symmetry, we have

Forx2<0,x3<0, it is clear that

Similarly, we consider ƒ on the remaining regions and conclude that ƒ is continuous on3.

Fact 2 (positive semidefinite test) [8, p.˜566] A matrix H∈n×nis positive semidefinite if and only if all of its principle minors are nonnegative. Recall that for a square matrix H∈n×n, an r×r principle submatrix is a submatrix of H that lies on the same set of r rows and columns, and an r×r principle minor is the determinant of an r×r principle submatrix.

Proposition 6.3 Let Ωi, i∈{0, 1, 2, 3}, be given by (4). The function ƒ in (11) is convex on each Ωi.

Proof. It is clear that ƒ is convex on Ω0. It suffices to prove that ƒ is convex on Ω1. Clearly ƒ is twice differentiable on Ω1. Let H(x1, x2, x3) be the Hessian of ƒ. Denote HIthe principle submatrix of H with respect to rows and columns in the index set I. One can check that

Thus, by Fact 2, H(x1, x2, x3) is positive semidefinite for all (x1, x2, x3)∈intΩ1. It follows that ƒ is convex on Ω1.

Theorem 6.4 The function ƒ in (11) is convex on3.

Proof. One can certainly check that the gradient of ƒ is continuous at every point except the origin. Thus, ƒ is convex by [4, Theorem˜5.5].

Since ƒ is convex, one can obtain the gradient set ∇ƒ of ƒ. In embodiment of the invention, that set is shown inFIGS. 4A and 4B. This set looks like a football and is called the volume subgradient set. A proximity operator may then project one or more heights of a triangle to its volume gradient set, in order to minimize the earthwork volumes.

Polyhedral Upper Approximation

Embodiments of the invention present a simple way to (upper) approximate the volume function by a polyhedral function. Of course, it is possible to refine this estimation or use different ways to approximate the function by polyhedral functions.

Now, suppose z=(z1, . . . , zn) is the original elevations on the triangular mesh and x=(x1, . . . , xn) is a feasible design for the mesh. This generates a volume difference over each triangle Δ in the mesh. So the total volume difference is
V(x,z)=ΣalltrianglesΔVolume difference over Δ≤ΣalltrianglesΔγΔΦΔ=Φ(x,z),  (31)
where ΦΔis the volume upper estimation for triangle Δ using formula (26).

FIGS. 5A and 5Billustrate two orthographic views of the volume set of a polyhedral upper approximation of the volume function. The volume set inFIGS. 5A and 5Bare here referred to as the approximate volume level set. One can see that the approximate volume level set (FIGS. 5A and 5B) is contained in the original volume level set (FIGS. 3A and 3B).

From the approximate volume level set inFIGS. 5A and 5B, the subgradient set is computed. This subgradient set is shown inFIGS. 6A and 6B. In embodiments of the invention, the approximate volume subgradient set may be referred to herein simply as the approximate set. In this regard, in one or more embodiments, step108ofFIG. 1includes computing the approximate set of the football norm (i.e., the volume subgradient set). Such an approximate set may be represented by the ortographic views illustrated inFIGS. 6A and 6B. In addition, such an approximate set may be represented by a variety of geoemtric shapes including, for example, a convex hull.

Theorem 7.2 Let {ui}i∈Ibe a system of finitely many vectors inn, and

FIGS. 7A and 7Bare two visualizations of the dual ball (34) in3.

One can aim to minimizes the upper approximation Φ(x, z) over all the constraints. Thanks to the available proximity operator for each term ΦΔfrom Theorem 7.2 and 7.3, one can apply any optimization methods that use this formula.

The Projection PD

FIG. 7Aillustrates the set D in3in accordance with one or more embodiments of the invention.FIG. 7Billustrates the set D1:=D∩(−Ω1) in accordance with one or more embodiments of the invention.

As D0={1≥x1,x2,x3≥0} is a unit cube Ω0with one vertex at the origin, one uses the projection
PD0(x1,x2,x3)=min(1,xi),i=1,2,3,  (36)
whenever x1, x2, x3∈Ω0. As −D0is the negative, symmetric counter part to D0, one uses
P−D0(x1,x2,x3)=min(−1,xi),i=1,2,3,  (37)
whenever x1, x2, x3∈−Ω0.

FromFIG. 7A, one can see that all the other subsets are oblique pyramids that are symmetric (seeFIG. 7B). It is therefore sufficient to derive the projection for D1, and then switch coordinates accordingly to obtain the other projections.

If x=(x1,x2,x3)∈Ω1, there are three cases.

Case 2: x∈(−×+2)D1with x2≥x3. This means one wants to project to the pyramid face with the base line from (0,1,0) to (0,1,1), using a=−e1+e2and

As this is a projection onto a hyperplane, p may now lay outside Ω1. If pi>0, then p∈Ω0and letting p←(0,1, min{1, p3}) will shift it back to the pyramid base. If p3>p1+1, then p is above the pyramid edge 1−x1. In this case, one wants to project x directly onto the edge defined by a=−e1=(−1,0,0) and b=(0,1,1). So

Case 3: x∈(−×+2)D1with x3>x2. This means one wants to project to the pyramid face with the base line from (0,1,1) to (0,0,1), using a=−e1+e3. The rest is similar to case 2.

Pseudo Code for PD1

Projections for Each Orthant

As the pyramidal subsets are all symmetric, one can reuse PD1for the other subsets by switching variables.

Based thereon, one is ready to construct PD:

In view of the above, a scalar is applied to the projection in order to minimize an objective function that computes an absolute earthwork volume for the mesh (when designing a surface). Subsequent to applying the projection to design a surface, the actual surface may be constructed based on the design (e.g., by minimizing the computation of the absolute earthwork volume thereby minimizing the costs associated with the earthwork volume).

Proximity Operator to Minimize Earthwork Volumes

One can now state the final proximity operator for (33).

Let z0∈3be elevation points of a triangle in an existing triangular mesh. Let S be the surface area of that same triangle, z∈3be some new elevation values, and γ∈, γ>0 be a weight for the volume minimization objective. In order to minimize the volumes using the proximity operator, one can perform the following steps.

Net Volume Between Triangles

In site construction, earthwork volumes in some areas need to be cut, and in other areas volumes need to be filled. For a designer or civil engineer, it is important for them to have the ability to reuse the volumes that get cut in the areas where fill is needed. Bringing into a construction site material for a fill, or hauling out of the construction site material from a cut, is generally a very expensive task. Hence the balancing of cut and fill volumes among the construction site is desirable.

When describing the volume between triangles (above), the absolute volumes between triangles were examined. In this section, embodiments of the invention describe the balancing of cut and fill volumes. The difference in cut and fill volumes is also called the net volume between triangles. The net volume is the sum of all cut and fill volumes, where cut is positive and fill is negative. Hence, only Case 1 in the Volume Between Triangles section above applies. To balance cut and fill volumes, it is desirable to minimize the function:

where t is a triangle and n is the number of all triangles, and where the net volume of the triangle t is calculated as in Case 1 above:

It follows that one can rewrite function ƒ in the more general form:
ƒ=|a,x|,

where a is a vector of constants reflecting the area parts of S/3, and x are the elevation differences of the triangle vertices.

Proximity Operator to Balance Cut and Fill

Consider Lemma 6.68 in [11]. Using the function ƒ=|a, x|, and for λ>0 the proximity operator becomes:

With such a proximity operator, a contains the scalar from the area of the first triangle, x contains the height of one or more vertices between the first triangle and the modified first triangle, and Δ is a user input weight for the objective function.

In view of the above, a proximity operator may be utilized as part of an objective to balance the cut and fill when designing a surface (e.g., as set forth inFIG. 1Babove). Subsequent to applying the proximity operator to design a surface, the actual surface may be constructed based on the design (e.g., by balancing the cut and fill thereby minimizing the costs associated with the cut and fill).

Hardware Environment

FIG. 8is an exemplary hardware and software environment800(referred to as a computer-implemented system and/or computer-implemented method) used to implement one or more embodiments of the invention. The hardware and software environment include a computer802and may include peripherals. Computer802may be a user/client computer, server computer, or may be a database computer. The computer802comprises a hardware processor804A and/or a special purpose hardware processor804B (hereinafter alternatively collectively referred to as processor804) and a memory806, such as random access memory (RAM). The computer802may be coupled to, and/or integrated with, other devices, including input/output (I/O) devices such as a keyboard814, a cursor control device816(e.g., a mouse, a pointing device, pen and tablet, touch screen, multi-touch device, etc.) and a printer828. In one or more embodiments, computer802may be coupled to, or may comprise, a portable or media viewing/listening device832(e.g., an MP3 player, IPOD, NOOK, portable digital video player, cellular device, personal digital assistant, etc.). In yet another embodiment, the computer802may comprise a multi-touch device, mobile phone, gaming system, internet enabled television, television set top box, or other internet enabled device executing on various platforms and operating systems.

In one embodiment, the computer802operates by the hardware processor804A performing instructions defined by the computer program810(e.g., a computer-aided design [CAD] application) under control of an operating system808. The computer program810and/or the operating system808may be stored in the memory806and may interface with the user and/or other devices to accept input and commands and, based on such input and commands and the instructions defined by the computer program810and operating system808, to provide output and results.

Output/results may be presented on the display822or provided to another device for presentation or further processing or action. In one embodiment, the display822comprises a liquid crystal display (LCD) having a plurality of separately addressable liquid crystals. Alternatively, the display822may comprise a light emitting diode (LED) display having clusters of red, green and blue diodes driven together to form full-color pixels. Each liquid crystal or pixel of the display822changes to an opaque or translucent state to form a part of the image on the display in response to the data or information generated by the processor804from the application of the instructions of the computer program810and/or operating system808to the input and commands. The image may be provided through a graphical user interface (GUI) module818. Although the GUI module818is depicted as a separate module, the instructions performing the GUI functions can be resident or distributed in the operating system808, the computer program810, or implemented with special purpose memory and processors.

In one or more embodiments, the display822is integrated with/into the computer802and comprises a multi-touch device having a touch sensing surface (e.g., track pod or touch screen) with the ability to recognize the presence of two or more points of contact with the surface. Examples of multi-touch devices include mobile devices (e.g., IPHONE, NEXUS S, DROID devices, etc.), tablet computers (e.g., IPAD, HP TOUCHPAD, SURFACE Devices, etc.), portable/handheld game/music/video player/console devices (e.g., IPOD TOUCH, MP3 players, NINTENDO SWITCH, PLAYSTATION PORTABLE, etc.), touch tables, and walls (e.g., where an image is projected through acrylic and/or glass, and the image is then backlit with LEDs).

Some or all of the operations performed by the computer802according to the computer program810instructions may be implemented in a special purpose processor804B. In this embodiment, some or all of the computer program810instructions may be implemented via firmware instructions stored in a read only memory (ROM), a programmable read only memory (PROM) or flash memory within the special purpose processor804B or in memory806. The special purpose processor804B may also be hardwired through circuit design to perform some or all of the operations to implement the present invention. Further, the special purpose processor804B may be a hybrid processor, which includes dedicated circuitry for performing a subset of functions, and other circuits for performing more general functions such as responding to computer program810instructions. In one embodiment, the special purpose processor804B is an application specific integrated circuit (ASIC).

The computer802may also implement a compiler812that allows an application or computer program810written in a programming language such as C, C++, Assembly, SQL, PYTHON, PROLOG, MATLAB, RUBY, RAILS, HASKELL, or other language to be translated into processor804readable code. Alternatively, the compiler812may be an interpreter that executes instructions/source code directly, translates source code into an intermediate representation that is executed, or that executes stored precompiled code. Such source code may be written in a variety of programming languages such as JAVA, JAVASCRIPT, PERL, BASIC, etc. After completion, the application or computer program810accesses and manipulates data accepted from I/O devices and stored in the memory806of the computer802using the relationships and logic that were generated using the compiler812.

The computer802also optionally comprises an external communication device such as a modem, satellite link, Ethernet card, or other device for accepting input from, and providing output to, other computers802.

In one embodiment, instructions implementing the operating system808, the computer program810, and the compiler812are tangibly embodied in a non-transitory computer-readable medium, e.g., data storage device820, which could include one or more fixed or removable data storage devices, such as a zip drive, floppy disc drive824, hard drive, CD-ROM drive, tape drive, etc. Further, the operating system808and the computer program810are comprised of computer program810instructions which, when accessed, read and executed by the computer802, cause the computer802to perform the steps necessary to implement and/or use the present invention or to load the program of instructions into a memory806, thus creating a special purpose data structure causing the computer802to operate as a specially programmed computer executing the method steps described herein. Computer program810and/or operating instructions may also be tangibly embodied in memory806and/or data communications devices830, thereby making a computer program product or article of manufacture according to the invention. As such, the terms “article of manufacture,” “program storage device,” and “computer program product,” as used herein, are intended to encompass a computer program accessible from any computer readable device or media.

FIG. 9schematically illustrates a typical distributed/cloud-based computer system900using a network904to connect client computers902to server computers906. A typical combination of resources may include a network904comprising the Internet, LANs (local area networks), WANs (wide area networks), SNA (systems network architecture) networks, or the like, clients902that are personal computers or workstations (as set forth inFIG. 8), and servers906that are personal computers, workstations, minicomputers, or mainframes (as set forth inFIG. 8). However, it may be noted that different networks such as a cellular network (e.g., GSM [global system for mobile communications] or otherwise), a satellite based network, or any other type of network may be used to connect clients902and servers906in accordance with embodiments of the invention.

A network904such as the Internet connects clients902to server computers906. Network904may utilize ethernet, coaxial cable, wireless communications, radio frequency (RF), etc. to connect and provide the communication between clients902and servers906. Further, in a cloud-based computing system, resources (e.g., storage, processors, applications, memory, infrastructure, etc.) in clients902and server computers906may be shared by clients902, server computers906, and users across one or more networks. Resources may be shared by multiple users and can be dynamically reallocated per demand. In this regard, cloud computing may be referred to as a model for enabling access to a shared pool of configurable computing resources.

Clients902may execute a client application or web browser and communicate with server computers906executing web servers910. Such a web browser is typically a program such as MICROSOFT INTERNET EXPLORER/EDGE, MOZILLA FIREFOX, OPERA, APPLE SAFARI, GOOGLE CHROME, etc. Further, the software executing on clients902may be downloaded from server computer906to client computers902and installed as a plug-in or ACTIVEX control of a web browser. Accordingly, clients902may utilize ACTIVEX components/component object model (COM) or distributed COM (DCOM) components to provide a user interface on a display of client902. The web server910is typically a program such as MICROSOFT'S INTERNET INFORMATION SERVER.

Web server910may host an Active Server Page (ASP) or Internet Server Application Programming Interface (ISAPI) application912, which may be executing scripts. The scripts invoke objects that execute business logic (referred to as business objects). The business objects then manipulate data in database916through a database management system (DBMS)914. Alternatively, database916may be part of, or connected directly to, client902instead of communicating/obtaining the information from database916across network904. When a developer encapsulates the business functionality into objects, the system may be referred to as a component object model (COM) system. Accordingly, the scripts executing on web server910(and/or application912) invoke COM objects that implement the business logic. Further, server906may utilize MICROSOFT'S TRANSACTION SERVER (MTS) to access required data stored in database916via an interface such as ADO (Active Data Objects), OLE DB (Object Linking and Embedding DataBase), or ODBC (Open DataBase Connectivity).

Although the terms “user computer”, “client computer”, and/or “server computer” are referred to herein, it is understood that such computers902and906may be interchangeable and may further include thin client devices with limited or full processing capabilities, portable devices such as cell phones, notebook computers, pocket computers, multi-touch devices, and/or any other devices with suitable processing, communication, and input/output capability.

Of course, those skilled in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices, may be used with computers902and906. Embodiments of the invention are implemented as a software/CAD application on a client902or server computer906. Further, as described above, the client902or server computer906may comprise a thin client device or a portable device that has a multi-touch-based display.

CONCLUSION

This concludes the description of the preferred embodiment of the invention. The following describes some alternative embodiments for accomplishing the present invention. For example, any type of computer, such as a mainframe, minicomputer, or personal computer, or computer configuration, such as a timesharing mainframe, local area network, or standalone personal computer, could be used with the present invention.

REFERENCES