The performance of constructive interference precoding (CIP) for multi-user multi-antenna (MU-MIMO) systems is governed by the structure of the constructive interference (CI) regions, yet this is overlooked in conventional constellation design. This work proposes the region-based constellation (RBC) model to lay the foundation for CIP constellation design. An RBC directly defines the mapping between messages and their feasible regions, instead of deriving them from an existing constellation. To provide insight for RBC design, we study the limitations of quadrature-amplitude-modulation (QAM)-based CIP. Analytical results show that the restrictive CI regions of QAM symbols are systematically misaligned with the objective-minimising sign pattern, resulting in a significant gap to the theoretical performance limit. From the perspective of improving sign alignment, two novel RBC schemes with non-convex feasible regions are proposed, namely mirrored-ends QAM (ME-QAM) and real-extended ME-QAM. A low-complexity algorithm is also developed for the resulting mixed-integer quadratic program, achieving a complexity comparable to QAM-based CIP. Simulation results with constellation sizes $\{16,64\}$ demonstrate up to $4$~dB signal-to-noise-ratio gain of the proposed schemes over QAM-based CIP. The proposed RBC model is also applicable to other systems with non-bijective modulation, representing a promising direction for future research.