Multi-curve rendering modification apparatus and method

• US 5,940,083 A
• Filed: 04/01/1997
• Issued: 08/17/1999
• Est. Priority Date: 04/01/1997
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Broekhuijsen, Jerome A.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/831,393
• Time in Patent Office: 868 Days
• Field of Search: 345/441, 345/442, 345/443, 345/440, 345/133, 345/134, 345/135
• US Class Current: 345/442
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A multi-curve object may be created as a graph of nodes interconnected by edges or links. Each node may be represented by a data structure containing a curve characterization corresponding to a sub-sequence of points selected from a sequence represented by the multi-curve object. Each node may include reference pointers or other links indicating the edges or links between nodes in the graph. A selection key in each node data structure may represent an attribute of the curve segment characterized in the node. A single, universal error for all curve segments is a suitable selection criterion. A member compound curve representing the multi-curve object may be selected by including curve segments associated with all nodes that meet a user-selected selection criterion. A rendition of the member compound curve so created may be modified at will by changing the selection criterion. A recursive modification, rendition, un-rendering, and re-rendering procedure may be implemented to minimize rendering times. Only those curve-segments associated with nodes that have been selected for removal or addition to a member compound curve need to be affected by rendering and un-rendering processes. Thus, an image need not be completely un-rendered to be replaced by a very similar replacement image, only selected portions need be.

Claims

1. An apparatus for prescriptively and proscriptively, arbitrarily, selecting a compound curve representing a multi-curve object, the apparatus comprising:

a processor programmed to build a multi-curve object and to receive inputs to control rendition of a compound curve representing the multi-curve object;

an input device operably connected to the processor for providing the inputs controlling selection of curve segments to be composed into the compound curve;

an output device operably connected to the processor for providing a rendition of the compound curve; and

a memory device operably connected to the processor to store data structures comprising;

a sequence of points, subdividable into sub-sequences and corresponding to the multi-curve object,

a plurality of curve segments corresponding to the sub-sequences,

a selection criterion, and

a selection executable, executable by the processor to select, from the curve segments, selected curve segments to be composed into the compound curve in accordance with the selection criterion.

2. The apparatus of claim 1, wherein:

the output device is a display; and

the data structures further comprise a rendering executable effective to render the compound curve on the display.

3. The apparatus of claim 1, wherein the data structures further comprise:

a new selection criterion; and

a selection modification executable, executable by the processor to selectively re-use and replace each of the selected curve segments in accordance with the selection criterion and the new selection criterion.

4. The apparatus of claim 3, wherein:

the output device is a display; and

the selection modification executable is further effective to provide a new compound curve, comprising a re-used portion, selected from the compound curve, and a replacement portion, by un-rendering from the display a replaced portion of the compound curve in accordance with the selection criterion, and rendering on the display the replacement portion in accordance with the new selection criterion.

5. The apparatus of claim 1, wherein the data structures further contains a plurality of selection criteria for selecting multiple compound curves in accordance therewith.

6. The apparatus of claim 1 wherein the data structures further comprise a graph representing the multi-curve object.

7. The apparatus of claim 6, wherein the graph further comprises nodes, each node corresponding to a curve segment and containing:

a characterization of the curve segment;

;

a selection key reflecting a value to be used for a comparison;

a plurality of references for linking the node to other nodes.

8. The apparatus of claim 7, wherein the plurality of references link the node, serving as a parent node, to child nodes.

9. The apparatus of claim 7, wherein the selection key reflects an error corresponding to a fit of the curve segment to a corresponding sub-sequence.

10. The apparatus of claim 6, wherein the graph is a tree.

11. An article comprising a memory device storing data structures for use in association with execution by a processor for prescriptively and proscriptively, arbitrarily, selecting a compound curve representing a multi-curve object, the data structures comprising:

a creation executable, executable by the processor to build a multi-curve object;

an interaction executable for selecting a selection criterion;

the selection criterion;

a sequence of points, subdividable into sub-sequences and corresponding to the multi-curve object,

a plurality of curve characterizations, each corresponding to a curve segment and associated sub-sequence of the sequence;

a selection executable, executable by the processor to select, from the curve segments, included curve segments to be composed into the compound curve in accordance with the selection criterion.

12. The article of claim 11, wherein the selection criterion corresponds to an error of fit between a curve segment and associated sub-sequence.

13. The article of claim 11, wherein the data structures further comprise a rendering executable effective to render the compound curve on a display.

14. The article of claim 13, wherein the rendering executable further provides a new compound curve, comprising a re-used portion, selected from the compound curve, and a replacement portion, by un-rendering from the display a replaced portion of the compound curve in accordance with the selection criterion, and rendering on the display the replacement portion in accordance with the new selection criterion.

15. The article of claim 14, wherein the data structures further comprise:

a new selection criterion; and

a selection modification executable, executable by the processor to selectively re-use and replace each of the selected curve segments in accordance with the selection criterion and the new selection criterion.

16. The article of claim 11, wherein the data structures further comprise a graph representing the multi-curve object.

17. The article of claim 16, wherein the graph further comprises nodes, each node corresponding to a curve segment and containing:

a characterization of the curve segment;

a selection key reflecting a value to be used for a comparison;

a plurality of references for linking the node to other nodes.

18. The article of claim 17, wherein the plurality of references link the node, serving as a parent node, to child nodes.

19. The article of claim 17, wherein the selection key reflects an error corresponding to a fit of the curve segment to a corresponding sub-sequence.

20. The article of claim 16, wherein the graph is a tree.

21. A method for interacting with a multi-curve object, the method comprising:

providing a sequence of sample points;

identifying joints associated with the sequence, each joint corresponding to a sample point;

providing a node data structure for storing data reflecting a curve segment, selection key associated with the curve segment, and plurality of references;

providing a plurality of nodes, each node comprising an instantiation of the node data structure; and

providing a graph representing a multi-curve object and relating the plurality of nodes to one another according to links effected by the references.

22. The method of claim 21 wherein the selection key corresponds to an error.

23. The method of claim 22, wherein the error reflects an error of a fit of the curve segment to a sub-sequence of points selected from the sequence.

24. The method of claim 23, wherein the curve segment spans a path approximating the sub-sequence of sample points.

25. The method of claim 21, wherein the graph is a tree.

26. The method of claim 21, further comprising creating the multi-curve object to order the nodes in a hierarchy according to the selection key corresponding to each of the nodes.

27. The method of claim 26, wherein the hierarchy reflects a ranking of a selection key of a parent node with respect to a selection key of a child node.

28. The method of claim 26 wherein creating the multi-curve object is effected by a method selected from the group consisting of recursion and iteration.

29. The method of claim 21, wherein the selection key is an error reflecting a fit of a curve segment to a corresponding sub-sequence of points selected from the sequence.

30. The method of claim 21 further comprising:

traversing the multi-curve object to select a member compound curve representing the multi-curve object and corresponding to selected nodes, each corresponding to a selection key having a selection key value satisfying a selection criterion; and

rendering the member compound curve using selected data structures corresponding to the selected nodes.

31. The method of claim 30 wherein the traversing further comprises recursing.

32. The method of claim 31, wherein recursing comprises:

beginning a traversal at a primal root of the multi-curve object;

recursively identifying a node as a current node having a current selection key corresponding thereto,

if the current selection key is higher than the selection criterion, continuing the traversal by recursively designating as a current node each child node pointed to by the current node;

if the current selection key is not higher than the selection criterion, rendering the curve segment corresponding to the current node.

33. The method of claim 30 further comprising replacing the member compound curve with another member compound curve by:

selecting and keeping a re-used portion selected from the member compound curve and included in the other member compound curve,

identifying and un-rendering a replaced portion from the member compound curve, and

selecting and rendering a replacement portion of the other member compound curve, replacing the replaced portion.

34. The method of claim 33, wherein replacing further comprises:

providing a previous rendering criterion and a current rendering criterion,

selecting a high value corresponding to the greater of the previous and current rendering criteria,

selecting a low value corresponding to the lesser of the previous and current selection criteria,

traversing the multi-curve object to classify nodes corresponding to the re-used portion, the replaced portion, and the replacement portion, based on a relationship of the high and low values to selection keys corresponding to the nodes.

35. The method of claim 34 , wherein traversing further comprises:

beginning a traversal at a primal root of the multi-curve object;

recursively identifying a current node and a current selection key corresponding thereto,

if the current selection key is higher than the high value, continuing the traversal by recursively designating as a current node each child node pointed to by the current node;

if the selection key is not higher than the high value and is higher than the low value, recursively un-rendering curve segments corresponding to replaced nodes rooted at the current node and meeting the previous rendering criterion, and recursively rendering curve segments corresponding to replacement nodes rooted at the current node and meeting the current rendering criterion.

36. The method of claim 35 wherein recursively un-rendering further comprises:

designating the current node as a root of a subtree;

identifying a node as a current un-rendering node, the selection key corresponding thereto being identified as a current un-rendering selection key;

if the current un-rendering selection key is higher than the previous selection criterion, continuing the traversal by recursively designating as a current un-rendering node each child node pointed to by the current un-rendering node;

if the current un-rendering selection key is not higher than the previous selection criterion, un-rendering the curve segment corresponding to the current un-rendering node.

37. The method of claim 35 wherein recursively rendering further comprises:

designating the current node as a root of a subtree;

identifying a node as a current rendering node, the selection key corresponding thereto being identified as a current rendering selection key;

if the current rendering selection key is higher than the current selection criterion, continuing the traversal by recursively designating as a current rendering node each child node pointed to by the current rendering node;

if the current rendering selection key is not higher than the current selection criterion, rendering the curve segment corresponding to the current rendering node.

38. The method of claim 30, further comprising:

identifying a subtree rooted at a sub-root node and containing a subset of the selected nodes, the subset corresponding to a portion of the member compound curve;

locking the subtree to prevent replacement of the subset.

39. The method of claim 38, wherein locking further comprises:

identifying a plurality of root nodes corresponding to a plurality of sub-trees in the multi-curve object.

subdividing the multi-curve object into a plurality of multi-curve objects, each rooted at a respective root node of the plurality of root nodes.

40. The method of claim 21, wherein providing a graph is done iteratively.

41. The method of claim 40, wherein providing a graph further comprises:

identifying a node sequence comprising leaf nodes of the graph;

identifying a working sequence containing candidate nodes to be considered for inclusion as children of a next parent node;

identifying a consolidation number reflecting a number of child nodes to be linked with a parent node in the graph;

identifying sub-sequences, selected from the working sequence, each containing a number of nodes, the number corresponding to the consolidation number;

fitting a candidate curve segment to each of the sub-sequences;

determining an error corresponding to each candidate curve segment;

comparing the errors to select from the candidate curve segments a best curve segment corresponding to a least error of the errors and a best sub-sequence of the sub-sequences;

providing the next parent node storing a characterization of the best curve segment and a selection key corresponding to the least error, and linked to the child nodes selected from the best sub-sequence;

replacing, by the next parent node, in the working sequence, the nodes corresponding to the best sub-sequence;

returning to the identifying sub-sequences step, until the working set contains a single node, identifiable as a primal root node of the graph.

42. The method of claim 41, wherein the returning step further comprises:

returning to the identifying a consolidation number step, and continuing to the identifying sub-sequences step.

43. The method of claim 21, wherein providing a graph further comprises:

selecting all leaf nodes corresponding to a single parent node of the plurality of nodes;

comparing a parent error corresponding to the parent node to a least leaf error selected from the leaf errors corresponding to each, respective, selected, leaf node;

deleting the selected leaf nodes if the parent error is not greater than the least leaf error;

converting the parent node to a leaf node by providing termination values to replace the references linking the parent node to the selected leaf nodes.

44. The method of claim 21, further comprising:

identifying an attribute corresponding to at least one node;

identifying a root node corresponding to a subtree to which the at least one node pertains;

locking the subtree to prevent alteration of the attribute.