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

Adaptive Maximum Subdivision Level for Spatial Subdivision Modellers

IP.com Disclosure Number: IPCOM000121556D
Original Publication Date: 1991-Sep-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 2 page(s) / 77K

Publishing Venue

IBM

Related People

Woodman, S: AUTHOR

Abstract

An algorithm is described for a graphics display spatial modeller which adapts the depth of subdivision to the best maximum level to suit the variety of models the system is required to process. The modeller becomes more efficient by recognizing and stopping when fruitless subdivision is foreseen. The process is self-regulating, carefully timed results are not required to establish maximum subdivision, the software adjusts the depth as it proceeds.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Adaptive Maximum Subdivision Level for Spatial Subdivision Modellers

      An algorithm is described for a graphics display spatial
modeller which adapts the depth of subdivision to the best maximum
level to suit the variety of models the system is required to
process.  The modeller becomes more efficient by recognizing and
stopping when fruitless subdivision is foreseen.   The process is
self-regulating, carefully timed results are not required to
establish maximum subdivision, the software adjusts the depth as it
proceeds.

      This description starts at a conventional modelling process
point before areas are shaded and when the model within a voxel gets
simplified to only one primitive.  If a pixel-sized voxel is reached
before this happens, a 'raycasting' algorithm is used to determine
which primitive it should shade for that pixel.  However, depending
on the efficiency of the implementation it is usually quicker to
raycast a 2 x 2 pixel-sized voxel (i.e., 4 calls to the raycaster)
than to subdivide this voxel into 8 smaller ones, have to classify
the model against each voxel, and probably end up having to raycast 3
out of 4 pixels anyway; the chances are that one sub-voxel might be
empty.  In an implementation it proved more efficient to start
raycasting at 8 x 8 or 4 x 4 areas.

      The best level to subdivide to will vary from implementation to
implementation, from model to model, and will even vary within
certain parts of the same model.  This problem is compounded when
drawing primitives for which classification is not accurate, for
instance, ellipsoid classification is difficult and therefore often
inaccurate. Two or more ellipsoids placed next to each other in a
model will result in a lot of subdivision to pixel level, only to
find that nearly every one of these pixel-sized voxels still contains
more than one ellipsoid and therefore has to be raycast....