1 | /************************************************************************
|
---|
2 |
|
---|
3 | MxEdgeFilter
|
---|
4 |
|
---|
5 | Copyright (C) 1998 Michael Garland. See "COPYING.txt" for details.
|
---|
6 |
|
---|
7 | $Id: MxEdgeFilter.cxx,v 1.1 2002/09/24 16:53:54 wimmer Exp $
|
---|
8 |
|
---|
9 | ************************************************************************/
|
---|
10 |
|
---|
11 | #include "stdmix.h"
|
---|
12 | #include "MxEdgeFilter.h"
|
---|
13 | #include "MxVector.h"
|
---|
14 |
|
---|
15 | MxEdgeFilter::MxEdgeFilter(MxStdModel *m0)
|
---|
16 | : heap(3*m0->vert_count()),
|
---|
17 | update_list(8)
|
---|
18 | {
|
---|
19 | m = m0;
|
---|
20 |
|
---|
21 | current_edge_count = original_edge_count = 0;
|
---|
22 | }
|
---|
23 |
|
---|
24 | void MxEdgeFilter::rank_and_update_edge(MxRankedEdge *edge)
|
---|
25 | {
|
---|
26 | float rank = compute_edge_rank(edge);
|
---|
27 |
|
---|
28 | edge->heap_key(rank);
|
---|
29 |
|
---|
30 | if( edge->is_in_heap() )
|
---|
31 | heap.update(edge);
|
---|
32 | else
|
---|
33 | heap.insert(edge);
|
---|
34 | }
|
---|
35 |
|
---|
36 | MxRankedEdge *MxEdgeFilter::create_edge(MxVertexID v1, MxVertexID v2,
|
---|
37 | bool will_rank)
|
---|
38 | {
|
---|
39 | MxRankedEdge *edge = new MxRankedEdge(v1, v2);
|
---|
40 | current_edge_count++;
|
---|
41 | if( will_rank )
|
---|
42 | rank_and_update_edge(edge);
|
---|
43 | return edge;
|
---|
44 | }
|
---|
45 |
|
---|
46 | void MxEdgeFilter::collect_star_for_update(MxVertexID v)
|
---|
47 | {
|
---|
48 | MxVertexList star;
|
---|
49 | m->collect_vertex_star(v, star);
|
---|
50 | for(uint i=0; i<star.length(); i++)
|
---|
51 | update_list.add(create_edge(v, star[i], false));
|
---|
52 | }
|
---|
53 |
|
---|
54 | void MxEdgeFilter::collect_edges()
|
---|
55 | {
|
---|
56 | MxVertexList star;
|
---|
57 |
|
---|
58 | for(MxVertexID i=0; i<m->vert_count(); i++)
|
---|
59 | {
|
---|
60 | star.reset();
|
---|
61 | m->collect_vertex_star(i, star);
|
---|
62 |
|
---|
63 | for(uint j=0; j<star.length(); j++)
|
---|
64 | if( i<star[j] )
|
---|
65 | {
|
---|
66 | create_edge(i, star[j]);
|
---|
67 | original_edge_count++;
|
---|
68 | }
|
---|
69 | }
|
---|
70 | }
|
---|
71 |
|
---|
72 | void MxEdgeFilter::initialize()
|
---|
73 | {
|
---|
74 | collect_edges();
|
---|
75 | }
|
---|
76 |
|
---|
77 | MxVertexID MxEdgeFilter::split_edge(MxRankedEdge *edge)
|
---|
78 | {
|
---|
79 | MxVertexID vnew = m->split_edge(edge->v1, edge->v2);
|
---|
80 |
|
---|
81 | collect_star_for_update(vnew);
|
---|
82 |
|
---|
83 | return vnew;
|
---|
84 | }
|
---|
85 |
|
---|
86 | bool MxEdgeFilter::filter1()
|
---|
87 | {
|
---|
88 | MxRankedEdge *edge = (MxRankedEdge *)heap.extract();
|
---|
89 | if( !edge ) return false;
|
---|
90 |
|
---|
91 | update_list.reset();
|
---|
92 |
|
---|
93 | filter_target_edge(edge);
|
---|
94 |
|
---|
95 | for(uint i=0; i<update_list.length(); i++)
|
---|
96 | rank_and_update_edge(update_list[i]);
|
---|
97 |
|
---|
98 | // Allow for the possibility that this edge will be modified
|
---|
99 | // and placed back in the heap with a new rank.
|
---|
100 | //
|
---|
101 | if( !edge->is_in_heap() )
|
---|
102 | delete edge;
|
---|
103 |
|
---|
104 | return true;
|
---|
105 | }
|
---|
106 |
|
---|
107 | bool MxEdgeFilter::filter(uint target)
|
---|
108 | {
|
---|
109 | while( current_edge_count < target )
|
---|
110 | {
|
---|
111 | if( !filter1() )
|
---|
112 | return false;
|
---|
113 | }
|
---|
114 |
|
---|
115 | return true;
|
---|
116 | }
|
---|
117 |
|
---|
118 | bool MxEdgeFilter::filter_above_rank(float rank)
|
---|
119 | {
|
---|
120 | while( heap.top() && heap.top()->heap_key() > rank )
|
---|
121 | {
|
---|
122 | if( !filter1() )
|
---|
123 | return false;
|
---|
124 | }
|
---|
125 |
|
---|
126 | return true;
|
---|
127 | }
|
---|
128 |
|
---|
129 | ////////////////////////////////////////////////////////////////////////
|
---|
130 | //
|
---|
131 | // Default implementations of rank & filter virtual functions. The
|
---|
132 | // effect of the defaults is to split edges based on squared length.
|
---|
133 | //
|
---|
134 | float MxEdgeFilter::compute_edge_rank(MxRankedEdge *edge)
|
---|
135 | {
|
---|
136 | return mxv_L2(m->vertex(edge->v1), m->vertex(edge->v2), 3);
|
---|
137 | }
|
---|
138 |
|
---|
139 | void MxEdgeFilter::filter_target_edge(MxRankedEdge *edge)
|
---|
140 | {
|
---|
141 | split_edge(edge);
|
---|
142 | }
|
---|