×

Method of converting continuous three-dimensional geometrical representations of polygonal objects into discrete three-dimensional voxel-based representations thereof within a three-dimensional voxel-based system

  • US 4,987,554 A
  • Filed: 08/24/1988
  • Issued: 01/22/1991
  • Est. Priority Date: 08/24/1988
  • Status: Expired due to Term
First Claim
Patent Images

1. A method of converting a continuous 3-D geometrical representation of a 3-D polygon into a discrete set of connected voxels representing said 3-D polygon in 3-D discrete voxel space of a voxel-based system, each said voxel being specified by integer x, y and z coordinate values said 3-D polygon being defined by an edge list representing a closed sequence of edges, said edge list including edges being a 3-D straight line segment defined by first and second endpoints forming the vertices of said 3-D polygon, said vertices of said 3-D polygon specifying a plane equation of said 3-D polygon, said 3-D discrete voxel space being characterized by orthogonal x, y, and z coordinate directions, said method comprising the sequence of steps of:

  • (a) specifying a generalized coordinate system having orthogonal coordinate directions u, v and w, which form three principal planes u-v, u-2, and v-w, said 3-D discrete voxel space being characterized by said u, v and w coordinate directions, each said voxel being specified by integer u, v and w coordinate values, said u, v and w coordinate directions corresponding to said x, y and z coordinate directions in such a way that said polygon has a projection of greatest area on said u-v plane and has a coordinate direction extent of smallest value along said w coordinate direction, said approximate plane equation being specified by plane equation coefficient α

    , β and

    Γ

    of said generalized coordinate directions u, v and w, respectively, and said coordinate direction w being defined as the depth direction of said polygon in said generalized coordinate direction;

    (b) determining from said vertices, the minimum and maximum values of said u, v and w coordinate directions;

    (c) defining an integer decision variable for said w coordinate direction, first and second integer decision threshold, integer decision variable increments and integer depth increments along each of said u and v coordinate directions, said definitions of said integer variables, decision thresholds, decision variable increments and depth increments being based on said α

    , β and

    Γ

    plane equation coefficients;

    (d) determining the initial value for said coordinate direction value w for said vertex having said minimum value for said v coordinate direction;

    (e) for each said edge in said edge list, determining(i) the slope of said edge in said u-v plane based on said first and second end points of said edge, and(ii) the depth increment along said edge based upon said u-v slope determined in substep (i) and said integer depth increment along said u-coordinate direction;

    (f) ordering said edge list by ascending value of said v coordinate direction of said first endpoint; and

    (g) converting said continuous 3-D polygon into said discrete set of voxels by stepping along said coordinate directions u and v and using decisional logic process for determining the integer value of said coordinate direction w, said conversion employing said edge list, said slopes of said edges in said u-v plane, said depth increment along said edges, said integer decision variable, said first and second integer decision thresholds, and said integer depth increments along each of said u and v coordinate directions.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×