CGAL users discussion list

[TroyMcLure <>]

Hi, i am trying to use the surface mesh simplification algorithms, with my
own cost and placement policies. But  i am experiencing some troubles cause
i don't understand what edge_collapse is doing inside. I need to understand
what edge_collapse is doing if i want to write my own policies. This is what
i understood by now, if someone can tell me if i am right or wrong, or tell
me something to make me uderstand...

(as far as i undestood ...)

edge_collapse needs a Polyhedron_3 concept object (i use
Polyhedron_3<SomeKernel,CGAL::Polyhedron_items_with_id_3>), a functor (for
the stop predicate, returng a bool), a functor (for the cost predicate,
returning optional<SomeKernel::FT>), a functor (for the placement policy,
returning an optional<SomeKernel::Point_3>)

(always as far as i undestood ...)

the functors returning an optional<> template class means that i can even
not return a value. for example, if i want to return 3.4 as the error (or
the cost) i have to do _ return optional<Kernel::FT>(Kernel::FT(3.4)), but
if i want to return nothing, i have to return optional<Kernel::FT>().
You can return nothing (a no value) as the cost, but u can NOT return
nothing as the placement otherwise u get an assertion error.

so the algorithm starts:

controls the surface is 2-mainifold, and it does not care if it has holes,
boundaries, or disconnected piecies of surfaces.

initialize some sort of priority queue, the elements are the edges(no
halfedges) and the priority is the increasing cost of collapsing. so, cost
of collapsing = 0.0002 has higher priority then cost of collapse = 0.2 . If
cost of collapse is absent, this mean the top of the queue, or else highest
priority.

starts the so called collecting phase. it cycles for every unoriented edge
taking the cost of collapsing (for the placement point you choose). it calls
for every edge, get_placement() and get_cost(). Put every edge in the
priority queue, putting the edges with cost absent at the top.

current_position_in_queue = the top of the queue

A: it starts a loop

B: it selects the edge at the current_position_in_queue, if the cost is
absent it just select the next edge in the queue,going down

C: it calls a Stop predicate to ask if it has to stop, if stop predicate
returns true, it quit from the loop and from the function

D: calls get_placement() to know where to put the point (it already knows
the cost)

E: checks if there are any topologically constraints (example the resulting
surface is not 2-mainifold). if there are topological problems it goes to
the next item in the queue, leaving (in the queue) the uncollapsable edge in
the same position as before (not sure about this), going back at step B: . 

F: collapse the edge. popping out from the queue the edge itself + other 2
edges (cause if u collapse an edge u collapse an edge and merge 2 edges into
1, so collapsing an edge means deleting 3 edges).

G: starts the refreshing costs fase. it means that i need to keep the
priority queue updated with the right values (the right costs). as far as i
understood, the updated edges are the ones incident (connected) to the new
vertex created by the collapse, and the edges connected to the vertices
connected to the beginning point. In other words, the edges connected to the
collapsed vertex, and the ones connected to those last edges . but it does
not uptade (calculate) the cost for every of those edges. it discards the
edges with absent cost (for sure). and it discard every edge above the
current selected edge in the queue? (not sure about this). So it makes a
list of the edges needing to be updated and call get_placement() and
get_cost() for each of them, but storing just the cost. So, changing the
cost, it changes even the position in the queue, most of the edges are going
down, but someone is going up... what happens if an edge is going up, above
the current selected prority (or cost). Is this edge forgotten? left in the
top of the queue?

H: end loop(starts again from B:)

someone knows how works this edge_collapse? 

i am doing my own policies and i am experiencing this problem. edge_collapse
does not choose (4 collapsing) the edges (collapsable) with the lowest cost.
i don't know why... i was thinking this: when an edge is updated , it
changes the position in the priority queue, and if it goes up above the
current selected cost, this edge (with lowest cost) will never be selected,
nor collapsed. But is just what i guess...



-- 
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/understanding-edge-collapse-tp3248855p3248855.html
Sent from the cgal-discuss mailing list archive at Nabble.com.