Method for partitioning, managing and displaying a collaboration space and interactive input system employing same

• US 9,471,957 B2
• Filed: 12/22/2014
• Issued: 10/18/2016
• Est. Priority Date: 03/28/2014
• Status: Active Grant

• Current Assignee: Smart Technologies ULC (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Smart Technologies ULC (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Xin, Min
• Primary Examiner(s): Buttram, Todd
• Application Number:
  US14/579,944
• Publication Number:
  US 20150279071A1
• Time in Patent Office: 666 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree

Abstract

A computerized method of managing a collaboration space comprises partitioning the collaboration space into a plurality of tiles in a tree structure; and associating each graphic object with a tile in said tree structure; said tile being the smallest tile in the tree structure that substantially accommodate said graphic object.

Claims

1. A method of controlling one or more memory devices of an interactive input system for storing a collaboration space, said collaboration space having one or more graphic objects therein, the method comprising:

partitioning the collaboration space into a plurality of tiles distributed at a plurality of levels in a tree structure representing a recursive subdivision of the collaboration space, the union of tiles at each level spanning the collaboration space, each tile at the same level having a same size, each tile at a level either being a leaf node or being subdivided into four smaller tiles at the next level;

determining one or more object tiles, each object tile being a tile of said plurality of tiles and associated with at least one of said one or more graphic objects; and

controlling a first memory of said one or more memory devices to store the one or more object tiles therein, each object tile being stored in said first memory as a separate record that may be independently accessed;

wherein the one or more object tiles are determined by;

for each graphic object,

determining a tile level L in the tree structure such that the size of each tile at said tile level L is larger than that of at least a predefined major portion of said graphic object;

determining an object tile as a tile at said tile level L that overlaps with at least the predefined major portion of said graphic object; and

associating the graphic object with the determined object tile in said tree structure.

2. The method of claim 1 wherein said object tile is the smallest tile in the tree structure that accommodates the entirety of said graphic object.

3. The method of claim 1 wherein said tile level L is determined as the tile level of the smallest tile that whose width is larger than or equal to the diameter of a bounding circle of the graphic object weighted by a first weighting factor C₁.

4. The method of claim 3 wherein said tiles are square tiles, and said determining a tile level L comprises:

iterating from the level having largest tile width to the level having the smallest tile width, to determine the tile level L having the largest tile width W that satisfies R>

C₂W, where R is the radius of the bounding circle of the graphic object, C₂ is a second weighting factor, and C₁=1/(4C₂).

5. The method of claim 4 wherein said second weighting factor C₂ is 0.25.

6. The method of claim 1 wherein determining the object tile as a tile in said tile level that overlaps with at least the predefined major portion of said graphic object comprises:

determining the object tile as a tile in said tile level that overlaps with the center of a bounding circle of said graphic object.

7. The method of claim 1 further comprising:

determining the position of a viewport, said viewport displaying a display image of at least a portion of said collaboration space;

determining a set of tiles in said tree structure required for rendering a display image to be displayed in said viewport; and

loading the determined set of tiles from the first memory device to a second memory device.

8. The method of claim 7 wherein determining a set of tiles comprises:

for each tile in the tree structure;

defining a zone for said tile as an area concentric with said tile with a dimension equal to that of said tile weighted by a third weighting factor C₃;

determining if the view port overlaps with said zone; and

marking the tile as a required tile of said set of tiles if the view port overlaps with said zone.

9. The method of claim 8 wherein said third weighting factor C₃ is 2.

10. An interactive input system for managing a collaboration space having one or more graphic objects, comprising:

a memory; and

a processing structure functionally coupled to said memory, said processing structure executing computer-executable code stored on a non-transitory computer readable storage device for;

partitioning the collaboration space into a plurality of tiles distributed at a plurality of levels in a tree structure representing a recursive subdivision of the collaboration space, the union of tiles at each level spanning the collaboration space, each tile at the same level having a same size, each tile at a level either being a leaf node or being subdivided into four smaller tiles at the next level;

determining one or more object tiles, each object tile being a tile of said plurality of tiles and associated with at least one of said one or more graphic objects; and

controlling a first memory area of said memory to store the one or more object tiles therein, each object tile being stored in said first memory area as a separate record that may be independently accessed;

wherein the one or more object tiles are determined by;

for each graphic object,

determining a tile level L in the tree structure such that the size of each tile at said tile level L is larger than that of at least the predefined major portion of said graphic object;

determining an object tile as a tile at said tile level L that overlaps with at least the predefined major portion of said graphic object; and

associating the graphic object with the determined object tile in said tree structure.

11. The interactive input system of claim 10 wherein said processing structure further executes computer-executable code stored on the non-transitory computer readable storage device for:

determining the position of a viewport, said viewport displaying a display image of at least a portion of said collaboration space;

determining a set of tiles in said tree structure required for rendering a display image to be displayed in said viewport; and

loading the determined set of tiles from the first memory area to a second memory area.

12. The interactive input system of claim 11 wherein said computer-executable code for determining a set of tiles comprises computer-executable code for:

for each tile in the tree structure;

defining a zone for said tile as an area concentric with said tile with a dimension equal to that of said tile weighted by a weighting factor;

determining if the view port overlaps with said zone; and

marking the tile as a required tile of said set of tiles if the view port overlaps with said zone.

13. A non-transitory, computer-readable storage device comprising computer-executable instructions for managing a collaboration space having one or more graphic objects, wherein the instructions, when executed by an interactive input system, cause a processor thereof to perform actions comprising:

partitioning the collaboration space into a plurality of tiles in a tree structure representing a recursive subdivision of the collaboration space, the union of tiles at each level spanning the collaboration space, each tile at the same level having a same size, each tile at a level either being a leaf node or being subdivided into four smaller tiles at the next level;

determining one or more object tiles, each object tile being a tile of said plurality of tiles and associated with at least one of said one or more graphic objects; and

controlling a first memory to store at least the one or more object tiles therein, each object tile being stored in said first memory as a separate record that may be independently accessed;

wherein the one or more object tiles are determined by;

for each graphic object,

determining a tile level L in the tree structure such that the size of each tile at said tile level L is larger than that of at least the predefined major portion of said graphic object;

determining an object tile as a tile at said tile level L that overlaps with at least the predefined major portion of said graphic object; and

associating the graphic object with the determined object tile in said tree structure.

14. The non-transitory, computer-readable storage device of claim 13 wherein said instructions, when executed, further cause the processor to perform actions comprising:

determining the position of a viewport, said viewport displaying a display image of at least a portion of said collaboration space;

determining a set of tiles in said tree structure required for rendering a display image to be displayed in said viewport; and

loading the determined set of tiles from the first memory area to a second memory area.

15. The non-transitory, computer-readable storage device of claim 14 wherein determining a set of tiles comprises:

for each tile in the tree structure;

defining a zone for said tile as an area concentric with said tile with a dimension equal to that of said tile weighted by a weighting factor;

determining if the view port overlaps with said zone; and

marking the tile as a required tile of said set of tiles if the view port overlaps with said zone.