← Back to team overview

kicad-developers team mailing list archive

Re: Experiments and considerations for more layer


On 09/03/2013 02:24 PM, Lorenzo Marcantonio wrote:
On Tue, Sep 03, 2013 at 05:29:12AM -0600, Brian F. G. Bidulock wrote:
See my other note.  Just remember what layers things are on instead
of messing around with bitmasks.  So, when you place pin 1, you place
it in the cells occupied by its shape and clearance, and place it (by
reference) in the front, inner1, inner2, back copper, silk front, mask
front, assembly front and assembly back layer sets.

Now I got it. You keep a 'by layer' index of entities. It's a good
solution, I agree. However when loading/saving/editing a pad (or
computing the netlist) it's way more handy to have the list of the
layers a pad is on, so I'd keep it around in the pad (not necessarily
a bitmask, see other message).

It's all a matter of the interface. IMHO the biggest problem with the current storage are the DLISTs, that leak the internals of the model to every single file in the code. For instance, if I want to iterate over the tracks, I can't do anything else than:

for (TRACK *t = board->m_Track; t; t = t->Next() ) {...}.

The t->Next() leaks an implementation detail (a doubly linked list) into the interface. If somebody wants to replace that list with a spatially indexing container, he'll likely have a problem, and what's worse, he'll have to rewrite a huge pile of code that directly accesses the DLIST..., at least replacing the m_Track (or whatever else) with an iterator class having same interface as the DLIST:

for (BOARD::Iterator<TRACK> t = board->Iterate ( PCB_TRACE_T ); t; t = t.Next() ) {...}.

IMHO the first goal is to clean the non-model code of the references to the internals of the model. Then we are free to implement any sort of cell/tree/layer-set indexing in BOARD without having to change the interface.

For the P&S I also needed some sort of lightweight copying (I call it branching), that is creating lots of copies of the root model that are slightly changed wrs to the root (I use it for making the traces "springback" when the cursor is moved back and for comparing different optimization strategies). I learned that having links between items stored in the items makes such copying mechanism difficult to implement.

My experience after writing the P&S router is:
- restrict access to the model through Add, Remove, Replace methods and iterators (in my case QueryColliding/NearestObstacle). - store connectivity information in the container, not in the items (JointMap). This way it's possible to replace any set of segments/vias in the newer branch without having to modify the old ones or the parent node that hosts them. - copy - modify - replace instead of modify live thing. I know it's slower but at least in case of the P&S, the bottleneck is collision finding...


PS. about more than 64 layers - I attached an example flag set class. Of course it's not as fast as a bare int/int64 (4 assembly instructions instead of one/two), but it brings type safety and automatic serialization (it's just a demo written in 20 minutes, not a quality code).
 * KiRouter - a push-and-(sometimes)-shove PCB router
 * Copyright (C) 2013 CERN
 * @author Tomasz WÅ‚ostowski <tomasz.wlostowski@xxxxxxx>
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or (at your
 * option) any later version.

 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * General Public License for more details.

 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.or/licenses/>.

#ifndef __PNS_NODE_H
#define __PNS_NODE_H

#include <vector>

#include <boost/unordered_set.hpp>
#include <boost/optional.hpp>
#include <boost/smart_ptr.hpp>

#include <geometry/shape.h>
#include <geometry/shape_line_chain.h>
#include <geometry/shape_index.h>

#include "pns_item.h"
#include "pns_joint.h"

class PNS_LINE;
class PNS_SOLID;
class PNS_VIA;

using boost::shared_ptr;

		virtual int operator() ( const PNS_ITEM *a , const PNS_ITEM *b) = 0;

 * Holds an object colliding with another object, along with
 * some useful data about the collision.
	///> Item we search collisions with
	PNS_ITEM *head;
	///> Item found to be colliding with head 
	PNS_ITEM *item;

	///> Hull of the colliding item
	///> First and last intersection point between the head item and the hull of the 
	//// colliding item
	VECTOR2I ip_first, ip_last;
	///> ... and the distance thereof
	int dist_first, dist_last;

 * Class PNS_NODE
 * Keeps the router "world" - i.e. all the tracks, vias, solids in a hierarchical and indexed way. 
 * Features:
 * - spatial-indexed container for PCB item shapes
 * - collision search (with clearance checking)
 * - assembly of lines connecting joints, finding loops and unique paths
 * - lightweight cloning/branching (for recursive optimization and shove springback)

class PNS_NODE {

	typedef boost::optional<PNS_OBSTACLE> OptObstacle;
	typedef std::vector<PNS_ITEM *> ItemVector;
	typedef std::vector<PNS_OBSTACLE> Obstacles;
	typedef boost::optional<PNS_JOINT> OptJoint;

	~PNS_NODE ();

	///> Returns the expected clearance between items a and b.
	int GetClearance(const PNS_ITEM *a, const PNS_ITEM *b) const;
	///> Returns the pre-set worst case clearance between any pair of items
	int GetMaxClearance() const
		return m_maxClearance;

	void SetMaxClearance( int aClearance ) 
		m_maxClearance = aClearance;

	void SetClearanceFunctor (PNS_CLEARANCE_FUNC *aFunc)
		m_clearanceFunctor = aFunc;

	///> Finds items that collide with aItem and stores collision information in aObstacles.
	int QueryColliding( const PNS_ITEM* aItem, Obstacles& aObstacles, int aKindMask = PNS_ITEM::ANY, int aLimitCount = -1);

	///> Finds the nearest item that collides with aItem.
	OptObstacle NearestObstacle( const PNS_LINE *aItem, int aKindMask = PNS_ITEM::ANY);

	///> Checks if the item collides with anything else in the world, and returns it if so.
	OptObstacle CheckColliding ( const PNS_ITEM *aItem, int aKindMask = PNS_ITEM::ANY);

	///> Checks if two items collide [deprecated].
	bool CheckColliding( const PNS_ITEM *aItemA, const PNS_ITEM *aItemB, int aKindMask = PNS_ITEM::ANY);

	///> Hit detection
	int HitTest( const VECTOR2I& aPoint, int aLayer, std::vector<PNS_ITEM*> &aItems, int aHitLimit = -1);

	void Add(PNS_ITEM *aItem);
	void Remove(PNS_ITEM *aItem);
	void Replace(PNS_ITEM *aOldItem, PNS_ITEM *aNewItem);

	///> Creates a lightweight copy ("branch") of self. Note that if there are any branches
	///  in use, their parents must NOT be deleted.
	PNS_NODE *Branch();

	///> Assembles a line connecting two non-trivial joints the segment aSeg belongs to.
	PNS_LINE *AssembleLine(PNS_SEGMENT *aSeg);
	///> Dumps the contents and joints structure	
	void Dump(bool aLong = false);

	///> Returns the number of joints
	int JointCount() const
		return m_joints.size();

	///> Returns the lists of items removed and added in this branch, with respect
	///> to the root.	
	void GetUpdatedItems( ItemVector& aRemoved,  ItemVector& aAdded);

	///> Copies the changes from a given branch (aNode) to the root. Called on 
	///> a non-root branch will fail.
	void Commit (PNS_NODE *aNode);

	///> finds a joint at a given position, layer and nets
	const OptJoint FindJoint(const VECTOR2I &aPos, int aLayer, int aNet);

	///> finds all linest between a pair of joints. Used by the loop removal engine.
	int FindLinesBetweenJoints( PNS_JOINT& a, PNS_JOINT& b, std::vector<PNS_LINE *> &aLines );

	///> finds the joints corresponding to the ends of line aLine
	void FindLineEnds (PNS_LINE *aLine, PNS_JOINT& a, PNS_JOINT& b );

	///> finds all joints that have an (in)direct connection(s) (i.e. segments/vias) with the joint aJoint.
	void FindConnectedJoints( const PNS_JOINT& aJoint, std::vector<PNS_JOINT *> &aConnectedJoints );

	///> Destroys all child nodes. Applicable only to the root node.
	void KillChildren();


	struct obstacleVisitor;
	typedef boost::unordered_multimap<PNS_JOINT::HashTag, PNS_JOINT> JointMap;	
	typedef JointMap::value_type TagJointPair;

	/// nodes are not copyable
	PNS_NODE( const PNS_NODE& b);
	PNS_NODE &operator=(const PNS_NODE& b);
	///> tries to find matching joint and creates a new one if not found
	PNS_JOINT& touchJoint( const VECTOR2I& aPos, const PNS_LAYERSET& aLayers, int aNet );
	///> touches a joint and links it to an item
	void linkJoint( const VECTOR2I& aPos, const PNS_LAYERSET& aLayers, int aNet, PNS_ITEM *aWhere );

	///> unlinks an item from a joint
	void unlinkJoint( const VECTOR2I& aPos, const PNS_LAYERSET& aLayers, int aNet, PNS_ITEM *aWhere );
		///> helpers for adding/removing items

	void addSolid( PNS_SOLID *aSeg );
	void addSegment( PNS_SEGMENT *aSeg );
	void addLine( PNS_LINE *aLine );
	void addVia( PNS_VIA *aVia );
	void removeSolid( PNS_SOLID *aSeg );
	void removeLine( PNS_LINE *aLine );
	void removeSegment (PNS_SEGMENT *aSeg );
	void removeVia (PNS_VIA *aVia );

	void doRemove( PNS_ITEM *aItem );
	void unlinkParent ( );
	void releaseChildren ();
	bool isRoot() const 
		return m_parent == NULL;

	///> checks if this branch contains an updated version of the item from the root branch.
	bool overrides ( PNS_ITEM * aItem ) const 
		return m_override.find(aItem) != m_override.end();

	///> scans the joint map, forming a line starting from segment (current). 
	void followLine(PNS_SEGMENT *current, PNS_LINE *line, bool scanDirection, int& pos, int limit, VECTOR2I *corners);

	///> spatial index of all items
	///> hash table with the joints, linking the items. Joints are hashed by their
	///> position, layer set and net. 
	JointMap m_joints;

	///> node this node was branched from
	PNS_NODE *m_parent;

	///> root node of the whole hierarchy
	PNS_NODE *m_root;
	///> list of nodes branched from this one
	std::vector<PNS_NODE *> m_children;

	///> hash of root's items that are more recent in this node
	boost::unordered_set<PNS_ITEM *> m_override;

	///> worst case item-item clearance 
	int m_maxClearance;
	///> Clearance resolution functor
	PNS_CLEARANCE_FUNC *m_clearanceFunctor;


#include <cstdio>
#include <string>
#include <vector>
#include <bitset>

// CRTP-based FLAG base class
template<class Derived>
class FLAG {
		FLAG(const std::string& name)
			m_name = name;
			m_id = current_id++;
		static void List()
			typename std::vector<FLAG<Derived> *>::const_iterator i;
			printf("Supported flags:\n");
			for(i=m_flagList.begin(); i!= m_flagList.end();++i)
				printf("%d: %s\n",  (*i)->getId(), (*i)->getName().c_str());

		const std::string& getName() const { return m_name; }
		const int getId() const { return m_id; }
		static const std::string& getNameForId ( int id ) { return m_flagList[id]->getName(); }

		int count() const
			return current_id;

		static std::vector<FLAG<Derived> *> m_flagList;
		static int current_id;	
		std::string m_name;
		int m_id;

template <class FlagType, int SetSize> class FLAG_SET {
		FLAG_SET (){};
		void set ( const FlagType& f )
			m_set[f.getId()] = true;

		void clear ( const FlagType& f )
			m_set[f.getId()] = false;

		bool isSet( const FlagType& f ) const{
			return m_set[f.getId()];

		const FLAG_SET<FlagType, SetSize> operator | ( const FLAG_SET<FlagType, SetSize>& rhs ) const
		 FLAG_SET<FlagType, SetSize> rv;
		 rv.m_set = m_set | rhs.m_set;
		 return rv;

		const FLAG_SET<FlagType, SetSize> operator & ( const FLAG_SET<FlagType, SetSize>& rhs ) const
		 FLAG_SET<FlagType, SetSize> rv;
		 rv.m_set = m_set & rhs.m_set;
		 return rv;

		bool operator & ( const FlagType& f ) const 
			return m_set[f.getId()];

		bool operator[] (const FlagType f) const
			return m_set[f.getId()];

		const std::string format() const
			std::string rv = "(flag-set";
			for(int i = 0; i<SetSize; i++)
					rv += std::string(" ") + FlagType::getNameForId(i);
			rv += ")";
			return rv;

		std::bitset<SetSize> m_set;

#define DECLARE_FLAGSET(_classname, _set_classname, _maxsize) \
	class _classname : public FLAG<_classname> { \
	public: \
		_classname (const std::string& name): FLAG<_classname>(name) {}; \
	}; \
template<> \
	int FLAG<_classname>::current_id = 0; \
template<> \
	std::vector< FLAG<LAYER> *> FLAG<LAYER>::m_flagList = std::vector< FLAG < _classname > * >(); \
	typedef FLAG_SET <_classname, _maxsize> _set_classname;


static const LAYER LAYER_N_BACK ("Back");
static const LAYER LAYER_N_2 ("Cu-1");
static const LAYER LAYER_N_3 ("Cu-2");
static const LAYER LAYER_N_4 ("Cu-3");
static const LAYER LAYER_N_5 ("Cu-4");
static const LAYER LAYER_N_FRONT ("Front");

static const LAYER ADHESIVE_N_BACK  ("Adhesive-back");
static const LAYER ADHESIVE_N_FRONT  ("Adhesive-front");

	LAYER_SET layers, layers2, result;
	layers.set( LAYER_N_FRONT );
	layers.set( LAYER_N_BACK );
	layers.set( ADHESIVE_N_FRONT );
	layers.clear ( LAYER_N_BACK );

	layers2.set( LAYER_N_2 );
	printf("Layers: %s\n", layers.format().c_str() );

	if( layers & LAYER_N_FRONT )
		printf("Front Layer present.\n");
	result = layers | layers2;

	printf("OR result: %s\n", result.format().c_str() );


Follow ups