×

Methods and apparatus for manipulating polygons in a multidimensional space

  • US 6,701,306 B1
  • Filed: 01/31/2002
  • Issued: 03/02/2004
  • Est. Priority Date: 03/15/2000
  • Status: Expired due to Term
First Claim
Patent Images

1. A method for storing data in a computer to represent a plurality of “

  • n”

    sided geometric objects, said method comprising the steps of;

    generating segment data for each of a plurality of, “

    n”

    sided geometric objects, said segment data specifying “

    n”

    number of sides and including “

    n”

    vertices for a corresponding geometric object;

    generating a hierarchical tree, with k levels of nodes, to represent said “

    n”

    sided geometric objects, wherein each node is associated with one of said segment data, by;

    selecting a discriminating node as a parent node for a corresponding level;

    computing a discriminator dimension;

    selecting one of said “

    n”

    vertices based on said discriminator dimension for said discriminating node for use as a discriminator key for each of said k levels; and

    portioning nodes, not yet assigned to said hierarchical tree, into outside_child nodes and inside_child nodes based on a comparison between said discriminator key and segment data for a node under analysis and recursively portioning nodes into said outside_child nodes and said inside_child nodes for each of said k levels.

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