is the command pattern the only way to do undo/redo

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

is the command pattern the only way to do undo/redo

Shi Yan
hello folks,

did you have any experience of writing a half-edge data structure with
undo/redo feature?

i'm wondering if the command pattern is the only way to achieve undo and redo.

the command pattern packs each operation and its parameters as a
command and pushes the commands into a stack as executing them.

once the user needs to restore the data, the commands will be popped
up and executed in backwards.

aside from the function parameters, i also need to pack the half-edge
handle on which the operation is applied   with the command.

however after some operations, the half-edge handle could be invalid.
for example:

suppose i have an edge  E with endpoints A and B                     A
<--------E--------- B

the half-edge handle E points to A.

now i want to move A a little bit. so i create a "move command" which
contains the half-edge handle E pointing to A.

and then, i split this E in to two edges by a "split command"
                           A<---------K<------------B


now suppose i want to restore all my previous operations.

i first reconstruct the edge BA by connecting KA and BK   :
        A <-------------U-------------- B

and now i need to move point A back to the original position, but i
cannot do it, because i lost the half-edge handle E.

so how i'm suppose to do this?

thank you.
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: is the command pattern the only way to do undo/redo

Ben Supnik
Hi,

Shi Yan wrote:
> did you have any experience of writing a half-edge data structure with
> undo/redo feature?
>
> i'm wondering if the command pattern is the only way to achieve undo and redo.

It is not.  Another design that can be used is a copy-on-write model for
data.  I haven't used this with DCELs, but I have used it with a
hierarchial geometry model (e.g. polygon is points, area is polygon set,
etc.).

The naive alternative to commands is to copy the entire data model every
time you push an operation onto the undo stack - the limiting factor is
that it's really slow and really memory hungry.

The copy-on-write goes like this:

1. All objects in the system need GUIDs.

2. All links between objects must work in some persistent form - either
by using GUIDs instead of ptrs, or by being able to patch pointers after
an undo/redo.

3. Any operation that modifies an object first tells it to copy itself
to the current undo.  (This includes creation and destruction...for
creation we only need to note that we were created, since we can call
the default ctor.)

4. There are some rules for object lifetime:

- If we persist the creation of an object and the destruction in one
buffer, we can delete both.

- If we modify and then destroy (or modify twice) an object, we can
remember only the first change (since we don't have to save intermediate
state within an undo).

- If we destroy, then create an object, we can change this to a single
"modify".

There are a few big wins of working this way:

- No need to write per-operation undo code.  This can be a huge win if
the data model is simple but you do a lot of operations on it...this is
the scenario where I usually deploy the pattern.  The right, simplest
subset of your data is persisted automatically as you do operations code.

- If the operations code is asymetric, writing an undo for something
simple can get complex (for example, undo a remove-vertex).  But since
this is based on restoring the underlying data structure directly, it's
just a question of putting objects back together.

And the problems:

- Heavy cost of infrastructure between objects, since we need persistent
pointers.

For something like a DCEL half-edge (which has at least four pointers I
think) that's potentially a lot of overhead.

> however after some operations, the half-edge handle could be invalid.

Yes - this can be a problem for ANY undo-redo system if the reference to
the data model (from outside the data model) uses references that aren't
persistence-safe, like pointers or iterators. :-(

The copy-on-write system has the side effect of giving you persistent
handles, because it needs them internally to operate.  Typically
observers of this data model would use persistent references too so that
other code wouldn't become confused by an undo-redo.

> and now i need to move point A back to the original position, but i
> cannot do it, because i lost the half-edge handle E.

> so how i'm suppose to do this?

For what it's worth, if you had persistent references to the elements of
your DCEL, this case would "just work" because structurally the DCEL is
right, even if the handles are wrong.

One way to implement persistent handles on top of a ptr-based structure
would be:

- The "archive" (container of your entire data structure) contains a
hash table of GUID->CGAL handles.

- All persisted forms of the data for the purpose of undo write GUIDs.

- During an undo, restore the objects in two parts: first execute any
creation/destruction of objects needed for the undo, so that you have
the real final handles for all needed objects.  Then restore the
contents, looking up CGAL handles by GUID.

For CGAL's DCEL you might have to be careful to ensure that edges are
always persisted in pairs.  However I suspect that the "stream of
creates and destroys" that you observe as you run will match these
required semantics...CGAL won't do (via code that modifies the DCEL)
anything that proves to be illegal later.

cheers
bEn


--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: [hidden email]
Developer mailing list: [hidden email]
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: is the command pattern the only way to do undo/redo

Shi Yan
thanks Ben.


i guess it is not easy to implement. i think the most practical way is
to maintain a hash table and give each geometry primitive (vertex,
half-edge, facet) an unique id.

each Euler operation will be recorded by the undo stack as an operator
and the unique id it was applied on.


i also thought about an another option. how about i write a memory
pool by implementing my own new and delete operators.
the memory pool holds the entire geometry.
 and i can maintain a command system onto the memory pool. in this
way, no matter how complicated a half-edge Euler operator is,
eventually it is a set of modify/allocate/release operations on the
memory pool. therefore i can only try to restore the memory pool with
commands like allocate, release and modify.


i'm just wondering how do those commercial software solve undo and
redo problems. this should be a very common issue facing by any
sophisticated program. but i really can't find any article on this.


On Tue, Jul 1, 2008 at 6:42 AM, Ben Supnik <[hidden email]> wrote:

> Hi,
>
> Shi Yan wrote:
>>
>> did you have any experience of writing a half-edge data structure with
>> undo/redo feature?
>>
>> i'm wondering if the command pattern is the only way to achieve undo and
>> redo.
>
> It is not.  Another design that can be used is a copy-on-write model for
> data.  I haven't used this with DCELs, but I have used it with a hierarchial
> geometry model (e.g. polygon is points, area is polygon set, etc.).
>
> The naive alternative to commands is to copy the entire data model every
> time you push an operation onto the undo stack - the limiting factor is that
> it's really slow and really memory hungry.
>
> The copy-on-write goes like this:
>
> 1. All objects in the system need GUIDs.
>
> 2. All links between objects must work in some persistent form - either by
> using GUIDs instead of ptrs, or by being able to patch pointers after an
> undo/redo.
>
> 3. Any operation that modifies an object first tells it to copy itself to
> the current undo.  (This includes creation and destruction...for creation we
> only need to note that we were created, since we can call the default ctor.)
>
> 4. There are some rules for object lifetime:
>
> - If we persist the creation of an object and the destruction in one buffer,
> we can delete both.
>
> - If we modify and then destroy (or modify twice) an object, we can remember
> only the first change (since we don't have to save intermediate state within
> an undo).
>
> - If we destroy, then create an object, we can change this to a single
> "modify".
>
> There are a few big wins of working this way:
>
> - No need to write per-operation undo code.  This can be a huge win if the
> data model is simple but you do a lot of operations on it...this is the
> scenario where I usually deploy the pattern.  The right, simplest subset of
> your data is persisted automatically as you do operations code.
>
> - If the operations code is asymetric, writing an undo for something simple
> can get complex (for example, undo a remove-vertex).  But since this is
> based on restoring the underlying data structure directly, it's just a
> question of putting objects back together.
>
> And the problems:
>
> - Heavy cost of infrastructure between objects, since we need persistent
> pointers.
>
> For something like a DCEL half-edge (which has at least four pointers I
> think) that's potentially a lot of overhead.
>
>> however after some operations, the half-edge handle could be invalid.
>
> Yes - this can be a problem for ANY undo-redo system if the reference to the
> data model (from outside the data model) uses references that aren't
> persistence-safe, like pointers or iterators. :-(
>
> The copy-on-write system has the side effect of giving you persistent
> handles, because it needs them internally to operate.  Typically observers
> of this data model would use persistent references too so that other code
> wouldn't become confused by an undo-redo.
>
>> and now i need to move point A back to the original position, but i
>> cannot do it, because i lost the half-edge handle E.
>
>> so how i'm suppose to do this?
>
> For what it's worth, if you had persistent references to the elements of
> your DCEL, this case would "just work" because structurally the DCEL is
> right, even if the handles are wrong.
>
> One way to implement persistent handles on top of a ptr-based structure
> would be:
>
> - The "archive" (container of your entire data structure) contains a hash
> table of GUID->CGAL handles.
>
> - All persisted forms of the data for the purpose of undo write GUIDs.
>
> - During an undo, restore the objects in two parts: first execute any
> creation/destruction of objects needed for the undo, so that you have the
> real final handles for all needed objects.  Then restore the contents,
> looking up CGAL handles by GUID.
>
> For CGAL's DCEL you might have to be careful to ensure that edges are always
> persisted in pairs.  However I suspect that the "stream of creates and
> destroys" that you observe as you run will match these required
> semantics...CGAL won't do (via code that modifies the DCEL) anything that
> proves to be illegal later.
>
> cheers
> bEn
>
>
> --
> Scenery Home Page: http://scenery.x-plane.com/
> Scenery blog: http://xplanescenery.blogspot.com/
> Plugin SDK: http://www.xsquawkbox.net/xpsdk/
> X-Plane Wiki: http://wiki.x-plane.com/
> Scenery mailing list: [hidden email]
> Developer mailing list: [hidden email]
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>



--
Dept. of Computer Science
University of California, Davis
Homepage:http://wwwcsif.cs.ucdavis.edu/~yans/
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

on oriented mesh

dfwang
Dear CGALers,

How to generate an oriented mesh from an non-oriented mesh in CGAL?

Thanks in advance.

Best wishes,
Vincent
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

inside and outside judgement for a closed mesh

dfwang
Dear CGALers,

Given a genus-0 closed mesh, how to judge a point is inside of the mesh or
not in CGAL?

Any comments are welcome!

Best wishes,
Vincent

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: inside and outside judgement for a closed mesh

andreas.fabri
dfwang wrote:
> Dear CGALers,
>
> Given a genus-0 closed mesh, how to judge a point is inside of the mesh
> or not in CGAL?
>
> Any comments are welcome!
>
> Best wishes,
> Vincent


Hi Vincent,

You can read it into a 3D Nef Polyhedron and then perform the test
http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/contents.html#part_VI

andreas
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: inside and outside judgement for a closed mesh

Pierre Alliez
if you want to query this many times and need efficiency, you can as
well launch a ray from the query point and count the number of
intersections.

the opcode library is very efficient for such collision query - but you
can assemble a CGAL version of it as well.

Andreas Fabri a écrit :

> dfwang wrote:
>> Dear CGALers,
>>
>> Given a genus-0 closed mesh, how to judge a point is inside of the
>> mesh or not in CGAL?
>>
>> Any comments are welcome!
>>
>> Best wishes,
>> Vincent
>
>
> Hi Vincent,
>
> You can read it into a 3D Nef Polyhedron and then perform the test
> http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/contents.html#part_VI
>
> andreas
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss