A hardware graphics accelerator accepts lists of polygon vertices from an application environment running application and systems graphics software. After a polygon is rotated and translated as needed, it is checked for trivial accept/reject against the clip limits of the viewing volume, but is not otherwise clipped. Polygons that are not rejected are decomposed into triangles before any other operations on them are performed. After decomposition the triangles are illuminated by light sources, if desired and then clipped by a triangle clipper, rasterized, and the results sent to a frame buffer for display. The triangle clipper incorporates trivial accept/reject operation, and is capable of operating on non-planar quadrilaterals. It avoids ugly artifacts during certain clip operations when the diagonal used to decompose a quadrilateral into triangles intersects a clip plane not parallel to the viewing axis. It does this by replacing the point of intersection along that diagonal that the clipper would ordinarily find with a point that is the projection of that diagonal onto a line between two adjacent points of intersection of the actual edges of the quadrilateral with the clip plane.

The temporal signal generated has a periodic configuration defined by an arrangement of seed patterns resulting from a branching construction employing n successive applications of m pattern type laws each defined by a specific arrangement of p pattern types. This construction amounts to defining a periodic signal configuration as a component "an" of the nth term Un with several components (an, bn) of a recurrent sequence defined at the level of its components by a particular recurrent composition law, the initial term UO having for its components the seed patterns (aO, bO). The temporal signals known by the name "fractal" result from a branching construction of this kind. The generator comprises an elementary signal forms generator circuit (20) corresponding to the definitions of the seed patterns, an m-digit counter (30) to base p incremented when each elementary signal form is delivered by the elementary forms generator circuit (20) and a pattern type selector circuit (40) controlled by the counter (30) to base p and controlling the elementary forms generator circuit (20).

A high order surface patch rendering system with adaptive tessellation. A patch is rendered by subdividing a patch until the subpatches are sufficiently flat that they can be approximated by a quadrilateral. To subdivide a patch, the patch rendering system uses a patch division unit which accepts the control points of a patch and divides the patch in half by determining the control points of a subpatch. The relationship of the patch to it's subpatches is that of a binary tree, where every patch division produces two subpatches which may themselves be subject to patch division. In one embodiment, the patch division unit is able to traverse the binary subdivision tree in three directions (parent to left-child, left-child to right-sibling, and right-sibling to parent) to minimize memory requirements. In this embodiment the patch division unit comprises a set of curve division units. An X-curve division unit is coupled to a patch buffer to receive current X coordinates for the set of control points for the current patch, and configured to convert the current X coordinates into new X coordinates for the control points of the new patch. A Y-curve division unit is coupled to the patch buffer to receive current Y coordinates for the set of control points for the current patch, and configured to convert the current Y coordinates into new Y coordinates for the control points of the new patch. A Z-curve division unit is coupled to the patch buffer to receive current Z coordinates for the set of control points for the current patch, and configured to convert the current Z coordinates into new Z coordinates for the control points of the new patch. Each of the curve division units is further configured to receive an operation type signal and configured to generate coordinates for (a) a left subpatch if the operation type signal indicates a left child operation, (b) a right subpatch if the operation type signal indicates a right sibling operation, and (c) a parent patch if the operation type signal indicates a parent operation.

There are provided a 3D-shape displaying program and an image processing apparatus which can display complicated three-dimensional objects by employing a distinctive data structure, and which allows the positional relationship between a specific point such as a character and a plane of a 3D-object to be easily grasped. A regular octahedron whose vertices are on one of the three-dimensional axes is used as a basic 3D-shape. Each of the eight planes of the regular octahedron is previously subdivided into a plurality of triangular regions, which are given specific ID numbers which can identify addresses in a memory. In the memory, a data storage area is previously secured for each ID number, where data such as a distance from the origin to each vertex of the triangle, a plane equation for the triangle, and a surface pattern are stored. Thus, for each triangle composing the basic regular octahedron, data for displaying the triangle is stored, so that it is easy to refer to the data on the basis of the ID numbers, and various 3D-shapes can be easily displayed by arbitrarily data alteration.

A process for efficiently drawing subdivision surfaces. The present invention operates within a computer system for visually displaying 3 dimensional (3D) surfaces on a display. The present invention pulls polygons from a polygon mesh of a 3D surface. The polygons are stored into a 2 dimensional array such that the vertices of the polygons occupy nodes of the 2 dimensional array and are readily accessed. The polygons are subsequently divided into a plurality of resulting polygons. The resulting polygons are then sent to a graphics pipeline, wherein the graphics pipeline renders the resulting polygons into a 3D image on the computer display.