Object detection in complex and cluttered environments is central to a number of robotic and cognitive computing tasks. This work presents a generic, scalable and fast framework for concurrently searching multiple rigid texture-minimal objects using 2D image edgelet constellations. The method is also extended to exploit depth information for better clutter removal. Scalability is achieved by using indexing of a database of edgelet configurations shared among objects, and speed efficiency is obtained through the use of fixed paths which make the search tractable. The technique can handle levels of clutter of up to 70% of the edge pixels when operating within a few tens of milliseconds, and can give good detection rates. By aligning our detection within 3D point clouds, segmentation and object pose estimation within a cluttered scene is possible. Results of experiments on the challenging case of multiple texture-minimal objects demonstrate good performance and scalability in the presence of partial occlusions and viewpoint changes.