Procedural modeling of medieval castles

This research paper describes a new method in which the discovery and construction of man-made structures, specifically medieval castles, in a three dimensional environment can be intelligently constructed given only a random terrain and simple user-defined suggestions. Our method of procedural modeling makes use of convex hulls, extracted from a given terrain, to provide several construction elements that are used to complete the finished model.In developing the procedurally modeled castles, we employed hybrid multi-fractals using Perlin noise as way to generate random terrains. It was essential to implement the random/fractal terrain generation to provide sufficient means of testing several cases, as opposed to using the same terrain over and over. This provided a fast and efficient means of testing a component of the modeling method on several different terrains.The approach this modeling procedure first takes is common among the construction of man made buildings. Just as one would do when first setting up a tent, for example, the first step is to locate a suitable site. The target for such a search is a satisfactory foundation in which to build upon. Our approach was to search the generated terrain for those facets whose normals are within some tolerance of straight up. This will find those portions of the terrain that are the most horizontal and, therefore, offer the most potential for a natural foundation for the castle, and require the least movement of soil.Once the horizontal facets of the terrain have been located they are grouped together. Now the decision as to what shape the encompassing foundation will take must be made. This is done because in most cases the grouped facets will contain holes or appear to branch which does not lend itself well to a foundation. Obviously bounding squares, rectangles, circumferences, or any other user defined shape, for that matter, could do this job. In fact, many castles are indeed built in such a way that they are quite symmetric and using a user defined shape may provide a very desirable foundation. However, our method implements a more general approach that provides a unique foundation and therefore a unique castle construction each time it is presented with a terrain.Our approach to foundation shape creation is to use the points from the grouped horizontal facets and use the convex hull of these points as the boundary of the foundation. One major advantage and positive visual effect that using a convex hull foundation provides over a user defined bounding shape is that it gives the appearance of the castle being built to suit its environment with minimal modification to the terrain.To provide easy access to these candidate foundation hulls, a scoring system was created which accepts a user's request for a convex hull from the set generated initially. The request defines desired attributes such as position, altitude, and area along with weights that specify the importance of the attributes. The foundation finder then scores the hulls according the the user's request and returns the highest scoring hull.We discovered that the convex hulls lent themselves very nicely to the other elements of the castle. Castle walls could be built simply by using either the foundation convex hull or a similar hull by using the hull's sides to project onto the terrain where the walls should be built. In addition, concentric outer and inner walls could be built by using hulls varying in scale and by perturbing the points of the hull to provide additional randomness. The towers along the walls could simply be placed at the points along the boundary of the hulls.The convex hulls were also employed in the creation of the castle moat. Using three hulls; one for the inner shore, another to define the middle band of the moat where it is at its deepest, and one for the outer shore, the terrain can be interpolated into a v-shape to create the moat. Additional terrain interpolation was also implemented to erode raised foundations back into the generated terrain to prevent sharp cliff-like artifacts. This too used convex hull boundaries to specify the points that were to interpolated.Convex hulls were also used when expanding the size of the castles. Castles often outgrew their usefulness and would need to be expanded in order to further serve a meaningful purpose. We again put to use the request system when expanding the area of a castle by using the first foundation request that was used to obtain the first convex hull foundation. Using the same request lets us retrieve the most similar, more importantly closest, piece of foundation-worthy land. We can then create a new convex hull using an enlarged version of our initial foundation hull and the newly requested convex hull, for example, in order to create a new outer wall.