RESTITUTION DE SCENES TRIDIMENSIONNELLES DANS L'INFOGRAPHIE

RENDERING 3-D SCENES IN COMPUTER GRAPHICS

Abrégé français

Procédé de restitution d'une image bidimensionnelle comprenant les étapes consistant à analyser des surfaces orientées dans une direction de visualisation dans des séquences de lignes de balayage représentant des surfaces continues, à vérifier les valeurs de profondeur de ces surfaces par rapport à une position de visualisation et à laisser de côté sans les restituer les objets ou surfaces situés derrière la surface la plus en avant. Ces étapes ont pour effet d'augmenter l'algorithme de ligne de balayage afin de réduire la quantité de listes de traitement et de gestion de travail, pour ces faces, par exploitation du fait que la plupart des scènes tridimensionnelles sont construites à partir de surfaces continues faites de faces contiguës.

Abrégé anglais

A method of rendering a 2-D image includes the steps of analysingsurfaces facing a viewing direction into scanline sequences which
represent continuous surfaces, checking depth values of those surfaces relative to a viewing position and discarding without rendering those
objects or surfaces lying behind a foremost surface. This has the effect of extending the scanline algorithum to reduce the amount of work
managing and processing lists of faces by exploiting the fact that most 3-D scenes are constructed from continuous surfaces made up of
adjoining faces.

Revendications

6
CLAIMS
1. A method of rendering a 2-D image including the
steps of analysing surfaces facing a viewing direction
into scanline sequences which represent continuous
surfaces, checking depth values of those surfaces relative
to a viewing position and discarding without rendering
those objects or surfaces lying behind a foremost surface.
2. A method according to claim 1, including the steps
of obtaining coordinates of vertices of an or each object
of the image and coordinates of edges connecting each two
vertices, and defining faces within a set of connected
edges, the faces forming one or more of said surfaces.
3. A method according to claim 2, comprising the steps
of examining each face to determine whether the face is in
front of or behind the viewing position relative to the
viewing direction, and ignoring each face behind the
viewing position.
4. A method according to claim 2 or 3, comprising the
steps of scanning the image data by line and generating
first and second lists for each scanline, the first list
identifying those visible silhouette edges at the edge of
an object which become active on that scanline; the second
list identifying all other edges that become active.
5. A method according to claim 4, comprising the step
of identifying as first silhouette edges the silhouette
edges of an object first reached during scanning along a
scanline.
6. A method according to claim 5, comprising the steps
of generating a third list of active faces by the steps of
logging an active face as each new first silhouette edge
becomes active on the scanline, as other active edges are

7
noted from the second list, associating each of said other
active edges to one of the existing active faces in the
third list by updating the adjoining faces to indicate
that this edge is now their neighbour.
7. A method according to claim 6, comprising the step
of processing the active list of faces to find the visible
segments by dividing the scanline into runs, and enumerat-
ing the runs in order so as to sort an active list of
faces that span the run by nearest depth relative to the
viewing position.
8. A method according to claim 7, comprising the step
of, when there are no faces in a list for a run, generat-
ing a background image or colour for the associated
section of the scanline.
9. A method according to claim 7 or 8, wherein when the
furthest depth of the first face is greater than the
nearest depth of any further faces of the list, any such
further face is rendered, and the next run processed.
10. Imaging generating apparatus operative to render a
2-D image by a method according to any preceding claim.

Description

21 8~06
WO g5/27263 1 r~ 6
~enderirg 3-D sce es i~ Computer Graphics
This invention relates to 3-D computer graphics.~ -
Converting the inf ormation relating to a 3 -D image into a
2-D projection for a computer resuires an assessment of
which objects are visible, and which are hidden by others.
In doing this, it is convPnti~nAl to analyse all surfaces
of objects into smaller polygonal flat faces defined by
the coordinates of those f aces, of ten triangles . The
images for an An;r~t;r~n (e.g. for - tPr games), have to
be produced in real time, i . e . at a rate that gives the
impression of fairly smooth mo~G t.
The current techni~ues are as f ollows:
Z -Buf f er - A depth value is kept f or each image pixel .
Each face in the scene is rendered, and at each pixel the
new depth is compared with that already in the image. If
the new depth is nearer to the observer than the old, the
image pixel and depth are updated.
Painters algorithm - Each f ace in the scene is rendered
into the image, the faces are visited in the order
' furthest ' to ' nearest ' . This order may be generated by
sorting the faces at runtime, or by using a binary space
partition that was calculated offline.
Scanline Z ~3uf f er - The image is traversed in scanline
order. As each scanline is processed, the faces that
intersect this scanline are m~;ntA;nP~l in an active list.
A set of depth values are mA;ntA;nPIl, corrP~p~n~l;ng to the
pixels in a scanline. For each of the current active
faces, the section that intersects the current scanline is
rendered. At each pixel, a depth test is made, and the
image pixel is only updated if the new pixel is nearer.

2 ~ 85~
wo 95/27263 2 P~l,~.,,,'.'l ~46
Scanline - The image is traversed in scanline order. As
each scanline is processed, the faces that intersect this
scanline are maintained in an active list. The faces in
the active list are sorted along the horizontal axis by
the f irst scanline pixel which they intersect . This
sorted list is then processed to generate the sections of
faces that are frontmost. Each of these visi~le sections
is then rendered into the output image.
These techniques suffer from various disadvantages:
z Buf f er - A large amount of memory is consumed by main-
taining a depth value per image pixel. A test is
performed per pixel to find out if it is obscured.
Painters Algorithm - Fully correct sorting is time consum-
ing. An approximate sort can be used, but this leads to
visual artifacts. Binary Spaçe Partitions can be used to
accelerate the sorting, at the cost of making some or all
of the 3-D scene lln~ hAn~ hl.-
Scanline Z Buffer - Extra work is required to m~int~in the
active lists.
All the above techniques suffer from the problem that the
value for an image pixel may be generated several times,
once for every face that covers that pixel. Only the
' nearest ' value will survive into the output image . If
there are complex calculations needed to generate a
pixel ' s colour, the OEtra work can amount to a significant
portion of the overall processing time.
Scanline - Extra work is required to maintain and sort
lists of active faces.
The invention proposes a new technique which is designed
to speed up processing while saving processing power.

2 1 ~59~6
wo s~/27263 3 ~ /46
The invention proposes a method of rendering a 2-D image
which includes the steps o~ analysing surfaces facing the
camera into scanline sequences which represent l~nntinllrnlc
surf aces, -checking depth values of those surf aces and
discarding without rendering those objects or surfaces
lying behind a foremost surface.
This has the effect of ~t~nflin~ the scanline algorithm to
reduce the amount of work managing and processing lists of
~aces by exploiting the fact that most 3-D scenes are
constructed from cnnt;n~lmlq surfaces made up of adjoining
f aces .
The invention also extends to image generating apparatus
for rendering images by the method herein disclosed. The
apparatus includes the means necessary to carry out the
described method steps and may be in hardware or software
form or in any combination thereof. These means will be
apparent to the skilled reader from the teachings herein.
In order that the invention shall be fully understood, a
more detailed example of the technique will now be
described .
A 3-D scene is fully described by defining for each object
a series o~ faces (which together make up a surface)
employing coordinates which def ine the vertices, edges
connecting each two vertices, and f aces ~ormed within a
set of connected edges.
As a first step, the faces are P~rATninGtl to see whether the
camera is in front of or behind the face. If behind, then
Che face is away from the camera on the back of the object
and can be ignored.
The next step is to look in turn at all the faces which
are facing the camera. One imagines going around the edges

W0 95127263 ~ - r~ /46
of each face once with a pen, and keeping a count of how
many times one passes over each edge in doing so. Start-
ing from zero, any edge at the silho~:ette of an.object
will accumulate a count of 1; an edge between two faces
will count 2. Moreover, each edge is marked to say which
f ace is to right or lef t of it .
Using this information, two lists are built up for each
scanline~ A first list identifies those visible silhou-
ette edges which become active on that scanline; the
second lists all other edges that become active.
Now the scene is considered by scanline in turn. A third
list is prepared of active surfaces (i.e. sequences of
faces) . As each new lefthand silhouette edge becomes
active on the scanline, an active surface is logged. As
other active edges are noted from the second list, it is
added to one of the existing active surf aces in the third
list by updating the adj oining f aces to indicate that this
edge is now their neighbour . Thus, each active surf ace
(without regard to depth) is enumerated by starting at the
lefthand silhouette edge and then following the n~ighhollr
references hetween edges and faces until the righthand
edge is reached
This active lis~ of surfaces is now processed to find the
visible segments. The scanline is broken up into runs
(groups of pixels separated ~y left or right hand edges of
surf aces ) . These runs are enumerated in order . _During
this process, an active list of surfaces that span the run
iS r~inl~~;nP~ sorted by nearest depth.
I~ there are no surfaces in the list for a run, then the
section of the scanline is the background colour.
I~ the furthest depth of the first surface is greater than
the nearest depth of any fur~her surf aces on the list, than

21 ~59f36
W095/27263 5 r~ .. ,s~ l46
that surface is rendered, and the next run processed.
This technique, although some more memory is required,
makes it possible to perform bulk rej ection of obscured
parts o~ a scene, based on accepting whole sur~aces f ormed
by linked sequences of ~aces.
Thus, rrnri~lPrAhly less processing is required than simple
scanline techniques.
There are complex areas of a scene which do not le~d
themselves to this simplified treatment, for example where
a run has two or more surf aces of which the depth overlap .
This may require that such areas of the scene are treated
in more detail by conv~ntir~nA1 techniques. These areas
will reriuire more processing than usual and be slower, but
these are usually a minority of the scene and the savings
on the maj ority are greater .
The disclosures in Eiritish patent application no.
9406509.1, ~rom which this application claims priority,
and in the abstract accompanying this application are
incorporated herein by re~erence.