Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

EIGHT SIDED BOUNDING BOXES

IP.com Disclosure Number: IPCOM000026875D
Original Publication Date: 1994-Feb-28
Included in the Prior Art Database: 2004-Apr-06
Document File: 2 page(s) / 116K

Publishing Venue

Xerox Disclosure Journal

Abstract

In computer graphics, operations on a scene are often necessary when two objects in the scene intersect or overlap. To image the scene one must first determine which objects within it overlap so that they may be processed. The ease of determining if objects overlap depends on the shape of the objects, but can in general be quite expensive. For this reason one often performs a simple bounding-box test to rule out many of the cases before invoking the expensive test. Referring to the figure, which represents an image display 12, one generally forms rectangular box 20 aligned with the coordinate axes which enclose the object, 18. Two objects cannot overlap if their bounding boxes do not overlap. The test for overlapping boxes is a simple one; if the minimum of one box is greater than the maximum of the other box for either x or y direction, then they do not overlap. However, for some objects the bounding box can be much larger than the object and, therefore, will not provide as much assistance as desired in eliminating overlaps. The worst case object is a line segment slanted at 45 degrees with respect to the axes.

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 54% of the total text.

Page 1 of 2

XEROX DISCLOSURE JOURNAL

EIGHT SIDED BOUNDING BOXES Proposed Steven J. Harrington Classification

U.S. C1.358/453 Int. C1. H04n 1/40

Y'

2 r:,

XEROX DISCLOSURE JOURNAL - Vol. 19, No. 1 JanuaryIFebruary 1994 75

[This page contains 1 picture or other non-text object]

Page 2 of 2

EIGHT SIDED BOUNDING BOXES(Cont'd)

In computer graphics, operations on a scene are often necessary when two objects in the scene intersect or overlap. To image the scene one must first determine which objects within it overlap so that they may be processed. The ease of determining if objects overlap depends on the shape of the objects, but can in general be quite expensive. For this reason one often performs a simple bounding-box test to rule out many of the cases before invoking the expensive test. Referring to the figure, which represents an image display 12, one generally forms rectangular box 20 aligned with the coordinate axes which enclose the object, 18. Two objects cannot overlap if their bounding boxes do not overlap. The test for overlapping boxes is a simple one; if the minimum of one box is greater than the maximum of the other box for either x or y direction, then they do not overlap. However, for some objects the bounding box can be much larger than the object and, therefore, will not provide as much assistance as desired in eliminating overlaps. The worst case object is a line segment slanted at 45 degrees with respect to the axes.

This disclosure proposes octagonal bounding regions 24 composed of the intersection of two rectangular bounding boxes, one parallel to the axes (20) and one rotated 45 degrees (22). Box 20 forms the axes-aligned bounding rectangle in the same manner as in conventional bounding boxes by determining the maximum and minimum of x + y and x - y. This actually provides the coordinates of a bo...