Browse Prior Art Database

# Fast Shadow Generation Algorithm Using Space Subdivision

IP.com Disclosure Number: IPCOM000036192D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 53K

IBM

## Related People

Doi, A: AUTHOR [+2]

## Abstract

This article proposes a fast shadow generation algorithm using space subdivision. Space is divided into 6 segments and every polygon in the scene is determined whether it is the self-shadows or the projected shadows in each segment. The method is effective for rapid generation of realistic half-tone images with shadows. Algorithm

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 3

Fast Shadow Generation Algorithm Using Space Subdivision

This article proposes a fast shadow generation algorithm using space subdivision. Space is divided into 6 segments and every polygon in the scene is determined whether it is the self-shadows or the projected shadows in each segment. The method is effective for rapid generation of realistic half-tone images with shadows. Algorithm

We assume that the data model is a polygonal model, and each polygon has appropriately oriented. Explanation of each step follows: 1) Space Subdivision

An imaginary cube is created at the center of a point light source, and we divide the cube into 6 quadrangular pyramids (Fig. 1(a)). Each face of the cube becomes a virtual screen on which polygons can be projected. For a spotlight source, the cube does not need to be divided (Fig. 1(b)). We suppose that the spotlight is enclosed by a quadrangular pyramid. When the light is parallel, we place the virtual screen in a suitable position and project polygons onto it.

Background surfaces for a point light source are eliminated in this step. The following steps are processed on each quadrangular pyramid.

(Image Omitted)

2) Projection to Virtual Screen

Each polygon is projected on the virtual screen (Fig. 2), and the bounding box values (Xmin, Ymin, Xmax, Ymax) on the virtual screen are then calculated simultaneously (Fig. 3). 3) Bounding Box Test

Using the bounding box test, we eliminate unnecessary polygons, which do not cast shadows or which are themselves shadowed. 4) Check for Polygon Edge Intersections

We check for intersections of the edges of all polygons that survive the bounding box test. If an edge intersects another, we calculate the distance from eye-point, we call "depth", at the intersection point (Fi...