Summary

City Architecture Generation

Tom Kelly

A dissertation submitted to the University of Bristol in accordance with the requirements of the degree of

Master of Engineering in the Faculty of Engineering

August 2006 | CSMENG-06

Declaration

This dissertation is submitted to the University of Bristol in accordance with the requirements of the degree of Master of Engineering in the Faculty of Engineering. It has not been submitted for any other degree or diploma of any examining body. Except where specifically acknowledged, it is all the work of the Author. Tom Kelly, August 2006

? All Rights Reserved - Tom Kelly, 2006

Summary

In this thesis I present a historical city generation tool named Sity. It allows video game artists to design the style of the buildings and then use Sity to create an area of architecture.

The games industry is worth ￡13 billion worldwide per year, and this market has doubled in the last 6 years. Annually game studios spend ￡3.6 billion creating content for games. Sity is a tool to allow studios to control these spiralling budgets by automating the content development process. As Don Mattrick of EA games stated:

“building a game engine is easy; creating content is hard”

The previously used alternatives consist of the labour intensive and expensive approach of creating content in-house or risking loss of artist control and quality to content creation. Game development studios are well funded, highly technical companies that are always looking for a competitive edge over their competition.

The attractions of Sity include1:

?Solving the impending content crisis caused by the increased detailed required for next generation console titles.

?Allowing more draft environments to be evaluated in the same time allowing the consideration of different layouts.

?Reducing art personnel budgets.

?Giving the consumer a better experience with larger and more consistently detailed environments.

Technically I show how the Voronoi diagram and the camp skeleton algorithms complement each other in generating a city. They are combined with some simple inputs and directed by an L grammar.

The program provides a non-programming user with an interface for creating city geometry. It provides a straight forward presentation of the myriad of options available to control Sity, using a GUI that is generated on the fly from the internal data structures.

Summary of Work:

?Developed a weighted straight skeleton algorithm that allows negative weights and bevelling (a camp skeleton), and explored the computational complexities of such a structure (page 25)?Developed an implementation the Voronoi algorithm (page 31)

?Created a set of techniques for approximating a historical city (page 36)

?Written 25,000 lines of Java including use of the JMonkey2 scene-graph engine (available from https://www.wendangku.net/doc/5016883149.html,/home/tk1748/sity)

?Developed a GUI interface to the city generator, incorporating runtime interface generation and a 3D preview (see user guide in Appendix 2, page 55)

Contents

Contents (5)

Background and Research (8)

Commercial Viability (8)

Expansion (9)

Research & Considered Approaches (9)

A Description of Sity’s Approach (16)

Technical Aspects of Sity (19)

On Skeletons (19)

On Convex Skeletons (20)

On Concave Skeletons (21)

On Camp Skeletons (25)

Voronoi Diagram (31)

Sity Grammar Overview (36)

Design and Implementation (39)

Tool chain choices (39)

Engineering Overview (41)

Waterfall System (42)

GUI Design & Generation (46)

Sheets, Sheaves and Sity’s internal Polygon System (47)

External 3D Generation (49)

Results (50)

Future Work (50)

Business Steps (50)

Future Work on Sity (51)

Future Work on Theory (53)

Appendices (55)

Appendix 1: Miscellaneous (55)

Appendix 2: User Manual (55)

Getting Sity (55)

Running Sity (55)

Introduction (56)

Outputting a City via MEL (60)

Outputting a city as an .obj file (61)

Saving and loading a set of waterfalls (61)

About the Waterfalls (61)

Appendix 3: Jordan Curve Algorithm (64)

Appendix 4: Index of Figures and Tables (64)

Appendix 5: Voronoi Bisector calculations (66)

Appendix 7:Ear clipping algorithm (70)

Appendix 8: Union Algorithm (71)

Appendix 9: Results (73)

Road Maps (73)

Generated Cities (74)

Dedicated to Green & Black’s

Background and Research

Commercial Viability

As video games becomes more complex the resources required to generate content for these video games is increasing. Games developers are facing rising bills for content generation, and risk having to rush work to create the quantity of content required or quality and lose artistic control by outsourcing the work.

Sity is a tool that offers a solution to this problem – procedural geometry. By using a computer to generate large fictional cityscapes, artists are able to spend their time defining the details of the city and then having arbitrarily sized cities created automatically.

The speed of graphics hardware is growing exponentially, guided by Moore’s Law. A typical game in 1993, such as ID Software’s Doom3, may have had three thousand polygons in the game, by 2000 with games such as Ion Storm’s DeusEx4this had become fifty thousand and a typical game today (mid 2006) such as Ubisoft’s5Ghost Recon: Advanced Warfighter may have three million polygons in an environment. This growth shows no sign of slowing and its effect can be seen in the typical make up of a game developer shown in Figure 1.

Figure 1 DTI: Typical Development Talent Split6 Content creation personnel make up the majority of game development staff and budget, and as the complexity of video games’ content continues to rise this is becoming a serious problem for next generation console developers. Finding more intelligent ways to use these content creation staff is essential to creating affordable yet rich and detailed environments. Sity is a tool for these content artists to do just that.

Sity as a company offers huge potential:

?There are theoretical models showing that the technologies are viable, which have not been turned into successful competing products,

?There are several engines for the creation of city geometry, but none have been successful commercially (such as Binary World’s Descensor Engine7) or only been applied to other fields (Such as Pascal

Mueller’s academic project, which has only been used to produce content for films)

?There are already procedural content companies creating other content for digital worlds. For example IDV and their flagship product SpeedTree8.

Expansion

After the development of Sity, there is the possibility of many spin off products. Sity is a tool that generates procedural architecture designed to be copied into a game environment (at game “compile time”). With some optimisation the technologies developed could be used to generate cityscapes at game runtime - every time the user turns a corner a new block of houses awaits them, the same game will never be played twice.

There are also many other potential areas of expansion – from procedural cars to humans. A video game where the ‘bad guy’ changes every time you start a new game offers exceptional value to the consumer.

Research & Considered Approaches

There is a large body of work relating to automated architecture and cityscape generation. Some of the broader topics in this scope include:

?Automated construction of a city from collected data is examined by Takase et al9. By combining laser scans, existing 2D maps and aerial photographs the system can digitally reproduce whole cities –

drastically cutting down the time required. Manual touching up of complex buildings is required,

although the final results are very detailed and accurate.

?Parker and Leach10 describe the data structures required to endlessly produce 'pseudo infinite' cities. By assigning each building a seed that is used to generate the building an endless city can be generated and explored. This random approach is similar to that I take in this paper.

?Rapid procedural modelling of architecture is tackled by Birch et al11. By understanding some of the common features of architecture a building modelling tool can be created that is much quicker and easier to use than a more general purpose tool. For example opposite walls can be kept parallel and features such as doors can be selected as an entity and moved to a different location, as the program knows this feature belongs on a wall.

There is a substantial body of academic work relating specifically to the automated generation of fictional architecture. The topics covered are quite varied; researchers have approached this problem and various sub problems with a multitude of techniques and varying levels of success. Below I discuss the different aspects of the challenge in context with the research.

In one of the first attempts using a machine learning centric approach was taken by Mitchell12. He describes the huge potential search space for designing buildings in real world architecture setting. Many parameters - from local building codes, to the quantity of light a window would produce must be encoded and solved to produce a technically correct building. Trickier is the problem of designing an algorithm with a sense of aesthetic beauty, which complicates this search space again. For example we may desire that windows across

a building are different sizes in odd and even columns. Formulating a problem that is sufficiently constrained, without over constraining the problem is a tough problem itself, before solving this massive logic problem is considered.

Mitchell suggests a range of possibilities, from using a computer to design the buildings and humans to verify them to the opposite as possibilities for making use of computers in architecture.

'The logic of architecture' is an earlier book by Mitchell13. He describes the kind of first order logic predicates that may be used to describe architecture. Throughout this lengthy volume many approaches for describing architecture in logical form are given. None of these are concise enough to implement and the NP-complete nature of inferring facts from logic problems make this approach a little unrealistic.

My initial response to the problem is to construct an encoding for a building and a city and then to then use heuristic guided search in this cavernous space to find a realistic city. This could be done using a first order set of predicates and assumptions. After reading Mitchell's paper and making a rough estimate of the number of variables that would have to be combined to design a house in one location in a city (30 degrees of freedom) I came to conclusion that searching this space would be too computationally taxing, even if an automated evaluation routine could be created. This is mostly because we would be searching in and arbitrary 3D search space with many complex and interdependent limits. To construct one building would be time consuming, to construct the thousands required to create a city would be beyond the technology available to me.

The rest of the materials I have reviewed have taken a much less theoretical approach. Instead of search, a popular approach is to procedurally create buildings. The speed of finding a solution is much improved, at the cost of realism. Yap's14 stochastic approach to modelling a virtual Manhattan is typical. A simple grid is imposed in the shape of Manhattan Island. This is then split up into the archetypal grid pattern with definitions for how big the buildings should be in each block. The simplistic buildings are grown stochastically to a distribution around the specified size. From a distance this creates a reasonably interesting view of down-town New York. It is very limited to skyscrapers and American 'block' cities. But if an overview of the LA area were required it may be an appropriate tool to use.

Here I noted that the Yap’s concept of a stochastically applied distribution when determining the height of a building may also be extended too many different parameters of a building from the floor plan to the number of panes of glass in the window.

In the very enlightening book How Buildings Learn15, Bond describes the way houses age, and how their appearance changes over time. This was very interesting to me as it supported observations that I had made about buildings. Buildings that have been used for a while end up looking very different to how they were built.

Figure 2- How Buildings Learn, front cover, left: houses New Orleans 1857, right same houses 1993

In old cities each house in an initially identical row will have had many different modifications made to it by different owners through the years. Some houses will have had similar alterations to do with current trends (such as PVC windows), others will have unique changes by generations of rich or poor owners (such as telescopes and flag poles).

Bond describes numerous examples of how the floor plan of a house can over time grow. There is also an interesting description of the effect of wealth on house development. Rich home owners are more likely to make changes to their properties. Poorer home owners will not alter the appearance of their houses, and this may preserve many historic features, such as has happened in the older parts of New Orleans (Figure 2).

The end result is that the old buildings seen in European cities are a complex mess of features with underlying patterns. There are more likely to be correlations between buildings close to each other. Such structures are built to similar plans and similar materials and modifications that are made to one house are likely to be applied to other local houses. For examples when conservatories became popular they were added to old and new houses alike. Because of historic building protection laws uniform appearance is not correlated with the age of the property.

This huge variety provides a challenge for city generation. On a positive note for my project it means that irregular features are expected, and from a gross overview outside of the house there is very little order to these patterns.

There is a huge body of related material dedicated to land use modelling. This field is particularly well advanced as it has useful applications in town and regional planning. Mackett16 describes his iterative microsimulator model, MASTER, that partitions cities into zones, and models the composition of families and households to predict zone popularity and growth year on year. These models are frequently used by professional planning consultancies such as MVA17, and have rigorous economic and mathematical underpinnings. These systems are intended to model the effects of changing parts of a city's infrastructure but do not (yet) deal with house locations or road locations. Instead they deal with the make up of each abstract house, which only uses a zone as its area, and transport costs between these zones. To take this iterative concept to the level of detail that would be able to generate geometry would incur the exponential penalties discussed above by Mitchell.

Another detailed land use model is introduced by Letchner and Watson18 that works with a rigid American zone system (industrial, commercial or residential) and also generates an associated road map. By using an agent based approach to tertiary (smallest road) road system creation a network is extended that services as much land as possible. The resulting city maps do appear resemble 'western culture within the last century'.

An alternative to using a search agent to construct a road system, is to use a self sensitive Lindenmayer(L)-system as impressively shown by Parish and Müller 19. An L-system uses a simple set of production rules, repeatedly applied to create a fractal-like structure. A system is defined by a set of variables, a set of constants and set of production rules. In the following example X may represent “a window”, Y represent a drainpipe and +,- represent different quantities of space between the items.

Variables: X,Y

Constants: +,-

Start: X

Production Rules: (X → XY) (Y → -X+Y)

This produces the successive generations:

Parish and Müller construct larger 'motorway' roads are constructed between areas with high population density. Between these a grammar is used and recursively applied to construct the smaller roads. A modification on the usual L-system is to let the roads be self sensitive, meaning that:

?if the terminal roads of the L system are close to another road they will attempt to move towards it,?the terminals roads will prefer to join with an existing junction to form an intersection,

?the terminal roads will then attempt to connect with existing roads to form T junctions.

The roads are also sensitive to height and the L grammar used is modified to produce circular, random or Manhattan-esque road maps.

Parish and Müller then go on to subdivide each 'block' between the streets into plots and then to grow a building on it, again using an L-system. Level Of Detail (LOD) groups are used to store multiple representations of group in order to allow very large cities to be computed and rendered, without producing unnecessary detail. Onto these buildings repeating textures are devised to give the impression of doors and windows. The location of doors and windows is specified by performing a binary AND operation between horizontal and vertical binary patterns, so where they intersect is designated as a location for a window or door. This system is used commercially and has produced some very impressive results, although the buildings often appear block-based and too square and regular for an ancient city.

Another possible extension to the L-system is hinted at by Yap's stochastic approach to modelling Manhattan. By pseudo-randomly or stochastically choosing the production rule to use in an L-system it is possible to introduce additional variation. In this case each production rule in a given context is assigned a probability and the computer makes a stochastic choice as to which to use.

There is also a significant body of work related to architecture generation on single buildings. Most of the approaches use a hierarchical organisation of subcomponent parts to define the block first, then the land the building occupies (plot) then the walls and roof, followed by the windows, doors and other adornments. A typical example of this is given by Wonka et al20. He develops a system based on a modified L system using a 'split grammar'. The grammar is very tightly controlled with application rules to ensure that the type of architecture is consistent, for example a window will have the same type of frame on all sides. As it is a L-grammar it is context sensitive and chooses appropriate designs for the size of the feature and the building material. A split grammar allows for the replacement of items of geometry (such as the cuboid representing the top floor of a building) for different sized items of geometry (a triangular prism for the roof). This approach creates a massive range of possible buildings, from those with central arches to cylindrical skyscrapers, but relies on an equally detailed language, grammar and additional rules as to where the different elements of the grammar may be applied. A serious limit to the popular L system is highlighted – that buildings cannot 'grow into another', for example one house being knocked through into another. While we saw Parish and Müller using a self sensitive L system to overcome this with a simple road network, doing the same with the architecture itself would be very challenging.

Wonka et al. go on to another feature that is interesting in buildings – that of repeated symmetry/patterns. For example features such as window size and spacing are likely to be kept symmetrical throughout a floor of a building. The same types of windows are also more likely to be found on different floors of the same building. There will almost certainly be a door on the ground floor. This lead me to the concept that repeated symmetry is a building block of architecture, but also that knowing where to break these symmetries is critical, for example a house should not create a overhang onto a motorway just to be symmetrical. Even the locations where the symmetries are broken will often follow a set repeated pattern. For example this can be observed in addition of satellite dishes to houses, while not every house will have them a sizeable minority will. They will all face in similar directions and be on the same side of people’s houses in order to get the

best signal. However properties next to other large buildings that would obstruct the signal, or listed properties where the use of dishes is controlled follow different patterns. This argument follows on from the earlier points about the distribution of uniform appearance of properties. The probability or frequency of these symmetries does vary over a large range, from 'certain' for having a door somewhere in the building to 'a minority' for satellite dish ownership.

A less applied approach to building design is taken by Finkenzeller and Schmitt21 who describe a logical way of defining a floor plan so that the individual geometric components. By using a simple algorithm to combine regular polygons into an ordered wall plan, and then basing higher storeys around this plan detailed buildings may be constructed without a formal L system. By retaining the geometric information the underlying geometries can be retained and used later to decide upon fa?ades that are shared between conceptually similar components, such as the same wall on both sides of a window. As well as producing some very realistic floor plans the system is the nicely hierarchical (building, floor-plan, line-strip wall, subwall, door or window, edge refinement, frame). The system also interfaces with Alias' Maya MEL scripting language to allow quick renders of scenes suitable, a feature suitable for their anticipated audience of virtual environment manufacturers.

An even more detailed approach to this problem is taken by Legakis et al. in devising a cellular encoding mechanism for applying details to a wall. By identifying walls and the location of holes in them, it is possible to select areas that are window frames or wall edges. Cells around these components can then be marked and geometry generated for them automatically. Typically these cells are converted into bricks and mortar, to create a tessellated stone wall. An important point raised is the difference between abstract geometry and real geometry. Abstract geometry will typically be converted into polygons to render, but in doing so will lose much information about where edges exist. This lost information is expensive to retrieve from a polygon mesh and is valuable in detecting edges. By storing the abstract representation Legakis' implementation is able to detail with complexities such as curved walls and pillars with ease. It also allows the details of the bricks to be consistent around the edges of walls where standard 2D texture derivations typically fail.

While exploring the possibilities for roof generation I came across a paper from Franz Aurenhammer22 explaining the issues generating a typical hatched roof from an arbitrary floor plan. This problem, finding the 'straight skeleton', is more complex than it initially appears. The straight skeleton is a mathematical structure that is defined by the shrinking of the base polygon. I describe the details later in this work. The best solution found runs sub-quadratic time to produce. While Eppstein and Erickson23 describe one such fast approach, and describe the result of the process as a tree, the details of the algorithm are best described by Felkel and Stepan24, who go into some detail about the complexity of its construction.

Figure 3 – a straight skeleton (not-bold) of a polygon (bold) Laycock and Day’s paper25 investigates how to use the straight skeleton to produce different types of roof edges, from Mansard to Gable. By adjusting the result of the straight skeleton, after it has run, it is possible to produce a wide range of roof styles. My observation of the skeleton revealed several modifications that might make the skeleton a powerful abstraction tool:

? A more interesting skeleton may be constructed if each edge is assigned different slope. This could be used to create gabled ends of roofs without Laycock and Day’s messy alteration after the skeleton

algorithm has run.

?The skeleton can be truncated at any height during its construction, leaving a ‘bevelled’ object, this may be used as a wall if the edges slope is near-vertical or for constructing a window or door frame.

?The slope of a side may be changed at any time to create say a vertical wall, followed by an overhang, followed by a roof.

?It should be possible to construct skeletons from non-planar polygon. For example from a roof line, that has been adjusted due to additional windows.

This modified straight skeleton, or camp skeleton (for its similarity to a ridge tent with sides of different slopes) is used constantly in architectural design and seems to be an excellent component of a grammar. It can be used to create both a wall and roof of a house, as well as many other features it forms a useful abstraction.

I discovered another useful algorithm on the data visualisation course at Bristol. The Voronoi26 diagram was introduced as the dual of the Delaunay triangulation for the purpose structuring unstructured data.

As shown in Figure 4, a Voronoi diagram is constructed from a collection of points on a plane, inside a master-polygon. A polygon is drawn around each point, inside the master polygon, so that for all possible locations inside the polygon they are nearer the bounded point than any other. It occurred to me that the map of polygons produced resembled an aerial view of city streets. This had been noted before by Glass, Morkel

and Bangay27 only as recently as January this year. Glass et al. used a regular square grid of points with some quantity of noise added to produce the course grid structure in African informal settlements. The results were impressive, but I was surprised to see them switch to an L-System inspired by Parish and Müller for the more detailed streets. I believe that by combining different types of point generator, such as rectangular, circular and spiral, a very detailed and intricate road map could be created, a simple example with random points is shown in Figure 4. The Voronoi would not have the dead ends and symmetries of the L-system, unless they were added in at a later stage

Bristol street map28Voronoi diagram

Figure 4 - Comparison of Voronoi diagram and a Bristol street map

Some useful features of the Voronoi diagram include:

?Complete delegation – all the space defined in the initial polygon is accounted for by one sub-polygon or another

?Concave and convex shapes allowed, while a little more complex to implement the concave version of the algorithm allows intricate shapes to be tessellated

?Simple input – it is relatively simple to generate the input, as only points are required

?It may be possible to weight the Voronoi, to give some points a larger space than others, to allow more variation in the patterns produced.

A Description of Sity’s Approach

Sity combines some of the above ideas into a product designed to generate areas of under a ilometer square of a city in a believable manner. As simulating the processes that lead to a city’s growth was too complex for the resources I have, the city is constructed using a stochastic L-system.

The Voronoi and camp skeleton algorithms complement each other as production rules in the grammar. The skeleton creates very rigid 3D geometry, with interesting exceptions that appeal to the eye as man made. The 2D Voronoi is able to clean up these anomalies into something that is suitable for additional computation.

For example the Voronoi can create city blocks, while the straight skeleton can shrink these in to create roads in the spaces between; the skeleton can identify the areas of ground that may be a wall and the Voronoi can split the wall up to allow a door in the wall of a specified size.

The camp skeleton can be used to generate both the walls and the rooves of the buildings, based on Voronoi output. The Voronoi input will be dots within the containing polygon or a specified pattern. By using a stochastic L-system additional variety can be introduced to the grammar without letting the grammar become too large and unusable.

The anticipated use of Sity in game development:

1. A base grammar is imported

2.Changes to the grammar are edited by the game artists

3.The grammar is evaluated and the output commented upon

4.(optional) improvements to the grammar are applied

5.The grammar is evaluated again and output placed in a standard game environment development

tool, such as AutoDesk’s Maya29.

6.Additional features that are not available in the grammar are added in

7.The game development workflow continues.

An important business aspect of Sity is that it is a program intended for use by the game artists. This is critical as these artists need to take leading roles in content generation. Working by proxy through a programmer is not acceptable, as it will diminish artistic input to the process. Part of Sity’s appeal is that it allows quicker draft turn around times, and waiting for a programmer to convert concepts into will reduce this benefit.

For these reasons Sity will present itself to the user as comprehensive GUI that gives a preview of the city generated, and allows the complex grammar to be built up in a guided manner in an integrated environment.

This manner in which this grammar is presented was designed to be familiar to game artists. Using the mathematical form of the L-system as outlined above would not only be difficult to interpret into three dimensions, but be difficult for someone without a mathematical background to interpret. For these reasons it was decided to have an input system similar to Maya’s Hypergraph (Figure 5) as this is an often understood concept. Extensive use of graphics, colour and topology are characteristics of this input method. This system provides much more information than an L-system would require, such as multiple input points, so a subset has been chosen for Sity’s GUI.

Sity also interfaces with Maya and a common 3d file format output (Lightwave .obj format), to ensure a game developer’s work-flow is as uninterrupted as possible.

Figure 5 – Autodesk’s Maya Hypergraph

Technical Aspects of Sity

This section considers the theory used in Sity. I start by giving details of the two algorithms introduced above, and move on to showing how they can be combined into an effective grammar.

On Skeletons

The straight skeleton algorithm given by Felkel24was implemented, revised and updated to be able to generate camp skeletons. Here I describe that algorithm & details of its implementation, and how it grew to create the more interesting geometry given by the camp skeleton. I expected this to be a relatively easy implementation, but should have noted the lack of any documentation on creating a skeletons before I started. There were numerous hold ups and complications that suggests that creating a skeleton of this form as a project unto itself.

A straight skeleton is an operation on a simple polygon. A simple polygon in a mathematical sense is a 2D shape in which no lines cross. The straight skeleton creates the ‘roof’ corners suitable for this polygon. It defines a volume bounded by the input polygon and planes defined by the edges of the polygon that slope inwards. Another way of thinking of it is the result of shrinking in the vertices of the polygon, as shown in Figure 6. Note that the skeleton is a 2D structure, but map be easily converted to a 3D form.

Figure 6 – Top left, the idea of shrinking a polygon(bold) to giver the straight skeleton (top right).

Skeleton extrapolated to 3D, bottom.

Here it is interesting to observe that we are constructing a tree. Each vertex generates a bisector (roof edge) and these merge together, removing sides as we progress higher up the skeleton. Branches merge as we come towards the top of the skeleton. While not strictly true when dealing with concave shapes (a twig, may lead to two branches), this hierarchy is an important feature when manipulating the skeleton.

A na?ve way to create the skeleton is by shrinking in the vertices several times. This is relatively inefficient because for each iteration shrinking, each vertex must be moved in and then checked against all other lines in the polygon to check it did not cross them. To get accurate results large numbers of iterations would be necessary and hence make the procedure very costly. Felkel’s method runs in O(nm+nlog n) time, where n in the total number vertices and m is the number of these that are concave. The modifications for the camp skeleton mean my implementation runs in O(n2) time.

On Convex Skeletons

Firstly I will describe the algorithm for unweighted convex simple polygons. The method I used, detailed by Felkel relies on the concept of finding collisions between the bisectors of each vertex. Each vertex is stored in a doubly linked list, along with pointers to the previous edges and the next edge, see Figure 7i.

Figure 7 – i) concave pointer layout, ii) changes that result after a split event, edge pointers are double

arrows next and previous pointers in the active list are single arrows At any time this linked list of vertices is the ‘active’ working set representing the height up the side of the roof that we have reached. All active points are stored in a hash set as well as the doubly linked list.

The bisector direction is defined by next and previous edges. This can be thought of as the midway line between the adjoining lines; a full description is given later. In a concave shape a vertex’s bisector may collide with either of the bisectors of the vertexes on either side. This type of simple collision is known as an edge event.

新托福阅读SUMMARY题型解法

对于目标明确，清晰认识自己薄弱的考生一定很想知道托福阅读summary题型该怎么解。接下来上海环球托福为考生解答。 首先，做阅读就要了解掌握文章的主旨是什么，新托福阅读SUMMARY题作为文章最后一种题型，考察的是对文章主要段落的主旨概括能力，而非全篇文章主旨。直白一点说，就是只需要关注文章局部段落，而不需要在意全局。这不同于老托福阅读里面每篇文章都有一道“What is the passage mainly about”这样的全文主旨题。 接着，考生要如何掌握主旨，来完成summary的题目。阅读英语段落的时候，应该是“匀速阅读”还是“变速阅读”呢？当然是“变速阅读”！这样考生才能做到阅读时的详略得当。但是，“变速阅读”是“先快后慢”还是“先慢后快”呢？这就要从英语的思维方式说起。 汉语族人的思维方式是“螺旋式”的，喜欢画龙点睛，我们称之为“Save the best for the last”。而英语族人的思维方式是“直线式”的，喜欢直入主题，我们称之为“Say what you want to say, then say why”。阅读英语段落的要领：变速阅读，先慢后快，精读首句，浏览全段。据统计，70%-80%的英语段落都是首句是主题句。所以，以后阅读英语段落，应该先精读首句（把握首句的“主题”和“方向”），再浏览全段（把握全段的“关系词”），才能实现快速阅读。而很多同学以前阅读的时候，要么就是倾向于到段落结尾找主题句（这主要是受了汉语思维方式的影响），要么就干脆把有限的精力平均分配到一段话内部的每个单词。 说了那么多，上海环球托福为你提出掌握主旨的方法： 1、常用法——分析段落结构找主题句 通过段落结构来概括主旨，常见的段落结构有如下六大类：（1）总分；（2）总分总（由总分演变而成）；（3）分总；（4）分总分（由分总演变而成）；（5）对比；（6）并列。其中，前四种段落结构都存在主题句和支持句之分。而后两种结构中可能不存在主题句，其段落内部会分成若干个势均力敌的部分，只不过对比结构段落的两部分之间方向相反，而并列结构段落的各部分之间方向相同。一、总分结构 总分结构的主题句一般为首句（如果首句结束后，第二句话存在转折关系，那么主题句就是第二句）。最常见的总分段落的标志就是第二句话前面出现“for example/instance”等举例关系词。如果总分结构段落最后再加一个总结句，就是总分总结构。这种段落结构约占70%。这个方法最大好处是大部分段落都存在主题句，所以能够广泛应用该方法概括段落主旨。这就是“常用法”的由来。但是，该方法的缺点是，如果段落结构比较复杂，又存在大量生词，可能导致我们难以找到主题句。这时候“简易法——重复出现是主旨”就会帮上大忙了。 2、简易法——重复出现是主旨 之所以有第二个方法是因为第一个方法有缺点，常用法的缺点是，如果段落结构比较复杂，又存在大量生词，可能导致我们难以找到主题句。这时候“简易法——重复出现是主旨”就会帮上大忙了。如果一段话在不断重复某一概念，就说明这段话在围绕这个概念展开，这个概念就是这段话的主旨。这就为我们快速把握主旨提供了极大的方便。因此，这种方法称为“简易法”。 在一段话内部重复出现可以分为三种类型。第一种是“原词”重复，但是这也是作者极力避

英文summary写作范例

Article Children Must be Taught to Tell Right from Wrong William Kilpatrick Many of today 's young people have a difficult time seeing any moral dimension （ 道德层 面 ） to their actions. There are a number of reasons why that 's true, but none more prominent than a failed system of education that eschews （ 回避 ） teaching children the traditional moral values that bind Americans together as a society and a culture. That failed approach, called “decision - making, ” was introduced in schools 25 years ago. It tells children to decide for themselves what is right and what is wrong. It replaced “character education. （ 品格教 育 ）” Character education didn 't ask children to reinvent the moral wheel （ 浪费时间重新发明早已存 在的道德标准）; instead, it encouraged them to practice habits of courage, justice and self-control. In the 1940s, when a character education approach prevailed, chewing gum; today they worry about robbery and rape. Decision-making curriculums pose thorny （ 棘手的 ） ethical dilemmas to students, with the impression that all morality is problematic and that all questions of right and wrong are in dispute. Youngsters are forced to question values and virtues they 've never acquired in the first place or upon which they have only a tenuous （ 薄弱的 ） hold. The assumption behind this method is that students will arrive at good moral conclusions if only they are given the chance. But the actual result is moral confusion. For example, a recent national study of 1,700 sixth- to ninth-graders revealed that a majority of boys considered rape to be acceptable under certain conditions. Astoundingly, many of the girls agreed. This kind of moral illiteracy is further encouraged by values-education （价值观教育 ） programs that are little more than courses in self-esteem （ 自尊 ）. These programs are based on the questionable assumption that a child who feels good about himself or herself won 't want to do anything wrong. But it is just as reasonable to make an opposite assumption: namely, that a child who has uncritical self-regard w ill conclude that he or she can 't do anything bad. Such naive self-acceptance results in large part from the non-directive （ 无指导性的 ）, non-judgmental （ 无是非观的 ）, as-long-as-you-feel-comfortable-with-your-choices mentality （ 思 想） that has pervaded （ 渗透） public education for the last two and one-half decades. Many of today 's drug education, sex education and values -education courses are based on the same 1960s philosophy that helped fuel the explosion in teen drug use and sexual activity in the first place. Meanwhile, while educators are still fiddling with （ 胡乱摆弄 ） outdated “feel - good ” approaches, New York, Washington, and Los Angeles are burning. Youngsters are leaving school believing that matters of right and wrong are always merely subjective. If you pass a stranger on the street and decide to murder him because you need money —if it feels right —you go with that feeling. Clearly, murder is not taught in our schools, but such a conclusion —just about any conclusion —can be reached and justified using the decision-making method. It is time to consign （ 寄出 ） the fads （风尚 ） of “decision - making ” and “non- judgmentalism ” to the ash heap of failed policies, and return to a proved method. Character education provides a much more realistic approach to moral formation. It is built on an understanding that we learn morality not by debating it but by practicing it. Sample teachers worried about students leaving them

summary 范文

Original: My neighbor's children love playing hide-and-seek as all children do, but no one imagine that a game they played last week would be reported in the local newspaper. One afternoon, they were playing in the vacant lot down the corner. Young Paul, who is only five years old, found the perfect place to hide. His sister, Natalie, had shut her eyes and was counting to ten when Paul noticed the storage mail box at the corner and saw that the metal door was standing open. The mailman had just taken out several sacks of mail and had carried them to his truck which was standing at the curb a few feet away. Paul climbed into the storage box and pulled the door closed so hard that it locked. Soon realizing what he had done, he became frightened and started crying. Meanwhile, Natalie was looking for him everywhere but could not find him. It was lucky that she happened to pause at the corner for a minute and heard her brother's cries. She immediately ran to tell the mailman who hurried back from his truck to unlock the metal door. Paul was now free, but he had had such a bad scare that he could not stop crying. The mailman, however, soon found a way of making him laugh again. He told him that the next time he wanted to hide in a mail box, he should remember to put a stamp on himself! Summary: The children were playing hide-and-seek in a vacant lot one afternoon. Finding that the storage mailbox had been left open, Paul hid and locked himself in it accidentally. His sister, Natalie, heard his cries and realized where he was hiding, so she immediately told the mailman to unlock the metal door. After letting him out, the mailman made him stop crying by telling him to put a stamp on himself the next he wanted to hide in a mailbox. Original: Why do some animals die out? In the past two hundred years people have caused many kinds of animals to die out--to become extinct. People keep building houses and factories in fields and woods. As they spread over the land, they destroy animals' homes. If the animals can't find a place to live, they die out. Sixteen kinds of Hawaiian birds have become extinct for this reason. Other animals, such as the Florida Key deer, may soon die out because they are losing their homes.Hunters have caused some animals to become extinct, too. In the last century, hunters killed all the passenger pigeons in North America and most of the buffalos. Today they are fast killing off hawks and wolves. Pollution is killing many animals today, too. As rivers become polluted, fish are poisoned. Many die. Birds that eat the poisoned fish can't lay strong, healthy eggs. New birds aren’t born. So far, no animals have become extinct because of pollution. But some, such as the bald eagle and the brown pelican, have become rare and may die out. Scientists think that some animals become extinct because of changes in climate. The places where they live become hotter or cooler, drier or wetter. The food that they eat cannot grow there any more. If the animals can't learn to eat something else, they die. Dinosaurs may have died out for this reason. Summary:

Summary的写作技巧和常见句型

S u m m a r y 的写作技巧和常见句型 、概括原文 一）阅读 1. 读懂文章读文章的时候，要养成良好的阅读习惯，划划写写，英文阅读的时候，用铅笔轻轻划出重点词汇。 认真阅读给定的原文材料。如果一遍不能理解，就多读两遍。阅读次数越多，你对原文的理解就越深刻。 2. 拆分文章按照作者的思路，把文章分段，每个段落用几个词，几个短语概括。尽量简短，精 炼。 段落中心句，在段落的开头或末尾。有时也会变态的在当中。 3. 概括主旨写出文章的thesis, 一句话概括文章的主旨。 二）基本结构和技巧 1.重新拟定标题给summary 起一个标题。用那些能概括文章主题思想的单词、短语或短句子作为标题。也可以采用文中的主题句作为标题。 2. 阐述观点 摘要应全部用自己的话完成。不要引用原文的句子。写概述的时候，如果能够明确是他人写作的文章，注意要把作者的名字放在第一句（或者是接着写出要阐述的main ideas （主要观点）和supporting points （对主要观点的the author .. ）。

支持）。 3. 词汇运用 注意概述的cohere nee （连贯性），运用好tran siti on words （过渡 词） , like however, furthermore, nonetheless, besides, therefore etc. 4. 删除细节 只保留主要观点。 5. 选择一至两个有代表性的例子 原文中可能包括5 个或更多的例子，你只需从中筛选一至二个例子。 6. 把长句变成短句，把长段的描述变成短小、简单的句子。 He was hard up for money and was being pressed by his creditor. 可以概括为：“ He was in finan cial difficulties. His courage in battle might without exaggeration be called lion- like. ” 可以概括为：” He was very brave in battle. He was hard up for money and was being pressed by his creditor. 可以概括为：“ He was in finan cial difficulties. 6）你还可以使用词组代替整句或者从句。请看下面的例子： Beautiful mountains like Mount Tai, Lushan Mountain, and Mount Huang, were visited by only a few people in the past. Today, better wages, holidays with pay, new hotels on these mountains, and better train and bus services, have brought them within reach of many who never thought of visiting them ten years ago. ” 可以概括为：” Beautiful mountains like Mount Tai, once visited by only a few people, are today accessible to many, thanks to better wages, paid holidays,

summary好例子

Steps to Writing a Summary 1.Read and understand the prompt or writing directions. What are you being asked to write about? Example: Summary of an Article Write a summary of the article. Your writing will be scored on how well you: ?state the main ideas of the article; ?identify the most important details that support the main ideas; ?write your summary in your own words, except for quotations; and ?express the underlying meaning of the article, not just the superficial details. 2. Read, think about, and understand the text. Review the material to make sure you know it well. Use a dictionary or context clues to figure out the meaning of any important words that you don’t know. 3. Take notes. Write down the main ideas and important details of the article. 4.Write a thesis statement. In a single sentence, state the main idea of the article. The thesis statement should mention the underlying meaning of the article, not just the superficial details. 5. Organize and outline ideas. Write down the important details you need to include in the summary. Put them in a logical order. Topic Sentence: Evidence: #1: #2: #3: 6.Write your essay. ?Your summary should be about one third of the length of the original article. ?Focus on the main point of the article and the most important details. ?Use your own words; avoid copying phrases and sentences from the article unless they’re direct quotations. 7.Revise. Have you indented all paragraphs? Have you captured the main point of the article? Have you included the most important details? Is there sentence variety? Have you avoided writing short, choppy sentences? Are there transitional words and phrases to connect ideas? 8. Proofread and edit. Check your spelling, grammar, and punctuation. Is the verb tense consistent? Are all names spelled correctly and capitalized? Have you avoided writing run-on sentences and sentence fragments? 9. Write your draft. Use blue or black ink. Skip lines. Write on one side of the paper only. Include a title on the top line. 10. Read your summary one last time before you turn it in. Look for careless spelling, punctuation, and grammar errors, especially omitted words or letters. Cross out errors neatly with a single line and write the correction above. Original Article: Bats In the distant past, many people thought bats had magical powers, but times have changed. Today, many people believe that bats are rodents, that they cannot see, and that they are more likely than other animals to carry rabies. All of these beliefs are mistaken. Bats are not rodents, are not blind, and are no more likely than dogs and cats to transmit rabies. Bats, in fact, are among the least understood and least appreciated of animals. Bats are not rodents with wings, contrary to popular belief. Like all rodents, bats are mammals, but they have a skeleton similar to the human skeleton. The bones in bat wings are much like those in arms and the human hand, with a thumb and four fingers. In bats, the bones of the arms and the four fingers of the hands are very long. This bone structure helps support the web of skin that stretches from the body to the ends of the fingers to form wings. Although bats cannot see colors, they have good vision in both dim and bright light. Since most bats stay in darkness during the day and do their feeding at night, they do not use their vision to maneuver in the dark but use a process called echolocation. This process enables bats to emit sounds from their mouths that bounce off objects and allow them to avoid the objects when flying. They use this system to locate flying insects to feed on as well. Typically, insect-eating bats emerge at dusk and fly to streams or ponds where they feed. They catch the insects on their wingtip or tail membrane and fling them into their mouths while flying. There are about 1,000 species of bat, ranging in size from the bumblebee bat, which is about an inch long, to the flying fox, which is sixteen inches long and has a wingspan of five feet. Each type of bat has a specialized diet. For seventy percent of bats, the diet is insects. Other types of bats feed on flowers, pollen, nectar, and fruit or on small animals such as birds, mice, lizards, and frogs. (continued on back)

有关summary的写作技巧

有关s u m m a r y的写作技 巧 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

Summary的写法1 一、概括原文 （一）阅读 1.读懂文章 读文章的时候，要养成良好的阅读习惯，划划写写，英文阅读的时候，用铅笔轻轻划出重点词汇。 认真阅读给定的原文材料。如果一遍不能理解，就多读两遍。阅读次数越多，你对原文的理解就越深刻。 2.拆分文章 按照作者的思路，把文章分段，每个段落用几个词，几个短语概括。尽量简短，精炼。 段落中心句，在段落的开头或末尾。有时也会变态的在当中。 3.概括主旨 写出文章的thesis, 一句话概括文章的主旨。 （二）基本结构和技巧 1.重新拟定标题 给summary起一个标题。用那些能概括文章主题思想的单词、短语或短句子作为标题。也可以采用文中的主题句作为标题。 2.阐述观点 摘要应全部用自己的话完成。不要引用原文的句子。写概述的时候，如果能够明确是他人写作的文章，注意要把作者的名字放在第一句（或者是the

author…….）。接着写出要阐述的main ideas（主要观点）和supporting points （对主要观点的支持）。 3.词汇运用 注意概述的coherence（连贯性），运用好transition words（过渡词）, like however, furthermore, nonetheless, besides, therefore etc. 4.删除细节 只保留主要观点。 5.选择一至两个有代表性的例子 原文中可能包括5个或更多的例子，你只需从中筛选一至二个例子。 6.把长句变成短句，把长段的描述变成短小、简单的句子。 “ He was hard up for money and was being pressed by his creditor.” 可以概括为：“He was in financial difficulties.” “His courage in battle might without exag geration be called lion-like.” 可以概括为：”He was very brave in battle.” “He was hard up for money and was being pressed by his creditor.” 可以概括为：“He was in financial difficulties.” 6) 你还可以使用词组代替整句或者从句。请看下面的例子： “Beautiful mountains like Mount Tai, Lushan Mountain, and Mount Huang, were visited by only a few people in the past. Today, better wages, holidays with pay, new hotels on these mountains, and better train and bus services, have brought them within reach of many who never thought of visiting them ten years ago.” 可以概括为：”Beautiful mountains like Mount Tai, once visited by only a few people, are today accessible to many, thanks to better wages, paid holidays, new hotels and better transportation services.” 7) 使用概括性的名词代替具体的词，比如： “She brought home several Chinese and English novels, a few copies of Time and Newsweek and some textbooks. She intended to read all of them during the winter vocation.”

雅思阅读SUMMARY题型解答

今天给大家介绍雅思阅读SUMMARY题型该如何解答 一、SUMMARY题型要求 雅思阅读该类题目是一小段文字，是原文或原文中的几个段落主要内容的缩写或改写，称之为摘要。摘要中有几个空白部分要求考生填空。 SUMMARY要求考生要对原文的内容结构有精确的把握，更需要考生运用一定的综合概括能力，将原文和缩写文章进行词句、词语的比较，提取原文信息。 按照范围，摘要可分为两种： 全文摘要（8－10题）和部分段落摘要（涉及2－3段，5－6题）。 全文摘要，摘要信息来自全文，题目空格的数目较多。 部分段落摘要，摘要信息来自原文某几个连续的段落，题目空格的数目较少。 最近雅思考试中出现的大部分是部分段落摘要，信息来自原文连续的两到三段，题目空格的数量在5 题左右。对于部分段落摘要，有的在题目要求中会指出它来自原文的哪些段落，如complete the summary below of the first two paragraphs of the reading passage。 但大部分的部分段落摘要只是在题目要求中说它是原文的一个摘要或部分段落摘要，并不指出它来自原文的哪些段落。 按照填空内容，摘要也可分为三种：原文原词、从多个选项中选词和自己写词。 原文原词的题目要求中常有from the reading passage 的字样。从多个选项中选词，选项的数目常常超过题目空格的数目。从多个选项 中选词或自己写词的题目要求中没有from the reading passage 的字样，有时会有using the information in the passage 的字样。 先看选项，按词性归类。注意是否有同根异性词选项（其中可能一个是答案）。以先猜后找方法解题：猜——用语法；找——回原文。 最近雅思考试中，绝大部分是原文原词或从多个选项中选词，很少有自己写词的。这类题在A类和G类考试中出现的频率一般都是每两次考一次， 每次考一组，共五题左右。 二、SUMMARY解题步骤 （1）雅思考试该类题型，要求仔细读摘要的第一句话，找出它在原文中的出处，通常是和原文某段话的 第一句相对应。确定填空部分是所给阅读文章的全篇还是部分的SUMMARY，确定是用题目所提供的单词表填空，还是需要自己从原文中挑选 单词填空。如果题目要求中已经指出了摘要的出处，则此步可以略去不做。 （2）略读缩写文章，了解大致内容，迅速回原文定位，确定是哪一段落的SUMMARY，或是涉及哪些段落的内容。 把空格前后的词作为signal words，到原文中去找这些词的对应词。 对应词的特点如下： a．原词 b．词性变化；如空格前的词为threatening, 形容词，原文中的词为threat, 名词。

Summary_常用句式

Summary 常用句式 1.This article/ passage mainly tells (a story) about…… 2.This passage mainly deals with/discusses/explores/…… 3.In this passage (about ……), the author …… 4.In this passage about ……, the author …… 5.The author began the essay/ passage by telling/ presenting…… 6.First/Firstly/ In the beginning/In the first part, the author argues/ explains/ mentions/ states/ points out (that)…… 7.Secondly/ Next/ Further on/ Then/ In the next part/ In the main part, the author goes on with…… 8.Finally/ As a conclusion/, the author concludes/ adds/ stresses that…… 9.Finally, the author summarizes that …… 二、常见句型 1）This paper deals with.. 2）This article focuses on the topics of (that,having,etc). 3）This essay presents knowledge that... 4）This thesis discusses... 5）This thesis analyzes... 6）This paper provides an overview of...

一篇英语summary范文英语Summary写

一篇英语summary范文英语Summary写第一步：阅读 A.认真阅读给定的原文材料。如果一遍不能理解，就多读两遍。阅读次数越多，你对原文的理解就越深刻。 B.给摘要起一个标题。用那些能概括文章主题思想的单词、短语或短句子作为标题。也可以采用文中的主题句作为标题。主题句往往出现在文章的开头或结尾。一个好标题有助于确定文章的中心思想。 C.现在，就该决定原文中哪些部分重要，哪些部分次重要了。对重要部分的主要观点进行概括。 D.简要地记下主要观点——主题、标题、细节等你认为对概括摘要重要的东西。 第二步：动手写作 A. 摘要应该只有原文的三分之一或四分之一长。因此首先数一下原文的字数，然后除以三，得到一个数字。摘要的字数可以少于这个数字，但是千万不能超过这个数字。

B. 摘要应全部用自己的话完成。不要引用原文的句子。 C. 应该遵循原文的逻辑顺序。这样你就不必重新组织观点、事实。 D. 摘要必须全面、清晰地表明原文所载的信息，以便你的读者不需翻阅原文就可以完全掌握材料的原意。 E. 写摘要时可以采用下列几种小技巧： 1) 删除细节。只保留主要观点。 2) 选择一至两个例子。原文中可能包括5个或更多的例子，你只需从中筛选一至二个例子。 3) 把长段的描述变成短小、简单的句子。如果材料中描述某人或某事用了十个句子，那么你只要把它们变成一两句即可。 4) 避免重复。在原文中，为了强调某个主题，可能会重复论证说明。但是这在摘要中是不能使用的。应该删除那些突出强调的重述句。

5) 压缩长的句子。如下列两例： “His courage in battle might without exaggeration be called lion-like.” 可以概括为：”He was very brave in battle.” “He was hard up for money and was being pressed by his creditor.”可以概括为：“He was in financial difficulties.” 6) 你还可以使用词组代替整句或者从句。请看下面的例子： “Beautiful mountains like Mount Tai, Lushan Mountain, and Mount Huang, were visited by only a few people in the past. Today, better wages, holidays with pay, new hotels on these mountains, and better train and bus services, have brought them within reach of many who never thought of visiting them ten years ago.”